Feature Matching Based on Graph Clustering: Implementation and Application of Local Affine Consensus

Academic Background and Motivation

Feature matching is a fundamental problem in computer vision, playing a critical role in various tasks such as 3D reconstruction, image retrieval, image registration, and simultaneous localization and mapping (SLAM). However, in practical applications, feature matching often encounters challenges such as noise, outliers, and diverse image transformations, making it difficult to establish accurate feature correspondences. Existing graph-based feature matching methods alleviate this problem due to their powerful structural representation capabilities but still face the following challenges:

1. Graph matching problems are typically NP-hard, resulting in high computational complexity.
2. Constructing geometrically meaningful graphs to represent relationships between feature points remains challenging.

To address these issues, this study proposes a method called GC-LAC (Graph Clustering with Local Affine Consensus), which transforms the feature matching task into a graph clustering problem and achieves efficient and general-purpose feature matching through a local affine strategy and robust graph clustering algorithm.

Paper Source and Author Information

This paper was authored by Yifan Lu and Jiayi Ma from Wuhan University and published in the International Journal of Computer Vision. The DOI of the paper is 10.1007/s11263-024-02291-5. It was submitted on September 9, 2022, and accepted on October 28, 2024.

Methodology and Workflow

Overview of the Research Method

GC-LAC comprises two core components: 1. Robust Graph Construction: Constructs sparse graphs that accurately represent the geometric relationships between feature points using a local affine consensus strategy. 2. Robust Graph Clustering: Introduces a novel density-driven graph clustering algorithm, D2SCAN, to extract reliable feature correspondences from outlier-contaminated data.

Research Workflow

1. Graph Construction

• Geometric Consistency Encoding: Each feature match is treated as a graph node, with edge weights computed based on geometric consistency between feature point pairs.
• Local Affine Strategy: Assumes that image transformations can be approximated by multiple locally affine transformations, dividing the image space into local regions using a sliding window.
• Sparse Graph Structure: Constructs sparse graphs guided by the motion coherence prior, reducing computational complexity.

2. Graph Clustering

• D2SCAN Algorithm: Combines Dominant Set Clustering and DBSCAN to introduce a new algorithm:
  • Defines a new standard for density-reachable nodes.
  • Uses replicator dynamics to optimize the clustering objective function.
  • Provides linear time complexity suitable for large-scale real-time tasks.

Key Innovations

1. Transforms the feature matching task into a density-driven robust graph clustering problem, filtering outliers while automatically discovering multiple visual patterns.
2. Proposes a local geometric consensus strategy and a motion coherence-driven geometric solver (MCDG), adaptable to various image transformations.
3. Introduces the robust graph clustering algorithm D2SCAN, overcoming the sensitivity to outliers and significantly improving clustering efficiency and effectiveness.

Experiments and Results

Experimental Setup

Experiments evaluate feature matching tasks in various scenarios and their applications in geometric estimation, relative pose estimation, loop detection, and other vision tasks. Test datasets encompass different image transformation types (rigid, non-rigid, multi-model motion).

Datasets and Evaluation Metrics

• Datasets: Public datasets such as AdelaideRMF, VGG40, and Nonrigid.
• Metrics: Precision, recall, F1-score for feature matching, and symmetric geometric distance (SGD) for geometric estimation.

Results

Feature Matching

• Qualitative Analysis: GC-LAC generates accurate and robust feature correspondences under complex scenarios, including non-rigid deformations and multiple motion patterns.
• Quantitative Comparison: GC-LAC outperforms state-of-the-art methods in precision, recall, and computational efficiency on VGG40 and AdelaideRMF datasets.

Geometric Estimation

• Using feature correspondence sets from GC-LAC combined with robust estimators (e.g., RANSAC), GC-LAC demonstrates outstanding performance on homography estimation (EVD dataset) and fundamental matrix estimation (TUM dataset).

Relative Pose Estimation

• On the YFCC100M dataset, GC-LAC exhibits superior generalization capabilities compared to deep learning methods like SuperGlue, particularly in unseen scenes.

Algorithm Complexity

GC-LAC’s computational complexity is approximately linear, significantly reducing complexity compared to traditional graph matching methods, making it suitable for large-scale or real-time applications.

Significance and Value

The proposed GC-LAC method addresses the challenges of outlier filtering and multi-visual pattern discovery in feature matching. Its sparse graph construction and robust clustering strategy demonstrate powerful performance across various tasks, offering significant scientific value and practical application potential.