Autocorrelation Descriptor for Efficient Co-alignment of 3D Shape Collections

1University College London     2Stanford University

Computer Graphics Forum 2015
Presented at Eurographics 2016

Figure 1:Shape collections typically come with inconsistent orientations (a). PCA-based alignment (b), or aligning to an arbitrarily chosen base model (c) is prone to error. The problem with pairwise alignments is attributed to several minima in alignment distances (Epair), arising due to near-symmetries of shapes. We introduce an autocorrelation-guided algorithm to efficiently sample the minima (red boxes) and jointly co-align the input models (d).


Abstract

Co-aligning a collection of shapes to a consistent pose is a common problem in shape analysis with applications in shape matching, retrieval, and visualization. We observe that resolving among some orientations is easier than others, for example, a common mistake for bicycles is to align front-to-back, while even the simplest algorithm would not erroneously pick orthogonal alignment. The key idea of our work is to analyze rotational autocorrelations of shapes to facilitate shape co-alignment. In particular, we use such an autocorrelation measure of individual shapes to decide which shape pairs might have well-matching orientations; and, if so, which configurations are likely to produce better alignments. This significantly prunes the number of alignments to be examined, and leads to an efficient, scalable algorithm that performs comparably to state-of-the-art techniques on benchmark datasets, but requires significantly fewer computations, resulting in 2-16$\times$ speed improvement in our tests.


Method Overview

Figure 5: Starting from a set of shapes, we normalize and compute their autocorrelation descriptors to cluster the shapes. We then align the shapes first within and then across the clusters using a graph-based discrete formulation wherein we intelligently sample candidate alignments for each shape guided by their autocorrelation descriptors.

Results

Figure 12: Randomly selected shapes from all our datasets, indicating their pose before (odd rows - in gray) and after (even rows - in green) alignment.

Bibtex
@article {Averkiou2016_CGF,
author = {Averkiou, Melinos and Kim, Vladimir G. and Mitra, Niloy J.},
title = {Autocorrelation Descriptor for Efficient Co-Alignment of 3D Shape Collections},
journal = {Computer Graphics Forum},
volume = {35},
number = {1},
issn = {1467-8659},
url = {http://dx.doi.org/10.1111/cgf.12723},
doi = {10.1111/cgf.12723},
pages = {261--271},
year = {2016},
}
      
Acknowledgements

We thank the reviewers for their comments and suggestions for improving the paper. This work was supported in part by ERC Starting Grant SmartGeometry (StG-2013-335373) and gifts from Adobe. Melinos Averkiou is grateful to the Rabin Ezra Scholarship Trust for the award of a bursary.

Links

Paper (7MB)

Code and Data (700MB)

Slides (35MB)