Connected-Component Labelling

[86] is applied after unimodal thresholding to identify all the clusters of spatially connected clique families. The unimodal thresholding algorithm converts an MBIM into a binary image, e.g., by assigning the clique families with the partial energy above the threshold with `1's, and with `0's otherwise. With a rather aggressive threshold, the regions with `1's are expected to be well isolated from the background with `0's. This allows the labelling algorithm to identify the clusters by sequentially scanning the binary image. The labelling algorithm scans a binary image twice in a raster scanline order, e.g, from left to right and from top to bottom of the image. In the first pass, the algorithm tags each `1' pixel with either an old label if it is connected to any pixel with the label or a new label otherwise. In the second pass, the algorithm merges equivalent labels, i.e. different labels assigned to connected pixels, and discovers possible new connections. As the result of the algorithm, each image region for a cluster is identified by a distinguishing label. The connectivity could be 8- or 4-nearest neighbourhood in the simplest case. This two-pass labelling algorithm might be neither space or time efficient especially for large images [70], but it is proved to be sufficient for usually small sized MBIMs. Smoothing operations might be applied before and after clustering in order to remove noisy or spurious clusters. The pseudo code for a single step of the labelling algorithm is outlined in Algorithm 6.

Figure 6.8: Detecting connected components by sequential scans.