基于DSP实现的移动场景的相位配准(5)
上图是两幅图像的互功率谱相位的反变换结果的3D图，很好的显示了相关峰和非相关峰，原点处的峰为非相关峰；在非原点处的峰为相关峰，是我们要找的配准点。一般情况下，两个峰的峰值的大小难以确定，所以一般我们将原点处的非相关峰赋0再进行下面的处理。
因此，这种方法可以归结为：进行图像配准就是求解互功率谱相位的傅里叶反变换的峰值所在的位置。需要指出的是，实际计算机处理的图像是有界并且离散的，必须符合采样定理，否则会发生混叠。在涉及亚像素级的平移时，往往要假定图像的采样率满足奈奎斯特定则。
4 快速傅里叶变换算法(FFT)
序列x(n), n = 0...N −1的离散傅立叶变换 (Discrete Fourier Transform, DFT) X(k), k = 0...N −1可定义为:
X(k)= = ， k=0,……,N-1；
其中 是旋转因子。
反离散傅立叶(Inverse DFT, IDFT)可定义为:
， n=0，……，N-1；
它们的输入输出序列都是复数。如果我们定义一个基本的运算单位为两个复数相乘再相加，则直接根据以上公式进行DFT计算需要 次基本运算。当N比较大时， 会变得非常大。这使得直接的DFT计算方法对很多应用来说都不现实。
4.1 基2 FFT
然而，如果N是2的整数次方，一种快速傅立叶变换（Fast Fourier Transform, FFT）算法可显著的减少运算量。基2 FFT算法利用了旋转因子的以下周期性特性:
利用这些特性，可以把N点DFT分解为以下两个N/2点DFT:
让我们把输出序列X(k),k= 0,…,N-1 分解成连个序列：
偶数序列: X(2r), r= 0,…,N/2-1：
奇数序列: X(2r+1)，r= 0,…,N/2-1：
按以上方法反复的分解N点DFT成 2/N点DFT直到N=2，使得 N点傅立叶变换的运算复杂度由原来的 降到 ，这是非常显著的改进。这个算法也被称为频域抽取(Decimate-In-Frequency, DIF)FFT算法。下图演示了 N=8点FFT的分解运算过程。上面的两个箭头（每个箭头上都有一个数字“1”）表示两个数相加，下面的两个箭头（一个箭头上数字“1”，一个箭头上数字“-1”）表示两个数相减。后面的 表示加减的结果再与旋转因子 相乘。
从图中可以看出，输出数据的顺序被打乱了。这种乱序其实是有规律的，我们把顺序的序号用二进制数列在下表中的左边，把乱序的序号用二进制数列在下表中的右边。从表中我们可以看出，乱序序号的二进制码可由顺序序号的二进制码反转得到，所以，这种规律被叫做比特反转。
正常序列 正常序列二进制 位比特反转二进制 位比特反转
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
4.2 基4 FFT
如果FFT点数N是4的整数次方，采用基4FFT算法可以进一步减少运算量。基4 FFT算法算法利用了旋转因子的以下周期性特性：
利用这些特性，可以把N点DFT分解为以下 4个N/4点DFT：
让我们把输出序列X(k), k= 0,…, N-1 分解成四个序列, X(4r), X(4r+1), X(4r+2), X(4r+3), r= 0,…,N/4-1；