基于測地距離的超像素分析算法
2022-03-16 03:58:30顏玉杰劉向陽
計算機技術(shù)與發(fā)展 2022年2期
顏玉杰，劉向陽
(河海大學 理學院，江蘇 南京 211100)
0 引 言
超像素是指具有相似紋理、顏色、亮度等特征的相鄰像素構(gòu)成的具有一定視覺意義的不規(guī)則像素塊。圖像分割是按照灰度、頻譜、紋理等特性把圖像空間劃分成一定數(shù)量區(qū)域的過程，是近年來快速發(fā)展的一種圖像預(yù)處理技術(shù)。相比于傳統(tǒng)處理方法中的基本單元——像素，超像素更有利于局部特征的提取與結(jié)構(gòu)信息的表達，并且能夠大幅度降低后續(xù)處理的計算復雜度，在計算機視覺領(lǐng)域尤其是圖像分割中得到了廣泛的應(yīng)用。
近年來，很多學者提出了超像素分析算法。超像素生成算法大致可分為基于圖論的算法和基于梯度下降的算法兩類，具有代表性的基于圖論的超像素分析算法有Shi等人提出的Ncut(normalized cuts)算法,利用輪廓特征和紋理特征遞歸地進行圖分割；Liu等人提出了基于熵率算法，通過最大化目標函數(shù)以實現(xiàn)分割；Bergh等人提出了基于能量驅(qū)動的SEEDS算法；Chen等實現(xiàn)了一種基于NC的線性譜聚類(LSC)算法；Gong等基于差分進化(DE)提出差分進化超像素(DES)算法。對于基于梯度下降法，已有的研究有Vincent等人提出的分水嶺(watersheds)算法,是一種基于拓撲理論的數(shù)學形態(tài)學分割算法；Comaniciu等人提出的Mean-shift算法，是一個迭代模態(tài)搜索的過程；Achanta等人提出的SLIC(simple linear iterative clustering)算法,是基于顏色和距離相似性進行超像素分割，該算法思想簡單，可以生成大小均勻、形狀規(guī)則的超像素；Zhao等提出一種改進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)通的像素點的局部相似性。具體表達式如下：
(1)
式中，I
表示輸入圖像，d
為空間上任意兩點z
、z
的測地線的距離，D
為像素點z
的測地距離，P
表示z
、z
兩點間所有路徑的集合，M
為二值掩碼，‖Γ(s
)‖:R→R表示這樣的一條路徑，其中參數(shù)s
∈[0,1]，Γ(s
)=?Γ(s
)/
?s
，u
=Γ(s
)/
‖Γ(s
)‖。測地距離的計算方法主要有兩大類，一類是基于圖的方法，將曲面看作是一個圖，把在圖上計算最短距離擴展到計算曲面上的測地距離。另一類是基于樣本的方法，設(shè)定這里的曲面是離散可微的，許多微分幾何中的方法可以用來計算曲面上的測地距離。當前流行的算法主要運用了兩類偏微分方程模型：
(1)程函方程(雙曲型方程)：
‖?u
‖=1(2)
(2)熱方程(拋物型方程)：
(3)
其中，波傳播問題可以轉(zhuǎn)化成求解程函方程的問題，而熱擴散問題可以轉(zhuǎn)化成求解熱方程的問題。
1.2 Fast Marching算法
Fast Marching算法就是一種波傳播方法，旨在通過求解正交網(wǎng)格離散化的程函方程獲得測地距離的近似，具體公式如下：
‖?u
(z
,z
)‖=C
in Ω,C
>0u
=g
(z
,z
) on Γ(4)
它是一種在矩形正交網(wǎng)格上以O
(M
logM
)步為單位求解橢圓方程的數(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
空間中的五維歐氏距離將導致不同超像素大小的聚類行為不一致。對于較大的超像素，空間距離遠超過顏色距離，因此空間距離會比顏色距離更重要，這樣會產(chǎn)生緊湊的超像素，而對于較小的超像素，情況剛好相反。為了權(quán)衡這兩個距離，該文添加了一個顏色權(quán)重ω
。計算初始區(qū)域內(nèi)每個像素點的局部密度，將局部密度最大值ρ
對應(yīng)的像素點作為種子點，目的就是為了選取相對比較大的平滑區(qū)域的中心。2014年Alex Rodriguez在新聚類算法(DP算法)中提出了局部密度概念。對于局部密度這個指標的計算,首先要計算出像素點集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è)計了一種新的算法，不再是從整體上計算一個圖像多個起始點的測地距離，而是縮小了每個種子點的搜索范圍來計算測地距離，最后將得到的距離矩陣進行整合。
2.2.1 算法代價函數(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ù)，進而可通過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，然后開始進行循環(huán)迭代，查找頂點z
相鄰狀態(tài)為Open的頂點z
，遍歷頂點z
的一環(huán)鄰域三角面片，利用Eikonal方程計算頂點z
的距離值d
，記錄d
，通過循環(huán)不斷地更新頂點z
的距離值d
(z
)=min{d
(z
),d
}，重復上述過程，就可以計算出每個種子節(jié)點z
的測地距離D
。種子節(jié)點z
的搜索范圍變小，會導致有些像素點的測地距離被重復計算，對于某個像素點z
的測地距離D
,D
,…,D
，定義該像素點的測地距離為min{D
,D
,…,D
}，(q
為該像素點被重復計算的次數(shù))。如此，就可以得到與原圖像同等大小的M
*N
的距離矩陣。2.3 超像素劃分
本節(jié)主要提出了一種基于圖標簽的標記方法，旨在通過此算法，將已標記簇標簽的局部密度最大的像素點的標簽傳遞給所有剩余像素點，迭代此過程直到所有像素點擁有相應(yīng)的標簽為止，形成最終的超像素劃分。使用該算法可以動態(tài)地將局部密度最大的像素點同時對剩余未分配標簽的像素點進行標記。記種子點z
的八鄰域內(nèi)的像素點集為{z
,z
,…,z
}，從中找到未標記的且與種子點的測地距離最小的像素點z
，那么z
的標簽就賦給像素點z
，具體公式如下：
(9)
其中，L
(z
)表示種子點z
的標簽，約束條件為H
:|D
-D
|<|D
-D
|,(r
,e
∈[1,8],r
≠e
)，其中|D
-D
|表示像素點z
、z
之間測地距離差的絕對值，該公式可以判定當像素點自身已有簇標簽的時候可以將簇標簽L
(z
)傳遞至未標記的像素點L
(z
)，如此完成一次標記。重復上述步驟，直到每個像素點都有對應(yīng)的標簽，即完成超像素的劃分。2.4 流程圖
該算法主要分為以下幾個步驟進行，首先是基于指定的k
值將圖像劃分成大致均勻的長方形區(qū)域；然后計算每個區(qū)域像素點的局部密度，將局部密度最大的像素點作為種子點；再從種子點出發(fā)，計算像素點間的測地距離；最后根據(jù)測地距離，找到像素點的標簽，完成超像素劃分。算法流程如圖1所示。
圖1 算法流程
3 實驗結(jié)果及分析
為了驗證文中超像素分析算法的性能,在Berkeley Benchmark標準數(shù)據(jù)集上選取10張有代表性的圖片進行了對比實驗，驗證算法包括文中算法、SLIC、SEEDS、Watershed等。評價標準包括ASA、SRC等。實驗中取數(shù)據(jù)集中所有兩點間距離值的1%～2%。
3.1 評價標準
利用可達分割精度(ASA)參數(shù)計算超像素分割算法的效率，并將超像素與地面真值分割的標簽進行比較。ASA參數(shù)定義為：
(10)
考慮到超像素邊界與人工標記邊界存在誤差，在人工標記邊界的24鄰域?qū)ふ页袼氐臉撕灐Ａ硗猓o密度是衡量超像素的重要評價指標，Giraud在2017年提出新的形狀規(guī)律準則(SRC)以描述超像素的形狀緊湊度。SRC考慮了形狀凸性、平衡再分配和輪廓光滑三種形狀規(guī)則屬性。形狀規(guī)律性標準定義如下：
(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，觀察可達分割精度ASA、形狀規(guī)律準則SRC在ω
改變時所發(fā)生的變化(見圖2)。
圖2 參數(shù)ω調(diào)整結(jié)果
由實驗結(jié)果可知，當顏色權(quán)重ω
設(shè)置過小時，可達分割精度ASA的值較低，會導致超像素的邊界與圖像邊界貼合度不高，而超像素規(guī)整度SRC較高，為了權(quán)衡這兩者，設(shè)置ω
=0.
5，超像素分割的結(jié)果會更好。由圖3可知，當超像素數(shù)量k
設(shè)置的較大時，超像素的緊湊度與精確度都可以達到一個較高的值，對于處理更大的圖像時，文中算法會取得一個更優(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é)果，分別利用上述兩種評價標準進行評價，對每幅圖的評價標準取算數(shù)平均數(shù)作為該算法在某超像素數(shù)量下的最終評價值。圖4、表1分別為ASA、SRC指標的比較結(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)于其他算法，而可達分割精度ASA也與其他算法相接近。綜合上述，文中算法生成的超像素整體效果較好，預(yù)計在處理更大的圖像時，會取得一個更好的效果。
由圖5的劃分結(jié)果可以看出，文中算法與SLIC算法得到的超像素形狀更為規(guī)整，對于圖像中不平滑的區(qū)域，SLIC算法所得超像素不能保持更好的形狀規(guī)律準則，而文中算法卻在保持分割精度的同時，使得所得超像素的規(guī)整度更優(yōu)。
4 結(jié)束語
該文提出了一種基于測地距離的超像素分析算法，大量實驗結(jié)果表明，算法的分割精度較好，當預(yù)期分割數(shù)較大時其ASA值優(yōu)于SLIC算法，并且該算法生成的超像素形狀規(guī)整度更好。綜合來看，提出的基于測地距離的超像素分析算法的劃分結(jié)果較好，且能穩(wěn)定生成形狀規(guī)整的超像素。接下來會進一步優(yōu)化該算法，加快算法的運行速度以及提升超像素的分割精度。
