基于多类标决策树和区域匹配的多源图像修复算法

王嵩，肖娟

（湘南学院计算机与人工智能学院，郴州 423000）

0 引言

图像修复是数字图像处理技术的一项重要内容，核心思想是利用图像中的现有信息来填补破损区域，使修复后的图像满足人眼视觉要求［1］。基于纹理合成的图像修复算法，主要应用于填补待修复图像中存在的较大面积破损，此类算法中比较有代表性的是Criminis等提出的融合纹理合成和Inpainting技术于一体的基于样本块纹理合成的修复技术［2］。在破损区域覆盖多类物体时，此算法修复后往往出现结构失真。很多学者针对此不足，从不同角度提出了一些改进算法［3-5］。

图像修复的过程主要是以图像已知区域的像素信息为参考，恢复出破损区域的信息。前段提及的两类经典修复算法，都需要根据一定的假设前提依靠邻域信息来进行修复。而在信息量缺失过多的情况下，仅依靠图像自身内容进行修复的算法均难以达到理想的效果。针对此类情形，若能找到与待修复图像风格相似的图像，就能够获取额外的信息量，为修复提供指导。因此，多源图像修复将是一个非常有实用价值的研究方向。

本文提出一种基于多类标决策树和区域匹配的图像修复算法。将一幅包含若干内容对象的图像看作具有多个类标的集合，图像中的每个对象归属于一个类标。选取多幅源图像进行均匀划分，得到的每一个图像块作为训练样本，将每一个图像块的颜色和纹理特征提取出来作为样本的属性集，并通过K均值聚类获取每个样本的多类标集，构建具有源图像颜色及纹理信息的多类标决策树；将破损图像中的图像场景块用于测试，提取均匀划分后各图像块的颜色及纹理特征，利用建立的多类标决策树进行分类判定，得到破损图像的类标集；在各个源图像中选择类标集一致的，列为修复的参考源，逐一进行移位区域匹配，筛选最优的内容映射进破损区域；最后修正其色彩信息，使修复后区域与周围环境协调一致。

1 本文算法描述

为了应对具有丰富内容图像的修复问题，利用其他图像作为参考源为修复提供指导已成为必需的手段。一幅图像的内容可分解成多个不同的对象，以风景图像为例，它可能由天空、沙滩、海洋、草地、树木、高山等景物构成。要判断一幅图像的内容，从决策树的角度可以看做是一个多类标问题。由于决策树在这种多类标问题的处理方面的优势，因此可以从多类标的角度出发建立多源图像的多类标决策树。

1.1 多类标决策树的建立

从建立决策树的角度出发，需要提取供训练的样本数据，样本数据的获取及处理可分为以下2个步骤。第一步，确定训练样本集；第二步，确定特征向量。

1.1.1 训练样本集的确定

根据建立决策树算法原理要求训练样本的数量必须超过一定的数值，并且类标要已知同时考虑到多源图像修复的出发点是同种风格图像间场景的互补，由此确立了样本集的基本选取准则：

（1）源图像的选取。选取图像分类检索库中的一些典型的图像，里面包含了风景图像典型景物的组合，满足其类标的合集包含的所有类标，为后续的修复提供指导。

（2）样本图像集的形成。出于算法及实验的需求，为获得足够数量的训练样本，对选取的源图像在横纵方向上进行了均匀的5×5的分割，具体效果如图1和图2所示。最后选取1500个训练样本图像，一部分用于训练，其余的用作测试决策树的预测准确率。

图1 样本图像

图2 5×5区域分割的图像

（3）样本类标的确定。为了确定类标，对上一步得到的1500个训练样本，确定其标准质心，并通过K均值聚类的方法实现计算机自动赋予类标。

在样本类标生成时，如果只考虑图象的lαβ三个分量，通过K均值聚类来确定类标，那么将面临以下问题：海洋和天空均为蓝色，可能会错误的判定为同一类，将会对后续进行修复造成填充异常，所以在决策树样本的训练数据部分还要加入样本的纹理特征，区分相似颜色的不同场景，实施的操作如下：

（1）在颜色信息方面，首先将图像从RGB空间转化到lαβ空间，然后算出经过分块划分后各样本3个分量的均值和方差。

（2）在纹理信息方面，利用灰度共生矩阵提取：

设k（x，y）是大小为M×N的一幅图像，Wg为其灰度级别，其满足一定空间关系的灰度共生矩阵为：

式中，#x代表集合x中元素的个数，H代表Wg×Wg的矩阵，如（x1,y1）到（x2,y2）间的距离为d，两者与横坐标轴的夹角为θ，设∂=(d,θ)，则可通过各种间距及角度的灰度共生矩阵H（i，j），计算下面的4个特征值：

（1）对比度：

公式（2）表示图像的全部像素的灰度差（|i-j|)的平均值，灰度差即对比度大的像素越多，这个值就越大。

（2）纹理一致性：

由公式（3）可知，当H∂(i,j)中有少数值大时，上式的值也大，反映出特定的像素对较多时一致性好。

（3）像素对灰度的相关性：

其中vp和σp表示p的均值与方差。公式（4）的计算结果取值范围在-1～1之间，与∂相关的像素对的灰度值成比例地增大，是描述∂的周期性的模式。

（4）熵：

H∂(i,j)的值分布越均匀，公式（5）的结果值就越大，此式反映的是纹理均衡性的逆性质。

灰度共生矩阵是在灰度图像上进行操作，要确定Wg和d，θ三个参数值，Wg与程序的运算量有关，d,θ与提取特征的有效性有关，一般取d=1，θ以45°为间隔。

以下介绍本算法的具体操作步骤。

第一步，将样本图像灰度化处理，设得到的灰度图像大小为M×N，初始灰度级别为O1；

第二步，将灰度级Wg设定为16，将原始图像转化为16级灰度；

第三步，设d=1，夹角θ=0°,45°,90°,135°，通过公式（1）计算，得到4个方向上Wg×Wg的矩阵H1，H2，H3，H4；

第四步：根据公式（2）—（5）对H1，H2，H3，H4计算上述相应的值，可得到16个特征值。

经过以上四步的计算，将获取每个样本的16个纹理特征值，再与颜色的6个特征值相加，合计共得22个特征值。为便于处理，对得到的这些特征值进行预处理，将其转化为离散数据，并使得其取值为［1，10］的整数值，用作决策树的训练样本数据。

1.1.2 样本类标的确定

彩色图像的任一像素点都可以用三维的颜色矢量lαβ来表示。因此，对图像进行分割可以转化为对颜色矢量集的聚类划分，出于建树的需要对源图像中像素点进行聚类划分，是为了给图像的对应区域确定类标。为保证每幅源图像相似区域赋予相同的类标，采用了如下的K均值聚类算法：

（1）对涉及的各个类标的单一景物图像进行统计分析，提取各个类标的lαβ三个分量特征均值，作为K均值聚类质心的参考。

（2）依据每幅源图像的景物数目确定K值进行聚类，聚类公式采用lαβ三个分量之间的欧氏距离。对于得到聚类区域，根据步骤（1）中的参考参数，根据距离最小准则，对相应的区域赋予类标。

（3）保存聚类后的图像各像素点的类标结果。

1.1.3 多类标决策树算法

针对本文需求要建一棵单值属性的多类标决策树，程序实现部分采用深度遍历的方式，相关的各种关键建树的规则依据SCC_SP算法中的方案SCC_SP_1［6］，在程序调试的时候人机交互调整和修正类标号的支持度Sup（Ci），类标号支持度阀值Supmin，类标号支持度距离阀值Diffmin以及记录最小个数Nummin。调整和修正的原则是需保证树的简洁及预测准确率高。

决策树算法包括构造和预测两个阶段［7］，下面是建立多类标决策树的算法：

●构造阶段：

Constructing（）

输入：训练数据集Train-D。输出：决策树T。

步骤1 初始化树T，将Train-D赋给根结点；

步骤2 如果T的叶子结点都为需要停止的结点，则返回T；

步骤3 对T中不需要停止的结点进行属性选择，并根据选择的属性对该结点进行后继结点的生成；

步骤4 判断后继结点是否需要停止，对需要停止的结点标记其类标集，否则以自身为Train-D，返回步骤2。

●预测阶段：

Predicting（）

输入：测试数据集Test-D。输出：预测准确率P和预测类标集合L。

初始化i＝1，Test-D的记录条数为N。

步骤1 从根节点开始，对于Test-D的第i条记录，按照其对应节点的属性取值，进行树T的遍历，到达叶子节点后，得到该记录的预测类标集，并记录下来；

步骤2 判断i，若i大于N则转至步骤3，否则i++，转至步骤1；

步骤3 计算所获得的全部预测类标集与真实类标集之间的相似度，其相似度的均值即为预测准确率P。输出P和预测类标集合L。

1.2 破损图像类标预测

多源图像的图像修复通常基于如下假设，多幅源图像与目标图像的形状风格基本一致，目标图像中任一对象都可以在参考源图像中找到类似的场景。利用源图像样本块训练得到的多类标决策树对目标图像进行分类决策，得到的结果一方面可以确定目标图像中各图像块的类标，另一方面可以确定目标图像与参考源图像之间的场景匹配程度，后续完成对目标图像空白内容的场景修复。

具体的做法是：将破损图像同样均匀分割成5×5的区域，提取每一区域的颜色和纹理特征值（破损处的信息不予考虑），作为目标图像样本的属性集。利用多类标决策树，对各个区域进行决策，确定其类标。将各个区域的类标集汇总，与各个源图像进行比较，类标集完全一致的即可看做为修复的源图像。

1.3 区域匹配

搜索到类标完全一致的源图像后，将破损边界线靠外20个象素点宽的区间定义为匹配带，将整个破损区域连同匹配带区间整体作为掩模，在源图像中进行移位匹配，匹配公式如下：

其中F表示的是掩模内的已知像素点，F′对应源图像中与F掩模空间位置相对应的像素点，M为已知像素点的数目。

将移位匹配计算得出的最小距离所对应的源图像掩模所覆盖的场景整块填充完成修复。

1.4 色彩修正技术

在完成区域匹配修补之后，新填充的内容与原始场景在色彩上可能会有差异。为了使修复结果更加自然，采用一种基于聚类的色彩修正算法。

基于聚类的色彩修正算法步骤如下：

第1步，提取修复区域所有像素点的lαβ值利用K均值算法聚成M类（根据修复区域面积的大小及场景色彩丰富程度，M可取值3，4，5，6）。

第2步，分别计算M类中各包含所有象素点的α、β均值和方差，记为μ1α（m），μ1β（m），δ1α（m），δ1β（m），其中m=1～M，并统计各类别中象素点的个数，记为num1～numM。

第3步，以聚类结果建立分类器，对破损图片原有场景象素点进行K近邻分类，并统计各类别中象素点个数,记为num21～num2M。以及各类别中,α、β均值和方差μ2α（m），μ2β（m），δ2α（m），δ2β（m），其中m=1～M。

第4步，对新填充场景中属于第m类的象素点进行色彩映射，映射公式如下，其中m=1～M。

2 实验结果分析

为验证本文算法的有效性，在Intel i3-4150 CPU和4 G内存的PC上，以Matlab 2012为平台进行仿真实验。实验的图片是从文献［8］提供的网址链接下载，共下载了2700幅256×256像素的各类自然图像。选择了其中的300幅图像作为参考源图像。并另选择了60幅图像随机构造了大面积的破损。每幅图像的平均修复时间为37秒。包含了多类标决策，区域匹配及色彩修正。

2.1 建立决策树的结果

根据SCC_SP算法建立的多类标决策树，树的规模和精确度得到合适的控制。实验结果表明：树的节点在5～8个时运算效率高。

2.2 修复结果与分析

图3为山岩树叶图，图3（a）为其原始图像，图像中有蓝天，黄绿树枝叶和灰白山岩及树阴影。图3（b）为破损图像，其破损区域为图像中最复杂的三景交汇处，在破损的区域里即有蓝天、灰白山岩又有黄绿树枝叶。图3（c）为与破损区域的类标集相近的源图像。图4为油菜花田图，图4（a）为其原始图像，图像中有天空，绿树，大片黄色油菜花田。图4（b）为破损图像，其破损区域为天空与油菜花田的交汇处，场景包括天空，绿树与黄色油菜花田。图4（c）为与原始图像破损区域的类标集相近的源图像。图5为树林图，图5（a）为其原始图像，图像中色调比较单一绿色的大树与绿色的草地。图5（b）为破损图像，其破损区域为一部分绿树与草地。图5（c）为与原始图像的类标集相近的源图像，其主要场景也是绿树与草地。图6为海面图，图6（a）为其原始图像，图像中有灰蓝色的天空，海岸及大片蓝色海面。图6（b）为破损图像，其破损区域为天空与海面交汇处，主要破损的区域是海岸部分，与图3、图4、图5矩形破损区域比较其破损区域为不规则破损。图6（c）为与原始图像破损区域的类标集相近的源图像，其主要场景也是天空与海岸及海面，色调也与原始图像相近。

图3 山岩树叶修复图

图4 油菜花田修复图

图5 树林修复图

图6 海面修复图

图3（d）、图4（d）、图5（d）、图6（d）都是将各图中（c）源图像中与破损区域类标集最接近的区域块位移填充进（b）破损图像中的结果，从各图（d）区域匹配结果可以看出，图像色调及场景大致匹配但是在破损区域的边缘都存在一定的不协调。

针对各图（d）中区域匹配不协调的结果，利用基于聚类的区域颜色映射算法对填充后不一致的色彩进一步的修正，修正后的结果如图3（e）、图4（e）、图5（e）、图6（e），从色彩修正结果可以看出各图修复后的色彩与场景都比较自然，符号人眼视觉要求，修复效果佳。

3 结语

以源图像中的图像块作为训练，提取其颜色、纹理特征，建立多类标决策树；利用多类标决策树对破损图像进行分类，找到修复源图像来实现对目标图像的修复。该算法对于包含复杂对象物体的目标图像具有较好的修复效果，弥补了单源图像修复算法参考信息不足的缺点，同时为同风格图像的批量修复提供了新的借鉴和参考。下一步的工作考虑建立具有同风格类型图像的类标库，增加类标的多样性，从而建立基于该风格特征图像的多类标决策树，提高决策树对图像的分类精度，增强图像修复后结果图像的细节部分修复效果等。