基于超像素隨機游走的自然場景圖像分割方法

李 普，陳 黎,2

(1.武漢科技大學 計算機科學與技術(shù)學院，湖北 武漢 430065；2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，湖北 武漢 430065)

0 引 言

自然場景圖像是目前人們通過各種成像設(shè)備獲得的最常見的自然圖像之一。隨著成像設(shè)備、圖像處理、計算機視覺等軟硬件技術(shù)的發(fā)展，自然場景圖像分析處理的學術(shù)價值和應用意義變得尤為重要。自然場景圖像分割作為從低維度圖像處理到高層自然場景圖像理解的關(guān)鍵步驟[1]，占據(jù)著十分重要的地位，同時也是圖像處理中最困難的問題之一。

近幾十年來，針對圖像分割這一問題，提出了各種方法，但大部分普遍缺乏普適性。所以，目前仍缺乏一種能夠普遍適用于大多數(shù)應用場景或者能夠自適應選擇分割算法已得到當前應用下精確分割結(jié)果的系統(tǒng)。學者Leo Grady在研究交互式圖像分割方法時將RW模型結(jié)合圖理論知識應用到數(shù)字圖像處理領(lǐng)域[2]。之后，該理論在多個圖像處理領(lǐng)域獲得成功應用，例如圖像分割、圖像濾波去噪[3]、圖像檢索及圖像修復與增強等。隨機游走圖像分割作為一種半自動分割算法，加入少量的人為主觀引導，并不能像無監(jiān)督聚類算法一樣自動完成整個分割過程，但卻在一定程度上更有效地提取出目標區(qū)域[4]。因此，交互式的圖像分割算法[5]在圖像分割領(lǐng)域同樣擁有很高的研究意義和應用價值。

作為一種交互式的分割模型，RW圖像分割算法雖然不能全自動完成整個分割過程，但相比于其他方法具有十分明顯的優(yōu)勢：(1)擁有完備的數(shù)學理論基礎(chǔ)支持算法的可用性。(2)通過將圖論結(jié)合到數(shù)字圖像中，通過求取帶權(quán)邊的概率最大化問題解決圖像分割問題，直觀性和可計算性強。

但是，由于隨機游走模型本身的特殊性，它在處理自然場景圖像的過程中還存在以下幾點問題：(1)隨機游走過程是以像素為基本計算單位進行的，處理大尺寸圖像時耗時過長。在實際應用中，隨著圖像采集技術(shù)的發(fā)展，圖像分辨率大幅提升，提升大尺寸圖像的分割效率越來越重要。(2)僅利用像素灰度值引導隨機游走的方向，沒有充分利用顏色、空間紋理等特征，對紋理復雜的圖像不能實現(xiàn)較好的分割效果。

超像素是一類具有相似度量的像素集合。它為計算局部圖像特征提供了方便，大幅降低了后續(xù)圖像處理的復雜性[6-7]。SLIC(simple liner iterative clustering)[8]是一種運用簡單線性迭代聚類的超像素分割算法，該算法可獲得形狀規(guī)則、大小均勻的超像素分割結(jié)果[9]，而且在運算速度、物體輪廓保持等方面相比于其他超像素分割算法有比較良好的表現(xiàn)。針對傳統(tǒng)隨機游走算法處理自然場景圖像時，存在分割效果不精確、效率低的問題，該文提出基于超像素改進的隨機游走圖像分割算法。

1 隨機游走圖像分割算法

隨機游走圖像分割算法是建立在圖論的基礎(chǔ)之上，圖論是數(shù)學知識的一個分支，已成為其他應用領(lǐng)域一個重要的理論工具，而圖論的基石是圖。圖是四類基本邏輯結(jié)構(gòu)中最為復雜的一種，它將事物之間的聯(lián)系以直觀化、結(jié)構(gòu)化的形式表現(xiàn)出來，在圖的結(jié)構(gòu)中，任意兩個節(jié)點之間都可能相關(guān)。圖結(jié)構(gòu)由節(jié)點集V和代表節(jié)點間關(guān)系的集合E組成，表示為G=(V,E)。V代表圖結(jié)構(gòu)中節(jié)點的集合(點集)，E代表圖結(jié)構(gòu)中相鄰節(jié)點之間關(guān)系的集合(邊集)[10-11]。

數(shù)字圖像實質(zhì)上是像素點矩陣，圖結(jié)構(gòu)中的節(jié)點集合V就代表了圖像中的像素，相鄰的像素連接起來就構(gòu)成帶權(quán)值的邊，所有的帶權(quán)邊組成了圖結(jié)構(gòu)中的邊集E[12]。帶權(quán)邊描述了相鄰節(jié)點之間的相似程度，決定了隨機游走過程中下一步游走的方向。

隨機游走圖像分割算法的基本思想就是首先通過原始圖像構(gòu)建一個無向加權(quán)圖。人為標記的像素點作為種子點，然后通過無向加權(quán)圖計算非種子點到達種子點的概率，通過比較將非種子點像素劃分到對應最大概率種子點的所屬區(qū)域，得到最后的分割結(jié)果。

1.1 邊的權(quán)值

構(gòu)建的無向加權(quán)圖用G=(V,E)來表示。其中，節(jié)點v∈V表示原始圖像的像素點，e∈E?V×V表示原始圖像中像素連接鄰域像素的帶權(quán)邊。邊eij的權(quán)重wij∈W表示節(jié)點以該邊移動的可能性大小，無向邊的權(quán)重值由高斯函數(shù)得到：

wij=e-β(gi-gj)2,?eij∈E

(1)

式中，gi,gj代表像素點vi,vj的強度，β是一個可控的參數(shù)。邊的權(quán)值直接引導隨機游走的下一步方向，因此權(quán)值函數(shù)構(gòu)建方式會對隨機游走的分割結(jié)果產(chǎn)生直接的影響。目前為止，大量理論和實驗表明通過高斯核函數(shù)構(gòu)建權(quán)值的效果比較理想。

1.2 求解狄利克雷問題

計算隨機游走節(jié)點的歸屬概率值的過程與已知邊界條件情況下求解Dirichlet是等價的，所以非種子點的歸屬計算問題，就可以轉(zhuǎn)化為求解在0和1為邊界條件下的聯(lián)合Dirichlet問題[13]。

狄利克雷積分為：

(2)

式中，Ω表示積分區(qū)域，u表示場[14]。

式(3)為調(diào)和函數(shù)，它滿足拉普拉斯方程，邊界條件Γ為式(4)[15]，滿足邊界條件Γ的調(diào)和函數(shù)問題可以使得式(2)取得最小值，而尋找該函數(shù)則稱為狄利克雷問題。Laplace方程則是求解狄利克雷的歐拉-拉格朗日方程。

(3)

(4)

為了求解該問題，先定義組合拉普拉斯矩陣Lij。

(5)

式中，Lij為vi和vj的關(guān)聯(lián)矩陣，di=∑wij為vi的度。

然后定義關(guān)聯(lián)矩陣A，來描述所有節(jié)點之間的關(guān)聯(lián)關(guān)系。

(6)

式中，通過邊e和節(jié)點v共同決定關(guān)聯(lián)矩陣A的值。矩陣A為聯(lián)合梯度算子，AT為散度算子。

C為大小m×m的對角矩陣，用來表示圖結(jié)構(gòu)中的邊的權(quán)值，如式(7)。

(7)

此時，得到一個Laplacian算子L。C為一個調(diào)節(jié)矩陣乘積的因子。

L=ATCA

(8)

因此，式(2)便可以表示為關(guān)于圖結(jié)構(gòu)中邊、點及權(quán)重三大要素的新形式，見式(9)。

(9)

將G中的頂點V由兩部分組成，標記的種子點集合VM以及沒有被標記的節(jié)點集合VU，兩者的關(guān)系可以用VM∪VU=V,VM∩VU=?表示，將拉普拉斯矩陣按照是否為標記點進行重新組合，如式(10)。于是，式(9)可以分解成式(11)。

(10)

(11)

其中，LM、LU分別表示種子點及非種子點集合構(gòu)成的拉普拉斯算子，xM和xU表示標記點和未被標記點的能量值。

(12)

因此，通過式(13)，可以求取非種子點與某一個標記為s種子點的聯(lián)合Dirichlet的解。狄利克雷問題可以通過電路圖的形式來進行分析，而在電路圖中，所有節(jié)點的電勢值之和為1。因此，在圖結(jié)構(gòu)中非種子點游走到種子點的概率之和也為1，如式(14)所示。那么可以利用式(15)計算出所有未標記節(jié)點第一次移動到已標記節(jié)點的概率。

Luxs=-BTms

(13)

(14)

LUX=-BTM

(15)

通過以上過程，計算出所有非種子節(jié)點VU分別游走到各個種子點VM的概率。然后將所有節(jié)點劃入概率最大的種子點所屬范圍內(nèi)，最終將圖像所有的像素點進行分類，類別數(shù)與事先標記種子點的類別數(shù)相同，實現(xiàn)圖像分割[16]。

2 基于超像素的RW圖像分割方法

利用超像素邊界貼合度好及通過將像素區(qū)域化降低計算量等優(yōu)點，對傳統(tǒng)的隨機游走圖像分割方法進行改進?；舅枷胧牵旱谝徊酵ㄟ^超像素分割算法對原始圖像作區(qū)域化處理，生成若干個超像素塊。利用生成的超像素替代單個像素稱為新的節(jié)點，然后提取超像素區(qū)域顏色直方圖及區(qū)域紋理信息聯(lián)合組成高斯權(quán)值函數(shù)，構(gòu)建無向加權(quán)圖，最后在新構(gòu)建的無向加權(quán)圖上進行隨機游走實現(xiàn)分割。

2.1 SLIC超像素分割

超像素是由一系列位置相鄰且顏色、亮度、紋理等特征相似的像素點組成的像素塊。它通過將局部像素聚合在一起，為計算圖像局部特征提供了便利，同時大幅降低了后續(xù)圖像處理的復雜性[17]。該文采用一種簡單線性迭代聚類的超像素分割方法(SLIC)。

由于每個像素的五維特征向量包含了兩種不同的含義，一種是像素的顏色，一種是像素的空間距離。所以可以適當?shù)貙臻g距離這一部分進行加權(quán)，以平衡它們在聚類過程中的影響，其公式如下：

(16)

(17)

(18)

其中，Ds是度量值；參數(shù)m為用來調(diào)節(jié)超像素的緊致度，m越大，那么空間相似性權(quán)重則越大，聚類結(jié)果越緊密。該文以m=10作為參數(shù)；lk、ak、bk分別表示第k個超像素區(qū)域中心像素點的lab值，li、ai、bi則表示在2S×2S區(qū)域內(nèi)像素點i的lab值；xk、yk表示第k個超像素區(qū)域中心像素點的圖像坐標值，xi、yi則表示在2S×2S區(qū)域內(nèi)的像素點i的圖像坐標值；dlab表示第k個超像素區(qū)域中心像素點與其周圍2S×2S區(qū)域內(nèi)的像素點lab顏色空間的距離度量值；dxy表示第k個超像素區(qū)域中心像素點與其周圍2S×2S區(qū)域內(nèi)的像素點圖像坐標的歐氏距離度量值。

2.2 RW權(quán)值的改進

傳統(tǒng)隨機游走圖像分割算法的最小計算單位是單個像素，利用像素的灰度值特征得到邊的權(quán)值。而在基于超像素改進的隨機游走圖像分割方法中，節(jié)點從單個像素變?yōu)槌袼?。因此，計算兩個超像素塊相似性的方法也發(fā)生了改變。該文提出提取超像素的顏色直方圖以及區(qū)域性LBP紋理信息來共同構(gòu)建權(quán)值函數(shù)，作為兩個超像素塊的相似性度量。

(1)顏色直方圖。彩色圖像由三個顏色通道組成，分別包含256個顏色度量值。為了盡量保留原始圖像的顏色信息，同時提高算法效率，將三個通道分別都劃分為16個顏色分組。因此，三通道信息可以產(chǎn)生4 096個顏色信息值。公式(19)為通過4 096個特征值來描述兩個超像素顏色差異度的顏色直方圖歐氏距離d(M,N)。

(19)

其中，HM和HN分別表示超像素M和N的歸一化顏色直方圖。d(M,N)越大則表示兩超像素區(qū)域之間的顏色距離越大，這兩個超像素塊在顏色空間上的差異性越大。反之，則兩個超像素近似程度越高。

(2)LBP紋理特征。LBP特征是一種用于描述圖像紋理的局部特征。僅僅依靠顏色直方圖來評判超像素區(qū)域之間的相似度容易造成分割結(jié)果不準確，因此加入超像素區(qū)域性LBP紋理信息。圖像中以c為中心像素點，p點鄰域中的LBP紋理值定義為：

(20)

(21)

式中，gc,gp分別為中心點c及c的p鄰域點的灰度值。

圖1 LBP特征計算示意圖

利用式(22)表示超像素D中,n個像素點的平均LBP紋理值。

(22)

用LBP紋理值的歐氏距離來表示超像素M和N的紋理信息差異度，見式(23)。

(23)

(3)改進后的權(quán)值。該文將上述兩種歐氏距離與高斯函數(shù)聯(lián)合起來共同構(gòu)建權(quán)值函數(shù)w。這樣能夠更加準確地描述兩個超像素區(qū)域之間的相似程度。超像素M、N之間的權(quán)值定義為：

wM,N=exp{-β1d(M-N)2-β2e(M-N)2}

(24)

式中,β1，β2>0為兩個可調(diào)參數(shù)，決定兩種特征的影響度。

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

該文主要安排對比實驗，驗證基于超像素改進的隨機游走圖像分割算法的有效性和相比于傳統(tǒng)隨機游走圖像分割算法的優(yōu)越性。實驗數(shù)據(jù)取自BSDS500分割數(shù)據(jù)集。本實驗所用的實驗環(huán)境為：MATLAB R2014B；實驗硬件條件為戴爾筆記本(CPU：Intel(R)Core(TM)i5-7300HQ CPU @ 2.50 GHz;內(nèi)存：12 GB；操作系統(tǒng)：64位Windows10)。

3.1 定性分析

實驗一：針對該文提出方法的有效性，本實驗選取兩張分辨率分別為585*373和480*320的簡單圖像，分別使用傳統(tǒng)RW圖像分割算法和基于超像素改進的算法來對圖像進行分割。實驗結(jié)果表明，對于前背景顏色簡單、紋理信息差異明顯的圖像，基于超像素改進的算法與傳統(tǒng)的RW圖像分割算法都能比較理想地分割出目標。圖2為實驗中的兩組實驗結(jié)果，對分割結(jié)果作二值化處理以進行對比分析。

圖2 不同算法圖像分割效果

實驗二：本實驗針對基于超像素改進的RW圖像分割算法相對于傳統(tǒng)RW圖像分割算法的優(yōu)越性，下面是本實驗選取的紋理結(jié)構(gòu)相對較復雜的圖像(見圖3)，分辨率分別為690*445、1 280*840和960*596。通過直觀地對比實驗結(jié)果，可以明顯觀察到，基于超像素改進后的RW算法得到的分割結(jié)果更加貼近真實目標。

圖3 不同算法分割效果

由以上實驗結(jié)果可以看到，傳統(tǒng)的RW算法在處理自然場景中顏色及紋理信息豐富的圖像會存在過分割和欠分割的情況。而基于超像素改進的RW圖像分割算法，對自然場景中復雜圖像的處理能力上有明顯提升。其中，對鹿的實驗結(jié)果中在鹿腿和鹿角上的分割效果最為明顯。

3.2 定量分析

本節(jié)將對算法的分割結(jié)果與人工分割結(jié)果進行量化分析，并對算法的效率作對比分析。

圖像分割結(jié)果的量化對比以重合率PO和誤差率PM作為判別標準,其定義如下：

(25)

(26)

式(25)、(26)中S表示人工標準分割結(jié)果，SC為算法實現(xiàn)的處理結(jié)果。式(25)中TO表示以人工分割為標準的前景目標部分，O表示算法分割結(jié)果與人工標準分割的前景目標重疊部分。式(26)中MC為算法分割結(jié)果中的誤差部分。其中：

(27)

(28)

表1為分割結(jié)果精確度量化數(shù)據(jù)。由實驗結(jié)果和表中數(shù)據(jù)可知，對于以上五幅圖像，基于超像素改進的隨機游走圖像分割方法均能比較完整地分割出前景目標。在前兩幅圖像中，前背景顏色和紋理信息相對簡單，傳統(tǒng)的RW圖像分割算法和基于超像素改進的RW圖像分割算法均能得到理想的目標分割邊界。對于實驗二中的三幅圖像，基于超像素改進后的算法能夠得到更貼合真實目標的分割邊界，實現(xiàn)更好的分割效果。

表1 不同算法分割結(jié)果精確度量化對比

表2為以上兩個實驗中的圖像的分割效率。由表中數(shù)據(jù)對比可知，基于超像素隨機游走圖像分割算法在計算效率上有了明顯的提高。

表2 不同算法分割效率對比 s

4 結(jié)束語

針對傳統(tǒng)隨機游走圖像分割算法在處理自然場景中前背景顏色紋理信息相對復雜、分辨率大的圖像時，存在目標邊界難以貼合甚至分割錯誤以及效率較低的問題，提出基于超像素隨機游走的自然場景圖像分割方法。通過超像素預處理將原始圖像離散化為若干個尺寸相對均勻的超像素區(qū)域，然后以超像素區(qū)域的顏色直方圖和區(qū)域性紋理信息衡量兩個超像素的相似性。以超像素替代原始像素作為圖結(jié)構(gòu)中的節(jié)點，超像素之間的相似度作為邊的權(quán)值構(gòu)建新的無向加權(quán)圖，最后在新構(gòu)建的無向加權(quán)圖上進行隨機游走實現(xiàn)分割。該方法可以在一定程度上提高精度和效率。由于該算法的分割結(jié)果是通過對超像素進行合并處理得到的，所以會造成分割結(jié)果邊緣不平整的問題，針對這一現(xiàn)象后續(xù)有待進一步研究。