Unsupervised Change Detection of Multispectral Images using Genetic based Particle Swarm Optimization

Unsupervised Change Detection of Multispectral Images using Genetic based Particle Swarm Optimization

Mrs.S.Gandhimathi@usha1, S.Vasuki2, P. Jega Suguna3, V.Janaki4, S.Jaya Priya5 Department of Electronics and Communication Engineering

Velammal College of Engineering and Technology, Viraganoor, Madurai.

Abstract This paper, proposes a novel method for unsupervised change detection in multispectral images using Genetic based Particle Swarm Optimization (GPSO). GPSO algorithm is a combination of two optimization algorithm used to search and find the change detection rapidly and efficiently. To achieve this it operates on a difference image, which is created by using multi-temporal images, by iteratively processing fitness function with GPSO to produce a nal change-detection map representing changed and unchanged pixels. GPSO initialized with a different starting population representing a set of change-detection masks. This iteration improves both the convergence rate and detection performance. The fitness function of GPSO is better because the RMV is considered as the fitness parameter but in BPSO probability is considered as the fitness parameter. The Mean Square Error (MSE) is reduced and Peak to Signal Ratio (PSNR) is increased. From the experimental results, it is observed that the proposed approach effectively optimizes the change detection problem and nds the nal change detection map.

Index Terms Remote sensing; Image processing; Optimization; Genetic algorithm; Binary particle swarm optimization; Genetic based Particle Swarm Optimization (GPSO).

1. INTRODUCTION

   THE Remote Sensing refers to the activities of recording and perceiving (sensing) objects or events at far away (remote) places. It is an efficient tool for rapid mapping application, which is defined as a method of getting the information about properties of object without coming into physical contact [1]. Identifying changes in the multi- temporal images is an important concept in various disciplines. Nowadays change detection in satellite images has become a major research area. Changes may be observed due to rapid environmental changes. Many methods have been proposed or developed to nd changes through the remote sensing images.

   Mainly, there are two categories in Change detection. They are, supervised method and unsupervised method [2],[3]. There are several major change detection technique categories they are, Algebra based approach, Transformation, and Classification based, advanced method, GIS, visual analysis and many other change detection techniques.

   Supervised change-detection algorithms utilize a training set to learn patterns that can be used to detect changes in the image [13]. However obtaining the training set

   is difficult. Unsupervised change-detection algorithms compare multi-temporal images or process the difference image using pattern recognition techniques. There is no need for a training set in this algorithm [14]. Due to the lack of training, the system with a huge data makes the unsupervised approaches more popular than the supervised ones.

   Fuzzy c-means [17], k-means [18], and normalized cut clustering [19] methods, have been also used to solve change-detection problem. Clustering is a mathematical tool that attempts to discover structures or certain patterns in a dataset, where the objects inside each cluster show a certain degree. The negative effects of high dimensional data sets can be reduced by adjusting the parameter of the algorithms, i.e. the fuzzier, depending on the number of dimensions.

   PSO (Particle Swarm Optimization) is a population based search algorithm based on the simulation of the social behavior of particles [11]. It is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. The algorithm was simplified and it was observed to be performing optimization.

   This algorithm originally intends to graphically simulate the unpredictable movement of a bird folk. Each individual within the swarm is represented by a vector in multi-dimensional search. This vector has one assigned vector which determines the next movement of the particle and is called the velocity vector. The PSO algorithm also determines how to update the velocity of a particle. Each particle updates its velocity depending on current velocity and the best position it has explored so far; and also based on the global best position explored by swarm. But in discrete or binary version there are still some difficulties. A number of benchmark optimization problems are solved using this concept and quite satisfactory results are obtained. The BPSO algorithm was introduced to allow the PSO algorithm to operate in binary problem spaces. It uses the concept of velocity as a probability that a bit (position) takes on one or zero. In order to achieve this, the randomly initialized particles are divided into groups of sub-population and transmitted to BPSO in the processor. The fitness function of BPSO may be a little lower and thus genetic algorithm is combined with the PSO method [12].

   A new unsupervised satellite change-detection method, which is strong to optimal illumination changes [13]. This method is used to find solutions in change detection problem using the functions of genetic algorithm. A fitness function is a type of objective function that is used to comprise, as a single figure of merit, for given design solution in achieving the set aims. Two main significance of fitness functions are one where the fitness function does not change, as in optimizing a fixed function and one where the fitness function is mutable

   In this paper, Genetic algorithm performs a search over a complex and multimodal space and is an important component in several applications such as evolutionary learning and optimization. The search is dependent on several parameters including the fitness function, parent selection process, mutation and crossover rate. The fitness function is an important factor in the evolutionary process since its performance metric is used to select the best individuals in a population that will come through the mutation, crossover and reproduction process in successive generations.

   The rest of the paper is organized as follows: In section 2, the fundamentals of Binary PSO and parameters for change detection are summarized. In section 3, the proposed change detection method GPSO is discussed and in section 4, experimental results and performance evaluation are presented. Section 6 describes the conclusion.

2. BINARY PSO AND PARAMETERS FOR CHANGE DETECTION

   In binary PSO the velocity of a particle defined as the probability that a particle might change its state

3. PROPOSED CHANGE-DETECTION METHOD The proposed method is a Genetic Particle Swarm

   Optimization (GPSO) based feature selection algorithm to solve the optimization issues of feature selection in change detection. We select the Ratio of Mean to Variance (RMV) as the fitness function of GPSO, apply the proposed algorithm to the object-based multivariate alternative detection model.

   1. Normalization Technique

      Illumination change is one of the main reasons to cause false detections on traditional change detection methods. For instance, multi-temporal images that are taken on the same scene on different timings.

      Therefore, it is vital to propose a framework which is robust against illumination. In order to achieve this, RGB

      colors are normalized to be insensitive to brightness

      to one.

      x t 1 0

      if rand S v t 1

      differences of images.

      1

      i, j

      if rand

      S vi, j t 1

   2. Estimation of Difference Image

      The second step is to create the difference image by

      It should be noted that the BPSO is susceptible to

      using the multi-temporal multispectral images

      xn1 and

      xn 2

      saturation, which occurs when velocity values are either too

      . Let xn d d be the difference image computed on the

      large or too small. In such cases, the probability of a change in bit value approaches zero, thereby limits exploration.

      spectral band n. The difference image using the following formula.

      xn d

      is obtained by

      There are two important steps to apply in PSO. One is the representation of the solution of particles and other one is to apply tness function regarding to the optimization problem.

      The final binary change-detection mask is estimated by finding the changed and unchanged parts on the difference image. To achieve it, change-detection mask is created as a possible global solution with H ×W × n matrices and there are

      2(H×W)3 possible solutions in the change-detection problem [20].Therefore, it is a challenging optimization problem to find the optimum change-detection mask. In order to solve this problem, the population created by the proposed method is divided into the M groups and each group of particles is employed by using individual BPSO algorithm in the corresponding processor independently.

      xn x, y log xn x, y log xn x, y

      d 2 1

   3. Ratio of Mean to Variance

      According to purpose of the change detection, we are choosing RMV as its fitness function for evaluating the fitness of particles in the GPSO algorithm, which denote the availability of the candidate feature in the image object feature dataset. Select the Ratio of Mean to Variance (RMV) as the fitness function of GPSO, and apply the proposed algorithm to the object-based multivariate alternative detection model. In general, the mean and variance of any data set are related to an important feature information, so some features are used to compare the samples belonging to different classes [15]. This denotes the separability of a multi- class sample by normalizing its mean of the feature data set according to its variance and comparing them among the different classes.

      Assume A and B are feature datasets belong to different classes, where A is the data set of the changed samples that have the feature f, and B is the dataset of the unchanged samples that has feature f[16]. Then, importance of feature f can be expressed by

      Equations:

      Sf | meanf ( A) meanf (B) |Vf Vf Varf ( A)nA Varf (B)nB

      where sf is the significance of feature f and represent their potential to classify two dataset A and B,

      mean f A and mean f B are the means datasets A and

      B, Varf a and Varf B are their variances of datasets A

      and B, and n A and n B are the number of samples in A and B, respectively[17].

      The optimal features are selected from the feature dataset once the features are sorted by the feature importance index. Assume that M features are selected, then the importance matrix S will be constructed by obtained important index of M features for every class, and the mean value of the feature importance in S AVG can be calculated using the feature importance matrix S, which has M feature importance indices:

      Savg 1m f 1mSf

      In the GAPSO, there are two different cases to share or exchange the individuals between the sub-populations of simultaneously running meta-heuristic algorithms.

      1. If there is a large variance in one of the sub- population of GA or PSO, the GA or PSO needs large number of iteration or substantial time to reach the optimum result. Stronger individuals are sent from one algorithm to the other algorithm.

      2. If there is a small variance in both sub- populations of GA or PSO, both sub-algorithms need large number of iteration or substantial time to reach the finest result. Best individuals are exchanged between two sub- populations.

4. RESULTS AND DISCUSSIONS

   We assess the performance of our method in terms of Qualitative and quantitative tests on both semi-synthetic and real multi temporal multi spectral data sets. The data set is the area of conifer mortality of the Hanoi, Vietnam. The data sets have been obtained from the Earth Resources Observation and Science (EROS) Centre and United States Geological Survey (USGS).

   The first data [19], shown in Fig. 1 and Fig.2, is the set of Land sat images with the size of 200 × 200. They were Captured on two different dates in 1986 and 1992. These Images are used to observe the changes in the forest area for analysing and understanding the amount of drought in the area.

   The objective function J is given as follow:

   J Vs S2Avg

   Vs f

   1mSf ;

   It is apparent that the larger values of S,AVG and J indicate stronger classification capability of the selected featured subset from the featured dataset, so the fitness function of RMV is:

   Fitness (RMV ) VS *(1m f

   1mSf ) 2

   1. Genetic based Particle Swarm Optimization

   In the proposed method, Genetic based PSO is used to optimize the change detection problem to nd the nal change detection map. GA and PSO are the population-based algorithms that have similarities and diversities between each other to optimize a search space problem. In the GA-PSO, two sub-algorithms which are GA and PSO run simultaneously and each algorithm uses its own generation process to create new individuals in each iteration as shown in Fig. Note that, generation processes of GA and PSO are given with the details in [17] and [18]. Each sub-algorithm in the GAPSO may need additional information if the distribution or variance of individuals is very high in their own population pool. Therefore, they have to inform others to reduce the variance by sharing their best tness values and representation solutions in each iteration. Thus, the quality of mutual information is increasing in the sub-algorithms to achieve the optimum result.

   Fig1. Input image 1 Fig 2. Input image 2

   The input images are given in fig 1 and fig 2. It is a multispectral image from which only selected bands are being processed. These images are being taken from different time period. These images are used to determine the history of the regions.

   Fig3. Segmented image of Fig4.Segmented image of Fig1 Fig2

   The segmented images are given in fig 3 and fig 4. They are being segmented from the input images. These are being done in the pre-processing stage and are considered to be in binary or gray level.

   Fig5. The iteration curve of Fig6.Change detection of BPSO BPSO

   The iteration curve of the BPSO method is given in fig 5. This curve determines the number of iterations being done in the BPSO method. The change detection in fig 1, the first input image is given in fig 6. It is considered to be the final output image from the BPSO methodology.

   Fig7. The iteration curve of Fig8. Change detection of GPSO GPSO

   The iteration curve of the proposed GPSO method is given in fig 7. It shows the iterations required to complete the process. The fitness value is comparatively compared to the BPSO method. The change detection of the GPSO is given in fig 8. It shows only the significant changes unlike the BPSO method.

   Fig9. MSE values of Fig10. PSNR values of BPSO and GPSO BPSO and GPSO

   The comparison of Mean Square Error (MSE) value between BPSO and GPSO is given in fig 9. The MSE value of BPSO is high compared to GPSO method. It should be low in order to get better results and it is being found lesser than the BPSO method. The comparison of PSNR value between BPSO and GPSO method is being given in fig 10. It is higher for the proposed method and it because of improved fitness value. Increase in it makes the output better.

   TABULATION

   Methodology	Mean Square Error	Peak Signal to Noise Ratio
   Base method	84.9513	28.8391
   Proposed method	51.0318	31.0524

   This tabulation shows the comparison between the BPSO and GPSO algorithm with the help of the MSE and PSNR values. The main significance of GPSO method is that it should have improved PSNR value and reduced MSR value compared to BPSO method.

5. CONCLUSION

In this paper, a new unsupervised approach is presented to find changed and unchanged pixels between satellite images. Our algorithm consists of two main steps. First, a pre-processing method is used to the input images to remove the illumination. The second one is to use the method by running the GA and PSO simultaneously to increase the probability of finding the optimal solution quickly and efficiently. After that, final change detection map is obtained by minimising a cost function which is based on the enhanced correlation coefficient similarity measurement. The proposed method presented in this paper minimises the change detection optimisation problem effectively to utilise local and global search capabilities of PSO and GA, respectively, to reduce the computational burden. Qualitative and quantitative tests on two different data sets show that our method remarkably reduces the error compare to other methods. The changes with significance are alone shown in the proposed method. It makes the final output clear and better understanding is obtained.

REFERENCES

1. T. Lillesand, R. Kiefer, and J. Chipman, Remote Sensing and Image Interpretation, 2nd ed. Hoboken, NJ: Wiley, 2008.

2. X. Liu and R. G. Lathrop, Urban change detection based on an articial neural network, Int. J. Remote Sens., vol. 23, no. 12, pp. 25132518, 2002.

3. Amir Yavariabdi, and Turgay Celik, Unsupervised Change Detection in Multitemporal Multispectral Satellite Images Using Parallel Particle Swarm Optimization April 15, 2015.

4. X. L. Dai and S. Khorram, Remotely sensed change detection based on articial neural networks, Photogramm. Eng. Remote Sens., vol. 65, pp. 11871194, 1999.

5. T. Kasetkasem and P. Varshney, An image change detection algorithm based on Markov random eld models, IEEE Trans. Geosci. Remote Sens., vol. 40, no. 8, pp. 18151823, Aug. 2002.

6. T. Celik, Unsupervised change detection in satellite images using principalcomponentanalysisandK-

   meansclustering,IEEEGeosci.Remote Sens. Lett., vol. 6, no. 4, pp. 772776, Oct. 2009.

7. P. Deer and P. Eklund, Values for the fuzzy C-means classier in change detection for remote sensing, in Proc. Int. Conf. Inf. Process. Manage. Uncertainty, 2002, pp. 187194.

8. Y. Zheng, X. Zhang, B. Hou, and G. Liu, Using combined difference image and k-means clustering for SAR image change detection, IEEE Geosci. Remote Sens. Lett., vol. 11, no. 3, pp. 691695, Mar. 2014.

9. X. Zhang, Z. Li, B. Hou, and L. Jiao, Spectral clustering based unsupervised change detection in SAR images, in Proc. Int. Conf. Geosci. Remote Sens. Symp., 2011, pp. 712715.

10. T. Celik, Change detection in satellite images using a genetic algorithm approach, IEEE Geosci. Remote Sens. Lett., vol. 7, no. 2, pp. 386390, Apr. 2010.

11. L. Bruzzone and D. Prieto, Automatic analysis of the difference image for unsupervised change detection, IEEE Trans. Geosci. Remote Sens., vol. 38, no. 3, pp. 11711182, May 2000.

12. P.GhamisiandJ.A.Benediktsson,Featureselectionbasedonhybridizati on of genetic algorithm and particle swarm optimization, IEEE Geosci. Remote Sens. Lett., vol. 12, no. 2, pp. 309313, Feb. 2015.

13. Y. Zheng, X. Zhang, B. Hou, and G. Liu, IEEE Geosci. Using combined difference image and k-means clustering for SAR image change detection, Remote Sens. Lett., vol. 11, no. 3, pp. 691695, Mar. 2014.

14. X. Liu and R. G. Lathrop, Urban change detection based on an articial neural network, Int. J. Remote Sens., vol. 23, no. 12, pp. 25132518, 2002.

15. Y. Bazi, L. Bruzzone, and F. Melgani, An unsupervised approach based on the generalized Gaussian model to automatic change detection in multitemporal SAR images, IEEE Trans. Geosci. Remote Sens., vol. 43, no. 4, pp. 874887, Apr. 2005.

16. C. Carincotte, S. Derrode, and S. Bourennane, Unsupervised change detection on SAR images using fuzzy hidden Markov chains, IEEE Trans. Geosci. Remote Sens., vol. 44, no. 2, pp. 432 441, Feb. 2006.

17. KevinBeyer,JonathanGoldstein,RaghuRamakrishnan,andUriShaft. Whenisnearestneighbor meaningful? In Database Theory – ICDT99, volume 1540 of Lecture Notes in Computer Science, pages 217235.

    Springer Berlin / Heidelberg, 1999

18. O. S. Soliman, A. S. Mahmoud, and S. M. Hassan, Remote sensing satellite images classication using support vector machine and particle swarm optimization, in Proc. Int. Conf. Innovations Bio- Inspired Comput. Appl., 2012, pp. 280285.

19. M.J.Dumskyj,S.J.Aldington,C.J.Dore,andE.M.Kohner,The accurate assessment of changes in retinal vessel diameter using multiple frame electro cardiograph synchronised fundus photography, Current Eye Res.,vol.15,pp.652632,1996.