纹理结构引导的自适应图像修复算法

郑晚秋，廖胜辉

(中南大学 信息科学与工程学院，湖南 长沙 410083)

纹理结构引导的自适应图像修复算法

郑晚秋，廖胜辉

(中南大学 信息科学与工程学院，湖南 长沙 410083)

利用约束纹理合成的方法来解决大面积缺损图像的修复问题，可以在视觉上获得比较好的效果。而修复过程中的合成顺序，对最后的结果有很大影响。Criminisi提出的基于样本图像的图像修复算法，在前人基础上，对合成顺序给出了解决方案。文中首先对决定合成顺序的优先级进一步做了改进，在数据项中加入结构张量，使图像修复从结构区域向无结构区域填充。其次，根据原图像区域纹理结构信息，使得每一次合成的块的大小自适应变化，这在一定程度上避免了纹理块过小或过大带来的弊端，从而使合成效果更为自然。经过对比实验，文中算法取得了较好的效果。

图像修复；纹理合成；结构张量；自适应

0 引 言

图像修复技术，是指针对图像中缺损的部分，根据图像中完好部分的结构和纹理信息，按一定方法进行填补的技术。早期，一般利用偏微分方程法来进行图像修复，采用的思想是扩散机制，典型的有基于高次偏微分方程的BSCB模型[1]、基于变分泛函的TV模型[2]和CDD模型[3]。文献[4-5]分别利用TV模型和CDD模型针对西藏壁画进行了图像修复。上述方法在原理上存在着固有的局限性，对于小面积的图像缺失效果显著，但是对大尺度破损区域的修复易产生模糊。

图像修复的实质思想是利用图像中已知的图像信息，对缺失信息进行填充或替换，这与纹理合成的思想有着异曲同工之妙。实际中多采用的是基于块拼接的纹理合成。文献[6]通过混沌变换得到合成纹理，Efros提出了一种Image Quilting的纹理合成方法[7]。文献[8]由于在纹理合成中应用了Graph Cut算法，因此，合成过程中的纹理块不再局限为矩形，可以是任意形状。

在有缺损的图像上，可以将缺损部分看成待合成区域，完好的部分看成是样本，这可以称为约束纹理合成。通常采用的顺序是扫描线顺序，但是这种顺序没有利用纹理特征，难以得到更加优良的效果。

2004年，Criminisi等受CDD模型[3]以及关于人类视觉相关研究[9]的启发，首次对基于纹理合成图像修复的合成顺序给出了包含置信度和数据项的优先级公式。只是其在修复过程中欠缺鲁棒性，容易将纹理部分和边缘部分混淆，从而导致修复顺序的错误偏差。文中采用结构张量对优先级数据项进行了改进。

在以块为单位进行拼接的纹理合成过程中，块的大小对合成效果也有很大的影响。如果单元块小于纹理单元，则可能会破坏结构信息；如果单元块比纹理单元大太多，又可能导致合成效果模糊[10]。而现实中的图像纹理结构通常是不规则的，所以文中根据图像结构信息在合成过程中自适应地改变单元块的大小。

1 基于纹理合成的图像修复算法

1.1 纹理合成算法

基于样图的纹理合成技术，可以依据给定的小块样本纹理，生成新的大块纹理图案。它根据小面积样图的纹理特征，生成大面积的曲面纹理，并使得合成的纹理具有连续性以及非重复的相似性。二维图像的纹理合成，针对处理基本单元分类，可以分为基于像素点以及基于纹理块的纹理合成两种。在纹理合成中以像素点为单位，不仅速度慢，而且会严重破坏纹理结构；以纹理块为单位提高了合成效率，并且能够更好地保持纹理图像的结构特征。以经典算法Image Quilting[5]为例，简要介绍基于块的纹理合成的思想。该算法按照扫描线的顺序进行纹理合成，合成过程中的基本单元为固定大小的纹理块，每次在样本纹理图像中，选取与输出纹理图末尾重叠区域像素值的累计误差最小的纹理块添加到已合成纹理块中；同时，对早先合成和新合成纹理块的重叠区域进行接缝处理。

1.2 约束纹理合成

基于样本的纹理合成算法可以用来合成任意大小的与样本类似的纹理图像，同时，也可以用来进行纹理图像的缺失块修复[11]。比如有时照片或其他图像上可能会包含一些在感官上有缺陷的区域，也可能是在扫描照片时出现了模糊区域，或者是图片上存在不想要的物体，想要将多余的物体移除而又不想影响整幅图像的完整性，这时可以利用基于样本的纹理合成的方法来进行修复。只需把图像中完好部分看作是纹理图像样本，把缺失区域看作待合成目标块，可以用扫描线顺序进行修复。由于是在限定范围内进行纹理合成，所以称为约束纹理合成。不过简单的机械式的修复顺序，很可能造成修复效果不佳。因此，需要对约束纹理合成算法进行相关的改进，比如在合成过程中采用可变大小的样本块以及改善合成顺序等。

1.3 Criminisi算法

Criminisi等于2004年提出了一种采用纹理合成思想的图像修复算法[12]，主要对图像修复中的合成顺序作了比较大的改进，获得了不错的合成效果。

该算法主要分为以下三个步骤：

1)计算待修复块的优先权重。

优先权的计算关系到图像修复的顺序，是该算法的关键。对于待修复边缘上的每一个像素点，都设定一小块以该像素为中心的区域，优先权最大的目标块最先进行修复。优先权的大小由两个因素决定：(1)目标块内像素的置信度大小；(2)目标块中心点周围结构信息的强弱。示意图如图1所示。

图1 Criminisi算法示意图

图中，Ω表示待修复区域；∂Ω表示其边界轮廓；Φ表示已知区域。

对于以轮廓上的点p为中心的目标块，其优先权定义为：

P(p)=C(p)•D(p)

(1)

其中，C(p)表示已知像素在目标块中的比例，称之为置信度项；D(p)表示p点沿着等照度线方向到达边界点的强度量化函数，称之为数据项。

分别定义如下：

(2)

(3)

其中，Ψp表示目标块的大小；C(q)表示目标块中已知像素点的个数；np为垂直与边缘线∂Ω上p点的法向量；为点p的等照度线的方向和强度；α为归一化因子。

2)搜索最佳匹配块并填充。

(4)

传统基于块的纹理合成计算指定宽度区域的SSD，是为了找到最佳接缝路径。而此算法中，由于修复顺序打乱，不再是规则地拼接，故计算两个块区域的SSD，直接利用最佳匹配块的对应位置对目标块缺失部分进行复制填充。

3)更新待修复边缘的优先权。

完成第二步后，目标块内的未知像素点变为已知像素点，边界点发生了变化，需要将待修复区域边缘的优先权进行更新，对于将新加入的已知像素，姑且将其置信度设置为与刚刚处理的p点相同。然后，再读取位于边界上的像素点，确定下一个优先级最高的像素点p，再次执行一次目标块的合成。如此循环，直至存储边界点的链表为空。

2 结构张量引导合成顺序

为了使合成效果更加满足视觉要求，需要重点抓住人类感知敏感的内容。人类视觉对纹理中的结构信息更加敏感，简单来讲，要获取像素点处的方向信息，只需计算该点处的梯度向量即可。然而，仅仅通过单个像素点计算得到的梯度向量，不足以表示图像的局部结构特性。通过计算结构张量，可以获得更加丰富的局部结构信息。根据结构张量能够识别图像中的边缘、角点以及平坦区域。借助结构张量的图像处理应用广泛，文献[13]基于广义结构张量进行了虹膜分割算法的研究，文献[14]则利用结构张量进行了变分多源图像融合。

最初，由DiZenzo[15]和Förstner[16]先后提出了结构张量的定义，并将其融入了实际应用。

首先定义图像I的梯度为：

(5)

式中，Ix、Iy分别为x、y方向的偏导数，Ix=∂xIσ，Iy=∂yIσ。其中，Iσ=Gσ*I，里面的*是卷积算子，此操作在上述的求导运算中，具有抗噪声作用，可以提高算法鲁棒性。

初始张量内积Υ0的定义如下:

Υ0=I•

(6)

其中，u12=u21；•是笛卡尔内积(CartesianProduct)。

由此可知，矩阵Υ0对称且半正定。

下面通过公式对Υ0的特点进行进一步的分析：

(7)

(8)

从上面的推导公式可见，图像的边缘强度大，可以量化为Υ0较大的特征值；而边缘的梯度方向，可以用数学表示为Υ0的特征向量。

鉴于仅仅利用单个像素点的梯度向量来获取方向信息，不足以表示图像局部特性，因此，选择利用结构张量来进行完善。通过对结构张量Υ进行深入剖析，不仅可以得到图像中更为细致的局部结构特征，而且还能够获取像素点邻域内结构特征的各向异性等更加丰富的信息。

为提取结构相关信息，对Υ进行如下的主轴变换(principalaxistransformation)：

(9)

其中，Λ=diag(λm)的对角元素是Υ的特征值，称之为对角矩阵，组成矩阵S的各行向量即为Υ的特征向量γ1、γ2，其中γ2⊥γ1。

(10)

(11)

其中，γ1表示边缘的法向，γ2表示边缘的切向，并且γ1可由下式计算得到：

(12)

另外，结构张量Υ的迹可以表征结构强度St，即

St=trace(Υ)=Υ11+Υ12=λ1+λ2

(13)

而2D图像数据的相干性(coherence)H通常由下式表征：

H=(λ1-λ2)2

(14)

基于上述公式进行进一步分析，从而通过结构张量Υ得到目标图像的数字化的局部结构特征描述。

假设导数的加权期望值Ex(Ix)=Ex(Iy)=0，则有：

(15)

从式中可以看到，结构张量可以近似为两个偏导数的联合分布，又由于协方差矩阵对称正定，可知结构张量有两个特征值且均为非负数，在几何意义上，特征值可以用来表示椭圆主轴的长度，则其相应的特征向量可用来描述主轴方向。

基于上述几何意义，目标图像的局部结构信息可以根据特征值分三种情况进行讨论：

(1)λ1≈λ2≈0。这种情况表示结构强度St以及相干性H都很小，此时在图像中该像素点附近，无论沿着任何方向，像素的灰度值变化都不大，因此，可以判定为平坦区域。

(2)λ1≫λ2≈0。这种情况表示结构强度St以及相干性H都比较大，此时图像中该像素点附近，沿某一方向的变化率远大于沿垂直于此方向的变化率，表现出明显的边缘特征，可以判定为边缘区域。

(3)λ1≈λ2≫0。这种情况表示结构强度St大而相干性H较小，此时图像中该像素点附近，沿着两个互相垂直的方向，像素灰度值变化都比较快，可以判定为角点区域。

在上述定性分析的基础上，进一步利用结构张量Υ的特征值λ1和λ2来对目标图像的局部结构信息进行定量分析：

(1)边强度，即方向一致性信息量：

E=(λ1-λ2)2

(16)

(2)角强度，即角点信息量：

C=(λ1•λ2)/(λ1+λ2)

(17)

于是，为得到从结构区域向无结构区域填充的效果，将图像的局部结构测度纳入决定优先权因素之一的数据项中。

(18)

其中，α为归一化因子。

同时，优先权公式修改为：

P(p)=mC(p)+nD(p)

(19)

其中，m、n分别为C(p)和D(p)两项的权重，根据具体的图像进行调整。

3 自适应纹理块大小

现实中纹理图像中所包含的纹理元通常是多种多样的。在合成过程中，如果每次合成都采用相同大小的合成块，就会引起纹理块尺寸选择不当的问题。纹理块选择过小会破坏纹理结构，纹理块选择过大则会引起边界模糊以及不连续的问题。因此，需要对图像局部特征进行研究，以解决纹理块尺寸动态选取的问题。

仅仅提取图像的一阶微分量——梯度，不足以表征图像的结构特征；随着研究的深入，发现通过提取二阶微分量可以得到更为丰富的图像结构信息。其中，二阶微分量中的等照度线的曲率，作为等照度线形态学特征的一个非常重要的描述，在很大程度上反映了目标图像的形状信息[17]。曲率的倒数就是曲率半径，曲率半径在一定程度上可以反映纹元的大小。

假设图像u(x,y)在任一像素点处有一条等值线，其灰度值为C(常量)，则该等值线可以表示为u(x,y)=C。

其中，纵坐标y可以看作自变量为横坐标x的函数，方程两边同时对x求导可得：

ux+uyy'=0

(20)

计算得到该等值线上纵坐标对横坐标的一阶导数：

y'=-(ux/uy)

(21)

下面进一步计算纵坐标对横坐标的二阶导数，再对式(21)两边同时对x求导：

(22)

将计算所得一阶和二阶导数带入下面的曲率公式：

(23)

由此，便得到了图像二元函数，在任意像素点的等照度线的曲率表达式为：

(24)

(25)

其中，w为可调参数。

4 实验结果

文中对图1～6分别进行了修复实验，并且将修复效果与Criminisi算法修复结果进行对比，证明了文中算法的有效性。

图2 大理石修复图

在图2(c)中，Criminisi算法进行大理石修复时，图像纹理结构出现紊乱现象；如图2(d)所示，文中算法在一定程度上对纹理结构的处理更好。

在图3(c)中，利用Criminisi算法修复时，纹理结构边缘出现变形缺陷；如图3(d)所示，文中算法由于合成顺序更为合理，虽然边缘稍有毛刺，但是实现了图像的较为理想的修复。

图3 花朵修复图

在图4(c)中，Criminisi算法修复时，出现了很明显的边界断层和参差不齐的现象；如图4(d)所示，文中算法由于合成时采用自适应大小的纹理块，同时合成顺序更加合理，比较有效地解决了图像修复中的层次不连续的问题。

图4 田野修复图

在图5(c)中，原Criminisi算法修复时造成了图像结构的紊乱，修复效果非常不理想；如图5(d)所示，文中算法在修复中图像的整体结构性没有受到损坏，有较好的视觉效果。

图5 湘江岸边修复图

在图6(c)中，Criminisi算法修复时，单一大小的修复块不能保持纹理的连续性，使得修复结果的纹理严重失真；如图6(d)所示，文中算法进行修复时，根据图像特点选择相对合适大小的纹理模板块，同时优化了合成顺序，合成效果有了显著的改善。修复结果中的小瑕疵，可以利用滤波[18]等方法进行完善。

图6 眼睛修复图

5 结束语

文中采用了纹理合成的思想，来解决大面积缺损图像的修复问题。在Criminisi修复算法的基础上，利用结构张量对决定合成顺序的优先级做了进一步的改进，同时，在合成过程中，根据纹理结构信息自适应地改变纹理模板块大小。实验结果表明，算法优先保证了结构信息的合理填充，较好地保持了修复边界的完整，在一定程度上解决了图像修复的纹理断层现象，获得了比较好的视觉效果。下一步关键性的改进是：在寻找最佳匹配块时，进行旋转不变特征匹配，然后进行相应的复制合成。

[1]BertalmioM,SapiroG,CasellesV,etal.Imageinpainting[C]//Proceedingsofthe27thannualconferenceoncomputergraphicsandinteractivetechniques.Anaheim,USA:ACMPress,2000:417-424.

[2]ChanT,ShenJ.Mathematicalmodelsforlocalnon-textureinpaintings[J].SIAMJournalonAppliedMathematics,2002,62(3)：1019-1043.

[3]ChanTF,ShenJ.Non-textureinpaintingbycurvature-drivendiffusions(CDD)[J].JournalofVisualCommunicationandImageRepresentation,2001,12(4)：436-449.

[4] 姜 军,卓 嘎,王朝霞,等.以TV模型为例的西藏壁画数字图像修复技术研究[J].电子技术工程，2013,21(3)：136-139.

[5] 姜 军,王龙业,王朝霞,等.基于CDD模型的西藏壁画数字图像修复技术研究[J].电子设计工程，2014,22(2)：177-179.

[6]XuY,GuoB,ShumHY.Chaosmosaic:fastandmemoryefficienttexturesynthesis[R].[s.l.]:MicrosoftResearch,2000.

[7]EfrosAA,FreemanWT.Imagequiltingfortexturesynthesisandtransfer[C]//Proceedingsofthe28thannualconferenceoncomputergraphicsandinteractivetechniques.Anaheim,USA:ACMPress,2001:341-346.

[8]KwatraV,SchodlA,EssaI,etal.Graph-cuttextures:imageandvideosynthesisusinggraphcuts[J].ACMTransactionsonGraphics,2003,22(2)：277-286.

[9]KanizsaG.Organizationinvision[M].NewYork:Praeger,1979.

[10] 孟春芝,何 凯,焦青兰. 自适应样本块大小的图像修复方法[J].中国图象图形学报，2012，17(3)：337-341.

[11] 苏良飞.基于样图的约束纹理合成研究[D].杭州：浙江大学，2008.

[12]CriminisiA，PerezP，ToyamaK.Regionfillingandobjectremovalbyexemplar-basedimageinpainting[J].IEEETransactionsonImageProcessing,2004,13(9)：1200-1212.

[13]Alonso-FernandezF,BigunJ.Irisboundariessegmentationusingthegeneralizedstructuretensor[C]//ProcofIEEEfifthinternationalconferenceonbiometricscompendiumbiometrics.[s.l.]:IEEE,2012:426-431.

[14] 许 娟,孙王宝,韦志辉.基于结构张量的Non-LocalMeans去噪算法研究[J].计算机工程与应用，2010,46(28)：178-180.

[15]Di-ZenzoS.Anoteonthegradientofamulti-image[J].ComputerVision,Graphics,andImageProcessing,1986,33(1):116-125.

[16]FörstnerW,GülchE.Afastoperatorfordetectionandpreciselocationofdistinctpoints,cornersandcentresofcircularfeatures[C]//ProceedingsofISPRS.[s.l.]:[s.n.],1987：281-305.

[17] 雷文娟,祝 轩,贾义亭,等.梯度与曲率变形力相结合的图像配准方法[J].计算机工程与应用，2012,48(5)：204-206.

[18] 徐 勇.边缘结构保持型的图像滤波算法研究[D].合肥：合肥工业大学，2011.

Adaptive Image Inpainting Algorithm Based on Texture Structure

ZHENG Wan-qiu，LIAO Sheng-hui

(College of Information Science and Engineering,Central South University,Changsha 410083,China)

Taking into account the large defect area of images，the constrained texture synthesis is used to image inpainting.The filling order is important because it has a great influence on the final result.Based on the previous studies,Criminisi algorithm gives a solution to the filling order.Firstly,an improvement is made on the priority of the filling order in this paper.Structure tensor is added to the data term in order to make the filling order is from the structural region to the non-structural region.Secondly,according to the texture structural information,it makes the size of template block change adaptively.To some extent,it avoids the disadvantages caused by the block of fixed size,so that the result is more natural.The contrast experiment shows that the algorithm obtains better visual appearance.

image inpainting；texture synthesis；structure tensor；adaptive

2015-09-08

2015-12-11

时间：2016-05-25

国家自然科学基金资助项目(60903136)

郑晚秋(1991-)，女，硕士研究生，CCF会员，研究方向为图形图像处理；廖胜辉，副教授，硕士研究生导师，研究方向为计算机图形学、生物仿真建模、医学图像处理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1706.030.html

TP301.6

A

1673-629X(2016)06-0040-06

10.3969/j.issn.1673-629X.2016.06.009