改進的簡單非迭代聚類的遙感影像分割研究

孫瑋婕，楊 軍

1.蘭州交通大學 測繪與地理信息學院，蘭州730070

2.地理國情監測技術應用國家地方聯合工程研究中心，蘭州730070

3.甘肅省地理國情監測工程實驗室，蘭州730070

4.蘭州交通大學 電子與信息工程學院，蘭州730070

圖像分割是將圖像中的像素按照一定的相似性分成若干不重疊的具有特殊意義的小區域。針對圖像分割已經提出如閾值、邊緣檢測和區域生長等方法，但傳統的圖像分割方法大多是以像素為單位，很少考慮到像素與像素之間的關系。因此，2003年，Ren等人[1]提出了具有相似紋理、顏色、亮度等特征的相鄰像素構成的超像素這一概念，能夠通過超像素塊將圖像分割為具有相似特征的小區域。計算機視覺領域[2-3]將基于超像素的分割算法作為圖像預處理的一種方法，能獲得較好的局部特征和結構信息，并在很大程度上提高了圖像的運行效率。隨著遙感技術的發展，遙感影像具有更清晰的地物特征和形狀輪廓，使得遙感影像分割成為信息提取的關鍵步驟，而基于超像素的分割方法能夠利用超像素塊代替影像中大量的原始像素，可以提高圖像分割的精度和效率，在遙感影像分割領域受到了廣泛關注[4-5]。

1 相關研究工作

超像素分割的方法大體上可分為兩類[6]：基于圖論的方法和基于梯度上升的方法。基于圖論的方法是將圖像中的每一個像素看做是一個節點，連接兩個節點形成邊，并通過分配給邊的權重及各種分割準則形成超像素。主要算法有歸一化切割算法（Normalized cuts，Ncut）[7]、熵率超像素分割算法（Entropy Rate Superpixel segmentation，ERS）[8]、種子超像素算法（Superpixels Extracted via Energy-Driven Sampling，SEEDS）[9]等。基于梯度下降的方法是將圖像中像素進行粗略的初始聚類后，再通過反復迭代細化聚類的結果，達到一定的收斂條件后形成超像素。主要算法有分水嶺分割算法（Watershed）[10]、均值漂移算法（Mean Shift，MS）[11]、渦輪像素算法（Turbo Pixel，TP）[12]、簡單線性迭代算法（Simple Linear Iterative Clustering，SLIC）[13]等。

同其他超像素分割算法相比，Achanta 等人[13]提出的SLIC 算法由于能夠得到較為緊湊和均勻的超像素，圖像分割結果較為準確，使其在圖像分割領域得到了廣泛應用。但將SLIC超像素算法直接應用到遙感圖像分割領域時，由于遙感影像相比于自然圖像具有更復雜的特性，分割結果中仍會存在過分割現象，且算法運行效率較低。近年來，國內外研究者提出了一些改進方法。劉仲民等人[14]首先用SLIC超像素算法獲得初始分割結果；接著利用區域鄰接圖和最近鄰接圖的鄰接表數據結構來表示區域之間的關系；然后計算每個待合并區域與其所有鄰接區域之間的不相似度函數值；最后根據該值合并不相似度值最小的區域，得到最后的分割結果。文獻[15]將灰度共生矩陣提取的影像紋理特征與SLIC 獲得的顏色特征相結合，并擴展了衡量加權紋理距離和顏色相似度以及超像素中心與相鄰像素之間的空間接近度的度量方法，獲得了較好的分割結果。大多數利用SLIC 算法進行分割的算法都是首先對影像進行SLIC初始分割，再使用其他方法對影像進行后處理從而得到較好的分割結果，但遙感影像本身較大，利用傳統SLIC 算法的運行時間較長，再加入其他方法對影像進行處理則會進一步降低運行效率，不能達到對影像的實時分割。

隨著深度學習的發展，基于深度學習的圖像分割方法也得到廣泛關注。文獻[16]提出了一種基于上下文分析的非均衡合并SAR圖像分割方法。首先通過超像素對圖像進行預分割；然后對超像素的上下文進行建模；最后通過一次粗合并和一次細合并得到分割結果。文獻[17]在文獻[16]的基礎上又提出一種新的分割算法，先將原始圖像進行超像素分割獲得初始分割結果；接著提取圖像的多個異質特征來描述SAR 圖像；然后將不同的特征分別集成到特征層和相似層中；最后，在粗合并和細分類組成的兩階段算法中分別提出基于上下文的區域迭代合并算法和基于混合優化的模糊聚類算法，對超像素進行處理后得到分割結果。Albayrak等人[18]采用SLIC 超像素方法對圖像作預分割，然后使用卷積神經網絡對這些超像素進行分類，以獲得整個圖像的分割結果。蔣應峰等人[19]首先利用深度學習方法從原始影像中提取多個特征圖，并利用特征對像素進行分類；然后對于分類錯誤的像素，利用SLIC對圖像進行超像素分割；最后統計超像素塊的像素類別信息來修正部分分類錯誤的像素類別。然而，利用深度學習對遙感影像進行分割時，所需要的分割數據集須包含大量的訓練樣本和對應的真實標簽，而現有的真實標簽大多通過手工標記，耗費大量的人力和時間，且對網絡進行訓練時也需要花費大量的時間，所以該方法的成本較高。

SLIC超像素算法僅考慮圖像的空間信息和顏色信息，且存在多次迭代、重疊局部區域重復計算等問題。因此，2017 年Achanta 等人[20]改進了SLIC 算法，提出了簡單非迭代聚類（Simple Non-Iterative Clustering，SNIC）算法，它是SLIC 算法的一種簡化版本，將SLIC 算法中多次迭代過程減少為一次，降低了計算復雜度，且對像素進行強制連接，有效地提高了聚類效率。然而，SNIC算法依舊存在對超像素數目設置較為敏感，當超像素數目設置過小或過大，易造成圖像欠分割或過分割的問題。為此，本文采用動態閾值和SNIC 超像素分割相結合的方法實現遙感影像的分割。主要貢獻和創新點為：（1）引入SNIC算法解決了SLIC算法在遙感影像分割中聚類效率較低的問題；（2）加入動態閾值分割方法，能更好地利用影像中的灰度信息，同時解決了動態閾值對影像進行分割時顏色及空間信息利用不足的問題。

2 分割方法與原理

2.1 改進的SLIC超像素

2.1.1 SLIC超像素

2012 年，Achanta 等人[13]提出了SLIC 超像素算法，它是一種顏色相似性和空間相近性相結合的方法，主要思想是將RGB 圖像轉換到CIELAB 顏色空間，并把圖像中每個像素的3個顏色分量和2個坐標值組成一個5維特征向量，然后通過度量向量之間的距離來判斷像素的相似性。使用SLIC超像素進行圖像分割的具體步驟如下：

（1）初始化種子點。假設一張圖像有N個像素點，將其預分割為K個相同尺寸的超像素，則每個超像素的大小為N/K，相鄰種子點的步長近似為S=sqrt(N/K)。

（2）移動種子點。為了避免初始化的種子點位于梯度較大的邊界上，計算初始化種子點3×3鄰域內像素點的梯度值，并將初始化種子點移至梯度最小處。

（3）距離度量并分配種子點。搜索種子點2S×2S范圍內所有像素點與該種子點的顏色距離和空間距離，并選取距離最小值對應的種子點作為該像素的聚類中心。

距離計算方法如下：

式中，NS為類內最大空間距離(NS=S)。Nc為最大的顏色距離，一般通過m代替該值，m是一個取值范圍為[1，40]的固定常數；dc和dS分別為顏色距離和空間距離，分別由下式計算：

其中，i為聚類中心標簽，j為對應聚類中心i的2S×2S大小鄰域的像素坐標的一維索引值，x、y為像素的空間坐標，l為CIELAB 顏色空間下的亮度通道，值域0（黑色）～100（白色），a、b為CIELAB顏色空間下的兩個顏色通道，a為從洋紅色至綠色的范圍，b為從黃色至藍色的范圍。

（4）迭代優化。重復上述步驟直到像素點的聚類中心不再發生變化，通常迭代10次左右。

（5）增強連通性。將經過上述步驟仍不在超像素塊中的小區域，通過新建一個零矩陣將其與周圍的超像素塊合并。

2.1.2 SNIC超像素

SLIC中算法中存在以下問題：（1）算法需要進行10次左右的迭代運算。（2）聚類中心的搜索空間存在部分重疊。（3）像素點之間沒有進行強制連接，以上3個問題導致SLIC算法在運行效率方面并不理想。因此，SNIC超像素對傳統的SLIC 算法進行了改進，有效地提高了聚類效率。

和SLIC 一樣，SNIC 超像素[20]依舊通過在原始影像劃分規則格網的方式選擇像素來初始化K個種子點C[k]={xk,ck}，通過K個種子點創建K個元素zi={xi,ci,k,di,k}，k表示超像素標簽，取值范圍為[1,K]，di,k表示第i個像素點到第k個質心的距離。

通過構建一個優先級隊列存儲創建的K個元素，每一次總是將di,k最小（距離第k個質心最近）的元素返回。因為質心的值是超像素中所有像素的平均值，所以若返回的元素所指向的標簽圖上的像素位置未標記，則先將其標記為質心，然后使用該像素對質心值進行更新。此外，對于未標記的4個或8個相鄰像素，都創建一個新元素，并將這些新元素加入隊列。當算法執行時在隊列的一端分配標簽，在另一端加入新的候選像素，直到隊列清空時算法結束。

（1）距離計算

同SLIC 算法一樣，設像素的空間坐標為[xy]T，CIELAB 顏色空間c=[lab]T，所以，第k個超像素質心到第j個候選像素的距離計算如下：

式中，S和m分別表示空間距離和顏色距離的歸一化因子。

（2）聚類中心的更新

SLIC 算法中，聚類中心是通過在每次k均值迭代中，計算與原聚類中心距離最近的所有像素的平均值得到，因此，需要多次迭代以使初始種子點收斂。而SNIC算法從初始種子點開始，通過優先級隊列來選擇要加入到超像素集群中的下一個像素，該隊列包含與當前正在增長的超像素集群周圍相連接的4 或8 個候選像素，最后通過優先級隊列返回與質心距離最小的像素。由此，聚類中心的在線更新通過添加到超像素集群中的每個新像素來完成。

（3）高效的距離計算

SLIC 通過搜索種子點2S×2S范圍內所有像素點與該種子點的顏色距離和空間距離來實現，導致圖像中相鄰種子點的正方形搜索范圍之間存在某些重疊部分，且這種計算方式沒有對原始影像中的像素實施強制連接，使得那些位于2S×2S范圍中卻可能不屬于最終超像素的像素仍然會被訪問，并為其計算距離，所以，SLIC 算法不可避免地會存在多余的計算。然而，SNIC算法不需要像SLIC 那樣對距離計算施加任何空間限制，只需要計算到與當前正在增長的超像素集群連接的4 個或者8 個候選像素的距離，以創建用于填充優先級隊列的元素。因此，即使SLIC 只進行了單次迭代，SNIC算法所計算的距離量也比其更少。

圖1為不同K值下的SNIC超像素算法分割實驗結果，所采用的遙感影像為Worldview-2衛星2011年10月10日拍攝的中國河南省省會鄭州的局部區域，分辨率為0.5 m。可以看出，當K值較大時，分割結果中會出現明顯的過分割現象；當K值較小時，出現欠分割現象。但無論K值較大或較小，SNIC算法的分割結果中在與背景區域顏色相近或有相同特質的邊緣區域分割效果都不佳。所以為了解決SNIC超像素算法中仍存在的這個問題，本文采用動態閾值的方法對傳統的SNIC 超像素分割算法進行優化。

圖1 不同K 值的SNIC分割結果

2.2 動態閾值

在局部區域內，背景一般比感興趣的目標亮或者暗，可通過設定目標所在局部區域的背景灰度值來提取感興趣的目標。通常可以采用均值濾波或者中值濾波的平滑處理來得到局部區域的背景灰度，本文采用均值濾波。動態閾值分割[21]的基本思想是通過平滑處理得到整幅影像的背景灰度，將原始影像與處理后的影像背景灰度圖相減后大于或者小于某個閾值來提取感興趣的目標物體，可以表示為：

以上述操作為理念，根據實際地圖大小及其復雜程度自定義初始，而網格密度以及網格密度升級速度降低算法搜索空間，提升算法搜索速度，加強針對性，以更高效率尋求最優路徑。

式中，f1(x,y)為原始影像，f2(x,y)為經過濾波平滑后的影像，T為人為設定的閾值。式（5）能夠分割出比背景亮的地物，式（6）能夠分割出比背景暗的地物。雖然人為設定了閾值，但動態閾值分割主要體現在設定的閾值基礎上加上該像素的平均灰度，使得閾值一直處于動態變化的過程中。均值濾波是一種典型的線性濾波算法，其由目標像素為中心的周圍n×n個像素構成濾波模板，再計算該模板中所有像素的平均值，用該值代替目標像素點原來的像素值。圖2為3種不同的均值濾波器（3×3、9×9和15×15）對原始遙感影像的灰度圖進行平滑處理后的結果，可以看出，決定動態閾值分割結果的第一個關鍵因素是濾波器，較大的濾波器更能估計出局部背景，而較小的濾波器則不能對局部背景得到準確的估計。通常情況下，局部區域內的濾波器的寬度都應該大于該區域內被分割物體的寬度，濾波器的尺寸越大，得到的分割結果越準確。但是，濾波器的寬度也不能無限大于分割物體的寬度，若濾波器的寬度過大，不僅增加了噪聲的影響，而且使計算的負擔也大幅度增加。

圖2 不同均值濾波器的分割結果

根據公式（4）和（5），以21×21 均值濾波結果為基礎，并通過人為設定閾值，得到不同閾值下的動態分割結果如圖3所示。可以看出，決定動態閾值分割結果的第二個關鍵因素是閾值。對于閾值的設定，分割的對象決定了人為設定閾值的大小，閾值太大或太小都會產生不準確的分割結果。閾值太大（例如T=40）雖然可以更好地抑制噪聲，但容易丟掉目標物體的邊緣灰度，產生欠分割的問題；閾值太小（T=5）雖然能夠得到更完整的分割對象，但是會產生噪聲，對分割結果造成一定的影響。

圖3 不同T 值的分割結果

2.3 動態閾值和SNIC相結合

經過比對不同K值下SNIC分割結果和不同閾值、不同濾波器下的動態閾值分割結果，發現動態閾值對圖像中的灰度特征較為敏感，在邊緣處具有較好的分割結果，但容易出現斷裂的區域，且分割時沒有考慮到像素之間的空間相關性。SNIC算法考慮了像素間的顏色相似性和空間相關性，但在顏色相近或者紋理等特征相似的區域，容易將其分割成一個區域。因此，本文將SNIC算法和動態閾值方法相結合，得到較好的分割結果，如圖4所示。

圖4 實驗過程圖

具體的操作步驟如下：

步驟1采用SNIC 超像素算法對原始影像進行分割，得到初始分割結果，記為A。

步驟2 對原始影像進行動態閾值分割，記為B。

步驟3 將SNIC 算法得到的初始分割結果A中的閉合區域進行填充（SNIC 算法得到的初始分割結果的邊緣區域是不閉合的，所以需要在后面的過程中單獨進行運算），將填充后的結果記為C。

步驟4 先將SNIC初始分割結果A與區域填充的結果C作差，將作差后的結果記為D，再將D與動態閾值分割結果B進行二次作差，二次作差后的結果記為E。

步驟5 將SNIC 算法得到的初始分割結果A中邊緣不閉合的區域，人為在影像四邊各設置一條邊界線，使得邊緣區域成為閉合的區域。接著對邊緣區域重復上述步驟后，與結果E進行合并，然后選擇滿足一定條件的分割線F。

步驟6 將結果F進行形態學閉運算后，再與結果F進行求交得到最終的分割結果。

3 實驗分析

實驗的軟件環境為Matlab R2018a和Visual Studio 2017，硬件為主頻2.60 GHz 的Core i5-3230M 處理器，內存4 GB，Win10操作系統的筆記本電腦。

為驗證本文算法可以用于處理不同復雜度的遙感影像，所以使用信息熵來判斷影像的復雜性[22]。影像的信息熵反映了影像平均信息量的多少，其表達式為：

式中，J為影像的灰度值，h1為該像素的灰度值，h2為鄰域的灰度值，其取值范圍都為[0，255]；h(h1,h2)為特征二元組(h1,h2)出現的頻數，γ為影像的尺度。若影像的信息熵越接近0，則表示影像越簡單；若信息熵的值越大，則表示影像越復雜。

3.1 評價方法

為了進一步驗證本文算法在圖像分割中的有效性，將本文算法與傳統的SLIC分割算法、SNIC算法和改進的SLIC算法[23]3種圖像分割算法進行對比實驗，采用視覺觀察和P-R方法[24]分別進行定性和定量的評價，并將3種算法的運行時間與本文算法進行對比。

P-R 方法由分割精度和召回率構成：分割精度（P）表示所有被預測為正確像素數中，真正的正確像素數的比例；召回率（R）表示所有被預測為正確像素數占影像所有像素數的比例。

式中，TP表示影像中分割正確的樣本數量；FP表示背景像素被預測為地物的像素數量；FN表示地物的像素被預測為背景的像素數量。

3.2 實驗結果

3.2.1 實驗一

選取2011 年7 月22 日下午12 時52 分Worldview-2衛星拍攝的美國佛羅里達州梅里特島的肯尼亞航天中心的局部影像，影像大小為1 031×924，分辨率為0.5 m，信息熵為6.101 5，分割對比結果如表1、圖5 和圖6 所示，圖中藍色為分割線。

表1 不同算法的分割精度和召回率對比（實驗一）

圖5 不同算法的分割結果對比圖（實驗一）

圖6 不同算法分割結果局部對比圖（實驗一）

將4 種算法設置相同的K值，圖5（b）傳統的SLIC算法和圖5（c）SNIC算法的分割結果中存在明顯的過分割和欠分割現象，由于傳統的SLIC和SNIC算法分割結果都隨設置的K值而產生較大的變化，無法得到較滿意的分割結果，但SLIC 和SNIC 算法的Precision 都比較高，而Recall 都表現出很低的狀態。文獻[23]相比于前兩種方法，分割效果已經有明顯的提高，如圖5（d）所示，是由于通過SLIC算法進行初始分割后，采用帶噪聲的基于密度的聚類方法對初始分割結果進行二次聚類，使圖6（d）分割結果的局部圖中樓頂的白色小方塊有一部分可以分割出來，但影像中汽車等小目標地物仍存在欠分割現象，該方法相比于文獻[23]，Precision有了小范圍的提高，且Recall 有了大幅度的提高。本文將SNIC超像素算法和動態閾值相結合對影像進行分割，使影像中細節特征更明顯，如圖6（e）所示，且本文算法在該實驗中的Precision 和Recall 都能夠達到0.9 以上，說明本文算法得到的分割結果較優。

3.2.2 實驗二

選取ISPRS 航空影像Vaihingen 數據集中的一幅影像，影像大小為1 919×2 569，分辨率為9 cm，信息熵為5.575 8，分割結果如表2、圖7 和圖8 所示。該數據集包含33 張航拍影像，由近紅外（NIR）、紅（R）和綠（G）這3個波段組成，所以影像中植被表現為紅色，為使分割結果能夠清晰地呈現在遙感影像中，圖中用藍色表示分割線。

圖7 不同算法的分割結果對比圖（實驗二）

圖8 不同算法分割結果局部對比圖（實驗二）

表2 不同算法的分割精度和召回率對比（實驗二）

傳統SLIC 和SNIC 依舊出現很明顯的過分割和欠分割現象，兩種方法的Precision 相對來說比較高，但Recall依舊非常低，文獻[23]算法的分割結果的Precision和Recall 已經達到0.8 以上，能夠大體反映分割地物的輪廓，分割效果相對比較理想，但不能體現地物的細節特征，且分割邊界不連續。而本文算法相比于文獻[23]在Precision和Recall兩方面都有一定的提高，不僅能夠突出影像中的細節特征，且具有較為連續的分割邊界，分割效果更好。

3.2.3 實驗三

選取2016 年11 月26 日Worldview-4 衛星拍攝的日本東京澀谷區的國立代代木綜合體育館的局部影像，影像大小為973×653，分辨率為0.3 m，信息熵為6.505 4，分割結果如表3、圖9和圖10所示，圖中藍色為分割線。

圖9 不同算法的分割結果對比圖（實驗三）

圖10 不同算法分割結果局部對比圖（實驗三）

表3 不同算法的分割精度和召回率對比（實驗三）

實驗三的遙感影像相對比較復雜，包含建筑物、植被、道路、小目標地物等。SNIC 算法和SLIC 算法都依舊存在過分割且細節特征不明顯的現象。文獻[23]算法Precision 和Recall 達到0.8 以上，已具有較好的分割結果，但影像中依舊存在過分割的現象且分割邊緣不貼合。本文算法在實驗三中的Precision 和相比于前兩個實驗結果較低，并沒有達到0.9以上，但分割結果中也已經能夠分割出影像中地物的輪廓特征，而且可以將地物表面的細節特征分割出來，分割邊緣較為貼合，具有較好的分割效果。

3.3 算法復雜度分析

SLIC算法像素落在小于8個聚類中心的附近，避免執行數千個冗余距離計算，其復雜度為O(N)。SNIC算法在SLIC算法的聚類中心和距離計算方面進行改進其復雜度也為O(N)。文獻[23]算法先通過SLIC 算法對原始影像進行預分割，將預分割的結果進行帶噪聲的基于密度的聚類（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）。SLIC算法的復雜度為O(N)，而DBSCAN聚類算法的復雜度在最壞的情況下為O(N2)，文獻[23]將兩種算法相結合后的復雜度為O(N2)。本文算法中，先將原始影像進行SNIC 預分割，接著將原始RGB 影像轉為灰度圖后進行動態閾值分割，然后經過兩次作差后選擇滿足條件的分割線，所以本文算法的復雜度為O(N)。

3.4 運行時間對比

表4 是本文算法與傳統的SLIC[13]、SNIC[20]以及文獻[23]算法設置相同K值的運行時間對比結果。從表中可以明顯看出SNIC 相比于SLIC 大大減少了運行時間。文獻[23]算法中DBSCAN 方法將達到一定密度的區域劃分為一個簇，并在具有噪聲的空間數據庫中發現任意形狀的簇，將其定義為密度相連的點的最大集合，所以增加了運行時間，降低了算法運行的效率。本文算法在SNIC 超像素算法的基礎上加入動態閾值方法，動態閾值具有運行效率高的特點，且比傳統的SNIC 算法分割精度高，更能滿足分割需要。

表4 不同算法運行時間對比 s

4 結論

本文提出了一種改進的SNIC超像素的遙感影像分割算法，將SNIC超像素和動態閾值相結合，得到了較好的分割結果，且運行效率較高。實驗分別從分割精度、召回率和運行時間三方面進行評價，表明本文算法相比于其他3種方法都能獲得較好的分割結果，但本文算法沒有利用到遙感影像豐富的紋理特性和獨有的光譜特性，這也是未來研究工作中需要進一步考慮的方面。