论文定稿010705202通信102陈江辉.doc

本 科 生 毕 业 论 文 一种基于稀疏表示的图像修复算法研究 陈江辉院 系： 信息工程学院 专 业： 通信工程 班 级： 102 学 号： 010705202 指导教师： 陈淑清 职称（或学位）： 博士 2014年4月原创性声明 本人郑重声明：所呈交的论文（设计），是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文（设计）不含任何其他个人或集体已经发表或撰写过的作品成果。对本论文（设计）的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学生签名： 年 月 日 指导声明本人指导的 同学的毕业论文（设计）题目大小、难度适当，且符合该同学所学专业的培养目标的要求。本人在指导过程中，通过网上文献搜索及文献比对等方式，对其毕业论文（设计）内容进行了检查，未发现抄袭现象，特此声明。指导教师签名： 年 月 日目 录1引言22 图像修复的一般方法2 2.1 基于偏微分方程的方法22.2 基于纹理的方法22.3 基于混合的方法32.4 基于稀疏表示的方法33 图像信号的稀疏表示理论33.1 稀疏编码43.2 字典的更新54 结论65 结束语7致谢8参考文献8附录9一种基于稀疏表示的图像修复算法研究陈江辉(信息工程学院 指导老师：陈淑清)摘要：图像具有直观地表达物体信息的功能，是人们获得信息的重要媒介，当图像受到破损时，图像本身的部分信息就会丢失，因此就需要一项技术对破损的区域进行修补，使其丢失的信息得到大部分的还原，这项技术就是图像修复。本文主要研究图像信号的稀疏表示方法，求解稀疏系数的匹配追踪算法，对字典原子进行更新的奇异值分解算法，通过对字典每一列原子的更新和对稀疏系数矩阵每一行的更新，减小了图像修复过程中产生的误差。关键词：图像修复；字典；稀疏表示；匹配追踪；奇异值分解Study of an Image Inpainting Algorithm Based on Sparse Representation Chen Jianghui(College of Information Engineering , Advisor: Chen Shuqing)Abstract: Image has the function of expressing the nformation of objects visually, which is an important medium of gainning information, when the image is damaged, a part of the information is lost, so they need a technology to repair the damaged areas, make the loss information is probably restored, the technology is called image inpainting. This paper mainly studies the sparse representation method of signal, the algorithm for solving sparse coefficient called matching pursuit algorithm and the singular value decomposition algorithm to update the atoms of dictionary , through the atomic learning dictionary each column and each line of sparse matrix is updated, which reduces the error occurring in the process of the image inpainting.Keywords: image inpainting; dictionary; sparse representation; matching pursuit; singular value decomposition1引言图像是人们获取信息的一种重要渠道，利用静态灰度图像验证算法的可行性和有效性，可以减小图像处理过程中的复杂度。为了能使图像的相关的、有效的数据能在计算机上进行处理，需要对其在空间和灰度上进行处理。图像修复就是利用破损图像的的现有信息通过一定的算法修补已遭破坏的图像区域或者去除多余的景物，使得修补后的效果接近原来的图像或者成为原来的图像。图像修复已成为在图片美化处理与修整、视频加工等领域一项不可缺少的综合性技术，尤其是在考古工作，侦破案件方面，有着极其重要的应用价值和研究意义。2 图像修复的一般方法图像修复目前有四种方法，分别是基于偏微分方程的方法、基于纹理的方法、基于混合的图像修复方法和基于稀疏表示的方法1。2.1 基于偏微分方程的方法基于偏微分方程的图像修复方法最早出现在2000年，由当时的知名学者Bcrtahnio，Sapiro，Case，Bcllester基于偏微分方程率先提出，后来人们为了纪念这几位学者的贡献，所以称这个模型为BSCB模型。BSCB模型采用各向异性的方式扩散灰度信息能够很好的保护图像的结构信息，尤其是图像的边缘信息，破损区域的边缘部分修复后不会产生模糊的视觉效果。在BSCB模型中，灰度值在同一等级上的像素点的连接线叫做等照度线，该模型以一种类似于热扩散的方式，将图像完好区域像素点的灰度值信息，按照等照度线的方向延长到达修复区域边界的等照度线，同时保持其与边界的交角，并继续以这种方式逐渐从边界向待修复区域内部延伸2，各向异性扩散信息，直到最终完成对整个破损区域的修复，图像修复的迭代公式：，表示每次迭代时的长度，表示迭代的次数，表示对的修复结果，当迭代的次数逐渐增加时，图像破损区域得到明显的修复，当迭代的次数大到一定程度时，这时有，如果再继续增加迭代次数，图像修复的视觉效果将保持不变或者不大明显，这说明了图像的破损区域已经达到了最好修复效果的极限了，结束修复。一般情况下，图像修复算法中都是设置某一阈值，和之间的差值小于时，算法自动停止迭代，修复过程结束。除了BSCB模型之外，其他类型的有TV、CDD模型，这些模型对于破损区域比较小而且结构性比较好的破损图像修复的效果很好，对于破损区域比较大而且结构性比较不好的图像修复效果比较模糊。2.2 基于纹理的方法纹理是物体表面呈现凹凸不平的沟纹，是物体最直观的视觉表现。基于纹理合成的图像修复算法最早可追溯到1995年，美国学者Heeger等提出了一种基于金字塔的模型，他们根据对图像数据进行分析和统计，做了大量的运算，成功地实现了对图像的纹理合成3。基于纹理合成的图像修复首先把图像的破损区域划分一个个的小块，然后用公式，计算每个待修补小块的优先权值，表示以点为中心的的待修补小块的优先权值，表示表示以点为中心的的待修补小块的置信度值，表示待修补块的数据值，所有待修补块的优先权值计算完毕之后，取出优先权值最大的那个待修补块，并在图像的完好区域中根据准则：，全局搜索与待修补块最为相似的匹配块，将其像素点上的有用的数据信息复制并替换到待修补块对应的位置上，至此，完成了对这一优先权值最高的图像块的修复之后，更新置信度值，对第二高优先权值的待修补块进行修补块进行修补，重复以上步骤直至修补完所以待修补的图像块，由于是复制匹配块的纹理信息，所以对自相似性较好的图像修复能取得很理想的视觉效果。基于纹理合成的图像修复对图像本身的结构信息的破坏程度较小，也很有效地保护了图像的纹理信息，针对破损面积较大的图像，取得很好的修复效果，同时也能适合破损区域较小的图像修复。在纹理这方面，目前应用比较广泛的，主要是Criminisi算法和基于其改进的各种算法。2.3 基于混合的方法基于混合的图像修复算法，把图像分解为结构部分和纹理部分，然后对结构部分和纹理部分单独施以合适的算法进行修复，此类算法的缺点比较多，图像分解繁琐，计算复杂，效果不是很好。2.4 基于稀疏表示的方法稀疏表示理论经过长期发展，在图像领域中的应用是其发展的成熟期，稀疏表示理论在图像修复等领域受到越来越多的关注和研究。Guleryuz等最先利用稀疏表示进行图像修复，虽然在图像待修复的局部区域获得最优解，但是并不能很有效地减少噪声对图像修复的干扰。Julien Mairal等在2008年提出了基于稀疏表示的图像重建4，他们用稀疏表示对图像进行去噪，同时对小于10 10区域进行修复，取得了良好的去噪和修复结果。基于稀疏表示的图像修复方法，首先把图像信号基于一个过完备字典上进行分解，通过匹配追踪MP（Matching Pursuit）算法求出图像信号在过完备字典上稀疏分解的系数，再利用方向最优化MOD（Method Of OptimalDirections）方法对字典进行更新，由于MOD方法在更新过完备字典的每一列原子的同时并没有更新稀疏系数，为了进一步提高修复质量，知名学者Elad和Aharon提出了奇异值分解SVD（Singular Value Decomposition）算法，这种算法更新了过完备字典的每一个原子的同时也更新了稀疏系数矩阵，有效地减少了误差。将过完备字典乘以稀疏分解之后所求得的稀疏系数矩阵，就可以近似地重构出图像，从而完成图像修复。大多数的基于稀疏表示的图像修复算法，对于修复过程中噪声的干扰具有比较强的抵抗能力，修复的效果比较清晰。3 图像信号的稀疏表示理论在一定误差允许的范围内，一系列预定的原子的线性组合可以近似地表示图像信号。设是图像信号集，是图像信号集的一个子集，也就是图像信号数据矩阵中的某一列，表示过完备字典库中的一列，即字典的一个原子，是过完备字典库，过完备字典的列数多于行数，所以称为过完备字典，过完备字典的每一列长度都为1，那么图像信号的稀疏表示可这样来描述：，其中就叫做图像信号在字典上稀疏分解的系数，也就是所谓的稀疏系数，在稀疏系数中，如果只有K个系数是非零的，而其他系数的值都为零，那么就把稀疏系数称为是K稀疏的，在图像处理过程中会受到噪声的干扰，设噪声为，因此，可以把稀疏表示的模型写成：。图像信号的稀疏分解如图1所示： 图1 图像信号的稀疏分解图基于稀疏表示的图像修复过程中，分为两个重要的环节，分别是稀疏系数的求解和字典与稀疏系数的更新。3.1 稀疏编码Mallat和Zhang 首次于1993年提出了信号可以在过完备库(over- complete dictionary)上分解的思想5，并基于过完备字典，实现了利用匹配追踪算法来求解稀疏系数，并且使得在稀疏系数中值为零的系数的个数达到最少。匹配追踪算法的诞生为以后各种改进的算法提供了必不可少的铺垫和启发，如后来基于其改进的正交匹配追踪OMP（Orthogonal Matching Pursuit）算法，从此之后，稀疏表示理论日益进步，走向成熟。匹配追踪算法所有追踪算法中最为常用的算法之一，其计算的难易程度相对其他追踪算法而言比较简单，算法易于理解，是目前比较流行的，其他各种追踪算法都是基于匹配追踪算法改进的，都克服了匹配追踪算法收敛慢的这一缺陷，但是算法的计算量特别大，不是很经常用到，但是比较经典。比如其中的正交匹配追踪算法就是典型的一种改进算法，其收敛速度相对比较快，但是处理的计算量比较大。正交匹配追踪算法，它的不同之处就是在每一次的稀疏分解过程中，都需要对之前每一步稀疏分解所有用过的原子和本次所用到的最佳匹配原子一一实施Gram-Schmidt正交化处理，得到一系列的正交原子，这些正交原子构成一个空间，再把待分解信号在这个空间投影，就可以得到比较准确的投影分量和残值分量，并且此方法收敛快，这就是改进的地方。正交匹配追踪算法，它的优点在于分解次数比较少，残值的收敛幅度大而且速度快，但缺点是计算的复杂度很大，比较不常用，匹配追踪算法因为具有简单性而比较常用。3.1.1 匹配追踪算法匹配追踪算法首先把待分解的图像信号分别与过完备字典的每个原子做内积运算，计算每个内积的值，内积值最大，就代表着待分解信号与这个原子最相关，这个原子就是最佳匹配原子。最佳匹配原子满足条件：，表示图像信号分别与字典中每一列原子作内积运算，内积运算之后，图像信号就在最佳匹配原子上分解为两部分，用表示，其中表示图像信号就在最佳匹配原子上分解的投影分量，表示图像信号就在最佳匹配原子上分解的残值分量，也就是第一次分解的残值，其中残值分量与投影分量正交，这样就完成了第一次稀疏分解，同样的道理，图像信号经过第一次分解后剩余的残值分量再进行分解，也就是把残值分量再分别作与过完备原子库中的每一列原子的内积运算，再选择出内积最大的那个最佳匹配原子，第二次的残值分量再与第二次的投影分量正交，并与第一次稀疏分解的残值分量构成一个类似于直角三角形的构架，因此，由此可见，第二次分解的残值分量小于第一次分解的残值分量，这说明了匹配追踪算法对图像信号的稀疏分解后的残值分量是随着分解次数的逐渐变多而减小的，也就是说匹配追踪算法对误差具有很好的收敛性，误差逐步下降。图像信号经过次稀疏分解后：,其中初始化等于，次分解之后，残值分量足够小，当残值趋于零时，在误差允许的一定范围内，图像信号就得到了很逼近的表示了。匹配追踪算法，所谓的匹配体现在：当图像信号分别与过完备字典的每个原子做内积求投影分量时，投影分量的值最大，就是是图像信号的最佳近似表示，这时候所选择的原子就是最佳匹配原子。所谓的追踪体现在：在有限次的稀疏分解之后，在一定的误差要求条件下，投影分量之和仍不能近似地表示图像信号时，还需要再对残值分量作多次的稀疏分解，直到残值分量足够小或者投影分量之和能近似表示图像信号为止，否则一直作重复性的分解，直到达到要求的条件为止。匹配追踪算法具体如下：输入：图像信号表示的集合，为图像信号数据中矩阵的列数，过完备字典原子库，残值参考性误差E2M，分解最高限制次数maxNumCoef。初始化：把最初的残值分量设为，稀疏分解的次数j=0，已找到的最佳匹配原子的索引集设为空集。输出：在过完备字典D上的稀疏系数。步骤一：分别计算待分解信号与过完备字典的每一列原子的内积，然后取出内积最大的对应的那个原子的脚下标作为索引。步骤二：更新原子索引集，求解目标函数，利用最小二乘法来计算此次分解的稀疏系数，这是一个对矩阵求伪逆的过程：，j=j+1。步骤三：更新残值分量。步骤四：判断稀疏分解条件jE2M,若条件成立，则返回到步骤一继续执行到步骤四，若条件不成立，则结束算法。最小二乘法，它通过最小化误差的平方和，来寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法又叫最小平方法。设、为已知量，求式的解，最小二乘法就是求最小化问题：，在matlab中，用语句就可求得。3.2 字典的更新图像信号在稀疏分解之后，为了进一步提高图像修复效果的质量，还需对过完备字典的原子进行更新。1999年Engan等提出了最优方向（MOD）算法，最优方向算法把误差问题作为一个最优化问题6，固定稀疏系数矩阵不变，用最小二乘法求出误差最小时得到更新的原子。MOD算法在适应性方面虽然有一定的优点，但是没有更新稀疏系数，所以目前应用不多。奇异值分解算法能同时更新过完备字典和稀疏系数，所以比较常用。3.2.1 奇异值分解算法最优方向算法在更新过完备字典的每一列的同时并没有更新稀疏系数，为了解决这一缺点，在2005年，知名学者Elad和Aharon提出了奇异值分解（KSVD）算法7，奇异值分级算法需要循环执行K次，所以被称为KSVD算法，KSVD算法在更新完字典每一列原子之后，利用更新完后的原子对稀疏系数矩阵的某一行进行更新，当字典的每一列原子更新完之后，稀疏系数矩阵的每一行也就随着更新完毕，这种算法在图像的稀疏表示领域里面产生颇为深远的影响。KSVD算法和MOD算法一样，适应能力都比较强，能适应各种方法所求出的稀疏矩阵来共同完成重构图像。目标函数：。把误差写成：，其中表示过完备字典的第j列，表示稀疏系数矩阵的第j行，在图像数据处理中，表示：字典乘以，取第k行中非零元素所在位置的列之后，并置第k行元素为0的稀疏系数矩阵，则表示将稀疏矩阵第k行的元素替换为零之后，字典与稀疏矩阵相乘之后重构的图像在数据上与原图像之间的误差，用表示，由于稀疏系数矩阵的第k行中不全部是非零的的，为了表达方便，设一有特殊用途的符号，则表示稀疏系数矩阵中的第k行的非零系数，对进行奇异值分解，得到，矩阵U的第一列就是原子的更新结果，表示矩阵的第一列，求解的结果就是稀疏系数矩阵的第k行中的非零系数的更新结果，依照上述的方法依次更新完过完备字典的所有原子和稀疏系数矩阵的每一行后，就得到了一个适合该图像信号的更新字典，大大提高了图像的修复质量。KSVD算法如下：输入：图像信号Y。初始化：k=1。步骤一：通过MP算法或者OMP算法来求解目标函数的稀疏分解系数矩阵。步骤二：计算，奇异值分解，得到更新的第k列字典原子，得到更新的稀疏系数矩阵的第k行。输出：得到更新的原子和更新的稀疏系数。 步骤三：k=k+1，当k小于过完字典的原子总个数时，返回步骤二继续往下执行，否则，退出算法。4 结论本文选择在Windows7系统环境下，使用matlab软件进行仿真实验，让已加入噪声和英文字母的lena图像分别基于利用没有更新的过完备字典和用KSVD算法更新的过完备字典为字典进行稀疏分解，用稀疏表示的方法对lena图像进行重构，效果如图2： 图2 图像修复的效果对比图图2中左上图为未被破坏的原始图像，右上图为加入许多英文字母和噪声的lena图像，左下图为基于稀疏表示的方法进行修复效果图，但是没有对其用到过完备字典进行更新。右下图为基于稀疏表示的方法进行修复，在此过程中利用KSVD算法对过完备字典进行学习，同时也更新了稀疏系数的修复效果图。图2表明，从视觉效果上看，这两种方法都能很好地对加入文字和噪声的图像进行修复。绝对误差如图3：图3 绝对误差图图像的绝对误差表示为未被破坏的原图像的每个像素点的灰度值与被破坏的、得到修复的图像的每个像素点的灰度值之间的差值。从图3中可以看出，同样是基于稀疏表示的，利用没有进行学习过的普通字典进行修复的，像素点灰度值的绝对误差，集中在零值附近的比利用奇异值分解而得到学习字典的图像修复来的少，由此可见，对字典进行学习可以提高图像修复的精确度。本文中的图像的误差表示为：图像数据被处理后，未被破坏的原图像的图像的灰度值数据矩阵的每一列灰度值，减去被破坏的、得到修复的图像的图像的灰度值数据矩阵的每一列灰度值，然后对这一列中每个像素点的灰度值进行平方，再求它们的平均值，直到图像数据矩阵的所有列都进行上诉运算之后，再求所有平均值的平均值，最后开方，这个开方值就是图像的误差，也就是均方误差，这种表示方法的图像误差，从数字上能很