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

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

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
13 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Nombre de lectures 25
Langue English
Poids de l'ouvrage 2 Mo

Exrait

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],imageclassication[18]orretrieval[29],[25],a[c3c6o]).Tdhiastepbaoptehr(bmuiolsdtslyolnotchails)wgoerokmientraicfrianmvaerwiaonrtkstahnadt 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]canbeusedtolporceavlioiumsamgeetdheosdcsr:ipFtiirosnt-sorardeersumsectehpotidbslebatsoeidm(faogreeaxmabmipgluei)tions efficiently explore consistent correspondence hypotheses when e themappingbetweenimagefeaturesisassumedtohavesomeadpupeetaorarnecpeeaftoerdepxaattmerpnles.,tGexetoumreestriocrcnoonn-sidsitsecnricmyiinsatnivoerlolclayl parametricform(e.g.,aplanarafnetransformation),orobeyenforcedusiirwiserelationshipsbetweenimagefeatmuares. 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 ndmatchingfeatureswhensuchanassumptiondoesnot(comnossitsltyentchyird(-Foirgduerre)c2o).nstTrhaiisntswotrokenfeonrecrealifzeeasturtehemsaptecchtirnagl hold: For example, bag-of-features methods that discard all g spatialinformationtobuildsomeinvariancetointra-classmatchinogndimnegthhoydperogfra[p1h9]mattochihnigghperr-oobrldeemrispoftoerntmiaullsa:tedThaes 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).Thesituationoarpdpelircamtiaotnchoifngthteastek,nscoormpboiwneerditweritahtioanrmeleatxhaotidotnobthaesehdigohn-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 spoolwuteironistetrhaattioanreamlgooreritihntmerp(rSeetactbiloenbu4t),stilalnadllo(3w)stahneefdecsiiegnnt ´ 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. ma1t.chTiongbewfearier,ictosnhsioduledrebdeanokteeydtchoamtpooptniemnitzaotfioonb-jbeacsterdecaopgprniotaicohneasntdogsrcaepnhe 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].
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents