Friday 31 December 2010

Histogram equalization

I have added histogram equalization to the Image Algorithms demo. This method scans through an image, inspecting each pixel and creates a histogram. If a pixel p_q of grayscale intensity g_q is found at location (x,y), the Histogram H is incremented at position g_q for all grayscale levels L = 0 .. G-1, where G = 256 for grayscale images. A cumulative histogram is then calculated and the resulting pixel value is the ratio between the cumulative histogram and the total amounts of pixels in the image multiplied with G - 1.

More formally.

ALGORITHM - Histogram equalization.

1. For an NxM image of G gray levels, create an array H (histogram) of length G initialized with default intensity value 0.

2. Form the image histogram. Scan every pixel and increment relevant position in the histogram H. If pixel p has intensity g_p, perform:
H[g_p] = H[g_p + 1.

3. Form the cumulative image histogram H_c. Set:
H_c[0] = H[0]
H_c[p] = H_c[p-1] + H[p] for all pixel intensities p where p = 0,1,2... G-1

4. Rescan the image and calculate the corrected intensity, which it output.
Let T[p] = round(((G-1)/(N*M)) * H_c[p]. For a pixel of intensity p in the image
at position x,y, use T[p] to find the correct adjusted value.

5. Display image results.

END.


Note about step 4. Use the (double) cast when doing the math.. In general, histogram equalization is all about creating a Histogram of an image, then form a cumulative histogram, and then use the ratio between the total amount of pixels N*M and multiply with the cumulative histogram H_c[p] and then multiply with (G-1), usually 255.. This will set the most luminous pixels in the image near full intensity, will the less luminous pixels towards zero intensity, increasing the dynamic range and contrast in the image.


Note about the demo, I have added also Hough transform (tested some basic images) and
filters for displaying histogram of the histogram equalization. Test them out. Hough transform shown the sinusoidal images in the parameter space and should be considered as not finished code.

A demonstration follows.



This is equalized to:



Download the demo here:
Image algorithms demo [2,7 Mb zip]

To summarize, to understand histogram equalization is to consider the cumulative histogram and scale this with the ratio with the total amount of pixels multiplied with 255 (G-1).. The result is that the brightest pixels are moved towards full intensity 255 and the darkest pixels are moved towards 0, increasing the contras and dynamic range.

Wednesday 29 December 2010

Test out iterative optimal treshold algorithm on images?

Merry Xmas




Image algorithms demo [2,6 MB zip]

Iterative optimal tresholding







I have tested out and implemented another filter in my image algorithms demo. I follow the Iterative (optimal) treshold selection algorithm from the "Image Processing, Analysis and Machine Vision" book from my Computer Vision course, which I took when studying to my Master of Science (Siv. ing datateknikk) degree at NTNU, Trondheim. It is a simple algorithm, consisting of these steps.

ALGORITHM - Iterative optimal tresholding.

GOAL: Separate an image into two regions, background and foreground.
DEFINITIONS: Background is pixels
which got intensity below the current treshold, calculated in the algorithm's iterations. Foreground pixels got intensity above the current treshold.

STEPS:
1.Calculate the initial average of the current treshold value. Set this value to the

average of the four corner pixels average value.
2. Traverse the image. If a pixel is above the current treshold value, it is added to the sum of object pixels
(foreground pixels). Incremement the count of foreground pixels. Also, vice versa for the background pixels. Add to the sum of background pixels and increment the background pixels if the pixel's intensity is below the treshold value.

3. Calculate the average of the background average and object (foreground average) and set this to the next treshold value.

4. If not the next treshold is the same as current treshold, iterate the image again, but now set current treshold to next treshold. When the next and current treshold is same, the treshold calculated is the optimal treshold value. End iteration or break at 100 iterations.

5. After calculation is complete, display result. Set the object pixels to full pixel intensity (255). Background
pixels are set to 0, creating a binary image showing foreground and background.

It took five iterations to calculate the iterative optimal treshold value for the infamous Lenna image, calculated to be 162 in pixel intensity. For an average picture one would expect the value to be above 140 - 180, if the picture is grayscale image with good contrast.
Result:





IMPLEMENTATION - OptimalTresholdFilter.cs 




using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ImageAlgorithms.Filters.Treshold
{
public class OptimalTresholdFilter : ImageFilterBase
{

int objectPixelSum = 0;
int backgroundPixelSum = 0;
int currentTresholdValue = 0;
int nextTresholdValue = 0;
int objectPixelsCount = 0;
int backgroundPixelCount = 0;

public OptimalTresholdFilter()
{
Header = "Optimal treshold filter";
FilterType = FilterTypeEnum.TresholdFilter;
}

public override void FilterProcessImage(int width, int height)
{
//base.FilterProcessImage(width, height);

//Read first four pixels (edges of image)
//Calculate the average of object pixels and background pixels
//Let avg+1 = average of background pixels and object pixels
//if avg+1 and avg is the same, stop, else continue.
CalculateAverage(width, height, 0);
DisplayTresholdImage(width, height);
}

private void DisplayTresholdImage(int width, int height)
{
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
int position = (j*width) + i;
if (TemporaryImageData[i, j] > nextTresholdValue)
{
ResultingImageData[position] = 255;
}
else
{
ResultingImageData[position] = 0;
}
}
}

}

private void CalculateAverage(int width, int height, int iteration)
{
InitFilterIteration();
CheckInitialStep(width, height, iteration);
TraverseImageBackgroundForeground(width, height, iteration);
CheckPixelCounts();
CalculateNextTreshold();
if (nextTresholdValue != currentTresholdValue && iteration < 100)
{
currentTresholdValue = nextTresholdValue;
CalculateAverage(width, height, iteration + 1);
}
}

private void CalculateNextTreshold()
{
nextTresholdValue = ((objectPixelSum / objectPixelsCount) +
(backgroundPixelSum / backgroundPixelCount)) / 2;
}

private void TraverseImageBackgroundForeground(int width, int height, int iteration)
{
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if (TemporaryImageData[i, j] > currentTresholdValue)
{
AddToObjectPixels(i, j);
}
else
{
if (iteration > 0)
{
AddToBackgroundPixels(i, j);
}
}
}
}
}

private void AddToBackgroundPixels(int i, int j)
{
backgroundPixelSum += TemporaryImageData[i, j];
backgroundPixelCount++;
}

private void AddToObjectPixels(int i, int j)
{
objectPixelSum += TemporaryImageData[i, j];
objectPixelsCount++;
}

private void CheckInitialStep(int width, int height, int iteration)
{
if (iteration == 0)
{
backgroundPixelSum = (TemporaryImageData[0, 0] + TemporaryImageData[width - 1, 0] +
TemporaryImageData[0, height - 1] +
TemporaryImageData[width - 1, height - 1]);
backgroundPixelCount = 4;
currentTresholdValue = backgroundPixelSum / backgroundPixelCount;
}
}

private void CheckPixelCounts()
{
objectPixelsCount = Math.Max(1, objectPixelsCount);
backgroundPixelCount = Math.Max(1, backgroundPixelCount);
}

private void InitFilterIteration()
{
backgroundPixelCount = 0;
objectPixelsCount = 0;
backgroundPixelSum = 0;
objectPixelSum = 0;
}
}
}



Download the latest version of the algorithms demo (v1.1.) to test out the optimal treshold filter. As you can see in the code above, the class inherits from ImageFilterBase, which handles some of the "logistics" around the image filter (loading the filter and showing the result).