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.
|
|
(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.
