孫 文 華

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

?

面向單視頻超分辨率重建的改進(jìn)的SIFT配準(zhǔn)算法

孫 文 華

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

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

特征點(diǎn)檢測(cè);特征匹配;SIFT配準(zhǔn)算法;超分辨率重建

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

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

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

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

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

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

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

u=Ax+By+C

v=Dx+Ey+F

(1)

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

(2)

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

(3)

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

(4)

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

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

假設(shè)：

H×X1=X2

(5)

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

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

(6)

2 改進(jìn)的SIFT特征點(diǎn)匹配

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

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

2.1 改進(jìn)的初始匹配

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

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

(7)

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

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

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

Step 3：假設(shè)Cij>0.95，則認(rèn)為Pi和Pj是一對(duì)初始匹配。

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

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

Step 1：選擇候選特征點(diǎn)，將目標(biāo)圖中與Pi的平面坐標(biāo)歐氏距離比r小的作為候選特征點(diǎn)。

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

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

Step 4：假設(shè)Cij>0.95，則認(rèn)為Pi和Pj是一對(duì)初始匹配。

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

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

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

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

(8)

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

(9)

(10)

其中，dr代表相對(duì)距離差，ε為相對(duì)距離偏差的一個(gè)閾值，在此取ε=0.3。當(dāng)dr=0時(shí)，即(A,C)和(B,D)相對(duì)距離差為零時(shí)，δ(A,B,C,D)=1，這時(shí)在其它因素相同的情況下，匹配點(diǎn)對(duì)(C,D)與(A,B)的關(guān)聯(lián)性最強(qiáng)，隨著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)越近，相同條件下與待驗(yàn)證匹配的關(guān)聯(lián)性越強(qiáng)。

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

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

2.3 改進(jìn)配準(zhǔn)算法傳統(tǒng)配準(zhǔn)算法的對(duì)比

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

表1 改進(jìn)配準(zhǔn)算法和傳統(tǒng)配準(zhǔn)算法比較

3 實(shí)驗(yàn)結(jié)果

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

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

表2 改進(jìn)SIFT配準(zhǔn)算法和傳統(tǒng)SIFT配準(zhǔn)算法性能對(duì)比

圖1 傳統(tǒng)SIFT配準(zhǔn)和改進(jìn)SIFT配準(zhǔn)實(shí)驗(yàn)

4 結(jié)論與討論

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

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

[2] 周正，雷夢(mèng)龍，唐少先.基于計(jì)算機(jī)視覺技術(shù)的番茄葉部病害識(shí)別研究[J].安徽農(nóng)業(yè)科學(xué)，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].河北科技師范學(xué)院學(xué)報(bào)，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] 曾文鋒，李樹山，王江安.基于仿射變換模型的圖像配準(zhǔn)中的平移、旋轉(zhuǎn)和縮放[J].紅外與激光工程，2001，30(1): 18-20，17.

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

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

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

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

[11] 申玉發(fā)，張曉昱，趙立強(qiáng).密度K均值聚類算法及在復(fù)雜網(wǎng)絡(luò)分析中的應(yīng)用[J].河北科技師范學(xué)院學(xué)報(bào)，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

南昌工程學(xué)院青年基金項(xiàng)目(項(xiàng)目編號(hào)：2012KJ020)；江西省科技廳科技計(jì)劃項(xiàng)目(項(xiàng)目編號(hào)：20141BBE50034)。

2015-06-18

10.3969/J.ISSN.1672-7983.2015.03.014

TP391

A

1672-7983(2015)03-0074-06

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

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