Improving Graph Matching via Density Maximization

Chao Wang, Lei Wang, Lingqiao LiuICCV 2013 · OpenReview

Abstract

Graph matching is a cornerstone of computer vision, yet it faces significant challenges: combinatorial complexity, sensitivity to outliers, and the restrictive assumption of a single object cluster. We introduce Density Maximization, a unified framework that addresses these issues by measuring match quality through a novel Graph Density Local Estimator (DLE). Our approach maximizes DLE both locally (via Density-Ascent Shift) and globally (via Density-Ascent Update) to filter outliers and handle many-to-many object correspondences. Density Maximization is orthogonal to existing graph matching solvers and demonstrates substantial improvements in accuracy and computational efficiency.

Introduction

Establishing correspondences between sparse features in images is essential for tasks like object recognition and 3D reconstruction. While graph matching provides a powerful framework for this by modeling spatial relationships, traditional methods often struggle in cluttered scenes or when multiple objects are present.

An example image pair containing multiple objects and background clutter, posing a challenge for traditional matching algorithms.

Traditional graph matching faces three primary hurdles:

  1. Combinatorial Complexity: The search space for matches grows exponentially, making global optimization difficult.
  2. Outlier Sensitivity: Objective functions often favor a higher quantity of matches, which can lead to the inclusion of noisy background features.
  3. Single-Cluster Assumption: Most algorithms assume all features belong to a single object, failing in scenes with multiple instances or repetitive patterns.

The Density Maximization Framework

We propose a framework that treats matching as the identification of "dense" clusters of geometrically consistent matches in a high-dimensional space.

The complete Density Maximization pipeline. The process begins with initial matches and graph matching, followed by an iterative loop of local pruning (DAS) and global expansion (DAU) to maximize match density.

Core Components

  • Density Local Estimator (DLE): The DLE assesses the quality of a match by examining its local neighborhood. It relies on the principle that true matches will have similar geometric transformations to their neighbors, whereas outliers will appear isolated or inconsistent.
  • Density-Ascent Shift (DAS): This local maximization step acts as a mode-seeking algorithm. It groups matches into clusters and prunes those identified as outliers based on their local density.
  • Density-Ascent Update (DAU): This global maximization step explores a "potential graph"—a larger set of candidate matches—to refine and expand the current set, effectively escaping local minima.

Crucially, this framework is orthogonal to specific graph matching algorithms; it serves as a powerful wrapper that enhances the output of existing solvers like Spectral Matching (SM) or Reweighted Random Walks (RRWM).

Key Insights and Methodology

  • Geometric Smoothness: The most critical insight is that geometric transformations vary smoothly among neighboring true matches. By enforcing this local smoothness via the DLE, the algorithm can effectively ignore clutter.
  • Efficiency through Sparsity: Instead of an exhaustive search, the framework focuses on a "potential graph" of the top unary matches. This captures the vast majority of true matches while maintaining computational tractability.
  • Iterative Refinement: By alternating between local pruning (DAS) and global expansion (DAU), the system avoids the noisy local minima that often plague traditional Integer Quadratic Programming (IQP) solvers.

Experimental Evaluation

The authors evaluated the method on Intra-class, ETHZ toys, and Co-recognition datasets. Key results include:

  • Accuracy Boost: On the Co-recognition dataset, the method improved precision by 36%–67% and recall by 18%–47% compared to standalone graph matching.
  • Computational Speed: The DAU component is more than ten times faster than previous state-of-the-art progressive matching techniques.
  • Robustness: The framework successfully identifies multiple distinct objects in a single scene and remains robust against heavy background clutter.

Conclusion

Density Maximization provides a scalable and robust solution for complex graph matching tasks. While the method shows impressive results, future work could address parameter sensitivity and the integration of higher-order hyper-graph constraints to further improve robustness to non-rigid deformations.

Summary updated

Abstract

Graph matching has been widely used in various applications in computer vision due to its powerful performance. However, it poses three challenges to image sparse feature matching: (1) The combinatorial nature limits the size of the possible matches, (2) It is sensitive to outliers because the objective function prefers more matches, (3) It works poorly when handling many-to-many object correspondences, due to its assumption of one single cluster for each graph. In this paper, we address these problems with a unified framework-Density Maximization. We propose a graph density local estimator (DLE) to measure the quality of matches. Density Maximization aims to maximize the DLE values both locally and globally. The local maximization of DLE finds the clusters of nodes as well as eliminates the outliers. The global maximization of DLE efficiently refines the matches by exploring a much larger matching space. Our Density Maximization is orthogonal to specific graph matching algorithms. Experimental evaluation demonstrates that it significantly boosts the true matches and enables graph matching to handle both outliers and many-to-many object correspondences.
BibTeX
@inproceedings{wang2013improving,
  author = {Chao Wang and Lei Wang and Lingqiao Liu},
  title = {{Improving Graph Matching via Density Maximization}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  url = {https://openreview.net/forum?id=rkZi8bGdZH},
}
Figure