基於最小生成樹的多尺度多層次影像分割方法
2023-08-13 08:50:26
專利名稱：基於最小生成樹的多尺度多層次影像分割方法
技術領域：
本方法屬於圖像處理與識別技術領域，特別是涉及一種新的基於最小生成樹最優 化理論以及圖模型特點的多層次多尺度金字塔影像分割方法。
背景技術：
高空間解析度遙感影像為我們提供了地面景觀的高精度空間幾何信息、豐富的紋 理信息以及多光譜信息，使得傳統的基於像素的遙感影像分類方法已不適用，因此，高分辨 率遙感影像處理面臨影像所提供的細節的挑戰。為此，BaatZ*khape於1999年在[1]中 指出重要的語義解釋更需要用有意義的影像中對象及對象之間的相互關係而不是用一個 個像素來表示，因此，提出了面向對象的高解析度遙感影像目標識別與分類方法，即首先對 影像進行分割生成對象區域，並用分層網絡來描述對象，再以對象為單位進行目標識別。基 於對象的光譜、形狀、紋理、空間關係以及人的知識進一步推理的新分類器證明在高空間分 辨率領域非常有用，它符合人類識別目標的規律，提高了分類精度和細節。面向對象的圖像 分割是對象獲取的主要方法之一，面向對象的目標識別技術是通過對對象的光譜、幾何、紋 理、空間鄰域關係等信息組合來識別目標，從理論和實際應用中發現，對象分割的好壞直接 影響影像分類識別的效果和精度，因為它直接關係到能否準確、有效地提取圖像上中目標 的幾何信息和結構信息，因此，面向對象高解析度遙感影像分割成為遙感圖像處理中的關 鍵和基礎，面向對象分割方法的研究也成為高空間解析度熱點和難點之一。圖像分割在圖像理解中扮演著重要角色，由它得到的滿足一定準則的同質區域， 區域的內部屬性和外部屬性(區域之間的包含、鄰接關係)的組合對目標識別具有重要意 義。然而，到目前為止還沒有一種圖像分割方法能將影像中的所有目標完全區分開來，往 往會有過分割或欠分割現象，分割方法中參數設置的不同必然會產生不同的分割結果，而 且通常，同一分割方法在某參數下可能對某類目標達到較好的分割效果，而與此同時，其它 類型目標可能出現過分割或欠分割，很難實現某一尺度參數的設置就能達到對所有目標的 完全劃分，往往只能針對某類目標在某種數據源下選擇合適的分割參數，這也就是說細節 保留和大尺度在同一分割算法中很難並存，特別是對於高解析度遙感影像，因此，通常研究 的圖像分割只是一種可以實現從影像中將特定尺度目標劃分開來的分割算法，選擇不同參 數將從影像中獲取不同細節(尺度大小)的對象。圖像分割的主要目的是為了目標識別， 為目標識別提供所需特徵。因此，提供可以提高分類和識別精度的分割結果以及有利於提 供目標識別所需對象也就成了是分割方法主要任務。圖像分割中分割精確性與易分割性 的矛盾、過分割與欠分割的矛盾用固定尺度的分割技術難以解決，但通過多尺度分割技術 有可能解決這些矛盾，這方面研究和有待改進的主要內容包括基於多尺度的圖像預處理； 更為合適的多尺度數據結構(描述和存儲數據)；與之配合更好的多尺度分割策略(抽取 數據的準則)。目前大多數多尺度分割都是結合多尺度分析理論，以事物在某一尺度下表現 為異質的結構要素，在大一級尺度上觀測卻是同質的這樣一個尺度效應為分割準則，設置 不同的尺度參數來得到不同尺度上的分割結果，即大尺度粗分，小尺度細分，但沒有建立大小尺度分割結果之間的聯繫以及分割結果的空間關係。同時，這種在多尺度圖像預處理後 進行的圖像分割，在高層次上會出現邊界模糊不準確問題，從而不利於高層次目標準確提 取。地物本身屬性、地物組成結構以及地物之間的鄰接關係等對目標識別與分類具有重要 意義，因此，設計滿足多尺度多層次表達的分割算法非常有意義。從目標識別角度考慮，人類認知世界、識別目標是將不同尺度組合，由粗到細、由 細到粗的認知過程，從一幅影像中判斷出不同目標時，是綜合了從圖像中所觀察到的各種 對象不同細節及其相互之間關係，如顏色、形狀、紋理、大小、鄰接、包含等關係才獲得很高 的識別準確度，因此，在計算機目標識別、高解析度遙感影像分類以及目標識別時，充分利 用影像所提供的目標的光譜、幾何以及鄰接、包含等特徵，將會大大提高識別和分類精度， 正因如此，建立智能目標識別與分類系統，需要獲取不同尺度對象的光譜、形狀、紋理和鄰 接關係，建立不同尺度的分類層次，這也就是說我們需要從影像中獲取不同尺度、不同層次 的綜合信息，而這也正是圖像分割所要提供的信息。由前面分析可知，通過某一組特定尺度 參數得到的分割結果並不能達到完全描述這些信息的目的，因此，需要將不同尺度參數得 到的分割結果，由粗到細或由細到粗的分割信息進行描述，這就涉及到影像的多尺度多層 次分割與表達，為高解析度遙感影像的目標識別提供有利證據。目前國外已有eCognition商業軟體實現了基於區域增長考慮光譜與形狀特徵的 多尺度多層次影像分割，國內目前還沒有這方面的軟體來實現多尺度多層次分割，大多數 分割都是基於影像多尺度空間選擇不同尺度影像進行分割，缺少層次之間以及鄰接區域之 間空間關係的聯繫與描述。為了更好地分析和利用同一層對象之間的空間鄰接關係、多尺度多層次信息、上 下層對象之間存在包含與被包含的關係，需要實現將小尺度目標合併得到大尺度目標的多 層次分割，這也正符合實際事物、地物層次劃分思想。本發明研究並實現了基於最小生成樹 的多層次多尺度影像分割，用金字塔圖模型來表示各層數據以及層內、層間聯繫。目前金字 塔圖模型主要有簡單圖(simple graph)、對偶圖(dual graph)和組合圖(combinatorial maps)三種金字塔表達模型。簡單圖是無自環、無重邊的圖，其結構簡單、容易實現，計算效 率高，映射節點的父子關係方便，容易獲取頂點間的鄰接關係，具有很強的實用性，因此，廣 泛應用於金字塔分割圖模型中。金字塔收縮方法是指如何由G1得到G1+1，特別是對於圖像分割來說，它確定了金字 塔的收斂高度以及所生成的每層數據的性質，合理的收縮方法可以避免金字塔過高而產生 存儲空間消耗太大，這實際上就是分割準則的設置，準則設置的好壞也決定了生成的分割 區域性質。Haxhimusa等分別用對偶圖[2_4]和組合圖[5]構造金字塔，用Boruvka最小生 成樹算法和文獻W]中的分割準則實現了影像的多層次多尺度分割。構造最小生成樹的圖像分割思想省去了構建整幅圖像最小生成樹的過程，提高了 效率。但是，簡單閾值準則對噪聲敏感，而且此類方法在分裂或合併過程中，與原始數據無 關，僅與邊權值有關。當然，也可以在算法實現和準則設置中將原始數據及其鄰域關係考慮 進來，但這樣將會增加計算複雜度。
背景技術：
中的引用文獻1. Blaschke, T. and J. Strobl, What 『 s wrong with pixels ？ Some recent developmentsinterfacing remote sensing and GIS. GIS-Zeitschrift
4fiirGeoinformationssysteme, 2001. 14(6) :ρ· 12-17.2. Haxhimusa, Y. and W. Kropatsch, Hierarchy of Partitions with Dual GraphContraction, in Pattern Recognition.2003, Springer Berlin/Heidelberg, p. 338-345.3. Haxhimusa, Y. and W. Kropatsch, Segmentation Graph Hierarchies, in Proceedingsof Joint Workshops on Structural, Syntactic, and Statistical PatternRecognition S+SSPR. 2004, Springer Berlin/Heidelberg, p. 343-351.4. Kropatsch, W. G. and Y. Haxhimusa. Grouping and segmentation in a hierarchy ofgraphs, in Proceeding of the 16th IS&T/SPIE Annual Symposium. 2004.5. Ion, A. , Y. Haxhimusa, W. G. Kropatsch, and L. Brunz, Hierarchical ImagePartitioning using Combinatorial Maps, in Proceeding of the JointHungarian-Austrian Conference on Image Processing and Pattern Recognition, D.Chetverikov, L.Czuni, and M. Vincze, Editors. May 2005 :Hungary. p. 179—186.6. Felzenszwalb, P. F. and D. P. Huttenlocher, Efficient Graph-Based ImageSegmentation. International Journal of Computer Vision 200459(2) :p. 167-18
發明內容
針對多尺度多層次影像分割與描述問題，為避免多尺度空間中出現的邊界模糊不 準確問題，同時能描述對象之間鄰接關係以及上下層之間的關係，本發明提供了一種基於 最小生成樹的多尺度多層次影像分割方法。本發明的技術方案包括如下步驟步驟一、將圖像用簡單圖模型來表示，簡單圖模型的每個頂點對應圖像的一個像 素，每兩個鄰接頂點之間用邊連接，每條邊的邊權值為該邊連接的兩個頂點所對應兩像素 之間的差異；步驟二、根據預先設定的區域合併準則以及分割參數對步驟一所得簡單圖模型進 行基於最小生成樹的影像分割，分割時從簡單圖模型中的最小權值邊開始按區域合併準則 進行增長直到最大權值邊，合併生成的每個最小生成樹代表一個連通的區域，得到初始的 分割結果；步驟三、以分割結果所得每個區域為頂點，每個區域與其鄰接區域之間由邊連接， 以區域與鄰接區域間的直方圖距離作為邊權值，構造出新的簡單圖模型；步驟四、對步驟三所得簡單圖模型根據邊權值進行基於最小生成樹的影像分割， 得到新的分割結果，然返回到步驟三循環執行構造新的簡單圖模型並分割，每輪循環中進 行分割時採用的區域合併準則設置不同大小相似度閾值，經多次循環完成得到所需的多尺
度多層次影像分割，每輪循環得到的簡單圖模型和步驟一得到的簡單圖模型形成影像金字 +
-tB。而且，在步驟一，簡單圖模型中邊權值為每條邊的權重，採用波段加權歐氏距離來
計算權重。或者，在步驟一，簡單圖模型中邊權值為每條邊的權重，在圖像為多波段影像時採用餘弦角距離來計算權重。而且，在步驟二，預先設定的區域合併準則綜合多種區域特性，包括考慮光譜、形 狀和紋理。而且，在步驟二，分割參數根據預先設定的區域合併準則來進行設定，分割參數中 包含一個用於防止生成過小區域的最小區域面積大小參數。而且，在步驟三，鄰接區域間的直方圖距離採用適合於多波段統計特性比較的直 方圖距離。而且，直方圖距離採用的是卡方距離，鄰接區域間的直方圖距離取值範圍為0-1。而且，影像金字塔每一層對應一個簡單圖模型，步驟一得到的簡單圖模型是影像 金字塔的最底層；整個影像金字塔用一個樹結構來描述，該樹結構反映上層某個區域由下 一層多個區域組成的對應關係。本發明採用圖模型來描述影像以及分割所生成的每一層對象以及對象之間的鄰 接關係，採用基於最小生成樹理論的圖像分割，以區域之間的直方圖距離構建邊權，通過設 置不同大小相似度閾值實現多尺度多層次影像分割。
圖1為本發明的多層次多尺度分割金字塔構建示意圖。
具體實施例方式以下結合附圖和本發明的實施例，對本發明技術方案進行詳細說明。實施例的實 現過程如下步驟一、將圖像用簡單圖模型來表示，簡單圖模型的每個頂點對應圖像的一個像 素，每兩個鄰接頂點之間用邊連接，每條邊的邊權值為該邊連接的兩個頂點所對應兩像素 之間的差異。簡單圖模型中邊權值為每條邊的權重，實施例採用波段加權歐氏距離來計算權 重。特別地，當圖像為多波段影像時，還可以採用餘弦角距離來計算權重。具體計算方式為 現有技術，本發明不予贅述。步驟二、根據預先設定的區域合併準則以及分割參數對步驟一所得簡單圖模型進 行基於最小生成樹的影像分割，分割時從簡單圖模型中的最小權值邊開始按區域合併準則 進行增長直到最大權值邊，合併生成的每個最小生成樹代表一個連通的區域，得到初始的 分割結果。最小生成樹問題描述為尋找邊權和最小的生成樹，對於圖像分割來說，尋找差異 最小的連通區域問題就可以轉化為最小生成樹問題。因此，在步驟一實現了將圖像表示的 像素之間關係用簡單圖模型表示後，可以基於最小生成樹對步驟一所得簡單圖模型進行影 像分割。基於最小生成樹的圖像分割主要有自頂向下分裂最小生成樹與自底向上合併生成 多個最小生成樹兩種策略。實施例採用Kruskal最小生成樹算法以及自底向上的合併策略 實現基於最小生成樹的影像分割，具體算法和策略為現有技術，本發明不予贅述。在預先設定區域合併準則時，建議綜合多種區域特性，包括考慮光譜、形狀和紋理 等，具體實施可以根據需要設定。為方便實施參考起見，以下提供三種準則設定方案
6
A基於最小類內方差的考慮光譜和形狀特徵的分割準則，設判斷是否能夠合併的 對象為區域S1和區域&，兩區域合併後所得對象的類內差異由( 式計算，若差異小於某 閾值th，則區域S1和區域&可以合併，若大於該閾值th則不合併，該準則表示為(1)式
權利要求
1.基於最小生成樹的多尺度多層次影像分割方法，其特徵是包括以下步驟， 步驟一、將圖像用簡單圖模型來表示，簡單圖模型的每個頂點對應圖像的一個像素，每兩個鄰接頂點之間用邊連接，每條邊的邊權值為該邊連接的兩個頂點所對應兩像素之間的差異；步驟二、根據預先設定的區域合併準則以及分割參數對步驟一所得簡單圖模型進行基 於最小生成樹的影像分割，分割時從簡單圖模型中的最小權值邊開始按區域合併準則進行 增長直到最大權值邊，合併生成的每個最小生成樹代表一個連通的區域，得到初始的分割結果；步驟三、以分割結果所得每個區域為頂點，每個區域與其鄰接區域之間由邊連接，以區 域與鄰接區域間的直方圖距離作為邊權值，構造出新的簡單圖模型；步驟四、對步驟三所得簡單圖模型根據邊權值進行基於最小生成樹的影像分割，得到 新的分割結果，然後返回到步驟三循環執行構造新的簡單圖模型並分割，每輪循環中進行 分割時採用的區域合併準則設置不同大小相似度閾值，經多次循環完成得到所需的多尺度多層次影像分割，每輪循環得到的簡單圖模型和步驟一得到的簡單圖模型形成影像金字 + -tB。
2.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是在步驟一，簡單圖模 型中邊權值為每條邊的權重，採用波段加權歐氏距離來計算權重。
3.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是在步驟一，簡單圖模 型中邊權值為每條邊的權重，在圖像為多波段影像時採用餘弦角距離來計算權重。
4.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是在步驟二，預先設定 的區域合併準則綜合多種區域特性，包括考慮光譜、形狀和紋理。
5.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是在步驟二，分割參數 根據預先設定的區域合併準則來進行設定，分割參數中包含一個用於防止生成過小區域的 最小區域面積大小參數。
6.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是在步驟三，鄰接區域 間的直方圖距離採用適合於多波段統計特性比較的直方圖距離。
7.根據權利要求6所述的多尺度多層次影像分割方法，其特徵是直方圖距離採用的 是卡方距離，鄰接區域間的直方圖距離取值範圍為0-1。
8.根據權利要求1所述的多尺度多層次影像分割方法，其特徵是影像金字塔每一層 對應一個簡單圖模型，步驟一得到的簡單圖模型是影像金字塔的最底層；整個影像金字塔 用一個樹結構來描述，該樹結構反映上層某個區域由下一層多個區域組成的對應關係。
全文摘要
本發明提出了一種基於最小生成樹的多尺度多層次影像分割方法，採用圖模型表達及實現多尺度多層次圖像分割。該分割方法適合於各種影像以及各種準則得到的初始分割結果，有效地將過分割區域在高層分割中進行合併，避免了過分割現象；同時，不同層次多尺度分割結果對分析目標結構組成提供了不同層次的特徵描述信息，對目標識別具有重要意義。
文檔編號G06T7/00GK102096816SQ20111003181
公開日2011年6月15日 申請日期2011年1月28日 優先權日2011年1月28日
發明者崔衛紅, 潘斌 申請人:武漢大學