DocumentCode :
1230069
Title :
Graph Rigidity, Cyclic Belief Propagation, and Point Pattern Matching
Author :
McAuley, Julian J. ; Caetano, Tibério S. ; Barbosa, Marconi S.
Author_Institution :
Stat. Machine Learning Group, NICTA, Canberra, ACT
Volume :
30
Issue :
11
fYear :
2008
Firstpage :
2047
Lastpage :
2054
Abstract :
A recent paper (Caetano et al., 2006) proposed a provably optimal, polynomial time method for performing near-isometric point pattern matching by means of exact probabilistic inference in a chordal graphical model. Its fundamental result is that the chordal graph in question is shown to be globally rigid, implying that exact inference provides the same matching solution as exact inference in a complete graphical model. This implies that the algorithm is optimal when there is no noise in the point patterns. In this paper, we present a new graph which is also globally rigid but has an advantage over the graph, its maximal clique size is smaller, rendering inference significantly more efficient. However, this graph is not chordal and thus standard junction tree algorithms cannot be directly applied. Nevertheless, we show that loopy belief propagation in such a graph converges to the optimal solution. This allows us to retain the optimality guarantee in the noiseless case, while substantially reducing both memory requirements and processing time. Our experimental results show that the accuracy of the proposed solution is indistinguishable when there is noise in the point patterns.
Keywords :
belief networks; graph theory; pattern matching; cyclic belief propagation; graph matching; graph rigidity; junction tree algorithm; point pattern matching; Point pattern matching; belief propagation; chordal graphs; global rigidity; graph matching; graphical models; Algorithms; Artificial Intelligence; Image Enhancement; Image Interpretation, Computer-Assisted; Information Storage and Retrieval; Pattern Recognition, Automated; Subtraction Technique;
fLanguage :
English
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Publisher :
ieee
ISSN :
0162-8828
Type :
jour
DOI :
10.1109/TPAMI.2008.124
Filename :
4527248
Link To Document :
بازگشت