基于相關(guān)系數(shù)的適用于視頻拼接的幀對(duì)齊方法

殷興華

（北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，北京100029）

0 引 言

傳統(tǒng)的視頻拼接在采集視頻時(shí)需要使用同步觸發(fā)器來同步兩臺(tái)攝像機(jī)啟動(dòng)，本實(shí)驗(yàn)中考慮到通用性，未使用同步觸發(fā)器，而由采集者進(jìn)行人工的控制。這造成了所獲得的兩段視頻在時(shí)間上不是同步的，所以在拼接之前需要進(jìn)行對(duì)幀工作。同時(shí)，為了拓展視場(chǎng)，兩臺(tái)攝像機(jī)拍攝所獲得視頻通常具有相對(duì)較小的重疊區(qū)域 （約1/3左右），這造成了使用傳統(tǒng)的視頻幀對(duì)齊方法［1－3］容易產(chǎn)生嚴(yán)重錯(cuò)誤，導(dǎo)致對(duì)幀的失敗。矩陣間的相關(guān)系數(shù)能夠反映兩數(shù)字矩陣的相似性，而且計(jì)算方法簡(jiǎn)潔，便于計(jì)算機(jī)實(shí)現(xiàn)，是一種常用的圖像匹配方法［4］。相位相關(guān)法能夠快速的確定兩圖像間的位移量，適用于拼接圖像間交疊區(qū)域的界定。本文結(jié)合兩者特性，并綜合運(yùn)用運(yùn)動(dòng)量檢測(cè)及變步長(zhǎng)搜索算法，提出了應(yīng)用于視頻拼接的幀對(duì)齊方法，有效的解決了源視頻幀序列在時(shí)間上不同步的問題，具有很重要的實(shí)際意義。

1 方法概述

如圖1所示，An和Bn是經(jīng)由兩臺(tái)攝像機(jī)獲取的視頻幀序列，且具有一定的交疊區(qū)域 （陰影區(qū)域）。由于采集者不可能十分精確的同時(shí)開始采集，所以即使兩源視頻A和B的幀率相同，視頻中第n幀圖像也不是同一時(shí)刻采集得到的。由于兩視頻的幀率是已知的，現(xiàn)假設(shè)A視頻中的第n幀與B視頻中的第n＋m幀是同一時(shí)刻采集的，所以只要先找到An與Bn＋m的這種對(duì)應(yīng)關(guān)系，就可以確定兩視頻啟動(dòng)時(shí)間差，從而得知A，B間幀的對(duì)應(yīng)關(guān)系。

圖1中虛線所示為兩具有交疊區(qū)域的兩視頻，為了找到An與Bn＋m的對(duì)應(yīng)關(guān)系，我們需要解決兩個(gè)問題：①交疊區(qū)域的界定。②利用交疊區(qū)域圖像在相同時(shí)間點(diǎn)上的一致性確定對(duì)應(yīng)幀。

圖1 幀序列對(duì)應(yīng)

1.1 交疊區(qū)域界定

本實(shí)驗(yàn)使用相位相關(guān)法界定交疊區(qū)域，相位相關(guān)法利用兩次快速傅立葉變換以及一次反變換即可得出沖擊函數(shù)，確定幀圖像間的位移量，具有較好的時(shí)效性。但傳統(tǒng)相位相關(guān)法確定位移量一般是使用在采集時(shí)間相同的拼接圖片間。本實(shí)驗(yàn)中，先使用幀差法尋找視頻中運(yùn)動(dòng)量最小的時(shí)間點(diǎn)［5］。此點(diǎn)附近的幀中含有較少的運(yùn)動(dòng)物體，各幀圖像之間的變化較小，有利于相位相關(guān)法確定兩源視頻幀圖像間的位移。實(shí)驗(yàn)證明，使用低運(yùn)動(dòng)量點(diǎn)附近的幀圖像來進(jìn)行相位相關(guān)法計(jì)算所得的位移量能夠滿足后續(xù)算法的要求。

1.1.1 幀差法確定低運(yùn)動(dòng)量點(diǎn)

設(shè)視頻A分辨率為M＊N，時(shí)長(zhǎng)為n秒，視頻幀率μ，則可知第i秒中第二幅幀圖像在視頻幀序列中的編號(hào)為ki＝μ＊ （i－1）＋1。對(duì)Aki－1，Aki＋1，計(jì)算i時(shí)刻的幀差如式（1）［6］所示

從而得到幀差序列Z1，Z2，Z3，…，Zn，取

按照式 （2）定義的規(guī)則，得到幀差最小的整點(diǎn)時(shí)刻為第i秒。之后再將第i－1秒至第i＋1秒之間的幀圖像序列如上計(jì)算幀差，得到幀差序列并比較，從而找到幀差最小的幀圖像。

本實(shí)驗(yàn)中不同運(yùn)動(dòng)量時(shí)刻所的幀差結(jié)果如圖2、圖3所示。

1.1.2 相位相關(guān)法

相位相關(guān)法是一種頻率域的配準(zhǔn)方法，它先利用傅立葉正變換，計(jì)算兩幅帶拼接圖像的互功率譜［7］。然后對(duì)互功率譜進(jìn)行傅立葉逆變換，通過互功率譜與沖擊函數(shù)的關(guān)系，求得沖擊函數(shù)。由沖擊函數(shù)的峰值便可以得到兩幅圖像間的位移量［8－9］。如果一幅數(shù)字圖像分辨率為M＊N，則其像素值可以表示為式 （3）所示二維離散矩陣

現(xiàn)假設(shè)幀圖像f1和圖像f2具備如下平移關(guān)系

式 （5）對(duì)上述等式進(jìn)行傅立葉變換

變換可得互功率譜為

式中：F＊——F的復(fù)共軛。對(duì)其進(jìn)行傅立葉逆變換得

式 （7）左側(cè)即為所求沖擊函數(shù)，由其峰值位置可確定兩圖像平移參數(shù)。本實(shí)驗(yàn)中，使用幀差法確定的運(yùn)動(dòng)量最低點(diǎn)幀圖片對(duì)進(jìn)行相位相關(guān)計(jì)算，所得沖擊函數(shù)峰值如圖4所示。

經(jīng)實(shí)驗(yàn)證明，此方法所求得的位移量能夠滿足后續(xù)計(jì)算的要求。取10對(duì)交疊區(qū)域不同的源視頻，通過此方法可得到各對(duì)視頻的位移量。計(jì)算此值與實(shí)際位移量的差值，不同交疊區(qū)域?qū)е碌恼`差如圖5所示。隨著交疊區(qū)域的增大，位移量的差值減小，當(dāng)交疊區(qū)域大于視頻拼接所一般要求的30%時(shí)，誤差降至30個(gè)像素以下，這完全可以滿足相關(guān)系數(shù)計(jì)算的要求。

1.2 確定幀對(duì)應(yīng)關(guān)系

1.2.1 相關(guān)函數(shù)

設(shè)圖像A，B為兩幅圖像，分辨率均為M＊N。則A，B的像素值二維矩陣可分別表示為f（x，y），g（x，y），其中x＝0，1，2，…，M－1；y＝0，1，2，…，N－1。A，B像素值矩陣的相關(guān)系數(shù)［10－11］可以定義如下

式中：cov（A，B）——兩二維矩陣的協(xié)方差，DA，DB——矩陣各自的方差。計(jì)算公式為

式 （9）、式 （10）和式 （11）中和分別為A和B像素值矩陣的均值，即兩幅源圖像的亮度均值。相關(guān)系數(shù)ρ的取值范圍為 ［－1，1］，其值越接近1，說明兩幅源圖像的相關(guān)程度越高，也就說明這兩幅幀圖像越可能是同一時(shí)間點(diǎn)采集到的。

1.2.2 搜索算法

設(shè)視頻A和B為待拼接的源視頻，交疊區(qū)域數(shù)字矩陣大小為K＊L，視頻A由NA幅幀圖片組成，幀率為fpsA，B由NB幅幀圖片組成，幀率為fpsB。如果直接取視頻A中的一幀作為基準(zhǔn)幀，在視頻B的幀序列中逐一計(jì)算相關(guān)系數(shù)并求取相關(guān)度最大的幀，這種方法會(huì)產(chǎn)生兩個(gè)問題。①由于兩視頻啟動(dòng)與停止時(shí)間差的存在，視頻A中的某些幀與B中的任何一幀在時(shí)間上均不存在對(duì)應(yīng)關(guān)系。②對(duì)幀圖像Ai和Bi進(jìn)行的相關(guān)系數(shù)的計(jì)算為二維運(yùn)算，如果對(duì)視頻B中的每一幅幀圖像都與基準(zhǔn)幀計(jì)算相關(guān)系數(shù)，這將是一個(gè)十分巨大的運(yùn)算量。所以，為了解決這兩個(gè)問題，本實(shí)驗(yàn)中使用了變步長(zhǎng)的搜索查找算法［12－13］。

本文所針對(duì)的問題中，在采集視頻時(shí)，采集者在主觀上應(yīng)盡量減小時(shí)間差，即采集者應(yīng)盡量做到同時(shí)啟動(dòng)攝像機(jī)。經(jīng)過多次試驗(yàn)，在此前提下，無論是采用口令由兩人啟動(dòng)兩臺(tái)攝像機(jī)，還是由一人使用兩手啟動(dòng)兩臺(tái)攝像機(jī)，攝像機(jī)的啟動(dòng)時(shí)間差絕對(duì)值是存在一個(gè)范圍的，設(shè)此絕對(duì)值的最大值為tmax。假設(shè)基準(zhǔn)幀為A中第i幀，則其對(duì)應(yīng)幀為視頻B中的第（i/fpsA－tmax）＊fpsB幀至第 （i/fpsA＋tmax）＊fpsB幀之間一幀。由以上推論可知，視頻序列Ai（i＝tmax＊fpsA，…，NA－ （tmax＊fpsA））中任何一幀在視頻B中必然存在對(duì)應(yīng)幀，所以在Ai中選擇基準(zhǔn)幀可以避免第一個(gè)問題的出現(xiàn)。

設(shè)定初始步長(zhǎng)為t0，對(duì) ［tmax＊fpsA，NA－ （tmax＊fpsA）］區(qū)間之內(nèi)的視頻A幀圖像序列抽樣得幀序列Ai（i＝tmax＊fpsA，…，k－t0，k，k＋t0，…，NA－ （tmax＊fpsA））。以相同步長(zhǎng)t0對(duì)視頻B進(jìn)行采樣得視頻序列Bi（i＝0，…，k－t0，k，k＋t0，…，NB）。為了更精準(zhǔn)的確定對(duì)應(yīng)幀，我們希望選取的基準(zhǔn)幀附近的幀序列圖片間差距越大越好。因?yàn)閮上噜弾g差距的大小決定了兩者是否易于區(qū)分，在數(shù)學(xué)上，即各自與基準(zhǔn)幀計(jì)算所得的相關(guān)系數(shù)之間差值越大［14］。由第一部分的分析可知，運(yùn)動(dòng)量的高低決定了相鄰幀之間的差距，所以我們?cè)贏i視頻幀序列中取運(yùn)動(dòng)量最高的幀 （由1.1.1節(jié)中計(jì)算所得），設(shè)在Ai序列中運(yùn)動(dòng)量最大的為第Ak幀。以第Ak幀為中心，縮短步長(zhǎng)，取新步長(zhǎng)t1（t1＝｜t0/2｜）。對(duì)幀圖片序列Ai（i＝k－t0，…，k0－t1，k0，k0＋t1，…，k＋t0）如上計(jì)算幀差求取運(yùn)動(dòng)量最高的幀，設(shè)其中運(yùn)動(dòng)量最大的幀為As。然后繼續(xù)如上縮短步長(zhǎng)，以第As幀為中心，求取運(yùn)動(dòng)量最高的幀……，直至步長(zhǎng)為1。假設(shè)此時(shí)求得的基準(zhǔn)幀為Ax。

則最終選定其作為基準(zhǔn)幀，對(duì)視頻序列Bi（i＝0，…，k－t0，k，k＋t0，…，NB）依次計(jì)算相關(guān)系數(shù)，得到以Ax為基準(zhǔn)幀的相關(guān)系數(shù)數(shù)列為ρi（i＝0，…，k－t0，k，k＋t0，…，NB），求取

假設(shè)取得此最大值的幀在視頻B中為第k0幀。然后保持視頻A中基準(zhǔn)幀不變，縮短步長(zhǎng)，取新步長(zhǎng)為t1（t1＝｜t0/2｜），以視頻B中第k0幀為中心，對(duì)幀圖片序列Bi（i＝k－t0，…，k0－t1，k0，k0＋t1，…，k＋t0）中每幅圖片計(jì)算相關(guān)系數(shù)，求得取到最大值的幀圖片為視頻B中的第k1幀。然后，繼續(xù)如上縮短步長(zhǎng)，以第k1幀為中心，求取相關(guān)系數(shù)最大的幀……，直至步長(zhǎng)為1，假設(shè)此時(shí)求得的幀數(shù)為kn。

為了提高配準(zhǔn)的準(zhǔn)確度與可信度，實(shí)驗(yàn)中取視頻A中運(yùn)動(dòng)量最大的三幀Ax1，Ax2，Ax3分別如上計(jì)算對(duì)應(yīng)幀數(shù)kn。設(shè)3次求得的對(duì)應(yīng)幀數(shù)分別為kn1，kn2，kn3［15］，則按照式 （13）分別求得的視頻對(duì)應(yīng)幀時(shí)間差

設(shè)如上求得時(shí)間差為δt1，δt2，δt3，則最終求的視頻A，B時(shí)間差為

2 實(shí)驗(yàn)結(jié)果

為了測(cè)試本方法能否實(shí)現(xiàn)所需要的對(duì)幀功能，實(shí)驗(yàn)中采用兩臺(tái)CANON A495相機(jī)采集視頻。兩相機(jī)之間距離可調(diào)整以改變交疊區(qū)域的大小，攝像機(jī)的啟動(dòng)與停止由兩人手工操作，采取口令的方式人工同步，啟動(dòng)與停止的時(shí)間差一般不大于3S。軟件運(yùn)行環(huán)境：操作系統(tǒng)：Windows XP 32，內(nèi)存：2G，CPU主頻：2.0GHz。共采集不同類型視頻10組，交疊區(qū)域所占視頻分辨率百分比最低為13%，最高為57%。視頻中不同時(shí)間段要求具有不同的運(yùn)動(dòng)量及場(chǎng)景，以涵蓋不同的情況。

下文中，取參數(shù)tmax＝3，t0＝10。以交疊區(qū)域40%，fpsA＝20，fpsB＝30的源視頻對(duì)為例。此視頻對(duì)具有明顯不同的光照，遠(yuǎn)、近境的運(yùn)動(dòng)物體，以及樹葉的擺動(dòng)等多種不同特征，具有較好的代表性。運(yùn)用本方法選取視頻A中第80幀、第90幀和第40幀為基準(zhǔn)幀，分別求得視頻B中于視頻A中基準(zhǔn)幀對(duì)應(yīng)的3個(gè)幀分別為：kn1＝130，kn2＝145，kn3＝69，依式 （13）求得

δt1＝0.333，δt2＝0.333，δt3＝0.300

按照式 （14）可求的視頻A與視頻B對(duì)應(yīng)幀時(shí)間差為δt＝ （0.333＋0.333＋0.300）/3＝0.32 （s）

以10幀為間隔，視頻A，B第40～80幀圖片序列如圖6、圖7所示。觀察圖片可知，視頻A中第40幀圖片與視頻B中第70幀圖片為對(duì)應(yīng)幀圖片，則兩視頻時(shí)間差為70/30－40/20＝0.33 （s），誤差為0.01，小于視頻A或B中單幀的時(shí)間長(zhǎng)度 （0.03）。所以誤差在可接受范圍內(nèi)，實(shí)現(xiàn)了對(duì)幀功能。

同樣以初始步長(zhǎng)10幀為間隔，視頻A，B幀序列中各幀處的幀差運(yùn)動(dòng)量及計(jì)算所得時(shí)間差與實(shí)際時(shí)間差的差值如表1所示，表2為不同交疊百分比視頻最終計(jì)算所得時(shí)間差與實(shí)際時(shí)間差的差值對(duì)比表。

表1 運(yùn)動(dòng)量與時(shí)間差對(duì)比

表2 交疊區(qū)域與時(shí)間差對(duì)比

經(jīng)過分析，第0幀處出現(xiàn)此種情況的原因是，采集視頻是由人手工啟動(dòng)的，而且未使用嚴(yán)格的支架，所以在按下攝像機(jī)時(shí)攝像機(jī)會(huì)出現(xiàn)一次抖動(dòng)，造成用幀差法檢測(cè)是會(huì)出現(xiàn)很大的灰度差，但此時(shí)刻往往并不具有可以接受的運(yùn)動(dòng)量。在本實(shí)驗(yàn)中，選取基準(zhǔn)幀時(shí)，tmax估計(jì)量的引入恰好可以將視頻開頭處的抖動(dòng)幀丟棄。

將實(shí)驗(yàn)中所用到的10組視頻對(duì)按照交疊區(qū)域百分比排序，與計(jì)算所得時(shí)間差與實(shí)際時(shí)間差的差值的絕對(duì)值可見表2。由此表中數(shù)據(jù)可知，當(dāng)交疊區(qū)域大于1/4時(shí)，此方法計(jì)算值與實(shí)際值差值接近0，當(dāng)交疊區(qū)域達(dá)到1/3以上時(shí)，經(jīng)過計(jì)算，一般都可準(zhǔn)確得到兩視頻啟動(dòng)時(shí)間差。而對(duì)于視頻拼接，為了能夠?yàn)楹罄m(xù)拼接提供較豐富的特征點(diǎn)，一般要求源視頻具有1/3以上的交疊區(qū)域。所以此方法可以滿足基于雙攝像機(jī)視頻拼接的對(duì)幀要求。

3 結(jié)束語

本文闡述了一種用于雙攝像機(jī)視頻拼接的對(duì)幀方法。該方法利用幀差法對(duì)視頻進(jìn)行分析，獲得視頻中不同時(shí)間點(diǎn)的運(yùn)動(dòng)量狀況，在運(yùn)動(dòng)量最低點(diǎn)利用相位相關(guān)法計(jì)算視頻位移，在運(yùn)動(dòng)量最高點(diǎn)計(jì)算基準(zhǔn)幀與另一視頻幀序列交疊區(qū)域間的相關(guān)系數(shù)，以此確定對(duì)應(yīng)幀。此方法具有運(yùn)算量較小，受樹葉擺動(dòng)等不規(guī)則運(yùn)動(dòng)干擾小的特點(diǎn)。經(jīng)實(shí)驗(yàn)證明，該方法能夠在人手工操作攝像機(jī)，具有要求交疊區(qū)域的情況下，準(zhǔn)確的定位到對(duì)應(yīng)幀，完成視頻對(duì)幀操作。

［1］BEN Yueyang，YIN Guisheng，GAO Wei，et al.Inertial frame coarse alignment for strap down inertial navigation system ［C］.IEEE International Forum on Information Technology and Applications，2009：647－651.

［2］Flavio Padua，Rodrigo Carceroni，Geraldo Santos，et al.Linear sequence－to－sequence alignment ［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2010，32 （2）：304－320.

［3］Philip A Tresadern，Ian D Reid.Video synchronization from human motion using rank constraints ［J］.Computer Vision and Image Understanding，2009，113 （8）：891－906.

［4］CHEN Weibing.Comparision of matching capabilities in similarity measurements［J］.Journal of Computer Applications，2010，30（1）：98－110 （in Chinese）.［陳衛(wèi)兵.幾種圖像相似性度量的匹配性能比較 ［J］.計(jì)算機(jī)應(yīng)用，2010，30 （1）：98－110.］

［5］Josue Hernandez，Hiroshi Morita，Mariko Nakano－Miytake，et al.Movement detection and tracking using video frames［C］.14th Iberoamerican Conferences，2009：1054－1061.

［6］Darlan N Brito，F(xiàn)lavio L C Padua，Guilherme A S PereiraL，et al.Temporal synchronization of non－overlapping videos using known object motion ［J］.Pattern Recognition Letters，2011，32 （1）：38－46.

［7］Yaron Caspi，Denis Simakov，Michal Irani.Feature－based sequence－to－sequence matching ［J］.International Journal of Computer Vision，2006，68 （1）：53－64.

［8］ZHANG Jing，WANG Changshun，LIAO Wuling.An image mosaic algorithm based on improved phase correlation ［C］.International Conference on Environmental Science and Information Application Technology，2009：383－386.

［9］Javed Ahmed，Noman Jafri M.Improved phase correlation matching ［C］.3rd International Conference on Image and Signal Processing，2008：128－135.

［10］SHEN Hengtao，SHAO Jie，HUANG Zi，et al.Effective and efficient query processing for video subsequence identification ［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21 （3）：321－334.

［11］ WANG Xiangqing， WANG Jun，PENG Hong.A semifragile image watermarking resisting to JPEG compression［C］.International Conference on Management of E－Commerce and E－Government，2009：498－502.

［12］Miroslaw Kordos，Wlodzislaw Duch.Variable step search algorithm for feedforward networks ［J］.Neurocomputing，2008，71 （13－15）：2470－2480.

［13］GAO Jian，LU Jining，HUANG Keyuan，et al.A novel variable step hill－climb search algorithm used for direct driven PMSG ［C］.International Conference on Energy and Environment Technology，2009：511－514.

［14］CAI Z H，WANG Y Y，WANG W Q.Improved image mosaic algorithm based on morphological method ［J］.Chinese Journal of Scientific Instrument，2006，27 （6）：721－723.

［15］Zirova B，F(xiàn)lusser J.Image registration methods：A survey ［J］.Image and Vision Computing，2007，21 （11）：977－1000.