Searching for Representative Modes on Hypergraphs for Robust Geometric Model Fitting

Hanzi Wang, Guobao Xiao, Yan Yan, David Suter

Abstract

Robust geometric model fitting is a fundamental challenge in computer vision, particularly when dealing with high outlier ratios and multiple overlapping structures. This paper introduces Mode-Seeking on Hypergraphs Fitting (MSHF), a framework that conceptualizes model fitting as a search for "authority peaks" within a hypergraph. By representing model hypotheses as vertices and data points as hyperedges, MSHF effectively segments multiple structures and automatically estimates the number of model instances. The method demonstrates superior performance in efficiency and robustness compared to traditional methods, even in the presence of up to 90% outliers.

Introduction

In computer vision, geometric model fitting involves identifying mathematical structures—such as lines, circles, or planes—within noisy datasets. This task is critical for applications like 3D reconstruction and object tracking. However, real-world data presents three significant hurdles: high outlier ratios, the presence of multiple intersecting structures, and unbalanced data where some structures have significantly fewer points than others.

Traditional tools like RANSAC are effective for single structures but struggle with multi-structure scenarios. While graph-based methods have been developed to address these complexities, they often suffer from high computational costs or lose critical information by simplifying multi-point relationships into pairwise links. MSHF addresses these limitations by utilizing a hypergraph representation that preserves higher-order data relationships.

Methodology

The MSHF framework operates in three distinct stages:

1. Hypergraph Construction

Unlike standard graphs, a hypergraph allows an edge to connect any number of vertices. In MSHF, each vertex represents a model hypothesis (e.g., a potential line), and each hyperedge represents a data point. A vertex is connected to a hyperedge if the corresponding data point is an inlier for that hypothesis. This structure captures the complex, higher-order similarities between hypotheses based on their shared data points.

The mapping between geometric data points/lines (a) and the corresponding hypergraph representation (b).

2. Hypergraph Reduction

To manage the computational load of a massive hypothesis space, the authors employ an information-theoretic reduction. By calculating the entropy of hypothesis weights, the algorithm prunes insignificant vertices. This step serves as both a performance optimization and a noise-reduction mechanism, preventing false detections in the hypothesis space.

3. Mode-Seeking for Authority Peaks

The core innovation of MSHF is the search for "authority peaks." These are vertices that possess high weighting scores (indicating a good fit for many points) and are distinct from other high-scoring vertices. The similarity between hypotheses is measured using a modified Tanimoto distance (T-distance). The algorithm identifies local maxima in this space that are "far" from each other in terms of their inlier sets, allowing it to distinguish between redundant hypotheses for the same structure and hypotheses representing distinct structures.

Experimental Evaluation

The authors evaluated MSHF against state-of-the-art competitors (including T-linkage, AKSWH, and RCG) using both synthetic and real-world datasets, such as the AdelaideRMF benchmark.

Key Results

  • Robustness to Noise: In synthetic tests with 90% outliers, MSHF maintained near-perfect accuracy, whereas competing methods failed as the data became increasingly unbalanced.
  • Real-World Accuracy: On the AdelaideRMF dataset, MSHF achieved the lowest average fitting error in 16 out of 19 image pairs for homography tasks.
  • Computational Efficiency: A variant of the method, MSHF2, demonstrated speeds up to 100x faster than T-linkage on complex datasets, making it viable for near real-time applications.
  • Automatic Model Selection: MSHF successfully estimated the number of models present in the data without requiring user-defined parameters for the count.
Identification of representative modes (authority peaks) using T-distance plots (a, b) and the resulting model segmentation on a real-world building image (c, d).

Discussion and Conclusion

MSHF represents a significant advancement in robust model fitting by leveraging the descriptive power of hypergraphs and the localization of mode-seeking. Its ability to characterize complex relationships without forcing fixed degrees on hyperedges allows it to find small structures even when they are obscured by larger ones.

The primary limitation identified is Hypothesis Dependency. Because the algorithm seeks modes among a set of generated hypotheses, it can only succeed if at least one "good" hypothesis is sampled initially. In cases where a structure represents a very small fraction of the total data (e.g., <5%), random sampling may fail to generate a representative candidate. Future research will focus on more intelligent sampling strategies to ensure even the most sparse structures are represented in the initial pool.

Summary updated

Abstract

In this paper, we propose a simple and effective {geometric} model fitting method to fit and segment multi-structure data even in the presence of severe outliers. We cast the task of geometric model fitting as a representative mode-seeking problem on hypergraphs. Specifically, a hypergraph is firstly constructed, where the vertices represent model hypotheses and the hyperedges denote data points. The hypergraph involves higher-order similarities (instead of pairwise similarities used on a simple graph), and it can characterize complex relationships between model hypotheses and data points. {In addition, we develop a hypergraph reduction technique to remove "insignificant" vertices while retaining as many "significant" vertices as possible in the hypergraph}. Based on the {simplified hypergraph, we then propose a novel mode-seeking algorithm to search for representative modes within reasonable time. Finally, the} proposed mode-seeking algorithm detects modes according to two key elements, i.e., the weighting scores of vertices and the similarity analysis between vertices. Overall, the proposed fitting method is able to efficiently and effectively estimate the number and the parameters of model instances in the data simultaneously. Experimental results demonstrate that the proposed method achieves significant superiority over {several} state-of-the-art model fitting methods on both synthetic data and real images.
BibTeX
@article{wang2018searching,
  author = {Hanzi Wang and Guobao Xiao and Yan Yan and David Suter},
  title = {{Searching for Representative Modes on Hypergraphs for Robust Geometric Model Fitting}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2018},
  doi = {10.1109/tpami.2018.2803173},
}
Figure