Projects

UCLA Vision Lab


Variational Shape Matching


PEOPLE

S. Manay, D. Cremers, B. Hong, A.Yezzi, S. Soatto
DESCRIPTION

When casual observers say that two shapes are similar, what do they mean? Generally, there is some intrinsic properties that are being compared, and some extrinsic nuisances (such as location, rotation, scaling, some deformations, and occlusions) that are being ignored. So, if we wish to compare two shapes (represented as closed, simple, planar curves), we must first factor out as many of these nuisances as possible.

Aligning and rescaling two shapes may account for some of the nuisances, but not all. Further, such an alignment is time consuming at best, and is very difficult to calculate in general. A more elegant solution is to use descriptions of the shapes that are invariant to the nuisances. The effects of translation, rotation, scaling, and noise are minimized (if not discarded) if the shapes are described with integral invariants.

Hand
Hand
(a)
(b)

However, a few nuisances still remain to be dealt with. Consider the two scaled, aligned hands, above. Simply taking a set-symmetric or Hausdorff distance between the two shapes, would yield a high number. These measures of distance cannot distinguish between shapes that are perceptually different (like a hand and a fish) and shapes that are mathematically different (like these two hands).

A similar problem occurs in the local area integral invariant domain, where changes in the arclength or parameterization of the contour result in shifts of feature location and description in the integral invariant.

If we were able to induce a pointwise correspondence between the two shapes, the comparison would be much easier, and much more meaningful. Now we could compare a thumb to a thumb and realize that they are very similar, regardless of their pose, translation, rotation, or noise.  Further, once all the corresponding features are found, we can recognize which features do not have a correspondence (like the ring finger in the figure above).  Our shape comparison is now based on the invariant comparison of corresponding parts, with a penalty term for the parts that do not correspond to anything.

We realize this type of shape comparison with a shape distance, computed by establishing an optimal pointwise correspondence everywhere on the shape contours and then integrating the difference between the invariant values or corresponding points over the contours.

The correspondence is represented by a warping function which maps the parameterization of one shape onto the other.  The warping function allows for the stretching and shrinking of one parameterization onto the other.  This warping accounts for differences in parameterization or arclength between the two contours, such as those caused by missing or occluded parts.  For instance, the warping function maps the ring finger on hand (a), above, to a small portion of the contour on hand (b), between the middle and pinky fingers.

Given the optimal correspondence, the shape distance function is the sum of two terms.  The first is the difference between the integral invariants of corresponding points.  The second is a penalty on the amount of warping at those points.  These terms are integrated over the entire shape, resulting in a single real value describing how well the two shapes match.

The optimal correspondence is the correspondence that minimizes the shape distance.  Both shape distance and optimal correspondence are computed in a discrete optimization framework.  The warping function is represented as the path through a 2D graph, where graph nodes are possible pointwise correspondences and graph edges embed point adjacency and the monotonicity of the warping function.  Fast algorithms, such as Dijkstra's algorithm, are then used to find the optimal path through the graph.

The noise robustness of the computed correspondence is demonstrated below.  For more details, please see the publications listed here.

Original Shape

Correspondence via Integral Invariants
Correspondence via Curvature


Shape correspondence in noise. Note that using integral invariants results in a consistent correspondence every time, while curvature results in a different correspondences.