To match 3D shapes, we need to find an efficient method for computing 3D shape signature of an object. In this project, I will implement the idea of using D2 shape function to generate signature and then comparing 3D shapes based on the signatures.

3D model databases and the applications of 3D shape analysis and matching are going to be ubiquitous because of 3 recent developments. First, improved modeling tools and scanning devices are making acquisition of 3D models easier and less expensive, creating a large supply of publically available 3D data sets. Second, the World Wide Web is enabling access to 3D models constructed by people all over the world, providing a mechanism ofr widespread distribution of high quality 3D models. Finally, 3D graphics hardware and CPUs have become fast enough and cheap enough that 3D data can be processed and displayed quickly on desktop computers, leading to a high demand for 3D models from a wide range of sources.

However, most 3D file formats(VRML, 3D studio) have been designed for visuaization, they contain only geometric and appearance attributes, and lack semantic information that would facilitate automatic matching. Although some 3D file formats include meaningful structure and semantic tags (like the â€œlayerâ€ field associated with entities in AutoCad models), the vast majority of 3D objects available via the World Wide Web and the 3D models acquired with scanning devices will not have them. Automatic shape-based matching algorithms will be useful for recognition, retrieval, clustering, and classification of 3D models in such databases. And the applications will not only be in traditional fields like computer graphics, computer vision, molecular biology, but also a variety of other fields.

Below is a 3D shape matching system, you can see shape signatures are the essential components of it.

A challenging aspect of this system is to find a suitable shape signature that can be constructed and compared quickly, while still discriminating between similar and dissimilar shapes. Ideally, shape signatures are invariant to translation, rotation, scale, and deformations so that shapes may be compared without requiring pose estimation. For efficiency, signatures are typically lower in dimension than the objects they represent.

The primary motivation for the approach in this project is that the shape matching problem is reduced to the comparison of 2 probability distributions, which is a relatively simple problem when compared to the more difficult problems encountered by traditional shape matching methods, such as pose registration, parameterization, feature correspondence and model fitting. At the same time, it also provides useful discrimination of 3D shapes.

Building shape distributions from 3D polygonal models and compute a measure of their dissimilarities.

The first and most interesting issue is to select a function whose distribution provides a good signature for the 3D shape. Based on the aforementioned criteria for an ideal shape signature, I will use a shape function named D2 representing the distribution of Euclidean distances between pairs of randomly selected points on the surface of a 3D model.

For each model, I will evaluate the D2 values of 1024 pairs of randomly selected points from the shape distribution and construct a histogram by counting how many samples fall into each of 1024 fixed sized bins. This forms the representation for the shape distribution.

To randomly select a point, I will first randomly select a polygon then randomly select a point in this polygon. The sampling density is equal for each unit area, i.e. big polygon will have more chance to be selected because they have big area.

To measure the dissimilarity of 2 3D shapes, I will use chi-square statistic and Bhattacharyya distance which are commonly used for comparing binned data. Below are their equations.

2.1 I will pick 5 different categories from the Princeton Shape benchmark, and for each category, pick 5 models. Then generate shape signatures for them, and compute the differences between the signatures.

2.2 Select some 3D models and simplify them. Testing the signature on original and simplified model pairs, see if there is any difference in their signatures.

Modify the algorithm to be "feature-sensitive". That is, use the same number of samples on every polygon regardless of their size. Then run these signatures on the simplified and original models and see how they are different.

Try another shape function that measures the radius of the surface at the sample point, kind of like what they do in the "Pose-Oblivious Shape Signature" paper.

I will use Visual C++ to implement the algorithm, OpenGL to visualize the 3D polygon model and Matlab to visualize the signatures and results of comparing the dissimilarity of 3D shapes. I will mainly get 3D shapes from Princeton Shape benchmark. MeshLab is used to simplify models.

To represent 3D shapes, we could use polygonal models, parametric models, implicit models and volumetric models, etc. This 3D shape matching method only works for polygonal models.

Below are the 3D models I selected from Princeton Shape benchmark. There are 5 types of models: dinosur, dog, face, horse and plane. And 5 of models in each of the types.

dinosur267

dinosur268

dinosur269

dinosur274

dinosur276

dog87

dog88

dog89

dog90

dog91

face293

face294

face301

face313

face319

horse103

horse104

horse105

horse107

horse108

plane1122

plane1145

plane1170

plane1175

plane1180

plane1191

Below are D2 signature similarity matrixs, i.e. the result of comparing the signatures by chi-square statistics and Bhattacharyya distance. Lightness indicates the dissimilarity between models. 1-25 correspond to dinosur267-plane1191.

1)The results of using chi-square statistics and Bhattacharyya distance are similar except that Bhattacharyya distance is a little darker.

2)Some models from different types can have very similar signatures, e.g. dog87 and horse104.

3)Some models from same type can have comparably bigger dissimilarity in signatures than the models from different types, e.g. face294 and face313.

Below are D2 signature similarity matrixs based on smoothed signatures. Lightness indicates the dissimilarity between models. 1-25 correspond to dinosur267-plane1191.

There is no obvious difference between the ways of using smoothed signature data and un-smoothed signature data.

Below are the results of comparing the difference of the signatures between detailed and simplified 3D models. And the results of modifying the D2 signature to be 'feature-sensitive' and then comparing the models.

2)The D2 signatures generated by feature-sensitive and non-feature-sensitive ways have little difference.

3)Feature-sensitive way tells the difference between detailed and simplified models better than non-feature-sensitive way.

4)Simplification has the effect of smoothing the signature, i.e. the signature of simplified model is smoother than the signature of detailed one.

Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin: Shape Distributions, ACM Transactions on Graphics, Vol. 21, No. 4, October 2002, Pages 807â€“832