Adaptive DE based on chaotic sequences and random adjustment for image contrast enhancement

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA)

Adaptive DE based on chaotic sequences and random adjustment for image contrast enhancement L. M. Rasdi Rere, M. Ivan Fanany, A. Murni Faculty of Computer Science Universitas Indonesia Depok – West Java, Indonesia [email protected], [email protected], [email protected]

Abstract—Differential Evolution (DE) is one of the powerful optimization methods. Performance of this algorithm is significantly relying on its parameter setting. These parameters are usually constant during the entire search process. However to set them accurately is not easy and totally depends on the problem characteristic. To address this challenge, a number of methods have been proposed to automatically fine-tune the parameters, according to feature of the problem. In this paper we evaluated two variations of adaptive DE for application of optimal image Contrast Enhancement. The first method was DE using chaotic sequences and the second was DE based on random adjustment of the parameters. The objective of both variations in this application is to increase the fitness criterion with the aim of enhance the contrast and details of the image. The results are compared with classical DE by four testing images, i.e. Cameraman, Lena, Boat, and Rice. The simulation results show that, applications of these variations adaptive DE in image contrast enhancement are potential approach to increase the performance of classical DE. Keywords—Adaptive Differential Evolution, Chaotic sequences, Image contrast enhancement.

I.

INTRODUCTION

Differential Evolution is one of the latest evolutionary algorithms applied to continuous optimization problem. Price and Storn proposed this method in 1995, to solve the fitting problem on Chebyshev polynomial and have verified it to be a very consistent optimization scheme for a number of different tasks. DE is constructed on individual’s difference, utilizing random research in solution space, further operate the mechanism of mutation, crossover, and selection to compute every individual to find suitable individual [1]. Since its introduction, DE has been used to answer any kinds of application problems in science and engineering, such as medicine, acoustic, aerodynamics, biotechnology, chemical engineering, electrical, environmental science, transportation, industry and economy. The wide range variety of application indicates that this method is powerful and versatile [2]. In addition, the simplicity and user-friendly structure are other advantages of DE after robustness and reliable performance. There are three important parameters in DE: population size (P), mutation factor (F) and crossover rate

(CR). These parameters are very sensitive, especially to F and CR; that affect the speed and robustness of the search with various degrees. Many studies have been reported about poor performance of DE due to unsuitable setting of the parameters. Although some guidelines to set the parameter are available, selecting the best parameter is problem dependent task in which is carried out using the trial and error method or the grid search [2]. In recent years, a number of methods have been recommended to automatically adjust the parameters of F and CR. Liu and Lampinen [3] proposed FADE (fuzzy adaptive DE), where the parameter controls of mutation and crossover are adaptive. They used fuzzy logic controller to adjust these parameter. Qin and Suganthan [4] proposed SaDE (Self-adaptive DE). They suggested the learning strategy, where the appropriate learning strategy and parameter setting are regularly selfadapted, along with the learning experience. Brest et al [5] proposed self-adaptive DE algorithm with several variant. They algorithm has been widely-used in applied cases, and has shown excellent result. Other important methods have been proposed were DE based on chaos theory [1], [6], [7] and DE based on random adjustment [8], by using the strategy to compare the fitness of spring with the average fitness value of the recent generation. Almost all of the several adaptation schemes usually apply some types of random. Another form is using better parameter choice and replaces the unproductive parameter values. In this paper, the application of DE based on chaotic sequences and random adjustment of parameters is evaluated for optimal image contrast enhancement. The performance of these methods were also compared to classical DE by applying to four testing images; i.e. Cameraman, Lena, Boat, and Rice. The objective of this work is to maximize the fitness criterion in order to enhance the contrast and detail the image, and also to improve the objective function compare to classical DE. The remainder of this paper is organized in the following manner: Section 2 describes Image Contrast Enhancement; Section 3 present the algorithm of DE; Section 4 give

978-1-4799-5100-0/14/$31.00 ©2014 IEEE

220

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA) explanation of simulation and result; and Section 5 is the Conclusions of the paper.

parameters according to an objective function that describes the contrast of the image.

II. IMAGE CONTRAST ENHANCEMENT

B. Enhancement evaluation criterion To apply automatically the technique of image enhancement, without human intervention and objective parameters given by the user, a standard for enhancement method should be selected. This standard will be related to objective function of the metaheuristic methods. The objective function shown in (2) is adopted in this paper for the standard of image enhancement [1]:

One of the main issues in computer vision, image processing, and pattern recognition is Contrast enhancement. The aim of this technology is to improve the visual quality of an image, including sharpens and contrasts of the features. Although the intrinsic information does not increase in the original image, but it is helpful in more application of image, for instance assisting segmentation of image, recognising and interpreting useful information from the image [9]. Two classification techniques usually used for contrast enhancement are indirect methods and direct methods. The algorithms based on indirect method enhance the image without measuring the contrast, while direct methods set up a criterion of contrast measure and enhance the images by improving the contrast measurement directly [9]. In this paper, algorithm of DE and its variants are used to adjust the intensity transformation of gray-level image using direct method approach. At this point, an important aspect is the creation of a right image contrast measure. A. Enhancement Kernel Measuring of an image contrast can be used globally and locally. If the image contains texture information, using a local contrast is more suitable. The contrast values are enhanced by function of contrast enhancement, such as trigonometric function, logarithm function, exponential function, and square root function [9]. The methods of local enhancement apply transformation functions that are based on the gray-level distribution in the region of every pixel in a given image. In this paper, the following transformation function is used to each pixel at location (x, y): § · K ¸¸ . > f ( x, y )  c.m( x, y )@  m( x, y ) a g ( x, y ) ¨¨ d V ( x , y )  b © ¹

(1)

where m(x, y) and V(x, y) are gray-level mean and standard deviation, respectively. f(x, y) and g (x, y) are the gray-level intensity of input and output image pixel at location (x, y), while K is the global mean of the image [1]. It is unlike the original method at present in [10], the parameter of b in (1) tolerates for zero standard deviation in the neighborhood. Parameter c permits for only a fraction of the mean m(x, y) to subtract from the original pixel’s graya level f(x, y), while the function of m(x, y) have a brightening and smoothing effect on the image. All of parameters (a, b, c and d) are defined over the real positive number and their value are similar for the whole image [2]. The task of DE methods in this formula is to find the combination of these

F (Z )

log(log( E ( I ( Z )))).

ne( I ( Z )) .H ( I ( Z )) PH .PV

(2)

Where F(Z) is objective function for maximization problem, I(Z) indicates the original image with the transformation in each pixel at location (x, y) applied according to Eq. (1), where the relevant parameters are given by Z = (a b c d). The function of E(I(Z)) and ne(I(Z)) are the edge intensity and the number of edge pixels, respectively. Both of them are detected by Sobel edge detector. Moreover, the number of pixels in horizontal and vertical direction are PH and PV, respectively, while H(I(Z)) measures the entropy of the image I(Z) [2]. In this study, the adaptive DE methods are to decide the solution that maximizes F(Z). To reach these objectives, the algorithms need to increase the relative number of pixels and the overall intensity in the edges of the image, as well as to transform the histogram of the image, that move toward a uniform distribution by maximizing the entropic measure [1]. III. DIFFERENSIAL EVOLUTION ALGORITHM Differential Evolution is originally proposed by Price and Storn to solve real-parameter optimization problem. Variation of DE have been suggested by Price et al and are conventionally named DE/x/y/z, where DE stands for Differential Evolution, x represents a string that denotes the base vector, whether it is ‘‘rand’’ or ‘‘best’’, y is the number of difference vectors considered for perturbation of the base vector x and z denotes the crossover scheme, which may be binomial or exponential [11]. A. Classical DE The form of classical DE is DE/rand/1/bin, meaning that the target vector is randomly selected, and only one different vector is used. The acronym of bin indicates that the recombination is controlled by a binomial decision rule [11]. The pseudo-code of classical DE is given in Fig.1 [8], and the procedure this method is given by the following steps [1]: Step 1: Determining of parameters setting The important parameters of DE are population size, mutation factor, and crossover rate, where all of them impact the performance of the DE.

221

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA) i

DE work with a population of individual x N , where every individual represent an answer of the problem. Dimension of the problem is individual in DE, which is encoded as real vectors with M sizes. In addition, the size of population (P) is number of individuals, and number of generation is represented by N. Mutation factor (F) controls the magnification of the difference between two individual to avoid search stagnation. In original DE, mutation factor with crossover rate (CR) is kept constant during the iteration process. The parameter of CR determines how many consecutive genes of the mutated vector are copied to the offspring. Other additional parameters setting are boundary constraint of optimization variables, and stopping criterion. Step 2: Initialization of the initial population of individuals The first population is generated by randomly creating the vectors in suitable search range. The process can be presented as follows:

x

i G 1

lb  rand (ub  lb)

(3)

Where lb is lower boundary, ub is upper boundary and rand is randomization [0, 1] Step 3: Evaluation of individuals Evaluation of each individual in population is done by calculate the score fitness function. Step 4: Operation of Mutation Generally, mutation is a process to complement the identical of variable in vector parameters. All individual in population get a chance to come to be primary parent and to raise its own offspring. i

In mutation operation, from the primary parents x N , three v1

v2

auxiliary parents are chosen randomly; x N , x N

, x Nv3 , where

these parents contribute in operation of mutation to generate a mutated individual

xNmut as follows

xNmut

xNv1  F ( xNv 2  xNv3 )

(4)

Note: v1, v2, v3  {1, 2… P} and i z v1z v2 z v3 Step 5: Operation of Recombination After the operation of mutation, crossover (recombination) mut

is applied in the population. For each mutant vector xN , an index jrnd is randomly chosen using a uniform distribution, and a trial vector

x Nchild is created with the following equation child xN

­° x Nm ut if rnd d CR or j ® i °¯ x N otherwise

j

rnd

(5)

The crossover rate, CR  (0, 1) is used to control fraction of the value variable that is copied by the mutant. Algorithm of classical DE Choose P, F, CR Set N = 1 Initialization of population PN while criterion is not satisfied do i

for individual x N in PN do v1

v2

N

N

choose auxiliary parents x , x

and x

v3 N

child

produce x N

child

PN+1 = PN+1 ‰ Best ( x N

i

, xN )

end for Set N = N + 1 end while Fig.1. Algorithm for the differential evolution (DE) method [8]

Step 6: Operation of Selection The offspring

xNchild is compared to primary parent xNi , to

decide as a member of population in the next generation. In this case, the objective function is maximization, so that the operation of selection can be described as follows: i x N 1

­ x Nchild if f ( x Nchild ) ! f ( x Ni ) ® i ¯ x N otherwise

(6)

Step 7: Verification of stopping criterion A new generation of individual in population is created by DE, through substitutes the current generation. Iteration of this process until the termination criterion is satisfied. In this cases, a new generation is update by go on to step 3 until stopping criterion is met. B. Chaotic DE Chaos is a characteristic of non linier systems, even though it appears to be stochastic, it occurs in a deterministic non linier system under deterministic condition [13]. Recently, a number of literatures have been informed that the chaos system is a good alternative in procedure of stochastic optimization. This method can improve the performance of searching and avoid being trapped into local optimum [1]. Some examples of these systems are Lozi map, Logistic map (chaotic sequences), and Ikeda map [6]. Mutation factor in DE is one of the important parameter controls. Application of chaotic sequences in this parameter is a great scheme to expand the population and also to increase the performance of DE in avoiding early convergence to local minima. Equation of chaotic sequence is defined as follow x(m) = P . x(m – 1) . [1 – x(m – 1)]

(7)

222

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA) Where m and P are sample and control parameter, respectively. Both of parameters determines significantly, whether x stabilizes at a constant size, oscillates between a limited sequences of sizes, or behaves chaotically in an unpredictable pattern. A very small difference in the initial value of x causes substantial differences in its long-time behavior [1]. Algorithm of chaotic DE

child

i

for individual xN do child

and CR N

end for while criterion is not satisfied do i

for individual xN in PN do v1

v2

N

N

and x

child

(11)

Choose P Set N=1

v3 N

i

for individual x N do

child xN

PN+1 = PN+1 ‰ Best ( x N

(10)

Algorithm of random adjustment DE

Choose auxiliary parents x , x produce offspring

child ­ °F i if f ( x )! f N N avg ® ° ¯rand otherwise child ­ °CR i if f ( x ) f N N avg ® ° ¯rand otherwise

Here for each individual, the values of F and CR are randomly designed. Every time a new individual is produced, these values are selected based on the scheme in equation 10 and 11. The pseudo-code description of DE based on random adjustment algorithm (aDE) is presented in Fig.3 [8].

Initialization of object vector child

child

FN

CRN

Choose P Set N=1

calculate FN

randomly. In case of maximization problem, the following are equations to select F and CR parameters:

initialization of object vector

i

, xN )

i

i

set FN and CR N

end for set N = N + 1 end while

end for while criterion is not satisfied do i

for individual x N in PN do

Fig.2. Algorithm for the chaotic DE method

v1

v2

N

N

choose auxiliary parents x , x

In this work, the variety of P is 1 < P d 4, and the value of x is [0, 1] providing the initial x(1)  {0, 0.25, 0.50, 0.75, 1}. In chaotic DE (cDE), the parameters of F and CR were initialized and adjusted using chaotic sequences as mentioned before. The value of F and CR were updated through the following equation: (8) FN+1 = P.FN*[1 – FN] CRN+1 = P.CRN*[1 – CRN]

(9)

and x

v3 N

child

produce offspring x N child

set FN

child

and CR N

child

PN+1 = PN+1 ‰ Best ( x N

i

, xN )

end for set N = N + 1 end while Fig.3. Algorithm for the random adjustment DE method [8]

In this case, the initialization of F and CR are random and based on the boundary constraint. The pseudo-code of cDE algorithm is described in Fig. 2 [1]. C. Random adjustment DE Random adjustment of the parameter is commonly used for adaptation schemes in DE parameters. In this method, setting of parameter is done to create the individuals with high quality and in other cases fine-tune values of the parameters. The strategy is by comparing fitness value of the offspring child

( f (xN

)) with the average of fitness value in current child

generation ( f avg ) . If f ( x N

) is better than f avg , then

mutation factor and crossover rate of the primary parent are retained in offspring, or else the parameters are changed

IV. SIMULATION AND RESULT In this paper, the main concern of simulation is to improve image contrast enhancement using DE based on Chaotic and random adjustment approach. Our objective is to maximize the number of pixel in the edges of image, increasing the overall intensity at the edges and increase the measurement of entropy. There are five strategy methods employed in this simulation: first is classical differential evolution (DE); second is DE by random adjustment the value of F and CR in each individual (aDE-1); third is DE by random adjustment only the parameter of F in each individual (aDE-2); fourth is DE by modified the value of F using the chaotic sequences (cDE-1); and the fifth is DE by combination of chaotic and DE random adjustment (cDE-2).

223

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA) TABLE I.

SIMULATION RESULT OF CAMERAMAN IMAGE

F(z)

DE

aDE-1

aDE-2

cDE-1

cDE-2

Max (best)

0.1594

0.1599

0.1599

0.1599

0.1596

Min (worst)

0.1530

0.1567

0.1548

0.1541

0.1496

Mean

0.1552

0.1585

0.1575

0.1577

0.1569

Time (avg.)

57.6969

54.4930

56.6683

42.9779

57.9920

(a) Original: 0.0812

(b) DE-1: 0.1572

(c) aDE-1: 0.1587

(d) aDE-2: 0.1586

(e) cDE-1: 0.1589

(f) cDE-2: 0.1583

Since it is difficult to ensure the control parameters, we decided to determine the population size is 20 and stopping criterion is 40 for all the methods. Based on the preexperiment that were conducted, we used mutation factor and crossover rate for classical DE is 0.9 and 0.3 respectively. Fig. 5 The best enhancement result of Lena image

(a) Original: 0.1013

(b) DE-1: 0.1594

(c) aDE-1: 0.1599

(d) aDE-2: 0.1599

(e) cDE-1: 0.1599

(f) cDE-2: 0.1596

In general, the best simulation results of Cameraman images from all methods are not very different; since the difference results of objective function is not significant (0.1594, 0.1596, and 0.1599).

(a) Original: 0.0844

(b) DE-1: 0.1432

(c) aDE-1: 0.1434

(d) aDE-2: 0.1435

(e) cDE-1: 0.1436

(f) cDE-2: 0.1435

Fig.4 the best enhancement result of Cameraman image

We also set the parameters that we are looking for, that is Z = (a b c d), with value of boundaries: a = [0, 1.5], b = [0, 2], c = [0.5, 2], and d = [0.5, 30]. In order to evaluate the enhancement method based on adaptive DE approaches, four images were evaluated, i.e. Cameraman, Lena, Boat, and Rice. TABLE II.

BEST RESULT (20 RUNS) OF CAMERAMAN IMAGE

Parameter

DE

aDE-1

aDE-2

cDE-1

cDE-2

F(z)

0.1594

0.1599

0.1599

0.1599

0.1596

a

0.0513

0.0303

0.0280

0.0375

0.0267

b

1.2112

1.0267

1.1131

0.9934

1.1436

c

1.0898

1.0826

1.0868

1.0854

1.0938

d

29.9831

29.7917

30.0000

26.9187

29.6093

Fig.6 The best enhancement result of Boat image

Another simulation results are the best images for Lena, Boat, and Rice as showed in Fig 5, 6, and 7, respectively. These results of images are also a little bit different, for the reason that the objective functions for all methods are not significantly different, but better than the original images. TABLE III.

DE

aDE-1

aDE-2

cDE-1

cDE-2

Cameraman (0.1013)

0.1552

0.1585

0.1575

0.1577

0.1569

Lena (0.0812)

0.1541

0.1567

0.1552

0.1584

0.1557

Boat (0.0844)

0.1401

0.1418

0.1418

0.1421

0.1407

Rice (0.2019)

0.2508

0.2525

0.2518

0.2525

0.2523

Image

We converted all pictures into double precision for numerical computation. In this case study, every algorithm was implemented in Matlab, with 20 independent run times, and the objective function is given by Eq.(1). Comparison statistics for the simulation results of the Cameraman image is given in Table I, where the best results are printed in bold font. It is worth note that the best results for mean objective function F(z) is given by aDE-1, while the best time is obtained using cDE-1 method. Table II and Fig.4 show the best simulation result of Cameraman for each tested.

THE MEAN OBJECTIVE FUNCTION FOR IMAGES

The comparison of main objective function for all images are summarized in Table III, which shows that the method of aDE-1 is the best result in Cameraman image, while cDE-1 is the best result in Lena and Boat image. Both of methods have

224

2014 International Conference of Advanced Informatics: Concept, Theory and Application (ICAICTA) the same mean objective function in Rice image. Evaluations of computation time for all methods are shown in Fig.8. Illustration from this Chart shows that cDE-1 method is the best computation time in Cameraman (42.978 second), Lena (60.715 second), and Boat (57.886 second). In Rice image, the best computation time is aDE-1 (91.959 second).

function in Cameraman image. Both of methods have the best objective function in Rice image. The best computation time is cDE-1 method for all images, except for Rice image.

REFERENCES [1] [2]

(a) Original: 0.2019

(b) DE-1: 0.2536

(c) aDE-1: 0.2536

[3] [4] [5]

(d) aDE-2: 0.2536

(e) cDE-1: 0.2538

(f) cDE-2: 0.2537

[6]

Fig.7 The best enhancement result of Rice image [7]

[8] [9] [10] [11] [12] Fig.8 Average of the Computation Time results [13]

V. CONCLUSION

Coelho, L. S., J. G. Sauer and M. Rudek,”Differential evolution optimization combined with chaotic sequences for image contrast enhancement,” Chaos, Solitons and Fractals 42 (2009) 522 – 29. Munteanu, C. and A. Rosa, “Gray-Scale enhancement as an automatic process driven by evolution,” IEEE Transaction on systems, man, and cybernetics – Part B: Cybernatics, vol. 34, no.2, pp. 1292 – 1298, 2004. J. Liu and J. Lampinen, “A fuzzy adaptive differential evolution algorithm,” Soft Computing—A Fusion of Foundations, Methodologies and Applications, vol. 9, no. 6, pp. 448–462, 2005. A. K. Qin and P. N. Suganthan, ”Self-adaptive Differential Evolution Algorithm for Numerical Optimization,” in 2005 IEEE Congress on Evolutionary Computation, pp. 1785–1791. Brest, J., S. Greiner, B. Boˇskovi´c, M. Mernik, and V. ˇZumer, “SelfAdapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems,” IEEE Transactions on Evolutionary Computation, vol. 10, no.6, pp. 646 – 657, 2006. R. Senkerik, M. Pluhacek, D. Davendra, I. Zelinka, and Z. Oplatkova, “Chaos Driven Evolutionary Algorithm: a New approach for Evolutionary Optimization”, in Proc. 2013 International Conference on Systems, Control an Informatics, pp. 117 – 122. Y. Lu, J. Zhou, H. Qin, Y. Wang, and Y. Zhang, “Chaotic differential evolution methods for dynamic economic dispatch with valve-point effects,” Engineering Applications of Artificial Intelligence, vol. 24, no. 2, pp. 378–387, 2011. Noman, N., D Bollegala, H. Iba, “An Adaptive Differential Evolution Algorithm,” IEEE Evolutionary Computation (CEC), pp. 2229 – 2236, 2011. H.D. Cheng, H. Xu,” A novel fuzzy logic approach to contrast enhancement,” Pattern Recognition 33 (2000) 809 – 819. Gonzales R.C. and Woods R.E, Digital Image Processing. Reading, MA, USA: Addison-Wesley Publising COmpany, 1992. Boussaid, Ilhem, Julien Lepagnot, and Patrict Siarry, “A survey on optimization metaheuristics,” Information Science 237 (2013) 82 – 117. Tonge, V. G. and P. S. Chandrpur, “Performance Improvement of Differential Evolutionary Algorithm: A Survey,” Int. J.of Current Eng. And Tech., vol. 2, no.4, 2012. El-Santawy, M.F., A. N. Ahmed and R.A.Z. El-Dean,” Chaotic Differential Evolution Optimization,” Computing and Information System Journal, vol.16, no. 2, pp. 1 – 4, 2012.

Performance of classical DE is sensitive to the parameter setting, especially for mutation factor (F) and crossover rate (CR). In this paper, four variants of adaptive DE based on chaotic sequences and adjusting parameter are used for application of image contrast enhancement; i.e. aDE-1, aDE-2, cDE-1 and cDE-2. The objective of these worked to maximize the fitness criterion in order to enhance the contrast and detail the image has been achieved. Classical DE approaches were successfully applied to enhance the contrast and detail in four case studies of images; i.e. Cameraman, Lena, Boat, and Rice. However, the simulation result of adaptive DE based on chaotic sequences and random adjustment provide the best objective function compare to classical DE. Adaptive DE based on modification mutation factor using chaotic sequences (cDE-1) provides the best objective function in Lena and Boat, while aDE-1 has the best objective

225