Optimized Multilevel Thresholding for Image Segmentation: A Review

OPTIMIZED MULTILEVEL THRESHOLDING FOR IMAGE SEGMENTATION: A REVIEW

ABSTRACT

Image segmentation is used to extract useful information from an image. It also compresses image so that space requirement decreases with no or least information loss. Thresholding is one of the effective and simple technique for image segmentation. There are many thresholding algorithms available in literature. They all work well for specific applications but suffer from high computational cost and space complexity. To reduce these complexities optimization techniques are introduced to thresholding algorithms. So that these algorithms can be more efficient and effective. This paper studies the optimized thresholding techniques available in literature and found that the although the optimization techniques have their own limitations however use of optimization techniques in multilevel thresholding techniques lead to quality results and real time application.

INTRODUCTION

In image processing, the main task is to analyse the image and for analysis it is necessary to depict the information that hides in the image. For this purpose, image segmentation is used to separate objects from the background. There are lots of image segmentation techniques available in literature, where thresholding is considered as very simple and effective method for image segmentation. Threshold based segmentation methods can effectively separate objects from the background. Earlier, thresholding techniques are used for grey image segmentation and efficiently do the task. But, with the advancement of technology and use of color images the need to segment color images arises and grey level thresholding methods do not work as efficiently for them.

The study of thresholding methods for image segmentation found that there are variety of thresholding selection methods for grey images present in literature. The most commonly thresholding is divided into three categories local, global and dynamic thresholds. The entropy based and Otsu method are popular methods for threshold selection for grey images and called bi-level thresholding methods. The Otsu method is simple and work with a global threshold values due to its low sensitivity to dark areas.  Otsu method does not require prior knowledge on the shape of the histogram. Entropy based methods are also very good in segmentation of grey images. The conventional Otsu’s method can achieve good result only when the histogram of an image has two distinct peaks. But these methods are not as efficient when applied to complex or color images. To make bi-level thresholding methods applicable on color images, multi-level thresholding algorithms are introduced. But the multi-level thresholding algorithms are computationally complex and expensive so some optimization techniques are used with these methods to accomplish effective results.

The various optimization techniques are used with Otsu, entropy and minimum error methods to improve the efficiency and make them effective for grey as well as color images.

Multilevel thresholding methods

The thresholding methods are efficiently applied on grey level images where the objects and backgrounds are clearly distinguishable. But these are affected by noise, hue, contrast, artefacts etc. present in image. That means the images having multiple features and undistinguishable objects are difficult to segment. To segment theses complex images, the multilevel thresholding is used. Although, it is not easy to determine multilevel thresholding because of overlapping and small objects present in the images. However, several techniques are proposed to do the same.

Wang and Haralick (1984) firstly introduced the multi-thresholding method based on the edge and non-edge pixels. A recursive approach is applied on edge and non-edge pixels separately to get multiple thresholds. This method gives average results [1].  Reddi et al. (1984) extended the Otsu method for multithresholding[2]. Boukharouba et al. (1985) studied curvature of image distribution function instead of histogram. This leads to noise reduction in image without any information loss. The critical points of curvature are obtained and correlated with histogram to get the multiple threshold values. This is a dynamic multiple threshold technique in which the number of threshold value is determined by user [3].  Spann and Wilson (1985) proposed a hybrid multi-threshold selection method based on statistical and spatial information. It consists of quad-tree smoothing technique, local centroid clustering algorithm and boundary estimation approach. It gives good results but applicable only when histogram consists of only Gaussian Distributions [4].

Carletto (1987) gave a new approach based on the change of zero crossings in second order derivative. This approach works on the principle that the histogram consists of only univariate normal distributions [5]. Hertz and Schafer (1988) also used the edge information for threshold selection. The process is called edge matching, it not only isolates the object from background but also helps in finding multiple threshold values. This algorithm segments only those images which have clearly defined edges [6]. Papamarkos and Gatos (1994) presented a three stage method for image segmentation. Firstly used hill clustering technique to determine the peaks, peaks are approximated by rational function and golden search gives optimal values which corresponds to a multilevel threshold. The results shows that the proposed method works well [7]. Yen et al. (1995) proposed a new maximum correlation criterion for multilevel image thresholding [8].

These all are multiple threshold selection methods. Some are advancements of bi-level thresholding methods and some introduced new criterion. All have some drawbacks, but one common drawback is their computational cost.

Optimized Multilevel thresholding Techniques

Thresholding techniques are introduced with optimization techniques, so that they can be more efficient and effective. With the use of optimization techniques the performance measures of the multilevel threshold algorithms can be improved.

Zahara et al. (2005) and Fan and Lin (2007) reported that Otsu and Gaussian distribution method is good for bi-level thresholding but computationally expensive for multi-thresholding. So, an optimization method should be introduced that can reduce its computational cost. In 2005 a hybrid Nelder-Mead Particle  Swarm Optimization (NM-PSO) Otsu method is proposed that uses Nelder-Mead simplex search for local search and Particle Swarm Optimization for global search. The method is found effective and efficient when compared to Otsu method [9]. Again in 2007, a hybrid multi-level thresholding method proposed, that uses PSO-EM methods. In this method, Particle Swarm Optimization carries out global search and expectation maximization updates the best particle, which leads the remaining particles to seek optimal solution in search space [10]. Both methods [9] and [10] successfully avoid the local minima and easily minimize the objective function Gaussian curve fitting for multi-level thresholding. Although  it is found that PSO-EM converges much faster than NM-PSO and PSO-EM is better. However, it is found that the PSO-EM method does not give quality results when applied to RAM image. Huang et al. (2005) proposed a new method of thresholding based on the pyramid data structure manipulation and the adaptively selected window size according to Lorentz information measure. The proposed method effectively and efficiently segment the images having uneven light distribution but not applicable for multi thresholding [11]. Zhang and Liu (2006) reported a new method for underwater image segmentation. This method overcome the complex computation problem of maximum entropy method. For this, an optimization method PSO is used. The threshold values are obtained using Particle Swarm Optimization method where fitness function is maximum entropy method. The threshold values are obtained effectively with high efficiency [12]. Yin (2007) found that the minimum cross entropy thresholding is time consuming for complex images i.e. multilevel threshold. So, to efficiently find out the multilevel threshold for a complex image, a recursive method to reduce the order of magnitude of minimum cross entropy method is proposed. To optimize the results the PSO is used. Whereas Zhao et al. (2007) found that PSO method stuck in sub optimal threshold and used quantum PSO to optimize the results. Experiment shows that the proposed QPSO method overcome the PSO shortcomings and  suitable for real world images [13] [14]. Ye et al. (2008) proposed a threshold selection method based on an optimization principle called Particle swarm Optimization (PSO). This method calculates the fitness of each particle or pixel and determines the local and global best positions. Then positions are updated and process continues until an optimal solution is achieved or maximum number of iterations are executed. The proposed algorithm successfully find the optimal solution. However, this method has a drawback that it requires the prior knowledge of number of thresholds [15]. Hammouche et al. (2008)  proposed a multilevel thresholding method that not only calculate the threshold value but also determine the appropriate number of thresholds. This method uses genetic algorithm with wavelet transform.. Experiments shows the efficiency of proposed method [16]. Huang (2009) proposed a new fast two-stage algorithm to improve the efficiency of Otsu’s method. The runtime of proposed method is less than the Otsu’s method but efficiency is equal [17]. Horng (2010) found that the maximum entropy thresholding method is most widely used for multilevel threshold selection, but having high computational cost. To optimize this a new multilevel threshold selection method based on Honey Bee mating is proposed. When compared to other methods it is found that the results are good and computational cost is relatively low [18]. Then, Horng (2011) proposed another maximum entropy thresholding algorithm that uses Artificial Bee Colony algorithm that simulates the behavior of honey bees foraging. It works efficiently than his previous method [19]. Al-Amri et al. (2010) presented a comparative study of various thresholding techniques such as Mean method, P-tile method, Histogram Dependent Technique (HDT), Edge Maximization Technique (EMT) and visual Technique. Experimental study done on all these techniques and the results show that the histogram dependent technique and edge maximization technique gives best results [20]. Abdulaah et al. (2012) proposed an image segmentation algorithm that produces good quality segmentation results of natural images. This method uses the Otsu method with inverse technique that efficiently segment natural images. When compared to conventional Otsu method and K-means clustering, the proposed method gives amazing results [21]. Zhiwei et al. (2012) gave a novel approach to segment images using 2-d thresholding and artificial fish swarm algorithm. This approach uses spatial information to segment an image. It segments the image with the best position of artificial fishes swarm. The results shows that the proposed method efficiently calculate the optimal threshold value [22]. Cai et al. (2014) proposed a new iterative triclass thresholding technique based on the Otsu’s method. This method classify the image into three classes instead of two by using Otsu’s thresholding method. The two classes are true background and foreground and third is to-be determined (TBD) class. Then repeatedly Otsu method is applied on TBD class until each pixel belongs to two classes i.e. pixel either in background or foreground class. Thus, a high quality segmented image is achieved. The results shows that this is effective and efficient segmentation method [23]. Bdioui et al. (2014) proposed an entropy based thresholding method for color image segmentation. The method uses discriminator color criterion to find out the suitable color space and then entropy based threshold based technique is applied. The results shows that the proposed method gives better results when compared to K-means [24]. Dhieb et al. (2014) proposed a global 2-d maximum entropy based image segmentation algorithm. The conventional entropy method trapped in local maximum entropy that is overcome by this method by using Particle Swarm Optimization method. This optimization method increase the efficiency of proposed method [25]. Sandeli and Batouche (2014) presented a new method for image segmentation by multilevel thresholding based on generalized island model (GIM). This GIM model constitute of three metaheuristics called Particle Swarm Optimization (PSO), Genetic Algorithm (GA) and Artificial Bee Colony (ABC). It helps the method to not stuck in local minima. The proposed method outperforms other methods and give effective results [26]. Devi et al. (2015) gave an iterative thresholding based on 2D improved Otsu method using a novel threshold value recognition function which is used to find the optimum threshold value in different types of histograms and separate it into two classes. For the two classes separated by the above threshold value, mean values are computed. Based on the threshold value and the two mean values, the histogram of an image is divided iteratively into three regions, namely, the Foreground (FG) region, Background (BG) region and To-Be-Processed (TBP) region. Again for that TBP region, the process is repeated iteratively until the stable values are not found. Finally, all the previously determined foreground regions are combined separately and the background regions are combined separately to give the segmented image. The experimental results show that the proposed method performs well in detecting the objects and has better anti-noise performance compared with the existing methods [27]. Tuba et al. (2015) found that the multilevel thresholding includes an exhaustive search for optimal threshold selection. The number of possible values for threshold grows exponentially and it prevents the exhaustive search. To solve this problem a swarm intelligence technique called firework algorithm is adopted for multilevel image thresholding. It uses Kapur’s entropy function as its objective function. On comparing with other swarm optimization methods, it is found that proposed method gives better results [28]. Sharma et al. (2016) stated that the fireworks algorithm used to maximize two functions called Otsu and Kapur. In this paper fireworks algorithm is used for multilevel thresholding and Otsu criterion is used as fitness function. Experimental results shows that the proposed method outperforms the method proposed in [28]. The segmentation quality of proposed method is very good [29]. Banerjee et al. (2016) proposed a region based triple thresholding method for image segmentation. It segments grey images using three threshold values; one global and two local threshold. Based on these threshold values image is divided into four regions having different intensity values. The proposed method segments images efficiently and detects all the regions in an image [30]. Win and Chomchuay (2017) proposed a method to segment cell nuclei in pleural fluid. In this method, the image is pre-processed using median filter and then the enhanced image is converted to l*a*b color space. The cell nuclei is segmented using Otsu method and morphological operations are applied to remove noise and to reconstruct into color-segmented image. the proposed method gives very good results [31].

Conclusions

This paper present an extensive review of multilevel thresholding techniques. Firstly the multilevel thresholding techniques are reviewed and found that these are recursive algorithms and requires more computational cost as well as have more space complexity. But, it also makes the thresholding or segmentation of complex images possible and easy. So, to improve the efficiency of these algorithms optimization techniques are introduced. There are many optimization techniques in literature such as Particle swarm Optimization, Honey bee, genetic algorithm etc. and all these have their own pros and cons. However, these makes the algorithms more effective and efficient by reducing time complexity and giving quality results.

[1] S. Wang and R. M. Haralick, “Automatic multithreshold selection,” Computer vision, graphics, and image processing, vol. 25, no. 1, pp. 46-67, January 1984.

[2] 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.

[3] S. Boukharouba, J. M. Rebordão, and P. Wendel, “An amplitude segmentation method based on the distribution function of an image,” Computer Vision, Graphics, and Image Processing, vol. 29, no. 1, pp. 47-59, January 1985.

[4] M. Spann and R. Wilson, “A quad-tree approach to image segmentation which combines statistical and spatial information,” Pattern Recognition, vol. 18, no. 3-4, pp. 257-269, January 1985.

[5] M. J. Carlotto, “Histogram analysis using a scale-space approach,” IEEE Transactions on Pattern Analysis and Machine Intelligence, no. 1, pp. 121-129, January 1987.

[6] L. Hertz and R. W. Schafer, “Multilevel thresholding using edge matching,” Computer Vision, Graphics, and Image Processing, vol. 44, no. 3, pp. 279-295, December 1988.

[7] N. Papamarkos and B. Gatos, “A new approach for multilevel threshold selection,” CVGIP: Graphical Models and Image Processing, vol. 56, no. 5, pp. 357-370, September 1994.

[8] 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.

[9] E. Zahara, S.-K. S. Fan, and D.-M. Tsai, “Optimal multi-thresholding using a hybrid optimization approach,” Pattern Recognition Letters, vol. 26, no. 8, pp. 1082-1095, 2005.

[10] S.-K. S. Fan and Y. Lin, “A multi-level thresholding approach using a hybrid optimal estimation algorithm,” Pattern Recognition Letters, vol. 28, no. 5, pp. 662-669, 2007.

[11] Q. Huang, W. Gao, and W. Cai, “Thresholding technique with adaptive window selection for uneven lighting image,” Pattern recognition letters, vol. 26, no. 6, pp. 801-808, May 2005.

[12] R. Zhang and J. Liu, “Underwater image segmentation with maximum entropy based on particle swarm optimization (PSO),” in Computer and Computational Sciences, 2006. IMSCCS’06. First International Multi-Symposiums on, 2006, vol. 2, pp. 360-636: IEEE.

[13] P.-Y. Yin, “Multilevel minimum cross entropy threshold selection based on particle swarm optimization,” Applied mathematics and computation, vol. 184, no. 2, pp. 503-513, January 2007.

[14] Y. Zhao, Z. Fang, K. Wang, and H. Pang, “Multilevel minimum cross entropy threshold selection based on quantum particle swarm optimization,” in Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2007. SNPD 2007. Eighth ACIS International Conference on, 2007, vol. 2, pp. 65-69: IEEE.

[15] Z. Ye, H. Chen, W. Liu, and J. Zhang, “Automatic threshold selection based on particle swarm optimization algorithm,” in Intelligent Computation Technology and Automation (ICICTA), 2008 International Conference on, 2008, vol. 1, pp. 36-39: IEEE.

[16] K. Hammouche, M. Diaf, and P. Siarry, “A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation,” Computer Vision and Image Understanding, vol. 109, no. 2, pp. 163-175, 2008.

[17] D.-Y. Huang and C.-H. Wang, “Optimal multi-level thresholding using a two-stage Otsu optimization approach,” Pattern Recognition Letters, vol. 30, no. 3, pp. 275-284, 2009.

[18] M.-H. Horng, “Multilevel minimum cross entropy threshold selection based on the honey bee mating optimization,” Expert Systems with Applications, vol. 37, no. 6, pp. 4580-4592, 2010.

[19] M.-H. Horng, “Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation,” Expert Systems with Applications, vol. 38, no. 11, pp. 13785-13791, 2011.

[20] S. S. Al-Amri and N. V. Kalyankar, “Image segmentation by using threshold techniques,” arXiv preprint arXiv:1005.4020, 2010.

[21] S. L. S. Abdullah and N. Jamil, “An accurate thresholding-based segmentation technique for natural images,” in Humanities, Science and Engineering Research (SHUSER), 2012 IEEE Symposium on, 2012, pp. 919-922: IEEE.

[22] Y. Zhiwei, L. Qinyun, Z. Mengdi, and L. Wei, “Image segmentation using thresholding and artificial fish-swarm algorithm,” in Computer Science & Service System (CSSS), 2012 International Conference on, 2012, pp. 1529-1532: IEEE.

[23] H. Cai, Z. Yang, X. Cao, W. Xia, and X. Xu, “A new iterative triclass thresholding technique in image segmentation,” IEEE Transactions on Image Processing, vol. 23, no. 3, pp. 1038-1046, 2014.

[24] N. Bdioui, M. Moussa, and A. Douik, “Entropy based thresholding for color image segmentation,” in Image Processing, Applications and Systems Conference (IPAS), 2014 First International, 2014, pp. 1-5: IEEE.

[25] M. Dhieb, S. Masmoudi, M. B. Messaoud, M. Frikha, and F. B. Arfia, “2-D entropy image segmentation on thresholding based on particle swarm optimization (PSO),” in Advanced Technologies for Signal and Image Processing (ATSIP), 2014 1st International Conference on, 2014, pp. 143-147: IEEE.

[26] M. Sandeli and M. Batouche, “Multilevel thresholding for image segmentation based on parallel distributed optimization,” in Soft Computing and Pattern Recognition (SoCPaR), 2014 6th International Conference of, 2014, pp. 134-139: IEEE.

[27] M. A. Devi, T. Latha, and C. H. Sulochana, “Iterative thresholding based image segmentation using 2D improved Otsu algorithm,” in Communication Technologies (GCCT), 2015 Global Conference on, 2015, pp. 145-149: IEEE.

[28] M. Tuba, N. Bacanin, and A. Alihodzic, “Multilevel image thresholding by fireworks algorithm,” in Radioelektronika (RADIOELEKTRONIKA), 2015 25th International Conference, 2015, pp. 326-330: IEEE.

[29] E. Sharma, P. Mahapatra, and A. Doegar, “Image thresholding based on swarm intelligence technique for image segmentation,” in Information Technology (InCITe)-The Next Generation IT Summit on the Theme-Internet of Things: Connect your Worlds, International Conference on, 2016, pp. 251-255: IEEE.

[30] A. Banerjee, S. Bhattacharjee, and S. Latib, “Image segmentation using region derived triple thresholding,” in Recent Advances in Information Technology (RAIT), 2016 3rd International Conference on, 2016, pp. 429-433: IEEE.

[31] K. Y. Win and S. Choomchuay, “Automated segmentation of cell nuclei in cytology pleural fluid images using OTSU thresholding,” in Digital Arts, Media and Technology (ICDAMT), International Conference on, 2017, pp. 14-18: IEEE.