Hierarchical fast two-dimensional entropic thresholding algorithm using a histogram pyramid

Abstract

Entropic thresholding provides an alternative view to the design rationale of conventional thresholding. Abutaleb proposed a second-order entropic thresholding approach to improve Pun’s first-order entropic thresholding by introducing a 2-D gray-level histogram to take into account the spatial correlation. Abutaleb’s (1989) method was further modified by Brink (1992). However, a major drawback of AbutalebBrink’s method is very high computational cost. Recently, Chen et al. (1994) developed a fast efficient 2-D algorithm that reduces computational complexity from O(L⁴) to O(L⁸/³), where L is the total number of gray levels. A hierarchical fast 2-D entropic thresholding algorithm using a gray-level histogram pyramid is presented that can be viewed as a generalization of Chen et al.’s algorithm. The new algorithm consists of a 2-D gray-level histogram pyramid build-up procedure expanding Abutaleb’s 2-D gray-level histogram to a histogram pyramid, and a thresholding process applying a modified version of Chen et al.’s algorithm to the histogram pyramid layer by layer from top to bottom. As a result, the computational complexity of Chen et al.’s algorithm can be further reduced to the optimal complexity, O(L²). The experiments show that the computer time of the new algorithm is only one tenth of that required for Chen et al.’s algorithm, which is a significant saving.