One of the most common operations in image understanding tasks is the segmentation of an image into many regions. Examples include the support regions for lines in the image or contiguous areas having similar intensity values. Illustrated below is a plane segmented into five different regions.
Once the image is segmented, we might want to do operations such as counting the number of PEs in each region or finding the center of mass of each region. We would like to do these operations in parallel by region. That is, we do not want to select each region one at a time and perform the same operation on it separately.
Several questions arise.
How do we form the regions?
How do we communicate values in a region?
How do we operate on the regions in parallel?
We form the regions by setting up a network of connections called the Coterie Network. We connect those PEs in a region by connecting switches between them. Each PE has four switches to connect to its four neighbors in the West, North, East, & South directions. If a PE has its West switch closed and its West neighbor has its East switch closed, then the two PEs are connected and belong to the same region. Below is an enlargement of the area enclosed by dotted lines in the previous figure. This figure shows the individual PEs and their switches. Note how the switches define the regions.
We set the switches by using a CoterieWENS declaration(1) and some BitPlanes. The planes specify the switch settings in the four directions as shown in the code below.
BitPlane west(ps), east(ps), north(ps), south(ps);
.....
{CoterieWENS pattern(west,east,north,south);
....
}
The switch settings have a scope defined by the block containing the CoterieWENS declaration. They may also be nested with the most recent declaration completely overriding the others.
The criteria we use to set the West, East, North & South switches defines the criteria for the regions. The usual method is to compute some value for each PE that places that PE in some equivalence class. Obviously, we may use many different ways to define these switch settings. Our original example above might have been created by the following statements.
UCharPlane intensity(ps);
UCharPlane eq_class(ps);
eq_class = 0;
{Select active(intensity > 200);
eq_class = 3;
}
{Select active(intensity > 150);
eq_class = 2;
}
{Select active(intensity > 100);
eq_class = 1;
}
{CoterieWENS pattern(
eq_class == eq_class.West(),
eq_class == eq_class.East(),
eq_class == eq_class.North(),
eq_class == eq_class.South());
.....
}
Once we have set the switches, the PEs that are connected may communicate.
The ICL provides three methods that do the communication.
The first method allows a PE in each region to broadcast a value to every other PE in the same region.
{CoterieWENS pattern(...);
receive_value = send_value.RegionBroadcast (sender);
}
We first define the regions with the CoterieWENS declaration and then use the RegionBroadcast method to send the value stored in send_value to all the PEs.
Which PE sends the value?
The variable sender specifies which PEs broadcast their value.
The argument to RegionBroadcast must be a BitPlane with a one bit for those that send and a zero bit everywhere else.
All planes used in these three methods must be compatible with the planes used in the Coterie declaration to define the regions.
What happens if more than one PE in a region sends a value? The value sent is the bitwise logical OR of all the senders values. The values are actually sent a bit at a time. If any PE sends a one bit, the value read is a one bit. If no PE sends a one bit, the value read is a zero bit.
How do we make sure that only one PE in each region sends at a time? The usual method is to select one PE to be the master PE for a region. How is this master PE selected? Again, there are many different ways in which this may be accomplished. However, the ICL provides two methods that make this task simple. These two methods create a BitPlane by selecting the minimum or maximum value in each region. For example, in the code below we select the PE with the minimum address in each region.
{CoterieWENS pattern(...);
BitPlane sender(ps);
sender = (x.Index()).RegionSelectMin ();
receive_value = send_value.RegionBroadcast (sender);
}
In this example, sender is a BitPlane whose values are generated by the method RegionSelectMin(2).
This method picks the PE with the minimum value of x.Index().
For any plane, the Index method generates an IntPlane of unique indexes for every PE.
Therefore, we know that there is one and only one PE selected by BitPlane sender in each region.
Another example is given below. This code broadcasts the maximum value of some plane for each region to all the other PEs in the region. After execution, the plane some_value has the same value for every PE in the same region.
{CoterieWENS pattern(...);
BitPlane sender(ps);
sender = some_value.RegionSelectMax ();
some_value = some_value.RegionBroadcast (sender);
}
In this example we are not guaranteed that the sender is unique in each region.
However, regardless of how many senders there are in a region, we are guaranteed that every one is sending the same value.
RegionSelectMin and RegionSelectMax select the minimum or maximum from all of the PEs in a region. You can restrict the candidates for the selection by supplying a BitPlane argument to the select method.
BitPlane subset (ps);
....
{CoterieWENS pattern(...);
selection = some_value.RegionSelectMax (subset);
....
}
Let us now do a more interesting example.
Suppose we need to compute the square of the distance of every PE from the center of the extents box(3) that bounds each region.
First we need to determine the extents boxes and then broadcast the center to each PE.
It is then a simple matter to compute the distances.
{CoterieWENS pattern(...);
BitPlane master(ps);
UShortPlane minrow(ps), maxrow(ps), mincol(ps), maxcol(ps);
UShortPlane center_row(ps), center_col(ps);
ShortPlane row_diff(ps), col_diff(ps);
master = (master.RowIndex()).RegionSelectMin ();
minrow = (master.RowIndex()).RegionBroadcast (master);
master = (master.RowIndex()).RegionSelectMax ();
maxrow = (master.RowIndex()).RegionBroadcast (master);
master = (master.ColIndex()).RegionSelectMin ();
mincol = (master.ColIndex()).RegionBroadcast (master);
master = (master.ColIndex()).RegionSelectMax ();
maxcol = (master.ColIndex()).RegionBroadcast (master);
center_row = (min_row + max_row) >> 1;
center_col = (min_col + max_col) >> 1;
row_diff = master.RowIndex() - center_row;
col_diff = master.ColIndex() - center_col;
distance_sqr = row_diff * row_diff + col_diff * col_diff;
}
An interesting thing about this example is that the only input to this code is the region definition (not explicitly shown) used in the CoterieWENS declaration.
Note also that every variable is a temporary except for distance_sqr and will disappear when the block is exited.
This example re-computes the row and column indexes because this is faster than using a saved copy.
You may have wondered about the effect of setting the West switch of the Western most PE or the South switch of the Southern most PE. Is there anything to which these switches connect? The answer is that the Coterie Network is connected in the shape of a torus. That means the the Western most PE can connect to the Eastern most PE in the same row and that the Northern most PE can connect to 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 efficiently maintain the torus connection for any actual plane.Because of this torus connection, regions may be created across this connection(4). We must also be concerned with the case where the actual size of our planes is greater than the size we declared them with. To avoid this, our original example could be written as
....
PlaneSize ps(eq_class);
BitPlane w(ps), e(ps), n(ps), s(ps);
// Disconnect the edges of the torus
w = (eq_class == eq_class.West()) & ~eq_class.WestEdge_p ();
e = (eq_class == eq_class.East()) & ~eq_class.EastEdge_p ();
n = (eq_class == eq_class.North()) & ~eq_class.NorthEdge_p ();
s = (eq_class == eq_class.South()) & ~eq_class.SouthEdge_p ();
// Disconnect from PEs that we aren't using
{Select active(
(eq_class.RowIndex() > maxr) |
(eq_class.ColIndex() > maxc));
w = 0; e = 0; n = 0; s = 0;
}
{CoterieWENS pattern(w, e, n, s);
.....
}
The IUA provides hardware support for Coterie operations that make them very fast.
Further speed may be obtained for two special cases which are recognized by both the hardware and the ICL.
The Coterie may be connected as either a set of row or column buses.
We use the CoterieWE declaration for the first case and the CoterieNS declaration for the second case.
Instead of four BitPlanes, these declarations only use two and allow the switches to be set only in the indicated directions.
One operation that is frequently needed is a scan. Suppose that you want to number selected PEs with consecutive values. That is, the first selected PE is numbered 1, the second is numbered 2 and so on. If the selected PEs are as shown below, then the result of the plus scan would be the indexes shown for each PE.
We can compute this plus scan by using the row bus and column bus. First, we will number the selected PEs consecutively in each row. Then, we will add to each row, the number of active PEs in the previous rows.
In parallel for each row, we find the first PE in the row that has not yet been found. Each time we find one, we add one to a counter in every remaining PE using the row bus. We then remove that PE from the remaining ones and loop until there are none remaining in any row. The result is a plus scan on the individual rows.
Once the rows have been scanned, we broadcast the maximum value of the scan to every other PE in that row. Then, a similar scan operation is performed using the column buses but this time the maximum value of each row is broadcast on the column buses.
UShortPlane
plus_scan (BitPlane selected)
{
Everywhere active;
PlaneSize ps(selected.Size());
BitPlane min(ps); // Minimum in row (column)
UShortPlane index(ps); // Index in row & plane
UShortPlane row_max(ps); // maximum index in each row
BitPlane all_ones(ps);
BitPlane remaining(ps);
remaining = selected;
all_ones = 1; // Row & Column bus switches
index = 0;
{CoterieWE pattern(all_ones, all_ones);
while (remaining.Any())
{ // Number across columns
min = (remaining.ColIndex()).RegionSelectMin (remaining);
index += min.RegionBroadcast (min);
remaining &= ~min; // This one is done.
row_max = index.RegionBroadcast (index.RegionSelectMax ());
}
}
remaining = row_max > 0;
{CoterieNS pattern(all_ones, all_ones);
while (remaining.Any())
{ // Number across rows
min = (selected.RowIndex()).RegionSelectMin (remaining);
remaining &= ~min; // This row is done
{Select active(remaining & selected);
index += row_max.RegionBroadcast (min);
}
}
}
return index;
}
Readers familiar with C++ will note that the name pattern, used in the Coterie declarations, is actually the name of a variable. We could use any name for this variable! However, we urge you to always use the name pattern. By being consistent, you will avoid errors that result from defining the Coterie twice in one block because the compiler will be able to detect this (multiple definition of a variable). And, other people will have an easier time reading your programs.For convenience, all three declarations will accept a single UCharPlane instead of multiple BitPlanes to define the regions. The least significant four bits of the UCharPlane define the four switches. Using the BitPlanes from above, we may define the regions by the following code.
UCharPlane region_def(ps);
region_def = w + (n << 1) + (e << 2) + (s << 3);
{CoterieWENS pattern(region_def);
...
}
For CoterieWE, the North and South switches are always set open regardless of how the corresponding bit is set.
For CoterieNS, the West and East switches are always set open.
BitPlane RegionSelectMin(IntPlane value)
{
Everywhere active;
BitPlane sender(value.Size()), temp(value.Size());
sender = 1;
for (int i = 31; i >= 0; i--)
{
temp = value.Bit(i);
sender = temp ^ (~temp).RegionBroadcast(sender);
}
return sender;
}