Enforcing Integrability Constraint for
Surface Reconstruction Using Factor Graphs
Nemanja Petrovic, Ira
Cohen
Introduction
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[1] (1986) and further explored by Frankot and Chellappa [2](PAMI88).
Horn and Brooks[1] 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[2] 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[3][4]), 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 [7](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 [6]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[5] 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.
We demonstrate the results on four objects, generating lighting using
Matlab. See Results
and Videos for
details.
References:
[4]
Forsythe D. and Ponce J., Computer Vision: A modern
approach, Prentice Hall, 2001.
There are many more references on the all
subjects. Please refer to the report for a complete list.
[Introduction][Presentation][PDF paper][Results] [Videos] [IFP Home]