Matching hierarchical structures using association graphs

被引:257
作者
Pelillo, M
Siddiqi, K
Zucker, SW
机构
[1] Univ Venice, Dipartimento Informat, I-30172 Venice, Italy
[2] McGill Univ, Sch Comp Sci, Montreal, PQ H3A 2A7, Canada
[3] McGill Univ, Ctr Intelligent Machines, Montreal, PQ H3A 2A7, Canada
[4] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
[5] Yale Univ, Dept Elect Engn, New Haven, CT 06520 USA
[6] Yale Univ, Ctr Computat Vis & Control, New Haven, CT 06520 USA
基金
加拿大自然科学与工程研究理事会;
关键词
maximal subtree isomorphisms; association graphs; maximal cliques; replicator dynamical systems; shock trees; shape recognition;
D O I
10.1109/34.809105
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
It is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) "association graph." However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. Here, we provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use "replicator" dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.
引用
收藏
页码:1105 / 1120
页数:16
相关论文
共 66 条
[1]  
Ambler A. P., 1973, P 3 INT JOINT C AI S, P298
[2]  
[Anonymous], CLIQUES COLORING SAT
[3]  
Ballard D.H., 1982, Computer Vision
[4]  
Barrow H. G., 1976, Information Processing Letters, V4, P83, DOI 10.1016/0020-0190(76)90049-1
[5]  
BARTOLI M, 1999, CS9912 U CA FOSC VEN
[6]   AN INEQUALITY WITH APPLICATIONS TO STATISTICAL ESTIMATION FOR PROBABILISTIC FUNCTIONS OF MARKOV PROCESSES AND TO A MODEL FOR ECOLOGY [J].
BAUM, LE ;
EAGON, JA .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1967, 73 (03) :360-&
[7]  
Bolles R. C., 1982, INT J ROBOT RES, V1, P57
[8]  
Bomze I. M., 1999, HDB COMBINATORIAL OP, V4
[9]   Evolution towards the maximum clique [J].
Bomze, IM .
JOURNAL OF GLOBAL OPTIMIZATION, 1997, 10 (02) :143-164
[10]   On standard quadratic optimization problems [J].
Bomze, IM .
JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (04) :369-387