Finding connected components on a scan line array processor

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding connected components on a scan line array processor

Full text

Pdf (757 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Barbara, California, United States

Pages: 195 - 202

Year of Publication: 1995

ISBN:0-89791-717-0

Author

Ronald I. Greenberg

Department of Electrical Engineering, Institute for Advanced Computer Studies, University of Maryland, College Park, MD

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/215399.215444 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Hussein M. Alnuweiri , Viktor K. Prasanna, Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays, Distributed Computing, v.5 n.2, p.55-65, September 1991 [doi>10.1007/BF02259747]
	3	Norbert Blum, On the single-operation worst-case time complexity of the disjoint set union problem, SIAM Journal on Computing, v.15 n.4, p.1021-1024, Nov. 1986 [doi>10.1137/0215072]
	4	CHIN, D., ET AL. The Princeton engine: A real-time video system simulator. IEEE Trans. Consumer Electronics 3#, 2 (May 1988), 285-297.
	5	R. Cyper , J. L. C. Sanz , L. Snyder, Hypercube and shuffle-exchange algorithms for image component labeling, Journal of Algorithms, v.10 n.1, p.140-150, Mar. 1989 [doi>10.1016/0196-6774(89)90028-X]
	6	R. E. Cypher , J. L. C. Sanz , L. Snyder, Algorithms for Image Component Labeling on SIMD Mesh-Connected Computers, IEEE Transactions on Computers, v.39 n.2, p.276-281, February 1990 [doi>10.1109/12.45215]
	7	Michael B. Dillencourt , Hannan Samet , Markku Tamminen, A general approach to connected-component labeling for arbitrary image representations, Journal of the ACM (JACM), v.39 n.2, p.253-280, April 1992 [doi>10.1145/128749.128750]
	8	DOYLE, J., AND RIVEST, R. L. Linear expected time of a simple union-find algorithm. Information Processing Letters 5, 5 (Nov. 1970), 146-148.
	9	A. L. Fisher, Scan line array processors for image computation, Proceedings of the 13th annual international symposium on Computer architecture, p.338-345, June 02-05, 1986, Tokyo, Japan
	10	FISHER, A. L., AND HIGHNAM, P. T. Real-time image processing on scan line array processors. In Proceedings of the IEEE Computer Society Workshop on Computer Architectures for Pattern Analysis and Image Database Management (1985), pp. 484-489.
	11	GABOW, H. N., AND TARJAN, R. E. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences 30, 2 (1985), 209-221.
	12	David Helman , Joseph JáJá, Efficient Image Processing Algorithms on the Scan Line Array Processor, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.1, p.47-56, January 1995 [doi>10.1109/34.368153]
	13	KNIGHT, S., ET AL. The Sarnoff engine: A massively parallel computer for high definition system simulation. In Proceedings of Application Specific Array Processors (1992), pp. 342-357.
	14	KNUTH, D. E., AND SCH(#NHAGE, A. The expected linearity of a simple equivalence algorithm. Theoretical Computer Science 6 (1978), 281-315.
	15	KUMAR, V. K. P., AND ESHAGHIAN, M. M#. Parallel geometric algorithms for digitized pictures on mesh of trees. In Proceedings of the 1986 International Conference on Parallel Processing (1986), pp. 270-273.
	16	S. Levialdi, On shrinking binary picture patterns, Communications of the ACM, v.15 n.1, p.7-10, Jan. 1972 [doi>10.1145/361237.361240]
	17	Russ Miller , Quentin Stout, Data movement techniques for the pyramid computer, SIAM Journal on Computing, v.16 n.1, p.38-60, Feb. 1987 [doi>10.1137/0216004]
	18	NASSIMI, D., AND SAHNI, S. Finding connected components and connected ones on a mesh-connected parallel computer. SIAM Journal on Computing 9, 4 (1980), 744-757.
	19	SCHWARTZ, J. T., SHARIR, M., AND SIEGEL, A. An efficient algorithm for finding connected components in a binary image. Tech. Rep. 154, Department of Computer Science, NYU, Feb. 1985. Revised July, 1985.
	20	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	21	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
	22	Andrew Chi-chih Yao, On the average behavior of set merging algorithms (Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.192-195, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803648]