Region Splitting

Table of Contents


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.


The basic idea of region splitting is to break the image into a set of disjoint regions which are coherent within themselves:

If only a splitting schedule is used then the final segmentation would probably contain many neighboring regions that have identical or similar properties. Thus, a merging process is used after each split which compares adjacent regions and merges them if necessary. Algorithms of this nature are called split and merge algorithms. To illustrate the basic principle of these methods let us consider an imaginary image.


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:


where r and c are row and column, N is the number of pixels in the region and Variance

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.

Image Partitioning

Each level of partitioning can be represented in a tree-like structure.

Tree Splitting


Region Splitting Step 1
Region Splitting Step 2
Region Splitting Step 3


MATLAB function: Quadtree decomposition

S = qtdecomp(I, threshold, [mindim maxdim])

Sample Code:

I = imread('images/cameraman.jpg');

S = qtdecomp(I, 0.4);
blocks = repmat(uint8(0), size(S));

for dim = [512 256 128 64 32 16 8 4 2 1];
  numblocks = length(find(S==dim));
  if (numblocks > 0)
    values = repmat(uint8(1), [dim dim numblocks]);
    values(2:dim,2:dim,:) = 0;
    blocks = qtsetblk(blocks,S,dim,values);

blocks(end, 1:end) = 1;
blocks(1:end, end) = 1;

title('Original Image');

title('Output Image');


Region Splitting Output 1
Region Splitting Output 2
Region Splitting Output 3