Automatic Image Segmentation using 2D Multistage Entropy
Image grey level reduction and object segmentation
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.
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..
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.
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.
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;
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]));
}
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;
}
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.
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.
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.
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.
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
