## Tuesday, 28 December 2010

### 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()
{
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)
{
}
else
{
if (iteration > 0)
{
}
}
}
}
}

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