
Home Image processing Object removal Introduction Some results Download Stereovision Introduction Nolf2 example "Flower" example "Crane" example Region-based segmentation Introduction Current algos Results Image noise filtering Types of noise Gaussian filter Median filter Mean Shift filter Pictures of China Arrival to Beijing Ti'an and Ti'Shan Visiting Datong Back to Beijing Cook recipes Bier tart Pineapple - cheese canapés Garlic chocolates HTML pre-processor Principles Introduction Reference manual FAQ Complete example Download
	Version française

The Image Processing Corner

Fast hierarchical region-based segmentation algorithm

Hierarchical ?

We saw that the major issue with region-based segmentation is the difficulty to get the right region quantity. Indeed, each object owns its proper scale. In the 512x512 pixels "house" image below from the INRIA's MOVI project, the letters on the ground are around 50 pixels big, windows are 500 pixels big and the front of the house is 10000 pixels big.
If the size of the regions is constrained above 5000 pixels, the front of the house is correctly segmented but the letters are gone. On the other side, allowing region size of 50 pixels leads to plenty of small regions on the front of the house, which therefore looses its global aspect:

=> Every object owns its proper scale

Initial Image

Min size=50px
(320 régions)
Letters scale

Min size=500px
(98 régions)
Windows scale

Min size=5000px
(21 régions)
House front scale

This explains why a single region image is NOT a sufficient result that can be exploited: in an ideal way, one region image per scale is needed. Therefore the "hierarchical" term.

Introduction to the algorithm

The used method is close to a merge algorithm :

At initialization time, each pixel is considered as a region.
Regions are merged with their neighbors as described below, until all possible merges are done:
- In increasing order of the gradient of their common frontier.
- If and only if the value of the gradient is below the noise intensity (first parameter) or if one of the two regions is smaller than the required minimum size (second and last parameter).

The hierarchical property of the algorithm comes from looping in increasing order on the specified minimum sizes and saving the results for each of them. As the algorithm restarts from the result of the previous minimum size, processing an additional scale is not only fast but ensures also that new regions will be a collection of one or several regions of the previous scale.
This property is very important because the result can be thus formatted as a region pyramid.

Output informations differs from the classical ones:

A region number image (each pixel is an integer number). It correspond to the classical region image for the finest scale (50 pixels in the example). However, the numbering is special (see below).
A list of {Rmin, Rmax} couples, for each specified scale (3 in the example, 50, 500 and 5000). Each couple { Rmin, Rmax } correspond to a region which support in the image is the group of pixels whose region number is in the range Rmin to Rmax (for any region on the finest scale, Rmin=Rmax).

Note: A image denoise phase (similar to a sequential alternate filter but faster) has been added before the merge phase in order to improve noise robustness.

Note: The algorithm uses the color information when available.

Execution time

The objection which shall rise is : apply this algorithm as is leads to prohibitive execution times (O(N²) with the pixel quantity in the image).
Some minor approximations, in particular the recomputation of the "gradient between regions", and an efficient implementation of the region neighbors gradient sort overcome this.

To give an idea, the previous result on the 512x512 pixels "house" image, has been obtained in 0.35 seconds (0.31 s for the two first scales (50 and 500) and 0.28 s for the first one alone (50)).

The algorithm has been implemented in C++ (compiled with GNU g++ 3.2.2 option -O2 under Linux, on an AMD 1800+ processor).

Other result examples

The first row displays images with special colors to enhance contrasts. The region color is the average color.
The second row displays images with random colors for each area.

Algorithm parameters :