Fast incremental algorithm for speeding up the computation of binarization

作者：Chung Kuo Liang^*; Tsai Chia Lun

来源：Applied Mathematics and Computation, 2009, 212(2): 396-408.

DOI：10.1016/j.amc.2009.02.061

• Binarization
• Heap
• Incremental algorithm
• Kittler and Illingworth method
• Otsu method
• Quantization
• Within-variance

Binarization is an important basic operation in image processing community. Based on the thresholded value, the gray image can be segmented into a binary image, usually consisting of background and foreground. Given the histogram of input gray image, based on minimizing the within-variance (or maximizing the between-variance), the Otsu method can obtain a satisfactory binary image. In this paper, we first transfer the within-variance criterion into a new mathematical formulation, which is very suitable to be implemented in a fast incremental way, and it leads to the same thresholded value. Following our proposed incremental computation scheme, an efficient heap- and quantization-based (HQ-based) data structure is presented to realize its implementation. Under eight real gray images, experimental results show that our proposed HQ-based incremental algorithm for binarization has 36% execution-time improvement ratio in average when compared to the Otsu method. Besides this significant speedup, our proposed HQ-based incremental algorithm can also be applied to speed up the Kittler and Illingworth method for binarization.

• 出版日期2009-6-15