Fast algorithm of the Hough transform for straight line detection in an image

Authors

  • Luis Canul-Arceo Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán. Calle 48 s/n. CP 97700. Tizimín. Yucatán, México
  • José Luis López Martínez Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán. Calle 48 s/n. CP 97700. Tizimín. Yucatán, México
  • Lizzie Narváez-Díaz Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán.

DOI:

https://doi.org/10.30973/progmat/2015.7.2/2

Keywords:

Hough transform, line detection, processing, pyramidal decomposition

Abstract

The Hough transform is one of the most common methods used to detect shapes (i.e. lines) in digital image processing. However, the computational complexity of the transform is high if performed sequentially (using a single processor). In this paper, we present a fast algorithm of the Hough transform to straight lines detection in an image, which use an image decomposition technique. Implemented in parallel computing, this technique enables balanced workload for the processors involved to avoid the computational overhead. Computer simulations are presented and discussed to show the efficiency of proposed algorithm with some images as examples.

Author Biographies

Luis Canul-Arceo, Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán. Calle 48 s/n. CP 97700. Tizimín. Yucatán, México

Luis Canul-Arceo es pasante de la Licenciatura en Ciencias de la Computación de la Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín de la Universidad Autónoma de Yucatán (UADY). Entre sus líneas de investigación se encuentran el procesamiento de imágenes, cómputo paralelo y reconocimiento de patrones.

José Luis López Martínez, Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán. Calle 48 s/n. CP 97700. Tizimín. Yucatán, México

José Luis López Martínez es Licenciado en Ciencias de la Computación, por la Universidad Autónoma de Yucatán, y recibió el grado de Doctor en Ciencias de la Computación en 2011 en el Centro de Investigación Científica y de Educación Superior de Ensenada, México. Actualmente es profesor en la Facultad de Matemáticas de la UADY. Sus áreas de investigación incluyen: el procesamiento de imágenes, computo paralelo y reconocimiento de patrones.

Lizzie Narváez-Díaz, Facultad de Matemáticas, Unidad Multidisciplinaria Tizimín, Universidad Autónoma de Yucatán.

Lizzie Narváez-Díaz es Licenciada en Ciencias de la Computación por la Universidad Autónoma de Yucatán, y obtuvo la Maestría en Ciencias de la Computación en 2006 en el Instituto Tecnológico de Estudios Superiores de Monterrey, campus Cuernavaca. Actualmente es profesora de la Facultad de Matemáticas de la UADY. Su área de interés son las redes de computadoras.

References

Chen, L., Chen, H., Pan, Y., Chen, Y. A fast efficient parallel Hough transform algorithm on LARPBS. The Journal of Supercomputing. 2004, 29, 185-195. https://doi.org/10.1023/B:SUPE.0000026850.06646.3c

Duda, R.O., Hart, P.E. Use of the Hough transform to detect lines and curves in pictures. Commun. ACM. 1972, 15(1), 11-15.

Zhu, T., Jeong-Hyun, K., Dong-Joong, K. Ellipse detection: a simple and precise method based on randomized Hough transform. Optical Engineering. 2012, 51(5). https://doi.org/10.1117/1.OE.51.5.057203

Atiquzzaman, M. Multiresolution Hough transform: an efficient method of detecting patterns in images. IEEE Transactions on pattern analysis and machine intelligence. 1992, 14(11), 1090-1095. https://doi.org/10.1109/34.166623

Ji, J., Chen, G., Sun, L. A novel Hough transform method for line detection by enhancing accumulator array. Pattern recognition letters. 2011, 32, 1503-1510. https://doi.org/10.1016/j.patrec.2011.04.011

Hanahara, K., Matuyama, T., Uchiyama, T. A real-time processor for the Hough transform. IEEE transactions on pattern analysis and machine intelligence. 1988, 10(1), 121-125. https://doi.org/10.1109/34.3876

Gauil, N.,Villalba, J., Zapata, E. A fast Hough transform for segment detection. IEEE transactions on image processing. 1995, 4(11), 1541-1548. https://doi.org/10.1109/83.469935

Gonzalez, R.C., Woods, R. E. Digital Image Processing. Upper Saddle River: Pearson / Prentice Hall, 2008.

Downloads

Published

2015-06-30

How to Cite

Canul-Arceo, L., López Martínez, J. L., & Narváez-Díaz, L. (2015). Fast algorithm of the Hough transform for straight line detection in an image. Programación Matemática Y Software, 7(2), 8–13. https://doi.org/10.30973/progmat/2015.7.2/2

Issue

Vol. 7 No. 2 (2015): June, 2015

Section

Articles

License

Copyright (c) 2015 Programación Matemática y Software

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.