An Experimental Comparison of Range Image Segmentation Algorithms
|
Abstract—A methodology for evaluating range image segmentation algorithms is proposed. This methodology involves 1) a common set of 40 laser range finder images and 40 structured light scanner images that have manually specified ground truth and 2) a set of defined performance metrics for instances of correctly segmented, missed, and noise regions, over- and under-segmentation, and accuracy of the recovered geometry. A tool is used to objectively compare a machine generated segmentation against the specified ground truth. Four research groups have contributed to evaluate their own algorithm for segmenting a range image into planar patches.
[1] 673 D.H. Ballard and C.M. Brown, Computer Vision, Prentice Hall, Upper Saddle River, N.J., 1982.
[2] J.L. Barron, D.J. Fleet, and S.S. Beauchemin, “Performance of Optical Flow Techniques,” Int'l J. Computer Vision, vol. 12, no. 1, pp. 43–77, 1994.
[3] P. Besl, “Active, Optical Imaging Sensors,” Machine Vision and Applications, pp. 127-152, 1988.
[4] 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.
[5] S.M Bhandarkar and A. Siebert, "INTEGRA—An Integrated System for Range Image Understanding," Int'l J. Pattern Recognition and Artificial Intelligence, vol. 6, no. 5, pp. 913-953, 1992.
[6] R.C. Bolles, H.H. Baker, and M.J. Hannah, "The JISCT Stereo Evaluation," Proc. Image Understanding Workshop, pp. 263-274,Washington, D.C., 1993.
[7] 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.
[8] R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis.New York: John Wiley&Sons, 1973.
[9] A.W. Fitzgibbon, D.W. Eggert, and R.B. Fisher, "High-level CAD Model Acquisition from Range Images," technical report, Dept. of Artificial Intelligence, Univ. of Edinburgh, 1995.
[10] P.J. Flynn and A.K. Jain, Surface classification: Hypothesis Testing and Parameter Estimation Proc. Computer Vision and Pattern Recognition, 1988.
[11] P. Flynn and A. Jain, "BONSAI: 3D object recognition using constrained search," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, pp. 1066-1075, 1991.
[12] S. Ghosal and R. Mehrotra, "Segmentation of Range Images: An Orthogonal Moment-Based Integrated Approach," IEEE Trans. Robotics and Automation, vol. 9, pp. 385-389, 1993.
[13] D.B. Goldgof, T.S. Huang, and H. Lee, "A Curvature-Based Approach to Terrain Recognition," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, 1,213-1,217, 1989.
[14] R.C. Gonzalez and R.E. Woods, Digital Image Processing, Addison-Wesley, New York, 1993.
[15] R.M. Haralick and L.G. Shapiro, Computer and Robot Vision. New York: Addison-Wesley, 1993.
[16] R. Haralick, “Performance Characterization in Image Analysis: Thinning, a Case in Point,” Pattern Recognition Letters, vol. 13, pp. 5-12, 1992.
[17] R. Hoffman and A.K. Jain,“Segmentation and classification of range images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no.5, pp. 608-620, Sept. 1987.
[18] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
[19] R.C. Jain,A.K. Jain,Analysis and Interpretation of Range Images,New York: Springer-Verlag, 1990.
[20] R.C. Jain and T.O. Binford, "Ignorance, Myopia, and Naivete in Computer Vision Systems," CVGIP, vol. 53-1, pp. 112-117, 1991.
[21] R.A. Jarvis, "Three Dimensional Object Recognition Systems," Range Sensing for Computer Vision, A.K. Jain and P.J. Flynn, eds., pp. 17-56. Elsevier Science Publishers, 1993.
[22] X.Y. Jiang and H. Bunke, "Fast Segmentation of Range Images into Planar Regions by Scan Line Grouping," Machine Vision and Applications, vol. 7, no. 2, pp. 115-122, 1994.
[23] R. Krishnapuram and S. Gupta, "Morphological Methods for Detection and Classification of Edges in Range Images," Mathematical Imaging and Vision, vol. 2, pp. 351-375, 1992.
[24] S.M. Lavalle and S.A. Hutchinson, “A Bayesian Segmentation Methodology for Parametric Image Models,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, pp. 211-217, 1995.
[25] S.U. Lee, S.Y. Chung, and R.H. Park, “A Comparative Performance Study of Several Global Thresholding Techniques for Segmentation,” Computer Vision, Graphics, and Image Processing, vol. 52, pp. 171-190, 1990.
[26] M.D. Levine and A.M. Nazif, "An Experimental Rule Based System for Testing Low Level Segmentation Strategies," Multicomputers and Image Processing: Algorithms and Programs, K. Preston and L. Uhr, eds., pp.149-160. Academic Press, 1982.
[27] M.D. Levine, Vision in Man and Machine.New York: McGraw-Hill, 1985.
[28] G.W. Cottrell and M.K. Fleming, "Categorisation of Faces Using Unsupervised Feature Extraction," Proc. Int'l Conf. Neural Networks,San Diego, vol. 2, pp. 65-70, 1990.
[29] Y.W. Lim and S.U. Lee, "On the Color Image Segmentation Algorithm Based on the Thresholding and the Fuzzy C-Means Techniques," Pattern Recognition, vol. 23, no. 9, pp. 935-952, 1990.
[30] S.-P. Liou, A.H. Chiu, and R.C. Jain, “A Parallel Technique for Signal-Level Perceptual Organization,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 4, pp. 317-325, Apr. 1991.
[31] T.S. Newman, P.J. Flynn, and A.K. Jain, “Model-Based Classification of Quadric Surfaces,” CVGIP: Image Understanding, vol. 58, no. 2, pp 235-249, 1993.
[32] N. Pal and S. Pal, "A Review on Image Segmentation Techniques," Pattern Recognition, vol. 26, no. 9, pp. 1,277-1,294, 1993.
[33] Perceptron Inc., LASAR Hardware Manual, 23855 Research Drive, Farmington Hills, Michigan, 1993.
[34] K. Price, "Anything You Can Do, I Can Do Better (No You Can't)..." CVGIP, vol. 36, pp. 387-391, 1986.
[35] B. Sabata,F. Arman,, and J.K. Aggarwal, Segmentation of 3D range images using pyramidal data structures. “, Computer Vision, Graphics, and Image Processing, vol. 57, pp. 373-387, May 1993.
[36] T.G. Stahs and F.M. Wahl, "Fast and Robust Range Data Acquisition in a Low-Cost Environment," SPIE #1395: Close-Range Photogrammetry Meets Machine Vision, pp. 496-503,Zurich, 1990.
[37] R.W. Taylor, M. Savini, and A.P. Reeves, "Fast Segmentation of Range Imagery into Planar Regions," Computer Vision, Graphics, and Image Processing, vol. 45, no. 1, pp. 42-60, 1989.
[38] E. Trucco and R.B. Fisher, "Experiments in Curvature-Based Segmentation of Range Data," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 2, pp. 177-181, Feb. 1995.
[39] M.A. Wani and B.G. Batchelor, “Edge-Region-Based Segmentation of Range Images,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 3, pp. 314-319, Mar. 1994.
[40] N. Yokoya and M. Levine,“Range image segmentation based on differential geometry: a hybrid approach,” IEEE Trans. on PAMI, vol. 11, no. 6, pp. 643-649, Jun. 1989.
[41] Handbook of Pattern Recognition and Image Processing: Computer Vision, T.Y. Young, ed., Chapter 7. Academic Press, 1994.
[42] 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.
[43] R. Zhang, P.S. Tsai, J.E. Cryer, and M. Shah, "Analysis of Shape From Shading Techniques," Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recognition, pp. 377-384, 1994.
Index Terms:
Experimental comparison of algorithms, range image segmentation, low level processing, performance evaluation.
Citation:
Adam Hoover, Gillian Jean-Baptiste, Xiaoyi Jiang, Patrick J. Flynn, Horst Bunke, Dmitry B. Goldgof, Kevin Bowyer, David W. Eggert, Andrew Fitzgibbon, Robert B. Fisher, "An Experimental Comparison of Range Image Segmentation Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 7, pp. 673-689, July 1996, doi:10.1109/34.506791
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb