Source-linked AI summary
A New Local Adaptive Thresholding Technique in Binarization
T. Romen Singh, Sudipta Roy, O. Imocha Singh, Tejmani Sinam, Kh. Manglem Singh
TL;DR
Degraded document images make foreground–background classification difficult, motivating local adaptive thresholding despite its computational cost. The paper introduces an integral-sum-image method using local mean and mean deviation, reporting better quality and speed than contemporary methods.
Problem
Degraded documents contain background noise or contrast and illumination variation that make foreground–background classification difficult for global thresholding.
Method
The proposed technique computes local thresholds from an integral sum image, local mean, and mean deviation without calculating local standard deviation.
Results
The proposed method is reported to be faster than Sauvola’s method, with running time approaching global binarization, and better than contemporary methods in quality and speed.
Takeaways & Limitations
Integral-sum-image preprocessing makes local-mean computation independent of window dimension, while the method performs well even at very small window sizes.
Takeaways & Limitations
The threshold formulation assumes that the local window size w is odd.
Abstract
from arXiv · showhide
Image binarization is the process of separation of pixel values into two groups, white as background and black as foreground. Thresholding plays a major in binarization of images. Thresholding can be categorized into global thresholding and local thresholding. In images with uniform contrast distribution of background and foreground like document images, global thresholding is more appropriate. In degraded document images, where considerable background noise or variation in contrast and illumination exists, there exists many pixels that cannot be easily classified as foreground or background. In such cases, binarization with local thresholding is more appropriate. This paper describes a locally adaptive thresholding technique that removes background by using local mean and mean deviation. Normally the local mean computational time depends on the window size. Our technique uses integral sum image as a prior processing to calculate local mean. It does not involve calculations of standard deviations as in other local adaptive techniques. This along with the fact that calculations of mean is independent of window size speed up the process as compared to other local thresholding techniques.
1. Introduction
Document binarization converts grayscale or color documents into a bi-level representation that separates text or other foreground objects from the background. Global methods use one threshold for the document, whereas local adaptive methods compute thresholds from each pixel’s neighborhood and are better suited to degraded documents but often slower.
- Document binarization: Document binarization converts input grayscale or color documents into a bi-level representation separating foreground text from the background.The representation commonly uses black for text and white for paper.
- Global and local thresholding: Global binarization methods find a single threshold value for the whole document and are fast for typical scanned documents.Each pixel is assigned to page foreground or background according to its gray value.
- Global and local thresholding: Local binarization methods compute thresholds individually for each pixel using information from its local neighborhood.They are intended to address variation in document appearance that global thresholding cannot handle as well.
- Global and local thresholding: Local methods can achieve good results on severely degraded documents but are often slow because neighborhood features are computed for every pixel.The paper targets this speed limitation with integral-sum-based local mean computation.
2. Integral Sum Image
An integral sum image stores cumulative pixel intensities so local window sums can be recovered efficiently. This enables local means to be computed in a single pass with runtime independent of window size.
- Integral sum image: An integral sum image stores at each pixel the sum of intensities of all input pixels above and to the left.The paper uses this cumulative representation as a prior process for local-window calculations.
- Integral sum image: The integral sum image of a grayscale image can be computed efficiently in a single pass using boundary recurrences and an interior recurrence.The interior calculation combines neighboring integral values with the current image intensity.
- Local window sums: The local sum of a w×w window can be computed from the integral image using two additions and one subtraction, without depending on window size.This replaces direct accumulation over all pixels in the window.
- Local window sums: The window half-width is defined as c=(w−1)/2 under the assumption that w is odd.The method uses d=round(w/2) when retrieving local sums from the integral image.
- Local mean: The local arithmetic mean m(x,y) is the average of pixels within the w×w window and can be obtained from the local sum.The paper states that this calculation is efficient in a single pass using the integral sum image.
3. Locally Adaptive Thresholding
Locally adaptive thresholding computes a separate threshold from neighborhood statistics, helping address document regions with varying contrast. Representative methods use local mean with standard deviation or local gray-range information, but these calculations can be computationally expensive.
- Local adaptive methods calculate a threshold for each pixel from statistics in its neighborhood.These statistics can include range, variance, or surface-fitting parameters.
- Local variance methods: Niblack and Sauvola methods use the local mean and standard deviation within a w×w window.Sauvola improves on Niblack particularly for stained and badly illuminated documents.
- Niblack’s Technique: Niblack’s threshold combines local mean, standard deviation, and bias k, with satisfactory results reported at k = -0.2 and w=15.The bias controls the adaptation level of the threshold.
- Sauvola’s Technique: Sauvola’s method uses local mean, standard deviation, maximum standard deviation R, and a positive bias k in [0.2, 0.5].Its threshold approaches the local mean in high-contrast regions and falls below the mean in low-contrast regions.
- Sauvola’s Technique: Naively computing local mean and standard deviation for every pixel has computational complexity O(n^2w^2) for an n×n image.The method is described as producing good results even for severely degraded documents, but its per-pixel statistics are costly.
- Local gray range method: Bernsen’s technique sets the threshold to the midpoint of the local maximum and minimum gray values.With contrast below 15, the neighborhood is treated as one foreground or background class; w =31 is reported as satisfactory.
4. Proposed Technique
The proposed technique accelerates local thresholding by using an integral sum image to compute local means independently of window size and by replacing standard deviation with mean deviation. The paper reports faster binarization than other methods.
- Proposed threshold: The proposed threshold uses local mean and mean deviation instead of local standard deviation.The mean deviation is defined as ∂(x,y)=I(x,y) - m(x,y), and bias k controls adaptation within [0,1].
- Threshold adaptation: Lower k raises the threshold, whereas higher k lowers it; in a uniform region, the threshold falls below the mean and the pixel becomes background.The paper states that k adjusts the threshold adaptation level for different scanned image types.
- Efficient computation: An integral sum image allows local sums and means to be computed without dependence on the local window dimension.The integral sum image is determined before local threshold calculation, while mean deviation follows by subtracting the mean from the concerned pixel.
- Results: The proposed technique can binarize faster than other methods.The paper attributes this to integral-sum computation of the local mean and omission of local standard deviation.
5. Experimental Result
The proposed binarization technique was evaluated qualitatively and quantitatively against other relevant methods on document and non-document images. Results emphasize comparative performance across methods and window sizes.
- Experiments used MATLAB 7.3 on a 2.33 GHz Intel Core 2 Duo PC with 2 GB RAM and a 32-bit Windows Vista system.
- The evaluation compared the proposed method with Sauvola’s, Niblack’s, and Bernsen’s methods across coin, scanned-document, text-document, nondocument, and large-text images.Figures 4–8 report these visual comparisons under different parameter and window-size settings.
- Sauvola’s method was previously reported as best on nondocument images but poorer on document images.
- Niblack’s and Bernsen’s methods require large windows, whereas the proposed method and Sauvola’s method give good results at smaller windows such as 5×5.For document images, the window size must vary with character size; otherwise large characters may yield only character boundaries.
6. Conclusions
The paper introduces a locally adaptive threshold computation using integral sum images. It reports lower runtime than Sauvola’s method and better quality and speed than contemporary methods.
- The proposed method computes local means with an integral sum image, making runtime independent of local window size.The paper reports that the method is faster than Sauvola’s and approaches global binarization speed.