Adaptive Thresholding - Implementation of the Minimum Error Thresholding Method

Question

I'm trying to implement the following Minimum Error Thresholding (By J. Kittler and J. Illingworth) method in MATLAB.

You may have a look at the PDF:

• Scribd - Minimum Error Thresholding.
• DocDroid - Minimum Error Thresholding.

My code is:

function [ Level ] = MET( IMG )
%Maximum Error Thresholding By Kittler
%   Finding the Min of a cost function J in any possible thresholding. The
%   function output is the Optimal Thresholding.

for t = 0:255 % Assuming 8 bit image
    I1 = IMG;
    I1 = I1(I1 <= t);
    q1 = sum(hist(I1, 256));

    I2 = IMG;
    I2 = I2(I2 > t);
    q2 = sum(hist(I2, 256));

    % J is proportional to the Overlapping Area of the 2 assumed Gaussians
    J(t + 1) = 1 + 2 * (q1 * log(std(I1, 1)) + q2 * log(std(I2, 1)))...
        -2 * (q1 * log(q1) + q2 * log(q2));
end

[~, Level] = min(J);

%Level = (IMG <= Level);

end

I've tried it on the following image:

Original size image.

The target is to extract a binary image of the letters (Hebrew Letters). I applied the code on sub blocks of the image (40 x 40). Yet I got results which are inferior to K-Means Clustering method.

Did I miss something? Anyone has a better idea?

Thanks.

P.S. Would anyone add "Adaptive-Thresholding" to the subject tags (I can't as I'm new).

Answer 1

I think your code is not fully correct. You use the absolute histogram of the image instead of the relative histogram which is used in the paper. In addition, your code is rather inefficient as it computes two histograms per possible threshold. I implemented the algorithm myself. Maybe, someone can make use of it:

function [ optimalThreshold, J ] = kittlerMinimimErrorThresholding( img )
%KITTLERMINIMIMERRORTHRESHOLDING Compute an optimal image threshold.
%   Computes the Minimum Error Threshold as described in
%   
%   'J. Kittler and J. Illingworth, "Minimum Error Thresholding," Pattern
%   Recognition 19, 41-47 (1986)'.
%   
%   The image 'img' is expected to have integer values from 0 to 255.
%   'optimalThreshold' holds the found threshold. 'J' holds the values of
%   the criterion function.

%Initialize the criterion function
J = Inf * ones(255, 1);

%Compute the relative histogram
histogram = double(histc(img(:), 0:255)) / size(img(:), 1);

%Walk through every possible threshold. However, T is interpreted
%differently than in the paper. It is interpreted as the lower boundary of
%the second class of pixels rather than the upper boundary of the first
%class. That is, an intensity of value T is treated as being in the same
%class as higher intensities rather than lower intensities.
for T = 1:255

    %Split the hostogram at the threshold T.
    histogram1 = histogram(1:T);
    histogram2 = histogram((T+1):end);

    %Compute the number of pixels in the two classes.
    P1 = sum(histogram1);
    P2 = sum(histogram2);

    %Only continue if both classes contain at least one pixel.
    if (P1 > 0) && (P2 > 0)

        %Compute the standard deviations of the classes.
        mean1 = sum(histogram1 .* (1:T)') / P1;
        mean2 = sum(histogram2 .* (1:(256-T))') / P2;
        sigma1 = sqrt(sum(histogram1 .* (((1:T)' - mean1) .^2) ) / P1);
        sigma2 = sqrt(sum(histogram2 .* (((1:(256-T))' - mean2) .^2) ) / P2);

        %Only compute the criterion function if both classes contain at
        %least two intensity values.
        if (sigma1 > 0) && (sigma2 > 0)

            %Compute the criterion function.
            J(T) = 1 + 2 * (P1 * log(sigma1) + P2 * log(sigma2)) ...
                     - 2 * (P1 * log(P1) + P2 * log(P2));

        end
    end

end

%Find the minimum of J.
[~, optimalThreshold] = min(J);
optimalThreshold = optimalThreshold - 0.5;

Answer 2

Thresholding is a rather tricky business. In the many years I've been thresholding images I have not found one single technique that always performs well, and I have come to distrust the claims of universally excellent performance in CS journals.

The maximum error thresholding method only works on nicely bimodal histogram (but it works well on those). Your image looks like signal and background may not be clearly separated enough for this thresholding method to work.

If you want to make sure that the code works fine, you could create a test program like this and check both whether you get good initial segmentation, as well as at what level of 'bimodality' the code breaks down.