图像的傅里叶变换

先做几点声明

图像数据是实值的，因此图像矩阵是实矩阵
本文将从矩阵的观点重新认识二维离散傅里叶变换

变换公式

假设图像的大小为 $ M*N $ ，则正变换为： \[ F(u,v) = \sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)e^{-j2\pi(ux/M+vy/N)} \] 逆变换为： \[ f(x,y) = \frac{1}{MN}\sum_{u=0}^{M-1}\sum_{v=0}^{N-1}F(u,v)e^{j2\pi(ux/M+vy/N)} \] 从上面我们可以发现两个很有意思的地方：（后面自会揭晓）

$ 1/MN $
$ e^{-j2(ux/M+vy/N)} $ 和 $ e^{j2(ux/M+vy/N)} $

正变换

傅里叶变换核是可分离的，故正变换可以改写为： \[ F(u,v) = \sum_{x=0}^{M-1}\bigg(\sum_{y=0}^{N-1}f(x,y)e^{-j2\pi vy/N}\bigg)e^{-j2\pi ux/M} \] 用矩阵来表示，就是： \[ F(u,v) = \left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{-j2\pi \frac{1}{M}} & \cdots & e^{-j2\pi \frac{M-1}{M}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{-j2\pi \frac{M-1}{M}} & \cdots & e^{-j2\pi \frac{(M-1)^2}{M}}\\ \end{matrix} \right)_{M\times M} f(x,y)_{M\times N} \left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{-j2\pi \frac{1}{N}} & \cdots & e^{-j2\pi \frac{N-1}{N}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{-j2\pi \frac{N-1}{N}} & \cdots & e^{-j2\pi \frac{(N-1)^2}{N}}\\ \end{matrix} \right)_{N\times N} \] 上述矩阵有以下特点：

对称的
行(列)向量是正交的
行(列)向量不是规范正交的
欲令行(列)向量规范化，可在矩阵前乘以如下因子：

\[ \frac{1}{\sqrt{M}}\,\,和\,\,\frac{1}{\sqrt{N}} \]

当上述矩阵变为规范正交矩阵时，满足： \[ MM^{*T}=M^{*T}M=E\,\,和\,\,NN^{*T}=N^{*T}N=E \\ M^{-1}=M^{*T}\,\, 和 \,\,N^{-1}=N^{*T} \] M 矩阵和 N 矩阵在 M 和 N 的值确定后即可确定

在 MATLAB 中编写一小段代码来实现正变换：

function res = myfft2(matrix)
[M, N] = size(matrix);
matM = zeros(M);
matN = zeros(N);
for i = 1:M
    for j = 1:M
        matM(i,j) = exp(-1i*2*pi*(i-1)*(j-1)/M);
    end
end
for i = 1:N
    for j = 1:N
        matN(i,j) = exp(-1i*2*pi*(i-1)*(j-1)/N);
    end
end
res = matM * matrix * matN;
end

再写一段用于和 MATLAB 自带函数 fft2 作比较的测试代码：

1
2
3

A = [1,3,4,9;2,0,8,7;1,1,10,6]
B = fft2(A)
C = myfft2(A)

运行后，发现 B 和 C 的结果相同

逆变换

思路同正变换一样，但有 2 处不同（就是上面提到的很有意思的地方）

一是系数（矩阵求逆产生的）
二是变换核（注意共轭关系）

体现在公式中，就是： \[ \frac{1}{\sqrt{MN}}F(u,v) = \frac{1}{\sqrt{M}}\left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{-j2\pi \frac{1}{M}} & \cdots & e^{-j2\pi \frac{M-1}{M}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{-j2\pi \frac{M-1}{M}} & \cdots & e^{-j2\pi \frac{(M-1)^2}{M}}\\ \end{matrix} \right) f(x,y) \frac{1}{\sqrt{N}}\left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{-j2\pi \frac{1}{N}} & \cdots & e^{-j2\pi \frac{N-1}{N}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{-j2\pi \frac{N-1}{N}} & \cdots & e^{-j2\pi \frac{(N-1)^2}{N}}\\ \end{matrix} \right) \]

\[ \frac{1}{MN}\left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{j2\pi \frac{1}{M}} & \cdots & e^{j2\pi \frac{M-1}{M}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{j2\pi \frac{M-1}{M}} & \cdots & e^{j2\pi \frac{(M-1)^2}{M}}\\ \end{matrix} \right)F(u,v)\left( \begin{matrix} 1 & 1 & \cdots & 1\\ 1 & e^{j2\pi \frac{1}{M}} & \cdots & e^{j2\pi \frac{M-1}{M}}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & e^{j2\pi \frac{M-1}{M}} & \cdots & e^{j2\pi \frac{(M-1)^2}{M}}\\ \end{matrix} \right) = f(x,y) \]

同样可以编写代码：

function res = myifft2(matrix)
[M, N] = size(matrix);
matM = zeros(M);
matN = zeros(N);
for i = 1:M
    for j = 1:M
        matM(i,j) = exp(1i*2*pi*(i-1)*(j-1)/M);
    end
end
for i = 1:N
    for j = 1:N
        matN(i,j) = exp(1i*2*pi*(i-1)*(j-1)/N);
    end
end
res = real(matM * matrix * matN / (M * N));
end

做测试：

A = [1,3,4,9;2,0,8,7;1,1,10,6]
B = fft2(A)
% C = myfft2(A)
D = ifft2(B)
E = myifft2(B)

发现结果一致