Subscribe Now Subscribe Today
Research Article
 

Optimization of Multilevel Image Thresholding Using the Bees Algorithm



Nahlah Shatnawi, Mohammad Faidzul and Shahnorbanun Sahran
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

Image thresholding was the process of converting grayscale or even color images into images that had fewer classes of possible pixel values. Thresholding methods could involve finding either a single threshold value (bi-level) or multiple thresholds (multilevel). Bi-level thresholding method was straightforward, but multilevel methods involved exhaustive searching that required large amounts of computation time. One meta-heuristic optimization method to solve the computation time problem was based on bee’s behavior in nature. The recently introduced variant of this method was the Bees Algorithm (BA). BA mimics honey bee foraging activities. It had been proven to be the most powerful fair optimization method for sampling a large solution space because of its fair random sampling. In this study, Otsu’s BA-based method was used to reduce computation time in multilevel image thresholding. Two standard images, Lena and Peppers, were thresholded using the peak signal-to-noise ratio as the image quality index. The effectiveness of the proposed method in terms of its peak signal noise ratio and computation time was measured. The results were then benchmarked against other optimization algorithms, such as Artificial Bee Colony (ABC), Honey Bee Mating Optimization (HBMO), Particle Swarm Optimization (PSO) and excessive search. The experiments showed that the quality of images generated by the BA was the best among all of the methods. The BA also used the shortest computation time to find more than 4 thresholds. This result demonstrates that the BA was an outstanding method for optimizing multilevel image thresholding, especially for large threshold values.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Nahlah Shatnawi, Mohammad Faidzul and Shahnorbanun Sahran, 2013. Optimization of Multilevel Image Thresholding Using the Bees Algorithm. Journal of Applied Sciences, 13: 458-464.

DOI: 10.3923/jas.2013.458.464

URL: https://scialert.net/abstract/?doi=jas.2013.458.464
 
Received: December 20, 2012; Accepted: February 18, 2013; Published: April 22, 2013



INTRODUCTION

Image thresholding was one of the basic image preprocessing techniques in computer vision. It was used in other image processing applications, such as document processing, image compression, object recognition and so on (Tao et al., 2008). Image thresholding was a method for separating objects in an image from the background by selecting a threshold value t, where t is the intensity or color value (Lee et al., 2008). A thresholding technique should segment images efficiently, balancing the processing time and the required image quality.

The thresholding process compares each pixel in an image with chosen threshold values that would divide an image into objects and background. Thresholding techniques can be either bi-level or multilevel. Bi-level thresholding was used to create binary images from grayscale images by assuming that there were two classes in an image: (1) Objects and (2) Background. Multilevel thresholding used multiple thresholds to divide the pixels into multiple groups of gray levels (Zhang and Wu, 2011). Examples of bi-level methods include a proposed iterative scheme that can converge to an optimal threshold (Ridler and Calvard, 1978), Pun and Kapur’s method (Pun, 1980; Kapur et al., 1985) and the famous bi-level thresholding method by Otsu’s method that was proposed by Otsu (1979). These all methods use image histograms only and do not take into account the image spatial information. Kapur’s and Otsu’s methods were efficient methods for bi-level thresholding; however, for multilevel thresholding, they require long computation times due to the exhaustive search.

The problem of finding multiple thresholds had been studied for many years. Many thresholding methods had been proposed to perform bi-level thresholding (Sahoo et al., 1988) and they had also been extended to multilevel thresholding. However, for optimal multilevel thresholding, the algorithms were usually trapped by an exhaustive searching process to test all possible threshold subsets. That process uses computation time that grows exponentially (Horng and Jiang, 2010a). To find the optimal values in an acceptable computation time, other researchers had employed optimization algorithms such as ABC, HBMO, PSO and Firefly. Generally, these techniques had been reduced the computation time, but they all can be further improved.

Currently, population-based optimization used for multilevel thresholding to solve the exhaustive search method problem. A new approach for the optimization of the maximum entropy based on the BA to address infrared images had been proposed by Azarbad et al. (2011). The bee algorithm which had proven to be the most powerful fair optimization method for sampling a large solution space, because of fair random sampling, had quickly been adapted to image processing infrared image segmentation. To enhance speed and accuracy, Azarbad et al. (2011) used the bee algorithm to find the optimum threshold. They find that maximum entropy image segmentation based on the bee algorithm finds a better threshold and, because of the selected threshold, can detect and extract the desired object from the background of the image. A new multilevel Maximum Entropy Thresholding (MET) algorithm that based on the ABC algorithm, the Maximum Entropy based Artificial Bee Colony Thresholding (MEABCT) method, was proposed by Horng and Jiang (2010a). Zhang and Wu (2011) used ABC to solve the multi-level thresholding model. The ABC approach was advantageous in that it conducts both global and local searches at each iteration and as a result, the probability of finding the optimal result was significantly increased, without local optima, when compared to GA (Genetic Algorithm) and PSO, both of which can jump from local minima but do not achieve satisfactory efficiencies. Multi-level image thresholding using the HBMO algorithm was proposed by Liou et al. (2009), where Kapur et al. (1985) method used to develop Maximum Entropy-based HBMO Thresholding (MEHBMOT). In study of Horng et al. (2009), the Minimum Cross Entropy Thresholding (MCET) algorithm used and developed by using Kullback method with HBMO, to select the thresholds by minimizing the cross entropy between the original image and the resulting image. Horng and Jiang (2010a) proposed a new multilevel Met algorithm based on the firefly algorithm, called Maximum Entropy-based FireFly Thresholding (MEFFT).

In this study, the use of BA as the optimizing algorithm was proposed to reduce the computation time in Otsu’s multilevel image thresholding process. The proposed technique simultaneously produced better quality thresholded images. Two standard images, Lena and Peppers, were used as test images. The Peak Signal-to-Noise Ratio (PSNR) used to measure the quality of the processed images. The results were compared with results from previous works that use the alternate algorithms ABC, HBMO and PSO and the excessive search itself.

METHODOLOGY

In this study, the Otsu method was described and then, the proposed method using the BA and the Otsu method was discussed in detail.

The Otsu’s method: Otsu’s method, introduced by Otsu (1979), this method maximizes the between-class variance of pixel intensity to perform picture thresholding. Otsu’s method achieves good threshold values in many cases, but for multilevel image thresholding, it was very time-consuming because of the inefficient formulation of the between-class variance (Liao et al., 2001). The threshold in this method can be calculated based on the following equations:

(1)

where, σB2 is the between-class variance, ω1 and ω2 are the probability distributions for class 1 and class 2, respectively, μ1 and μ2 are the means for class 1 and class 2, respectively and μT is the mean for the whole image. The Otsu’s method chooses the optimal threshold t* so that, the between-class variance was maximized, as follows:

(2)

where, t is greater than or equal to 1 and less than the maximum gray level.

BA algorithm for multilevel thresholding: The BA was an optimization algorithm based on the nature of bees foraging for food (Pham et al., 2006). It was one of many biologically inspired algorithms. It was a new population-based algorithm that had been proposed to overcome the local optima problem and was applicable to both combinatorial and functional optimization problems (Pham et al., 2006).

The BA had proved to be the most powerful fair optimization method for sampling a large solution space because of its fair random sampling. Some other nature-based algorithms were the Ant Colony Optimization (ACO), PSO, ABC and the HBMO algorithm.

Fig. 1: Proposed BA with Otsu’s method for multilevel image thresholding

In this study, the proposed application of the BA algorithm to find the best threshold using less computation time was discussed. The first step was to use the Otsu’s method to calculate the bi-level threshold value (t0), by calculating the histogram of the image, probability distribution, mean and between-class variance. Then, the histogram was used with t0 to divide the histogram into 2 classes and calculate the probability distribution and mean for each class. The next step was to apply the BA algorithm to each class to find the threshold values. The BA algorithm was applied to all of the classes in parallel by sending scout and follower bees to each class simultaneously. Figure 1 showed how the proposed method works.

RESULTS

In the previous study some optimization-based algorithms for multilevel image thresholding described. To understand these methods enough to choose the best algorithm to obtain the optimal results and computation time, they must be analyzed and evaluated. A few quantitative evaluation indexes, such as correlation, contrast measure and the Peak Signal-to-Noise Ratio (PSNR) had been used. PSNR was a popular performance indicator which was an engineering term for the "ratio between the maximum possible power of a signal and the power of corrupted noise that affects the fidelity of its representation" (Kaur and Singh, 2011). A higher PSNR means that the quality of the image threshold value was better. Currently, most thresholding methods use the PSNR for ending multilevel thresholding (Abdullah et al., 2010). The PSNR equation is as follows:

(3)

Figure 2 and 3 showed the PSNR value in (db) for two standard images, Lena and Pepper. The algorithms used for the multilevel image thresholding (2, 3, 4 and 5 threshold values) are: PSO and MEABCT (Zhang and Wu, 2011), MEHBMOT Kapur (Liou et al., 2009), MEFFT (Horng and Jiang, 2010b), exhaustive (Liou et al., 2009) and the proposed BA-based Otsu’s method.

Comparing the PSNR value for the Lena image when 5 threshold values found, showed that the PSNR value increased as the threshold number increased. As shown in Fig. 2, the proposed BA with Otsu’s method gives the best results for 3, 4 and 5 thresholds, followed by MFFT and exhaustive search; PSO was the worst. In the Pepper image, the BA algorithm gives the best results, followed by exhaustive search, then MEACBT and MEHBMOT (Kapur); PSO was the worst. These results do not mean, however, that the use of the exhaustive search was good, because it is still time consuming.

The exhaustive search gives good results, as observed in Fig. 2 and 3, but it was time consuming compared to other population-based algorithms, where the computation time exponentially increases when the number of thresholds was increased, as example, it needs for Lena image 4.89 msec to find two threshold values and reaches 451304 for five thresholds. Based on these observations, it was concluded that the exhaustive search was not applicable to multilevel thresholding.

Fig. 2: PSNR values for the Lena image using six threshold election methods

Fig. 3: PSNR for the Pepper image using six threshold election methods

Fig. 4: Computation time (ms) for five threshold election methods to segment the Lena image

Figure 4 and 5 showed the computation time for the algorithms shown in Fig. 2 and 3.

Figure 4 and 5 showed that the computation time increased dramatically when the threshold number was more than 5. From a practical standpoint, it was difficult to select more than 5 threshold values from the many possibilities.

Fig. 5: Computation time (ms) for five threshold election methods to segment the Pepper image

MEFFT was faster for multilevel thresholding, followed by PSO, but PSO is still not stable. ABC, similar to MEABCT, showed better performance in function optimization problems when compared to PSO, but it was slower than PSO. The proposed BA with Otsu’s method was the worst method for 2, 3 and 4 thresholds. But the proposed BA with Otsu was the fastest method for 5 thresholds by a difference in time equal to 41.12 when compared to MEFFT.

Table 1 showed the threshold values when applying the Bees algorithm for multilevel image thresholding using Otsu’s method and exhaustive search. The threshold values found by using BA algorithm with Otsu’s method near to exhaustive search threshold values, but found by BA algorithm in less computation time with better quality based on the PSNR values in Fig. 2 and 3.

Figure 6 showed the segmented images resulted from using the thresholding values of BA algorithm with Otsu’s method mentioned in Table 1. Where, K is the number of thresholds used to segment the image.

The BA which had proven to be the most powerful fair optimization method for sampling a large solution space, because of fair random sampling, had quickly been adapted to image processing infrared image segmentation (Azarbad et al., 2011). MEABCT algorithm results were better and its computation time is relatively faster compared with PSO and MEHBMOT (Horng and Jiang, 2010b).

Table 1: Thresholds, computation times and PSNR values for test images using the BA algorithm with Otsu’s method and exhaustive search
K is the No. of thresholds, BA Thresholds is Bees Algorithm used with Otsu’s method threshold values

Fig. 6(a-h): Segmented images using threshold values found by BA algorithm (a and e) used two thresholds, (b and f) used three thresholds, (c and g) used four thresholds and (d and h) used five thresholds

Based on Zhang and Wu (2011), ABC is more rapid than GA and PSO, exhaustive algorithm failed for multi-level thresholding and the efficiency of the intelligence optimization is higher than traditional exhaustive method. Based on Liou et al. (2009) and Horng et al. (2009) the results of PSO and Fast Otsu’s methods are not stable and not robust and the segmentation result of HBMO is better than PSO method and slower.

CONCLUSION

Image segmentation was an important field for object recognition and computer vision; many methods had been implemented to handle image segmentation for bi-level thresholding using exhaustive search, but they were not applicable to multilevel thresholding because the computation time required for exhaustive search grows exponentially with number of thresholds. To handle multilevel thresholding, new optimization algorithms had been developed, specifically the meta-heuristic algorithms which had been proven to be better than other optimization algorithms; the best algorithms were those that depend on natural behaviors.

When meta-heuristic algorithms were applied to multilevel thresholding, they showed good results with lower computation times compared to exhaustive search. In this study, PSNR was used as the indicator for the results and the algorithms that were based on bees’ natural behavior, i.e., BA, ABC and HBMO, give the best results. The BA algorithm was the best in terms of the quality of segmented images, as measured by the PSNR value.

ACKNOWLEDGMENT

This project research is funded by the KETUA project UKM-TT -02-FRGS0207-2010 grant entitled "The Enhancement of Bees Algorithm”.

REFERENCES
1:  Abdullah, S.N.H.S., F. PirahanSiah, N.H.H.Z. Abidin and S. Sahran, 2010. Multi-threshold approach for license plate recognition system. World Acad. Sci. Eng. Technol., 48: 804-808.
Direct Link  |  

2:  Azarbad, M., A. Ebrahimzade and V. Izadian, 2011. Segmentation of infrared images and objectives detection using maximum entropy method based on the bee algorithm. Int. J. Comput. Infom. Syst. Ind. Manage. Appl., 3: 26-33.
Direct Link  |  

3:  Horng, M.H. and T.W. Jiang, 2010. Multilevel image thresholding selection based on the firefly algorithm. Proceeding of the 7th International Conference on Ubiquitous Intelligence and Computing and 7th International Conference on Autonomic and Trusted Computing, October 26-29, 2010, Xian, Shaanxi, China, pp: 58-63.

4:  Horng, M.H. and T.W. Jiang, 2010. Multilevel image thresholding selection using the artificial bee colony algorithm. Proceedings of the International Conference on Artificial Intelligence and Computational Intelligence, Part II, October 23-24, 2010, Sanya, China, pp: 318-325.

5:  Horng, M.H., T.W. Jiang and J.Y. Chen, 2009. Multilevel minimum cross entropy threshold selection based on honey bee mating optimization. Proceedings of the 3rd WSEAS International Conference on Circuits, Systems, Signal and Telecommunications, January 10-12, 2009, Zhejiang Wanli University, Ningbo, Zhejiang, China, pp: 25-30.

6:  Kapur, J.N., P.K. Sahoo and A.K.C. Wong, 1985. A new method for gray level picture thresholding using the entropy of the histogram. Comput. Vis. Graph. Image Process., 29: 273-285.
Direct Link  |  

7:  Kaur, P. and J. Singh, 2011. A study on the effect of gaussian noise on PSNR value for digital images. Int. J. Comput. Electr. Eng., 3: 319-321.
Direct Link  |  

8:  Lee, C.C., Y.C. Chiang, C.Y. Shih and W.S. Hu, 2008. Image thresholding using mean-shift based particle swarm optimization. Proceeding of the 8th International Conference on Intelligent Systems Design and Applications, Volume 1, November 26-28, 2008, Kaohsiung, Taiwan, pp: 65-70.

9:  Liao, P.S., T.S. Chen and P.C. Chung, 2001. A fast algorithm for multilevel thresholding. J. Inform. Sci. Eng., 17: 713-727.
Direct Link  |  

10:  Liou, R.J., M.H. Horng and T.W. Jiang, 2009. Multi-level thresholding selection by using the honey bee mating optimization. Proceeding of the 9th International Conference on Hybrid Intelligent Systems, Volume 1, August 12-14, 2009, Shenyang, China, pp: 147-151.

11:  Otsu, N., 1979. A threshold selection method from gray-level histogram. IEEE Trans. Syst. Man Cybern., 9: 62-66.
CrossRef  |  Direct Link  |  

12:  Pham, D.T., A. Ghanbarzadeh, E. Koc, S. Otri, S. Rahim and M. Zaidi, 2006. The bees algorithm-a novel tool for complex optimization problems. Proceedings of the 2nd International Virtual Conference on Intelligent Production Machines and Systems, July 3-14, 2006, Cardiff University, UK., pp: 454-459.

13:  Pun, T., 1980. A new method for gray-level picture threshold using the entropy of the histogram. Signal Process, 2: 223-237.

14:  Ridler, T. and S. Calvard, 1978. Picture thresholding using an iterative selection method. IEEE Trans. Syst. Man Cybernetics, 8: 630-632.
CrossRef  |  

15:  Sahoo, P.K., S. Soltani and A.K.C. Wong, 1988. A survey of thresholding techniques. Comput. Vision Graphics Image Process, 41: 230-260.

16:  Tao, W., H. Jin, Y. Zhang, L. Liu and D. Wang, 2008. Image thresholding using graph cuts. IEEE Trans. Syst. Man Cybern. Part A: Syst. Hum., 38: 1181-1195.
CrossRef  |  

17:  Zhang, Y. and L. Wu, 2011. Optimal multi-level thresholding based on maximum tsallis entropy via an artificial bee colony approach. Entropy, 13: 841-859.
CrossRef  |  

©  2021 Science Alert. All Rights Reserved