基于超像素的遙感圖像并行分割算法?

李 帥 韓俊崗 范 望 張恩澤

（1.西安郵電大學研究生學院 西安 710121）（2.西安電子科技大學研究生學院 西安 710126）

1 引言

衛星遙感技術的迅速發展，使得遙感圖像的分辨率大幅度提高，從而顯著推動了遙感技術在各個領域的應用。實地調查和人工解譯方法對區域尺度的地物進行處理費時費力，因此，探索快速、高效的高分辨率影像數據處理與信息提取方法，已成為當前遙感研究領域的一個重要研究課題［1］。

在2003 年，Ren［2］等首先提出了超像素這個概念。Gould［3］，Fulkerson［4］，Yang［5］等利用超像素提取特征，直接做物體識別，在PASCAL VOC Challenge 取得了很好的名次。Mori［6］等則利用超像素做人體動作方面的檢測，構造超像素的過程實際上是一種粗糙的圖像分割。

國內外對于圖像分割與研究已久，各種方法層出不窮。近年來隨著研究的日益深入，一些新的效率較高的方法也不斷出現。

對于圖像分割技術來說，目前常用的方法主要有基于閾值的分割、聚類法、基于能量函數的分割、基于圖論的分割和分水嶺算法等分割方法［7］。

基于閾值的分割算法常常是通過設定不同的閾值，依據影像灰度值把像元分為不同灰度級的目標區域和背景區域，這種方法比較簡單、計算量小，但當場景較為復雜時，算法性能較差。為提升閾值的自適應性，Otsu［8］提出最大類間方差法，該算法利用圖像中的灰度直方圖，以目標與背景之間的方差最大而動態地確定圖像分割閾值，但該方法采用窮舉法，計算速度較慢。

聚類分割算法中應用比較廣泛的主要有譜聚類 方 法 和K-means 方 法，陳 作 炳［8］等 首 次 采 用K-means 方法對CT 數據進行分割處理，實現了輪廓提取，Bezdek［9］提出了FCM 算法，又稱模糊C 均值，該方法通過引入樣本到聚類中心的隸屬度，確定樣本所屬區域，實現圖像分割。聚類分割算法的優點是計算較為簡單，但初始參數值對于分割的影響較大。

基于圖論的分割算法是近年來應用較為廣泛的圖像分割方法之一。 主要方法有GC（Graph-Cut）［10］、NC（Normalized Cuts）［11］、RW（Random Walks）［12］、GS（Graph-Based Segmentation）［13］的分割算法。基于圖割的分割算法的優點是分割精度較高，不足之處在于算法效率普遍較低。

分水嶺算法［14］是目前在圖像分割中廣泛被應用的一種算法，其優點在于分割精度高，結果準確，但是其缺點也比較明顯，在分割過程中，很容易出現過分割現象，且其算法效率較低。因此，為了提高遙感圖像的識別能力，尋找一種精度高、速度快的分割算法是圖像分割領域目前面臨的重要問題［15］。

傳統分割算法自身空間復雜度較高，需要將海量遙感圖像數據一次性調入內存并進行分析與處理，不僅降低了分割的速度，甚至會使整個系統異常中斷，進而嚴重限制了其實際應用。本文利用現如今計算機多核的優勢，利用OpenMPI，提出了一種并行分割方案，使得分割時間有了提高，增大了其實際應用范圍。

2 本文工作

本文提出一種快速精確且工程易實現的遙感圖像并行分割方法，旨在解決傳統串行分割的時間消耗多、占用空間大的問題。本文融合了假彩色圖像生成、并行分割、區域異質性評價，邊界合并處理，游程碼壓縮存儲等技術，既保證了分割邊緣的精度，又提高了分割速度，有利于算法的工程應用。其具體步驟如下。

步驟1:計算各波段的圖像熵，選擇信息量最大的四波段，預處理后合成假彩色圖像；

步驟2:對假彩色圖像進行帶狀分塊；

步驟3:設定分割區域參數和終止條件，對分塊后的子圖像進行并行SLIC分割；

步驟4:建立分塊邊界的上下區域鄰接關系圖，設計區域合并準則，對區域進行合并，并更新區域標簽；

步驟5:對全圖的合并區域進行標簽重組，采用游程碼的方法壓縮存儲分割結果。

2.1 假彩色圖像合成

1）計算各個波段的圖像熵，選擇熵值最大的四個波段，此處采用圖像的一元灰度熵作為圖像熵的衡量單位，計算公式如下:

式中，pi是某個灰度在該圖像中出現的概率，可由灰度直方圖獲得。

2）對所選的四個波段分別統計其亮度直方圖，進行閾值為2%的截斷拉伸；

3）提取直方圖累計概率位于2%和98%的亮度值，作為線性歸一化的下、上限，對該范圍內的所有像元歸一化到［0，255］；

4）將圖像從RGB空間變換到XYZ空間:

5）然后將圖像從XYZ空間變換到ST空間:

式中:

6）最后將圖像從ST 空間變換為HLC 空間，生成假彩色圖像。

2.2 分塊理論

遙感圖像有著“數據可分”的優點，所以可以將遙感圖像根據一定的規則進行分塊，分解成一定數量并且相互獨立的圖像塊，按照要求分配給多個線程，各線程獨立讀取分割圖像塊，進行處理并寫入，直到結束。

分塊機制是處理大內存遙感圖像常用策略。在其大數據處理中，數據并行是最常見的處理模式，如圖1和圖2所示，此機制利用虛擬的網格將遙感圖像分成若干塊并分配到相互獨立的子線程中。具體方法如下。

1）影像分塊并編號

根據遙感圖像及其投影獲得影像的分塊邊界，將影像從上到下分成若干個大小相同的矩形子圖像；若下邊界的剩余部分不夠平均分塊的大小，則保留剩余塊的大小。對分塊后的影像，按照從上到下的順序進行編號。

圖1 影像分塊過程圖

2）分配子線程

每個子線程都有相同的劃分方法，根據分塊策略獲得各自對應編號的子圖像。假設有n 個線程，第i個線程要處理的子圖像的編號就是i。

3）分塊處理

子線程按照編號從小到大順序處理各個圖像，并把處理結果保存下來，像主線程發送完成消息，直到所有子圖像處理完畢為止。

圖2 智能分塊器工作原理圖

2.3 圖像分割

1）設置SLIC 分割的參數，包括分割最小因子，預期種子點個數；

2）對SLIC分割算法進行OpenMP并行改造，應用并行編譯指令#pragma omp parallel for 優化循環工作；

程序中最耗時的當屬循環語句，OpenMP 對循環做了優化，編譯指令#pragma omp parallel for就是循環優化的注釋語句，當有其作用時，for 循環的工作就會被分配給一組線程進行執行，每個線程會承擔一定任務，則程序由原來的串行模式轉變為并行模式。

3）在Visual Studio編譯器中，打開項目的“屬性頁”欄，展開“配置屬性”，展開“C++”，將“語言”欄中“OpenMP 支持”選項改成“是”，并在源代碼文件中加入頭文件“omp.h”；

4）根據分塊策略獲得對應編號的子圖像，每個子線程按照編號從小到大順序處理各子圖像，保存處理結果，向主線程發送完成消息，直到所有子圖像處理完畢為止。

2.4 邊界縫合算法

2.4.1 區域異質性

相鄰區域的異質性，與兩個區域的顏色特性和形狀特性相關。所以計算方式為

Z 代表相鄰區域的權值，w 表示光譜特性所占的權值，h(color)為光譜異質性公式，h(shape)為形狀異質性公式，總的異質性是這兩部分的加權。計算公式如下:

式中，σobj1和σobj2分別表示兩個區域對象的方差，nobj1和nobj2為為兩個區域對象的像素個數，nmerge表示合并后對象像素個數，σmerge表示合并后對象的方差。

式中，ωcmpct為緊湊度權值，取值0 到1 之間，為緊湊度異質性表示平滑異質性，l 表示區域邊界長度，n 表示區域個數，b 表示區域最小外接矩形周長。

2.4.2 邊界區域鄰接圖

邊界區域鄰接圖描述分塊后子圖像分割結果的邊界區域鄰接關系，在圖3 中，圖3（a）表示兩個相鄰分塊的邊界處的區域標簽，圖3（b）表示圖3（a）對應的邊界區域鄰接圖。

具體步驟如下。

Step 1:掃描分割后的分塊邊界，確定邊界區域的節點標簽；

Step 2:根據分割邊界的空間位置關系，建立邊界處的節點關系；

Step 3:根據區域異質性的定義，計算節點區域的權值Z；

Step 4:邊界區域鄰接圖建立完成。

2.4.3 邊界合并處理步驟

根據分塊邊界處建立的鄰接圖，就可以根據合并準則進行邊界區域的分割處理其具體步驟如下。

Step 1:根據分塊處邊界上區域和下區域空間位置關系，建立邊界鄰接圖；

Step 2:按照從左到右的順序依次遍歷鄰接圖中上區域的節點；

Step 3:找出上區域節點相鄰的下區域節點；

Step 4:判斷下區域所有相鄰邊的權值是否在設置的區域異質性閾值范圍內，如果在，將下區域的節點標簽更新成上區域標簽，并重新計算該標簽區域的屬性值。

Step 5:重復Step 2，3，4 步驟，直到所有的上區域節點處理完成，則結束。

圖3 邊界標簽和區域鄰接圖

2.5 圖像存儲算法

1）對所有分塊的邊界進行區域合并后，對全圖的標簽進行連續化整理，使標簽值從0 開始且連續；

2）將分割區域采用游程碼的方式進行壓縮存儲；

3）如圖4 所示，首先保存圖像文件信息頭、圖像大小和分割區域個數，然后根據實際的分割結果，以游程碼結構，保存每一行的分割區域標簽。N1表示分割結果第一行不同游程碼的個數，NM表示分割結果第M行不同游程碼的個數。

圖4 游程碼存儲圖

3 實驗結果與分析

3.1 實驗環境

3.1.1 硬件環境

系統:Windows7

CPU:Intel（R）Core（TM）i3-4170 四核

主頻:3.7GHz

內存:8G

3.1.2 軟件環境

Visual Studio 2010軟件

OpenMP支持

3.2 實驗評價

并行計算效率常用的評價方法有很多種，如執行時間、加速比等。

3.2.1 執行時間

對于并行分割算法來說，其執行時間是衡量算法的性能指標之一，其主要包括2 個部分:并行執行時間和串行執行時間。并行執行時間是所有線程完成全部工作所消耗的時間。串行執行時間是程序串行執行的時間。

3.2.2 加速比

加速比是串行執行時間與并行執行時間的比值，它是評價并行分割算法最重要的指標。

3.3 實驗方案

3.3.1 并行實驗方案

為了檢測并行分割算法的提速效果，本文設計了并行實驗方案，具體內容如下。

1）實驗數據

采用Landsat8 衛星圖像作為原圖像，將原圖像進行裁剪，生成14 個不同尺寸的圖像，具體見表2.3。

2）對實驗用到的14 個影像數據進行數據分塊；

3）采用串行的方式分別對14 個影像數據的分塊子影像進行分割，每組分割數據統計20 次，然后去每組的平均值作為其對應串行時間；

4）對分割算法進行OpenMP 并行改造，然后將14 個硬性數據的分塊數據交給多線程執行，每組進行10次實驗，然后記錄并行執行時間；

5）對獲得的結果進行耗時評價。

3.3.2 邊界合并算法實驗方案

為了檢測邊界合并算法的有效性，本文設計了以下實驗方案，具體內容如下。

1）實驗數據具體見表1；

2）對所選三個實驗影像，利用本章改進算法進行分割，不進行邊界合并，記錄實驗結果；

3）對三個實驗影像，利用本章算法進行分割，進行邊界合并，記錄實驗結果；

4）對比實驗結果并分析。

表1 邊界合并算法實驗數據參數列表

3.3.3 分割精度對比實驗方案

為了驗證本分割算法的有效性，本文設計了不同算法對比實驗方案，具體內容如下:

1）實驗數據具體見表2；

表2 分割精度對比實驗數據參數列表

2）對所選四個實驗影像，利用本章改進算法進行分割，記錄實驗結果；

3）對所選四個實驗影像，利用易康軟件的多尺度分割算法進行分割，記錄實驗結果；

4）對比實驗結果并分析。

3.4 實驗結果分析

3.4.1 并行實驗結果分析

根據并行實驗方案，結果見表3，串行執行時間與并行執行時間的對比折線圖見圖5，加速比折線圖見圖6。

通過實驗分析可以得到以下結論:

1）從圖5 可以看出，對于SLIC 分割算法，串行執行時間與并行執行時間相似，與遙感圖像大小近似成線性關系。

2）由于程序執行中，存在數據讀取和存入時間，還有SLIC算法存在大量不可進行OpenMP并行改造的循環語句，所以在圖6 中，加速比一直維持在1.9 上下波動，在四核CPU 下，沒有完全發揮OpenMP 在多核下的加速作用，所得的加速比低于理想情況下的加速比。

表3 串行與并行時間對比表

圖5 串行與并行時間對比圖

圖6 加速比與其平均值對比圖

3.4.2 邊界合并算法實驗結果分析

以下展示了三個不同影像的分割結果數據邊界合并處的局部放大圖，圖7（a）為Landsat8遙感圖像未進行邊界處理的分割結果圖，圖7（b）為Landsat8 遙感圖像進行邊界合并處理的分割結果圖；圖8（a）為SPOT5 遙感圖像未進行邊界處理的分割結果圖，圖8（b）為SPOT5 遙感圖像進行邊界合并處理的分割結果圖；圖9（a）為SPOT6 遙感圖像未進行邊界處理的分割結果圖，圖9（b）為SPOT6 遙感圖像進行邊界合并處理的分割結果圖。

圖7 Landsat8遙感圖像分割結果對比圖

圖8 SPOT5遙感圖像分割結果對比圖

圖9 SPOT6遙感圖像分割結果對比圖

從圖7、圖8 和圖9 中，在進行合并處理前，存在很明顯的分界線，進行合并處理后，已經消除了圖（a）中存在的分界線，由于合并前，合并后采用相同的分割方法和相同的分割參數，所以選擇的分割區域不存在太多的區別，由此，該實驗實現了邊界合并算法的正確性和有效性的驗證。

3.4.3 分割精度對比實驗結果分析

以下展示了四個不同遙感圖像使用不同分割算法的分割結果局部放大圖，圖10（a）為Landsat8遙感圖像使用易康多尺度分割結果圖，圖10（b）為Landsat8 遙感圖像使用改進算法分割結果圖；圖11a 為SPOT5 遙感圖像使用易康多尺度分割結果圖，圖11（b）為SPOT5 遙感圖像使用改進算法分割結果圖；圖12（a）為SPOT6 遙感圖像使用易康多尺度分割結果圖，圖12（b）為SPOT6 遙感圖像使用改進算法分割結果圖。圖13（a）為GF1遙感圖像使用易康多尺度分割結果圖，圖13（b）為GF1 遙感圖像使用改進算法分割結果圖。

圖10 Landsat8遙感圖像不同算法分割結果對比圖

圖11 SPOT5遙感圖像不同算法分割結果對比圖

圖12 SPOT6遙感圖像不同算法分割結果對比圖

圖13 GF1遙感圖像不同算法分割結果對比圖

根據不同分割算法的實驗結果，對其計算對應的錯分率和區域數比，其具體如表4。

從圖10、圖11、圖12 和圖13 中可以很明顯地看出，同一影像，使用本章分割算法得到的實驗結果圖，能夠找到正確的邊緣，然而，使用易康自帶的多尺度分割算法得到的實驗結果圖，都存在欠分割的情況，不能找到正確的邊緣。圖13 中顯示GF1影像的分割局部放大圖，使用多尺度分割，對圖中右下角深綠色島嶼目標的分割邊緣明顯不正確。表4 統計了不同算法的錯分率和區域數比，很顯然，本章改進分割算法在保持區域數比與多尺度分割算法一致的前提下，錯分率更低，分割更準確。以上驗證了基于超像素的遙感圖像并行分割算法的有效性。

表4 不同算法分割結果評價指標統計表

4 結語

本文引入了遙感圖像并行的思想，在SLIC 分割算法的基礎上，做了相應的改進，利用遙感圖像數據可分的特征，提出遙感圖像數據分塊理論和基于區域鄰接圖的邊界合并算法，設計出基于超像素的遙感圖像并行分割算法；最后，根據并行實驗方案和邊界合并算法實驗，驗證了本算法在遙感圖像分割領域的正確性和有效性。