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

In a similar fashion, we check the top, bottom, right, and left neighbors, but we
may miss some closer neighbors that are located in a diagonal position from the
original figure. To address this issue, we need to revise the algorithm in the following
way. First, all the black nodes (including nonextreme points) broadcast their address
and ID to their neighbors. When a black pixel receives this data, it blocks it. All black
(and white) nodes compute their distance from the closest black pixel belonging to a
different figure. All the intermediate white nodes which have received the broad-
casted address find their distance to the nearest black node (with a different ID). On
each side of the extreme point, the minimum distance of all these nodes is found in a
binary tree fashion. In other words, each two adjacent nodes repeatedly find their
minimum which will be compared to the minimum of their adjacent pair. As a result,
the nearest neighbor in each direction is found in O(log N) time. The extreme point
then finds the minimum distance between these four distances and knows which
figure, with which ID, is the closest neighbor to it. All the extreme points know their
closest neighbor in O(log N) time. The next step will be finding the minimum number
among the data of all the extreme points, which takes O(log N) time as well. &

Algorithm 19.1.8
Given an N 1/2 N 1/2 image, using an N N spin-wave reconfigurable mesh, the

nearest neighbor of a single figure can be found in O(1) time.

This is quite similar to the algorithm presented in Algorithm 19.1.7. Here, since
the image size is an order of N smaller than the size of the reconfigurable mesh, we
can find the maximum and minimum of numbers in O(1) using the technique
discussed in Algorithm 2 in the previous section. The time complexity of most of the
steps of the nearest neighbor algorithm explained above are O(1), except labeling
and finding the minimum number among the extreme points' ID which are
O(logN). As we showed previously, for a N 1/2 N 1/2 image, labeling can be done

in O(1) time, and similarly minimum distance is found in O(1) time.

&

Algorithm 19.1.9
The nearest neighbor of each of the multiple (N) figures in a given an N N image
using an N N reconfigurable mesh with spin-wave buses can be found in O(logN)
time.

As shown in Algorithm 19.1.7, the nearest neighbor of each single figure is
found in O(log N) time. The nearest neighbor of all figures can be found within
each connected region simultaneously. Therefore, the nearest neighbor of all
figures is found in O(log N). &

19.2. DISCRETE FOURIER TRANSFORM

One of the most important operations in image processing is discrete Fourier
transform (DFT) and its optimized version, fast Fourier transform (FFT). Many