一種新的基礎矩陣估計算法研究

魏曉艷

摘 要：該文提出了一種新的估計基礎矩陣的魯棒算法——基于粒子群算法的最小平方中值法（PSO-LMedS）。該方法是將最小平方中值法（LMedS）與粒子群算法（PSO）相結合，將LMedS方法得到的匹配點對作為PSO的初始種群，利用粒子群算法的全局優化特性，通過不斷的尋優過程，估計得到最佳基礎矩陣，提高基礎矩陣估計精度。通過仿真實例，證明改進后的算法具有較高的魯棒性和精確性。

關鍵詞：極線幾何 基礎矩陣 粒子群算法 最小平方中值法

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1672-3791（2016）01（c）-0148-03

Abstract：This paper proposes a new robust algorithm（PSO-LMedS） for estimating fundamental matrix.This new algorithm views matching points obtained by LMedS as the initial population in PSO，then improves fundamental matrix estimation accuracy by using global optimization characteristics of PSO.Finally，it uses the new approachestimate the fundamental matrix，and the simulation results show high robustness and accuracy.

Key Words：Epipolar geometry；Fundamental matrix；PSO；LMedS

對于兩幅待匹配的圖像，極線幾何關系是可以獲得的唯一一組信息，該關系是對未定標圖像進行分析的一種基本工具。極線幾何關系可以通過一個3×3的矩陣來表示，即基礎矩陣（F陣）。對基礎矩陣的估計是三維重建問題、運動估計問題、像機標定問題、匹配和跟蹤等問題研究的基礎，因此，對其估計問題的研究已經成為人們研究的一個重要方向。該文主要針對基礎矩陣的估計問題進行研究[1-2]。

1 常用的基礎矩陣估計方法

常用的基礎矩陣估計方法有線性方法、迭代方法以及魯棒方法。在估計基礎矩陣的各種算法中，線性算法是最基本的，其實現簡單，計算速度快，其缺點是對誤匹配和噪聲比較敏感；迭代算法和魯棒算法需要線性算法為其提供好的初值，不論是迭代算法還是魯棒算法都是反復調用線性方法[3]。

常用的魯棒估計算法有M-估計法、最小平方中值法（LMedS）及隨機采樣一致方法（RANSAC）[4]。該文基于魯棒方法的思想在LMedS的基礎上進行了改進，提出了一種基于粒子群算法的最小平方中值法——PSO-LMedS，來提高基礎矩陣的估計精度。

2 一種改進的基礎矩陣估計算法研究

2.1 PSO算法

隨機初始一群粒子，每個粒子既不包括體積信息，也不包括質量信息，可以將每個粒子都看作為優化過程中的一個可行解，對于粒子的好壞，可以通過一個事先設定好的適應度函數來進行確定。優化過程中，每個粒子都將在可行解空間中進行運動，由一個速度變量決定其方向和距離。通常情況下粒子將追隨當前的最優粒子，并經過不斷的迭代搜索最后得到全局最優解。在每一次迭代過程中，粒子都將會跟蹤兩個最優值：一個是粒子本身迄今為止找到的最優解，即局部最優解；另一個是整個粒子群體到目前為止找到的最優解，即全局最優解。

其中n為所有的匹配對數目，p為子集的大小。當（其中推薦值為2.5）時，則認為該匹配對是正確的；否則就是錯誤的匹配對。

（5）將上述由最小平方中值法得到的匹配點對作為粒子群算法的初始種群，同時初始化相關參數：搜索空間的上限和下限，學習因子，收斂精度，粒子位置及速度范圍。

（6）評價每一個粒子：按照公式（2）計算粒子的適應值，如果優于當前最優解，則將其設置為該粒子的位置且更新最優解，更新粒子序號。

（7）按照式（1）更新每個粒子的位置及速度，并做越限處理。

（8）按照公式（2）重新計算各粒子的適應值，將每個粒子的當前位置的適應值和當前最好位置的適應值相比較，如果當前位置適應值優于最優解的適應值，則進行更新。

（9）是否滿足終止條件，該文中選取最大迭代次數，如果達到最大迭代次數時，則轉到步驟（10），否則轉入步驟（7），迭代次數增加一次。

（10）輸出結果，即最佳基礎矩陣F。

3 仿真實驗

為了驗證基于粒子群算法的最小平方中值法估計基礎矩陣的有效性及優越性，下列將八點算法（LMedSeig）、隨機采樣一致方法（RANSAC）及該文所提出的改進的基礎矩陣估計算法（PSO-LMedS）進行性能的比較。用兩匹配點偏離對應極線的距離（對極距離）的平均值及方差來評價其性能。首先選取圖1中的圖像進行圖像特征點的檢測與匹配，得到初始的匹配點對。分別采用8點算法、RANSAC算法以及PSO-LMedS，利用圖1 c圖中得到的初始匹配點對，進行基礎矩陣的估計。采用公式（2）來計算所有有效匹配點對的對極距離d，采用對極距離的均值（Mean）及方差值（Stdev）來表征估計得到的基礎矩陣的精確性。

圖2中描述了沒有加入誤匹配點時3種不同算法的性能比較結果，其中黑色直方圖表示對極距離的平均值，白色直方圖表示對極距離的方差；可以看出，PSO-LMedS的均值和方差較小，較其他幾種方法的精度都高；然而在實際計算過程中，PSO-LMedS計算時間較長，這是因為在計算的過程中，不僅先要對outliers進行剔除，同時對利用不同的匹配點對求的基礎矩陣進行了尋優過程，以便找到最佳基礎矩陣，因此較為耗時。

圖3為加入30%的誤匹配點時的性能比較結果，由仿真結果可以看出，PSO-LMedS在計算精度方面較其它幾種算法都具有一定的優勢。

4 結語

該文將PSO與LMedS相結合，提出了一種新的基礎矩陣估計方法——PSO-LMedS。仿真結果表明：改進后的算法提高了基礎矩陣的估計精度，驗證了算法的有效性。

參考文獻

[1] 陳澤志，吳成柯，劉勇.對極幾何估計的魯棒性新算法[J].西安電子科技大學軟件學報，2000，23（6）：634-639.

[2] 胡凌山，朱齊丹.計算機視覺中基本矩陣的估計方法[J].應用科技，2005（10）：41-43.

[3] 陳杰，劉松林，宇超群.一種改進的基本矩陣魯棒估計算法[C]//《測繪通報》測繪科學前沿技術論壇摘要集.2008.

[4] 鐘慧湘.基本矩陣計算方法的研究[D].吉林大學，2005.

[5] 宋漢辰，張小義，吳玲達.一種基礎矩陣線性估計的魯棒方法[J].國防科技大學學報，2005，31（15）：178-179，185.