Bias in Robust Estimation Caused by Discontinuities and Multiple Structures
Abstract—When fitting models to data containing multiple structures, such as when fitting surface patches to data taken from a neighborhood that includes a range discontinuity, robust estimators must tolerate both gross outliers and pseudo outliers. Pseudo outliers are outliers to the structure of interest, but inliers to a different structure. They differ from gross outliers because of their coherence. Such data occurs frequently in computer vision problems, including motion estimation, model fitting, and range data analysis. The focus in this paper is the problem of fitting surfaces near discontinuities in range data.
To characterize the performance of least median of the squares, least trimmed squares, M-estimators, Hough transforms, RANSAC, and MINPRAN on this type of data, the "pseudo outlier bias" metric is developed using techniques from the robust statistics literature, and it is used to study the error in robust fits caused by distributions modeling various types of discontinuities. The results show each robust estimator to be biased at small, but substantial, discontinuities. They also show the circumstances under which different estimators are most effective. Most importantly, the results imply present estimators should be used with care, and new estimators should be developed.
[1] 818 S. Ayer and H. Sawhney, "Layered Representation of Motion Video Using Robust Maximum-Likelihood Estimation of Mixture Models and mdl Encoding," Int'l Conf. Computer Vision, pp. 777-784,Cambridge, Mass., June 1995.
[2] P.J. Besl,J. B. Birch,, and L.T. Watson,“Robust window operators,” Proc. 2nd Int’l Conf. on Computer Vision, pp. 591-600, 1988.
[3] P.J. Besl and R.C. Jain,“Segmentation through variable-order surface fitting,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 2, pp. 167-191, Mar. 1988.
[4] R.C. Bolles and M.A. Fischler, "A Ransac-Based Approach to Model Fitting and Its Application to Finding Cylinders in Range Data," Proc. Seventh Int'l Joint Conf. Artificial Intelligence, pp. 637-643, 1981.
[5] K.L. Boyer, M.J. Mirza, and G. Ganguly, "The Robust Sequential Estimator: A General Approach and Its Application to Surface Organization in Range Data," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 10, pp. 987-1,001, Oct. 1994.
[6] T. Darrell and A. Pentland, "Cooperative Robust Estimation Using Layers of Support," Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 474-487, May 1995.
[7] M.A. Fischler and R.C. Bolles, "Random Sample Consensus: A Paradign for Model Fitting with Applications to Image Analysis and Automated Cartography," Comm. ACM, vol. 24, pp. 381-395, 1981.
[8] J.D. Gaskill, Linear Systems, Fourier Transforms, and Optics.New York: John Wiley and Sons, 1978.
[9] F.R. Hampel, P.J. Rousseeuw, and E. Ronchetti, "The Change-of-Variance Curve and Optimal Redescending M-Estimators," J. Am. Statistical Assoc., vol. 76, pp. 643-648, 1981.
[10] F.R. Hampel, P.J. Rousseeuw, E. Ronchetti, and W.A. Stahel, Robust Statistics: The Approach Based on Influence Functions.New York: John Wiley&Sons, 1986.
[11] P.W. Holland and R.E. Welsch, "Robust Regression Using Iteratively Reweighted Least-Squares," Communications of Statististics-Theoretical Methods, vol A6, pp. 813-827, 1977.
[12] P.J. Huber, Robust Statistics.New York: John Wiley&Sons, 1981.
[13] J. Illingworth and J. Kittler, "A Survey of the Hough Transform," Computer Vision, Graphics, and Image Processing, vol. 44, pp. 87-116, 1988.
[14] 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.
[15] A. Leonardis, A. Gupta, and R. Bajcsy, "Segmentation of Range Images as the Search for Geometric Parametric Models," Int'l J. Computer Vision, vol. 14, pp. 253-277, 1995.
[16] P. Meer, D. Mintz, A. Rosenfeld, and D.Y. Kim, "Robust Regression Methods for Computer Vision: A Review," Int'l J. Computer Vision, vol. 6, pp. 59-70, 1991.
[17] J.V. Miller and C.V. Stewart, "MUSE: Robust Surface Fitting Using Unbiased Scale Estimates," Proc. Computer Vision and Pattern Recognition '96, pp. 300-306,San Francisco, June 1996.
[18] M.J. Mirza and K.L. Boyer, "Performance Evaluation of a Class of M-Estimators for Surface Parameter Estimation in Noisy Range Data," IEEE Trans. Robotics and Automation, vol. 9, pp. 75-85, 1993.
[19] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C: The Art of Scientific Computing. Cambridge Univ. Press, 1992.
[20] G. Roth and M.D. Levine, "Extracting Geometric Primitives," Computer Vision, Graphics, and Image Processing: Image Understanding, vol. 58, pp. 1-22, 1993.
[21] P.J. Rousseeuw, "Least Median of Squares Regression," J. Am. Statistical Assoc., vol. 79, pp. 871-880, 1984.
[22] P.J. Rousseeuw and C. Croux, "Alternatives to the Median Absolute Deviation," J. Am. Statistical Assoc. vol. 88, pp. 1,273-1,283, 1993.
[23] C.V. Stewart,“A new robust operator for computer vision: Application to range images,” Proc. IEEE Conf. Computer Vision and Pattern Recognition pp. 167-173, 1994.
[24] C.V. Stewart,“A new robust operator for computer vision: Theoretical analysis,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 1-8, 1994.
[25] C.V. Stewart, "Expected Performance of Robust Estimators Near Discontinuities," Proc. Fifth Int'l Conf. Computer Vision, pp. 969-974,Boston, Mass., June 1995.
[26] 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.
[27] C.V. Stewart, "Bias in Robust Estimation Caused by Discontinuities and Multiple Structures," Technical Report 96-4, Dept. of Computer Science, Rensselaer Polytechnic Inst. (see also http://www.cs.rpi.edu/~stewart), 1996.
[28] D.M. Titterington, A.F.M. Smith, and U.E. Makov, Statistical Analysis of Finite Mixture Distributions.New York: John Wiley and Sons, 1985.
[29] J.Y.A. Wang and E. Adelson, "Layered Representation for Motion Analysis," Proc. Computer Vision and Pattern Recognition Conf., 1993.
Index Terms:
Robust estimation, outliers, parameter estimation, discontinuities, multiple structures, bias.
Citation:
Charles V. Stewart, "Bias in Robust Estimation Caused by Discontinuities and Multiple Structures," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 8, pp. 818-833, Aug., 1997
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb