HIERARCHICAL FAST 2-DIMENSIONAL ENTROPIC THRESHOLDING ALGORITHM USINGA HISTOGRAM PYRAMID

Entropic thresholding provides an alternative view to the design ratio nale of conventional thresholding. Abutaleb proposed a second-order en tropic thresholding approach to improve Pun's first-order entropic thr esholding by introducing a 2-D gray-level histogram to take into accou nt the spatial correlation. Abutaleb's (1989) method was further modif ied by Brink (1992). However, a major drawback of Abutaleb-Brink's met hod is very high computational cost. Recently, Chen et al. (1994) deve loped a fast efficient 2-D algorithm that reduces computational comple xity from O(L(4)) to O(L(8/3)), where L is the total number of gray le vels. A hierarchical fast 2-D entropic thresholding algorithm using a gray-level histogram pyramid is presented that can be viewed as a gene ralization of Chen et al.'s algorithm. The new algorithm consists of a 2-D gray-level histogram pyramid build-up procedure expanding Abutale b's 2-D gray-level histogram to a histogram pyramid, and a thresholdin g process applying a modified version of Chen et al.'s algorithm to th e histogram pyramid layer by layer from top to bottom. As a result, th e computational complexity of Chen et al.'s algorithm can be further r educed to the optimal complexity, O(L(2)). The experiments show that t he computer time of the new algorithm is only one tenth of that requir ed for Chen et al.'s algorithm, which is a significant saving. (C) 199 6 Society of Photo-Optical Instrumentation Engineers.