Papers

 

 

 

3D Entropy Based Image Segmentation

 

 

eng. Georgi Petrov

 

 

Introduction


This article makes a short comparison between several multidimensional image segmentation methods using global image histogram multistage entropy functions and combination
with 2D entropy. Using two types of 3D image histogram entropy we can create automatic and optimal image segmentation for different applications such as; micro objects inspection and biomedical cell analysis systems, digital video for security applications and multimedia motion based segmentation. 


Image segmentation using 2D entropy function

 

Entropy function of 2D grey scale image histograms can be used for automatic image segmentation. For more details see here.

Maximum of entropy function can be used for automatic threshold pointer that defines the brightness threshold value – b* for the image (Fig. 1.a and Fig. 1.b).
 

Fig.1.a, Grey scale image (right) and its 2D PDF (left)
Fig.1.b, BW image (right) calculated using threshold level defined by 2D entropy function (left)

Image segmentation using 2D multistage entropy

Single stage 2D entropy function is fast and automatic approach for thresholding different images, preferably for inspection needs. When we work with outdoor and complex images this is not sufficient. Thus the multistage 2D entropy function can be used (Fig. 2) compares multistage image thresholding using fixed values and entropy calculated values.

Fig.2.a, Multi threshold – 4 layers, using fixed values
Fig.2.b, Multi threshold – 4 layer image, using multistage 2D entropy (right) and its entropy (left)

This function can be used to create image object extraction mask - this mask is used foe multilayer object based segmentation. We can continue this local entropy segmentation using the same procedure for any new entropy region inside image histogram. Best results can be achieved using 4, 8 and 16 layered mask.


3D Entropy based image segmentation

2D entropy function is commonly used for many image segmentation applications. 2D entropy lacks his robustness when multiple images with large variety contrasts between different regions and background need to be segmented. Here 3D entropy function comes in sense. Before this we need to define and calculate 3D image histogram (joint pixel probability function) (Fig. 3.a). Using this histogram we can calculate 3D entropy function (Fig. 3.b). Finding its maximum we can threshold image much better than using 2D entropy. This type of thresholding will provide us information regarding two types of joint pixels: homogeneity zones (joint pixels having the same brightness) and non homogeneity (object surrounding areas and shades).

a b
Fig. 3, 3D image histogram (a), 3D entropy function (b)

3D entropy function is calculated as a sum of all entropy functions calculated for 3D histogram columns and rows. The maximum of this function can be found dividing 3D histogram in to 4 separate regions; A, B, C, D (Fig. 4). Zones A and B corresponds to object and background, and zones C and D corresponds to object shades and surrounding areas brightness gradient. In most of cases 3D entropy maximum lays on the main diagonal passing through A and B quadrants.

Fig. 4, 3D entropy maximum divide 3D image histogram in to 4 regions (A, B, C and D)

This diagonal plays an important role in 3D histogram, because values laying on it represent the probability to occur different homogeneity zones inside of image. If images are noisy or very shaded, their histogram maximum can lie around main diagonal. In most cases well filtered images have most of values grouped around main diagonal. Different authors examine zone C and D separately, but we thing that for most of standard applications we can treat B, C and D as background. Zones C and D take an important role when multistage segmentation is taking place. If we have 3D normalized histogram:

(1)

 

 

We calculate image 3D entropy function using discrete histogram . 3D entropy is calculated for each column and row inside using method described in section (2.1). After this we create two 3D entropy functions, first is called gradient entropy function and is presented by;

(2)

 

And second for rows;

(3)

 

After this we need to find entropy maximum:

(4)

Some implementations may consider that 3D entropy function is a simultaneously calculated for each one point inside 3D histogram. We prefer to create 3D entropy function as a fraction of 2D columns and rows. This kind of representation gives us the right to make image segmentation based on entire 3D entropy (Fig. 5) and on 3D gradient entropy, without having the need to recalculate 3D entropy each time we need to make segmentation for homogeneity and gradient zones.

a b
Fig. 5, Image thresholding using 2D entropy function (a), and using 3D entropy function (b).

Image segmentation using 3D gradient entropy

Because 3D entropy is based on 2D entropy calculation of single columns and rows we introduce a new 3D gradient entropy function. This function examines only the columns of 3D histogram, interpreting values on main homogeneity diagonal as zeros. This approach gives us a powerful method to calculate entropy only of brightness transition zones. This technique give use the power of local adaptive 2D entropy segmentation method and histogram equalization using global 3D image histogram (Fig. 6).
 

a b c
Fig. 6, 3D image gradient entropy (a), image segmented using 3D gradient entropy (b), and using standard 3D entropy (c)

3D gradient entropy can help us to find target object even if we work with noisy images having bad spatial resolution and contrast (Fig. 7).

a b c
Fig. 7, Input image (a), 3D gradient entropy (b), and 2D entropy (c) – object is lost.

Multistage 3D and gradient entropy

In section 2.2 we explained how a multistage segmentation mask can be calculated using entropy based histogram division and local entropy definition. No considers we have 3D entropy function calculated for . In section 3 we define how simple BW threshold value can be calculated more precisely taking in account joint pixel probability distribution. Nothing easier if we treat 3D histogram quadrant A and B, C, D as we treated 2D histograms and . In this case we will define and histograms (Fig. 7). Remember to fill all non target histogram quadrants as filled with zeros. Thus the multistage 3D entropy function is calculated.


Fig. 7, Multistage 3D entropy segmentation

3D gradient multistage entropy is calculated by calculating entropy functions for all columns of 3D histogram, treating main diagonal as filled with zeros. Difference between 3D multistage entropy and 3D gradient multistage entropy is shown on Fig. 8. Because gradient entropy analyze and group only image shading zones it can be used as a stage before image texture analysis.

a b
c d
e f
Fig. 8, Multistage 2D entropy image (a) and 3D histogram (c), 3D gradient entropy image (b) and his histogram (d), 3D entropy function (e), 3D gradient entropy function (f).

Entire 3D entropy function trends to separate 3D histogram mainly inside main homogeneity diagonal, making easier to better extract image homogeneity zones and surrounding areas (Fig. 8,b). In opposite to this 3D gradient entropy separate 3D histogram in to different pikes around homogeneity diagonal (Fig. 8,e).

Complex method for multidimensional entropy based image segmentation

Above we have explained two global histogram methods for 2D and 3D entropy based multistage image segmentation. These methods can be combined in to multidimensional entropy image. Results obtained from 2D and 3D multistage entropy give us a good understanding about image object laying in large spatial areas and their edges and surrounding areas and shades. 3D gradient entropy multistage segmentation give us the information regarding image global shading, thus giving a god background for future texture analysis and processing using global histogram methods. Combining results achieved by 2D multistage entropy and 3D gradient entropy provide valuable information regarding large and small object statistical representation. Multistage entropy image 3D histograms have less data to be compared, making image classification faster, than using entire 3D histograms. Combined images are more similar to original one (Fig. 9).

a b
Fig. 9, Multidimensional entropy image combined from 2D multistage entropy and 3D gradient entropy (a), and original image (b)

The most important in new model for complex multidimensional entropy based image segmentation is that we have more information for spatial image regions – objects and background, including information about the brightness gradient inside them. Because 3D image histograms can be interpreted in several ways; main diagonal homogeneity entropy, entire entropy and 3D histogram columns entropy, we can extract corresponding data for each one selected area inside 3D histogram space and finding corresponding objects inside grey scale image.

 

a b
Fig. 10, Image segmented using 2D entropy function (a) and 3D gradient entropy (b).

3D image entropy is a global histogram method producing homogenization effect, like statistical mode and median filtration. This method is not comprehensive. It can be used in several types of images: where we have constant background and many constant objects having similar brightness and shape. Improvements can be significant in images that have large amount of low pass and high pass noise, such as scanned documents (Fig. 10). In such cases noise can be classified in 2-3 classes. Using gradient 3D entropy function scanned documents pixels are simply divided in to 2 classes: background noise and object noise.

It is recommended to calculate 3D gradient entropy function for any grey level channel after 2D multistage entropy mask calculation. In these case each one grey level channel can be classified as a entropy defined maximum grey level + gradient entropy defined pixel to pixel gradient (deviation). In most cases this method lack his robustness in images having many different areas with different contrast, shapes, size - natural photos having large homogeneity areas and large gradient areas are not good for 3D gradient entropy analysis.

Video motion segmentation using 3D multistage entropy frames

3D multidimensional image entropy can help us to achieve better and faster digital video segmentation. Such segmentation is important for content based video post processing. A good example of statistical based motion detection is shown here. Using 2D and 3D multistage entropy images we can faster the process of motion detection simultaneously achieving object segmentation and statistical classification, see section 7. Multistage 2D entropy + 3D gradient entropy images can be used to improve results in algorithms that use statistical motion based visual scene indexing using 3D image histograms. In such cases it improves video segmentation (Fig. 11).

a
b
c
Fig. 11, Video motion segmentation using 3D histograms of original 8bit grey level frame sequence (a), corresponding 8 layer 3D entropy frame sequence (b), 8 layer 3D entropy frame sequence after frame 3D histogram homogenization.

3D multistage entropy frame sequence tend to blink in small information changes between 2 video frames (Fig. 12). We can avoid this negative effect using frame sequence 3D histogram homogenization (equalization). 2D histogram equalization do not provide such balancing effect.3D histogram equalization group joint pixels instead of single pixels like this is done in 2D histogram equalization.

Conclusion

In some simple cases when working with good filtered images we can use single stage 2D entropy function. For better region segmentation in more shaded images we can use multistage 2D entropy function. Even better spatial object segmentation can be achieved using global 3D entropy function and its multistage variant.

References

  • http://www.codeproject.com/useritems/Image_Histograms.asp

  • Tzvetkov, P.; Petrov, G.,Iliev, P. “Multidimensional dynamic scene analysis for video security applications” – IEEE Computer Science’2006 Istanbul

  • Iliev, P.; Tzvetkov, P.; Petrov, G., Motion Detection Using 3D Image Histograms Sequences Analysis IEEE Volume, Sept. 2005 Page(s):596 - 601

  • PUN. T. "A new method for grey level thresholding using the entropy of the histogram", Signal Processing, 1980, 2 pp. 223-237

  • Mark,L. G.,Althouse, "Target detection in multispectral images using the spectral co-occurrence matrix and entropy thresholding" Optical Engineering 34(7), 2135—2148 (July 1995)

 

 

© Copyright 2006 - 2007