Yefeng Zheng

Robust Point Matching for Non-Rigid Shapes by Preserving Local Neighborhood Structures


Though rigid shape matching has widely studied, non-rigid shape matching attract more and more attention in the computer vision community. Shape matching or registration is often formulated as a point matching problem. In point matching for non-rigid shape, the local geometric constraints among points (such as a pair of points may tend to moving together) are often hard to be used in matching. And they are not explicitly preserved in many applications. In this paper, we formulate point matching as a graph matching problem to preserve the neighborhood of a point. Each point composes a node in the graph, and two nodes are connected by an edge if their Euclidean distance is less than a threshold. The matching of two graphs is initialized with the shape context distance. The relaxation labeling technique after enforcing one-to-one matching is applied to refine the matching results. The non-rigid deformation is compensated gradually by bringing a shape closer the other in each iteration using deformation parameters estimated with the current point correspondence. Experiments on real and synthesized data demonstrate the effectiveness of our approach: it outperforms the shape context and TPS-RPM matching algorithms under deformation and noise on a public data set.

Experiments on Handwriting Matching

Handwriting is a kind of non-rigid shape. Following figure shows two samples of handwritten initials from the same person. We randomly extracted 200 points from the skeleton of each shape, and run our point matching on the extracted point sets.

(a) A handwritten initial (b) 200 points extracted from the skeleton (c) Another handwritten initial (d) 200 points extracted from the skeleton
Fig 1. Handwriting and points sampled from the skeletons.

The Point matching results are shown below.

Fig 2. Point matching result

Experiments on Chui-Rangarajan Synthesized Data Sets

Synthetic data is easy to get and can be designed to test a specified aspect of the algorithms. We tested our algorithm on the same synthesized data, and compare it with the shape context method and TPS-RPM algorithm. There are three sets of data designed to measure the robustness of an algorithm under deformation, noise and outliers. In each test, the model point set is subjected to one of the above distortions to create a "target'' point set. And then we run our algorithm to find the correspondence between these two sets of points and use the estimated correspondence to warp the model. The accuracy of the matching is quantified as the average Euclidean distance between a point in the warped model and the correspondent point in the target. Several examples from the synthetic data sets are shown in Fig. 3. 100 samples are generated for each degradation level.


Fig 3. Some samples from the Chui-Rangarajan synthesized data sets. The model point sets are shown in the first column. Column 2-4 show examples of target point sets for the deformation, noise, and outlier tests respectively.

The mean and variance of the performance of three algorithms are shown in Fig. 4. As we can see, our algorithm performs best on the deformation and noise sets. However, TPS-RPM algorithm outperforms us on the Chinese character shape with large outlier rates. As shown in Fig. 4, points spread for the Chinese character shape, when a large number of outliers presented, the neighborhood changes significantly which violates our assumption. As a global coarse-to-fine approach, TPS-RPM performs better than us on this shape with large outlier rates. On the contrary, points on the fish shape are clustered, and the neighborhood of a point preserves well even under large outlier rates. Therefore, better results are achieved by us.

Fig 4. Comparison of our results (O) to the TPS-RPM (*) and shape context ([]) algorithms. The error bars indicate the standard deviation of the error over 100 random trials. Top row: the shape of fish; Bottom row: the shape of a Chinese character.


Download demos here (under Windows operating systems).

Source Code

Download source code here. The code should be used for non-commercial purposes only!

Test Samples

The synthesized data sets generated by Dr. Haili Chui and Prof. Anand Rangarajan are available here (about 12MB). Additional synthesized data under rotation and occlusion are available here (about 6MB).