基于測地距離的超像素分析算法

顏玉杰，劉向陽

(河海大學(xué) 理學(xué)院，江蘇 南京 211100)

0 引 言

超像素是指具有相似紋理、顏色、亮度等特征的相鄰像素構(gòu)成的具有一定視覺意義的不規(guī)則像素塊。圖像分割是按照灰度、頻譜、紋理等特性把圖像空間劃分成一定數(shù)量區(qū)域的過程，是近年來快速發(fā)展的一種圖像預(yù)處理技術(shù)。相比于傳統(tǒng)處理方法中的基本單元——像素，超像素更有利于局部特征的提取與結(jié)構(gòu)信息的表達(dá)，并且能夠大幅度降低后續(xù)處理的計算復(fù)雜度，在計算機(jī)視覺領(lǐng)域尤其是圖像分割中得到了廣泛的應(yīng)用。

近年來，很多學(xué)者提出了超像素分析算法。超像素生成算法大致可分為基于圖論的算法和基于梯度下降的算法兩類，具有代表性的基于圖論的超像素分析算法有Shi等人提出的Ncut(normalized cuts)算法,利用輪廓特征和紋理特征遞歸地進(jìn)行圖分割；Liu等人提出了基于熵率算法，通過最大化目標(biāo)函數(shù)以實現(xiàn)分割；Bergh等人提出了基于能量驅(qū)動的SEEDS算法；Chen等實現(xiàn)了一種基于NC的線性譜聚類(LSC)算法；Gong等基于差分進(jìn)化(DE)提出差分進(jìn)化超像素(DES)算法。對于基于梯度下降法，已有的研究有Vincent等人提出的分水嶺(watersheds)算法,是一種基于拓?fù)淅碚摰臄?shù)學(xué)形態(tài)學(xué)分割算法；Comaniciu等人提出的Mean-shift算法，是一個迭代模態(tài)搜索的過程；Achanta等人提出的SLIC(simple linear iterative clustering)算法,是基于顏色和距離相似性進(jìn)行超像素分割，該算法思想簡單，可以生成大小均勻、形狀規(guī)則的超像素；Zhao等提出一種改進(jìn)SLIC搜索策略的超像素快速線性迭代聚類FLIC算法；Ban等提出一種高斯混合模型(GMM)的超像素算法。其中SLIC是目前最為經(jīng)典、簡單的算法，該算法比現(xiàn)有算法更快，有著更高的記憶效率，展示了目前最優(yōu)的邊界貼合度。它是采用

k

均值聚類算法生成超像素，在圖像上大致均勻地選取

k

個像素點，計算

k

個超像素內(nèi)所有像素點的平均向量值，重新得到

k

個聚類中心，然后不斷更新聚類中心，直到收斂的過程。

該文提出了一種歸屬于第一類的基于測地距離的超像素分析算法，該算法是定義初始劃分區(qū)域內(nèi)局部密度最大的像素點作為種子點，然后由種子點出發(fā)計算測地距離，完成超像素劃分的過程。和傳統(tǒng)算法相比，該算法的優(yōu)點在于：生成超像素的形狀緊湊度更高，并且邊界貼合度也更接近于SLIC算法。

1 圖像測地距離與Fast Marching算法

1.1 圖像測地距離

n

維空間中，曲面上任意兩點之間測地線的長度稱之為測地距離。該文把測地距離應(yīng)用于圖像分析，就是因為測地距離是計算空間中任意兩點的曲面最短距離，可以更好地描述聯(lián)通的像素點的局部相似性。具體表達(dá)式如下：

(1)

式中，

I

表示輸入圖像，

d

為空間上任意兩點

z

、

z

的測地線的距離，

D

為像素點

z

的測地距離，

P

表示

z

、

z

兩點間所有路徑的集合，

M

為二值掩碼，‖Γ(

s

)‖:R→R表示這樣的一條路徑，其中參數(shù)

s

∈[0,1]，Γ(

s

)=?Γ(

s

)

/

?

s

，

u

=Γ(

s

)

/

‖Γ(

s

)‖。

測地距離的計算方法主要有兩大類，一類是基于圖的方法，將曲面看作是一個圖，把在圖上計算最短距離擴(kuò)展到計算曲面上的測地距離。另一類是基于樣本的方法，設(shè)定這里的曲面是離散可微的，許多微分幾何中的方法可以用來計算曲面上的測地距離。當(dāng)前流行的算法主要運用了兩類偏微分方程模型：

(1)程函方程(雙曲型方程)：

‖?

u

‖=1

(2)

(2)熱方程(拋物型方程)：

(3)

其中，波傳播問題可以轉(zhuǎn)化成求解程函方程的問題，而熱擴(kuò)散問題可以轉(zhuǎn)化成求解熱方程的問題。

1.2 Fast Marching算法

Fast Marching算法就是一種波傳播方法，旨在通過求解正交網(wǎng)格離散化的程函方程獲得測地距離的近似，具體公式如下：

‖?

u

(

z

,

z

)‖=

C

in Ω,

C

>0

u

=

g

(

z

,

z

) on Γ

(4)

它是一種在矩形正交網(wǎng)格上以

O

(

M

log

M

)步為單位求解橢圓方程的數(shù)值算法，其中

M

是網(wǎng)格點的總數(shù)，Ω是R中的定義域，

C

是給定的已知函數(shù)，邊界條件是

u

=

g

(

z

,

z

)，此處的邊界是域Ω的邊界，可以是一個特定的曲線或者曲面。解這個程函方程的中心思想是使用數(shù)值方法中的逆向有限差分來近似擬合，從而得到近似的數(shù)值解。

2 基于測地距離的超像素分析算法

2.1 初始化種子點

對于一幅大小為

M

*

N

的圖像

I

，圖像中每個像素的顏色在CIELAB顏色空間[

l

a

b

]中表示，其取值范圍是已知的，而像素的位置[

x

y

]的取值范圍隨著圖像的尺寸變化而變化，所以每個像素點的五維向量表示為[

x

y

l

a

b

]。如果簡單定義像素點間的距離為

xylab

空間中的五維歐氏距離將導(dǎo)致不同超像素大小的聚類行為不一致。對于較大的超像素，空間距離遠(yuǎn)超過顏色距離，因此空間距離會比顏色距離更重要，這樣會產(chǎn)生緊湊的超像素，而對于較小的超像素，情況剛好相反。為了權(quán)衡這兩個距離，該文添加了一個顏色權(quán)重

ω

。計算初始區(qū)域內(nèi)每個像素點的局部密度，將局部密度最大值

ρ

對應(yīng)的像素點作為種子點，目的就是為了選取相對比較大的平滑區(qū)域的中心。2014年Alex Rodriguez在新聚類算法(DP算法)中提出了局部密度概念。對于局部密度這個指標(biāo)的計算,首先要計算出像素點集

z

={

z

,

z

,…,

z

*}中任意兩點間的歐氏距離：

(5)

再將像素點的局部密度定義為“數(shù)據(jù)集中到該點距離小于截斷距離

d

的數(shù)據(jù)點個數(shù)”。該文采用高斯核函數(shù)計算局部密度，這樣計算不同的數(shù)據(jù)點具有相同的局部密度值的概率會更小。即：

(6)

其中，

d

為截斷距離，是算法中的可變參數(shù)。

2.2 圖像測地距離計算

由上述步驟選取的種子點出發(fā)，該文基于引入代價函數(shù)的Fast Marching算法計算搜索范圍內(nèi)像素點間的測地距離。在處理一幅大圖像時，F(xiàn)ast Marching算法由多個初始點出發(fā)計算測地距離的時間代價太大，因此該文設(shè)計了一種新的算法，不再是從整體上計算一個圖像多個起始點的測地距離，而是縮小了每個種子點的搜索范圍來計算測地距離，最后將得到的距離矩陣進(jìn)行整合。

2.2.1 算法代價函數(shù)

設(shè)定義在二維平面上的曲線是其法線方向向上的速度

v

，如果曲線經(jīng)過種子點

z

的時間為

T

，那么在路徑規(guī)劃中最小代價求解問題的Eikonal方程通常寫成：‖

T

(

z

,

z

)‖

v

(

z

,

z

)=1

(7)

其中，

T

(

z

,

z

)為時間距離函數(shù)，為拓展代價函數(shù)，該算法定義的代價函數(shù)為：

(8)

通過上述方程再結(jié)合式(5)可以求解時間距離函數(shù)，進(jìn)而可通過Fast Marching算法求得種子點與其余像素點之間的測地距離。

2.2.2 測地距離的計算

對于任意一個種子節(jié)點

z

，利用Fast Marching算法計算像素點間的測地距離。初始化源點距離為0，其他頂點距離為Inf:

d

(

z

)=0,

d

(

d

)=∞(

l

≠

s

)，設(shè)置源點狀態(tài)為Open，其他頂點狀態(tài)為Far，查找集合Open中距離值最小的頂點

z

，將其狀態(tài)更新為Dead，將頂點

z

相鄰狀態(tài)為Far的頂點狀態(tài)更新為Open，然后開始進(jìn)行循環(huán)迭代，查找頂點

z

相鄰狀態(tài)為Open的頂點

z

，遍歷頂點

z

的一環(huán)鄰域三角面片，利用Eikonal方程計算頂點

z

的距離值

d

，記錄

d

，通過循環(huán)不斷地更新頂點

z

的距離值

d

(

z

)=min{

d

(

z

),

d

}，重復(fù)上述過程，就可以計算出每個種子節(jié)點

z

的測地距離

D

。種子節(jié)點

z

的搜索范圍變小，會導(dǎo)致有些像素點的測地距離被重復(fù)計算，對于某個像素點

z

的測地距離

D

,

D

,…,

D

，定義該像素點的測地距離為min{

D

,

D

,…,

D

}，(

q

為該像素點被重復(fù)計算的次數(shù))。如此，就可以得到與原圖像同等大小的

M

*

N

的距離矩陣。

2.3 超像素劃分

本節(jié)主要提出了一種基于圖標(biāo)簽的標(biāo)記方法，旨在通過此算法，將已標(biāo)記簇標(biāo)簽的局部密度最大的像素點的標(biāo)簽傳遞給所有剩余像素點，迭代此過程直到所有像素點擁有相應(yīng)的標(biāo)簽為止，形成最終的超像素劃分。使用該算法可以動態(tài)地將局部密度最大的像素點同時對剩余未分配標(biāo)簽的像素點進(jìn)行標(biāo)記。記種子點

z

的八鄰域內(nèi)的像素點集為{

z

,

z

,…,

z

}，從中找到未標(biāo)記的且與種子點的測地距離最小的像素點

z

，那么

z

的標(biāo)簽就賦給像素點

z

，具體公式如下：

(9)

其中，

L

(

z

)表示種子點

z

的標(biāo)簽，約束條件為

H

:|

D

-

D

|<|

D

-

D

|,(

r

,

e

∈[1,8],

r

≠

e

)，其中|

D

-

D

|表示像素點

z

、

z

之間測地距離差的絕對值，該公式可以判定當(dāng)像素點自身已有簇標(biāo)簽的時候可以將簇標(biāo)簽

L

(

z

)傳遞至未標(biāo)記的像素點

L

(

z

)，如此完成一次標(biāo)記。重復(fù)上述步驟，直到每個像素點都有對應(yīng)的標(biāo)簽，即完成超像素的劃分。

2.4 流程圖

該算法主要分為以下幾個步驟進(jìn)行，首先是基于指定的

k

值將圖像劃分成大致均勻的長方形區(qū)域；然后計算每個區(qū)域像素點的局部密度，將局部密度最大的像素點作為種子點；再從種子點出發(fā)，計算像素點間的測地距離；最后根據(jù)測地距離，找到像素點的標(biāo)簽，完成超像素劃分。算法流程如圖1所示。

圖1 算法流程

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

為了驗證文中超像素分析算法的性能,在Berkeley Benchmark標(biāo)準(zhǔn)數(shù)據(jù)集上選取10張有代表性的圖片進(jìn)行了對比實驗，驗證算法包括文中算法、SLIC、SEEDS、Watershed等。評價標(biāo)準(zhǔn)包括ASA、SRC等。實驗中取數(shù)據(jù)集中所有兩點間距離值的1%～2%。

3.1 評價標(biāo)準(zhǔn)

利用可達(dá)分割精度(ASA)參數(shù)計算超像素分割算法的效率，并將超像素與地面真值分割的標(biāo)簽進(jìn)行比較。ASA參數(shù)定義為：

(10)

考慮到超像素邊界與人工標(biāo)記邊界存在誤差，在人工標(biāo)記邊界的24鄰域?qū)ふ页袼氐臉?biāo)簽。另外，緊密度是衡量超像素的重要評價指標(biāo)，Giraud在2017年提出新的形狀規(guī)律準(zhǔn)則(SRC)以描述超像素的形狀緊湊度。SRC考慮了形狀凸性、平衡再分配和輪廓光滑三種形狀規(guī)則屬性。形狀規(guī)律性標(biāo)準(zhǔn)定義如下：

(11)

式中，

Z

={

Z

,

Z

,…,

Z

}，

Z

為第

k

個超像素，CR(

Z

)為圓形凸包覆蓋率，

V

(

Z

)為最小位置與最大位置方差比值。

3.2 算法參數(shù)分析

文中算法需設(shè)置的參數(shù)有超像素數(shù)量

k

和像素點的顏色權(quán)重

ω

。通過調(diào)整參數(shù)可以使得分割結(jié)果更加符合預(yù)期，對于每幅圖的評價結(jié)果取算數(shù)平均數(shù)作為該算法在某超像素數(shù)量下的最終評價值。為了便于評價，把超像素數(shù)量設(shè)置為

k

=1 000，觀察可達(dá)分割精度ASA、形狀規(guī)律準(zhǔn)則SRC在

ω

改變時所發(fā)生的變化(見圖2)。

圖2 參數(shù)ω調(diào)整結(jié)果

由實驗結(jié)果可知，當(dāng)顏色權(quán)重

ω

設(shè)置過小時，可達(dá)分割精度ASA的值較低，會導(dǎo)致超像素的邊界與圖像邊界貼合度不高，而超像素規(guī)整度SRC較高，為了權(quán)衡這兩者，設(shè)置

ω

=0

.

5，超像素分割的結(jié)果會更好。由圖3可知，當(dāng)超像素數(shù)量

k

設(shè)置的較大時，超像素的緊湊度與精確度都可以達(dá)到一個較高的值，對于處理更大的圖像時，文中算法會取得一個更優(yōu)的結(jié)果。

圖3 參數(shù)k調(diào)整結(jié)果

3.3 實驗結(jié)果比較與分析

為了便于評價，超像素數(shù)量值統(tǒng)一設(shè)置為1 000、2 000、3 000、4 000、5 000。對所有的分割結(jié)果，分別利用上述兩種評價標(biāo)準(zhǔn)進(jìn)行評價，對每幅圖的評價標(biāo)準(zhǔn)取算數(shù)平均數(shù)作為該算法在某超像素數(shù)量下的最終評價值。圖4、表1分別為ASA、SRC指標(biāo)的比較結(jié)果。圖5為SLIC、SEEDS、Watershed和文中算法以

k

=1 000、

k

=3 000為示例劃分圖像的結(jié)果。

圖4 不同超像素算法的ASA對比

表1 不同超像素算法的SRC對比

(a) k=1 000 (b)k=3 000

由上述圖表可以看出，文中算法生成的超像素規(guī)整度明顯優(yōu)于其他算法，而可達(dá)分割精度ASA也與其他算法相接近。綜合上述，文中算法生成的超像素整體效果較好，預(yù)計在處理更大的圖像時，會取得一個更好的效果。

由圖5的劃分結(jié)果可以看出，文中算法與SLIC算法得到的超像素形狀更為規(guī)整，對于圖像中不平滑的區(qū)域，SLIC算法所得超像素不能保持更好的形狀規(guī)律準(zhǔn)則，而文中算法卻在保持分割精度的同時，使得所得超像素的規(guī)整度更優(yōu)。

4 結(jié)束語

該文提出了一種基于測地距離的超像素分析算法，大量實驗結(jié)果表明，算法的分割精度較好，當(dāng)預(yù)期分割數(shù)較大時其ASA值優(yōu)于SLIC算法，并且該算法生成的超像素形狀規(guī)整度更好。綜合來看，提出的基于測地距離的超像素分析算法的劃分結(jié)果較好，且能穩(wěn)定生成形狀規(guī)整的超像素。接下來會進(jìn)一步優(yōu)化該算法，加快算法的運行速度以及提升超像素的分割精度。