Adaptive Thresholding
Adaptive thresholding is an image segmentation algorithm that appears quite resistent to varying lighting conditions.
This recent paper attempts to summarize and compare various image thresholding algorithms/techniques.
Contents
Global Value Adaptive Thresholding
(useful for barrel-in-sunlight detection)
Below are various algorithms for auto-thresholding, that is, the process by which a threshold value on a histogram of a grayscale image is chosen automatically so as to fall in between the "foreground mound" and the "background mound" of the histogram. Once this threshold value is chosen, the "foreground" and "background" components of an image can be distinguished by comparing pixel values to the chosen threshold value.
Otsu Thresholding
A somewhat technical overview of the Otsu algorithm can be found in section 2 of this paper. The same paper additionally proposes a modified version of the Otsu algorithm in section 3 that it asserts is less computationally expensive than the traditional Otsu algorithm.
- "Otsu�s method chooses the optimal thresholds by maximizing the between-class variance with an exhaustive search."
- "The Sahoo et al. study on global thresholding, concluded that Otsu�s method was one of the better threshold selection methods for general real world images with regard to uniformity and shape measures. However, Otsu�s method uses an exhaustive search to evaluate the criterion for maximizing the between-class variance. As the number in classes of an image increases, Otsu�s method takes too much time to be practical for multilevel threshold selection."
Another paper's take on Otsu thresholding:
- Otsu�s method is an early, but still popular histogram-based global threshold algorithm. It proposed a criterion for maximising the variance of the between-class pixel intensities to perform thresholding. However, Otsu�s algorithm is very time-consuming for image binarisation because of its inefficient formulation of the between-class variance, and the performance varies with image types.
Ah ha! I've located the citation for Otsu's original paper:
- Otsu, N.: �A threshold selection method from grey level histogram�, IEEE Trans. Syst. Man Cybern., 1979, 9, (1), pp. 62 � 66
Links
- Sample Image Filter
- Original Source Code
- Cleaned up Source Code by David
Progress
I've been trying to analyze the source code of this image filter (not written by me) in order to figure out how the Otsu Thresholding algorithm works. I've had limited success, in that I have completely figured out how GrayLevelClass.java works. However I have not been able to decode OtsuThresholding.java which appears to contain the essential details specific to the Otsu algorithm. --David 21:14, 7 Nov 2005 (EST)
After several hours of work, I've finally decoded the Otsu algorithm! Not only that - I have written my own implementation of the algorithm which seems to produce good results when given sample images. To the right is a histogram augmented with a vertical red line indicating the thresholding level selected by the Otsu algorithm. In the near future I will incorporate the Otsu algorithm into the next ImageFilterDemo distribution. --David 16:01, 8 Nov 2005 (EST)
Implementation
I've implemented the Otsu algorithm in the OtsuThresholdingAlgorithm class, included with ImageFilterDemo v1.3.1. The GrayscaleLevelHistogram filter in ImageFilterDemo v1.3.2 uses this algorithm to calculate a threshold value which is displayed as a vertical red line on the output histogram. --David
Issues
- The Otsu algorithm is computationally expensive, according to a number of papers I have come across. Admittedly a number of these papers were written in the 1980s or earlier, but it is still a potential problem to keep in mind.
- The Otsu algorithm assumes (like many histogram-based algorithms) that its input histogram is bimodal. If, in fact, this is not the case - for example if the Otsu algorithm is applied to the unimodal histogram of an image that does not contain the object of interest (like orange/white construction barrels) - the algorithm will perform poorly.
- I have yet to resolve this issue but am actively researching a solution. --David 19:10, 9 Nov 2005 (EST)
Maximum Entropy Thresholding
Links
Once again, I've tried to analyze the source code of this image filter in order to figure how the algorithm its using works. --David 21:27, 7 Nov 2005 (EST)
Mixture Model Thresholding
Links
Other Thresholding Algorithms
- Binary Clustering
- Metric
- Moment-Preserving Thresholding
- "Moment preserving thresholding is a parametric method which segments the image based on the condition that the thresholded image has the same moments as the original image." - taken from [1]
- Inner-class Variance
- Pun Thresholding
- "In Pun�s method, as modified by Kapur et al., the picture threshold is found by maximizing the entropy of the histogram of gray levels of the resulting classes." - taken from [2]
Local Value Adaptive Thresholding
(useful for line-on-grass detection)
Other Thresholding Algorithms
- Niblack Thresholding
- Bernsen Thresholding
- Abutaleb Thresholding
- Sauvola Thresholding
- PirahanSiah Adaptive Single thresholding based on PSNR ( www.pirahansiah.com )
Unassessed Thresholding Algorithms
- Lloyd Thresholding
- Ridler-Calvard Thresholding // Iterative Selection Thresholding
- Johannsen Entropy Thresholding
- Yen, Chang Thresholding
- Sahoo, Wilkins, Yeager Thresholding // Renyi's Entropy Thresholding
- Triangle Thresholding
- Kittler-Illingworth Thresholding // Minimum Error Thresholding
- Kapur, Sahoo, Wong Thresholding
References
- A Fast Algorithm for Multilevel Thresholding
- Has a decent overview of the Otsu thresholding algorithm
- Proposes a more optimized version of the Otsu algorithm. From a quick skim of the new algorithm's description, it might be more memory intensive than the Otsu alogrithm (since extra lookup tables are involved).
- Decompose algorithm for thresholding degraded historical document images
- Has a very useful set of tables (on the third and fourth pages) that list the various common thresholding algorithms that have been developed since 2005.
- Proposes its own interesting thresholding algorithm that involves analyzing an image and then choosing one of the historical thresholding alogrithms to apply to it, based on the image's characteristics. (This algorithm would take way too long to implement, even though it is very good.)
- Otsu, N.: �A threshold selection method from grey level histogram�, IEEE Trans. Syst. Man Cybern., 1979, 9, (1), pp. 62 � 66
- Original article proposing the Otsu thresholding algorithm
