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




Sunday 26 December 2010

Image algorithms demo

At last an update to my blog! This has been a busy year for me with my work, I am now a developer in Helse Midt-Norge IT since May, earlier this year I worked as an independent consultant for Artsdatabanken (NTNU). I work with WPF and C# mainly presently.

I will now present a new hobby project of mine.

This WPF application demo of image algorithms demonstrates different techniques towards
blur, sharpen, edge detection and other filtering techniques, all relying on the general concept of Convolution in image processing. 8-bits level grayscale images (256 levels, 1 bpp) are supported.




I have worked with an image algorithms demo the last days. The
demo is a small WPF application that demonstrates image algorithms used in
edge detection. See the link below to download the zip file that contains
the Microsoft Visual Studio 2010 project with source code.

Examples of edge operators are sobel edge operator and Prewitt, Laplacian, Roberts and
Horizontal and Vertical Sobel, blur difference operator, shown above. There are additional
filters included.

The resulting images can be inverted. The application works with 8-bit grayscale images (256 levels). The BitmapSource class must be able to import the image (BMP or GIF should work).

Right now the demo is in v1.1. I will add more features soon. There are a few issues with double-edges, noise and normalization in the demo, but I hope I will complete the demo in a more stable version later. Feel free to unzip the zip file linked below and provide comments of the code. Perhaps you can add new features to my code and discuss optimizations, corrections?

I will state that already there is very little code to make a new filter, so this source code could be used as a basis for developing filters for applications needing to provide basic blur, sharpen and edge detection capabilities.



Sobel operator, horisontal komponent (3x3 convolution kernel).

Comment:

Download newest version of ImageAlgorithmsDemo WPF Application here [v1.1.]

Image algorithms v1.1 (Zip-fil, ca. 2,4 MB compressed)

Last update 28th of December 2010.

Future stuff:
  • improve the speed of the filtering
  • support greater than 8 bpp (e.g. RGB)
  • support more operators. Canny edge and more advanced filters are desired
  • improve code, add tests to the test project
  • even friendlier GUI, more feedback and information
  • document code
  • share code with the community when v2.0 is done.
The goal is that this demo should be a good starter demo of edge analysis in digital image algorithms, that can be used in courses at universities and the likes. The demo demonstrates pixel manipulation in WPF-application and filtering also with up to date .NET 4.0 code. Often one only finds C or C++ code when looking for these kinds of algorithms..

Comments?