Split and merge segmentation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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.

Algorithm[edit]

  • Define the criterion to be used for homogeneity
  • Split the image into equal size regions
  • Calculate homogeneity for each region
  • If the region is homogeneous, then merge it with neighbors
  • The process is repeated until all regions pass the homogeneity test[1]

Homogeneity[edit]

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:

  • Uniformity- the region is homogeneous if its gray scale levels are constant or within a given threshold.
  • Local mean vs global mean - if the mean of a region is greater than the mean of the global image, then the region is homogeneous
  • Variance - the gray level variance is defined as

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

An example incorporation would be that the variance of a region be less than a specified value in order to be considered homogeneous.

Data structure[edit]

The splitting results in a partitioned image as shown below to 3 levels.

Partition.jpg

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

Tree structure.png

Example[edit]

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.

Original grayscale.png

The blocks created during splitting are shown in the following picture:

Smblocks seg.jpg

And the segmented image is below.

Segmented project box.png

References[edit]

  1. ^ E.,, Umbaugh, Scott. Digital Image Processing and Analysis with MATLAB and CVIPtools, Third Edition (3rd ed.). ISBN 9781498766074. OCLC 1016899766.
  2. ^ C., Gonzalez, Rafael (2004). Digital Image processing using MATLAB. Woods, Richard E. (Richard Eugene), 1954-, Eddins, Steven L., 1964-. Upper Saddle River, NJ: Pearson/Prentice Hall. ISBN 0130085197. OCLC 54345501.
  3. ^ "Quadtree decomposition - MATLAB qtdecomp". www.mathworks.com. Retrieved 2018-04-24.