一種基于改進擬仿射變換的基礎矩陣估計方法*

范宜凱,劉石堅,潘正祥,2

(1.福建工程學院人工智能研究所，福建 福州 350118;2.山東科技大學計算機科學與工程學院，山東 青島 266590)

1 引言

基礎矩陣估計是利用運動中恢復結構(Structure from Motion)[1,2]、多視角立體視覺(Multi-view Stereo)[3,4]等方法獲取空間目標信息的關鍵問題，被廣泛應用于基于圖像的建模(Image-based Modeling)[5,6]、即時定位與地圖構建(Simultaneous Localization and Mapping)[7,8]等計算機視覺領域前沿熱點研究中。

從一組不同角度、不同距離拍攝的同一場景所得的二維序列圖像中還原出目標對象的三維空間信息，其理論基礎是彼此之間存在的對極幾何約束[9,10]。基礎矩陣在對極約束下描述了相關圖像中匹配特征點對之間的數(shù)學關系。相關研究最早可見于攝像機自標定[11,12]等算法中。

令pi=(xi,yi,1)T和p′i=(x′i,y′i,1)T分別是第1幅圖像I和第2幅圖像I′中匹配的第i(1≤i≤n，n是特征點的對數(shù))個特征點的齊次坐標。式(1)描述了這些特征點之間的對極約束關系。

p′iTFpi=0

(1)

其中，F(xiàn)即基礎矩陣(Fundamental Matrix)。

F的估計是一個方程組超定問題，在數(shù)學上可通過給定的8對特征點進行求解。鑒于誤差的普遍存在，可將n對特征點分成2類，即與其真實值相比誤差較小的內點和誤差較大的外點。那么，要得到較為準確的估計結果，關鍵在于8對特征點的選取方法。稱由8對內點組成的集合為最小內點子集，每組最小內點子集可確定一個基礎矩陣估計模型。本文提出一種基于改進擬仿射變換的基礎矩陣估計方法，其核心思想在于：基礎矩陣估計模型對所有特征點的擬合能力越強，所選取的最小內點子集越好。

準確性和效率是衡量基礎矩陣估計算法的主要指標。當準確性不夠時，往往需要在后期花費高昂的計算代價對其進行校正[13]。效率低則會影響系統(tǒng)運行的實時性。針對上述問題，本文將智能算法QUATRE(QUasi-Affine TRansformation Evolutionary)[14]引入基礎矩陣的估計問題，主要貢獻包括：

(1)提出一種基于特定“基因-染色體”模式的種群協(xié)作方法，用于基礎矩陣估算。具體來說，與最小內點子集由8對特征點組成相對應，本文提出的種群協(xié)作方法將匹配的特征點對看作基因，由8個基因組成1條染色體，通過這種特定的種群協(xié)作方式估計基礎矩陣。

(2)對原有QUATRE算法進行改進，重新定義齊次坐標系所表示的離散解空間中的種群初始化、變異和交叉等操作，使得利用QUATRE 算法框架解決基礎矩陣估算問題成為可能。

(3)提出一種基于置信度的迭代次數(shù)確定方式，用于算法加速。與QUATRE算法采用固定迭代次數(shù)尋優(yōu)求解不同，本文提出的迭代次數(shù)確定方式基于給定的置信度實時計算終止條件，提升運行效率。

2 相關工作

2.1 基礎矩陣估計方法

基于計算機視覺的基礎矩陣估計方法主要包括線性法、迭代法和魯棒法3類。

線性法的典型代表是8點算法及其相關擴展算法。8點算法由Longuet-Higgins[15]提出，使用隨機選取的8對特征點來計算基礎矩陣。該算法對噪聲和誤匹配較為敏感。在其基礎上Hartley[16]提出一種改進的8點算法，該算法首先對匹配特征點進行尺度和平移上的規(guī)則化處理，再使用8點算法計算基礎矩陣，最后進行逆規(guī)則化操作。實驗結果表明，改進的策略對噪聲有一定的抑制作用。然而，由于8對特征點仍使用隨機的方法獲得，因此無法從根本上消除外點對估計結果的影響。

迭代法主要包括M-估計法[17]和事件刪除法[18]。M-估計法的特點是采用所有特征點進行迭代，并對其中的外點和內點賦予不同的權重。例如文獻[19]中方法所引入的動態(tài)懲罰加權機制。該方法在噪聲抑制問題上有不錯的效果，但在外點較多的數(shù)據(jù)集上效果不佳。事件刪除法就該問題進行了一定的改進，但計算復雜度仍然較大。

魯棒法的代表有最小中值法LMedS(Least Median Squares)[20,21]、隨機抽樣一致性算法RANSAC(RANdom SAmple Consensus)[22,23]及其相關改進算法(如高于最小子集算法HMSS (Higher than Minimal Subset Sampling)[24]和M估計抽樣一致性算法MSAC(M-estimator Sample Consensus)[25])等。其中，LMedS算法比較簡單，對噪聲和誤匹配比較敏感。許金山等人[26]在LMedS的基礎上提出一種單應性矩陣自適應方法，以剔除外點并減少迭代次數(shù)。RANSAC算法的核心思想在于使用特征點到極線的距離作為依據(jù)，對大量的特征點子集進行測試，從中找到最優(yōu)的結果，是目前主流的基礎矩陣估計方法之一。但是，RANSAC算法需要大量隨機初始化最小子集，針對該問題HMSS算法使用一種高于最小子集的抽樣算法來加速最優(yōu)內點子集的尋找。然而，HMSS算法無法明確算法準確性與所使用內點子集規(guī)模間的關系。針對RANSAC結果的優(yōu)劣性依賴于閾值選取的問題，MSAC算法引入損失函數(shù)予以解決，但該算法收斂速度有待提高。

由于進化算法具有在解空間中智能尋優(yōu)的特點，本文方法采用改進的QUATRE算法[14]解決基礎矩陣估計問題。與線性法相比，可以有效剔除由噪聲和誤匹配產生的外點干擾。相對迭代法來說，由于應用了粒子群協(xié)作的方式，能快速匯聚到全局最優(yōu)解。與魯棒法相比，能有效減少抽取子集的數(shù)量。下面就QUATRE算法的基本概念進行闡述。

2.2 QUATRE算法

QUATRE是一種粒子群進化算法，由Meng等人[14]提出，QUATRE算法種群進化的核心思想如式(2)和式(3)所示：

B=Xgbest+c*(Xr1-Xr2)

(2)

(3)

(4)

上述進化方法從本質上來說是一種特定的尋優(yōu)求解策略，從種群進化的角度來理解是一種包含變異、交叉操作在內的種群演化過程，因此B和M也可分別稱為變異矩陣和交叉矩陣。

基礎矩陣估計問題可看作從給定有限匹配特征點對空間中選取8對內點的尋優(yōu)問題，問題空間是離散的，而原始QUATRE尋優(yōu)算法是定義在連續(xù)域上的，因此，需要對上述尋優(yōu)策略進行相應的改進，才能將其應用于基礎矩陣估計問題求解。

3 本文方法

本節(jié)主要介紹基于改進擬仿射變換的基礎矩陣估計方法。具體來說，本文方法用匹配的特征點對組建種群，結合粒子群的尋優(yōu)能力和QUATRE算法解決組合問題的優(yōu)勢來估計基礎矩陣，基本流程如圖1所示。以匹配的特征點對作為輸入，首先基于特定的“基因-染色體”模式對第1代種群進行初始化。然后基于內點率對染色體進行排序，并計算迭代終止條件(最大迭代次數(shù)GEN)。當終止條件滿足時，方法結束并輸出對應的基礎矩陣估計值；否則，依次通過變異、交叉和選擇操作迭代式地實現(xiàn)種群的進化。

Figure 1 Workflow of the proposed method圖1 方法流程圖

3.1 初始化

與QUATRE算法在連續(xù)坐標空間中生成指定數(shù)量具有隨機坐標的粒子群初始化方法不同，在基礎矩陣估計中，候選特征點是已知的，且通常使用齊次坐標表示，以簡化運算。另外，由于8對特征點可確定一個基礎矩陣的估計模型，因此本文方法將匹配特征點對的齊次坐標作為基因，使用8個基因組成一條染色體的方式初始化種群。

具體來說，首先使用特定的特征點識別算法(例如SURF(Speeded Up Robust Features)[27])獲得2幅圖像中的N對匹配特征點，然后按照如式(5)所示的方式將其表示為N×2矩陣A:

(5)

其中,pi,1=(xi,1,yi,1,1)和pi,2=(xi,2,yi,2,1)(1≤i≤N)分別是第i對特征點的2個齊次坐標。

(6)

其中，xu,v=(p(u-1)×8+v,1,p(u-1)×8+v,2)(1≤u≤NP,1≤v≤8),X(1)的每一行就是1條染色體。

3.2 內點率及終止條件

進化算法要求設定一種指標來衡量個體的優(yōu)劣，以便進行尋優(yōu)。本文方法使用內點率作為衡量指標。具體來說，對于任意染色體，可利用其所包含的8對特征點確定一個基礎矩陣的估計模型。通過該模型可進一步計算得到任意給定特征點到對應極線的距離d，將d小于給定閾值的特征點定義為內點。記N對特征點中，依照某染色體對應估計模型所確定的內點數(shù)目為Nin，則該染色體的內點率w可定義為w=Nin/N。根據(jù)w可對每代種群X中的所有染色體進行排序，w值最大的染色體即最優(yōu)染色體，其坐標值用Xgbest表示。

為保證算法的有窮性，QUATRE的種群進化具有固定的最大迭代次數(shù)GEN=10000×D/NP,其中NP是種群的規(guī)模，D是每個種群個體的維度。也就是說，當種群代數(shù)k增長至GEN時算法才能停止。本文方法則提出基于置信度的算法終止策略，即在滿足給定置信度要求的情況下按照式(7)求得迭代終止條件值GEN。

(7)

其中，p為預先指定的置信度(例如p=99%)，代表從特征點集中隨機選取8行均為內點的概率；wbest即Xgbest對應的內點率。如果當前種群代數(shù)k≥GEN,將結束算法，否則按照下文所述的變異、交叉和選擇操作繼續(xù)迭代進化種群。

3.3 進化策略

按照物種進化的思想，種群演化的過程存在個體的變化。通過自然選擇，優(yōu)秀的基因將被保留，不好的突變則被淘汰。對于進化算法來說，令種群當前代數(shù)為k，上述過程表現(xiàn)為依次對種群X(k)進行變異、交叉和選擇操作，以產生新一代種群X(k+1)。其中，變異操作產生突變的內容，交叉操作實現(xiàn)基因的變化，選擇操作則表示優(yōu)勝劣汰。

3.3.1 變異操作

由于染色體是由基因決定的，根據(jù)3.2節(jié)有關內點率w值越高染色體越優(yōu)秀的討論，可進一步衍生出w值越高的染色體所包含的基因越優(yōu)秀的結論。與式(2)所示QUATRE所使用的變異方法不同，本文方法將變異基因(p′i,1,p′i,2)(1≤i≤N′)定義為主要來自X(k)中排名前r位染色體中的基因，以及少量來自后N′-r位染色體中基因，其總數(shù)為N′，所組成的矩陣A′如式(8)所示：

(8)

為便于實現(xiàn)后續(xù)的交叉操作，可從A′中隨機抽取D個基因作為一條染色體，連續(xù)執(zhí)行NP次(NP為種群的規(guī)模)該操作，得到如式(9)中NP×D矩陣B所示的變異種群。

(9)

3.3.2 交叉操作

交叉操作實現(xiàn)種群的突變，將采用QUATRE所提出的類仿射變換形式進行。若當前種群X通過基因突變產生的種群記為X′，則X′中應既保留X的部分基因，也包含一些來自B中的變異基因，其實現(xiàn)方法如式(10)所示。

(10)

3.3.3 選擇操作

種群的進化取決于基因的優(yōu)勝劣汰，記k為種群X(k)的當前代數(shù)，X′(k)為變異種群，則下一代種群X(k+1)的各個染色體應選取X′(k)與X(k)中對應位置中更優(yōu)的那個，即選擇操作。其中，染色體優(yōu)劣的比較方法仍然通過基于3.2節(jié)所述的內點率的比較來實現(xiàn)。

4 實驗與結果分析

本節(jié)將通過實驗說明本文方法的準確性和高效性。實驗數(shù)據(jù)為使用小米MIX 2S手機拍攝的30個場景，共計60幅圖像(分辨率為1440×1080)。所有實驗均在一臺處理器為英特爾雙核i5(主頻2.5 GHz)、內存16 GB的筆記本電腦上運行，編程環(huán)境為Matlab R2017a。為便于展示，從30個場景中選取6個SURF[27]特征點對規(guī)模不等的典型場景，并將其編號,如表1所示。

Table 1 Information of six typical scenes of the experiment dataset表1 實驗數(shù)據(jù)中的6個典型場景信息

SA、SB和SA∩B中的點對分別在圖2中以“+”“×”和“○”表示(為便于展示，圖中僅隨機標記1/3的SURF特征點)。

Figure 2 Demonstration of the overlapping of scene A and scene B圖2 場景圖A和場景圖B的重疊度展示

4.1 有效性分析

首先，將本文方法應用于所采集的數(shù)據(jù)，對各個場景所表示的基礎矩陣進行估計，以測試方法的有效性。圖3a～圖3f分別展示了場景1～場景6的測試結果，其中2幅圖中相匹配的特征點用線段連接。每幅子圖的上部分是使用SURF[27]算法得到的結果(對應于表1第2列)，下部分是在SURF特征點對基礎上使用本文方法所得基礎矩陣估計模型所確定的所有內點(對應于表1第3列)。可見，對于不同規(guī)模的求解問題，本文方法都能夠有效剔除SURF匹配特征點對中的誤匹配點。

Figure 3 Results of applying our method to 6 typical scenes after getting rid of the outliers圖3 將本文方法應用于6個典型場景的外點剔除效果

圖3中每幅子圖的上部分為SURF算法生成的特征點對，下部分是在SURF特征點對基礎上使用本文方法所得基礎矩陣估計模型所確定的所有內點。

4.2 準確性對比及分析

接下來，為評價本文方法的準確性，將基于式(11)對極距離d開展對比實驗。

(11)

其中,B是通過評估方法得到的基礎矩陣，p和p′分別是特征點對的2個點，(*)1和(*)2分別表示向量的第1個和第2個分量。

使用平均對極距離及標準差作為衡量指標，對LMedS[20]、RANSAC[21]、MSAC[25]和本文方法開展對比實驗。具體來說，對6幅場景圖像，分別運行LMedS、RANSAC、MSAC 和本文方法各100次，然后計算相應的平均對極距離和標準差。圖4展示了各方法在場景1～場景6中的實驗結果。

Figure 4 Comparison of the average epipolar distance and their standard deviations in 6 typical scenes圖4 6個典型場景中各方法的平均 對極距離及其標準差的對比

就整體表現(xiàn)對不同方法進行橫向對比，本文方法在平均對極距離方面與MSAC和RANSAC相當，且明顯優(yōu)于LMedS;在標準差方面與LMedS和RANSAC相當，且優(yōu)于MSAC。就應用于不同場景中的縱向對比可知，本文方法在特征點數(shù)多的場景下仍表現(xiàn)出較好的準確性。

4.3 效率對比及分析

除準確性以外，還可從運行效率方面對本文方法進行評價。將對比實驗中各方法的平均運行時間記錄下來，如圖5所示。由圖5可見，本文方法的運行效率比其他方法都要好。隨求解問題規(guī)模(即特征點對數(shù)目)的增大，本文方法的運行時間略微有所增加，但整體上保持平穩(wěn)。

Figure 5 Average time consumption of each method applying to 6 typical scenes圖5 6個典型場景中的各方法平均運行時間對比

5 結束語

本文提出了一種改進擬仿射變換的基礎矩陣估計方法，結合粒子群的尋優(yōu)能力和QUATRE算法解決組合問題的優(yōu)勢來估計基礎矩陣。首先，提出一種基于特定“基因-染色體”模式的種群協(xié)作方法，用于基礎矩陣估算。其次，重新定義齊次坐標系所表示的離散解空間中的種群初始化、變異和交叉等操作，使得利用QUATRE 算法框架解決基礎矩陣估算問題成為可能。此外，提出一種基于置信度的迭代次數(shù)確定方式，用于加速本文方法。與傳統(tǒng)方法相比，本文方法能有效剔除噪聲和誤匹配所產生的外點干擾，具有快速尋優(yōu)求解等優(yōu)勢。實驗結果表明，本文方法在準確性和效率方面都優(yōu)于LMedS、RANSAC和MSAC等基礎矩陣估計方法。后續(xù)工作將對種群演化中的變異和交叉策略作進一步的優(yōu)化，以進一步提升算法的效率和準確性。