In
computer vision and
image processing, Otsu's method, named after , is used to perform automatic image
thresholding.
In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes, foreground and background. This threshold is determined by minimizing intra-class intensity variance, or equivalently, by maximizing inter-class variance.
Otsu's method is a one-dimensional discrete analogue of
Fisher's Discriminant Analysis, is related to
Jenks optimization method, and is equivalent to a globally optimal
k-means
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers o ...
performed on the intensity histogram. The extension to multi-level thresholding was described in the original paper,
and computationally efficient implementations have since been proposed.
Otsu's method
![Otsu's Method Visualization](https://upload.wikimedia.org/wikipedia/commons/3/34/Otsu%27s_Method_Visualization.gif)
The algorithm exhaustively searches for the threshold that minimizes the intra-class variance, defined as a weighted sum of variances of the two classes:
:
Weights
and
are the probabilities of the two classes separated by a threshold
,and
and
are variances of these two classes.
The class probability
is computed from the
bins of the histogram:
:
For 2 classes, minimizing the intra-class variance is equivalent to maximizing inter-class variance:
[
:
which is expressed in terms of class probabilities and class means , where the class means , and are:
:
The following relations can be easily verified:
:
The class probabilities and class means can be computed iteratively. This idea
yields an effective algorithm.
]
Algorithm
# Compute histogram and probabilities of each intensity level
# Set up initial and
# Step through all possible thresholds maximum intensity
## Update and
## Compute
# Desired threshold corresponds to the maximum
MATLAB implementation
histogramCounts
is a 256-element histogram of a grayscale image different gray-levels (typical for 8-bit images).
level
is the threshold for the image (double).
function level = otsu(histogramCounts)
total = sum(histogramCounts); % total number of pixels in the image
%% OTSU automatic thresholding
top = 256;
sumB = 0;
wB = 0;
maximum = 0.0;
sum1 = dot(0:top-1, histogramCounts);
for ii = 1:top
wF = total - wB;
if wB > 0 && wF > 0
mF = (sum1 - sumB) / wF;
val = wB * wF * ((sumB / wB) - mF) * ((sumB / wB) - mF);
if ( val >= maximum )
level = ii;
maximum = val;
end
end
wB = wB + histogramCounts(ii);
sumB = sumB + (ii-1) * histogramCounts(ii);
end
end
Matlab has built-in functions graythresh()
and multithresh()
in the Image Processing Toolbox which are implemented with Otsu's method and Multi Otsu's method, respectively.
Python implementation
This implementation requires the NumPy library.
import numpy as np
def compute_otsu_criteria(im, th):
# create the thresholded image
thresholded_im = np.zeros(im.shape)
thresholded_im = th">m >= th= 1
# compute weights
nb_pixels = im.size
nb_pixels1 = np.count_nonzero(thresholded_im)
weight1 = nb_pixels1 / nb_pixels
weight0 = 1 - weight1
# if one the classes is empty, eg all pixels are below or above the threshold, that threshold will not be considered
# in the search for the best threshold
if weight1 0 or weight0 0:
return np.inf
# find all pixels belonging to each class
val_pixels1 = im 1">hresholded_im 1 val_pixels0 = im 0">hresholded_im 0
# compute variance of these classes
var0 = np.var(val_pixels0) if len(val_pixels0) > 0 else 0
var1 = np.var(val_pixels1) if len(val_pixels1) > 0 else 0
return weight0 * var0 + weight1 * var1
im = # load your image as a numpy array.
# For testing purposes, one can use for example im = np.random.randint(0,255, size = (50,50))
# testing all thresholds from 0 to the maximum of the image
threshold_range = range(np.max(im)+1)
criterias = ompute_otsu_criteria(im, th) for th in threshold_range
# best threshold is the one minimizing the Otsu criteria
best_threshold = threshold_range p.argmin(criterias)
Python libraries dedicated to image processing such as OpenCV
OpenCV (''Open Source Computer Vision Library'') is a library of programming functions mainly aimed at real-time computer vision. Originally developed by Intel, it was later supported by Willow Garage then Itseez (which was later acquired by In ...
and Scikit-image
scikit-image (formerly scikits.image) is an open-source image processing library for the Python programming language.
It includes algorithms for segmentation, geometric transformations, color space manipulation, analysis, filtering, morphology, ...
propose built-in implementations of the algorithm.
Limitations and variations
Otsu's method performs well when the histogram has a bimodal distribution with a deep and sharp valley between the two peaks.
Like all other global thresholding methods, Otsu's method performs badly in case of heavy noise, small objects size, inhomogeneous lighting and larger intra-class than inter-class variance. In those cases, local adaptations of the Otsu method have been developed.
Moreover, the mathematical grounding of Otsu's method models the histogram of the image as a mixture of two Normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu ...
s with equal variance and equal size. Otsu's thresholding may however yield satisfying results even when these assumptions are not met, in the same way statistical test
A statistical hypothesis test is a method of statistical inference used to decide whether the data at hand sufficiently support a particular hypothesis.
Hypothesis testing allows us to make probabilistic statements about population parameters.
...
s (to which Otsu's method is heavily connected) can perform correctly even when the working assumptions are not fully satisfied. However, several variations of Otsu's methods have been proposed to account for more severe deviations from these assumptions, such as the Kittler-Illingworth method.
A variation for noisy images
A popular local adaptation is the two-dimensional Otsu's method, which performs better for the object segmentation task in noisy images. Here, the intensity value of a given pixel is compared with the average intensity of its immediate neighborhood to improve segmentation results.
At each pixel, the average gray-level value of the neighborhood is calculated. Let the gray level of the given pixel be divided into discrete values and the average gray level is also divided into the same values. Then a pair is formed: the pixel gray level and the average of the neighborhood . Each pair belongs to one of the possible 2-dimensional bins. The total number of occurrences (frequency), , of a pair , divided by the total number of pixels in the image , defines the joint probability mass function in a 2-dimensional histogram:
:
And the 2-dimensional Otsu's method is developed based on the 2-dimensional histogram as follows.
The probabilities of two classes can be denoted as:
:
The intensity mean value vectors of two classes and total mean vector can be expressed as follows:
:
In most cases the probability off-diagonal will be negligible, so it is easy to verify:
:
:
The inter-class discrete matrix is defined as
: