周建平 楊金坤 鄭宇

摘要：文章主要在限定的特征點(diǎn)提取區(qū)域，用改進(jìn)的SIFT特征匹配算法進(jìn)行幀圖像的并行雙向搜索匹配，縮短視頻幀圖像的匹配時(shí)間達(dá)到視頻拼接的目的。

關(guān)鍵詞：SIFT；幀圖像匹配；視頻拼接

中圖分類號(hào)：TP391.41文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1006-8937（2011）22-0070-02

1視頻幀圖像拼接

1.1SIFT算法

SIFT算法由D.G.Lowe 1999年提出，后來Y.Ke進(jìn)行完善。主要有四個(gè)步驟：第一，建立尺度空間。尺度空間理論的主要思想是利用高斯對(duì)原始圖像進(jìn)行尺度變換，獲得圖像多尺度下的尺度空間表示序列。為了得到在不同尺度空間下的穩(wěn)定特征點(diǎn)，主要是構(gòu)建高斯金字塔和DOG金字塔，然后在DOG金字塔里面進(jìn)行極值檢測(cè)。第二，精確定位極值點(diǎn)。由于DOG值對(duì)噪聲和邊緣較敏感，通過上面的方法所檢測(cè)到的局部極值點(diǎn)還要經(jīng)過進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。通過三維二次函數(shù)擬合來精確確定極值點(diǎn)的位置和尺度。第三，特征點(diǎn)指定方向參數(shù)。用直方圖統(tǒng)計(jì)鄰域像素的梯度方向，梯度直方圖的范圍是0～360°，其中每10°一個(gè)柱，總共36個(gè)柱。直方圖的峰值則代表了該特征點(diǎn)處鄰域梯度的主方向，作為該特征點(diǎn)的方向。第四，特征向量的生成。在窗口中用箭頭方向來代表該像素的梯度方向，箭頭長(zhǎng)度來代表梯度模值，在窗口上用一個(gè)圓圈代表高斯加權(quán)的范圍。然后在每4×4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)。

1.2SIFT特征向量的匹配

本文采用歐氏距離作為兩幅圖像間的相似性度量。獲取SIFT特征向量后，采用K-D樹進(jìn)行優(yōu)先搜索來查找每個(gè)特征點(diǎn)的2近似最近鄰特征點(diǎn)。在這兩個(gè)特征點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對(duì)匹配點(diǎn)。

1.3圖像的配準(zhǔn)與融合

在上述的SIFT算法過程中獲得的特征點(diǎn)和有效匹配對(duì)的基礎(chǔ)上，進(jìn)行圖像間變換參數(shù)估計(jì)。以視頻圖像V1為參照系，將視頻圖像V2變換到V1所在的坐標(biāo)系，記變換后的圖像為V2'，其對(duì)應(yīng)關(guān)系如公式（1）所示：

x2'y2'1=t11 t12 t13t21 t22 t23t31 t32 1x2y21=Tx2y21 （1）

式（1）中有8個(gè)參數(shù)，僅需要四對(duì)匹配點(diǎn)即可計(jì)算變換圖像V2'，即V2'=TV2

圖像配準(zhǔn)后，圖像間的變換關(guān)系就得到了唯一確定。本文采用加權(quán)平均的融合方法進(jìn)行圖像平滑過渡，從而達(dá)到圖像的無縫拼接。

2實(shí)際問題框架

本文主要工作是將倒車時(shí)所拍攝的實(shí)時(shí)視頻進(jìn)行拼接，具體步驟如下：

①獲取兩組視頻同一時(shí)刻的幀圖像。在汽車尾部對(duì)稱的兩側(cè)安裝視角范圍大小為60°的攝像頭，并在同一時(shí)刻分別抓取視頻幀圖像。

②對(duì)同一時(shí)刻的幀圖像進(jìn)行拼接。攝像頭的位置和角度固定以后，抓取圖片的相對(duì)位置也就固定，重疊區(qū)域也相對(duì)固定了，如圖 1所示。其中l(wèi)是車身后面兩攝像頭之間的距離，L是攝像頭與車身后面場(chǎng)景的距離，O點(diǎn)是攝像頭視線交叉點(diǎn)，OO1是O點(diǎn)到攝像頭的距離，OO3是O點(diǎn)到駕駛員視線范圍的距離。重疊區(qū)域即A與B之間的部分，其寬度為H，通過公式（2）得到。

（3）

③對(duì)拼接好的幀圖像按時(shí)序進(jìn)行視頻格式的播放。把同一時(shí)刻的兩張幀圖像拼接成的一幅圖像，進(jìn)行校正后按照時(shí)序用視頻格式輸出。此時(shí)駕駛員根據(jù)視頻所反映的車身后面的場(chǎng)景來進(jìn)行倒車。

3算法優(yōu)化

3.1特征點(diǎn)提取區(qū)域的限定

本文中視頻幀圖像的拼接是基于特征點(diǎn)的拼接，提取特征點(diǎn)是拼接的關(guān)鍵，為了達(dá)到視頻拼接的實(shí)時(shí)要求本文提出選取特征點(diǎn)時(shí)只在限定的區(qū)域進(jìn)行，如圖2所示。即右邊攝像頭所獲取的視頻幀圖像其特征點(diǎn)提取區(qū)域即為圖1中CO2之間的部分，它們之間的距離為l/2，左邊攝像頭所獲取的視頻幀圖像其特征點(diǎn)提取區(qū)域即為圖1中O2C'之間的部分，它們之間的距離為l/2。

3.2K-D樹優(yōu)先搜素算法

在SIFT算法中，特征向量的匹配先采用歐氏距離進(jìn)行了相似性度量，再采用K-D樹進(jìn)行優(yōu)先搜索來查找每個(gè)特征點(diǎn)的2近似最近鄰特征點(diǎn)。樹的頂層結(jié)點(diǎn)按一維進(jìn)行劃分，下一層結(jié)點(diǎn)按另一維進(jìn)行劃分，以此類推，各個(gè)維循環(huán)往復(fù)。劃分要使得存儲(chǔ)在子樹中大約一半的結(jié)點(diǎn)落入一側(cè)，而另一半落入另一側(cè)。當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給定的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束。在SIFT算法中實(shí)際運(yùn)用中是采用的一種K-D樹搜索算法基礎(chǔ)上改進(jìn)的搜索算法，即BBF（best-bin-first）算法來搜索樣本特征點(diǎn)的最近鄰和次近鄰特征點(diǎn)，其中BBF搜索算法是在四維空間，即k=4的K-D樹基礎(chǔ)上用一個(gè)優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)以結(jié)點(diǎn)和被查詢結(jié)點(diǎn)距離遞增的順序來搜索結(jié)點(diǎn)，結(jié)點(diǎn)和被查詢結(jié)點(diǎn)的距離是指他們之間的最短距離。

3.3改進(jìn)的K-D樹優(yōu)先搜素算法

本文提出雙向并行搜索的策略，即以特征集A中所有的特征點(diǎn)基準(zhǔn)點(diǎn)在特征集B中采用K-D樹進(jìn)行優(yōu)先搜索，找到與特征點(diǎn)最近鄰和次近鄰的兩點(diǎn)bi1、bi2，如果bi1、bi2之間的距離比值小于某一個(gè)設(shè)定的比例閾值，則接受這一對(duì)匹配點(diǎn)；同時(shí)又以特征集B中的所有特征點(diǎn)為基準(zhǔn)點(diǎn)在特征集A中采用K-D樹進(jìn)行優(yōu)先搜索，找到與特征點(diǎn)最近鄰和次近鄰的兩點(diǎn)aj1、aj2，如果aj1、aj2之間的距離比值小于某一個(gè)設(shè)定的比例閾值，則接受這一對(duì)匹配點(diǎn)。如圖 3所示。

如果以A中的點(diǎn)ai為基準(zhǔn)點(diǎn)搜索時(shí)，在B中找到了點(diǎn)bj與其匹配，并且在B中以bj點(diǎn)為基準(zhǔn)點(diǎn)，在A中進(jìn)行搜索時(shí)，恰好又與A中的點(diǎn)ai匹配的話，則從A中去除點(diǎn)ai，從B中去除點(diǎn)bj；

算法步驟如下：第一，同時(shí)輸入特征點(diǎn)集A和B以及集合總數(shù)m和n，使i=0，j=0。第二，若i＜m或j＜n，或n＜0，則ai去B中找匹配點(diǎn)，bj去A中找匹配點(diǎn)。第三，若ai找到匹配點(diǎn)bp，bj找到匹配點(diǎn)aq則保存這樣的匹配對(duì)。第四，從集合A和B中減去已經(jīng)配對(duì)的點(diǎn)，然后進(jìn)入步驟2。

通過本文改進(jìn)算法的分析，對(duì)兩個(gè)2×2的特征點(diǎn)矩陣進(jìn)行匹配，如圖 4所示。用改進(jìn)的K-D搜索策略，A集合與B集合中的特征點(diǎn)是同時(shí)進(jìn)行，即第一步，a1用4次找到b3匹配，同時(shí)b1用4次找到a4匹配；第二步，a2用4次找到b2匹配，同時(shí)b2用4次找到a2匹配，此時(shí)a2與b2雙向都匹配上了，所以在A中去除a2，在B中去除b2；第三步，a3用3次沒有找到匹配點(diǎn)，同時(shí)b3用3次找到a1匹配，此時(shí)a1與b3構(gòu)成了雙向匹配上了，所以同時(shí)去除a1，b3；第四步，a4用2次找到b1，同時(shí)b4用2次找到a3匹配。至此所有的點(diǎn)搜索完畢，K-D樹搜索方法共用了16次，而改進(jìn)的K-D樹搜索方法共用了13次。

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

本實(shí)驗(yàn)采用兩個(gè)設(shè)置相同焦距、色度等參數(shù)的攝像頭，以某場(chǎng)景進(jìn)行實(shí)驗(yàn)。根據(jù)上述的理論，通過VC++和Opencv編程實(shí)現(xiàn)視頻拼接。

參考文獻(xiàn)：

[1] 周顏軍.數(shù)據(jù)結(jié)構(gòu)[M].長(zhǎng)春:吉林科學(xué)技術(shù)出版社,2003.