NANOSCALE IMAGE PROCESSING - Bio-Inspired and Nanoscale Integrated Computing - page 516

of the spin-wave paths. So, this architecture represents a new approach for
designing nanometer-scale computational structures, thus aiming to preserve the
main advantages of wave-based computers [21-24].
In this section, we study different image processing algorithms on the spin-
wave reconfigurable mesh architecture [22]. We first show that given an N 1/2 N 1/2

image, using a N N spin-wave reconfigurable mesh, in O(1) time, the figures can
be labeled and their nearest neighbor and convex hull can be found. This is due to
the fact that the superposition characteristic of spin waves allows concurrent
writes if all the requesting processors write a ''1.'' We then present the same
algorithms for ''multiple'' figures and show that they can be solved in O(log N)
time, considering the fact that multiple spin waves at different frequencies can be
transmitted on each of the spin-wave buses.
The input to our algorithms is a digitized (black and white) image with
processor (i, j ) storing the pixel (i, j ), 0

N 1, in the plane, where the black
pixels are 1-valued and white pixels are 0-valued. Figures correspond to connected
1's (black pixels) in the image.

i, j

r r

19.1.1. Labeling Problem
An early step in image processing is the identification of the figures in the image.
Figures correspond to connected 1's (black pixels) in the image. Since this
architecture allows concurrent writes all the 1's are connected in O(1) time.
Each black node (1-valued) broadcasts 1 on the four buses connected to it, so that
all the black pixels simultaneously connect to each of their 1-valued neighbors.
As mentioned above, in a 0/1 picture, the connected 1's are said to form a
figure. An N N digitized image may contain more than one region of black
pixels. The labeling problem is to identify to which figure each '1' belongs and to
label each figure with a unique ID.
Here we present three variations of the labeling problem. First, we show a
simple algorithm that labels O(N)figuresinanN N image in O(logN)timeusing
an N N spin-wave reconfigurable mesh. Next, we present the same algorithm for a
smaller image size and prove that on an N 1/2 N 1/2 image, the figures can be labeled

in O(1) time. Finally, we show that the figures of an N N image can be labeled in
O(N) steps in a systolic fashion, where each systolic cycle takes just O(1) time.

Algorithm 19.1.1
Given an N N image, using an N N reconfigurable mesh with spin-wave buses,
O(N) figures can be labeled in O (log N) time.

We would like to label each figure with a unique identification number (ID).
Associated with each PE is an ID, and we choose the largest ID in each figure to be
the label of that figure. First, each processing element (PE) checks its most
significant bit (MSB). If its MSB is 1, the PE broadcast 1 to all the nodes
connected to it. If its MSB is 0, on the other hand, the PE listens to the channel
and if there is a 1 on the bus, that PE gets disabled. At the next step, the nodes