Abstract
In this paper, we propose a novel hierarchical representation via message propagation (HRMP) method for robust model fitting, which simultaneously takes advantages of both the consensus analysis and the preference analysis to estimate the parameters of multiple model instances from data corrupted by outliers. Instead of analyzing the information of each data point or each model hypothesis independently, we formulate the consensus information and the preference information as a hierarchical representation to alleviate the sensitivity to gross outliers. Specifically, we firstly construct a hierarchical representation, which consists of a model hypothesis layer and a data point layer. The model hypothesis layer is used to remove insignificant model hypotheses and the data point layer is used to remove gross outliers. Then, based on the hierarchical representation, we propose an effective hierarchical message propagation (HMP) algorithm and an improved affinity propagation (IAP) algorithm to prune insignificant vertices and cluster the remaining data points, respectively. Experimental results on both synthetic data and real images show that the proposed HRMP significantly outperforms several state-of-the-art model fitting methods in terms of fitting accuracy and speed.
Introduction
Model fitting is a cornerstone of computer vision, essential for identifying geometric structures like lines, circles, or planes within raw data. However, real-world datasets are rarely clean; they are typically plagued by noise, pseudo-outliers (points belonging to different structures), and gross outliers (random noise).
Existing techniques generally fall into two categories: consensus-based methods, which seek models with the highest data support, and preference-based methods, which analyze which models individual points prefer. While consensus methods struggle with redundant hypotheses, preference methods often require sensitive, manually-tuned thresholds. HRMP addresses these issues by combining both perspectives into a unified hierarchical framework.
Methodology
1. Hierarchical Graph Construction
The HRMP method begins by constructing a two-layer graph. The top layer, $\mathcal{V}^h$, contains model hypotheses generated from the data, while the bottom layer, $\mathcal{V}^d$, contains the data points themselves. Edges between these layers represent the affinity between a point and a hypothesis.
2. Hierarchical Message Propagation (HMP)
To handle heavy outlier contamination, the algorithm employs a pruning phase called Hierarchical Message Propagation. Messages are passed bidirectionally:
- Consensus Messages: Points send messages to hypotheses to evaluate their global quality.
- Preference Messages: Hypotheses send messages to points to determine their likelihood of being inliers.
This process allows the system to identify and discard "junk" hypotheses and gross outliers before the final clustering step, drastically reducing computational overhead.
3. Improved Affinity Propagation (IAP)
Once the data is pruned, the remaining points must be grouped into distinct structures. HRMP utilizes an improved version of Affinity Propagation (AP). By introducing a sparse graph and a Tanimoto-like similarity measure, the IAP algorithm becomes more robust to intersections where multiple structures might overlap, ensuring cleaner segmentation of complex multi-structural data.
Adaptive Thresholding
A significant challenge in robust fitting is determining the boundary between inliers and outliers without prior knowledge of the noise level. HRMP solves this by using a 1D Gaussian Mixture Model (GMM) to analyze the distribution of weighting scores. This allows the algorithm to automatically learn the optimal threshold for each specific dataset.
Key Results
The HRMP method was tested against 11 state-of-the-art algorithms on synthetic data, the AdelaideRMF benchmark, and industrial images. Key findings include:
- Speed: HRMP achieved massive speedups, performing up to 360 times faster than T-Linkage in circle-fitting tasks.
- Robustness: The method successfully estimated the correct number of structures even when outliers exceeded 80-90% of the total data points.
- Accuracy: On real-world motion segmentation tasks, HRMP consistently achieved the lowest median fitting error, demonstrating its practical utility for complex perspective and motion analysis.
Conclusion
By integrating consensus and preference analysis into a hierarchical message-passing framework, HRMP provides a fast and robust solution for multi-structural model fitting. While the method is highly effective, its performance depends on the quality of initial hypothesis sampling. Future research may focus on more advanced sampling strategies to ensure even the smallest structures are captured in the initial hypothesis layer.
Summary updated