Enforcing Integrability Constraint for
Surface Reconstruction Using Factor Graphs
Nemanja Petrovic, Ira Cohen
Accurate calculation of three dimensional shape of an object remains the ultimate goal of computer vision. We introduce a new method for shape reconstruction by integration of slope gradient maps. The essence of the new approach is the strict enforcement of surface integrability constraint via belief propagation in the graphical model. Graphical model is used to infer the values of true slope gradients given their noisy observations, and the constraints that hold for the valid surface. Graphical model is selected in such a way to extract information from underlying slope gradient estimators, utilize surface integrability constraint, and produce surface that is smooth, yet correct.
What is the Problem We are trying to Solve?
A class of vision algorithms estimate the surface of objects from a single or multiple images by estimating the first order partial derivatives of the height of the surface.
Shape from Shading (SFS) uses a single image of a surface using knowledge of the light source position, albedo and position of the camera. The integrability constraint is used in optimization to make the problem well posed. The main algorithms for SFS were described by Horn and Brooks (1986) and further explored by Frankot and Chellappa (PAMI88). Horn and Brooks used an iterative variational approach to solve for the first order partial derivative, not strictly enforcing the integrability constraint, but using it as a penalty in the minimization function. Frankot and Chellapa use orthogonal projection to the subspace of valid smooth surfaces at each iteration of the Horn and Brooks algorithm. Although their algorithm does result in a valid smooth surface, it might not be the best choice of smooth surface representing the original one.
In Photometric stereo (PMS), the integrability constraint is not used at all. At least three images are taken of the object with known (or estimated) light sources. In the basic algorithm, the surface normals are estimated using Least-Square solution (Woodham 1980), and no global information is used at all in the estimation. In more recent work, interreflectance between object surfaces are also taken into account, and the solution becomes more complex. For example, Woodham and his team (1999) use Neural networks to account for concave objects, and produce improved results. The integrability of the surface is not taken into account though in this minimization problem, and the surface might not be a valid smooth surface.
The following figure illustrates the basic image formation process:
In this figure we assume that the image plane is directly above the surface. This can be relaxed, as long as we know the direction to the surface. A pixel I(x,y) is proportional to the dot product between the light source direction and the surface normal at point (x,y).
From estimates of N(x,y) we can get the first order partial derivatives of the height:
The surface height at point (x,y) can be reconstructed by integrating the partial derivatives along ANY path from point (x0,y0) to point (x,y). For a smooth surface, the integrability constraint means that no matter what path we choose, we still get the same height for point (x,y). Formally this means:
What are Factor Graphs?
Factor graphs are graphs that visualize the factoring of global functions into a product of local function, hence simplifying a possibly complicated functional form between many variables. Factor graphs have been used successfully in a number of applications ranging from turbo-coding, phase unwrapping and more. A number of known signal processing and artificial intelligence algorithms, such as Fast Fourier Transform, belief propagation in Bayesian networks, the Vitterbi algorithm and Kalman filtering, can be solved using the sum-product algorithm of an appropriate factor graph.
How does belief propagation using Factor graphs help us to solve the problem of surface reconstruction?
We can look at the height map as a 2-D grid. Each vertice on the grid is the pixel location on the surface. The first order partial derivative is assumed to be the difference between two neighboring vertices. These derivatives are what we are trying to estimate, and we treat them as hidden random variables, normally distributed. Each hidden node (marked empty in the figure below) has a local observation (yellow) which is the input from the basic PMS algorithm (or in general, any algorithm estimating these partial first order derivatives). For each quad in the grid, we introduce a check node. This node will receive messages from the hidden nodes, compute the integral of the quad, and pass messages to the hidden nodes (in forms of PDFs), which will try to force them to make the integral 0. This message passing from hidden nodes to check node and back forms a single iteration.
Since the graph is loopy, several iterations will enforce this constraint
globally across the entire graph.
The description of the message passing is shown in the Presentation
in more details. It consists of two main steps – passing of a message (mean and
variance) from the hidden nodes to the check nodes. Each check node computes 4
messages, to be passed to its connected hidden nodes, which is basically the
value that the hidden node should be based on its three quad neighbors (the sum
of the means of the neighbors, with appropriate sign), and the confidence of
this assessment (the sum of neighbors variances). The second step is done in
the hidden node, and it is the factoring of the message coming from the check
nodes and the local observation to form a new Gaussain PDF for the hidden node.
In the final step, the mean is the estimated value used for the hidden node and
hence used in the integration.
 Koetter R., Frey B.J, Petrovic N., Munson Jr., D.C, “Unwrapping phase images by propagating probabilities across graphs”, in International Conference on Acoustics, Speech and Signal Processing, 2001.
 Iwahori Y., Woodham R.J, Shoaib Bhuiyan M., Ishii N., “Neural Network based photometric stereo for object with non-uniform reflectance factor”, 6th international conference on Neural information Processing, Vol. 3, pp. 1213-18, 1999.
There are many more references on the all subjects. Please refer to the report for a complete list.