臺灣博碩士論文加值系統

基礎矩陣在影像處理是非常重要的參數，舉凡不同影像間對應點之計算、座標系統轉換、乃至重建物體三維模型等問題，都有賴於基礎矩陣之精確與否。本論文中，我們提出一個機制，透過粒子群最佳化的觀念來求取基礎矩陣，我們的方法不但能提高基礎矩陣的精確度，同時能降低計算成本。

我們從多視角影像出發，以SIFT取得大量對應點資料後，從中選取8點進行粒子群最佳化。取樣時，我們透過分群與隨機挑選以避免選取共平面之點。然後利用最小平方中值表來估算初始評估值，並遵循粒子群最佳化演算法，以最小疊代次數為收斂準則，計算出最佳之基礎矩陣。

實作中我們以不同的物體模型為標的，以粒子群最佳化與最小平方中值法兩者結果比較。實驗結果顯示，疊代次數相同的實驗，粒子群最佳化演算法估測基礎矩陣所需的時間，約為最小平方中值法來估測所需時間的八分之一，同時粒子群最佳化演算法估測出來的基礎矩陣之平均誤差值也優於最小平方中值法所估測出來的結果。

Fundamental matrix is a very important parameter in image processing. In corresponding point determination, coordinate system conversion, as well as three-dimensional model reconstruction, etc., fundamental matrix always plays an important role. Hence, obtaining an accurate fundamental matrix becomes one of the most important issues in image processing.

In this paper, we present a mechanism that uses the concept of Particle Swarm Optimization (PSO) to find fundamental matrix. Our approach not only can improve the accuracy of the fundamental matrix but also can reduce computation costs.

After using Scale-Invariant Feature Transform (SIFT) to get a large number of corresponding points from the multi-view images, we choose a set of eight corresponding points, based on the image resolutions, grouping principles, together with random sampling, as our initial starting points for PSO. Least Median of Squares (LMedS) is used in estimating the initial fitness value as well as the minimal number of iterations in PSO. The fundamental matrix can then be computed using the PSO algorithm.


We use different objects to illustrate our mechanism and compare the results obtained by using PSO and using LMedS. The experimental results show that, if we use the same number of iterations in the experiments, the fundamental matrix computed by the PSO method have better estimated average error than that computed by the LMedS method. Also, the PSO method takes about one-eighth of the time required for the LMedS method in these computations.

第一章 緒論 1
1.1前言 1
1.2研究背景與動機 1
1.3問題描述 3
1.4論文貢獻 4
1.5論文章節架構 4
第二章 文獻回顧 5
2.1粒子群最佳化演算法 5
2.2估測基礎矩陣 7
第三章 背景技術 10
3.1粒子群最佳化演算法流程 10
3.2隨機取樣 14
3.3最小平方法 15
3.4最小平方中值法 17
3.5估測基礎矩陣流程 18
第四章 以粒子群最佳化演算法估測基礎矩陣 20
4.1模擬基礎實驗 20
4.1.1平面中粒子群最佳化 20
4.1.2圓錐近似中粒子群最佳化 24
4.2研究方法與流程 28
4.2.1系統架構 28
4.2.2評估基礎矩陣 31
第五章 實驗結果 33
5.1平面中粒子群最佳化實驗結果 33
5.1.1速度未經過正規化 34
5.1.2速度經過正規化 46
5.1.3討論與分析 55
5.2圓錐近似中粒子群最佳化實驗結果 55
5.2.1限制固定疊代次數 55
5.2.2對Gbest收斂 57
5.2.3限制fitness值和對Gbest收斂 64
5.2.4討論與分析 64
5.3以粒子群最佳化估測基礎矩陣實驗結果 65
5.3.1第一組實驗(3DMAX)資料 65
5.3.2第二組實驗(LIDAR)資料 69
5.3.3討論與分析 73
第六章 結論 74
6.1結論 74
6.2未來工作 75
參考文獻 76

[1]. 尹邦嚴，柳依旻，江元傑，黃冠哲，陳映良，“粒子族群最佳化的視覺化及開發工具”，2005銘傳大學國際學術研討會論文集，桃園，民國94年11月。
[2]. 李宜靜，蔡賢亮，“以粒子群體最佳化為基礎之中文文字細線化演算法”，2009資訊技術應用及管理研討會論文集，高雄，民國98年6月。
[3]. 鄒慎財，“強健式估測基礎矩陣之研究”，碩士論文，華梵大學資訊管理系，台北，民國94年1月。
[4]. 廖怡儂，“應用於電腦視覺強健式估測之研究”，碩士論文，華梵大學資訊管理系，台北，民國94年5月。
[5]. 蔡介元，鍾佩潔，“建立一個以PSO求解多點最佳路徑的行動地理資訊系統”，2007臺灣作業研究學會學術研討會論文集，花蓮，民國96年10月。
[6]. 蔡賢亮，溫千慧，鄭永雄，“基於粒子族群最佳化之不完全資料處理”，2006電子商務與數位生活研討會論文集，台北，民國95年2月。
[7]. 賴岳宏，“利用演化式計算做最佳化之研究”，碩士論文，華梵大學資訊管理系，台北，民國94年5月。
[8]. C. Tang, Y. Wu, and Y. Lai, “Fundamental Matrix Estimation using Evolutionary Algorithms with Multi-Objective Functions”, Journal of Information Science and Engineering , 2008, pp.785-800.
[9]. F. Frenzel, “Genetic algorithms,” Potentials, IEEE , vol.12, no.3, pp.21-24, Oct 1993.
[10]. L. George. 2004. Artificial Intelligence: Structures and Strategies for Complex Problem Solving (5th Edition). Pearson Addison Wesley.
[11]. M. Lhuillier, Q. Long, “Match propagation for image-based modeling and rendering,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol.24, no.8, pp. 1140- 1146, Aug 2002.
[12]. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
[13]. J. Kennedy, R. Eberhart, “Particle swarm optimization,” Neural Networks, 1995. Proceedings., IEEE International Conference on, vol.4, no., pp.1942-1948 vol.4, Nov/Dec 1995.
[14]. J. Phillip, “Taguchi Techniques for Quality Engineering”, McGraw-Hill Professional, 2nd edition, 1995.
[15]. A. Ratnaweera, K. Halgamuge, C.Watson, “Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients,” Evolutionary Computation, IEEE Transactions on, vol.8, no.3, pp. 240- 255, June 2004.
[16]. H. Richard, Z. Andrew. 2003. Multiple View Geometry in Computer Vision (2 ed.). Cambridge University Press, New York, NY, USA.
[17]. H. Thomas, S. Clifford, L. Ronald, and E. Charles. 2001. Introduction to Algorithms (2nd ed.). McGraw-Hill Higher Education.
[18]. A. Xavier, S. Joaquim, “Overall view regarding fundamental matrix estimation” Image and Vision Computing, vol. 21, no. 2, pp. 205-220, 2003
[19]. Z. Zhengyou, “Parameter Estimation Technique: A Tutorial with Application to Conic Fitting”, Image and Vision Computing, vol. 15, no. 1, pp. 59-76, 1997.
[20]. Ground Truth data, http://cvlab.epfl.ch/~strecha/multiview/denseMVS.html