Decomposition based two-dimensional threshold algorithm for gray images

As a generalization of ID Otsu algorithm, 2D Otsu algorithm considers both the gray value of a pixel and the average gray value of its neighborhood, thus is more robust to noise. By constructing look-up tables recursively, its fast algorithm reduces its complexity from O(L4) to O(L2). Based on the decomposition of 2D Otsu algorithm, a method of calculating the optimal threshold of two ID Otsu algorithms independently, instead of the optimal threshold of 2D Otsu algorithm, is proposed. When the hypothesis of original 2D Otsu algorithm holds, we point out that the threshold computed by our method is exactly the same as that of 2D Otsu algorithm, while the computational complexity is reduced to O(L). As for real images, the hypothesis of 2D Otsu algorithm always fails, whereas experimental results show that the proposed threshold algorithm still outperforms original 2D Otsu algorithm. Without losing the robustness to noise, this method needs less time and space, and produces a comparable or better segmentation result. © 2009 Acta Automatica Sinica. All rights reserved.