loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Two-Dimensional Convolution on a Pyramid Computer
July 1988 (vol. 10 no. 4)
pp. 590-593
ASCII Text
x 
 
J.H. Chang, O.H. Ibarra, T.C. Pong, S.M. Sohn, "Two-Dimensional Convolution on a Pyramid Computer," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 4, pp. 590-593, July, 1988.
 
 
BibTex
x
 
@article{ 10.1109/34.3920,
author = {J.H. Chang and O.H. Ibarra and T.C. Pong and S.M. Sohn},
title = {Two-Dimensional Convolution on a Pyramid Computer},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {10},
number = {4},
issn = {0162-8828},
year = {1988},
pages = {590-593},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.3920},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Two-Dimensional Convolution on a Pyramid Computer
IS - 4
SN - 0162-8828
SP590
EP593
EPD - 590-593
A1 - J.H. Chang,
A1 - O.H. Ibarra,
A1 - T.C. Pong,
A1 - S.M. Sohn,
PY - 1988
KW - 2D convolution; computerised picture processing; computational complexity; pyramid computer; window; image matrix; finite state; Boolean operations; Boolean functions; computational complexity; computerised picture processing; matrix algebra; parallel architectures
VL - 10
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

An algorithm for convolving a k*k window of weighting coefficients with an n*n image matrix on a pyramid computer of O(n/sup 2/) processors in time O(logn+k/sup 2/), excluding the time to load the image matrix, is presented. If k= Omega ( square root log n), which is typical in practice, the algorithm has a processor-time product O(n/sup 2/ k/sup 2/) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two (0, 1)-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state.

[1] H. T. Kung and S. W. Song, "A systolic 2-D convolution chip," inProc. IEEE Comput. Soc. Workshop Comput. Arch. Pattern Anal. Image Database Man., Nov. 1981, pp. 159-160.
[2] M. Maresca and H. Li, "Morphological operations on mesh connected architecture: A generalized convolution algorithm," inProc. 1986 IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognition, 1986, pp. 299-304.
[3] S.-Y. Lee and J. K. Aggarwal, "Parallel 2-D convolution on a mesh connected array processor,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, pp. 590-594, July 1987.
[4] Z. Fang, X. Li, and L. Ni, "Parallel algorithms for 2-D convolution," inProc. 1986 Int. Conf. Parallel Processing, 1986, pp. 262- 269.
[5] V. Cantoni and S. Levialdi, Eds.,Pyramidal Systems for Computer Vision. Berlin: Springer-Verlag, 1986.
[6] L. Uhr,Multicomputer Architectures for Artificial Intelligence. New York: Wiley-Interscience, 1987.
[7] N. Ahuja and S. Swamy, "Multiprocessor pyramid architectures for bottom-up image analysis,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, pp. 463-475, July 1984.
[8] S. L. Tanimoto, "Sorting, histogramming and other statistical operations on a pyramid machine," inMultiresolution Image Processing and Analysis, A. Rosenfeld, Ed. New York: Springer-Verlag, 1984, pp. 136-145.
[9] Q. F. Stout, "Drawing straight lines with a pyramid cellular automaton,"Inform. Processing Lett., vol. 15, pp. 233-237, 1982.
[10] R. Miller and Q. F. Stout, "Data movement techniques for the pyramid computer,"SIAM J. Comput., vol. 16, pp. 38-60, 1987.
[11] A. P. Reeves, "Parallel computer architectures for image processing,"Comput. Vision, Graphics, Image Processing, vol. 25, pp. 68- 88, 1984.

Index Terms:
2D convolution; computerised picture processing; computational complexity; pyramid computer; window; image matrix; finite state; Boolean operations; Boolean functions; computational complexity; computerised picture processing; matrix algebra; parallel architectures
Citation:
J.H. Chang, O.H. Ibarra, T.C. Pong, S.M. Sohn, "Two-Dimensional Convolution on a Pyramid Computer," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 4, pp. 590-593, July 1988, doi:10.1109/34.3920
Usage of this product signifies your acceptance of the Terms of Use.