If we consider just the West, North, East, & South neighbors, then each grid element (or CAAPP PE) has four neighbors. If we also include the NorthWest, NorthEast, SouthEast, & SouthWest neighbors, then each PE has eight neighbors.
Frequently in image processing tasks, it is necessary to consider more than just the value at each location in the grid. We must often consider the value in relationship to the values of the neighboring grid elements. An example is the operation of smoothing an image.
Consider the simple smoothing operation implemented by taking the average of an element and its neighbors. If we use just the W, N, E, & S neighbors, we will be summing five values and dividing by five to obtain the average.
How can we accomplish the summing of these elements? Operations on planes are performed the same way at every PE. What facility exists to operate on a neighbor PE?
We provide this facility through the implementation of a mesh communication network that connects every PE to its neighbor in the West, North, East, and South direction. We provide an operation to shift every element in a plane to its neighbor in one direction using this mesh network.
Let x be some plane defined as an IntPlane;. Then,
z = x.West();
would cause each element in x to be moved as shown below.
Our simple smoothing operation can now be written as
smoothed = (x + x.West() + x.North()
+ x.East() + x.South() ) / 5;
The values of the smoothed plane are shown below.
For our example, we have shown just a small portion of a plane. The values outside of this portion are not shown and are unknown. These unknown values are represented by the character ? in the examples.
How would we create the smoothed result using all eight neighbors? The statement for this would be
z = (x + x.West() + x.North()
+ x.East() + x.South()
+ (x.West()).South() + (x.West()).North())
+ (x.East()).South() + (x.East()).North()) / 9;
or
z = (x + x.West() + x.North()
+ x.East() + x.South()
+ (x.South()).West() + (x.South()).East())
+ (x.North()).West() + (x.North()).East()) / 9;
and the result would be as shown below.
A better (more efficient) way of performing this operation would be to create an intermediate sum. Note that the above expressions do 9 additions and 12 shift operations. The following method uses 4 additions and 4 shifts.1
IntPlane smooth_8 (IntPlane x)
{
IntPlane temp(x.Size());
temp = x + x.West() + x.East();
return (temp + temp.North() + temp.South()) / 9;
}
A generalized smoothing function using neighbors on the diagonals, which takes the size of the window as an argument, is implemented by the following function.
IntPlane smoother(IntPlane x, IntScalar radius)
{
PlaneSize ps(x);
IntPlane tempw(ps), tempe(ps), tempn(ps), temps(ps);
IntPlane result(ps);
result = x;
tempw = x;
tempe = x;
for (int i = 0; i < radius; i++)
{
tempw = tempw.West();
tempe = tempe.East();
result += tempw + tempe;
}
tempn = result;
temps = result;
for (int j = 0; j < radius; j++)
{
tempn = tempn.North();
temps = temps.South();
result += tempn + temps;
}
return result / ((2 * radius + 1) * (2 * radius + 1));
}
We have touched on three important concepts in these examples.
The first is the concept of connectedness.
When we use just the West, North, East and South neighbors, we are using a four-way connected algorithm.
If we use the diagonal neighbors, regardless of the radius, we are using an eight-way connected algorithm.
When we talk about using the neighbors to affect the value at some PE, we are using a windowing operation. When the window is square, we specify the window by a radius. A window whose radius is zero is just a single PE and does not use any neighboring values.
The third concept is the concept of the edge of a plane. In the examples above, we used the ? character to denote unknown values in particular PEs. These values were unknown because we did not know the values beyond the edge of the data shown. Our examples showed just a portion of a plane. But, the problem still exists for a complete plane. What are the values past the edges of any plane?
The CAAPP implements the mesh communication paths as a torus. That is, the Western most PE's West neighbor is the Eastern most PE in the same row and the Northern most PE's North neighbor is the Southern most PE in the same column. This is a physical connection and is independent of the size of any plane! The ICL makes a distinction between the size of a plane as declared in a program and the actual size implemented so that the actual size is always some integer multiple of the physical size of the CAAPP. This allows the ICL to maintain the torus connection for any actual plane at a relatively low cost to performance.For the purposes of this discussion and the following examples, let us assume that the size of our CAAPP is 4 rows by 4 columns. If we define a plane using the following program fragment
IntPlane x(6,6);
...
for (row = 0; row < 6; row++)
{
Select active(x.RowIndex() == row);
for (col = 0; col < 6; col++)
{
Select active(x.ColIndex() == col);
x = (row * 10) + col;
}
}
we will cause the following mapping to the physical CAAPP.
Our plane is implemented using four tiles. What are the values in rows 6 & 7 or columns 6 & 7? We do not know. If we care about these values, and we should care if we are using the mesh, we must set them ourselves. For example(2),
{Select active ((x.RowIndex() >= 6) | (x.ColIndex() >= 6));
x = 0;
}
We also have to decide if we want to use values from around the edge of the torus.
In an example such as smoothing, we probably don't want to use these values(3).
How can we not use them?
First, we must decide what values we do want to use for window locations that are off the edge.
There are several ways that are traditionally used.
One way uses the torus connection.
Another method uses some specified value (usually zero as shown below).
A third uses the closest existing value.
These three ways are illustrated below using a 4 by 4 CAAPP grid and a 3 by 3 window.
We have seen examples of the first method already. The second and third methods are illustrated by the two functions shown below. Another commonly used method is called reflection. For windows with a radius greater than 1, further positions away from the center of the window are filled with values further in from the edge of the plane. It is as if a mirror were held up to the edge of the plane.
IntPlane
smoother_with_edge_value(IntPlane x, IntScalar radius,
IntScalar edge_value)
{
PlaneSize ps(x);
IntPlane tempw(ps), tempe(ps), tempn(ps), temps(ps);
IntPlane result(ps);
result = x;
tempw = x;
tempe = x;
for (int i = 0; i < radius; i++)
{
tempw = tempw.West();
{Select active(x.EastEdge_p());
tempe = edge_value;
}
tempe = tempe.East();
{Select active(x.WestEdge_p());
tempw = edge_value;
}
result += tempw + tempe;
}
tempn = result;
temps = result;
for (int j = 0; j < radius; j++)
{
tempn = tempn.North();
{Select active(x.NorthEdge_p());
tempn = edge_value;
}
temps = temps.South();
{Select active(x.SouthEdge_p());
tempws= edge_value;
}
result += tempn + temps;
}
return result / ((2 * radius + 1) * (2 * radius + 1));
}
IntPlane
smoother_with_nearest_value(IntPlane x, IntScalar radius)
{
PlaneSize ps(x);
IntPlane tempw(ps), tempe(ps), tempn(ps), temps(ps);
IntPlane result(ps);
result = x;
tempw = x;
tempe = x;
for (int i = 0; i < radius; i++)
{
{Select active(!x.WestEdge_p());
tempw = tempw.West();
}
{Select active(!x.EastEdge_p());
tempe = tempe.East();
}
result += tempw + tempe;
}
tempn = result;
temps = result;
for (int j = 0; j < radius; j++)
{
{Select active(!x.NorthEdge_p());
tempn = tempn.North();
}
{Select active(!x.SouthEdge_p());
temps = temps.South();
}
result += tempn + temps;
}
return result / ((2 * radius + 1) * (2 * radius + 1));
}
Each windowing method introduces some artifact into the resulting image. This is true regardless of what computer language is being used. Consequently, you have to be aware that this is occurring and take steps to rectify these problems. One method is to ignore results near the edge when windowing operations have been used.