1.

張家寶-混合模型平行計算運用於遙測影像特徵抽取與分類法上之分析(2009)

<<

2.

林靜賢-以KML技術實現台灣遙測地理資訊平台(2009)

<<

3.

朱偉傑-在嵌入式系統上實現之不完整條碼辨識系統(2009)

<<

4.

洪聖詠- ZigBee網路之AODV路由改進演算法(2009)

<<

5.

高世宇-以半擬陣為基礎架構之k-way分類器應用於高光譜遙測影像(2009)

<<

6.

陳致嘉-平行化基因演算法應用於超大型積體電路之平面規劃(2009)

<<

7.

陳佳輝-平行粒子尋優演算法於高光譜影像特徵抽取應用(2009)

<<

8.

唐孝威-奇異值分解與半擬陣架構為基礎的k-d樹分類應用於高光譜影像(2009)

<<

9.

廖志緯-避開障礙物直角史坦納樹建構(2009)

<<

 

 

張家寶-混合模型平行計算運用於遙測影像特徵抽取與分類法上之分析(2009)

摘要:
近年來在圖形識別的領域裡,如何從原始的高維資料中,抽取高品質與穩定度的特徵,再根據所選取的特徵透過一個有效的分類器進行分類,進而獲取較好的辨識率,已漸成為研究的主流。然而在遙測領域中在面對大量資料處理時,本論文提出了以特徵為基礎之平行概念的特徵選取方法及以測試樣本為基礎之平行概念的分類器,來解決近年來,已成熟的高維資料量感測技術所帶來的龐大計算問題。

本研究分為兩個部份,第一部分是建立平行近似架構來降低資料維度,再使用平行k-way SM (Semi-Matroid)做資料分類;第二部份是提出混合模型平行架構,利用叢集電腦中每部電腦所設置中央處理器(Central Processing Unit, CPU)和圖形處理器(Graphic Processing Unit, GPU)來完成混合平行系統。

本研究使用的硬體架構是利用MPI(Message Passing Interface)來完成每部電腦之間的資料傳送與接收,並在每部電腦中分別使用OpenMP和CUDA(Compute Unified Device Architecture)的函式庫來處理CPU和GPU的任務分配,建立出一套高計算能力的混合模型平行架構系統。

Top

 

林靜賢-以KML技術實現台灣遙測地理資訊平台(2009)

摘要:
本篇論文提出一個台灣地理遙測地理資訊平台,遵循開放地理空間協會(Open Geospatial Consortium,OGC)[1]所開放之Keyhole Markup Language(KML)語法,整合使用者上傳之遙測影像與地理資訊,並使用JSP與MySQL資料庫實現跨平台之台灣地理遙測資訊系統平台,將各種經由分類器演算法處理過之遙測影像與各領域所發布之遙測影像一同壘蓋於Google Earth(GE)與Google Map(GM)[14],在既有的圖資上加以展示與應用。

此資訊平台亦為一跨領域之架構,整合各個領域所發布之遙測影像,和經由Cluster執行分類器平行程式運算遙測影像資料後所獲取分類之影像,壘蓋於GE和GM中,並於伺服器採用大尺寸Touch Panel做一整合展示應用,亦可利用Wii Remote操控展示,藉此提供使用者更細膩的地理影像資訊且與精確操控GE展示。除此之外,使用者亦可使用網頁方式選擇對其有用之遙測影像,再採用KML自動更新語法,讓最新的遙測影像能即時顯示於使用者的GE與GM中,使用者就能立即獲取更多層面之遙影像與地理資訊,並加以分析對其有利之遙測影像與地理資訊。除此之外亦可讓其他亦遵循OGC
KML的Geographic Information System(GIS)透過下載此資訊平台所發布之KML檔案,在字型的GIS上遊覽展示與應用,最終將呈現一遵循OGC KML規範、跨平台且跨領域之台灣地理遙測資訊系統平台。

Top

 

朱偉傑-在嵌入式系統上實現之不完整條碼辨識系統(2009)

摘要:
自條碼發明以來,大幅地改善了人們的生活習慣,在現今社會中隨處可見到條碼的蹤影。條碼使用簡單的一組黑白相間條紋符號做為儲存的訊號,減少輸入資料的大量人力與時間,並廣泛應用在商品管理、倉儲、物流、圖書管理等領域。
一般的條碼系統所使用的掃描器是以一帶有輔助光源的光罩式或雷射式掃描器為主要解碼工具,不僅成本較為高昂,也必須在一定的距離下才能掃描。為了降低掃描器的成本及增加其可用範圍,已有一些人研究以一般的數位相機、攝影機等做為條碼影像擷取的工具,進而利用影像處理的方法進行條碼辨
識。但從相關的文獻中可發現大部分的辨識方法皆以辨識條碼本體為主,並且當條碼不完整或是髒汙、破損的情況下便無法成功辨識。因此本論文在嵌入式系統的基礎上,以數位相機做為條碼影像擷取工具,並開發新的辨識方法,除了辨識條碼主體外,亦同時辨識條碼的數字,發揮影像處理的優點,提高辨識
的正確率。最後提出一個比對方法,當條碼不完整或破損的情況下,能夠利用交叉比對得到正確的辨識結果。

Top

 

洪聖詠- ZigBee網路之AODV路由改進演算法(2009)

摘要:
ZigBee為一種短距離低速無線個人區域網路,具有低成本、低傳輸速率、低功率消耗、低複雜度的特點;而且還具有可靠性高、組網簡單的優點。ZigBee應用範圍包括無線感測網路(WSN , Wireless Sensor Network)、家庭自動化、智能交通、工廠應用與醫院應用等。目前關於ZigBee的相關研究中,降低耗能與降低成本為主要的課題,本文藉由修改路由的方式來達到降低耗能的功效。目前ZigBee大部分都使用AODV(ad-hoc on-demand distance vector)路由與樹狀路由的路由方式,AODV路由方式可以達到最有效率的傳輸,但是在尋找路由時,會花費大量的封包與時間,所以本文先分析樹狀路由與AODV路由的特性,再使用樹狀拓璞,並將樹狀路由與AODV路由作結合,來達到降低封包量的功效。

Top

 

高世宇-以半擬陣為基礎架構之k-way分類器應用於高光譜遙測影像(2009)

摘要:
本篇論文中,我們提出一個新的監督式分類方法,為了監督多光譜遙測影像,稱為k-way Semi-Matroid (KWSM) 分類器。KWSM是以k-way tree為架構,是一個有組織系統的樹,每一個節點均由正、負樣本的集合所組成的,利用正、負樣本我們可以計算出每類別所佔之百分比。換而言之,所佔之百分比是特定的類別與其他類別的比。KWSM是使用一個不平衡的k路樹狀結構,其中每個葉節點(leaf node) 均符合半擬陣的架構代表了不同大小的區塊及所有類別的分佈。k路樹是建構在任一特定的類別上,根據不同類別間的統計機率來判定是否停止切割產生新的子空間和哪一個類別歸屬於該子空間。KWSM學習模型透過不同類別的正、負樣本,就分類的正確率而言,KWSM優於傳統的分類器。為了計算我們所提出的KWSM效能,我們是利用Pacrim
II的計畫MODIS/ASTER airborne simulator (MASTER)和airborne synthetic aperture radar (AIRSAR)的影像作為地表分類的依據。由實驗結果可知,KWSM的結果是我們所期待的。

Top

 

陳致嘉-平行化基因演算法應用於超大型積體電路之平面規劃(2009)

摘要:
平面規劃是在傳統積體電路設計流程中的後端,實體設計裡所處理。平面規劃的結果直接影響晶片面積的大小,面積越小則成本降低,故平面規劃問題在積體電路設計中的重要性十分的高。

    一般而言,在解平面規劃問題通常搭配模擬退火法(Simulated Annealing, SA)來尋求較佳的解;然而隨著記憶體越來越大也越來越便宜,處理器亦邁入多核心的時代,因此解決了基因演算法(Genetic Algorithm, GA)較耗記憶體的問題,平行運算亦十分適合應用在基因演算法單一世代中染色體(Chromosome)的交配(Crossover)及突變(Mutation)運算,並且,我們使用序列對(Sequence Pair)表示法,其資料結構類似於染色體的結構,相當適合用於基因演算法的交配運算中,故我們使用基因演算法搭配序列對表示法為基礎來處理平面規劃的問題。

    為了加強搜尋解空間(Solution Space)的能力,我們引入直交實驗設計(Orthogonal Experimental Design, OED)的概念,以期在相同的世代數(Generation)中可以得到更好的解。

    此外,我們使用多核心處理器(Chip Multiprocessor, CMP)在OpenMP的環境下實驗上述的方法,其結果與傳統的循序式(Sequential)方法比較,我們可以在更快的時間內得到同樣好的解。

Top

 

陳佳輝-平行粒子尋優演算法於高光譜影像特徵抽取應用(2009)

摘要:
隨著影像衛星技術的日新月異以及普及化,高光譜影像的資料複雜度也相對的越來越高,高維度的資料且龐大的資料量會帶來費時又複雜的計算問題,且特徵值的品質也左右著分類器的好壞,因此如何有效的萃取高相關度的特徵值、降低雜訊的影響度,並且提升運算效率是相當重要的。
  本篇論文提出一套平行粒子尋優演算法(Parallel Particle Swarm Optimization, PPSO),利用PSO具有的快速收歛特性應用在降低資料維度(Reduction Dimension, RD),並結合利用空間轉換的觀念,使得PSO搜索空間能夠對應到降維的相關係數陣列(Correlation Coefficient Matrix)解空間,來解決空間型態不同的問題。在參數設定的部份,首先對於粒子尋優演算法裡自身搜尋參數採用線性遞減的方法,用來提升粒子本身在周圍區域搜尋的活動力;第二採用time-delay的方式來調整PSO內部參數全域值取決率,讓每顆粒子在其範圍內做更完整的搜尋;最後為避免粒子陷入區域性搜尋停滯狀態,加入隨機變數以更新粒子位置與速度,使得PSO能更有效的萃取高相關度的特徵值。

除此之外,為了使PPSO可以有效的逼近最佳解,並且提升整體運算效率,本篇論文結合三種平行機制[11]—「非互動式平行」、「同步交換訊息平行」、「非同步交換訊息平行」。最終由實驗結果顯示,本篇論文提出之PPSO與PSA[12]作一比較,PPSO方法可以找到接近最佳解的機率比PSA高出許多。

Top

 

唐孝威-奇異值分解與半擬陣架構為基礎的k-d樹分類應用於高光譜影像(2009)

摘要:
隨著人造衛星上感測器技術的進步,獲得的光譜資訊與日俱增,在高光譜影像(hyperspectral imagery)中包含了許多令當前問題混淆之資訊,因此如何從中萃取出有意義的資訊進而在分類時得到較佳之正確率,成為一門重要課題。

本論文分為二部份:『奇異值分解』(Singular Value Decomposition, SVD)、『半擬陣架構為基礎的k-d樹分類』(k-dimensional tree classification based on Semi-Matroid structure, KDSM)。第一部份為分類的前處理,首先將訓練樣本(training sample)奇異值分解,利用左奇異向量(Left Singular Vector, LSV)降低樣本個數(downsizing),再利用右奇異向量(Right Singular Vector, RSV)對訓練樣本及受測樣本(test sample)降低維度(dimensionality reduction)。第二部份為分類階段,先由訓練過程中,每個父節點利用被抽選之某一維度的平均值切割訓練樣本集合,將分群後的訓練樣本傳送至左子節點及右子節點,且重複此步驟並判斷終止條件建構出k-d樹。再以此樹進入測試過程,受測樣本依由上而下(top-down)的方式搜尋k-d樹節點,依照比較各節點鍵值大小為條件,將受測樣本分類。

最後實驗結果證明,對高光譜資料經由奇異值分解轉換後的維度空間,優於過去的維度抽取方法,能大幅度減少分類時所需的資料量,降低計算時間,並有效提升以半擬陣架構為基礎的k-d樹分類方法之正確率。

Top

 

廖志緯-避開障礙物直角史坦納樹建構(2009)

摘要:
繞線問題是超大型積體電路實體設計中非常重要的一部分,隨著半導體製程不斷的進步,晶片電路複雜度也與日俱增,單位面積的繞線密度也隨之大幅提升,繞線問題佔整體晶片設計效能的比例也提高了許多。所以如何有效的決定繞線路徑來解決繞線問題,是一個相當重要的研究議題。

    我們考量一個給定的平面上存在著節點以及障礙物的集合,透過直線以及橫線且可能經過額外的史坦納點的集合,連結所有的節點並避免穿越任何障礙物,建構出具有最小線長的直角史坦納樹。

    在本篇論文中,我們提出一個新的避開障礙物直角史坦納樹建構的演算法。首先經由建立Escape Graph來避開障礙物,繼而設法減少Escape Graph中不必要的座標點和邊線,並保證其最佳解仍舊存在。在Escape Graph的架構下建構出直角史坦納樹,為了減少建構過程的時間複雜度,我們使用Forest的概念來產生以各個節點為中心的最小生成樹集合,再以距離表查表的方式找出各節點之間的最短路徑,最後將所得到的最小生成樹轉換成直角史坦納樹。

Top