纹理图像中重复纹理元素提取方法*

杨弄影，李　峰，桂　彦长沙理工大学 计算机与通信工程学院，长沙 410114

纹理图像中重复纹理元素提取方法*

杨弄影，李峰，桂彦+
长沙理工大学 计算机与通信工程学院，长沙 410114

YANG Nongying,LI Feng,GUI Yan.Repeated texture elements extraction from texture images.Journal of Frontiers of Computer Science and Technology,2016,10(8):1154-1165.

摘要：提出了一种交互式纹理图像中纹理元素提取算法，该算法能够在用户提供少量交互的情况下较好地实现纹理图像中重复纹理元素的同时提取。首先采用均值漂移聚类算法将纹理图像分割成独立且连通的子块区域，并构建图像子块区域之间的连通关系；然后结合颜色特征与纹理特征定义一个鲁棒的相似性度量公式，从而准确地捕获具有外观相似特征的纹理元素；在此基础上，通过进一步改进优化的图割模型，最终实现高质量的纹理元素提取。该算法针对前/背景颜色相近的纹理图像中纹理元素的提取有较大改善，并且大大提高了现有图像分割算法的时间效率。

关键词：重复纹理元素；纹理特征；相似性度量；图割模型

1　引言

重复元素在自然场景或人工场景中是普遍存在的，而这种重复特性在纹理图像中尤为显著。纹理图像的背景通常比较单一，且重复出现的纹理元素在颜色、形状、大小和纹理等特征上具有一定的相似性，即在外观上易于分辨。从这类纹理图像中提取感兴趣的目标对象（如重复出现的纹理元素），较为常用的处理方式是采用图像分割技术分割这些感兴趣区域。

近年来，虽然一些新的交互式图像分割技术[1-7]已经实现了重复场景元素的同时提取，但是这些方法仍然不能较好地用于纹理图像的处理。其中，文献[5]中的方法仅适用于同时提取与背景具有较大颜色差异的目标前景区域。因而，当纹理图像中存在纹理元素种类繁多，纹理元素之间颜色差异大或存在渐变，图像前/背景颜色相近似等复杂形态时，该方法获得的纹理元素提取效果往往较差。而仅采用基于形状特征匹配的方法[4]只能够提取出与用户所选模板具有相似轮廓的纹理元素。因此当纹理图像中纹理元素之间存在遮挡或形变严重时，该方法产生的纹理元素提取效果亦不理想。因此，对于交互式图像分割方法的改进仍然是必要的：一方面，用于进行外观相似性度量的方式较单一，导致这些方法在使用上存在较大的局限性；另一方面，现阶段对于纹理元素的提取主要是应用于纹理图像的编辑与处理，包括纹理合成与设计、纹理转移等，然而现有基于样图的纹理合成方法[8-11]在处理这类具有大量纹理元素的纹理图像时，无法保持合成的纹理结果中纹理元素的完整性，以致产生不连续或断裂的纹理结构。虽然现有基于基元分布的纹理合成方法[12-14]解决了这一问题，但这些方法往往需要耗费大量的时间用于纹理元素的提取，从而极大地降低了纹理合成的效率。因此，如何快速地提取纹理图像中的纹理元素已成为纹理图像编辑与处理技术中亟待解决的关键问题，这也为本文的研究提供了新的思路与突破点。

本文提出了一种高效的交互式纹理图像中纹理元素的提取方法。通过建立一种鲁棒的外观相似性度量机制，从而能够更精确地捕获纹理图像中重复的纹理元素；在此基础上进一步优化现有图割模型[5,15-17]，通过对纹理图像中重复纹理元素的同时提取，极大地提高了纹理元素提取的时间效率，从而为纹理图像的编辑与处理进一步奠定了良好基础。

2　相关工作

图像分割是图像处理领域的研究热点之一，即通过将图像中的目标对象与背景内容分离，来达到提取感兴趣区域的目的。现有图像分割技术主要分为两大类：自动的图像分割方法[18-21]和交互式的图像分割方法[1-7,15-17,22-24]。虽然自动的图像分割方法操作简便，且自适应性能强，但是交互式的图像分割方法普遍准确率更高，并且具有主观能动性，能更好地满足用户分割图像的要求。因此，本文主要侧重于研究交互式的图像分割技术。

2001年，Boykov等人[15-17]提出了Graphcut算法，该方法构建了一种基于联合概率分布的计算模型，并通过图的最大流/最小割（max flow/min cut）算法解决能量的最优化问题，因而具有良好的分割性能。2004年，Rother等人[22]提出了一种更加优化的图割算法（Grabcut），该方法将前/背景建模为RGB三通道的高斯混合模型（Gaussian mixture model，GMM），并通过迭代求解最佳能量划分，从而使得分割效果更加优化。同年，Li等人[23]提出了一种“懒人”抠图方法（LazySnapping），该方法在Graphcut算法基础上，用多边形描绘目标对象的边界，并对多边形的节点通过拖拽的方式加以调节，从而极大地提高了图像分割的精准度。2010年，Gulshan等人[24]提出了一种新的基于形状约束的交互式图像分割算法，该算法通过扩充凸面上的星型先验图的概念，从而使得用户仅通过选中凸面中心点的少量交互即可精准地获得目标凸面。同年，肖春霞等人[25]提出了一种有效的边缘停止函数，该函数采用多尺度图像增强，并通过高斯混合模型进行颜色匹配以引导level set函数演化，从而使得level set能精确地分割出目标对象的边缘。2011年，赵在新等人[26]提出了一种基于活动轮廓的双纹理图像分割算法，该算法通过结合半局部的方向性与非线性结构张量构造4通道纹理特征，从而能够自适应高效地实现复杂双纹理图像的分割。2013年，张会等人[27]提出了一种基于颜色和纹理的显著性区域提取方法，该方法通过将原图像的L、a、b三通道转化为亮度图像，综合亮度图像中Gabor滤波器产生的4个方向的纹理图与Lab图，从而有效地提取出输入纹理图像中的显著部分。

然而，上述图像分割技术[15-17,22-24]与纹理分割方法[25-27]仅适用于对图像中的某一个感兴趣目标对象进行提取，如若提取图像中的多个感兴趣目标对象，例如在本文待处理的纹理图像中存在的大量重复的纹理元素[28]，则需要用户逐一地进行处理。此时，不仅需要用户提供大量的人工交互，导致分割效率低下，而且不一定产生高质量的纹理元素提取结果。因此，如何通过少量的用户交互达成多个目标对象的同时提取已成为图像分割领域新的研究热点。

1996年，Leung等人[1]提出了一种重复场景元素检测、定位算法，该算法通过估计用户交互的图像子块与相邻图像子块之间的仿射变换，将相似的图像子块扩张成为一个更大的连通域，从而达到快速聚类重复场景元素的目的。2004年，Liu等人[2]提出了一种基于周期方向感知计算模型的纹理分割算法，该算法通过自动识别周期方向图中的对称元素，提取其中的基础单元子块，从而能够自动地检测纹理元素。2007年，Ahuja等人[3]提出了一种同时提取2.1D自然重复场景元素的算法，该算法将具有相似结构的可视纹理元素部分表现为子树的形式，建立光学与几何学的联合树学习模型，并匹配学习模型与原图像的分割树，从而较好地处理了2.1D自然场景元素的遮挡问题。2010年，Cheng等人[4]提出了一种基于边界带图的重复元素检测算法，该算法通过用户选定模板，并逐一匹配模板与待检测区域的边界带图，从而能够检测出具有一定程度遮挡或不完整的重复场景元素。2011年，Huang等人[5]提出了一种基于优化的图割模型的重复元素提取算法，该算法通过度量像素点之间的相似性，并在图中建立连接相似重复元素的边来改进经典的图割模型，从而能够实现重复场景元素的同时提取。2012年，Zhang等人[6]提出了一种使用半自动图像编辑框架的重复元素检测算法，该算法采用对象级操作，并利用重复元素的外观曲线相似程度对其进行分割，从而顺利解决了提取过程中不同层面上重复元素的遮挡问题。2013年，Xu等人[7]提出了一种综合考虑空间距离、取样位置和外观特征的稀疏控制模型，该模型以最佳的方式解决了稀疏控制带来的歧义性，能够广泛应用于用户交互工作的引导，从而大大降低了交互的复杂度。

虽然上述方法均能不同程度地实现自然场景中重复元素或纹理图像中纹理元素的提取，但是仍没有一种方法是通用的，即能够很好地处理具有各类复杂场景的图像。因此，在改进现有图像分割方法进行重复元素提取时，如何获得高质量的提取结果以及如何提高算法的时间效率依然是图像分割的一个重要研究方向。

3　优化的图割模型

经典图割算法Graphcut将原图像表示为图G=(P,N)，如图1（b）所示。其中P为以像素点为节点的点集，N为连接像素点的边的集合，s和t分别代表源端点和终端点。图G中每一条边都附有相应的权值，且边的权值表示节点之间的差异。另外，图G中每一个节点都与s点和t点相连接，且边的权值为无穷大。

Graphcut算法将图像分割转换为图的最优划分问题，根据图G定义马尔科夫随机场（Markov random field，MRF）能量公式E，并获得使能量公式E最小化的标签分配方案。此时，图中的每一个像素点都取得了一个“0”或“1”的标签。其中，标签“1”表示将该像素点标记为前景，否则反之。由此，该算法根据获得的标签将图像I划分为前景与背景，即实现图像的最优分割。

Fig.1　Illustration for graph cnstruction图1Graph构建示意图

MRF能量公式E(f)定义如下：

其中，Dp为数据项，用于度量像素点p与标签 fp的一致性，通常来源于先验信息；Vp,q为平滑项，用于度量相邻像素点p与q之间的标签过渡平滑性；fi∈{0,1}为像素点i的标签。

Graphcut算法能够较好地处理单个目标对象的分割问题，主要是由于平滑项约定p与q的距离仅为相邻像素点之间的空间距离（通常取4-连通或8-连通邻域）。由此，当原图像中出现大量重复场景元素时，该图割算法则需要用户对目标对象逐一地进行交互，这在增加用户输入工作量的同时，也降低了图像分割方法的时间效率。

针对Graphcut算法在图像分割中存在的不足，Huang等人[5]充分利用重复元素之间具有的外观相似特性提出了一种新的目标对象提取方法——Rep-Snapping算法。算法通过建立相距较远且外观相似的像素点之间的连接关系，从而进一步改进Graphcut算法中的图割模型，改进的能量公式E(f)定义如下：

其中，等式右端中增加的能量项Ui,j为特征空间上的重复项，用于度量颜色特征上相似像素点i与j之间的标签过渡平滑性。在能量公式Ε(f)中，RepSnapping算法通过引入度量外观相似性的重复项，能够连接空间距离较远但颜色相近的像素点对。由此，仅在提供少量用户交互的情况下，该算法也能同时提取大规模的重复场景元素，从而极大地提高图像分割算法的时间效率。

Fig.2　Algorithm flow chart图2 算法流程图

4　重复纹理元素的提取

虽然RepSnapping算法已经能够实现重复元素的同时提取，但该方法仅仅在颜色特征上进行相似性度量。当多个目标对象之间颜色差异较大或前/背景颜色相近时，该方法的提取效果不是很理想。因此，本文进一步改进RepSnapping算法，提出了一种新的交互式的图像分割方法，其算法流程如图2所示，主要用于提取纹理图像中大量的重复纹理元素。

本文算法主要由以下3部分组成：用户交互、图像预处理和纹理元素提取。

在用户交互中，用户仅标记纹理图像中一到两个颜色显著和形状完整的纹理元素作为前景，并同样标记与前景位置较为相近的颜色显著的背景区域作为背景，这样标记前/背景区域可以有效避免因前/背景具有相近似特征时造成分割不理想的情况。另外，纹理图像中目标前景数目较多且相互之间排布紧密，因而纹理图像的背景区域通常较为狭小或不具有纹理背景，需要用户较细致地标记前景和背景区域。

在图像预处理中，本文采用颜色聚类方法，将原图像分割成相互独立且连通的图像子块。图像预处理的目的在于：在图的构建中使用图像子块代替像素点作为图中的节点，使得能够大大减少图像分割过程中的计算量，提高算法的时间效率。

在纹理元素提取中，通过分析纹理图像的纹理特征，并将纹理特征与颜色特征相结合，从而定义一个鲁棒的外观相似性度量公式。在此基础上，进一步改进现有图割模型，从而实现纹理元素的同时提取，并提高纹理图像中纹理元素提取的准确率。

本文算法通过图像的预处理，将纹理图像聚类成具有独立特征的图像子块并运用于图G的构建，极大地降低了算法的冗余计算量；通过结合纹理特征，构建一个更加稳健的多尺度相似性度量公式并运用于图割模型的改进，极大地改善了纹理图像中纹理元素提取结果。

4.1纹理图像的预处理

一幅图像中往往具有大量的像素点，特别是高清图像。现有图割算法通常利用像素点的空间相邻关系构建4-连通或8-连通的拓扑结构，对图像中大量的像素点建立点对点连通关系会使得图中的节点以及节点之间的连接边都数量庞大，且这一过程将会耗费大量的时间代价。尤其当RepSnapping算法[5]在图的构建中增加了连接具有一定特征相似的像素点对之间的连通关系后，任意两像素点间都有可能建立起一条连接边，使得像素点之间的拓扑图显得更加杂乱（如图3所示），即在某种程度上限制了算法的运行效率。

为了降低算法的计算负荷，本文采用均值漂移（mean shift）聚类算法[18]将原图像分割成若干个相互独立且各区域连通的图像子块。为了便于观察，将颜色聚类后的多个图像子块区域分别用不同颜色进行填充（如图4（b）所示）。此时，图像子块区域将在图的构建中取代原图像中的像素点作为图中的节点。

Fig.3　Extended connectivity based on pixels图3　基于像素点的扩展连通图

将原图像进行区域划分后，图中各图像子块与其相邻图像子块不再是简单的4-邻域或8-邻域连通关系（如图1所示）。由于各图像子块的相邻图像子块的数目会各不相同，并且在距离和方向上也各有差异，连通关系的构建将具有不确定性。因此，为了建立各图像子块之间的连通关系，本文首先获得包围各图像子块的矩形框，并取其中心点位置信息代替原图像中的图像子块位置信息，以及用图像子块的平均RGB颜色值作为图像子块的颜色特征，如图4 （c）所示。然后，通过采用Delaunay三角剖分构建图像子块与相邻图像子块之间的连通关系，用于代替现有图构建中的4-邻域或8-邻域连通关系，如图4 （d）所示。另外，记录的各图像子块间的相邻关系将会用于后续的纹理元素提取过程。

4.2基于外观相似性度量的纹理元素提取

4.2.1多特征融合的相似性度量公式

图像分割中最常采用的特征是颜色特征，这主要是因为颜色特征具有易提取、易分辨等显著优点。但是，纹理图像中的纹理元素除颜色特征以外，通常还存在如纹理特征、形状特征等另外一些显著的特征。仅基于颜色特征的分割算法虽然操作简单且辨识度高，但这些方法对呈现一致色调或前/背景颜色差异不明显的图像并不能很好地处理，存在较大局限性。因此，本文定义了一种更加鲁棒的外观相似性度量机制，即通过融合多种特征捕获纹理元素之间的相似程度，从而改善纹理元素提取结果的质量。

除利用颜色特征之外，本文通过采用Gabor小波变换对纹理图像中的纹理特征进行分析。Gabor滤波[29]是一种最佳的纹理特征描述方式，它能够在空间域和频率域上最小化联合二维的不确定性。Gabor滤波在多尺度和多方向上类似于人类的视觉系统，因而能够较好地表达图像中的纹理特征。

Fig.4　Image preprocessing图4 图像预处理

二维Gabor滤波器是一个高斯核函数和正弦平面波的乘积，其Gabor函数g(x,y)表示为：

Gabor函数g(x,y)的傅里叶变换G(u,v)如下所示：

其中，σu=。

通过膨胀和旋转小波系数可以获得一类自相似滤波函数gm,n(x,y)：

因此，给定原图像I(x,y)，其Gabor小波变换Wm,n(u,v)如下：

其中，上标*表示复共轭；下标m和n分别表示多个尺度和方向。

在各尺度和方向上分别计算Gabor小波变换系数的均值 μm,n和标准差σm,n：

由此，纹理特征T是由M个尺度和N个方向（通常取M=4，N=6）上的均值 μm,n和标准差σm,n组成的特征向量：

结合颜色特征和纹理特征，图像子块i和图像子块j之间的外观相似性度量公式δ(i,j)定义如下：

4.2.2图的构建

本文通过图像预处理后得到图像子块之间的连通关系图（如图4（d）所示），在此基础上，将原图像仍构建为图G=(P,N)，如图5所示。此时，P为以图像子块为节点的点集；N为连接图像子块之间的边的集合，包括直接相邻的图像子块之间的边和具有相似特征的图像子块之间的边（不一定直接相邻）；s和t分别代表源端点和终端点，且图G中每一个节点都与s点和t点相连接。图像子块 j在纹理特征上的差异，Ti与Tj分别为图像子块i与 j的纹理特征向量。本文分别取以图像子块内每个像素点为中心的k×k的区域，计算这些局部区域的Gabor特征向量并求平均，由此得到图像子块i和 j的纹理特征Ti和Tj。需要指出的是，对于不同的纹理图像，k的取值不同，使得能够提取到显著的纹理特征即可。另外，

Fig.5　Construction of Graph G图5图G的构建

在计算图G中每条连接边的权值后，通过使用最大流/最小割算法寻求一条最佳分割路径（所有边的权值之和最小），即实现了图G的最优划分。图G中每条边的权值可由能量公式（式（2））计算得到，其中连接直接相邻节点之间的边的权值取决于能量公式中的平滑项，而连接具有外观相似节点之间的边的权值则取决于能量公式中的重复项。

由此，数据项Dp定义如下：

其中，P为图G中节点的集合，即由图像子块的中心点组成；fp为节点p的标签；分别为p点到前景F与背景B中子区域颜色上的最小距离，可由下列等式计算得到：

其中，{KnF}和{KnB}为由k-means算法分别聚类前景与背景得到的一系列的簇。

为了获得高质量的纹理元素提取结果，本文结合颜色特征和纹理特征用于度量图像子块之间的外观相似性，相似程度可由式（10）计算得到。因此，平滑项Vp,q进一步改写为：

其中，λ为权重系数；β为常数，用于控制当相邻图像子块被划分不同标签值时的差异容限；δ(p,q)为度量节点p与q之间相似度的距离；N是由图G中直接相邻节点对组成的集合。

对于图G中任意两个图像子块i和图像子块 j，当它们之间的相似度小于指定的阈值ε时，图像子块i和图像子块 j则被认为是属于特征空间H上相邻的节点对。因此同样地，重复项Ui,j可进一步改写为：

其中，μ为权重系数；H为连接扩展空间上具有外观相似特征节点对的集合。

5　实验结果与分析

本文在硬件环境为2.2 GHz CPU，内存2 GB的PC机上使用VC++和OpenCV实现纹理元素提取算法。为了验证了本文算法的有效性和实用性，分别在算法时间效率与纹理元素提取结果两个方面与现有的图像分割方法[5,22-23]进行了对比。

5.1算法时间效率的比较

对于同一幅纹理图像，Grabcut算法、LazySnapping算法、RepSnapping算法和本文算法得到理想的分割结果所需要的用户交互数不同，这也一定程度上影响了算法的时间效率。因此，对上述4种算法在处理各种尺寸的纹理图像所需的交互数量进行了统计，如表1所示。

Table 1　User interaction statistics for various texture images表1　不同图像用户交互的统计

由表1可知，在对纹理图像中的纹理元素进行提取时，Grabcut与LazySnapping算法的交互次数远大于RepSnapping和本文算法，并且图像的大小发生变化时，交互次数亦有较大增加。由于前两种方法仅适用于单个目标对象的提取，从而纹理图像中的纹理元素越多，所需的用户交互次数也就越多。相反，RepSnapping与本文算法在处理纹理图像时仅需要提供少量的用户交互，即不需要对纹理元素逐一标记，并且用户交互次数也不会随着纹理元素数量的增加而发生明显的变化，因而使得用户交互过程能够最大程度地简便及高效。

为了比较以上几种分割算法的纹理元素提取时间效率，本文对纹理元素提取时间代价进行逐一统计，具体内容如表2所示。需要指出的是，表2中的纹理元素提取时间泛指算法在图像分割过程中的时间消耗，不包括用户交互的时间与图像预处理所耗费的时间。

Table 2　Running time statistics for texture elements extraction表2　纹理元素提取时间的统计

由表2可以看出，Grabcut算法的分割时间最长，LazySnapping算法的分割时间最短，RepSnapping与本文算法的分割时间位于二者之间。由于Grabcut算法在能量最优化中需要进行迭代求解，导致该算法在迭代过程中需要消耗大量时间以保证纹理元素提取的效果；而LazySnapping、RepSnapping以及本文算法则均是一次性实现能量的最优划分，因此分割时间相对较短。另外，RepSnapping与本文算法的提取时间指同时提取图像中全部纹理元素的总时间，而Grabcut与LazySnapping算法则指提取一个目标对象所需的时间。如若提取一幅纹理图像中所有纹理元素，则需要的时间也会成倍增加。由此可见，Rep-Snapping与本文算法在时间效率上有较大的提升。

5.2提取结果的比较

图6给出了本文算法与现有的3种图像分割算法[5,22-23]的实验结果比较。其中，图6（a）为原图像；图6（b）为Grabcut算法得到的实验结果；图6（c）为LazySnapping算法得到的实验结果；图6（d）为Rep-Snapping算法得到的实验结果；图6（e）为本文算法得到的实验结果。

由图6给出的实验结果可以看到，待处理的纹理图像具有纹理元素之间颜色差异大，形态多且复杂的特点。在图6第一行中，原图像由多个大小不一的石头组成，其中每个石头内部颜色不统一，相互之间颜色不相同且与背景颜色相似。若使用Grabcut算法对这些纹理元素进行提取，那么需要用户在各个目标纹理上逐一标记，需要大量的用户交互，且分割效果较差。如图6（b）第一行所示，该方法仅能分割出矩形框内用户交互的目标纹理元素，不能检测出与其外观相似的纹理元素，也不能将与目标前景颜色相近的图像背景分割出来；LazySnapping算法的提取效果较好于Grabcut算法（如图6（c）第一行所示），原因是在该算法自动提取完成后仍可以通过人工交互对提取的纹理边界进行修改，直到用户满意。但这类方法同样只能提取出标记为前景种子的纹理元素，并且边界的调整需要耗费大量的时间；RepSnapping算法处理这类纹理图像的优点在于可以同时提取外观相似的纹理元素，因此仅需要较少的交互内容，但是该纹理图像的前/背景颜色相近似，在该方法构建的颜色特征空间上没有明显差异，因此得到的分割效果十分不理想（如图6（d）第一行所示）；在本文提出的基于改进的图割模型的图像分割方法中，通过结合颜色特征和纹理特征用于纹理元素之间的外观相似性的度量，能够明确地提取目标前景，并分离图像背景。另外，本文算法仅需要少量的用户交互与编辑即能得到较好的分割效果（如图6（e）第一行所示）。

Fig.6　Experimental results comparison for algorithms图6 算法结果对比图

在图6第二行与第三行中，咖啡豆与钢板花纹图像中的纹理元素均尺寸较小且分布密集，给用户交互带来一定的困难，使得现有的3种图像分割方法[5,22-23]不能提取出完整的纹理元素（如图6（b）、（c）、（d）第二、三行所示）；本文算法则能够提取出较为完整的纹理元素，但是在前景与背景颜色及纹理均较相近的部分，也一定程度上存在缺失。

在图6第四行中，猕猴桃表面与其斑点颜色十分相似，Grabcut算法能提取出标记位置的纹理元素，但提取出的纹理元素形状大多发生了改变（如图6（b）最后一行所示）；LazySnapping算法提取出的纹理元素较为完整，但是这需要用户进行大量的交互并反复调整边界（如图6（c）最后一行所示）；RepSnapping算法在仅提供少量用户交互的情况下，由于前/背景颜色相近似，得到的分割效果十分不理想（如图6（d）最后一行所示）；本文算法不仅能够同时提取出所有纹理元素，且这些纹理元素均能保持完整的结构与形态，与文中提到的其他方法比较，具有较好的分割性能。需要指出的是，用户交互时，应选择纹理图像中颜色特征显著且纹理特征清晰的纹理元素标记作为前景，并选择与标记的目标前景位置较为相近且同样具有显著颜色或纹理特征的背景区域作为背景。这是因为在具有歧义性的区域进行用户交互，可以有效避免在前/背景具有相近似外观特征时造成分割不理想的情况。然而，用户交互的细致程度能够很大程度上影响纹理元素的分割效果。因此，如若选取的前/背景区域不具备较为明显的颜色或纹理特征，分割效果并不理想。

另外，为了验证本文算法的可行性，对具有大量重复元素的自然场景图像与纹理图像进行实验，更多的实验结果如图7所示。从图中可以看出，该实验结果很大程度上保持了重复场景元素的完整性，证明了本文算法运用的广泛性与灵活性。

Fig.7　More experimental results图7 更多实验结果图

6　结束语

本文针对优化的图割算法进行改进，在Rep-Snapping算法的基础上引入纹理特征的度量，建立了一个更加鲁棒的相似性度量公式。因此，对于前景与背景颜色差异不明显的纹理图像，本文算法也能精准地度量纹理元素之间相似程度。另外，通过结合新的相似性度量公式改进现有图割模型，实现纹理图像中具有相似外观特征的纹理元素的同时提取，并且获得高质量的纹理元素提取结果，较好地处理颜色特征差异不显著的纹理图像。

本文算法也一定程度上存在缺陷，当提取的目标之间不存在纹理特征，且前/背景颜色特征差异不明显时，提取效果不太理想。另外，由于引入了纹理特征用于外观相似性的度量，本文算法在预处理部分耗时较多，时间效率上还有待提高。如何解决以上问题也将成为本文以后探讨纹理图像处理的主要方向。

References:

[1]Leung T,Malik J.Detecting,localizing and grouping repeated scene elements from an image[C]//LNCS 1064:Proceedings of the 4th European Conference on Computer Vision,Cambridge,UK,Apr 15-18,1996.Berlin,Heidelberg:Springer, 1996:546-555.

[2]Liu Yanxi,Collins R T,Tsin Y.A computational model for periodic pattern perception based on frieze and wallpaper groups[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(3):354-371.

[3]Ahuja N,Todorovic S.Extracting texels in 2.1D natural textures[C]//Proceedings of the 11th IEEE International Conference on Computer Vision,Rio de Janeiro,Brazil,Oct 14-20,2007.Piscataway,USA:IEEE,2007:1-8.

[4]Cheng Mingming,Zhang Fanglue,Mitra N J,et al.RepFinder: finding approximately repeated scene elements for image editing[J].ACM Transactions on Graphics,2010,29(4): 157-166.

[5]Huang Hua,Zhang Lei,Zhang Hongchao.RepSnapping:efficient image cutout for repeated scene elements[J].Computer Graphics Forum,2011,30(7):2059-2066.

[6]Zhang Fanglue,Cheng Mingming,Jia Jiaya,et al.Image-Admixture:putting together dissimilar objects from groups[J]. IEEE Transactions on Visualization and Computer Graphics, 2012,18(11):1849-1857.

[7]Xu Li,Yan Qiong,Jia Jiaya.A sparse control model for image and video editing[J].ACM Transactions on Graphics,2013, 32(6):2504-2507.

[8]Wei Liyi,Levoy M.Fast texture synthesis using tree-structured vector quantization[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques,New Orleans,USA,Jul 23-28,2000.New York, USA:ACM,2000:479-488.

[9]Efros AA,Freeman W T.Image quilting for texture synthesis and transfer[C]//Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques,Los Angeles,USA,Aug 12-17,2001.New York,USA:ACM,2001: 341-346.

[10]Kwatra V,Schödl A,Essa I,et al.Graphcut textures:image and video synthesis using graph cuts[J].ACM Transactions on Graphics,2003,22(3):277-286.

[11]Lefebvre S,Hoppe H.Parallel controllable texture synthesis[J]. ACM Transactions on Graphics,2005,24(3):777-786.

[12]Dischler J M,Maritaud K,Lévy B,et al.Texture particles[J]. Computer Graphics Forum,2002,21(3):401-410.

[13]Ijiri T,Mech R,Igarashi T,et al.An example-based procedural system for element arrangement[J].Computer Graphics Forum,2008,27(2):429-436.

[14]Gui Yan,Ma Lizhuang.Periodic pattern of texture analysis and synthesis based on texels distribution[J].The Visual Computer,2010,26(6/8):951-964.

[15]Boykov Y,Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images [C]//Proceedings of the 8th IEEE International Conference on Computer Vision,Vancouver,Canada,Jul 7-14,2001.Piscataway,USA:IEEE,2001:105-112.

[16]Kolmogorov V,Zabin R.What energy functions can be minimized via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(2):147-159.

[17]Boykov Y,Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137.

[18]Comaniciu D,Meer P.Mean shift:a robust approach toward feature space analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(5):603-619.

[19]Felzenszwalb P F,Huttenlocher D P.Efficient graph-based image segmentation[J].International Journal of Computer Vision,2004,59(2):167-181.

[20]Nikou C,Galatsanos N P,Likas C L.A class-adaptive spatially variant mixture model for image segmentation[J].IEEE Transactions on Image Processing,2007,16(4):1121-1130.

[21]Ugarriza L G,Saber E,Vantaram S R,et al.Automatic image segmentation by dynamic region growth and multiresolution merging[J].IEEE Transactions on Image Processing, 2009,18(10):2275-2288.

[22]Rother C,Kolmogorov V,Blake A.“GrabCut”:interactiveforeground extraction using iterated graph cuts[J].ACM Transactions on Graphics,2004,23(3):309-314.

[23]Li Yin,Sun Jian,Tang C K,et al.Lazy snapping[J].ACM Transactions on Graphics,2004,23(3):303-308.

[24]Gulshan V,Rother C,Criminisi A,et al.Geodesic star convexity for interactive image segmentation[C]//Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition,San Francisco,USA,Jun 13-18,2010.Piscataway,USA:IEEE,2010:3129-3136.

[25]Xiao Chunxia,Chu Yu,Zhang Qing,Texture image segmentation using level set function evolved by Gaussian mixture model[J].Chinese Journal of Computers,2010,33(7):1295-1304.

[26]Zhao Zaixin,Cheng Lizhi.Unsupervised texture segmentation combined semi local image information and structure tensor[J].Journal of Image and Graphics,2011,16(4):559-565.

[27]Zhang Hui,Liu Shirong,Zhang Botao.A salient region extraction algorithm based on color and texture[J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2013,41(S1):399-402.

[28]Xie Xianghua,Mirmehdi M.TEXEMS:texture exemplars for defect detection on random textured surfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007,29(8):1454-1464.

[29]Manjunath B S,Ma W Y.Texture features for browsing and retrieval of image data[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(8):837-842.

附中文参考文献：

[25]肖春霞,初雨,张青.高斯混合函数区域匹配引导的Level Set纹理图像分割[J].计算机学报,2010,33(7):1295-1304.

[26]赵在新,成礼智.结合半局部信息与结构张量的无监督纹理图像分割[J].中国图象图形学报,2011,16(4):559-565.

[27]张会,刘士荣,张波涛.一种基于颜色和纹理的显著区域提取算法[J].华中科技大学学报:自然科学版,2013,41 (S1):399-402.

YANG Nongying was born in 1991.She is an M.S.candidate at Changsha University of Science&Technology.Her research interests include digital image processing and visual media editing,etc.

杨弄影（1991—），女，湖南常德人，长沙理工大学计算机与通信工程学院硕士研究生，主要研究领域为数字图像处理，可视媒体编辑与处理等。

LI Feng was born in 1964.He is a professor and M.S.supervisor at Changsha University of Science&Technology. His research interests include image processing,pattern recognition,computer vision and information security,etc.李峰（1964—），男，湖南澧县人，博士，长沙理工大学教授、硕士生导师，主要研究领域为图像处理，模式识别，计算机视觉，信息安全等。

GUI Yan was born in 1985.She received the Ph.D.degree from Shanghai Jiaotong University in 2012.Now she is a lecturer and M.S supervisor at Changsha University of Science&Technology.Her research interests include digital image processing,computer graphics,computer vision and visual media editing,etc.

桂彦（1985—），女，湖南永州人，2012年于上海交通大学获得博士学位，现为长沙理工大学讲师、硕士生导师，主要研究领域为数字图像处理，计算机图形学，可视媒体编辑与处理等。

*The National Natural Science Foundation of China under Grant No.61402053(国家自然科学基金). Received 2015-06,Accepted 2015-08.

CNKI网络优先出版:2015-08-27,http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1504.010.html

文献标志码：A

中图分类号：TP391

doi:10.3778/j.issn.1673-9418.1508025

Repeated Texture Elements Extraction from Texture Images*

YANG Nongying,LI Feng,GUI Yan+
School of Computer&Communication Engineering,Changsha University of Science&Technology,Changsha 410114,China
+Corresponding author:E-mail:guiyan122@163.com

Abstract:This paper presents an interactive element extraction method for texture image,which is able to simultaneously cut out the repeated texture elements with much less user interaction.Firstly,texture image can be segmented into individual and connected subpatches by using Mean Shift algorithm,and their connectivity can be constructed by using Delaunay triangulation.Secondly,by considering color information and texture feature,a robust measurement distance is redefined,which can precisely capture all repeated texture elements with similar appearance.Finally,this paper further modifies the optimization graphcut model in order to achieve the best texture extraction.The proposed method gets a great better extraction result for the texture image that has foreground and background with similar color, and improves the speed of image segmentation significantly.

Key words:repeated texture elements;texture feature;similarity measurement;graphcut model