使用圖割方法提取圖像的紋理特征

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