Generalized projection-based M-estimator

A New Approach to Robust Estimation of Parametric Structures

Most robust estimators require tuning the parameters of the algorithm for the particular application, a bottleneck for practical applications. The paper presents the multiple input structures with robust estimator (MISRE), where each structure, inlier or outlier, is processed independently. The same two constants are used to find the scale estimates over expansions for each structure. The inlier/outlier classification is straightforward since the data is processed and ordered with the relevant inlier structures listed first. If the inlier noises are similar, MISRE's performance is equivalent to RANSAC-type algorithms. MISRE still returns the correct inlier estimates when inlier noises are very different, while RANSAC-type algorithms do not perform as well. MISRE's failures are gradual when too many outliers are present, beginning with the least significant inlier structure. Examples from 2D images and 3D point clouds illustrate the estimation.

A Fast and Robust Rotation Search and Point Cloud Registration Method for 2D Stitching and 3D Object Localization

Rotation search and point cloud registration are two fundamental problems in robotics, geometric vision, and remote sensing, which aim to estimate the rotation and transformation between the 3D vector sets and point clouds, respectively. Due to the presence of outliers (probably in very large numbers) among the putative vector or point correspondences in real-world applications, robust estimation is of great importance. In this paper, we present Inlier searching using COmpatible Structures (ICOS), a novel, efficient, and highly robust solver for both the correspondence-based rotation search and point cloud registration problems. Specifically, we (i) propose and construct a series of compatible structures for the two problems, based on which various invariants can be established, and (ii) design time-efficient frameworks to filter out outliers and seek inliers from the invariant-constrained random sampling based on the compatible structures proposed. In this manner, even with extreme outlier ratios, inliers can be effectively sifted out and collected for solving the optimal rotation and transformation, leading to our robust solver ICOS. Through plentiful experiments over standard datasets, we demonstrated that: (i) our solver ICOS is fast, accurate, and robust against over 95% outliers with nearly a 100% recall ratio of inliers for rotation search and both known-scale and unknown-scale registration, outperforming other state-of-the-art methods, and (ii) ICOS is practical for use in real-world application problems including 2D image stitching and 3D object localization.

Deterministic Model Fitting by Local-neighbor Preservation and Global-residual Optimization

Geometric model fitting has been widely used in many computer vision tasks. However, it remains as a challenging task when handing multiple-structural data contaminated by noises and outliers. Most previous work on model fitting cannot guarantee the consistency of their solutions due to their randomness, precluding them from many real-world applications. In this research, we propose a fast two-view approximately deterministic model fitting scheme (called LGF), to provide consistent solutions for multiple-structural data. The proposed LGF scheme starts from defining preference function by preserving local neighborhood relationship, and then adopts the min-hash technique to roughly sample subsets. By this way, it is able to cover all model instances in data in the parameter space with a high probability. After that, LGF refines the previous sampled subsets by globalresidual optimization. Furthermore, we propose a simple yet effective model selection framework to estimate the number and the parameters of model instances in data. Extensive experiments on real images show that the proposed LGF scheme is able to observe superior or very competitive performance on both accuracy and speed over several state-of-the-art model fitting methods.

Quantized Residual Preference Based Linkage Clustering for Model Selection and Inlier Segmentation in Geometric Multi-Model Fitting

In this paper, quantized residual preference is proposed to represent the hypotheses and the points for model selection and inlier segmentation in multi-structure geometric model fitting. First, a quantized residual preference is proposed to represent the hypotheses. Through a weighted similarity measurement and linkage clustering, similar hypotheses are put into one cluster, and hypotheses with good quality are selected from the clusters as the model selection results. After this, the quantized residual preference is also used to present the data points, and through the linkage clustering, the inliers belonging to the same model can be separated from the outliers. To exclude outliers as many as possible, an iterative sampling and clustering process is performed within the clustering process until the clusters are stable. The experiments undertake indicate that the proposed method performs even better on real data than the some state-of-the-art methods.

Outlier Detection Based on Residual Histogram Preference for Geometric Multi-Model Fitting

Geometric model fitting is a fundamental issue in computer vision, and the fitting accuracy is affected by outliers. In order to eliminate the impact of the outliers, the inlier threshold or scale estimator is usually adopted. However, a single inlier threshold cannot satisfy multiple models in the data, and scale estimators with a certain noise distribution model work poorly in geometric model fitting. It can be observed that the residuals of outliers are big for all true models in the data, which makes the consensus of the outliers. Based on this observation, we propose a preference analysis method based on residual histograms to study the outlier consensus for outlier detection in this paper. We have found that the outlier consensus makes the outliers gather away from the inliers on the designed residual histogram preference space, which is quite convenient to separate outliers from inliers through linkage clustering. After the outliers are detected and removed, a linkage clustering with permutation preference is introduced to segment the inliers. In addition, in order to make the linkage clustering process stable and robust, an alternative sampling and clustering framework is proposed in both the outlier detection and inlier segmentation processes. The experimental results also show that the outlier detection scheme based on residual histogram preference can detect most of the outliers in the data sets, and the fitting results are better than most of the state-of-the-art methods in geometric multi-model fitting.

Searching for Representative Modes on Hypergraphs for Robust Geometric Model Fitting

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 first 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.

Random sampling and model competition for guaranteed multiple consensus sets estimation

Robust extraction of consensus sets from noisy data is a fundamental problem in robot vision. Existing multimodel estimation algorithms have shown success on large consensus sets estimations. One remaining challenge is to extract small consensus sets in cluttered multimodel data set. In this article, we present an effective multimodel extraction method to solve this challenge. Our technique is based on smallest consensus set random sampling, which we prove can guarantee to extract all consensus sets larger than the smallest set from input data. We then develop an efficient model competition scheme that iteratively removes redundant and incorrect model samplings. Extensive experiments on both synthetic data and real data with high percentage of outliers and multimodel intersections demonstrate the superiority of our method.

Exploiting Unsupervised and Supervised Constraints for Subspace Clustering

Data in many image and video analysis tasks can be viewed as points drawn from multiple low-dimensional subspaces with each subspace corresponding to one category or class. One basic task for processing such kind of data is to separate the points according to the underlying subspace, referred to as subspace clustering. Extensive studies have been made on this subject, and nearly all of them use unconstrained subspace models, meaning the points can be drawn from everywhere of a subspace, to represent the data. In this paper, we attempt to do subspace clustering based on a constrained subspace assumption that the data is further restricted in the corresponding subspaces, e.g., belonging to a submanifold or satisfying the spatial regularity constraint. This assumption usually describes the real data better, such as differently moving objects in a video scene and face images of different subjects under varying illumination. A unified integer linear programming optimization framework is used to approach subspace clustering, which can be efficiently solved by a branch-and-bound (BB) method. We also show that various kinds of supervised information, such as subspace number, outlier ratio, pairwise constraints, size prior and etc., can be conveniently incorporated into the proposed framework. Experiments on real data show that the proposed method outperforms the state-of-the-art algorithms significantly in clustering accuracy. The effectiveness of the proposed method in exploiting supervised information is also demonstrated.