Skip to main content
SpringerLink
Log in

Computing the Hough transform on a pyramid architecture

  • Short Communication
  • Published:
Machine Vision and Applications Aims and scope Submit manuscript

Abstract

An algorithm to implement the Hough transform for the detection of a straight line on a pyramidal architecture is presented. The algorithm consists of two phases. The first phase, called block-projection, takes constant time. The second phase, called block-combination, is repeated logn times and takes a total ofO(n 1/2) time for the detection of all straight lines having a given slope on an n×n image; if there arep different slopes to be detected, then the total time becomesO(pn 1/2).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  • Ballard DH (1981) Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition 3(2): 110–122

    Google Scholar 

  • Cantoni V, Levialdi S (eds) (1986) Pyramidal systems for computer vision. Springer-Verlag, Berlin. NATO ARW, Series F, Vol. 25

    Google Scholar 

  • Chuang, HY, Li CC (1985) A systolic array for straight line detection by modified Hough transform, IEEE Workshop on Computer Architectures for Pattern Analysis and Image Data Base Management, pp 300–304

  • Cypher R, Sanz JLC (1987) The Hough transform hasO(n) complexity on a SIMD n×n mesh array architecture. IEEE Workshop on Computer Architectures for Pattern Analysis and Machine Intelligence, pp 115–121

  • Davis LS, Dementhon D, Gajulapali R, Kushner TR, LeMoigne J, Veatch P (1987) Vision-based navigation: A status report, IUW, pp. 153–169

  • Duda RO, Hart PE (1972) Use of the Hough transform to detect lines and curves in pictures, Communications of the ACM 15(1):

  • Fischer AL, Highnam PT (1985) Real-time image processing on scanline array processors. IEEE Workshop on Computer Architectures for Pattern Analysis and Image Data Base Management, pp 484–489

  • Freeman H (1974) Computer processing of line-drawing images. ACM Computing Surveys 6:57–9

    Google Scholar 

  • Guerra C, Hambrusch S (1989) Parallel algorithms for line detection on a mesh. Journal of Parallel and Distributed Computing 6:1–20

    Google Scholar 

  • Hough PV (1962) Methods and means to recognize complex patterns. U.S. Patent 3,069,654

  • Ibrahim HA, Render JR, Shaw DE (1985) The analysis and performance of two middle-level vision tasks on a fine-grained SIMD tree machine. In: Proceedings of the IEEE, Conference on Computer Vision and Pattern Recognition, pp 248–256

  • Kung HT, Webb J (1986) Mapping image processing operations onto a linear systolic machine. Distributed Computing 246–257

  • Levialdi S (ed) (1988) Multicomputer vision. Academic Press, London

    Google Scholar 

  • Li H, Lavin M, Le Master R (1986) Fast Hough transform: A hierarchical approach. Computer Vision, Graphics, and Image Processing 36:139–161

    Google Scholar 

  • Miller R, Stout Q (1984) Convexity algorithms for pyramid computers. In: Proceedings International Conference on Parallel Processing, pp 177–184

  • Miller R, Stout Q (1987) Data movement techniques for the pyramid computer. SIAM Journal on Computing 16(1):38–60

    Google Scholar 

  • Nassimi D, Sahni S (1980) Finding connected components and connected ones on a mesh-connected parallel computer. SIAM Journal on Computing 9:744–757

    Google Scholar 

  • Rosenfeld A (ed) (1984) Multiresolution image processing and analysis. Springer-Verlag, New York

    Google Scholar 

  • Sanz JLC, Dinstein I (1987) Projection-based geometrical feature extraction for computer vision: Algorithms in pipeline architectures. IEEE Transactions on Pattern Analysis and Machine Intelligence 9(1): 160–168

    Google Scholar 

  • Tanimoto SL (1982) Programming techniques for hierarchical parallel image processors. In: Preston K, Uhr L (eds) Multicomputers for image processing. Academic Press, New York pp 421–429

    Google Scholar 

  • Tanimoto SL, Kingler A (1980) Structured computer vision. Academic Press, New York

    Google Scholar 

  • Thorpe C, Shafer S, Kanade T (1987) Vision and Navigation for the Carnegie-Mellon Navlab, IUW, pp 143–152

  • Uhr L (1972) Layered recognition cone networks that preprocess, classify, and describe. IEEE Transactions on Computers, pp 758–768

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica, Università dell'Aquilla, Aquila, Italy

    G. Bongiovanni

  2. Department of Computer Sciences, Purdue University, Lafayette, Indiana

    C. Guerra

  3. Dipartimento di Matematica, Università “La Sapienza” Roma, Roma, Italy

    C. Guerra

  4. Dipartimento di Matematica, Università “La Sapienza” Roma, Roma, Italy

    S. Levialdi

Authors
  1. G. Bongiovanni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. Guerra
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Levialdi
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bongiovanni, G., Guerra, C. & Levialdi, S. Computing the Hough transform on a pyramid architecture. Machine Vis. Apps. 3, 117–123 (1990). https://doi.org/10.1007/BF01212195

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01212195

Key words

Search

Navigation