ECCV 2006 · Oral presentation Surface reconstruction
What is the Range of Surface Reconstructions from a Gradient Field?
The idea
One gradient field.
A range of surfaces.
Gradient integration need not produce just one least-squares reconstruction. A generalized equation connects Poisson integration, robust estimation, regularization, and diffusion. Changing how gradients are weighted provides a way to balance smoothness, robustness, and preservation of surface features.
01 / Results
Preserve salient features while discounting noise
Reconstruction comparisons on a synthetic Ramp-Peaks surface and on gradients estimated by photometric stereo for Mozart, vase, and flowerpot. The diffusion and α-surface methods recover salient features while reducing the influence of noise.
Why gradient
integration?
Reconstruction from gradient fields is important in photometric stereo, shape from shading, mesh smoothing, Retinex, high dynamic range compression, phase unwrapping, image editing, matting, and fusion. Gradient-domain algorithms manipulate an image’s gradient field and obtain the final image through 2D integration. In photometric stereo and shape from shading, the surface is similarly recovered by integrating estimated surface gradients.
For an N × N grid, the space of integrable gradient fields has dimension N² − 1. The framework derives a meaningful family of reconstructions from this high-dimensional space. Least-squares Poisson integration and the Frankot-Chellappa algorithm use isotropic weights; varying the weights spatially and by direction allows discontinuities and salient features to be preserved.
The proposed family includes α-surfaces with binary weights, M-estimators and edge-preserving regularization with continuous weights, and diffusion based on an affine transformation of the gradient field.
General
framework
Let Z be the desired surface and (p, q) the given gradient field. Consider an error functional of the following form; the formulation can also be generalized to higher-order derivatives.
The Euler–Lagrange equation gives the main reconstruction equation:
In the least-squares Poisson case, the four functions reduce to Zx, Zy, p, and q. Changing f₁, f₂, f₃, and f₄ produces the different solutions shown below.
A Poisson solver uses a spatially invariant Laplacian kernel 
. The equation is LZ = u, where u is the divergence of the given gradient field and L is the Laplacian matrix obtained from .
Assigning different weights to the gradients changes this to a weighted kernel 
and a weighted Laplacian matrix Lb for binary weights or Lw for continuous weights. Both allow individual weights for x and y gradients.
An affine transformation using a diffusion tensor D leads to the diffusion-based Laplacian LD, analogous to anisotropic diffusion for edge-preserving smoothing. Changing the anisotropy of the gradient weights produces different feature-preserving reconstructions.
α-surfaces
The α-surface algorithm applies the idea of robust estimation, as in RANSAC, to gradient integration. Estimating a surface is analogous to fitting a line to noisy 2D points: even one outlier can skew a least-squares solution. Robust estimation instead identifies and uses an inlier set.
To apply this idea, we need the minimum number of gradients required for integration. A line requires two points and a plane requires three. On an N × N grid, there are 2N² gradient observations and N² surface values. The minimum set for integration contains N² − 1 gradients forming a spanning tree of the underlying planar graph.
In this graph, nodes are surface values and horizontal and vertical edges are x and y gradients. Integration recovers node values from edge values. A spanning tree is the smallest connected configuration that reaches every node.
Brute-force RANSAC is impractical because the number of spanning trees grows exponentially with the number of nodes. The method first fixes a tree by assigning weights to gradients and finding a minimum spanning tree (MST), analogous to choosing an initial pair of points for a line fit.
The parameter α sets the accepted tolerance for noise. Starting with that tree, additional gradients are accepted as inliers when they lie within the tolerance. At α = 0, only the initial spanning-tree gradients are used. Increasing α includes more gradients; at sufficiently large α, all gradients become inliers and the solution approaches least squares. This traces a path through reconstruction space, trading robustness against smoothness.
In the videos below, the initial MST uses gradient magnitude as edge weights. Small α rejects outliers but leaves a noisier surface because not all inliers are used. Large α produces a smoother least-squares-like surface. In Ramp-Peaks, outlier distortion begins at α = 2.7653. In the face example, the right-cheek/background discontinuity is smoothed out at α = 0.8203.
Face reconstruction video (AVI) · Ramp-Peaks reconstruction video (AVI)
Discussion and
future work
The best reconstruction algorithm for a particular application remains an open problem. In the experiments described here, α-surfaces and diffusion generally outperformed the other approaches. The explored family represents meaningful solutions likely to be close to the true surface; it does not span every possible reconstruction in the N² − 1 dimensional space.
Further solutions may arise from higher-order derivatives, and some may fall outside this framework. Each proposed approach may itself contain useful families: for example, coherence-preserving tensors could replace the edge-preserving diffusion tensor used here. The solutions also omit the ∂E/∂Z term, which could incorporate control-point information in photometric stereo.
Abstract
We propose a generalized equation to represent a continuum of surface reconstruction solutions of a given non-integrable gradient field. We show that common approaches such as Poisson solver and Frankot-Chellappa algorithm are special cases of this generalized equation. For an N × N pixel grid, the subspace of all integrable gradient fields is of dimension N² − 1. Our framework can be applied to derive a range of meaningful surface reconstructions from this high dimensional space.
The key observation is that the range of solutions is related to the degree of anisotropy in applying weights to the gradients in the integration process. While common approaches use isotropic weights, we show that by using a progression of spatially varying anisotropic weights, we can achieve significant improvement in reconstructions.
We propose (a) α-surfaces using binary weights, where the parameter α allows tradeoff between smoothness and robustness, (b) M-estimators and edge preserving regularization using continuous weights and (c) diffusion using affine transformation of gradients. We provide results on photometric stereo, compare with previous approaches and show that anisotropic treatment discounts noise while recovering salient features in reconstructions.