Backtracking search algorithm for color image multilevel thresholding

Abstract

Multilevel thresholding of the color images such as natural and satellite images becomes a challenging task due to the inherent fuzziness and ambiguity in such images. To address this issue, a modified fuzzy entropy (MFE) function is proposed in this paper. MFE function is the difference of adjacent entropies, which is optimized to provide thresholding levels such that all regions have almost equal entropies. To improve the performance of MFE, backtracking search algorithm is used. The numerical and statistical results indicate that MFE-BSA has higher peak signal-to-noise ratio, lower mean square error for all the images at different thresholding levels. Moreover, structural and feature similarity indices for MFE-BSA are closer to unity and the average fitness value obtained using MFE-BSA is minimum (lesser than 0.5). Overall, MFE-BSA shows very good segmentation results in terms of preciseness, robustness, and stability.

1 Introduction

Over the years, various segmentation approaches have been compiled to segment various types of images [1,2,3,4,5]. However, among all the existing approaches, image thresholding have been adopted widely owing to its simplicity, accuracy and better performance.

Conventional entropy-based nonparametric thresholding approaches [6, 7] fails to segment the color images efficiently as the threshold level increases. Therefore, meta-heuristics optimization algorithms have been coupled with the entropy functions to improve thresholding performance [8, 9]. In last few years, multilevel image segmentation has gained wide popularity by using meta-heuristics algorithms such as artificial bee colony (ABC) [9], bacterial foraging optimization (BFO) [10], krill herd algorithm [11], particle swarm optimization (PSO) [12], modified firefly algorithm (FA) [13] and various other nature-inspired and quantum-inspired optimization techniques [14, 15].

Nowadays, satellite images are vital in various applications involving geographical information systems, astronomy and geoscience studies [16]. Therefore, multilevel segmentation approaches based on modified ABC [17], genetic algorithm [18], differential algorithm [19], Cuckoo search [20] and other nature-inspired algorithms [16, 21] have been presented in the literature to efficiently deal with the satellite images. For the multilevel thresholding of colored satellite images, recently, Bhandari et al. [22] proposed Tsalli’s entropy-based different evolutionary algorithms and Pare et al. [23] proposed a new energy curve-based entropy functions optimized by CS algorithm and its variant. Later, Pare et al. [24] presented GLCM and CS satellite image segmentation algorithm.

Among various optimization algorithm, a simple and effective structure-based backtracking search algorithm (BSA) has emerged as a successful algorithm for many multimodal optimization problems [25, 26]. In addition, the proposed algorithm is also compared with BFO algorithm using MFE as objective function.

2 Backtracking search optimization algorithm

BSA undergoes five steps: initialization, selection-I, mutation, crossover and selection-II [26]. The general flowchart of BSA is shown in Fig. 1.

2.1 Initialization

PopulationP is initialized by BSA fori = 1,2,3,...,N and j= 1,2,3,...,D through Eq. (1):

$$\begin{aligned} P_{i,j} \sim U(\mathrm{low}_j ,\mathrm{up}_j ), \end{aligned}$$

(1)

N and D represent population size and problem dimension, respectively. $P_{i,j}$ represents target individual in the population P and U shows uniform distribution.

2.2 Selection-I

In this process, historical population oldP which computes the search direction is determined. After oldP is determined, permutting function is used to change the order of the individuals in oldP randomly after determining it.

2.3 Mutation

The initial form of the trial population ‘Mutant’ has been generated using BSA’s mutation process. For computing search direction matrix, historical population is used

2.4 Crossover

In this process, final form of trial population T is generated. After the crossover process, individual may exceed the search space boundaries.

Fig. 1

General structure of BSA algorithm [25]

2.5 Selection-II

$P_\mathrm{is}$ values are updated by a greedy selection strategy that uses $T_\mathrm{is}$ that have better fitness values than corresponding $P_\mathrm{is}$ values. Global minimum value is replaced by the best individual of $P(P_\mathrm{best})$ when $P_\mathrm{best }$value is better than global minimum value.

Detailed description of BSA is given in [25, 26].

Fig. 2

Membership function graph

Fig. 3

Original color images a Satellite image 1, b Satellite image 2, c Satellite image 3, d Lena, e Barbara and f Sailboat (color figure online)

Table 1 Comparison of PSNR, MSE and CPU time (in seconds) for energy-Tsalli’s-CS, Tsalli’s-CS, MFE-BFO, and proposed (MFE-BSA) algorithms

3 Proposed methodology

In image segmentation field, fuzzy entropy measures the information quantity of the segmented image.

3.1 Modified fuzzy entropy function

Assume that the imageI with a size of $M\times N$ is divided into dark (d), medium (m), bright (b) regions using thresholds $t_{1}$ and $t_{2}$. $E_\mathrm{d}$, $E_\mathrm{m}$, and $E_\mathrm{b}$ are the three regions that comprises pixels with high gray levels, middle gray levels, and low gray levels, respectively. Let, Ï$_{3}$= {$E_\mathrm{d}$, $E_\mathrm{m}$, $E_\mathrm{b}$ } represents unknown probabilistic partition of image. Then Ï $_{3}$ is an unknown probability partition with distribution:

$$\begin{aligned} p_\mathrm{d} =P(E_\mathrm{d} );\hbox { }p_\mathrm{m} =P(E_\mathrm{m} );\hbox { }p_\mathrm{b} =P(E_\mathrm{b} ). \end{aligned}$$

(2)

In order to divide an image into three regions (fuzzy sets), three trapezoidal membership functions ($\mu _\mathrm{d}(k)$, $\mu _\mathrm{m}(k)$, and $\mu _\mathrm{b}(k))$ are selected to classify image pixels. Figure 2 shows the fuzzy partition of the image formed by using membership functions given in Eq. (3).

$$\begin{aligned} \mu _\mathrm{d} \hbox {(}k\hbox {)}= & {} \left\{ {\begin{array}{ll} 0 &{}\quad k\le u_1\\ \frac{\hbox {(}k-u{ }_1\hbox {)}^{2}}{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}v_1 -u_1 )}&{}\quad u_1<k\le v_1 \\ 1-\frac{\hbox {(}k-w_1 \hbox {)}^{2}}{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}w_1 -v_1 \hbox {)}} &{}\quad v_1<k\le w_1 \\ \hbox {1 } &{} \quad v_1<k\le w_2 \end{array}} \right. \nonumber \\ \mu _\mathrm{m} \hbox {(}k\hbox {)}= & {} \left\{ {\begin{array}{ll} 1 &{}\quad k\le u_1 \\ 1-\frac{\hbox {(}k-u_1\hbox {)}^{2}}{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}v_1 -u_1 \hbox {)}} &{}\quad u_1<k\le v_1 \\ \frac{\hbox {(}k-w_1 \hbox {)}^{2}}{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}w_1 -v_1 \hbox {)}} &{}\quad v_1<k\le w_1 \\ 0 &{}\quad k>w_1 \\ \end{array}} \right. \nonumber \\ \mu _\mathrm{b} \hbox {(}k\hbox {)}= & {} \left\{ {\begin{array}{ll} 0 &{}\quad k\le u_2 \\ \frac{\hbox {(}k-u_2\hbox {)}^{2}}{\hbox {(}w_2 -u_2 \hbox {)}\,{*}\,\hbox {(}v_2 -u_2 \hbox {)}} &{}\quad u_2<k\le v_2 \\ 1-\frac{\hbox {(}k-w_2 \hbox {)}^{2}}{\hbox {(}w_2 -u_2 \hbox {)}\,{*}\,\hbox {(}w_2 -v_2 \hbox {)}} &{}\quad v_2 <k\le w_2 \\ 1 &{}\quad k>w_2 \\ \end{array}} \right. \end{aligned}$$

(3)

The shape of these three membership functions are determined by using the fuzzy parameters ($u_{1}$,$v_{1}$,$w_{1}$,$u_{2}$,$v_{2}$,$w_{2})$ which satisfy the condition 0 $\le u_{1}<v_{1}<w_{1}<u_{2}<v_{2}<w_{2}\le$ 255. In this paper, the optimal fuzzy parameters are determined by minimizing MFE. Once the optimal parameters combination is determined, shape of membership functions shown in Fig. 2 is determined.

Table 2 Comparison of SSIM, FSIM and fitness values for energy-Tsalli’s-CS, Tsalli’s-CS, MFE-BFO and proposed (MFE-BSA) algorithms

Fuzzy entropy function for each class ($E_\mathrm{d}$, $E_\mathrm{m}$, and $E_\mathrm{b})$ can be represented as:

$$\begin{aligned} H_\mathrm{d}= & {} -\sum _{k=0}^{255} {\frac{p_k \,{*}\,\mu _\mathrm{d} \hbox {(}k\hbox {)}}{p_\mathrm{d} }}\, {*}\,\ln \left( {\frac{p_k \,{*}\,\mu _\mathrm{d} \hbox {(}k\hbox {)}}{p_\mathrm{d} }} \right) \nonumber \\ H_\mathrm{m}= & {} -\sum _{k=0}^{255} {\frac{p_k \,{*}\,\mu _\mathrm{m} \hbox {(}k\hbox {)}}{p_\mathrm{m} }}\, {*}\,\ln \left( {\frac{p_k \,{*}\,\mu _\mathrm{m} \hbox {(}k\hbox {)}}{p_\mathrm{m} }} \right) \nonumber \\ H_\mathrm{b}= & {} -\sum _{k=0}^{255} {\frac{p_k \,{*}\,\mu _\mathrm{b} \hbox {(}k)}{p_\mathrm{b} }}\, {*}\,\ln \left( {\frac{p_k \,{*}\,\mu _\mathrm{b} \hbox {(}k\hbox {)}}{p_\mathrm{b} }} \right) , \end{aligned}$$

(4)

where, probability of each of the classes are:

$$\begin{aligned} p_\mathrm{d}= & {} \sum _{k=0}^{255} {p_k } \,{*}\,\mu _\mathrm{d} \hbox {(}k\hbox {)} \nonumber \\ p_\mathrm{m}= & {} \sum _{k=0}^{255} {p_k }\, {*}\,\mu _\mathrm{m} \hbox {(}k\hbox {)} \nonumber \\ p_\mathrm{b}= & {} \sum _{k=0}^{255} {p_k } \,{*}\,\mu _\mathrm{b} \hbox {(}k\hbox {) }, \end{aligned}$$

(5)

$p_k =P\hbox {(}D_k \hbox {)}=h_k , \,\,h_{k}$ is the histogram of the image at gray-level value k.

Fig. 4

Graphical comparison between energy-Tsalli’s-CS, Tsalli’s-CS, MFE-BFO and proposed (MFE-BSA) using a PSNR, b MSE, c CPU time, d SSIM and e fitness values (color figure online)

To determine the optimal thresholds, MFE function is defined in Eq. (6). In MFE, minimization on the sum of difference of entropies of adjacent thresholded divisions of the histogram of image matrixes is used.

$$\begin{aligned}&H\hbox {(}u_1 ,v_1 ,w_1 ,u_2 ,v_2 ,w_2 \hbox {)}\nonumber \\&\quad =abs\hbox {(}H_\mathrm{d} -H_\mathrm{m} )+(absH_\mathrm{m} -H_\mathrm{b} \hbox {)} +\,\hbox {(}absH_\mathrm{b} -H_\mathrm{d} \hbox {)}.\nonumber \\ \end{aligned}$$

(6)

The MFE varies along with the fuzzy parameters $u_{1}$, $v_{1}$, $w_{1}$, $u_{2}$, $v_{2}$, $w_{2}$. Thus, the optimum fuzzy parameter combination is determined by minimizing the MFE, H ($u_{1}$, $v_{1}$, $w_{1}$, $u_{2}$, $v_{2}$, $w_{2})$ so that all the regions can have almost equal entropies:

$$\begin{aligned} \varphi \hbox {(}u_1 ,v_1 ,w_1 ,u_2 ,v_2 ,w_2 \hbox {)}= & {} \mathrm{arg} \min \nonumber \\&{\{H(u_1 ,v_1 ,w_1 ,u_2 ,v_2 ,w_2)\}}.\nonumber \\ \end{aligned}$$

(7)

The optimal fuzzy parameters find desired threshold values ($t_{1}$ and $t_{2})$ located at crossover points of membership function curves as shown in Fig. 2. The gray level, whose membership is 0.5, is selected as the threshold. Consequently, the thresholds can be computed as:

$$\begin{aligned} \mu _\mathrm{d} \hbox {(}t_1 \hbox {)}= & {} \mu _\mathrm{m} \hbox {(}t_1 \hbox {)}=0.5, \nonumber \\ \mu _\mathrm{m} \hbox {(}t_2 \hbox {)}= & {} \mu _\mathrm{b} \hbox {(}t_2 \hbox {)}=0.5. \end{aligned}$$

(8)

The solution can be obtained on the basis of Eq. (3), as:

$$\begin{aligned} t_1= & {} \left\{ {\begin{array}{ll} u_1 +\sqrt{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}v_1 -u_1 \hbox {)}/2} &{} \hbox { (}u_1 + w_1 \hbox {)/2}\le v_1 \le w_1, \\ w_1 -\sqrt{\hbox {(}w_1 -u_1 \hbox {)}\,{*}\,\hbox {(}w_1 -v_1 \hbox {)}/2} &{} \hbox { (}u_1 \le v_1 \le \hbox {(}u_1 +w_1 \hbox {)}/2 \\ \end{array}} \right. \nonumber \\ t_2= & {} \left\{ {\begin{array}{ll} u_2 +\sqrt{\hbox {(}w_2 -u_2 \hbox {)}\,{*}\,\hbox {(}v_2 -u_2 \hbox {)}/2} &{} \hbox { (}u_1 +w_1 \hbox {)/2}\le v_1 \le w_1 \\ w_2 -\sqrt{\hbox {(}w_2 -u_2 \hbox {)}\,{*}\,\hbox {(}w_2 -v_2 \hbox {)}/2}&{} \hbox { (}u_2 \le v_2 \le \hbox {(}u_2 +w_2 \hbox {)}/2. \\ \end{array}} \right. \nonumber \!\!\!\!\!\\ \end{aligned}$$

(9)

The two-level thresholding presented can be extended to three and more levels based on the segmentation problem. The above methodology can be extended for n-level thresholding, the n number of threshold values are dependent on optimal fuzzy parameters $u_{1}$,$v_{1}$,$w_{1}$,$u_{2}$,$v_{2}$,$w_{2,}$...,$u_{n}$,$v_{n}$,$w_{n}$, determined by the minimum entropy criterion:

$$\begin{aligned}&\varphi (u_1 ,v_1 ,w_1 ,\ldots ,u_n ,v_n ,w_n )=\mathrm{arg} \min \nonumber \\&\quad \left( {H(u_1 ,v_1 ,w_1 ,\ldots ,u_n ,v_n ,w_n )} \right) . \end{aligned}$$

(10)

The MFE principle proposed in this paper is more universal. However, the numbers of fuzzy parameters to be optimized increase as the thresholding level increases, so the proposed fitness function becomes computationally complex and converges slowly. Therefore, BSA is employed to compute the best combination of fuzzy parameters that can obtain minimum entropy value. BSA eliminates the redundant computations, consequently reducing the computational cost of MFE.

Fig. 5

Multilevel segmented color images obtained for satellite image 1 at segmentation levels 3, 5, 8 and 12 using energy-Tsalli’s-CS, Tsalli’s-CS, MFE-BFO and proposed (MFE-BSA) (color figure online)

Fig. 6

Multilevel segmented images obtained for colored satellite and natural test images at level-5 using a energy-Tsalli’s-CS, b Tsalli’s-CS, c MFE-BFO and d proposed (MFE-BSA) (color figure online)

3.2 BSA based multilevel thresholding algorithm

In this paper, the following steps have been undertaken to obtain color image multilevel through MFE-BSA:

Step 1 :

Extract the red, green and blue pixel matrixes from an input image.

Step 2 :

For each of the individual image matrixes, obtain the histogram distributions, and then set the number of discrete levels for the image to be segmented.

Step 3 :

Set the required control parameters (N, D, mixrate, low$_{1:D}$, up$_{1:D}$, maximum iterations) for BSA.

Step 4 :

Input image histogram and number of thresholds.

Step 5 :

Initialize the population for basic components of color image (red, green and blue) using randomly chosen gray-level pixel intensity values between 0 and 255.

Step 6 :

For each of the color components, form the required number of classes from the corresponding position of every particle in population P. Form each of the class by using pre-defined number of threshold values as pixel intensity from image.

Step 7 :

Obtain best fuzzy parameters combination using BSA algorithm that can minimize the fitness function.

Step 8 :

Determine the threshold values and the corresponding segmented image.

4 Results and discussion

All the experimental results evaluated on three test colored natural images and three satellite images (adopted from www.visibleearth.NASA.gov). The test images are shown in Fig. 3. All the experiments are conducted using MATLAB R2017a on a personal computer with 3.4 GHz Intel core-i7 CPU, 8 GB RAM running on Windows 10 system.

For a fair comparison between the performances of the algorithms, population size and number of generations are set as 20 and 300, respectively, for all optimization algorithms. Other control parameter specifications are: In BSA, only control parameter mixrate is set as 1 [25]. For BFO: maximum number of chemotactic steps ($N_\mathrm{c})$, swims ($N_\mathrm{s})$, reproduction steps ($N_\mathrm{re})$ and elimination-dispersal events ($N_\mathrm{ed})$ are selected as 10, 5, 4 and 4, respectively [10]. The swarming coefficient $d_\mathrm{attract}$, $x_\mathrm{attract}$, $h_\mathrm{repellent}$, $x_\mathrm{repellent }$ are 0.1, 0.2, 0.1 and 10, respectively. For CS algorithm, step size ($\alpha )$, mutation probability ($p_{a})$, and scale factor ($\beta$) are set as 1, 0.25, and 1.5 respectively [23].

The segmented results are evaluated in terms of peak signal-to-noise ratio (PSNR), mean square error (MSE), computation time (CPU time in seconds), feature similarity index (FSIM), structural similarity index (SSIM) and fitness value. As meta-heuristic algorithms deals with randomness, the best quantitative results obtained by algorithms in 10 different runs are shown in Tables 1 and 2.

4.1 Comparison based on PSNR and MSE

To measure the performance of compared algorithms in terms of strength and accuracy, PSNR and MSE are shown in Table 1. It can be seen that MFE-BSA has obtained highest PSNR and lowest MSE. This shows that MFE-BSA shows better multilevel thresholding of complex colored images (satellite and natural image) possessing fuzziness and ambiguity in nature. MFE-BFO algorithm and Tsalli’s-CS have also obtained satisfactory outcomes than energy-Tsalli’s-CS. Moreover, on increasing the thresholding levels, PSNR and MSE further improve.

4.2 Comparison based on computation complexity

To measure the computational complexity or speed of all algorithms, CPU time (in seconds) is shown in Table 1. The CPU time of the Tsalli’s-CS is lowest among all other techniques. However, the proposed algorithm takes higher time than Tsalli’s-CS. Result show that MFE-BSA has significantly lesser computational time than MFE-BFO. The computational complexity of the energy-Tsalli’s-CS is highest. Table 1 shows that as the threshold levels increase, CPU time of algorithms increases as well.

4.3 Comparison based on SSIM and FSIM

Similarity index such as FSIM and SSIM shown in Table 2 is evaluated to measure the similarity among the original and segmented image. Table 2 shows that on increasing the thresholding levels, SSIM and FSIM approach closer to unity.

4.4 Comparison based on fitness values

The segmentation results depend majorly on the fitness function to be optimized. From the values indicated in Table 2, MFE-BSA has gain minimum fitness value followed by MFE-BFO. This is due to the fuzzy-based mathematical formulation of the MFE function. The minimum fitness value indicates better searching ability of the algorithm in obtaining accurate thresholds.

It is perceptible from the values in Tables 1 and 2 that MFE-BSA has given most promising results in terms of accuracy, robustness and efficiency. This can be attributed to the good explorational and exploitational property of the BSA algorithm in contrast to BFO and CS algorithm. Based on increasing performance, compared algorithms can be arranged as: Energy-Tsalli’s-CS < Tsalli’s-CS < MFE-BFO < MFE-BSA. In terms of increasing CPU time: Tsalli’s-CS < MFE-BSA < MFE-BFO < energy-Tsalli’s-CS. The heavy computation workload of the MFE-BSA that grows exponentially with the number of thresholds would limit the real-time multilevel thresholding applications. Still results indicate that proposed algorithm effectively and efficiently searches optimal fuzzy parameters and optimal threshold values at various segmentation levels based on histogram of color images. The graphical results indicated in Fig. 4 also justify the numerical results determined in Tables 1 and 2 showing best performance of proposed MFE-BSA algorithm.

4.5 Qualitative performance evaluation

For the visual interpretation of the performance, a detailed qualitative validation of segmented images with 3-level, 5-level, 8-level and 12-level thresholding using energy-Tsalli’s-CS, Tsalli’s-CS, MFE-BFO and MFE-BSA are demonstrated in Figs. 5 and 6. Figure 6 represents the segmented results obtained through all the algorithms at segmentation level 5. From the results in Fig. 5, it can be seen that segmentation is much smoother and more uniform at higher threshold levels as compared to levels 3 and 5. On comparing the segmentation results in Figs. 5 and 6, it can be depicted that the proposed MFE-BSA algorithm yields adequate segmentation with more accuracy and better quality. As an example, consider the satellite image 1 shown in Fig. 5. The objects in the image are much better and become more interpretable and identifiable at $m>$ 5 than at m = 2. Moreover, it can be observed from Fig. 5 that at higher dimensions, the quality of the thresholded images gets superior as they resemble original image.

5 Conclusions

In this paper, a new multilevel thresholding approach has been proposed using a MFE function and BSA algorithm. The objective and subjective evaluation of experimental results reveal that the proposed algorithm (MFE-BSA) obtained: (1) best PSNR and minimum MSE values. The average PSNR value for the proposed algorithm obtained is 18.456 approximately, which is better than the values of MFE-BFO and Tsalli’s-based approaches. The average PSNR values obtained by energy-Tsalli’s-CS and Tsalli’s-CS is lower, nearly 12.4351 and 14.566 (2) best segmentation quality shown by minimum mean fitness values which is around 0.3125. MFE-BFO has slightly higher fitness values than MFE-BSA. The energy-Tsalli’s-CS has obtained much larger fitness values with an average value of 5.1245 and 2.5425 (3) SSIM and FSIM values closer to unity which shows higher accuracy (4) average computation time of MFE-BSA is although higher than the Tsalli’s-CS approach.