2D and 3D image histograms and 2D multistage entropy

• Download demo project and code - 108 KB
• Download test images - 1.56 MB

Automatic Image Segmentation using 2D Multistage Entropy

This software supports bitmaps and JPEGs. You can open such files and can see their 2D histograms and entropy functions; you can threshold images in 2, 4, and 8 grey scale levels. You can try different image processing functions like histogram equalization, entropy maximum and entropy multistage maximum calculation, 3D histogram calculation, and 3D histogram equalization. You can save the processed images and you can save the calculated 2D histograms and 3D histogram functions in txt files so you can open them in MathCAD or Excel. This version supports loading and processing AVI files. Note that AVI processing takes a lot of time; be sure to test the application on AVI files that have 100-300 frames.

Definitions

Digital images are discrete representations of an analogous nature. Like conventional photographic images, most of them have a rectangular form. Each image consists of many small building blocks called pixels. Pixels are situated inside two dimensional image matrixes like in Fig. 1. Each pixel represents a different light value. In color images, colors are represented using an RGB color model. RGB images have three separate matrixes where each red, green, and blue light intensity values for each pixel are stored. There are several color representation models, but RGB is the most convenient for digital computers. In this article, I will cover topics regarding grey level images. The same algorithms can be used when dealing with color images but calculations need to be done for RGB components separately. Color image processing is more complex, and can be properly done in conjunction with grey level image processing.

Where "X" and "Y" are image dimensions, or simply the number of pixel columns and rows. Larger values of "X" and "Y" will lead to better spatial resolution. Spatial resolution is a parameter that shows how many pixels are used to represent a real object in digital form. Fig. 2 shows the same color image represented by a different spatial resolution. The left flower has a much better resolution than the right one. Having a large number of pixels will help us calculate a more representative histogram.

Histogram is a statistical representation of different image pixel frequencies inside an image. In our case, a 2D histogram will represent the corresponding number of pixels that have different light levels. Simply said, an image histogram can show how many pixels with an exact light intensity are met in the original image. Because our image can vary in size, we will use a one dimensional integer array to store histogram values. All examples here will be for grey level images. These calculations can be used for color images, but each color space matrix must be processed separately as a grey level image histogram. 2D Histogram calculation is easy, we just make a loop inside the image pixels and index a 256 element integer array:

for(int i=0; i<y; i++)
{
    for(int j=0;j<x; j++)
    {
        HiGrey[Grey[i,j]] ++;
    }
}

• y is the image height, and x is the image width.
• Grey[i,j] is a byte array that holds information about the 2D image brightness.
• HiGrey[i] is a 256 element integer array that holds the 2D image histogram.

2D Image Histogram Normalization

Now we have the 2D image histogram stored in a 256 element integer array. This type of representation is not very convenient and is not suitable for statistical calculations. There is another form of histogram representation, called normalized histogram. A normalized histogram shows the probability distribution of different pixel values. The process of normalization is very simple; all we need to do is divide each histogram 256 array element by the total number of pixels inside an image. To have a better understanding of this, suppose we have a 3x3=9 pixel image as in Fig. 1. Fig. 3 represents the histogram calculation and histogram normalization..

for(int i=0; i<256; i++)
{
    HiGrey[i]/(x*y) ++;
}

2D Image Histogram Equalization and Entropy Function

After having the image histogram calculated and normalized, we can calculate the 2D image histogram entropy function, see Fig. 4.

Histogram equalization is a simple process of grouping all small histogram columns into one. After this grouping, we need to make image pixel substitution regarding histogram changes. To do 2D histogram equalization, we need to calculate the histogram mean value. After this, we make a loop and check all the histogram columns from position 0 to 255 and if the current histogram column is smaller than the global histogram mean value, we exceed the mean value. If this is the case, we jump to the next column and treat its value. All positions that we add are marked as grey level substitution candidates. If the next column has a value larger than the mean, we jump to the next column without adding its value to the first one. See Fig. 5.

//Calculate Entropy of 2D histogram
double Sum_prob_1k = 0, Sum_prob_kl = 0, Sum_prob_ln_1k = 0, Sum_prob_ln_kl = 0;
for (int k = start; k < end; k++)
{
    Sum_prob_1k = 0; Sum_prob_kl = 0;
    Sum_prob_ln_1k = 0; Sum_prob_ln_kl = 0;
    //i=1 need to be start = 1
    for (int i = 1; i < k; i++)
    {
        Sum_prob_1k += HiGreyN[i];
        if (HiGreyN[i] != 0)
            Sum_prob_ln_1k += (HiGreyN[i] * System.Math.Log(HiGreyN[i]));
    }
    for (int i = k; i < end; i++)
    {
        Sum_prob_kl += HiGreyN[i];
        if (HiGreyN[i] != 0)
            Sum_prob_ln_kl += (HiGreyN[i] * System.Math.Log(HiGreyN[i]));
    }
    //Final equation of entropy for each K
    EiGrey[k] = System.Math.Log(Sum_prob_1k) + System.Math.Log(Sum_prob_kl) -
               (Sum_prob_ln_1k / Sum_prob_1k) - (Sum_prob_ln_kl / Sum_prob_kl);
    if (EiGrey[k] < 0)
        EiGrey[k] = 0;
}
//End calculating 2D Entropy

After completing this function, the image entropy is held inside a 2D 256 element double precision array EiGrey[k]. start and stop are integer values that determine the part of the 256 element array where we need to calculate the entropy. If start=0 and end=256, we calculate the entropy of the entire 2D image histogram; if we use different values between 0-256, we can calculate the entropy of the dedicated 2D histogram segment.

Image entropy of the 2D image histogram shows the "chaos" inside the image. The calculation of this function is a complex procedure that measures each 2D histogram column probability corresponding to the total information inside all other pixels. This function is used to determine which pixels wear most of the information content inside an image. This function is used for automatic image threshold and for image object segmentation. After calculating the 2D image histogram entropy function, we can select the entropy maximum and use the maximum position as a threshold for image quantization. Such an approach is used in automatic biomedical cell counting systems. See Fig. 6.

This approach for object segmentation can be well used for images that have a constant background and non-moving objects. In the case of the flying helicopter in Fig. 4, we need a different approach. Because the helicopter, missile, and background are very different and change in time, we need a more complex approach for object segmentation. A simpler approach is to reduce the total amount of grey levels. Because our original image is 8 bit per pixel, we can try to reduce it to 2 or 3 bit per pixel. This can be done using re-quantization of the original image. Using a simple division of each pixel will not provide us good results. See Fig. 7.

As we can see, dividing the image histogram in to four equal zones does not provide us with good information about the objects inside an image. This can be significantly improved if we incorporate entropy based image histogram segmentation. We need to divide the image histogram several times using entropy maximum calculation over selected areas inside a histogram. Once we calculate the first entropy maximum, we calculate the entropy maximum between 0 and the first maximum position. After this, we calculate the entropy maximum position between the first maximum and the 255^th element of the image histogram. After this, we can reconstruct the corresponding grey level image regarding histogram substitution values. See Fig. 8.

Conclusions

Here I provided you with practical examples of how we can use multistage entropy for information reduction in BW digital images. Using a 2D image histogram entropy function, we can create images that are ready for object based segmentation and analysis. 2D entropy threshold is important for the autoimmunization of the image segmentation process. In the next article, I'll cover 3D image histogram and entropy calculation.

References

• http://www.instrumentation.hit.bg/Papers/2007-08-17%202D%20Multistage%20Entropy.htm
• Color Models: http://www.colorcube.com/articles/basics/basics.htm
• http://www.sphoto.com/techinfo/histograms/histograms.htm
• http://www.cambridgeincolour.com/tutorials/histograms1.htm
• Image Entropy: http://people.csail.mit.edu/msabuncu/Spatial_info.pdf
• http://www.nbu.bg/PUBLIC/IMAGES/File/departments/telecommunication/research/37.pdf
• http://www.nbu.bg/PUBLIC/IMAGES/File/departments/telecommunication/research/3.pdf