我们已经 state: 图像可以被看作一个离散信号.
这里我们先简略讲解一下傅里叶变换. 着重将我们用得到的部分 (DFT)
我们可能经常会看到各种形式的傅里叶变换, 尤其是对于 f∈L1(R) 的傅里叶变换, 以及 f∈L1(Zmn) 的傅里叶变换 (即这里的图像作为一个函数 f); 但是很少看到解释: 为什么取频率函数的集合是不同的, 为什么累加 / 积分等等. 所以笔者这里先 state 一下 general 的理论.
最 general 的 def 与 properties 是:
Set Up:
-
设 G 是局部紧阿贝尔群 (Locally Compact Abelian group), together with 一个唯一的 Haar measure μ.
-
我们定义对偶群 G 为所有连续的群同态 χ:G→S1 (其中每个称为特征 (character)).
注意: G 本身亦是 LCA 群.
-
对任意的 f∈L1(G,μ) 定义 Fourier transform f^:G^→C
$f^(χ)=∫Gf(x)χ(x)dμ(x),χ∈G$
则有以下定理:
-
反演定理 (Fourier Inversion): 若 f∈L1(G) 且 f∈L1(G), 则几乎处处
$f(x)=∫Gf^(χ)χ(x)dμG(χ)其中d\mu_{\widehat G}是\widehat G$ 上的 Haar 测度 (normalized).
这个定理即: Fourier 逆变换.
-
Plancherel 定理: 如果 f∈L2(G) , 则傅里叶变换扩展为一个 L2 isometry:
$∫G∣f(x)∣2dμ(x)=∫G∣f^(χ)∣2dμG(χ)即任意的|f|{L^2(G)}=|\hat{f}|{L^2(\widehat{G})}$.
在 Rn 上就是 Parseval 恒等式. 这个定理的现实意义是时域与频域的等距同构.
G=R 时, 时最标准的傅里叶变换. 这个时候的对偶群 G 的每个元素是一个函数:
$χξ(x)=e2πiξx=cos(2πξx)+isin(2πξx)$
这个特征函数的性质:
-
对于所有的 ξ, 它的这个特征函数对于任意 x 的取值的模都是 1, 并且在有限区间上 (如 [0,1] ) 存在正交性:
$∫01χξ(x)χη(x)dx=∫01e2πi(ξ−η)xdx={1,0,ξ=η,ξ=η( 若 ξ,η∈Z).$
-
具有乘法群结构:
$χξ(x)⋅χη(x)=χξ+η(x)$
χξ(x)=χ−ξ(x)
在 Fourier 正变换里,
$f^(ξ)=∫Rf(x)e−2πiξxdx$
f^(ξ) 的这个值, 这个积分运算即: 信号函数 f 与频率模式 χξ 的内积.
更加形象地说: 是函数 f 在频率模式 χξ(x)=e2πiξx 上的投影.
对于每个频率模式 χξ, f 在其上的投影系数 f^(ξ) 都是一个 constant, 其模值表示这个频率模式在整个信号 f 中的强度, 而其值包含了这个频率模式的相位 (辐角).
而在傅里叶逆变换里,
$f(x)=∫Rf^(ξ)e2πiξxdξ$
就是把所有频率成分加权叠加回来.
就是说, 原函数是对偶群中的所有频率模式的加权积分, 每个频率模式的权重就是 f 的 Fourier 变换 f^ 中, 这个频率模式 χξ 的得分 f^(ξ).
因而, 整个傅里叶变换其实就是把一个函数 f 给分解成一族振动模式 {χξ} 关于 ξ 的加权积分.
对于 G=ZN, 即有限长度的时间 / 位置上, 对偶群 G 的元素是所有群同态:
$χk:n↦ej2πkn/N,k=0,1,…,N−1$
我们画出 χ0,χ1,χ2 的图来演示:



我们已经从群论的角度解释: 它们是 ZN 的 characters.
而
- 线性代数解释: 它们构成 CN 的一组正交基
- 信号处理解释: 它是从连续傅里叶基 ejωt 离散化 (时间采样+有限窗口) 自然得到的
几何意义:
ej2πkn/N 表示的是单位圆上, 从角度 0 开始, 沿逆时针旋转了 N2π 的 kn 倍;
对于每个 k, χk 都表示一个频率函数: 一个复正弦函数
$χk:n↦ej2πkn/N=cos(N2πkn)+jsin(N2πkn)$
在位置 n=0,⋯,N−1 的这几个采样点上, ej2πkn/N 表示的是这个频率函数在位置 n 上的值.
从欧拉公式来看:
所以它确实就是一个正弦/余弦波(复正弦波)。
对于每个 n, 取 k=1, 这个 ej2πn/N 表示了单位圆上的一个旋转点 (所有点合起来是一个周期), 就是给这个时刻 n 的 encodingc, 代表时刻 n 代表的基本相位.
注意: 这个 encoding 不止是一个标签, 而是带有自然的顺序意义(阿贝尔群). 容易发现, 因为指数只依赖乘积 knmodN, 时刻 2 的旋转点以频率 3 的速度旋转, 与时刻 3 的旋转点以频率 2 的速度旋转, 会落到单位圆上的同一点. 这是 DFT 的 时间–频率对偶性, 即时域和频域在有限维情形下是完全平等的.
所以说, 必须要依次映射. 如果打乱 (比如时间 n=3 映射到 ej2π2/N, 时间 n=2 映射到 ej2π3/N), 相当于对 DFT 矩阵的行进行了置换, 虽然频谱依然正确, 但是失去了其天然的几何意义.
而固定 n, 在指数上乘上频率索引 k, 表示的就是这个旋转点在旋转速度为 k 的时候, 旋转到的位置. 代表在这个频率上, 这个旋转点的相位.
- 时刻 n 的信号 x[n] 就是“对于旋转点 n, 所有频率分量上它在单位圆上的相位, 乘以这个频率分量的强度 X[k], 再加权合成”的结果.
从而 general 的傅里叶变换在这个情景可以简化得到**离散傅里叶变换 (DFT) **为:
$X[k]=X(e−j2πk/N)=∑n=0N−1x[n]e−j2πkn/N,x[n]=N1∑k=0N−1X[k]ej2πkn/N这是在有限维空间\mathbb{C}^N上用基{e^{j2\pi kn/N}}_{k=0}^{N-1}$ 做系数投影, 即一个可以用矩阵来表达的简单线性映射.
对于一维离散信号而言, 傅里叶变换的现实意义非常好理解:
- x(n) 是 intensity (overtime), 表示在时间/位置 t 上信号的强度多大
- X[k] 是 frequency, 表示信号在 “第 k 个频率分量” 上的强度有多大.
如果写成向量:
- 信号 x=(x[0],x[1],…,x[N−1])⊤∈CN
- 频谱 X=(X[0],X[1],…,X[N−1])⊤∈CN
- DFT 矩阵 F=(e−j2πkn/N)k,n=0N−1
那么:
$X=Fx,x=N1FHX即,得到了一个用频率基函数的线性组合来表达强度函数的方法.任意时间/位置上的信号强度x(n)$ 都可以通过:
- 所有频率分量上的信号强度的大小 X
和
- 此时刻 n 所有频率基函数的取值 ϕn=(ej2π0⋅n/N,ej2π1⋅n/N,…,ej2π(N−1)⋅n/N)⊤
的内积 x[n]=N1⟨X,ϕn⟩ 来表达.
这个 ej2πkn/N 看着很烦, 它有另一个形式:
$ej2πkn/N=cos(N2πkn)+jsin(N2πkn)这就是Fouriertransform的核心思想:∗∗把任何函数(实际上限制于f \in L^1(G,\mu)$, 不过离散的肯定是) 转化成一堆正弦波和余弦波的线性组合.**
这里就是我们的情况!
图像是一个离散二维信号, 也就是一个矩阵, 也就是一个函数 (之前说过):
$I:ZM×ZN→R3$
我们先具体地看一维离散信号的傅里叶变换:
Applications in image
而我们现在看回 “image” 这个信号:
二维信号 I(x,y) 的傅里叶变换 X(fx,fy) 中, 频率是向量 (fx,fy). ∣X∣ 的位置给出方向 (纹理方向) 与尺度 (条纹密度) .
[^]: Source: Torralba, Freeman, Isola
