Otsu's method
In computer vision and image processing, Otsu's method, named after Nobuyuki Otsu (大津展之, Ōtsu Nobuyuki), is used to perform automatic image thresholding.
[1] In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes, foreground and background.
[2] 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[3] performed on the intensity histogram.
The extension to multi-level thresholding was described in the original paper,[2] and computationally efficient implementations have since been proposed.
Python libraries dedicated to image processing such as OpenCV and Scikit-image propose built-in implementations of the algorithm.
Otsu's method performs well when the histogram has a bimodal distribution with a deep and sharp valley between the two peaks.
[6] 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.
[7] In those cases, local adaptations of the Otsu method have been developed.
[9] Otsu's thresholding may however yield satisfying results even when these assumptions are not met, in the same way statistical tests (to which Otsu's method is heavily connected[10]) can perform correctly even when the working assumptions are not fully satisfied.
[11] A popular local adaptation is the two-dimensional Otsu's method, which performs better for the object segmentation task in noisy images.
[8] At each pixel, the average gray-level value of the neighborhood is calculated.
discrete values and the average gray level is also divided into the same
Then a pair is formed: the pixel gray level and the average of the neighborhood
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 The trace of the discrete matrix can be expressed as where Similar to one-dimensional Otsu's method, the optimal threshold
is obtained iteratively which is similar with one-dimensional Otsu's method.
, we can use a fast recursive dynamic programming algorithm to improve time performance.
[12] However, even with the dynamic programming approach, 2d Otsu's method still has large time complexity.
Note that if only coarse resolution is needed in terms of threshold, N_bins can be reduced.
When the levels of gray of the classes of the image can be considered as Normal distributions but with unequal size and/or unequal variances, assumptions for the Otsu algorithm are not met.
The Kittler-Illingworth algorithm (also known as Minimum Error thresholding)[11] is a variation of Otsu's method to handle such cases.
[9] One limitation of the Otsu’s method is that it cannot segment weak objects as the method searches for a single threshold to separate an image into two classes, namely, foreground and background, in one shot.
Because the Otsu’s method looks to segment an image with one threshold, it tends to bias toward the class with the large variance.
[14] Iterative triclass thresholding algorithm is a variation of the Otsu’s method to circumvent this limitation.
Then the algorithm tentatively separates the image into three classes (hence the name triclass), with the pixels above the upper mean
For the second iteration, the Otsu’s method is applied to the TBD region only to obtain a new threshold
Pixels in the TBD region that are greater than the upper mean
Similarly, a new TBD region is obtained, which contains all the pixels falling between
The algorithm then proceeds to the next iteration to process the new TBD region until it meets the stopping criterion.
In implementation, the algorithm involves no parameter except for the stopping criterion in terminating the iterations.
By iteratively applying the Otsu’s method and gradually shrinking the TBD region for segmentation, the algorithm can obtain a result that preserves weak objects better than the standard Otsu’s method does.
