3D Correspondence by Breadth First Search Frontiers

This paper presents a novel, robust, and fast 3D shape correspondence algorithm applicable to the two snapshots of the same object in arbitrary deformation. Given two such frames as triangle meshes with fixed connectivity, our algorithm first classifies vertices into Breadth-First Search (BFS) frontiers according to their unweighted shortest path distance from a source vertex. This is followed by the rigid or non-rigid alignment of the corresponding frontiers of two meshes as the second and final step. This algorithm is flexible; high-resolution meshes are welcome. It is robust; results approved by human intuition as well as our own numerical correspondence error metric. It is fast; sequential running time turns out to be quadratic in number of vertices, whereas this upper bound can be pulled down as low as subquadratic O(V 1.5 ) once the second step is naturally and easily parallelized. Due to consistent frontier selection, second step does the optimal work of O(V 3 ) Hungarian assignment in less than a quadratic time.
Citation Formats
Y. Sahillioğlu, “3D Correspondence by Breadth First Search Frontiers,” Las Vegas, Nevada, USA, 2009, p. 203, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/84211.