Region Splitting

Table of Contents

Introduction

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.

Theory

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.

Splitting

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:

Variance

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

Algorithm

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

Code

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);
  end
end

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

figure(1);
subplot(1,2,1);
imshow(I);
title('Original Image');

subplot(1,2,2);
imshow(blocks,[]);
title('Output Image');

Output

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

References