一种基于分水岭分割的快速图像修复算法

屠 昕，钮圣虓，陈更生，许 薇

(复旦大学 专用集成电路与系统国家重点实验室，上海 201203)

一种基于分水岭分割的快速图像修复算法

屠 昕，钮圣虓，陈更生，许 薇

(复旦大学 专用集成电路与系统国家重点实验室，上海 201203)

为快速准确地对破损图像进行修复，提高传统算法的修复质量和速度，本文提出了一种改进的基于分水岭分割的快速图像修复算法．首先针对传统算法在修复速度上的不足，采用改进的匹配区域搜索方法以缩小搜索区域，然后通过分水岭分割结果筛选匹配块以进一步加速图像修复，最后利用分水岭分割结果提出了新的分类修复方法来改进图像修复质量．实验结果表明，相较于现有算法，本文提出的算法在修复质量上有明显的改进，并且修复速度平均提升了40%左右．

图像修复； 匹配区域缩小； 分水岭分割； 分类比较

图像修复，是在保证图像的质量和自然效果不受破坏的前提下，利用图像中未损坏的信息对图像中遗失信息进行修补或者对图像中特定的信息进行移除的图像处理技术，在图像轮廓修复、气象云图处理、物联网等许多领域都有广泛的应用．

图像修复技术主要分为两类．一类是基于Bertalmio等[1]提出的基于偏微分方程的方法，通过对破损区域的边界进行不同方向的扩散来对图像进行修复．在其基础上，Chan等[2]提出基于全变分的修复方法，改进了对有噪声图像的修复．该类算法的缺点是运算量大，不适合修复大面积的破损．另一类方法是最早由Efros[3]提出的基于纹理合成的图像修复方法，通过对纹理的适当采样来对破损区域进行填补，适合大区域的图像修补．纹理合成的方法容易导致修复后的图像结构信息出现断裂．

Criminisi[4]在纹理合成的基础之上结合边界扩散算法的优点提出了基于样本块的图像修复算法，利用破损区域的边界信息确定修复优先级，在图像未破损的已知区域(源区域)中寻找与待修复区域的纹理信息最为接近的样本块来填充破损区域(目标区域)，获得了较好的图像修复质量．在Criminisi算法的基础上，Wen等[5]通过优化修复块的优先级计算公式在修复结构信息时取得了更好的效果，但并没有对修复速度做出改进；刘奎等[6]提出了一种利用结构张量来决定目标区域修复顺序的改进算法，但是同样没有对修复速度做出优化．Masnou[7]通过对图像中的等照度线进行匹配和连接来改进Criminisi算法中修复结构信息时产生的误差．Frederic等[8]在Masnou算法的基础上通过使用欧拉曲线替代直线来修复图像的等照度线，使得修复效果更加自然．基于等照度线的改进算法缺点在于增加了修复时间，而且难以保证等照度线断点的正确匹配．

在提升修复速度方面，Hui等[9]则通过预先对源区域中的样本块进行分类来加快匹配速度．王昊京等[10]通过放缩图像的方法显著地提升了Criminisi算法的修复速度，但是修复质量也随着缩放倍数的提升出现了明显的下降．而Anupam等[11]针对Criminisi算法在修复质量和时间上同时进行了改进，相较于前述的几种算法取得了更为理想的处理效果，但仍然在修复时间、修复效果等方面存在不足．

针对目前图像修复算法存在的各种不足之处，本文首先改进了Anupam算法中的匹配区域搜索算法以减少每次填充过程中的匹配次数，并利用分水岭分割的结果对匹配块进行筛选，通过减少需要比较的匹配块数量来对算法进行加速；同时基于分水岭算法的分类匹配结果，提出了一种改进的分类修复算法，针对不同类型的待填充块采取不同的填充策略，以提高图像修复的质量．实验结果表明，相比上述各类已有的算法，本文算法不仅能够快速有效地修复大面积破损区域，图像修复的质量更高，修复效果也更加自然．

1 基于样本块的图像修复算法

1.1Criminisi算法

图1 Criminisi算法修复过程示意图Fig.1 Diagram of the inpainting process of Criminisi algorithm

Criminisi算法的主要思想是在确定了破损区域后，通过匹配最接近的样本块来对图像的破损区域进行修复．如图1所示，Ω为待修复的破损区域，φ为未破损的源区域，I为整幅图像(I=Ω∪φ)，δΩ为破损区域和源区域的边界．Criminisi算法分为3个步骤：

步骤1.计算破损部分边界上的修复优先级．

由于修复顺序会影响修复效果，为了确定边界δΩ上各点的修复顺序，Criminisi算法首先计算δΩ边界上所有像素点的优先级，找出优先级最高的点p和以其为中心的样本块Ψp．为了保证破损区域较小且包含结构区域的样本块优先合成，式(1) 定义了修复优先级：

P(p)=C(p)×D(p)，

(1)

其中：C(p)为信任项，D(p)为数据项.具体定义如式(2)和式(3)所示：

(2)

(3)

式(2)中，Ψp为图1中以p点为中心的待修复块的像素点的集合，Ψp∩φ为黑色方框里的已知区域，即Ψp中位于源区域的部分．|Ψp|表示整个待填充块中像素点的个数．C(p)为像素点p通过Ψp中所有像素点q的信任项C(q)所求得的对应信任项，对于位于源区域的像素点q其信任项为1，对于位于破损区域的像素点q其信任项为0．C(q)越大表示对应的Ψp破损程度越小，越值得被优先修复．

步骤2.寻找最佳匹配块Ψq．

在找到优先级最高的待填充块Ψp之后，需要在图像的源区域φ中寻找与Ψp最接近的匹配块Ψq，并用Ψq来对Ψp中的破损区域进行填充．其中Ψq的选择条件如式(4)所示，其中d(Ψp,Ψq)表示样本块Ψp中未破损区域与匹配块Ψq对应区域之间的欧式距离[4]：

(4)

步骤3.填充待修复区域并更新边界．

在找到与Ψp最接近的匹配块Ψq之后，Ψp中的破损区域被Ψq中的对应区域填充．在填充完成后，更新破损区域的边界δΩ．以更新后的边界为新的边界，重复步骤1～3的计算直到破损区域被全部修复．

图2 相似块的误匹配示意图Fig.2 Diagram of the false match of similar patches

Criminisi算法的优点是一方面能够保证图像纹理的修复质量，另一方面能维持原图的结构信息基本不变．但是，按照Criminisi算法来对图像进行修复，存在2个问题： 1) 在选定填充块的过程中只考虑了匹配块与待填充块对应的已知部分的相似度，没有考虑匹配块中用来作为填充区域的部分对修复结果的影响，导致修复结果易产生误差(如图2所示)；2) 每次找到用于填充的目标样本块之前，都要对源区域进行全局搜索，严重影响了算法的效率．

1.2Anupam算法

图2中，为了修复样本块p，Criminisi算法首先在已知区域中寻找最接近的匹配块进行修复．由于样本块A先于样本块B的搜索顺序，在A和B拥有同样差异的情况下，尽管样本块B更符合视觉填充的效果，但B始终被算法所忽略，造成误匹配．针对这种误匹配情况，Anupam算法通过比较匹配块中与待修复块缺损区域对应的部分和待修复块中已知部分平均值的均方误差(Mean Square Error, MSE)来判断填充部分与待修复块已知部分的差异大小，修正选择结果，判断的条件如下所示：

(5)

(6)

其中：fp∈φ∩Ψ表示待修复块已知区域中点p的颜色；#{p|p∈φ∩Ψ}为待修复块已知区域中像素的数量，M为待填充区域中已知颜色的平均值，fp∈φ-Ψ表示待修复块破损区域中的点p在匹配块中对应位置的颜色，#{p|p∈φ-Ψ}表示待修复块破损区域中像素的数量；V表示由匹配块中对应破损区域位置的颜色与待修复块中已知部分的平均值M计算得到的MSE．V越小说明用于填充的颜色均值越接近待修复块已知区域的颜色均值．改进后，当根据式(4)再次搜索到拥有同样差异的样本块时，则继续计算2个样本块与待修复块的差异V，并选择V值更小的样本块进行修复．改进后的修复结果对比如图3所示．

图3 修复结果比较示意图Fig.3 Diagram of the comparison of inpainting results

Anupam算法在修正误匹配、改进修复效果的同时，对修复速度也进行了改进．由于实际情况下最终搜索到的匹配块大多分布在距离待填充块较近的区域，而Criminisi算法采用的全图搜索方式会遍历众多距离较远的区域，存在大量的冗余计算．Anupam算法将Criminisi算法中的全图搜索方式改为局部搜索的方式来减少匹配次数，局部搜索的范围由(startX,startY)和(endX,endY)所给出的矩形框加以限定，其坐标定义如式(7)～(10)所示：

(7)

(8)

(9)

(10)

其中：h和w表示图像的高和宽；m和n表示样本块中包含的列数和行数；Dx和Dy为常量，分别表示搜索范围在X和Y方向上的最小直径；c表示样本块的边长．

与Criminisi算法相比，Anupam算法在修复时考虑了填充部分对修复的影响，所以修复效果更好，同时因为缩小了搜索区域，修复速度得到了明显提升．但是该算法的改进同时也使匹配块的选取更倾向于颜色均值接近的区域，弱化了结构信息对选取的影响，导致在修复结构区域时依旧存在误差．另外经过该算法缩小后的搜索区域，依然含有大量始终未被使用的匹配块，算法的效率仍然有较大的提升空间，尤其当破损区域较大时，通过该算法计算出的搜索区域接近整张图片的大小．

2 基于分水岭分割的快速图像修复算法流程

针对Criminisi算法和Anupam算法在图像修复质量、修复速度上存在的不足之处，本文提出了一种基于分水岭分割的快速图像修复算法，进行了3个方面的改进： 1) 在Anupam算法的基础上利用改进的匹配区域搜索，进一步缩小了搜索区域，加快了修复速度；2) 提出了一种样本块筛选方法，通过分水岭算法对图像进行分割，判断样本块和待修复块是否属于同一个区域，根据筛选结果选择是继续进行匹配运算还是直接忽略该样本块继续寻找下一个样本块；3) 本文利用分水岭分割的结果，提出了一种分类修复纹理区域和结构区域的新的匹配方法来改进Anupam算法在修复结构上的误差．算法的整体流程如图4所示．

图4 Anupam算法和本文改进算法的流程图Fig.4 Flow charts of Anupam algorithm and the proposed algorithm

2.1改进的匹配区域搜索

由于Criminisi算法在修复过程中选中的匹配块大部分集中于修复边界的周围， Anupam算法通过在待修复块周围划定矩形区域的方式缩小搜索区域，达到提升修复速度的目的．但是Anupam算法在划定搜索区域时，为了保证每个待修复块都能找到对应的匹配块，分别使用样本块中心点对应的行和列中的待修复像素数量作为修复区域宽和高的半径．因此对于位于一些图像边缘区域的待修复块，Anupam算法所采用的矩形框会包含大量无用的区域．

为了修复破损区域，首先需要在图像中搜索与待修复块最接近的样本块．由于Criminisi算法采用全图搜索的方式，所以非常耗时．但是根据马尔科夫随机场(Markov Random Filed, MRF)模型的假设，一张图像具有局部统计特征，图像中某一点的特征与其附近的邻域有关，因此可以用局部搜索来代替全局搜索．根据文献[12]中的统计结果，相似块大部分位于破损区域附近，因此本文在Anupam算法的基础上通过改进匹配区域的方法来加速搜索.

图5 改进的匹配区域搜索过程示意图Fig.5 Diagram of the searching process of modified matching area

表1给出了分别使用Anupam算法和本节中改进的匹配区域搜索方法进行修复的耗时对比(原图见图6第一列)．可以看出，本文的改进方法使得Anupam算法取得了40%左右的平均加速比．

表1 2种方法的修复速度和搜索结果的相似比例

为了进一步验证改进的匹配区域对修复质量影响，本文引入文献[13]中的感知哈希值(图像指纹)作为相似性的评测标准，针对每个待修复块，通过同时在Anupam算法的匹配区域和改进区域中分别搜索匹配块并计算对应的哈希值来进行验证．根据标准，如果感知哈希值不相同的数据位数小于5，就说明2张图像相似；如果大于10，就说明这2张图像不同[13]．根据表1中的结果显示，针对同样的待修复块，2种算法选中的匹配块有高度的相似性．由此可以推测出，改进后的加速算法可以获得与Anupam算法基本一致的图像修复质量．图6显示了经过本节算法改进后的修复效果和原算法的结果对比，从图中可以看出改进前后的修复质量基本没有变化．因此改进的匹配区域搜索算法在不影响修复质量的同时可以大幅提高图像的修复速度．

从左至右依次为原图、待修复图、本文实现的Anupam算法结果、本节算法的修复结果.图6 修复结果对比示意图Fig.6 Diagram of the comparison of inpainting results

2.2利用分水岭分割结果的匹配块筛选

由于Crminisi算法在搜索匹配块的过程中会遇到大量与待填充块明显不符合的样本块，为了能够快速地分辨出这些样本块，可以先对图像进行分割操作，将颜色相近的区域用同一种颜色表示，然后在匹配的过程中通过判断是否属于同一颜色区域来快速剔除明显不符合的匹配块．文献[14]提出了一种通过模糊聚类对图像进行分割的算法，但是使用模糊聚类对图像进行分割需要预先设定图像的聚类数目，并且在进行分类的过程中会由于样本集的选取不理想导致分割结果不理想，当存在远离各聚类中心的像素时，由于模糊聚类的约束条件会使得该像素对各聚类的隶属度都相当大，最终影响迭代的结果．此外模糊聚类的计算时间较长，因而不利于实际应用．文献[15]提出了一种通过k- means聚类对图像进行分割的算法，和文献[14]中的改进一样，使用k- means聚类分割图像必须事先指定要生成的聚类数目，而且对选取的初值敏感，对于不同的初值，可能产生不同结果．k- means聚类同样对于孤立的像素敏感，个别孤立像素的存在会极大影响分类结果．

鉴于上述分析，本文基于分水岭分割的结果，提出了一种新的匹配块筛选方法，通过比较分水岭分割结果来筛选掉不合适的匹配块，进一步加快了修复速度．分水岭分割是一个迭代标注过程，该过程首先把图像当作测地学上的拓扑地貌，按灰度对每个像素从低到高进行排序，然后对海拔高度上的局部极小值执行膨胀操作，在膨胀的过程中判断和标注出局部极小值在不同高度的影响域．如图7(a)所示，为了得到2个集水盆间的分水岭，需要对连通区域进行多次膨胀．在每一次膨胀的过程中每个点都必须满足结构化元素的中心只能位于当前连通分量的条件，结果如图中的第1次膨胀边界所示．在下一次膨胀时，由于膨胀边界上的部分像素点造成了不同连通分量的集合聚合，如图中的第2次膨胀边界所示．为了划分出不同的连通分量，这些点就被标记为分水岭[16]．使用分水岭分割图像的好处在于能够在自适应地对微弱边缘做出良好响应的同时，保证分割边界的封闭连续．

图7 分水岭分割图像示意图Fig.7 Diagram of the watershed segmentation image

图7(c)、图7(d)和图7(e)为分别对LENA图(图7(b))使用模糊聚类、k- means聚类和分水岭分割的结果，其中模糊聚类分割耗时4.891s，k- means聚类耗时173ms，而分水岭分割耗时21.499ms，明显优于其他2种算法．从图7(c)～(e)中可以看到，使用分水岭分割得到的结果在整体颜色区域的识别上有着更优秀的效果，既保证集水盆拥有封闭连续的边缘，又保留了图像大致的结构信息，从而为之后分析图像的局部特征提供了可能．为了消除分水岭分割中由于灰度的微小变化产生的过度分割，梯度图像中用于提取图像边缘信息的分割阈值设为20．

在得到分水岭分割结果后，图像被分割成不同的单一颜色区域．之后匹配块的搜索由式(11)加以筛选：

∀Ψafor ∃q：R(p)=R(q),q∈Ψa,p∈Ψp∩φ，

(11)

其中：Ψa表示搜索中有效的候选样本块；R(p)表示待修复块已知区域中的p点在分割图像中包含的颜色区域集合；R(q)表示候选的样本块Ψa中的q点在分割图像中包含的颜色区域集合．通过式(11)的限制，只有搜索到拥有和待匹配块相同颜色区域的样本块才进行误差计算，否则直接忽略该样本块．筛选过程如图8(见第64页)所示，Ω为待修复区域，φ为未破损区域，A、B为不同颜色的匹配区域，中心位于p的方框为待修复块．如图8(a)所示，当待修复块中的颜色只包含区域A中的颜色时，区域B被忽略，只搜索区域A中的样本块；如图8(b)所示，当待修复块中的颜色只包含区域B中的颜色时，区域A被忽略，只搜索区域B中的样本块；如图8(c)所示，当待修复块中的颜色同时包含2种以上的颜色时，只搜索同时包含对应颜色区域的样本块．通过筛选匹配区域，当再次搜索到差异较大的区域时，匹配操作的算法复杂度则由计算欧几里得距离时的O(8n)下降到遍历样本块中颜色种类的O(n)，从而大大节约了修复时间，其中8表示计算欧式距离时每个点需要执行的算术运算次数，n表示样本块中的像素个数．

图8 匹配块筛选示意图Fig.8 Diagram of filtering the matching patches

筛选匹配区域的实例如图9(见第64页)所示，图9(c)中的小方框为待修复块，大方框为按照Anupam算法划分出的匹配区域，本文采用的基于分水岭分割的匹配块筛选，筛选后的匹配区域被限制在图9(d)中的着色部分，因为这个区域的颜色和待修复区域中的颜色相同．通过对比图9(c)和图9(d)，可以看出经过筛选后，需要匹配的区域明显减少．

图9 分水岭分割筛选搜索区域的过程示意图Fig.9 Diagram of the process of narrowing the searching area by watershed segmentation

表2给出了修复耗时的比较．可以看出，与Anupam算法相比，采用分水岭分割结果筛选匹配块的改进方法，可以取得25%左右的平均加速比，明显降低了图像修复时间．当破损区域所跨越的源区域中颜色对比越明显，使用这种方法的加速效果越为突出．图10显示了加速前后图像修复质量的对比结果，可以看出，图像修复的质量基本保持一致．

表2 修复速度比较

从左至右依次为原图、待修复图、Criminisi算法结果、Anupam算法结果、本节算法的修复结果.图10 修复结果对比示意图Fig.10 Diagram of the comparison of inpainting results

2.3利用分水岭分割结果的分类修复

图11 相似块的误匹配示意图Fig.11 Diagram of false match of similar patches

Anupam算法针对Criminisi算法在进行修复时只考虑对已知部分进行比较而造成的误差，提出了一种比较样本块间MSE的改进方法，改进效果如图3所示．尽管该算法在一定程度上解决了相似块的误匹配问题，但是Anupam算法在修复含有结构信息的待填充块时会造成新的误差．产生这种错误主要是因为当样本块间的欧式距离相等时，MSE就成了选取匹配块的决定因素，从而导致了结构信息在修复时出现断裂．如图11所示，当同时存在与待填充块p中已知区域欧式距离相等的样本块A和样本块B时，由于样本块A中存在与待填充块p中已知部分的平均值一致的部分，使得样本块A与待填充块p的MSE较小，导致在修复结构区域时会去选取样本块A来填充，而不是结构上更加一致的样本块B．

在图2中，出现错误匹配是因为没有考虑待填充块中未知区域的纹理信息，而在图11中，出现错误匹配是由于忽略了图像的结构信息，因而得到了错误的匹配结果．为了能够快速分辨待填充块是由单一纹理构成的区域还是包含结构变化的区域，并进行针对性修复，本文提出了一种利用分水岭分割结果的分类修复方法．

由于分水岭算法在区分颜色边缘时具有良好的效果，能够在识别出物体边缘同时，保证识别结果的封闭连续，本文首先根据之前的分水岭分割算法得到一张分割结果，用来快速划分近似的颜色区域．如图12所示，(a)为原图，(b)为待修复图，(c)为经过分水岭分割后的效果，(d)为待修复区域中的2个样本块．其中，(d)中标识为1的样本块为结构变化区域，标识为2的样本块为单一颜色区域．

图12 分水岭分割分类结果示意图Fig.12 Diagram of the results of watershed segmentation classification

在得到如图12(c)所示的分水岭分割结果后，为了分辨出待填充块是由单一颜色构成的纹理区域还是由多种颜色构成的结构区域，首先在分水岭分割结果中找到与待填充块对应的区域并统计其中的颜色数目，当含有多种颜色时，说明该区域内可能存在结构变化，否则是单一颜色的纹理区域．在识别出结构变化的区域之后，为了降低Anupam算法在修复结构时因为均值的引入而造成的误差，本文在式(6)的基础上引入了颜色梯度变化的差异比较来进一步修正匹配的准确度．由于图像的变化情况可以用图像分布的梯度来反应，所以通过比较颜色梯度的变化，能够更加准确地识别出拥有相同结构的区域来进行修复．具体过程如下：

步骤1.首先得到分水岭分割结果，寻找优先级最高的待填充块.

步骤2.在找到优先级最高的待填充块Ψp后，首先按照式(4)计算出d(Ψp,Ψq)，如果同时存在点q和q′使得d(Ψp,Ψq)=d(Ψp,Ψq′)，则使用式(12)和式(13)来进一步分类寻找最匹配的填充块Ψq：

Ψq=argmind′(Ψp,Ψq),

(12)

(13)

式(13)中d′(Ψp,Ψp)为分类匹配后得到的差异结果．为了对填充块Ψp进行有针对性的匹配，本文根据待填充块Ψp在分水岭分割结果中包含的颜色数量来选择相应的匹配方法，具体可分为下列两种情况：

a.如图12(d)的样本块2，当Ψp在分水岭分割结果中只包含一种颜色时，表示Ψp处于单一的纹理区域中．在计算匹配块间距离时，引入V(Ψp,Ψq)做修正．V(Ψp,Ψq)为匹配块间的MSE，计算方式如式(6)所示．V(Ψp,Ψq)越小，说明2个样本块颜色的平均值越接近，越有可能属于同一区域．

b.如图12(d)的样本块1，当包含多种颜色时，表示在Ψp中可能存在结构变化．在计算匹配块间差异时，引入g(Ψp,Ψq)来修正结构区域的修复结果．g(Ψp,Ψq)为匹配块和待填充块中对应的已知部分在颜色梯度上差值的平方和，g(Ψp,Ψq)值越小，说明2个样本块间的结构越接近，反之，差异越大说明2个样本块在结构上差异越大．g(Ψp,Ψq)的计算方式如式(14)所示，其中Rp，Gp，Bp分别表示在RGB颜色空间中利用Sobel算子求得的点p处的颜色梯度，p′为待修复块中的点p在匹配块Ψq中对应的像素点：

(14)

步骤3.在找到最合适的匹配块后，用匹配块中的已知部分对待填充块中缺失的部分进行填充，同时依照待填充块和选中的匹配块的坐标，对分水岭分割图像中的对应部分进行相应的填充．之后更新边界δΩ的优先级并重复步骤1～3来继续寻找优先级最高的待填充块进行修复．

该方法在修复图像的过程中，既保证了同一纹理区域在寻找匹配块时的准确性，同时也保证了修复结构区域时，图像缺失的结构信息得到延伸．修复结果的对比如图13所示，其中图(d)为Anupam算法的修复结果，方框圈出的结构区域出现了明显的误差．而使用本节算法的结果如图13(e)所示，由于在修复时采取了分类修复方法，因此结构区域得到了更好的修复．

图13 修复结果对比示意图Fig.13 Diagram of the comparison of inpainting results

3 实验结果分析

本文所用算法工作均在如下硬件测试平台完成： 操作系统为Ubuntu13.04，CPU为AMD A4- 5000 APU with RadeonTMHD Graphics，主频为1.5GHz．实验中用到的测试图片来自于Berkeley大学的BSR_bsds500测试集和参考文献．

3.1算法耗时比较

表3为Criminisi算法、Anupam算法和本文算法的整体耗时的结果比较．其中第5列给出了本文整体算法改进后的修复耗时．可以看出，经过本文算法的改进，图像修复速度平均提高了40%左右．其中图14(c)由于图像尺寸较小且破损区域占比相对较大，因此按照本文2.1节中改进的算法划分出的区域与Anupam算法划分出的搜索区域接近，加速效果不及其他图标的明显．

表3 3种算法修复耗时比较

但如表3中最后一列所示，第2章中通过第2.1节对匹配区域搜索和第2.2节对匹配块筛选的改进，分别获得了40%左右和25%左右的算法平均加速比，而最终的加速比只在40%左右，主要是因为为更加准确地识别出拥有相同结构的区域来进行后续的修复，本文第2.3节的改进部分在Anupam算法的基础上增加了分类匹配和梯度差异计算，部分增加了修复耗时，因此导致了整体改进耗时没有单独使用2.1节和2.2节的优化修复耗时短．

3.2主观视觉比较

图14为修复结果对比，从图14(a)和图14(b)中可以看出在修复有明显边界区域区分的修复区域时，本文算法在加快修复速度的同时保持了原算法的修复效果．此外，在修复图14(c)中拥有复杂背景的破损区域时，本文算法改进了Anupam算法在结构区域处的修复误差(红框圈出部分)．在修复图14(d)中边界模糊的破损区域时，本文算法同样改进了结构区域处的修复误差(红框圈出部分)．从修复结果中可以看出，经过本文算法修复的破损图片在主观视觉效果上更加自然平滑，图像修复的质量更高．

从左至右依次为原、待修复图、Criminisi算法结果、Anupam算法结果、改进后的修复结果.图14 修复结果对比示意图Fig.14 Diagram of the comparison of inpainting results

3.3客观标准评价

为了更加客观的评价图像的修复结果，本文使用文献[15]提到的峰值信噪比PSNR值(图像在每个颜色通道上的峰值与噪声方差之比，Peak Singal to Noise Ratio)和MSE来衡量图像的修复质量．图15显示了分别使用Anupam算法和本文算法对加入随机划痕后的图片进行修复的对比结果．分别对2种算法结果的PSNR和MSE值进行计算和比较，结果如表4和表5所示．

从左至右依次为原图、待修复图、Anupam算法结果、本文算法结果.图15 修复结果对比示意图Fig.15 Diagram of the comparison of inpainting results

PSNR越高、MSE越小，说明修复图和原图间的差异越小，相应的图像修复的质量也越好．由表4和表5可以看出，本文算法的修复结果优于Anupam算法．

表4 Anupam算法和本文中提出的算法的PSNR结果比较

表5 Anupam算法和本文中提出的算法的MSE结果比较

4 结 语

本文在Criminisi算法和Anupam算法的基础上对传统的图像修复算法进行了改进．首先通过改进的匹配区域搜索算法缩小了搜索区域，使修复的平均耗时缩短了40%左右．进而提出了利用分水岭分割结果筛选匹配块的改进方法，进一步提高了25%左右的修复速度．最后通过利用分水岭分割结果的分类修复算法来改进图像结构信息的修复，改进了原算法在修复结构区域时产生的误差，完整再现了图像缺损部分的精细结构，修复效果更加自然平滑．实验和分析结果表明，较之传统算法，本文提出的基于分水岭分割的快速图像修复算法在平均提升了40%左右的修复速度的同时，有效地提升了图像修复的质量，对于大区域破损图像的修复具有更好的适用性．

[1] BERTALMIO M, GUILLERMO S, VINCENT C,etal. Image inpainting[C]∥Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA： ACM Press/Addison- Wesley Publishing Co, 2000： 417- 424.

[2] CHAN T, SHEN F. Mathematical models for local non- texture inpainting[J].SIAMJournalonAppliedMathematics, 2002,62(3)： 1019- 1043.

[3] EFROS A, LEUNG T. Texture synthesis by non- paramet ric sampling[C]∥Proceedings of IEEE International Conference on Computer Vision. Kerkyra, Greece： IEEE Press, 1999： 1033- 1038.

[4] CRIMINISI A P, PEREZ P, TOYAMA K. Region filling and object removal by exemplar- based image inpainting[J].IEEETransactionsonImageProcessing, 2004,13(9)： 1200- 1212.

[5] CHENG W H, HSIEH C W, LIN S K,etal. Robust algorithm for exemplar- based image inpainting[C]∥Proceedings of the International Conference on Computer Graphics, Imaging and Vision (CGIV 2005). Beijing, China： [s.n.], 2005： 64- 69.

[6] 刘 奎,苏本跃,王一宾.基于样例的图像修复改进算法[J].计算机工程,2012,38(7)： 193- 194.

[7] MASNOU S. Disocclusion： A variational approach using level lines[J].IEEETransactionsonImageProcessing, 2002,11(2)： 68- 76.

[8] CAO F, GOUSSEAU Y, MASNOU S,etal. Geometrically guided exemplar- based inpainting[J].SIAMJImagingSciences, 2009,4(4)： 1143- 1179.

[9] HUI Q W, QING C, CHENG H H,etal. FAST exemplar- based image inpainting approach[C]∥Proceedings of International Conference on Machine Learning and Cybernetics, ICMLC 2012, International Conference. Xi’an, China： IEEE Computer Society Press, 2012： 1743- 1747.

[10] 王昊京,王建立,王鸣浩，等.采用双线性插值收缩的图像修复方法[J].光学精密工程,2010,8(5)： 1234- 1241.

[11] ANUPAM, GOYAL P, DIWAKAR S. Fast and enhanced algorithm for exemplar based image inpainting[C]∥2010 Fourth Pacific- Rim Symposium on Image and Video Technology. Singapore： IEEE Press, 2010： 325- 330.

[12] PARK C, KIM B. Distance weighted bounding for fast exemplar- based inpainting[J].InternationalJournalofSoftwareEngineeringandItsApplications, 2015,9(2)： 143- 150.

[13] KRAWETZ N. Looks like it.[EB/OL]. http：∥www.hackerfactor.com/blog/index.php?/archives/432- Looks- Like- It.html.

[14] 王宇新,贾 棋,刘天阳,等.遮挡物体移除与图像纹理修补方法[J].计算机辅助设计与图形学学报,2008,20(1)： 43- 49.

[15] 朱 霞,李 宏,张 卫.一种基于颜色区域分割的图像修复算法[J].计算机工程,2008,34(14)： 191- 193.

[16] HARIS K, EFSTRATIADIS S N, MAGLAVERAS N,etal. Hybrid image segmentation using watersheds and fast region merging[J].IEEETransactionsonImageProcessing, 1998,7(12)： 1684- 1699.

Abstract： In order to repair damaged image quickly and precisely, an algorithm based on Watershed Transform is proposed in this paper. Based on the results of watershed segmentation calculation, the new algorithm has three aspects of improvements. Firstly, a new method of searching area reduction is used to reduce the cost of patch matching. Secondly, a new filtering method of matching patches is applied to further improve the inpainting speed. Finally, a new method of classification inpainting is proposed to improve the image processing quality. Experimental results show that the algorithm proposed in this paper obtains an improvement of about 40% in run- rate together with a large improvement of inpainting quality as well, compared with the existing algorithm.

Keywords： inpainting; searching area reduction; watershed segmentation; classification matches

AFastInpaintingMethodBasedonWatershedSegmentation

TU Xin, NIU Shengxiao, CHEN Gengsheng, XU Wei

(StateKeyLaboratoryofASIC&System,FudanUniversity,Shanghai201203,China)

TP391

A

0427- 7104(2017)01- 0057- 14

2016- 02- 16

上海市科技创新行动计划(14511108002)

屠 昕(1990—)，男，硕士研究生；许 薇，女，工程师，通信联系人，E- mail： xuwei@fudan.edu.cn.