一種改進(jìn)的高精度視頻幀間匹配算法

1、引言

　　圖像匹配技術(shù)是數(shù)字圖像處理領(lǐng)域的一項(xiàng)重要研究，并已在計(jì)算機(jī)視覺、虛擬現(xiàn)實(shí)場(chǎng)景生成、航空航天遙感測(cè)量、醫(yī)學(xué)影像分析、光學(xué)和雷達(dá)跟蹤、景物制導(dǎo)等領(lǐng)域得到了廣泛的應(yīng)用。它涉及到許多相關(guān)領(lǐng)域，如圖像預(yù)處理、圖像采樣、圖像分割、特征提取等，并且將計(jì)算機(jī)視覺、多維信號(hào)和數(shù)值計(jì)算方法等緊密結(jié)合在一起。因此，如何找到一種有效的圖像匹配方法，使得它能快速而準(zhǔn)確的從大量信息中找出所需圖像信息成為急待需要解決的問題。

　　特征法[1]是圖像匹配算法中的一種經(jīng)典方法，其原理是選取圖像中的典型特征作為運(yùn)動(dòng)估計(jì)的基本單元，這種方法比較接近于人的視覺特性，主要受制于特征提取的穩(wěn)定性和特征定位的精確性。而SIFT (scale in-variant feature transform)特征[2,3]是一種對(duì)尺度、旋轉(zhuǎn)、亮度、仿射、噪音等都具有不變性的圖像局部特征。所以，本文針對(duì)視頻幀間匹配的要求，結(jié)合SIFT特征對(duì)尺度和旋轉(zhuǎn)具有不變性的優(yōu)點(diǎn)，將歐式距離判別和RANSAC法融合到對(duì)SIFT特征點(diǎn)的匹配計(jì)算中，通過研究得到了一種高精度的視頻幀間匹配算法。

2、基于SIFT特征的視頻幀間匹配

　　在需要處理的視頻幀間圖像中，普遍地存在旋轉(zhuǎn)和尺度縮放，而常用的Harris角點(diǎn)[4] 和K-L角點(diǎn)[5]不適用于這種場(chǎng)合。SIFT特征是分別在兩幀圖像的高斯差分尺度空間（DOG scale-space）提取出的圖像局部特征，以某段在直升機(jī)上拍攝的航拍視頻為例，對(duì)視頻中某兩幀圖像的SIFT特征點(diǎn)進(jìn)行匹配，仿真結(jié)果如圖1所示。

                            
              圖1 視頻中某兩幀圖像的SIFT特征匹配結(jié)果

　　仿真結(jié)果表明，SIFT特征不僅具有對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化的不變性，而且對(duì)視角變化、仿射變換、噪聲也具有一定程度的穩(wěn)定性。由于該算法不以單個(gè)像素作為研究對(duì)象，所以提高了對(duì)圖像局部變形的適應(yīng)能力。

　　但是在傳統(tǒng)的僅采用歐式距離判別法對(duì)特征點(diǎn)進(jìn)行匹配的過程中，仍舊存在誤匹配問題。圖2是將相鄰兩幀圖像中提取的特征點(diǎn)在同一幀圖像中顯示，可以根據(jù)性質(zhì)將誤匹配點(diǎn)分為兩類：第一類是完全匹配錯(cuò)誤的點(diǎn)，如圖2方框（a）所示，即被配對(duì)的兩幀圖像上的兩個(gè)點(diǎn)實(shí)際上不是一對(duì)具有匹配關(guān)系的點(diǎn)，他們具有相同或極其相似的SIFT特征向量，但他們并不是同一個(gè)圖像特征；第二類是有誤差的匹配點(diǎn)，如圖2方框（b）所示，即兩個(gè)點(diǎn)雖然是同一個(gè)圖像特征，但是由于鏡頭的晃動(dòng)，圖像的局部運(yùn)動(dòng)及其他擾動(dòng)的影響，同一個(gè)點(diǎn)在兩幀圖像中的坐標(biāo)差異與其他大部分點(diǎn)的坐標(biāo)差異相比，存在較大的偏差。這兩種情況都會(huì)影響到運(yùn)動(dòng)參數(shù)估計(jì)的準(zhǔn)確度，因此都是需要被去除的誤匹配點(diǎn)。

                             圖2 歐式距離法判別匹配點(diǎn)

　　實(shí)驗(yàn)表明，利用歐式距離進(jìn)行關(guān)鍵點(diǎn)匹配的匹配精度基本取決于比例閾值r 的大小，r 取值過大會(huì)出現(xiàn)大量錯(cuò)匹配點(diǎn)，而r取值過小可能得到的匹配點(diǎn)數(shù)目過少。然而存在這樣的情況，即如果兩幀圖像上的某兩個(gè)不同的特征點(diǎn)的特征向量的歐式距離值非常小，則閾值r 需要取足夠小的值才有可能去掉這一對(duì)錯(cuò)誤的匹配點(diǎn)，這樣一來匹配點(diǎn)總數(shù)目就太少甚至為零，甚至無法進(jìn)行后面的參數(shù)計(jì)算。故單純靠調(diào)節(jié)歐式距離匹配中的比例閾值r無法解決上述誤配點(diǎn)問題，難以達(dá)到高精度、數(shù)目適中的特征點(diǎn)匹配結(jié)果。

3、匹配準(zhǔn)則的改進(jìn)

　　RANSAC法和傳統(tǒng)的方法的區(qū)別在于傳統(tǒng)的方法先把全部的數(shù)據(jù)點(diǎn)作為內(nèi)點(diǎn)而計(jì)算出初始參數(shù)值，然后重新計(jì)算并統(tǒng)計(jì)內(nèi)點(diǎn)和外點(diǎn)；而RANSAC法最開始是利用一部分?jǐn)?shù)據(jù)作為內(nèi)點(diǎn)得到初始值，然后尋找數(shù)據(jù)集中所有別的內(nèi)點(diǎn)。即應(yīng)用RANSAC法對(duì)歐式距離法粗匹配的特征點(diǎn)進(jìn)行準(zhǔn)確度檢驗(yàn)，可以最大限度地減少噪聲及外點(diǎn)的影響。所以，本文首先采用關(guān)鍵點(diǎn)特征向量的歐式距離判定視頻中某兩幀圖像的特征點(diǎn)相似性，進(jìn)行粗略匹配，然后利用RANSAC法對(duì)粗略匹配結(jié)果進(jìn)行迭代演算[7,8]，通過二次精確匹配來剔除粗匹配中的誤配點(diǎn)，得到精確的匹配點(diǎn)，從而得到精確的圖像匹配結(jié)果。

3.1 歐式距離判別法的一次粗匹配

　　當(dāng)兩幀圖像的SIFT特征向量生成后，首先采用關(guān)鍵點(diǎn)特征向量的歐式距離作為兩幀圖像中關(guān)鍵點(diǎn)的相似性判定度量。歐氏距離（Euclidean distance）是一個(gè)通常采用的距離定義，它是在n維空間中兩個(gè)點(diǎn)之間的真實(shí)距離。

　　計(jì)算兩幀圖像中特征點(diǎn)的歐式距離的公式是：

                                       （1）
 
　　Xi1表示第一幀圖像上某一點(diǎn)的第i 維坐標(biāo)，Xi2表示第二幀圖像上某一點(diǎn)的第i 維坐標(biāo)。
 
　　判斷準(zhǔn)則：取圖像1中的某個(gè)關(guān)鍵點(diǎn)，計(jì)算出圖像2中與其歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離d1除以次近的距離d2少于某個(gè)比例閾值r ，則接受這一對(duì)匹配點(diǎn)，否則拋棄。

3.2 RANSAC法的二次精確匹配

　　RANSAC(Random Sampling Consensus) 法[6]的基本思想是在進(jìn)行參數(shù)估計(jì)時(shí)，不是不加區(qū)分地對(duì)待所有可用的輸入數(shù)據(jù)，而是首先針對(duì)具體問題設(shè)計(jì)出一個(gè)目標(biāo)函數(shù)，然后迭代地估計(jì)該函數(shù)的參數(shù)值，利用這些初始參數(shù)值把所有的數(shù)據(jù)分為所謂的“內(nèi)點(diǎn)”（Inliers, 即滿足估計(jì)參數(shù)的點(diǎn)）和“外點(diǎn)”（Outliers，即不滿足估計(jì)參數(shù)的點(diǎn)），最后反過來用所有的“內(nèi)點(diǎn)” 重新計(jì)算和估計(jì)函數(shù)的參數(shù)。

　　本文中的全局運(yùn)動(dòng)包括尺度變換、旋轉(zhuǎn)變換和平移變換。如果用X 和Y 表示一幀圖像中任意一個(gè)特征點(diǎn)的位置坐標(biāo)，x 和y 表示另一幀圖像中任意一個(gè)特征點(diǎn)的位置坐標(biāo)，L 表示這兩幀圖像之間的尺度變換，θ表示旋轉(zhuǎn)變換， a 和b 表示平移變換。那么，計(jì)算全局運(yùn)動(dòng)參數(shù)可以用相似變換表示如下： （2）

　　在兩幀圖像的粗匹配點(diǎn)中選出8 對(duì)，利用它們的坐標(biāo)信息，組成一個(gè)方程組，計(jì)算出運(yùn)動(dòng)參數(shù)，利用參數(shù)把第二幀圖像中所有的點(diǎn)都變換到第一幀圖像上，反變換后的點(diǎn)坐標(biāo)用X’,Y’表示，則：

                                 （3）
 
　　判斷準(zhǔn)則：如果某一點(diǎn)變換到第一幀圖像上能和它在第一幀圖像上的對(duì)應(yīng)點(diǎn)重合或者基本重合（位移值小于1象素），即：

                     （4）
 
　　那它們就是該變換確定的一對(duì)對(duì)應(yīng)點(diǎn)。若對(duì)應(yīng)點(diǎn)的個(gè)數(shù)占區(qū)域中全部點(diǎn)個(gè)數(shù)的比例達(dá)到一定的閾值（人工選定），那就認(rèn)為這組變換關(guān)系是可接受的。利用經(jīng)該變換確定的所有對(duì)應(yīng)點(diǎn)即內(nèi)點(diǎn)以最小二乘的方法去重新求解運(yùn)動(dòng)參數(shù)，至此匹配點(diǎn)檢驗(yàn)結(jié)束，不再向下計(jì)算。若對(duì)應(yīng)點(diǎn)比例不能達(dá)到要求，則重新選擇一組點(diǎn)，再去計(jì)算它們所對(duì)應(yīng)的運(yùn)動(dòng)參數(shù)。如果對(duì)于每一組求出的運(yùn)動(dòng)參數(shù)，對(duì)應(yīng)點(diǎn)的比例都達(dá)不到設(shè)定的閾值，則判定這兩幀圖之間不存在匹配關(guān)系。

4、實(shí)驗(yàn)結(jié)果及分析

　　在實(shí)驗(yàn)中，視頻圖像大小為884×662，視頻幀率為25fps，計(jì)算機(jī)配置為AMD Athlon(tm) 64×2 Dual Core Processor 5000+，內(nèi)存2.00GB。圖3為歐式距離判別法的一次粗匹配得到的匹配點(diǎn)，其中（a）、（b）分別為在兩幀圖像中得到的匹配點(diǎn)，（c）表示特征點(diǎn)在兩幀圖像中的點(diǎn)位移，可以看出，絕大多數(shù)點(diǎn)位移是微小的，故（c）中的長(zhǎng)線表示點(diǎn)位移值較大，證明該匹配點(diǎn)為誤配點(diǎn)。

                   （a）　　　?。╞） 　　?。╟）
                 圖3 歐式距離判別法的一次粗匹配結(jié)果

　　圖4為經(jīng)過RANSAC法的二次精確匹配得到的匹配結(jié)果，由4（c）可得，經(jīng)過二次匹配，去掉了一次粗匹配中錯(cuò)配的點(diǎn)和由于局部運(yùn)動(dòng)造成的有誤差的匹配點(diǎn)，得到了完全正確的匹配結(jié)果。表1 給出了用傳統(tǒng)歐式距離判別算法和本文的歐式距離—RANSAKC二次匹配法對(duì)視頻幀間圖像進(jìn)行SIFT特征匹配所得結(jié)果。

                       （a） 　　?。╞） 　　?。╟）
           圖4 經(jīng)過RANSAC法二次匹配檢驗(yàn)得到的匹配結(jié)果
 
表1 歐式距離法和RANSAC二次匹配法的視頻幀間圖像特征匹配結(jié)果比較

          
　　經(jīng)過對(duì)該段視頻430幀圖像的處理，得出單純采用歐式距離匹配算法得到的平均正確匹配率為96.2%，平均峰值信噪比為21.8541dB，其中單次正確匹配率100%的幀數(shù)為8幀，而本文所用的歐式距離-RANSAC兩次匹配法的平均正確匹配率為98.8%，平均峰值信噪比為31.2271dB，單次正確匹配率100%的幀數(shù)為349幀，有效地減少了誤配點(diǎn)數(shù)，根據(jù)峰值信噪比（PSNR）值可以看出視頻幀間圖像的匹配精度得到了顯著提高。

5、結(jié)論

　　本文研究了視頻幀間圖像特征的提取和匹配問題，采用關(guān)鍵點(diǎn)SIFT特征向量的歐式距離判定視頻中某兩幀圖像的特征點(diǎn)相似性進(jìn)行粗略匹配，通過采用RANSAC法的二次精確匹配算法最大限度地減少噪聲及外點(diǎn)的影響，從而解決粗匹配中的誤匹配點(diǎn)問題。仿真試驗(yàn)表明，該算法能夠有效地解決僅采用歐式距離判別法進(jìn)行匹配時(shí)的誤匹配問題，顯著地提高視頻幀間圖像的匹配精度，同時(shí)仿真試驗(yàn)還顯示出該算法具有較強(qiáng)的魯棒性。