Robust fitting of multiple models

R. Toldo, A. Fusiello


This paper tackles the problem of fitting multiple instances of a model to data corrupted by noise and outliers. The proposed solution is based on random sampling and conceptual data representation. Each point is represented with the characteristic function of the set of random models that fit the point. A tailored agglomerative clustering, called J-linkage, is used to group points belonging to the same model. The method does not require prior specification of the number of models, nor it necessitate parameters tuning. Experimental results demonstrate the superior performances of the algorithm.

A list of applications of j-linkage.


The method starts with random sampling, as in RANSAC. Then we consider the preference set of each point, i.e., the set of models that are satisfied by the point within a tolerance. The characteristic function of the PS of a point can be regarded as a conceptual representation of that point. Points belonging to the same structure will have similar PS, in other words, they will cluster in the conceptual space. The J-linkage algorithm is an agglomerative clustering that proceeds by linking elements with Jaccard distance smaller than 1 and stop as soon as there are no such elements left.



Dataset Plane fitting results

Real-time J-linkage

Image consistent patches Video

Reference papers

A Continuous Relaxation of J-Linkage

L. Magri, A. Fusiello


T-linkage is an improvement of J-linkage for fitting multiple instances of a model to nois data corrupted by outliers. In T-Linkage the binary preference analysis implemented by J-linkage is replaced by a continuous (soft, or fuzzy) generalization. The benefits of working with continuous values rather than operating with hard thresholding is that we are allowed to integrate more specific information on residual for depicting points preferences (this parallels the difference between RANSAC and MSAC if Consensus Set is considered). Consequently the soft threshold parameter adopted by T-Linkage is a more educated guess compared to the J-Linkage hard inlier threshold. T-linkage also takes advantage of the more expressive representation of points both in term of misclassification error and robustness to outliers.



Dataset Video motion segmentation
Hopkins 155 dataset

Dataset Multi fundamental matrices fitting

Dataset Plane segmentation

The reference page for MCT - Fitting Multiple Heterogeneous Models by Multi-class Cascaded T-linkage - is here.

Reference paper