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

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

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

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

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

1　引言

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

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

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

2　相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.3　Extended connectivity based on pixels圖3　基于像素點(diǎn)的擴(kuò)展連通圖

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

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

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

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

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

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

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

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

其中，σu=。

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

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

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

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

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

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

4.2.2圖的構(gòu)建

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

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

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

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

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

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

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

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

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

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

5　實(shí)驗(yàn)結(jié)果與分析

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

5.1算法時(shí)間效率的比較

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.7　More experimental results圖7 更多實(shí)驗(yàn)結(jié)果圖

6　結(jié)束語(yǔ)

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

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

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].計(jì)算機(jī)學(xué)報(bào),2010,33(7):1295-1304.

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

[27]張會(huì),劉士榮,張波濤.一種基于顏色和紋理的顯著區(qū)域提取算法[J].華中科技大學(xué)學(xué)報(bào):自然科學(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—），女，湖南常德人，長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?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—），男，湖南澧縣人，博士，長(zhǎng)沙理工大學(xué)教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閳D像處理，模式識(shí)別，計(jì)算機(jī)視覺(jué)，信息安全等。

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)為長(zhǎng)沙理工大學(xué)講師、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閿?shù)字圖像處理，計(jì)算機(jī)圖形學(xué)，可視媒體編輯與處理等。

*The National Natural Science Foundation of China under Grant No.61402053(國(guó)家自然科學(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

中圖分類號(hào)：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