GPS應用 

遙測資訊平台 3D 建模    

K-way/KD Tree Semi-Matroid Classifiers  

Parallel Positive Boolean Function Classifiers  

Parallel Simulated Annealing Band Selection for Hyperspectral Imagery   

Parallel Particle Swarm Optimization Band Selection for Hyperspectral Imagery   

Multisource Data Fusion 

Landslide Classification    

 

研究方法: K-way Tree Semi-Matroid Classifiers

本研究所採用的是k-way的樹狀結構,並且利用改善後的semi-greedy搜尋法,來尋找出不同類別間的最佳區域邊界,因此我們將此方法稱為KWSM (k-way Semi-Matroid) 分類器,如下圖所示為k-way Semi-Matroid (KWSM)分類器的架構。

 

 

k-way Semi-Matroid (KWSM)分類器的架構流程圖

 

研究方法: KD Tree Semi-Matroid Classifiers

「KD-tree」演算法為二元樹 (binary tree) 的一種,其原理為應用分群的概念,將一點集合以二元樹的概念依次分類,「KD Tree SMC」演算法是以KD-tree概念為基礎,利用一個正方形(體)來含括同類別的訓練樣本點,架構如下圖。本研究計劃將「KD Tree SMC」演算法,以第一年計劃所發展出來的平行「奇異值分解演算法」減少高維資料的維度,並利用「多/高光譜光學、SAR與LiDar遙測影像的資料融合」,於不同類別間,有著其自然的分散度的特性,應用於平行「KD Tree SMC」演算法的可行性。另外除了將此演算法,以「平行計算」的概念實現於先前提出之「混合式多核心多處理機叢集平行計算」的架構下,並預計將此演算法,以「通用計算圖形處理單元」技術,有效率地增加執行的速度。

 

 

KD二元樹為基礎之SMC 

Parallel Positive Boolean Function Classifiers

 

研究方法:

由於「布林函數分類器」(PBF) 具有高對稱與平行的特性,本研究團隊也因此於九十六年國科會計畫中,提出一個高效率「平行布林函數分類器」計算(High Performance Computing Techniques for the PBF Classifier of High-Dimensional Datasets) 的演算法(詳見本研究團隊九十六年於IEEE IGARSS ‘07口頭發表之"A Parallel Positive Boolean Function Approach to Supervised Multispectral Image Classification" 之論文,本篇已改寫為期刊投稿IEEE Geosci. Remote Sensing Letters並review中)來加速「布林函數分類器」的處理速度,本方法是改進單一處理器執行「布林函數分類器」的方法,應用「平行叢集計算」改善「布林函數分類器」高維資料計算效率,將運算速度利用「平行叢集計算」提升,以改良「布林函數分類器」運算較慢的缺點,請參考下圖所設計的平行計算「布林函數」流程圖。

 

 

一個利用平行計算的「布林函數」多類分類器的流程圖

「平行布林函數分類器」可以大幅減少「布林函數分類器」所需的計算時間,同時所需的記憶體也分散至其它計算機上,大幅降低了每台電腦所需的記憶體用量。採用「平行計算」技術來解決「高維遙測資料」龐大資料運算的問題,有著 1. 高效益價格比的優點:由於目前多處理機電腦已經接近傳統高階工作站的速度水準,使用多處理機電腦來構建高速「平行計算」系統已成為主流。2. 投資分散的優點:由於「平行計算」的多處理機電腦系統,多處理機電腦計算單元數目可以任意增減,因此可以分散投資的風險,是以「多處理機平行化」將是「高維資料」、「高速運算」的主流。   

Parallel Simulated Annealing Band Selection for Hyperspectral Imagery

研究方法:

80年代科學家發現「退火冶金術程序」和尋找「近似最佳解」問題有著極為相似的關聯性。類似於「模擬退火」冶金術,「模擬退火波段選取方法」(SABS)提供一個冶金鍛練的進度表,一開始設定一個固定有效的冶煉高溫,隨著時間漸漸遞減溫度直到趨近於零。這種啟發式的最佳演算法(Heuristic algorithm),近似於在各種不同的溫度下執行的巢狀迴圈,用以逼近「近似最佳解」。「模擬退火波段選取」方法的優點包含: 1. 可避免在最高溫度時,「最佳近似解」出現於區域極小值(local minima);2. 在較低溫度下,使得「最佳近似解」有機會呈現全域極小值(global minima)。

由於「模擬退火法波段選取」(被SPIE學會邀稿發表於最新2006編輯之SPIE Newsroom雜誌上)具有高對稱與平行的特性,應用SABS可以將「高維資料」的光譜解析度分散的特性加以放大應用及開發擴充,並可充分利用其絕佳之分散性,提供一個很好的模組特徵選取方法,尤其是應用於特殊的「地質遙測影像融合」中所產生之高維度、巨大資料量,所伴隨產生之高度複雜計算量及高消耗計算機資源的問題上,其所展現的縮減多餘無用資料量,而不失精確度的解決效益。本研究團隊也因此提出一個高效率「平行模擬退火波段選取」計算 (High Performance Computing Techniques
for the SABS of High-Dimensional Datasets)的演算法來加速「模擬退火波段選取」的處理速度,本方法是改進單一處理器執行「模擬退火波段選取」的方法,應用「平行叢集計算」改善「模擬退火波段選取方法」高維資料計算效率,並改良「模擬退火法波段選取」高度複雜計算量及高消耗計算機資源的問題(詳見本研究團隊九十六年於IEEE IGARSS ‘08發表之"Parallel Simulated Annealing Approach to Band Selection for Hyperspectral Imagery" 之論文,本篇準備投稿IEEE Trans. Geosci. Remote Sensing)。

參考以下圖1~3所示,我們採用文獻中所提出三種不同特性之平行方法,分別為「非互動式多重馬可夫鏈平行模擬退火法」、「同步式多重馬可夫鏈平行模擬退火法」及「非同步式多重馬可夫鏈平行模擬退火示法」;他們皆以多個執行緒執行個別的獨立運算,其中P代表擾動(Perturb)、C為計算求解(Calculate)成本函數、D為判斷(Determine)是否接受新的鄰近解,並且每個執行緒之間,在每次降溫階段之前,會透過灰色區塊(Global State Access)相互交換自己當下較佳解,若其他執行緒的較佳解比自己的好,則會繼承其結果,並繼續運算,黑色區塊為(Idle State)代表先執行完的執行緒等待所浪費的時間。

 

 

圖1. 非互動式多重馬可夫鏈平行模擬退火示意圖

 

 

圖2. 同步式多重馬可夫鏈平行模擬退火示意圖

 

 

圖3. 非同步式多重馬可夫鏈平行模擬退火示意圖

 

「平行模擬退火波段選取方法」可以大幅減少「模擬退火波段選取」所需的計算時間,同時所需的記憶體也分散至其它計算機上,大幅降低了每台電腦所需的記憶體用量。採用平行的「叢集計算」(cluster parallel computing)及「多核心處理器」(multi-core) 電腦技術來解決「高維遙測資料」龐大資料運算的問題,有著 1. 高效益價格比的優點:而由於目前「圖形處理單元」(graphics processing units, GPU)電腦也已經接近傳統超級電腦工作站的速度水準,使用「GPU多核心處理器叢集」電腦來構建高速「平行計算系統」已成為主流。2. 投資分散的優點:由於「平行計算」的「GPU多核心處理器叢集」電腦系統,計算單元數目可以任意增減,因此可以分散投資的風險,是以「電腦平行化」將是「高維資料」、「高速運算」的主流。3.
採用「平行模擬退火波段選取」的方法,更有機會挑脫區域極小值,進而走訪整個解空間,獲得全域極小值,挑選出更具有代表性的波段。   

    Parallel Particle Swarm Optimization Band Selection for Hyperspectral Imagery

研究方法:

「粒子群尋優化法」(PSO)假設有一群粒子(particle),每個粒子都有一個fitness 函數來判斷該粒子的位置,每個粒子皆可記錄所有搜尋過的最佳位置,另還有一個速度向量,用以決定距離及方向。假設在這個區域裡我們欲尋找最佳解,所有的粒子都不知道最佳解在哪裡,但他們知道目前距離最佳解還有多遠,那麼找到最佳解的策略是什麼?最簡單的方法就是找尋距離最佳解最近的粒子之周圍區域及根據自己本身紀錄最佳位置判斷最佳解的所在,如下圖1。由於Foster曾經對於「粒子群尋優化法」提出一個設計最佳平行運算負載平衡的方法,試將多處理器之平行計算工作負載效能最佳化。

 

 

圖1 粒子群尋優化法(PSO)

 

因此本研究應用「混合式多核心多處理機叢集平行計算」(Hybrid Multi-core and Multi-computer cluster parallel computing)及「通用計算圖形處理單元」(General-purpose computing on graphics processing units, GPU)技術,發展「粒子群尋優化」(Particle Swarm Optimization, PSO),對高維遙測影像資料進行波段選取,以提升分類器的辨識正確率,如下圖2所示。

 

 

圖2 以PPSOBS(平行粒子尋優法於特徵萃取)進行高光普影像分類流程圖  

Multisource Data Fusion

 

資料融合概念:

資料融合(Data Fusion)之技術發展主要目的在於處理不同來源與格式之資料,透過架構與演算法之處理,而成為研究者或分析者所需之有效資料,而融合的理論在諸多領域上已廣泛被應用,例如在交通層面,透過資料融合技術,將固定式車輛偵測器、影像式偵測器、GPS探測車等交通資料來源,進行篩選與結合,再提供給交通管理中心進行交通控制策略之擬定;醫學領域上,單一種類影像無法獲取足夠的資訊,因此將電腦斷層掃瞄及磁振造影兩種影像融合,可保留兩種不同類型影像的特性,增益兩種影像的價值達到正確判讀及診斷之功效;而在遙感探測的領域上,利用衛星或飛機從空中探測地表之地物地貌,並運用不同的電磁頻譜的特性記載影像,例如利用不同解析度的遙測影像,結合影像融合(Image
Fusion)的技術,將高解析度全色態影像及低解析度多頻譜影像進行融合,以助於影像後續的判釋及分析。

 

本實驗室研究主要利用SAR (Synthetic Aperture Radar)及MASTER (MODIS/ASTER airborne simulator)兩種同一時間不同來源影像,藉由資料融合的概念進行融合,以提高影像的有效程度。