Research Blog

My research blog is moving: here is the new URL:

http://www.mit.edu/~jglov/research/

GOAL PLAN

(F 8-10) goal 1: pick up 1 object (known geometry)
(T 8-14) goal 2: locate, pick up object from a pile (known geometry)
(T 8-21) goal 3: pick up 1 object (probabilistic geometry)
(T 8-28) goal 4: pick up object from a pile (probabilistic geometry)


DAILY PLAN

W 8-08: mount camera, calibrate camera (image to world)
R 8-09: locate object in image, write grasp planner (search for
............ intersecting friction cones), demonstrate picking up object
F 8-10: *** goal 1 experiments, collect data & images ***
S 8-11: write goal 4 pseudo-code
S 8-12: segmentation, layer analysis, determine goal 4 daily plan
............ (with nick)
M 8-13: write object pile planner, demonstrate picking up objects
T 8-14: *** goal 2 experiments, collect data & images ***
W 8-15: find correspondences, then use PCA to plan grasp on
............. projected contour
R 8-16: write probablistic grasp planner pseudo-code
F 8-17: implement probablistic grasp planner
S 8-18: (out of town)
S 8-19: (out of town)
M 8-20: demonstrate picking up object (with probabilistic
............. geometry)
T 8-21: *** goal 3 experiments, collect data & images ***
W 8-22:
R 8-23:
F 8-24:
S 8-25:
S 8-26:
M 8-27:
T 8-28: *** goal 4 experiments, collect data & images ***

(7-16) 1. drive around and process images of the ground
(7-20) 2. pick up single object with known geometry
(7-27) 3. pick up objects with known geometry from a pile
(8-3) 4. pick up single object with unknown (probabilistic) geometry
(8-17) 5. pick up objects with unknown (probabilistic) geometry from a pile

I. Introduction
- specific example
- motivation
- contribution

II. Background & Related Work

(7-31)

III. Geometry
- Procrustes
- mean shape
- tangent space PCA
- model inference
- shape completion
- anecdotal results
- marginalization vs. completion

IV. Data Assocation
- graphical models
- COPAP algorithms

(8-15)

V. Experimental Results
- MPEG-II Shape B
- Manipulation

VI. Conclusion

(8-31)

At a high level, the graphical model for COPAP looks like this:

where phi is the correspondence vector from shape x to shape y. The independence assumption in local features breaks the model into


where {x_i} and {y_i} are local shape descriptors. We wish to maximize P(phi|x,y), which is broken down into (1/Z)*P(x,y|phi)*P(phi), where Z is a normalizing constant. We model P(x,y|phi) using the PLSD assignment costs. In order to model P(phi), we note that building the cyclic-ordering constraint into P(phi) introduces dependencies between the phi_i's. In fact, these dependencies will be non-Markovian since phi_i depends on the last non-zero (i.e. non-skipped) assignment, which may or may not be phi_{i-1}. However, we can transform the model for P(phi) into a cyclic Markov chain by adding the following state:

alpha_i = last non-zero assignment (before phi_i)
omega_i = wrapping point (i.e. j s.t. phi_j < alpha_j)

In a legal matching, all omega_i's must be the same (i.e. there is only one wrapping assignment), and aside from the wrapping assignment, phi_i > alpha_i for all i. Graphically, the structure is:

where the graph wraps around on itself to form a cycle. If we collapse the tuple (phi_i, alpha_i, omega_i) into a single variable, phi'_i, we get the following cyclic Markov chain:

Now, if we knew ahead of time where the wrapping point was going to be (i.e. omega_i = k for all i, k known), then the cycle would be broken between phi'_{k-1} and phi'_k, yielding a linear chain:

Therefore a naive approach (and the approach we will ultimately use, with some modifications), is to simply try each wrapping point, k, each time solving the linear Markov chain using dynamic programming, and then to pick the k that yields the maximum likelihood assignment vector, phi.

15 training shapes per class, 5 testing shapes. Classification rates were about as expected, perhaps slightly better than expected, since correct classification means that the correct model must have the highest likelihood out of all 70 shape models. In other words, there is no difference between 2nd best and worst in terms of classification error.



Figure 1. Classification rate (averaged over all shape classes) vs. number of principle components retained in the tangent space PCA shape models in each class. There was an error in the classification with 15 PCs (perhaps due to singularities). On average, overfitting does not appear to be a major problem in the models since the classification rate increases monotonically with model dimensionality.




Figure 2. Average classification rates for each shape class (averaged over all numbers of principle components).




Figure 3. Max. classification rates for each shape class (maximized over all numbers of principle components).

[ doc (color) ] [ pdf (gray) ]

the weighted Procrustes Local Shape Distance (where we use a weighted sum of the entire local shape vs. neighborhood size curve instead of just the min value) performed much better for finding correspondences between shapes with missing/extra parts, and i was able to generate the mean shapes for a few examples of pairs of shapes with extra parts.



matching between two birds correctly skips over left foot of red bird.


matching (left) and mean shape (right)

unfortunately, even with the weighted PLSD the quality of the match depended on the order of matching--matching the shape with the extra part to the shape without the extra part did horribly while the other way around did perfectly. this is because we were not allowing the correspondence to skip over any points on the first shape (i.e. the lambda spacing penalties were only on the horizontal edges in the COPAP graph).



good match (left) and bad match (right) due to asymmetry in the correpondence graph.



good match (left) and bad match (right) due to asymmetry in the correpondence graph.

because of this problem, tonight i tried using lambda on both the horizontal and vertical edges of the COPAP graph, where the vertical edges now allow us to skip points on the matching (first) shape. with this small change, i'm now getting correspondences that look quite resonable for almost all the hard classes of shapes in the MPEG shape database (i'll post some picture on my blog when i wake up later today). the only caveat is that now if we turn the lambda parameter down too low, we will get an empty correspondence, since it will low cost to skip over all the points on both shapes. i've been playing around with the lambda parameter, and it seems like a good choice of lambda depends on 1) the complexity of the shape, and 2) the number of points used to represent the shape. i think regression seems like the right way to learn the lambda parameter, although we may also need to adaptively change lambda on the fly if we get a bad match.

here are some examples of correspondences with the symmetric COPAP graph (with the weighted PLSD):




one interesting thing we can see from these pictures is that when one shape has two legs very close together where the other one only has one leg, the correspondence often skips over the concavity between the two legs rather than skipping over one of the legs. a priori, this makes sense--there is no reason to bias the correspondence towards positive curvature portions of the curve. also, from the horse matching, we can see that the tail of the blue horse is matched up to the back leg of the red horse. but notice that the back leg and tail do look strikingly similar! it is only due to prior knowledge of horses that i as a human am able to distinguish the tail from the leg on the blue horse.

finally, flies and lizards are simply extremely hard to match well with contour-based shape models--lizards deform too much, and flies have too many pointy appendages. still--the correspondences are resonable for the lizard at least, and if we didn't know the fly was a fly then the fly correspondences may not be that bad either.

The PLSD can underestimate the local feature similarity when the minimum of the PLSD curve lies at the smallest scale. In the following example, the left corner of the perturbance at the top of the red shape matches locally to the top-left corner of the blue shape, and thus the PLSD (the dashed line in the figure) is just as low as for the correct match in the figures below. However, at larger neighborhood sizes, the local shapes do not match well.





Also plotted on the PLSD curve figures on the right is the weighted PLSD (solid line), which is formed by the weighted sum of Procrustes distances over each scale, where the weights are proportional to 1 at the smallest scale, 1 - 1/n at the second smallest scale, ... , and 1/n at the highest scale. (n is the number of scales in total, and weights are scaled by 2/(n+1) so as to form a probability distribution.) Clearly, the weighted PLSD, which weights smaller scales more heavily than larger scales, is more discriminitive for the features above.

Running COPAP on the two shapes (blue to red) yields:





where the regular (min) PLSD was used on the left, and the weighted PLSD is shown on the right. Spacing penalty (lambda) was zero for both figures, although matched are similar for lambda up to 12 (which is extremely high).

Matching from the red shape to the blue shape does not yield good results, however:



To handle this case (where a shape with an extra part is matched to a shape without the part), we must modify the COPAP graph--no local distance will compensate for this.

When the spacing of points varies around the two contours, the PLSD can be a bad approximation for local shape dissimilarity.



Given the blue and red contours above, here is the COPAP solution (blue to red) using the original PLSD, with spacing penalty lambda = 0, where we compute neighborhoods simply by taking k points directly from the contour (without attempting to correct for uneven spacing):



As we can see, this matching is quite bad--two corners of the blue shape are matched to sides on the red shape. We must crank lambda up to 2 in order to correct for this poor match:



The story for matching from the red shape to the blue shape is even worse--for lambda = 0 we get the following mess:



It is only when we crank up lambda to 6 that the correspondences look reasonable:



True, with the higher spacing penalties good correspondences can seemingly be found; however, this may be an artifact of the particular example chosen, and it seems very unsatisfactory to have to rely on the spacing penalty to achieve a solution which is even close to being reasonable. The spacing penalty's place is to avoid bunching up correspondences along long, flat portions of the contours, not to make a reasonable over-all match possible.

To remedy this situation, we change the PLSD as follows.

• Instead of forming neighborhoods of size k by grabbing k nearby contour points (which may or may not be spaced evenly from one contour to the next), we instead take k evenly-spaced points along the nearby contour boundary (interpolating between vertices as necessary) up to some maximum neighborhood distance, d.

In this way, we can achieve reasonable COPAP solutions even with lambda = 0:



(blue to red, red to blue)

Now when lambda is cranked up, the effect is only to even out the bunched up spacings along, and does not change the overall structure of the matching:

TIMELINE

3/12: (A1,B1) Complete initial comparison (bullseye test) of correspondence algorithms for shape retrieval on MPEG7 Shape B data set. Collect additional image data sets of 2-D shapes.

3/16: (B1,C1) Complete full evaluation of shape retrieval/recognition of
shape models (built with best correspondence algorithm variant from 3/12
task) on all image data sets of 2-D shapes.

3/23: (B3) Complete generation of view-dependent shape models of 3-D
objects.

3/30: (Spring Break) (C1) Finish evaluation of shape recognition of view dependent shape models of 3-D objects.

4/13: (A2) Finish development and implementation of algorithms for partial contour correspondences.

4/20: (C2) Complete evaluation of partial shape completion on 2-D shape
image data.

4/27: (C2) Complete evaluation of partial shape completion (and view
recovery) on 2-D views of 3-D shape data.

* 5/4: (D1,D2) Segment images and overlapping contours with shape priors. (B2) Generate shape models from laser data of chairs, couches, etc. Test shape recognition, shape completion, and segmentation on laser data.

5/11: Finish thesis draft.

5/18: Submit thesis.

* The tasks for 5/4 are marked as optional, since image segmentation and
modeling laser range data are not the main focus of this thesis.


KEY

For my master’s thesis, I would like to achieve the following goals:

• A. Correspondences
1. Evaluate the PLSD point assignment cost function and variants; compare to shape contexts, ICP, etc.
2. Develop and evaluate PLSD-based correspondence algorithms for partial
contours.

• B. Shape Modeling
1. Generate statistical shape models from images of 2-D shapes.
2. Generate statistical shape models from laser range data.
3. Generate view-dependent statistical shape models from images of 3-D
shapes.

• C. Shape Recognition / Shape Completion
1. Evaluate full contour shape recognition on all three types of data sets
listed above; compare to published performance of existing algorithms
(e.g. shock graphs, shape contexts, etc.) on publicly-available shape
data sets.
2. Evaluate several iterative methods for shape completion (with respect
to tangent space principle components shape models) according to two
measures: (i) completion accuracy as a function of occlusion size, and
(ii) partial shape classification rate.

• D. Data Association / Segmentation
1. Use shape priors to segment image data.
2. Use shape models to separate overlapping shape contours.

ms_thesis_proposal.pdf

Solving the Cyclic Order-Preserving Assignment Problem

Jared Glover, Christian Uldall Pedersen, Erik Taarnhøj

The cuts problem is the problem of making point correspondences between the following two contours:



In order to solve this cuts problem, one may either allow for points on one contour to be skipped in the correspondence (e.g. in COPAP-lambda), or one may separate the low and high frequencies of each contour, developing a pyramidal shape recognition algorithm which would determine that, at the highest resolution, the two shapes above just aren't very similar, whereas after downsampling or blurring the shapes are extremely similar.

The only question is whether to perform this downsampling in image space, or directly on the contour, e.g. removing the highest-frequency terms in the curvature space around the contour. In support of the former (downsampling in image space) is the following example:



In this case downsampling in curvature space would simply shrink the arms of the shape on the left until just a stump in the center is left, whereas the effect we are looking for is to close the gaps between the arms so that the shape is recognized as a pentagon. This task is clearly better accomplished in image space.

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