National Aeronautics and Space Administration

In its original from, Hierarchical Step-Wise Optimization produces a much better quality in segmentation, and provides a direct approach to producing a segmentation hierarchy. However, these gains came at significant computational cost: It takes over 30 minutes on 1.2 Ghz computer to process a 256 x 256 pixel image. However, a recursive formulation of HSWO can bring the processing time down from over 30 minutes to less than a minute.

This recursive approach is a divide and conquer approximation of the HSWO, referred to as RHSWO, which is defined as follows:

• Given an input image, X, specify the number levels of recursion required (rnb_levels) and pad the input image, if necessary, so that the width and height of the image can be evenly divided by 2rnb_levels-1. Set level=1.
• Call rhswo(level,X).
• Execute the HSWO algorithm on the image X using as a pre-segmentation the segmentation ouput by the call rhswo() in step 2.

where rhswo(level,X) is as follows:

• If level = rnb_levels, go to step 3. Otherwise, divide the image data into quarters (designated by X/4) and call rhswo(level+1,X/4).
• After all four calls to rhswo() from step 1 complete processing, reassemble the image segmentation results.
• If level < rnb_levels, initialize the segmentation with the reassembled segmentation results from step 2. Otherwise, initialize the segmentation with one pixel per region. Execute the HSWO algorithm on the image X with the following modification: Terminate the algorithm when the number of regions reaches the preset value min_nregions. Exit.

* Note: rnb_levels and min_nregions are user defined variables.

(a)

(b)

Fig. 5. (a) Region mean image for the segmentation result produced by RHSWO with the BSMSE dissimilarity function at 39 regions and global dissimilarity value of 10.13. (b) Hierarchical boundary map for (a).