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