楊弄影，李　峰，桂　彥長沙理工大學(xué) 計算機與通信工程學(xué)院，長沙 410114

紋理圖像中重復(fù)紋理元素提取方法*

楊弄影，李峰，桂彥+
長沙理工大學(xué) 計算機與通信工程學(xué)院，長沙 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.

摘要：提出了一種交互式紋理圖像中紋理元素提取算法，該算法能夠在用戶提供少量交互的情況下較好地實現(xiàn)紋理圖像中重復(fù)紋理元素的同時提取。首先采用均值漂移聚類算法將紋理圖像分割成獨立且連通的子塊區(qū)域，并構(gòu)建圖像子塊區(qū)域之間的連通關(guān)系；然后結(jié)合顏色特征與紋理特征定義一個魯棒的相似性度量公式，從而準(zhǔn)確地捕獲具有外觀相似特征的紋理元素；在此基礎(chǔ)上，通過進(jìn)一步改進(jìn)優(yōu)化的圖割模型，最終實現(xiàn)高質(zhì)量的紋理元素提取。該算法針對前/背景顏色相近的紋理圖像中紋理元素的提取有較大改善，并且大大提高了現(xiàn)有圖像分割算法的時間效率。

關(guān)鍵詞：重復(fù)紋理元素；紋理特征；相似性度量；圖割模型

1　引言

重復(fù)元素在自然場景或人工場景中是普遍存在的，而這種重復(fù)特性在紋理圖像中尤為顯著。紋理圖像的背景通常比較單一，且重復(fù)出現(xiàn)的紋理元素在顏色、形狀、大小和紋理等特征上具有一定的相似性，即在外觀上易于分辨。從這類紋理圖像中提取感興趣的目標(biāo)對象（如重復(fù)出現(xiàn)的紋理元素），較為常用的處理方式是采用圖像分割技術(shù)分割這些感興趣區(qū)域。

近年來，雖然一些新的交互式圖像分割技術(shù)[1-7]已經(jīng)實現(xiàn)了重復(fù)場景元素的同時提取，但是這些方法仍然不能較好地用于紋理圖像的處理。其中，文獻(xiàn)[5]中的方法僅適用于同時提取與背景具有較大顏色差異的目標(biāo)前景區(qū)域。因而，當(dāng)紋理圖像中存在紋理元素種類繁多，紋理元素之間顏色差異大或存在漸變，圖像前/背景顏色相近似等復(fù)雜形態(tài)時，該方法獲得的紋理元素提取效果往往較差。而僅采用基于形狀特征匹配的方法[4]只能夠提取出與用戶所選模板具有相似輪廓的紋理元素。因此當(dāng)紋理圖像中紋理元素之間存在遮擋或形變嚴(yán)重時，該方法產(chǎn)生的紋理元素提取效果亦不理想。因此，對于交互式圖像分割方法的改進(jìn)仍然是必要的：一方面，用于進(jìn)行外觀相似性度量的方式較單一，導(dǎo)致這些方法在使用上存在較大的局限性；另一方面，現(xiàn)階段對于紋理元素的提取主要是應(yīng)用于紋理圖像的編輯與處理，包括紋理合成與設(shè)計、紋理轉(zhuǎn)移等，然而現(xiàn)有基于樣圖的紋理合成方法[8-11]在處理這類具有大量紋理元素的紋理圖像時，無法保持合成的紋理結(jié)果中紋理元素的完整性，以致產(chǎn)生不連續(xù)或斷裂的紋理結(jié)構(gòu)。雖然現(xiàn)有基于基元分布的紋理合成方法[12-14]解決了這一問題，但這些方法往往需要耗費大量的時間用于紋理元素的提取，從而極大地降低了紋理合成的效率。因此，如何快速地提取紋理圖像中的紋理元素已成為紋理圖像編輯與處理技術(shù)中亟待解決的關(guān)鍵問題，這也為本文的研究提供了新的思路與突破點。

本文提出了一種高效的交互式紋理圖像中紋理元素的提取方法。通過建立一種魯棒的外觀相似性度量機制，從而能夠更精確地捕獲紋理圖像中重復(fù)的紋理元素；在此基礎(chǔ)上進(jìn)一步優(yōu)化現(xiàn)有圖割模型[5,15-17]，通過對紋理圖像中重復(fù)紋理元素的同時提取，極大地提高了紋理元素提取的時間效率，從而為紋理圖像的編輯與處理進(jìn)一步奠定了良好基礎(chǔ)。

2　相關(guān)工作

圖像分割是圖像處理領(lǐng)域的研究熱點之一，即通過將圖像中的目標(biāo)對象與背景內(nèi)容分離，來達(dá)到提取感興趣區(qū)域的目的。現(xiàn)有圖像分割技術(shù)主要分為兩大類：自動的圖像分割方法[18-21]和交互式的圖像分割方法[1-7,15-17,22-24]。雖然自動的圖像分割方法操作簡便，且自適應(yīng)性能強，但是交互式的圖像分割方法普遍準(zhǔn)確率更高，并且具有主觀能動性，能更好地滿足用戶分割圖像的要求。因此，本文主要側(cè)重于研究交互式的圖像分割技術(shù)。

2001年，Boykov等人[15-17]提出了Graphcut算法，該方法構(gòu)建了一種基于聯(lián)合概率分布的計算模型，并通過圖的最大流/最小割（max flow/min cut）算法解決能量的最優(yōu)化問題，因而具有良好的分割性能。2004年，Rother等人[22]提出了一種更加優(yōu)化的圖割算法（Grabcut），該方法將前/背景建模為RGB三通道的高斯混合模型（Gaussian mixture model，GMM），并通過迭代求解最佳能量劃分，從而使得分割效果更加優(yōu)化。同年，Li等人[23]提出了一種“懶人”摳圖方法（LazySnapping），該方法在Graphcut算法基礎(chǔ)上，用多邊形描繪目標(biāo)對象的邊界，并對多邊形的節(jié)點通過拖拽的方式加以調(diào)節(jié)，從而極大地提高了圖像分割的精準(zhǔn)度。2010年，Gulshan等人[24]提出了一種新的基于形狀約束的交互式圖像分割算法，該算法通過擴充凸面上的星型先驗圖的概念，從而使得用戶僅通過選中凸面中心點的少量交互即可精準(zhǔn)地獲得目標(biāo)凸面。同年，肖春霞等人[25]提出了一種有效的邊緣停止函數(shù)，該函數(shù)采用多尺度圖像增強，并通過高斯混合模型進(jìn)行顏色匹配以引導(dǎo)level set函數(shù)演化，從而使得level set能精確地分割出目標(biāo)對象的邊緣。2011年，趙在新等人[26]提出了一種基于活動輪廓的雙紋理圖像分割算法，該算法通過結(jié)合半局部的方向性與非線性結(jié)構(gòu)張量構(gòu)造4通道紋理特征，從而能夠自適應(yīng)高效地實現(xiàn)復(fù)雜雙紋理圖像的分割。2013年，張會等人[27]提出了一種基于顏色和紋理的顯著性區(qū)域提取方法，該方法通過將原圖像的L、a、b三通道轉(zhuǎn)化為亮度圖像，綜合亮度圖像中Gabor濾波器產(chǎn)生的4個方向的紋理圖與Lab圖，從而有效地提取出輸入紋理圖像中的顯著部分。

然而，上述圖像分割技術(shù)[15-17,22-24]與紋理分割方法[25-27]僅適用于對圖像中的某一個感興趣目標(biāo)對象進(jìn)行提取，如若提取圖像中的多個感興趣目標(biāo)對象，例如在本文待處理的紋理圖像中存在的大量重復(fù)的紋理元素[28]，則需要用戶逐一地進(jìn)行處理。此時，不僅需要用戶提供大量的人工交互，導(dǎo)致分割效率低下，而且不一定產(chǎn)生高質(zhì)量的紋理元素提取結(jié)果。因此，如何通過少量的用戶交互達(dá)成多個目標(biāo)對象的同時提取已成為圖像分割領(lǐng)域新的研究熱點。

1996年，Leung等人[1]提出了一種重復(fù)場景元素檢測、定位算法，該算法通過估計用戶交互的圖像子塊與相鄰圖像子塊之間的仿射變換，將相似的圖像子塊擴張成為一個更大的連通域，從而達(dá)到快速聚類重復(fù)場景元素的目的。2004年，Liu等人[2]提出了一種基于周期方向感知計算模型的紋理分割算法，該算法通過自動識別周期方向圖中的對稱元素，提取其中的基礎(chǔ)單元子塊，從而能夠自動地檢測紋理元素。2007年，Ahuja等人[3]提出了一種同時提取2.1D自然重復(fù)場景元素的算法，該算法將具有相似結(jié)構(gòu)的可視紋理元素部分表現(xiàn)為子樹的形式，建立光學(xué)與幾何學(xué)的聯(lián)合樹學(xué)習(xí)模型，并匹配學(xué)習(xí)模型與原圖像的分割樹，從而較好地處理了2.1D自然場景元素的遮擋問題。2010年，Cheng等人[4]提出了一種基于邊界帶圖的重復(fù)元素檢測算法，該算法通過用戶選定模板，并逐一匹配模板與待檢測區(qū)域的邊界帶圖，從而能夠檢測出具有一定程度遮擋或不完整的重復(fù)場景元素。2011年，Huang等人[5]提出了一種基于優(yōu)化的圖割模型的重復(fù)元素提取算法，該算法通過度量像素點之間的相似性，并在圖中建立連接相似重復(fù)元素的邊來改進(jìn)經(jīng)典的圖割模型，從而能夠?qū)崿F(xiàn)重復(fù)場景元素的同時提取。2012年，Zhang等人[6]提出了一種使用半自動圖像編輯框架的重復(fù)元素檢測算法，該算法采用對象級操作，并利用重復(fù)元素的外觀曲線相似程度對其進(jìn)行分割，從而順利解決了提取過程中不同層面上重復(fù)元素的遮擋問題。2013年，Xu等人[7]提出了一種綜合考慮空間距離、取樣位置和外觀特征的稀疏控制模型，該模型以最佳的方式解決了稀疏控制帶來的歧義性，能夠廣泛應(yīng)用于用戶交互工作的引導(dǎo)，從而大大降低了交互的復(fù)雜度。

雖然上述方法均能不同程度地實現(xiàn)自然場景中重復(fù)元素或紋理圖像中紋理元素的提取，但是仍沒有一種方法是通用的，即能夠很好地處理具有各類復(fù)雜場景的圖像。因此，在改進(jìn)現(xiàn)有圖像分割方法進(jìn)行重復(fù)元素提取時，如何獲得高質(zhì)量的提取結(jié)果以及如何提高算法的時間效率依然是圖像分割的一個重要研究方向。

3　優(yōu)化的圖割模型

經(jīng)典圖割算法Graphcut將原圖像表示為圖G=(P,N)，如圖1（b）所示。其中P為以像素點為節(jié)點的點集，N為連接像素點的邊的集合，s和t分別代表源端點和終端點。圖G中每一條邊都附有相應(yīng)的權(quán)值，且邊的權(quán)值表示節(jié)點之間的差異。另外，圖G中每一個節(jié)點都與s點和t點相連接，且邊的權(quán)值為無窮大。

Graphcut算法將圖像分割轉(zhuǎn)換為圖的最優(yōu)劃分問題，根據(jù)圖G定義馬爾科夫隨機場（Markov random field，MRF）能量公式E，并獲得使能量公式E最小化的標(biāo)簽分配方案。此時，圖中的每一個像素點都取得了一個“0”或“1”的標(biāo)簽。其中，標(biāo)簽“1”表示將該像素點標(biāo)記為前景，否則反之。由此，該算法根據(jù)獲得的標(biāo)簽將圖像I劃分為前景與背景，即實現(xiàn)圖像的最優(yōu)分割。

Fig.1　Illustration for graph cnstruction圖1Graph構(gòu)建示意圖

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

其中，Dp為數(shù)據(jù)項，用于度量像素點p與標(biāo)簽 fp的一致性，通常來源于先驗信息；Vp,q為平滑項，用于度量相鄰像素點p與q之間的標(biāo)簽過渡平滑性；fi∈{0,1}為像素點i的標(biāo)簽。

Graphcut算法能夠較好地處理單個目標(biāo)對象的分割問題，主要是由于平滑項約定p與q的距離僅為相鄰像素點之間的空間距離（通常取4-連通或8-連通鄰域）。由此，當(dāng)原圖像中出現(xiàn)大量重復(fù)場景元素時，該圖割算法則需要用戶對目標(biāo)對象逐一地進(jìn)行交互，這在增加用戶輸入工作量的同時，也降低了圖像分割方法的時間效率。

針對Graphcut算法在圖像分割中存在的不足，Huang等人[5]充分利用重復(fù)元素之間具有的外觀相似特性提出了一種新的目標(biāo)對象提取方法——Rep-Snapping算法。算法通過建立相距較遠(yuǎn)且外觀相似的像素點之間的連接關(guān)系，從而進(jìn)一步改進(jìn)Graphcut算法中的圖割模型，改進(jìn)的能量公式E(f)定義如下：

其中，等式右端中增加的能量項Ui,j為特征空間上的重復(fù)項，用于度量顏色特征上相似像素點i與j之間的標(biāo)簽過渡平滑性。在能量公式Ε(f)中，RepSnapping算法通過引入度量外觀相似性的重復(fù)項，能夠連接空間距離較遠(yuǎn)但顏色相近的像素點對。由此，僅在提供少量用戶交互的情況下，該算法也能同時提取大規(guī)模的重復(fù)場景元素，從而極大地提高圖像分割算法的時間效率。

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

4　重復(fù)紋理元素的提取

雖然RepSnapping算法已經(jīng)能夠?qū)崿F(xiàn)重復(fù)元素的同時提取，但該方法僅僅在顏色特征上進(jìn)行相似性度量。當(dāng)多個目標(biāo)對象之間顏色差異較大或前/背景顏色相近時，該方法的提取效果不是很理想。因此，本文進(jìn)一步改進(jìn)RepSnapping算法，提出了一種新的交互式的圖像分割方法，其算法流程如圖2所示，主要用于提取紋理圖像中大量的重復(fù)紋理元素。

本文算法主要由以下3部分組成：用戶交互、圖像預(yù)處理和紋理元素提取。

在用戶交互中，用戶僅標(biāo)記紋理圖像中一到兩個顏色顯著和形狀完整的紋理元素作為前景，并同樣標(biāo)記與前景位置較為相近的顏色顯著的背景區(qū)域作為背景，這樣標(biāo)記前/背景區(qū)域可以有效避免因前/背景具有相近似特征時造成分割不理想的情況。另外，紋理圖像中目標(biāo)前景數(shù)目較多且相互之間排布緊密，因而紋理圖像的背景區(qū)域通常較為狹小或不具有紋理背景，需要用戶較細(xì)致地標(biāo)記前景和背景區(qū)域。

在圖像預(yù)處理中，本文采用顏色聚類方法，將原圖像分割成相互獨立且連通的圖像子塊。圖像預(yù)處理的目的在于：在圖的構(gòu)建中使用圖像子塊代替像素點作為圖中的節(jié)點，使得能夠大大減少圖像分割過程中的計算量，提高算法的時間效率。

在紋理元素提取中，通過分析紋理圖像的紋理特征，并將紋理特征與顏色特征相結(jié)合，從而定義一個魯棒的外觀相似性度量公式。在此基礎(chǔ)上，進(jìn)一步改進(jìn)現(xiàn)有圖割模型，從而實現(xiàn)紋理元素的同時提取，并提高紋理圖像中紋理元素提取的準(zhǔn)確率。

本文算法通過圖像的預(yù)處理，將紋理圖像聚類成具有獨立特征的圖像子塊并運用于圖G的構(gòu)建，極大地降低了算法的冗余計算量；通過結(jié)合紋理特征，構(gòu)建一個更加穩(wěn)健的多尺度相似性度量公式并運用于圖割模型的改進(jìn)，極大地改善了紋理圖像中紋理元素提取結(jié)果。

4.1紋理圖像的預(yù)處理

一幅圖像中往往具有大量的像素點，特別是高清圖像?，F(xiàn)有圖割算法通常利用像素點的空間相鄰關(guān)系構(gòu)建4-連通或8-連通的拓?fù)浣Y(jié)構(gòu)，對圖像中大量的像素點建立點對點連通關(guān)系會使得圖中的節(jié)點以及節(jié)點之間的連接邊都數(shù)量龐大，且這一過程將會耗費大量的時間代價。尤其當(dāng)RepSnapping算法[5]在圖的構(gòu)建中增加了連接具有一定特征相似的像素點對之間的連通關(guān)系后，任意兩像素點間都有可能建立起一條連接邊，使得像素點之間的拓?fù)鋱D顯得更加雜亂（如圖3所示），即在某種程度上限制了算法的運行效率。

為了降低算法的計算負(fù)荷，本文采用均值漂移（mean shift）聚類算法[18]將原圖像分割成若干個相互獨立且各區(qū)域連通的圖像子塊。為了便于觀察，將顏色聚類后的多個圖像子塊區(qū)域分別用不同顏色進(jìn)行填充（如圖4（b）所示）。此時，圖像子塊區(qū)域?qū)⒃趫D的構(gòu)建中取代原圖像中的像素點作為圖中的節(jié)點。

Fig.3　Extended connectivity based on pixels圖3　基于像素點的擴展連通圖

將原圖像進(jìn)行區(qū)域劃分后，圖中各圖像子塊與其相鄰圖像子塊不再是簡單的4-鄰域或8-鄰域連通關(guān)系（如圖1所示）。由于各圖像子塊的相鄰圖像子塊的數(shù)目會各不相同，并且在距離和方向上也各有差異，連通關(guān)系的構(gòu)建將具有不確定性。因此，為了建立各圖像子塊之間的連通關(guān)系，本文首先獲得包圍各圖像子塊的矩形框，并取其中心點位置信息代替原圖像中的圖像子塊位置信息，以及用圖像子塊的平均RGB顏色值作為圖像子塊的顏色特征，如圖4 （c）所示。然后，通過采用Delaunay三角剖分構(gòu)建圖像子塊與相鄰圖像子塊之間的連通關(guān)系，用于代替現(xiàn)有圖構(gòu)建中的4-鄰域或8-鄰域連通關(guān)系，如圖4 （d）所示。另外，記錄的各圖像子塊間的相鄰關(guān)系將會用于后續(xù)的紋理元素提取過程。

4.2基于外觀相似性度量的紋理元素提取

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

圖像分割中最常采用的特征是顏色特征，這主要是因為顏色特征具有易提取、易分辨等顯著優(yōu)點。但是，紋理圖像中的紋理元素除顏色特征以外，通常還存在如紋理特征、形狀特征等另外一些顯著的特征。僅基于顏色特征的分割算法雖然操作簡單且辨識度高，但這些方法對呈現(xiàn)一致色調(diào)或前/背景顏色差異不明顯的圖像并不能很好地處理，存在較大局限性。因此，本文定義了一種更加魯棒的外觀相似性度量機制，即通過融合多種特征捕獲紋理元素之間的相似程度，從而改善紋理元素提取結(jié)果的質(zhì)量。

除利用顏色特征之外，本文通過采用Gabor小波變換對紋理圖像中的紋理特征進(jìn)行分析。Gabor濾波[29]是一種最佳的紋理特征描述方式，它能夠在空間域和頻率域上最小化聯(lián)合二維的不確定性。Gabor濾波在多尺度和多方向上類似于人類的視覺系統(tǒng)，因而能夠較好地表達(dá)圖像中的紋理特征。

Fig.4　Image preprocessing圖4 圖像預(yù)處理

二維Gabor濾波器是一個高斯核函數(shù)和正弦平面波的乘積，其Gabor函數(shù)g(x,y)表示為：

Gabor函數(shù)g(x,y)的傅里葉變換G(u,v)如下所示：

其中，σu=。

通過膨脹和旋轉(zhuǎn)小波系數(shù)可以獲得一類自相似濾波函數(shù)gm,n(x,y)：

因此，給定原圖像I(x,y)，其Gabor小波變換Wm,n(u,v)如下：

其中，上標(biāo)*表示復(fù)共軛；下標(biāo)m和n分別表示多個尺度和方向。

在各尺度和方向上分別計算Gabor小波變換系數(shù)的均值 μm,n和標(biāo)準(zhǔn)差σm,n：

由此，紋理特征T是由M個尺度和N個方向（通常取M=4，N=6）上的均值 μm,n和標(biāo)準(zhǔn)差σm,n組成的特征向量：

結(jié)合顏色特征和紋理特征，圖像子塊i和圖像子塊j之間的外觀相似性度量公式δ(i,j)定義如下：

4.2.2圖的構(gòu)建

本文通過圖像預(yù)處理后得到圖像子塊之間的連通關(guān)系圖（如圖4（d）所示），在此基礎(chǔ)上，將原圖像仍構(gòu)建為圖G=(P,N)，如圖5所示。此時，P為以圖像子塊為節(jié)點的點集；N為連接圖像子塊之間的邊的集合，包括直接相鄰的圖像子塊之間的邊和具有相似特征的圖像子塊之間的邊（不一定直接相鄰）；s和t分別代表源端點和終端點，且圖G中每一個節(jié)點都與s點和t點相連接。圖像子塊 j在紋理特征上的差異，Ti與Tj分別為圖像子塊i與 j的紋理特征向量。本文分別取以圖像子塊內(nèi)每個像素點為中心的k×k的區(qū)域，計算這些局部區(qū)域的Gabor特征向量并求平均，由此得到圖像子塊i和 j的紋理特征Ti和Tj。需要指出的是，對于不同的紋理圖像，k的取值不同，使得能夠提取到顯著的紋理特征即可。另外，

Fig.5　Construction of Graph G圖5圖G的構(gòu)建

在計算圖G中每條連接邊的權(quán)值后，通過使用最大流/最小割算法尋求一條最佳分割路徑（所有邊的權(quán)值之和最?。?，即實現(xiàn)了圖G的最優(yōu)劃分。圖G中每條邊的權(quán)值可由能量公式（式（2））計算得到，其中連接直接相鄰節(jié)點之間的邊的權(quán)值取決于能量公式中的平滑項，而連接具有外觀相似節(jié)點之間的邊的權(quán)值則取決于能量公式中的重復(fù)項。

由此，數(shù)據(jù)項Dp定義如下：

其中，P為圖G中節(jié)點的集合，即由圖像子塊的中心點組成；fp為節(jié)點p的標(biāo)簽；分別為p點到前景F與背景B中子區(qū)域顏色上的最小距離，可由下列等式計算得到：

其中，{KnF}和{KnB}為由k-means算法分別聚類前景與背景得到的一系列的簇。

為了獲得高質(zhì)量的紋理元素提取結(jié)果，本文結(jié)合顏色特征和紋理特征用于度量圖像子塊之間的外觀相似性，相似程度可由式（10）計算得到。因此，平滑項Vp,q進(jìn)一步改寫為：

其中，λ為權(quán)重系數(shù)；β為常數(shù)，用于控制當(dāng)相鄰圖像子塊被劃分不同標(biāo)簽值時的差異容限；δ(p,q)為度量節(jié)點p與q之間相似度的距離；N是由圖G中直接相鄰節(jié)點對組成的集合。

對于圖G中任意兩個圖像子塊i和圖像子塊 j，當(dāng)它們之間的相似度小于指定的閾值ε時，圖像子塊i和圖像子塊 j則被認(rèn)為是屬于特征空間H上相鄰的節(jié)點對。因此同樣地，重復(fù)項Ui,j可進(jìn)一步改寫為：

其中，μ為權(quán)重系數(shù)；H為連接擴展空間上具有外觀相似特征節(jié)點對的集合。

5　實驗結(jié)果與分析

本文在硬件環(huán)境為2.2 GHz CPU，內(nèi)存2 GB的PC機上使用VC++和OpenCV實現(xiàn)紋理元素提取算法。為了驗證了本文算法的有效性和實用性，分別在算法時間效率與紋理元素提取結(jié)果兩個方面與現(xiàn)有的圖像分割方法[5,22-23]進(jìn)行了對比。

5.1算法時間效率的比較

對于同一幅紋理圖像，Grabcut算法、LazySnapping算法、RepSnapping算法和本文算法得到理想的分割結(jié)果所需要的用戶交互數(shù)不同，這也一定程度上影響了算法的時間效率。因此，對上述4種算法在處理各種尺寸的紋理圖像所需的交互數(shù)量進(jìn)行了統(tǒng)計，如表1所示。

Table 1　User interaction statistics for various texture images表1　不同圖像用戶交互的統(tǒng)計

由表1可知，在對紋理圖像中的紋理元素進(jìn)行提取時，Grabcut與LazySnapping算法的交互次數(shù)遠(yuǎn)大于RepSnapping和本文算法，并且圖像的大小發(fā)生變化時，交互次數(shù)亦有較大增加。由于前兩種方法僅適用于單個目標(biāo)對象的提取，從而紋理圖像中的紋理元素越多，所需的用戶交互次數(shù)也就越多。相反，RepSnapping與本文算法在處理紋理圖像時僅需要提供少量的用戶交互，即不需要對紋理元素逐一標(biāo)記，并且用戶交互次數(shù)也不會隨著紋理元素數(shù)量的增加而發(fā)生明顯的變化，因而使得用戶交互過程能夠最大程度地簡便及高效。

為了比較以上幾種分割算法的紋理元素提取時間效率，本文對紋理元素提取時間代價進(jìn)行逐一統(tǒng)計，具體內(nèi)容如表2所示。需要指出的是，表2中的紋理元素提取時間泛指算法在圖像分割過程中的時間消耗，不包括用戶交互的時間與圖像預(yù)處理所耗費的時間。

Table 2　Running time statistics for texture elements extraction表2　紋理元素提取時間的統(tǒng)計

由表2可以看出，Grabcut算法的分割時間最長，LazySnapping算法的分割時間最短，RepSnapping與本文算法的分割時間位于二者之間。由于Grabcut算法在能量最優(yōu)化中需要進(jìn)行迭代求解，導(dǎo)致該算法在迭代過程中需要消耗大量時間以保證紋理元素提取的效果；而LazySnapping、RepSnapping以及本文算法則均是一次性實現(xiàn)能量的最優(yōu)劃分，因此分割時間相對較短。另外，RepSnapping與本文算法的提取時間指同時提取圖像中全部紋理元素的總時間，而Grabcut與LazySnapping算法則指提取一個目標(biāo)對象所需的時間。如若提取一幅紋理圖像中所有紋理元素，則需要的時間也會成倍增加。由此可見，Rep-Snapping與本文算法在時間效率上有較大的提升。

5.2提取結(jié)果的比較

圖6給出了本文算法與現(xiàn)有的3種圖像分割算法[5,22-23]的實驗結(jié)果比較。其中，圖6（a）為原圖像；圖6（b）為Grabcut算法得到的實驗結(jié)果；圖6（c）為LazySnapping算法得到的實驗結(jié)果；圖6（d）為Rep-Snapping算法得到的實驗結(jié)果；圖6（e）為本文算法得到的實驗結(jié)果。

由圖6給出的實驗結(jié)果可以看到，待處理的紋理圖像具有紋理元素之間顏色差異大，形態(tài)多且復(fù)雜的特點。在圖6第一行中，原圖像由多個大小不一的石頭組成，其中每個石頭內(nèi)部顏色不統(tǒng)一，相互之間顏色不相同且與背景顏色相似。若使用Grabcut算法對這些紋理元素進(jìn)行提取，那么需要用戶在各個目標(biāo)紋理上逐一標(biāo)記，需要大量的用戶交互，且分割效果較差。如圖6（b）第一行所示，該方法僅能分割出矩形框內(nèi)用戶交互的目標(biāo)紋理元素，不能檢測出與其外觀相似的紋理元素，也不能將與目標(biāo)前景顏色相近的圖像背景分割出來；LazySnapping算法的提取效果較好于Grabcut算法（如圖6（c）第一行所示），原因是在該算法自動提取完成后仍可以通過人工交互對提取的紋理邊界進(jìn)行修改，直到用戶滿意。但這類方法同樣只能提取出標(biāo)記為前景種子的紋理元素，并且邊界的調(diào)整需要耗費大量的時間；RepSnapping算法處理這類紋理圖像的優(yōu)點在于可以同時提取外觀相似的紋理元素，因此僅需要較少的交互內(nèi)容，但是該紋理圖像的前/背景顏色相近似，在該方法構(gòu)建的顏色特征空間上沒有明顯差異，因此得到的分割效果十分不理想（如圖6（d）第一行所示）；在本文提出的基于改進(jìn)的圖割模型的圖像分割方法中，通過結(jié)合顏色特征和紋理特征用于紋理元素之間的外觀相似性的度量，能夠明確地提取目標(biāo)前景，并分離圖像背景。另外，本文算法僅需要少量的用戶交互與編輯即能得到較好的分割效果（如圖6（e）第一行所示）。

Fig.6　Experimental results comparison for algorithms圖6 算法結(jié)果對比圖

在圖6第二行與第三行中，咖啡豆與鋼板花紋圖像中的紋理元素均尺寸較小且分布密集，給用戶交互帶來一定的困難，使得現(xiàn)有的3種圖像分割方法[5,22-23]不能提取出完整的紋理元素（如圖6（b）、（c）、（d）第二、三行所示）；本文算法則能夠提取出較為完整的紋理元素，但是在前景與背景顏色及紋理均較相近的部分，也一定程度上存在缺失。

在圖6第四行中，獼猴桃表面與其斑點顏色十分相似，Grabcut算法能提取出標(biāo)記位置的紋理元素，但提取出的紋理元素形狀大多發(fā)生了改變（如圖6（b）最后一行所示）；LazySnapping算法提取出的紋理元素較為完整，但是這需要用戶進(jìn)行大量的交互并反復(fù)調(diào)整邊界（如圖6（c）最后一行所示）；RepSnapping算法在僅提供少量用戶交互的情況下，由于前/背景顏色相近似，得到的分割效果十分不理想（如圖6（d）最后一行所示）；本文算法不僅能夠同時提取出所有紋理元素，且這些紋理元素均能保持完整的結(jié)構(gòu)與形態(tài)，與文中提到的其他方法比較，具有較好的分割性能。需要指出的是，用戶交互時，應(yīng)選擇紋理圖像中顏色特征顯著且紋理特征清晰的紋理元素標(biāo)記作為前景，并選擇與標(biāo)記的目標(biāo)前景位置較為相近且同樣具有顯著顏色或紋理特征的背景區(qū)域作為背景。這是因為在具有歧義性的區(qū)域進(jìn)行用戶交互，可以有效避免在前/背景具有相近似外觀特征時造成分割不理想的情況。然而，用戶交互的細(xì)致程度能夠很大程度上影響紋理元素的分割效果。因此，如若選取的前/背景區(qū)域不具備較為明顯的顏色或紋理特征，分割效果并不理想。

另外，為了驗證本文算法的可行性，對具有大量重復(fù)元素的自然場景圖像與紋理圖像進(jìn)行實驗，更多的實驗結(jié)果如圖7所示。從圖中可以看出，該實驗結(jié)果很大程度上保持了重復(fù)場景元素的完整性，證明了本文算法運用的廣泛性與靈活性。

Fig.7　More experimental results圖7 更多實驗結(jié)果圖

6　結(jié)束語

本文針對優(yōu)化的圖割算法進(jìn)行改進(jìn)，在Rep-Snapping算法的基礎(chǔ)上引入紋理特征的度量，建立了一個更加魯棒的相似性度量公式。因此，對于前景與背景顏色差異不明顯的紋理圖像，本文算法也能精準(zhǔn)地度量紋理元素之間相似程度。另外，通過結(jié)合新的相似性度量公式改進(jìn)現(xiàn)有圖割模型，實現(xiàn)紋理圖像中具有相似外觀特征的紋理元素的同時提取，并且獲得高質(zhì)量的紋理元素提取結(jié)果，較好地處理顏色特征差異不顯著的紋理圖像。

本文算法也一定程度上存在缺陷，當(dāng)提取的目標(biāo)之間不存在紋理特征，且前/背景顏色特征差異不明顯時，提取效果不太理想。另外，由于引入了紋理特征用于外觀相似性的度量，本文算法在預(yù)處理部分耗時較多，時間效率上還有待提高。如何解決以上問題也將成為本文以后探討紋理圖像處理的主要方向。

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.

附中文參考文獻(xiàn)：

[25]肖春霞,初雨,張青.高斯混合函數(shù)區(qū)域匹配引導(dǎo)的Level Set紋理圖像分割[J].計算機學(xué)報,2010,33(7):1295-1304.

[26]趙在新,成禮智.結(jié)合半局部信息與結(jié)構(gòu)張量的無監(jiān)督紋理圖像分割[J].中國圖象圖形學(xué)報,2011,16(4):559-565.

[27]張會,劉士榮,張波濤.一種基于顏色和紋理的顯著區(qū)域提取算法[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,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—），女，湖南常德人，長沙理工大學(xué)計算機與通信工程學(xué)院碩士研究生，主要研究領(lǐng)域為數(shù)字圖像處理，可視媒體編輯與處理等。

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—），男，湖南澧縣人，博士，長沙理工大學(xué)教授、碩士生導(dǎo)師，主要研究領(lǐng)域為圖像處理，模式識別，計算機視覺，信息安全等。

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年于上海交通大學(xué)獲得博士學(xué)位，現(xiàn)為長沙理工大學(xué)講師、碩士生導(dǎo)師，主要研究領(lǐng)域為數(shù)字圖像處理，計算機圖形學(xué)，可視媒體編輯與處理等。

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

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-08-27,http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1504.010.html

文獻(xiàn)標(biāo)志碼：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