date: 2016-03-09
categories: Image processing
tag: [Fourier transform]
mathjax: true
博客

title: 从图像处理的角度看傅里叶变换

前言

傅里叶变换（Fourier transform）是一种线性的积分变换，常在将信号在时域（或空域）和频域之间变换时使用，在物理学和工程学中有许多应用。因其基本思想首先由法国学者约瑟夫·傅里叶系统地提出，所以以其名字来命名以示纪念[1]。

傅里叶变换是图像处理中非常重要的工具！但是由于很多教材对傅里叶变换讲的要不就不够透彻，要不就复杂化，导致我之前对傅里叶都心存“恐惧”。直到看到[2]的文章，才发现原来傅里叶变换也就这么回事。

频率（Frequency）

不用于时间域和空间域，很多人觉得频率域不能够直观感受。实则不然，频率在我们生活中扮演着相当重要的角色，比如：音乐。我们常说“高音”“低音”，这里的高和低指的不是音量，而是频率。而频率实际上是不同的正弦曲线（sinusoids）组合而成。正弦曲线的一般式为：

$$x(t) = a \sin(\omega t + \phi) = a \sin(2\pi f t + \phi)$$

可以由单个正弦曲线表示的音调称为纯音。这里 $\omega = 2 \pi f$，$\omega$的单位是rad/sec，$f$的单位是Hz；a是峰值，也就是我们常说的音量。而由于是纯音，所以$\phi$不改变任何音调。

实际上所有音调均能由一个或一个以上的正选函数组成，比如：

$$x(t) = \sin(2\pi t) + \sin(4\pi t)$$

以上$x(t)$就是由1Hz和2Hz的正选曲线组合而成。当然如果要组合成人能够听到的声音，还必须提高其频率：

$$d(t) = \sin(2\pi \ast 350 \ast t) + \sin(2\pi \ast 400 \ast t)$$

人耳能听到的频率范围在20Hz--20kHz之间

如果我们使用图像来表示这个组合过程的话：

图1. 两个不同的正弦函数组合成一个新的正弦曲线

傅里叶变换

如果将时域信号分为连续/离散时间，周期性（有限持续时间）/非周期性（无限持续时间）的，那么我可以将傅里叶变换分为以上四种类型。每种类型的定义如下：

上图中值得说明的是：
- $x(t)$表示连续的时域信号，而$x[n]$则表示离散的时域信号，对应的，傅里叶变换后的频率信号分别用$X(\omega)$和$X[k]$表示；
- 离散信号的频率实际上均是$\omega_0$的倍数，$\omega_0 = \frac{2\pi}{N}$称为基频率（fundamental frequency）。

变换与反变换

时间长观察上图不难发现。每种类型的傅里叶变换都含有两个方程，其中第一个称为傅里叶变换，而第二个则称为傅里叶反变换。也就是我们能够时域信号变换到频域，也能将其频域信号反变换到时域。我们可以表示为：

$$X[\omega] = \mathcal{F}[x(t)]$$

$$x(t) = \mathcal{F}^{-1}[{X(\omega)}]$$

其实际上变换与反变换都只是积分/累加和的求导过程，以FT（时域连续无穷信号变换）举例，其变换与反变换如下：

$$X(\omega) = \int_{-\infty}^{\infty} x(t)e^{-j \omega t}dt$$

$$x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(\omega)e^{j \omega t}dt$$

而DFT（时域离散有限持续时间）的变换与反变换则如下：

$$X[k] = \sum_{n=0}^{N-1} x[n]e^{-jk\omega_0 n}, k = 0, 1,...,N-1$$

$$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k]e^{jk\omega_0 n}, k = 0, 1,...,N-1$$

其中：$\omega_0 = \frac{2\pi}{N}$

对偶性（Duality）

傅里叶变换一个非常重要的性质就是对偶性。我们先来观察其连续/离散，有限域/无限域性质。实际上若信号在一个域（时间/频率）上是有限域的，那么其信号在另一个域（频率/时间）则是离散的。同样的，若信号在一个域（时间/频率）上是无限域的，那么其信号在另一个域（频率/时间）则是连续的。结合之前的分类图如下所示：

傅里叶变换对

如果$X(\omega)$是$x(t)$的傅里叶变换后频域信号，那么我们称其$X(\omega)$和$x(t)$傅里叶变换对，且用以下方式表示：

$$x(t) \leftrightarrow X(\omega)$$

由傅里叶变换的对偶性我们可以知道，傅里叶变换对互换域后仍然成立。举个例子，矩形函数与sinc函数互为傅里叶变换对，那么时域矩形函数能够变换成频域sinc函数，频域矩形函数能反变换成时域sinc函数。

$$X(\omega) = \mathcal{F}[ x(t)] = \int_{-\infty}^\infty x(t)e^{-j\omega t}dt$$

$$= \int_{-\frac{1}{2}}^{\frac{1}{2}} e^{-j\omega t}dt$$

$$= \frac{e^{-j\omega t}}{-j\omega}|_{t=-\frac{1}{2}}^{\frac{1}{2}}$$

$$= \frac{e^{j\frac{\omega}{2}} - e^{-j\frac{\omega}{2}}}{j\omega}$$

$$= \frac{2\sin(\frac{\omega}{2})}{\omega}$$

$$= sinc(\frac{\omega}{2\pi})$$

矩形函数与sinc函数的图像如下：

同样的，我们能够根据傅里叶变换与反变换的定义，或者结合待会将要介绍的变换特性得到许许多多的傅里叶变换对，其中有些变化对十分重要，是使用傅里叶变换时常用的变换对，如：

$$\mathcal{F}[\delta(t)] = \int_{-\infty}^\infty \delta(t)e^{-j\omega t} = 1$$

更多常用的傅里叶变换对如下：

变换特性

如果傅里叶变换仅如上述所描述的，那么无疑是麻烦且不使用的。而这里要介绍的变换特性，则提供了我们能够更容易使用傅里叶变换的方法。

傅里叶变换特性表（部分）如下：

部分证明如下：

• 线性（Linearity）

$$\mathcal{F}[ax(t) + by(t)]= \int_{-\infty}^\infty[ax(t) + by(t)]e^{-j\omega t}dt$$

$$= a\int\_{-\infty}^\infty x(t)e^{-j\omega t}dt + b\int\_{-\infty}^\infty y(t)e^{-j\omega t}dt$$

$$= a\mathcal{F}[x(t)] + b\mathcal{F}[y(t)]$$

• 频移性（Frequency shift property）

$$\mathcal{F}[e^{j\omega\_0 t} x(t)] = \int\_{-\infty}^\infty [e^{j\omega_0 t}x(t)]e^{-j\omega t}dt$$

$$= \int_{-\infty}^\infty x(t)e^{-j(\omega - \omega_0) t}dt$$

$$= X(\omega - \omega_0)$$

• 时移性（Time shift property）

$$\mathcal{F} [ x(t - t\_0) ] = \int\_{-\infty}^\infty x(t - t_0)e^{-j\omega t}dt$$

$$= \int_{-\infty}^\infty x(u)e^{-j\omega (u+t_0)}du,u = t - t_0$$

$$=\int_{-\infty}^\infty x(u)e^{-j\omega u}e^{-j\omega t_0}du$$

$$=e^{-j\omega t\_0} \int\_{-\infty}^\infty x(u)e^{-j\omega u}du$$

$$= e^{-j\omega t_0}X(\omega)$$

• 卷积性（Convolution property）

$$\mathcal{F} [ x(t) \ast h(t)] = \mathcal{F}[ \int_{-\infty}^\infty x(\tau)h(t - \tau)d\tau]$$

$$= \int\_{-\infty}^\infty \left( \int\_{-\infty}^\infty x(\tau)h(t - \tau)d\tau \right) e^{-j\omega t}dt$$

$$= \int\_{-\infty}^\infty x(\tau) \left( \int\_{-\infty}^\infty h(t - \tau) e^{-j\omega t}dt \right) d\tau$$

$$= \int\_{-\infty}^\infty x(\tau) \left( \int\_{-\infty}^\infty h(u) e^{-j\omega (u+\tau)}du \right) d\tau$$

$$= \int\_{-\infty}^\infty x(\tau) \left( \int\_{-\infty}^\infty h(u) e^{-j\omega u} e^{-j\omega \tau}du \right) d\tau$$

$$= \int\_{-\infty}^\infty x(\tau) e^{-j\omega \tau} \left( \int\_{-\infty}^\infty h(u) e^{-j\omega u} du \right) d\tau$$

$$= \left(\int\_{-\infty}^\infty x(\tau) e^{-j\omega \tau} d\tau \right)\left( \int\_{-\infty}^\infty h(u) e^{-j\omega u} du \right)$$

$$= X(\omega)H(\omega)$$

同时根据傅里叶的对偶性，我们也能将时域卷积特性扩展到频域卷积特性：

$$x(t)y(t) = \frac{1}{2\pi} X(\omega) \ast Y(\omega) = \frac{1}{2\pi} \int_{-\infty}^\infty X(\eta) Y(\omega - \eta)d\eta$$

傅里叶变换特性中最重要也是最常用的性质！

二维傅里叶变换

之前我们一直讲的是一维的傅里叶变换，而想要将傅里叶变换应用到图像处理方面，则需要使用到二维傅里叶变换：

$$x(u,v) = \sin(\omega_1 u)\sin(\omega_2 v)$$

$x(u,v)$是图像上点$(u,v)$的值。

又因为$e^{j\omega_1 u}e^{j\omega_2 v} = e^{j(\omega_1 u+ \omega_2 v)}$，所以二维的傅里叶变换和反变换可以写成：

$$X(\omega_1, \omega\_2) = \int\_{-\infty}^\infty \int\_{-\infty}^\infty x(u,v)e^{-j(\omega_1 u+ \omega_2 v)}dudv$$

$$x(u,v) = \frac{1}{4\pi^2} \int\_{-\infty}^\infty \int\_{-\infty}^\infty X(\omega_1,\omega_2)e^{j(\omega_1 u+ \omega_2 v)}d\omega_1d\omega_2$$

如果用图像来表示二维傅里叶变换，其效果如下：

如果对图像进行二维傅里叶变换，其效果如下：

应用

傅里叶频率变换一个很重要的应用就是可以保留图像最为重要的信息（低频）而忽略细节（高频）。比如说我们在网页上浏览图片时，如果网页需要等到图像完全加载后才显示的话，无疑是很不友好的。另外，有时我们需要在网页的大量图片中寻找钟意的图像，此时如果把所有包括我们不太需要的图像都加载出来的话，无疑是耗时且没有意义的。

此时我们就需要对图像进行傅里叶变换变保留最重要的信息从而显示到屏幕上。只有当用户对该图像感兴趣并打开时，具有更加丰富细节的图像才会被下载并显示到屏幕上。

图2. 傅里叶变换后图像效果显示。同样数据量的图像（左边25%，右边6.25%），进行傅里叶变换后的图像能够显示出图像较完整的信息，而没有经过傅里叶变换的图像仅能显示一部分原图像。

参考与其他

[1]: 傅里叶变换-维基
[2]: Frequency Domain and Fourier Transforms by Prof. Kulkarni from Princeton University