一種融合超像素與最小生成樹的高解析度遙感影像分割方法
董志鵬1, 王密1,2, 李德仁1,2
1. 武漢大學測繪遙感信息工程國家重點實驗室, 湖北 武漢 430079;
2. 地球空間信息協同創新中心, 湖北 武漢 430079
收稿日期：2016-10-24； 修回日期：2017-05-26
基金項目：國家自然科學基金（91438203）；國家973計劃（2014CB744201）
第一作者簡介：董志鵬(1991—), 男, 博士, 研究方向為高分辨遙感影像處理及信息提取。E-mail:zhipengdong@foxmail.com
通信作者：王密, E-mail：wangmi@whu.edu.cn
摘要：影像分割是面向對象高解析度遙感影像分析的基礎與關鍵。針對傳統影像分割方法易受噪聲影響，且難以確定合適的影像分割尺度的問題，本文提出了一種融合超像素與最小生成樹的高解析度遙感影像分割方法。首先用簡單線性迭代聚類算法對影像進行過分割生成超像素；然後初始設定影像分割數，採用區域動態約束聚類算法對超像素進行合併，獲得分割數-方差和、分割數-局部方差、分割數-局部方差變化率指標圖，依據3個指標圖確定合適的影像分割數；最後根據確定的合適影像分割數，採用區域動態約束聚類算法對超像素重新合併得到分割結果。定性對比試驗和定量評價結果表明，本文方法可以有效地克服影像噪聲對分割結果的影響，獲得良好的影像分割結果。
關鍵詞：高解析度遙感影像 影像分割 超像素 聚類 區域合併
A High Resolution Remote Sensing Image Segmentation Method by Combining Superpixels with Minimum Spanning Tree
DONG Zhipeng1, WANG Mi1,2, LI Deren1,2
Abstract: Image segmentation is the basic and key step of object-oriented remote sensing image analysis. Conventional image segmentation method is sensitive to image noise and hard to determine the correct segmentation scale. To solve these problems, a novel image segmentation method by combining superpixels with minimum spanning tree was proposed in this paper. First, the image is over-segmented by simple linear iterative clustering algorithm to obtain superpixels. Then, superpixels are firstly clustered by regionalization with dynamically constrained agglomerative clustering and partitioning algorithm using the initial segmentation number and the sum of squared deviations (SSD), local variance (LV), rate of LV change (ROC-LV) index of graphs corresponding to the segmentation number are obtained. So the suitable image segmentation number is determined according to the SSD, LV, ROC-LV index of graphs corresponding to segmentation number. Finally, superpixels are reclustered by regionalization with dynamically constrained agglomerative clustering and partitioning algorithm based on the suitable segmentation number. The experimental results showed that the proposed method can obtain good segmentation results.
Key words: high resolution remote sensing image remote sensing image segmentation superpixels clustering region merging
隨著對地觀測衛星技術的發展，高解析度的遙感影像已經應用到城市規劃、作物分類、災害檢測等領域[1]。影像分割作為高解析度遙感影像信息提取與目標識別的前提和基礎，是實現從數據到信息的對象化提取的過渡環節和關鍵步驟，具有十分重要的地位[2]。相對於中低解析度遙感影像高解析度遙感影像擁有更加豐富的地物信息，如清晰的地物輪廓形狀信息、明顯的紋理信息等，但也增加了影像噪聲對影像分割的影響[3-4]。傳統的基於像素的影像分割方法如mean-shift算法[5]、分水嶺算法[6]等易受高解析度影像中「椒鹽」噪聲的影響，難以得到理想的分割結果。面向對象的影像分割方法可以克服影像中「椒鹽」噪聲的影響[7]，並利用對象的結構、光譜信息等特徵提高影像分割的精度，如文獻[1]結合對象結構和光譜特徵實現影像分割，文獻[8]利用對象光譜、結構和紋理信息分割影像，文獻[9]結合對象形狀和光譜特徵進行影像分割，文獻[10]利用對象光譜和紋理實現影像分割，eCognition軟體中的FNEA算法根據對象形狀與光譜實現影像分割[11]，但面向對象的影像分割方法需要調整分割尺度來獲得合適的影像分割結果，而合適的分割尺度又難以確定。
針對影像分割方法易受噪聲影響，且難以確定合適影像分割尺度的問題，本文提出一種融合超像素與最小生成樹的高解析度遙感影像分割方法。用簡單線性迭代聚類(simple linear iterative clustering，SLIC)算法對影像過分割生成超像素，克服影像噪聲對影像分割的影響。用基於最小生成樹分割思想的區域動態約束聚類(regionalization with dynamically constrained agglomerative clustering and partitioning，REDCAP)算法對超像素初次合併獲得分割數-方差和、分割數-局部方差、分割數-局部方差變化率指標圖，根據3個指標圖獲得合適的影像分割數，再次用REDCAP算法對超像素重新聚類合併得到最終的影像分割結果。通過定性對比試驗和定量評價驗證本文方法的有效性。
1 方法
本文方法主要分為4個步驟：① SLIC算法對影像過分割生成超像素；② 設定初始影像分割數，用REDCAP算法對超像素層次聚類合併；③ 得到每次合併的分割數對應的方差和(sum of squared deviations，SSD)、局部方差(local variance，LV)、局部方差變化率(rate of LV change，ROC-LV)指標圖，確定合適的影像分割數；④ 根據合適影像分割數用REDCAP算法對超像素重新聚類合併。總體流程圖如圖 1所示。
圖 1 分割流程圖Fig. 1 The flow chart of the proposed approach圖選項
1.1 超像素的生成
文獻[12]提出了超像素這一概念，所謂超像素是指具有相似紋理、顏色、亮度等特徵的相鄰像素構成的圖像塊。文獻[13]提出SLIC算法生成超像素。該算法將彩色圖像轉換為CIELAB顏色空間和XY坐標下的5維特徵向量，然後對5維特徵向量構造度量標準，對圖像像素進行局部聚類生成超像素[14]。相對於分水嶺算法、區域增長算法、基於圖的圖像分割算法[15]等傳統的影像過分割算法生成的超像素，SLIC算法生成的超像素具有更好的地物邊界依附性、更加規則緊湊的形狀，並且SLIC算法可以人為控制生成超像素的個數和具有良好的抗噪性[16]。SLIC算法的具體步驟為：
(1) 初始化種子點。假設影像中有N個像素點，預設將影像分為K個大小均勻超像素，則每個超像素的大小為N/K。將初始劃分矩形格網中心處的像素作為超像素的種子點，且每個種子點間的距離近似為。為了避免種子點被分配於影像的邊緣位置，對後續的聚類過程造成幹擾，將種子點在以它為中心的3×3的窗口內移動到梯度值最小的位置，並為每個種子分配一個標籤。
(2) 相似性度量。計算影像中像素與種子點間的相似程度，將最相似種子點的標籤賦給該像素。通過不斷迭代相似性判斷過程，直到收斂，則相似性的度量關係如下
(1)
(2)
(3)
式中，[lk ak bk xk yk]為種子點的5維特徵向量；[li ai bi xi yi]為待判斷像素點的5維特徵向量；dlab為像素點間的顏色差異；dxy為像素點間的空間距離；D為兩個像素的相似度；S為種子點的間距；m為平衡參數，用來衡量顏色值與空間信息在相似度衡量中的比重。D取值越小，說明兩個像素越相似。
對於影像中像素與種子點相似性判斷時，只在以種子點為中心的2S×2S區域內搜索相似像素點，而不是在整張圖像中尋找，如圖 2所示。
圖 2 像素搜索範圍示意圖Fig. 2 Pixel search scope圖選項
(3) 後續處理。SLIC算法有時會使屬於同一標籤的超像素內的像素不連通，會產生一些孤立的像素。對於這種現象在聚類分割結束後進行後續處理，使孤立像素被重新分配到距離它空間距離最近的超像素中，從而生成緊湊且連通的超像素。
1.2 超像素的合併
REDCAP算法[17]是一種動態的區域聚類算法，該算法可以充分利用各區域間的屬性差異與鄰接關係進行區域合併，使最終合併在同一簇中的區域具有最大的同質性。該算法首先根據區域間的鄰接關係與屬性差異建立連接各區域的最小生成樹，在生成最小生成樹的過程中根據Full-Older-CLK規則實時調整屬於不同簇的相鄰區域間的相似性差異，在最小生成樹生成後，根據切割樹得到的子樹中包含的區域同質性最大原則切割樹，最終切割生成一系列子樹，這些子樹中所包含的區域即被合併在一起。本文中把超像素作為區域單元，用REDCAP算法對超像素進行聚類合併，REDCAP算法合併超像素的流程示意圖如圖 3所示。
圖 3 超像素合併流程示意圖Fig. 3 Diagram of merging superpixles圖選項
統計每個超像素所包含的像素點的光譜均值作為超像素的光譜屬性值，本文的試驗數據為經融合後的包含3個波段的遙感影像，3個波段分別作為R、G、B波段，則超像素的光譜屬性為Si(Ri、Gi、Bi)，則光譜屬性計算公式如式(4)-(6) 所示
(4)
(5)
(6)
相鄰超像素之間的屬性差異Ci, j計算公式如式(7) 所示
(7)
式中，ni為第i個超像素所包含的像素點的個數；Rk、Gk、Bk為第i個超像素中包含的第k個像素點的R、G、B屬性值；Ci, j為超像素i與超像素j之間的光譜差異。
1.3 分割數的確定和超像素的重新合併
REDCAP算法唯一的參數設置是輸入最終生成子樹的個數即最終影像的分割數，當切割生成多少子樹時能夠得到合適的影像分割結果，這裡涉及到尺度問題。關於研究空間格局的最佳尺度，文獻[18]認為在某一空間解析度水平下，若空間格局得以體現並且模型運行的結果能獲得有重要意義的轉變，那麼這個空間分辨水平就是合適的，或者說對於研究該問題來說是最佳的。文獻[19]提出用量測不同解析度景觀地物之間的相互關係，通過利用一個n×n像素的移動窗口，來計算窗口內像素光譜屬性標準差的均值，即局部方差，最後形成局部方差曲線圖得到最佳影像解析度。其中包含的邏輯思想是「如果影像的空間解析度優於場景中物體的大小，n×n窗口內像素相似性較高，求得的局部方差值較低。如果影像的空間解析度與場景中物體大小相近，n×n窗口內像素相似性較低，求得的局部方差值較高。通過局部方差探索影像中像素間的自相關性」[20]。
文獻[21]對局部方差法進行改進提出尺度參數評價(estimation of scale parameter，ESP)理論，用多尺度分割代替n×n窗口，求得不同分割尺度對應的LV值。根據不同尺度對應的LV值得到分割尺度-LV曲線圖，在曲線圖趨於平穩時對應的尺度能有效反應影像的空間結構，則影像有意義的分割尺度處於該尺度範圍內。在有意義的尺度範圍內求得不同尺度對應的ROC-LV值，畫出分割尺度-ROC-LV曲線圖，分割尺度-ROC-LV曲線圖反映LV值從一種物體到另一種物體的改變，在曲線圖中當ROC-LV值劇烈變化時對應的尺度是有意義的，根據得到的有意義尺度獲得影像的多尺度分割結果。
目前通過局部方差思想求影像有意義的分割結果，均是自下而上獲得分割尺度-LV曲線圖，需要設定影像的分割尺度閾值[22-23]。本文結合ESP理論與REDCAP算法合併超像素的過程提出自上而下求得影像合適尺度，用REDCAP算法對超像素不同層次的合併情況表示不同尺度下影像的分割結果。REDCAP算法對超像素合併，首先生成連接所有超像素的最小生成樹，根據設定分初始分割數對最小生成樹進行分割，在分割過程中以每次分割生成子樹中包含的超像素區域作為每次分割情況下求LV值、SSD值的計算窗口，獲得不同分割數對應的LV值、SSD值，畫出分割數-LV值、分割數-SSD值、分割數-ROC-LV曲線圖。觀察分割數-SSD值與分割數-LV值曲線圖，確定曲線圖平穩時分割數所在區間範圍，則合適的影像分割數處於該區間範圍內。在分割數-ROC-LV值曲線圖中，在確定的合適影像分割數所在區間範圍內，當ROC-LV值劇烈變化時對應的分割數即為合適的影像分割數。
根據得到的合適影像分割數用REDCAP算法對超像素重新聚類合併，得到最終的影像的分割結果。
對超像素進行聚類合併，每次合併的影像分割數對應的SSD、LV、ROC-LV的計算公式如下
(8)
(9)
式中，N為設定的分割數即分割得到的子樹的個數；r為設定的N棵子樹中第r棵子樹的標籤；i為標籤為r的子樹中第i個超像素的標籤；j為標籤為i的超像素屬性j的標籤；nr為標籤為r的子樹中所包含的超像素的個數；d為超像素的屬性個數；xrij為子樹r中i超像素的j屬性值；xrj為子樹r中所有超像素的j屬性均值
(10)
式中，LN為分割數為N的LV值；LN+1為分割數為N+1的LV值；所求的ROC值即為分割數為N所對應的ROC-LV指標。
1.4 分割結果評價
分割結果評價是影像分割研究中必不可少的一步，雖然已經提出了多種分割評價方法，但目前仍沒有統一的標準評價流程[1]。本文採用目視判別與定量評價相結合的方法對本文方法的有效性進行評價。
目視判別是一種最基本、最常用的評價方法。通過目視判別可以直觀地觀察分割結果中區域的幾何形態、過分割、欠分割等情況。而且，只有分割結果和目視評價的效果吻合時，定量評價指標才能使人信服[24]。因此，在目視判別的基礎上採用Kappa係數[25]和對象一致性誤差(object-level consistency error，OCE)[26]對本文方法進行定量評價。其中Kappa係數表述了分割方法對地物分類結果與真實的地物分類結果的一致性程度，Kappa係數的取值範圍為[0,1]，當Kappa係數越大時說明分割方法對地物的分類結果與真實地物的分類結果越一致。OCE來描述分割方法的分割結果與真實的分割結果一致性程度，OCE評價方法可以有效地評價圖像的過分割與欠分割現象，OCE滿足0≤OCE(Ig, Is)≤1，其中，Ig為地面參考對象，Is為實際分割對象；當OCE=0時，表示分割完全符合地面參照對象。相比較而言，OCE越小，表示分割效果越好。
為了更加全面的評價本文方法的性能，將本文方法的分割結果與EDSION軟體中mean-shift分割算法和eCognition軟體中FNEA算法進行了對比評價。
2 試驗結果與分析
所使用的試驗平臺CPU為Inter(R) Pentium(R)雙核，2 GB內存，Windows7作業系統。本文方法用VC++6.0軟體進行編程實現。採用兩幅QuickBird高解析度影像來驗證本文方法的有效性。用mean-shift算法和FNEA算法調整參數進行多次分割試驗，並採用目視解譯的方式選擇整體效果最佳的分割結果與本文方法分割結果進行對比。
2.1 試驗1
2.1.1 試驗數據
試驗1使用的數據為美國佛羅裡達州城區的QuickBird全色及紅、綠、藍多波段經PANSHARPEN融合後的影像，影像大小為512×512像素，各波段解析度為0.61 m。該影像主要包括房屋、道路、湖泊、樹林等地物如圖 4(a)，影像過分割生成超像素的結果如圖 4(b)。
圖 4 試驗1影像數據Fig. 4 Remote sensing image of test 1圖選項
2.1.2 影像分割數選擇
用REDCAP算法對超像素進行聚類合併，初始設定把超像素合併為200個區域，根據每次合併的分割數對應的SSD值、LV值、ROC-LV值，畫出分割數-SSD值、分割數-LV、分割數-ROC-LV指標圖如圖 5(a)、(b)、(c)。在圖 5(a)、圖 5(b)中當分割數大於100時走勢圖趨於平穩，則影像合適的分割數處於分割數大於100的範圍內。在圖 5(c)中，當分割數為106、119、150、160、176、192時ROC-LC值劇烈變化，則將超像素合併為106、119、150、160、176、192個區域時對應的分割結果是有意義的，經過目視判別當超像素合併為106個區域時整體分割效果最好，則將超像素合併為106個區域時作為影像的分割結果。
圖 5 試驗1指標圖Fig. 5 The index chart of test 1圖選項
2.1.3 目視評價
圖 6(a)為影像的目視解譯結果；圖 6(b)為mean-shift算法的影像分割結果，其參數設置為：minimum region=200，spatial=5，color=6.5；圖 6(c)為FNEA算法的影像分割結果，其參數設置為：shape=0.1, compactness=0.7，scale=100；圖 6(d)為本文方法把影像分割為106個區域的分割結果。在矩形框標定的區域內，FNEA算法難以區分出光譜相似的建築物與道路對象，出現欠分割現象，而mean-shift算法與本文方法可以較好地區分建築物與道路。兩個箭頭所指的湖泊區域，在內部光譜特徵變化較大的湖泊區域內mean-shift算法產生了大量的過分割現象，而FNEA算法和本文方法的分割結果與目視解譯結果基本一致。總的來說，FNEA算法難以區分出光譜相似的不同地物，mean-shift算法在內部光譜特徵變化較大的同種地物區域內易產生過分割現象，而本文方法可以較好地平衡影像分割的過分割與欠分割現象。
圖 6 試驗1結果Fig. 6 The experimental results of test 1圖選項
2.1.4 定量評價
表 1列出了3種不同算法對影像分割結果的Kappa係數和OCE係數的評價情況。在表 1中本文方法的Kappa係數大於mean-shift算法與FNEA算法，說明本文方法對地物分類結果優於mean-shift算法和FNEA算法，此外本文方法的Kappa係數為0.814 4，說明本文方法對地物的分類結果與實際地物的分類結果基本一致。本文方法的OCE指標為0.124 8，低於mean-shift算法的0.497 7和FNEA算法的0.356 8，說明本文方法與目視解譯分割結果更一致。
表 1 試驗1分割測試結果Tab. 1 Segmentation results of test 1
表選項
2.2 試驗2
2.2.1 試驗數據
試驗2使用的數據為美國佛羅裡達州郊區的QuickBird全色及紅、綠、藍多波段經PANSHARPEN融合後的影像，影像大小為512×512像素，解析度為0.61 m。影像中主要包括道路、河流、森林、草地、耕地等地物如圖 7(a)。對影像過分割處理生成超像素結果如圖 7(b)。
圖 7 試驗2影像數據Fig. 7 Remote sensing image of test 2圖選項
2.2.2 影像分割數選擇
初始設定REDCAP算法把超像素合併為120個區域，得到每次合併的分割數對應的SSD值、LV值、ROC-LV值，根據得到的分割數對應的SSD值、LV值、ROC-LV值畫出分割數-SSD、分割數-LV、分割數-ROC-LV指標圖如圖 8(a)、(b)、(c)。在分割數-SSD指標圖、分割數-LV指標圖中當分割數大於40時走勢圖基本趨於平穩，則影像合適的分割數處於分割數大於40的範圍內。在分割數-ROC-LV指標圖中，當分割數為44、52、56、72、82、87時ROC-LV值發生劇烈變化，則分割數為44、52、56、72、82、87時的分割結果是有意義的，經過目視對比觀察當分割數為44時影像的整體分割結果最好，則影像合適的分割數為44。
圖 8 試驗2指標圖Fig. 8 The index chart of test 2圖選項
2.2.3 目視評價
圖 9(a)為影像的目視解譯圖；圖 9(b)為影像的mean-shift算法結果圖，算法參數設置為：minimum region=200，spatial=7，color=6.5；圖 9(c)為影像的FNEA算法結果圖，其參數設置為：shape=0.1, compactness=0.9，scale=100；圖 9(d)為本文方法把影像分割為44個區域的試驗結果。在箭頭所指的草地區域FNEA算法產生過分割現象，而本文算法與目視解譯基本一致，說明本文方法在內部光譜特徵變化較大的草地區域可以得到更好的分割結果。在箭頭所指的河流區域mean-shift算法與FNEA算法把明顯的一條河流分為兩段，出現過分割現象，而本文方法可以正確地分割這段河流。從整體上對比觀察3種算法的分圖與目視解譯圖，本文方法分割結果圖與目視解譯圖更接近，說明本文方法可以得到良好的影像分割結果。
圖 9 試驗2結果Fig. 9 The experimental results of test 2圖選項
2.2.4 定量評價
表 2列出了在mean-shift算法、FNEA算法與本文方法對影像分割結果Kappa係數和OCE係數的評價。本文方法的Kappa係數為0.841 7大於mean-shift算法的0.747 4與FNEA算法的0.794 8，本文方法可以更好的區分各地物類型，對各地物的分類結果與實際地物的分類結果基本上一致。本文方法的OCE指標為0.369低於mean-shift算法的0.502 5與FNEA算法的0.688 4，說明本文方法對影像有更好的分割結果。
表 2 試驗2分割測試結果Tab. 2 Segmentation results of test 2
表選項
3 結論
針對影像分割易受噪聲影響、難以確定合適影像分割數的問題，本文提出一種融合超像素與最小生成樹的高解析度遙感影像分割方法，該方法首先用SLIC算法對影像進行過分割生成SLIC超像素克服影像噪聲對分割結果的影響。用REDCAP算法對SLIC超像素進行兩次區域劃分，首次劃分得到分割數對應的SSD值、LV值、ROC-LV值指標圖確定合適的影像分割數，再次劃分是根據合適影像分割數用REDCAP算法對SLIC超像素重新進行區域劃分從而得到影像分割結果。通過兩組試驗對本文方法與mean-shift算法、FNEA算法進行定性與定量對比評價，本文方法可以良好地平衡影像分割中的過分割與欠分割現象，獲得整體分割效果良好的影像分割結果。下一步將對本文方法進行算法優化提高運行效率。
【引文格式】董志鵬，王密，李德仁。 一種融合超像素與最小生成樹的高解析度遙感影像分割方法[J]. 測繪學報，2017，46(6)：734-742. DOI: 10.11947/j.AGCS.2017.20160514
更多精彩內容：
唐新明：資源三號02星雷射測高儀在軌幾何檢校與試驗驗證
一分鐘讓你讀懂北京的地圖
火星實地探測20周年: 原來火星長這樣
院士論壇| 李德仁：衛星大數據要以72億老百姓的需求作為方向（PPT+文字實錄）
武漢大學張過教授專著推薦：《高解析度視頻衛星標準產品分級體系》
2017年測繪遙感信息工程國家重點實驗室開放研究基金指南及申請通知
論文推薦| 張力：基於多視影像匹配模型的傾斜航空影像自動連接點提取及區域網平差方法
論文推薦| 張春森：顧及曝光延遲的無人機GPS輔助光束法平差方法
2017中國地理信息產業優秀工程公示
78歲院士劉先林穿舊鞋坐高鐵 二等座上仍不忘備課
如何評價 Google推出的室內定位技術VPS？
北鬥專輯|張小紅：BeiDou B2/Galileo E5b短基線緊組合相對定位模型及性能評估
想著為國家和人民做事，就充滿活力——首個全國科技工作者日專訪78歲李德仁雙院士
武大測繪學院李星星教授獲歐洲地學聯合會傑出青年科學家獎
再不去把握這九大空間信息趨勢, 等著被顛覆吧！
徵稿| 2017測繪地理信息前沿技術論壇（無人機測繪技術及應用專場）徵文通知
測繪地理信息領域至少30人有望新晉工程院院士
書訊| 張過教授：《線陣推掃式光學衛星幾何高精度處理》
權威 | 專業 | 學術 | 前沿
微信投稿郵箱 | song_qi_fan@163.com
微信公眾號中搜索「測繪學報」，關注我們，長按上圖二維碼，關注學術前沿動態。
歡迎加入《測繪學報》作者QQ群： 297834524
進群請備註：姓名+單位+稿件編號