Robust Model Fitting, Random Sample Consensus, Least Median Of Squares, Residual Consensus, Adaptive Least Kth Order Squares, Kernel Density Estimation, Mean Shift, Range Image Segmentation, Fundamental Matrix Estimation
Abstract
Robust model fitting essentially requires the application of two estimators. The first is an estimator for the values of the model parameters. The second is an estimator for the scale of the noise in the (inlier) data. Indeed, we propose two novel robust techniques: the Two-Step Scale estimator (TSSE) and the Adaptive Scale Sample Consensus (ASSC) estimator. TSSE applies nonparametric density estimation and density gradient estimation techniques, to robustly estimate the scale of the inliers. The ASSC estimator combines Random Sample Consensus (RANSAC) and TSSE: using a modified objective function that depends upon both the number of inliers and the corresponding scale. ASSC is very robust to discontinuous signals and data with multiple structures, being able to tolerate more than 80 percent outliers. The main advantage of ASSC over RANSAC is that prior knowledge about the scale of inliers is not needed. ASSC can simultaneously estimate the parameters of a model and the scale of the inliers belonging to that model. Experiments on synthetic data show that ASSC has better robustness to heavily corrupted data than Least Median Squares (LMedS), Residual Consensus (RESC), and Adaptive Least Kth order Squares (ALKS). We also apply ASSC to two fundamental computer vision tasks: range image segmentation and robust fundamental matrix estimation. Experiments show very promising results.
1. A. Bab-Hadiashar, and D. Suter, "Robust Optic Flow Computation," Int'l J. Computer Vision, vol. 29, no. 1, pp. 59-77, 1998.
2. A. Bab-Hadiashar, and D. Suter, "Robust Segmentation of Visual Data Using Ranked Unbiased Scale Estimate," ROBOTICA, Int'l J. Information, Education and Research in Robotics and Artificial
Intelligence, vol. 17, pp. 649-660, 1999.
3. M.J. Black, and A.D. Jepson, "EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-Based
Representation," Int'l J. Computer Vision, vol. 26, pp. 63-84, 1998.
4. H. Chen, and P. Meer, "Robust Computer Vision through Kernel Density Estimation," Proc. European Conf. Computer Vision, pp. 236-250, 2002.
5. H. Chen, and P. Meer, "Robust Regression with Projection Based M-Estimators," Proc Ninth Int'l Conf. Computer Vision, 2003.
6. H. Chen, P. Meer, and D.E. Tyler, "Robust Regression for Data with Multiple Structures," Proc. 2001 IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2001.
7. Y. Cheng, "Mean Shift, Mode Seeking, and Clustering," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 790-799, 1995.
8. D. Comaniciu, and P. Meer, "Robust Analysis of Feature Spaces: Color Image Segmentation," Proc. 1997 IEEE Conf. Computer Vision and Pattern Recognition, pp. 750-755, 1997.
9. D. Comaniciu, and P. Meer, "Mean Shift Analysis and Applications," Proc. Seventh Int'l Conf. Computer Vision, pp. 1197-1203, 1999.
10. D. Comaniciu, and P. Meer, "Mean Shift: A Robust Approach towards Feature Space A Analysis," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603-619, May 2002.
11. D. Comaniciu, V. Ramesh, and A.D. Bue, "Multivariate Saddle Point Detection for Statistical Clustering," Proc. Europe Conf. Computer Vision (ECCV), 2002.
12. D. Comaniciu, V. Ramesh, and P. Meer, "The Variable Bandwidth Mean Shift and Data-Driven Scale Selection," Proc. Eighth Int'l Conf. Computer Vision, 2001.
13. M.A. Fischler, and R.C. Rolles, "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image
Analysis and Automated Cartography," Comm. ACM, vol. 24, no. 6, pp. 381-395, 1981.
14. K. Fukunaga, and L.D. Hostetler, "The Estimation of the Gradient of a Density Function, with Applications in Pattern
Recognition," IEEE Trans. Information Theory, vol. 21, pp. 32-40, 1975.
15. P. Gotardo, O. Bellon, and L. Silva, "Range Image Segmentation by Surface Extraction Using an Improved Robust Estimator," Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2003.
16. A. Hoover, G. Jean-Baptiste, and X. Jiang, "An Experimental Comparison of Range Image Segmentation Algorithms," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 7, pp. 673-689, July 1996.
17. P.V.C. Hough, "Methods and Means for Recognising Complex Patterns," US Patent 3 069 654, 1962.
18. P.J. Huber, Robust Statistics. Wiley, 1981.
19. K. Koster, and M. Spann, "MIR: An Approach to Robust Clustering—Application to Range Image Segmentation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 5, pp. 430-444, May 2000.
20. K.-M. Lee, P. Meer, and R.-H. Park, "Robust Adaptive Segmentation of Range Images," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 2, pp. 200-205, Feb. 1998.
21. J.V. Miller, and C.V. Stewart, "MUSE: Robust Surface Fitting Using Unbiased Scale Estimates," Proc. Conf. Computer Vision and Pattern Recognition, 1996.
22. E.P. Ong, and M. Spann, "Robust Optical Flow Computation Based on Least-Median-of-Squares Regression," Int'l J. Computer Vision, vol. 31, no. 1, pp. 51-82, 1999.
23. P.J. Rousseeuw, "Least Median of Squares Regression," J. Am. Statistics Assoc., vol. 79, pp. 871-880, 1984.
24. P.J. Rousseeuw, and C. Croux, "Alternatives to the Median Absolute Derivation," J. Am. Statistical Associaion, vol. 88,
no. 424, pp. 1273-1283, 1993.
25. P.J. Rousseeuw, and A. Leroy, Robust Regression and Outlier Detection. John Wiley & Sons, 1987.
26. D.W. Scott, "Parametric Statistical Modeling by Minimum Integrated Square Error," Technometrics, vol. 43, no. 3, pp. 274-285, 2001.
27. A.F. Siegel, "Robust Regression Using Repeated Medians," Biometrika, vol. 69, pp. 242-244, 1982.
28. B.W. Silverman, Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
29. C.V. Stewart, "MINPRAN: A New Robust Estimator for Computer Vision," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17,
no. 10, pp. 925-938, Oct. 1995.
30. C.V. Stewart, "Bias in Robust Estimation Caused by Discontinuities and Multiple Structures," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 8, pp. 818-833, Aug. 1997.
31. C.V. Stewart, "Robust Parameter Estimation in Computer Vision," SIAM Rev., vol. 41, no. 3, pp. 513-537, 1999.
32. G.R. Terrell, and D.W. Scott, "Oversmoothed Nonparametric Density Estimates," J. Am. Statistical Association, vol. 80, pp. 209-214, 1985.
33. P. Torr, and D. Murray, "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix," Int'l J. Computer Vision, vol. 24, pp. 271-300, 1997.
34. P. Torr, and A. Zisserman, "MLESAC: A New Robust Estimator With Application to Estimating Image Geometry," Computer Vision and Image Understanding, vol. 78, no. 1, pp. 138-156, 2000.
35. M.P. Wand, and M. Jones, Kernel Smoothing. Chapman & Hall, 1995.
36. H. Wang, and D. Suter, "MDPE: A Very Robust Estimator for Model Fitting and Range Image Segmentation," Int'l J. Computer Vision, to appear.
37. H. Wang, and D. Suter, "False-Peaks-Avoiding Mean Shift Method for Unsupervised Peak-Valley Sliding Image
Segmentation," Digital Image Computing Techniques and Applications, pp. 581-590, 2003.
38. H. Wang, and D. Suter, "Variable Bandwidth QMDPE and Its Application in Robust Optic Flow Estimation," Proc. Int'l Conf. Computer Vision, pp. 178-183, 2003.
39. X. Yu, T.D. Bui, and A. Krzyzak, "Robust Estimation for Range Image Segmentation and Reconstruction," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 5, pp. 530-538, May 1994.
40. Z. Zhang et al., "A Robust Technique for Matching Two Uncalibrated Image through the Recovery of the
Unknown Epipolar Geometry," Artificial Intelligence, vol. 78, pp. 87-119, 1995.