Enforcing integrability by error correction using ℓ1-minimization

TitleEnforcing integrability by error correction using ℓ1-minimization
Publication TypeConference Papers
Year of Publication2009
AuthorsReddy D, Agrawal A, Chellappa R
Conference NameComputer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on
Date Published2009/06//
Keywords-, algebra;lscr<sub>0</sub>, algebra;minimisation;, analogy;integrability;least, compressed, correction;gradient, equivalence;lscr<sub>1</sub>-minimization;noise-outlier;surface, estimation;gradient, field, integration;gradient, lscr<sub>1</sub>, manipulation;graph, methods;graph, reconstruction;error, reconstruction;linear, sensing;error, squares;linear, theory;image

Surface reconstruction from gradient fields is an important final step in several applications involving gradient manipulations and estimation. Typically, the resulting gradient field is non-integrable due to linear/non-linear gradient manipulations, or due to presence of noise/outliers in gradient estimation. In this paper, we analyze integrability as error correction, inspired from recent work in compressed sensing, particulary lscr0 - lscr1 equivalence. We propose to obtain the surface by finding the gradient field which best fits the corrupted gradient field in lscr1 sense. We present an exhaustive analysis of the properties of lscr1 solution for gradient field integration using linear algebra and graph analogy. We consider three cases: (a) noise, but no outliers (b) no-noise but outliers and (c) presence of both noise and outliers in the given gradient field. We show that lscr1 solution performs as well as least squares in the absence of outliers. While previous lscr0 - lscr1 equivalence work has focused on the number of errors (outliers), we show that the location of errors is equally important for gradient field integration. We characterize the lscr1 solution both in terms of location and number of outliers, and outline scenarios where lscr1 solution is equivalent to lscr0 solution. We also show that when lscr1 solution is not able to remove outliers, the property of local error confinement holds: i.e., the errors do not propagate to the entire surface as in least squares. We compare with previous techniques and show that lscr1 solution performs well across all scenarios without the need for any tunable parameter adjustments.