Segmentation by Hierarchical Step-Wise Optimization (HSWO)

The primary flaw with the previous region growing approaches is that the segmentaion produced by these approaches is non-optimal, thus are not unique. The number and shape of the partitions depend on the order in which the image is scanned and processed. The concept of optimality is not present as any partition that satisfies the conditions represent an equally valid segmentation of the image. This is where the Hierarchical Step-Wise Optimization provides a much more optimal solution.

In the first step, the algorithm initializes the segmentation by labeling each pixel. If a pre-segmentation exists, each pixel is labeled according to the pre-segmentation. Otherwise, each pixel is labeled as a separate region. In the second step, it calculates the dissimilarity criterion value between all pairs of spatially adjacent regions, finds the pair of spatially adjacent regions with the smallest dissimilarity value, and merges that pair of regions. In the third step, the algorithm stops if no more merges are required, otherwise it returns to the second step.

(a)

(b)

Fig. 4. (a) Region mean image for the segmentation result produced by HSWO with the BSMSE dissimilarity function at 36 regions and global dissimilarity value of 10.1357. (b) Hierarchical boundary map for (a).

In the implementation utilized here, all pairs of spatially adjacent regions that have the smallest criterion value are merged in the second step, resolving the issue of "ties."

The HSWO algorithm produces a globally optimal segmentation result if the statistics at all iterations are independent. However, excellent results are still obtained for natural images, in which the statistics are generally no independent. The sequence of partitions generated from this iterative approach creates a quality hierarchical boundary map of the image, including no scan line dependence. A problem, though, with this HSWO algorithm the large amount of computing time required: more than 30 minutes to process an 256 pixel X 256 pixel image on a 1.2 Ghz computer.