# Estimation of Large Scalings in Images Based on Multilayer Pseudopolar Fractional Fourier Transform

Authors: Zhenhong Li; Jianwei Yang; Ming Li; Rushi Lan
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Accurate estimation of the Fourier transform in log-polar coordinates is a major challenge for phase-correlation based motion estimation. To acquire better image registration accuracy, a method is proposed to estimate the log-polar coordinates coefficients using multilayer pseudopolar fractional Fourier transform (MPFFT). The MPFFT approach encompasses pseudopolar and multilayer techniques and provides a grid which is geometrically similar to the log-polar grid. At low coordinates coefficients the multilayer pseudopolar grid is dense, and at high coordinates coefficients the grid is sparse. As a result, large scalings in images can be estimated, and better image registration accuracy can be achieved. Experimental results demonstrate the effectiveness of the presented method.


---

## Body

## 1. Introduction

Motion estimation is of great importance to many image processing and computer vision applications. It plays a vital role in image mosaic, image compression, video enhancement, scene representation, and so forth. [1–6]. Numerous image registration techniques have been developed throughout the years [1, 7–9]. These methods can be loosely divided into the following groups: algorithms that use image pixel values directly, for example, correlation methods [10]; algorithms that use the frequency domain, for example, Fourier-based methods [11–14]; algorithms that use low-level features such as edges and corners, for example, feature-based methods [15]; and algorithms that use high-level features such as identified (parts of) objects or relations between features [16], for example, graph-theoretic methods [17]. Fourier-based methods, which take advantage of fast Fourier transform (FFT), are among the most popular.The theory background of Fourier-based image registration is described in [18, 19]. Based on the shift property of Fourier transform, the translation can be robust-estimated by phase correlation. In order to account for rotations and scaling, the image is transformed into a uniform polar or log-polar Fourier representation. As a result, rotations and scalings are reduced to translations, which can be estimated by phase correlation again. It has been shown that Fourier-based methods are robust to noise and time varying illumination disturbances [20, 21].In the Fourier-based method, the largest challenge is to evaluate the log-polar Fourier transform efficiently and accurately. FFT is commonly defined on the Cartesian grid. To calculate the log-polar coordinates coefficients, one might calculate the FFT coefficients on the Cartesian grid and then interpolate them to the log-polar grid (see [19] for more details). Unfortunately, such an interpolation process is not accurate enough and results in significant errors. Based on the technique of pseudopolar fractional Fourier transform (PPFFT) [11], a method is developed in [20] to estimate large translations, rotations, and scaling in images. It is demonstrated in [20] that a more accurate estimation of registration parameters can be achieved by PPFFT compared to the method given in [19]. However, the PPFFT method [20] can only recover scales up to 4. Recently, Pan et al. [21] present a novel method called multilayer fractional Fourier transform (MLFFT) for the fast and accurate polar/log-polar Fourier transforms. The advantages of MLFFT over other fast log-polar Fourier transform methods have been proven theoretically and experimentally in [21].Though PPFFT and MLFFT have tremendous improvements in the fast polar/log-polar Fourier transform, they are still unsatisfying in motion estimation because they are not suitable for the log-polar Fourier transform. PPFFT pays more attention to the reduction of angular differences between the constructed grids and the uniform log-polar grids, and the radial differences have been ignored. On the other hand, MLFFT pays more attention to the reduction of radial differences between the constructed grids and the uniform log-polar grids, and the angular differences have been ignored.To acquire better image registration accuracy, a method is proposed to estimate the log-polar coordinates coefficients using multilayer pseudopolar fractional Fourier transform (MPFFT). It encompasses PPFFT and MLFFT and provides a grid which is geometrically similar to the log-polar grid. The multilayer pseudopolar grid is dense at low coordinates coefficients and sparse at high coordinates coefficients. We compare the approximation accuracy of the log-polar Fourier transform using the PPFFT, MLFFT, and MPFFT. It is shown that accumulated distances of MPFFT are lower than those of PPFFT and MLFFT. As a result, large scalings in images can be estimated, and better image registration accuracy can be achieved. Experimental results demonstrate the effectiveness of the presented method.The rest of the paper is organized as follows. Prior techniques related to FFT-based image registration are given in Section2. In Section 3, MPFFT is described, and the accuracy of MPFFT is also analyzed. Experimental results are discussed in Section 4, and final conclusions are given in Section 5.


## 2. Basic Theory of Fourier Domain

### 2.1. Phase Correlation

Letf1 and f2 be two images that differ only by a displacement (x0,y0), that is,
(1)f2(x,y)=f1(x-x0,y-y0).
Their corresponding Fourier transforms F1 and F2 will be related by
(2)F2(ξ,η)=e-j2π(ξx0+ηy0)F1(ξ,η).
The cross-power spectrum of two images f1 and f2 with Fourier transforms F1 and F2 is defined as follows:
(3)F1(ξ,η)F2*(ξ,η)|F1(ξ,η)F2(ξ,η)|=ej2π(ξx0+ηy0),
where F2* is the complex conjugate of F2; the shift theorem guarantees that the phase of the cross-power spectrum is equivalent to the phase difference between the images. By taking inverse Fourier transform of the representation in the frequency domain, we will have a function that is an impulse; it is approximately zero everywhere except at the displacement that is needed to optimally register the two images [19].


### 2.2. Log-Polar Coordinates Translation

Letf2 be a translated, rotated, and scaled replica of f1:
(4)f2(x,y)=f1(s(xcosθ0+ysinθ0)+x0,cs(-xsinθ0+ycosθ0)+y0),
where θ0, s, and (x0,y0) are the rotation angle, scale factor, and translation parameters, respectively.The Fourier transform of (4) in polar coordinate systems is
(5)I^2(r,θ)=e-j(ωxx0+ωyy0)s-2I^1(s-1r,θ+θ0),
where ωx=rcosθ, ωy=rsinθ. Let M1 and M2 be the magnitudes of I^1 and I^2. Then, we have
(6)M2(r,θ)=s-2M1(s-1r,θ+θ0),(7)M2(logr,θ)=s-2M1(logr-logs,θ+θ0).Lettingξ=logr,d=logs, (7) can be written as
(8)M2(ξ,θ)=s-2M1(ξ-d,θ+θ0).Due to the fact that the Fourier spectrum is conjugate symmetric for real sequences, only two quadrants of the Fourier spectra of images are used to map them to the log-polar plane for estimation parameters. These parameters can be recovered by phase correlation using (8) [22].Obviously, it is hard for us to calculate the discrete Fourier magnitudes of images in the log-polar coordinates. 2D FFT is used in traditional algorithms to approximate the log-polar Fourier representation of images. This will introduce large interpolation errors.


## 2.1. Phase Correlation

Letf1 and f2 be two images that differ only by a displacement (x0,y0), that is,
(1)f2(x,y)=f1(x-x0,y-y0).
Their corresponding Fourier transforms F1 and F2 will be related by
(2)F2(ξ,η)=e-j2π(ξx0+ηy0)F1(ξ,η).
The cross-power spectrum of two images f1 and f2 with Fourier transforms F1 and F2 is defined as follows:
(3)F1(ξ,η)F2*(ξ,η)|F1(ξ,η)F2(ξ,η)|=ej2π(ξx0+ηy0),
where F2* is the complex conjugate of F2; the shift theorem guarantees that the phase of the cross-power spectrum is equivalent to the phase difference between the images. By taking inverse Fourier transform of the representation in the frequency domain, we will have a function that is an impulse; it is approximately zero everywhere except at the displacement that is needed to optimally register the two images [19].


## 2.2. Log-Polar Coordinates Translation

Letf2 be a translated, rotated, and scaled replica of f1:
(4)f2(x,y)=f1(s(xcosθ0+ysinθ0)+x0,cs(-xsinθ0+ycosθ0)+y0),
where θ0, s, and (x0,y0) are the rotation angle, scale factor, and translation parameters, respectively.The Fourier transform of (4) in polar coordinate systems is
(5)I^2(r,θ)=e-j(ωxx0+ωyy0)s-2I^1(s-1r,θ+θ0),
where ωx=rcosθ, ωy=rsinθ. Let M1 and M2 be the magnitudes of I^1 and I^2. Then, we have
(6)M2(r,θ)=s-2M1(s-1r,θ+θ0),(7)M2(logr,θ)=s-2M1(logr-logs,θ+θ0).Lettingξ=logr,d=logs, (7) can be written as
(8)M2(ξ,θ)=s-2M1(ξ-d,θ+θ0).Due to the fact that the Fourier spectrum is conjugate symmetric for real sequences, only two quadrants of the Fourier spectra of images are used to map them to the log-polar plane for estimation parameters. These parameters can be recovered by phase correlation using (8) [22].Obviously, it is hard for us to calculate the discrete Fourier magnitudes of images in the log-polar coordinates. 2D FFT is used in traditional algorithms to approximate the log-polar Fourier representation of images. This will introduce large interpolation errors.


## 3. Multilayer Pseudopolar Fractional Fourier Transform

### 3.1. Fractional Fourier Transform

The proposed algorithm is based on the fractional Fourier transform. As in [20], the centered fractional Fourier transform is employed in the proposed method. Given a vector f=f(x),-N/2≤x≤N/2, the fractional Fourier transform is defined as follows:
(9)Fα(k)=∑n=-N/2N/2f(n)e-j(2πk/(N+1))αn,(-N2≤k≤N2).Whenα=1, the fractional Fourier transform is equal to the discrete Fourier transform; thus, we get the values of the N+1 frequencies that are distributed uniformly in -π≤ω≤π in the frequency domain.When0<α<1, the fractional Fourier transform returns the values of the N+1 frequencies that are scattered uniformly in -απ≤ω≤απ in the frequency domain.In this paper, we only discuss the case ofα=1/2m-1, where m∈Z+.


### 3.2. Multilayer Pseudopolar Grid

In this paper, we estimate motions of images using MPFFT. MPFFT is defined on multilayer pseudopolar grid. The set of multilayer pseudopolar grid points (MPL) is defined as follows:(10)MPL={(-lk2m-1n,k2m-1)c∪(k2m-1,-lk2m-1n)∣-n2≤k,l≤n2},
where n,L∈Z+,l,k∈Z, and m={1,2,3,…,L} (e.g., see Figure 1(d)). If L=1, this grid is the same as the pseudopolar grid. MPL can be viewed as a composite of pseudopolar grid and multilayer grid, but it is denser than them.(a)logP; (b) PP; (c) ML2; (d) MP2. The two-layer pseudopolar is much closer to the log-polar grid.
(a)
(b)
(c)
(d)LetlogP be the set of log-polar grid points, PP the set of pseudopolar grid points, and MLL the set of L-layer Cartesian grid points:
(11)logP={cos(2πkn)·nl/n,csin(2πkn)·nl/n∣0≤k,l≤n,k,l∈Z},PP={(-2lkn,k)⋃(k,-2lkn)∣-n2≤k,l≤n2,k,l∈Z},MLL={⋃(km,lm)∣-n2≤k,l≤n2,k,l∈Z},
where n,L∈Z+,m={1,2,3,…,L}. Figure 1 shows examples of logP, PP, and MLL. We note that if L=1, this MLL grid is the same as the Cartesian grid.From Figure1, we observed that the multilayer pseudopolar grid is much closer to the log-polar grid than to the pseudopolar grid and the multilayer grid.


### 3.3. The Interpolation Error

In this section, the interpolation errors of PPFFT, MLFFT, and MPFFT will be discussed.For a certain image’s spectrum magnitudeM, the interpolation error is defined as follows [20]:
(12)ε≈∑i,j|εGrid(ri,θj)|·|∇M(ri,θj)|,
where εGrid(ri,θj) is the distance between the actual point in the frequency plane and the closest point in the grid. Because |∇M(ri,θj)| are different for different signals, we substitute |∇M(ri,θj)| with max{|∇M(ri,θj)|}. It follows from (12) that
(13)ε≤∑i,j|εGrid(ri,θj)|·max{|∇M(ri,θj)|}.
By calculating (13) with such a constant max{|∇M(ri,θj)|}, we are able to compare the max interpolation errors of different transform methods without considering the signal itself [21].In the rest of this paper, we only consider two-layer MP (MP2). Other MPs can be discussed similarly.We denoteC as the set of Cartesian grid points:
(14)C={(k,l)∣-n2≤k,l≤n2,k,l∈Z}.
Let ML12 be the set of the first layer Cartesian grid points in ML2:
(15)ML12={(k2,l2)∣-n2≤k,l≤n2,k,l∈Z}.
Let ML22 be the set of the second layer Cartesian grid points in ML2. In other words, ML22 is the complement set of ML12 in ML2. We denote MP12 as the set of first-layer pseudopolar grid points in MP2:
(16)MP12={(-lkn,k2)⋃(k2,-lkn)∣-n2≤k,l≤n2,k,l∈Z}.
Furthermore, we denote MP22 as the set of second-layer pseudopolar grid points in MP2. In other words, MP22 is the complement set of MP12 in MP2.The distance between a point onlogP and the closest point on PP can be expressed as follows [20]:
(17)εGrid_PP2(θi,rj)=(Xclosest_PP(i,j)-Xreal_logP(i,j))2+(Yclosest_PP(i,j)-Yreal_logP(i,j))2,
where (Xclosest_PP(i,j),Yclosest_PP(i,j)) in pseudopolar grid is the closest point of (Xreal_logP(i,j),Yreal_logP(i,j)) in log-polar grid. In pseudopolar grid it is derived in [20] that
(18)ΔθPP(j)≈2nn2+4j2,ΔrPP(i)=1+4(in)2,i,j=1,…,n2,
where ΔθPP is the angle between two neighboring polar radii, and the ΔrPP is the distance between two points on neighboring polar radii in pseudopolar grid. Furthermore, it is shown in [20] that
(19)εGrid_PP<εGrid_C,
where εGridPP is the distance between PP and logP,εGrid_C is the distance between C and logP.The distance between ML2 and logP can be expressed as
(20)εGrid_ML2=εGrid_ML12+εGrid_ML22.
In ML12, we note that Δi=Δj=1/2. Therefore,
(21)εGrid_ML12<εGrid_C(i,j),-n4≤i,j≤n4.
The points in ML22 coincide with the points in C. It follows that
(22)εGrid_ML2<εGrid_C.The distance between MP2 and logP can be expressed as
(23)εGrid_MP2=εGrid_MP12+εGrid_MP22.
In MP2 (see Figure 2), we notice that
(24)ΔθMP2=ΔθPP,ΔrMP22=ΔrPP,ΔrMP12=12ΔrPP,
where ΔθMP2 is the angle between two neighboring polar radii in MP2, ΔrMP22 is the distance between two points on one polar radius in MP22, and ΔrMP12 is the distance between two points on one polar radius in MP12. As a consequence,
(25)εGrid_MP2<εGrid_PP.Figure 2
Geometrical properties of the MP2.The points inMP22 coincide with the points in PP, and from (19) we reach the following conclusion:
(26)εGrid_MP22<εGrid_ML22.MP12 is denser than ML12, and if we magnified the ML12 and MP12 two times, they should be the same as the C and PP. Then, we obtain
(27)εGrid_MP12<εGrid_ML12.
From (26) and (27), we get
(28)εGrid_MP2<εGrid_ML2.It follows from (19), (22), (25), and (28) that the distance between the log-polar grid points and two-layer pseudopolar grid points is the shortest one. We calculate the average distances between the log-polar grid points and other grid points. The results which are listed in Table 1 demonstrate the foregoing discussion.Table 1
Average distances between log-polar grid and other grids.
n
C
PP
M
L
2
M
P
2
n
=
25
0.3718
0.2618
0.2172
0.1697
n
=
50
0.3791
0.2653
0.2169
0.1678
n
=
1
00
0.3800
0.2616
0.2142
0.1581


## 3.1. Fractional Fourier Transform

The proposed algorithm is based on the fractional Fourier transform. As in [20], the centered fractional Fourier transform is employed in the proposed method. Given a vector f=f(x),-N/2≤x≤N/2, the fractional Fourier transform is defined as follows:
(9)Fα(k)=∑n=-N/2N/2f(n)e-j(2πk/(N+1))αn,(-N2≤k≤N2).Whenα=1, the fractional Fourier transform is equal to the discrete Fourier transform; thus, we get the values of the N+1 frequencies that are distributed uniformly in -π≤ω≤π in the frequency domain.When0<α<1, the fractional Fourier transform returns the values of the N+1 frequencies that are scattered uniformly in -απ≤ω≤απ in the frequency domain.In this paper, we only discuss the case ofα=1/2m-1, where m∈Z+.


## 3.2. Multilayer Pseudopolar Grid

In this paper, we estimate motions of images using MPFFT. MPFFT is defined on multilayer pseudopolar grid. The set of multilayer pseudopolar grid points (MPL) is defined as follows:(10)MPL={(-lk2m-1n,k2m-1)c∪(k2m-1,-lk2m-1n)∣-n2≤k,l≤n2},
where n,L∈Z+,l,k∈Z, and m={1,2,3,…,L} (e.g., see Figure 1(d)). If L=1, this grid is the same as the pseudopolar grid. MPL can be viewed as a composite of pseudopolar grid and multilayer grid, but it is denser than them.(a)logP; (b) PP; (c) ML2; (d) MP2. The two-layer pseudopolar is much closer to the log-polar grid.
(a)
(b)
(c)
(d)LetlogP be the set of log-polar grid points, PP the set of pseudopolar grid points, and MLL the set of L-layer Cartesian grid points:
(11)logP={cos(2πkn)·nl/n,csin(2πkn)·nl/n∣0≤k,l≤n,k,l∈Z},PP={(-2lkn,k)⋃(k,-2lkn)∣-n2≤k,l≤n2,k,l∈Z},MLL={⋃(km,lm)∣-n2≤k,l≤n2,k,l∈Z},
where n,L∈Z+,m={1,2,3,…,L}. Figure 1 shows examples of logP, PP, and MLL. We note that if L=1, this MLL grid is the same as the Cartesian grid.From Figure1, we observed that the multilayer pseudopolar grid is much closer to the log-polar grid than to the pseudopolar grid and the multilayer grid.


## 3.3. The Interpolation Error

In this section, the interpolation errors of PPFFT, MLFFT, and MPFFT will be discussed.For a certain image’s spectrum magnitudeM, the interpolation error is defined as follows [20]:
(12)ε≈∑i,j|εGrid(ri,θj)|·|∇M(ri,θj)|,
where εGrid(ri,θj) is the distance between the actual point in the frequency plane and the closest point in the grid. Because |∇M(ri,θj)| are different for different signals, we substitute |∇M(ri,θj)| with max{|∇M(ri,θj)|}. It follows from (12) that
(13)ε≤∑i,j|εGrid(ri,θj)|·max{|∇M(ri,θj)|}.
By calculating (13) with such a constant max{|∇M(ri,θj)|}, we are able to compare the max interpolation errors of different transform methods without considering the signal itself [21].In the rest of this paper, we only consider two-layer MP (MP2). Other MPs can be discussed similarly.We denoteC as the set of Cartesian grid points:
(14)C={(k,l)∣-n2≤k,l≤n2,k,l∈Z}.
Let ML12 be the set of the first layer Cartesian grid points in ML2:
(15)ML12={(k2,l2)∣-n2≤k,l≤n2,k,l∈Z}.
Let ML22 be the set of the second layer Cartesian grid points in ML2. In other words, ML22 is the complement set of ML12 in ML2. We denote MP12 as the set of first-layer pseudopolar grid points in MP2:
(16)MP12={(-lkn,k2)⋃(k2,-lkn)∣-n2≤k,l≤n2,k,l∈Z}.
Furthermore, we denote MP22 as the set of second-layer pseudopolar grid points in MP2. In other words, MP22 is the complement set of MP12 in MP2.The distance between a point onlogP and the closest point on PP can be expressed as follows [20]:
(17)εGrid_PP2(θi,rj)=(Xclosest_PP(i,j)-Xreal_logP(i,j))2+(Yclosest_PP(i,j)-Yreal_logP(i,j))2,
where (Xclosest_PP(i,j),Yclosest_PP(i,j)) in pseudopolar grid is the closest point of (Xreal_logP(i,j),Yreal_logP(i,j)) in log-polar grid. In pseudopolar grid it is derived in [20] that
(18)ΔθPP(j)≈2nn2+4j2,ΔrPP(i)=1+4(in)2,i,j=1,…,n2,
where ΔθPP is the angle between two neighboring polar radii, and the ΔrPP is the distance between two points on neighboring polar radii in pseudopolar grid. Furthermore, it is shown in [20] that
(19)εGrid_PP<εGrid_C,
where εGridPP is the distance between PP and logP,εGrid_C is the distance between C and logP.The distance between ML2 and logP can be expressed as
(20)εGrid_ML2=εGrid_ML12+εGrid_ML22.
In ML12, we note that Δi=Δj=1/2. Therefore,
(21)εGrid_ML12<εGrid_C(i,j),-n4≤i,j≤n4.
The points in ML22 coincide with the points in C. It follows that
(22)εGrid_ML2<εGrid_C.The distance between MP2 and logP can be expressed as
(23)εGrid_MP2=εGrid_MP12+εGrid_MP22.
In MP2 (see Figure 2), we notice that
(24)ΔθMP2=ΔθPP,ΔrMP22=ΔrPP,ΔrMP12=12ΔrPP,
where ΔθMP2 is the angle between two neighboring polar radii in MP2, ΔrMP22 is the distance between two points on one polar radius in MP22, and ΔrMP12 is the distance between two points on one polar radius in MP12. As a consequence,
(25)εGrid_MP2<εGrid_PP.Figure 2
Geometrical properties of the MP2.The points inMP22 coincide with the points in PP, and from (19) we reach the following conclusion:
(26)εGrid_MP22<εGrid_ML22.MP12 is denser than ML12, and if we magnified the ML12 and MP12 two times, they should be the same as the C and PP. Then, we obtain
(27)εGrid_MP12<εGrid_ML12.
From (26) and (27), we get
(28)εGrid_MP2<εGrid_ML2.It follows from (19), (22), (25), and (28) that the distance between the log-polar grid points and two-layer pseudopolar grid points is the shortest one. We calculate the average distances between the log-polar grid points and other grid points. The results which are listed in Table 1 demonstrate the foregoing discussion.Table 1
Average distances between log-polar grid and other grids.
n
C
PP
M
L
2
M
P
2
n
=
25
0.3718
0.2618
0.2172
0.1697
n
=
50
0.3791
0.2653
0.2169
0.1678
n
=
1
00
0.3800
0.2616
0.2142
0.1581


## 4. Experiments and Results

The proposed registration algorithm was tested using a large set of test images which were rotated, scaled, and translated.


### 4.1. A Framework for Image Registration with MPFFT

LetI1 and I2 be the target images. The algorithm operates as follows.(i)
Input imagesI1 and I2. Apply a Blackman window function to them if it is necessary, as shown in Figure 3.(ii)
Choose the proper layer (α). In this paper, we use the two-layer pseudopolar grid.(iii)
Calculate the MPFFT magnitudes ofI1 and I2. We get MP1α and MP2α. Then apply a high-pass filter to them.(iv)
Calculate the log-polar Fourier transform magnitude spectrums ofI1 and I2 by bilinear interpolation on the multilayer pseudopolar grid.(v)
Calculate the scale factor and the rotation angle by the phase correlation technique on the log-polar Fourier transform spectrums of both images.(vi)
Apply the scale factor and the rotation angle to the reference image and use the phase correlation again to detect the translation.Registration results of images. (a) Reference images. (b) Target images. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


### 4.2. Registration for Arbitrary Rotation and Large Scaling Images

Registration experiments of the MPFFT algorithm were provided by comparing with PPFFT and MLFFT in this section. All the experiments were tested on the256×256 images which were rotated θ0 and scaled 1/a as shown in Figure 3. All the test images were preprocessed by a high-pass filter to reduce the scaling overlapping [23]. Some of the test images were preprocessed by a Blackman window to decrease the rotation aliasing [24]. We presented the numeric registration results for these images in Table 2. Two-layer pseudopolar fractional Fourier transform method was shown to be more accurate than pseudopolar fractional Fourier transform method and two-layer fractional Fourier transform method by testing the Cameraman image with the Blackman window, the Lena image, and the Westconcordortho image without the Blackman window.Table 2
Registration results of Figure3.
Image name
Scale rotation
PPFFT
MLFFT
MPFFT
Cameraman
0.1060°
1.8212236.2500°
0.1056299.5313°
0.105660.4688°
Lena
0.1390°
0.8931291.0938°
0.1373360.0000°
0.137390.0000°
Westconcordortho
0.13130°
0.8608157.5000°
0.137350.6250°
0.1373129.3750°


### 4.3. Registration for Noisy Images

All the experiments in this section were tested on the256×256 images which were rotated and scaled as shown in Figure 4. It is well known that Fourier-based methods are robust to noise. MPFFT algorithm was verified to be also robust to noise by experiments. The images of Figure 4(b) are target images with noise. The registration results of noisy images by PPFFT, MLFFT, and MPFFT are the images in Figures 4(c), 4(d), and 4(e). We present the numeric registration results for these images in Table 3.Table 3
Registration results of Figure4.
Image name
Noise (parameter)
Scale rotation
PPFFT
MLFFT
MPFFT
Cameraman
salt & pepper(0.02)
0.1060°
1.8212236.2500°
0.1056299.5313°
0.105660.4688°
Lena
Poisson
0.1390°
0.8931291.0938°
0.1373360.0000°
0.137390.0000°
Westconcordortho
Gaussian(0,0.01)
0.13130°
0.8608157.5000°
0.137350.6250°
0.1373129.3750°Registration results of noisy images. (a) Reference images. (b) Target images with noise. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


### 4.4. Registration for Real Images

The images of Figures5(a) and 5(b) were used to test the estimation of real images. In this section, MPFFT was tested on the real images which were rotated and scaled, as shown in Figure 5, similar to previous experiments. The images of Figure 5(a) are reference images, and the images of Figure 5(b) are target images. The registration results of campus images by PPFFT, MLFFT, and MPFFT are the images in Figures 5(c), 5(d), and 5(e). It was shown from the experiments that PPFFT method could not find the rotation factor and the scale factor. MLFFT method could find the scale factor but could not find the rotation factor while all the correct factors could be found by MPFFT.Registration results of campus images. (a) Reference images. (b) Target images. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


## 4.1. A Framework for Image Registration with MPFFT

LetI1 and I2 be the target images. The algorithm operates as follows.(i)
Input imagesI1 and I2. Apply a Blackman window function to them if it is necessary, as shown in Figure 3.(ii)
Choose the proper layer (α). In this paper, we use the two-layer pseudopolar grid.(iii)
Calculate the MPFFT magnitudes ofI1 and I2. We get MP1α and MP2α. Then apply a high-pass filter to them.(iv)
Calculate the log-polar Fourier transform magnitude spectrums ofI1 and I2 by bilinear interpolation on the multilayer pseudopolar grid.(v)
Calculate the scale factor and the rotation angle by the phase correlation technique on the log-polar Fourier transform spectrums of both images.(vi)
Apply the scale factor and the rotation angle to the reference image and use the phase correlation again to detect the translation.Registration results of images. (a) Reference images. (b) Target images. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


## 4.2. Registration for Arbitrary Rotation and Large Scaling Images

Registration experiments of the MPFFT algorithm were provided by comparing with PPFFT and MLFFT in this section. All the experiments were tested on the256×256 images which were rotated θ0 and scaled 1/a as shown in Figure 3. All the test images were preprocessed by a high-pass filter to reduce the scaling overlapping [23]. Some of the test images were preprocessed by a Blackman window to decrease the rotation aliasing [24]. We presented the numeric registration results for these images in Table 2. Two-layer pseudopolar fractional Fourier transform method was shown to be more accurate than pseudopolar fractional Fourier transform method and two-layer fractional Fourier transform method by testing the Cameraman image with the Blackman window, the Lena image, and the Westconcordortho image without the Blackman window.Table 2
Registration results of Figure3.
Image name
Scale rotation
PPFFT
MLFFT
MPFFT
Cameraman
0.1060°
1.8212236.2500°
0.1056299.5313°
0.105660.4688°
Lena
0.1390°
0.8931291.0938°
0.1373360.0000°
0.137390.0000°
Westconcordortho
0.13130°
0.8608157.5000°
0.137350.6250°
0.1373129.3750°


## 4.3. Registration for Noisy Images

All the experiments in this section were tested on the256×256 images which were rotated and scaled as shown in Figure 4. It is well known that Fourier-based methods are robust to noise. MPFFT algorithm was verified to be also robust to noise by experiments. The images of Figure 4(b) are target images with noise. The registration results of noisy images by PPFFT, MLFFT, and MPFFT are the images in Figures 4(c), 4(d), and 4(e). We present the numeric registration results for these images in Table 3.Table 3
Registration results of Figure4.
Image name
Noise (parameter)
Scale rotation
PPFFT
MLFFT
MPFFT
Cameraman
salt & pepper(0.02)
0.1060°
1.8212236.2500°
0.1056299.5313°
0.105660.4688°
Lena
Poisson
0.1390°
0.8931291.0938°
0.1373360.0000°
0.137390.0000°
Westconcordortho
Gaussian(0,0.01)
0.13130°
0.8608157.5000°
0.137350.6250°
0.1373129.3750°Registration results of noisy images. (a) Reference images. (b) Target images with noise. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


## 4.4. Registration for Real Images

The images of Figures5(a) and 5(b) were used to test the estimation of real images. In this section, MPFFT was tested on the real images which were rotated and scaled, as shown in Figure 5, similar to previous experiments. The images of Figure 5(a) are reference images, and the images of Figure 5(b) are target images. The registration results of campus images by PPFFT, MLFFT, and MPFFT are the images in Figures 5(c), 5(d), and 5(e). It was shown from the experiments that PPFFT method could not find the rotation factor and the scale factor. MLFFT method could find the scale factor but could not find the rotation factor while all the correct factors could be found by MPFFT.Registration results of campus images. (a) Reference images. (b) Target images. (c) Registration results by PPFFT. (d) Registration results by MLFFT. (e) Registration results by MPFFT.
(a)
(b)
(c)
(d)
(e)


## 5. Conclusions

Based on PPFFT and MLFFT, a new image registration algorithm called MPFFT was presented for recovering large translations, rotations, and scaling between images. The multilayer pseudopolar grid was utilized to approximate log-polar grid to improve the accuracy of the PPFFT and MLFFT in the proposed algorithm. There are some problems that deserve further studies. For example, although our algorithm is more accurate than PPFFT and MLFFT, the computing cost is twice (layer number) as that of the PPFFT algorithm and twice as that of the MLFFT algorithm. Further works will focus on these problems.



---

*Source: 179489-2013-05-16.xml*