顏玉杰，劉向陽

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

0 引 言

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

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

k

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

k

個(gè)像素點(diǎn)，計(jì)算

k

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

k

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

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

1 圖像測(cè)地距離與Fast Marching算法

1.1 圖像測(cè)地距離

n

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

(1)

式中，

I

表示輸入圖像，

d

為空間上任意兩點(diǎn)

z

、

z

的測(cè)地線的距離，

D

為像素點(diǎn)

z

的測(cè)地距離，

P

表示

z

、

z

兩點(diǎn)間所有路徑的集合，

M

為二值掩碼，‖Γ(

s

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

s

∈[0,1]，Γ(

s

)=?Γ(

s

)

/

?

s

，

u

=Γ(

s

)

/

‖Γ(

s

)‖。

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

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

‖?

u

‖=1

(2)

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

(3)

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

1.2 Fast Marching算法

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

‖?

u

(

z

,

z

)‖=

C

in Ω,

C

>0

u

=

g

(

z

,

z

) on Γ

(4)

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

O

(

M

log

M

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

M

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

C

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

u

=

g

(

z

,

z

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

2 基于測(cè)地距離的超像素分析算法

2.1 初始化種子點(diǎn)

對(duì)于一幅大小為

M

*

N

的圖像

I

，圖像中每個(gè)像素的顏色在CIELAB顏色空間[

l

a

b

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

x

y

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

x

y

l

a

b

]。如果簡(jiǎn)單定義像素點(diǎn)間的距離為

xylab

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

ω

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

ρ

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

z

={

z

,

z

,…,

z

*}中任意兩點(diǎn)間的歐氏距離：

(5)

再將像素點(diǎn)的局部密度定義為“數(shù)據(jù)集中到該點(diǎn)距離小于截?cái)嗑嚯x

d

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

(6)

其中，

d

為截?cái)嗑嚯x，是算法中的可變參數(shù)。

2.2 圖像測(cè)地距離計(jì)算

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

2.2.1 算法代價(jià)函數(shù)

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

v

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

z

的時(shí)間為

T

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

T

(

z

,

z

)‖

v

(

z

,

z

)=1

(7)

其中，

T

(

z

,

z

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

(8)

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

2.2.2 測(cè)地距離的計(jì)算

對(duì)于任意一個(gè)種子節(jié)點(diǎn)

z

，利用Fast Marching算法計(jì)算像素點(diǎn)間的測(cè)地距離。初始化源點(diǎn)距離為0，其他頂點(diǎn)距離為Inf:

d

(

z

)=0,

d

(

d

)=∞(

l

≠

s

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

z

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

z

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

z

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

z

，遍歷頂點(diǎn)

z

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

z

的距離值

d

，記錄

d

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

z

的距離值

d

(

z

)=min{

d

(

z

),

d

}，重復(fù)上述過程，就可以計(jì)算出每個(gè)種子節(jié)點(diǎn)

z

的測(cè)地距離

D

。種子節(jié)點(diǎn)

z

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

z

的測(cè)地距離

D

,

D

,…,

D

，定義該像素點(diǎn)的測(cè)地距離為min{

D

,

D

,…,

D

}，(

q

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

M

*

N

的距離矩陣。

2.3 超像素劃分

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

z

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

z

,

z

,…,

z

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

z

，那么

z

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

z

，具體公式如下：

(9)

其中，

L

(

z

)表示種子點(diǎn)

z

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

H

:|

D

-

D

|<|

D

-

D

|,(

r

,

e

∈[1,8],

r

≠

e

)，其中|

D

-

D

|表示像素點(diǎn)

z

、

z

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

L

(

z

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

L

(

z

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

2.4 流程圖

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

k

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

圖1 算法流程

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

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

(10)

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

(11)

式中，

Z

={

Z

,

Z

,…,

Z

}，

Z

為第

k

個(gè)超像素，CR(

Z

)為圓形凸包覆蓋率，

V

(

Z

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

3.2 算法參數(shù)分析

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

k

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

ω

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

k

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

ω

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

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

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

ω

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

ω

=0

.

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

k

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

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

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

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

k

=1 000、

k

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

圖4 不同超像素算法的ASA對(duì)比

表1 不同超像素算法的SRC對(duì)比

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

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

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

4 結(jié)束語

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