We consider the problem of minimum distortion intrinsic correspondence between deformable shapes, many useful formulations of which give rise to the NP-hard quadratic assignment problem (QAP). Previous attempts to use the spectral relaxation have had limited success due to the lack of sparsity of the obtained fuzzy solution. In this paper, we adopt the recently introduced alternative L1 relaxation of the QAP based on the principles of game theory. We relate it to the Gromov and Lipschitz metrics between metric spaces and demonstrate on state-of-the-art benchmarks that the proposed approach is capable of finding very accurate sparse correspondences between deformable shapes. © 2012 IEEE.

A Game-Theoretic Approach to Deformable Shape Matching

RODOLA', Emanuele;ALBARELLI, Andrea;BERGAMASCO, FILIPPO;TORSELLO, Andrea
2012-01-01

Abstract

We consider the problem of minimum distortion intrinsic correspondence between deformable shapes, many useful formulations of which give rise to the NP-hard quadratic assignment problem (QAP). Previous attempts to use the spectral relaxation have had limited success due to the lack of sparsity of the obtained fuzzy solution. In this paper, we adopt the recently introduced alternative L1 relaxation of the QAP based on the principles of game theory. We relate it to the Gromov and Lipschitz metrics between metric spaces and demonstrate on state-of-the-art benchmarks that the proposed approach is capable of finding very accurate sparse correspondences between deformable shapes. © 2012 IEEE.
2012
IEEE Computer Society Conference on Computer Vision and Pattern Recognition
File in questo prodotto:
File Dimensione Formato  
published.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 554.39 kB
Formato Adobe PDF
554.39 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/30636
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 74
  • ???jsp.display-item.citation.isi??? 46
social impact