The hierarchical image segmentation approach described herein was developed from earlier work described in [1], and is related to image segmentation approaches developed in [2-3]. An upcoming proceedings paper [4] will describe several algorithmic refinements the current version has over previously reported versions. This current report is restricted to the current status of a recent implementation of this approach on theHIVE.

As described on its web page (http://newton.gsfc.nasa.gov/thehive/), theHIVE is a Beowulf-class [5] parallel computer, (i.e., a cluster of Pcs running LINUX, connected by its on private LAN). theHIVE is a cluster of 64 computer nodes (bees) and two types of host of fronted nodes, the queen and one or more drones. The queen administers theHIVE and the drones allow access to theHIVE by users...

The previous implementation of this hierarchical segmentation (HSEG) algorithm was a pixel oriented approach on the MasPar MP-2 massively parallel computer. This implementation is called pixel oriented because each image pixel is assigned to a virtual processor. This approach makes it very easy to keep track of which regions are neighbors of each other, as the neighborhood information is implicit in the physical layout of the data in the virtual processors. The problem with this implementation is that it gets very inefficient when regions get large (contain a large number of pixels), since information must be propagated throughout all virtual processors handling image pixels for a particular region.

The current implementation of HSEG on theHIVE is a region oriented approach. In this approach, each region is represented by a node in a data structure. Information on which regions neighbor each other is maintained by a linked list, which must be updated after each merge. An array of region links keeps track of the physical location of each region in image space. This region oriented implementation gets very efficient as the regions grow and the total number of regions gets smaller, since fewer and fewer regions need to be considered in the analysis. The only processing that must be performed in the original image space is the bookkeeping required to keep track of the current physical extent and location of each region.

Both the pixel oriented and region oriented approaches can be implemented in a divide-and-conquer fashion. Here the HSEG algorithm is performed through intermediate points on rectangular subsections of the image which are reassembled for further processing. For example, a the processing of a 1024-by-1024 pixel image may be described as follows:

1) Divide the 1024-by-1024 pixel image into 1024 32-by-32 pixel sections which are processed until 256 (or fewer) regions are obtained in each section.

2) Assemble the appropriate 32-by-32 pixel sections into 256 64-by-64 pixel sections which are processed until 256 (or fewer) regions are obtained in each section.

3) Assemble the appropriate 64-by-64 pixel sections into 64 128-by-128 pixel sections which are processed until 256 (or fewer) regions are obtained in each section.

4) Assemble the appropriate 128-by-128 pixel sections into 16 256-by-256 pixel sections which are processed until 256 (or fewer) regions are obtained in each section.

5) Assemble the appropriate 256-by-256 pixel sections into 4 512-by-512 pixel sections which are processed until 256 (or fewer) regions are obtained in each section.

6) Assemble the 512-by-512 pixel sections into a single 1024-by-1024 pixel section which is processed with results saved at various natural convergence points.

In the above described divide-and-conquer implementation, no more that 1024 regions are considered at any time by the HSEG algorithm. A 1024-by-1024 pixel section of a 4-band Landsat MSS image has been successfully segmented using the above described approach and a region oriented implementation of HSEG in approximately 30 minutes on theHIVE. Image segmentation results with about 256 or fewer regions show no signs of the image partitioning.

As previous simulation of the divide-and-conquer approach (with an initial partitioning into 256-by-256 pixel sections) on the MasPar MP-2 using the pixel oriented implementation of HSEG suggested that over 9 hours of processing time would be required using 16 MasPar MP-2 computers!

We should note that this is not a fair comparison between theHIVE and the MasPar MP-2 computers. We anticipate that a recursive region oriented implementation of HSEG on the MasPar MP-2 should be able to segment a 1024-by-1024 pixel image in MUCH less than 9 hours.

References

[1] J. C. Tilton, Image segmentation by iterative parallel region growing and splitting, Proceedings of the 1989 International Geoscience and Remote Sensing Symposium, 2235-2238, Vancouver, Canada, 1989.

[2] J.-M. Beaulieu and M. Goldberg, Hierarchy in Picture Segmentation: A Stepwise Optimization Approach, IEEE Transactions. on Pattern Analysis and Machine Intelligence, 11 (2), 150-163, 1989.

[3] R. P. H. M. Schoenmakers, Integrated Methodology for Segmentation of Large Optical Satellite Image in Land Applications of Remote Sensing, Agriculture series, Catalogue number: CL-NA-16292-EN-C, Luxembourg: Office for Official Publications of the European Communities, 1995.

[4] J. C. Tilton, Image Segmentation by Region Growing and Spectral Clustering with Natural Convergence Criteria, to appear in the Proceedings of the 1998 International Geoscience and Remote Sensing Symposium, Seattle Washington, July 1998.

[5] Daniel Ridge, Donald Becker, Phillip Merkey and Thomas Sterling, Beowulf: Harnessing the Power of Parallelism in a Pile-of-PCs, Proceedings, IEEE Aerospace, 1997