Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching

Details Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching

2007-09-29

arxiv.org/abs/0710.0043v2

Computer Science

Computer Vision and Pattern Recognition

9 pages, 8 figures

Scientific paper

A recent paper \cite{CaeCaeSchBar06} 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. Their 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 proposed in \cite{CaeCaeSchBar06}: its maximal clique size is smaller, rendering inference significantly more efficient. However, our 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 from that of \cite{CaeCaeSchBar06} when there is noise in the point patterns.

Affiliated with

Also associated with

No associations

Rating

Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-462080