# A Novel Frequency Domain Iterative Image Registration Algorithm Based on Local Region Extraction

Authors: Xiujie Qu; Haili Huo; Sitong Lian; Fei Zhao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Because of the differences of imaging time, position between sensor and target position, scaling, rotation, translation, and other transformations between the series of images will be generated by the imaging system. The conventional phase correlation algorithm has been widely applied because of its advantages of high speed, precision, and weak influence of the geometric distortion when computing these changing parameters. However, when the scaling factor and the rotation angle are too large, it is difficult to use the conventional phase correlation method for high precision registration. To solve this problem, this paper presents a novel method, which combines the speeded up robust features algorithm and the phase correlation method under the log polar. Through local region extraction and reusing a two-step iterative phase correlation algorithm, this method avoids excessive computation and the demand of characteristics of the image and effectively improves the accuracy of registration. A plurality of visible light image simulation verifies that this is a fast, accurate, and robust algorithm, even when the image has large angle rotation and large multiple scaling.


---

## Body

## 1. Introduction

Image registration is a process of matching and superposing two or more images obtained from different time, different angles, and different sensors [1]. With the rapid development of science and technology, image registration technique has been widely used in medical image processing, computer vision, remote sensing image processing, target recognition, and so forth. At home and abroad, three aspects are mainly concentrated in the research on image registration at present: feature space, search strategy, and similarity measure [2–4]. Image registration methods can be roughly divided into two categories: first, the spatial domain registration method relying on the gray information, for example, mutual information based registration and feature based registration [5]; second, the frequency domain registration method, for example, cross correlation registration and phase correlation registration based on Fourier transform [6–8]. The conventional spatial domain registration method has a large amount of calculation and slow execution speed. It is difficult to effectively suppress the image geometric distortion. For the image without distinguishing characteristic, feature based registration method also cannot reach the expected purpose. When the scaling factor and the rotation angle are too large, the conventional phase correlation method cannot get satisfying result of registration either. Literature [9] proposed an algorithm based on mutual information and Fourier-Mellin, which can achieve the image registration with large scaling factor and the rotation angle at the same time. But it is difficult to meet the real-time registration because it is time consuming. Literature [10] proposed an algorithm which is of great randomness and is very difficult to guarantee to obtain suitable region when intercepting the reference image and the image to be registered. This paper proposes a novel frequency domain iterative image registration algorithm based on local region extraction. First, one pair of angular points which are close to the central region between the reference image and the image to be registered are detected, and the local area is intercepted at the same time by the SURF algorithm. Second, the large scaling factor of intercepted image and the rotation angle can be roughly estimated by the Fourier-Mellin algorithm. Then, those parameters can be compensated according to the estimated results, precisely estimated by Fourier-Mellin algorithm once again. Finally, the precise registration parameters are obtained. The simulation results of multiple images indicate that this method has obvious advantages of speed and accuracy of image registration and shows good universality and robustness compared with the conventional phase correlation algorithm and the method of literature [9].


## 2. Phase Correlation Registration Algorithm

### 2.1. Phase Correlation Method for the Translation Parameters

Phase correlation method is proposed by Kuglin and Hines. First, the images are transformed from the time domain to the frequency domain through the fast Fourier transform. Then the translation vectors between the two images are directly calculated through their cross power spectrum, thus determining the relations of the image location [11, 12]. Phase correlation algorithm has now been extended to image registration applications in which the two images differ from each other in rotation and scale [13]. Rotation and scaling transformation on the Cartesian coordinates can be converted to translation transform on the log-polar coordinates, so the image rotation and scaling parameters can be extracted according to phase correlation algorithm. This paper discusses the case under the condition of relatively large scaling factor and the rotation angle. Principle of phase correlation technique: given two images I1 and I2, which differ only by a displacement (dx,dy), the relationship of the two is expressed as follows:   (1)I2x,y=I1x-dx,y-dy.Assuming the digital image is an M×N dimensional matrix, where F1 and F2 are, respectively, the Fourier transform for the two images, so they are expressed as follows: (2)F1ωx,ωy=∑x,yI1x,yMNexp⁡⁡-2πjωxxM+ωyyN,F2ωx,ωy=∑x,yI2x,yMNexp⁡⁡-2πjωxxM+ωyyN.F1, F2 can be related by(3)F2ωx,ωy=e-j(ωxdx+ωydy)F1ωx,ωy.Through the formula above, two images which have the same Fourier magnitude but a phase difference which can be directly calculated by their cross power spectrum. The phase of the cross power spectrum is as follows:(4)e-j(ωxdx+ωydy)=F1ωx,ωyF2∗ωx,ωy|F1ωx,ωyF2∗ωx,ωy|,where the asterisk ∗ is the complex conjugate of F1 and F2. The inverse Fourier transform of the phase difference is a delta function centered at the displacement. By searching the peak of the inverse Fourier transform, the maximum value of the function can be obtained, which in this case is the point of the registration.


### 2.2. Phase Correlation Algorithm on the Log-Polar Coordinates

Log-polar coordinate transformation expressed the changes of image description. The Cartesian coordinates system is shown in Figure1 which represents the scene plane coordinates. Log-polar coordinates are the converted coordinates, as shown in Figure 2.Figure 1
Cartesian coordinate.Figure 2
Log-polar coordinate.If the image in thex,y directions is, respectively, multiplied by a scaling parameter, (x,y) in the Cartesian coordinates will become (ax,ay); then log transformation can be used to simplify the process: (5)(ln⁡⁡ax,ln⁡⁡ay)=((ln⁡⁡a+ln⁡⁡x),(ln⁡⁡a+ln⁡⁡y)).The scale transformation of the Cartesian coordinates system is corresponding to the translation transform of log-polar coordinates system [14, 15]. Similarly, the angle transform in Cartesian coordinates system is also corresponding to their counterparts in log-polar coordinates system, which can simplify the registration process by transforming images into log-polar coordinates system when angle exists. If the image I2 is a scaled, rotated, and translated version of I1, then I2 can be expressed as follows: (6)I2x,y=I1xacos⁡⁡θ0+yasin⁡θ0+dx,-xasin⁡θ0+yacos⁡⁡θ0+dy,where θ0 represents a rotation angle, (dx,dy) represents the amount of shift between the images, and α represents a scaling parameter between images. First we apply the Fourier transform on both of the images and get the following formula: (7)I2ωx,ωy=e-2πjωxdx+ωydy×I1ωxacos⁡⁡θ0+ωyasin⁡θ0,-ωxasin⁡θ0+ωyacos⁡⁡θ0.Then the log-polar transform can be applied to the magnitude spectrum of the Fourier transform. The rotation and scale parameter are obtained by using the phase correlation on the log-polar image:(8)M2ωx,ωy=M1(ωxacos⁡⁡θ0+ωyasin⁡θ0,-ωxasin⁡θ0+ωyacos⁡⁡θ0),wwwwwwwwwwwwwwwwwwwwwwawhereM=F.If α is not equal to 1, the registration of two images contains scaling transformation. By converting the magnitude spectra to the log-polar domain, as in (9), the scaling parameters can be easily extracted from (4): (9)M2γ,θ=M1aγ,θ-θ0.The coordinate γ can be transformed to the logarithmic coordinates:(10)M2lg⁡γ,θ=M1lg⁡a+lg⁡γ,θ-θ0.Assuming ω=lg⁡γ, η=lg⁡α, the formula can be rewritten as follows: (11)M2ω,θ=M1ω+η,θ-θ0.Then the phase correlation method can be used to compute the scaling parameter: (12)a=eη.


## 2.1. Phase Correlation Method for the Translation Parameters

Phase correlation method is proposed by Kuglin and Hines. First, the images are transformed from the time domain to the frequency domain through the fast Fourier transform. Then the translation vectors between the two images are directly calculated through their cross power spectrum, thus determining the relations of the image location [11, 12]. Phase correlation algorithm has now been extended to image registration applications in which the two images differ from each other in rotation and scale [13]. Rotation and scaling transformation on the Cartesian coordinates can be converted to translation transform on the log-polar coordinates, so the image rotation and scaling parameters can be extracted according to phase correlation algorithm. This paper discusses the case under the condition of relatively large scaling factor and the rotation angle. Principle of phase correlation technique: given two images I1 and I2, which differ only by a displacement (dx,dy), the relationship of the two is expressed as follows:   (1)I2x,y=I1x-dx,y-dy.Assuming the digital image is an M×N dimensional matrix, where F1 and F2 are, respectively, the Fourier transform for the two images, so they are expressed as follows: (2)F1ωx,ωy=∑x,yI1x,yMNexp⁡⁡-2πjωxxM+ωyyN,F2ωx,ωy=∑x,yI2x,yMNexp⁡⁡-2πjωxxM+ωyyN.F1, F2 can be related by(3)F2ωx,ωy=e-j(ωxdx+ωydy)F1ωx,ωy.Through the formula above, two images which have the same Fourier magnitude but a phase difference which can be directly calculated by their cross power spectrum. The phase of the cross power spectrum is as follows:(4)e-j(ωxdx+ωydy)=F1ωx,ωyF2∗ωx,ωy|F1ωx,ωyF2∗ωx,ωy|,where the asterisk ∗ is the complex conjugate of F1 and F2. The inverse Fourier transform of the phase difference is a delta function centered at the displacement. By searching the peak of the inverse Fourier transform, the maximum value of the function can be obtained, which in this case is the point of the registration.


## 2.2. Phase Correlation Algorithm on the Log-Polar Coordinates

Log-polar coordinate transformation expressed the changes of image description. The Cartesian coordinates system is shown in Figure1 which represents the scene plane coordinates. Log-polar coordinates are the converted coordinates, as shown in Figure 2.Figure 1
Cartesian coordinate.Figure 2
Log-polar coordinate.If the image in thex,y directions is, respectively, multiplied by a scaling parameter, (x,y) in the Cartesian coordinates will become (ax,ay); then log transformation can be used to simplify the process: (5)(ln⁡⁡ax,ln⁡⁡ay)=((ln⁡⁡a+ln⁡⁡x),(ln⁡⁡a+ln⁡⁡y)).The scale transformation of the Cartesian coordinates system is corresponding to the translation transform of log-polar coordinates system [14, 15]. Similarly, the angle transform in Cartesian coordinates system is also corresponding to their counterparts in log-polar coordinates system, which can simplify the registration process by transforming images into log-polar coordinates system when angle exists. If the image I2 is a scaled, rotated, and translated version of I1, then I2 can be expressed as follows: (6)I2x,y=I1xacos⁡⁡θ0+yasin⁡θ0+dx,-xasin⁡θ0+yacos⁡⁡θ0+dy,where θ0 represents a rotation angle, (dx,dy) represents the amount of shift between the images, and α represents a scaling parameter between images. First we apply the Fourier transform on both of the images and get the following formula: (7)I2ωx,ωy=e-2πjωxdx+ωydy×I1ωxacos⁡⁡θ0+ωyasin⁡θ0,-ωxasin⁡θ0+ωyacos⁡⁡θ0.Then the log-polar transform can be applied to the magnitude spectrum of the Fourier transform. The rotation and scale parameter are obtained by using the phase correlation on the log-polar image:(8)M2ωx,ωy=M1(ωxacos⁡⁡θ0+ωyasin⁡θ0,-ωxasin⁡θ0+ωyacos⁡⁡θ0),wwwwwwwwwwwwwwwwwwwwwwawhereM=F.If α is not equal to 1, the registration of two images contains scaling transformation. By converting the magnitude spectra to the log-polar domain, as in (9), the scaling parameters can be easily extracted from (4): (9)M2γ,θ=M1aγ,θ-θ0.The coordinate γ can be transformed to the logarithmic coordinates:(10)M2lg⁡γ,θ=M1lg⁡a+lg⁡γ,θ-θ0.Assuming ω=lg⁡γ, η=lg⁡α, the formula can be rewritten as follows: (11)M2ω,θ=M1ω+η,θ-θ0.Then the phase correlation method can be used to compute the scaling parameter: (12)a=eη.


## 3. Phase Correlation Algorithm Based on SURF Feature Points

When the scaling ratio and rotation angle of the image to be registered are too large compared to the original image, it is difficult for the conventional phase correlation method  to compute the registration parameters accurately. If the local area with the same information in two images is extracted and the registration parameters are obtained using Fourier-Mellin algorithm, precision will be significantly improved. SURF is a method which has the advantages of high speed, stable scale invariant, and invariant rotation features and which is a fast and robust method of selecting feature points [16, 17]. In this paper, the local area with the same information in two images is extracted by using the SURF feature algorithm. Then by the Fourier-Mellin algorithm with two-step iterative from coarse to fine, the registration parameters can be obtained accurately. The specific steps are as follows.(1)
Construct the scale space of the reference image and the image to be registered and extract the feature points with scale invariant feature in the scale space using the Hessian matrixt.(2)
Confirm the main direction of the characteristic points and rotate the coordinate axis according to the main direction.(3)
Generate the 64-feature vector by describing the feature of feature points after synthesizing the spatial distribution information and determine the corresponding points of the reference image and the image to be registered.(4)
Take one pair of the same point near the image center point and intercept a small area of the same size which is about half of an image.(5)
Compute the intercepted image scaling factor and rotation angle roughly using the log-polar coordinate.(6)
Preliminary compensate the interception of images to be registered for rotation and scaling and compute the fine scaling factor and the rotation angle by the Fourier-Mellin algorithm again.(7)
Fuse the scaling factor and the rotation angle obtained from two-step iterative and compute and extract the center area of the two images according to the difference of images between the size, scaling factor, and rotation angle.(8)
Compute the translation parameters of the two images using the extracted image of the center region.(9)
Compensate the image to be registered by scaling, rotating, and translating and output the registration image.


## 4. Experimental Results and Analysis

As shown in Figure3, two pieces of 512∗512 images are selected to validate the image registration algorithm proposed in this paper. The reference image is shown in Figure 3(a). After scaling 1.53 times, rotating 40.67 degrees and translating (20, 30) pixels, the image to be registered is obtained (Figure 3(b)). Figure 3(c) is the same point detected between the reference image and the image to be registered using the SURF algorithm. Figures 3(d) and 3(e) are the local areas intercepted from Figures 3(a) and 3(b) according to Figure 3(c). Figures 3(f) and 3(g) are the images transformed from Figures 3(d) and 3(e) according to the log polar. Figure 3(h), which has a clear peak, is the three-dimensional display obtained by the cross power spectrum after inversing Fourier transform. Figure 3(i) is the registered image.Figure 3
Using the proposed algorithm to calculate the translation, rotation, and scaling parameters.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)As can be seen from Table1, the estimation error of the translation parameters is within 1 pixel through the proposed algorithm. The estimation error of rotation angle is less than 0.5 degree, and the error estimates of scaling factor are less than 0.005.  Compared with the conventional phase correlation algorithm, this algorithm improves the accuracy of registration without loss of speed.Table 1
Comparison of this algorithm and the traditional phase correlation algorithm.
The known parameters
Calculated parametersby this algorithm
Calculated parametersby phase correlation algorithm
The zoom
1.53
1.5314
1.4978
Rotation angle
40.67
40.67
40.4082
Translation vector
(20, 30)
(19, 30)
(25, 35)
Registration time
2.290529 s
3.0086 sIt can be seen from Table2, the two-step iterative algorithm proposed in this paper consumes some computation time, but the accuracy of registration will be more satisfactory.Table 2
The performance comparison results of before iteration and after iteration.
The known parameters
Before iteration
After iteration
The zoom
1.53
1.5693
1.5314
Rotation angle
40.67
40.78
40.67
Translation vector
(20, 30)
(19, 29)
(19, 30)
Registration time
2.06864 s
2.290529 sLiterature [9] presents an image registration method based on mutual information and Fourier-Mellin, which integrate the accuracy of calculating linear parameters in Fourier-Mellin-based method and the accuracy of calculating rotation and scale parameters in mutual information based method. Using this method can obtain precise registration parameters but takes a long time. Figure 4 verifies the algorithm proposed in this paper compared with literature [9]. The reference image is shown in Figure 4(a). After scaling 0.4 times, rotating 10 degrees, and translating (10, 18) pixels, the image to be registered is obtained shown in Figure 4(b). Figure 4(c) is the same point which is using the SURF algorithm. Figure 4(d) is the registered image. The registration results are shown in Table 3.Table 3
Comparison of this algorithm and the mutual information algorithm.
The known parameters
Calculated parametersby this algorithm
Calculated parametersby mutual information algorithm
The zoom
0.4
0.4020
0.4005
Rotation angle
10
10.000
9.9908
Translation vector
(10, 18)
(10, 18)
(10, 18)
Registration time
1.78 s
90.7843 sFigure 4
Remote sensing image registration results.
(a)
(b)
(c)
(d)As can be seen from Table3, the algorithm based on Fourier-Mellin and mutual information is at slow speed and needs a large amount of calculation. It is difficult to find the perfect balance between registration accuracy and calculation speed, while the algorithm proposed in this paper can greatly improve the registration rate without loss of accuracy.In order to verify the universality of this algorithm, these images are registered with different brightness and clarity, respectively. The registration in images with different clarity is shown in Figure5. The reference image is a fuzzy image shown in Figure 5(a). After scaling 1.2 times, rotating 15 degrees, and translating (5, 15) pixels, the image to be registered is obtained which is shown in Figure 5(b). Figure 5(c) is the same point which is using the SURF algorithm. Figure 5(d) is the registered image. The registration results are shown in Table 4. The experimental results fully demonstrate the superiority of this method.Table 4
Comparison of this algorithm and the known parameters.
The known parameters
Calculated parameters
The zoom
1.2
1.2015
Rotation angle
15
14.7656
Translation vector
(5, 15)
(5, 16)
Registration time
2.98 sFigure 5
The images with different clarity to be registered.
(a)
(b)
(c)
(d)Then we register the images with different brightness. Figure6(a) is the reference image with dark brightness. After scaling 1.2 times, rotating 15 degrees, and translating (5, 15) pixels, the image to be registered is obtained which is shown in Figure 6(b). Figure 6(c) is the same point which is using the SURF algorithm. Figure 6(d) is the registered image. The registration results are shown in Table 5.Table 5
Comparison of this algorithm and the known parameters.
The known parameters
Calculated parameters
The zoom
1.2
1.2045
Rotation angle
10
10
Translation vector
(10, 10)
(9, 10)
Registration time
3.47 sFigure 6
The images with different brightness to be registered.
(a)
(b)
(c)
(d)


## 5. Conclusion

Phase correlation method is a subpixel image registration technique which is widely used. The large scaling factor and rotation angle influence the precision of translation parameters using the traditional phase correlation method. The two-step iterative method proposed in this paper, combining the SURF feature points extraction and phase correlation method, avoids the huge computation using the fast algorithm based on frequency domain. This paper, respectively, validates different types of visible light images with Matlab simulation. The results show that this algorithm ensures the registration precision, reduces the registration time, makes up for the defects of the traditional phase correlation method, and meets the requirement of high precision and fast image registration system.



---

*Source: 215960-2015-05-04.xml*