Details

A set of points is given in an square grid. A Moore window around a point is the list of eight points surrounding it, corresponding to its NW, N, NE, E, SE, S, SW, and W neighbors. To illustrate the component identification and boundary delineation, it is important to construct some artificial components first. To do this, points from the Moore windows of a set of randomly chosen seeds are added to form a new set. Then more points from Moore windows of random points of this set are added. As this process is applied times and duplicate copies are deleted each time, the set grows into multiple windows of random shapes.

The morphological component identification is performed with the routines BottomLeftPoint, RetWindow, and AllWindows.

As the name suggests, the BottomLeftPoint returns the point in the bottom-left portion of the list. The RetWindow routine takes a list of points and returns the first connected component or window. It works according to the ”one component at a time” method given in [1], using buffer, window, and total stacks to track the points in a binary search scheme.

Define the total stack to be the complete set of points (from all windows). Let denote the point at the bottom left. Add to the buffer stack. Let be the connected members of in the Moore window. Add them to the buffer stack with as the first member to get . Also add to the window stack, drop from the buffer, and drop from the total stack. Next, look for members connected to ; call them and add them to the buffer stack. As before, add to the window stack, drop from the buffer stack to get , and drop from the total stack.

Progressing like this sequentially, all members of a single window are identified using "marching squares." It is important that this routine be coded optimally to minimize the number of comparisons, unions, complements, etc. The AllWindows routine takes the complete set of data and returns all the windows.

The boundary delineation is performed with the routines ClkRot, BottomLeftPoint, and Bdry.

The Bdry routine takes the map given by indices and computes the boundary using Moore’s algorithm (given in [2]). It uses the function ClkRot for clockwise rotation of neighborhood points. The function resembles a wheel spinning in the clockwise direction at each point on the boundary, using the backtracking variable . It starts from the point at the bottom left in the window. As a side benefit, the returned boundary is also ordered in the clockwise orientation.

In the Demonstration, choose settings and generate points to see how the different components are identified and boundaries drawn. You can also notice that if the seeds are closely located, with adequate expansions, the components coalesce, yielding a single boundary.

References

[1] Wikipedia. "Connected-Component Labeling." (Jan 27, 2015) en.wikipedia.org/wiki/Connected-component_labeling.

[2] Wikipedia. "Moore Neighborhood." (Jan 27, 2015) en.wikipedia.org/wiki/Moore_neighborhood.