平行粒子群優法應用於高維度影像特徵抽取

Particle Swarm Optimization Band Selection Algorithm for High Dimensional Images Based on GPU Parallel Computing

王宏原(Wei-Ren Wang)

指導教授 ： 張陽郎

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

摘要

隨著衛星影像的普及，高維度影像的龐大資料量會帶來費時的複雜計算問題，且特徵值的品質也左右著分類器，因此如何萃取高相關度的特徵值、降低雜訊，並且提升運算效率是相當重要的。
　　傳統粒子群優法(Particle Swarm Optimization, PSO)在搜尋最佳解時，初期收斂速度較快，到了後期卻容易因為粒子逐漸往搜尋空間的最佳解靠近，導致無法完整搜尋整個粒子空間因而陷入區域最佳解。
本文提出平行計算粒子群優演算法，有效的針對整個粒子空間做最完整的搜尋。本論文主要著重在三個部份，首先利用PSO演算法具有的快速收歛特性應用在降低資料維度，並利用排序觀念來進行空間轉換，使得PSO演算法的向量空間能對應到降維的相關係數陣列(Correlation Coefficient Matrix)解空間，來解決空間型態不同的問題；其次是重新設定PSO演算法參數，並使用變異數概念在相關係數陣列做特徵選取方式，使得PSO演算法能更有效的萃取高相關度的特徵值；最後採用CUDA（Compute Unified Device Architecture）技術應用於PSO演算法，有效提升整體運算速度並且更有機會逼近最佳解。

關鍵字

粒子群優法 ； 相關陣列 ； 降維 ； 平行運算 ； CUDA

並列摘要

With the popularization of satellite image, a large amount of materials with high demension would cause the following problems, ie time consumption and complex calculation. The quality of characteristic value also influences classifiers. Therefore, how to extract the characteristic value with better correlation, to reduce noise, and to raise the efficiency of computation are very important.
When Particle Swarm Optimization (PSO) searches the optimization, the rate of convergence in the initial stage is faster, but at the later stage, it would be easier to get a local optimization without searching the whole particle space, because the particle is inclining towards the optimization of the searched space. This dissertation aruges that we use Compute Unified Device Architecture (CUDA) to calculate PSO algorithm, and it is efficient to search completely for the whole search space.
This dissertation focuses on three steps. Firstly, we apply the characteristic of quick convergence of PSO to the Reduction Dimension (RD), and we execute space conversion which makes the searched space of PSO to reflectto the solution space of Correlation Coefficient Matrix. It will solve the problem for different data type. Then, we also use the concept of barycenter to choose characteristic for Correlation Coefficient Matrix, which will be more efficient to extract the characteristic value with high correlation. Finally, we apply CUDA to PSO algorithm which has more opportunity to approach the optimization than SA algotithm.
With the experimental results show, we apply CUDA to PSO algorithm which has more opportunity to approach the optimal solution than SA algotithm.

並列關鍵字

CUDA ； PSO ； Remote Sensing ； CM ； RD ； Parallel computing

參考文獻

[9] 劉進男，一個對於高光譜影像資料融合平行的模擬退火波段選擇及特徵抽取方法，碩士論文，國立台北科技大學，台北，民國96年

[10] 陳佳輝，平行粒子尋優演算法於高光譜影像特徵抽取應用，碩士論文，國立台北科技大學，台北，民國98年

[1] Yang-Lang Chang, Chin-Chuan Han, Kuo-Chin Fan, K.S. Chen, Chia-Tang Chen and Jeng-Horng Chang, "Greedy Modular Eigenspaces and Positive Boolean Function for Supervised Hyperspectral Image Classification" Optical Engineering, Vol. 42, Issue 9, 2003, pp. 2576-2587.

[2] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing" Science 220, No. 4598, 1983, pp. 671-680.

[4] Wei Pang, Kang-Ping Wang, Chun-Guang Zhou, "Modified Particle Swarm Optimization Based On Space Transformation For Solving Traveling Salesman Problem" 2004, pp. 2342-2346.