1.電子科技大學(xué) 電子工程學(xué)院，成都 610054

2.重慶市/信息產(chǎn)業(yè)部計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065

3.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065

4.重慶郵電大學(xué) 軟件學(xué)院，重慶 400065

1.電子科技大學(xué) 電子工程學(xué)院，成都 610054

2.重慶市/信息產(chǎn)業(yè)部計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065

3.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065

4.重慶郵電大學(xué) 軟件學(xué)院，重慶 400065

1 引言

圖割方法是近年來圖像分割領(lǐng)域的一個(gè)研究熱點(diǎn)，可以用來對各種離散像素的標(biāo)記問題給出最大后驗(yàn)解。圖割方法首先構(gòu)造一個(gè)與能量泛函相應(yīng)的具有特殊結(jié)構(gòu)的圖，求解圖的最小割就可以得到最小能量的狀態(tài)，而圖的最小割則可以通過最大流算法[1]高效得到。圖割方法在立體視覺[2]，圖像分割[3]，圖像復(fù)原[4]和紋理分析[5]等領(lǐng)域得到了廣泛的應(yīng)用。最近的圖割方法的研究主要有：根據(jù)處理目標(biāo)的不同，構(gòu)建不同的能量函數(shù)[6]；在能量項(xiàng)中，設(shè)計(jì)不同的區(qū)域因子[7]或者目標(biāo)分割因子[8]以便針對性地處理區(qū)域。Lombaert[9]等研究了高清晰度數(shù)據(jù)中圖割算法的使用，提出了多層次帶寬結(jié)構(gòu)，通過在更小的圖中進(jìn)行處理可以減少運(yùn)行時(shí)間和內(nèi)存的需求。因?yàn)閳D割方法能集成各種可視因子，一些研究者將形狀因子集成到圖割理論的框架中。Freedman and Zhang[10]利用level set的思想構(gòu)造了一個(gè)距離函數(shù)，將形狀因子定義為一個(gè)模板。這些方法大多是通過手工干預(yù)的方式提供形狀信息，太多的干預(yù)使得算法變得更加麻煩而且更耗時(shí)間。文獻(xiàn)[11]中設(shè)計(jì)了拓?fù)浔３值膱D割方法，得到了較好的結(jié)果。

多重網(wǎng)格法于1960s被提出來，一開始用于求解橢圓邊值問題，后來被Terzopoulos[12]首次用于圖像分析。多重網(wǎng)格法的基本思想是引進(jìn)一種粗網(wǎng)格系列，并使用它來加速細(xì)網(wǎng)格修正量的傳播以得到快速消除擾動(dòng)的結(jié)果。多重網(wǎng)絡(luò)法主要有兩種方法：幾何多重網(wǎng)絡(luò)和代數(shù)多重網(wǎng)格（AMG）。AMG方法僅利用方程組本身的信息來求解代數(shù)方程組，允許在無結(jié)構(gòu)的網(wǎng)格上進(jìn)行求解，因此更容易擴(kuò)展到圖像處理等領(lǐng)域。代數(shù)多重網(wǎng)格方法分為兩步：平滑過程和粗網(wǎng)格修正過程。平滑過程可以迅速將那些高頻分量去掉，而粗網(wǎng)格修正過程則可以幫助修正那些光滑了的低頻分量，通過不斷的迭代，從而快速精確地處理問題。AMG方法相對于金字塔結(jié)構(gòu)而言，它增加了粗網(wǎng)格調(diào)整過程，這一過程可以看成是對平滑過程的一個(gè)反饋，能將更多的有用信息保留在粗網(wǎng)格之中。AMG在圖像中的應(yīng)用主要是將圖像重構(gòu)、圖像二值化、圖像復(fù)原和圖像去噪[13-17]等通過差分方程（PDE）表示，并使用AMG方法來進(jìn)行快速求解。SWA（Segmentation by Weighted Aggregation）算法[18]是其中典型的例子，它是通過構(gòu)建原始圖像的粗網(wǎng)格來加速分割過程，提高分割質(zhì)量。

在使用AMG方法處理圖像數(shù)據(jù)的過程中發(fā)現(xiàn)，圖像突變的區(qū)域網(wǎng)格密度較大，而圖像平緩的區(qū)域網(wǎng)格密度較小，而且在對均質(zhì)紋理圖案處理時(shí)AMG顯示了較強(qiáng)的能力。本文將AMG方法用來提取圖像的紋理圖案，并結(jié)合到圖割方法之中，最終得到圖像紋理區(qū)域的圖像分割結(jié)果。

2 圖割方法和代數(shù)多重網(wǎng)格

圖割方法是一種圖論方法。已知一幅有N個(gè)像素的圖像 S={S1，S2，…，SN}，圖像分割則需要將這些像素點(diǎn)分配到不同的標(biāo)簽 L={l1，l2，…，lM}。這需要構(gòu)建一個(gè)關(guān)于標(biāo)號的能量函數(shù)，一個(gè)通用的能量函數(shù)表示為：

其中Edata是數(shù)據(jù)項(xiàng)，表示數(shù)據(jù)約束，用來保證每個(gè)像素盡可能地找到其對應(yīng)標(biāo)號，Esmooth是平滑項(xiàng)，表示光滑約束，用于約束相鄰像素的一致性，而Eextra是附加項(xiàng)，用來增加一些附加的約束。子集L′是標(biāo)簽集合L的一個(gè)子集，當(dāng)附加信息中提供了圖像中某個(gè)區(qū)域與該子集具有特定關(guān)系時(shí)，可以對該子集增加相應(yīng)的懲罰值以便對該區(qū)域進(jìn)行特殊處理。本文將主要針對圖像的紋理特征增加附加項(xiàng)，以便能更好地提取圖像的紋理特征信息。

代數(shù)多重網(wǎng)格法的求解對象是滿足一定條件的線性問題 Au=f。首先，定義最細(xì)的網(wǎng)格為Ω1，構(gòu)造一個(gè)網(wǎng)格序列 Ω2，Ω3，…，Ωk，使得：

代數(shù)多重網(wǎng)格過程的具體思路是：先在細(xì)網(wǎng)格Ω1上做松弛迭代（又稱平滑過程），然后將誤差投影到粗一層網(wǎng)格Ω2上去，在粗網(wǎng)格Ω2上又做松弛迭代，繼續(xù)平滑相應(yīng)的高頻部分。依次類推，直到最粗的一層Ωk。在最粗一層用直接法求解，然后，用插值算子將所求得的誤差返回到細(xì)網(wǎng)格上去，用以修正原有結(jié)果，這稱為粗網(wǎng)格修正過程，直到最細(xì)的一層Ω1。

在構(gòu)成這些網(wǎng)格的同時(shí)，要在每個(gè)網(wǎng)格上確定相應(yīng)的系數(shù)矩陣 A2，A3，…，Ak。此外需要建立相鄰網(wǎng)格層之間的聯(lián)系，即建立插值算子和投影算子。定義限制算子為插值算子為限制矩陣和插值矩陣分別表示為：

系數(shù)矩陣之間的關(guān)系可以通過粗網(wǎng)格算子來得到：

其中I為單元矩陣，其他的參數(shù)設(shè)置請參考文獻(xiàn)[19-20]，通用的多重網(wǎng)格算法步驟如下：

在第m層執(zhí)行V(um，fm)：

（1）前光滑：在第m層進(jìn)行松弛Amum=fm。

（2）粗網(wǎng)格校正：

①在細(xì)網(wǎng)格層計(jì)算殘差rm=fm-Amum。

在第m+1層遞歸執(zhí)行V(um+1，fm+1)，直到在最粗的網(wǎng)格層直接求解Akek=rk。

④在細(xì)網(wǎng)格層校正錯(cuò)誤um←um+em。

（3）后光滑：在m層進(jìn)行n2次松弛 Amum=fm。

3 算法分析與算法實(shí)現(xiàn)

在將AMG應(yīng)用到圖像處理的實(shí)踐中，發(fā)現(xiàn)AMG在計(jì)算粗網(wǎng)格時(shí)，網(wǎng)格密度會根據(jù)圖像中的變化情況而改變。初始化時(shí)原始圖層時(shí)網(wǎng)格是等密度的，但在粗網(wǎng)格中，灰度變化平滑區(qū)網(wǎng)格密度是較為稀疏而且比較規(guī)則，而當(dāng)灰度變化急劇時(shí)，網(wǎng)格密度則很稠密而且不規(guī)則，在一定程度上起到了自適應(yīng)網(wǎng)格的作用。通過進(jìn)一步分析，AMG對于邊緣，紋理具有一定的檢測能力。只要對粗網(wǎng)格進(jìn)行詳細(xì)的分析，圖像中的重要特征都能較好地保留，但目前在這一領(lǐng)域研究較少，如何更好地描述這些重要特征并將其檢測出來還有待進(jìn)一步的工作。

本文應(yīng)用pyamg包中的Ruge_stuben方法[20]來進(jìn)行求解。通過AMG方法提取的粗網(wǎng)格分析，同種紋理在AMG中表述方式較為一致，通過直觀顯示，能夠從結(jié)果圖中發(fā)現(xiàn)其中隱藏的紋理。紋理的提取是一個(gè)較為復(fù)雜的過程，根據(jù)不同的紋理需要采取不同的特征描述的方法。本文采用消除均勻的網(wǎng)格部分再對消除后的結(jié)果進(jìn)行均值濾波，主要目的是減少非紋理部分對紋理部分的影響。將粗網(wǎng)格數(shù)據(jù)中紋理部分對應(yīng)的能量部分設(shè)置一個(gè)較小的值，而其他部分的能量設(shè)置情況與標(biāo)準(zhǔn)的圖割方法一樣，這樣可以重點(diǎn)突出粗網(wǎng)格部分提取的紋理數(shù)據(jù)對于最終結(jié)果的影響。

根據(jù)AMG方法確定紋理特征區(qū)域A(p)，然后對于不同的紋理特征設(shè)定不同的標(biāo)簽值。公式（1）中能量公式的三個(gè)部分分別表示為：

其中 fp為待處理圖片中對應(yīng) p點(diǎn)的灰度值，而 f′p'為紋理特征圖片中對應(yīng) p點(diǎn)的灰度值。數(shù)據(jù)項(xiàng)懲罰灰度值與標(biāo)簽值遠(yuǎn)離的狀況，平滑項(xiàng)懲罰相鄰像素的標(biāo)簽值遠(yuǎn)離的狀況，而附加項(xiàng)則是對像素點(diǎn)屬于同一種紋理特征的獎(jiǎng)勵(lì)，當(dāng)像素點(diǎn)屬于該紋理特征時(shí)，給予較小的能量值，在最終的結(jié)果中，屬于同一種紋理特征的像素會被賦予同一種標(biāo)簽。

根據(jù)紋理分割的問題，本文的算法流程如下：

（1）通過原始圖像構(gòu)建能量函數(shù)中的數(shù)據(jù)項(xiàng)和平滑項(xiàng)。

（2）通過Ruge-Stuben方法求解，提取原始圖像的粗網(wǎng)格數(shù)據(jù)。

（3）使用平滑方法進(jìn)行處理，減少非紋理網(wǎng)格點(diǎn)對紋理結(jié)果提取的影響。

（4）使用粗網(wǎng)格數(shù)據(jù)計(jì)算能量函數(shù)的懲罰項(xiàng)，加到能量函數(shù)中。

（5）使用max-flow方法進(jìn)行求解，進(jìn)行能量的最小化，得到最終的分割結(jié)果。

4 實(shí)驗(yàn)結(jié)果及分析

進(jìn)行了多次測試，并得到了較好的結(jié)果。文中使用常見的Barb圖與其他算法進(jìn)行比較測試。Barb圖中紋理圖案比較規(guī)則，背景不是很復(fù)雜。

從圖1（d）可以看出，標(biāo)準(zhǔn)的圖割算法對于具有一定紋理的圖像的檢測不夠精確，究其原因是因?yàn)樵谔卣鞅硎龅乃阕由蠜]有充分反映紋理特征的算子。通過AMG方法提取圖像的紋理部分，然后對AMG方法提取的紋理部分給以較低的能量，加到能量表達(dá)式中，這樣就可以將這部分突出顯示。圖 1中所示的結(jié)果中，（a）為原始圖像，（b）（c）為提取的粗網(wǎng)格數(shù)據(jù)和對其進(jìn)行平滑之后的結(jié)果。在能量設(shè)置時(shí)，將紋理區(qū)域所在的點(diǎn)設(shè)置較低的能量，然后結(jié)合到原始圖像的能量表達(dá)式中，可以得到如圖1（f）的圖像，圖1（d）是標(biāo)準(zhǔn)的圖割算法的結(jié)果。兩者比較可以看出，圖1（f）中將頭巾，圍巾，褲子和桌布等的紋理圖案提取得較為充分，考慮到光照的影響，桌布和頭巾中部分位置沒有提取出來。與SWA算法的結(jié)果相比，圖1（e）中提取的桌布相對比較準(zhǔn)確，總的來說還是本文算法提取更為準(zhǔn)確。

5 結(jié)束語

圖割方法與傳統(tǒng)的分割方法相比，是一種全局的分類目標(biāo)。結(jié)合合適的能量目標(biāo)函數(shù)，可以對于邊緣，紋理等特征可以提取得更為全面。本文方法可以在一定程度上擴(kuò)展圖割算法的使用范圍，合適的能量目標(biāo)函數(shù)的選擇是關(guān)鍵。AMG方法提取的粗網(wǎng)格信息對于邊緣，紋理等特征反映較為充分，但是如何對這些特征進(jìn)行有效的提取并且加到圖割框架之中，還需要進(jìn)一步的研究。

圖1 本文方法與其他方法進(jìn)行的比較

[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]劉朝霞，常謙順.由擴(kuò)散張量導(dǎo)出的各向異性擴(kuò)散模型的隱式數(shù)值模擬[J].計(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

研究目的是對代數(shù)多重網(wǎng)格（AMG）方法進(jìn)行分析，粗網(wǎng)格中會保留強(qiáng)連接部分而去掉弱連接部分，可以提取圖像的紋理信息。將AMG方法提取的圖像的紋理特征結(jié)合到圖分割算法中，針對具有紋理特征的圖片構(gòu)建能量函數(shù)，并使用最大流方法進(jìn)行優(yōu)化。使用一些自然圖像進(jìn)行了驗(yàn)證，結(jié)果證明針對該方法能夠較好地提取圖像的紋理特征。

圖割方法；代數(shù)多重網(wǎng)格；最大流方法；紋理特征

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.

國家自然科學(xué)基金（No.61100113，No.61100114）；教育部重點(diǎn)項(xiàng)目（No.KJ100525）；重慶市/信息產(chǎn)業(yè)部計(jì)算機(jī)網(wǎng)絡(luò)與通信技術(shù)重點(diǎn)實(shí)驗(yàn)室（No.CY-CNCL-2010-03）；重郵自然科學(xué)基金（No.A2011-07）。

黃穎（1978—），男，博士研究生，副教授，主要研究領(lǐng)域?yàn)閿?shù)字圖像處理、模式識別和人工智能；李偉生（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