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 Kapurs method
(Pun, 1980; Kapur et al.,
1985) and the famous bi-level thresholding method by Otsus method
that was proposed by Otsu (1979). These all methods use
image histograms only and do not take into account the image spatial information.
Kapurs and Otsus 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 Otsus 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.
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 Otsus method: Otsus method, introduced by Otsu
(1979), this method maximizes the between-class variance of pixel intensity
to perform picture thresholding. Otsus 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:
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 Otsus method chooses the optimal threshold t* so that, the between-class variance was maximized, as follows:
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.
|| Proposed BA with Otsus method for multilevel image
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 Otsus 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.
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:
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 Otsus 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 Otsus 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.
|| PSNR values for the Lena image using six threshold election
|| PSNR for the Pepper image using six threshold election methods
||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.
||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 Otsus 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 Otsus method and exhaustive search. The threshold values found by using BA algorithm with Otsus 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 Otsus 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).
||Thresholds, computation times and PSNR values for test images
using the BA algorithm with Otsus method and exhaustive search
|K is the No. of thresholds, BA Thresholds is Bees Algorithm
used with Otsus method threshold values
||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 Otsus methods are
not stable and not robust and the segmentation result of HBMO is better than
PSO method and slower.
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.
This project research is funded by the KETUA project UKM-TT -02-FRGS0207-2010 grant entitled "The Enhancement of Bees Algorithm.