Global Thresholding Image Segmentation Techniques

Abstract

Image thresholding is used to provide a representation of an image in a simplest form which requires less space. This representation is called segmented image and the process is image segmentation.  This paper presents an extensive review of global thresholding techniques for image segmentation. It includes the various methods used for global threshold selection of grey level images. In this survey, global thresholding methods are divided into two categories: histogram modification and methods that computes threshold. The study found that the histogram improvement methods are sensitive to noise whereas threshold computing methods are robust to noise and give effective results. The threshold computing method includes the review of Otsu and Entropic method. Both of these methods are well known global thresholding methods.

Introduction

To understand an image, it has to be divided into different meaningful parts called objects which can be easily identified and depicts some information. This division process is called image segmentation and thresholding is one of the popular techniques for image segmentation. It has low computational cost when compared to other algorithms Image thresholding works on the principle of pixel classification. It divides an image into segments depending upon the pixel attributes. This techniques applies on each pixel and by comparing it to a specific threshold value decides whether the picture belongs to an object or background. For gray images, the segmentation is carry out on the basis of image gray levels where the brighter part of an image is object and darker is background. The objects and background of gray level images can be easily identified, but the process becomes more complicated for color or textured images. So, for color and textured images requires much more attention and processing to get segmented [1]. The thresholding is also affected by the noise and artefacts present in image. Usually some preprocessing steps are applied to reduce the noise and artefacts effects.

Thresholding is mainly classified into three local, global and dynamic categories depending upon the functional dependencies of the threshold operator T. When T depends only on the gray value of pixel, it will be global. When T depends upon the gray value as well as the local property of pixel, then the threshold value is called local threshold. Whereas, if threshold value depends on pixel grey value, local property and on its position also, then the threshold is called dynamic threshold [2]. Weszka (1978) presented a survey on threshold techniques which concluded that many different threshold approaches are possible and the more sophisticated threshold selection methods can be developed [2].

This study includes only the grey level or bi-level global thresholding techniques and divided into histogram modification and threshold computing methods. This paper consists of section 2 about global thresholding technique, section 3 reviews histogram improvement methods whereas section 4 includes threshold computing methods and section 5 consists of conclusions drawn from the study.

Global Threshold technique

Earlier, only few types of segmentation techniques were known and most commonly used were preprocessing and thresholding or combination of both [3]. Thresholding is the most simple method and having least computation cost. Global threshold is totally dependent on the histogram of the image. The histograms of images may be affected with noise, contrast, hue, saturation, shadow etc. So, the global threshold selection has been aid with the use of local properties of image. Values of local property can be used to improve the histogram as well as to directly compute the global threshold. Thus, global threshold selection techniques based on local properties are divided into two categories: histogram improvement methods and threshold computing methods. The histogram improvement methods tried to improve the histograms of the images so that the threshold selection process can be made easy whereas the threshold computing methods tried to include a local property of image to compute the optimal threshold value.

Histogram improvement

An image having one object and background or having only two grey levels can be easily classified or segmented using histogram. This type of images have bimodal histograms where two peaks are separated by a deep valley, which results into a threshold value. But the threshold selection becomes a difficult task when there is noise or peaks and valleys are not well defined. The global threshold value totally depends upon the histogram of the image. Hence, many methods are introduced to improve the histograms, so that the threshold value can be computed easily and efficiently. Some of the methods were reviewed by Weszka and Rosenfeld(1977) [4].

Doyle(1962) proposed a “p-tile” global threshold technique for segmenting images having dark objects and light background [5]. The threshold value of the proposed method depending upon the area of object and not suitable for the images having unknown object areas. To overcome this drawback a histogram based threshold selection technique was proposed. Prewitt and Mendelson called it mode method [6]. This method involves smoothing of histogram, finding modes and then select the threshold at the minima between the modes. This method is suitable for gray level images but does not work well where the object and background are not clearly separated by a deep valley. Weszka, Nagel and Rosenfeld (1974) overcomes the problems of locating valleys in images having multiple peaks of unequal sizes. They described a method which selects a threshold value from a histogram of only those points which take on high values under a digital Laplacian operation [7].  Mason et al. (1975) described a method which computed weighted histogram that makes valleys deeper and peaks sharper and higher. This method facilitates the use of mode method to select the threshold value easily [8].  Ahuja and Rosenfeld (1978) used concurrences matrices alternative to histogram modification for threshold selection. In this method elements near the diagonal corresponds to pairs of neighboring elements which have almost similar grey levels and such elements are likely to be interior of the objects.. Thus histogram of these elements have deep valleys which makes threshold selection easy [9].  Wu et al. (1982) demonstrated a quad-tree method to improve the histogram of grey images. This method yields histograms having sharper peaks and deep valleys which makes the threshold selection easy [10] . Rosenfeld and Torre (1983) depicted that the histogram’s concavity structure make threshold selection for the images having unclear peaks and valleys in histogram. Concavity structure can be extracted using convex hull. This method gives good results but sensitive to noise [11].  This method fails to detect small objects and background of different intensities. To overcome these problems Whatmough (1991) presented a new exponential method to modify the histogram so that the effects of contrast stretching or compression and thresholds that separate small numbers of objects can be eliminated [12].

Sezan (1990) presented a peak detection method to detect the peaks of histograms that can be further used to select threshold. It is simple but effective method [13]. Tsai (1995) gave a Gaussian curvature analysis method to improve the histogram of the image. The proposed method is efficient and effective method and appropriate even for the real time applications [14].  Ramesh et al. (1995) proposed two automatic threshold selection methods based on functional approximation of histogram. First method is based on the minimizing the sum of squares whereas other is based on minimizing the variance. The second performs better than first [15]. Cai and Liu (1998) presented an all pole model method to estimate the optimal threshold value. Although, this method does not require prior knowledge but the mumber of classes to be segmented should be known [16].

The histogram modification methods are sensitive to noise and fails when there are more objects or complex background in an image. These methods are insensitive to small objects present in the image and the local properties of the image affect the threshold estimation process. So, to make the threshold selection an easy task the local properties are also considered for the determination of global threshold value in threshold computing methods.

Threshold computing methods

For the images having multiple objects and complex background, the threshold computing method are proposed. These methods used local property as well grey level information for threshold selection and works well even in noisy images. This study includes only Otsu and Entropy methods because Otsu method is suitable for

Otsu’s Method

Otsu (1979) found that till that time no threshold evaluating method has been proposed so that the optimal threshold value can be selected. So, an automatic optimal threshold selection method was proposed based on the global property of histogram. It maximizes separability of zeroth and first order cumulative moments of histogram [17]. Reddi et al. (1984) used the Otsu’s method [17] and presented a fast search scheme for finding single and multiple threshold value. A continuous probability function was introduced to calculate maximum interclass variance for threshold selection. The proposed method gives better results than Otsu’ method [18]. Jianzhuang et al. (1991) enhanced the 1-D Otsu method to 2-D otsu method. This method used grey level information of the image along with the spatial information of its neighborhood. The proposed method is robust to noise and give better results than 1-D Otsu method. But, requires more computational time [19]. Gong et al. (1998) gave a recursive algorithm for 2-D thresholding. A recursive algorithm used in this method reduces the computational complexity of algorithm and give satisfactory results [20]. This recursive algorithm can be used with 2-D Otsu method to decrease its computational cost. Cheriet et al. (1998) presented recursive approach an extension of Otsu’s method to segment only the document images. This is a recursive approach that segments the lowest intensity object at each iteration leaving the darkest object in digitized image. Results of the images depicts that the proposed method is very effective and efficient [21]. Liao et al. (2001) proposed a fast and efficient algorithm along with look up table for 1-d image thresholding which is improvement over Otsu’s method. The proposed method requires less computational time and provides good segmentation results [22].  Zhang and Hu (2008) presented a 2D Otsu thresholding method which works much better than 1D Otsu method when the difference of grey-level distribution is unremarkable. However, 2D Otsu gives rise to the exponential increment of computation time [23]. Lang et.al. (2008) utilized integral image to speed up the computation of 2D Otsu, but the method still had to search the entire 2D space [24]. Fengji et al. (2009) gave a solution to the problem of high computation cost. It reduced the computation time by using improved genetic algorithm to search the optimal threshold value [25]. Zhu et al. (2009) presented a fast two dimensional Otsu method. This algorithm used two dimensional histogram projected into one and uses three look up tables to reduce the computational cost [26].  But it increases the space complexity. Chen et al. (2012) presented a fast modified 2-D Otsu method. In this method the probabilities of diagonal quadrants are calculated separately and avoid unnecessary calculations [20].

Thus it has much higher segmentation precision and robustness to low contrast images. However, its speed is much slower, which is a fatal drawback in the on-line monitoring system.. Although 2-D searching speed was faster, but they demanded more memory capacity.

Entropy Based Method

Pun (1980) defined a new global function based on entropy of the histogram for threshold selection. This method automatically selects the threshold from histogram disrespect to the picture that is not depend upon the small variations in picture. The selected threshold performs a priori maximization of the posteriori known entropy of the resulting picture [27]. Pun (1981) used the derivation of entropic threshold and defined a new threshold selection method for images having irregular and various kinds of histograms. This method extracts the anisotropy coefficients from grey level histogram and then selects the threshold value [28]. Kapur (1985) found that there are some drawbacks in the algorithms suggested by Pun. It stated that there is some algebraic mistake in[27]  and second algorithm [28] does not give always satisfactory results. So, to overcome these shortcomings a new entropy based algorithm is introduced. This algorithm derived two probability distributions from original grey level distribution of the image. The total entropy of the image is then maximized to give threshold value and good segmentation results [29]. The definition of entropy does not include the spatial information. So, the images with similar histograms results in same entropic value and same threshold, which is not acceptable. Pal and Pal (1989) introduced two new definitions of entropy called entropy of order and the conditional entropy. Two algorithms are proposed, one consists of entropy of order and probability of co-occurrence of pixel intensities which takes into consideration spatial information of image whereas another algorithm based on conditional entropy. The proposed algorithms good results but the study does not include the effect of noise [30]. Wong and Sahoo (1989) presented a threshold selection algorithm based on the maximum entropy principle. This method uses both spatial as well as grey level information of an image. It does not require prior information about the image. The optimal threshold value is determined by maximizing a posterior entropy according to some features of image. This method provides good results but cannot applied to color images [31].  Brink (1992) proposed a new method, which is refinement of [32] that extends the [29]. Abutaleb (1989) extends the one dimensional entropy concept of Kapur et al. (1985) into 2-dimensional concept. Then Brink refines this concept by maximizing the smaller two entropies instead of maximizing the sum of the two entropies of the object class and background class. The proposed method gives good results but fails when there is uneven illumination [33].  Li and Lee (1993) proposed a minimum cross entropy method for segmenting an image. This method selects the threshold which minimizes the cross entropy between the threshold image and original image. For the image having no prior information, the minimum cross entropy method gives the most unbiased results [34]. Chen et al. (1994) proposed a fast 2-d entropic method for threshold selection. The computation complexity can be reduced to O(L8/3) for an image with L gray levels [35]. Then, Gong et al. (1998) proposed a recursive algorithm for 2D entropic thresholding to reduce the computation complexity from O (L4) to O (L2). However, it is still inefficient to apply this algorithm to 1D multilevel thresholding selection, due to their computation of threshold without taking advantage of the recursive structure of entropy measures [36].  Sahoo and Arora (2004) proposed a two-dimensional threshold selection method based on Renyi’s entropy of order and uses two-dimensional histogram to choose an optimal threshold value. This method of thresholding comprises global thresholding method of [37] and the two-dimensional version of the entropic correlation method introduced in [32]. Experimental results shows that proposed method gives good results but suffers from high computational cost [38].  Xie et al. (2008) presented an undistorted fast recursion method and a distorted optimal search strategy for low signal to noise ratio images. The search strategy uses entropy function proposed in [39], it calculates 2-D maximum entropy threshold by using subtraction which utilizes less computational time. The search strategy is distorted therefore; the method gives good results only if the pixels of a region are homogeneous [40].  Xiao et al. (2008) tried to use pixel similarity to describe the edge, and extended Kapur’s method, based on the gray level spatial correla-tion (GLSC) histogram. The GLSC histogram takes into account the local property of the image by using the gray value of the pixels and their similarity with neighboring pixels [41]. Yimit et al. (2013) gave an entropic thresholding approach which involves the local features along with the conventional entropic method. The proposed method gives better thresholding results [42].  Nie et al. (2017) presented a novel generalized entropic method that can handle the additive information present in physical system. The proposed method works well in real time applications [43].

Entropy method is one of the most popularly known global thresholding methods. Earlier 1-D entropic methods were introduced which have a shortcoming that different images with same histogram calculates the same threshold value.  Because they do not consider the spatial information. So, to overcome this shortcoming 2-D methods are proposed. But these 2-D methods are suffer from high computational cost and when tried to reduce this cost the space complexity get increased. In spite of these disadvantages it is useful in segmentation because of its real time performance.

Conclusions

Various factors, such as noise, ambient illumination, complexity of gray levels within the object and its background, contrast, and object size not appropriate with the scene, complicate the thresholding operation. The histogram improvement methods are sensitive to noise but gives accurate results for simple grey level images. The study of computing threshold techniques found that the entropy and Otsu methods are reasonably good thresholding methods when concerns about uniformity and better shape of the object. These methods give high precision and real time performance. This study can be further enhanced to the experimental comparison of these two techniques.

REFERENCES

[1] L. Lucchese and S. Mitra, “Advances in color image segmentation,” in Global Telecommunications Conference, GLOBECOM, 1999, vol. 4, pp. 2038-2044: IEEE.

[2] J. S. Weszka, “A survey of threshold selection techniques,” Computer Graphics and Image Processing, vol. 7, no. 2, pp. 259-265, April 1978.

[3] A. Rosenfeld, “Picture processing by computer,” ACM Computing Surveys (CSUR), vol. 1, no. 3, pp. 147-176, 1969.

[4] J. S. Weszka and A. Rosenfeld, “Histogram Modification for Threshold Selection,” IEEE Trans. Syst. Man Cybern., vol. 9, 1977.

[5] W. Doyle, “Operations useful for similarity-invariant pattern recognition,” Journal of the ACM (JACM), vol. 9, no. 2, pp. 259-267, 1962.

[6] J. Prewitt and M. L. Mendelsohn, “The analysis of cell images,” Annals of the New York Academy of Sciences, vol. 128, no. 1, pp. 1035-1053, 1966.

[7] J. S. Weszka, R. N. Nagel, and A. Rosenfeld, “A threshold selection technique,” IEEE Transactions on Computers, vol. 100, no. 12, pp. 1322-1326, December 1974.

[8] D. Mason, I. Lauder, D. Rutovitz, and G. Spowart, “Measurement of C-bands in human chromosomes,” Computers in biology and medicine, vol. 5, no. 3, pp. 179IN9181-180IN10201, December 1975.

[9] N. Ahuja and A. Rosenfeld, “A Note on the Use of Second-Order Gray Level Statistics for Threshold Selection,” IEEE Trans. Syst. Man Cybern., vol. 8, pp. 895-898, 1977.

[10] A. Y. Wu, T.-H. Hong, and A. Rosenfeld, “Threshold selection using quadtrees,” IEEE transactions on pattern analysis and machine intelligence, no. 1, pp. 90-94, 1982.

[11] A. Rosenfeld and P. De La Torre, “Histogram concavity analysis as an aid in threshold selection,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-13, no. 3, pp. 231-235, April 1983.

[12] R. Whatmough, “Automatic threshold selection from a histogram using the “exponential hull”,” CVGIP: Graphical Models and Image Processing, vol. 53, no. 6, pp. 592-600, November 1991.

[13] M. I. Sezan, “A peak detection algorithm and its application to histogram-based image data reduction,” Computer vision, graphics, and image processing, vol. 49, no. 1, pp. 36-51, January 1990.

[14] D.-M. Tsai, “A fast thresholding selection procedure for multimodal and unimodal histograms,” Pattern Recognition Letters, vol. 16, no. 6, pp. 653-666, June 1995.

[15] N. Ramesh, J.-H. Yoo, and I. Sethi, “Thresholding based on histogram approximation,” IEE Proceedings-Vision, Image and Signal Processing, vol. 142, no. 5, pp. 271-279, 1995.

[16] J. Cai and Z.-Q. Liu, “A new thresholding algorithm based on all-pole model,” in Pattern Recognition, 1998. Proceedings. Fourteenth International Conference on, 1998, vol. 1, pp. 34-36: IEEE.

[17] N. OTSU, “A threshold selection method from gray level histograms,” IEEE Trans. Syst. Man Cybern., vol. 9, no. 1, pp. 62-66, January 1979.

[18] S. Reddi, S. Rudin, and H. Keshavan, “An optimal multiple threshold scheme for image segmentation,” IEEE Transactions on Systems, Man, and Cybernetics, no. 4, pp. 661-665, July 1984.

[19] L. Jianzhuang, L. Wenqing, and T. Yupeng, “Automatic thresholding of gray-level pictures using two-dimension Otsu method,” in Circuits and Systems, 1991. Conference Proceedings, China., 1991 International Conference on, 1991, pp. 325-327: IEEE.

[20] Q. Chen, L. Zhao, J. Lu, G. Kuang, N. Wang, and Y. Jiang, “Modified two-dimensional Otsu image segmentation algorithm and fast realisation,” IET Image Processing, vol. 6, no. 4, pp. 426-433, June 2012.

[21] M. Cheriet, J. N. Said, and C. Y. Suen, “A recursive thresholding technique for image segmentation,” IEEE transactions on image processing, vol. 7, no. 6, pp. 918-921, June 1998.

[22] P.-S. Liao, T.-S. Chen, and P.-C. Chung, “A fast algorithm for multilevel thresholding,” Journal of Information Science and Enineering, vol. 17, no. 5, pp. 713-727, September 2001.

[23] J. Zhang and J. Hu, “Image segmentation based on 2D Otsu method with histogram analysis,” in Computer Science and Software Engineering, 2008 International Conference on, 2008, vol. 6, pp. 105-108: IEEE.

[24] X. Lang, F. Zhu, Y. Hao, and J. Ou, “Integral image based fast algorithm for two-dimensional Otsu thresholding,” in Image and Signal Processing, 2008. CISP’08. Congress on, 2008, vol. 3, pp. 677-681: IEEE.

[25] S. Fengjie, W. He, and F. Jieqing, “2D Otsu segmentation algorithm based on simulated annealing genetic algorithm for iced-cable images,” in Information Technology and Applications, 2009. IFITA’09. International Forum on, 2009, vol. 2, pp. 600-602: IEEE.

[26] N. Zhu, G. Wang, G. Yang, and W. Dai, “A fast 2d otsu thresholding algorithm based on improved histogram,” in Pattern Recognition, 2009. CCPR 2009. Chinese Conference on, 2009, pp. 1-5: IEEE.

[27] T. Pun, “A new method for grey-level picture thresholding using the entropy of the histogram,” Signal processing, vol. 2, no. 3, pp. 223-237, January 1980.

[28] T. Pun, “Entropic thresholding, a new approach,” Computer Graphics and Image Processing, vol. 16, no. 3, pp. 210-239, 1981.

[29] J. N. Kapur, P. K. Sahoo, and A. K. Wong, “A new method for gray-level picture thresholding using the entropy of the histogram,” Computer vision, graphics, and image processing, vol. 29, no. 3, pp. 273-285, March 1985.

[30] N. R. Pal and S. K. Pal, “Entropic thresholding,” Signal processing, vol. 16, no. 2, pp. 97-108, February 1989.

[31] A. K. Wong and P. K. Sahoo, “A gray-level threshold selection method based on maximum entropy principle,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 19, no. 4, pp. 866-871, August 1989.

[32] A. S. Abutaleb, “Automatic thresholding of gray-level pictures using two-dimensional entropy,” Computer vision, graphics, and image processing, vol. 47, no. 1, pp. 22-32, 1989.

[33] A. Brink, “Thresholding of digital images using two-dimensional entropies,” Pattern recognition, vol. 25, no. 8, pp. 803-808, 1992.

[34] C. H. Li and C. Lee, “Minimum cross entropy thresholding,” Pattern recognition, vol. 26, no. 4, pp. 617-625, 1993.

[35] W.-T. Chen, C.-H. Wen, and C.-W. Yang, “A fast two-dimensional entropic thresholding algorithm,” Pattern Recognition, vol. 27, no. 7, pp. 885-893, July 1994.

[36] J. Gong, L. Li, and W. Chen, “Fast recursive algorithms for two-dimensional thresholding,” Pattern recognition, vol. 31, no. 3, pp. 295-300, 1998.

[37] J.-C. Yen, F.-J. Chang, and S. Chang, “A new criterion for automatic multilevel thresholding,” IEEE Transactions on Image Processing, vol. 4, no. 3, pp. 370-378, March 1995.

[38] P. K. Sahoo and G. Arora, “A thresholding method based on two-dimensional Renyi’s entropy,” Pattern Recognition, vol. 37, no. 6, pp. 1149-1161, June 2004.

[39] Y. Shu, L. Gao, and B. Li-ying, “Improvement of 2-D maximum entropy threshold algorithm based on optimal entropy function [J],” Journal of System Simulation, vol. 17, no. 6, pp. 1350-1352, 2005.

[40] J. Xie, T. Liu, J. Wang, and Y. He, “A fast two-dimensional entropic thresholding algorithm,” in Information and Automation, 2008. ICIA 2008. International Conference on, 2008, pp. 275-278: IEEE.

[41] Y. Xiao, Z. Cao, and T. Zhang, “Entropic thresholding based on gray-level spatial correlation histogram,” in Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, 2008, pp. 1-4: IEEE.

[42] A. Yimit, Y. Hagihara, T. Miyoshi, and Y. Hagihara, “2-D direction histogram based entropic thresholding,” Neurocomputing, vol. 120, pp. 287-297, November 2013.

[43] F. Nie, P. Zhang, J. Li, and D. Ding, “A novel generalized entropy and its application in image thresholding,” Signal Processing, vol. 134, pp. 23-34, May 2017.