Click here to Skip to main content
Click here to Skip to main content

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

, 20 Sep 2007 CPOL
Rate this:
Please Sign up or sign in to vote.
Image processing using image histograms and entropy function.

Automatic Image Segmentation using 2D Multistage Entropy

Image grey level reduction and object segmentation

Screenshot - Image_HistogramsJPG.jpg

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.

Fig. 1 Simple 3x3 pixels image

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.

Screenshot - sample.JPG

Fig. 2 The same image represented by different spatial resolution

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..

Screenshot - histogram1.jpg

Fig. 3 Image histogram calculation and 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.

Screenshot - copter_rocket.jpg

Fig. 4 Image of helicopter launching a missile, image 2D histogram, image 2D entropy

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.

Screenshot - copter_rocket1.jpg

Fig. 5 Helicopter and its 2D histogram - top, helicopter after histogram equalization - down

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.

Screenshot - cell.jpg

Fig. 6 Using entropy maximum, we can calculate the adaptive grey level threshold for image object mask calculation

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.

Screenshot - copter_rocket2.jpg

Fig. 7 Original 8 bit image and its 2D histogram - top, image with reduced grey levels 2 bits and its 2D histogram (have only four histogram columns) - down

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 255th element of the image histogram. After this, we can reconstruct the corresponding grey level image regarding histogram substitution values. See Fig. 8.

Screenshot - copter_rocket3.jpg

Fig. 8 2 bit grey level image calculated with simple histogram segmentation - top/left and 2 bit image calculated using multistage entropy threshold - top/right; 4 bit grey level image calculated with simple histogram segmentation - down/left and 4 bit image calculated using multistage entropy threshold - down/right

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Georgi Petrov
Instructor / Trainer
Bulgaria Bulgaria
PhD, Cum Laude in digital automation systems
M.S. in Telemommunication management
B.S. in Telecommunication systems engineering
Programming: CUDA, C/C++, VHDL
Software and Hardware development and consulting:
data acquisition, image processing, medical instrumentation

Comments and Discussions

 
Generalread me Pinmembermohammed alshaweesh20-Dec-10 13:26 
QuestionStandard Deviation Pinmembertulipvn15-May-09 13:56 
AnswerRe: Standard Deviation PinmemberMr.AshokN28-Aug-09 2:14 
GeneralNot equal to MATLAB entropy calculation PinmemberHossein Margani14-May-09 23:50 
GeneralRe: Not equal to MATLAB entropy calculation PinmemberGeorgi Petrov17-Nov-10 10:32 
General:( Program execution failed PinmemberMember 31498531-Jul-08 1:09 
Generalconversion from rgb to greyscale using c programming Pinmemberg_vivian12-Dec-07 22:49 
GeneralEntropy PinmemberGeorgi Petrov28-Nov-06 0:32 
GeneralRe: Entropy Pinmembersamsamsam1-Feb-08 8:49 
GeneralRe: Entropy PinmemberGeorgi Petrov1-Feb-08 9:11 
GeneralRe: Entropy Pinmembersamsamsam1-Feb-08 19:24 
GeneralRe: Entropy PinmemberGeorgi Petrov4-Feb-08 8:16 
GeneralColor (RGB) to Grayscale Conversion PinmemberMicroImaging21-Aug-06 12:31 
GeneralRe: Color (RGB) to Grayscale Conversion PinmemberGeorgi Petrov21-Aug-06 21:26 
GeneralRe: Color (RGB) to Grayscale Conversion PinmemberMicroImaging22-Aug-06 5:46 
GeneralRe: Color (RGB) to Grayscale Conversion Pinmemberlola190030-Sep-07 4:47 
GeneralRe: Color (RGB) to Grayscale Conversion PinmemberGeorgi Petrov3-Oct-07 9:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141223.1 | Last Updated 20 Sep 2007
Article Copyright 2006 by Georgi Petrov
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid