Study of a Firefly Meta-Heuristics for Multithreshold Image Segmentation

order, where d and n are the number of thresholds and histogram bins respectively. It is computationally expensive to calculate the results for $d \geq 3$ .


One important issue is to define the number of thresholds required to obtain a segmentation result as close as possible to that obtained manually. The answer seems subjective and dependent on cognitive factors that are outside the scope of this paper. Thus, the database used for comparison of the results consists of several images that were manually segmented during psychophysical experiments that were defined and performed in [12]. Moreover, the results will be compared in two directions. First, we compare the results of the exhaustive segmentation with the respective manual one. Then, we compare the results of the manual segmentation with the ones obtained with the Firefly meta-heuristics, allowing us to draw a comparison between both methods used.

Although answering cognitive questions is not the purpose of this paper, the exhaustive search of the entire result space, allows us to observe the minimum amount of thresholds required to obtain the closest result to the manual segmentation. This lower limit can be used for any segmentation algorithms besides those cited in this paper. The method used to compute the threshold-based multi segmentation with the Firefly meta-heuristics is shown in Fig. 1.



A329170_1_En_17_Fig1_HTML.gif


Fig. 1
Proposed comparison methodology scheme. The first row shows an example of original image and its manual segmentation taken as a basis of comparison


A329170_1_En_17_Fig2_HTML.gif


Fig. 2
Adapted from [24]. Automatic q value calculation. In this figure it is possible to see that the optimum value of q is 0.5



3 Firefly Meta-Heuristics


The Firefly (FF) algorithm was proposed by Xin-She Yang [13] and is a meta-heuristics inspired on the fireflies behavior, which are attracted among themselves according to their natural luminescence.

After their interactions, convergence is achieved through the creation of fireflies clusters, on which the brighter attract the less bright ones under certain restrictions, such as: (i) all fireflies are unisex so that one firefly will be attracted to any other fireflies regardless of their sex; (ii) attractiveness is proportional to their brightness, thus for any two flashing fireflies, the less bright one will move towards the brighter one, remembering that the glow dimishes as the distance between them increases; (iii) if, for any given firefly, there isn’t any other brighter firefly, than it moves randomly.

The general idea is modeling a non-linear optimization problem by associating each problem’s variable to a firefly and make the objective evaluation depending on these variables, which are associated to the fireflies brighten. Then, iteratively, the variables are updated (their brightens) under preestablished rules until the convergence to a global minimum. Generically, it is accomplished at each generation, according to the following main steps:



  • bright evaluation;


  • compute all distances between each par of fireflies;


  • move all fireflies one toward all others, according to their brightens;


  • keep the best solution (the brighter firefly);


  • generate randomly new solutions;

The kernel of the algorithm is its Z-function evaluation, which depends on the current problem. Specifically for multi-level thresholding problem, as proposed in [13, 11] and [14], each firefly is considered a d-dimensional variable, where each dimension is a distinct threshold, partitioning the histogram space. In the specific case of the reference [14], the goal is to minimize an objective function under the non-extensive Tsallis entropy criterium of intensity histogram associated to each image to be segmented. The Algorithm 1, reproduced from [14], shows this idea in a more formal perspective, where the set of n initial firefly solutions is given in line 4. Each firefly f i is a d-dimensional vector and $x_k^i$ is the k-th threshold of the i-th firefly solution f i .

In this implementation, for any firefly f i , the strength of attractiveness for other brighter firefly f j can be given by the update rule from lines 12 to 23. This equation states that at each iteration t, the solution f i depends mainly on the f j solution and the bright differences $r_{i,j}$ of all fireflies j, and the new random solution $\mu_t$ , which is drawn from a Gaussian or other distribution. The bright of a firefly i is only updated when i is less brighter than any other firefly j. Such update is proportional to the attractiveness factor β, the absorption coefficient γ and the step motion α.

The objective Z-function very much influences the final result and is application dependent. In this paper, we consider multi-level image thresholding problems in the step two of the proposed methodology and we investigate how the traditional Shannon entropy [1] and its generalization Tsallis entropy [8] influences in the final results of the proposed CAD system.

The algorithm is designed to model a non-linear optimizer associating the thresholds to fireflies. The kernel depends on these variables, which are associated with the fireflies glow and can be modified according to be more appropriate to the data that is being manipulated. Then, the fireflies luminescences are updated iteratively under pre-established rules until the algorithm convergence to a global minimum.



A329170_1_En_17_Figa_HTML.gif

The papers of Lukasik and Zak [15] and Yang [13] suggest that the FF overcome other meta-heuristics, such as the Ant Farm [16], Tabu search [17], PSO [18] and Genetic Algorithms [19]. Thus, the FF was presented as a computing-time efficient method to the Multilevel Thresholding Problem (MLTP). Recently, the work of [20] showed a computational time comparison of the FF against the other method, demonstrating that the FF is more efficient when the evaluation function is modeled with the maximum inter-cluster variance. Other works, such as [11] and [10] also showed similar results when applied to the MLTP.

Specifically for the MLTP modeling, each firefly is a d-dimensional vector, where each dimension is a single threshold that partitions the histogram space. In the specific work of M. H. Horng and R. J. Liou [11], the goal was to minimize the objective function using the Cross-Entropy of the intensities histogram associated with each segmented image criteria.

The Algorithm 1 describes the FF, where a solution set of n initial fireflies is given on line 3. Each firefly f i is a d-dimensional vector and $x_k^i$ is the k-th threshold of i-th solution. More details about the FF can be found in [11] and [13].


4 The Entropy Criteria for Evaluation Functions


In this paper we show the results obtained using a novel approach for the firefly algorithm. Our contribution is the use of Tsallis non-extensive entropy as a kernel evaluation function for the firefly algorithm. This type of entropy is described in the following sections.


4.1 The Shannon Entropy


The very celebrated Shannon entropy has been achieved several applications since C. Shannon proposed it for information theory [21]. Considering a probability distribution $P(H) =\{h(1),h(2),\dots,h(n)\}.$ , the Shannon entropy, denoted by S(H), is defined as:


$$S(H)=-\sum\limits_{i=1}^{L}h_{i}\log (h_{i})$$

(1)
As stated before, T. Pun [1] applied this concept for 1LTP through the following idea. Let two probability distributions from P(H), one for the foreground, $P(H_{1})$ , and another for the background, $P(H_{2})$ , given by:


$$P(H_{1}) :\frac{h_{1}}{p_{A}},\frac{h_{2}}{p_{A}},\dots,\frac{h_{t}}{p_{A}}$$

(2)



$$P(H_{2}) :\frac{h_{t+1}}{p_{B}},\frac{h_{t+2}}{p_{B}},\dots, \frac{h_{L}}{p_{B}}$$

(3)
where $p_{A}=\sum_{i=1}^{t}p_{i}$ and $p_{B}=\sum_{i=t+1}^{L}p_{i}$ .

If we assume that $H_{1}$ and $H_{2}$ are independent random variables, then the entropy of the composed distribution1 verify the so called additivity rule:


$$S(H_{1}\ast H_{2})=S(H_{1})+S(H_{2}).$$

(4)
In the case of 1LTP, the optimal threshold $t^*$ is that one which maximizes the Eq. (4), which can be computed in $O(L^2)$ time.

As before, by assuming independent distributions and under the same normalization restrictions, it is easy to extend the Eq. (4) for the case of $d>1$ ” src=”http://basicmedicalkey.com/wp-content/uploads/2017/06/A329170_1_En_17_Chapter_IEq21.gif”></SPAN> partitions, to obtain the following generalization of the additive rule:<br /> <DIV id=Equ5 class=Equation><br /> <DIV class=EquationContent><br /> <DIV class=MediaObject><IMG alt=

(5)
which, as in the case of cross-entropy, requires $O(L^{d+1})$ in order to achieve the set of d optimal thresholds that maximizes the entropy in Expression (5).


4.2 The Non-Extensive Tsallis Entropy


As mentioned before, the Tsallis entropy is a generalization of the Shannon one (see [22] and references therein). The non-extensive Tsallis entropy of the distribution P(H), denoted by $S_{q}(H)$ , is given by:


$$S_{q}(H)=\frac{1-\sum\limits_{i=1}^{L}h_{i}^{q}}{1-q}$$

(6)
The main feature observed in Eq. (6) is the introduction of a real parameter q, called non-extensive parameter. In [9] it is shown that, in the limit $q \rightarrow 1$ , Eq.  (6) meets the Eq. (1).

For Tsallis entropy we can find an analogous of the additivity property (Expression (4)), called pseudo-additivity due to the appearance of an extra term. For 1LTP $(d=1)$ , given two independent probability distributions $P(H_{1})$ and $P(H_{2})$ from P(H), the pseudo-additivity formalism of Tsallis entropy is given by the following expression:


$$S_{q}(H_{1}\ast H_{2})=S_{q}(H_{1})+S_{q}(H_{2})+(1-q)S_{q}(H_{1})S_{q}(H_{2})$$

(7)
where $S_{q}(H_{1})$ and $S_{q}(H_{2})$ are calculated by applying Eq. (6) for the probability distributions $P( H_{1})$ and $P(H_{2})$ .

For this 1LTP, the optimal threshold $t^{\ast}$ is the one that maximizes the pseudo-additivity property (7), and is computed in $O(L^{2})$ . As in the case of Shannon entropy, we can easily derive a generalized version of Eq. (7) given by:


$$\begin{aligned} S_{q}(H_{1}\ast \cdot \cdot \ast H_{d+1})= S_{q}(H_{1})+\cdots +S_{q}(H_{d+1})+\nonumber\\(1-q)S_{q}(H_{1})S_{q}(H_{2})\dots S_{q}(H_{d+1})\end{aligned}$$

(8)
which is useful for MLTP. However, for the same reasons of cross-entropy and Shannon entropy, the computational time for solving the corresponding MLTP (without a recursive technique) is $O(L^{d+1})$ .

As Shannon Entropy (SE), Tsallis Entropy (TE) also tries to balance mutual information between partitions of a distribution, since it depends on the individual probabilities instead of their positions. Note that the parameter q powers the probability values, given a fine tuning in the pseudo-additivity maximization.

Only gold members can continue reading. Log In or Register to continue

Related posts:

  1. Bone Identification from CT Images, Fragment Separation and Fracture Zone Detection
  2. 3D Computed Tomography Based Tool for Orthopedic Surgery Planning
  3. Planning of Surgical Treatment with the Use of 3D Visualization and Finite Element Method
  4. Influence on the Trabecular Bone Elasticity and Mechanical Competence

Stay updated, free articles. Join our Telegram channel
Tags:
Jun 14, 2017 | Posted by in GENERAL SURGERY | Comments Off on Study of a Firefly Meta-Heuristics for Multithreshold Image Segmentation

Full access? Get Clinical Tree
Get Clinical Tree app for offline access