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

殷興華

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

0 引 言

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

1 方法概述

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

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

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

1.1 交疊區(qū)域界定

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

1.1.1 幀差法確定低運動量點

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

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

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

本實驗中不同運動量時刻所的幀差結(jié)果如圖2、圖3所示。

1.1.2 相位相關(guān)法

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

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

式 （5）對上述等式進行傅立葉變換

變換可得互功率譜為

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

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

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

1.2 確定幀對應(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——矩陣各自的方差。計算公式為

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

1.2.2 搜索算法

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

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

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

則最終選定其作為基準(zhǔn)幀，對視頻序列Bi（i＝0，…，k－t0，k，k＋t0，…，NB）依次計算相關(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)幀不變，縮短步長，取新步長為t1（t1＝｜t0/2｜），以視頻B中第k0幀為中心，對幀圖片序列Bi（i＝k－t0，…，k0－t1，k0，k0＋t1，…，k＋t0）中每幅圖片計算相關(guān)系數(shù)，求得取到最大值的幀圖片為視頻B中的第k1幀。然后，繼續(xù)如上縮短步長，以第k1幀為中心，求取相關(guān)系數(shù)最大的幀……，直至步長為1，假設(shè)此時求得的幀數(shù)為kn。

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

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

2 實驗結(jié)果

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

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

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

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

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

同樣以初始步長10幀為間隔，視頻A，B幀序列中各幀處的幀差運動量及計算所得時間差與實際時間差的差值如表1所示，表2為不同交疊百分比視頻最終計算所得時間差與實際時間差的差值對比表。

表1 運動量與時間差對比

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

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

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

3 結(jié)束語

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

［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］.計算機應(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.