书城计算机网络智能计算方法概论
19100100000004

第4章 多尺度几何分析概述(1)

1807年,法国人Fourier提出任意一个周期为的函数都可以表示成一系列三角函数的代数和,到今天蓬勃发展的小波分析,科学家们的目的都是在对不同的函数空间提供一种直接的、简便的分析方式。换言之,就是寻求函数在某一特定空间下,在某种基下的最优逼近,而逼近的误差体现了用此基表示函数的“稀疏”程度或是分解系数的能量的集中程度。

对于Fourier分析而言,其思想是将函数表示为具有不同频率的谐波函数的线性叠加,也就是将函数用一簇三角基展开,将原函数在时域里的讨论转化为对这个叠加的权系数的讨论,即Fourier变换在频域里的研究。当然这种三角体系的展开方式的局限性导致了人们寻找其他的正交体系,从而产生了小波分析。小波分析的地位在数学界是独一无二的,它较精确的时频定位特性,成为处理非平稳信号的有利工具。数学上也证明了小波分析比Fourier分析更能“稀疏”地表示一段分段光滑或者有界变差函数,这是小波分析成功的一个关键原因。

但是,由于张量积小波只具有有限个方向数,它主要适合于表示一维奇异性的对象,当它在处理二维或者更高维奇异性的时候,就显得无能为力。因此,小波在表示这些函数时并不是最优的或者最“稀疏”的表示方法。

为了更好地处理高维奇异性,一类带有方向性的“稀疏”表示方法——多尺度几何分析应运而生了。它的产生符合人类视觉皮层对图像的有效表示的要求:局部性、方向性、多尺度性和各向异性(Anisotropy)。它的目的就是为具有面奇异或线奇异的高维函数找到最优或最“稀疏”的表示方法。目前,已有的多尺度几何分析方法包括:Candès和Donoho提出的脊波变换(Ridgelet Transform)(1998年)、单尺度脊波变换(Monoscale Ridgelet Transform)(1999年)和Curvelet变换(Curvelet Transform)(1999年)、Pennec和Mallat提出的Bandelet变换(2000年),以及Do和Vetterli提出的Contourlet变换(2002年)。另外一些多尺度分析方法如Donoho提出Wedgelet(1997年)和Beamlet(2000年)我们也将做简要的介绍。而关于Brushlet(1997年)、Directionlet(2006年)、Shearlet(2006年)的介绍请参见相应的文献。

接下来,我们将根据各自出现的时间先后顺序仔细讨论它们各自不同的逼近性能。

2.1奇异性分析

我们称无限次可导的函数是光滑的或没有奇异性的。若函数在某处有间断或某阶导数不连续,则称该函数在此处有奇异性。图像的奇异性或非正则结构通常包含了图像的本质信息。如图像亮度的不连续性表示景物中的边缘部分,这是认识图中最重要的部分。图像的奇异性是常见的,也是重要的,而在自然界中,光滑物体的边界往往体现为沿光滑曲线的奇异性,并不仅仅是点的奇异性。

在数学上,通常用Lipschitz指数刻化信号的奇异性大小。

定义2.1

(1)称函数在点为Lipschitz。

(2)称函数在区间上是一致Lipschitz的,如果存在与无关的常数使得式(2.1)对所有的成立。其中,可以是无限区间。

(3)满足在点是Lipschitz的所有的上界(可简单地理解为其中最大者)刻画了函数在该点的正则性,称为函数在点的Lipschitz指数。同样的,可定义函数在一个区间上的Lipschitz指数。

如果在点的Lipschitz指数小于1,则称函数在点是奇异的。若的Lipschitz指数满足,则称在点是次可微的,但其次导数在点是奇异的,它的Lipschitz指数为,我们也说描述了这个奇异性。

2.1.1Fourier和小波的逼近性能分析

有界变差函数是信号的一类重要例子,其非线性逼近的误差比线性逼近的误差要小得多。大多数一维信号,如连续可导的光滑信号和具有有限不连续点的不连续信号,都属于有界变差函数范畴。图像的全变差既依赖于它的变差幅度,也依赖于变化着的围线的长度。

有界变差函数为一大类不具有非正则纹理的图像提供了好的模型。

2.1.2非线性Fourier逼近

Fourier基是的一组标准正交基,可以分解为Fourier级数。

若函数不连续但具有有界变差时,Fourier基对函数的非线性逼近误为,即有级的衰减速度。

2.1.3非线性小波逼近

非线性逼近是由个具有最大幅值的小波系数构造得到的。

比较函数的级的Fourier非线性逼近误差可知,在不连续点之间的正则性越高,小波非线性逼近相对于Fourier非线性逼近的改进就越大。

我们给出一个具体的例子。假设单变量函数,并且除了在外连续。这是一个很简单的函数,我们将把它进行Fourier展开和小波展开。将当成圆周处理,通过计算我们将可以看到的Fourier系数绝对值大于的个数超过,当时。相比较,对于一个好的正交小波基,如Lemarie.Meyer周期小波基,其小波系数大于的个数在幅度上增长得很缓慢,只有,为任意正数。事实上,Fourier变换在奇异点处引起了扩散,而小波却在此处有着高度集中,所以我们说小波分析在表示间断性光滑函数的时候的确是优秀的,而Fourier分析却不是。

对于所有的有界变差函数,用小波变换所得到的误差衰减速率不能通过最佳样条逼近或规范正交基下的任何非线性逼近来改进。在这种意义下小波对有界变差函数的逼近是最佳的。

对于维对象,0维奇异性就一定是点奇异,一维奇异性就是曲线奇异,而维就是超表面奇异。不幸的是,小波的这种能力只能处理0维奇异性,也就是点奇异。当遇到高维奇异性:在图像中,虽然也可能存在点奇异性(如所谓的“胡椒盐”噪音),但更普遍更重要的是表现为一维奇异性,即物体的边缘,小波就无能为力了。

而多尺度几何分析的目的就是找到更好表现这种高维奇异性的分析方法,下面分别作出介绍。

2.2多尺度几何分析

2.2.1脊波变换(Ridgelet Transform)

脊波理论的基本框架是由E.J Candès在博士学位论文中建立,并与D.L.Donoho等在其后续工作中逐步拓展和完善的。脊波变换是一种非自适应的高维函数表示方法,对含直线奇异的多变量函数能够达到“最优”的逼近阶。脊波理论的提出在多尺度几何分析史上产生了深远的影响,具有不可估量的意义。

脊波变换的核心主要是经过Radon变换把线状奇异性变换成点状奇异性,小波变换能有效地处理在Radon域的点状奇异性。而它的本质就是通过对小波基函数添加一个表征方向的参数得到的,所以它不但和小波一样有局部时频分析的能力,而且还具有很强的方向选择和辨识的能力,可以非常有效地表示信号中具有方向性的奇异特征,这是小波变换所不能办到的。

1.连续脊波变换的定义

2.数字脊波的实现

在实际应用中,脊波变换的离散化及其算法实现的是一个具有挑战性的问题。由于脊波的径向性质,对连续公式直接离散实现时要在极坐标中进行插值,这样的变换结果或者是冗余的,或者不能完全重构。因此脊波变换的数字实现的优劣很大程度上取决于其中Radon变换数字实现的重构精度。为此,人们提出了各种各样的方法,大体上可分为在Fourier域利用投影切片定理的方法、多尺度方法和代数方法三类。

近似脊波变换是建立在所谓的“伪极坐标”网格基础上的,首先对的离散点列作二维FFT,并将得到的包含个点的频域点列作径向划分,然后估计各个径向直线方向上个数据点的值。在每个径向方向都有个节点,在对这个点列作一维IFFT,从而得到对应于图像域的个点列,对这些点列作均匀化插值和重组就得到一次Radon变换的结果。但其有两点不足:一方面在实现频率平面中直角坐标向极坐标变换的过程中引入误差是明显的。另一方面,它具有总数为4倍的数据冗余性。因此这种脊波变换不适合图像编码压缩。

于是,M.N.DD和M.Vetterli在参考文献中提出的另一种数字脊波实现方法,称为有限脊波变换(FRIT)。首先用有限Radon变换将一幅图像变换到FRAT域中,再对每一个投影序列进行离散小波变换(DWT)其中方向是固定的。这种方法可以同时做到可逆性与非冗余性,并且是完全重构的。但由于有限脊波变换是基于有限Radon变换构造的,有限Radon变换在表达直线时有“折叠”效应,因此有限脊波变换在几何上不是真实的。

2001年,Donoho和Flesia为了克服有限脊波变换的“折叠”效应,构造了一种数字脊波变换,它能用真实的脊函数进行分解和合成,并且具有精确重构和框架性质。这种脊波变换采用的Radon变换,称作Fast Slant Stack,先进行Fast Slant Stack运算,然后进行二维快速小波变换。这种构造使得离散物体(离散脊波、离散Radon变换、离散伪极坐标Fourier域)具有与连续脊波理论平行的内在联系(脊波、Radon变换、极坐标Fourier域)。

Donoho构造的脊波变换在几何上是真实的,即在此处Radon变换的确是沿直线积分的,从而避免了“折叠”效应。在创建系数矩阵时,它将一个的矩阵变换为的矩阵,因此冗余因子为4,这在一定程度上影响了运算的速度。这种脊波变换在实现上的缺点是正交脊波系数衰减速度相对慢。

3.脊波的逼近能力

定理2.4设是的函数,沿某一直线是不连续的,除此之外均为阶连续。

也就是说,逼近误差显示好像不存在间断,这个结果对任意阶光滑都是成立的。

这个方法的显着特点是我们不需要知道间断的位置。与此相似,一维小波变换也不需要先验地知道点奇异的位置。因而对于具有直线奇异的函数来说,脊波的表示是最优的。

4.小结与展望

从上面的分析我们可以看到,脊波在分析直线奇异的分段光滑的高维函数是优秀的,脊波已经成功地应用在数学中的函数逼近、信号检测、特征提取、目标识别以及图像恢复、图像去噪和图像增强等方面。在脊波分析的框架下,结合二进小波变换的局部脊波变换,用于检测直线的方法,应用于方向性较强的图像获得了良好的检测效果。但是必须看到对于自然物体而言,奇异的边界是曲线的,经过Radon变换后曲线仍然为曲线,而小波对曲线不具备“稀疏”表示的能力,因而脊波不能够处理曲线奇异的高维函数。另外,脊波的数字化实现仍然是一个有待进一步提高的问题:如何很好地解决冗余度和精度,如何提高运算速度,而这些正是制约着脊波走向广泛应用的主要因素。

2.2.2单尺度脊波变换(Monoscale Ridgelet Transform)

针对脊波变换不能处理曲线奇异的问题,Candès在文献中提出了单尺度脊波变换(Monoscale Ridgelets)的概念,也叫局部脊波变换(Local Ridgelet Transform)。其主要思想是利用剖分的方法,用直线逼近曲线。

设是定义在上的以三阶光滑曲线为奇异边界的函数,是的一个框架,以尺度为对作均匀分割,并记所有与相交的子区域的全体为,每个的边长为,其左下角处的点为,那么就是的框架。