Approximating the problem, not the solution: An alternative view of point set matching

Date

2006

Authors

Caetano, Tiberio
Caelli, Terry

Journal Title

Journal ISSN

Volume Title

Publisher

Pergamon-Elsevier Ltd

Abstract

This work discusses the issue of approximation in point set matching. In general, one may have two classes of approximations when tackling a matching problem: (1) an algorithmic approximation which consists in using suboptimal procedures to infer the assignment, and (2), a representational approximation which involves a simplified and suboptimal model for the original data. Matching techniques have typically relied on the first approach by retaining the complete model and using suboptimal techniques to solve it. In this paper, we show how a technique based on using exact inference in simple Graphical Models, an instance of the second class, can significantly outperform instances of techniques from the first class. We experimentally compare this method with well-known Spectral and Relaxation methods, which are exemplars of the first class. We have performed experiments with synthetic and real-world data sets which reveal significant performance improvement in a wide operating range.

Description

Keywords

Keywords: Approximation theory; Graph theory; Markov processes; Mathematical models; Random processes; Set theory; Graph matching; Graphical models; Markov random fields; Point pattern matching; Pattern matching Graph matching; Graphical models; Markov random fields; Point pattern matching

Citation

Source

Pattern Recognition

Type

Journal article

Book Title

Entity type

Access Statement

License Rights

DOI

10.1016/j.patcog.2005.10.005

Restricted until

2037-12-31