Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.5, pp.713-727 (September 2001)

A Fast Algorithm for Multilevel Thresholding

Ping-Sung Liao, Tse-Sheng Chen* and Pau-Choo Chung+
Department of Electrical Engineering
ChengShiu Institute of Technology
Kaohsiung, 833 Taiwan
*Department of Engineering Science
National Cheng Kung University
Tainan, 701 Taiwan
Department of Electrical Engineering
National Cheng Kung University
Tainan, 701 Taiwan

Otsu reference proposed a criterion for maximizing the between-class variance of pixel intensity to perform picture thresholding. However, OtsuíŽs method for image segmentation is very time-consuming because of the inefficient formulation of the between-class variance. In this paper, a faster version of OtsuíŽs method is proposed for improving the efficiency of computation for the optimal thresholds of an image. First, a criterion for maximizing a modified between-class variance that is equivalent to the criterion of maximizing the usual between-class variance is proposed for image segmentation. Next, in accordance with the new criterion, a recursive algorithm is designed to efficiently find the optimal threshold. This procedure yields the same set of thresholds as the original method. In addition, the modified between-class variance can be pre-computed and stored in a look-up table. Our analysis of the new criterion clearly shows that it takes less computation to compute both the cumulative probability (zeroth order moment) and the mean (first order moment) of a class, and that determining the modified between-class variance by accessing a look-up table is quicker than that by performing mathematical arithmetic operations. For example, the experimental results of a five-level threshold selection show that our proposed method can reduce down the processing time from more than one hour by the conventional OtsuíŽs method to less than 107 seconds.

Keywords: OtsuíŽs thresholding, image segmentation, picture thresholding, multilevel thresholding, recursive algorithm

Full Text (ą■Ąň└╔) Retrieve PDF document (200109_01.pdf)

Received May 5, 1999; revised August 24, 1999; accepted December 30, 1999.
Communicated by Wen-Hsiang Tsai.