一种基于搜索准则和约束条件的块稀疏表示的图像修复方法

摘要

本发明公开了一种基于搜索准则和约束条件的块稀疏表示的图像修复方法，步骤包括：在源图像中确定待修复块Ψ

说明书

技术领域

本发明涉及图像处理技术领域，具体说是一种基于搜索准则和约束条件的块稀疏表示的图像修复方法。

背景技术

图像修复是一门古老的艺术，起源于欧洲文艺复兴时期。通常把恢复图像中丢失或者破损的像素或者区域的过程叫做图像修复。有价值的艺术品在保存时，不可避免的会受到潮湿、鼠害、以及恶劣天气等的影响，导致艺术品受到损坏。为了更好的恢复艺术品的本来面貌，一般会请一些专业人士根据自己的经验和技术对受损的艺术品进行手工修复，通常叫做“润泽”，修复过程常常带有主观性。另外，由于受损的艺术品具有极高的价值，所以修复工作也存在巨大风险，一旦修复失败，便难以挽回。随着数字技术的发展，人们逐渐开始使用相关算法对破损图像进行修复，以避免由于人的主观性以及手工修复水平参差不齐造成的失误。图像修复技术应用领域广泛，包括古文物字画的修复、老照片的修复、用于目标移除图像的修复以及网络传输信息丢失造成的图像修复等。

2004年，Wexler使用全局连通性度量函数来约束搜索候选块，实现在众多候选块中，保持连通度量的最小值，进一步限制了错误纹理的延续，使得延续的纹理与原始纹理不同。之后有研究者使用稀疏线性组合表示候选修复块，与传统基于匹配块的修复方法相比，其中结构稀疏能够更好地区分结构和纹理，修复块的稀疏表示迫使被修复的区域不会过于锐利，与周围的纹理一致。也有研究者以压缩传感和稀疏表示为理论依据，提出了基于剪切波变换的稀疏性正则化的图像修复模型，以便更好地保留图像的结构特征，该模型用剪切波作为图像的稀疏表示，以稀疏性作为正则化项，同时基于变量分裂法，采用增广Lagrange优化方法求解最优化问题，并且通过交替最小化方式来降低计算复杂性。随着研究的深入，有研究者指出基于组的稀疏表示(Group-based Sparse Represention,GSR)具有低复杂度特性，并设计了一种自适应的字典学习算法，并且利用分裂的Bregman技术解决了GSR驱动的最小化问题。最新的研究成果则提出采用词典学习框架，创建Trainlets，通过利用稀疏字典学习算法从各种数据库的语料库设计大的适应性原子。根据学习的全局模型，将图像修复任务作为一个疏导促进先验的逆问题。

现有技术中，一般利用块结构稀疏度计算填充顺序,将多个匹配块的稀疏表示作为填充信息,进一步提高了修复图像的质量，但其也存在明显的不足，即不能很好的保持结构部分的连贯性及结构和纹理部分的清晰性。稀疏表示的多个匹配块，直接决定合成待修复块的匹配块质量。如果合成的匹配块是基于多个图像块合成的，合成的像素块中的每一个像素点都是由多个图像块的对应像素点的线性加权和。如果图像块的差异较小，合成的图像可能不会有太大的影响。但是如果多个图像块的差异较大，合成图像块差异大的部分必定会模糊。

如果破损区域是小区域(如划痕，文字遮挡)，由于待修复的中心没有过于远离最开始的待修复区域的边界，修复的模糊块不会过多的对后续的修复产生太大的影响。但是当破损区域是大区域时，现有技术对图像修复的质量就会产生非常严重的影响。对于大区域破损的图像，优先修复的边缘往往是待修复图像的边缘而且修复后模糊的图像块还会做为待修复图像块的已知区域成为搜索匹配块的区域，相似度高将成为新的匹配块。如果每一次的修复都会产生或多或少的模糊，而模糊效果逐级叠加，修复后图像的中心区域已经区域平滑，当修复的区域是纹理区域时图像的可视性会受到严重影响。

在图像修复时，现有算法修复待修复图像时都是基于待修复区域的模板划分图像的已知区域个未知区域，待修复的图像块位于已知区域的边界上，图像块中存在已知区域的位置区域。利用待修复块中的已知信息在图像的未破损区域查找相似的图像块，作为填充的条件。而利用最优匹配块修复时，直接使用源图像中的单块图像信息进行修复，因此并不存在明显的缺陷。但是如果在多个匹配块合成修复块时还将待修复块已知信息作为选取合成匹配块的唯一条件，那么便忽略了选取的多个匹配块对应待修复块未知区域的差异。

发明内容

鉴于已有技术存在的不足，本发明的目的是要提供一种能够保持图像结构连贯性及结构清晰性且适应性强的图像修复方法。

为了实现上述目的，本发明技术方案如下：

一种基于搜索准则和约束条件的块稀疏表示的图像修复方法，其步骤包括：

S1读取源图像，确定待修复块Ψ_p及其中心点p，并标记待修复块已知区域和待修复块未知区域，定义F为待修复块的已知信息标示矩阵，E为待修复块未知信息标示矩阵；

S2从源图像中选取M个与待修复块已知区域最相似的图像块，对所选M个图像块进行删减，得到候选块集合Q＝{Ψ_q}_{q＝1,2,…,L}；

S3将候选块集合中各候选块进行稀疏表示，并构建待填充块为其中Ψ_t为待填充块稀疏表示信息，α＝{α₁,α₂,…,α_L}为稀疏表达系数；

S4综合待填充块与待修复块已知区域最优匹配约束条件和待填充块与待修复块未知区域最优匹配约束条件，构建系数表达约束条件；

S5根据稀疏表达候选块约束条件构建稀疏表达方程；

S6通过贪心算法求解稀疏表达系数α＝{α₁,α₂,…,α_L}；

S7将稀疏表达系数带回待填充快稀疏方程求得待填充块Ψ_t；

S8将待填充块Ψ_t填充到源图像中，进行图像修补。

与现有技术相比，本发明的有益效果：

本发明针对使用稀疏表示匹配块存在的不能很好的保持结构部分的连贯性及结构和纹理部分的清晰性的问题，对多个匹配块的选择方法和稀疏表示信息的约束条件进行优化，计算系数表达系数，进一步改善图像的修复质量。其修复的图像更好的保持了结构连贯性以及结构的清晰性。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明工作流程示意图；

图2为本发明系数表达带填充块流程示意图；

图3为本发明求解α流程示意图；

图4为实施例一本发明方法与对比算法的实施效果图；

图5为实施例二本发明方法与对比算法的实施效果图；

图6为实施例三本发明方法与对比算法的实施效果图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

现有技术中利用块结构稀疏度计算填充顺序，并将多个匹配块的稀疏表示作为填充信息，以提高修复图像的质量。但是该方法不能很好的保持结构部分的连贯性及结构和纹理部分的清晰性。匹配块的稀疏表示流程如图2所示。稀疏表示的多个匹配块，直接决定合成待修复块的匹配块质量。如果合成的匹配块是基于多个图像块合成的，合成的像素块中的每一个像素点都是由多个图像块对应像素点的线性加权和。如果图像块的差异较小，合成的图像可能不会有太大的影响。但是如果多个图像块的差异较大，合成图像块差异大的部分必定会模糊。

如果破损区域是小区域(如划痕，文字遮挡)时，由于待修复的中心没有过于远离最开始的待修复区域的边界，修复的模糊块不会过多的对后续的修复产生太大的影响。但是当破损区域是大区域的时候就会对图像修复的质量产生非常严重的影响。图像大区域的破损先修复的边缘往往还是待修复图像的边缘而且修复后模糊的图像块还会做为待修复图像块的已知区域成为搜索匹配块的区域，相似度高将成为新的匹配块。如果每一次的修复都会产生或多或少的模糊，修复后图像的中心区域已经区域平滑。当修复的区域是纹理区域时图像的可视性会受到严重影响。

在图像修复时，现有算法修复待修复图像时都是基于待修复区域的模板划分图像的已知区域个未知区域，待修复的图像块位于已知区域的边界上，图像块中存在已知区域的位置区域。利用待修复块中的已知信息在图像的未破损区域查找相似的图像块，作为填充的条件。

当利用最优匹配块修复时，直接使用源图像中的单块图像信息进行修复，因此并不存在明显的缺陷。但是如果在多个匹配块合成修复块时还将待修复块已知信息作为选取合成匹配块的唯一条件，那么便忽略了选取的多个匹配块对应待修复块未知区域的差异。针对上述问题，本算法对多个匹配块的选择方法和稀疏表示信息的约束条件进行优化，进一步改善图像的修复质量。

下面结合附图以及具体实施例进一步说明本发明的技术方案：

如图1所示，为基于搜索准则和约束条件的块稀疏表示的图像修复方法的工作流程，其步骤包括：

S1读取源图像，确定待修复块Ψ_p及其中心点p，并标记待修复块已知区域和待修复块未知区域，定义F为待修复块的已知信息标示矩阵，E为待修复块未知信息标示矩阵。

S2从源图像中选取M个与待修复块已知区域最相似的图像块，因为是根据待修复块已知区域选取的图像块，所以各个图像块对应待修复块的已知区域应该比较接近，然而未知区域差异无法确定，为了缩小差异，对所选图像块进行删减，以得到候选块集合Q＝{Ψ_q}_{q＝1,2,…,L}，其步骤包括：

S21根据平方差之和准则从源图像的已知区域中选取M个与待修复块已知区域最相似的图像块，构成预选块集合

Ψ_u＝{Ψ_u1,Ψ_u2,…,Ψ_uM}>

S22计算预选块集合中各图像块之间的相似度，并定义图像块彼此间相似度集合为

G＝{G₁,G₂,…,G_i,…,G_M}>

其中，1≤i≤M，元素G_i为第i图像块与其他图像块相似度之和，即：

其中，1≤j≤M且j≠i。G_i越小说明与所选相似块整体越相似，因此选取其中较小的元素作为稀疏表示的字典。

S23将预选块集合中各元素按照其与其余图像块相似度之和G_i由小到大排序，并删除第L个元素之后的元素，得到候选块集合Q＝{Ψ_q}_{q＝1,2,…,L}。L根据以下公式求得：

其中，ν为候选块集合元素个数优化参数。

S3将候选块集合中各候选块进行稀疏表示，并构建待填充块为其中Ψ_t为待填充块稀疏表示信息，α＝{α₁,α₂,…,α_L}为稀疏表示系数，如图2给出了待填充块稀疏表达的流程。

S4综合待填充块与待修复块已知区域最优匹配约束条件和待填充块与待修复块未知区域最优匹配约束条件，构建系数表达候选块约束条件。现有技术中使用合成的待填充块和待修复块邻域合成块进行比较作为约束条件，虽然可以充分的保持与邻域信息的衔接，不产生接缝效应，但是没有考虑了待修复块未知区域之间的差异。为了进一步优化产生匹配块的产生的模糊，本算法对稀疏表示的约束条件进行改进。其步骤包括：

S41构建待填充块与待修复块已知区域最优匹配约束条件为：

||FΨ_t-FΨ_p||²≤δ>

其中，F为待修复块的已知信息标示矩阵，Ψ_t为优化待填充块，δ为优化参数。因为待修复块的不完整性，因此不能将合成的图像块与待修复图像块进行比较。但是待修复图像块也存在已知区域，所以可以作为与合成块比较的条件之一。

S42为了保证待修复块的未知区域与合成的填充块的连贯性，针对候选块集合Q中每一个匹配块，均在待修复块周围按照步骤S2中方法选取与其最相似的n个图像块，并将选取的nL个图像块{Ψ_s}_s＝1,…,nL合成一个对比块Ψ_e来约束稀疏表示的填充块未知部分，定义：

其中，γ_s为线性表示图像块{Ψ_s}_s＝1,…,nL的系数，γ_s根据图像块{Ψ_s}_{s＝1,2,…,nL}与待修复块Ψ_p的相似关系定义。这样既保证对比块和修复块足够接近也可以反映出候选块的整体特性。使用SSD方法区分已经找到的相似块集合{Ψ_s}_s＝1,…,nL。因为相似性与SSD所求出的值成反比，所以选用d(·)值的倒数作为判断标准，所述γ_s的根据公式

γ_s＝(d(Ψ_p,Ψ_s)·Z(p))^-1

求得，其中Z_s(p)为归一化常数，即

S43构建待填充块与待修复块未知区域最优匹配约束条件为：

||β(EΨ_t-EΨ_e)||²≤δ>

其中，β为邻域一致性约束的权重系数。

因为待修复块中存在已知区域，使用修复块中的已知区域信息进行对比比使用合成块的信息进行对比更加精准，所以只需要使用合成的对比块对比未知区域的信息即可。

S44将公式(6)待填充块与待修复块已知区域最优匹配约束条件和公式(7)待填充块与待修复块未知区域最优匹配约束条件结合，即系数表达候选块约束条件为：

其中，

S5根据稀疏表达候选块约束条件构建稀疏表达方程：

S6通过贪心算法求解稀疏表达系数α＝{α₁,α₂,…,α_L}，如图3所示，系数表达系数的求解步骤包括：

S61从候选块集合Q＝{Ψ_q}_{q＝1,2,…,L}中选择l个非零的候选块记为T_l＝{Ψ₁,Ψ₂,…,Ψ_l}，其稀疏表示为其中0≤l≤L-1；

S62从集合Q-T_l中依次选取一个新的图像块为Ψ_ql+1，求得满足

的图像块Ψ_ql+1；

S63对上式进行系数优化，则有：

为了解决该优化问题，定义格拉姆矩阵为：

其中，X为装有集合T_l和判断块Ψ的矩阵，即：X＝{DΨ_q1,DΨ_q2,…,DΨ_ql+1,DΨ}，1为长度为l+1值全为1的列向量，则：

S64将由式(11)计算出的Ψ_ql+1和集合T_l带入(8)求得ε；

S65判断ε是否满足式(9)或者ε的值增加，若是则求得的α即为稀疏表示系数；否则将Ψ_ql+1加入到集合T_l中形成新的集合T_l+1，并且令l＝l+1，重新开始迭代。

S7将稀疏表达系数带回待填充快稀疏方程求得待填充块Ψ_t；

S8将待填充块Ψ_t填充到源图像中，进行图像修补。

下面结合具体实施例对本发明进行进一步说明。

本方法基于Windows7系统、以Visual.Studio2013+OpenCV v2.4作为实验平台。为了验证本文算法的有效性，将对不同类型的破损图片，如划痕，文字覆盖，目标去除等，进行修复。

利用现有技术中采用稀疏线性组合表示候选修复块的方法作为对比算法。对比算法参数设置如下，候选匹配块M设置为30，参数δ设置设为5，邻域一致性约束的权重系数β设置为0.5，待修复图像块直径w为7，邻域图像块直径大小设置为11。

作为本发明的较佳的实施方案，优选将本发明所述方法各项参数做如下设置：优化参数δ设置为5，使用SSD查找的与待修复块的候选匹配块数量M设置为30，与候选块邻域相似块查找个数n设置为3，邻域一致性约束的权重系数β设置为0.5，带修复图像块的直径w设置为7，邻域图像块直径大小设置为11。下面依据不同实施例对本发明方法和对比算法的效果进行比较。

实施例一

分别就小尺度破损图像采用本发明所述方法和对比算法进行修复，其修复效果对比如图4所示，图4中第一行到第四行的图像大小依次为分别选取208×209、237×265、248×270和228×229像素；(a)列表示没有破损的原始图像，(b)列表示破损需要进行修复的图像，(c)列表示使用对比算法进行修复的效果，(d)列表示使用本算法进行修复的效果。

由图4可知，第一幅图中小车的后备箱中对比算法修复后存在一个与缝隙连接的黑斑修复效果有欠缺，使用本文算法修复后的效果图中没有出现。第二幅图中对比算法修复后的蝴蝶腿部有缺陷，出现了腿部断连的效果，并且蝴蝶靠近腿部的翅膀出现了小区域的模糊，使用本文算法并没有出现上述问题。第三幅图片中，对比算法的实验结果在人物的眉毛处出现了一个向上的角，本文算法的实验结果图中没有出现。在第四幅图中，对比算法在红辣椒的边缘存在不够圆滑有棱角的修复问题，本文算法没有。为了更客观的对比原始算法和本算法的优劣，峰值信噪比的比较和时间对比如表1和2所示：

表1对比算法与本发明算法结果比较

表2原始算法与本算法结果比较

如表1、表2所示，本文算法不但PSNR值高于对比算法，而且在运行时间上也有所提升。图4给出了多幅模拟划痕造成的小区域图像进行修复，以验证本文算法的非局限性。

实施例二

分别就严重破损图像采用本发明所述方法和对比算法进行修复，其修复效果对比如图5所示，图5中第一行到第四行的图像大小依次为分别选取208×209、237×265、248×270和228×229像素；(a)列表示没有破损的原始图像，(b)列表示破损需要进行修复的图像，(c)列表示使用对比算法进行修复的效果，(d)列表示使用本算法进行修复的效果。

如图5所示，对比算法在第一幅图像的公路上存在较为严重的结构区域不连贯，第二幅图像在雕像的腿部和手臂部存在一定的纹理区域不清晰，第三幅图像树干的连接存在一定的结构区域不连贯，同时也存在一定的纹理区域不清晰，第四幅图像在长颈鹿的脖子处存在明显的结构区域不连贯。这些问题是由于匹配块未知区域差异过大造成的合成块不理想，先修复的区域成为了后续待修复块的已知区域，而先修复的区域存在问题则严重影响到了后续修复的质量，最终导致图像修复质量不理想。本算法通过改进匹配块搜索原则来降低匹配块之间差异，改进约束条件来优化合成块质量，较为成功的避免了对比算法中出现的问题。为了客观对比本算法的优劣，本发明算法与对比算法修复结果的PSNR值对比如表3所示：

表3对比算法与本算法结果比较

如表3所示，第一幅图图像本文算法PSNR值比对比算法提高了1.97dB，第二幅图像本算法比对比算法提高了2.92dB，第三幅图像本算法比对比算法提高了0.35dB，第四幅图像本算法比对比算法提高了2.74dB。本发明算法与对比算法运行时间对比如下表所示：

表4.4原始算法与本算法时间结果比较

如表4所示，本文算法通过改进匹配块搜索策略缩小匹配块之间的差异，改进约束条件提高合成块清晰度，提升了图像修复的质量。

实施例三

分别就目标移除图像采用本发明所述方法和对比算法进行修复，其修复效果对比如图6所示，图6中第一副图像大小为211×253像素，第二副图像大小为192×253像素，第三幅图像大小为167×254像素，第四幅图像大小为182×198像素，(a)列表示没有破损的原始图像，(b)列表示破损需要进行修复的图像，(c)列表示使用对比算法进行修复的效果，(d)列表示使用本算法进行修复的效果。第一幅图像为去除图片阴影部分的小球，对比算法由于没有考虑匹配块未知部分的区别，在修复算法的前期的合成块不理想，严重影响后期修复，导致图片修复的效果较差。而本文算法没有则成功的消除了对比算法修复中的问题，修复效果比较理想。第二幅图像为去除图像中的动物，对比算法修复区域中心存在一条黑线，而本文算法没有出现类似问题。第三幅图像为去除在图片风景中的人物，对比算法存在小区域的模糊，导致修复效果不佳，本文算法使用本文选择的候选匹配块成功的避开了问题。第四幅图片为去除图片中较大的人物，对比算法由于合成的填充区域存在问题影响到了后续的修复导致了较为严重的问题，本文算法则没有出现类似问题。本文算法与对比算法运行时间对比如表5所示：

表4.5原始算法与改进算法结果比较

由表5可知，本发明提出的图像修复方法在运行时间较对比算法有所提升。

本发明主要针对使用稀疏表示匹配块存在不能很好的保持结构部分的连贯性及结构和纹理部分的清晰性的问题，提出了一种改进的稀疏表示匹配块的图像修复算法。基于SSD搜索策略忽略搜索到的匹配块之间与待修复块对应未知区域的差异，基于匹配块之间的相似性构建改进的匹配块搜索策略；根据匹配块需要与待填充块已知区域充分接近并且与邻域的连贯性构建约束方程，求解稀疏表达系数确定填充块。通过实验验证本算法可以较好的保持结构的连贯性以及结构的清晰性。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。