## Hierarchical Image Segmentation

Hierarchical Image Segmentation, as presented here, is identical to HSWO with the the addition of a spectral clustering option. Spectral clustering allows the merging of spatially non-adjacent regions, resulting in spatially disjoint regions.

The algorithm defintion and description of each step ensues as follows:

Description | Defintion | |
---|---|---|

1 | Give each pixel a region label. If a pre-segmentation is provided, label each image according to the pre-segmentation. Otherwise label each pixel as a separate region. |
Step 1 initiates the HSEG algorithm by setting the initial region labels for each image pixel. |

2 | Calculate the dissimilarity value, dissim_val, between all pairs of spatially adjacent regions. If the spectral clustering weight, spclust_wght > 0.0, also calculate dissim_val for spatially non-adjacent regions. | In step 2, the dissimilarity criterion values for all pairs of spatially adjacent regions are calculated. If spclust_wght > 0.0, the dissimilarity criterion values for all pairs of spatially non-adjacent regions are also calculated. In the implementation, the results with the minimum value of the dissimilarity criterion value for each region are the only results that are saved from the dissimilarity criterion calculations. |

3 | Find the smallest dissim_val between all spatially adjacent pairs of regions and set nghbr_thresh equal to it. Set prev_max_threshold = 0.0 and max_threshold = nghbr_thresh. | In step 3, the value of the max_threshold variable is set. This value is output by HSEG to be used in the processing window artifact elmination process. It is also used internally by HSEG to accelerate the region merging process by forcing the region merging threshold to be strictly non-decreasing. The value of prev_max_threshold is also, intialized to 0.0. Along with max_threshold, prev_max_threshold is used in convergence checking step 11. |

4 | If spclust_wght = 0.0, go to step 7. Otherwise, if max_threshold = 0.0, merge all pairs of regions with dissim_val=0.0. If max_threshold > 0.0, merge all pairs of regions with dissim_val < spclust_wght*max_threshold. | Step 4 is executed only if spclust_wght > 0.0. If max_threshold > 0.0, only spatially non-adjacent merges will occur. If max_threshold = 0.0, no merges will occur by the dissim_val < spclust_wght*max_threshold test, and spatially adjacent and non-adjacent merges are made by the dissim_val = 0.0 test. |

5 | If the number of regions remaining is less than or equal to the preset value chk_nregions, go to step 11. Otherwise, update the dissim_val's between spatially adjacent pairs of regions as necessary. | Step 5 checks to make sure the number of regions for convergence checking hasn't already been reached. If not, the dissimilarity criterion values between spatially adjacent region pairs are updated as necessary. |

6 | Find the smallest dissim_val between spatially adjacent pairs of regions and set nghbr_thresh equal to it. If nghbr_thresh > max_threshold, set prev_max_threshold = max_threshold and then set max_theshold = nghbr_thresh. | Step 6 finds the smallest dissimilarity criterion value between spatially adjacent regions and sets the threshold variable to it. If the current value of max_threshold is less than nghbr_thresh, the value of prev_max_threshold is updated to the value of max_threshold and value of max_threshold is updated to the value of nghbr_thresh. |

7 | Merge all pairs of spatially adjacent regions with dissim_val ≤ max_threshold (update dissim_val's as necessary). | Step 7 does the merging between spatially adjacent regions and keeps the dissimilarity criterion values updated as necessary. |

8 | If the number of regions remaining is less than or equal to the preset value chk_nregions, or if spclust_wght = 0.0, go to step 11. Otherwise, update the dissim_val's between all pairs of spatially adjacent and non-adjacent regions. | Step 8 checks to make sure the number of regions for convergence checking hasn't already been reached. If not, if spclust_wght > 0.0, the dissim_val's between spatially non-adjacent regions are updated as necessary. |

9 | Merge all pairs of spatialy adjacent or non-adjacent regions with dissim_val ≤ spclust_wght*max_threshold. (update dissim_val's as necessary). | Step 9 performs the merging between spatially non-adjacent regions, and keeps the dissimilarity criterion values updated as necessary. |

10 | If the number of regions remaining is less than or equal to chk_nregions, go to step 11, else go to step 6. | Step 10 checks to see if convergence checking, step 11, should be executed, and sends the process to step 6 or 11 as appropriate. |

11 | If the number of regions remaining is less than or equal to conv_nregions, save the current region label map along with associated region information and STOP. If this is the first this step is executed, save the current region label map with associated region information and go to step 6, else calculate tratio = max_threshold/prev_max_threshold. If tratio is greater than the preset threshold convfact, save the region label map from the previous iteration along with associated region information and go to step 6, else just go to step 6. | Step 11 performs convergence checking. If final convergence has been reached, the appropriate results are output and the algorithm is terminated. Otherwise, convergence checking is performed for determining whether or not the results from the current or previous iteration should be output as a hierarchical level in the segmentation hierarchy output by HSEG. Then the process is returned to step 6. |

(a)

(b)

(c)

(d)

Fig. 7. Segmentation results for RHSEG with spclust_wght=1.0, processing window artifact elimination, and with the BSMSE dissimilarity function. (a) Region mean image for the 13 region segmentation result and global dissimilarity value of 9.9326. (b) Hierarchical boundary map for (a). (c) Region mean image for the 9 region segmentation and global dissimilarity value of 11.6204. (d) Hierarchical boundary for (c).

Spectral Clustering, the merging of spatially non-adjacent regions, enables the representation of an image in a fraction of the number of regions required for the case where the merging of spatially non-adjacent regions is not allowed (i.e., when spclust_wght=0.0). However, this creates disjointed subregions. But, whether or not this is acceptable depends on the application. Thus, a hierarchical segmented image with a higher global dissimilarity value, as in Figure 7d, would produce a segmentation closer to the previous results. Whereas, the global dissimilarity value approximate to the previous segmentation results, produces a more detail segmentation, as in Figure 7b. Ultimately, this demonstrates the level of detail spectral clustering maintains.