Tejaswi with HTML5 Markup

Tejaswi Agarwal Graduate student @ UW-Madison

5. MC-RANSAC: A Pre-processing Model for RANSAC using Monte Carlo method implemented on a GPU

Guide: Dr. K Muthunagai, Vellore Institute of Technology, Chennai, India

Probability and Statistics Course Project, Chennai, India

Published at the Student Research Symposium, ICACCI 2013, Mysore, India

RANSAC is a repeating hypothesize-and-verify procedure for parameter estimation and filtering of noise or outlier data. In the traditional approach, this algorithm is evaluated without any prior information on the set of data points which leads to an increase in the number of iterations and compute time. In this work, we implemented a GPU based RANSAC algorithm with pre-processing of the assumed sample set of hypothetical inliers by Monte Carlo method. Based on our implementation and results using the Point Cloud Library and NVIDIA CUDA framework for data intensive tasks we obtain significant improvement in the performance of plane segmentation algorithm over the randomly sampled subset of hypothetical inliers. The final consensus set is formed with less number of iterations using our pre-processing model. We can conclude that a pre-processed sample set of hypothetical inliers results in a faster determination of the consensus set consisting of maximum inliers


The results of MC-RANSAC on GPU were compared with the traditional RANSAC and a significant change in the number of iterations was observed. With significant advances in accelerators, our model performed better than the existing RANSAC extensions proposed on the CPU. In order to scale the proposed algorithm, better hardware capabilities would sufficiently enhance the performance. Also, enhanced sampling techniques can further increase the determination of the consensus set with minimum number of iterations


[1] Fisher, M., Bolles, R.: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. of the ACM 24(6), 381-395 (1981).

[2] Matas, J., Chum, O.: Randomized RANSAC with Td,d test. Image and Vision Computing 22(10), 837-842 (2004)

[3] Matas, J., Chum, O.: Randomized RANSAC with Sequential Probability Ratio Test. In: Proc. ICCV, pp. 1727-1732 (2005)

[4] Rahul Raguram1, Jan-Michael Frahm1, and Marc Pollefeys1,2; A Comparative Analysis of RANSAC Techniques Leading to Adaptive Real-Time Random Sample Consensus.In: ECCV 2008, Part II, LNCS 5303, pp. 500-513, 2008. Springer-Verlag Berlin Heidelberg 2008

[5] Fijany, A. Diotalevi, F, A cooperative search algorithm for highly parallel implementation of RANSAC for model estimation on Tilera MIMD architecture, IEEE Aerospace Conference, 2012.

[6] Nister, D.: Preemptive RANSAC for live structure and motion estimation. In: Proc. ICCV, vol. 1, pp. 199-206 (2003).

[7] Point Cloud Library, www.pointclouds.org

[8] Torsten Sattler, Bastian Leibe and Leif Kobbelt, " SCRAMSAC: Improving RANSAC's Efficiency with a Spatial Consistency Filter "

[9] Matas J, Randomized RANSAC using Sequential Probability Ratio Test, In: ICCV 2005. Tenth IEEE International Conference on Computer Vision, 2005.

[10] Sunglok Choi, Taemin Kim, and Wonpil Yu (2009). "Performance Evaluation of RANSAC Family". In: Proceedings of the British Machine Vision Conference (BMVC).

[11] Xiaoyan Wang,Hui Zhang and Sheng Liu,Reliable RANSAC Using a Novel Preprocessing Model, Computational and Mathematical Methods in Medicine Volume 2013.