Consistent Shape Maps via Semidefinite Programming
Q. Huang, L. Guibas

Citation
Q. Huang, L. Guibas. "Consistent Shape Maps via Semidefinite Programming". Proc. Eurographics Symposium on Geometry Processing (SGP), 2013.

Abstract
Recent advances in shape matching have shown that jointly optimizing the maps among the shapes in a collection can lead to significant improvements when compared to estimating maps between pairs of shapes in isolation. These methods typically invoke a cycle-consistency criterion — the fact that compositions of maps along a cycle of shapes should approximate the identity map. This condition regularizes the network and allows for the correction of errors and imperfections in individual maps. In particular, it encourages the estimation of maps between dissimilar shapes by compositions of maps along a path of more similar shapes. In this paper, we introduce a novel approach for obtaining consistent shape maps in a collection that formulates the cycle-consistency constraint as the solution to a semidefinite program (SDP). The proposed approach is based on the observation that, if the ground truth maps between the shapes are cycle-consistent, then the matrix that stores all pair-wise maps in blocks is low-rank and positive semidefinite. Motivated by recent advances in techniques for low-rank matrix recovery via semidefinite programming, we formulate the problem of estimating cycle-consistent maps as finding the closest positive semidefinite matrix to an input matrix that stores all the initial maps. By analyzing the Karush-Kuhn- Tucker (KKT) optimality condition of this program, we derive theoretical guarantees for the proposed algorithm, ensuring the correctness of the recovery when the errors in the inputs maps do not exceed certain thresholds. Besides this theoretical guarantee, experimental results on benchmark datasets show that the proposed approach outperforms state-of-the-art multiple shape matching methods.

Electronic downloads

Citation formats  
  • HTML
    Q. Huang, L. Guibas. <a
    href="http://robotics.eecs.berkeley.edu/pubs/9.html"
    >Consistent Shape Maps via Semidefinite
    Programming</a>, Proc. Eurographics Symposium on
    Geometry Processing (SGP), 2013.
  • Plain text
    Q. Huang, L. Guibas. "Consistent Shape Maps via
    Semidefinite Programming". Proc. Eurographics Symposium
    on Geometry Processing (SGP), 2013.
  • BibTeX
    @inproceedings{HuangGuibas13_ConsistentShapeMapsViaSemidefiniteProgramming,
        author = {Q. Huang and L. Guibas},
        title = {Consistent Shape Maps via Semidefinite Programming},
        booktitle = {Proc. Eurographics Symposium on Geometry
                  Processing (SGP)},
        year = {2013},
        abstract = {Recent advances in shape matching have shown that
                  jointly optimizing the maps among the shapes in a
                  collection can lead to significant improvements
                  when compared to estimating maps between pairs of
                  shapes in isolation. These methods typically
                  invoke a cycle-consistency criterion â the fact
                  that compositions of maps along a cycle of shapes
                  should approximate the identity map. This
                  condition regularizes the network and allows for
                  the correction of errors and imperfections in
                  individual maps. In particular, it encourages the
                  estimation of maps between dissimilar shapes by
                  compositions of maps along a path of more similar
                  shapes. In this paper, we introduce a novel
                  approach for obtaining consistent shape maps in a
                  collection that formulates the cycle-consistency
                  constraint as the solution to a semidefinite
                  program (SDP). The proposed approach is based on
                  the observation that, if the ground truth maps
                  between the shapes are cycle-consistent, then the
                  matrix that stores all pair-wise maps in blocks is
                  low-rank and positive semidefinite. Motivated by
                  recent advances in techniques for low-rank matrix
                  recovery via semidefinite programming, we
                  formulate the problem of estimating
                  cycle-consistent maps as finding the closest
                  positive semidefinite matrix to an input matrix
                  that stores all the initial maps. By analyzing the
                  Karush-Kuhn- Tucker (KKT) optimality condition of
                  this program, we derive theoretical guarantees for
                  the proposed algorithm, ensuring the correctness
                  of the recovery when the errors in the inputs maps
                  do not exceed certain thresholds. Besides this
                  theoretical guarantee, experimental results on
                  benchmark datasets show that the proposed approach
                  outperforms state-of-the-art multiple shape
                  matching methods.},
        URL = {http://robotics.eecs.berkeley.edu/pubs/9.html}
    }
    

Posted by Ehsan Elhamifar on 16 May 2014.
Groups: ehumans
For additional information, see the Publications FAQ or contact webmaster at robotics eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.