An Algebraic Approach to Surface Reconstruction from Gradient Fields

Shape from shading and photometric stereo estimate a gradient field that must be integrated to recover the surface. Least-squares methods, including Poisson integration and the Frankot-Chellappa algorithm, can distribute local errors across the surface and smooth away features.

Two observations motivate the algebraic approach. An N × N image has N² surface values but 2N² gradient observations, so not every gradient is required for integration. If erroneous gradients can be identified, the remaining gradients can be used, or the erroneous values can be recovered.

Second, curl carries information about errors in the measured field. Least-squares reconstruction uses its divergence but does not use curl to identify erroneous gradients. The proposed method uses curl to estimate a residual field and integrability constraints to recover the corrected gradients.

Let A₁ be the true gradient field and A₂ the measured, non-integrable field. A least-squares result A₃ has the same divergence as A₂ and zero curl. Instead, we model A₂ as A₁ plus a residual and estimate that residual from curl.

1. Compute loop curl. Evaluate four-pixel square loops. Non-zero curl identifies a loop containing erroneous gradients and a non-zero residual.
2. Form the linear system. Write the loop equations as Ax = b, with x representing the residual gradients.
3. Check connectivity. Remove edges corresponding to the erroneous gradients. The system can be solved when the remaining graph is connected. If it has n components, the rank deficit is n − 1.
4. Reconnect the graph. Assign weights to edges and choose a minimum-weight set of n − 1 connecting edges. Form the system again for the remaining broken edges and solve for the residual.
5. Integrate the corrected field. Subtract the estimated residual from the measured gradient field, then integrate to obtain the surface.

Several important problems in computer vision such as Shape from Shading (SFS) and Photometric Stereo (PS) require reconstructing a surface from an estimated gradient field, which is usually non-integrable, i.e. has non-zero curl. We propose a purely algebraic approach to enforce integrability in the discrete domain.

We first show that enforcing integrability can be formulated as solving a single linear system Ax = b over the image. In general, this system is under-determined. We show conditions under which the system can be solved and a method to get to those conditions based on graph theory. The proposed approach is non-iterative, has the important property of local error confinement and can be applied to several problems. Results on SFS and PS demonstrate the applicability of our method.

For improved reconstruction algorithms, see What is the Range of Surface Reconstructions from a Gradient Field? · ECCV 2006.