Registration of Satellite Imagery Using Genetic Algorithm

Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. Registration of Satellite Imagery Using Genetic Algorithm Rakesh Singhai and Jyoti Singhai Abstract— Image Registration is the process of determining a are either feature based or intensity based. In feature based transform that provides the most accurate match between two similarity measure, the image is preprocessed to extract images. The search for matching transformation can be features such as edge and then geometric correspondence is automated with the use of suitable metric, but it is difficult to determine local maxima with direct search methods. In this established between these features. In this method, reliable paper a simple and powerful search strategy based on genetic algorithm is proposed to register satellite images. This method edge detection or image segmentation is required. In applies mutual information (MI) to measure statistical intensity-based method, preprocessing is not required. dependence of information redundancy between the image Cross-correlation is the most common intensity based intensities of corresponding voxels in both floating image and similarity metric used in image registration. Other intensity reference image. Partial Volume distribution interpolation (PV) is used to compute the MI criterion. Scope of the paper is based objective functions are intensity correlation, mean limited to pair of images, which are misaligned by rigid square difference of image intensity values, mutual transformation (i.e. rotation and/or translation). Performance information (MI) etc. In this paper, mutual information is of genetic algorithm based proposed approach is compared used as the similarity metric. Mutual information found to with existing search methods, which shows that the proposed be robust for satellite image registration and in medical approach overcomes the limitation of local maxima with the imagery [3][9][13]. desired accuracy and speed. In this paper, the mutual information between two satellite Index Terms— Image Registration, Mutual Information, images is maximized by optimizing the parameters using Interpolation, Genetic Algorithm Genetic algorithms (GA’s). Genetic algorithms (GA’s) [5][6] are mathematically motivated search techniques that try to emulate biological evolutionary processes to solve I. INTRODUCTION optimization problems. Instead of searching one point at a R EGISTRATION is the determination of geometrical transform that aligns points of an object in one view with corresponding points of that object in another view. time, GA’s use multiple search points. GA determines near- optimal solutions without going through an exhaustive search mechanism. Thus, GA can claim significant Registration of satellite images is often necessary for advantage of large reduction in search space and search integrating information taken from different sensors, time. In GA, search for function optimization starts from transponders, finding changes in images taken at different population of points in the function domain, instead of a times, elevation or under different conditions for model single point as in direct search method. This characteristic based object recognition and inferring three-dimensional suggests that GA is global search method. They can climb information from images in which either the camera on peaks in parallel, reducing the probability of finding local satellite or the objects in the scene have moved. Registration maxima, which is one of the drawbacks of traditional of satellite images require spatial (geometric) transformation optimization methods. mapping that establishes a spatial correspondence between all points in input gray level satellite image Si(x,y) and II. OPTIMIZATION OF MI USING GENETIC ALGORITHM reference image Sr(x,y). The main aim of image registration is to determine optimum transformation parameters that can The commonly used method as search strategy is simple best match the two images. The four components of image hill climbing search method. A simple hill climbing search registration which contribute to the optimization are feature method can give good performance, if the MI function of space, search space, search strategy and similarity metric the parameter space is enough smooth. The best situation is [1]. Image registration uses similarity measure by finding an that the MI value function is strictly monotonic, in that case, accurate match between an input image Si and transformed there are no local maxima, and a hill climbing search always versions of the reference image Sr. These similarity works [2][4]. This requires the spatial dependence of image measures intensity values. If this is not satisfied, the existence of too many local maximums of the MI function values will Manuscript received Feb26, 2011 mislead the process of finding the global maximum. In this Rakesh Singhai is with the Electronics Department, UIT, paper, a genetic algorithm based search method is proposed RGPV, Bhopal, India (email: [email protected]) to overcome this problem. Jyoti Singhai is with the Electronics Department, MANIT, Bhopal, India (email: [email protected]) ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online) Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. Figure 1 depicts the block diagram of the genetic evolution PAB (a, b) implemented in the proposed simulation. Let S be a solution I ( A, B)   PAB (a, b) log space where all the elements have their associated fitness a ,b PA(a ) * PB (b) values. The straightforward way to find the element with the MI of two images is maximal when these two images are maximum fitness value is to search among all the elements perfectly aligned [11]. Therefore, image registration is and to compare their fitness values. However, the achieved by adjusting relative position and orientation of computational complexity will be very high if the space size images, until their mutual information is maximized. is large. In order to reduce the computational complexity, an For individual selection, we select highly fit individuals efficient search algorithm should be applied. with higher mutual information values based on Partial In most GA’s based applications, random selection of Volume distribution interpolation [12]. Chromosomes with elements from the solution space creates the initial larger MI values in the current population have higher population [8][14]. As shown in Figure 1, first block probability to be selected as seeds of the next generation. generates a population P consisting of elements and The reproduction method used in this work is similar to the population size N. Each element in P is a chromosome, weighted Roulette wheel method [6]. The relative weight of which is composed of a list of genes. The population will the fitness values for each chromosome i can be expressed evolve into another population by performing some genetic as follows. operations. The chromosomes with higher fitness values fi Fi  will have more probability to be retained in the population of the next generation, and to propagate their offspring. On  fi i the other hand, the stronger chromosomes will replace weak where Fi is the weighted fitness of a chromosome i and fi is chromosomes whose fitness values are small. Therefore, the the fitness of chromosome i. The Roulette selection assigns quality of the chromosomes in the population will be better probability to each chromosome i, using the Fi value. The and better. After a suitable number of generations, the roulette wheel is partitioned into sectors as in Figure 2 mature population will be expected to contain the elements corresponding to the weighting obtained from Fi. The with the global maximum value. In this application, the spinning of the wheel begins by generating a random solution space S is a 32-bit binary data. In which the first 12 number. If the number falls into a portion that belongs to a bits represent the rotation angle, next 10 bits represent X- specific individual, that individual is selected. When the translation and the last 10 bits represent Y-translation. The interval of each chromosome has been determined, N real ith chromosome Ci in the population is defined as Ci = [bi1 numbers, Rn , for n=0,1,…N-1, are randomly generated, bi2 …………..bi32]. where 0 ≤ Rn < 1 F2 Region Information. 20% Initial Population F2 F3 20% F1 Initial Population Fitness Survival 10% 40% evaluation competition Generator (S) (P) F4 Reproduction 30% Feature point Figure 2 A Roulette wheel for chromosome selection Crossover The chromosome Ci is then selected as a seed to generate the rival population. It is possible that one chromosome can Mutation be selected twice or more. Because real random numbers are generated, seeds could be selected and placed in the mating pool. The seeds will be processed by the genetic operations of crossover and mutation. As part of the reproduction, the crossover is a recombination operator for a Figure 1 Block Diagram of the adopted Genetic Algorithm pair of chromosomes. The crossover method used here is the The objective function in image registration is to maximize so-called uniform crossover [7]. For every two seeds CL and the mutual information between the reference and input N 1 images. This means that the fitness function is simply the CN-1-L, 0 ≤ L ≤ selected from the mating pool, two mutual information between the transformed image and the 2 reference image [10]. The correlation function between two new chromosomes are produced by performing uniform images A and B to be registered with marginal probability crossover operations as distributions PA(a) and PB(b) and joint probability PAB(a,b) M i  (mi  Mx)  (mj  M y ) is given as M j  (mi  M x)  (mj  My) ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online) Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. where M i and M j represent the new chromosomes, the population size is usually not large in this case. This stage is added in the proposed algorithm to prevent the mi and mj are the original chromosomes selected from the chromosomes from being destroyed by the new ones with mating pool, Mx and My are two randomly generated bit poorer fitness values, because the new chromosomes masks. M x and M y are the complements of Mx and generated from the original ones are not guaranteed to have larger fitness values in GA’s. The chromosome with the My respectively. The simplest crossover is called a single- maximum fitness value is selected from the current point crossover. Usually, the crossing point is randomly population as the possible solution. The other ones from a selected. For example in Figure 3, the genes in two 8-bit generation to the other generations might replace the chromosomes A and B are exchanged at the cross point 2 possible solution. The iteration will be terminated if the from the left. This produces two new chromosomes C and solution is not updated for a predetermined period of D. iterations Crossover point III. EXPERIMENTAL EVALUATION A. Spatial Dependence Of Image Intensity And Smoothness Of MI Function A 00000000000 Spatial dependence of image intensity values will result in the smoothness of MI values. The Figure 4 and 5 show B 11111111111 the MI values corresponding to different rotation angles and translation. Figure 4(a) is the result based on NN interpolation, and Figure 4(b) on PV interpolation. It is C 00111111111 clearly seen that at the center, which indicates no rotation, a new chromosomes max MI value is attained, and MI value shows some D 11000000000 smoothness in the neighbour of the no rotation position. Figure 3 An example of a single-point crossover New elements from the search space are explored by applying crossover operations. In the proposed algorithm, we have used many types of cross over are implemented to get better results and compare the performance such as simple, uniform, non-uniform, arithmetic , heuristic, single point and two point. After the crossover stage, each chromosome in the mating pool is processed and transferred into a candidate chromosome of the new generation. Mutation is a random change of the gene. For example, an 8-bit chromosome ‘0000 0000’ can be mutated at bit 4 to produce a new chromosome ‘0001 0000’. Mutation offers the opportunity to introduce new genetic material into a population. Mutation is useful for avoiding local optima Figure 4(a) MI for NN interpolation problems. It occurs, after the crossover, only at a small percentage of the time. In the proposed algorithm, various mutations like uniform, non-uniform, shift, swap, adjacent swap, binary, boundary mutations are used with the mutation rate of 0.01. Using the mutation rate of 0.01, each selected individual is mutated by randomly altering one bit in the chromosome string. The position of the bit to be altered is also randomly selected. The proposed GA-based algorithm stops when the solution has converged or a certain number of generations is reached. There are chromosomes in the mating pool after performing the genetic operations. Along with the original chromosomes in the current generation, chromosomes are selected from these chromosomes according to their fitness values .The chromosomes with larger fitness values will be picked up as the members of the population in the next Figure 4(b) MI for PV interpolation generation, and go through the next iterations of the genetic evolution. Although the sorting operation is needed in the survival competition stage, the overhead is not high because ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online) Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. Furthermore, the PV interpolation shows more climbing search method provides the best accuracy, but fails smoothness than NN interpolation, which indicates more when local maxima occur. Genetic search method is suitable robustness of the algorithm. This is proven in the for any range of data at the cost of speed. Table IV shows experimental results of searching. that as the number of generations in GA is increased the execution time also increases. B. Description Of Test Data Sets Performance of proposed algorithm is evaluated on two IV. CONCLUSION data sets, namely a remote sensing imagery of Bhopal city and group of four satellite images. The 601  701 BPL.tif In the proposed algorithm, registration of rigidly image is the image of Bhopal city, which is artificially transformed satellite images is implemented with an translated and rotated to create data set for testing the optimization strategy i.e. genetic algorithm (GA). GA is algorithm. In these images translation parameters are varied applied to optimize search space and the results of proposed in the horizontal direction by 0 to 100 pixels and rotation algorithm are compared with the conventional hill climbing parameters are varied with angles ranging from 0 to 6o. search method. The experimental results show that mutual Reference image of Bhopal city is shown in Figure 5(a), information criterion applies well to image registration. The while translated and rotated images are shown in Figure mutual information criterion states that the images are 5(b) to Figure 5(f). The second data set is group of four geometrically aligned by the transformation for which different image pairs of the same scene due to satellite I(A,B) is maximal. Partial Volume interpolation method rotation, in which one is reference and the other is the input improves the smoothness of the mutual information function image as shown in Figure 6(a) and 6(b). The reference and and reduces the chances of local maxima, but it needs more calculated transformation parameters are tabulated in Table time compared to nearest-neighbour scheme for each mutual II. information evaluation. C. Algorithm Implementation The results show that the average RMSE calculated for data A series of experiments is conducted using synthatic set I with GA for 200 generations is 0.043, which is images from the dataset 1 . The two search methods “simple improved as compared to RMSE of 0.18 of hill climbing hill climbing search” and “genetic algorithm search” are search method. Similarly, for second data set average used to get registration parameters. RMSE value for y translation is reduced from 5.93 of hill Search space used in simple hill climbing search method climbing search to 1.65 of genetic search with 200 were Angle Range from 0 to (pi/30=0.1047)*2,i.e. the true generations. Timing accuracy shows that genetic search solution lies at the center; Translation along x direction from gives good speed as 1.9160 seconds, which is comparable -10 to 10, the true solution lies at the center; Translation with 2.213 of hill climbing search. The GA with 25 along y direction from -10 to 10, the true solution lies at the generations takes 0.7190 seconds, which gives better speed, center. but at the cost of accuracy. Search space used in Genetic Algorithm method is rigid transform. For this search space chromosome, encoding is Genetic Algorithm (GA) is a good searching strategy to tabulated in Table I. overcome the limitation of local maxima and is also suitable for the mutual information maximization process. It is based D. Image Registration Accuracy on crossover, mutation, and selection idea. However, the limitation of GA algorithm is decrease in its speed, if the The registration accuracy for three types of search numbers of generations are increased to improve the method i.e. using simple hill climbing search method, accuracy. Combination of traditional gradient based method genetic search with 25 generations and genetic search with and GA may give good performance. 200 generations are compared in terms of RMSE of the registered image with respect to the reference image. Table REFERENCES II represents the results of data set 1 which shows the [1] L. G. Brown, “A survey of image registration techniques,” ACM average RMSE values for the above three methods. Table Computer Survey, vol. 24, no. 4, pp. 325–376, 1992. III represents the results of data set 2, which shows the [2] F. Maes, A. Collignon, D. Vandermeulen, G. Marchal, and P. average RMSE values for the same three search methods. In Suetens,“Multimodality image registration by maximization of mutual Table II and III, dX and dY are translation in x and y information,” IEEE Transaction on Medical Imaging, vol. 16, April direction in pixel and dR is the rotation in degree. 1997. [3] W. M. Wells III, P. Viola, H. Atsumi, S. Nakajima, and R. Kikinis,“Multi-modal volume registration by maximization of mutual information,” Medical Image Analysis, vol. 1, pp. 35–51, 1996. E. Timing Performance [4] Zhang xiangwei,“Image Registration by Maximization of Mutual Information,” Homework #3 of Advanced Image Processing 2004. Table IV summarizes the total execution time of the [5] M. Srinivas and L. M. Patnaik,“Genetic algorithms: A survey,” IEEE image registration methods using three types of search Computer Magazine, vol. 27, pp. 17–26, June 1994. methods. The genetic algorithms provide significant computational savings over the exhaustive search. The hill ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online) Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. [6] K. S. Tang, K. F. Man, S. Kwong, and Q. He, “Genetic algorithms and [11] Philippe Thevenaz,Michael Unser,“Optimization of Mutual their applications,” IEEE Signal Processing Magazine, vol. 13, pp. Information for Multiresolution Image Registration,” IEEE 22–37, Nov. 1996. Transactions On Image Processing, vol. 9, no. 12, December 2000 [7] S. K. Pal, D. Bhandari, and M. K. Kundu,“Genetic algorithms for optimal image enhancement,” Pattern Recognition Letter, vol. 15, pp. [12] Qi Li,Isao Sato , Yukata Murakami, “Interpolation Effects on 261–271, 1994. Accuracy of Mutual Information Based Image Registration”, IEEE [8] J.B.A. Maintz, and M.A.Viergever, “A Survey of Medical Image conference of Geoscience and Remote Sensing Symposium,IGARSS Registration,” Medical Image Analysis, vol. 2, no.1, pp. 1-36, 1998. 2006 [9] Hua-Mei Chen and Pramod K Varshney,“Mutual Information–Based [13] Ingole, V.T. Deshmukh, C.N. Joshi, A. Shete, D., “Medical Image CT-MR Brain Image Registration Using Generalized Partial Volume Registration Using Genetic Algorithm,” 2nd International Conference Joint Histogram Estimation,” IEEE Transactions on Medical Imaging, on Emerging Trends in Engineering and Technology (ICETET), 2009 vol. 22, no.9 , September 2003 [14] Ibrahiem M.M. El-Emary and Mona M. Abd El-Kareem, “On the Application of Genetic Algorithms in Finger Prints Registration,” World Applied Sciences Journal 5 (3): 276-281, 2008. Table I: Search space for GA Search space Chromosome encoding Transform Bit Length Range Scope Rotation 12 ± 2048 ±20.48º X Translation 10 ±512 ±5.12 pixels Y Translation 10 ± 512 ± 5.12 pixels Table II: RMSE performance for data set 1 Input Ground Truth Hill Climbing Search GA (25 Generations) GA (200 Generations) Images (transformation parameter) dR dX dY dR dX dY dR dX dY dR dX dY BPL_a.tif 0 0 0 -0.12 0.12 -0.15 0.02 0.22 -0.32 0.05 -0.16 -0.47 BPL_b.tif -10 0 0 -10 -0.21 -0.02 -9.69 0.13 -0.5 -10. 0.01 -0.02 BPL_c.tif 18 0 50 17.54 0.48 50.22 17.86 -0.14 51.01 18.02 0.06 50.1 BPL_d.tif 4 50 0 3.96 50.29 -0.48 4.17 49.67 0.09 3.97 49.99 0.02 BPL_e.tif 4 53 0 4.14 52.83 0.25 3.92 52.74 -0.9 3.99 52.50 0.05 BPL_f.tif 4 5 -2 3.96 5.23 -2.03 3.69 5.07 -1.88 4.09 4.50 -2 Avg. 0.18 0.381 .354 0.15 0.24 0.206 0.043 0.069 0.18 RMSE Table III: RMSE performance for data set 2 Input Ground Truth Hill Climbing Search GA GA Images (25 Generations) (200 Generations) dR dX dY dR dX dY dR dX dY dR dX dY Sat_a1 & Sat_a2 0.5 16 5 1.1 12 10 0.81 16 4 0.6 14 6 Sat_b1 & Sat_b2 0.2 5 16 2.1 8 20 0.21 5 11 0.21 4 15 Average RMSE .82 8.3 5.93 .478 2.56 2.80 0.42 1.31 1.65 Table IV: Total Execution Time Average Time(Sec.) Input Hill climbing Search GA (25 generations) GA (200Generations) Data Set 1 3.219 1.0231 2.224 Data Set 2 2.213 0.7190 1.9160 ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online) Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K. Figure 5(a) BPL_a.tif Figure 5(b) BPL_b.tif Figure 5(c) BPL_c.tif Figure 5(d) BPL_d.tif Figure 5(e) BPL_e.tif Figure 5(f) BPL_f.tif Figure 5: Data set 1: Satellite Reference Image and translated/ rotated satellite images of Bhopal city, India Figure 6(a1) Sat_a1.tif Figure 6(a2) Sat_a2.tif Figure 6(b1) Sat_b1.tif Figure 6(b2) Sat_b2.tif Figure 6: Data set 2: Satellite Image pairs of the same scene due to satellite rotation ISBN: 978-988-19252-1-3 WCE 2012 ISSN: 2078-0958 (Print); ISSN: 2078-0966 (Online)