基于改進型FAST快速視頻拼接技術

阮學勇

(福州大學 機械工程及自動化學院，福建 福州 350108)

基于改進型FAST快速視頻拼接技術

阮學勇

(福州大學 機械工程及自動化學院，福建 福州 350108)

為提高視頻拼接的實時性，提出一種改進型FAST快速視頻拼接算法。該算法的過程是先計算圖像的自適應閾值，根據該閾值對角點粗提取，接著對角點精提取，包括抑制單點噪聲、剔除邊緣角點、剔除不穩定的角點。為提高角點匹配速度，利用BRIEF算法對角點進行描述，通過Hamming算法匹配兩幅圖像的角點，接著使用RANSAC算法剔除外點。根據匹配點對計算變換矩陣，拼接每一幀視頻圖像。由于動態視頻拼接產生的背景抖動現象可以通過動靜態結合的拼接方法改善。實驗表明，該拼接算法的速度顯著提高，定位精度較高，能夠滿足實時性要求，而且能夠改善靜態拼接中景深不同而產生的鬼影現象。

FAST算法；角點；BRIEF算法；RANSAC算法；視頻拼接

0 引言

視頻拼接是指對采集到有重合區域的視頻圖像，通過一系列算法融合成清晰無縫的寬場景視頻的技術[1]。視頻拼接技術被廣泛應用于汽車影像，遙感，監控等領域[2-5]。

視頻拼接主要有3種實現方法：1) 單攝像頭拼接：通過云臺的轉動，對攝像頭捕捉的每一幀圖像進行拼接。2) 多攝像頭靜態拼接：同時對每個攝像頭采集一幀圖像，計算圖像之間的變換模型，之后的各攝像頭同時采集的每一幀圖像數據都按照這個變換模型進行變換。其優點是：只需要計算一次變換模型就可以實現視頻拼接，因此運算速度快。缺點是：當攝像頭移動后按照確定的變化模型就不能實現準確的拼接，而且對不同景深的物體拼接會出現鬼影現象。3) 多攝像頭動態拼接：同時對每個攝像頭采集圖像數據，實時計算每一幀圖像之間的變換模型，并按照該模型拼接每一幀圖像。缺點是：由于需要計算每幀圖像之間的變換模型，實時性比第二種略差。優點是：對不同景深的物體拼接時不易產生鬼影現象。

圖像拼接的核心關鍵是圖像的配準。圖像配準方法分為區域配準和特征配準。文中采用的是特征配準的方法。1999年David G.lowe教授提出了尺度不變特征變換-SIFT[6]，該算法的角點定位的精度比較高，支持圖像旋轉和尺度空間的變換，但實時性比較差，不適用于視頻拼接場合。2004年，Y.ke使用主成分分析法對SIFT算法128維描述子降維，提高了存儲利用率和角點提取速度[7]。2008年Bay H, Ess A, Tuyrtelaars T提出了SURF算法[8]，提出了一種圖像積分的思想，再一次改進了SIFT算法的缺點，提高了角點提取速度。以上的算法中為了能夠在各種變化圖像中得到穩定的角點，使用Harris[9]提取角點，建立多尺度空間等。這些方法雖然能夠適應各種圖像變化，但大大影響視頻拼接速度。現研究的就是以提高拼接速度為核心目的。因此提出了基于改進的FAST[10]特征提取圖像拼接方法對圖像拼接。實驗表明該算法大大提高了運算速度，同時角點的精度也不會降低。

1 系統流程

基于改進型FAST特征提取的視頻拼接方法關鍵流程如下：

1) 兩攝像頭同時采集圖像幀；

2) 使用FAST算法對圖像角點粗提取；

3) 剔除噪聲點，不穩定的角點，局部集中的角點；

4) 對角點進行描述與匹配；

5) 使用RANSAC算法剔除外點；

6) 使用圖像變換矩陣計算變換模型；

7) 根據變換模型拼接圖像；

8) 重復1)-7)形成拼接視頻流。

下面對關鍵流程具體分析如圖1所示。

圖1 視頻拼接流程圖

1.1 角點的粗提取

圖2 各個算法對圖像采集角點所消耗的時間 隨著圖像尺寸的增加而增加

圖3 各個算法對圖像采集的角點個數隨著 圖像尺寸的增加而增加

Edward Rosten和 Tom Drummond 論文中提到FAST提取角點的方法是基于假定角點周圍的圖像強度來定義角點的。圖4[5]中給出了假定角點和周圍區域的情況。

圖4 某一像素點p和他周圍鄰域情況

若要判斷一個角點是否為候選角點的方法，通過檢查候選像素周圍一圈像素來決定是否接受這個角點。與中心差異較大的像素點的個數超過像素點總數的3/4，那么認為該點為一個角點。計算公式如式(1)、式(2)：

(1)

(2)

Ixi為圖1圓P上的點的灰度值。Ip為圓心p的灰度值，閾值t決定所能檢測到的角點的最小對比度，也決定所能忽略的噪聲的最大容限，t的大小主要影響檢測到的角點數量。 閾值g決定角點的質量，即角點的銳利程度，通常情況下選取g值為12。

N的值只要大于12即可將p點選為是候選角點。通過把這些點限定在以p點為圓心的連續的圓弧上，可以抑制圖5所示的邊緣響應。

圖5 邊緣響應

1.2 角點的精提取

對于以上使用的FAST算法存在很多問題：角點提取依賴一個閾值，魯棒性較差，角點定位不夠精確，存在偽角點等。因此引入一些方法解決這些問題。

1) 自適應閾值

對于FAST算法，t值的選取需要人為的確定，因此可以提出一種自適應閾值的方法，自動確定閾值t。一般而言，自適應閾值都是通過圖像的全局對比度和角點數目系數來估計。按照對比度定義計算相對來說比較復雜。文獻[12] 給出了一種自適應閾值的方法。是通過將采集圖像最大10個灰度值和最小10個灰度值之差作為對比度來運算閾值。該方法優點是簡單，缺點是僅使用局部的幾個點計算閾值缺乏準確性，容易受到噪聲干擾。因此，可以引用文獻[13]提出的方法。采用圖像的標準差作為對比度，計算相對比較容易，可靠性好。具體如式(3)：

f=aSTD(I)

(3)

STD(I)代表整幅圖像的灰度值標準差，系數a決定了可檢測的角點數量。通過實驗表明，系數a取值為0.01較為合理，既保證角點數量，又能抑制偽角點的產生。

2) 提高角點的魯棒性。

FAST算法對單點噪聲響應比較強烈，如圖6所示，中心點用0表示，和中心點不相似的周圍像素點用1表示。(a)為真實角點，(b)為單點噪聲。按照FAST算法，該噪聲點會被誤認為是角點。可以引入如下方法抑制單點噪聲。如圖6(c)、(d)所示，取中心像素點周圍的8個點和中心像素點比較，如果周圍存在和中心像素點相似的像素點，則認為該點為真實的角點，如果周圍像素點和中心像素點不相似，并認為該點為噪聲點。可以用式(4)、式(5)進行計算。

(4)

(5)

圖6 真實角點和噪聲點對比圖

Vo為中心像素點的像素值，Vi為中心像素點周圍像素點的像素值，ε為一閾值，需要人為給定，文中選為60。

3) 抑制非極值點

對2維空間函數S(x)進行曲線擬合，將S(x)函數泰勒展開：

(6)

4) 小范圍內角點抑制

使用FAST提取角點時會產生很多相鄰角點，需要采用一些方法將其剔除。先將候選角點按照角點量從大到小排序，按順序提取角點，確保與該角點街區距離為D的范圍內不存在其他角點，如果存在，則將其剔除。如式(7)：

|xi-xj|≥D且 |yi-yj|≥D(0≤i

(7)

其中：i,j為角點的序號，N為角點數量， (xj,yj) 為角點的坐標。滿足式(7)則保留角點j，不滿足式(7)則刪除角點j。

1.3 角點描述與匹配

角點的描述方法很多。SIFT算法中角點描述是基于鄰域分布法。通過計算角點周圍像素點梯度幅值和方向，最后形成128維描述子，用于描述該角點。SURF是計算鄰域x,y方向上的Harr小波分布，這樣做能夠借助積分圖加速運算，而且使用的是64維描述子，大大提高了運算速度。BRIEF(binary robust independent elementary features)[14]算法是由EPFL提出的。主要原理就是在角點附近隨機選取若干點對，將這些點對的灰度值的大小，組合成一個二進制串，并將這個二進制串作為該角點的特征描述子。為了實現視頻快速拼接，采用BRIEF進行特征描述。如式(8)：

(8)

其中：x,y是一對特征點對。

角點匹配是通過距離法實現的。即通過計算角點間距離判斷兩點間的匹配程度，尋找最佳匹配點對。常用的距離法有歐氏距離法，Hausdorff距離法，Hamming距離法等。在文中的BRIEF描述子使用的是32維的，采用Hamming距離法計算任意兩個描述子每一維之間的對應位不同數字的個數，以此來判斷描述子的匹配程度。如果對應位不同的個數越少，則兩描述子越匹配。采用BRIEF 和Hamming算法組合能夠提高視頻拼接的速度。

1.4 計算變化矩陣和剔除誤匹配點。

在匹配點對中隨機選取3個角點通過線性變換式(9)計算出變換矩陣H。計算其余匹配點通過矩陣H變換后與對應匹配點之間的距離，按照RANSAC算法要求的距離閾值分類內點和外點(文中將距離閾值定義為一個像素距離，若匹配點按照矩陣H變換后與對應匹配點之間的距離小于1個像素則認為該匹配點為內點，否則為外點)。內點按照最小二乘法估計式(10)變換矩陣H’取代原來的矩陣H。計算其余的匹配點通過矩陣H’變換后與對應點的距離，按照RANSAC算法要求的距離閾值分類內點和外點。重復以上步驟直到前后兩次計算的內點個數差不超過1。那么就將該矩陣當做匹配點的變換矩陣。最后根據變換矩陣計算拼接兩幅圖像。

(9)

(10)

2 算法的實時性分析

所謂實時性是指能夠在限定時間內執行完規定的功能并對外部的異步事件做出響應的能力。實時性的強弱是以完成規定功能和做出響應時間的長短來衡量的[15]。實時視頻拼接算法主要重視視頻拼接的準確性和實時性，視頻拼接的準確性依賴于圖像之間角點對匹配的準確性，拼接的實時性依賴于算法的速度。影響視頻拼接的實時性因素有圖像的尺寸，算法的運算速度。

對于圖像的尺寸，如表1所示，采用同種算法，圖像尺寸越小，所用的時間也越少。但過小的圖像尺寸不利于角點的提取，而且使視覺效果變差。因此，綜合考慮，采用320×240大小的圖像。

對于算法的運行速度，通過采集100，200，500 幀圖像所消耗的總時間來計算平均每幀用時，從表2中可以看出SURF算法用時是文中算法用時的10倍左右，可見對于實時性要求較高的場合可以采用此算法。

表1 文中算法對于不同尺寸圖像用時比較

表2 SURF算法和文中算法的用時比較

對于文中算法而言，如果每次拼接圖像都執行算法的每個步驟的話，每秒只能形成大約8幀的視頻流，這樣觀測視頻會很不流暢。對于提高視頻流速度，文獻[16]提出可以通過提取RIO區域提高視頻拼接速度。文獻[17]提出一種用光流法跟蹤匹配點對的方法，對跟蹤得到的點對由投影矩陣計算得到圖像誤差。若誤差超過一定閾值或跟蹤點對的數目太少，后臺階段就會再次執行。一旦得到了投影矩陣，就采取一種非線性的融合算法對視頻進行融合。在文中采用如下方法，即引入一段判斷程序，如果前后兩幀圖像數據有發生較大變化或者攝像頭有移動就啟動該算法計算變換矩陣再拼接圖像，否則采用前一次的變換矩陣拼接圖像。這樣能夠使視頻流速度達到每秒25幀。

3 實驗結果和分析

實驗采用的開發環境是visual stdio2008 + OpenCv2.4.3，處理器為AMD Athlon(tm) Ⅱx2 215 processor 2.71 GHz，內存為1.75GHz。使用雙攝像頭同步采集圖像，攝像頭型號是藍色妖姬T91，圖像尺寸為320×240，為了刪除拼接后的空白部分，拼接后的圖像尺寸為380×220。下面針對使用此論文算法和SURF算法進行圖像匹配和拼接的效果對比。

對于SURF算法和文中算法采集的角點都以圓圈標記。匹配點使用白色圓圈標記，未匹配點使用黑色圓圈標記。角點按照匹配度排序，選取匹配度最高的25對匹配點用直線連接，如圖7和圖8所示。

圖7 FAST算法用于圖像匹配的效果

圖8 SURF算法用于圖像匹配的效果

下面是兩種算法實現圖像拼接的效果。黑色的邊界是兩幅圖像拼接的邊界，對圖9和圖10比較，可以看出兩種算法用于拼接的效果都比較好。可見對于圖像拼接使用此論文算法效果比較理想。

圖9 FAST算法用于拼接的效果圖

圖10 SURF算法用于拼接的效果圖

4 結語

實驗表明，文中算法可用于實時性要求較高的場合。在視頻拼接中，很少需要考慮尺度空間上的問題。因此，相對于SURF，SIFT算法而言，文中算法犧牲了尺度不變性，大大提高算法的速度。如果視頻前后兩幀圖像有較大變化或者攝像頭有移動則會啟動拼接算法計算變換矩陣，由于每對待拼接的圖像使用的變換矩陣都不一致，因此經每對圖像拼接后形成的視頻流存在背景輕微抖動現象。

[1] ZOU Xiaochun, HE Mingyi, ZHAO Xinbo, et a1. A robust mosaic panorama technique for vedio [C] //2nd international Conference on Computer engineering and Technology, 2010: 641-644.

[2] 李新,葛小燕. 基于SIFT的低空遙感圖像拼接[J]. 制造業自動化,2013, 35(3): 18-20.

[3] 殷瑞靜,陳水利. 基于ASIFT的低空遙感影像拼接技術[J]. 集美大學學報：自然科學版, 2012,17(2): 153-160.

[4] 周建平,楊金坤,鄭宇，等. 基于改進SIFT特征匹配的視頻拼接——在倒車系統中的應用[J]. 企業技術開發, 2011, (11):70-71.

[5] 石向榮,樊永生. 一種新的視頻監控圖像拼接算法[J]. 電子測試, 2011,12(3): 8-11,15.

[6] BROWNM, LOWEDG. Automatic panoramic image stitching using invariant features [J]. International Journal of Computer Vision, 2007,4(1): 59-73.

[7] Ke, Y., and Sukthankar, R. 2004. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors. Proc. CVPR2:506-513.

[8] Herbert Bay, Andreas Ess, Tinne Tuytelaars. SURF: Speeded up robust features[J]. Computer Vision and Image Understanding, 2008, 110 (3): 346-359.

[9] C. Harris，M. Stephens. A Combined Corner and Edge Detector[C]. Proc of 4thAlvey Vision Conference, 1988.

[10] E. ROSTEN, T. DRUMMOND. Maching learning for high-speed corner detection[C]//Lecture Notes in Computer Science, 2006, 3951: 430-443.

[11] SMITH S M, BRADY M. SUSAN - a new approach to low level image processing[J]. Internetional Journal of Computer Vision, 1997,23(1): 45 - 78.

[12] 燕鵬,安如. 基于FAST改進的快速角點探測算法[J]. 紅外與激光工程,2009, 38(6): 1104-1108, 1115.

[13] 張志剛,周明全.一種快速自適應的角點檢測算法[J]. 計算機應用與軟件,2007,24(7):9-11.

[14] Calonder M, et al. Brief: binary robust independent elementary features [A]. 11thEuropean Conference on Computer Vision [C], Heraklion, Crete, 2010:778-792.

[15] 鄭小寶,王仕成,張金生，等. 紅外圖像實時生成系統的實時性實現[J]. 電訊技術, 2008,48 (11):38-42.

[16] 首照宇, 歐陽寧, 張華俊，等. 基于SURF和動態ROI的實時視頻拼接[J]. 計算機工程與設計,2013,34(3):998-1003.

[17] 劉明杰,任帥,金城，等. 基于自適應投影矩陣的實時視頻拼接算法[J]. 計算機應用與軟件, 2012,29(5): 81-85.

Improved-based FAST Method Used in Video Stitching Technique

RUAN Xueyong

(College of Mechanical Engineering and Automation, Fuzhou University, Fuzhou 350108,China)

In order to enhance real-time video stitching, this paper proposes the improved FAST method which is used to stitch video image. The process of this method is as follows. self-adapting threshold is calculated to detect and picks up enough feature points. those points are extracted through suppressing noise of single pixel, removing border and unstable feature points. For the purpose of increasing speed of match feature points, BRIEF method is used to decribe feature points. Here hamming method operates to match the feature points of two relevant images. The outline feature points is removed by RANSAC method. The match feature point pairs are used to compute homography matrix, then each frame of video is stitched. Background trembling coused by dynamic video stitching method can be reduced through combining dynamic and static stitching method. The experiments show that improved-based FAST method is of higher positional accuracy and satisfied with real-time requirements. It can be used to improve the speed of stitching, decrease ghosted image created by static stitching of different deep view.

FAST method; feature points; BRIEF method; RANSAC method; video stitching

阮學勇(1989-)，男，福建福州人，碩士研究生，研究方向為圖像處理。

TH123

B

1671-5276(2015)05-0134-05

2014-03-12