臺灣博碩士論文加值系統

本論文將數個需要給定分群數量的監督式Fuzzy C-Means分群演算法，評估出最適合的分群數量，以達到非監督式Fuzzy C-Means分群演算法為目的。在本論文中採用以可程式化圖形處理器為設計平台，利用高度的平行計算能力使平行模糊分群演算法能同時運算多個Fuzzy C-Means分群演算法，並利用Xie-Beni之分群評估方法，找出最佳的分群數量。此外，本論文將非監督式Fuzzy C-Means分群演算法應用於動態影像之物件偵測，找出動態影像上有移動的物件，達到動態影像可分析之結果。由實驗結果顯示，本論文所提出的系統架構能夠快速且並有效地的將非監督式Fuzzy C-Means分群演算法應用於序列影像的移動偵測(Motion Detection)

1緒論 --------------------------------------------------------------1
1.1 研究背景 --------------------------------------------------------1
1.1.1 Fuzzy c-means -----------------------------------------------1
1.1.2 General-purpose computing on graphics processing units ------2
1.2 研究動機與目的 --------------------------------------------------2
1.3 論文架構 -------------------------------------------------------4
2 文獻探討 ---------------------------------------------------------5
2.1 移動估計 -------------------------------------------------------5
2.1.1 全域搜尋演算法 ------------------------------------------------6
2.1.2 快速搜尋演算法 ------------------------------------------------6
2.2 資料分群演算法 --------------------------------------------------7
2.3 分群效果評估 ----------------------------------------------------8
2.4 可程式化圖形處理器 -----------------------------------------------8
2.4.1 NVIDIA - Compute Unified Device Architecture, CUDA ---------8
2.4.2 AMD - Stream -----------------------------------------------9
3 演算方法 --------------------------------------------------------10
3.1 演算方法 ------------------------------------------------------10
3.1.1 演算方法步驟 -------------------------------------------------10
3.1.2 移動估計 ----------------------------------------------------12
3.1.3 Fuzzy C-Means分群 ------------------------------------------15
4 實現平行計算之系統架構 --------------------------------------------21
4.1 簡介 ---------------------------------------------------------21
4.2 移動估計單元 --------------------------------------------------23
4.3 Fuzzy C-Means分群演算法 ---------------------------------------25
5 實驗結果與數據探討 -----------------------------------------------30
5.1 開發平台及實驗環境介紹 ------------------------------------------30
5.2 實驗數據的呈現與討論 --------------------------------------------32
5.2.1 可程式化圖形處理器與中央處理器效能比較 ---------------------------33
5.2.2 移動偵測效果呈現與驗證 ----------------------------------------37
6 結論 -----------------------------------------------------------45
參考著作 ----------------------------------------------------------46

[1] http://ati.amd.com/technology/streamcomputing/index.html
[2] http://developer.nvidia.com/object/cuda.html
[3] http://www.amd.com
[4] http://www.nvidia.com
[5] ATI Radeon 9500/9600/9700/9800 OpenGL Programming and ptimization Guide 2003.
[6] A. Bensaid, L. Hall, J. Bezdek, L. Clarke, M. Silbiger, J. Arrington, and R. Murtagh.
Validity-guided (re)clustering with applications to image segmentation. IEEE Transactions
on Fuzzy Systems, 4(2):112 –123, may 1996.
[7] H. C. Bergmann. Displacement estimation based on the correlation of image segments.
IRE Conf. Electron. Image Processing, 1982.
[8] J. Bezdek. Numerical taxonomy with fuzzy sets. Journal of Mathematical Biology,
1:57–71, 1974. 10.1007/BF02339490.
[9] J. Bezdek and N. Pal. Some new indexes of cluster validity. IEEE Transactions on
Systems, Man, and Cybernetics, Part B: Cybernetics, 28(3):301 –315, jun 1998.
[10] J. C. Bezdek. Cluster validity with fuzzy sets. Journal of Cybernetics, 3(3):58–73,
1973.
[11] J. C. Bezdek, J. Keller, R. Krisnapuram, and N. R. Pal. Fuzzy Models and Algorithms
for Pattern Recognition and Image Processing (The Handbooks of Fuzzy
Sets). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
[12] C. Chinrungrueng and C. Sequin. Optimal adaptive k-means algorithm with dynamic
adjustment of learning rate. IEEE Transactions on Neural Networks, 6(1):157
–169, jan 1995.
[13] C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297,
1995. 10.1007/BF00994018.
[14] Y. Fukuyama and M. Sugeno. A new method of choosing the number of clusters for
fuzzy c-means method. 1989.
[15] A. Jain. Image data compression: A review. Proceedings of the IEEE, 69(3):349 –
389, march 1981.
[12] C. Chinrungrueng and C. Sequin. Optimal adaptive k-means algorithm with dynamic
adjustment of learning rate. IEEE Transactions on Neural Networks, 6(1):157
–169, jan 1995.
[13] C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297,
1995. 10.1007/BF00994018.
[14] Y. Fukuyama and M. Sugeno. A new method of choosing the number of clusters for
fuzzy c-means method. 1989.
[15] A. Jain. Image data compression: A review. Proceedings of the IEEE, 69(3):349 –
389, march 1981.
[16] X. Jing and L.-P. Chau. An efficient three-step search algorithm for block motion
estimation. IEEE Transactions on Multimedia, 6(3):435 – 438, june 2004.
[17] H. Kaneko and T. Ishiguro. Digital television transmission using bandwidth compression
techniques. IEEE Communications Magazine, 18(4):14 –22, july 1980.
[18] J. Kolen and T. Hutcheson. Reducing the time complexity of the fuzzy c-means
algorithm. IEEE Transactions on Fuzzy Systems, 10(2):263 –267, apr 2002.
[19] K. Krishna and M. Narasimha Murty. Genetic k-means algorithm. IEEE Transactions
on Systems, Man, and Cybernetics, Part B: Cybernetics, 29(3):433 –439, jun
1999.
[20] S. Kwon. Cluster validity index for fuzzy clustering. Electronics Letters,
34(22):2176 –2177, oct 1998.
[21] D. Lee, S. Baek, and K. Sung. Modified k-means algorithm for vector quantizer
design. IEEE Signal Processing Letters, 4(1):2 –4, jan 1997.
[22] R. Li, B. Zeng, and M. Liou. A new three-step search algorithm for block motion
estimation. IEEE Transactions on Circuits and Systems for Video Technology,
4(4):438 –442, aug 1994.
[23] E. Lindholm, J. Nickolls, S. Oberman, and J. Montrym. Nvidia tesla: A unified
graphics and computing architecture. IEEE Micro, 28(2):39 ?5, march-april 2008.
[24] J. L徨zaro, J. Arias, J. L. Mart渾n, C. Cuadrado, and A. Astarloa. Implementation of a
modified fuzzy c-means clustering algorithm for real-time applications. Micropro-cessors and Microsystems, 29(8-9):375 – 380, 2005. Special Issue on FPGAs: Case
Studies in Computer Vision and Image Processing.
[25] D. Manocha. General-purpose computations using graphics processors. Computer,
38(8):85 – 88, aug. 2005.
[26] A. Netravali and J. Limb. Picture coding: A review. Proceedings of the IEEE,
68(3):366 – 406, march 1980.
[27] C. Olaru and L. Wehenkel. Data mining. IEEE Computer Applications in Power,
12(3):19 –25, jul 1999.
[28] J. Owens, M. Houston, D. Luebke, S. Green, J. Stone, and J. Phillips. Gpu computing.
Proceedings of the IEEE, 96(5):879 –899, may 2008.
[29] N. Pal and J. Bezdek. On cluster validity for the fuzzy c-means model. IEEE
Transactions on Fuzzy Systems, 3(3):370 –379, aug 1995.
[30] L.-M. Po and W.-C. Ma. A novel four-step search algorithm for fast block motion
estimation. IEEE Transactions on Circuits and Systems for Video Technology,
6(3):313 –317, jun 1996.
[31] M. Sarkar and B. Yegnanarayana. A clustering algorithm using evolutionary programming.
In IEEE International Conference on Neural Networks, 1996., volume 2,
pages 1162 –1167 vol.2, jun 1996.
[32] J. Suykens and J. Vandewalle. Least squares support vector machine classifiers.
Neural Processing Letters, 9:293–300, 1999. 10.1023/A:1018628609742.
[33] S. Vassiliadis, E. Hakkennes, J. Wong, and G. Pechanek. The sum-absolutedifference
motion estimation accelerator. In Euromicro Conference, 1998. Proceedings.
24th, volume 2, pages 559 –566 vol.2, aug 1998.
[34] X. Xie and G. Beni. A validity measure for fuzzy clustering. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 13(8):841 –847, aug 1991.
[35] S. Zhu and K.-K. Ma. A new diamond search algorithm for fast block-matching
motion estimation. IEEE Transactions on Image Processing, 9(2):287 –290, feb
2000.50