1 Introduction

Image segmentation is an important image preprocessing technology. The calculation of thresholding image segmentation is simple and effective [1]. Hence, thresholding has become a popular approach for image segmentation. Basically, thresholding is used to separate an image into targets and background on the basis of the gray histogram. Assume that an image can be divided into two regions, such as the background region and object region, which is known as the bilevel thresholding image segmentation method [2]. In the case of an image containing more than one object, bilevel thresholding does not achieve the desired result [3]. On account of multilevel thresholding, we can accurately segment the image into different significant regions [4]. For traditional exhaustive methods, multilevel thresholding can be very time-consuming. It is an NP-hard optimization problem. In such cases, the metaheuristic algorithms are proposed to solve the optimal multilevel thresholding. Many related works are based on metaheuristic algorithms, such as the improved particle swarm optimization (IPSO) [5], the improved electromagnetism optimization algorithm (IEMO) [6], the modified artificial bee colony (MABC) [7] algorithm, the improved harmony search algorithm (IHSA) [8], the crow search algorithm (CSA) [9], the cuckoo search algorithm (CS) [10], the improved emperor penguin optimization (IEPO) [11], the improved flower pollination algorithm (IFPA) [12], the wind-driven optimization (WDO) [13], the hybrid Harris Hawks optimization (HHHO) [14], and the fuzzy adaptive gravitational search algorithm (FAGSA) [15]. Moreover, a number of modified and improved metaheuristic algorithms have been applied to multilevel thresholding [16,17,18].

The cuckoo search algorithm is a popular metaheuristic algorithm that was inspired by the egg-laying behavior of natural cuckoo birds [19]. More recently, CS has been widely used in feature selection [20], numerical optimization [21], data clustering [22], and many-objective optimization [23]. Studies have shown that CS is an effective algorithm for solving various optimization problems [24]. The successes recorded by the CS are that fewer parameters need to be adjusted for execution, and the robustness of the algorithm is perfect. However, although the CS algorithm has been well-applied for solving different practical application problems when dealing with complex optimization problems, the CS still needs to be improved to enhance the performance. An adaptive parameter strategy was proposed in the CS by Wang and Zhou. The experimental tests indicated that the proposed algorithm was superior to CS with fixed parameters [25]. Guerrero M et al. [26] proposed a fuzzy cuckoo search (FCS), in which a fuzzy system was designed to dynamically adjust the control parameters. The results demonstrated that the FCS outperformed the standard CS. Walton S et al. [27] presented a modified cuckoo search (MCS). In MCS, a dynamic parameter control strategy for step size α was used. The results showed that the MCS had advantage over DE, PSO, and CS. Wang G et al. [28] proposed a chaotic cuckoo search (CCS), in which 12 chaotic maps were used to adjust the step size of the CS. The experimental results showed that a suitable chaotic map was superior to the CS. Huang et al. proposed a fully informed cuckoo search algorithm (FICS). In FICS, a fully informed strategy was firstly proposed to improve particle swarm optimization. The proposed FICS was tested by four benchmark images; the results suggested that the FICS was better than other algorithms [29]. A hybrid adaptive cuckoo search squirrel search algorithm (ACSS) for brain MR image segmentation was proposed [30]. In ACSS, an adaptive step size strategy was used to improve the convergence and a new hybrid search was also adopted. The experimental results indicated that the ACSS was superior to CS, ACS, and SS. In a word, the standard CS can be categorized as adaptive, self-adaptive, and hybridizing according to the kinds of parameter control strategies. In conclusion, all operations are adopted to balance exploration and exploitation [31].

All the above-mentioned CS variants are aimed to improve the convergence speed and accuracy of the algorithm and then obtain the desired results when solving different optimization problems. The improvement of CS focused on the control parameters. In this paper, we propose novel parameter adaptation strategies to enhance the CS and then apply it to solve the optimal multilevel thresholding. The main contribution of this study is that two modifications are proposed to improve the standard CS: (1) the adaptive control parameters method and (2) the dynamic weighted random-walk strategy. We evaluate the performance of the ICS on six test images as well as seven well-known metaheuristic algorithms. Some measure indexes such as objective function value and standard deviation, PSNR, FSIM, and SSIM as well as the Wilcoxon rank sum and convergence performance are performed in the experiments.

The rest of the paper is organized as follows: Section 2 shows the theory of multilevel thresholding based on the Otsu method. In Sect. 3, the cuckoo search algorithm is described. The improved cuckoo search algorithm is shown in Sect. 4. Experimental results are discussed in Sect. 5. In Sect. 6, conclusions are drawn.

2 Segmentation based on between-class variance

A multilevel threshold value image segmentation method based on the image one-dimensional gray histogram is proposed. Based on that, the image can be segmented into different regions. The process of thresholding image segmentation is to obtain the best objective function value by employing an intelligent optimization algorithm and then obtaining approximate optimal thresholds. The multilevel thresholding image segmentation method is utilized to find the best possible threshold in the segmented histogram by meeting some criteria. In 1979, image thresholding based on the Otsu method was proposed. This method obtains the optimal solution by maximizing the objective function [32]. In the present work, Otsu’s nonparametric segmentation method, called between-class variance, is considered. In addition, some nonparametric criteria, such as Kapur's [33] and Tsallsi entropy [34], are used for image thresholding segmentation. A detailed description of the between-class variance method can be found in bilevel thresholding image segmentation. An image can be segmented into two classes, A1 and A2 (objects and background), by a threshold at a level “t.” Class A1 encloses the gray levels in the range 0–t − 1, and class A2 encloses the gray levels from t to L − 1. The probability distributions for gray levels A1 and A2 can be expressed as:

$$ A_{{1}} = \frac{{p_{0} }}{{\omega_{{1}} \left( t \right)}}...\frac{{p_{t - 1} }}{{\omega_{{1}} \left( t \right)}},\;\;A_{{2}} = \frac{{p_{t} }}{{\omega_{{2}} \left( t \right)}}...\frac{{p_{L - 1} }}{{\omega_{{2}} \left( t \right)}}\; $$
(1)

where pi is the gray-level probability,\(\omega_{{1}} \left( t \right) = \sum\nolimits_{i = 0}^{t - 1} {p_{i} ,\;\omega_{{2}} } \left( t \right) = \sum\nolimits_{i = t}^{L - 1} {p_{i} } ,{\text{and}}\;L = 256,\) and the mean levels μ1 and μ2 for A1 and A2 can be measured by:

$$ \mu_{{1}} = \sum\limits_{i = 0}^{t - 1} {\frac{{ip_{i} }}{{\omega_{{1}} \left( t \right)}}} ,\;\;\;\;\mu_{{2}} = \sum\limits_{i = t}^{L - 1} {\frac{{ip_{i} }}{{\omega_{{2}} \left( t \right)}}} $$
(2)

The average intensity (μT) of the entire image can be calculated by:

$$ u_{T} = \omega_{{1}} \mu_{{1}} + \omega_{{2}} u_{{2}} ,\;\;\;\;\;\omega_{{1}} + \omega_{{2}} = 1 $$
(3)

The objective function for the bilevel thresholding problem can be defined as:

$$ F_{t}^{{{\text{opt}}}} = \arg \max \left( {\delta_{{1}} + \delta_{{2}} } \right) $$
(4)

where \(\sigma_{{1}} = \omega_{{1}} \left( {u_{{1}} - u_{T} } \right)^{2} \;{\text{and }}\sigma_{{2}} = \omega_{{2}} \left( {u_{{2}} - u_{T} } \right)^{2} .\)

Bilevel thresholding can be extended to a multilevel thresholding problem by increasing the number of threshold values “m” as follows. Assume that there are “m” thresholds (t1, t2…,tm), which divide the image into “m + 1” classes: A1 with gray levels in the range 0–t − 1, A2 with enclosed gray levels in the range t1–t2 − 1…, and Am+1 with gray levels from tm to L − 1. The objective function for the multilevel thresholding problem can be measured by [35]:

$$ F_{t}^{{{\text{opt}}}} = \arg \max \left( {\delta_{{1}} + \delta_{{2}} + ... + \sigma_{{m + {1}}} } \right) $$
(5)

where \(\sigma_{{1}} = \omega_{{1}} \left( {u_{{1}} - u_{T} } \right)^{2} ,\sigma_{{2}} = \omega_{{2}} \left( {u_{{2}} - u_{T} } \right)^{2} \;,...,\sigma_{{m + {1}}} = \omega_{{m + {1}}} \left( {u_{{m + {1}}} - u_{T} } \right)^{2} .\)

3 Cuckoo search algorithm

The cuckoo search algorithm is a nature-inspired algorithm that was proposed by Yang in 2009. The CS mimics the process of cuckoo egg-laying. Cuckoos normally lay their fertilized eggs in host nests with the hope of their offspring being raised by proxy parents. Sometimes, the host identifies that the eggs in their nests do not belong to them. Under these circumstances, the foreign eggs are thrown out of the nests, or the whole nests are discarded. The CS optimization algorithm is generally based on the following three principles:

  1. 1.

    Interestingly, each cuckoo bird lays one egg at a time and randomly places its egg in a host bird's nest.

  2. 2.

    Usually, the best nests containing high-quality eggs are carried over to the next generations.

  3. 3.

    The number of available host nests is fixed. The host bird discovers foreign eggs with a probability pα, and the range of pα is from 0 to 1. Note that the best nests are selected for further calculations. For simplicity, principle 3 can be explained as follows: the n nests will be replaced by new nests with a probability pα.

Based on these three principles, the CS process can be summarized as follows:

While generating new solution \(x_{i}^{t + 1}\) for cuckoo i, a Lévy flight is performed [36]:

$$ x_{i}^{t + 1} = x_{i}^{t} + \alpha_{{0}} \left( {x_{i}^{t} - x_{{{\text{best}}}} } \right) \oplus {\text{Levy}}\left( {s,\lambda } \right) $$
(6)

where α0 is the step size, α0 > 0, and xbest represents the current optimal solution. Lévy flights are drawn from a Lévy distribution, which can be defined by:

$$ {\text{Levy}}\left( {s,\lambda } \right)\sim u = t^{ - \lambda } ,\;\;\left( {1 < \lambda \le 3} \right) $$
(7)

where

$$ {\text{Levy}}\left( {s,\lambda } \right) = \frac{{\lambda \Gamma \left( \lambda \right)\sin \left( {\pi \lambda /2} \right)}}{\pi }\;\frac{1}{{s^{1 + \lambda } }},\;\;\left( {s > > s_{0} > 0} \right) $$
(8)

where Γ(λ) is the standard gamma function with an index λ.

In the CS algorithm, the worst nest is abandoned with a probability pα, and a new nest is built with random walks by the following formula:

$$ x_{i}^{t + 1} = x_{i}^{t} + r\left( {x_{j}^{t} - x_{k}^{t} } \right) $$
(9)

where r represents a random number and \(x_{j}^{t}\) and \(x_{k}^{t}\) are the random solutions at iteration t. The pseudocode of the CS algorithm is summarized in Table 1.

Table 1 Pseudocode for the cuckoo search algorithm
Full size table

4 The improved cuckoo search algorithm

CS is also a metaheuristic global search algorithm that is widely used to solve different optimization problems, such as gray image segmentation [37] or color image segmentation [38]. The CS has fewer parameters compared to other algorithms. It is easy to set the parameter of the algorithm. Hence, CS may be useful for nonlinear problems and many-objective optimizations. Although CS is efficient, it has some drawbacks, such as time consumption and premature convergence for a number of real-world optimization problems. Therefore, the basic structure of the CS has been modified to improve its performance.

4.1 Adaptive control parameters

The control parameters are sensitive to the performance of the metaheuristic algorithms; a lot of parameter strategies are proposed to improve the performance. The control parameters like linear, piece-wise, or curve decrease with the generation, which is called adaptive parameter strategy [29], if the control parameters changed with the fitness value or optimization problem named self-adaptive strategy such as fuzzy parameter strategy and parameter archiving mechanism [16]. In CS, the parameters pα and α0 are introduced to help the algorithm find globally locally improved solutions. The parameters pα and α0 are very important parameters and can potentially be utilized in controlling the convergence rate. The original CS algorithm adopts a fixed value for both pα and α0. In facing different problems, the parameters should be adjusted based on personal experience. If the value of pα is small and the value of α0 is large, the performance of the algorithm will be poor and lead to a considerable increase in the number of iterations. If the value of pα is large and the value of α0 is small, the speed of convergence is high, but it may be unable to find the best solutions [31]. To improve the performance of the CS algorithm, we propose adaptive variables pα and α0. At the beginning of the iteration, the values of pα and α0 must be large enough to increase the diversity of the population. However, these values should decrease in the final generations. In this paper, we propose an adaptive control parameter strategy. The values of pα and α0 dynamically change with the number of generations and are expressed in the following equations:

$$ p_{\alpha } = p_{\alpha i} \cdot 2^{\tau } ,\;\tau = e^{{1 - \frac{{G_{m} }}{{G_{m} + 1 - G}}}} $$
(10)
$$ \alpha_{{0}} = 0.5*\exp \left( { - \frac{G - 1}{{G_{m} }}} \right) $$
(11)

where pαi is a predefined constant, Gm is the maximum number of iterations, and G is the current number of iterations. Figure 1 shows the parameter values changed with the number of generation when Gm = 1000, pai = 0.25.

Fig. 1
figure 1

The parameter values changed with the number of generations

Full size image

4.2 A dynamic weighted random-walk strategy

A new nest built with random walks often leads to a slow convergence rate and vibration. To enhance the local search, we propose that a larger ω leads to greater control of exploration or exploitation of host nest positions (solutions). Based on formulas 12 and 13, ω linearly decreases from a relatively large value to a small value throughout the course so that the CS can effectively enhance the local search ability.

$$ x_{i}^{t + 1} = \omega x_{i}^{t} + r\left( {x_{j}^{t} - x_{k}^{t} } \right) $$
(12)
$$ \omega = \omega_{\max } - \frac{{G\left( {\omega_{\max } - \omega_{\min } } \right)}}{{G_{m} }} $$
(13)

where ω is a weighted coefficient. ωmax and ωmin are user-defined constants. Correspondingly, the pseudocode of the improved CS algorithm is summarized in Table 2.

Table 2 Pseudocode for an improved cuckoo search algorithm
Full size table

5 Experiments and analysis

In this section, the performance of the proposed algorithm was evaluated by six test images. In the following, the objective function value, image segmentation quality, and Wilcoxon rank sum are compared with FCS [27], MCS [28], CS [10], FICS [29], ACSS [30], FAGSA [16], and IEPO [11].

5.1 Experimental setting

A maximum between-class variance based on the proposed ICS was tested under a set of benchmark images. Six classic images from the Benchmarks 500 named “Hunter,” “House,” “Baboon,” “Couple,” “Lena,” and “Peppers” are used in the experiment. The size of all images is 512 × 512. The test images and corresponding histograms are shown in Fig. 2.

Fig. 2
figure 2

The test images and corresponding histograms

Full size image

The experiments were performed on a Lenovo Laptop with an Intel Core i7 processor and 8 GB memory, running the Windows 10 operating system. The algorithm was carried out by MATLAB R2019a. In the next subsections, the ICS will be compared with CS variants such as CS, FCS, MCS, FICS, ACSS and other two newly proposed metaheuristic algorithms FAGSA and IEPO. The comparison with different algorithms was mainly used to test the advantages of the ICS. For the sake of fairness, all the algorithms were performed under the same conditions. Generally, the thresholds were set as m = 2, 3, 4, 5. The number of maximum iterations was 300; the population size was 30. All experiments were repeated 25 times. The corresponding parameters used for the presented four algorithms are listed in Table 3, which originate from related references.

Table 3 Parameters of the heuristic algorithms
Full size table

5.2 Results on the objective function value

As the aim of multilevel thresholding is to maximize the given objective function, the objective function value obtained by the involved algorithms directly shows the algorithm's performance. In detail, the mean objective function values are shown in Table 4 (the optimal value is marked in bold) and Fig. 3 (the average objective function value), where “m” stands for the number of thresholds. The corresponding standard deviation values are given in Table 5.

Table 4 Comparison of the mean objective function values
Full size table
Fig. 3
figure 3

The average objective function values of the algorithms over all images

Full size image
Table 5 Results of the standard deviation of objective function values
Full size table

From Table 4 and Fig. 3, it is clear that our algorithm outperformed the other methods, and the ICS obtained the best results in 22 cases (total 30 cases), whereas MCS was the second-best but did not show an advantage in any case when compared meticulously with the other six algorithms. However, the differences in the maximum objective function values obtained by the eight algorithms are not more than 10. Correspondingly, the standard deviation of the objective function values is shown in Table 5; the results show that the stability of the ICS was the best, which obtained the best results in 21 cases (total 30 cases). However, the stability of ACSS, FICS, FCS, and MCS was worse than that of the ICS. From the result analysis, the proposed algorithm is better than other algorithms in most case, but for the image “Baboon,” the algorithm did not perform well, but the difference of the objective function values is small.

5.3 Quality measures of segmented images

To further verify the performance of the proposed algorithm, the time consumption (seconds) and appropriate performance indicators, including the peak signal-to-noise ratio (PSNR), structural similarity (SSIM), and feature similarity (FSIM), were calculated to evaluate the corresponding image segmentation performance of the results. Image quality measurement was performed using PSNR, which is defined as [39]:

$$ {\text{PSNR}} = 20\log_{10} \left( {\frac{{255^{{}} }}{{{\text{RMSE}}}}} \right),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left( {{\text{dB}}} \right) $$
(14)

where

$$ {\text{RMSE}} = \sqrt {\frac{{\sum\nolimits_{i = 1}^{M} {\sum\nolimits_{j = 1}^{N} {\left( {I\left( {i,j} \right) - C\left( {i,j} \right)} \right)^{2} } } }}{M \times N}} $$
(15)

and C and I are original and segmented images of size M × N, respectively. A higher value of PSNR indicates a better quality segmented image.

The SSIM was used to compare the structures of the original and segmented images. The SSIM index is described as follows [40]:

$$ {\text{SSIM}}\left( {C,I} \right) = \frac{{\left( {2\mu_{C} \mu_{I} + C_{1} } \right)\;\left( {2\delta_{CI} + C_{2} } \right)}}{{\left( {\mu_{C}^{2} + \mu_{I}^{2} + C_{1} } \right)\;\left( {\delta_{C}^{2} + \delta_{I}^{2} + C_{2} } \right)}} $$
(16)

where μC and δC represent the pixel mean and variance, respectively, of the original image; μI and δI represent the pixel mean and variance, respectively, of the segmented image; δCI is the covariance of the original image and the segmented image; and C1 and C2 are constants, where C1 = C2 = 6.5025. A higher value of SSIM indicates better performance. In addition, the FSIM is employed to measure the feature similarity between two images. It is calculated between two images C and I as [41]:

$$ {\text{FSIM}} = \frac{{\sum\nolimits_{x \in \Omega } {S_{L} \left( x \right)PC_{m} \left( x \right)} }}{{\sum\nolimits_{x \in \Omega } {PC_{m} \left( x \right)} }} $$
(17)

where

$$ \begin{gathered} S_{L} \left( x \right) = S_{{{\text{PC}}}} \left( x \right)S_{G} \left( x \right); \hfill \\ S_{{{\text{PC}}}} \left( x \right) = \frac{{2{\text{PC}}_{1} \left( x \right){\text{PC}}_{2} \left( x \right) + T_{1} }}{{{\text{PC}}_{1}^{2} \left( x \right) + {\text{PC}}_{2}^{2} \left( x \right) + T_{1} }}; \hfill \\ S_{G} \left( x \right) = \frac{{2G_{1} \left( x \right)G_{2} \left( x \right) + T_{2} }}{{G_{1}^{2} \left( x \right) + G_{2}^{2} \left( x \right) + T_{2} }}; \hfill \\ {\text{PC}}_{m} \left( x \right) = \max \left\{ {{\text{PC}}_{1} \left( x \right),{\text{PC}}_{2} \left( x \right)} \right\}. \hfill \\ \end{gathered} $$
(18)

T1 and T2 are constants. Here, we choose T1 = 0.85 and T2 = 160 in the experiments, G(x) represents the gradient magnitude of an image, and PC(x) is the phase congruency of an image [12]. A higher value of FSIM indicates better performance.

Furthermore, Table 6 and Fig. 4 display the PSNR index values, Table 7 and Fig. 5 show the SSIM index values, and Table 8 and Fig. 6 show the FSIM index values. The experimental results show that the ICS obtained the best values in 23 cases, 25 cases, and 25 cases for PSNR, SSIM, and FSIM, respectively. The experimental results show that the ICS outperforms the other seven algorithms in image segmentation quality, but IEPO, MCS, ICS, and FICS have little difference on PSNR, SSIM, and FSIM.

Table 6 Comparison of the mean PSNR
Full size table
Fig. 4
figure 4

The average PSNR values of the algorithms over all images

Full size image
Table 7 Comparison of the mean SSIM
Full size table
Fig. 5
figure 5

The average SSIM values of the algorithms over all images

Full size image
Table 8 Comparison of the mean FSIM
Full size table
Fig. 6
figure 6

The average FSIM values of the algorithms over all images

Full size image

5.4 Statistical results analysis

A Wilcoxon rank sum is performed to verify the experimental results, which has been conducted with 5% significance level [42]. The null hypothesis is expressed as: There is no significant difference between the ICS algorithm and other seven algorithms. Nevertheless, the alternative hypothesis seems a significant difference among them. Based on the Wilcoxon rank sum, the p value is used to judge the null hypothesis whether to accept the null hypothesis or not. If the p value is greater than 0.05, the null hypothesis will be rejected; it implies there is no significant difference between all algorithms. On the contrary, if the p value is less than 0.05, the alternative hypothesis will be accepted. Table 9 shows the p value results, which is executed on the objective function value, PSNR, SSIM, and FSIM. It can be summarized from Table 9 that there is no significantly difference between ICS and FCS MCS, CS, FICS, ACSS, FAGSA, and IEPO for all metrics. Analyzing the whole data, the ICS has a remarkable improvement, and it is feasible and effective for multilevel thresholding image segmentation.

Table 9 Wilcoxon rank-sum test results
Full size table

5.5 Convergence performance

The nature-inspired metaheuristic algorithms are stochastic process that execute randomly operations. For this reason, it is not practical to conduct a complexity analysis from a deterministic point of view. However, it is possible to have an idea of this complexity through the mathematical notation called Big O notation [43]. To find the optimal solutions, the proposed metaheuristic algorithms have an initialization stage and a subsequent stage of iterations. The computational complexity of nature-inspired algorithm depends upon n, Popsize and Maxiter:

$$ {\text{Computation complexity}} = {\text{ O}}\left( {n \times {\text{Popsize}} \times {\text{Maxiter}}} \right) $$
(19)

For all the proposed metaheuristic algorithms, the maximum computational complexity in terms of Big O notation is

$$ {\text{Computation complexity}} = {\text{ O}}\left( {n \times {3}0 \times {3}00} \right) = {\text{O}}\left( {{9}000n} \right) $$
(20)

From the analysis of computational complexity, it may be difficult to judge the performance of each algorithm. To further measure the ICS, the convergence performance on 5 levels of thresholding was also studied. For the sake of fairness, all the parameters and settings keep it the same as the previous setting. In the same way, the six test images are tested to exemplify the performance. The results are shown in Fig. 7. It can be found in Fig. 7 that most of the algorithms like FCS, MCS, CS, FICS, ACSS, FAGSA, and IEPO encountered the premature convergence, whereas only ICS overcame the problems and obtained the best objective function values. It also demonstrated that the success of the improved CS is effective. In conclusion, the proposed algorithm achieved significant improvements based on the standard CS, and the other seven algorithms seem a little difference in convergence performance.

Fig. 7
figure 7

The convergence performance of all algorithms

Full size image

6 Conclusion and future work

This paper proposed an improved cuckoo search algorithm for multilevel thresholding image segmentation. Two modifications were adopted. First, an adaptive control parameter method was utilized to perform effective exploration. Second, the dynamic weighted random-walk strategy was used to improve exploitation and enhance the convergence. The experiments demonstrated the success of our modification. In the experiments, the results show that the proposed algorithm is better than other seven state-of-the-art metaheuristic algorithms for multilevel thresholding in terms of the objective function value, standard deviation PSNR, SSIM, FSIM, Wilcoxon rank sum and convergence performance. Future works of this study will focus on studying the performance of the proposed algorithm on remote sensing images.