Image Segmentation

contents

Introduction

Splitting merge quadtree algorithm

Introduction

The segmentation problem

Image segmentation is a process in which regions or features sharing similar characteristics are identified and grouped together, The output of the segmentation step is usually a set of classified elements.

Most segmentation techniques are either region-based or edgebased.

Region-based techniques rely on common patterns in intensity values within a cluster of neighboring pixels. The cluster is referred to as the region, and the goal of the segmentation algorithm is to group regions according to their anatomical or functional roles.
Edge-based techniques rely on discontinuities in image values between distinct regions, and the goal of the segmentation algorithm is to accurately demarcate the boundary separating these regions.

Our goal:

Our goal in this work to implement our own segmentation algorithm based on splitting merge quadtree algorithm.

Our method:

We started implementing the algorithm using region-based technuiqes. The result of this algorithm wasn't satisfying. As the algorithm didn't handle well the edges of the objects in the picture. We then decided to combine it with edge-based criterions to enhance the results.

Splitting merge quadtree algorithm

The workflow:

The following diagram explains our workflow in a very high level

work flow

Split stage:

The split stage aimed to divide the image into homogenous regions according a certain color criterion.We used quadtree structure, it's a tree structure in which each internal node has exactly four children

Initially take the whole image as a single region
Check region homogenity according to a color criterion
- If the region is homogeneous then the region corespponds to an entire region in the imge
- If the region is considered non-homogeneous spllit it into four regions and repeat step 2 for each region until homogeneous criterion is fulfilled

Split stage color criterion:

Initially we used the most restrictive color Criterion, that each region has all its pixels with the same color.
For optimization and in order to get a more compact quadtree, we used the mean squared error measure.

Prunning stage:

Merging neighboring leaves with the same parent node using a color criterion less restrictive than the one used in the first step. This merging process is not iterative. The aim is to achieve a compacter QT representation to speed-up the rest of the process.

Merge stage:

Regions are sorted according to their size, giving more importance to the bigger regions and facilitating the merging of small regions with the big ones.

Only regions with a common boundary can be merged. This will represent the spatial constraint in the merging process

Consider each leave from the pruned tree as an initial cluster and create an ordered list according to their size.
Look for the first pair of neighbouring clusters in the list that can be merged according to the merging criterion. The search is done beginning by the biggest cluster in decreasing size order. Merging bigger regions first is aimed at looking for significant clusters supported by as much pixels as possible that act as seeds that grow by further collecting smaller neighbour clusters.
If any clusters are merged, reorder the list of clusters.
Repeat steps 2 and 3 until regions became stable. This part of the process correspond to an iterative sequence that may be seen as a coarse-to-fine segmentation process.

Merge criterion:

In this stage we combined edge and region information, we used Sobel edge detection approach to get the Magnitude and Direction of the image.

Sobel operator:

The operator uses two kernels which are convolved with the original image.

The x-coordinate is defined here as increasing in the "right"-direction, and the y-coordinate is defined as increasing in the "down"-direction. At each point in the image, the resulting gradient approximations can be combined to give:

the gradient magnitude, using:

magnitude

Using this information, we can also calculate the gradient's direction:

Direction

For merging two regions we used local processing edge linking approach combined with a color criterion.

To determine the homogenouty of R₁and R₂ we checked the similarity for each adjacent pixel from R₁ and R_2.The principal properties used for establishing similarity between two pixels:

Edge pixel with coordinates (s, t ) is similar in magnitude to pixel at (x, y ) if

|G (s, t ) − G (x, y )| < E

Edge pixel with coordinates (s, t ) has an angle similar to pixel at (x, y ) if

|Θ (s, t ) − Θ (x, y )| < A

pixels to check homogenouty

If each adjacent pixel from R₁ and R₂ satisfy the above criterions, then we check the color similarity of the regions R₁ and R₂ using the following formula, if

|color (R₁ ) − color (R₂ )| < C

Then the regions are homogenous, if not then the regions are non-homogenous