COS 429 - Computer Vision

Fall 2009

Course home Outline and lecture notes Assignments

Assignment 3

Due Tuesday, Dec. 1

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

Download the database of objects, in zip format. This consists of 200 models organized into 20 classes of 10 objects each.

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 and the trimesh library). The usage is:

	pointsample model.ply nsamples model.pts
This generates nsamples points on the mesh in model.ply, and outputs file model.pts. Start with nsamples small (maybe a few hundred) for your initial experiments, then, if you determine that it helps, increase the sampling for your final results. Some of the algorithms you will implement have running time quadratic in the number of points, so don't go too wild with this number.

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;
As you can see, the point coordinates are in columns 1, 2, and 3; the normals are in columns 4, 5, and 6. Once you have a point cloud displayed, you can use the rotation tool to look at it from different directions.

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:

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 (recommended libraries include: LAPACK, GSL and TNT).

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)
So, if you compare one of the table models against the 200-model database and the top 5 most similar models contain 3 of the 9 other tables, you would have a point in your graph with recall=3/9=.33 and precision=3/5=.6 If among the 25 most similar models are 8 tables, this corresponds to recall=8/9=.89 and precision=8/25=.32

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


This assignment is due Tuesday, December 1, 2009 at 11:59 PM. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.

Please submit the URL to a .zip file with the following:

Last update 29-Dec-2010 11:53:32
smr at princeton edu