阮學(xué)勇
(福州大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院,福建 福州 350108)
基于改進(jìn)型FAST快速視頻拼接技術(shù)
阮學(xué)勇
(福州大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院,福建 福州 350108)
為提高視頻拼接的實(shí)時(shí)性,提出一種改進(jìn)型FAST快速視頻拼接算法。該算法的過(guò)程是先計(jì)算圖像的自適應(yīng)閾值,根據(jù)該閾值對(duì)角點(diǎn)粗提取,接著對(duì)角點(diǎn)精提取,包括抑制單點(diǎn)噪聲、剔除邊緣角點(diǎn)、剔除不穩(wěn)定的角點(diǎn)。為提高角點(diǎn)匹配速度,利用BRIEF算法對(duì)角點(diǎn)進(jìn)行描述,通過(guò)Hamming算法匹配兩幅圖像的角點(diǎn),接著使用RANSAC算法剔除外點(diǎn)。根據(jù)匹配點(diǎn)對(duì)計(jì)算變換矩陣,拼接每一幀視頻圖像。由于動(dòng)態(tài)視頻拼接產(chǎn)生的背景抖動(dòng)現(xiàn)象可以通過(guò)動(dòng)靜態(tài)結(jié)合的拼接方法改善。實(shí)驗(yàn)表明,該拼接算法的速度顯著提高,定位精度較高,能夠滿足實(shí)時(shí)性要求,而且能夠改善靜態(tài)拼接中景深不同而產(chǎn)生的鬼影現(xiàn)象。
FAST算法;角點(diǎn);BRIEF算法;RANSAC算法;視頻拼接
視頻拼接是指對(duì)采集到有重合區(qū)域的視頻圖像,通過(guò)一系列算法融合成清晰無(wú)縫的寬場(chǎng)景視頻的技術(shù)[1]。視頻拼接技術(shù)被廣泛應(yīng)用于汽車(chē)影像,遙感,監(jiān)控等領(lǐng)域[2-5]。
視頻拼接主要有3種實(shí)現(xiàn)方法:1) 單攝像頭拼接:通過(guò)云臺(tái)的轉(zhuǎn)動(dòng),對(duì)攝像頭捕捉的每一幀圖像進(jìn)行拼接。2) 多攝像頭靜態(tài)拼接:同時(shí)對(duì)每個(gè)攝像頭采集一幀圖像,計(jì)算圖像之間的變換模型,之后的各攝像頭同時(shí)采集的每一幀圖像數(shù)據(jù)都按照這個(gè)變換模型進(jìn)行變換。其優(yōu)點(diǎn)是:只需要計(jì)算一次變換模型就可以實(shí)現(xiàn)視頻拼接,因此運(yùn)算速度快。缺點(diǎn)是:當(dāng)攝像頭移動(dòng)后按照確定的變化模型就不能實(shí)現(xiàn)準(zhǔn)確的拼接,而且對(duì)不同景深的物體拼接會(huì)出現(xiàn)鬼影現(xiàn)象。3) 多攝像頭動(dòng)態(tài)拼接:同時(shí)對(duì)每個(gè)攝像頭采集圖像數(shù)據(jù),實(shí)時(shí)計(jì)算每一幀圖像之間的變換模型,并按照該模型拼接每一幀圖像。缺點(diǎn)是:由于需要計(jì)算每幀圖像之間的變換模型,實(shí)時(shí)性比第二種略差。優(yōu)點(diǎn)是:對(duì)不同景深的物體拼接時(shí)不易產(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í)時(shí)性比較差,不適用于視頻拼接場(chǎng)合。2004年,Y.ke使用主成分分析法對(duì)SIFT算法128維描述子降維,提高了存儲(chǔ)利用率和角點(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)各種圖像變化,但大大影響視頻拼接速度。現(xiàn)研究的就是以提高拼接速度為核心目的。因此提出了基于改進(jìn)的FAST[10]特征提取圖像拼接方法對(duì)圖像拼接。實(shí)驗(yàn)表明該算法大大提高了運(yùn)算速度,同時(shí)角點(diǎn)的精度也不會(huì)降低。
基于改進(jìn)型FAST特征提取的視頻拼接方法關(guān)鍵流程如下:
1) 兩攝像頭同時(shí)采集圖像幀;
2) 使用FAST算法對(duì)圖像角點(diǎn)粗提?。?/p>
3) 剔除噪聲點(diǎn),不穩(wěn)定的角點(diǎn),局部集中的角點(diǎn);
4) 對(duì)角點(diǎn)進(jìn)行描述與匹配;
5) 使用RANSAC算法剔除外點(diǎn);
6) 使用圖像變換矩陣計(jì)算變換模型;
7) 根據(jù)變換模型拼接圖像;
8) 重復(fù)1)-7)形成拼接視頻流。
下面對(duì)關(guān)鍵流程具體分析如圖1所示。
圖1 視頻拼接流程圖
1.1 角點(diǎn)的粗提取
圖2 各個(gè)算法對(duì)圖像采集角點(diǎn)所消耗的時(shí)間 隨著圖像尺寸的增加而增加
圖3 各個(gè)算法對(duì)圖像采集的角點(diǎn)個(gè)數(shù)隨著 圖像尺寸的增加而增加
Edward Rosten和 Tom Drummond 論文中提到FAST提取角點(diǎn)的方法是基于假定角點(diǎn)周?chē)膱D像強(qiáng)度來(lái)定義角點(diǎn)的。圖4[5]中給出了假定角點(diǎn)和周?chē)鷧^(qū)域的情況。
圖4 某一像素點(diǎn)p和他周?chē)徲蚯闆r
若要判斷一個(gè)角點(diǎn)是否為候選角點(diǎn)的方法,通過(guò)檢查候選像素周?chē)蝗ο袼貋?lái)決定是否接受這個(gè)角點(diǎn)。與中心差異較大的像素點(diǎn)的個(gè)數(shù)超過(guò)像素點(diǎn)總數(shù)的3/4,那么認(rèn)為該點(diǎn)為一個(gè)角點(diǎn)。計(jì)算公式如式(1)、式(2):
(1)
(2)
Ixi為圖1圓P上的點(diǎn)的灰度值。Ip為圓心p的灰度值,閾值t決定所能檢測(cè)到的角點(diǎn)的最小對(duì)比度,也決定所能忽略的噪聲的最大容限,t的大小主要影響檢測(cè)到的角點(diǎn)數(shù)量。 閾值g決定角點(diǎn)的質(zhì)量,即角點(diǎn)的銳利程度,通常情況下選取g值為12。
N的值只要大于12即可將p點(diǎn)選為是候選角點(diǎn)。通過(guò)把這些點(diǎn)限定在以p點(diǎn)為圓心的連續(xù)的圓弧上,可以抑制圖5所示的邊緣響應(yīng)。
圖5 邊緣響應(yīng)
1.2 角點(diǎn)的精提取
對(duì)于以上使用的FAST算法存在很多問(wèn)題:角點(diǎn)提取依賴一個(gè)閾值,魯棒性較差,角點(diǎn)定位不夠精確,存在偽角點(diǎn)等。因此引入一些方法解決這些問(wèn)題。
1) 自適應(yīng)閾值
對(duì)于FAST算法,t值的選取需要人為的確定,因此可以提出一種自適應(yīng)閾值的方法,自動(dòng)確定閾值t。一般而言,自適應(yīng)閾值都是通過(guò)圖像的全局對(duì)比度和角點(diǎn)數(shù)目系數(shù)來(lái)估計(jì)。按照對(duì)比度定義計(jì)算相對(duì)來(lái)說(shuō)比較復(fù)雜。文獻(xiàn)[12] 給出了一種自適應(yīng)閾值的方法。是通過(guò)將采集圖像最大10個(gè)灰度值和最小10個(gè)灰度值之差作為對(duì)比度來(lái)運(yùn)算閾值。該方法優(yōu)點(diǎn)是簡(jiǎn)單,缺點(diǎn)是僅使用局部的幾個(gè)點(diǎn)計(jì)算閾值缺乏準(zhǔn)確性,容易受到噪聲干擾。因此,可以引用文獻(xiàn)[13]提出的方法。采用圖像的標(biāo)準(zhǔn)差作為對(duì)比度,計(jì)算相對(duì)比較容易,可靠性好。具體如式(3):
f=aSTD(I)
(3)
STD(I)代表整幅圖像的灰度值標(biāo)準(zhǔn)差,系數(shù)a決定了可檢測(cè)的角點(diǎn)數(shù)量。通過(guò)實(shí)驗(yàn)表明,系數(shù)a取值為0.01較為合理,既保證角點(diǎn)數(shù)量,又能抑制偽角點(diǎn)的產(chǎn)生。
2) 提高角點(diǎn)的魯棒性。
FAST算法對(duì)單點(diǎn)噪聲響應(yīng)比較強(qiáng)烈,如圖6所示,中心點(diǎn)用0表示,和中心點(diǎn)不相似的周?chē)袼攸c(diǎn)用1表示。(a)為真實(shí)角點(diǎn),(b)為單點(diǎn)噪聲。按照FAST算法,該噪聲點(diǎn)會(huì)被誤認(rèn)為是角點(diǎn)。可以引入如下方法抑制單點(diǎn)噪聲。如圖6(c)、(d)所示,取中心像素點(diǎn)周?chē)?個(gè)點(diǎn)和中心像素點(diǎn)比較,如果周?chē)嬖诤椭行南袼攸c(diǎn)相似的像素點(diǎn),則認(rèn)為該點(diǎn)為真實(shí)的角點(diǎn),如果周?chē)袼攸c(diǎn)和中心像素點(diǎn)不相似,并認(rèn)為該點(diǎn)為噪聲點(diǎn)。可以用式(4)、式(5)進(jìn)行計(jì)算。
(4)
(5)
圖6 真實(shí)角點(diǎn)和噪聲點(diǎn)對(duì)比圖
Vo為中心像素點(diǎn)的像素值,Vi為中心像素點(diǎn)周?chē)袼攸c(diǎn)的像素值,ε為一閾值,需要人為給定,文中選為60。
3) 抑制非極值點(diǎn)
對(duì)2維空間函數(shù)S(x)進(jìn)行曲線擬合,將S(x)函數(shù)泰勒展開(kāi):
(6)
4) 小范圍內(nèi)角點(diǎn)抑制
使用FAST提取角點(diǎn)時(shí)會(huì)產(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)的序號(hào),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)描述是基于鄰域分布法。通過(guò)計(jì)算角點(diǎn)周?chē)袼攸c(diǎn)梯度幅值和方向,最后形成128維描述子,用于描述該角點(diǎn)。SURF是計(jì)算鄰域x,y方向上的Harr小波分布,這樣做能夠借助積分圖加速運(yùn)算,而且使用的是64維描述子,大大提高了運(yùn)算速度。BRIEF(binary robust independent elementary features)[14]算法是由EPFL提出的。主要原理就是在角點(diǎn)附近隨機(jī)選取若干點(diǎn)對(duì),將這些點(diǎn)對(duì)的灰度值的大小,組合成一個(gè)二進(jìn)制串,并將這個(gè)二進(jìn)制串作為該角點(diǎn)的特征描述子。為了實(shí)現(xiàn)視頻快速拼接,采用BRIEF進(jìn)行特征描述。如式(8): (8) 其中:x,y是一對(duì)特征點(diǎn)對(duì)。 角點(diǎn)匹配是通過(guò)距離法實(shí)現(xiàn)的。即通過(guò)計(jì)算角點(diǎn)間距離判斷兩點(diǎn)間的匹配程度,尋找最佳匹配點(diǎn)對(duì)。常用的距離法有歐氏距離法,Hausdorff距離法,Hamming距離法等。在文中的BRIEF描述子使用的是32維的,采用Hamming距離法計(jì)算任意兩個(gè)描述子每一維之間的對(duì)應(yīng)位不同數(shù)字的個(gè)數(shù),以此來(lái)判斷描述子的匹配程度。如果對(duì)應(yīng)位不同的個(gè)數(shù)越少,則兩描述子越匹配。采用BRIEF 和Hamming算法組合能夠提高視頻拼接的速度。 1.4 計(jì)算變化矩陣和剔除誤匹配點(diǎn)。 在匹配點(diǎn)對(duì)中隨機(jī)選取3個(gè)角點(diǎn)通過(guò)線性變換式(9)計(jì)算出變換矩陣H。計(jì)算其余匹配點(diǎn)通過(guò)矩陣H變換后與對(duì)應(yīng)匹配點(diǎn)之間的距離,按照RANSAC算法要求的距離閾值分類(lèi)內(nèi)點(diǎn)和外點(diǎn)(文中將距離閾值定義為一個(gè)像素距離,若匹配點(diǎn)按照矩陣H變換后與對(duì)應(yīng)匹配點(diǎn)之間的距離小于1個(gè)像素則認(rèn)為該匹配點(diǎn)為內(nèi)點(diǎn),否則為外點(diǎn))。內(nèi)點(diǎn)按照最小二乘法估計(jì)式(10)變換矩陣H’取代原來(lái)的矩陣H。計(jì)算其余的匹配點(diǎn)通過(guò)矩陣H’變換后與對(duì)應(yīng)點(diǎn)的距離,按照RANSAC算法要求的距離閾值分類(lèi)內(nèi)點(diǎn)和外點(diǎn)。重復(fù)以上步驟直到前后兩次計(jì)算的內(nèi)點(diǎn)個(gè)數(shù)差不超過(guò)1。那么就將該矩陣當(dāng)做匹配點(diǎn)的變換矩陣。最后根據(jù)變換矩陣計(jì)算拼接兩幅圖像。 (9) (10) 所謂實(shí)時(shí)性是指能夠在限定時(shí)間內(nèi)執(zhí)行完規(guī)定的功能并對(duì)外部的異步事件做出響應(yīng)的能力。實(shí)時(shí)性的強(qiáng)弱是以完成規(guī)定功能和做出響應(yīng)時(shí)間的長(zhǎng)短來(lái)衡量的[15]。實(shí)時(shí)視頻拼接算法主要重視視頻拼接的準(zhǔn)確性和實(shí)時(shí)性,視頻拼接的準(zhǔn)確性依賴于圖像之間角點(diǎn)對(duì)匹配的準(zhǔn)確性,拼接的實(shí)時(shí)性依賴于算法的速度。影響視頻拼接的實(shí)時(shí)性因素有圖像的尺寸,算法的運(yùn)算速度。 對(duì)于圖像的尺寸,如表1所示,采用同種算法,圖像尺寸越小,所用的時(shí)間也越少。但過(guò)小的圖像尺寸不利于角點(diǎn)的提取,而且使視覺(jué)效果變差。因此,綜合考慮,采用320×240大小的圖像。 對(duì)于算法的運(yùn)行速度,通過(guò)采集100,200,500 幀圖像所消耗的總時(shí)間來(lái)計(jì)算平均每幀用時(shí),從表2中可以看出SURF算法用時(shí)是文中算法用時(shí)的10倍左右,可見(jiàn)對(duì)于實(shí)時(shí)性要求較高的場(chǎng)合可以采用此算法。 表1 文中算法對(duì)于不同尺寸圖像用時(shí)比較 表2 SURF算法和文中算法的用時(shí)比較 對(duì)于文中算法而言,如果每次拼接圖像都執(zhí)行算法的每個(gè)步驟的話,每秒只能形成大約8幀的視頻流,這樣觀測(cè)視頻會(huì)很不流暢。對(duì)于提高視頻流速度,文獻(xiàn)[16]提出可以通過(guò)提取RIO區(qū)域提高視頻拼接速度。文獻(xiàn)[17]提出一種用光流法跟蹤匹配點(diǎn)對(duì)的方法,對(duì)跟蹤得到的點(diǎn)對(duì)由投影矩陣計(jì)算得到圖像誤差。若誤差超過(guò)一定閾值或跟蹤點(diǎn)對(duì)的數(shù)目太少,后臺(tái)階段就會(huì)再次執(zhí)行。一旦得到了投影矩陣,就采取一種非線性的融合算法對(duì)視頻進(jìn)行融合。在文中采用如下方法,即引入一段判斷程序,如果前后兩幀圖像數(shù)據(jù)有發(fā)生較大變化或者攝像頭有移動(dòng)就啟動(dòng)該算法計(jì)算變換矩陣再拼接圖像,否則采用前一次的變換矩陣拼接圖像。這樣能夠使視頻流速度達(dá)到每秒25幀。 實(shí)驗(yàn)采用的開(kāi)發(fā)環(huán)境是visual stdio2008 + OpenCv2.4.3,處理器為AMD Athlon(tm) Ⅱx2 215 processor 2.71 GHz,內(nèi)存為1.75GHz。使用雙攝像頭同步采集圖像,攝像頭型號(hào)是藍(lán)色妖姬T91,圖像尺寸為320×240,為了刪除拼接后的空白部分,拼接后的圖像尺寸為380×220。下面針對(duì)使用此論文算法和SURF算法進(jìn)行圖像匹配和拼接的效果對(duì)比。 對(duì)于SURF算法和文中算法采集的角點(diǎn)都以圓圈標(biāo)記。匹配點(diǎn)使用白色圓圈標(biāo)記,未匹配點(diǎn)使用黑色圓圈標(biāo)記。角點(diǎn)按照匹配度排序,選取匹配度最高的25對(duì)匹配點(diǎn)用直線連接,如圖7和圖8所示。 圖7 FAST算法用于圖像匹配的效果 圖8 SURF算法用于圖像匹配的效果 下面是兩種算法實(shí)現(xiàn)圖像拼接的效果。黑色的邊界是兩幅圖像拼接的邊界,對(duì)圖9和圖10比較,可以看出兩種算法用于拼接的效果都比較好。可見(jiàn)對(duì)于圖像拼接使用此論文算法效果比較理想。 圖9 FAST算法用于拼接的效果圖 圖10 SURF算法用于拼接的效果圖 實(shí)驗(yàn)表明,文中算法可用于實(shí)時(shí)性要求較高的場(chǎng)合。在視頻拼接中,很少需要考慮尺度空間上的問(wèn)題。因此,相對(duì)于SURF,SIFT算法而言,文中算法犧牲了尺度不變性,大大提高算法的速度。如果視頻前后兩幀圖像有較大變化或者攝像頭有移動(dòng)則會(huì)啟動(dòng)拼接算法計(jì)算變換矩陣,由于每對(duì)待拼接的圖像使用的變換矩陣都不一致,因此經(jīng)每對(duì)圖像拼接后形成的視頻流存在背景輕微抖動(dò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è)自動(dòng)化,2013, 35(3): 18-20. [3] 殷瑞靜,陳水利. 基于ASIFT的低空遙感影像拼接技術(shù)[J]. 集美大學(xué)學(xué)報(bào):自然科學(xué)版, 2012,17(2): 153-160. [4] 周建平,楊金坤,鄭宇,等. 基于改進(jìn)SIFT特征匹配的視頻拼接——在倒車(chē)系統(tǒng)中的應(yīng)用[J]. 企業(yè)技術(shù)開(kāi)發(fā), 2011, (11):70-71. [5] 石向榮,樊永生. 一種新的視頻監(jiān)控圖像拼接算法[J]. 電子測(cè)試, 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)探測(cè)算法[J]. 紅外與激光工程,2009, 38(6): 1104-1108, 1115. [13] 張志剛,周明全.一種快速自適應(yīng)的角點(diǎn)檢測(cè)算法[J]. 計(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í)時(shí)生成系統(tǒng)的實(shí)時(shí)性實(shí)現(xiàn)[J]. 電訊技術(shù), 2008,48 (11):38-42. [16] 首照宇, 歐陽(yáng)寧, 張華俊,等. 基于SURF和動(dòng)態(tài)ROI的實(shí)時(shí)視頻拼接[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2013,34(3):998-1003. [17] 劉明杰,任帥,金城,等. 基于自適應(yīng)投影矩陣的實(shí)時(shí)視頻拼接算法[J]. 計(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-),男,福建福州人,碩士研究生,研究方向?yàn)閳D像處理。 TH123 B 1671-5276(2015)05-0134-05 2014-03-122 算法的實(shí)時(shí)性分析
3 實(shí)驗(yàn)結(jié)果和分析
4 結(jié)語(yǔ)