An Integer Projected Fixed Point Method for Graph Matching and MAP Inference

Marius Leordeanu, Martial Hebert, Rahul SukthankarNeurIPS 2009 · OpenReview

TL;DR

The authors introduce IPFP (Integer Projected Fixed Point), a fast and efficient iterative algorithm for solving complex matching and labeling problems. By focusing on the often-neglected "discretization" step, IPFP significantly outperforms state-of-the-art methods in graph matching and MAP inference, either as a standalone solver or as a "booster" for existing algorithms.

What Problem Does This Paper Address?

Many fundamental tasks in computer vision—like recognizing an object by matching its features to a template or labeling pixels in an image—are mathematically formulated as Integer Quadratic Programs (IQP). These problems are NP-hard, meaning we can't find the perfect solution quickly as the number of features grows.

To cope, researchers usually "relax" the problem: they pretend the discrete constraints (e.g., "feature A matches feature B") are continuous probabilities. They solve this easier continuous version and then perform a quick, often crude, "binarization" at the very end to get a final answer. The authors argue that this final step is a missed opportunity. They show that even if you have a "globally optimal" solution in the relaxed space, it might be far from the best solution in the original discrete space.

Methods

The authors propose the Integer Projected Fixed Point (IPFP) algorithm. Instead of solving a relaxed problem once, IPFP iteratively climbs the "quadratic score" (the measure of how good a match is) while staying close to the discrete domain.

The algorithm works in two main stages per iteration:

  1. Linear Approximation: It takes the current solution and creates a linear "best guess" of which direction improves the score most. It then finds the best discrete solution in that direction (using the Hungarian method for one-to-one matching or simple independent labeling for many-to-one tasks).
  2. Line Search: It then looks along the path between the current solution and that new discrete point to find the spot that maximizes the original quadratic score.

Crucially, IPFP is a "climbing" algorithm—the score is guaranteed to increase or stay the same at every step—and it typically converges in just 5 to 10 iterations, making it extremely fast.

IPFP convergence on Cars and Motorbikes datasets from various starting points

Datasets

The paper evaluates the algorithm on two distinct types of problems:

  • Graph Matching: They used image pairs of cars and motorbikes from the Pascal 2007 database. These are challenging because they contain many "outliers" (features in one image that have no match in the other) and significant variations in shape.
  • MAP Inference: They tested on synthetic 4-connected and 8-connected planar graphs, as well as graphs with varying edge densities, to simulate Markov Random Field (MRF) labeling problems.

Key Insights and Ideas

  • The "Relaxation Gap": The most striking insight is that a "well-designed local procedure" in the original discrete domain (like IPFP) is often more powerful than a "global procedure" in a loosely relaxed domain.
  • The Universal Booster: IPFP doesn't just work alone; it can take the output of any other graph matching algorithm (like Spectral Matching or Graduated Assignment) and refine it. In many cases, it dramatically improves the results of these older methods.
  • Parallel ICM: For MAP inference, IPFP acts as a parallel version of the classic Iterated Conditional Modes (ICM) algorithm. Unlike standard parallel ICM, which can oscillate or fail to converge, IPFP’s line-search step ensures it always climbs toward a local maximum.

Key Results

  • Graph Matching Performance: On the Pascal dataset, IPFP alone achieved a 64.4% matching rate, outperforming established methods like Spectral Matching (58.2%) and Graduated Assignment (46.7%).
  • Massive Improvements: When used to post-process other algorithms, the gains were huge. For example, it improved Probabilistic Matching (PM) from a lowly 36.6% to 67.2%—a 30.6% jump in accuracy.
Matching accuracy on Cars and Motorbikes datasets, showing IPFP as a standalone solver and a booster
  • MAP Inference: IPFP significantly outperformed Max-Product Belief Propagation (BP) and sequential ICM on random graph labeling tasks, reaching higher objective scores more consistently.
  • Efficiency: The algorithm is computationally "cheap," with a complexity similar to the linear assignment problems it solves internally.

Limitations and Future Work

  • Local Optima: Like all climbing algorithms, IPFP is a local optimizer. While the paper shows it is robust, its final result still depends on where it starts (the initial "guess").
  • Positive Definiteness: The paper notes that if the compatibility matrix is positive definite, the problem becomes a concave minimization, which is notoriously difficult to solve globally.
  • Future Directions: While not explicitly detailed, the framework suggests IPFP could be extended to higher-order matching (hypergraphs) or integrated more deeply into end-to-end machine learning pipelines.

Summary updated

Abstract

Graph matching and MAP inference are essential problems in computer vision and machine learning. We introduce a novel algorithm that can accommodate both problems and solve them efficiently. Recent graph matching algorithms are based on a general quadratic programming formulation, that takes in consideration both unary and second-order terms reflecting the similarities in local appearance as well as in the pairwise geometric relationships between the matched features. In this case the problem is NP-hard and a lot of effort has been spent in finding efficiently approximate solutions by relaxing the constraints of the original problem. Most algorithms find optimal continuous solutions of the modified problem, ignoring during the optimization the original discrete constraints. The continuous solution is quickly binarized at the end, but very little attention is put into this final discretization step. In this paper we argue that the stage in which a discrete solution is found is crucial for good performance. We propose an efficient algorithm, with climbing and convergence properties, that optimizes in the discrete domain the quadratic score, and it gives excellent results either by itself or by starting from the solution returned by any graph matching algorithm. In practice it outperforms state-or-the art algorithms and it also significantly improves their performance if used in combination. When applied to MAP inference, the algorithm is a parallel extension of Iterated Conditional Modes (ICM) with climbing and convergence properties that make it a compelling alternative to the sequential ICM. In our experiments on MAP inference our algorithm proved its effectiveness by outperforming ICM and Max-Product Belief Propagation.
BibTeX
@inproceedings{leordeanu2009integer,
  author = {Marius Leordeanu and Martial Hebert and Rahul Sukthankar},
  title = {{An Integer Projected Fixed Point Method for Graph Matching and MAP Inference}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=rybXmKb_ZH},
}
Figure