Information Based Complexity Applied to Optimal Recovery of the 2 1/2-D Sketch

Kender, John R.; Lee, David; Boult, Terrance E.

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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-170-85
Published Here
November 1, 2011