图像处理某些发展动态和问题

图像处理：某些发展动态和问题邹谋炎[e-mail]82625719-8018中国科学院研究生院2011年暑期讲座材料2011年7月6日StephaneMallat：“AwaveletTourofSignalProcessing----TheSparseWay”,ThirdEd.,Elsevier,2009.一、从一本书谈起：StephaneMallatisProfessorinAppliedMathematicsatEcolePolytechnique,Paris,France.From1986to1996hewasaProfessorattheCourantInstituteofMathematicalSciencesatNewYorkUniversity,andbetween2001and2007,heco-foundedandbecameCEOofanimageprocessingsemiconductorcompany.S.Mallat书的第二版（1998）中译本“信号处理的小波引导”已于2002年由机械工业出版社出版“PrefacetotheSparseEditionIcannothelpbutfindstrikingresemblancesbetweenscientificcommunitiesandschoolsoffish.Weinteractinconferencesandthrougharticles,andwemovetogetherwhileaglobaltrajectoryemergesfromindividualcontributions.Someofusliketobeatthecenteroftheschool,othersprefertowanderaround,andafewswiminmultipledirectionsinfront.Toavoiddyingbystarvationinaprogressivelynarrowerandspecializeddomain,ascientificcommunityneedsalsotomoveon.……….”学习和理解一个成功数学教授的心路历程：将应用作为数学研究的归宿我不禁发现科学界和鱼群之间惊人的相似之处。我们在会议和通过文章相互接触，有人抛出一个贡献时就会出现一个全局性的轨迹，大家往一起凑。我们当中有人喜欢处于鱼群的中心，有人喜欢在周围游荡，也有人在前面朝多个方向游动。在一个越来越狭窄和专门的领域内为了不被饿死，科学界也需要往前凑。计算调和分析仍然非常活跃，因为它超出了小波的范畴。写本书的目的是为了解译群体的轨迹并把一路上发现的珍珠收集起来。小波不再是中心题目。它只是一个重要工具，如同富氏变换那样。稀疏表示和处理当前处于核心位置。在80年代，许多研究人员集中关注建立时频分解，试图绕开不定性屏障，期望找出最终的表示方法。沿着构造小波正交基的路子，通过与物理学家和数学家的合作，开辟了新的前景。设计X-let相关的正交基变成了一种流行运动，连带着压缩和噪声抑制应用。近似和稀疏性的联系也变得更加明显。对稀疏性的研究已正当时，引导出新的基地：标准正交基被波形冗余词典所替代。在过去7年间我与工业界相遇。带着许多天真，和几个人共建了一个小公司。这让我们花了一点时间去学习到：在3个月内一个良好的工程应该生产出稳健的算法可以实时运算；与此对照，在过去我们习惯于用3年的时间来写那些有发展前景的新思想。是的，我们还活着，因为数学是信号处理工业创新的一个主要源泉。半导体技术提供了惊人的计算能力和灵活性。但是，特定算法常常不易估量，并且数学能够加速凑试发展过程。稀疏性使计算、存贮和数据搬运得以下降。虽然数学理解非常漂亮，但绝不奢侈。它是越来越精妙的信息处理元件所需要的。S.Mallat书序言简译：FromWaveletToX-let：waveletcontourletsurfaceletshearletridgeletcurveletbandlet……关于X-let的解读：这些X-let关心信号和图像的表示，特别关心如何表达信号（图像）的不连续性（或奇异性），包括点（灰度）不连续性（wavelet）；线不连续性（ridgelet)；曲线不连续性(contourlet,surfacelet,Curvelet)；流场不连续性（bandlet）；等等理论要点：沿袭wavelet的理论模式，构造出表达信号或图像的“基”或“标架”，具有以下要求(1)有几何规则性，能够逼近图像中任意方向的线、曲线的不连续性；（2）有容易计算的分析（正变换）和综合（反变换）表达；（3）对分析（变换）域的结果有明确的物理解释，便于实施去噪、压缩的近似处理，以及超分辨重建的进一步工作。1、由可缩放的Meyer窗函数V(t)和W(r)来定义。例：CurveletbyE.Candès,D.Donoho(2003,2004)1001201-1-2201V(t)W(r)2、由V(t)和W(r)定义极坐标窗函数：aVarWarUa)(:),(433、将Ua内插为直角坐标函数Ua(ξ),作为基础curvelet小波函数的富氏变换)(:)(ˆ0,0,aaU4、由的富氏反变换，对空间双坐标x作旋转和位移变换，得到curvelet函数族：)(ˆ0,0,a)(0,0,xa))(()(bxxθa,0,0θb,a,R这保证了在频域(ξ1,ξ2)平面有扇形支持域。)(ˆ0,0,a例：CurveletbyE.Candès,D.Donoho(2003,2004)（续）5、计算的富氏变换，有)(xθb,a,)()(ˆξRξθaξb,θb,a,Uej6、连续Curvelet变换定义为：2)()(,:)(Rfdffxxxθb,a,θb,a,θb,a,7、逆curvelet变换：（略）8、离散curvelet函数族：)(,,xlkj用类似连续curvelet函数族的方法来建立。可以证明，离散Curvelet函数族能构成一个紧标架，因此离散curvelet变换是可逆的，有重建公式lkjlkjlkjff,,,,,,,)(ˆξθb,a,于是，在频域(ξ1,ξ2)平面有旋转的扇形支持域。例：CurveletbyE.Candès,D.Donoho(2003,2004)（续）几个要点：1、选用具有平滑性的Meyer窗函数V(t)和W(r)，分别用来构造射径方向和角度方向的频域窗。平滑窗的意义在于它的傅里叶变换有近似有限支持。2、用内插方法从极坐标变到直角坐标，便于使用FFT计算。3、在直角坐标下引入坐标旋转，使获得的curvelet标架具有平移、尺度、旋转三种表示能力。4、证明curvelet标架是紧标架，即Riesz基，因此curvelet变换是可逆的，有简单的反变换公式。几何解释：1、在频域上具有离散小波瓦片，有抛物型伪极坐标支持，如图所示。2、由于空域图样和频域图样的垂直关系，可以看出，所构造的小波标架能够覆盖各种取向和各种尺度的空域棱边。事实上和平移量b无关，这和富氏变换性质相似。3、频域小波瓦片的全体形成一个紧支持。空域小波标架一定是不紧的。离散型curvelet标架是高度冗余的。)(ˆξθb,a,)(ˆξθb,a,)(xθb,a,例：CurveletbyE.Candès,D.Donoho(2003,2004)（续）应用：1、去噪图像→Curvelet变换→去噪处理→重建算法→输出图像典型去噪处理算法：硬门限法，特别对高频、低电平小波系数。基于成像物理的处理方法。2、利用稀疏性的图像数据压缩。Curvelet变换能够适应性地表达图像上各种几何取向的棱边。棱边取向的几何规则性越高，重要的变换系数个数越少，图像可压缩更有效。因此，对于纹理几何规则性强的图像，适合于用Curvelet或Bandlet变换来实现去噪和压缩。如果图像纹理的几何规则性不强，应该用常规的Wavelet变换。关于稀疏性和压缩后面专门介绍。基本观察：从wavelet到X-let，人们追求发现更有效的信号（图像）表示方法。目前这些方法的发展带有高度程式化、技巧性、和特定有效性的特征。学习和掌握这些方法和相关理论是有意义的和重要的，沿着类似的思路去寻求突破性的创新是困难的。二、稀疏性和压缩感知(SparsityandCompressiveSensing)各种形态的稀疏性：信号（图像）本身可能是稀疏的；信号（图像）在变换域是稀疏的；信号（图像）中含有内部的相关性、规律性，当用某个数学模型描述时，只需要少量的模型系数；信号（图像）的规则性：良好的图像具有卡通模式，噪声和干扰较少，这意味着具有变差稀疏性或总变差有限性。压缩采样：采样是一个线性泛函作用于信号，不限于获得信号的一个瞬时电平。例：信号xRn，将信号与随意选取的m个向量vi作内积（滤波），mn,内积结果y。这种采样可以用一个m×n代数方程描述：Φx=y。在一般情况下，重建x有无穷多解。K-稀疏性解：上述问题中，如果假定已知x中至多只有K个非零元，求解问题变成求解Φx=y，带着附加约束#supp(x)≤K。整数规划问题：求最稀疏解（P0)min{||x||0：Φx=y，xRn}，其中ΦRm×n，yRm，mn。||x||0=#supp(x)=x中非零元个数。（1）解通常不唯一；（2）具有NP-hard计算复杂性。mnФxy凸松弛规划（P1)min{||x||1：Φx=y，xRn}，等价的线性规划问题：多项式时间算法minΣaisubjecttoΦx=y-a≤x≤aΦx=yx1x2Φx=yx1x2整数规划问题凸松弛规划▬▬►问题P1≡P0的条件:受限等量性质RestrictedIsometryPropertyofOderk(RIP)[E.J.Candes,etal.,2006]定义：假定km是一个整数，一个矩阵ФRm×n的等量常数δk是指对所有k稀疏向量xRn，满足以下不等式的最小值：(1-δk)||x||l22≤||Фx||l22≤(1-δk)||x||l22大致地说，RIP是要求Ф的每个m×k子矩阵Sk是近似单位正交的，即任何一个SkTSk的各个特征值不要偏离数值1太远。充分条件（Candes，2006）：如果δ2k√2–1,那么对于所有k稀疏向量x，（P1）问题的解等于（P0）问题的解。有噪情况：（Candes,2005）去噪问题（P1ε)min{||x||1:||Φx–y||2≤ε，xRn}，设Ф给定，且y＝Φx＋e，||e||2≤ε.如果δ2k√2–1，则||x*-x||2≤C0k-1/2σk(x)1+C1ε,其中x*是（P1ε）的解，而σk(x)1＝minzXk||x–z||1,Xk是全体k稀疏向量集合，C0和C1是两个小数值常数。这个结果表明：解的误差与观测误差在同样的数量等级上（稳定性）。离散不定性原理：记T=suppf,|T|:=#(T)Ω=suppf,|Ω|:=#(Ω)---信号f时域非零点的个数。---信号f频域非零点的个数。一个大致的结果是：|T|+|Ω|~2√N，N---信号长度典型的信号复原例子：信号长度N，频域谱线个数为K，则在时域使用M~KlogN个样本，用l1最小化，可以得到完美的复原。更一般的稀疏信号重建问题：如果f在某个正交系统Ψ下是稀疏的：有f=Ψa,#{suppa}≤K,使用M个互不相关的“观测序列”φk获得M个观测量yk=f,φk,因此有y=Фf。信号重建问题可以表达为min{||a||1：ΦΨa=y}，当M≥const•KlogN时，信号能够被精确地重建。这个结果适用于图像。找M个互不相关的“观测序列”φk是容易的！仍然在发展中的问题：1、如何更准确地估计解的k-稀疏性和需要的最小量测数m？2、如何构造观测矩阵（或称词典矩阵）Ф？使用随机数构造观测矩阵已证明可行，一定条件下能保证RIP条件。是否存在通用和对重建计算最有