P某的备忘录

传统方法下的图像处理数学原理整理 (2)

传统方法下的图像处理数学原理整理 (2)

封面图片 credit: From Digital Image Processing 4E, Global Edition

继承上一篇文章,本篇文章中继续会继续数理传统图像处理方法中的数学原理。这些方法比起上一篇更加复杂。

Karhunen-Loeve 变换

按照惯例(什么时候来的惯例啊?),本P先上这玩意的定义:

K-L转换(Karhunen-Loève Transform)是建立在统计特性基础上的一种转换,它是均方差(MSE, Mean Square Error)意义下的最佳转换,因此在资料压缩技术中占有重要的地位。K-L转换是对输入的向量x,做一个正交变换,使得输出的向量得以去除数据的相关性。然而,K-L转换虽然具有均方差(MSE)意义下的最佳转换,但必须事先知道输入的讯号,并且需经过一些繁杂的数学运算,例如协方差(covariance)以及特征向量(eigenvector)的计算。因此在工程实践上K-L转换并没有被广泛的应用,不过K-L转换是理论上最佳的方法,所以在寻找一些不是最佳、但比较好实现的一些转换方法时,K-L转换能够提供这些转换性能的评价标准。以处理图片为范例,在K-L转换途中,图片的能量会变得集中,有助于压缩图片,但是实际上,KL转算为input-dependent,即需要对每张输入图片存下一个转换机制,每张图都不一样,这在实际应用上是不实际的。

——来自 Wikipedia

Karhunen-Loeve 变换的目的是寻找任意统计分布的数据集合主要分量子集。基向量满足相互正交性。使得原始数据集合变换到主分量空间,使单一数据样本的互相关性(cross-correlation)降低到最低点

这玩意倒是在处理多光谱图像用的比较多,于是本P举个例子:
对某nn个 band 的多光谱图像做 Karhunen-Loeve 变换,即是对该多光谱图像组成的光谱空间XRC\mathbf{X}\in \mathbb{R}^{C}乘以一个线性变换矩阵ARC×C\mathbf{A\in \mathbb{R}^{ C\times C}},产生一个新的光谱空间YRC\mathbf{Y}\in \mathbb{R}^{C},即产生一幅新的nn个 band 的多光谱图像。其表达式为

Y=AX\mathbf{Y} = \mathbf{AX}

式中:X\mathbf{X}为变换前多光谱空间的像元矢量;Y\mathbf{Y}为变换后多光谱空间的像元矢量;A\mathbf{A}为一个n×nn\times n的线性变换矩阵。

对于变换中的矩阵A\mathbf{A},必须满足以下要求:

  • A\mathbf{A}n×nn\times n 正交矩阵,A=[ϕ1,ϕ2,ϕ3,,ϕn]\mathrm{A}=[\phi_1, \phi_2, \phi_3,\ldots,\phi_n]
  • 正交矩阵 A\mathbf{A}来说,取ϕi\phi_iX\mathbf{X}的协方差矩阵Σx\Sigma x的特征向量,协方差矩阵除对角线以外的元素都是零。
  • 变换后的向量Y\mathbf{Y}中各分量均不相关。亦即矩阵为非 Hermitian 矩阵,也就是矩阵复共轭对称。

讲到这里,增补协方差矩阵:


讲协方差矩阵,先要涉及协方差。其实协方差这个概念在概率论中已经涉及过,亦即:

期望值分别为E(X)=μE(X)=\muE(Y)=νE(Y)=\nu的两个具有有限二阶矩的实数随机变量XXYY之间的协方差定义为:

cov(X,Y)=E((Xμ)(Yν))=E(XY)μν \operatorname {cov} (X,Y)=\operatorname {E} ((X-\mu )(Y-\nu ))=\operatorname {E} (X\cdot Y)-\mu \nu

那么,对应协方差矩阵定义如下:
假设XX是以nn个随机变量组成的列向量,

X=[X1X2Xn]\mathbf{X}=\left[\begin{array}{c} X_{1} \\ X_{2} \\ \vdots \\ X_{n} \end{array}\right]

并且μi\mu_iXiX_{i}的期望值,即, μi=E(Xi)\mu_i = \mathrm{E}(X_i)。协方差矩阵的第(i,j)(i,j)项(第(i,j)(i,j)项是一个协方差)被定义为如下形式:

Σij=cov(Xi,Xj)=E[(Xiμi)(Xjμj)T] \Sigma _{ij}=\mathrm {cov} (X_{i},X_{j})=\mathrm {E} {\begin{bmatrix}(X_{i}-\mu _{i})(X_{j}-\mu _{j})^{\rm {T}}\end{bmatrix}}

而协方差矩阵为:

Σ=E[(XE[X])(XE[X])T]=[E[(X1μ1)(X1μ1)]E[(X1μ1)(X2μ2)]E[(X1μ1)(Xnμn)]E[(X2μ2)(X1μ1)]E[(X2μ2)(X2μ2)]E[(X2μ2)(Xnμn)]E[(Xnμn)(X1μ1)]E[(Xnμn)(X2μ2)]E[(Xnμn)(Xnμn)]]{\Sigma =\mathrm {E} \left[\left(\mathbf {X} -\mathrm {E} [\mathbf {X} ]\right)\left(\mathbf {X} -\mathrm {E} [\mathbf {X} ]\right)^{\rm {T}}\right]} {={\begin{bmatrix}\mathrm {E} [(X_{1}-\mu _{1})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{1}-\mu _{1})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{1}-\mu _{1})(X_{n}-\mu _{n})]\\\\\mathrm {E} [(X_{2}-\mu _{2})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{2}-\mu _{2})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{2}-\mu _{2})(X_{n}-\mu _{n})]\\\\\vdots &\vdots &\ddots &\vdots \\\\\mathrm {E} [(X_{n}-\mu _{n})(X_{1}-\mu _{1})]&\mathrm {E} [(X_{n}-\mu _{n})(X_{2}-\mu _{2})]&\cdots &\mathrm {E} [(X_{n}-\mu _{n})(X_{n}-\mu _{n})]\end{bmatrix}}}

矩阵中的第(i,j)(i,j)个元素是XiX_{i}XjX_j的协方差。这个概念是对于标量随机变量方差的一般化推广。
——来自 Wikipedia


所以说,变换矩阵A\mathrm{A}有:

A=(Φ11Φ12Φ1nΦ21Φ22Φ2nΦn1Φn2Φnn)A=\left(\begin{array}{cccc} \Phi_{11} & \Phi_{12} & \ldots & \Phi_{1 n} \\ \Phi_{21} & \Phi_{22} & \ldots & \Phi_{2 n} \\ \cdots & \cdots & \cdots & \cdots \\ \Phi_{n 1} & \Phi_{n 2} & \ldots & \Phi_{n n} \end{array}\right)

n=3n=3为例(也就是普通的RGB图)有:

y1=Φ11x1+ϕ12x2+ϕ13x3y2=ϕ21x1+ϕ22x2+ϕ23x3y3=ϕ31x1+ϕ32x2+ϕ33x3\begin{array}{l} {y}_{1}=\Phi_{11} {x}_{1}+\phi_{12}{x}_{2}+\phi_{13} x_{3} \\ {y}_{2}=\phi_{21} {x}_{1}+\phi_{22}{x}_{2}+\phi_{23} x_{3} \\ {y}_{3}=\phi_{31} {x}_{1}+\phi_{32}{x}_{2}+\phi_{33} x_{3} \end{array}

从上式可以看出,A\mathrm{A}的作用实际上对各分量加一个权重系数,实现线性变换。Y\mathrm{Y}的各分量的信息的线性组合,它综合了原有各分量的信息而不是简单的取舍,这使得新的nn维随机向量Y\mathrm{Y}能够较好的反映事物的本质特征。(本P发现好像什么东西扯上加权都可以这么讲((((

Y=AX\mathbf{Y} = \mathbf{AX}知,显然逆变换有:

X=ATY\mathbf{X} = \mathbf{A^{T} Y}

说回正题,在图像变换上,为了得到矢量\mathbf{X},可以将图像或子图像的像素按行行相接列列相接的次序排列。(震 撼 本 P(就硬降维啊喂!

在建立了矢量信号之后,就要计算协方差矩阵,然后就得到了变换后的矩阵Y\mathbf{Y}

以上,我们总结出 Karhunen-Loeve 变换的性质:

  • Y\mathrm{Y}均值向量零向量。即:EY=0\operatorname{E}{Y} =0
  • Karhunen-Loeve 变换使矢量信号各分量不相关,即变换域信号的协方差为对角矩阵:Σy=(λ1000λ2000λn)\Sigma_{y}=\left(\begin{array}{cccc}\lambda_{1} & 0 & \ldots & 0 \\ 0 & \lambda_{2} & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & \lambda_{\mathrm{n}}\end{array}\right)
  • Karhunen-Loeve 变换是在均方误差准则下失真最小的一种变换,故又称作最佳变换。

由此可见,尽管K-L变换具有最佳去相关和误差性能,但是由于求解特征值和特征根并非易事,特别是在维数高时甚至可能求不出来,而且变换矩阵与图像的内容有关,因而难以满足实时处理的要求。但是,K-L变换在变换编码中具有理论指导意义,人们通过比较,寻找出一些性能与K-L变换接近,但实现却容易得多的“准最佳”编码方法。

照例,给出matlab实例: AWSL好复杂编不出来(((

小波变换与多分辨率分析理论 (Wavelet Transform and Multiresolution Analysis theory)

首先祭出定义:

小波分析(英语:wavelet analysis)或小波转换(英语:wavelet transform)是指用有限长或快速衰减的“母小波”(mother wavelet)的振荡波形来表示信号。该波形被缩放和平移以匹配输入的信号。
小波变化的发展,承袭Gabor transform的局部化思想,并且克服了傅立叶和Gabor transform的部分缺陷,小波变换提供了一个可以调制的时频窗口,窗口的宽度(width)随着频率变化,频率增高时,时间窗口的宽度就会变窄,以提高清晰度.小波在整个时间范围内的幅度平均值为0,具有有限的持续时间和突变的频率与震幅,可以是不规则,或不对称的信号。
小波变换分成两个大类:离散小波变换(DWT) 和连续小波转换(CWT)。两者的主要区别在于,连续变换在所有可能的缩放和平移上操作,而离散变换采用所有缩放和平移值的特定子集。

多分辨率分析(multiresolution analysis, MRA)或是多尺度近似(multiscale approximation, MSA)是最常用来分析离散小波变换〈DWT〉或是验证快速小波转换〈FWT〉理论的方法。本分析方法在1989年及1998年由Stephane Mallat 著作的论文提到。

——来自 Wikipedia

所谓的小波的小是针对傅里叶波而言,傅里叶波指的是在时域空间无穷震荡的正弦或余弦波。
“小波”(wavelet)是一种「尺度很小」的波动,并具有时间和频率特性。
小波函数必须满足以下两个条件:

  • 小波必须是振荡的;
  • 小波是能量在时域非常集中的波,它的能量有限,都集中在某一点附近,即振幅只能在一个很短的一段区间上非0,即是局部化的,且积分的值为零。如下图所示:
    上图为 Morlet 小波,来源于 Wikipedia

讲了这么多,为啥要用看上去这么复杂的玩意呢,这就说来话长了。

本来 DFT 用着挺方便的,但用着用着 DFT 就出现了问题,观察下列三组信号及其 DFT:


可以发现,DFT 后的三组信号的主要频率都集中在了四个频率上,而原信号却大相径庭。因此人们需要一种新的可以准确描述信号特征的变换。

为了解决这个问题,人们尝试过 STFT (Short-time Fourier Transform),也就是加窗口分别作傅里叶变换,如下图:

这个信号在每个红框框内分别做傅立叶变换,就能知道在每一个变换时间段内的频域分布,但问题很明显:这个红框要如何选取?取宽了,又会变成原来的那种问题;取窄了,描述的信息又不够。这种时候有人提出了把这个「框框」自适应变化的算法,这就是小波变换。

为了尽可能的把小波变换体系讲清楚,我们需要结合 MRA 背景进行说明。


在给出离散小波变换式子之前,我们首先给出连续小波变换(CWT)的式子(为了说明简便,给出一维表达式):

W(a,τ)=<x(t),ψa,τ(t)>=1aRx(t)ψ(tτa)dtW(a, \tau)=<x(t), \psi_{a, \tau}(t)>=\frac{1}{\sqrt{a}} \int_{R} x(t) \psi\left(\frac{t-\tau}{a}\right) d t

其实看上去和CFT也没什么大区别,为了确保小波作为「基函数」的性质,在前面乘上了一个带根号的归一化系数。值得一提的是,积分符号内除去对时间变量tt积分,还留下了两个参量τ\tauaa。这两个符号对微积分熟悉的人一眼可以看出来是平移参数和缩放参数。那么,为什么要这么做呢?

平移实际上还比较好解释,就和卷积一样,只不过这里的函数变成了小波函数在原函数上滑动。

其步骤如下:

  • 小波ψ(t)\psi (t)和原始信号x(t)x(t)的开始部分进行比较。
  • 计算系数WW—该部分信号与小波的近似程度;WW值越高表示信号与小波相似程度越高。
  • 小波右移τ\tau得到的小波函数为ψ(tτ)\psi(t-\tau) ,然后重复步骤1和2,直到信号结束。
  • 扩展小波,如扩展一倍,得到的小波函数为ψ (t/2)。
  • 重复步骤1~4。

这其中缩放多少,重复几次呢?由程序编写者来定。

换言之,就是不同 scale 的小波在原函数上滚一圈,出来的各个结果能够在时间-频域-响应系数空间内表示。


进入离散部分,上面说到aaτ\tau都没定的情况下,CWT可以作连续的、多尺度的移动,也就是那两个参数可以在任意小的范围内移动。不难想象,当精度相当高的时候,其计算量是惊人的。为此,推出离散小波变换(DWT)。

给出离散小波变换的式子(同样地,为了说明简便,给出一维表达式):

Wx(j,k)=Rx(t)ψj,k(t)dtW_{x}(j, k)=\int_{R} x(t) {\psi_{j, k}(t)} d t

其中,

ψj,k(t)=12jψ(t2jk)\psi_{j, k}(t)=\frac{1}{\sqrt{2^{j}}} \psi\left(\frac{t}{2^{j}}-k\right)

式子都差不多,只不过那两个参数用了2的幂指数表示。使用这样的缩放因子和平移参数的小波变换叫做双尺度离散小波变换。需要强调的是,此处的「离散」指的是针对缩放因子平移参数离散化,与时间参量无关。

剩下大片的数学推导看这里,本P要复习其他科目所以目前是写不完了(x


转了这么一大圈,倒数第二步之时,我们比较一下傅立叶变换和小波变换吧:

  • 傅里叶变换:基础函数是正弦或余弦函数。反映的是图像的整体特征, 其频域分析具有很好的局部性,但空间(时间)域没有局部化功能。傅立叶变换是将信号完全的放在频率域中分析,但无法给出信号在每一个时间点的变化情况,并且对时间轴上任何点的突变都会影响整个频率的信号(想想看方波信号DFT后对应的 sinc\operatorname{sinc} 函数吧,时域上那个跳变要用多少正弦函数去拟合啊)。
  • 小波变换:基函数是小波,具有变化的频率有限的持续时间。是空间(时间)和频率的局部变换,它通过伸缩平移运算对信号逐步进行多尺度细化,最终达到高频处时间细分,低频处频率细分,能自动适应时频信号分析的要求,从而可聚焦到信号的任意细节。是多分辨率理论(就是大名鼎鼎的 MRA 喔)的分析基础。

最后,按照惯例,给出应用实例代码。也给不出来AWSL((

嘛……主要是时间不够用……看看之后有什么时间把这个坑填上吧……

Powered by Gridea. CopyRight 2018-2020 MrPeterJin's Media Dept.