采用局域像素匹配的隨機抽樣一致改進(jìn)算法

戴衛(wèi)華，劉盛春，趙 慎 ，彭 華，張 昊，黃志剛，李小林

(1. 信息工程大學(xué) 信息系統(tǒng)工程學(xué)院， 河南 鄭州 450001；2. 哈爾濱工程大學(xué) 水聲工程學(xué)院， 黑龍江 哈爾濱 150006；3. 陸軍工程大學(xué) 石家莊校區(qū)， 河北 石家莊 050003；4. 盲信號處理國防科技重點實驗室， 四川 成都 610041；5. 拉蓋爾電子科技有限公司， 湖南 長沙 410073)

圖像拼接技術(shù)可以有效解決寬視場圖像獲取問題，是“全景視頻”熱點應(yīng)用的技術(shù)基礎(chǔ)，在視頻會議、監(jiān)控和遙感測繪等領(lǐng)域有廣泛的應(yīng)用[1]。現(xiàn)實中可以采用廣角相機拍攝得到寬視場圖像，但是這樣得到的寬視場圖像在邊緣容易發(fā)生嚴(yán)重畸變，校正畸變的過程十分煩瑣，且廣角相機光學(xué)器件價格昂貴。除此之外，廣角相機視場一般不超過180°，只采用單個廣角相機很難獲取更寬視場圖像，尤其是360°全景圖像。圖像拼接技術(shù)恰能解決該問題：采用多個相機，同時獲取視場圖像，相鄰相機的視場圖像一般存在30%至50%的重疊區(qū)域，所有相機視場能夠覆蓋360°范圍。通過處理，將相鄰兩個視場圖像拼接成更寬的視場圖像。經(jīng)過多次拼接，所有視場圖像最終形成一個360°的全景圖像。

圖像拼接算法眾多，大致分為設(shè)備標(biāo)定法和重疊區(qū)域檢測法[2]。設(shè)備標(biāo)定法需要精密成像器材，耗費大量人工操作，使用很不方便。重疊區(qū)域檢測法容易自動化操作，實現(xiàn)靈活，因此成為主流方法[3]，其典型代表是尺度不變特征變換(Scale Invariant Feature Transform，SIFT)算法[4]和加速穩(wěn)健特征(Speeded-Up Robust Features，SURF)算法[5]。SIFT算法利用圖像特征點360°方向的梯度信息，同時利用高斯核實現(xiàn)尺度空間變換，具有顯著的圖像變換不變性，在旋轉(zhuǎn)、仿射、尺度變換等場合下性能穩(wěn)定，唯一不足的是計算量大。SURF算法則被稱為加速SIFT算法，即除了采用盒子濾波代替高斯濾波，其他過程基本一樣，性能與 SIFT算法十分接近，但計算大幅度簡化，在視頻拼接等實時性要求高的場合具有優(yōu)勢。不過，隨著圖形處理單元(Graphics Processing Unit, GPU)高性能計算芯片技術(shù)的發(fā)展，SIFT算法在圖像、視頻拼接領(lǐng)域應(yīng)用時機逐漸成熟。

無論采用SIFT算法，還是SURF算法，在完成特征提取和特征匹配之后，至少需要4對特征匹配點才能計算參考圖像和待拼接圖像之間的坐標(biāo)轉(zhuǎn)換參數(shù)，即單應(yīng)矩陣。在大多數(shù)場合，會得到多于4對的特征匹配點，用于計算單應(yīng)矩陣的匹配點組合很多。由于圖像多樣性、模糊和噪聲等干擾，有些匹配點存在誤差，甚至錯誤，不適合用于計算單應(yīng)矩陣。因此需要從原始匹配點中選出最佳的4對，以盡可能準(zhǔn)確地計算單應(yīng)矩陣。SIFT算法和SURF算法采用隨機抽樣一致(RANdom SAmpling Consensus，RANSAC)算法[6]來優(yōu)選4對特征匹配點，它具有很強的容錯能力，本質(zhì)上是一種離散數(shù)據(jù)集擬合方法：隨機抽取4對匹配點作為一個組合，計算單應(yīng)矩陣，再計算其余匹配點由單應(yīng)矩陣映射為內(nèi)點(即匹配誤差在閾值范圍內(nèi)的匹配點)的數(shù)目。重復(fù)抽樣，通過比較各組合得到的內(nèi)點數(shù)目來確定4對最佳匹配點組合以及單應(yīng)矩陣。然而， RANSAC算法難以適應(yīng)內(nèi)點占比低的情形。比如得到12對匹配點，其中，4對內(nèi)點，8對外點(即匹配誤差超出閾值范圍的匹配點)，則RANSAC算法優(yōu)選出錯誤組合的概率很高。為此，不少學(xué)者提出RANSAC改進(jìn)方法，主要策略是對匹配點提純，即在執(zhí)行RANSAC算法之前剔除部分外點。李彬[2]、劉海洋[7]和周玉潔[8]等對匹配點相似程度量化排序，棄用相似程度低的匹配點，或利用圖像重疊信息棄用非重疊區(qū)域匹配點；汪旌[9]等用行列式點過程抽樣實現(xiàn)抽樣點的均勻化和分散化, 剔除一些錯誤匹配點；劉宇[10]等對匹配點分布進(jìn)行排序并剔除稀疏匹配點。這些改進(jìn)方法降低了外點的干擾，提高了后續(xù)RANSAC算法的效率，本質(zhì)上則優(yōu)化了RANSAC算法的數(shù)據(jù)集輸入。

本文提出一種新策略：改進(jìn)特征匹配點優(yōu)選準(zhǔn)則。即給定特征匹配點的數(shù)據(jù)集輸入，獨立于特征匹配點，從參考圖像重疊區(qū)域任選出局域像素點集合。隨機抽樣，從輸入數(shù)據(jù)集中選出4對匹配點，構(gòu)成一個組合，計算單應(yīng)矩陣，再由單應(yīng)矩陣計算映射的待拼接圖像局域像素集合，然后計算兩個局域像素集合之間的像素誤差。重復(fù)抽樣，當(dāng)像素誤差最小時實現(xiàn)局域像素粗匹配，將單應(yīng)矩陣初步確定為最佳圖像轉(zhuǎn)換參數(shù)。在此基礎(chǔ)上，進(jìn)一步提出局域像素精匹配方法，對粗匹配所得映射局域像素，在其鄰域內(nèi)各方向進(jìn)行微調(diào)，計算像素誤差，當(dāng)像素誤差最小時實現(xiàn)局域像素精匹配，記錄此時的微調(diào)量，與單應(yīng)矩陣共同用于圖像拼接。

1 RANSAC算法

RANSAC算法最初由Fischler[7]等提出。其本質(zhì)是一種數(shù)據(jù)集擬合方法，即確定一個最佳參數(shù)模型，以描述數(shù)據(jù)集。在SIFT算法或SURF算法中，假設(shè)數(shù)據(jù)集為N對匹配點，每對匹配點記為sn=(xn,yn;x′n,y′n)，其中(xn,yn)、(x′n,y′n)為匹配特征點分別在參考圖像和待拼接圖像中的坐標(biāo)。數(shù)據(jù)集記作SN={sn}。執(zhí)行RANSAC算法的基本步驟如下所示。

Step1：從數(shù)據(jù)集SN中隨機抽樣，選取4對匹配點si1、si2、si3與si4，構(gòu)成一個組合，計算單應(yīng)矩陣Hi。以參考圖像投影變換至待拼接圖像的模型參數(shù)為例[3]，公式為：

h=(ATA)-1ATb

(1)

式中：

(2)

(3)

(4)

單應(yīng)矩陣Hi與向量h元素的關(guān)系為：

(5)

(6)

Step3：重復(fù)Step 1、Step 2，重復(fù)隨機抽樣的總次數(shù)為M，得到M個內(nèi)點統(tǒng)計數(shù)，找出最大值，將其對應(yīng)的單應(yīng)矩陣取出，作為最佳圖像轉(zhuǎn)換參數(shù)H。M通過如式(7)計算確定。

M=log1-p4(1-P)

(7)

由此可見，RANSAC算法的核心是在每次隨機抽樣時判斷內(nèi)點并比較前后兩次隨機抽樣所得內(nèi)點數(shù)目的大小。該方法在數(shù)據(jù)集內(nèi)點占比較高的條件下十分有效和穩(wěn)健，但在外點占比高尤其是外點集中分布時表現(xiàn)不佳。其根本原因為RANSAC算法自身的局限性：判斷內(nèi)點僅依賴數(shù)據(jù)集空間分布屬性，雖然可以保證至少一次抽樣的4對匹配點全是內(nèi)點，但是無法保證該次抽樣時計算所得內(nèi)點總數(shù)最大。圖1為RANSAC算法用直線擬合局限性示意圖。由于外點數(shù)目更多，且集中分布在虛線附近，由RANSAC算法原理不難推出虛線擬合下計算所得內(nèi)點更多，從而錯失正確擬合的直線。

圖1 RANSAC算法直線擬合局限性示意圖Fig.1 Limitation schematic of RANSAC algorithm linear fitting

為克服RANSAC算法局限性，常見策略是盡量剔除外點，正如前文所述；采用新策略：引入特征匹配點以外的監(jiān)督數(shù)據(jù)，即圖像的局域像素，通過判斷局域像素是否匹配，優(yōu)選出4對特征匹配點，計算單應(yīng)矩陣。

2 改進(jìn)算法

改進(jìn)算法分兩部分：局域像素粗匹配和局域像素精匹配。算法所要求的輸入數(shù)據(jù)集與RANSAC算法一致，可以是特征匹配點原始數(shù)據(jù)集，也可以是經(jīng)過其他改進(jìn)方法剔除了部分外點的特征匹配點新數(shù)據(jù)集。數(shù)據(jù)集仍記為sN={sn}，匹配點數(shù)目為N對。

2.1 局域像素粗匹配

粗匹配基本步驟如下所示。

Step1：在參考圖像的重疊區(qū)域(避免單一紋理或重復(fù)紋理區(qū)域)，任選出N個局域像素，構(gòu)成集合TN={tn}，作為監(jiān)督數(shù)據(jù)集，其中tn=(an,bn)。

Step2：與RANSAC算法Step 1相同。

(8)

Step4：重復(fù)Step 2、Step 3，重復(fù)隨機抽樣的總次數(shù)仍為M，由式(7)確定。得到M個像素誤差，找出最小值，將其對應(yīng)的單應(yīng)矩陣取出，作為最佳圖像轉(zhuǎn)換參數(shù)H。

由于局域像素集合TN與匹配對數(shù)據(jù)集SN點數(shù)相同，經(jīng)單應(yīng)矩陣映射局域像素、計算像素誤差所需計算量與RANSAC方法基本相同。

局域像素匹配本質(zhì)上也是像素相關(guān)算法，但與傳統(tǒng)像素相關(guān)圖像配準(zhǔn)方法不同。本算法在SIFT或SURF算法完成特征匹配之后使用，不受圖像旋轉(zhuǎn)、尺度變換和仿射變換等影響，像素點未缺失遺漏，避免了傳統(tǒng)相關(guān)算法的不足。圖2以矩形局域像素為例，對粗匹配進(jìn)行示意。

(a) 旋轉(zhuǎn)變換(a) Rotation transformation

(b) 尺度變換(b) Scaling transformation

(c) 仿射變換(c) Affine transformation圖2 局域像素粗匹配Fig.2 Local pixel rough matching

圖2(a)、(b)和(c)分別表示圖像旋轉(zhuǎn)變換、尺度變換和仿射變換時的局域像素匹配。左圖為參考圖像，右圖為待拼接圖像。各圖像中的陰影表示重疊區(qū)域，陰影中小矩形塊內(nèi)的圓點表示局域像素。從圖2看到，無論圖像發(fā)生旋轉(zhuǎn)、尺度變換還是仿射變換，在參考圖像中給定9個局域像素點，在待拼接圖像中都會映射出9個局域像素點。只要Step 2隨機抽樣的4對特征匹配點均為內(nèi)點，那么局域像素達(dá)成匹配，單應(yīng)矩陣大概率確定為最佳轉(zhuǎn)換參數(shù)，而不受其他外點影響，比RANSAC算法更加穩(wěn)健。

2.2 局域像素精匹配

在粗匹配基礎(chǔ)上，進(jìn)一步，通過精匹配提高本算法圖像配準(zhǔn)精度。精匹配基本步驟如下所示。

Step1: 在待拼接圖像中，以粗匹配得到的映射局域像素為參考中心，在0°～360°范圍以45°間隔取8個方向，如圖3所示。

圖3 局域像素精匹配Fig.3 Local pixel fine matching

Step4: 新得20個像素誤差，取最小值，與粗匹配得到的最小像素誤差比較。若小于后者，記錄其移位方向及移位量，用于圖像配準(zhǔn)微調(diào)，提高配準(zhǔn)精度。為避免只匹配到局域極小值，可以適度擴(kuò)大精匹配范圍，例如增加8個移位方向，盡可能搜索得到最佳移位量。

與RANSAC算法相比，本文算法將使圖像配準(zhǔn)更加穩(wěn)健和精確。算法計算量略有增加，來自局域像素精匹配，不過只有簡單的加減、乘法，而且可根據(jù)指標(biāo)要求靈活調(diào)減。

3 算法仿真驗證

基于LENOVO小新系列筆記本(inter(R) i5-7300HQ CPU@2.5GHz)硬件和MATLAB R2014b軟件，對算法進(jìn)行驗證仿真。

3.1 特征匹配點內(nèi)點占比高的情景

驗證本文改進(jìn)方法在SIFT算法或SURF算法所得特征匹配點內(nèi)點占比高的情景下的有效性，并與RANSAC經(jīng)典算法進(jìn)行比較。在良好光照條件下通過攝像頭采集了圖4所示的兩幅數(shù)字圖像(來自武漢理工大學(xué)某實驗室)，左圖為參考圖像，右圖為待拼接圖像，均為png格式，像素大小為216×384，重疊區(qū)域約占33%。

圖4(a)左、右圖中重疊區(qū)域用符號“+”標(biāo)記SIFT算法搜索的有效特征匹配點(描述符歐式距離最小值與次最小值之比不大于0.5)，共15對，內(nèi)點13對，內(nèi)點占比達(dá)86.7%。在參考圖像重疊區(qū)域任選9個局域像素點，用符號“·”表示，呈矩形，如圖4(b)左圖所示。右圖用藍(lán)色和黃色符號標(biāo)記的點分別為通過本文改進(jìn)算法和RANSAC經(jīng)典算法在待拼接圖像中映射的局域像素。圖4(c)是圖4(b)在局域像素附近局部放大的效果圖。而從放大效果圖可以看出，改進(jìn)算法與RANSAC算法搜索的映射局域像素點接近，但前者更加精確。

圖5(a)、圖5(b)分別是采用RANSAC與改進(jìn)算法獲得的拼接圖像，拼接縫兩側(cè)均保留原始像素，未做像素融合，以便于顯示拼接位置。可以發(fā)現(xiàn)，前者在拼接縫位置存在一點垂直方向的錯位，而后者在拼接縫位置對接良好。

改進(jìn)算法執(zhí)行局域像素粗匹配階段用時[1 365×(132+198.4+58.6)]μs,共0.531 0 s。其中：1 365為從15對特征匹配點中任選4對的組合數(shù)，即循環(huán)控制數(shù)；132 μs為單次循環(huán)需要計算的映射局域像素坐標(biāo)耗時；198.4 μs為單次循環(huán)插值計算映射局域像素灰度值耗時，58.6 μs為單次循環(huán)計算像素誤差耗時。在圖像局域像素精匹配階段耗時0.011 7 s，像素匹配總耗時0.542 7 s。與之相比，RANSAC經(jīng)典算法耗時(1 365×242.3 )μs，共0.330 7 s。故改進(jìn)算法與RANSAC經(jīng)典算法計算耗時大致相同。

(a) 特征點匹配(a) Feature point matching

(b) 局域像素匹配(b) Local pixel matching

(c) 局域像素匹配放大(c) Amplified local pixel matching圖4 特征點匹配和局域像素匹配效果Fig.4 Feature point matching and local pixel matching effect

(a) RANSAC算法效果(a) RANSAC algorithm effect

(b) RANSAC改進(jìn)算法效果(b) Improved RANSAC algorithm effect圖5 圖像拼接效果Fig.5 Image splicing effect

3.2 特征匹配點內(nèi)點占比低的情景

進(jìn)一步驗證改進(jìn)算法在SIFT算法或SURF算法特征匹配點內(nèi)點占比較低的情景下的有效性，并與RANSAC經(jīng)典算法進(jìn)行比較。在輕度霧霾天氣和逆光條件下用相同攝像頭采集圖6所示兩幅圖像(來自鄭州某高校實驗室)。左圖為參考圖像，右圖為待拼接圖像。兩幅圖質(zhì)量不高，顏色對比度低，細(xì)節(jié)不夠清晰，僅能分辨建筑、樹林和路燈的基本輪廓。兩幅圖重疊區(qū)域約占36%，但仍在33%左右區(qū)域搜索特征匹配點。

圖6(a)展示了SIFT算法搜索的有效特征匹配點(描述符歐式距離最小值與次最小值之比不大于0.5)，共19對，內(nèi)點10對，內(nèi)點占比52.6%。圖6(b)、圖6(c)依次是局域像素匹配效果的全圖和局部放大圖。在左側(cè)參考圖像中選了16個局域像素，分別通過本文改進(jìn)算法和RANSAC算法得到映射局域像素；在右圖中仍然分別用藍(lán)色和黃色符號標(biāo)記。由圖6(c)可見，兩種算法的待拼接圖像相對參考圖像發(fā)生了小角度的旋轉(zhuǎn)。

圖7(a)、(b)分別是根據(jù)RANSAC算法和改進(jìn)算法結(jié)果進(jìn)一步拼接的圖像，圖中參考圖像在拼接圖中均做了旋轉(zhuǎn)映射。但是，在圖7(a)中拼接縫左側(cè)下方存在無法映射的像素區(qū)域(用右側(cè)像素填充)，參考圖像與待拼接圖像在垂直方向未配準(zhǔn)，且縮放有明顯誤差。原因主要是RANSAN算法優(yōu)選的4對特征匹配點只保證了計算所得“內(nèi)點”數(shù)目最大，而無法有效降低該4對內(nèi)點自有誤差的干擾。相比之下，圖7(b)拼接更加精確，驗證了改進(jìn)算法在優(yōu)選最佳特征匹配點組合和準(zhǔn)確計算單應(yīng)矩陣時的穩(wěn)健性能。

(a) 特征點匹配(a) Feature point matching

(b) 局域像素匹配(b) Local pixel matching

(c) 局域像素匹配放大(c) Amplified local pixel matching圖6 特征點匹配和局域像素匹配效果Fig.6 Feature point matching and local pixel matching effects

(a) RANSAC算法效果(a) RANSAC algorithm effect

(b) RANSAC改進(jìn)算法效果(b) Improved RANSAC algorithm effect圖7 拼接效果圖Fig.7 Image splicing effect

4 結(jié)論

提出一種基于局域像素匹配的RANSAN改進(jìn)算法。仿真結(jié)果表明：改進(jìn)算法未明顯增加計算耗時，在特征匹配點內(nèi)點占比較高與較低的條件下，均具有優(yōu)于RANSAC經(jīng)典算法的穩(wěn)健性能，求解的單應(yīng)矩陣使得圖像拼接更加精確。