阮學(xué)勇

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

基于改進(jìn)型FAST快速視頻拼接技術(shù)

阮學(xué)勇

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

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

FAST算法；角點(diǎn)；BRIEF算法；RANSAC算法；視頻拼接

0 引言

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

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

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

1 系統(tǒng)流程

基于改進(jìn)型FAST特征提取的視頻拼接方法關(guān)鍵流程如下：

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

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

3) 剔除噪聲點(diǎn)，不穩(wěn)定的角點(diǎn)，局部集中的角點(diǎn)；

4) 對角點(diǎn)進(jìn)行描述與匹配；

5) 使用RANSAC算法剔除外點(diǎn)；

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

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

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

下面對關(guān)鍵流程具體分析如圖1所示。

圖1 視頻拼接流程圖

1.1 角點(diǎn)的粗提取

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

圖3 各個算法對圖像采集的角點(diǎn)個數(shù)隨著 圖像尺寸的增加而增加

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

圖4 某一像素點(diǎn)p和他周圍鄰域情況

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

(1)

(2)

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

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

圖5 邊緣響應(yīng)

1.2 角點(diǎn)的精提取

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

1) 自適應(yīng)閾值

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

f=aSTD(I)

(3)

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

2) 提高角點(diǎn)的魯棒性。

FAST算法對單點(diǎn)噪聲響應(yīng)比較強(qiáng)烈，如圖6所示，中心點(diǎn)用0表示，和中心點(diǎn)不相似的周圍像素點(diǎn)用1表示。(a)為真實(shí)角點(diǎn)，(b)為單點(diǎn)噪聲。按照FAST算法，該噪聲點(diǎn)會被誤認(rèn)為是角點(diǎn)?？梢砸肴缦路椒ㄒ种茊吸c(diǎn)噪聲。如圖6(c)、(d)所示，取中心像素點(diǎn)周圍的8個點(diǎn)和中心像素點(diǎn)比較，如果周圍存在和中心像素點(diǎn)相似的像素點(diǎn)，則認(rèn)為該點(diǎn)為真實(shí)的角點(diǎn)，如果周圍像素點(diǎn)和中心像素點(diǎn)不相似，并認(rèn)為該點(diǎn)為噪聲點(diǎn)。可以用式(4)、式(5)進(jìn)行計算。

(4)

(5)

圖6 真實(shí)角點(diǎn)和噪聲點(diǎn)對比圖

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

3) 抑制非極值點(diǎn)

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

(6)

4) 小范圍內(nèi)角點(diǎn)抑制

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

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

(7)

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

1.3 角點(diǎn)描述與匹配

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

(8)

其中：x,y是一對特征點(diǎn)對。

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

1.4 計算變化矩陣和剔除誤匹配點(diǎn)。

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

(9)

(10)

2 算法的實(shí)時性分析

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

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

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

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

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

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

3 實(shí)驗結(jié)果和分析

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

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

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

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

下面是兩種算法實(shí)現(xiàn)圖像拼接的效果。黑色的邊界是兩幅圖像拼接的邊界，對圖9和圖10比較，可以看出兩種算法用于拼接的效果都比較好?？梢妼τ趫D像拼接使用此論文算法效果比較理想。

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

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

4 結(jié)語

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

[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]. 制造業(yè)自動化,2013, 35(3): 18-20.

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

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

[5] 石向榮,樊永生. 一種新的視頻監(jiān)控圖像拼接算法[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ìn)的快速角點(diǎn)探測算法[J]. 紅外與激光工程,2009, 38(6): 1104-1108, 1115.

[13] 張志剛,周明全.一種快速自適應(yīng)的角點(diǎn)檢測算法[J]. 計算機(jī)應(yīng)用與軟件,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] 鄭小寶,王仕成,張金生，等. 紅外圖像實(shí)時生成系統(tǒng)的實(shí)時性實(shí)現(xiàn)[J]. 電訊技術(shù), 2008,48 (11):38-42.

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

[17] 劉明杰,任帥,金城，等. 基于自適應(yīng)投影矩陣的實(shí)時視頻拼接算法[J]. 計算機(jī)應(yīng)用與軟件, 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

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

TH123

B

1671-5276(2015)05-0134-05

2014-03-12