薛麗霞, 孫 偉, 汪榮貴, 楊 娟, 胡 敏

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230601)

圖像分割是圖像處理領(lǐng)域和計(jì)算機(jī)視覺領(lǐng)域中的經(jīng)典難題之一,其目的是從圖像中將感興趣區(qū)域與其他部分進(jìn)行分離并提取出來。隨著計(jì)算機(jī)處理能力的提高以及對圖像處理需求的增加,圖像分割更是受到研究者們越來越多的關(guān)注,它是許多高層視覺任務(wù)的基礎(chǔ),如場景識別、圖像理解、視頻目標(biāo)追蹤等。由于自然圖像類型的多樣性以及內(nèi)容的復(fù)雜性,再加上理想分割目標(biāo)對于人類主觀視覺感知的依賴性,完全自動式圖像分割方法顯然不具有較好的實(shí)用性。目前,融合用戶先驗(yàn)知識的交互式分割已逐漸成為圖像分割中流行的方法。文獻(xiàn)[1]提出的Graph Cut方法將圖割應(yīng)用到灰度圖像前景提取領(lǐng)域,用戶只需指定一部分區(qū)域作為前景和背景;文獻(xiàn)[2]提出的Grab Cut方法利用高斯混合模型對前景和背景的顏色空間進(jìn)行建模,并采用迭代的圖割進(jìn)行圖像分割。上述方法雖然能夠?qū)崿F(xiàn)較好的分割效果,但是都以像素為基本處理單元,在計(jì)算效率上很難滿足實(shí)際應(yīng)用要求。

2003年,文獻(xiàn)[3]首次提出超像素概念,并將其應(yīng)用于圖像分割中。經(jīng)過十幾年的發(fā)展,超像素在圖像分割領(lǐng)域中的應(yīng)用日益廣泛?；趫D論的圖像分割算法具有很好的代表性。文獻(xiàn)[4]提出了懶人摳圖(lazy snapping)技術(shù),較之于Graph Cut[1],該方法利用watershed[5]作為預(yù)處理,將得到的超像素作為圖的頂點(diǎn)并用于構(gòu)建圖模型;文獻(xiàn)[6]使用Mean Shift[7]作為初始分割,并利用迭代的圖割進(jìn)行圖像分割;文獻(xiàn)[8]在基于Graph Cut框架的基礎(chǔ)上,通過學(xué)習(xí)超像素間的相關(guān)性,并用它們作為相鄰超像素間邊的權(quán)值來構(gòu)建超像素圖。由于超像素的數(shù)量遠(yuǎn)遠(yuǎn)小于像素,圖的規(guī)模將大大減小?；趨^(qū)域合并的圖像分割方法也是很好的例子。文獻(xiàn)[9]提出了基于區(qū)域合并的最大相似度交互式分割算法(maximal similarity based region merging,MSRM),該算法使用Mean Shift對輸入圖像進(jìn)行初始分割,并依據(jù)局部最大相似度合并策略實(shí)現(xiàn)區(qū)域合并;文獻(xiàn)[10]對MSRM進(jìn)行了改進(jìn),根據(jù)k-全局最大相似度合并策略(即每次區(qū)域合并時(shí)合并前k個(gè)最相似的區(qū)域)來完成圖像分割。盡管這些基于區(qū)域合并的分割算法能夠?qū)崿F(xiàn)較好的分割性能,但在預(yù)處理階段,超像素分割算法(如Mean Shift)通常會產(chǎn)生較多的超像素,使后續(xù)區(qū)域合并操作的代價(jià)大大增加,甚至降低了整個(gè)算法的執(zhí)行效率。Mean Shift過分割圖像如圖1所示。

圖1 原始圖像以及對應(yīng)的Mean Shift過分割圖像

本文提出了一種新的基于邊緣概率的層次交互式圖像分割算法。利用一種性能優(yōu)異的邊緣檢測算子[11](structured edge,SE)作為輸入,得到邊緣概率圖,并作用于現(xiàn)有的超像素分割算法,實(shí)現(xiàn)對超像素的提純;通過計(jì)算相鄰區(qū)域之間的相似度,并依據(jù)全局最大相似度合并準(zhǔn)則,采用區(qū)域鄰接圖[12](region adjacency graph, RAG)和最近鄰圖[13](nearest neighbor graph, NNG)來實(shí)現(xiàn)層次區(qū)域合并,提高區(qū)域合并操作的準(zhǔn)確性。本文方法的流程如圖2所示。

1 本文方法

本文方法主要概括為基于邊緣概率的超像素分割算法、相鄰區(qū)域間相似度計(jì)算和層次區(qū)域合并3個(gè)部分。

1.1 基于邊緣概率的超像素分割算法

1.1.1 人工標(biāo)記的超像素分割

本文給出了超像素提純的流程,如圖3所示。在實(shí)驗(yàn)中,采用Mean Shift生成初始過分割區(qū)域(即超像素),為了對圖像進(jìn)行標(biāo)記,用戶可以輸入任何線條、曲線和筆觸來指定目標(biāo)和背景。本文分別使用綠色、藍(lán)色標(biāo)注所有的初始目標(biāo)區(qū)域和初始背景區(qū)域,如圖3b所示。若一個(gè)區(qū)域中含有綠色目標(biāo)標(biāo)記的像素點(diǎn),則該區(qū)域?yàn)槟繕?biāo)區(qū)域;若一個(gè)區(qū)域中含有藍(lán)色背景標(biāo)記的像素點(diǎn),則該區(qū)域?yàn)楸尘皡^(qū)域;剩余的所有區(qū)域?yàn)闊o標(biāo)記區(qū)域。通常,用戶只需標(biāo)記部分目標(biāo)區(qū)域和背景區(qū)域。如果用戶指定的先驗(yàn)信息越少,那么交互式算法的魯棒性越強(qiáng)。

用戶標(biāo)記完之后,共有帶標(biāo)記的目標(biāo)區(qū)域、帶標(biāo)記的背景區(qū)域、無標(biāo)記區(qū)域3種不同標(biāo)簽類型的區(qū)域,分別記為MO、MB、U。所有的目標(biāo)區(qū)域都應(yīng)該具有相同的標(biāo)記,所有的背景區(qū)域以及無標(biāo)記區(qū)域亦然。

1.1.2 SE+超像素分割算法

實(shí)驗(yàn)中發(fā)現(xiàn)大部分相鄰超像素之間的邊界并非真實(shí)目標(biāo)輪廓。因此,為了更好地提純超像素,本文引入結(jié)構(gòu)化邊緣檢測算子SE[11]。相比于其他方法[14-15],SE法極大地提高了檢測速度。在檢測階段,1個(gè)32×32圖像塊的特征向量X∈R32×32×K(K為通道數(shù)目)輸入到結(jié)構(gòu)化隨機(jī)森林中,通過聯(lián)合多棵決策樹的輸出結(jié)果可以得到圖像的邊緣概率。對于像素點(diǎn)(i,j),將它的邊緣概率值記為Pb(i,j)。圖像bird的邊緣概率圖如圖3c所示。每個(gè)像素點(diǎn)的邊緣概率取值范圍為[0,1]。像素點(diǎn)的邊緣概率值越大,表明其屬于真實(shí)目標(biāo)輪廓的可能性就越大,反之則越小。

對于圖像的邊緣概率圖,對其進(jìn)行二值化操作可得邊緣二值圖,即

(1)

其中,b(i,j)表示像素點(diǎn)(i，j)的二元取值0或255;T為SE閾值。在實(shí)驗(yàn)中,使用邊緣概率圖的邊緣概率均值作為閾值T的值。

利用(1)式對邊緣概率圖執(zhí)行閾值操作可得邊緣二值圖,如圖3d所示。此外,對于相鄰超像素R、Q,需要知道邊界處的像素點(diǎn)是否位于真實(shí)目標(biāo)輪廓。定義如下:

(2)

其中,e(i,j)表示像素點(diǎn)(i,j)是否位于真實(shí)目標(biāo)輪廓;(i,j)∈lRQ,lRQ為R與Q之間公共邊界處的像素點(diǎn)集合。

為了判斷相鄰超像素R、Q是否被合并,定義R、Q的邊界強(qiáng)度arcRQ為:

(3)

若arcRQ>0,則R與Q不合并;否則R與Q合并。

聯(lián)合(1)～(3)式,最終可以得到提純后的超像素圖,如圖3e所示。

1.2 區(qū)域的內(nèi)容表達(dá)與相似度度量

為了更好地指導(dǎo)后續(xù)合并操作,使用歸一化的顏色直方圖作為區(qū)域的特征描述符。首先,將RGB空間中的每個(gè)顏色分量都量化為16級,因此在特征空間中共有16×16×16=4 096個(gè)通道可以用來描述區(qū)域。則區(qū)域R可以表示為:

(4)

本文選擇巴氏系數(shù)[16]度量區(qū)域R、區(qū)域Q的相似度。由于區(qū)域合并過程中僅合并相鄰的2個(gè)區(qū)域,對于不相鄰的2個(gè)區(qū)域,它們之間的相似度置為0。則區(qū)域R、區(qū)域Q的相似度定義為:

ρ(R,Q)=

(5)

1.3 層次區(qū)域合并

本文利用RAG和NNG來實(shí)現(xiàn)層次區(qū)域合并。RAG表示區(qū)域間的拓?fù)潢P(guān)系,NNG則對區(qū)域間的拓?fù)潢P(guān)系進(jìn)行抽樣簡化,反映了合并的順序。通過RAG與NNG的聯(lián)合,本文構(gòu)建了一個(gè)快速、高效的區(qū)域合并方法。

RAG為無向簡單圖,其頂點(diǎn)為區(qū)域,邊為拓?fù)潢P(guān)系。一幅m個(gè)區(qū)域的圖像可以表示為G=(V,E)。其中,V={v1,v2,…,vm},為圖像的頂點(diǎn)集,表示圖像的區(qū)域;E表示圖像的區(qū)域相鄰連接關(guān)系,E?V×V，在圖結(jié)構(gòu)中為邊集,其權(quán)重w(vi,vj)為區(qū)域之間的相似度,可由(5)式計(jì)算。本文給出了一個(gè)區(qū)域劃分以及對應(yīng)的區(qū)域鄰接圖,如圖4所示。

圖4 區(qū)域劃分以及對應(yīng)的區(qū)域鄰接圖

在區(qū)域合并過程中,通過尋找RAG中的全局最大相似度邊,并將相應(yīng)頂點(diǎn)進(jìn)行合并,更新RAG。如此反復(fù)執(zhí)行,最終可實(shí)現(xiàn)圖像分割任務(wù)。但是在尋找全局最大相似度邊時(shí),需要不斷對邊集進(jìn)行排序,這是一個(gè)極為耗時(shí)的過程。另外,在區(qū)域合并時(shí),只有部分區(qū)域的拓?fù)浣Y(jié)構(gòu)發(fā)生改變,此時(shí)只會影響RAG部分邊的權(quán)值。NNG則是簡化區(qū)域間的拓?fù)潢P(guān)系,僅保留每個(gè)頂點(diǎn)中最大相似度的邊描述圖像區(qū)域。對于給定的RAG圖G=(V,E),NNG為有向圖Gm=(Vm,Em),其中Vm=V,邊集合Em可表示為:

Em={(vi,vj)|wm(vi,vj)=

maxw(vi,vk),(vi,vk)∈E}

(6)

其中,wm(vi,vj)為頂點(diǎn)vi相關(guān)聯(lián)的指向其最相近區(qū)域vj的最大相似度邊。對于NNG圖的頂點(diǎn)序列,若始點(diǎn)與終點(diǎn)相一致,則稱其為環(huán)。圖4b對應(yīng)的一個(gè)可能的NNG圖，如圖5所示。由圖5可知,頂點(diǎn)序列v4v5v4(或v5v4v5)為環(huán),v4與v5為2個(gè)區(qū)域互為最相似的區(qū)域,即該NNG中拓?fù)渥訄D的最優(yōu)合并區(qū)域?qū)Α?/p>

圖5 最近鄰圖

易證得NNG的下列性質(zhì)[13]:

(1) 沿著邊的方向,權(quán)值逐漸減小。

(2) 環(huán)的最大長度為2。

(3) 至少存在1個(gè)子圖,即至少有1個(gè)環(huán)。

由性質(zhì)(3)可知,若NNG中不存在環(huán),則區(qū)域合并將終止,即在區(qū)域合并終止之前,總能找到至少一個(gè)區(qū)域?qū)M(jìn)行合并。由性質(zhì)(4)可知,NNG中環(huán)集合的數(shù)量小于邊的數(shù)量,因而其搜索和排序的時(shí)間都將大幅降低。在合并期間,只需要維持NNG環(huán),而不必對整個(gè)RAG進(jìn)行搜索。初始的RAG來源于過分割圖像,在搜索每個(gè)頂點(diǎn)的最相似鄰域時(shí)形成NNG。在對NNG進(jìn)行掃描時(shí)可發(fā)現(xiàn)NNG環(huán)。當(dāng)區(qū)域合并終止時(shí),所有的目標(biāo)(背景)都被標(biāo)記為目標(biāo)(背景)標(biāo)簽,此時(shí)的目標(biāo)區(qū)域輪廓即為待提取目標(biāo)的輪廓。

2 實(shí) 驗(yàn)

為了評估本文方法的分割性能,選擇Grab Cut[2]、GSC[17]、 MSRM、CRCM[18]4種不同的分割算法進(jìn)行對比。實(shí)驗(yàn)中所有圖像來源于MSRM分割圖像庫[9]和ASD自然圖像庫[19]。ASD自然圖像庫包含1 000幅自然圖像和1 000幅人工標(biāo)記的真實(shí)分割圖像。

本文的實(shí)驗(yàn)平臺為Matlab 7.12,操作系統(tǒng)為Windows 7 64 bit,CPU為雙核2.60 GHz,RAM為4 G。

2.1 過分割區(qū)域數(shù)量對比

為了驗(yàn)證本文提出的SE+超像素分割算法的有效性,選擇Mean Shift與SE+Mean Shift進(jìn)行對比。實(shí)驗(yàn)中選用ASD自然圖像庫作為測試數(shù)據(jù)集。本文從ASD自然圖像庫中選取5幅自然圖像作為初始分割結(jié)果展示,相應(yīng)圖像的Mean Shift和SE+Mean Shift過分割結(jié)果如圖6所示。2種算法的初始過分割區(qū)域平均數(shù)量對比見表1所列。從實(shí)驗(yàn)結(jié)果來看,SE+Mean Shift能夠產(chǎn)生更少的過分割區(qū)域,并且仍能保持較強(qiáng)的邊界一致性。值得注意的是,本文提出的SE+超像素分割算法具有較強(qiáng)的普適性。當(dāng)前其他一些應(yīng)用較為廣泛的初始過分割算法如watershed[5]、SLIC[20]等,也可以應(yīng)用于本文提出的SE+超像素分割算法模型中。

圖6 Mean Shift和SE+Mean Shift過分割結(jié)果

表1 2種算法的初始過分割區(qū)域平均數(shù)量對比

2.2 本文方法與其他方法的對比

為了對分割質(zhì)量進(jìn)行定量分析,本文以人工分割的結(jié)果作為理想情況,并參考文獻(xiàn)[21]的方法,使用查準(zhǔn)率P、查全率R、F度量進(jìn)行評估。查準(zhǔn)率P代表當(dāng)前分割結(jié)果中準(zhǔn)確分割所占的比例;查全率R代表此準(zhǔn)確分割部分在理想分割結(jié)果中所占的比例;而F度量則為查準(zhǔn)率P與R的線性加權(quán)(加權(quán)系數(shù)參考文獻(xiàn)[21],設(shè)定α=1)。F度量所表示的綜合指標(biāo)值越大,則分割結(jié)果越符合人類視覺的主觀目標(biāo)判斷準(zhǔn)則。定義如下:

(7)

(8)

(9)

其中,N(PG)為真實(shí)目標(biāo)區(qū)域的像素點(diǎn)數(shù)目;N(PO)為由算法計(jì)算得到的目標(biāo)區(qū)域的像素點(diǎn)數(shù)目;N(PO∩PG)為真實(shí)目標(biāo)區(qū)域與算法計(jì)算得到的目標(biāo)區(qū)域之間的重疊像素點(diǎn)數(shù)目。

實(shí)驗(yàn)比較了本文方法與其他4種分割算法在ASD自然圖像庫上的分割性能,結(jié)果見表2所列。所有實(shí)驗(yàn)均在相同的人工標(biāo)記下執(zhí)行。

表2 不同方法在ASD自然圖像庫上的分割性能對比 %

由表2可知,本文方法的分割性能優(yōu)于其他4種分割算法；而且本文方法具有最高的F度量,并且比MSRM高出1%。由于對超像素進(jìn)行了有效的提純,本文方法在執(zhí)行效率上比MSRM更高效。盡管本文方法的分割性能優(yōu)于競爭對手,但是當(dāng)輸入圖像帶有噪聲或者由SE產(chǎn)生的邊緣不是很明顯時(shí),本文方法的分割性能可能會受到影響。為了直觀地展示圖像分割結(jié)果,給出了5張?jiān)紙D像以及對應(yīng)的本文方法分割結(jié)果,如圖7所示。

圖7 原始圖像以及本文方法的分割結(jié)果

2.3 不同顏色空間和相似度度量準(zhǔn)則下的分割

2.2節(jié)的實(shí)驗(yàn)已經(jīng)表明了本文方法在RGB顏色空間具有令人滿意的分割性能,下面將測試本文方法其他顏色空間是否也具有較為理想的分割效果。分別將RGB顏色空間轉(zhuǎn)化成HSI和LAB顏色空間。對于這2種顏色空間,仍使用HSI和LAB顏色直方圖以及巴氏系數(shù)來計(jì)算相鄰區(qū)域間的相似度。本文方法在圖像bird上的分割結(jié)果如圖8所示。從圖8可以看出,基于HSI和LAB顏色空間的分割結(jié)果與基于RGB顏色空間的幾乎一致,說明本文方法在不同顏色空間下都具有不錯(cuò)的分割性能。

圖8 本文方法在3種不同顏色空間下的分割結(jié)果

采用不同的相似度度量準(zhǔn)則測試本文方法的分割效果。實(shí)驗(yàn)仍使用RGB顏色直方圖,但利用歐式距離替換巴氏系數(shù)作為相似度度量準(zhǔn)則。區(qū)域R、區(qū)域Q之間的歐式距離定義如下:

(10)

本文方法在圖像dogs上的分割結(jié)果如圖9所示。從圖9可以看出,基于歐式距離的分割結(jié)果與基于巴氏系數(shù)的基本類似。可見本文方法在不同相似度度量準(zhǔn)則下都具有較好的分割結(jié)果。

圖9 2種不同相似度度量準(zhǔn)則下的分割結(jié)果

2.4 本文方法的魯棒性分析

本文方法是一種交互式方法,用戶輸入的先驗(yàn)信息對算法性能有著較大程度的影響。通常,只要用戶標(biāo)記的區(qū)域能夠很好地覆蓋主要特征區(qū)域,目標(biāo)區(qū)域基本都能被準(zhǔn)確地提取出來。

圖像plane的初始分割以及圖像分割結(jié)果如圖10所示。圖像plane的主要特征區(qū)域?yàn)闄C(jī)翼、機(jī)身、尾翼等,只需對這些主要特征區(qū)域進(jìn)行簡單的人工標(biāo)記即可實(shí)現(xiàn)較為理想的分割效果。但對于復(fù)雜的圖像,往往需要更多的用戶輸入。2組不同人工標(biāo)記下的分割結(jié)果如圖11所示。在圖11a左半部分,左上角和右下角部分目標(biāo)和背景較為相似,使得本文方法未能完整地提取出目標(biāo)區(qū)域;在增加了一些額外的用戶輸入后,本文方法最終可以完整地提取出目標(biāo)區(qū)域,如圖11b右半部分所示。

圖10 圖像plane的初始分割以及圖像分割結(jié)果

圖11 2組不同人工標(biāo)記下的分割結(jié)果

本文方法盡管在大部分情形下可以實(shí)現(xiàn)令人滿意的結(jié)果,但若目標(biāo)和背景極為相似或者初始分割質(zhì)量不是太好,則不能取得較好的分割效果。本文方法2個(gè)失敗的例子如圖12 所示。

圖12 本文方法2個(gè)失敗的例子

在圖12a左半部分,部分目標(biāo)與背景極為相似(2點(diǎn)鐘、4點(diǎn)鐘、5點(diǎn)鐘方向),即便使用了較多的用戶輸入先驗(yàn)信息,但最終的分割效果仍難以令人滿意;在圖12b左半部分,由于初始分割算法的目標(biāo)邊界一致性不是很好,臨近目標(biāo)邊緣的部分區(qū)域既包含了目標(biāo)也包含了背景(8點(diǎn)鐘方向),導(dǎo)致最終的分割結(jié)果不是很理想。幸運(yùn)的是,圖12a左半部分的分割結(jié)果可以通過增加更多的用戶輸入來改善,例如對于靠近目標(biāo)邊緣的區(qū)域給與更多的用戶標(biāo)記;圖12b左半部分的分割結(jié)果可以通過調(diào)整初始分割算法參數(shù)加以改進(jìn)。對于初始分割算法的進(jìn)一步研究將會改善初始分割質(zhì)量,從而提高本文方法的魯棒性。

3 結(jié) 論

本文提出了一種新的基于邊緣概率的層次交互式圖像分割算法。在初始分割階段,本文利用SE提純?nèi)斯?biāo)記的超像素圖,得到的超像素?cái)?shù)量較少且邊界一致性較好。在區(qū)域合并階段,利用RAG和NNG實(shí)現(xiàn)了快速、高效的區(qū)域合并。由于初始的超像素被進(jìn)一步提純,本文方法的層次區(qū)域合并代價(jià)明顯降低,算法執(zhí)行效率大大增加。仿真實(shí)驗(yàn)結(jié)果表明,本文方法的魯棒性、分割性能更好。

本文方法的最終分割結(jié)果依賴于初始過分割質(zhì)量,后續(xù)工作是研究如何進(jìn)一步改進(jìn)超像素分割算法。另外,本文方法僅使用顏色直方圖作為超像素的內(nèi)容表達(dá),接下來將研究如何使用更加有效的特征對超像素進(jìn)行描述。