炼数成金 门户 科学探索 数学 查看内容

小波变换

2017-4-11 22:21| 发布者: 炼数成金_小数| 查看: 8649| 评论: 0|来自: 算法与数学之美

摘要: 我希望能简单介绍一下小波变换,它和傅立叶变换的比较,以及它在移动平台做motion detection的应用。如果不做特殊说明,均以离散小波为例子。考虑到我以前看中文资料的痛苦程度,我会尽量用简单,但是直观的方式去介 ...

基础 计算机 数学 超级计算 科学探索

我希望能简单介绍一下小波变换,它和傅立叶变换的比较,以及它在移动平台做motion detection的应用。如果不做特殊说明,均以离散小波为例子。考虑到我以前看中文资料的痛苦程度,我会尽量用简单,但是直观的方式去介绍。有些必要的公式是不能少的,但我尽量少用公式,多用图。另外,我不是一个好的翻译者,所以对于某些实在翻译不清楚的术语,我就会直接用英语。我并不claim我会把整个小波变换讲清楚,这是不可能的事,我只能尽力去围绕要点展开,比如小波变换相对傅立叶变换的好处,这些好处的原因是什么,小波变换的几个根本性质是什么,背后的推导是什么。我希望达到的目的就是一个小波变换的初学者在看完这个系列之后,就能用matlab或者别的工具对信号做小波变换的基本分析并且知道这个分析大概是怎么回事。

要讲小波变换,我们必须了解傅立叶变换。要了解傅立叶变换,我们先要弄清楚什么是”变换“。很多处理,不管是压缩也好,滤波也好,图形处理也好,本质都是变换。变换的是什么东西呢?是基,也就是basis。如果你暂时有些遗忘了basis的定义,那么简单说,在线性代数里,basis是指空间里一系列线性独立的向量,而这个空间里的任何其他向量,都可以由这些个向量的线性组合来表示。那basis在变换里面啥用呢?比如说吧,傅立叶展开的本质,就是把一个空间中的信号用该空间的某个basis的线性组合表示出来,要这样表示的原因,是因为傅立叶变换的本质,是。小波变换自然也不例外的和basis有关了。再比如你用Photoshop去处理图像,里面的图像拉伸,反转,等等一系列操作,都是和basis的改变有关。

既然这些变换都是在搞基,那我们自然就容易想到,这个basis的选取非常重要,因为basis的特点决定了具体的计算过程。一个空间中可能有很多种形式的basis,什么样的basis比较好,很大程度上取决于这个basis服务于什么应用。比如如果我们希望选取有利于压缩的话,那么就希望这个basis能用其中很少的向量来较大程度地表示信号,这样即使把别的向量给砍了,信号也不会损失很多。而如果是图形处理中常见的线性变换,最省计算量的完美basis就是eigenvector basis了,因为此时变换矩阵T对它们的作用等同于对角矩阵( Tv_n = av_n,a是eigenvalue )。总的来说,抛开具体的应用不谈,所有的basis,我们都希望它们有一个共同的特点,那就是,容易计算,用最简单的方式呈现最多的信号特性。

好,现在我们对变换有了基本的认识,知道他们其实就是在搞基。当然,搞基也是分形式的,不同的变换,搞基的妙处各有不同。接下来先看看,傅立叶变换是在干嘛。

傅立叶级数最早是Joseph Fourier 这个人提出的,他发现,这个basis不仅仅存在与vector space,还存在于function space。这个function space本质上还是一个linear vector space,可以是有限的,可以是无限的,只不过在这个空间里,vector就是function了,而对应的标量就是实数或者复数。在vector space里,你有vector v可以写成vector basis的线性组合,那在function space里,function f(x)也可以写成对应function basis的线性组合,也有norm。你的vector basis可以是正交的,我的function basis也可以是正交的(比如sin(t)和sin(2t))。不同的是,我的function basis是无穷尽的,因为我的function space的维度是无穷的。好,具体来说,那就是现在我们有一个函数,f(x)。我们希望将它写成一些cos函数和一些sin函数的形式,像这样

我们知道函数内积是这样算的了,自然也就容易证明,按照这个形式去写的傅立叶展开,这些级数确实都是两两正交的。证明过程这里就不展开了。好,下一个问题就是,为什么它们是正交basis如此重要呢?这就牵涉到系数的求解了。我们研究了函数f,研究了级数,一堆三角函数和常数1,那系数呢?a0, a1, a2这些系数该怎么确定呢?好,比如我这里准备求a1了。我现在知道什么?信号f(x)是已知的,傅立叶级数是已知的,我们怎么求a1呢?很简单,把方程两端的所有部分都求和cosx的内积,即:

这样,a1就求解出来了。到这里,你就看出正交的奇妙性了吧:)

好,现在我们知道,傅立叶变换就是用一系列三角波来表示信号方程的展开,这个信号可以是连续的,可以是离散的。傅立叶所用的function basis是专门挑选的,是正交的,是利于计算coefficients的。但千万别误解为展开变换所用的basis都是正交的,这完全取决于具体的使用需求,比如泰勒展开的basis就只是简单的非正交多项式。

有了傅立叶变换的基础,接下来,我们就看看什么是小波变换。首先来说说什么是小波。所谓波,就是在时间域或者空间域的震荡方程,比如正弦波,就是一种波。什么是波分析?针对波的分析拉(囧)。并不是说小波分析才属于波分析,傅立叶分析也是波分析,因为正弦波也是一种波嘛。那什么是小波呢?这个”小“,是针对傅立叶波而言的。傅立叶所用的波是什么?正弦波,这玩意以有着无穷的能量,同样的幅度在整个无穷大区间里面振荡,像下面这样:

那小波是什么呢?是一种能量在时域非常集中的波。它的能量是有限的,而且集中在某一点附近。比如下面这样:

这种小波有什么好处呢?它对于分析瞬时时变信号非常有用。它有效的从信号中提取信息,通过伸缩和平移等运算功能对函数或信号进行多尺度细化分析,解决了傅立叶变换不能解决的许多困难问题。恩,以上就是通常情况下你能在国内网站上搜到的小波变换文章告诉你的。但为什么呢?这是我希望在这个系列文章中讲清楚的。不过在这篇文章里,我先点到为止,把小波变换的重要特性以及优点cover了,在下一篇文章中再具体推导这些特性。

小波变换的本质和傅立叶变换类似,也是用精心挑选的basis来表示信号方程。每个小波变换都会有一个mother wavelet,我们称之为母小波,同时还有一个scaling function,中文是尺度函数,也被成为父小波。任何小波变换的basis函数,其实就是对这个母小波和父小波缩放和平移后的集合。下面这附图就是某种小波的示意图:

从这里看出,这里的缩放倍数都是2的级数,平移的大小和当前其缩放的程度有关。这样的好处是,小波的basis函数既有高频又有低频,同时还覆盖了时域。对于这点,我们会在之后详细阐述。

小波展开的形式通常都是这样(注意,这个只是近似表达,严谨的展开形式请参考第二篇http://www.kunli.info/2011/01/27/fourier-wavele…otion-signal-2/):

3. 从信号算出展开系数a需要很方便。普遍情况下,小波变换的复杂度是O(Nlog(N)),和FFT相当。有不少很快的变换甚至可以达到O(N),也就是说,计算复杂度和信号长度是线性的关系。小波变换的等式定义,可以没有积分,没有微分,仅仅是乘法和加法即可以做到,和现代计算机的计算指令完全match。

可能看到这里,你会有点晕了。这些特性是怎么来的?为什么需要有这些特性?具体到实践中,它们到底是怎么给小波变换带来比别人更强的好处的?计算简单这个可能好理解,因为前面我们已经讲过正交特性了。那么二维变换呢?频域和时域定位是如何进行的呢?恩,我完全理解你的感受,因为当初我看别的文章,也是有这些问题,就是看不到答案。要说想完全理解小波变换的这些本质,需要详细的讲解,所以我就把它放到下一篇了。

接下来,上几张图,我们以一些基本的信号处理来呈现小波变换比傅立叶变换好的地方,我保证,你看了这个比较之后,大概能隐约感受到小波变换的强大,并对背后的原理充满期待:)

假设我们现在有这么一个信号:

看到了吧,这个信号就是一个直流信号。我们用傅立叶将其展开,会发现形式非常简单:只有一个级数系数不是0,其他所有级数系数都是0。好,我们再看接下来这个信号:

简单说,就是在前一个直流信号上,增加了一个突变。其实这个突变,在时域中看来很简单,前面还是很平滑的直流,后面也是很平滑的直流,就是中间有一个阶跃嘛。但是,如果我们再次让其傅立叶展开呢?所有的傅立叶级数都为非0了!为什么?因为傅立叶必须用三角波来展开信号,对于这种变换突然而剧烈的信号来讲,即使只有一小段变换,傅立叶也不得不用大量的三角波去拟合,就像这样:

看看上面这个图。学过基本的信号知识的朋友估计都能想到,这不就是Gibbs现象么?Exactly。用比较八股的说法来解释,Gibbs现象是由于展开式在间断点邻域不能均匀收敛所引起的,即使在N趋于无穷大时,这一现象也依然存在。其实通俗一点解释,就是当变化太sharp的时候,三角波fit不过来了,就凑合出Gibbs了:)

接下来我们来看看,如果用刚才举例中的那种小波,展开之后是这样的:

看见了么?只要小波basis不和这个信号变化重叠,它所对应的级数系数都为0!也就是说,假如我们就用这个三级小波对此信号展开,那么只有3个级数系数不为0 。你可以使用更复杂的小波,不管什么小波,大部分级数系数都会是0。原因?由于小波basis的特殊性,任何小波和常量函数的内积都趋近于0。换句话说,选小波的时候,就需要保证母小波在一个周期的积分趋近于0。正是这个有趣的性质,让小波变换的计算以及对信号的诠释比傅立叶变换更胜一筹!原因在于,小波变换允许更加较精确的局部描述以及信号特征的分离。一个傅立叶系数通常表示某个贯穿整个时间域的信号分量,因此,即使是临时的信号,其特征也被强扯到了整个时间周期去描述。而小波展开的系数则代表了对应分量它当下的自己,因此非常容易诠释。

小波变换的优势不仅仅在这里。事实上,对于傅立叶变换以及大部分的信号变换系统,他们的函数基都是固定的,那么变换后的结果只能按部就班被分析推导出来,没有任何灵活性,比如你如果决定使用傅立叶变换了,那basis function就是正弦波,你不管怎么scale,它都是正弦波,即使你举出余弦波,它还是移相后的正弦波。总之你就只能用正弦波,没有任何商量的余地。而对于小波变换来讲,基是变的,是可以根据信号来推导或者构建出来的,只要符合小波变换的性质和特点即可。也就是说,如果你有着比较特殊的信号需要处理,你甚至可以构建一个专门针对这种特殊信号的小波basis function集合对其进行分析。这种灵活性是任何别的变换都无法比拟的。总结来说,傅立叶变换适合周期性的,统计特性不随时间变化的信号; 而小波变换则适用于大部分信号,尤其是瞬时信号。它针对绝大部分信号的压缩,去噪,检测效果都特别好。

在上一篇中讲到,每个小波变换都会有一个mother wavelet,我们称之为母小波,同时还有一个father wavelet,就是scaling function。而该小波的basis函数其实就是对这个母小波和父小波缩放和平移形成的。缩放倍数都是2的级数,平移的大小和当前其缩放的程度有关。

还讲到,小波系统有很多种,不同的母小波,衍生的小波基就完全不同。小波展开的近似形式是这样:

另外,为了方便处理,父小波和母小波也需要是正交的。可以说,完整的小波展开就是由母小波和父小波共同定义的。

该信号长度为8,是离散的一维信号。我们要考虑的,就是如何用小波将其展开。为了方便讲解,我们考虑最简单的一种小波,哈尔小波。下面是它的一种母小波:

那如何构建基于这个母小波的基呢?刚才提到了,要缩放,要平移。我们先试试缩放,那就是ψ(2n):

但这样的话,它与自己的内积就不是1了,不符合小波基orthonormal的要求,所以我们要在前面加一个系数根号二,这样我们就得到了另一个哈尔小波的basis function:

这里的k是可以看成时域的参数,因为它控制着小波基时域的转移,而j是频域的参数,因为它决定了小波基的频率特性。看到这里,你应该会感觉很熟悉,因为这里的平移和变换本质和刚才对scaling function的平移变换是一模一样的。

这样,我们就有了针对此信号space的哈尔小波basis组合:

图1

可以看出,我们用到了三层频率尺度的小波函数,每往下一层,小波的数量都是上面一层的两倍。在图中,每一个小波基函数的表达形式都写在了波形的下面。

等等,你可能已经发现了,有问题。这里为什么多了个没有函数表达式的波形呢?这货明显不是wavelet function阿。没错,它是之前提到的scaling function,也就是父小波。然后你可能就会问,为啥这个凭空插了一个scaling function出来呢?明明目标信号已经可以用纯的小波基组合表示了。是,确实是,就算不包括scaling function,这些小波函数本身也组成了正交归一基,但如果仅限于此的话,小波变换也就没那么神奇的功效了。引入这个scaling function,才能引入我们提到的多解析度分析的理论,而小波变换的强大,就体现在这个多解析度上。那在这里,我们怎么用这个多解析度呢?这个哈尔小波basis组合是怎么通过多解析度推导出来的呢?

话说在数学定义中,有一种空间叫Lebesgue空间,对于信号处理非常重要,可以用L^p(R)表示,指的是由p次可积函数所组成的函数空间。我们在小波变换中要研究的信号都是属于L^2(R)空间的,这个空间是R上的所有处处平方可积的可测函数的集合,这样就等于对信号提出了一个限制,就是信号能量必须是有限的,否则它就不可积了。小波变换的定义都是基于但不限于L^2(R)中的信号的。这玩意的特性要具体解释起来太数学了,牵涉到太多泛函知识,我就不在这里详述了。而且老实说我也没能力完全讲清楚,毕竟不是学这个的,有兴趣可以参考wiki。总之你记住,小波变换研究中所使用的信号基本都是平方可积的信号,但其应用不限于这种信号,就行了。

对L^2(R)空间做MRA是在干嘛呢?就是说,在L^2(R)空间中,我们可以找出一个嵌套的空间序列,并有下列性质:

这个图是圈圈套圈圈,最里面的圈是V0,之后分别是V1,V2,V3,V4 。那他们有趣的性质就是,假如有一个函数f(t)他属于一个某空间,那你将其在时域上平移,它还是属于这个空间。但如果你对它频域的放大或缩小,它就会相应移到下一个或者上一个空间了。

同时我们还知道,你要形容每一个空间的话,都需要有对应的orthonormal basis,这是必然的,那对于V0来讲,它的orthonormal basis就是

当然,如果这个scaling function只是用来代表一个子空间的,那它的地位也就不会这么重要了。刚才我们提到,这个嵌套空间序列有一个性质,。这就是这个函数,如果你对它频域的放大或缩小,它就会相应移到下一个或者上一个空间了。这个性质就有意思了,它代表什么呢?对于任何一个包含V0的更上一层的空间来讲,他们的基都可以通过对scaling function做频域的scale后再做时域上的整数变换得到!推广开来就是说,当

到这里,我们就明白这些个子空间和那个凭空冒出来的scaling function的作用了。scaling的构建这些不同的子空间的基础,当j越大的时候,每一次你对频率变换后的scaling function所做的时域上的整数平移幅度会越小,这样在这个j子空间里面得到的f(t)表示粒度会很细,细节展现很多。反之亦然。通俗点说,就是对scaling function的变换平移给你不同的子空间,而不同的子空间给你不同的分辨率,这样你就可以用不同的分辨率去看目标信号。

好,稍微总结一下。到现在,已经讲了关于scaling function的基本理论知识,知道了信号空间可以分为不同精细度的子空间,这些子空间的basis集合就是scaling function或者频率变换之后的scaling function,如下图所示:

上图就是四个子空间的basis集合的展览。通过前面的讨论,我们还知道,一开始的scaling function可以通过更精细的子空间的scaling function(它们都是对应子空间的basis)来构建。比如

对于更加finer的scale:

图2
依此类推。实际上,对于任何scale和translate过的scaling function,都可以用更加精细的scale层面上的scaling function构建出来。

然后,我们有各种scale下的scaling function了,该看看它们分别所对应的嵌套的空间序列了。先看看V0,自然就是以基本的scaling function为基础去span出来的:

我们之前讲了一堆多解析度的理论,但直到现在,通过这些图形化的分析,我们可能才会真正理解它。那好,既然我们有一个现成的信号,那就来看看,对这个信号作多解析度分析是啥样子的:

你看,在不同的子空间,对于同一个信号就有不同的诠释。诠释较好的当然是V3,完全不损失细节。这就是多解析度的意义。我们可以有嵌套的,由scaling function演变的basis function集合,每一个集合都提供对原始信号的某种近似,解析度越高,近似越较精确。

说到这里,可能你对scaling function以及多解析度分析已经比较理解了。但是,我们还没有涉及到它们在小波变换中的具体应用,也就是还没有回答刚才那个问题:凭空插了一个scaling function到小波basis组合中干嘛。也就是说,我们希望理解scaling function是怎么和小波函数结合的呢,多解析度能给小波变换带来什么样的好处呢。这其实就是是小波变换中的核心知识。理解了这个,后面的小波变换就是纯数学计算了。

好,我们已经知道,对于子空间V0,basis是scaling function:

看出什么规律了么?多看几次这三个图,你会惊讶地发现,在V0中的scaling function和wavelet function的组合,其实就是V1中的basis!继续这样推导,V1本来的的basis是:

然后V1中对应的wavelet function是

他们的组合,本质上也就是V2的basis(参考图2)。你继续推导下去,会得到同样的结论:在scale j的wavelet function,可以被用来将Vj的basis扩展到V(j+1)中去!这是一个非常非常关键的性质,因为这代表着,对任何一个子空间Vj,我们现在有两种方法去得到它的orthonormal basis:

第二种选择能给我们带来额外的好处,那就是我们可以循环不断地用上一级子空间的scaling function以及wavelet function的组合来作为当前子空间的基。换句话说,如果针对V3这个子空间,它实际上就有四种不同的,但是等价的orthonormal basis:

1. 本级(V3)的scaling function basisset

2. 上一级(V2)的scaling function +wavelet function;

3 . 上上一级(V1)的scaling function + 上上一级(V1)的wavelet function + 上一级(V2)的wavelet function;

4. 上上上一级(V0)的scaling function + 上上上一级(V0)的wavelet function + 上上一级(V1)的wavelet function + 上一级(V2)的wavelet function

好,看看最后一种选取方式,有没有感到眼熟?对了,它就是我们之前提到的“针对此信号space的哈尔小波basis组合”,参见图1。现在我们知道了,这个scaling function不是凭空插进去的,而是通过不断的嵌套迭代出来的:)

那为什么我们最后选定的是这种选取方式呢?实际上,刚才介绍的这个性质已经告诉我们,对于任何的scale j0,我们都可以给我们的signal space找到一组orthonormal basis,这个basis是通过组合scale j0上的scaling function以及所有在scale j,j>=j0上的wavelets得到的。这样,基于这个orthonormal basis,所有信号空间中的信号都可以写成组成这个basis的functions的线性组合:

这,就是最终的,也是最核心的,小波变换形式。不管是信号压缩,滤波,还是别的方式处理,只要是用小波变换,都逃不出这个基础流程:

1. 选取合适的wavelet function和scaling function,从已有的信号中,反算出系数c和d。

2. 对系数做对应处理

3. 从处理后的系数中重新构建信号。

这里的系数处理是区别你的应用的重点。比如图像或者视频压缩,就希望选取能将能量聚集到很小一部分系数中的小波,然后抛弃那些能量很小的小波系数,只保留少数的这些大头系数,再反变换回去。这样的话,图像信号的能量并没有怎么丢失,图像体积却大大减小了。

还有一个没有解释的问题是,为什么要强调尺度函数和小波函数组成一个orthonormal basis呢?计算方便是一方面,还有一个原因是,如果他们满足这个性质,就满足瑞利能量定理,也就是说,信号的能量,可以完全用每个频域里面的展开部分的能量,也就是他们的展开系数表示:

左边这四个basis组成元素,也就是scaling functions,的系数,表征的是信号的local平均(想想它们和信号的内积形式),而右边的这四个basis组成元素,也就是wavelet functions,的系数则表征了在local平均中丢失的信号细节。得益于此,多解析度分析能够对信号在越来越宽的区域上取平均,等同于做低通滤波,而且,它还能保留因为平均而损失的信号细节,等同于做高通滤波!这样,我们终于可以解释了wavelet function和scaling function背后的物理意义了:wavelet function等同于对信号做高通滤波保留变化细节,而scaling function等同于对信号做低通滤波保留平滑的shape!

欢迎加入本站公开兴趣群
高性能计算群
兴趣范围包括:并行计算,GPU计算,CUDA,MPI,OpenMP等各种流行计算框架,超级计算机,超级计算在气象,军事,航空,汽车设计,科学探索,生物,医药等各个领域里的应用
QQ群:326600878
1

鲜花

握手

雷人

路过

鸡蛋

刚表态过的朋友 (1 人)

相关阅读

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2018-1-21 01:08 , Processed in 0.153687 second(s), 25 queries .