臺灣博碩士論文加值系統

由於人造衛星感測器的硬體技術持續的進步，所以能從中獲得的光譜資訊也飛快增加，但是高維度及大量的資料量卻會為處理資料時帶來相當大的負荷，因此如何降低在處理資料時所需耗費的大量時間已成為一個重要的議題。
本篇論文分為二部份：第一部分為以傳統最近鄰分類(Nearest Neighbor Rule，NNR)為基礎，透過使用由NVIDIA所提出的計算統一架構(Compute Unified Device Architecture，CUDA)來對最近鄰分類演算法進行以測試樣本為基礎之平行化；第二部分為以KDSM(k-dimensional tree classification based on Semi-Matroid structure) 演算法為基礎，提出以節點(Node)為基礎的平行訓練(Training)方法，以KDSM為二元分類樹的架構與分割超平面後其分割區域間再也沒交集的特性，透過OpenMP來控制多核CPU去各自對分割後的區域再進行劃分，而分類階段則是使用CUDA以測試樣本為基礎進行平行化。最後並透過MPI(Message Passing Interface)及OpenMP(Open Multi-Processing)來控制叢集電腦及多核心中央處理器(Central Processing Unit,CPU)去使用各電腦所擁有的兩張圖形顯示卡，進而平均分散資料量來達到大量降低分類時間之需求
最後實驗結果證明，分類演算法透過平行化後確實能達到大量降低處理時間之需求。

Because the progress with lasting hardware technology of the detecting device of the satellite, so the spectrum information we can get also increase quickly. A large number of materials amount will bring sizable load punish materials, so how to reduce a large amount of time while dealing with the materials have already become an important topic.

This thesis is divided into two components:Part one is based on Classify NNR(Nearest Neighbor Rule).B y using unify calculation structure (Compute Unified Device Architecture, CUDA) which is put forward by NVIDIA, it executes parallel algorithm for NNR based on testing samples. Part two contains KDSM (k-dimensional tree classification based on Semi-Matroid structure).It is proposed with the parallel training which is based on node.The structure of KDSM is a binary categorized tree and it will be never mixed after cutting apart with ultra level.OpenMP(Open Multi-Processing) controls multi-core CPU to divide the area for each one after cutting apart. In categorized stage, we use CUDA to parallel based on testing samples. Finally, by passing MPI(Message Passing Interface) and OpenMP,we control and gather together with cluster computer and nulti-core CPU(Central Processing Unit, CPU) to use two graphic display card with both. It helps us to disperse the materials amount on average, in order to reduce the cost of categorized time.

The experimental results prove that we can really reduce the time demand of dealing by using classified algorithm through melting paralleled process.

第一章　緒論 1
1.1 研究背景介紹 1
1.2 研究動機與目的 2
1.3 論文內容大綱 2
第二章　相關文獻回顧 3
2.1 遙測影像簡介 3
2.2 平行計算 4
2.2.1 平行計算簡介 4
2.2.2 MPI簡介與架構 5
2.2.3 OpenMP簡介與架構 6
2.2.4 CUDA簡介與架構 8
2.3 分類器 13
2.3.1 最近鄰法分類器 13
2.3.2 KDSM分類器 14
第三章　研究方法 17
3.1 概述 17
3.2 平行最近鄰分類法 17
3.3 平行KDSM分類法 19
3.3.1 平行訓練階段 19
3.3.2 平行分類階段 23
3.4 混合平行計算模型架構 25
第四章　實驗結果 27
4.1實驗設備 28
4.2實驗結果 28
4.2.1平行分類階段 28
4.2.1.1樣本數量對效能的影響 28
4.2.1.2波段數量對效能的影響 33
4.2.1.3分類器效能評比 35
4.2.2平行訓練階段 36
第五章　結論與未來研究方向 38
5.1 結論 38
5.2 未來研究方向 38
參考文獻 39

書籍
[1]Sergios Theodoridis and Konstantinos Koutrounbas,Pattern Recognition,third edition, London: Academic Press, 2006.
[2]Peter Pacheco,Parallel Programming with MPI, Morgan Kaufmann Publishers,San Francisco, California,1997.

期刊論文
[3]魏子軒，「高光譜影像分類辨識方法」，儀科中心簡訊，第18期，2007，第14-15頁。
[4]徐百輝，「大地的辨識密碼-高光譜影像」，科學發展，第416期，2007，第13-19頁。
[5]Cover, T. M. and Hart, P. E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, vol. 13, 1, pp.21-27.

學位論文
[6]Xuechuan Wang, Feature Extraction and Dimensionality Reduction in Pattern Recognition and Their Application in Speech Recognition, Ph.D. Thesis, Griffith University, Australia, 2002.
[7]陳建文，高光譜影像雜訊模式估計，碩士論文，國立中央大學資訊工程研究所，桃園，民國95年。
[8]陳靖怡，一個對於高光譜與合成孔徑雷達遙測影像資料融合的模擬退火特徵齊一化波段選取方法，碩士論文，國立台北科技大學，台北，民國97年。
[9]陳武勇，使用圖形處理器於B-Spline有限元素分析，碩士論文，國立成功大學機械工程研究所，台南，民國96年。
[10]唐孝威，奇異值分解與半擬陣架構為基礎的k-d樹分類應用於高光譜影像，碩士論文，國立台北科技大學，台北，民國98年。
[11]Yang-Lang Chang, A Novel Approach to Hyperspectral Image Classification, Ph.D. Thesis, Chungli, Taoyuan, Taiwan , National Central University, May 2003.

其他
[12]http://en.wikipedia.org/wiki/Spectrum
[13]http://www.mpi-forum.org/docs/mpi-20-html/node2.htm#Node2
[14]http://en.wikipedia.org/wiki/Openmp
[15]https://computing.llnl.gov/tutorials/openMP/
[16]http://zh.wikipedia.org/w/index.php?title=OpenMP&variant=zh-tw
[17]NVIDIA, “CUDA Programming Guide v3.0”,2010.