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

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

1 引言

基礎(chǔ)矩陣估計是利用運動中恢復(fù)結(jié)構(gòu)(Structure from Motion)[1,2]、多視角立體視覺(Multi-view Stereo)[3,4]等方法獲取空間目標(biāo)信息的關(guān)鍵問題，被廣泛應(yīng)用于基于圖像的建模(Image-based Modeling)[5,6]、即時定位與地圖構(gòu)建(Simultaneous Localization and Mapping)[7,8]等計算機視覺領(lǐng)域前沿?zé)狳c研究中。

從一組不同角度、不同距離拍攝的同一場景所得的二維序列圖像中還原出目標(biāo)對象的三維空間信息，其理論基礎(chǔ)是彼此之間存在的對極幾何約束[9,10]?；A(chǔ)矩陣在對極約束下描述了相關(guān)圖像中匹配特征點對之間的數(shù)學(xué)關(guān)系。相關(guān)研究最早可見于攝像機自標(biāo)定[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ù))個特征點的齊次坐標(biāo)。式(1)描述了這些特征點之間的對極約束關(guān)系。

p′iTFpi=0

(1)

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

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

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

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

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

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

2 相關(guān)工作

2.1 基礎(chǔ)矩陣估計方法

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

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

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

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

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

2.2 QUATRE算法

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

B=Xgbest+c*(Xr1-Xr2)

(2)

(3)

(4)

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

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

3 本文方法

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

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

3.1 初始化

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

(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 內(nèi)點率及終止條件

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

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

(7)

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

3.3 進化策略

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

3.3.1 變異操作

由于染色體是由基因決定的，根據(jù)3.2節(jié)有關(guān)內(nèi)點率w值越高染色體越優(yōu)秀的討論，可進一步衍生出w值越高的染色體所包含的基因越優(yōu)秀的結(jié)論。與式(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所提出的類仿射變換形式進行。若當(dāng)前種群X通過基因突變產(chǎn)生的種群記為X′，則X′中應(yīng)既保留X的部分基因，也包含一些來自B中的變異基因，其實現(xiàn)方法如式(10)所示。

(10)

3.3.3 選擇操作

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

4 實驗與結(jié)果分析

本節(jié)將通過實驗說明本文方法的準(zhǔn)確性和高效性。實驗數(shù)據(jù)為使用小米MIX 2S手機拍攝的30個場景，共計60幅圖像(分辨率為1440×1080)。所有實驗均在一臺處理器為英特爾雙核i5(主頻2.5 GHz)、內(nèi)存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中以“+”“×”和“○”表示(為便于展示，圖中僅隨機標(biāo)記1/3的SURF特征點)。

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

4.1 有效性分析

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

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

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

4.2 準(zhǔn)確性對比及分析

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

(11)

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

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

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

就整體表現(xiàn)對不同方法進行橫向?qū)Ρ龋疚姆椒ㄔ谄骄鶎O距離方面與MSAC和RANSAC相當(dāng)，且明顯優(yōu)于LMedS;在標(biāo)準(zhǔn)差方面與LMedS和RANSAC相當(dāng)，且優(yōu)于MSAC。就應(yīng)用于不同場景中的縱向?qū)Ρ瓤芍疚姆椒ㄔ谔卣鼽c數(shù)多的場景下仍表現(xiàn)出較好的準(zhǔn)確性。

4.3 效率對比及分析

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

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

5 結(jié)束語

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