cs / computer-vision

Frequency and Fourier transform

我们已经 state: 图像可以被看作一个离散信号.

这里我们先简略讲解一下傅里叶变换. 着重将我们用得到的部分 (DFT)

Fourier transform

Fourier transform in general (代过, 详见 Fourier Analysis 笔记)

我们可能经常会看到各种形式的傅里叶变换, 尤其是对于 f∈L1(R)f\in L^1(\mathbb{R}) 的傅里叶变换, 以及 f∈L1(Zmn)f\in L^1( \mathbb{Z}_m^n) 的傅里叶变换 (即这里的图像作为一个函数 ff); 但是很少看到解释: 为什么取频率函数的集合是不同的, 为什么累加 / 积分等等. 所以笔者这里先 state 一下 general 的理论.

最 general 的 def 与 properties 是:

Set Up:

  • 设 GG 是局部紧阿贝尔群 (Locally Compact Abelian group), together with 一个唯一的 Haar measure μ\mu.

  • 我们定义对偶群 G^\widehat G 为所有连续的群同态 χ:G→S1\chi: G\to S^1 (其中每个称为特征 (character)).

    注意: G^\widehat G 本身亦是 LCA 群.

  • 对任意的 f∈L1(G,μ)f\in L^1(G,\mu) 定义 Fourier transform f^:G^→C\hat f: \hat{G} \to \mathbb{C} $f^(χ)  =  ∫Gf(x) χ(x)‾ dμ(x),χ∈G^ \hat f(\chi) \;=\; \int_G f(x)\,\overline{\chi(x)}\, d\mu(x), \qquad \chi \in \widehat G $

则有以下定理:

  • 反演定理 (Fourier Inversion): 若 f∈L1(G)f\in L^1(G) 且 f^∈L1(G^)\widehat f\in L^1(\widehat G), 则几乎处处 $f(x)=∫G^f^(χ)χ(x)dμG^(χ) f(x)=\int_{\widehat{G}} \hat{f}(\chi) \chi(x) d \mu_{\widehat{G}}(\chi) 其中 其中 d\mu_{\widehat G}是 是 \widehat G$ 上的 Haar 测度 (normalized).

    这个定理即: Fourier 逆变换.

  • Plancherel 定理: 如果 f∈L2(G)f \in L^2(G) , 则傅里叶变换扩展为一个 L2L^2 isometry: $∫G∣f(x)∣2dμ(x)=∫G^∣f^(χ)∣2dμG^(χ) \int_G|f(x)|^2 d \mu(x)=\int_{\widehat{G}}|\hat{f}(\chi)|^2 d \mu_{\widehat{G}}(\chi) 即任意的 即任意的 |f|{L^2(G)}=|\hat{f}|{L^2(\widehat{G})}$.

    在 Rn\mathbb{R}^n 上就是 Parseval 恒等式. 这个定理的现实意义是时域与频域的等距同构.

Fourier transform on G=RG= \mathbb{R}

G=RG= \mathbb{R} 时, 时最标准的傅里叶变换. 这个时候的对偶群 G^\widehat G 的每个元素是一个函数: $χξ(x)=e2πiξx=cos⁡(2πξx)+isin⁡(2πξx) \chi_{\xi}(x)=e^{2 \pi i \xi x} = \cos (2 \pi \xi x)+i \sin (2 \pi \xi x) $ 这个特征函数的性质:

  • 对于所有的 ξ\xi, 它的这个特征函数对于任意 xx 的取值的模都是 1, 并且在有限区间上 (如 [0,1][0,1] ) 存在正交性: $∫01χξ(x)χη(x)‾dx=∫01e2πi(ξ−η)xdx={1,ξ=η,0,ξ≠η( 若 ξ,η∈Z). \int_0^1 \chi_{\xi}(x) \overline{\chi_\eta(x)} d x=\int_0^1 e^{2 \pi i(\xi-\eta) x} d x= \begin{cases}1, & \xi=\eta, \\ 0, & \xi \neq \eta(\text { 若 } \xi, \eta \in \mathbb{Z}) .\end{cases} $

  • 具有乘法群结构: $χξ(x)⋅χη(x)=χξ+η(x) \chi_{\xi}(x) \cdot \chi_\eta(x)=\chi_{\xi+\eta}(x) $

    χξ(x)‾=χ−ξ(x)\overline{\chi_{\xi}(x)}=\chi_{-\xi}(x)

在 Fourier 正变换里, $f^(ξ)=∫Rf(x)e−2πiξxdx \hat{f}(\xi)=\int_{\mathbb{R}} f(x) e^{-2 \pi i \xi x} d x $

f^(ξ)\hat{f}(\xi) 的这个值, 这个积分运算即: 信号函数 ff 与频率模式 χξ\chi_{\xi} 的内积.

更加形象地说: 是函数 ff 在频率模式 χξ(x)=e2πiξx\chi_{\xi}(x)=e^{2 \pi i \xi x} 上的投影.

对于每个频率模式 χξ\chi_{\xi}, ff 在其上的投影系数 f^(ξ)\hat{f}(\xi) 都是一个 constant, 其模值表示这个频率模式在整个信号 ff 中的强度, 而其值包含了这个频率模式的相位 (辐角).

而在傅里叶逆变换里, $f(x)=∫Rf^(ξ)e2πiξxdξ f(x)=\int_{\mathbb{R}} \hat{f}(\xi) e^{2 \pi i \xi x} d \xi $

就是把所有频率成分加权叠加回来.

就是说, 原函数是对偶群中的所有频率模式的加权积分, 每个频率模式的权重就是 ff 的 Fourier 变换 f^\hat f 中, 这个频率模式 χξ\chi_\xi 的得分 f^(ξ)\hat f(\xi).

因而, 整个傅里叶变换其实就是把一个函数 ff 给分解成一族振动模式 {χξ}\{\chi_\xi\} 关于 ξ\xi 的加权积分.

What we are interested: DFT, 即 Fourier transform on G=ZNG = \mathbb{Z}_N

对于 G=ZNG = \mathbb{Z}_N, 即有限长度的时间 / 位置上, 对偶群 G^\widehat G 的元素是所有群同态: $χk:n↦ej2πkn/N,k=0,1,…,N−1 \chi_k: n \mapsto e^{j 2 \pi k n / N}, \quad k=0,1, \ldots, N-1 $

我们画出 χ0,χ1,χ2\chi_0, \chi_1, \chi_2 的图来演示:

image-20250922223229316image-20250922223239339image-20250922223253916

我们已经从群论的角度解释: 它们是 ZN\mathbb{Z}_N 的 characters.

而

  1. 线性代数解释: 它们构成 CN\mathbb{C}^N 的一组正交基
  2. 信号处理解释: 它是从连续傅里叶基 ejωte^{j\omega t} 离散化 (时间采样+有限窗口) 自然得到的

几何意义:

ej2πkn/Ne^{j 2\pi kn/N} 表示的是单位圆上, 从角度 0 开始, 沿逆时针旋转了 2πN\tfrac{2\pi}{N} 的 knkn 倍;

对于每个 kk, χk\chi_k 都表示一个频率函数: 一个复正弦函数 $χk:n↦ej2πkn/N=cos⁡ ⁣(2πkNn)+jsin⁡ ⁣(2πkNn) \chi_k: n \mapsto e^{j 2 \pi k n / N} =\cos\!\Big(\tfrac{2\pi k}{N}n\Big) + j \sin\!\Big(\tfrac{2\pi k}{N}n\Big) $

在位置 n=0,⋯ ,N−1n=0, \cdots, N-1 的这几个采样点上, ej2πkn/Ne^{j 2\pi k n/N} 表示的是这个频率函数在位置 nn 上的值.

从欧拉公式来看:

所以它确实就是一个正弦/余弦波(复正弦波)。

对于每个 nn, 取 k=1k=1, 这个 ej2πn/Ne^{j 2\pi n/N} 表示了单位圆上的一个旋转点 (所有点合起来是一个周期), 就是给这个时刻 nn 的 encodingc, 代表时刻 nn 代表的基本相位.

注意: 这个 encoding 不止是一个标签, 而是带有自然的顺序意义(阿贝尔群). 容易发现, 因为指数只依赖乘积 kn mod Nkn \bmod N, 时刻 22 的旋转点以频率 33 的速度旋转, 与时刻 33 的旋转点以频率 22 的速度旋转, 会落到单位圆上的同一点. 这是 DFT 的 时间–频率对偶性, 即时域和频域在有限维情形下是完全平等的.

所以说, 必须要依次映射. 如果打乱 (比如时间 n=3n=3 映射到 ej2π2/Ne^{j 2\pi 2/N}, 时间 n=2n=2 映射到 ej2π3/Ne^{j 2\pi 3/N}), 相当于对 DFT 矩阵的行进行了置换, 虽然频谱依然正确, 但是失去了其天然的几何意义.

而固定 nn, 在指数上乘上频率索引 kk, 表示的就是这个旋转点在旋转速度为 kk 的时候, 旋转到的位置. 代表在这个频率上, 这个旋转点的相位.

  • 时刻 nn 的信号 x[n]x[n] 就是“对于旋转点 nn, 所有频率分量上它在单位圆上的相位, 乘以这个频率分量的强度 X[k]X[k], 再加权合成”的结果.

从而 general 的傅里叶变换在这个情景可以简化得到**离散傅里叶变换 (DFT) **为: $X[k]=X(e−j2πk/N)=∑n=0N−1x[n] e−j2πkn/N,x[n]=1N∑k=0N−1X[k] ej2πkn/N X[k]= X(e^{-j2\pi k / N}) = \sum_{n=0}^{N-1} x[n]\,e^{-j2\pi kn/N},\quad x[n]=\frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{j2\pi kn/N} 这是在有限维空间 这是在有限维空间 \mathbb{C}^N上用基 上用基 {e^{j2\pi kn/N}}_{k=0}^{N-1}$ 做系数投影, 即一个可以用矩阵来表达的简单线性映射.

对于一维离散信号而言, 傅里叶变换的现实意义非常好理解:

  • x(n)x(n) 是 intensity (overtime), 表示在时间/位置 tt 上信号的强度多大
  • X[k]X[k] 是 frequency, 表示信号在 “第 kk 个频率分量” 上的强度有多大.

如果写成向量:

  • 信号 x=(x[0],x[1],…,x[N−1])⊤∈CN\mathbf{x} = (x[0], x[1], \dots, x[N-1])^\top \in \mathbb{C}^N
  • 频谱 X=(X[0],X[1],…,X[N−1])⊤∈CN\mathbf{X} = (X[0], X[1], \dots, X[N-1])^\top \in \mathbb{C}^N
  • DFT 矩阵 F=(e−j2πkn/N)k,n=0N−1F = \big( e^{-j2\pi kn/N}\big)_{k,n=0}^{N-1}

那么: $X=Fx,x=1NFHX \mathbf{X} = F \mathbf{x}, \qquad \mathbf{x} = \frac{1}{N} F^H \mathbf{X} 即,得到了一个用频率基函数的线性组合来表达强度函数的方法.任意时间/位置上的信号强度 即, 得到了一个用频率基函数的线性组合来表达强度函数的方法. 任意时间/位置上的信号强度 x(n)$ 都可以通过:

  • 所有频率分量上的信号强度的大小 X\mathbf{X}

和

  • 此时刻 nn 所有频率基函数的取值 ϕn=(ej2π0⋅n/N,  ej2π1⋅n/N,  …,  ej2π(N−1)⋅n/N)⊤\phi_n = \big( e^{j2\pi 0\cdot n/N},\; e^{j2\pi 1\cdot n/N},\; \dots,\; e^{j2\pi (N-1)\cdot n/N} \big)^\top

的内积 x[n]=1N⟨X, ϕn⟩x[n] = \frac{1}{N}\langle \mathbf{X}, \, \phi_n\rangle 来表达.

这个 ej2πkn/Ne^{j2\pi kn/N} 看着很烦, 它有另一个形式: $ej2πkn/N=cos⁡ ⁣(2πknN)+jsin⁡ ⁣(2πknN) e^{j2\pi kn/N} = \cos\!\Big(\tfrac{2\pi kn}{N}\Big) + j \sin\!\Big(\tfrac{2\pi kn}{N}\Big) 这就是Fouriertransform的核心思想:∗∗把任何函数(实际上限制于 这就是 Fourier transform 的核心思想: **把任何函数 (实际上限制于 f \in L^1(G,\mu)$, 不过离散的肯定是) 转化成一堆正弦波和余弦波的线性组合.**

Fourier transform on G=ZM×ZNG=\mathbb{Z}_M\times\mathbb{Z}_N

这里就是我们的情况!

图像是一个离散二维信号, 也就是一个矩阵, 也就是一个函数 (之前说过): $I:ZM×ZN→R3 I: \mathbb{Z}_M \times \mathbb{Z}_N \rightarrow \mathbb{R}^3 $

我们先具体地看一维离散信号的傅里叶变换:

Applications in image

而我们现在看回 “image” 这个信号:

二维信号 I(x,y)I(x,y) 的傅里叶变换 X(fx,fy)X(f_x,f_y) 中, 频率是向量 (fx,fy)(f_x,f_y). ∣X∣|X| 的位置给出方向 (纹理方向) 与尺度 (条纹密度) .

image-20250921054610022

[^]: Source: Torralba, Freeman, Isola

image-20250921054712919