Tight Relaxation of Quadratic Matching

Simple item page
dc.contributor.authorKezurer, Itayen_US
dc.contributor.authorKovalsky, Shahar Z.en_US
dc.contributor.authorBasri, Ronenen_US
dc.contributor.authorLipman, Yaronen_US
dc.contributor.editorMirela Ben-Chen and Ligang Liuen_US
dc.date.accessioned2015-07-06T05:00:44Z
dc.date.available2015-07-06T05:00:44Z
dc.date.issued2015en_US
dc.description.abstractEstablishing point correspondences between shapes is extremely challenging as it involves both finding sets of semantically persistent feature points, as well as their combinatorial matching.We focus on the latter and consider the Quadratic Assignment Matching (QAM) model.We suggest a novel convex relaxation for this NP-hard problem that builds upon a rank-one reformulation of the problem in a higher dimension, followed by relaxation into a semidefinite program (SDP). Our method is shown to be a certain hybrid of the popular spectral and doublystochastic relaxations of QAM and in particular we prove that it is tighter than both. Experimental evaluation shows that the proposed relaxation is extremely tight: in the majority of our experiments it achieved the certified global optimum solution for the problem, while other relaxations tend to produce suboptimal solutions. This, however, comes at the price of solving an SDP in a higher dimension. Our approach is further generalized to the problem of Consistent Collection Matching (CCM), where we solve the QAM on a collection of shapes while simultaneously incorporating a global consistency constraint. Lastly, we demonstrate an application to metric learning of collections of shapes.en_US
dc.description.number5en_US
dc.description.sectionheadersCorrespondence and Matchingen_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume34en_US
dc.identifier.doi10.1111/cgf.12701en_US
dc.identifier.pages115-128en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12701en_US
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.titleTight Relaxation of Quadratic Matchingen_US
Files
Collections
34-Issue 5
SGP15: Eurographics Symposium on Geometry Processing (CGF 34-5)