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).
References
Ballard DH (1981) Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition 3(2): 110–122
Cantoni V, Levialdi S (eds) (1986) Pyramidal systems for computer vision. Springer-Verlag, Berlin. NATO ARW, Series F, Vol. 25
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
Guerra C, Hambrusch S (1989) Parallel algorithms for line detection on a mesh. Journal of Parallel and Distributed Computing 6:1–20
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
Li H, Lavin M, Le Master R (1986) Fast Hough transform: A hierarchical approach. Computer Vision, Graphics, and Image Processing 36:139–161
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
Nassimi D, Sahni S (1980) Finding connected components and connected ones on a mesh-connected parallel computer. SIAM Journal on Computing 9:744–757
Rosenfeld A (ed) (1984) Multiresolution image processing and analysis. Springer-Verlag, New York
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
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
Tanimoto SL, Kingler A (1980) Structured computer vision. Academic Press, New York
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
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF01212195