Robust fitting of multiple models with J-linkage and T-linkage

with R. Toldo and L. Magri

J-linkage

J-linkage [1] is a method for fitting multiple instances of a model to data corrupted by noise and outliers. RANSAC, for comparison, fits a single instance of a model to data corrupted by noise and outliers. The proposed solution is based on random sampling (as RANSAC) and conceptual data representation. Each point is represented with the characteristic function of its preference set, i.e., the set of models that fitthe point within a tolerance. Points belonging to the same model will have similar preference sets, in other words, they will cluster in the conceptual space. A tailored linkage clustering based on Jaccard distance is then qused to group points belonging to the same model. A real-time version of J-linkage have been proposed in [3] [Video].

In this work we improve the efficiency of J-Linkage with an efficient min-hash scheme that approximates the Jaccard distance and allows to tackle large dataset, such as laser scans of entire buildings (Scan2BIM).

In [4,5] we included image consistency constraints into J-linkage with the aim of fitting planar patches coresponding to actual surfaces instead of planes to 3D data. [Video 2010] [Video 2013]

T-linkage

In T-Linkage [2] the binary preference analysis implemented by J-linkage is replaced by a continuous (soft, or fuzzy) generalization, and the Tanimoto Jaccard distance takes the place of Jaccard. 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). 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.

T-Linkage have been extended here to cope with multiple heterogeneous models (i.e., multiple istances of multiple classes of models).

Other methods for robust fitting of multiple models we proposed are RPA and RansaCov.

Code

Reference papers

  1. Toldo, R. and Fusiello, A. Robust Multiple Structures Estimation with J-Linkage. In Proceedings of the European Conference on Computer Vision (ECCV), pages 537-547, Springer, Marseille, FR, Lecture Notes in Computer Science 5302, 2008. PDF
  2. Magri, L. and Fusiello, A. T-Linkage: A Continuous Relaxation of J-Linkage for Multi-Model Fitting. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014. PDF
  3. Toldo, R. and Fusiello, A. Real-time Incremental J-Linkage for Robust Multiple Structures Estimation. In Proceedings of the International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT), 2010. PDF
  4. Toldo, R. and Fusiello, A. Photo-consistent Planar Patches from Unstructured Cloud of Points. In Proceedings of the European Conference on Computer Vision (ECCV), pages 589-602, Springer, Lecture Notes in Computer Science , 2010. PDF
  5. Toldo, R. and Fusiello, A. Image-consistent patches from unstructured points with J-linkage. In Image and Vision Computing, 31 (10): 756-770, 2013. PDF