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

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

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

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

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

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

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

1 RANSAC算法

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

Step1：從數(shù)據(jù)集SN中隨機(jī)抽樣，選取4對(duì)匹配點(diǎn)si1、si2、si3與si4，構(gòu)成一個(gè)組合，計(jì)算單應(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ù)隨機(jī)抽樣的總次數(shù)為M，得到M個(gè)內(nèi)點(diǎn)統(tǒng)計(jì)數(shù)，找出最大值，將其對(duì)應(yīng)的單應(yīng)矩陣取出，作為最佳圖像轉(zhuǎn)換參數(shù)H。M通過(guò)如式(7)計(jì)算確定。

M=log1-p4(1-P)

(7)

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

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

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

2 改進(jìn)算法

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

2.1 局域像素粗匹配

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

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

Step2：與RANSAC算法Step 1相同。

(8)

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

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

局域像素匹配本質(zhì)上也是像素相關(guān)算法，但與傳統(tǒng)像素相關(guān)圖像配準(zhǔn)方法不同。本算法在SIFT或SURF算法完成特征匹配之后使用，不受圖像旋轉(zhuǎn)、尺度變換和仿射變換等影響，像素點(diǎn)未缺失遺漏，避免了傳統(tǒng)相關(guān)算法的不足。圖2以矩形局域像素為例，對(duì)粗匹配進(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)變換、尺度變換和仿射變換時(shí)的局域像素匹配。左圖為參考圖像，右圖為待拼接圖像。各圖像中的陰影表示重疊區(qū)域，陰影中小矩形塊內(nèi)的圓點(diǎn)表示局域像素。從圖2看到，無(wú)論圖像發(fā)生旋轉(zhuǎn)、尺度變換還是仿射變換，在參考圖像中給定9個(gè)局域像素點(diǎn)，在待拼接圖像中都會(huì)映射出9個(gè)局域像素點(diǎn)。只要Step 2隨機(jī)抽樣的4對(duì)特征匹配點(diǎn)均為內(nèi)點(diǎn)，那么局域像素達(dá)成匹配，單應(yīng)矩陣大概率確定為最佳轉(zhuǎn)換參數(shù)，而不受其他外點(diǎn)影響，比RANSAC算法更加穩(wěn)健。

2.2 局域像素精匹配

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

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

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

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

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

3 算法仿真驗(yàn)證

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

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

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

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

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

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

(a) 特征點(diǎn)匹配(a) Feature point matching

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

(c) 局域像素匹配放大(c) Amplified local pixel matching圖4 特征點(diǎn)匹配和局域像素匹配效果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 特征匹配點(diǎn)內(nèi)點(diǎn)占比低的情景

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

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

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

(a) 特征點(diǎn)匹配(a) Feature point matching

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

(c) 局域像素匹配放大(c) Amplified local pixel matching圖6 特征點(diǎn)匹配和局域像素匹配效果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)算法未明顯增加計(jì)算耗時(shí)，在特征匹配點(diǎn)內(nèi)點(diǎn)占比較高與較低的條件下，均具有優(yōu)于RANSAC經(jīng)典算法的穩(wěn)健性能，求解的單應(yīng)矩陣使得圖像拼接更加精確。