Research Blog

Here are the results of some experiments using local shape neighborhood distances to compute the assignment cost function for the contour correspondence dynamic program.

First, on tools, with lambda=0, 0.5, 1, and 2:




Next, on forks (lambda=0,1,2):




And on mugs (lambda=0,1,2):




Again on mugs (lambda=0,.5,1,2):




Some comments:

First of all, the local shape neighborhood cost function seems to perform relatively well (for lambda > 0) on the mugs and the tools, but not on the forks. This is because the forks are actually quite different when local shape is considered, since one contour has prongs, while the other does not.

Second, the local shape neighborhood cost function seems to give good correspondence results for points with high curvature, while sometimes being sloppy about points along flat portions of the contours. This can be explained by looking at the cost matrices for the tools, mugs, and forks (darker means higher shape distance):




In each case, there are several dark rows and columns, which correspond to points on the two contours whose local shape doesn't match up well with most of the local shapes on the other contour. In other words, these rows and columns point out locations on the shape which are distinct. The other rows and columns represent undistinct local shapes on the contours. This points out a natural way to find salient local features of two shapes to be matched, which should significantly reduce the computational burden. The only drawback is that the cost matrix itself is quite costly to compute (as each element in the matrix is the minimum of a vector of local shape distances at different scales).

thu nov 23 - thanksgiving
mon nov 27 - nail down algorithms to implement & design experiments
fri dec 1 - finish implementation
wed dec 6 - finish experiments
mon dec 11 - finish final paper
wed dec 13 - final paper due

We will solve the geometric problem of finding the "best" correspondences between the points of two closed contours in 2D. We will compare two popular representations in the literature, shape contexts and shock graphs, with a third method which I have been developing in my research for the past year, using local contour shapes over multiple scales.

Shape contexts and shock graphs are both ways of respresenting the shapes of objects in the plane; shape contexts model the relative positions of points on an object, while shock graphs model the skeletal structure of the object, and thus capture the global shape topology. In the literature, both representations have primarily been used for the tasks of shape retrieval and classification, while in our study we wish to solve a different problem--finding correspondences between contours. While the basic shape retrieval algorithms using shape contexts do find point correspondences as an intermediate step (via bipartite graph matching), shock graph methods do not, instead relying in most cases on the graph edit distance as well as differences in local geometry of parts to compute a shape distance. While some attempts have been made to utilize skeletal (e.g. shock graph) representations of contours in order to find point correspondences, we have been unable to find a satisfactory algorithm for this purpose, and so will make a slight modification to an existing shock graph matching algorithm in order to match contour points (rather than just contour skeletons) using the built-in notion of part similarity inherant in the shock graph models. For our final method, we will use similarity in local shape around contour points (at multiple scales) in order to determine point correspondences.

The output of all three methods will be a cost function, c(x_i, y_j) for each pair of points on contour x and y representing the cost of a potential correspondence from point x_i on contour x to point y_j on contour y. Many algorithms exist to then compute a min-cost matching between the two contours (for example relaxation labelling or the hungarian method), however since we are restricting ourselves to closed contours, we will find an order-preserving min-cost matching from x to y, which can be done very efficiently with dynamic programming.

We will evaluate each algorithm by comparing its performance (1) against human correspondences, and (2) with respect to shape retrieval. The baseline algorithm of simply finding the best starting point and making one-to-one correspondences around the contours will also be considered.

Modified dynamic program from Scott & Nowak's "Robust Contour Matching Via the Order-Preserving Assignment Problem" paper to include spacing penalty, lambda. Here's how it performs on the tool, for lambda=0, 0.5, and 1:





Appears to do better than greedy search, and is just as fast. Next step is to try including local shape match in the distance function...

Modified greedy assignment algorithm to add a spacing penalty, lambda, which (when assigning the kth point on contour X to contour Y) is a multiplier on a squared error term on the difference between the actual circumference travelled thus far on Y, and the desired circumference travelled on Y in the first k points. The desired circumference travelled is equal to k/n times the total circumference of Y. (Figures are with lambda=0, 0.5, 2, and 5.)

Correspondences are still not perfect, expecially around the ends of the tool handles, so it appears that a different metric between contour points on X and Y is needed, e.g. using shape contexts or local shape distances.

1. Hausdorff vs. ICP alignment
2. formulated ILP and LP relaxation
3. formulated, implemented and tested search w/pruning and greedy search
4. read Dellaert's chain flipping paper for SFM
5. contour correspondence literature search
four main approaches:
--> medial axis
--> shape contexts
--> landmark sliding
--> greedy, sequential
5a. read paper on evaluating the performance of shape recognition algorithms on partial shapes
6. got two new datasets:
--> mpeg7shapeB
--> articu

Implemented pruning search over space of feasible (i.e. satisfying the contour ordering constraints) assignments, minimizing the sum of squared Euclidean distances between corresponding points.

First of all, here's what happens with the greedy algorithm (greedily make NN-assignments, while satisfying the ordering constraints):





(Click on the images to view them in more detail)

The first interesting thing to note is how good the greedy solutions are when the shapes are fairly similar. Even in the second tool case, when the shapes don't align very well, the correspondences are quite good in a least squares sense.

The pruning search algorithm is as follows:

1) Set dmin = sum of squares distance in greedy solution, and cmin = greedy solution

2) Search over space of feasible assignments in the assignment tree which first branches on c1, then c2, then c3, etc., pruning the branch when the sum of squared distances in the partial assignment plus the minimum (NN) sum of squared distances in the remaining, unassigned points is greater than the current best sum of squared distances, dmin. In other words, if the best score we can possibly get by following the current branch to a leaf is worse than the current best score, then we don't need to explore this assignment branch any more.

Some results:

When the shapes are very similar (as in the first tool example after ICP), the pruning search can run extremely fast (in this case, .08 secs). This is because the greedy solution is already quite good, so any deviation from a nearly optimal solution will be pruned immediately.





When the shapes are not similar, the algorithm can run arbitrarily slowly. However, we don't have to find an assignment of ALL the points; we can simply assign a small subset of evenly spaced points on one contour, and after finding the best such "low-resolution" assignment, we can interpolate assignments between these points:





At least in these few examples, however, this low-resolution approach doesn't appear to improve upon the greedy solution. In fact, even incorporating the interpolated point assignments into the score computation during the pruning search does not appear to improve upon the greedy solution, in the second tool case:





While these are clearly very preliminary results, they appear to show that the greedy solution is often near-optimal, assuming a "good" alignment has been found, when only least-squares distance between corresponding points is considered. However, the greedy solution is often quite unappealing, as we saw in the first images at the top of this post! In order to improve upon this situation, it may be desirable to incorporate additional criteria into the objective function, such as local shape matches, shape context distances, or spacing regularization penalties. With these additional objectives in place, the LP formulation of the correspondence problem (which will be given in a later post) may become more desirable, since the more complicated the objective function is, the harder it is to design an effective pruning strategy for a search algorithm.

Date: Sat, 11 Nov 2006 15:20:25 -0500 (EST)
From: Jared M Glover
To: Nicholas Roy
Cc: Daniela Rus
Subject: Re: hausdorff matching images

the figures are side by side--default alignment is on the left-hand side, and final alignment (after hausdorff) is on the right side. i think the color scheme was just reversed on the right-hand side. the hausdorff search was in a 50x50x30 space (50x50 for translation, 30 for rotation), and took on the order of one minute per alignment. i'm sure it could be sped up considerably using some multi-resolution techniques, which is why i didn't post any hard numbers, although i doubt it will ever run as fast as ICP (<< 1 sec).

the fundamental insight, i think, is that the hausdorff metric doesn't give a good estimate of shape similarity when we are dealing with images that change in predictable, non-linear ways, such as opening and closing of a tool. it is very much an image similarity metric, rather than a shape metric. i think we are much more likely to have success with ICP or some other metric designed for shapes, such as shape contexts. i will try to implement an algorithm to get feasible (in-order) contour correspondences from the ICP alignment, and i will also try to implement belongie's shape context correspondence algorithm to compare against.

-jared

# posted by Jared @ 5:27 AM 0 comments

Nov 9
-------
Show ICP with no scaling
- on tools
Show Hausdorff-minimizing transformations
- on tools
--> Do we need more sophisticated correspondence functions?

Nov 12
---------
Read Frank Dellaert's MCMC Chain Flipping paper

Nov 14
---------
Preliminary implementation of correspondence algorithm

Nov 21
---------
Evaluate complete correspondence algorithm on a reasonable set of objects.
Build shape distributions from complete contours with correspondences

Nov 23
---------
Thanksgiving

Nov 28
---------
Preliminary object completion

Dec 5
--------
Testing, begin 2D grasping

Here are some results of aligning contours by finding the Hausdorff-distance-minimizing rigid transformation (via a discretized search in translation and rotation space). What is interesting about these results is how badly the alignment is when the two contours vary by more than a certain tolerance. ICP appears to outperform Hausdorff in these cases because contours naturally do have correspondences (since the points around them are well-ordered), and so two shapes whose contour images may not look very similar at all (e.g. the first two tool matching figures) may actually be a reasonable match once correspondences are considered. Furthermore, Hausdorff-matching is MUCH slower than ICP, as a search is required, rather than being iterative like ICP.

Implemented ICP (with translation and rotation) to find initial correspondences and alignment of two complete contours. Initialized ICP with one-to-one correspondences found by searching for the best starting points on the two contours and matching evenly around the two contours starting from there (e.g. 1->25, 2->26, 3->27, ...). NN was used for point correspondences at each step of the ICP algorithm. Here are the initial alignments and final matching alignments for some sample contours:



























Interestingly, only the second tool example seems to make a bad match at all; even given bad initial correspondences (such as in the 2nd and 3rd fork examples), the ICP algorithm does a good job of bringing the contours into alignment.