Block Diagram of Region Growing Algorithms
The region growing techniques took on a variety of aspects the block diagram below illustrates the potential sequences of processes that can lead to segmentation using region growing.
Uniform blocking is the first step in any of our algorithms. This step involves dividing the images into uniform blocks for processing. We typically used 2x2 blocks if region growing was to be employed directly or 16x16 blocks if the merge-split algorithm was to be used. It shouldn't matter what blocksize is fed into the merge-split routine, but picking an intermediate value enhances the speed for most images.
The merge-split routine is an optional stage of our region growing based segementation scheme. It requires a threshold as an input. This threshold determines which blocks can be merged into a single block and which blocks can be split into smaller blocks based on the difference between the maximum and minimum intensities in each block. If the max-min difference of a block is close to the max-min difference of its neighbors (i.e., difference between blocks is within the threshold), then the blocks are merged into a single block. A block is split in half if the max-min difference of the block exceeds the threshold. The merge-split mechanism is a quadtree structure, meaning that the merging and splitting of blocks goes from 4 to 1 and 1 to 4 respectively. This process is done recursively until, no blocks satisfy the criteria to be split or merged. Thus a block whose max-min difference exceeds the threshold will continue to be split until the max-min difference of the subsequent block(s) are within the threshold or the blocksize reaches one pixel, in which case the max-min difference is zero. There is also a minimum block size argument which allows the user to specify the smallest blocksize that can be generated through splitting. This allows the user to force the segmenting algorithm to end up with a small number of regions by ensuring that the output of the merge-split algorithm has blocks that are no smaller than a specified size. Without this feature there is a potential for the merge-split routine to return many small blocks. If these blocks are not successfully merged by the region growing algorithm, undesirable results are likely.
Region growing is done by examining properties of each block and merging them with adjacent blocks that satisfy some criteria. We used one of two criteria. One criteria is to look at the max-min difference and combine adjacent regions whose max-min difference is within a tolerance of the seed block's. The new region is now the seed and the process is repeated, examining adjacent regions, comparing max-min differences, and adding blocks that are within the tolerance specified by the user. This tolerance does not have to be the same as the threshold used in the merge-split algorithm. Alternatively, the mean values of the blocks can be used to determine which blocks should be merged.
Note the enhanced results from the dissolve algorithm.
Note the progressively larger block sizes indicated in the upper right plots of each sequence as the threshold is increased.
Note the enhanced results from the use of the dissolve algorithm above.
The merge-split algorithm due to its use of a criteria based on the difference between the maximum and minimum pixel values within the region tends to act like an edge detection algorithm. In smooth (no noise or textures) and low gradient images, edges are the only areas where large differences in pixel values tend to occur. As a result near edges, the merge-split algorithm tends to split blocks down to individual pixels. Larger merged blocks appear in the interiors. So for this class of images, merge-splitting is an effective first stage in segmentation, and region growing can take place faster. For images with complex subregions, fine detail, patterns, and gradients such as the plane, merge-splitting with a max-min criteria doesn't buy you that much. Too low a merge split threshold creates too many small pixel size regions. Too high a merge split threshold creates too many large blocky regions. Using merge splitting prior to region growing tends to result in sharper edges. Unfortunately it also results in blockiness in the final image. On the other hand, region growing without merge-splitting generated images with blurry edges.
It is difficult to say which of the region growing algorithms worked better in general. The two algorithms each had difficulties dealing with various image features. The max-min algorithm did a better job of preserving edges and handled some textures better than the mean algorithm. The mean algorithm did better on images with speckle. In the end the choice of the algorithm really depends on the image you are dealing with. Neither algorithm, with or without merge splitting, is really optimal for segmenting diverse image types, but then again what is? Effective segmentation of an image requires some level of global analysis and understanding of the image features. Neither of these algorithms performs any sort of high level spatial correlation, so it is understandable that they fail for complex images consisting of complex regions.