3D Hough transform for sphere recognition on point clouds
Tóm tắt
Three-dimensional object recognition on range data and 3D point clouds is becoming more important nowadays. Since many real objects have a shape that could be approximated by simple primitives, robust pattern recognition can be used to search for primitive models. For example, the Hough transform is a well-known technique which is largely adopted in 2D image space. In this paper, we systematically analyze different probabilistic/randomized Hough transform algorithms for spherical object detection in dense point clouds. In particular, we study and compare four variants which are characterized by the number of points drawn together for surface computation into the parametric space and we formally discuss their models. We also propose a new method that combines the advantages of both single-point and multi-point approaches for a faster and more accurate detection. The methods are tested on synthetic and real datasets.
Tài liệu tham khảo
Schnabel, R., Wessel, R., Wahl, R., Klein, R.: Shape recognition in 3d point-clouds, in: Skala, V. (ed.) The 16-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision’2008. UNION Agency-Science Press (2008)
van der Glas, M., Vos, F.M., Botha, C.P., Vossepoel, A.M.: Determination of position and radius of ball joints. In: Medical imaging 2002: image processing, vol. 4684, pp 1571–1577, San Diego (2002)
Rabbani, T., Van Den Heuvel, F.: Efficient Hough transform for automatic detection of cylinders in point clouds. ISPRS WG III/3, III/4 3, 60–65 (2005)
Hough, P.V.C.: Method and means for recognizing complex patterns. U.S. Patent No. 3069654, December 1962
Ballard, D.: Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognit. 13(2), 111–122 (1981)
Borrmann, D., Elseberg, J., Lingemann, K., Nüchter, A.: The 3d hough transform for plane detection in point clouds: a review and a new accumulator design. 3D Res. 2, 1–13 (2011)
Tarsha-Kurdi, F., Landes, T., Grussenmeyer, P.: Hough-transform and extended Ransac algorithms for automatic detection of 3d building roof planes from lidar data. In: Rönnholm, P., Hyyppä, H., Hyyppä, J. (eds.) ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007, pp. 407–412. Espoo, Finland (2007)
Borrmann, D., Elseberg, J., Lingemann, K., Nüchter, A.: A data structure for the 3d Hough transform for plane detection. In: Proceedings of the 5th IFAC Symposium on Intelligent Autonomous Vehicles (IAV ’10), Lecce, Italy (2010)
Bernal-Marin, M., Bayro-Corrochano, E.: Integration of Hough transform of lines and planes in the framework of conformal geometric algebra for 2d and 3d robot vision. Pattern Recognit. Lett. 32(16), 2213–2223 (2011)
Illingworth, J., Kittler, J.: A survey of the Hough transform. Comput. Vis. Graph. Image Process. 44(1), 87–116 (1988)
Hart, P.: How the Hough transform was invented [dsp history]. Signal Process. Mag. IEEE 26(6), 18–22 (2009)
Bastien, P., Dunn, L.: Global transformations in pattern recognition of bubble chamber photographs. Comput. IEEE Trans. C–20(9), 995–1001 (1971)
Bazin, M.J., Benoit, J.W.: Off-line global approach to pattern recognition for bubble chamber pictures. Nucl. Sci. IEEE Trans. 12(4), 291–293 (1965)
Rosenfeld, A.: Picture processing by computer. ACM Comput. Surv. 1(3), 147–176 (1969)
Duda, R.O., Hart, P.E.: Use of the Hough transformation to detect lines and curves in pictures. Commun. ACM 15(1), 11–15 (1972)
Illingworth, J., Kittler, J.: The adaptive Hough transform. Pattern Anal. Mach. Intel. IEEE Trans. PAMI–9(5), 690–698 (1987)
Tsuji, S., Matsumoto, F.: Detection of ellipses by a modified Hough transformation. Comput. IEEE Trans. C–27(8), 777–781 (1978)
Yuen, H.K., Princen, J., Illingworth, J., Kittler, J.: Comparative study of Hough transform methods for circle finding. Image Vis. Comput. 8(1), 71–77 (1990)
Kiryati, N., Eldar, Y., Bruckstein, A.: A probabilistic Hough transform. Pattern Recognit. 24(4), 303–316 (1991)
Xu, L., Oja, E., Kultanen, P.: A new curve detection method: randomized Hough transform (rht). Pattern Recognit. Lett. 11(5), 331–338 (1990)
Kultanen, P., Xu, L., Oja, E.: Randomized Hough transform (rht). In: Pattern Recognition. Proceedings of 10th International Conference, vol. 1, pp. 631–635 (1990)
Kiryati, N., Kälviäinen, H., Alaoutinen, S.: Randomized or probabilistic hough transform: unified performance evaluation. Pattern Recognit. Lett. 21(13–14), 1157–1164 (2000) (selected papers from the 11th Scandinavian conference on image)
Lu, W., Tan, J.: Detection of incomplete ellipse in images with strong noise by iterative randomized Hough transform (irht). Pattern Recognit. 41(4), 1268–1279 (2008)
Princen, J., Illingworth, J., Kittler, J.: A formal definition of the Hough transform: properties and relationships. J. Math. Imaging Vis. 1, 153–168 (1992)
Hsu, C.-C., Huang, J.S.: Partitioned Hough transform for ellipsoid detection. Pattern Recognit. 23(3–4), 275–282 (1990)
Taylor, R.: An efficient implementation of decomposable parameter spaces. In: Pattern recognition. Proceedings of 10th International Conference, vol. 1, pp. 613–619 (1990)
Cao, M., Ye, C., Doessel, O., Liu, C.: Spherical parameter detection based on hierarchical Hough transform. Pattern Recognit. Lett. 27(9), 980–986 (2006)
Ogundana, O.O., Coggrave, C.R., Burguete, R.L., Huntley, J.M.: Fast Hough transform for automated detection of spheres in three-dimensional point clouds. Opt. Eng. 46(5), 051002-1–051002-11 (2007)
Kharbat, M., Aouf, N., Tsourdos, A., White, B.: Sphere detection and tracking for a space capturing operation. In: Advanced Video and Signal Based Surveillance. AVSS 2007. IEEE Conference, pp. 182–187 (2007)
Abuzaina, A., Nixon, M., Carter, J.: Sphere detection in kinect point clouds via the 3d hough transform. In: Wilson, R., Hancock, E., Bors, A., Smith, W. (eds.) Computer Analysis of Images and Patterns, vol. 8048 of Lecture Notes in Computer Science. Springer, Berlin Heidelberg, pp. 290–297 (2013)
Khoshelham, K.: Accuracy analysis of kinect depth data. ISPRS Works. Laser Scan. 38, 1 (2011)
Smisek, J., Jancosek, M., Pajdla, T.: 3d with kinect. In: Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference, pp. 1154–1160 (2011)