Constant-time locally optimal adaptive binarization

Scanned document images are nowadays becoming available in increasingly higher resolutions. Meanwhile, the variations in image quality within typical document collections increase due to images coming from different scan service providers, time periods or digitization methods. Binarization is a crucial first step for many document analysis algorithms. Adaptive thresholding algorithms have been shown to perform well on degraded documents, however their speed is orders of magnitude slower than that of global algorithms and they generally require manual fine-tuning of parameters for producing good results. This paper proposes a generic constant-time adaptive binarization algorithm, along with a constant-time method for automatically determining good window sizes for adaptive algorithms working on document images. Tests demonstrate a significant speedup compared to a straightforward implementation. Visual assessment of the results shows that the proposed method compares favorably with two well-known binarization techniques, and is especially suited for documents containing overexposed areas.