IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE VOL V NO N APRIL

Description

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. V, NO. N, APRIL 2010 1 A Tensor-Based Algorithm for High-Order Graph Matching Olivier Duchenne, Francis Bach, In-So Kweon, and Jean Ponce Abstract—This paper addresses the problem of establishing correspondences between two sets of visual features using higher-order constraints instead of the unary or pairwise ones used in classical methods. Concretely, the corresponding hypergraph matching problem is formulated as the maximization of a multilinear objective function over all permutations of the features. This function is defined by a tensor representing the affinity between feature tuples. It is maximized using a generalization of spectral techniques where a relaxed problem is first solved by a multi-dimensional power method, and the solution is then projected onto the closest assignment matrix. The proposed approach has been implemented, and it is compared to state-of-the-art algorithms on both synthetic and real data. Index Terms—Hypergraphs, Graph Matching, Image Feature Matching. F 1 INTRODUCTION Establishing correspondences between two sets of visual fea- tures is a key problem in computer vision tasks as diverse as feature tracking [6], image classification [18] or retrieval [29], object detection [5], shape matching [19], [36], or wide- baseline stereo fusion [27]. Different image cues may lead to very different matching strategies.

• matrix


• order interactions


• score


• problem


• between matched


• problem statement


• supersymmetric tensor

Sujets

• Duchenne
• Analysis
• Matrix
• Problem
• Problem statement

Informations

• Publié par: pefav
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. V, NO. N, APRIL 2010

1

A Tensor-Based Algorithm for High-Order Graph Matching Olivier Duchenne, Francis Bach, In-So Kweon, and Jean Ponce

Abstract —This paper addresses the problem of establishing correspondences between two sets of visual features using higher-order constraints instead of the unary or pairwise ones used in classical methods. Concretely, the corresponding hypergraph matching problem is formulated as the maximization of a multilinear objective function over all permutations of the features. This function is defined by a tensor representing the affinity between feature tuples. It is maximized using a generalization of spectral techniques where a relaxed problem is first solved by a multi-dimensional power method, and the solution is then projected onto the closest assignment matrix. The proposed approach has been implemented, and it is compared to state-of-the-art algorithms on both synthetic and real data. Index Terms —Hypergraphs, Graph Matching, Image Feature Matching. ✦

1 I NTRODUCTION has changed in the past few years, with the advent of com- Establishing correspondences between two sets of visual fea-  binatorial or mixed continuous/combinatorial optimization ap- tures is a key problem in computer vision tasks as diverse as  proaches t 1 o feature matching (see, for example [5], [19], [23], featuretracking[6],imageclassification[18]orretrieval[29], [25], a [ c 3 c 6 o ]).T d hi a s te p b a o p t e h r ( b m ui o l s d t s ly o l n o t c h a i l s ) w g o e r o k m i e n tr a ic fr i a n m va e r w ia o n r t k s t a h n a d t object detection [5], shape matching [19], [36], or wide-  can mmo baseline stereo fusion [27]. Different image cues may lead  image descriptors. Concretely, the search for correspondences to very different matching strategies. At one end of the spec-  is cast as a hypergraph matching problem using higher-order trum, geometric matching techniques such as RANSAC [10],  constraints instead of the unary or pairwise ones used by interpretationtrees[14],oralignment[15]canbeusedto l p o r c e a v l io i u m s a m ge et d h e o s d c s r : ip F t i i r o s n t- s or ar d e er su m s e c t e h p o ti d b s le ba t s o e i d m (f a o g r e e a x m a b m i p g l u e i ) ti on s efficiently explore consistent correspondence hypotheses when  e themappingbetweenimagefeaturesisassumedtohavesome a d p u p e e t a o ra r n e c p e ea f t o e r d e p x a a tt m er p n le s . ,t G ex e t o u m re e s tri o c r c n o o n n- si d s i t s e c n ri c m y i i n s at n iv o e r lo l c l a y l parametricform(e.g.,aplanaraffinetransformation),orobey enforcedusiirwiserelationshipsbetweenimagefeat m u a res. some parametric constraints (e.g., epipolar ones). At the other  ng pa end of the spectrum, visual appearance alone can be used to  In contrast, we propose in this paper to use higher-order findmatchingfeatureswhensuchanassumptiondoesnot ( co m n o s s i t s l t y en t c h y ird ( - F o i r g d u e r r e )c 2 o ). nst T r h a i i s nts wo t r o k enf e o n r e c r e ali f z e e a s tur t e he m s a p t e c c h t i r n a g l hold: For example, bag-of-features methods that discard all g spatialinformationtobuildsomeinvariancetointra-class matchin o g ndi m n e g th h o y d per o g f ra [ p 1 h 9] ma t t o chi h n ig g h p e r r- o o b r l d e e m r is po f t o e r nt m ia u l l s a : ted Th a e s variations and viewpoint changes have been applied quite  corresp successfully in image classification tasks [34], [35]. Modern  the maximization of a multilinear objective function over all methods for image matching now tend to mix both geometric  permutations of the features. This function is defined by a and appearance cues to guide the search for correspondences  tensor representing the affinity between feature tuples. It is (see, for example, [18], [21]).  maximized by first using a multi-dimensional power method Many matching algorithms proposed in the 80s and 90s  to solve a relaxed version of the problem, whose solution is have an iterative form but are not explicitly aimed as opti-  then projected onto the closest assignment matrix. mizing a well-defined objective function (this is the case for  The three main contributions of this article are (1) the RANSACandalignmentmethodsforexample).Thesituation o a r p d p e li r ca m ti a o t n ch o i f ng th t e as te k, ns c o o r m p b o i w n e e r d it w er it a h tio a n r m el e a t x h a o ti d o t n o b th a e se h d ig o h n - • Olivier Duchenne and Jean Ponce are with the department of Computer constraints on the row norms of assignment matrices, which ´ is tighter than previous methods (Section 3), (2) an ` 1 - ScienceatEcoleNormaleSup ´ erieuredeParisandtheWillowprojectteam (CNRS/ENS/INRIA UMR 8548) norm instead of the classical ` 2 -norm relaxation, that rovid E-mail: olivier.duchenne at ens.fr and jean.ponce at ens.fr p es • Francis Bach is with INRIA and the Sierra team, Laboratoire s p o o l w ut e i r on i s te t r h a a t t io a n re a m lg o o re rit i h nt m erp ( r S e e ta ct b i l o e n bu 4 t ), stil a l n a d llo (3 w ) s t a h n e ef d fi e c s i i e g n n t ´ d’Informatique de Ecole Normale Supe´rieure de Paris (CNRS/ENS/INRIA UMR 8548) E-mail: francis.bach at ens.fr of appropriate similarity measures that can be chosen either • In-So Kweon is with RCVlab in the department of electrical engineering at the university of KAIST, South Korea. ma 1 t . ch T i o ng be w f e a r i e r,i c t o s n h si o d ul e d re b d e a no k t e e y dt c h o a m t p o o pt n i e m n i t za o t f io o n b - j b e a c s t e r d ec a o p g pr ni o t a i c o h n e a s n t d og s r c a e p n h e E-mail: iskweon at ee.kaist.ac.kr analy is strategies in the 70s and 80s, see for example the classical text by s Ballard and Brown [4, Ch. 11].