Algorithms for 3D Isometric Shape Correspondence - Algorithms for 3D Isometric Shape Correspondence
MetadataShow full item record
There are many pairs of objects in the digital world that need to be related before performing any comparison, transfer, or analysis in between. The shape correspondence algorithms essentially address this problem by taking two shapes as input with the aim of finding a mapping that couples similar or semantically equivalent surface points of the given shapes. We focus on computing correspondences between some featured or all present points of two semantically similar 3D shapes whose surfaces overlap completely or partially up to isometric, i.e., distance-preserving, deformations and scaling. Differently put, our isometric shape correspondence algorithms handle several different cases for the shape correspondence problem that can be differentiated based on how similar the shape pairs are, whether they are partially overlapped, the resolution of the desired mapping, etc. Although there exist methods that can, in most cases, satisfactorily establish 3D correspondences between two given shapes, these methods commonly suffer from certain drawbacks such as high computational load, incapability of establishing a correspondence which is partial and dense at the same time, approximation and embedding errors, and confusion of symmetrical parts of the shapes. While the existing methods constitute a solid foundation and a good starting point for the shape correspondence problem, our novel solutions designed for a given scenario achieve significant improvements as well as contributions. We specifically explore the 3D shape correspondence problem under two categories as complete and partial correspondences where the former is categorized further according to the output resolution as coarse and dense correspondences. For complete correspondence at coarse resolution, after jointly sampling evenly-spaced feature vertices on shapes, we formulate the problem as combinatorial optimization over the domain of all possible mappings between source and target features, which then reduces within a probabilistic framework to a log-likelihood maximization problem that we solve via EM (Expectation Maximization) algorithm. Due to computational limitations of this approach, we design a fast coarse-to-fine algorithm to achieve dense correspondence between all vertices of complete models with specific care on the symmetric flip issue. Our scale normalization method based on a novel scale-invariant isometric distortion measure, on the other hand, handles a particular and rather restricted setting of partial matching whereas our rank-and-vote-and-combine (RAVAC) algorithm deals with the most general matching setting, where both two solutions produce correspondences that are partial and dense at the same time. In comparison with many state-of-the-art methods, our algorithms are tested by a variety of two-manifold meshes representing 3D shape models based on real and synthetic data.