1985 Reports
Information Based Complexity Applied to Optimal Recovery of the 2 1/2-D Sketch
In this paper, we introduce the information based complexity approach to optimal algorithms as a paradigm for solving image understanding problems, and obtain the optimal error algorithm for recovering the "2 1/2-D Sketch" (i.e. a dense depth map) from a sparse depth map. First, we give a interpolation algorithm that is provably optimal for surface reconstruction; furthermore the algorithm runs in linear time. Secondly, we show that adaptive information (i.e. the intelligent and selective determination of where to sample next, based on the values of previous samples) can not improve the accuracy of reconstruction. Third, we discuss properties of an implementation of the algorithm which make it very amenable to parallel processing, and which allow for point-wise determination of surface depth without the necessity for global surface reconstruction. We conclude with some remarks on a serial implementation.
Subjects
Files
-
cucs-170-85.pdf application/pdf 1.11 MB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-170-85
- Published Here
- November 1, 2011