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

李 帥 韓俊崗 范 望 張恩澤

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

1 引言

衛(wèi)星遙感技術(shù)的迅速發(fā)展，使得遙感圖像的分辨率大幅度提高，從而顯著推動(dòng)了遙感技術(shù)在各個(gè)領(lǐng)域的應(yīng)用。實(shí)地調(diào)查和人工解譯方法對(duì)區(qū)域尺度的地物進(jìn)行處理費(fèi)時(shí)費(fèi)力，因此，探索快速、高效的高分辨率影像數(shù)據(jù)處理與信息提取方法，已成為當(dāng)前遙感研究領(lǐng)域的一個(gè)重要研究課題［1］。

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

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

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

基于閾值的分割算法常常是通過設(shè)定不同的閾值，依據(jù)影像灰度值把像元分為不同灰度級(jí)的目標(biāo)區(qū)域和背景區(qū)域，這種方法比較簡(jiǎn)單、計(jì)算量小，但當(dāng)場(chǎng)景較為復(fù)雜時(shí)，算法性能較差。為提升閾值的自適應(yīng)性，Otsu［8］提出最大類間方差法，該算法利用圖像中的灰度直方圖，以目標(biāo)與背景之間的方差最大而動(dòng)態(tài)地確定圖像分割閾值，但該方法采用窮舉法，計(jì)算速度較慢。

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

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

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

傳統(tǒng)分割算法自身空間復(fù)雜度較高，需要將海量遙感圖像數(shù)據(jù)一次性調(diào)入內(nèi)存并進(jìn)行分析與處理，不僅降低了分割的速度，甚至?xí)拐麄€(gè)系統(tǒng)異常中斷，進(jìn)而嚴(yán)重限制了其實(shí)際應(yīng)用。本文利用現(xiàn)如今計(jì)算機(jī)多核的優(yōu)勢(shì)，利用OpenMPI，提出了一種并行分割方案，使得分割時(shí)間有了提高，增大了其實(shí)際應(yīng)用范圍。

2 本文工作

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

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

步驟2:對(duì)假彩色圖像進(jìn)行帶狀分塊；

步驟3:設(shè)定分割區(qū)域參數(shù)和終止條件，對(duì)分塊后的子圖像進(jìn)行并行SLIC分割；

步驟4:建立分塊邊界的上下區(qū)域鄰接關(guān)系圖，設(shè)計(jì)區(qū)域合并準(zhǔn)則，對(duì)區(qū)域進(jìn)行合并，并更新區(qū)域標(biāo)簽；

步驟5:對(duì)全圖的合并區(qū)域進(jìn)行標(biāo)簽重組，采用游程碼的方法壓縮存儲(chǔ)分割結(jié)果。

2.1 假彩色圖像合成

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

式中，pi是某個(gè)灰度在該圖像中出現(xiàn)的概率，可由灰度直方圖獲得。

2）對(duì)所選的四個(gè)波段分別統(tǒng)計(jì)其亮度直方圖，進(jìn)行閾值為2%的截?cái)嗬欤?/p>

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

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

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

式中:

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

2.2 分塊理論

遙感圖像有著“數(shù)據(jù)可分”的優(yōu)點(diǎn)，所以可以將遙感圖像根據(jù)一定的規(guī)則進(jìn)行分塊，分解成一定數(shù)量并且相互獨(dú)立的圖像塊，按照要求分配給多個(gè)線程，各線程獨(dú)立讀取分割圖像塊，進(jìn)行處理并寫入，直到結(jié)束。

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

1）影像分塊并編號(hào)

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

圖1 影像分塊過程圖

2）分配子線程

每個(gè)子線程都有相同的劃分方法，根據(jù)分塊策略獲得各自對(duì)應(yīng)編號(hào)的子圖像。假設(shè)有n 個(gè)線程，第i個(gè)線程要處理的子圖像的編號(hào)就是i。

3）分塊處理

子線程按照編號(hào)從小到大順序處理各個(gè)圖像，并把處理結(jié)果保存下來，像主線程發(fā)送完成消息，直到所有子圖像處理完畢為止。

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

2.3 圖像分割

1）設(shè)置SLIC 分割的參數(shù)，包括分割最小因子，預(yù)期種子點(diǎn)個(gè)數(shù)；

2）對(duì)SLIC分割算法進(jìn)行OpenMP并行改造，應(yīng)用并行編譯指令#pragma omp parallel for 優(yōu)化循環(huán)工作；

程序中最耗時(shí)的當(dāng)屬循環(huán)語(yǔ)句，OpenMP 對(duì)循環(huán)做了優(yōu)化，編譯指令#pragma omp parallel for就是循環(huán)優(yōu)化的注釋語(yǔ)句，當(dāng)有其作用時(shí)，for 循環(huán)的工作就會(huì)被分配給一組線程進(jìn)行執(zhí)行，每個(gè)線程會(huì)承擔(dān)一定任務(wù)，則程序由原來的串行模式轉(zhuǎn)變?yōu)椴⑿心Ｊ健?/p>

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

4）根據(jù)分塊策略獲得對(duì)應(yīng)編號(hào)的子圖像，每個(gè)子線程按照編號(hào)從小到大順序處理各子圖像，保存處理結(jié)果，向主線程發(fā)送完成消息，直到所有子圖像處理完畢為止。

2.4 邊界縫合算法

2.4.1 區(qū)域異質(zhì)性

相鄰區(qū)域的異質(zhì)性，與兩個(gè)區(qū)域的顏色特性和形狀特性相關(guān)。所以計(jì)算方式為

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

式中，σobj1和σobj2分別表示兩個(gè)區(qū)域?qū)ο蟮姆讲?，nobj1和nobj2為為兩個(gè)區(qū)域?qū)ο蟮南袼貍€(gè)數(shù)，nmerge表示合并后對(duì)象像素個(gè)數(shù)，σmerge表示合并后對(duì)象的方差。

式中，ωcmpct為緊湊度權(quán)值，取值0 到1 之間，為緊湊度異質(zhì)性表示平滑異質(zhì)性，l 表示區(qū)域邊界長(zhǎng)度，n 表示區(qū)域個(gè)數(shù)，b 表示區(qū)域最小外接矩形周長(zhǎng)。

2.4.2 邊界區(qū)域鄰接圖

邊界區(qū)域鄰接圖描述分塊后子圖像分割結(jié)果的邊界區(qū)域鄰接關(guān)系，在圖3 中，圖3（a）表示兩個(gè)相鄰分塊的邊界處的區(qū)域標(biāo)簽，圖3（b）表示圖3（a）對(duì)應(yīng)的邊界區(qū)域鄰接圖。

具體步驟如下。

Step 1:掃描分割后的分塊邊界，確定邊界區(qū)域的節(jié)點(diǎn)標(biāo)簽；

Step 2:根據(jù)分割邊界的空間位置關(guān)系，建立邊界處的節(jié)點(diǎn)關(guān)系；

Step 3:根據(jù)區(qū)域異質(zhì)性的定義，計(jì)算節(jié)點(diǎn)區(qū)域的權(quán)值Z；

Step 4:邊界區(qū)域鄰接圖建立完成。

2.4.3 邊界合并處理步驟

根據(jù)分塊邊界處建立的鄰接圖，就可以根據(jù)合并準(zhǔn)則進(jìn)行邊界區(qū)域的分割處理其具體步驟如下。

Step 1:根據(jù)分塊處邊界上區(qū)域和下區(qū)域空間位置關(guān)系，建立邊界鄰接圖；

Step 2:按照從左到右的順序依次遍歷鄰接圖中上區(qū)域的節(jié)點(diǎn)；

Step 3:找出上區(qū)域節(jié)點(diǎn)相鄰的下區(qū)域節(jié)點(diǎn)；

Step 4:判斷下區(qū)域所有相鄰邊的權(quán)值是否在設(shè)置的區(qū)域異質(zhì)性閾值范圍內(nèi)，如果在，將下區(qū)域的節(jié)點(diǎn)標(biāo)簽更新成上區(qū)域標(biāo)簽，并重新計(jì)算該標(biāo)簽區(qū)域的屬性值。

Step 5:重復(fù)Step 2，3，4 步驟，直到所有的上區(qū)域節(jié)點(diǎn)處理完成，則結(jié)束。

圖3 邊界標(biāo)簽和區(qū)域鄰接圖

2.5 圖像存儲(chǔ)算法

1）對(duì)所有分塊的邊界進(jìn)行區(qū)域合并后，對(duì)全圖的標(biāo)簽進(jìn)行連續(xù)化整理，使標(biāo)簽值從0 開始且連續(xù)；

2）將分割區(qū)域采用游程碼的方式進(jìn)行壓縮存儲(chǔ)；

3）如圖4 所示，首先保存圖像文件信息頭、圖像大小和分割區(qū)域個(gè)數(shù)，然后根據(jù)實(shí)際的分割結(jié)果，以游程碼結(jié)構(gòu)，保存每一行的分割區(qū)域標(biāo)簽。N1表示分割結(jié)果第一行不同游程碼的個(gè)數(shù)，NM表示分割結(jié)果第M行不同游程碼的個(gè)數(shù)。

圖4 游程碼存儲(chǔ)圖

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

3.1.1 硬件環(huán)境

系統(tǒng):Windows7

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

主頻:3.7GHz

內(nèi)存:8G

3.1.2 軟件環(huán)境

Visual Studio 2010軟件

OpenMP支持

3.2 實(shí)驗(yàn)評(píng)價(jià)

并行計(jì)算效率常用的評(píng)價(jià)方法有很多種，如執(zhí)行時(shí)間、加速比等。

3.2.1 執(zhí)行時(shí)間

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

3.2.2 加速比

加速比是串行執(zhí)行時(shí)間與并行執(zhí)行時(shí)間的比值，它是評(píng)價(jià)并行分割算法最重要的指標(biāo)。

3.3 實(shí)驗(yàn)方案

3.3.1 并行實(shí)驗(yàn)方案

為了檢測(cè)并行分割算法的提速效果，本文設(shè)計(jì)了并行實(shí)驗(yàn)方案，具體內(nèi)容如下。

1）實(shí)驗(yàn)數(shù)據(jù)

采用Landsat8 衛(wèi)星圖像作為原圖像，將原圖像進(jìn)行裁剪，生成14 個(gè)不同尺寸的圖像，具體見表2.3。

2）對(duì)實(shí)驗(yàn)用到的14 個(gè)影像數(shù)據(jù)進(jìn)行數(shù)據(jù)分塊；

3）采用串行的方式分別對(duì)14 個(gè)影像數(shù)據(jù)的分塊子影像進(jìn)行分割，每組分割數(shù)據(jù)統(tǒng)計(jì)20 次，然后去每組的平均值作為其對(duì)應(yīng)串行時(shí)間；

4）對(duì)分割算法進(jìn)行OpenMP 并行改造，然后將14 個(gè)硬性數(shù)據(jù)的分塊數(shù)據(jù)交給多線程執(zhí)行，每組進(jìn)行10次實(shí)驗(yàn)，然后記錄并行執(zhí)行時(shí)間；

5）對(duì)獲得的結(jié)果進(jìn)行耗時(shí)評(píng)價(jià)。

3.3.2 邊界合并算法實(shí)驗(yàn)方案

為了檢測(cè)邊界合并算法的有效性，本文設(shè)計(jì)了以下實(shí)驗(yàn)方案，具體內(nèi)容如下。

1）實(shí)驗(yàn)數(shù)據(jù)具體見表1；

2）對(duì)所選三個(gè)實(shí)驗(yàn)影像，利用本章改進(jìn)算法進(jìn)行分割，不進(jìn)行邊界合并，記錄實(shí)驗(yàn)結(jié)果；

3）對(duì)三個(gè)實(shí)驗(yàn)影像，利用本章算法進(jìn)行分割，進(jìn)行邊界合并，記錄實(shí)驗(yàn)結(jié)果；

4）對(duì)比實(shí)驗(yàn)結(jié)果并分析。

表1 邊界合并算法實(shí)驗(yàn)數(shù)據(jù)參數(shù)列表

3.3.3 分割精度對(duì)比實(shí)驗(yàn)方案

為了驗(yàn)證本分割算法的有效性，本文設(shè)計(jì)了不同算法對(duì)比實(shí)驗(yàn)方案，具體內(nèi)容如下:

1）實(shí)驗(yàn)數(shù)據(jù)具體見表2；

表2 分割精度對(duì)比實(shí)驗(yàn)數(shù)據(jù)參數(shù)列表

2）對(duì)所選四個(gè)實(shí)驗(yàn)影像，利用本章改進(jìn)算法進(jìn)行分割，記錄實(shí)驗(yàn)結(jié)果；

3）對(duì)所選四個(gè)實(shí)驗(yàn)影像，利用易康軟件的多尺度分割算法進(jìn)行分割，記錄實(shí)驗(yàn)結(jié)果；

4）對(duì)比實(shí)驗(yàn)結(jié)果并分析。

3.4 實(shí)驗(yàn)結(jié)果分析

3.4.1 并行實(shí)驗(yàn)結(jié)果分析

根據(jù)并行實(shí)驗(yàn)方案，結(jié)果見表3，串行執(zhí)行時(shí)間與并行執(zhí)行時(shí)間的對(duì)比折線圖見圖5，加速比折線圖見圖6。

通過實(shí)驗(yàn)分析可以得到以下結(jié)論:

1）從圖5 可以看出，對(duì)于SLIC 分割算法，串行執(zhí)行時(shí)間與并行執(zhí)行時(shí)間相似，與遙感圖像大小近似成線性關(guān)系。

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

表3 串行與并行時(shí)間對(duì)比表

圖5 串行與并行時(shí)間對(duì)比圖

圖6 加速比與其平均值對(duì)比圖

3.4.2 邊界合并算法實(shí)驗(yàn)結(jié)果分析

以下展示了三個(gè)不同影像的分割結(jié)果數(shù)據(jù)邊界合并處的局部放大圖，圖7（a）為L(zhǎng)andsat8遙感圖像未進(jìn)行邊界處理的分割結(jié)果圖，圖7（b）為L(zhǎng)andsat8 遙感圖像進(jìn)行邊界合并處理的分割結(jié)果圖；圖8（a）為SPOT5 遙感圖像未進(jìn)行邊界處理的分割結(jié)果圖，圖8（b）為SPOT5 遙感圖像進(jìn)行邊界合并處理的分割結(jié)果圖；圖9（a）為SPOT6 遙感圖像未進(jìn)行邊界處理的分割結(jié)果圖，圖9（b）為SPOT6 遙感圖像進(jìn)行邊界合并處理的分割結(jié)果圖。

圖7 Landsat8遙感圖像分割結(jié)果對(duì)比圖

圖8 SPOT5遙感圖像分割結(jié)果對(duì)比圖

圖9 SPOT6遙感圖像分割結(jié)果對(duì)比圖

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

3.4.3 分割精度對(duì)比實(shí)驗(yàn)結(jié)果分析

以下展示了四個(gè)不同遙感圖像使用不同分割算法的分割結(jié)果局部放大圖，圖10（a）為L(zhǎng)andsat8遙感圖像使用易康多尺度分割結(jié)果圖，圖10（b）為L(zhǎng)andsat8 遙感圖像使用改進(jìn)算法分割結(jié)果圖；圖11a 為SPOT5 遙感圖像使用易康多尺度分割結(jié)果圖，圖11（b）為SPOT5 遙感圖像使用改進(jìn)算法分割結(jié)果圖；圖12（a）為SPOT6 遙感圖像使用易康多尺度分割結(jié)果圖，圖12（b）為SPOT6 遙感圖像使用改進(jìn)算法分割結(jié)果圖。圖13（a）為GF1遙感圖像使用易康多尺度分割結(jié)果圖，圖13（b）為GF1 遙感圖像使用改進(jìn)算法分割結(jié)果圖。

圖10 Landsat8遙感圖像不同算法分割結(jié)果對(duì)比圖

圖11 SPOT5遙感圖像不同算法分割結(jié)果對(duì)比圖

圖12 SPOT6遙感圖像不同算法分割結(jié)果對(duì)比圖

圖13 GF1遙感圖像不同算法分割結(jié)果對(duì)比圖

根據(jù)不同分割算法的實(shí)驗(yàn)結(jié)果，對(duì)其計(jì)算對(duì)應(yīng)的錯(cuò)分率和區(qū)域數(shù)比，其具體如表4。

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

表4 不同算法分割結(jié)果評(píng)價(jià)指標(biāo)統(tǒng)計(jì)表

4 結(jié)語(yǔ)

本文引入了遙感圖像并行的思想，在SLIC 分割算法的基礎(chǔ)上，做了相應(yīng)的改進(jìn)，利用遙感圖像數(shù)據(jù)可分的特征，提出遙感圖像數(shù)據(jù)分塊理論和基于區(qū)域鄰接圖的邊界合并算法，設(shè)計(jì)出基于超像素的遙感圖像并行分割算法；最后，根據(jù)并行實(shí)驗(yàn)方案和邊界合并算法實(shí)驗(yàn)，驗(yàn)證了本算法在遙感圖像分割領(lǐng)域的正確性和有效性。