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

• hg-csmsdp-13.pdf · application/pdf · 3400 kbytes

• 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.