×

Computing Hough transforms on hypercube multicomputers. (English) Zbl 1215.65217

Summary: Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputer are developed. Our algorithms can compute \(p\) angles of the Hough transform of an \(N \times N\) image, \(pleN\), in \(0(p + \log N)\) time on both MIMD and SIMD hypercubes. These algorithms require \(0(N ^{2})\) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.

MSC:

65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ballard, D.H. 1981. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition, 12, 2: 111?122. · Zbl 0454.68112 · doi:10.1016/0031-3203(81)90009-1
[2] Ballard, D.H., and Brown, C.M. 1982. Computer Vision. Prentice Hall, Englewood Cliffs, N.J.
[3] Chan, T.F., and Saad, Y. 1986. Multigrid algorithms on the hypercube multiprocessor. IEEE Trans. Comps., C-35 (Nov.), 969?977. · doi:10.1109/TC.1986.1676698
[4] Chandran, S., and Davis, L. 1987. The Hough transform on the Butterfly and the NCUBE. Univ. of Md. tech. rept., College Park, Md.
[5] Cypher, R.E., Sanz, J.L.C., and Snyder, L. 1987. The Hough transform has O(N) complexity on SIMD N {\(\times\)} N mesh array architectures. In Proc., IEEE Workshop on Comp. Arch. for Pattern Analysis and Machine Intelligence. · Zbl 0711.68099
[6] Dekel, E., Nassimi, D., and Sahni, S. 1981. Parallel matrix and graph algorithms. SIAM J. on Computing, 10, 4 (Nov.), 657?675. · Zbl 0468.68044 · doi:10.1137/0210049
[7] Fishburn, A., and Highnam, P. 1987. Computing the Hough transform on a scan line array processor. In Proc., IEEE Workshop on Comp. Arch. for Pattern Analysis and Machine Intelligence, pp. 83?87.
[8] Guerra, C., and Hambrusch, S. 1987. Parallel algorithms for line detection on a mesh. In Proc., IEEE Workshop on Comp. Arch. for Pattern Analysis and Machine Intelligence, pp. 99?106.
[9] Horowitz, E., and Sahni, S. 1985. Fundamentals of Data Structures in Pascal. Computer Science Press. · Zbl 0408.68003
[10] Ibrahim, H., Kender, J., and Shaw, D.E. 1986. On the application of massively parallel SIMD tree machines to certain intermediate level vision tasks. Comp. Vision, Graphics, and Image Processing, 36: 53?75. · doi:10.1016/S0734-189X(86)80029-9
[11] Nassimi, D., and Sahni, S. 1981. Data broadcasting in SIMD computers. IEEE Trans. Comps., C-30, 2 (Feb.), 101?107. · doi:10.1109/TC.1981.6312172
[12] Prasanna Kumar, V.K., and Krishnan, V. 1987. Efficient image template matching on SIMD hypercube machines. In Proc., 1987 Internat. Conf. on Parallel Processing (Chicago, Aug.), pp. 765?771. · Zbl 0682.68053
[13] Ranka, S., and Sahni, S. 1990. Parallel algorithms for image template matching. In Parallel Algorithms for Machine Intelligence (to appear). · Zbl 0744.68063
[14] Rosenfeld, A., and Kak, A.C. 1982. Digital Picture Processing. Academic Press, New York. · Zbl 0564.94002
[15] Rosenfeld, A., Ornelas, J., and Hung, Y. 1988. Hough transform algorithms for mesh-connected SIMD parallel processors. Comp. Vision, Graphics, and Image Processing, 41, 3: 293?305. · doi:10.1016/0734-189X(88)90104-1
[16] Thompson, C.D., and Kung, H.T. 1977. Sorting on a mesh-connected parallel computer. CACM, 20, 4: 263?271. · Zbl 0349.68020 · doi:10.1145/359461.359481
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.