\[ \begin{aligned} e^{j\theta} &= \cos\theta + j\sin\theta \\ e^{-j\theta} &= \cos(-\theta) + j\sin(-\theta)\\ &= \cos\theta - j\sin\theta \\ e^{j\pi} &= \cos\pi + j\sin\pi = -1 \\ e^{j\pi x} &= \cos\pi x + j\sin\pi x = (-1)^x \\ \end{aligned} \]
一维连续傅里叶变换公式及其反变换公式：
\[ \begin{aligned} \mathfrak{J}\{f(t)\} = \int_{-\infty}^{\infty} f(t) e^{-j2\pi ut} dt &= F(u) \\ \mathfrak{J}^{-1}\{F(u)\} = \int_{-\infty}^{\infty} F(u) e^{j2\pi ut} du &= f(t) \end{aligned} \]
二维连续傅里叶变换公式及其反变换公式：
\[ \begin{aligned} F(u,v) &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(x,y) e^{-j2\pi(ux+vy)} dx dy \\ f(x,y) &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} F(u,v) e^{j2\pi(ux+vy)} du dv \end{aligned} \]
一维离散傅里叶变换公式及其反变换公式：
\[ \begin{aligned} F(u) &= \frac{1}{N}\sum_{x=0}^{N-1} f(x) e^{-j2\pi ux/N} \\ f(x) &= \sum_{u=0}^{N-1} F(u) e^{j2\pi ux/N} \end{aligned} \]
可以看出\(x\)和\(u\)的取值范围都是\(0,1,2,\cdots,N-1\)，\(x\)是空间域的坐标，\(u\)是频率域的坐标。离散傅里叶变换可以看作是连续空间上的\(N\)个采样点，采样点之间是等间隔的，所以要乘一个平均系数\(\frac{1}{N}\)。二维离散傅里叶变换公式及其反变换公式：
\[ \begin{aligned} F(u,v) &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{-j2\pi(ux/M+vy/N)} \\ f(x,y) &= \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u,v) e^{j2\pi(ux/M+vy/N)} \end{aligned} \]
易得：
\[ F(0,0) = \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) = \bar{f} \]
令\(\Re(u,v)\)表示实部，\(\Im(u,v)\)表示虚部，那么有:
\[ \begin{aligned} F(u,v) &= |F(u,v)|e^{j\phi(u,v)} &\text{极坐标形式} \\ |F(u,v)| &= \sqrt{\Re^2(u,v)+\Im^2(u,v)} &\text{幅度谱或频率谱} \\ \phi(u,v) &= \arctan\frac{\Im(u,v)}{\Re(u,v)} &\text{相角或相位谱} \\ P(u,v) &= |F(u,v)|^2 = \Re^2(u,v)+\Im^2(u,v) &\text{功率谱} \end{aligned} \]
平移是针对离散傅里叶变换而言的，对连续时域的讨论见时移。
\[ \begin{aligned} F(u-u_0,v-v_0) &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{-j2\pi((u-u_0)x/M+(v-v_0)y/N)} \\ &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{-j2\pi(ux/M+vy/N)} e^{j2\pi(u_0x/M+v_0y/N)} \\ &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} [f(x,y)e^{j2\pi(u_0x/M+v_0y/N)}] e^{-j2\pi(ux/M+vy/N)} \\ &\Leftrightarrow f(x,y)e^{j2\pi(u_0x/M+v_0y/N)} \\ f(x-x_0,y-y_0) &= \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u,v) e^{j2\pi(u(x-x_0)/M+v(y-y_0)/N)} \\ &= \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u,v) e^{j2\pi(ux/M+vy/N)} e^{-j2\pi(ux_0/M+vy_0/N)} \\ &= \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} [F(u,v)e^{-j2\pi(ux_0/M+vy_0/N)}] e^{j2\pi(ux/M+vy/N)} \\ &\Leftrightarrow F(u,v)e^{-j2\pi(ux_0/M+vy_0/N)} \end{aligned} \]
二维傅里叶变换在\(u\)方向和\(v\)方向都是无限周期的，即：
\[ \begin{aligned} F(u,v) &= F(u+k_1M,v+k_2N) \\ f(x,y) &= f(x+k_1M,y+k_2N) \\ \text{where } & k_1\in \mathbb{Z}, k_2\in \mathbb{Z} \end{aligned} \]
假设我们将\(F(u,v)\)平移，令\(u_0=\frac{M}{2}\)，\(v_0=\frac{N}{2}\)，那么：
\[ F(u-\frac{M}{2},v-\frac{N}{2}) \Leftrightarrow f(x,y)e^{j\pi(x+y)} \\ \]
因为\(e^{j\pi x}=(-1)^x\)，所以：
\[ F(u-\frac{M}{2},v-\frac{N}{2}) \Leftrightarrow f(x,y)(-1)^{x+y} \]
所以频率域滤波的第一步就是用\((-1)^{x+y}\)乘以空间域的图像，来进行中心变换，这样就可以将频率域的原点移动到空间域的中心，然后再进行图像的傅里叶变换。
对于二维离散傅里叶变换，\(f(x,y)\in \mathbb{R}\)，且\(x,y,u,v\in \mathbb{Z}\)，那么：
\[ \begin{aligned} F(u,v) &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{-j2\pi(ux/M+vy/N)} \\ &= \underbrace{\frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y)\cos(2\pi(ux/M+vy/N))}_{\mathbb{R}} - j\underbrace{\frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y)\sin(2\pi(ux/M+vy/N))}_{\mathbb{R}} \\ F(-u, -v) &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{-j2\pi(-ux/M-vy/N)} \\ &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{j2\pi(ux/M+vy/N)} \\ &= \frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y)\cos(2\pi(ux/M+vy/N)) + j\frac{1}{MN}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y)\sin(2\pi(ux/M+vy/N)) \\ &= F^*(u,v) \end{aligned} \]
同样
\[ |F(-u,-v)| = |F(u,v)| \\ \]
先前讨论的二维离散傅里叶变换都是在实数域上的，而奇偶性是针对连续复数域上的函数\(f(x,y)\)而言的，这里我们对一维连续傅里叶变换进行讨论，二维的情况类似。
\[ \begin{aligned} F(u) &= \int_{-\infty}^{\infty} f(x) e^{-j2\pi ux} dx \\ &= \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx - j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx \\ \end{aligned} \]
我们首先讨论\(f(x)\)是实函数或虚函数的情况：
\[ \begin{aligned} F(-u) &= \int_{-\infty}^{\infty} f(x) \cos(-2\pi ux) dx - j\int_{-\infty}^{\infty} f(x) \sin(-2\pi ux) dx \\ &= \underbrace{\int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx}_{\mathbb{\Re}} + \underbrace{j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx}_{\mathbb{\Im}} \\ &= [\int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx - j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx]^* \\ &= F^*(u) \end{aligned} \]
与对称性的讨论类似，因为空域中的像素值\(f(x,y)\)都是实数。
\[ \begin{aligned} F(-u) &= \int_{-\infty}^{\infty} f(x) \cos(-2\pi ux) dx - j\int_{-\infty}^{\infty} f(x) \sin(-2\pi ux) dx \\ &= \underbrace{\int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx}_{\mathbb{\Im}} + \underbrace{j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx}_{\mathbb{\Re}} \\ &= -[\int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx - j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx]^* \\ &= -F^*(u) \end{aligned} \]
接着讨论\(f(x)\)是偶函数或奇函数的情况：
\[ \begin{aligned} \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx &= 2\int_{0}^{\infty} f(x) \cos(2\pi ux) dx \\ \int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx &= 0 \\ F(u) &= \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx\\ F(-u) &= \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx + j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx \\ &= \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx \\ &= F(u) \end{aligned} \]
\[ \begin{aligned} \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx &= 0 \\ \int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx &= 2\int_{0}^{\infty} f(x) \sin(2\pi ux) dx \\ F(u) &= -j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx\\ F(-u) &= \int_{-\infty}^{\infty} f(x) \cos(2\pi ux) dx + j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx \\ &= j\int_{-\infty}^{\infty} f(x) \sin(2\pi ux) dx \\ &= -F(u) \end{aligned} \]
说明\(F(u)\)的奇偶性取决于\(f(x)\)的奇偶性
\[ \mathfrak{J} \{\alpha f(x,y) + \beta g(x,y)\} = \alpha \mathfrak{J}\{f(x,y)\} + \beta \mathfrak{J}\{g(x,y)\} \]
以一维连续卷积为例：
\[ (f\star h)(t) = \int_{-\infty}^{\infty} f(\tau)h(t-\tau) d\tau \\ \]
对其进行傅里叶变换：
\[ \begin{aligned} \mathfrak{J}\{(f\star h)(t)\} &= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(\tau)h(t-\tau) d\tau e^{-j2\pi ut} dt \\ &= \int_{-\infty}^{\infty}f(\tau)[\int_{-\infty}^{\infty}h(t-\tau) e^{-j2\pi ut} dt] d\tau \\ \text{令 }t-\tau = m & \text{ 则 } t = m+\tau\text{ ,} dt = dm \\ &= \int_{-\infty}^{\infty}f(\tau)[\int_{-\infty}^{\infty}h(m) e^{-j2\pi u(m+\tau)} dm] d\tau \\ &= \int_{-\infty}^{\infty}f(\tau)[\int_{-\infty}^{\infty}h(m) e^{-j2\pi um} dm] e^{-j2\pi u\tau} d\tau \\ &= \int_{-\infty}^{\infty}f(\tau)H(u) e^{-j2\pi u\tau} d\tau \\ &= H(u)\int_{-\infty}^{\infty}f(\tau) e^{-j2\pi u\tau} d\tau \\ &= H(u)F(u) \end{aligned} \]
所以空间域上的卷积在频率域上就是乘积。此外，频率域的卷积类似于空间域的乘积。
\[ \begin{aligned} (f\star h)(t) &\Leftrightarrow F(u)H(u) \\ (f\cdot h)(t) &\Leftrightarrow (F\star H)(u) \end{aligned} \]
复习一下空域上的二维卷积：
\[ (f\star h)(x,y) = \frac{1}{MN} \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} f(m,n)h(x-m,y-n) \]
空域上的离散相关与内积类似，定义为：
\[ (f\circ h)(x,y) = \frac{1}{MN}\sum_{m=0}^{M-1} \sum_{n=0}^{N-1} f^*(m,n)h(x+m,y+n) \]
\[ \begin{aligned} (f\circ h)(x,y) &\Leftrightarrow F^*(u,v)H(u,v) \\ f^*(x,y)h(x,y) &\Leftrightarrow (F\circ H)(u,v) \\ (f\circ f)(x,y) &\Leftrightarrow |F(u,v)|^2 \\ |f(x,y)|^2 &\Leftrightarrow (F\circ F)(u,v) \end{aligned} \]
\[ \begin{aligned} \mathfrak{J} \{f(at)\} &= \int_{-\infty}^{\infty} f(at) e^{-j2\pi ut} dt \\ \text{令 }at = \tau & \text{ 则 } t = \frac{\tau}{a}\text{ ,} dt = \frac{d\tau}{a} \\ &= \int_{-\infty}^{\infty} f(\tau) e^{-j2\pi \frac{u}{a} \tau} \frac{d\tau}{a} \\ &= \frac{1}{a}\int_{-\infty}^{\infty} f(\tau) e^{-j2\pi \frac{u}{a} \tau} d\tau \\ &= \frac{1}{a}F(\frac{u}{a}) \end{aligned} \]
与空域类似，时域上的平移也满足类似的性质，即：
\[ \begin{aligned} \mathfrak{J} \{f(t-t_0)\} &= \int_{-\infty}^{\infty} f(t-t_0) e^{-j2\pi ut} dt \\ \text{令 }t-t_0 = \tau & \text{ 则 } t = \tau+t_0\text{ ,} dt = d\tau \\ &= \int_{-\infty}^{\infty} f(\tau) e^{-j2\pi u(\tau+t_0)} d\tau \\ &= e^{-j2\pi ut_0}\int_{-\infty}^{\infty} f(\tau) e^{-j2\pi u\tau} d\tau \\ &= e^{-j2\pi ut_0}F(u) \end{aligned} \]
\[ \begin{aligned} \mathfrak{J} \{\delta(t)\} &= \int_{-\infty}^{\infty} \delta(t) e^{-j2\pi ut} dt \\ &= e^{-j2\pi u0} = 1 \\ \mathfrak{J} \{\delta(t-t_0)\} &= \int_{-\infty}^{\infty} \delta(t-t_0) e^{-j2\pi ut} dt \\ &= e^{-j2\pi ut_0} \\ \end{aligned} \]
频率域滤波的基本步骤如下：
更完整地，我们一般先对图像进行填充使其大小为\(P\times Q\)，其中\(P=2M\)，\(Q=2N\)，然后再乘上\((-1)^{x+y}\)；同样，反变换处理后的图像最终也要裁剪，我们保留左上角的\(M\times N\)部分。对于图像\(f_{A\times B}\)和滤波器\(h_{C\times D}\)进行填充是为了避免卷积的边界效应，将图像进行填充后的大小为\(P\times Q\)一般满足
\[ \begin{aligned} P &\geq A+C-1 \\ Q &\geq B+D-1 \end{aligned} \]