孫 文 華

(南昌工程學院信息工程學院，江西 南昌，330099)

?

面向單視頻超分辨率重建的改進的SIFT配準算法

孫 文 華

(南昌工程學院信息工程學院，江西 南昌，330099)

針對單視頻超分辨率重建傳統(tǒng)的基于SIFT特征點檢測的配準，在特征匹配上占用時間很大，難于滿足實時性的要求，而用于計算128維特征描述子的時間最長這一缺點，提出了一種改進的SIFT配準算法，該算法的原理為通過放棄對128維特征描述子的計算，采用特征點之間的灰度相關(guān)系數(shù)來進行初始匹配，以期大大減少計算時間，提高特征匹配速度。實驗結(jié)果證明，該算法在配準結(jié)果、時間消耗上明顯優(yōu)于傳統(tǒng)配置算法。

特征點檢測;特征匹配;SIFT配準算法;超分辨率重建

單視頻超分辨率重建中，只涉及到空間分辨率的增強。由于單視頻超分辨率重建的特殊性，傳統(tǒng)的基于SIFT特征點檢測的配準只是一種通用解決方案，但傳統(tǒng)SIFT算法在實時性方面較差，主要原因就是需要對128維特征描述子進行計算，從而需要耗費大量時間在特征匹配上。此外，利用特征描述子的歐式距離的消除法在多對一的歧義消除中還會有錯誤選擇的出現(xiàn)。故如果想要在實時性上有所提高，就必須對算法進行優(yōu)化，對特征描述子進行改進。在此筆者提出一種改進的SIFT配準算法，該算法的原理為通過放棄對128維特征描述子的計算，采用特征點之間的灰度相關(guān)系數(shù)代替特征描述子進行視頻幀間配準，從而大大減少計算時間，提高特征匹配速度。

1 傳統(tǒng)SIFT特征匹配算法

David.Lowe在1999年在對現(xiàn)有的基于不變量技術(shù)的特征檢測方法[1]研究和總結(jié)的基礎上，提出了尺度不變特征變換(Scale Invariant Feature Transform)，簡稱SIFT算法。該算法是基于尺度空間的，通過對圖像平移、旋轉(zhuǎn)、縮放、甚至仿射變換保持不變性的圖像局部特征。并于2004年得以改善，現(xiàn)被廣泛應用于物體識別、導航、醫(yī)學圖像處理、圖片拼接[2]、影像跟蹤配準和手勢識別等多個領(lǐng)域。

1.1 傳統(tǒng)SIFT特征匹配算法特點

近年來，SIFT特征匹配算法在計算機視覺 (Computer Vision) 領(lǐng)域中的研究和應用都相當廣泛，該算法既可以對影像圖片[3]中局部具有明顯的特征進行檢測與描述，又可以對多幅圖像中檢測到的特征向量進行配對。SIFT特征匹配算法的特征歸納起來主要有：(1)關(guān)鍵點檢測速度快；(2)關(guān)鍵點定位精確；(3)獨特性好，信息量豐富，對特征描述子的計算過程中還包含了區(qū)域統(tǒng)計特性；(4)穩(wěn)定性較好，不但對常見的線性光照模型表現(xiàn)出不變性，而且對復雜的光照變化模型同樣具有較強的適應性。

1.2 變換參數(shù)矩陣的計算

SIFT特征匹配算法采用六參數(shù)仿射變換模型[4]，即兩幀之間的變換矩陣共有6個未知參數(shù)。而每一對匹配可以建立2個匹配方程，如式(1)所示。(u,v)是原圖中點(x,y)在目標圖中的匹配特征點。

u=Ax+By+C

v=Dx+Ey+F

(1)

式(1)又可轉(zhuǎn)化為：

(2)

其中的3×3矩陣就是六參數(shù)配準中的變換參數(shù)矩陣，只要求出它，就可以進行圖像的配準。6個未知數(shù)需要6個方程，即3對特征點?？赊D(zhuǎn)化為式(3)：

(3)

根據(jù)線性代數(shù)的知識，可知變換參數(shù)矩陣有解，但是事實上圖像中存在很多組這樣的特征點匹配，但由于匹配誤差[5]導致的解各不相同，故只能求出一組解，以盡量逼近結(jié)果，即超定方程組的最小二乘解。最終n對匹配特征點可以轉(zhuǎn)化為：

(4)

目前常用的解決這個問題的方法有最小二乘法，退火算法和遺傳算法[6]，現(xiàn)對其做一個簡單比較。

最小二乘法只能解決一階的超定方程問題，但是速度非常快，且解幾乎是最優(yōu)解。模擬退火算法和遺傳算法是啟發(fā)式搜索算法，前者模仿固體冷卻時內(nèi)部粒子的不穩(wěn)態(tài)，采用隨機干擾來搜索最優(yōu)解，但后者則是模仿自然界的生物種群進化行為，利用選擇，交叉和變異3種行為和一個評估函數(shù)來進行最優(yōu)解的搜索。由于這2種算法并非專為一階超定方程組準備，所以在實驗中發(fā)現(xiàn)用這2種算法來解變換參數(shù)矩陣，只能逼近最優(yōu)解，并且收斂速度慢。因此最終采用最小二乘法來計算變換參數(shù)矩陣[7]。

假設：

H×X1=X2

(5)

X1是一個3×N的矩陣，其中N為特征點匹配的對數(shù)。由于N往往不為3，X1并非方陣，因此不能直接求其逆矩陣而得解H。現(xiàn)對等式兩邊同時乘以X1的轉(zhuǎn)置矩陣，則等式左邊變成H和一個3×3方陣之積，于是可得解：

H=(X2*X1T)×(X1*X1T)-1

(6)

2 改進的SIFT特征點匹配

圖像的特征點匹配主要分為以下步驟：第一步，進行SIFT特征點檢測；第二步，進行特征點的初始匹配；第三步，進行變換參數(shù)矩陣的計算和誤匹配與歧義方面的消除。在這幾步當中，除了變換參數(shù)矩陣的計算，都需要用到128維特征描述子。特征描述子包含了特征點周圍16個4×4鄰域內(nèi)的8個方向的梯度變化信息，是一個128維的歸一化向量，使其能夠表達豐富的圖像梯度信息[8]。

在單視頻超分辨率重建過程中，每秒大約有30幀的圖像信息，故相鄰的幀之間的圖像信息都不會有太大的變化，也就是說圖像中特征點的位置都不會出現(xiàn)太大的偏移，故完全可以利用X與Y坐標的信息消除歧義匹配或者誤匹配。改進SIFT配準算法通過放棄對128維特征描述子的計算，而采用特征點之間的灰度相關(guān)系數(shù)來進行單視頻幀與幀之間的配準[8]。

2.1 改進的初始匹配

根據(jù)特征點匹配的原理，在進行SIFT特征點檢測之后，就是對特征點進行初始匹配。傳統(tǒng)算法中認為128維特征描述子的歐氏距離優(yōu)劣直接影響到特征點的初始匹配的成功與否。

假設m是圖1(a)中的特征點，坐標為(u,v)，n是圖1(b)中與之對應的特征點，坐標為(j,k)，分別以m和n為中心，R1為半邊長作2個正方形鄰域，則這2個鄰域的相關(guān)系數(shù)定義為：

(7)

由于現(xiàn)在放棄對128維特征描述子的計算，且特征點之間的灰度相關(guān)系數(shù)是可以用來甄別特征點的匹配，故選取了特征點之間的灰度相關(guān)系數(shù)來作為初始匹配的依據(jù)。通過實驗發(fā)現(xiàn)，當特征點之間的灰度相關(guān)系數(shù)閾值達到0.95的時候就能較好的剔除誤匹配[10]。假設現(xiàn)在需要在目標圖中找一個特征點與原圖中的特征點Pi進行初始匹配?？梢酝ㄟ^以下步驟進行：

Step 1：根據(jù)式(7)，分別計算Pi與目標圖中所有特征點的灰度相關(guān)系數(shù)。

Step 2：選取目標圖特征點中，找出和Pi相關(guān)性最強的一點Pj。

Step 3：假設Cij>0.95，則認為Pi和Pj是一對初始匹配。

在實際應用中，一個320×200像素的圖像往往能找到大約400個特征點。因而如果對每一對特征點都進行灰度相關(guān)系數(shù)的計算，那么就要計算大約16 000次灰度相關(guān)系數(shù)，如果灰度相關(guān)系數(shù)的計算鄰域再大一點，這與性能優(yōu)化的初衷背道而馳。實驗證明，其計算時間甚至大于用128維特征描述符來進行運動配準。

考慮到應用環(huán)境為基于單視頻超分辨率的重建，相鄰幾幀之間的差異在非高速攝影中變化往往不大，每個特征點的仿射變換位移很小，所以可以將目標圖中候選特征點集限定在和原圖特征點平面坐標歐氏距離小于r的子集上。之前的步驟就可以修改為：

Step 1：選擇候選特征點，將目標圖中與Pi的平面坐標歐氏距離比r小的作為候選特征點。

Step 2：計算候選特征點與Pi的灰度相關(guān)系數(shù)。

Step 3：找出與Pi之間灰度相關(guān)系數(shù)最高的一點Pj。

Step 4：假設Cij>0.95，則認為Pi和Pj是一對初始匹配。

在實際的應用當中，r的取值需要根據(jù)圖像的長寬像素尺寸來決定。通常，r取50或者長寬像素較大者的1/6。

2.2 改進的匹配關(guān)聯(lián)度

在能效消除多對一歧義匹配或者誤匹配的常用方法當中，通常認為，匹配關(guān)聯(lián)度是唯一一種既能有效消除多對一歧義匹配又能同時消除誤匹配的方法。

基于128維SIFT特征描述符子的匹配關(guān)聯(lián)度定義為：

(8)

其中，cAB，cCD分別為匹配點對(A,B)和(C,D)的灰度相關(guān)系數(shù)，這里的d(p1,p2)為點p1和點p2基于128維特征描述符的歐幾里德距離。

(9)

(10)

其中，dr代表相對距離差，ε為相對距離偏差的一個閾值，在此取ε=0.3。當dr=0時，即(A,C)和(B,D)相對距離差為零時，δ(A,B,C,D)=1，這時在其它因素相同的情況下，匹配點對(C,D)與(A,B)的關(guān)聯(lián)性最強，隨著dr的增大，δ(A,B,C,D)單調(diào)遞減。分母上，若(d(A,C)+d(B,D))×0.5值越小，即是(A,C)和(B,D)之間距離的平均值越小，S(A,B)越大，也就是說(C,D)離(A,B)越近，相同條件下與待驗證匹配的關(guān)聯(lián)性越強。

根據(jù)式(8)和式(9)，發(fā)現(xiàn)在一對匹配點的匹配關(guān)聯(lián)度計算過程中，對兩點之間的距離進行了多次的計算，而之前這個距離用的是128維特征描述子的歐氏距離來進行表示[11]。由于現(xiàn)在放棄對128維特征描述子的計算，故這個距離必須用平面坐標系的歐氏距離替換。

在匹配關(guān)聯(lián)度中，這個距離主要是為了計算多個匹配之間的相互關(guān)系，也就是多組匹配在原圖中的特征點關(guān)系和在目標圖中的特征點關(guān)系是否相似。在單視頻超分辨率重建的配準過程中，由于相鄰幀與幀之間的特征點位移不是很大，故它們之間的相似性可以通過幾何上的位置關(guān)系來表示。故在此采用平面坐標系的歐氏距離來替代128維特征描述子向量空間中的歐氏距離。

2.3 改進配準算法傳統(tǒng)配準算法的對比

改進的配準算法與傳統(tǒng)配準算法原理上基本一樣，主要也是下面幾個步驟：(1)特征點的提??；(2)進行初始的匹配；(3)歧義以及誤匹配的剔除；(4)計算變換矩陣。其中，改進的配準法主要是在前面3個步驟對傳統(tǒng)配準算法進行了改進，而在步驟(4)和傳統(tǒng)配置算法一樣，都是采用最小二乘法。改進的配準算法與傳統(tǒng)配準算法的比較見表1。

表1 改進配準算法和傳統(tǒng)配準算法比較

3 實驗結(jié)果

實驗中提取了臨近的兩幀彩色視頻的圖像，分別為第70幀和第90幀，并對第90幀的圖像進行了一定程度的仿射變換(圖1(a)，圖1(b))。下面分別采用傳統(tǒng)SIFT配準算法與改進SIFT配準方法進行配準實驗。檢驗配準的準確程度采用配準后的灰度圖與目標灰度圖的圖像像素值相減，如果相減后結(jié)果的絕對值越小，則配準越準確，當相減結(jié)果為0時，也就是說配準前后兩幅圖像完全一樣。

另外，對改進SIFT配準算法和傳統(tǒng)SIFT配準算法性能進行了比較。結(jié)果證明，改進的配準算法得到的配準結(jié)果明顯優(yōu)于傳統(tǒng)配準算法，在初始匹配、歧義和誤匹配剔除方面都明顯占優(yōu)勢，特別是在時間消耗上(表2)。

表2 改進SIFT配準算法和傳統(tǒng)SIFT配準算法性能對比

圖1 傳統(tǒng)SIFT配準和改進SIFT配準實驗

4 結(jié)論與討論

傳統(tǒng)的基于SIFT特征點檢測的配準只是一種通用解決方案，而在單視頻的應用場景下，完全可以放棄對128維特征描述子的計算。該算法通過采用特征點之間的灰度相關(guān)系數(shù)來進行初始匹配，并用平面坐標歐氏距離配合本次研究提出的匹配關(guān)聯(lián)度算法來取代特征描述子進行誤匹配的剔除，大大節(jié)省了計算時間。通過實驗證明，該算法的準確性和效率高等特點彌補了傳統(tǒng)算法在單視頻超分辨率重建視頻的質(zhì)量方面和實時性方面的不足。

[1] 劉彬，葉麗娜.一種基于SIFT特征的序列圖像拼接算法[J].兵工自動化，2009，28(6):76-78.

[2] 周正，雷夢龍，唐少先.基于計算機視覺技術(shù)的番茄葉部病害識別研究[J].安徽農(nóng)業(yè)科學，2013，41(5):2 288-2 289.

[3] Beritelli F，Grasso R.A pattern recognition system for environmental sound classification based on MFCCs and neural networks[C]//2nd International Conference on Signal Processing and Communication Systems，ICSPCS 2008，2008：1-4.

[4] 尹洪武，張步英，王靜.一類非線性拋物方程的高精度有限元分析[J].河北科技師范學院學報，2013，27(2): 53-56.

[5] K Yan,Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE.Computer Society Conference on Computer Vision and Pattern Recognition,2004:506-513.

[6] 曾文鋒，李樹山，王江安.基于仿射變換模型的圖像配準中的平移、旋轉(zhuǎn)和縮放[J].紅外與激光工程，2001，30(1): 18-20，17.

[7] 許錄平，姚靜.一種圖像快速超分辨率復原方法[J].西安電子科技大學學報：自然科學版，2007，34(3): 382-385,408.

[8] 程光權(quán)，成禮智.基于小波的方向自適應圖像插值[J].電子與信息學報，2009，31(2): 265-269.

[9] 陳建輝，王博亮，徐中佑，等.一種自適應最大相關(guān)性數(shù)字圖像插值算法[J].廈門大學學報：自然科學版，2005，44(3): 355-358.

[10] 林虹.基于小波和插值的超分辨率圖像重建算法研究[D].西安：西安電子科技大學，2005.

[11] 申玉發(fā)，張曉昱，趙立強.密度K均值聚類算法及在復雜網(wǎng)絡分析中的應用[J].河北科技師范學院學報，2013，27(4): 32-36.

The SIFT Registration Algorithm of Super Resolution Reconstruction of Single Video

SUN Wen-hua
(School of Information Engineering,Nanchang Institute of Technology,Nanchang Jiangxi,330099,China)

In view of the traditional single video super-resolution reconstruction based on SIFT feature point detecting registration, we found that holding time on the feature matching is too long to meet the requirements of real-time, and the time calculating 128 d features is the longest, thus, we proposed an improved SIFT registration algorithm, which adapted the gray correlation coefficient between the feature points to do the initial matching instead of using the calculation of 128 d feature descriptor, in order to greatly reduce the computing time and increase the speed of feature matching. The experimental results showed that the algorithm is superior to the traditional configuration algorithm on the registration results and time consumption.

feature point detection;feature matching;SIFT algorithm;super resolution reconstruction

南昌工程學院青年基金項目(項目編號：2012KJ020)；江西省科技廳科技計劃項目(項目編號：20141BBE50034)。

2015-06-18

10.3969/J.ISSN.1672-7983.2015.03.014

TP391

A

1672-7983(2015)03-0074-06

孫文華(1981-)，男，碩士，工程師。主要研究方向：計算機網(wǎng)絡管理、視頻跟蹤和圖像處理等。

(責任編輯：朱寶昌，楊靜)