傅里叶变换

傅里叶变换关系

冲激

  • 冲激
    • 单位冲激($0$ 处):$\delta(t)=[t=0]\infty,\int_{-\infty}^{\infty}\delta(t)dt=1$
    • 单位冲激($t_0$ 处):$\delta(t-t_0)\infty$
    • 采样性质:$\int_{-\infty}^{\infty}f(t)\delta(t)dt=f(0)$
  • 离散冲激
    • 离散单位冲激:$\delta(x-x_0)=[t=0]$
    • 采样性质:$\sum_{x=-\infty}^\infty f(x)\delta(x-x_0)=f(x_0)$
  • 冲激串: $s_{\Delta T}(t)=\sum_{n=-\infty}^{\infty}\delta(t-n\Delta T)$
    • $S_{\Delta T}(\mu)=\frac{1}{\Delta T}s_{\frac{1}{\Delta T}}$
  • 采样: $f(t)s_{\Delta T}(t)=\sum_{n=-\infty}^{\infty}f(t)\delta(t-n\Delta T)$
  • 周期化:$f(t)\star s_{\Delta T}(t)$

(Continuous) Fourier Tranform

连续函数 $f(t)$ $\overset{\mathcal{F}}{\leftrightarrow}$ 连续函数 $F(\mu)$

  • FT

$$F(\mu)=\mathcal{F}(f)=\int_{-\infty}^{\infty}f(t)e^{-i2\pi\mu t}dt=\int_{-\infty}^\infty f(t)[\cos(2\pi\mu t)-i\sin(2\pi\mu t)]dt$$

  • IFT

$$f(t)=\mathcal{F}^{-1}(F)=\int_{-\infty}^{\infty}F(\mu)e^{i2\pi\mu t}d\mu$$

  • 性质
    • 对称性:$\mathcal{F}(F(t))=f(-\mu)$
    • 线性: $\mathcal{F}(\alpha f+\beta g)=\alpha\mathcal{F}(f)+\beta\mathcal{F}(g)$
    • 平移性:
      • $\mathcal{F}(f(t-\tau))=F(\mu)e^{-i2\pi\mu\tau}$
    • 微分关系:$\mathcal{F}(f'(x))i\mu=\mathcal{F}(f(x))$
    • 卷积定理
      • $(f(t)\star h(t))(x)=\int_{-\infty}^\infty f(x-t)h(t)dt$
      • $\mathcal{F}(f(t)\star h(t))=H(\mu)F(\mu)$
      • $\mathcal{F}(f(t)h(t))=H(\mu)\star F(\mu)$
  • 盒状函数:$f(t)=A[|x|<=\frac{W}{2}]$
    • $F(\mu)=AW\frac{\sin(\pi\mu W)}{\pi\mu W}=AW\text{sinc}(\mu W)$

Fourier Series

连续周期函数 $\overline{f}(t)$ $\overset{\mathcal{FS}}{\leftrightarrow}$ 离散函数 $F[k]$

  • $\overline{f}(t)=f(t)\star s_{T_0}(t)$
  • FS

$$ F[k] = \mathcal{FS}(\overline{f}) = \mathcal{F}(f\star s*{T_0}) = \frac{1}{T}\int*{-T/2}^{T/2}f(t)e^{-i\frac{2\pi k}{T}t}dt$$

  • IFS

$$\overline{f}(t) = \mathcal{FS}^{-1}(F) =\sum_{n=-\infty}^{\infty}F[n]e^{i\frac{2\pi n}{T}t}$$

Discrete Time Fourier Transform

离散函数 $x[n]$ $\overset{\mathcal{DTFT}}{\leftrightarrow}$ 连续周期函数 $\widetilde F(\mu)$

  • $x[n]=\widetilde f(t)=f(t)s_{\Delta T}$
  • DTFT

$$\widetilde F(\mu) = \mathcal{DTFT}(x[n]) = \mathcal{F}(f(t)s_{\Delta T})$$

  • 采样定理:可完全恢复的采样率 $\frac{1}{\Delta T}>2\mu_{\max}$
    • 带限函数:傅里叶变换后非零频率属于 $[-\mu_{\max},\mu_{\max}]$
    • 奈奎斯特采样率:$2\mu$(无限采样)
  • 混淆:带限函数必须在 $(-\infty,\infty)$ 有值,有限长度的采样,混淆不可避免
    • 带限函数有限长度采样 $f(t)[0\leq t\leq T]$
    • 抗混淆:事先防止或减轻混淆
      • 平滑输入函数:图像散焦,减少高频分量
  • 由样本恢复原函数
    • 内插: $f(t)=\sum_{n=-\infty}^{\infty}f(n\Delta T)\text{sinc}(\frac{t-n\Delta T}{\Delta T})$

Discrete Fourier Transform

离散周期函数 $f_n$ $\overset{\mathcal{DFT}}{\leftrightarrow}$ 离散周期函数 $F_m$

  • DFT:

$$F(u)=\mathcal{DFT}(f_n)=\sum_{x=0}^{M-1}f(x)e^{-i2\pi ux/M} ,u=0,1,2,\cdots,M-1$$

  • IDFT:

$$f(x)=\mathcal{IDFT}(F)=\frac{1}{M}\sum_{0}^{M-1}F(u)e^{i2\pi ux/M},x=0,1,\cdots,M-1$$

  • 适用于任何均匀采样的有限离散样本集
    • 采样数:$M$
    • 时间间隔:$\Delta T$
    • 时间长度:$T=M\Delta T$
    • 频域间隔:$\Delta u=\frac{1}{T}$
    • 频域范围: $\Omega=\frac{1}{\Delta T}$
  • 循环卷积: $f(x)\star h(x)=\sum_{m=0}^{M-1}f(m)h(x-m)$

二维傅里叶变换

冲激

  • 冲激:$\delta(t,z)$
  • 二维冲激串:$s_{\Delta T\Delta Z}(t,z)=\sum_{m=-\infty}^{\infty}\sum_{n=-\infty}^\infty\delta(t-m\Delta T,z-n\Delta Z)$
  • 二维盒状函数:$F(\mu,v)=ATZ\text{sinc}(\pi\mu T)\text{sinc}(\pi v Z)$
  • 二维采样定理:$\frac{1}{\Delta T}>2\mu_{\max},\frac{1}{\Delta Z}>2v_{\max}$
  • 混淆
    • 空间混淆(欠采样):锯齿,伪高光,虚假模式
      • 图像放大:过采样
      • 图像缩小:欠采样
    • 时间混淆:图像系列中的时间间隔:车轮倒转
    • 摩尔模式:两个等间隔的光栅产生的差拍模式

离散傅里叶变换

  • DFT

$$F(u,v)=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)e^{-i2\pi(ux/M+vy/N)}$$

  • IDFT

$$f(x,y)=\frac{1}{MN}\sum_{u=0}^{M-1}\sum_{v=0}^{N-1}F(u,v)e^{i2\pi(ux/M+vy/N)}$$

  • 平移性
    • $f(x-x_0,y-y_0)\iff F(u,v)e^{-i2\pi(x_0u/M+y_0v/N)}$
    • $f(x,y)e^{i2\pi(u_0x/M+v_0y/N)}\iff F(u-u_0,v-v_0)$
    • 中心化:$f(x,y)(-1)^{x+y}\iff F(u-M/2,v-N/2)$
    • 幅值不变
  • 旋转性
    • 极坐标:$f(r,\theta+\theta_0)\iff F(\omega,\varphi+\theta_0)$
  • 对称性
    • 偶函数:$w_e(x,y)=w_e(M-x,N-y)$
    • 奇函数:$w_o(x,y)=-w_o(M-x,N-y)$
    • $w_e(x,y)=\frac{w(x,y)+w(M-x,N-y)}{2}$
    • $w_o(x,y)=\frac{w(x,y)-w(M-x,N-y)}{2}$
    • 实函数的傅里叶变换是共轭对称的:$F^*(u,v)=F(-u,-v)$
    • 虚函数的傅里叶变换是共轭反对称:$F^*(u,v)=-F(-u,-v)$

傅里叶谱

  • 极坐标:$F(u,v)=|F(u,v)|e^{i\phi(u,v)}$
  • 幅度(傅里叶谱):$|F(u,v)|$
    • 偶对称
    • 正弦波的幅度,携带了灰度信息
  • 相角:$\phi(u,v)\in[-\pi,\pi]$
    • 奇对称
    • 正弦波的位移,携带了定位信息
  • 功率:$P(u,v)=|F(u,v)|^2$
  • $F(0,0)$: 直流分量
    • $|F(0,0)|=MN|\overline{f}(x,y)|$

二维离散卷积

  • $f(x,y)\star h(x,y)=\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}f(m,n)h(x-m,y-n)$
  • $f(x,y)\star h(x,y)\iff F(u,v)H(u,v)$
  • $f(x,y)h(x,y)\iff F(u,v)\star H(u,v)$
  • 缠绕错误
    • 样本数:$A,B$
    • $0$ 填充:$P\geq A+B-1$

其它变换

拉普拉斯变换

$F(\omega)=\int_0^{+\infty}f(t)e^{-\sigma t}e^{-i\omega t}dt=\int_0^{+\infty}f(t)e^{-(\sigma+i\omega)t}dt=\int_0^{+\infty}f(t)e^{-st}dt$

$Z$ 变换

$X(\omega)=\sum_{-\infty}^{+\infty}x[n]e^{-(\sigma+i\omega)nT_s}$

$X(z)=\sum_{n=-\infty}^{+\infty}x[n]z^{-n}$

短时傅里叶变换

STFT: 方窗函数(紧支撑性)

$X(\omega,t_s)=\int_{-\infty}^{+\infty}h(t-t_s)x(t)e^{i\omega(t-t_s)}dt$

连续小波变换(CWT)

海森堡测不准原理:$\Delta t\Delta f>C$

  • 低频信号:宽窗,低时域分辨度,高频率分辨率
  • 高频信号:窄窗,高时域分辨度,低频域分辨度
  • 动态分辨率:小波母函数
    • 紧支撑性:$\exists a>0,\forall|t|>a,\psi(t)=0$
    • 波动性:$\int_{-\infty}^{+\infty}\psi(t)dt=0$
    • 容许条件(变换可逆):$c_\psi=2\pi\int_{-\infty}^{+\infty}\frac{|\overline{\psi}(f)|^2}{|f|}df<+\infty$
    • 正交性(变换可逆)
  • 小波函数:$\psi^*(\tau,s)=\frac{1}{\sqrt{s}}\psi(\frac{t}{s}-\tau)$
    • s 小,挤压,频率提高
  • CWT: $\mathrm{CWT}x^\psi(\tau, s)=\frac{1}{\sqrt{s}}\int{-\infty}^{+\infty}x(t)\psi(\frac{t}{s}-\tau)dt$
  • Haar 小波
    • 尺度函数(父函数) $\phi=[0\leq x<1]$
    • Haar 小波函数(母函数)$\psi=\phi(2x)-\phi(2x-1)$

离散小波变换(DWT)

Mallet 算法

  • Haar 父函数与母函数
    • $V_j={\sum_{k\in \mathbb{Z}}a_k\phi(2^jx-k)}$
    • $W_j={\sum_{k\in \mathbb{Z}}a_k\psi(2^jx-k)}$
    • $V_j=W_{j-1}\oplus W_j\oplus\cdots\oplus W_0\oplus V_0$
    • $f_j=\omega_{j-1}+\omega_{j-2}+\cdots+\omega_0+f_0$
  • 采样:$a_k=f(\frac{k}{2^j})$
    • $f_j(x)=\sum_{k\in\mathbb{Z}}a_k^j\phi(2^jx-k)=\omega_{j-1}+f_{j-1}$
  • 半子带滤波:获得高频 $(\frac{F_s}{2},F_s)$ 和低频 $(0,\frac{F_s}{2})$ 信号
  • 一层小波分解:一次半子带滤波 + 一次 2 倍下采样

频域滤波

  • 直观
    • 变化最慢的分量,与平均灰度成正比
    • 低频对应于图像中缓慢变化的灰度(墙)
    • 高频对应于图像剧烈变化的灰度(边缘)
  • 频域滤波器:$H(u,v)$
    • $g(x,y)=\mathcal{F}^{-1}(H(u,v)F(u,v))$
    • $F(u,v)$ 中心化: $F(u,v)=\mathcal{F}(f(x,y)(-1)^{x+y})$
  • 频域滤波流程
    • 补零:$M\times N$ 补零成 $P=2M,Q=2N$ 的图像 $f_p(x,y)$
    • 频域中心化:$f_p(x,y)(-1)^{x+y}$
    • DFT: $F(u,v)$
    • 滤波函数 $H(u,v)$生成: $P\times Q$, 中心在 $(\frac{P}{2},\frac{Q}{2})$
    • $G(u,v)=H(u,v)F(u,v)$
    • 得到处理后函数:$g_p(x,y)=\text{Re}(\mathfrak{F}^{-1}(G(u,v)))(-1)^{x+y}$
    • 提取 $g_p(x,y)$ 中左上角的 $M\times N$ 的图像
  • 对应的空间滤波器:$g(x,y)=\mathfrak{F}^{-1}(H(u,v))$
    • 构造空间滤波器来近似频率滤波器
  • 零相角滤波器:$\mathcal{F}^{-1}(H(u,v)F(u,v))=\mathcal{F}^{-1}(H(u,v)R(u,v)+iH(u,v)C(u,v))$

平滑图像(低通滤波)

衰减高频通过低频,模糊图像

  • 理想低通滤波器(ILPF):$H(u,v)=[D(u,v)\leq D_0]$
    • $D(u,v)=[(u-\frac{P}{2})^2+(v-\frac{Q}{2})^2]^{\frac{1}{2}}$
    • 截止频率:$D_0$
    • 振铃(ringring) 现象
  • Butterworth 低通滤波器(BLPF):$H(u,v)=\frac{1}{1+(D(u,v)/D_0)^{2n}}$
    • $n=2$:平滑效果较好,且无振铃
  • 高斯低通滤波器(GLPF):$H(u,v)=e^{-D^2(u,v)/2D_0^2}$

锐化图像

  • 高通滤波器:衰减低频通过高频,强化细节,对比度降低
    • 略微平移保留对比度
    • 理想高通滤波器
    • 布特沃斯高通滤波器
    • 高斯高通滤波器
  • 频率域的拉普拉斯算子
    • $H(u,v)=-4\pi^2(u^2+v^2)$
    • $\nabla^2f(x,y)=\mathcal{F}^{-1}(H(u,v)F(u,v))$
    • 图像锐化
      • $g(x,y)=f(x,y)+c\nabla^2f(x,y)$
      • $g(x,y)=\mathcal{F}^{-1}((1+4\pi^2D^2(u,v))F(u,v))$
        • 量纲问题
  • 非锐化掩蔽
    • $g(x,y)=f(x,y)+kg_{\text{mask}(x,y)}$
    • $g(x,y)=\mathcal{F}^{-1}((1+k(1-H_{\text{LP}(u,v)}))F(u,v))$
    • 高频增强滤波:$\mathcal{F}^{-1}((k_1+k_2H_{\text{HP}(u,v)})F(u,v))$
      • $1-H_{\text{LP}}=H_{\text{HP}}$
      • 防止图像变暗
  • 同态滤波
    • 照射反射模型:$f(x,y)=i(x,y)r(x,y)$
      • 照射:$0<i(x,y)<\infty$
      • 反射:$0<r(x,y)<1$
    • $z(x,y)=\ln f(x,y)=\ln i(x,y)+\ln r(x,y)$
    • $Z(u,v)=F_i(u,v)+F_r(u,v)$
      • 低频:照射分量
      • 高频:反射分量
    • 增强对比度,压缩灰度:$H(u,v)=(\gamma_H-\gamma_L)(1-e^{-c(D^2(u,v)/D_0^2)})+\gamma_L$

选择性滤波

  • 带阻/带通滤波器
    • 理想带阻滤波器:$H_{\text{BR}}(u,v)=1-[D_0-\frac{W}{2}\leq D\leq D_0+\frac{W}{2}]$
    • 理想带通滤波器:$H_{\text{BP}}=1-H_{\text{BR}}$
  • 陷波滤波器(notch filters)
    • $H_{\text{NR}}=\prod_{k=1}^QH_k(u,v)H_{-k}(u,v)$
    • $H_k(u,v)$ 是中心在 $(u_k,v_k)$ 的高通滤波器
    • 交互式改变,不进行补 0 填充
    • 处理摩尔模式