COS 429 - Computer Vision

Fall 2005

Assignment 4

Some notes on shape matching that might be helpful are here.

In this assignment, you will implement a set of routines for determining the similarity between 3D shapes. These types of algorithms form the basis for a shape search engine such as this one, which was built by a research group here at Princeton. The steps you should implement are the following:

1. Obtaining and Loading 3D Data

You will be computing a set of shape descriptors over the 3D data. One simple way to account for the different numbers of polygons in each object is to generate a fixed number of samples randomly distributed over the surface of each object. To do this, use the pointsample program (download pointsample_Win32.exe or pointsample_Linux; if you want/need the source, you'll need pointsample.cc and the trimesh library). The usage is:

	pointsample model.ply nsamples model.pts

The pointsample program generates a file containing the 3D coordinates and normals of points, one point per line in ASCII format. To load these into Matlab and display them, try

	model_points = load('somemodel.pts');
	plot3(model_points(:,1), model_points(:,2), model_points(:,3), '.');
	axis equal;

2. Normalization for Translation and Scale

The first thing you should do with each point set is normalize it for translation and scale. To do this, translate the data so the center of mass of the points is at the origin, then apply a uniform scale such that the root-mean-square distance of points from the origin is 1.

3. Computing Descriptors

Compute the following descriptors:

• D2 Shape Distributions: [Osada et al.] This descriptor is just a histogram of the distances between random points on the surface. Note that because of the RMS distance-based scale normalization suggested above, this distance is not necessarily bounded and you might have to truncate it to some maximum.
• Shell Histograms: [Ankerst et al.] This is a count of how many points fall into each of a set of concentric spherical shells around the origin. That is, you should compute the distance of each point to the origin, quantize it, and compute a histogram of the values.
• Shells and PCA: Decompose the model into shells, as above. Within each shell, compute the SVD of the points that fell into that shell, and take the three singular values. This yields a descriptor of size 3xn, where n is the number of shells.
• Shells and Sectors: Decompose the model into shells. Take the points falling into a given shell, and distribute them into sectors uniformly spread over the surface of the sphere (hint: here are some points spaced equally over the sphere - assign points to sectors by normalizing them to the sphere and finding the closest point). This gives you a 2-dimensional histogram indexed by shell and sector. Now, to make the descriptor invariant over rotation, sort the bins according to the number of points that fell into each sector. Compare the effects of sorting within each shell independenty vs. sorting over all shells.
• EGIs: An extended Gaussian image is basically a histogram of surface normals. Start by normalizing the model for rotation using PCA. That is, compute the principal axes of the points, and transform the points and normals so that the principal axes are aligned with the x, y, and z axes, in a fixed order. Then, similarly to the previous case, index the normals by clustering to uniformly-sampled directions. Because you normalized for rotation, you should be able to form a descriptor just by listing the number of normals falling in each bin, in a canonical order (i.e., the sorting trick from above shouldn't be necessary).

Note: Some of the descriptors may be easier and/or faster to implement using C or C++ instead of in Matlab. You are welcome to use whatever language or combination of languages is easiest for you. If you use C or C++, you may download and use a library to perform SVD.

4. Evaluating the Results: Precision-Recall Graphs

In order to see how well each descriptor does, use each model in the database in turn as a query, and order all the models in the database in order of similarity of their descriptors to that of the query (simply compare descriptors using Euclidean distance). Summarize the results in a precision-recall graph:

Precision: fraction of results that are in the same category as the query (plotted along the y axis)
Recall: fraction of models in the same category as the query that are among the results (plotted along x)

The full precision-recall graph will have points for several precision/recall values (to be precise, 9, since all the classes have 10 objects and you are omitting one at a time), and will be the average of the values obtained using all the objects as queries. Better performance corresponds to plots closer to the upper right-hand corner (see page 18 of this paper for examples - note that recall goes along the horizontal axis and precision is along the vertical axis).

Submitting

This assignment is due Thursday, Dec. 8. Please submit:

• An HTML file containing comments on your experiments and any relevant implementation notes.
• Precision/recall curves for the descriptors you implemented
• Your code (as one or more .m files, or source code if you are not working in Matlab).