基于改進SIFT特征匹配的視頻拼接

周建平 楊金坤 鄭宇

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

關鍵詞：SIFT；幀圖像匹配；視頻拼接

中圖分類號：TP391.41文獻標識碼：A文章編號：1006-8937（2011）22-0070-02

1視頻幀圖像拼接

1.1SIFT算法

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

1.2SIFT特征向量的匹配

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

1.3圖像的配準與融合

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

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

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

圖像配準后，圖像間的變換關系就得到了唯一確定。本文采用加權平均的融合方法進行圖像平滑過渡，從而達到圖像的無縫拼接。

2實際問題框架

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

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

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

（3）

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

3算法優(yōu)化

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

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

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

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

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

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

如果以A中的點ai為基準點搜索時，在B中找到了點bj與其匹配，并且在B中以bj點為基準點，在A中進行搜索時，恰好又與A中的點ai匹配的話，則從A中去除點ai，從B中去除點bj；

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

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

4實驗結果與分析

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

參考文獻：

[1] 周顏軍.數(shù)據(jù)結構[M].長春:吉林科學技術出版社,2003.