理论基础
- 卷积:$y(t) = f(t)*h(t) = \int^\infty_{-\infty} f(\tau)h(t-\tau)d\tau$
- 相关的定义:
- 任意两个信号的相关函数定义为: $R_{fg}(t) = f(t)\cdot g(t) = \int^\infty_{-\infty} f(\tau)g(t+\tau)d\tau$
- 相关与卷积的关系:$R_{fg}(t) = f(t)\cdot g(t) = f(-t)*g(t)$
- 图像变换:
- 图像变换是将图像从空域变换到其它域如频域的数学变换
- 可进行图像变换的基本条件:
- 满足正交、完备两个条件的函数集合或矩阵才能用于图像的分析
- 常用的几种变换:傅里叶变换、 WALSH变换、哈达玛变换、 Haar变换、 SLANT变换、 K-L变换以及特定条件下的CONSINE变换、 SINE变换等,都满足正交性和完备性两个条件
正交变换
- 连续函数集合的正交性
- 正交函数集合 $U={u_0(t),u_1(t),\cdots}$
- $\int^{t_0+T}_{t_0} u_m(t)u_n(t)dt = \left\lbrace \begin{matrix}C & if\, m=n \\ 0 & others \end{matrix} \right.$
- 当C = 1时,称集合为归一化正交函数集合,即每一个向量为单位向量
- 正交函数集合的完备性:
- 若$f(x)$是定义在 $t_0$ 和 $t_0+T$ 区间的实值信号,平方可积。可以表示为 $f(x) = \sum^\infty_{n=0} a_nu_n(x)$
- 对任意小的 $\epsilon>0$,存在充分大的$N$,用$N$个有限展开式估计$f(x)$时, $\hat f(x) = \sum^{N-1}_{n=0} a_nu_n(x)$
- 可有:$\int^{t_0+T}_{t_0}|f(x)-\hat f(x)|^2dx<\epsilon$
- 则称函数 U 集合是完备的
- 正交函数集合完备性的物理意义:
- 任何数量的奇函数累加仍为奇函数
- 任何数量的偶函数累加仍为偶函数
- 酉变换(unitary transform)
- 若A为复数矩阵,正交的条件为: $A^{-1}=A^{*T}$
- A*为A的复数共轭矩阵,满足这个条件的矩阵为酉矩阵(unitary matrix)
- 对于任意向量f的运算称为酉变换: $g=Af$
- 正交变换是酉变换的特例
- 酉矩阵是正交阵
- 用于信号分析的基函数集合和正交矩阵都应满足正交性和完备性
- 二维酉变换: $F=AfA^T$
- A为酉阵,则$A^{-1}$和$A^T$都是酉阵
- 酉变换是能量保持的变换 ($F=Af$)
- 酉变换能量的紧缩: 正交酉变换往往趋于将信号能量压缩到相对少的变换系数中,由于总能量保持不变,因此许多变换系数将包含很少的能量. K-L变换可以达到最大的能量紧缩
- 酉变换去相关: 当输入向量元素间高度相关时,变换系数趋向于去相关,这意味着协方差矩阵的非对角项和对角项相比趋于变小。K-L变换可以达到完全的去相关
- 均值和方差:
- 设 $f(x,y)$ 的均值和协方差为 $\mu_f$ 和 $\Sigma_f$
- 则 $F(u,v)$ 的均值为: $\mu_F=E(Af)=AE(f)=A\mu_f$
- $F(u,v)$ 的协方差为: $\Sigma_f=A\Sigma_fA^{*T}$
- A为酉阵,则其行列式值$|A|=1$
傅立叶变换
- 一维连续傅里叶变换:
- $F(f)=\int^{\infty}_{-\infty}h(t)e^{-j2\pi ft} dt$
- 指数形式:$F(u)=|F(u)|e^{j\phi (u)}$, 其中 $|F(u)|$ 为幅度谱,$\phi (u)$ 为 相位谱,相位角
- 一维离散傅立叶变换(DFT)
- $F(u)=\frac 1N \sum^{N-1}_{x=0}f(x)e^{-j\frac{2\pi ux}{N}},\; u=0,1,\cdots,N-1$
- 逆变换为: $f(x) =\sum^{N-1}_{u=0}F(u)e^{j\frac{2\pi ux}{N}}, \; x=0,1,\cdots,N-1 $
- 二维傅立叶变换:
- $F(u,v)=\int^{\infty}{-\infty} \int^{\infty}{-\infty} f(x,y)e^{-j2\pi(ux+vy)} dxdy$
- 二维离散傅立叶变换:
- $F(u,v)=\frac{1}{MN}\sum^{M-1}{x=0}\sum^{N-1}{y=0} f(x,y)e^{-j2\pi(\frac{ux}M+\frac{vy}N)}$
- 二维离散傅立叶变换的性质:
- 线性性质(加法定理): $a_1f_1(x,y)+a_2f_2(x,y) \Leftrightarrow a_1F_1(u,v)+a_2F_2(u,v)$
- 比例性质(相似性定理):
- $f(ax,by)\Leftrightarrow \frac1{|ab|}F(\frac ua,\frac vb) $
- 比例特性表明:信号在时域中压缩(k>1,变化速度加快)等效于在频域扩展(频带加宽);反之亦然
- 可分离性:
- $F(u,v)=F_x\lbrace F_y[f(x,y)]\rbrace = F_y\lbrace F_x[f(x,y)]\rbrace$
- 二维DFT可分离为两次一维DFT
- 空间位移(位移定理):
- $f(x-x_0,y-y_0) \Leftrightarrow F(u,v)e^{-j2\pi (ux_0+vy_0)/N}$
- 函数自变量的位移的傅立叶变换产生一个复系数,等效于频谱函数的相位谱改变,而幅度谱不变
- 频率位移:
- $f(x,y)e^{j2\pi (xu_0+yv_0)/N} \Leftrightarrow F(u-u_0,v-v_0)$
- 函数的频率位移的相当于傅立叶变换的坐标原点平移,而幅度谱和相位谱不变
- 周期性:
- $F(u,v)=F(u+aN,v+bN), \; f(x,y)=f(x+aN,y+bN)$
- 离散傅立叶变换DFT和它的逆变换是以N为周期的函数
- 共轭对称性:
- 若 $f(x,y)$ 为实函数,$F(u,v)$ 为其傅里叶变换,则 $F(u,v) \Leftrightarrow F^*(-u,-v)$
- 图像的傅立叶变换结果是以原点为中心的共轭对称函数
- 旋转不变性:
- $f(r,\theta +\theta_0) \Leftrightarrow F(\rho,\varphi+\theta_0)$
- 对图像的旋转变换和傅立叶变换的顺序是可交换的
- 平均值:
- $F(0,0)=\frac 1{N^2}\sum^{N-1}{x=0} \sum^{N-1}{y=0} f(x,y)=\bar f(x,y)$
- 离散函数的均值等于该函数傅立叶变换在(0,0)点的值
- 二维离散傅立叶变换的显示
- 为使频谱分布中间低、周围高,通常对频域进行换位以使频谱分布符合上述要求——图像中心化
- 使频域的中心位移$u_0=v_0=N/2$: $f(x,y)(-1)^{x+y}\Leftrightarrow F(u-\frac N2,v-\frac N2) $
- 相当于对原始图像$f(x,y)$乘以$(-1)^{m+n}$,再进行傅里叶变换
- 离散傅立叶变换的幅度与相位
- 图像信号的傅里叶变换包含幅度与相位两部分
- 幅度谱具有较明显的信号结构特征和易于解释
- 实验证明,幅度本身只包含有图像本身含有的周期结构,并不表示其在何处
- 相位谱类似随机图案,一般难以进行解释
- 物体在空间的移动,相当于频域的相位移动, 相位谱具有同样重要的意义
- 单凭幅度或相位信息,均不足以恢复原图像
快速傅立叶变换
- 基本思想
- 将变换公式分解为奇数项和偶数项之和
- 逆向FFT算法:
- 用正向变换计算逆向变换: $f(x)=FFT^{-1}[F(u)]=N{\lbrace FFT[F^(u)]\rbrace}^$
- 二维快速Fourier变换
- 利用傅里叶变换的分离性质,对二维FFT进行2次的一维FFT变换
离散余弦变换
- 问题的提出:
- 傅里叶变换的一个最大问题是:它的参数都是复数,在数据的描述上相当于实数的两倍。为此,我们希望有一种能够达到相同功能但数据量又不大的变换
- 当f(x)为偶函数时,傅里叶变换的计算公式虚部为零,只有余弦项
- 一维离散余弦变换定义
- $F(u)=\sqrt{\frac 2N} \sum^{N-1}_{x=0} f(x)cos[\frac \pi{2N}(2x+1)u]$
- $F(0)=\sqrt{\frac 1N}\sum^{N-1}_{x=0} f(x)$
- 任意函数离散余弦变换
- 一个任意函数采样从0, 1, 2, …, N-1,若向负方向折叠形成2N采样的偶函数,就可以进行2N的偶函数傅立叶变换。此时可采用离散余弦变换进行。
- 余弦变换的性质
- 余弦变换为实的正交变换,变换核的基函数正交
- 序列的余弦变换是DFT的对称扩展形式
- 核可分离,可以用两次一维变换来执行
- 余弦变换的能量向低频集中
- 余弦变换有快速变换,和傅立叶变换一样,分奇偶组
沃尔什变换
- 思路:
- 正弦函数集,不考虑函数值,仅考察函数值的过零点位置分布时,可形成包含+1和-1极值状态下的正交函数集
- 希望找到更简单的变换,构建更为简单的正交函数集,只要满足正交关系
- 二维沃尔什—哈达玛变换定义
- $F_H=WHT{f}=HfH, \; f=WHT^{-1}{F_H}=HF_HH$
- 变换矩阵H具有递推公式:$H_1=[1], H_2=\frac 1{\sqrt2} \begin{bmatrix} 1 & 1 \ 1 &-1 \end{bmatrix}, \; H_{2N}=\frac 1{\sqrt2} \begin{bmatrix} H_N & H_N \ H_N &-H_N \end{bmatrix}$
- 沃尔什—哈达玛变换特性
- WHT变换是实的、对称的、正交变换
- WHT可由快速算法实现,因为DHT只包括加减,因此没有任何乘法运算。
- WHT有较好的能量集中特性
K-L变换
- 主导思想
- 假定一幅图像在某个通讯信道中传输了M次,由于任何物理信道均存在随机干扰因素,接收到的图像系列总混杂有许多随机干扰信号,称之为随机图像集合,集合中各图像之间存在相关性但又不相等
- K-L变换本质上是针对这类广泛的随机图像提出来的,当对M个图像施加了K-L变换以后,变换后的M新图像组成的集合中各图像之间互不相关
- 由变换结果图像集中取有限个图像K (K<M)而恢复的图像将是原图像在统计意义上的最佳逼近
- 变换原理:
- 设 $X=[x_1,x_2,…,x_n]^T$ 和 $Y=[y_1,y_2,…,y_n]^T$ 为两个n维随机向量,其元素$x_i, y_j$ 分别具有M个随机值
- 假定X能由Y精确表示为:$X=\Phi Y$, $\Phi$为$n\times n$正交矩阵,记为$[\Phi_1,\Phi_2,…,\Phi_n]$
- 若取Y向量的前m个向量$Y_m$来表示X,记为$X_m$,可有误差 $\Delta X_m=X-X_m$
- 从统计角度,如何选择$\Phi$, 使得上述误差的统计均方值达到极小
- 若取$\Phi_i$为X的协方差矩阵$C_x$的特征向量,则对X进行下述变换后: $Y=\Phi^TX$, 其结果Y向量可满足前述要求
- $Y=\Phi^TX$ 与反变换 $X=\Phi Y$ 称为 K-L 变换,通常又称之为Hotelling变换、特征向量变换或主成分分析
- 计算方法:
- 对N维随机向量$X=[x_1,x_2,…,x_n]^T$,其每个元素$x_i$分别具有M个样本
- 其平均值向量定义为:$M_x=E{X}, \; M_x \cong \frac 1M\sum^M_{i=1}x_i$
- 其协方差矩阵为一个$N×N$的矩阵,定义为 $C_x=E{(X-M_x)(X-M_x)^T}$,
- $C_x \cong \frac 1M \sum^M_{i=1}(x_i-m_x)(x_i-m_x)^T =\frac 1M[\sum x_ix_i^T]-m_xm_x^T$
- 令 $F$ 和 $\lambda$ 为 $C_x$ 的特征向量和对应的特征值,可有关系: $|C_x-\lambda I|=0,\; C_xF=\lambda F$
- 特征向量 $F$ 为N维矢量,由上式可解出N个特征值$\lambda_1,\lambda_2,…,\lambda_n$,将其按降序排列, $\lambda_1>\lambda_2>\lambda_3>…>\lambda_n$
- 将各特征值分别代入,可得出对应各特征值的特征向量为:$F_i=[f_{i1},f_{i2},…,f_{in}]^T$
- 将各特征向量转置后即可构成变换矩阵: $\Phi = \begin{bmatrix} F_1^T \ F_2^T \ \vdots \ F_N^T \end{bmatrix} = \begin{bmatrix} f_{11} \; f_{12}\; \cdots \; f_{1N} \ f_{21} \; f_{22}\; \cdots \; f_{2N} \ \cdots \; \cdots \ f_{N1} \; f_{N2}\; \cdots \; f_{NN} \end{bmatrix}$
- K-L变换性质
- 去相关性:上述变换结果Y向量的各分量互不相关, 具有协方差矩阵为 $C_y=\Phi^TC_x\Phi=\begin{bmatrix} \lambda_1 & & & \ & \lambda_2 & & \ & & \ddots & \ & & & \lambda_n \end{bmatrix}$
- 最佳重构特性:对变换后结果进行截断后恢复原数据,其均方误差是最小的
- 假定取Y向量的前M个分量进行反变换恢复X向量,其均方误差为: $\varepsilon^2(m)=\sum^{N}_{i=M+1}\lambda_i$
- K-L变换的应用
- 图像目标旋转的应用:将图像的坐标作为随机向量的分量 X=[x, y]
- 多波段图像特征抽取应用:将图像的波段作为随机向量的分量 X=[b1,b2,…,bn]
- 图像数据压缩应用:将图像的波段或像素作为随机向量的分量 X=[p1,p2,…,pn]
哈尔变换 Haar transform
- 来源:
- 与沃尔什—哈达玛变换的构成方法相似,寻找其他可用的正交函数
- Haar函数于1910年提出,其矩阵只有+1,-1和另一个以$\sqrt2$为基础的系数。它是正交稀疏矩阵,可实现快速计算
- 哈尔函数具备完备性与归一化正交性
- 定义
- 利用哈尔函数作为基函数的对称、可分离酉变换,要求 $N=2^n$
- 令整数$o\le k \le N-1$由其他两个整数$p$和$q$唯一决定 $k=2^p+q-1$
- 哈尔函数定义为: $h_0=\frac 1N \quad h_k(x)=\frac 1N \left\lbrace \begin{matrix} 2^{p/2} & \frac{q-1}{2^p}\le x < \frac{q-0.5}{2^p} \ -2^{p/2} & \frac{q-0.5}{2^p}\le x < \frac{q}{2^p} \ 0 & else \end{matrix} \right.$
- 对于$i=0,1,…,N-1$,令$x=i/N$,则形成一组基函数,除$k=0$时为常数外,每个基函数均具有独特的一个矩形脉冲对
- 这些基函数在尺度(宽度)和位置上均有所变化,索引 $p$ 规定了尺度,$q$ 决定了平移量
- 哈尔变换的特性
- Haar函数的一个重要特性—收敛均匀而迅速
- 傅里叶变换的基函数仅是频率不同,哈尔函数在尺度和位置上都不同
- 哈尔变换具有尺度和位置的双重性
- 全域特性和区域特性:哈尔函数系列可分为全域部分和区域部分。全域部分作用于整个变换区间,区域部分作用于局部区域
- 小波特性:变换后子波的尺度远小于原始信号
小波变换
- 问题引入:
- 傅里叶变换可以准确地知道信号中含有哪些频率成分,但不知道这些成分发生的时间、位置
- 稳态信号特征
- 由一系列不随时间变化的频率组成
- 不需要知道任何频率的开始与停止时间
- 傅立叶变换基于在时间轴上无限伸展的正弦曲线波作为正交基函数,十分适于表现稳态信号
- 非稳态信号具有随时间变化的频率成分,分析中需要知道
- 什么频率在什么时候发生
- 特定频率发生的位置
- 傅里叶变换的局限性
- 时间信息损失:什么时候特定的事件发生?
- 位置信息的损失:傅里叶变换不能确定某一事件的漂移、趋势、突变、起始和结束等
- 傅里叶变换分析是全局性的分析,难以分析局部信号特征
- Gabor变换、加窗付里叶变换、短时傅里叶变换(STFT)
- 为了克服上述缺陷,使用有限宽度基函数的变换方法
- STFT变换步骤为:
- 选定一个有限窗口
- 将窗口放置于信号的起点
- 计算窗口内信号的傅里叶变换
- 将窗口向右移动一个距离
- 重复上两步步,直至达到信号的末尾
- 由此,得到每个时间段内信号的频率成分
- 特征:
- 实现了对于信号的频率与时间观察的折衷
- 无论时间还是频率的观察均为有限精度;整体精度取决于窗口尺寸
- 一旦窗口尺寸确定,将作用于所有频率
- 小波变换
- 可采用频率不同、位置不同、宽度有限的基函数进行变换
- 哈尔变换是最早出现的小波变换实例,其基向量均为一个函数通过不断的平移和伸缩来产生
- 小波是具有有限区间和均值为零的波
- 从傅里叶变换到小波变换:
- 傅里叶变换:意味着信号在所有时间区间与复指数相乘,结果产生傅里叶系数$F(ω)$。按照傅里叶系数,可将原信号分解为不同频率的组合
- 小波变换: 结果产生小波变换系数。按照小波系数,原始信号分解为不同小波的组合
- 连续小波变换
- 基本小波
- 基本小波是具有特殊性质的实值函数,它是震荡衰减的,而且通常衰减得很快,在数学上满足积分为零的条件: $\int^{\infty}_{-\infty} \psi(t)dt=0$
- 同时其频谱:$\Psi(\omega)=\int^{\infty}{-\infty} \psi(t)e^{-j\omega t}dt$ 满足条件: $C{\psi} = \int^{\infty}_{-\infty} \frac{|\Psi(\omega)|^2}{\omega}d\omega < \infty$
- 两个条件可概括为:小波应是一个具有振荡性和迅速衰减的波
- 小波基函数
- 通过对基本小波进行尺度上的伸缩和位置上的移动,可形成一系列小波函数 — 小波基函数
- 一组小波基函数是通过尺度因子和位移因子由基本小波来产生:$\psi_{a,b}(t)=\frac{1}{\sqrt a}\psi(\frac{t-b}{a})$
- a: 尺度系数(伸缩系数); b: 位移系数
- 连续小波变换定义(又称之为积分小波变换):
- $W_f(a,b) = \langle f,\psi_{a,b}(t)\rangle = \int^{\infty}{-\infty}f(t)\psi{a,b}(t)dt = \frac{1}{\sqrt a}\int^{\infty}_{-\infty}f(t)\psi(\frac{t-b}{a})dt$
- 连续小波变换的逆变换为: $f(t)=\frac{1}{C_\psi}\int^{\infty}{0}\int^{\infty}{-\infty} W_f(a,b)\psi_{a,b}(t)db\frac{da}{a^2}$
- $W(a,b)=\langle x(t),\psi(a,b) \rangle = \langle x(t),\psi_{a,0}(t-b) \rangle = R_{x,\psi_{a,0}}(b)$ (考虑内积函数和互相关函数得出)
- $W(a,b)$是信号$x(t)$与小波基本函数在尺度因子$a$和位移因子$b$时的互相关函数 (即当$a,b$固定时)
- 如果信号在特定的尺度因子$a$和位移因子$b$下与基本小波函数具有较大的相关性(相似性),则$W(a,b)$值将较大
- 若只固定尺度因子$a$, 由线性系统输入输出关系可得出:$W(a,b)=x(b)\psi^_{a,0}(-b)$
- 对于任意给定的尺度因子$a$(频率~ $1/a$),小波变换$W(a,b)$为输入信号作用于具有响应函数的滤波器输出;小波变换定义了一组由尺度因子 $a$ 规范的连续滤波器组
- 几种典型的一维小波: Mexican Hat; Wavelet; Haar Wavelet; Morlet Wavelet; Daubechies
- 基本小波
- 小波变换参数的深入分析
- 尺度(Scaling)
- 小波的“尺度”变化意味着对小波进行“拉伸”或“压缩”
- 某种程度上类似于频率:频率~$1/a$
- 尺度与频率
- 大尺度对应于“展开”的小波,小波展开越大,该小波表征的信号特征就越粗糙(平滑)
- 小尺度a:对应于压缩的小波;可表征更好的细节(变化): 高频率
- 大尺度a:对应于展开的小波;表征粗糙部分(慢变化):低频率
- 位移(Shifting)
- 延迟或加速小波
- 尺度(Scaling)
- 小波变换的基本性质
- 线性: 小波变换是线性变换, $f(t)=\alpha f_1(t)+\beta f_2(t), \; W_f(a,b)=\alpha W_{f_1}(a,b)+\beta W_{f_2}(a,b)$
- 平移和伸缩的共变性: $f(a_0t) \Leftrightarrow \frac{1}{\sqrt a}W_f(a_0a,a_0b)$
- 冗余性:连续小波变换中存在信息表述的冗余度
- 由连续小波变换恢复原信号的重构公式不唯一
- 小波变换的核函数存在许多可能的选择