一種快速高分辨率遙感影像分割算法

摘 要：高分辨率遙感影像(如IKONOS 影像)海量數據、復雜細節的特點決定了高分辨率遙感影像分割的技術難點，提出了基于同質性梯度特征、分水嶺算法和最小代價合并的快速分割方法。首先對于原始圖像進行同質梯度計算得到同質梯度圖像；其次利用一種高效的分水嶺變換獲得初始分割圖像；最后給出一種改進的區域合并算法來優化初始分割區域。應用于IKONOS影像的實驗證明與其他的分割算法相比，采用所提出的分割方法能快速、準確地獲得高分辨率遙感圖像的分割結果。

關鍵詞：高分辨率;遙感影像;分割；區域合并；梯度；分水嶺

中圖法分類號：TP391 文獻標識碼：A 文章編號：1001-3695(2006)10-0154-02

Fast Segmentation Algorithm of High Resolution Remote Sensing Image

CHEN Zhong1，2，ZHAO Zhongming1，GONG Peng2

(1.Institute of Remote Sensing Applications， Chinese Academy of Sciences， Beijing 100101， China;2.State Key Laboratory of Remote Sensing Science， Chinese Academy of Sciences， Beijing 100101， China)

Abstract:The characters such as large size and complex details of high resolution remote sensing image like IKONOS image determines the technological difficult point of such image segmentation. In this study， a fast and accurate segmentation approach was proposed based on homogeneity gradient character， watershed transform and mincost region merging. First， a homogeneity gradient image was produced from initial image. Then， an efficient watershed transform was employed to gain the initial segments. Finally， an improved region merging approach was proposed to merge the initial segments and the final segment was obtained. Experiments show， compared with other segment approach， the proposed one is a bit faster and a bit more accurate when applied to the IKONOS image.

Key words:High Resolution;Remote Sensing Image;Segmentation;Region Merging;Gradient;Watershed

圖像分割是一個重要和關鍵的圖像分析技術，是圖像分析的第一步。到目前為止，圖像分割仍然是一個重要的圖像分析研究方向［1］，尤其是在遙感圖像處理領域，近年來得到了越來越多的重視。然而，人們對于遙感圖像的分割算法如區域生長和分水嶺算法大部分是針對SAR（Synthetic Aperture Radar)圖像［2，3］和中、低分辨率的遙感圖像，如TM或者SPOT影像［4，5］，對于高分辨遙感影像分割的研究相對較少。隨著遙感技術的發展，地球資源衛星所提供的遙感影像具有越來越高的空間分辨率，突破米級分辨率的遙感影像數據中，已能夠清晰地分辨出地面的細節特征，從而在農業、森林、礦山開采、環境現狀調查等社會各領域中具有廣闊的應用市場。目前，針對高空間分辨率遙感影像的自動分析和理解的技術手段，尤其是分割技術還很不成熟，影像中大量的信息不能得到充分的應用。

本文通過利用整合光譜和紋理特征的同質梯度特征，結合一種高效的分水嶺算法和區域合并算法來實現高分辨率遙感圖像的分割。

1 算法描述

本分割算法總的描述如下：①利用圖像的同質梯度特征生成同質梯度圖（H圖像)；②將分水嶺變換作用于同質梯度圖像形成初始分割；③給出一種改進的區域合并算法來獲得最終的分割結果。

1．1 局域同質梯度的提取

在高分辨率遙感影像中，既有紋理占優的圖像區域（紋理區），也有亮度一致性程度較高的區域(均色區)，探求一種能同時適應上述兩類區域的特征表達方法顯得非常重要。良好的、兼顧上述兩種區域的特征表達方法應當具有以下屬性：①紋理區和均色區內部的特征值表現出一致性（如同高或同低）；②紋理區和均色區邊緣的特征值也表現出一致性，但是邊緣特征值與內部特征值之間存在明顯的差異。文獻［6］提出的局域同質性指標能較好地滿足上述要求。事實上，更確切地說，上述局域同質性特征為梯度特征，分割的關鍵是找出局域范圍內的極值點。通過計算圖像中每個像素的H值就可以獲得同質梯度圖像（H圖像）。

定義（x，y）為像元在圖像中的位置，I（x，y）為（x，y）處像元的特征值，則對于任意一個窗口（大小為2N+1）中的每一個像元相對于中心像元的矢量可表示為cpi=(xi-xc，yi-yc)。基于cpi可以構建一個新的矢量：

fi=(I(xi，yi)-I(xc，yc))×cpi｜cpi｜(1)

令f為窗口中所有矢量的和，即f=2N+1i=1fi，局域同質性指標H可定義為f的模，即H=‖f‖。

從上面的定義可以看出：①同質區域H值會較小;②H值越大，中心像元越可能接近區域的邊緣。因此選擇合適的H值域值將會獲得較好的同質梯度圖像。

1．2 分水嶺變換

分水嶺變換適合于分割這類梯度特征圖像。在數學形態學領域，圖像數據可以理解為地形表面，其中梯度圖像的灰度表示高程。因此，區域邊緣對應于高的分水嶺線，低梯度的區域內部對應于集水盆地。到目前為止，在眾多的分水嶺算法中一種基于浮點計算的降水分水嶺算法的效率最高［7］。降水分水嶺變換的實質是尋找從圖像的每個像素到圖像表面高程局部較小的下游路徑；而集水盆地則定義為滿足以下條件的所有像素的集合：這些像素的下游路徑終止于同一個高程極小點。本文利用這種分水嶺算法來獲得初始分割圖像。分水嶺變換的詳細原理參考文獻［7］。

分水嶺變換的不足之處在于它的過分割，降水分水嶺算法也不例外，通常人們是通過在分水嶺變換前或者變換后處理來減輕這種過分割現象。本文采用一種域值——面積域值來去除圖像中的一些由于噪聲引起的孤立小區域，面積小于域值的區域將會被去除，在一定程度上也可以消除過分割現象。

1．3 改進的最小代價區域合并算法

通過上面的小區域去除后仍然有一些區域需要通過合并來形成有意義的區域，使得最終結果形成N個有意義的區域。

為了最大化分割單元內部的均質性程度，也就是說從總體上最小化區域內部異質性程度，設法使每一次合并所導致的變異的增加盡可能地小，選擇使變異增加最小的鄰接區域對進行合并，從而達到最小化區域內部的異質性程度和保證合并錯誤率降到最低的目的。每次合并總是合并所有相鄰區域對中的最小代價對。本文采用基于區域灰度均值和面積的判決函數，最小代價判決函數的計算公式如下：

Cost=kj=1SAA2j+kj=1SBB2j-kj=1(SA+SB)C2j（2）

式（2）中，SA，SB分別表示相鄰兩個區域的面積；Aj，Bj表示兩個區域各個波段的均值；Cj表示合并后區域各個波段的均值。

初始分割后的K個區域可以采用RAG（Region Adjacent Graph）的數據結構［8，9］來表示。文獻［8，9］提出的RAG為無向圖G=（V，E），其中V={1，2， …，K}表示節點也就是各個區域，E V×V表示相鄰接區域邊界像素的集合。這種方法在每次合并之后需要重新計算新節點與相鄰節點間的所有鏈接，只有當新鏈接與相鄰節點的其他鏈接的合并代價比較之后才能更新其在RAG中的鏈接，因而該方法的實現效率還是不能令人滿意。

本文提出了一種新的改進的數據結構來描述區域鄰接圖，可表述為G=（V，E，C）。其中V類似于上面提到的V，但考慮到每個區域的鄰接區域數不一樣，為了節省存儲空間、提高效率，采用動態二維數組來描述個區域節點。E與RAG中的E類似，也是表示鄰接區域邊界像素的集合。C是一個記錄合并代價或者區域相似度的矩陣，矩陣的行號和列號分別對應了區域的標志號，矩陣中的每一個元素記錄了行號和列號所對應區域的合并代價。本文通過鏈表來實現改進的RAG，每個鏈表頭表示一個區域，每個鏈表的節點表示該區域的鄰接區域，該區域里存放著指向兩個區域間邊界像素的鏈表指針和兩個區域的合并代價。這樣在建立RAG時可以通過式（2）計算出鄰接區域對的合并代價值，每次合并時只要找出最小合并代價的區域對進行合并，而且每次合并后僅僅需要更新那些與合并的區域相關區域的鏈表，相比對RAG的全搜索，算法速度得到了極大的提高。與文獻［9］的快速合并算法相比，本算法不需要建立和維持NNG（Nearest Neighbor Graph）表，也就避免了建立NNG和更新NNG的耗時和煩瑣的工作，從而提高了算法的速度，減小了算法所需的存儲空間。算法的步驟如下：

（1）輸入改進的RAG。

（2）當區域個數小于結果區域個數和最小合并代價小于所設定的合并代價域值時，做以下循環：①尋找最小合并代價的區域對;②合并最小合并代價區域對;③更新改進的RAG。

（3）輸出合并后的圖像。

2 實驗結果和結論

實驗圖像為某地區4波段、空間分辨率為4m的 IKONOS影像，圖像數據中能體現出地物的紋理和光譜信息。利用本文提出的分割算法的實驗結果如圖1所示。

本算法較好地實現了高分辨率遙感圖像的分割。比較圖1（a）和圖1(b)實驗結果表明：①本文提出的合并算法運算速度快，從初始分割的1 303個區域（圖1（c））到最終的242個區域（圖1(d)）在P4 1.8GHz，256MB內存的PC機上運行時間不到2s。②通過使用局域同質梯度獲得H圖像，很好地獲得了局部同質區域。③對于圖像中較為散碎的地方由于有噪聲等的影響，分割后的區域也相應較為散碎。本算法由于沒有加入形狀參數，所以分割結果的邊界較為粗糙，今后的研究中應加入形狀參數來進一步增強圖像分割的能力。

參考文獻：

［1］章毓晉.圖像分割[M].北京：科學出版社，2001.

［2］P B GDammert，J I H Askne，et al. Unsupervised Segmentation of Multitemporal Interferometric SAR Images[J]. IEEE Transactions on Geoscience and Remote Sensing， 1999，37(5): 2259-2271.

［3］Y Dong， B C Forester， A K Milne. Segmentation of Radar Imagery Using the Gaussian Markov Random Field Model[J]. Int. J. Remote Sensing， 1999，20(8):16171639.

［4］M Acharyya， R K De， M K Kundu. Segmentation of Remotely Sensed Images Using Wavelet Features and Their Evaluation in Soft Computing Framework[J]. IEEE Transactions on Geoscience and Remote Sensing， 2003，41(12):2900-2905.

［5］J Bosworth， T Koshimizu， S T Acton. Multiresolution Segmentation of Soil Moisture Imagery by Watershed Pyramids with Region Merging[J]. Int. J. Remote Sensing，2003，24(4):741760.

［6］F Jing， M J Li， H J Zhang et al. Unsupervised Image Segmentation Using Local Homogeneity Analysis[C]. Proc.of IEEE International Symposium on Circuits and Systems， 2003.

［7］P D Smet， R L Pires. Implementation and Analysis of an Optimized Rainfalling Watershed Algorithm[C]. Proc. of SPIE， Image and Video Communications and Processing， 2000.759766.

［8］羅玲，解梅，陳杉.基于多尺度形態濾波的分水嶺圖像分割方法[J].計算機輔助設計與圖形學報，2004，16(2):168173.

［9］Haris K，Efstratiadis S，et al．Hybrid Image Segmentation Using Watersheds and Fast Region Merging［J］．IEEE Transactions on Image Procosing，1998，7(12)：16841698.

作者簡介：

陳忠(1974-)，博士研究生，主要研究方向為遙感圖像的分類與識別、圖像分割等。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文