稀疏图像表示和自然计算.ppt

1,稀疏图像表示和自然计算,焦李成西安电子科技大学智能信息处理研究所2006.8,2,报告内容,稀疏图像表示稀疏几何图像表示;稀疏几何表示域隐马模型;过完全稀疏表示.自然计算人工免疫系统;协同进化;粒子群优化.,3,第一部分：稀疏图像表示,4,小波分析的局限性,寻求客观事物的“稀疏”表示方法,一直是计算机视觉、数学、数据压缩等领域的专家学者致力于的研究目标.对于含“点奇异”的一维信号,小波能达到最优的非线性逼近阶.而在处理二维或者更高维含“线奇异”的信号时,由一维小波张成的高维小波基不能达到最优逼近阶.小波变换的不足使人们开始寻求更好的非线性逼近工具.,5,边缘在小波的各个尺度上扩散,6,稀疏几何表示,过去几年,在数学分析、计算机视觉、模式识别、统计分析等不同学科中,分别独立地发展着一种彼此极其相似的理论:多尺度几何分析.发展多尺度几何分析的目的是为了检测、表示、处理某些高维奇异性.对于二维图像,奇异性主要由边缘所刻画,因此主要的任务是处理边缘。目前,提出的多尺度几何分析方法主要有:Ridgelet、Curvelet、Bandelet、Contourlet等.,7,小波和稀疏几何方法在处理边缘上的差异,小波,稀疏几何表示,8,Ridgelet,脊波理论由Cands 在1998 年提出,是一种非自适应的高维函数表示方法.脊波变换对于具有直线奇异的多变量函数有良好的逼近性能,但是,对于含曲线奇异的多变量函数,其逼近性能只相当于小波变换.为了解决含曲线奇异的多变量函数的稀疏逼近问题,Cands提出了单尺度脊波变换.单尺度脊波对于具有曲线奇异的多变量函数的逼近性能比小波有明显的提高.,9,正交Ridgelet的图示,三维视图,俯视图,10,Curvelet,Curvelet变换由Cands和Donoho在1999 年提出,其由脊波理论衍生而来.单尺度脊波的基本尺度是固定的,而Curvelet变换则不然,其在所有可能的尺度上进行分解,实际上Curvelet变换是由一种特殊的滤波过程和多尺度脊波变换组合而成.Curvelet对于具有曲线奇异的多变量函数的逼近性能比单尺度脊波有明显的提高.,11,Contourlet,2002 年,Do和Vetterli提出了一种图像二维表示方法:Contourlet变换,也称塔型方向滤波器.Contourlet变换继承了Curvelet变换的各向异性尺度关系,因此,在一定意义上,可以认为是Curvelet变换的另一种实现方式.Contourlet变换的最终结果是用类似于线段的基结构来逼近原图像,这也是所以称之为Contourlet变换的原因.,12,小波基和Contourlet基,小波基,Contourlet基,13,Bandelet,2000年,Pennec和Mallat提出了Bandelet换.Bandelet变换是一种基于边缘的图像表示方法,能自适应地跟踪图像的几何正则方向.构造Bandelet 变换的中心思想是定义图像中的几何特征为矢量场,而不是看成普通的边缘的集合.矢量场表示了图像空间结构的灰度值变化的局部正则方向.Bandelet基并不是预先确定的,而是以优化最终的应用结果来自适应的选择具体的基的组成.,14,Bandelet中定义的矢量场,15,存在的问题和进一步研究的方向,自适应与非自适应方法：近几年中,对于高维奇异函数的的逼近问题,一些研究者有这样一种认识:相对于非自适应方法,自适应方法应该具有更好的逼近性能.然而，回想一维情况,小波变换对含点奇异的分段光滑函数的表示是最优的.但一维小波变换并不需要先验地知道点奇异的具体位置,小波基的构建并没有自适应于函数本身,即小波变换是一种非自适应的函数表示方法.图像的多尺度几何分析将以一种什么方式发展呢?最终为人们所广泛采用的方法是自适应的还是非自适应的呢?这些问题值得我们深思.,16,存在的问题和进一步研究的方向,自适应方法存在的问题：自适应的多尺度几何表示方法,实际上是边缘检测和图像表示方法的结合.比如,Bandelet变换根据图像边缘自适应地构造了一种局部弯曲小波变换.于是,问题的关键归结为怎样剖分图像,局部区域中如何“跟踪”奇异方向等.然而,在自然图像中,灰度值的突变并不总是对应着物体的边缘,一方面,衍射效应使得图像中物体的边缘可能并不明显地表现出灰度的突变;另一方面,许多时候图像的灰度值剧烈变化是由于纹理的变化而产生的.所有基于边缘的自适应方法需要解决的一个共同的问题,是如何确定图像中灰度值剧烈变化的区域对应的是物体边缘还是纹理的变化,实际上这是一个非常困难的问题.,17,存在的问题和进一步研究的方向,Curvelet变换存在的问题：Curvelet变换提出的初衷是为了对高维空间中含奇异曲线或者曲面的函数进行”稀疏”表示.而目前Curvelet变换的数字实现算法冗余度很高,因此实际的实现与提出Curvelet变换时的初衷产生了背离.Curvelet在频域定义,其空域的采样特性并不显而易见.对于高阶正则的奇异边缘,Curvelet变换不能达到最优的非线性逼近阶,而当奇异边缘是非正则的,其逼近性能甚至不如小波。,18,存在的问题和进一步研究的方向,Contourlet变换存在的问题：Contourlet变换是一种近似的Curvelet变换数字实现方式,走的却是一条与Curvelet变换截然相反的技术路线.Contourlet变换首先直接在数字域中定义,再将数字域和连续域联系起来,在连续域中讨论Contourlet变换的逼近性能.Contourlet变换具有比Curvelet变换少得多的冗余度,然而,对于Contourlet变换,其数学基础还有待进一步完善.,19,存在的问题和进一步研究的方向,图像模型：多尺度分析的结论都是基于自然图像的简化模型（如左图）,然而,真正的自然图像远比这个简化模型更复杂.对于更复杂的图像模型,如包含纹理的模型,我们怎么处理呢?还需建立怎样的多尺度几何表示方法呢?对这些问题的回答将推动之一领域的发展.,20,小波域隐马尔科夫模型,在基于子波的统计信号处理方法研究之初,许多学者都是将子波系数建模为高斯形式,但高斯模型的假设与子波变换的压缩特性相冲突.压缩特性意味着只有少量的系数包含信号的绝大部分能量,其余的系数对信号能量贡献很小.这一特性说明子波系数的概率密度分布比通常的高斯分布在零值位置更尖,并在分布的两端呈现明显拖尾的趋势.从理论上讲,完全建模所有子波系数的联合概率密度函数可以准确地刻画系数间的统计相关性,但实际应用时相当复杂,也难以估.,21,小波域隐马尔科夫模型,在实际应用时我们需要在上述两种假设之间做出合理的折衷,对系数之间关键的相关性做出准确的描述,同时忽略次要因素.子波域隐马尔科夫模型正是在这一想法的启发下应运而生的并开辟了多尺度变换域统计信号处理这一新的研究领域.子波域隐马尔科夫作为一种概率图模型,是子波域统计信号与图像处理的一种有效的工具.借助于概率图技术,这种模型可以有效地描述子波系数的各种统计相关性.到目前为止,众多学者提出了许多不同的变换域隐马尔科夫模型,并广泛地将这些模型应用于图像恢复和重建、图像分割、图像纹理分析与合成、图像检索、边缘检测、自动目标识别、贝叶斯图像分析和图像水印等领域.,22,稀疏几何表示域隐马模型,随着多尺度几何分析研究领域的发展,一些学者也在一些多尺度几何变换域比如Contourlet变换域建立了隐马尔科夫模型.然而，我们应该清醒地认识到:多尺度几何变换域隐马尔科夫模型的研究还处于起步阶段,很多基本的问题还有待认识清楚.如隐马尔科夫模型是不是理想的多尺度几何变换域统计模型？在多尺度几何域有没有更好的统计模型？相信这些问题的回答将大大推动该领域的发展。,23,过完全稀疏表示,过完全稀疏表示采用过完全函数系统代替传统的正交基函数。从过完全系统中找到具有最佳线性组合的m项原子来表示一个信号，被称作是过完全稀疏表示.过完全稀疏表示方法始于上世纪九十年代，1993年Mallat和Zhang首次提出了应用过完全函数系统对信号进行稀疏分解的思想,并引入了匹配追踪算法.,24,基函数选择算法,匹配追踪：匹配追踪是一个迭代的贪婪算法.在每一次迭代过程中，匹配追踪从字典里选择最能匹配信号结构的一个基函数来构建稀疏逼近.在统计学领域，匹配追踪被称作投影跟踪.基追踪：基追踪利用了1范数能促使小系数收缩的零的特点，将基函数选择问题转化成线性规划问题。,25,存在的问题和进一步研究的方向,要找到最好的M个基函数是一个组合优化问题,由于计算量的原因,穷举法是不可行的.但是,匹配追踪和基追踪只能获得该问题的近似解,因此一个公开的问题就是有没有更好的,计算上可行的原子选择算法,如何实现?各算法的收敛性理论问题的研究才刚刚开始,误差与逼近速率的关系仍是一个开放的问题.,26,自然计算为基函数选择,一方面，要找到最好的M个基函数是一个组合优化问题；另一方面自然计算（见报告的下半部分）方法为组合优化问题的求解提供了新的途径。这两点为自然计算方法应用到基函数选择提供了可能。基于自然计算的基函数选择方法能不能提供比匹配追踪和基追踪更好的性能？这有待我们进一步研究。,27,第二部分：自然计算,28,人工免疫系统,生物体是一个复杂的大系统,其信息处理功能是由时间和空间尺寸相异的三个子系统完成的,即:脑神经系统、免疫系统和内分泌系统.人工免疫系统是一种受生物免疫系统启发,模仿自然免疫系统功能的一种智能方法.人工智能对神经系统的借鉴和模拟的成果很丰富,已经有比较成熟的方法和模型以资利用,相比较而言,对免疫系统研究还处于初级阶段.,29,克隆选择过程的图示,30,人工免疫系统的研究内容,记忆学习：免疫系统的记忆作用是众所周知的,如患了一次麻疹后,第二次感染了同样的病毒也不致发病.这是因为在一次免疫响应后,如果同类抗原再刺激时,在短时间内,免疫系统会产生比上一次多得多的抗体,同时与该抗原的亲和力也提高了.免疫遗忘：近年来的研究初步阐明，机体对多样性外来抗原的选择识别能力来源于机体在免疫系统发育分化过程中对淋巴细胞的选择和删除，通过基因重排产生多种多样的T细胞和B细胞克隆。如果不严格地区分B细胞和抗体，可以认为在免疫反应过程中，抗体可能是扩生、无反应或者消亡。,31,人工免疫系统的研究内容,多样性遗传机理：在免疫系统中,抗体的种类要远大于已知抗原的种类.其主要原因可能是受基因片段多样性的联接以及重链和轻链配对时等复杂机制所控制.该机理可以用于搜索的优化,从而提高全局搜索能力,避免陷入局部最优.克隆选择机理：细胞的无性繁殖称为克隆.有机体内免疫细胞的多样性能达到这种程度,以至于当每一种抗原侵入机体都能在机体内选择出能识别和消灭相应抗原的免疫细胞克隆,使之激活、分化和增殖,进行免疫应答以最终清除抗原,这就是克隆选择.但是,克隆中父代与子代间只有信息的简单复制,而没有不同信息的交流,无法促使进化.因此,需要对克隆后的子代进行进一步处理.,32,遗传算法和克隆选择算法,找到了一个局部最优,找到了多个局部最优包括全局最优,33,人工免疫系统存在的问题,由于对人工免疫系统的研究还处于起步阶段且免疫机理复杂,系统庞大,甚至连免疫学家对免疫现象的认识和描述都比较困难,人工免疫系统可以借鉴的成果不多,人工免疫系统不论在模型建立,算法等方面都存在一定的问题.Gasper、Dasgupta等研究者认为人工免疫系统现在没有统一的基本框架,难以象人工神经网络那样用线性或非线性模型来对免疫机理进行抽象描述.就免疫系统机理本身来讲,也存在缺憾.为了构造防御系统,获得初始抗体,需要进行大量计算.,34,人工免疫系统值得研究的方向,进一步研究免疫系统的各种计算机理:只有对免疫机理有了深入认识,才能为算法构造提供保障;而且,新机理的发现必将催化新算法的产生.改进已有的人工免疫系统模型:如前所述,现有的人工免疫系统模型还比较简单,不能满足人工智能应用的需要,具体地讲,就是利用模型深入理解算法的执行过程,分析算法的收敛性,计算量,为算法的评价和改进提供依据.,35,人工免疫系统值得研究的方向,为人工免疫系统开辟新的应用领域:与其他人工智能方法一样,应用是方法研究的价值体现,是检验算法优劣的标准.人工免疫系统在短短10年间获得了广泛的应用,但是在工程应用中,还没有取得和其他智能算法(如模糊逻辑、神经网络)一样的地位.基于人工免疫系统的智能整合集成方法研究:免疫系统的机理可以被用于改进现有的方法,免疫-进化、免疫-神经网络等已经被提出,并有成功的应用.在这一交叉整合过程中诞生的新思想,正把人工免疫系统的能力扩展到能应付越来越复杂的问题,人工免疫系统也正以全新的方式对人工智能等学科作出贡献.,36,协同进化论,达尔文进化论过分强调生存斗争,而忽略了生物其它方面的种种联系,具有片面性.达尔文把繁殖过剩所引起的生存斗争看做生物进化的主要动力也不是很恰当.其实,即使没有繁殖过剩,物种也会变异,变异的原因是多种多样的。近30年来,生物学上兴起了另一个重要理论,就是生物多样性和协同进化论.该理论已成为生态学的基础理论.应用生物多样性协同进化理论研究生物进化和环境保护,要比达尔文以生存斗争为中心的进化论更有效.,37,传统进化算法的不足,虽然进化算法较传统的方法具有巨大的优势，但也存在一些不足之处.适应度函数是预定义好的，而真正的适应度应该是局部的，是个体和环境作生存斗争时自然形成的而且随着环境变化而变化的。进化算法只考虑了生物之间的竞争，而没有考虑生物之间协作的可能性，实际的情况应该是竞争和协作共存，这就是协同进化,38,协同进化算法,协同进化算法是近十几年来在协同进化论基础上提出的一类新的进化算法.协同进化算法考虑了种群与环境之间,种群与种群之间在进化过程中的协调。虽然在这方面的研究起步较晚,但由于协同进化算法的优越性,越来越多的学者对此进行了研究,目前协同进化算法已成为自然计算法领域一个活跃的研究分支。,39,协同进化算法的研究内容,基于种间竞争机制的协同进化算法：这类算法由几个种群组成,这几个种群处于竞争关系,但同时又存在合作行为.种群间通过个体的迁移来达到信息交流的目的.基于捕食-猎物机制的协同进化算法：捕食-猎物关系是一种遭受选择压力个体间的一种反馈机制,这种反馈机制为系统走向复杂提供了有力的驱动.猎物为了不被猎食,通过发展某些手段更好保护自己,但同时导致捕食者发展更好的袭击策略.,40,协同进化算法的研究内容,基于共生机制的协同进化算法：这类算法把问题分解为几个问题,每个子问题对应一个种群,每个种群用一个进化算法进化.面对一个待解问题,每个进化个体只对应问题的部分解,由不同种群个体构成的一个共生体对应问题的一个完整解.基于病毒进化理论的协同进化算法：根据病毒进化理论,病毒具有一种特有的感染功能,它能获得一个个体的染色基因,并且感染给另一个个体,使得该个体的部分染色体基因发生相应的变化,从而改变该个体的遗传信息.,41,粒子群优化,Reynolds对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居,但最终的整体结果是整个鸟群好像在一个中心的控制之下,即复杂的全局行为是由简单规则的相互作用引起的.粒子群优化源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域.粒子群优化算法从鸟群模型中得到启示而产生,并用于解决优化问题.,42,鸟群的启示,43,粒子群优化,粒子群优化求解优化问题时,问题的解对应于搜索空间中一只鸟的位置,称这些鸟为“粒子”(particle).每个粒子都有自己的位置和速度,还有一个由被优化函数决定的适应值.每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解.粒子群优化的优势在于算法的简洁性,易于实现,没有很多参数需要调整,且不需要梯度信息.目前已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域.,44,存在的问题和进一步研究的方向,虽然粒子群优化在实际应用中被证明是有效的,但缺乏收敛速度估计等方面的理论.虽有一些研究者对此做了一些研究,但还不够深入.利用问题的先验知识设计出相应的算法是非常有意义的工作.因此当前针对具体应用问题深化研究粒子群优化算法是有意义的工作.结合其他技术来缓解虽然粒子群优化易陷入局部最优的问题也是一个值得研究的方向.,45,谢谢！,