Split and merge segmentation is an image processing technique used to segment an image. The image is successively split into quadrants based on a homogeneity criterion and similar regions are merged to create the segmented result. The technique incorporates a quadtree data structure, meaning that there is a parent-child node relationship. The total region is a parent, and each of the four splits is a child.
After each split, a test is necessary to determine whether each new region needs further splitting. The criterion for the test is the homogeneity of the region. There are several ways to define homogeneity, some examples are:
\sigma2=(1/(N-1))\sum(r,c)\epsilon[I(r,c)-\bar{I}]2
where r and c are row and column, N is the number of pixels in the region and
\bar{I}=(1/N)\sum(r,c)\epsilonI(r,c)
An example incorporation would be that the variance of a region be less than a specified value in order to be considered homogeneous.
The splitting results in a partitioned image as shown below to 3 levels.
Each level of partitioning can be represented in a tree-like structure.
The following example shows the segmentation of a gray scale image using matlab.[2] [3] The homogeneity criterion is thresholding, max(region)-min(region) < 10 for a region to be homogeneous.
The blocks created during splitting are shown in the following picture:
And the segmented image is below.