使用图割方法提取图像的纹理特征

1.电子科技大学 电子工程学院，成都 610054

2.重庆市/信息产业部计算机网络与通信技术重点实验室，重庆 400065

3.重庆邮电大学 计算机科学与技术学院，重庆 400065

4.重庆邮电大学 软件学院，重庆 400065

1.电子科技大学 电子工程学院，成都 610054

2.重庆市/信息产业部计算机网络与通信技术重点实验室，重庆 400065

3.重庆邮电大学 计算机科学与技术学院，重庆 400065

4.重庆邮电大学 软件学院，重庆 400065

1 引言

图割方法是近年来图像分割领域的一个研究热点，可以用来对各种离散像素的标记问题给出最大后验解。图割方法首先构造一个与能量泛函相应的具有特殊结构的图，求解图的最小割就可以得到最小能量的状态，而图的最小割则可以通过最大流算法[1]高效得到。图割方法在立体视觉[2]，图像分割[3]，图像复原[4]和纹理分析[5]等领域得到了广泛的应用。最近的图割方法的研究主要有：根据处理目标的不同，构建不同的能量函数[6]；在能量项中，设计不同的区域因子[7]或者目标分割因子[8]以便针对性地处理区域。Lombaert[9]等研究了高清晰度数据中图割算法的使用，提出了多层次带宽结构，通过在更小的图中进行处理可以减少运行时间和内存的需求。因为图割方法能集成各种可视因子，一些研究者将形状因子集成到图割理论的框架中。Freedman and Zhang[10]利用level set的思想构造了一个距离函数，将形状因子定义为一个模板。这些方法大多是通过手工干预的方式提供形状信息，太多的干预使得算法变得更加麻烦而且更耗时间。文献[11]中设计了拓扑保持的图割方法，得到了较好的结果。

多重网格法于1960s被提出来，一开始用于求解椭圆边值问题，后来被Terzopoulos[12]首次用于图像分析。多重网格法的基本思想是引进一种粗网格系列，并使用它来加速细网格修正量的传播以得到快速消除扰动的结果。多重网络法主要有两种方法：几何多重网络和代数多重网格（AMG）。AMG方法仅利用方程组本身的信息来求解代数方程组，允许在无结构的网格上进行求解，因此更容易扩展到图像处理等领域。代数多重网格方法分为两步：平滑过程和粗网格修正过程。平滑过程可以迅速将那些高频分量去掉，而粗网格修正过程则可以帮助修正那些光滑了的低频分量，通过不断的迭代，从而快速精确地处理问题。AMG方法相对于金字塔结构而言，它增加了粗网格调整过程，这一过程可以看成是对平滑过程的一个反馈，能将更多的有用信息保留在粗网格之中。AMG在图像中的应用主要是将图像重构、图像二值化、图像复原和图像去噪[13-17]等通过差分方程（PDE）表示，并使用AMG方法来进行快速求解。SWA（Segmentation by Weighted Aggregation）算法[18]是其中典型的例子，它是通过构建原始图像的粗网格来加速分割过程，提高分割质量。

在使用AMG方法处理图像数据的过程中发现，图像突变的区域网格密度较大，而图像平缓的区域网格密度较小，而且在对均质纹理图案处理时AMG显示了较强的能力。本文将AMG方法用来提取图像的纹理图案，并结合到图割方法之中，最终得到图像纹理区域的图像分割结果。

2 图割方法和代数多重网格

图割方法是一种图论方法。已知一幅有N个像素的图像 S={S1，S2，…，SN}，图像分割则需要将这些像素点分配到不同的标签 L={l1，l2，…，lM}。这需要构建一个关于标号的能量函数，一个通用的能量函数表示为：

其中Edata是数据项，表示数据约束，用来保证每个像素尽可能地找到其对应标号，Esmooth是平滑项，表示光滑约束，用于约束相邻像素的一致性，而Eextra是附加项，用来增加一些附加的约束。子集L′是标签集合L的一个子集，当附加信息中提供了图像中某个区域与该子集具有特定关系时，可以对该子集增加相应的惩罚值以便对该区域进行特殊处理。本文将主要针对图像的纹理特征增加附加项，以便能更好地提取图像的纹理特征信息。

代数多重网格法的求解对象是满足一定条件的线性问题 Au=f。首先，定义最细的网格为Ω1，构造一个网格序列 Ω2，Ω3，…，Ωk，使得：

代数多重网格过程的具体思路是：先在细网格Ω1上做松弛迭代（又称平滑过程），然后将误差投影到粗一层网格Ω2上去，在粗网格Ω2上又做松弛迭代，继续平滑相应的高频部分。依次类推，直到最粗的一层Ωk。在最粗一层用直接法求解，然后，用插值算子将所求得的误差返回到细网格上去，用以修正原有结果，这称为粗网格修正过程，直到最细的一层Ω1。

在构成这些网格的同时，要在每个网格上确定相应的系数矩阵 A2，A3，…，Ak。此外需要建立相邻网格层之间的联系，即建立插值算子和投影算子。定义限制算子为插值算子为限制矩阵和插值矩阵分别表示为：

系数矩阵之间的关系可以通过粗网格算子来得到：

其中I为单元矩阵，其他的参数设置请参考文献[19-20]，通用的多重网格算法步骤如下：

在第m层执行V(um，fm)：

（1）前光滑：在第m层进行松弛Amum=fm。

（2）粗网格校正：

①在细网格层计算残差rm=fm-Amum。

在第m+1层递归执行V(um+1，fm+1)，直到在最粗的网格层直接求解Akek=rk。

④在细网格层校正错误um←um+em。

（3）后光滑：在m层进行n2次松弛 Amum=fm。

3 算法分析与算法实现

在将AMG应用到图像处理的实践中，发现AMG在计算粗网格时，网格密度会根据图像中的变化情况而改变。初始化时原始图层时网格是等密度的，但在粗网格中，灰度变化平滑区网格密度是较为稀疏而且比较规则，而当灰度变化急剧时，网格密度则很稠密而且不规则，在一定程度上起到了自适应网格的作用。通过进一步分析，AMG对于边缘，纹理具有一定的检测能力。只要对粗网格进行详细的分析，图像中的重要特征都能较好地保留，但目前在这一领域研究较少，如何更好地描述这些重要特征并将其检测出来还有待进一步的工作。

本文应用pyamg包中的Ruge_stuben方法[20]来进行求解。通过AMG方法提取的粗网格分析，同种纹理在AMG中表述方式较为一致，通过直观显示，能够从结果图中发现其中隐藏的纹理。纹理的提取是一个较为复杂的过程，根据不同的纹理需要采取不同的特征描述的方法。本文采用消除均匀的网格部分再对消除后的结果进行均值滤波，主要目的是减少非纹理部分对纹理部分的影响。将粗网格数据中纹理部分对应的能量部分设置一个较小的值，而其他部分的能量设置情况与标准的图割方法一样，这样可以重点突出粗网格部分提取的纹理数据对于最终结果的影响。

根据AMG方法确定纹理特征区域A(p)，然后对于不同的纹理特征设定不同的标签值。公式（1）中能量公式的三个部分分别表示为：

其中 fp为待处理图片中对应 p点的灰度值，而 f′p'为纹理特征图片中对应 p点的灰度值。数据项惩罚灰度值与标签值远离的状况，平滑项惩罚相邻像素的标签值远离的状况，而附加项则是对像素点属于同一种纹理特征的奖励，当像素点属于该纹理特征时，给予较小的能量值，在最终的结果中，属于同一种纹理特征的像素会被赋予同一种标签。

根据纹理分割的问题，本文的算法流程如下：

（1）通过原始图像构建能量函数中的数据项和平滑项。

（2）通过Ruge-Stuben方法求解，提取原始图像的粗网格数据。

（3）使用平滑方法进行处理，减少非纹理网格点对纹理结果提取的影响。

（4）使用粗网格数据计算能量函数的惩罚项，加到能量函数中。

（5）使用max-flow方法进行求解，进行能量的最小化，得到最终的分割结果。

4 实验结果及分析

进行了多次测试，并得到了较好的结果。文中使用常见的Barb图与其他算法进行比较测试。Barb图中纹理图案比较规则，背景不是很复杂。

从图1（d）可以看出，标准的图割算法对于具有一定纹理的图像的检测不够精确，究其原因是因为在特征表述的算子上没有充分反映纹理特征的算子。通过AMG方法提取图像的纹理部分，然后对AMG方法提取的纹理部分给以较低的能量，加到能量表达式中，这样就可以将这部分突出显示。图 1中所示的结果中，（a）为原始图像，（b）（c）为提取的粗网格数据和对其进行平滑之后的结果。在能量设置时，将纹理区域所在的点设置较低的能量，然后结合到原始图像的能量表达式中，可以得到如图1（f）的图像，图1（d）是标准的图割算法的结果。两者比较可以看出，图1（f）中将头巾，围巾，裤子和桌布等的纹理图案提取得较为充分，考虑到光照的影响，桌布和头巾中部分位置没有提取出来。与SWA算法的结果相比，图1（e）中提取的桌布相对比较准确，总的来说还是本文算法提取更为准确。

5 结束语

图割方法与传统的分割方法相比，是一种全局的分类目标。结合合适的能量目标函数，可以对于边缘，纹理等特征可以提取得更为全面。本文方法可以在一定程度上扩展图割算法的使用范围，合适的能量目标函数的选择是关键。AMG方法提取的粗网格信息对于边缘，纹理等特征反映较为充分，但是如何对这些特征进行有效的提取并且加到图割框架之中，还需要进一步的研究。

图1 本文方法与其他方法进行的比较

[1]Boykov Y，Kolmogorov V.An experimental comparison of min-cut/max-flow algorithmsforenergy minimization in vision[J].PAMI，2004，26（9）：1-34.

[2]Roy S，Cox I.A maximum-flow formulation of the n-camera stereo correspondence problem[C]//IEEE Proc of Int Conference on Computer Vision，1998：492-499.

[3]Boykov Y，Jolly M P.Interactivegraph cutsforoptimal boundary®ion segmentation of objects in N-D images[C]// International Conference on Computer Vision，2001：105-112.

[4]Greig D，Porteous B，Seheult A.Exact maximum a posteriori estimation for binary images[J].Journal of the Royal Statistical Society，Series B，1989，51（2）：271-279.

[5]Kwatra V，Schodl A，Essa I，et al.GraphCut textures：image and video synthesis using graph cuts[J].ACM Transactions on Graphics，2003，22（3）：277-286.

[6]Kolmogorov V，Zabih R.What energy function can be minimized via graph cuts[J].PAMI，2004，26：147-159.

[7]Rother C，Kolmogorov V，Blake A.Grabcut-interactive foreground extraction using iterated graph cuts[J].ACM Transactions on Graphics，2004，23（3）：309-314.

[8]Boykov Y，Kolmogorov V.Computing geodesics and minimal surfaces via graph cuts[C]//International Conference on Computer Vision，2003，1：26-33.

[9]Lombaert H，Sun Y，Grady L，et al.A multilevel banded graph cuts method for fast image segmentation[C]//International Conference on Computer Vision，2005，1：259-265.

[10]Freedman D，Zhang T.Interactive graph cut based segmentation with shape prior[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2005，1：755-762.

[11]Danek O，Maska M.A simple topology preserving max-flow algorithm for graph cut based image segmentation[C]//6th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science（MEMICS’10），2011，16：19-25.

[12]TerzopoulosD.Image analysisusing multigrid relaxation methods[J].IEEE Trans on PAMI，1986，8：129-139.

[13]Chan R H，Chan T F，Wan W L.Multigrid for differential convolution problems arising from image processing，CAM report 97-20[R].Los Angeles：UCLA，1997.

[14]Acton S.Multigrid anisotropic diffusion[J].IEEE Transactions on Image Processing，1998，7（3）：280-290.

[15]Kimmel R，Yavneh I.An algebraic multigrid approach for image analysis[J].SIAM，2003，24（4）：1218-1231.

[16]Xu Qiu-bin.Numericals for total variation-based reconstruction ofmotion blurred images[J].Applied Mathematics-a Journal of Chinese University，2010，25（3）：367-373.

[17]刘朝霞，常谦顺.由扩散张量导出的各向异性扩散模型的隐式数值模拟[J].计算物理，2005，22（4）：365-370.

[18]Alpert S，Galun M，Basri R，et al.Image segmentation by probabilistic bottom-up aggregation and cue integration[C]// IEEE Conf on Computer Vision and Pattern Recognition（CVPR-07），2007.

[19]Papandreou G，Maragos P.Multigrid geometric active contourmodels[J].IEEE Transactionson Image Processing，2007，16（1）：229-240.

[20]Pyamg[EB/OL].[2011-05-15].code.google.com/p/pyamg.

使用图割方法提取图像的纹理特征

黄 颖1，2，3，李伟生2，3，周丽芳4，王矿生3

HUANG Ying1，2，3,LI Weisheng2，3,ZHOU Lifang4,WANG Kuangsheng3

1.School of Electronic Engineering,University of Electronic Science and Technology of China,Chengdu 610054,China
2.Chongqing Key Lab of Computer Network and Communication Technology,Chongqing 400065,China
3.College of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
4.College of Software,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

Algebraic multi-grid method is analyzed and is applied in the normalized cut method to extract the texture feature of the image.Large grid density appears in the image regions with radical changes,and small one in the smoother regions.Singularities in the image can be detected by the AMG method,and especially the singularities in the texture image.An energy function is constructed for the texture feature and is minimized using max-flow method.Experimental results show that the proposed method can extract more texture details.

graph cut method;algebraic multi-grid;max-flow method;texture feature

研究目的是对代数多重网格（AMG）方法进行分析，粗网格中会保留强连接部分而去掉弱连接部分，可以提取图像的纹理信息。将AMG方法提取的图像的纹理特征结合到图分割算法中，针对具有纹理特征的图片构建能量函数，并使用最大流方法进行优化。使用一些自然图像进行了验证，结果证明针对该方法能够较好地提取图像的纹理特征。

图割方法；代数多重网格；最大流方法；纹理特征

A

TP391.41

10.3778/j.issn.1002-8331.1110-0090

HUANG Ying,LI Weisheng,ZHOU Lifang,et al.Extraction of texture feature using graph cut method.Computer Engineering and Applications,2013,49（11）：166-168.

国家自然科学基金（No.61100113，No.61100114）；教育部重点项目（No.KJ100525）；重庆市/信息产业部计算机网络与通信技术重点实验室（No.CY-CNCL-2010-03）；重邮自然科学基金（No.A2011-07）。

黄颖（1978—），男，博士研究生，副教授，主要研究领域为数字图像处理、模式识别和人工智能；李伟生（1975—），男，博士，教授；周丽芳（1975—），女，博士研究生，讲师；王矿生（1987—），男，硕士研究生。E-mail：huangying@cqupt.edu.cn

2011-10-09

2011-11-24

1002-8331（2013）11-0166-03

CNKI出版日期：2012-03-08 http://www.cnki.net/kcms/detail/11.2127.TP.20120308.1520.025.html