Browse Prior Art Database

Parallel Image Processing Using Cellular Arrays

IP.com Disclosure Number: IPCOM000131575D
Original Publication Date: 1983-Jan-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 11 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

Azriel Rosenfeld: AUTHOR [+3]

Abstract

Cellular array computers are not new to image processing, but mr ore refined techniques have led to broader implementations. We can now construct arrays with up to 128 x 128 processors.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1983 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Parallel Image Processing Using Cellular Arrays

Azriel Rosenfeld

University of Maryland

Cellular array computers are not new to image processing, but mr ore refined techniques have led to broader implementations. We can now construct arrays with up to 128 x 128 processors.

Nearly 25 years ago, Urgers 2 suggested a twodimensional array of processing elements as a natural computer architecture for image processing and recognition. Ideally, in this approach, each processor is responsible for one pixel, or one element of the image, with neighboring processors responsible for neighboring pixels. Thus, using hardwired communication between neighboring processors, local operations can be performed on the image, or local image features can be detected in parallel, with every processor simultaneously accessing its neighbors and computing the appropriate function for its neighborhood.

Over the last two decades, several machines embodying this concept have been constructed. The Illiac 1113 used a 36 x 36 processor array (the 111iac IV used only an 8 x 8 array) to analyze "events" in nuclear bubblechamber images by examining 36 x 36 "windows" of the images. In later machines, such as the CLIP,4 DAP,5 and Mpp,6 arrays of up to 128 x 128 processors were used and were applied blockwise to larger images.

This article reviews the basic techniques of image processing using two-dimensional arrays of processors, or cellular arrays. It also discusses various extensions and generalizations of the cellular array concept and their possible implementations and applications. The term cellular array is used because these machines can be regarded as generalizations of bounded cellular automata, which have been studied extensively on a theoretical level. The relative merits of cellular arrays for image processing as compared to other architectures. are not discussed here; but they have been studied extensively for such purposes, on levels from theory to hardware.

Cellular arrays

A cellular array (Figure 1) is a two-dimensional array of processors, or cells, usually rectangular, each of which can directly communicate with its neighbors in the array. Here, for simplicity, I assume that each cell is connected to its four horizontal and vertical neighbors. Each cell on the borders of the array then has only three neighbors, and each cell in the four corners of the array has only two. I also assume that a cell can distinguish its neighbors; i.e., it can send a different message to each neighbor, and when it receives messages from them, it knows...