Efficient High Order Matching

被引：81
作者：
Chertok, Michael [1 ]
Keller, Yosi [1 ]
机构：
[1] Bar Ilan Univ, Sch Engn, Ramat Gan, Israel
来源：
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 2010年 / 32卷 / 12期
关键词：
High-order assignment; probabilistic matching; spectral relaxation; ALGORITHM; ASSIGNMENT; THEOREM;
D O I：
10.1109/TPAMI.2010.51
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We present a computational approach to high-order matching of data sets in IRd. Those are matchings based on data affinity measures that score the matching of more than two pairs of points at a time. High-order affinities are represented by tensors and the matching is then given by a rank-one approximation of the affinity tensor and a corresponding discretization. Our approach is rigorously justified by extending Zass and Shashua's hypergraph matching [40] to high-order spectral matching. This paves the way for a computationally efficient dual-marginalization spectral matching scheme. We also show that, based on the spectral properties of random matrices, affinity tensors can be randomly sparsified while retaining the matching accuracy. Our contributions are experimentally validated by applying them to synthetic as well as real data sets.
引用
收藏
页码：2205 / 2215
页数：11
相关论文
共 41 条
[21]   Tensor Decompositions and Applications [J].
Kolda, Tamara G. ;
Bader, Brett W. .
SIAM REVIEW, 2009, 51 (03) :455-500
[22]   A counterexample to the possibility of an extension of the Eckart-Young low-rank approximation theorem for the orthogonal rank tensor decomposition [J].
Kolda, TG .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2003, 24 (03) :762-767
[23]  
Leordeanu M, 2005, IEEE I CONF COMP VIS, P1482
[24]   Randomized algorithms for the low-rank approximation of matrices [J].
Liberty, Edo ;
Woolfe, Franco ;
Martinsson, Per-Gunnar ;
Rolchlin, Vladimir ;
Tyger, Mark .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (51) :20167-20172
[25]  
Lim LH, 2005, IEEE CAMSAP 2005: FIRST INTERNATIONAL WORKSHOP ON COMPUTATIONAL ADVANCES IN MULTI-SENSOR ADAPTIVE PROCESSING, P129
[26]   Learning physics-based motion style with nonlinear inverse optimization [J].
Liu, CK ;
Hertzmann, A ;
Popovic, Z .
ACM TRANSACTIONS ON GRAPHICS, 2005, 24 (03) :1071-1081
[27]   Distinctive image features from scale-invariant keypoints [J].
Lowe, DG .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2004, 60 (02) :91-110
[28]   A global solution to sparse correspondence problems [J].
Maciel, J ;
Costeira, JP .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2003, 25 (02) :187-199
[29]   A comparison of affine region detectors [J].
Mikolajczyk, K ;
Tuytelaars, T ;
Schmid, C ;
Zisserman, A ;
Matas, J ;
Schaffalitzky, F ;
Kadir, T ;
van Gool, L .
INTERNATIONAL JOURNAL OF COMPUTER VISION, 2005, 65 (1-2) :43-72
[30]   A performance evaluation of local descriptors [J].
Mikolajczyk, K ;
Schmid, C .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27 (10) :1615-1630
12345