| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
On Computing Complete Histograms of Images in Log (n) Steps Using Hypercubes
February 1989 (vol. 11 no. 2)
pp. 212-213
An algorithm for the computation of the histogram of limited-width (such as gray-level) values on a SIMD (single-instructions multiple-data) hypercube multiprocessor is proposed, which does not require the use of a general interconnection capability such as that on the connection machine. The computation of the complete histogram of n such values takes place in a series of log n steps, after which the histogram for value i can be found in the lowest-addressed processor whose address ends in i. The algorithm makes use of the association of suffixes of data values of increasing width with suffixes of processor addresses.
[1] 212S. L. Tanimoto, "Sorting, histogramming, and other statistical operations on a pyramid machine," inMultiresolution Image Processing and Analysis, A. Rosenfeld, Ed. New York: Springer-Verlag, pp. 136-145.[2] D. Hillis,The Connection Machine. Cambridge, MA: M.I.T. Press, 1985.[3] W. D. Hillis and G. L. Steele, Jr., "Data parallel algorithms,"Commun. ACM, vol. 29, no. 12, pp. 1170-1183, Dec. 1986.
Index Terms:
computerised picture processing; parallel processing; histograms; gray-level; SIMD; hypercube multiprocessor; computational complexity; computerised picture processing; parallel processing
Citation:
T. Bestul, L.S. Davis, "On Computing Complete Histograms of Images in Log (n) Steps Using Hypercubes," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 2, pp. 212-213, Feb. 1989, doi:10.1109/34.16717
