Real-time line detection through an improved Hough transform voting scheme. (English) Zbl 1122.68529

Fernandes, Leandro A. F.; Oliveira, Manuel M.

Pattern Recognition 41, No. 1, 299-314 (2008).

Summary: The Hough Transform (HT) is a popular tool for line detection due to its robustness to noise and missing data. However, the computational cost associated to its voting scheme has prevented software implementations to achieve real-time performance, except for very small images. Many dedicated hardware designs have been proposed, but such architectures restrict the image sizes they can handle. We present an improved voting scheme for the HT that allows a software implementation to achieve real-time performance even on relatively large images. Our approach operates on clusters of approximately collinear pixels. For each cluster, votes are cast using an oriented elliptical-Gaussian kernel that models the uncertainty associated with the best-fitting line with respect to the corresponding cluster. The proposed approach not only significantly improves the performance of the voting scheme, but also produces a much cleaner voting map and makes the transform more robust to the detection of spurious lines.

MSC:

68T10

Pattern recognition, speech recognition

Keywords:

Hough transformation; real-time line detection; pattern recognition; collinear points; image processing

References:

[1]	Debevec, P. E.; Taylor, C. J.; Malik, J., Modeling and rendering architecture from photographs: a hybrid geometry- and image-based approach, (Proceedings of the 23th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH-96) (1996), Addison-Wesley: Addison-Wesley Reading, MA), 11-20
[2]	Hartley, R. I.; Zisserman, A., Multiple view geometry in computer vision (2000), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0956.68149
[3]	Ferreira, A.; Fonseca, M. J.; Jorge, J. A.; Ramalho, M., Mixing images and sketches for retrieving vector drawings, (Eurographics Multimedia Workshop (2004), Eurographics Association: Eurographics Association China), 69-75
[4]	Caprile, B.; Torre, V., Using vanishing points for camera calibration, Int. J. Comput. Vision (IJCV), 4, 2, 127-139 (1990)
[5]	Straforini, M.; Coelho, C.; Campani, M., Extraction of vanishing points from images of indoor and outdoor scenes, Image Vision Comput., 11, 2, 91-99 (1993)
[6]	Lew Yan Voon, L. F.; Bolland, P.; Laligant, O.; Gorria, P.; Gremillet, B.; Pillet, L., Gradient-based discrete Hough transform for the detection and localization of defects in nondestructive inspection, (Proceedings of the V Machine Vision Applications in Industrial Inspection, vol. 3029 (1997), SPIE: SPIE San Jose, CA), 140-146
[7]	Lee, H.-J.; Ahn, H.-J.; Song, J.-H.; Park, R.-H., Hough transform for line and plane detection based on the conjugate formulation, (Proceedings of the IX Machine Vision Applications in Industrial Inspection, vol. 4301 (2001), SPIE: SPIE San Jose, CA), 244-252
[9]	Karnieli, A.; Meisels, A.; Fisher, L.; Arkin, Y., Automatic extraction and evaluation of geological linear features from digital remote sensing data using a Hough transform, Photogramm. Eng. Remote Sensing, 62, 5, 525-531 (1996)
[11]	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) · Zbl 1296.94027
[12]	Princen, J.; Illingworth, J.; Kittler, J., A hierarchical approach to line extraction based on the Hough transform, Graphical Model Image Process., 52, 1, 57-77 (1990)
[13]	Yacoub, S. B.; Jolion, J., Hierarchical line extraction, IEE Vision Image Signal Process., 142, 1, 7-14 (1995)
[14]	Chung, K.-L.; Chen, T.-C.; Yan, W.-M., New memory- and computation-efficient Hough transform for detecting lines, Pattern Recognition, 37, 953-963 (2004)
[15]	Ho, C. G.; Young, R. C.D.; Bradfield, C. D.; Chatwin, C. R., A fast Hough transform for the parametrisation of straight lines using Fourier methods, Real-Time Imaging, 2, 113-127 (2000)
[17]	Albanesi, M. G.; Ferretti, M.; Rizzo, D., Benchmarking Hough transform architectures for real-time, Real-Time Imaging, 6, 2, 155-172 (2000)
[18]	Mayasandra, K.; Salehi, S.; Wang, W.; Ladak, H. M., A distributed arithmetic hardware architecture for real-time Hough-transform-based segmentation, Can. J. Electr. Comput. Eng., 30, 4, 201-205 (2005)
[19]	Canny, J., A computational approach to edge detection, IEEE Trans. Pattern Anal. Mach. Intell., 8, 6, 679-698 (1986)
[20]	Ballard, D. H., Generalizing the Hough transform to detect arbitrary shapes, Pattern Recognition, 13, 2, 111-122 (1981) · Zbl 0454.68112
[21]	Leavers, V. F.; Sandler, M. B., An efficient radon transform, (Proceedings of the 4th International Conference on Pattern Recognition (ICPR-88) (1988), Springer: Springer Cambridge, UK), 380-389
[22]	Illingworth, J.; Kittler, J. V., A survey of the Hough transform, Graphical Model Image Process., 44, 1, 87-116 (1988)
[23]	Leavers, V. F., Survey: which Hough transform?, Graphical Model Image Process., 58, 2, 250-264 (1993)
[24]	Lin, X.; Otobe, K., Hough transform algorithm for real-time pattern recognition using an artificial retina camera, Opt. Express, 8, 9, 503-508 (2001)
[25]	Costa, L. F.; Sandler, M., A binary Hough transform and its efficient implementation in a systolic array architecture, Pattern Recognition Lett., 10, 329-334 (1989) · Zbl 0825.68562
[26]	Pope, A. R.; Lowe, D. G., Vista: a software environment for computer vision research, (Proceedings of Computer Vision and Pattern Recognition (CVPR’94) (1994), IEEE Computer Society: IEEE Computer Society Seattle, WA), 768-772
[27]	Lowe, D. G., Three-dimensional object recognition from single two-dimensional images, Artif. Intell., 31, 355-395 (1987), (section 4.6)
[28]	Draper, N. R.; Smith, H., Applied regression analysis (1966), Wiley: Wiley New York · Zbl 0158.17101
[29]	Parratt, L. G., Probability and experimental errors in science (1961), Wiley: Wiley New York · Zbl 0101.10804