# Evolutionary Game Algorithm for Image Segmentation

Authors: Jin Zhong; Hao Wu
Journal: Journal of Electrical and Computer Engineering
 (2017)

---

## Abstract

The traditional two-dimensional Otsu algorithm only considers the limitations of the maximum variance of between-cluster variance of the target class and background class; this paper proposes evolutionary game improved algorithm. Algorithm takes full consideration of own pixel cohesion of target and background. It can meet the same of maximum variance of between-cluster variance. To ensure minimum threshold discriminant function within the variance, this kind of evolutionary game algorithm searching space for optimal solution is applied. Experimental results show that the method proposed in this paper makes the detail of segmentation image syllabify and has better antijamming capability; the improved genetic algorithm which used searching optimal solution has faster convergence speed and better global search capability.


---

## Body

## 1. Introduction

Image segmentation is the first step in image analysis, understanding, and pattern recognition, which is also one of the most important steps. Image segmentation is often used in medical image processing, such as nuclear magnetic resonance image, but it is also widely used in geographical space, environmental meteorology, and other fields. At present, there are many methods of image segmentation. Since each image has its own target and background, there is no general segmentation method for all images. Threshold segmentation is one of the most commonly used methods of image segmentation. Its essence is through the image histogram information to determine the threshold of image segmentation. Threshold segmentation method has the minimum error method, the maximum entropy method, and the maximum between-class variance methods. The traditional Otsu method is based on the statistical properties of the first-order histogram. It is widely used because of its simple algorithm and high real-time performance. Therefore, many literatures have improved the Otsu method and proposed a series of two-dimensional thresholding segmentation methods. In the literature [1], the statistical properties based on two-dimensional histogram are proposed to determine the threshold value. It includes not only the gray information of the image pixels. But also the spatial information of the pixels. The effect is better than the one-dimensional Otsu method and has stronger antinoise performance. However, the traditional two-dimensional Otsu algorithm is complex and has long running time. And the effect of segmentation is vague on the contour. This paper is based on the evolutionary game algorithm of protein secretion mechanism. The two-dimensional thresholds are continuously optimized to obtain the two-dimensional thresholds that need to be image segmented. The algorithm has a good segmentation result and relatively good real-time performance and to a great extent solves the problem of local convergence.


## 2. The Principle of Two-Dimensional Maximum Between-Class Variance (Otsu) and Its Improvement

Otsu method Proposed by Japanese scholars in 1979 is the classic threshold segmentation methods. The basic idea is that it obtained the largest class difference of targets and background between the parties by image histogram statistics to determine the optimal threshold for image segmentation dynamically.


### 2.1. Two-Dimensional Maximum Between-Class Variance Methods (Two-Dimensional Otsu Algorithm Method)

Two-dimensional Otsu method is a two-dimensional correlation threshold method. The principle is as follows. Assume that the gray level of the original imagef is L, size is M∗N, and the value of each pixel in the image corresponds to a gray level. Scan the whole image. Calculating the neighborhood gray value of each pixel in the image, the size of the window neighborhood is usually odd. Get a smooth image g. Obviously g gray level is also L. Let mij be pixel value i of that image f. The number of pixels in the neighborhood gray value of j is the gray value and its binary group (i,j) of neighborhood pixels average. The result is two-dimensional histogram of point gray—neighborhood pixels gray. Then the two-dimensional joint probability density is(1)pij=mijM×N.pij Meet ∑i=0L-1∑j=0L-1pij=1. It is L∗L matrix with size of L∗L.Figure1 shows two-dimensional histogram of the schematic image. Figure 2 is the corresponding projection plane, f-axis represents the gray value of each pixel, and g-axis means neighborhood pixels’ average of each pixel gray. Figures 1 and 2 show the peak of pixels intensity in the vicinity of the diagonal, because of the largest proportion of the target region and background region of the image. Distribution of the pixels gray level is uniform relatively.Figure 1
Two-dimensional histogram of an image histogram.Figure 2
Two-dimensional projection plane.Difference of point gray value and its neighborhood pixels gray average is not large, so they are concentrated near the diagonal.Assume that value of the background and objectives in the image as two classes isCb and Co, respectively. (s,t) is two-dimensional threshold vector for images segmentation, and occurrence probability of the background is(2)ωb=pCb=∑i=0s∑j=0tpij=ωbs,t.Occurrence probability of the target is(3)ωo=pCo=∑i=s+1L-1∑j=t+1L-1pij=ωos,t.In most cases, the occurrence probability of the noise and edge is very small. According to Figure 2, the probability of the regions II and IV can be regarded as 0 approximately.According to Figure2, the probability of the regions II and IV can be regarded as 0 approximately.This can be considered asωb+ωo=1. The two classes of background and target correspond to the mean vector to be(4)μbs,t=μbi,μbjT=∑i=0s∑j=0tipijωbs,t,∑i=0s∑j=0tjpijωbs,tT,μos,t=μoi,μojT=∑i=s+1L-1∑j=t+1L-1ipijωos,t,∑i=s+1L-1∑j=t+1L-1jpijωos,tT.Ensemble average is(5)μalls,t=μalli,μalljT=∑i=0L-1∑j=0L-1ipij,∑i=0L-1∑j=0L-1jpijT.Define discrete matrix(6)σB=ωbμb-μallμb-μallT+ωoμo-μallμo-μallT.The trace of the discrete matrix class as the measure of dispersion of the background and objectives is(7)trσB=ωbμbi-μalli2+μbj-μallj2+ωoμoi-μalli2+μoj-μallj2.When the trace of the dispersion matrix is the maximum value, we obtain the optimal segmentation threshold(8)trss∗,t∗=max⁡trss,t,0≤s,t≤L-1.


### 2.2. Two-Dimensional Maximum of Between-Class Variance Method

In the traditional two-dimensional Otsu method, the threshold discriminant function (trace of the dispersion matrix) takes into account only the variance of the target class and the background class; that is, the larger the variance between classes, the better the segmentation effect. However, the traditional two-dimensional Otsu algorithm does not take into account its own classified information of each type of pixels of target class and background class, that is, considering the cohesion within the classes. So, in this paper, the measure of the dispersion within the class is also introduced to the recognition function of threshold. This can reflect the efficiency of the overall classification, specifically, the following: two classesco and cb existing in two-dimensional histogram and calculated variance of the center of the target class μo. The center of the background class μo with i,j is from each gray value and its neighborhood pixels average separately:(9)do=∑i=0s∑j=0ti-μoi2+j-μoj2pijωo,db=∑i=s+1L-1∑j=t+1L-1i-μbi2+j-μbj2pijωb.Obviously, the smaller the value of the variance of the target class and background class, the better its cohesion and the better the segmentation effect.The definition of the measure of dispersion within class is(10)ρs=ωodo+ωbdb.Obviously,ρs is required smaller value, and cohesion within the classes gets the better effect.We are considering the between-class variance and within the class variance. The threshold makes between-class variance the largest, and, at the same time, within the class variance meets the minimum value. A new discriminant function of the threshold is used in this article as follows:(11)ϕss,t=ωo×ωb×trσBρs.Molecularωo×ωb×trσB shows the property of between-class variance and denominator ρs performance within the class cohesion; when ϕss,t obtains the maximum value, effect of the image segment is best.That is, when value of the discriminant function is the maximum,s′,t′ is the best threshold for the segmentation threshold.Now, the target class and background class are separated greatly, and the cohesion of target class and background is the best kind.The optimal threshold vector to achieve the gray image banalization is got as follows:(12)fi,j=0,i<t,j<s,1,i≥torj≥s.


## 2.1. Two-Dimensional Maximum Between-Class Variance Methods (Two-Dimensional Otsu Algorithm Method)

Two-dimensional Otsu method is a two-dimensional correlation threshold method. The principle is as follows. Assume that the gray level of the original imagef is L, size is M∗N, and the value of each pixel in the image corresponds to a gray level. Scan the whole image. Calculating the neighborhood gray value of each pixel in the image, the size of the window neighborhood is usually odd. Get a smooth image g. Obviously g gray level is also L. Let mij be pixel value i of that image f. The number of pixels in the neighborhood gray value of j is the gray value and its binary group (i,j) of neighborhood pixels average. The result is two-dimensional histogram of point gray—neighborhood pixels gray. Then the two-dimensional joint probability density is(1)pij=mijM×N.pij Meet ∑i=0L-1∑j=0L-1pij=1. It is L∗L matrix with size of L∗L.Figure1 shows two-dimensional histogram of the schematic image. Figure 2 is the corresponding projection plane, f-axis represents the gray value of each pixel, and g-axis means neighborhood pixels’ average of each pixel gray. Figures 1 and 2 show the peak of pixels intensity in the vicinity of the diagonal, because of the largest proportion of the target region and background region of the image. Distribution of the pixels gray level is uniform relatively.Figure 1
Two-dimensional histogram of an image histogram.Figure 2
Two-dimensional projection plane.Difference of point gray value and its neighborhood pixels gray average is not large, so they are concentrated near the diagonal.Assume that value of the background and objectives in the image as two classes isCb and Co, respectively. (s,t) is two-dimensional threshold vector for images segmentation, and occurrence probability of the background is(2)ωb=pCb=∑i=0s∑j=0tpij=ωbs,t.Occurrence probability of the target is(3)ωo=pCo=∑i=s+1L-1∑j=t+1L-1pij=ωos,t.In most cases, the occurrence probability of the noise and edge is very small. According to Figure 2, the probability of the regions II and IV can be regarded as 0 approximately.According to Figure2, the probability of the regions II and IV can be regarded as 0 approximately.This can be considered asωb+ωo=1. The two classes of background and target correspond to the mean vector to be(4)μbs,t=μbi,μbjT=∑i=0s∑j=0tipijωbs,t,∑i=0s∑j=0tjpijωbs,tT,μos,t=μoi,μojT=∑i=s+1L-1∑j=t+1L-1ipijωos,t,∑i=s+1L-1∑j=t+1L-1jpijωos,tT.Ensemble average is(5)μalls,t=μalli,μalljT=∑i=0L-1∑j=0L-1ipij,∑i=0L-1∑j=0L-1jpijT.Define discrete matrix(6)σB=ωbμb-μallμb-μallT+ωoμo-μallμo-μallT.The trace of the discrete matrix class as the measure of dispersion of the background and objectives is(7)trσB=ωbμbi-μalli2+μbj-μallj2+ωoμoi-μalli2+μoj-μallj2.When the trace of the dispersion matrix is the maximum value, we obtain the optimal segmentation threshold(8)trss∗,t∗=max⁡trss,t,0≤s,t≤L-1.


## 2.2. Two-Dimensional Maximum of Between-Class Variance Method

In the traditional two-dimensional Otsu method, the threshold discriminant function (trace of the dispersion matrix) takes into account only the variance of the target class and the background class; that is, the larger the variance between classes, the better the segmentation effect. However, the traditional two-dimensional Otsu algorithm does not take into account its own classified information of each type of pixels of target class and background class, that is, considering the cohesion within the classes. So, in this paper, the measure of the dispersion within the class is also introduced to the recognition function of threshold. This can reflect the efficiency of the overall classification, specifically, the following: two classesco and cb existing in two-dimensional histogram and calculated variance of the center of the target class μo. The center of the background class μo with i,j is from each gray value and its neighborhood pixels average separately:(9)do=∑i=0s∑j=0ti-μoi2+j-μoj2pijωo,db=∑i=s+1L-1∑j=t+1L-1i-μbi2+j-μbj2pijωb.Obviously, the smaller the value of the variance of the target class and background class, the better its cohesion and the better the segmentation effect.The definition of the measure of dispersion within class is(10)ρs=ωodo+ωbdb.Obviously,ρs is required smaller value, and cohesion within the classes gets the better effect.We are considering the between-class variance and within the class variance. The threshold makes between-class variance the largest, and, at the same time, within the class variance meets the minimum value. A new discriminant function of the threshold is used in this article as follows:(11)ϕss,t=ωo×ωb×trσBρs.Molecularωo×ωb×trσB shows the property of between-class variance and denominator ρs performance within the class cohesion; when ϕss,t obtains the maximum value, effect of the image segment is best.That is, when value of the discriminant function is the maximum,s′,t′ is the best threshold for the segmentation threshold.Now, the target class and background class are separated greatly, and the cohesion of target class and background is the best kind.The optimal threshold vector to achieve the gray image banalization is got as follows:(12)fi,j=0,i<t,j<s,1,i≥torj≥s.


## 3. Threshold Vector Evolutionary Game Algorithm

In this paper, the optimal solution of the threshold vector can be obtained by the evolutionary game algorithm. The new generation of each generation of the algorithm is randomly paired and repeated. Each individual is to optimize their objective function to the optimal value [2–8]. The target value is determined by the evolutionary game matrix. Set the objective function as f1x,y, f2x,y. The objective function has two mixed variables x and y. The game structure of evolutionary algorithm is designed as follows:(13)AgentV1=x1,y1V2=x2,y2⋮Vk=xk,ykFitnessF1F2⋮Fk↔↔⋮↔PlaysAgentG1=x1′,y1′G2=x2′,y2′⋮Gk=xk′,yk′FitnessF1′F2′⋮Fk′.The fitness of Fi is determined by the game matrix, i=1,2,…,k. For the participants of the two random pairs of the game through the evolution game, the Gi of each participant’s game payoff is the difference between the two objective functions:(14)G1Vi,Vi′=G1xi,yi,xi′,yi′=f1xi,yi-f2xi′,yi′,G2Vi,Vi′=G2xi,yi,xi′,yi′=f1xi′,yi′-f2xi,yi.According to this value, the fitness of each objective function is calculated by (15)Fi=100×G1xi,yi,xi′,yi′ω,Fi′=100×G2xi,yi,xi′,yi′ω.In the formula, a is B or C fitness scalar. ω is the maximum value of Gkxi,yi,xi′,yi′. Each generation of the subgame of the evolutionary algorithm is based on the fitness value.


### 3.1. Evolutionary Game Algorithm Based on Protein Secretion Mechanism

Drawing on the main signal hypothesis in recent years, that is, the cooperative translation of protein secretion process [9], in this paper, based on the self-organization evolutionary game algorithm of protein secretion mechanism behavior, we use the method of signal peptide in the cell matrix to guide the synthesis of secreted protein synthesis as an algorithm to realize [9], as shown in Figure 3.Figure 3
Architecture of population for the proliferation of evolution PEP.It is assumed that the state of the protein secretion system is discrete and the state, behavior, and emotional intelligence are represented by a collection of three-dimensional sequences, represented by theI,Iat,It. The game matrix is described as (16)Iatt+1It1=I11-ωI13100001=ItIatt-11.The line number of the matrix represents the behavior sequence. The value of the element of the matrix represents the corresponding behavioral states corresponding to the emotional intelligence value. Iat is expressed sentiment value a of behavior execution under state k. It represents the state of t intelligence. The high level regulation of protein secretion is achieved by evaluating the state of the system and by feedback learning based on the results of the evaluation. Here is the selection behavior of the algorithm steps in state recognition. Hypothetical selection behavior steps are as follows:(1) After the behavior evolution of the state recognition, the state action selection rule is described by the formula, and all possible behaviors in the state can be represented by the “∗”:(17)A=AfunctionI∗t=max⁡I∗t.(2) The rules of evaluation rules of emotional intelligence of the state of emotional intelligence factor are(18)It=IfunctionI∗t=max⁡I∗t.(3) The learning rules of emotional intelligence are described in formula, in which ω represents learning rate:(19)I∗tt+1=Ufunction=I∗,I∗t=1-ωI∗tt+ωI∗t.Define the end condition of an emotional learning after the end of emotional learning. The self-adaptation of the subject to the behavioral environment is preserved in the protein secretion environment. These adaptive results are passed to the individual through the output of the protein secretion mechanism. Compared to the next generation, the next generation has a more adaptive behavior environment. Based on the mechanism of protein secretion, this paper designs the self-organization evolutionary game algorithm, as shown in Figure 4.Figure 4
Evolutionary algorithm based on the mechanism of protein secretion.Here is the solving process for specific threshold vector.(1) Coding. Gray level of an image is from 0 to 255, encoding binary. For one-dimensional Otsu method, the threshold is only one which can be represented by 8-bit binary.The two-dimensional Otsu method has two threshold segmentations, so we use 16-bit (bit string length) method to achieve a binary encoding, that isx0,x1,…,x7,x8,…,x15, where top eight represent segmentation threshold s, and after eight they represent segmentation threshold t.According to the improved two-dimensional histogram strategy proposed in Section2.2 a strategy is that, in this test, N is 30, so 0+30≤s,t≤255-30; that is, 0+30≤s,t≤255-30.(2) Initialization. Let the initial population be of popsize. Because the optimization parameters are two-dimensional threshold, so Initialize can randomly generate a pop size line, 16-column matrix by random number generator.The following operations are for the targeted population initialized. Here process of decoding needs to take into account the range ofs and t.(3) Fitness Function. According to the analysis of Section 2.2, this new the threshold discriminant function ϕss,t is the fitness function, and when ϕss,t obtains the maximum, value of the parameters s and t is the optimal threshold for image segmentation.(4) Select. The traditional genetic algorithm used in the roulette selection method usually leads to the loss of diversity of the population, and genetic algorithm will prematurely lose its evolutionary capacity.This article takes the choice explained here. First of all, to retain some of the individuals with the highest fitness value of the parent directly into the offspring, for some suboptimal individuals after a certain mutation the excellent individuals can also enter the progeny; that is, through the evolution of different populations of the parent population, we get offspring.This way not only ensures the outstanding individuals of the population structure into the next generation, but also ensures the diversity of the population. This makes the probability of having similar individual in the population reduced, increases the following crossover and mutation operation efficiency, and improves the convergence of the algorithm.(5) Crossover. Crossover operation is the unique original characteristics [10] of genetic algorithm of evolutionary algorithm.There is a problem about the traditional crossover operator; when Stocks evolve to the local optimum, many individuals are very similar, which is “close.”Cross-string of individuals is the same largely; the role of crossover operation does not work.In order to avoid “close” cross, in this article, we selected individuals randomly for crossover Hamming distance judgments on the mating pool.If we select the individual on the Hamming distanceHsi,sj≥λ0≤λ≤l, according to the original the probability, we operate cross-cross.Conversely, ifHsi,sj<λ, then we determine that the individuals are “close” and replace one of the individuals, until the conditions are met or all individuals in the group are tried to be replaced.(6) Variation. The mutation operation in traditional genetic algorithm is based on a certain mutation probability for values of each individual bit string, that is, 1 to 0 or 0 to 1. Typically, the probability of mutation is relatively small. In the implementation process, some individuals could not have taken place to mutate, wasting a lot of computing resources. This article uses a dynamic mutation probability in order to increase the diversity of the population. The basic idea is to determine whether the current population is or not “mature”; if it is, then it mutates on a larger probability; otherwise, according to conventional mutation probability, fmax is defined as the best current population fitness; favi is the current population average fitness; if kfmax≥favi, where 0.5≤k≤1, as intensive factor, then our algorithm determines that the population does not “premature” and mutate on conventional probability. On the contrary, if the population is “premature” and mutates on much bigger than conventional probability to all individuals, it results in more individuals into the next generation, in order to ensure population out of local convergence.


## 3.1. Evolutionary Game Algorithm Based on Protein Secretion Mechanism

Drawing on the main signal hypothesis in recent years, that is, the cooperative translation of protein secretion process [9], in this paper, based on the self-organization evolutionary game algorithm of protein secretion mechanism behavior, we use the method of signal peptide in the cell matrix to guide the synthesis of secreted protein synthesis as an algorithm to realize [9], as shown in Figure 3.Figure 3
Architecture of population for the proliferation of evolution PEP.It is assumed that the state of the protein secretion system is discrete and the state, behavior, and emotional intelligence are represented by a collection of three-dimensional sequences, represented by theI,Iat,It. The game matrix is described as (16)Iatt+1It1=I11-ωI13100001=ItIatt-11.The line number of the matrix represents the behavior sequence. The value of the element of the matrix represents the corresponding behavioral states corresponding to the emotional intelligence value. Iat is expressed sentiment value a of behavior execution under state k. It represents the state of t intelligence. The high level regulation of protein secretion is achieved by evaluating the state of the system and by feedback learning based on the results of the evaluation. Here is the selection behavior of the algorithm steps in state recognition. Hypothetical selection behavior steps are as follows:(1) After the behavior evolution of the state recognition, the state action selection rule is described by the formula, and all possible behaviors in the state can be represented by the “∗”:(17)A=AfunctionI∗t=max⁡I∗t.(2) The rules of evaluation rules of emotional intelligence of the state of emotional intelligence factor are(18)It=IfunctionI∗t=max⁡I∗t.(3) The learning rules of emotional intelligence are described in formula, in which ω represents learning rate:(19)I∗tt+1=Ufunction=I∗,I∗t=1-ωI∗tt+ωI∗t.Define the end condition of an emotional learning after the end of emotional learning. The self-adaptation of the subject to the behavioral environment is preserved in the protein secretion environment. These adaptive results are passed to the individual through the output of the protein secretion mechanism. Compared to the next generation, the next generation has a more adaptive behavior environment. Based on the mechanism of protein secretion, this paper designs the self-organization evolutionary game algorithm, as shown in Figure 4.Figure 4
Evolutionary algorithm based on the mechanism of protein secretion.Here is the solving process for specific threshold vector.(1) Coding. Gray level of an image is from 0 to 255, encoding binary. For one-dimensional Otsu method, the threshold is only one which can be represented by 8-bit binary.The two-dimensional Otsu method has two threshold segmentations, so we use 16-bit (bit string length) method to achieve a binary encoding, that isx0,x1,…,x7,x8,…,x15, where top eight represent segmentation threshold s, and after eight they represent segmentation threshold t.According to the improved two-dimensional histogram strategy proposed in Section2.2 a strategy is that, in this test, N is 30, so 0+30≤s,t≤255-30; that is, 0+30≤s,t≤255-30.(2) Initialization. Let the initial population be of popsize. Because the optimization parameters are two-dimensional threshold, so Initialize can randomly generate a pop size line, 16-column matrix by random number generator.The following operations are for the targeted population initialized. Here process of decoding needs to take into account the range ofs and t.(3) Fitness Function. According to the analysis of Section 2.2, this new the threshold discriminant function ϕss,t is the fitness function, and when ϕss,t obtains the maximum, value of the parameters s and t is the optimal threshold for image segmentation.(4) Select. The traditional genetic algorithm used in the roulette selection method usually leads to the loss of diversity of the population, and genetic algorithm will prematurely lose its evolutionary capacity.This article takes the choice explained here. First of all, to retain some of the individuals with the highest fitness value of the parent directly into the offspring, for some suboptimal individuals after a certain mutation the excellent individuals can also enter the progeny; that is, through the evolution of different populations of the parent population, we get offspring.This way not only ensures the outstanding individuals of the population structure into the next generation, but also ensures the diversity of the population. This makes the probability of having similar individual in the population reduced, increases the following crossover and mutation operation efficiency, and improves the convergence of the algorithm.(5) Crossover. Crossover operation is the unique original characteristics [10] of genetic algorithm of evolutionary algorithm.There is a problem about the traditional crossover operator; when Stocks evolve to the local optimum, many individuals are very similar, which is “close.”Cross-string of individuals is the same largely; the role of crossover operation does not work.In order to avoid “close” cross, in this article, we selected individuals randomly for crossover Hamming distance judgments on the mating pool.If we select the individual on the Hamming distanceHsi,sj≥λ0≤λ≤l, according to the original the probability, we operate cross-cross.Conversely, ifHsi,sj<λ, then we determine that the individuals are “close” and replace one of the individuals, until the conditions are met or all individuals in the group are tried to be replaced.(6) Variation. The mutation operation in traditional genetic algorithm is based on a certain mutation probability for values of each individual bit string, that is, 1 to 0 or 0 to 1. Typically, the probability of mutation is relatively small. In the implementation process, some individuals could not have taken place to mutate, wasting a lot of computing resources. This article uses a dynamic mutation probability in order to increase the diversity of the population. The basic idea is to determine whether the current population is or not “mature”; if it is, then it mutates on a larger probability; otherwise, according to conventional mutation probability, fmax is defined as the best current population fitness; favi is the current population average fitness; if kfmax≥favi, where 0.5≤k≤1, as intensive factor, then our algorithm determines that the population does not “premature” and mutate on conventional probability. On the contrary, if the population is “premature” and mutates on much bigger than conventional probability to all individuals, it results in more individuals into the next generation, in order to ensure population out of local convergence.


## 4. Simulations and Analysis of Experiments

Image segmentation tests were carried out by the proposed image segmentation, that is, two-dimensional Otsu method based on improved genetic algorithm. We compared between segmentation of horse picture, airplane image, and tank image by the one-dimensional Otsu method, the traditional two-dimensional Otsu method, improved two-dimensional Otsu method based on the traditional GA, and the proposed algorithm.Experiment hardware platform is 2.6 GHz Pentium 4, Capacity of memory is 512 MB, and operating environment is Matlab 7.0.Various experimental parameters are set as follows(1)
one-dimensional Otsu method using the standard threshold of GA optimization, size of population: 10; number of iterations: 15; length of code: 8; probability of crossover: 0.7; probability of mutation: 0.05;(2)
traditional neighborhood of two-dimensional Otsu method, size of window neighborhood: 3;(3)
this method adopting an improved two-dimensional Otsu method and the improved GA, size of window neighborhood: 3; size of population: 10; number of iterations: 150; length of code: 16; probability of crossover: 0.7; Hamming discriminant distance: 2; larger mutation probability: 0.2; small mutation probability: 0.01; intensive factor: 0.8.Various types of experimentally derived physical threshold are in Table1, and result of one-dimensional Otsu method, traditional Otsu method based on the standards of GA, and this method is the average obtained for 30 independent experiments.Table 1
The threshold obtained from several algorithms.
Image
Threshold
One-dimensional Otsu method is based on the traditional standards of GA
Method of literature 3
Traditional two-dimensional Otsu standards-based GA
This method
Horse
96
(
83,145
)
(
83,146
)
(
66
,
143
)
Airplane
174
(
130,209
)
(
131,204
)
(
51,218
)
Tank
116
(
175,87
)
(
173,85
)
(
34,200
)In the actual image acquisition process, images often will be affected by the external environment; the image will contain all kinds of noise; in the following example, horse pictures added a variety of noise; then this method deals with the results of noise.Running time of one-dimensional Otsu method is shorter; however, from Figures5, 6, and 7, the segmentation results show that traditional two-dimensional Otsu algorithm and out method are better; many details are not separated out, especially in Figure 6; the segmentation of the target aircraft is more accurate.Figure 5
Segmentation of horse image. (a) Horse original. (b) Segmentation of one-dimensional Otsu. (c) The traditional two-dimensional Otsu method. (d) Our algorithm.
(a)
(b)
(c)
(d)Figure 6
Segmentation of airplane image. (a) Horse original. (b) Segmentation of one-dimensional Otsu. (c) The traditional two-dimensional Otsu method. (d) Our algorithm.
(a)
(b)
(c)
(d)Figure 7
Segmentation of tank image. (a) Horse original. (b) Segmentation of one-dimensional Otsu. (c) The traditional two-dimensional Otsu method. (d) Our algorithm.
(a)
(b)
(c)
(d)Figures8, 9, and 10 show that various types of noise have a great impact on results of all one-dimensional Otsu algorithm. Its effects and antijamming capability are poorer than this method.Figure 8
Horse image (0.02-degree encryption salt and pepper noise). (a) Original. (b) The results of one-dimensional Otsu method. (c) The results of our algorithm.
(a)
(b)
(c)Figure 9
Horse image (mean of Gaussian noise is 0 and variance is 0.02). (a) Original. (b) The results of one-dimensional Otsu method. (c) The results of our algorithm.
(a)
(b)
(c)Figure 10
Horse image (mixed mean of Gaussian noise is 0 and variance is 0.02 and 0.02-degree encryption salt and pepper noise). (a) Original. (b) The results of one-dimensional Otsu method. (c) The results of our algorithm.
(a)
(b)
(c)The traditional two-dimensional Otsu method is better than the one-dimensional Otsu method; the segmentation of images containing noise removal can be seen very clearly.But its calculation is based on exponential growth because the algorithm has a double loop, a total of calculation times needed areM×N, that is, tr(ss,t), and M×N is the total pixel number of times.Every time it cumulatess×t+L-s×L-t points; therefore, the algorithm complexity is oL4.This calculation is very large, and in practice such a long running time is unacceptable.Relative to the one-dimensional Otsu method, the traditional two-dimensional Otsu method is the sacrifice of time in exchange for consideration of segmentation accuracy.In this paper, an improved GA optimizes the threshold parameters; it is clear that the convergence for the calculation ofϕss,t is product of the number of generations and size of population; Table 2 shows that the average convergence times of generation algebra of our algorithm are 15; therefore, it is also necessary to calculate 15×10 = 150 times. At the same time, it also needs to cumulate s×t+L-s×L-t points. Thus, time complexity of the algorithm is oL2.Table 2
Comparison of the running time of several two-dimensional Otsu algorithms.
Photo (specification)
Method (parameters)
Method of literature 3
The traditional method based on the traditional GA Otsu
This method (improved Otsu + improved GA)
Time complexity
Running time (/s)
Running time
The average convergence times of 30 times
The average convergence times of 30 times (/s)
Time multiplexing complex degree
The average convergence times of 30 times
The average convergence times of 30 times (/s)
Horse(158∗228)
o(L4)
6193
o
(
L
2
)
137
14.3424
o
(
L
2
)
15
4.1222
Airplane(230∗500)
o
(
L
4
)
8537
o
(
L
2
)
113
17.4219
o
(
L
2
)
14
5.9717
Tank(212∗178)
o
(
L
4
)
6723
o
(
L
2
)
129
14.5323
o
(
L
2
)
11
4.3312For an image, the traditional Otsu method requires256×256 calculating of tr(ss,t). Out algorithm only needs to calculate 150 times of ϕss,t, 437 times faster.In fact, the improved GA algorithm in this paper accelerates the convergence process; it is basically the average convergence times to twenty, saving the running time of this algorithm greatly and avoiding local convergence problems from the traditional GA algorithm.In order to verify that the improved GA has better convergence, the improved two-dimensional Otsu method also used standard GA parameters to do experiment and compared with our method.Figures11, 12, and 13 are the evolution curve of two algorithms about horse image, dragon image, and tank image, respectively.Figure 11
Two evolutionary curves’ algorithm for horse image.Figure 12
Two evolutionary curves’ algorithm for airplane image.Figure 13
Two evolutionary curves’ algorithm for tank image.According to Figures11 and 12, we can get result of the improved GA algorithm and the traditional GA algorithm. In Figure 11, convergence times of the improved GA are 4, whereas convergence times of the traditional GA algorithm are 87; they have been the largest fitness value.In Figure12, convergence times of the improved GA is 22, convergence times of the traditional GA is 78, and the traditional GA get into a premature local convergence and did not reach maximum fitness value.In Figure13, convergence times of the improved GA is 13, convergence times of the traditional GA is 61, and there is no maximum fitness value.Therefore, the improved genetic algorithm GA obtained the optimal threshold that is clearly better than the optimal solution traditional genetic algorithm obtained, but also it is closer to the optimal solution and overcomes “premature” problem from the traditional GA algorithm largely.The horse figure, dragon figure, and tank image show the comparative results of running time of several algorithms from 30 figures of independent experiments, shown in Table2.Results of experimental show that the proposed improved genetic algorithm based optimization method to improve two-dimensional Otsu threshold vector is effective; it can both search the global optimal vector and get the cost of a very small amount of time, showing the higher robustness and real-time of algorithm.


## 5. Conclusion

The paper points out that the traditional two-dimensional Otsu method only considered deficiency of the largest variance between classes and proposes the threshold discriminant function which not only can reflect variance between classes, but also can reflect the variance within classes, and it obtained better segmentation than the traditional two-dimensional Otsu, while the genetic algorithm improved by this method has better population diversity and global search capacity.Results of simulation show that the proposed method not only has better and faster segmentation effect, but also has some practical value.Through a lot of pictures of other experiments, the results are generally better than the traditional two-dimensional Otsu method.However, the relative algorithm GA based on the traditional standard two-dimensional Otsu method already has a very good time performance, but there are still some obstacles, because, in real-time applications, its running time is more than 4 seconds. So how to reduce running time and do not affect the segmentation result is an issue worthy of consideration.



---

*Source: 8746010-2017-07-25.xml*