Research Blog

Moving

2007-10-18T16:19:00.000-05:00

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

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

New Manipulation Timeline

2007-08-08T16:16:00.000-05:00

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 ***

Manipulation Timeline

2007-07-12T23:02:00.000-05:00

(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

Thesis Timeline

2007-07-12T22:23:00.000-05:00

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)

Graphical Models for COPAP

2007-05-09T17:24:00.000-05:00

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.

MPEG-7 Shape Classification Results

2007-05-07T18:36:00.000-05:00

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

MPEG-7 Shape B dataset model building experiments (attempt #1)

2007-04-23T05:27:00.000-05:00

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

WPLSD and symmetric COPAP-lambda

2007-03-23T09:51:00.000-05:00

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.

Weighted PLSD

2007-03-15T22:19:00.000-05:00

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.

Effect of uneven spacing on PLSD correspondences

2007-03-13T04:11:00.000-05:00

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:

MS Thesis Timeline

2007-03-11T03:59:00.000-05:00

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.

Master's Thesis Proposal

2007-03-11T03:57:00.000-05:00

ms_thesis_proposal.pdf

Advanced Algorithms Final Project

2007-03-11T03:46:00.000-05:00

Solving the Cyclic Order-Preserving Assignment Problem

Jared Glover, Christian Uldall Pedersen, Erik Taarnhøj

Multi-scale shape matching

2007-02-26T23:01:00.000-05:00

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.

Local Shape Neighborhood Distance

2006-11-29T09:09:00.000-05:00

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

Algorithms Project Timeline

2006-11-28T03:49:00.000-05:00

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

Algorithms Project Summary

2006-11-28T03:44:00.000-05:00

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.

DP for correspondences

2006-11-21T21:22:00.000-05:00

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

Correspondence from alignment: greedy search with spacing regularization

2006-11-17T17:40:00.000-05:00

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.

Accomplished this week

2006-11-15T19:09:00.000-05:00

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

Correspondence from alignment

2006-11-14T05:32:00.000-05:00

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.

Email about Hausdorff vs. ICP

2006-11-14T05:27:00.000-05:00

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

Timeline

2006-11-14T05:18:00.000-05:00

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

Hausdorff alignment

2006-11-10T17:47:00.000-05:00

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.

ICP for initial alignment

2006-11-09T20:03:00.000-05:00

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.

Silverware Shape Completion

2006-07-10T05:47:00.000-05:00

Shape Completion Experiments (part 2)

2006-07-09T00:05:00.000-05:00

More text from an email:

-------------------------------------------

i just finished running some more shape completion experiments with single
partial contours and unknown correspondences. results were good for partial
contours very similar to the mean shape, as the algorithm tries to
find correspondences from the partial contour to the mean shape. results
for partial contours sufficiently different from the mean shape were not
good.

it seems to me that what we have here is a classic hidden variable problem:
we assume the completed shape should be a mix of principle components in our
shape model (i.e. the completed shape lies in eigenspace), and the
difficulty in finding correspondences is that we don't know a priori the
mixing coefficients (principle component coordinates) of the completed
shape. if we knew the mixing coefficients, we could use the resulting shape
(rather than the mean shape, as we are currently doing) to find
correspondences to the partial contour.

i don't know if it's worth the time to write this out as an EM problem, but
i just thought i'd point it out that the problem exists. for now, we could
try a sampling technique, for example:

1) sample 50 full shapes from the tangent space shape distribution.
2) for each sample, find the best correspondences to the partial shape.
3) use these correspondences and the sample full shape to sample several
orientations and scales.
4) complete the shapes for each (full shape sample, orientation, scale)
combination, and take the best one.

-------------------------------------------

Here is the data I was referring to; once again we use the occluded tools contour:

We again hand-segment out the following two partial contours:

For the partial contour on the right, results were almost identical (even slightly improved) to the previous experiment where correspondences from the partial shape to the mean shape were estimated by hand. Here is the best completion (in green) shown against the mean shape (in blue):

For the partial contour on the left, however, the situation was much worse. As is explained in the text from the email above, this is likely due to the fact that the partial contour was generated from a full contour which is significantly different from the mean shape, so finding correspondences to the mean shape is the wrong thing to do. Here is the best completion (the rest were just as bad):

Shape Completion Experiments

2006-07-08T23:29:00.000-05:00

Here are the effects of the first 5 eigenvectors on the mean shape for a model of a wire-cutter tool:

Here is a contour of two tools occluding eachother:

Segmenting this contour by hand yields the following two partial contours (shown in dashed-red):

With hand-labelled correspondences between partial contours and the mean shape, 50 (scale, orientation) pairs were sampled. Here are some of the resulting sample completed shapes (in green) for the first partial contour (on the left):

Clearly, either of the first two completions is to be preferred over the latter two; however, the maximum likelihood shape completion was closer to the bottom two:

The situation is slightly better for the second partial shape (on the right). Here are a few sample completions (in green):

and here is the best completion:

Here is a brief discussion (from an email to my advisor) of the challenges of shape completion as pertains to this experiment:

-------------------------------------------

i've just completed some experiments with known correspondences, and one
issue that stuck out as being problematic is that the shape completion is
highly sensitive to the eigenvalues of the gaussian eigenspace model. for
example, if the model thinks that opening and closing of a tool (a
wire-cutter) is much more likely than changes in perspective, the completed
shape will incorporate very little perspective change, even if the resulting
completed shape is quite ridiculous (e.g. makes the tool look like one of
the handles is crooked).

clearly this is a modelling problem, and not a flaw in the shape completion
algorithm. one way this issue is dealt with in some of the active contour
literature is to use the original dataset of complete contours from which
the model is generated to simply discover modes of transformation
(eigenvectors) while ignoring the relative eigenvalues associated with the
transformations. thus, such an discovery algorithm for the wire-cutter
should discover the modes of opening/closing, and one or two perspective
transformations. this approach makes sense when the changes in contour
appearance have more to do with external factors, such as camera positioning
or deformation by a human (opening/closing), rather than to internal changes
such as the change in shape between two different wire-cutters (as was the
case for the fish classification problem).

--------------------------------------------

New fish video

2006-05-15T10:37:00.000-05:00

fish_classification_pseg_bkd_et025.mpg

Found: one bug (in Mahalanobis distance computation)

Implemented: background subtraction contour classification (blue contours in video; red contours are still from color segmentation contours)

Reduced: number of principle components (by about half)

Realized: for noisy data, you still need a couple of high frequency principle components in order to perform robust classification.

Fish Finding

2006-05-13T14:30:00.000-05:00

After porting the shape modeling code from matlab to opencv, I finally have results from the Cousteau video:

fish_classification_pseg.mpeg

The main limitation at this point is the contour extraction; nearly all of the human-discernable fish-like contours that were extracted by the algorithm were classified correctly. Contours were extracted using a pyramid color segmentation algorithm, then for the first one-third of the video fish contours were labelled by hand to train the fish shape model.

Many of the contours were quite noisy:

Tangent space PCA was performed to get a set of principle components. Here are the mean shape and the effects of the first four principle components:

The corresponding eigenvalues were:
eigenvalue 1 = 0.084449
eigenvalue 2 = 0.048138
eigenvalue 3 = 0.031195
eigenvalue 4 = 0.016441

To my surprise, when I looked at the dataset after running the algorithm, there were 18 principle components in use, with the lowest eigenvalue being 1/100th the heighest eigenvalue. All but the top four principle components were simply modeling high-frequency noise. For example, the 18th principle component was:

Despite this massive case of overfitting, the model still performed quite well on the dataset, where the classification rule was a thresholded Mahalanobis distance from the origin to the new shape (normalized and projected into the tangent space), with a penalty for projecting onto the eigenspace which was inversely proportional to the lowest eigenvalue. The threshold was determined by hand, and was set to about 1/10th the largest Mahalanobis distance in the training set. Thus, not all of the hand-labelled fish from the training set were recognized as fish by the classification algorithm.

In addition to reducing the number of principle components in the model, there are a few other improvements that can be made to the algorithm. First, learning a generative model of noise would enable an ML or MAP classifier, eliminating the need for a knob to control the maximum Mahalanobis distance. Second, contours from the thresholded background subtraction images should be analyzed to increase the detection rate. Finally, the mirror image of each contour should be classified, in order to detect flipped, non-symmetric shapes.

More videos will be forthcoming!

Honduras Report

2006-04-27T20:14:00.000-05:00

Here's a short video from the Honduras trip: [ fish5.avi ]

Watch it, and you will realize why I haven't gotten any major new results in shape classification this semester. The changes in lighting, camera jitter, small relative size of fish to the image, and abundance of texture (but not color) on which to segment make extracting fish contours an extremely challenging problem. Color segmentation (e.g. with pyramidal flood-filling) does a terrible job: under-water most objects are some shade of aqua-marine, and the texture varies so much when the fish is seen on the backdrop of the sea floor that the resulting contours are based almost exclusively on local texture patterns.

Background subtraction also does a bad job, since the camera is moving too quickly:

Even motion subtraction, via affine warping the previous frame to fit as closely as possible the current frame (using the flow field from sparse pyramidal Lucas Kanade optical flow) doesn't help us find the fish (which should be moving differently from the rest of the image). Due to the large range in scales across the image and the high degree of occlusion, many other pixels in the image stand out apart from the fish.

At this point you may be saying to yourself: "but there aren't any fish in this image." In fact, there are two:

It is only when the motion of the fish is seen that humans can even detect them. Thus, more complicated techniques for motion segmentation are needed, such as:

"Hierarchical Image-Motion Segmentation by Swendsen-Wang Cuts"
http://civs.stat.ucla.edu/Barbu_Research/Motion/index.html

I have also been playing around with some texture metrics for the purposes of segmenting out the sea-bed and for finding and classifying coral. However, for the time being I am giving up on the Honduras videos because they are simply too difficult to process. I will generate shape models from the Cousteau video, where fish are usually against the solid backdrop of the open sea, and where lighting conditions are much more favorable. I also have a Hokuyo laser range finder (http://www.hokuyo-aut.jp/products/urg/urg.htm) to play with for 3D shape analysis--I worked out the math for 3D Procrustean shape analysis while we were in Honduras.

Finally, while in Honduras the main application I worked on was optical flow/visual odometry. I had an implementation in OpenCV before we left; unfortunately we were using a Blackfin DSP processor, so OpenCV had to be ported. This turned out to be much more difficult than anticipated, even though there is at least one reference on the web claiming to have ported OpenCV to the Blackfin (or at least there was a reference...a google search for "opencv blackfin" turns up nothing now). The main problem is that the Blackfin has no hardware support for floating point arithmetic, so all of OpenCV's math functions were extremely slow, and had to be changed to use fixed point. Aside from over/underflow problems, in the end some of the algorithms themselves were too slow--pyramidal sparse Lucas Kanade optical flow was a little too pyramidal for the Blackfin's taste, it seems. In the end, after rewriting many of the image processing functions in OpenCV, the frame-rate was down to a blazingly fast 1.5 Hz through the JTAG debugging interface (*sarcasm*). Ironically, when we tried to run the program without the JTAG, the Blackfin operating system complained. The most likely explanation I got from the hardware people on the trip was that the program was too big. *Sigh*

Finally, on the last night of the trip, I gave up on OpenCV and hacked together a non-optical-flow-based image registration algorithm which almost, sorta-kinda worked. More processing power (to increase the searchable motion space) and smarter image processing techniques (registering edge images, for example) should improve results, but I haven't had a chance to work on it any more yet.

That's all for now! I remember why I usually don't post to my blog now...it takes so much time!

More Fish Art

2006-04-27T20:04:00.000-05:00

Forget to re-normalize the log-distance transform of an edge map of a fish, and this is what you get =)

Fall '05 Final Paper

2006-04-27T18:20:00.000-05:00

My final paper for Machine Learning last semester:

Probabilistic Procrustean Shape Analysis for Object Recognition

and a short set of slides for my vision class on the final project:

[ ppt slides ]

The task was to generate shape models of two types of fish from training image data, and then to classify new shapes extracted from test image data.

Contours were extracted by hand, using color thresholding to get binary images from which contours could be extracted. Gaussian smoothing and morphological dilation and erosion operations were used to remove noise from the contours. All of this was done using OpenCV from Intel.

The correspondence problem was handled in two steps. First, features were found using peaks in "local shape derivatives."

Next, a probabilistic search algorithm for finding feature correspondences between two contours was designed by considering neighborhoods of local shape at varying scales around each feature, together with feature spacing, and the overall shape of the features.

All the matched contours in the training set were then hand-labeled as belonging either to the "angelfish" of "yellow tang" classes, and then mean shapes and tangent plane principle components were found using Procrustean shape analysis.

Effects of principle components on the mean shape:

Angelfish

Yellow Tang

Contours extracted from test data were then feature-matched against the mean shapes of each class and then classified to the shape class with the smallest Mahalanobis distance. In other words, Gaussian models were assumed for each shape class and classification was acheived with a maximum likelihood decision rule.

Results were nearly perfect for the small dataset we had (10 angelfish and 14 yellow tang contours), but obviously more data and shape categories are needed to truly test the validity of the matching algorithm. The novel part of the algorithm lies in the feature extraction and correspondence methods; tangent-plane PCA on shape models using the Procrustes metric has been done many times before in other domains, although it is a relatively unknown technique to the vision community.

The next steps are to extract shapes from video, and to apply our shape completion techniques to complete partially-occluded shapes in video sequences.

Good DSP Reference

2006-02-15T00:12:00.000-05:00

More and more it seems my discrete-math-heavy background at Carnegie Mellon University left me woefully unprepared for the very continuous flavor of math at MIT; recently I've been trying to better understand convolution and Fourier transforms as they seem to pop up everywhere. I've found a good basic reference for these and other DSP concepts in a book called:

The Scientist and Engineer's Guide to Digital Signal Processing
http://www.dspguide.com

Back to reading!

Psychedelic Fish Art

2005-11-30T23:02:00.000-05:00

So I was trying to segment fish from a Jacques Cousteau video today (playing around with background subtraction, active contours, etc.)

...when I accidentally forgot to erase a window every frame, resulting in the following AI/Cousteau-generated art:

Installing OpenCV beta5 (0.9.7) in Cygwin

2005-11-11T13:43:00.000-05:00

These are revised instructions from:

http://www.dh.aist.go.jp/~kimura/opencv/opencv-0.9.7.html.en

First of all, install the Windows version of OpenCV 0.9.7 from the binaries on Sourceforge. Then, run this script from within an empty directory in cygwin:

opencv-cygwin-install.sh

That's it! You can try running the OpenCV examples (C:/Program Files/OpenCV/samples/c/*.exe) from a cygwin shell to make sure the DLLs were built properly.

Shape Completion

2005-11-10T17:29:00.000-05:00

Here is a set of six training shapes:

After computing the mean shape and performing PCA in the tangent space, the effects of the most significant eigenvectors (from highest to lowest) can be plotted (green shape is mean, blue shape is mean + 3*eigenvector):

Now if we input a partial shape, we can sample orientation and scale from the Bookstein matching between the mean shape and the partial shape (with Gaussian noise). For every orientation and scale sample we can compute the MLE completed shape with respect to our normal shape distribution (in the tangent plane).

A partial shape:

Some completed sample shapes:

And here is the completed shape with max. likelihood among all 50 samples: