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

Singular Value Decomposition and k-d Tree Classification based on Semi-Matroid Structure applied to Hyperspectral Imagery

唐孝威(Hsiao-Wei Tang)

指導教授 ： 張陽郎 ； 方志鵬

國立臺北科技大學/電資學院/電機工程系研究所/碩士(2009年)

摘要

隨著人造衛星上感測器技術的進步，獲得的光譜資訊與日俱增，在高光譜影像(hyperspectral imagery)中包含了許多令當前問題混淆之資訊，因此如何從中萃取出有意義的資訊進而在分類時得到較佳之正確率，成為一門重要課題。
本論文分為二部份：『奇異值分解』(Singular Value Decomposition, SVD)、『半擬陣架構為基礎的k-d 樹分類』(k-dimensional tree classification based onSemi-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 樹分類方法之正確率。

關鍵字

高光譜影像 ； 降低樣本個數 ； 降低維度 ； 奇異值分解 ； 左奇異向量 ； 右奇異向量 ； 半擬陣架構 ； k-d 樹 ； 由上而下

並列摘要

With the advancement of remote sensing in satellites, the spectral information isincreasing day by day. Hyperspectral images contain a lot of data that is not applicableto the current considerated problem. So how to extract useful information and then toget better accuracy rate in classification becomes an important issue.
This thesis is divided into two parts: Singular Value Decomposition (SVD), andk-dimensional tree classification based on Semi-Matroid structure (KDSM). First part ispre-processing of classification. In this part, we use Left Singular Vector (LSV) to downtraining sample size by SVD and then use the Right Singular Vector (RSV) to reducedimensions of training and testing samples. The second part is KDSM classification.During the training stage, every parent node divides training sample set by using themean of the extracted dimension and then setting classified training samples to left andright child nodes. By repeating this step and judging the termination condition, we canconstruct the k-d tree. Then use this tree into the testing stage. Test samples search thenodes in k-d tree by top-down. According to comparing the key value of each node, wecan classify test samples.
Experiment results show that the space of hyperspectral image after SVD is betterthan the traditional methods of dimension selection. It can extremely reduce theinformation during classifying, decrease execution time and increase accuracy rate of KDSM classification.

並列關鍵字

hyperspectral imagery ； downsizing ； dimensionality reduction ； Singular Value Decomposition ； Left Singular Vector ； Right Singular Vector ； Semi-Matroid ； k-d tree ； top-down

參考文獻

[21] 林鈞傑，一個對於高光譜影像的二維模擬退火波段選擇方法，碩士論文，國立台北科技大學，台北，2007年6月。.

[1] Smith, G. M. and E. J. Milton,1999. The Use of the Empirical Line Method to Calibrate Remotely Sensed Data to Reflectance, Int. J. Remote Sensing, 1999, vol. 20, no.13, 2653-2662.

[3] Vapnik, V. (1995.) The Nature of Statistical Learning Theory. New York, NY:Springer-Verlag.

[4] Hughes, G.F.(1968). On the mean accuracy of statistical pattern recognition. IEEE Trans. Inform. Theory, vol. 14, pp. 55-63, jan.

[6] V. Cerny, " Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, " Journal of Optimization Theory and Applications, vol. 45, no.1, 1985, pp. 41-51.