NDLI: Graph Rigidity, Cyclic Belief Propagation, and Point Pattern Matching

Content Provider	IEEE Xplore Digital Library
Author	McAuley, J.J. Caetano, T.S. Barbosa, M.S.
Copyright Year	1979
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.
Sponsorship	IEEE Computer Society
Page Count	8
File Size	1721517
Starting Page	2047
Ending Page	2054
File Format	PDF
ISSN	01628828
Volume Number	30
Issue Number	11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-11-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Belief propagation Pattern matching Graphical models Tree graphs Inference algorithms Computational complexity Polynomials Rendering (computer graphics) Noise reduction Pattern recognition chordal graphs Point pattern matching graph matching graphical models belief propagation global rigidity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence Computational Theory and Mathematics Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Graphical Models and Point Pattern Matching

Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching

Sufficient Conditions for Convergence of the Sum–Product Algorithm

Finding Non-Overlapping Clusters for Generalized Inference Over Graphical Models

Fast Inference with Min-Sum Matrix Product

Semi-Supervised Video Segmentation Using Tree Structured Graphical Models

Scene Text Recognition Using Similarity and a Lexicon with Sparse Belief Propagation

Dot Pattern Processing Using Voronoi Neighborhoods

Convergence Analysis of the Variance in Gaussian Belief Propagation

Graph Rigidity, Cyclic Belief Propagation, and Point Pattern Matching

Similar Documents

Graphical Models and Point Pattern Matching

Graph rigidity, Cyclic Belief Propagation and Point Pattern Matching

Sufficient Conditions for Convergence of the Sum–Product Algorithm

Finding Non-Overlapping Clusters for Generalized Inference Over Graphical Models

Fast Inference with Min-Sum Matrix Product

Semi-Supervised Video Segmentation Using Tree Structured Graphical Models

Scene Text Recognition Using Similarity and a Lexicon with Sparse Belief Propagation

Dot Pattern Processing Using Voronoi Neighborhoods

Convergence Analysis of the Variance in Gaussian Belief Propagation

Graph Rigidity, Cyclic Belief Propagation, and Point Pattern Matching