Electors Voting for Fast Automatic Shape Correspondence

Oscar Kin-Chung Au3  Chiew-Lan Tai1  Daniel Cohen-Or2  Youyi Zheng1  Hongbo Fu3

Computer Graphics Forum (Proc. of Eurographics 2010)

1The Hong Kong Unversity of Science and Technology

2Tel Aviv University

3City University of Hong Kong


Our electors voting algorithm automatically and instantaneously computes a semantic correspondence between the sitting dog and the standing elephant by considering their skeletons. A large set of selected electors vote for the skeletal feature pairs (middle) to synthesize the final correspondence between the two shapes (right). Corresponding nodes that are matched by our algorithm are rendered in the same colors; two incorrect matchings are marked with a red square.

This paper challenges the difficult problem of automatic semantic correspondence between two given shapes which are semantically similar but possibly geometrically very different (e.g., a dog and an elephant). We argue that the challenging part is the establishment of a sparse correspondence and show that it can be efficiently solved by considering the underlying skeletons augmented with intrinsic surface information. To avoid potentially costly direct search for the best combinatorial match between two sets of skeletal feature nodes, we introduce a statistical correspondence algorithm based on a novel voting scheme, which we call electors voting. The electors are a rather large set of correspondences which then vote to synthesize the final correspondence. The electors are selected via a combinatorial search with pruning tests designed to quickly filter out a vast majority of bad correspondence. This voting scheme is both efficient and insensitive to parameter and threshold settings. The effectiveness of the method is validated by precision-recall statistics with respect to manually defined ground truth. We show that high quality correspondences can be instantaneously established for a wide variety of model pairs, which may have different poses, surface details, and only partial semantic correspondence.
Shape Correspondence, Electors Voting

author = {Oscar Kin-Chung Au and Chiew-Lan Tai and Daniel Cohen-Or and Youyi Zheng and Hongbo Fu},
title = {Electors Voting for Fast Automatic Shape Correspondence},
booktitle = {Computer Graphics Forum (In Proc. of Eurographics 2010)},
year = {2010},
volume = {29},
number = {2},
pages = {to appear}

We would like to thank the anonymous reviewers for their constructive comments, and Dror Aiger and Hao (Richard) Zhang for valuable feedback. We also thank Richard for the comparison example in Figure 7 and Michael Brown for video narration. This work was supported in part by grants from the Hong Kong Research Grant Council (Project No. GRF619908), the City University of Hong Kong (Project No. 7200148) and the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities.