基于運(yùn)動(dòng)目標(biāo)三維軌跡重建的視頻序列同步算法

王雪 SHI Jian-Bo PARK Hyun-Soo 王慶

視頻同步,又稱視頻對(duì)準(zhǔn),是計(jì)算機(jī)視覺領(lǐng)域中一個(gè)重要的基礎(chǔ)問題.根據(jù)同步方式不同,現(xiàn)有的視頻同步方法可分為基于外觸發(fā)脈沖的同步和基于視頻圖像序列中視覺特征的同步.其中,基于外觸發(fā)脈沖的同步技術(shù)作用在相機(jī)端,多用于控制多相機(jī)同步實(shí)現(xiàn)高速圖像采集存儲(chǔ),硬件成本較高;基于視覺特征的同步算法通過分析圖像序列中的同步線索實(shí)現(xiàn)多個(gè)視頻間的時(shí)域?qū)R,可用于行為識(shí)別、基于內(nèi)容的視頻檢索及非剛性結(jié)構(gòu)三維重建等視覺任務(wù).本文主要討論基于視覺特征的視頻同步方法,其常規(guī)思路是聯(lián)合優(yōu)化圖像序列間的空間和時(shí)間對(duì)準(zhǔn).空間對(duì)準(zhǔn)多指在待同步幀對(duì)的二維圖像或三維相機(jī)坐標(biāo)系下計(jì)算某種幾何變換,因此依賴精確的特征提取和匹配.時(shí)域?qū)?zhǔn)通過估算圖像序列間的線性或非線性時(shí)域映射以獲得最優(yōu)的空間對(duì)準(zhǔn).

為了降低問題求解的復(fù)雜度,研究者們提出各種假設(shè)來減少待估計(jì)參數(shù)的數(shù)量.假設(shè)靜止相機(jī)或聯(lián)合運(yùn)動(dòng)相機(jī),則空間變換關(guān)系恒定不變.現(xiàn)有方法多在二維圖像坐標(biāo)系中估算幾何變換,如單應(yīng)[1?2]、仿射變換[3]、射影變換[2?6]等,并利用重投影誤差來度量空間對(duì)準(zhǔn)的程度.由于求解基礎(chǔ)矩陣對(duì)噪聲敏感,Rao等[7]針對(duì)透視模型提出一種基于對(duì)極幾何的秩約束.進(jìn)一步地,Tresadern等[8]綜合單應(yīng)、仿射變換和射影變換三種幾何模型下的虧秩條件,提出了統(tǒng)一的算法框架.這類方法多用于窄基線條件下圖像點(diǎn)軌跡及對(duì)應(yīng)關(guān)系已知的視頻對(duì)準(zhǔn).為克服寬基線條件下特征匹配難的問題,文獻(xiàn)[9?10]提出一種弱假設(shè),即觀測(cè)序列中像點(diǎn)的空間位置可以用參考序列中像點(diǎn)子集空間位置的線性組合描述,且該線性關(guān)系維持不變.這樣,算法不再依賴已知的像點(diǎn)對(duì)應(yīng)關(guān)系,各序列中的像點(diǎn)甚至可以對(duì)應(yīng)不同的空間點(diǎn).缺點(diǎn)是該方法僅適用于固定仿射相機(jī)間的常量偏移時(shí)域同步.假設(shè)相機(jī)沿相似軌跡運(yùn)動(dòng)[11?15],則對(duì)應(yīng)幀的相機(jī)坐標(biāo)系可近似認(rèn)為原點(diǎn)重合,僅對(duì)應(yīng)坐標(biāo)軸間存在較小的旋轉(zhuǎn)角度.因此,內(nèi)容上越相似的兩幅圖像幀,其時(shí)域同步的可能性越高.基于這種思想,Wang等[16]提出了一種基于SIFT特征點(diǎn)匹配的視頻同步算法,并提供友好的交互界面允許用戶手動(dòng)設(shè)置入點(diǎn)、出點(diǎn)或剪輯標(biāo)記來同步多機(jī)位序列.值得一提的是,這種交互方式也是眾多視頻編輯工具實(shí)現(xiàn)多機(jī)位序列同步的方式,此外還包括使用基于音頻的同步來準(zhǔn)確對(duì)齊剪輯,例如Edius、Premiere等.假設(shè)時(shí)域映射關(guān)系為線性,例如常量偏移模型[4,9?10],或者一維仿射模型[1?2,5,7],則時(shí)域映射關(guān)系可以用一個(gè)簡(jiǎn)單的參數(shù)化模型tr=ρto+?來描述,其中tr和to分別表示參考序列和觀測(cè)序列中的圖像幀索引,ρ為兩序列的幀率比,?為幀索引偏移常量.

聯(lián)合空間和時(shí)間對(duì)準(zhǔn)能夠提高系統(tǒng)的魯棒性,但這類方法面臨兩個(gè)主要的挑戰(zhàn).1)對(duì)于獨(dú)立運(yùn)動(dòng)相機(jī)和包含多個(gè)運(yùn)動(dòng)目標(biāo)的三維動(dòng)態(tài)場(chǎng)景(圖1)來說,基于幾何變換的空間對(duì)準(zhǔn)是十分困難的.2)考慮到丟幀、時(shí)域連續(xù)性等問題,線性時(shí)域映射不再滿足需求,而非線性時(shí)域映射的估算會(huì)增加現(xiàn)有算法求解的復(fù)雜度.

圖1 待同步的第一人稱視角圖像序列Fig.1 Video sequences captured by fi rst-person cameras

針對(duì)獨(dú)立運(yùn)動(dòng)相機(jī),Tuytelaars等[17]提出一種基于反向投影的同步方法,用于弱透視投影模型下視頻間的偏移常量時(shí)域同步,通過將圖像點(diǎn)反向投影到空間中的一條線,從而將時(shí)域?qū)?zhǔn)問題轉(zhuǎn)換為在空間中尋找相交或距離最短的直線問題.Lei等[18]基于三視圖幾何約束建立時(shí)間軸圖,用于多個(gè)圖像序列間的偏移常量時(shí)域同步.這些方法都假設(shè)線性時(shí)域映射關(guān)系,并且依賴精確的特征點(diǎn)跟蹤和匹配,因此在實(shí)際應(yīng)用中受到限制.Dexter等[19]利用圖像序列的自相似矩陣為每幀圖像計(jì)算時(shí)域自適應(yīng)的特征描述,通過時(shí)域運(yùn)動(dòng)特征匹配實(shí)現(xiàn)圖像序列對(duì)的非線性時(shí)域同步.該算法利用場(chǎng)景中靜止的背景點(diǎn)估計(jì)全局運(yùn)動(dòng)實(shí)現(xiàn)相機(jī)自運(yùn)動(dòng)補(bǔ)償,僅適用于平面場(chǎng)景或遠(yuǎn)視角.

本文提出一種針對(duì)獨(dú)立運(yùn)動(dòng)相機(jī)的視頻時(shí)域?qū)?zhǔn)算法,其主要想法是利用空間中運(yùn)動(dòng)目標(biāo)的軌跡(時(shí)間空間特征)來同步圖像序列.取代傳統(tǒng)的幀對(duì)空間對(duì)準(zhǔn),我們?cè)跁r(shí)間軸上從單幀的圖像點(diǎn)延長(zhǎng)到持續(xù)整個(gè)子序列段的圖像點(diǎn)軌跡,通過三維運(yùn)動(dòng)軌跡重建,提出一個(gè)基于軌跡基系數(shù)的秩約束用于度量任意子序列對(duì)的空間對(duì)準(zhǔn)程度.隨后,本文提出一種基于圖的非線性時(shí)域?qū)?zhǔn)算法,用于搜索最優(yōu)時(shí)域映射關(guān)系.進(jìn)一步地,我們將該算法從雙序列對(duì)準(zhǔn)擴(kuò)展到多序列的情況.最后,本文在仿真數(shù)據(jù)和真實(shí)第一視角數(shù)據(jù)集上進(jìn)行驗(yàn)證.

1 雙序列時(shí)域?qū)?zhǔn)

1.1 基于三維軌跡重建的線性時(shí)域?qū)?zhǔn)

當(dāng)兩個(gè)或多個(gè)相機(jī)相對(duì)靜止,或者沿相似軌跡運(yùn)動(dòng),空間中同一個(gè)運(yùn)動(dòng)點(diǎn)在不同相機(jī)拍攝的圖像序列中的二維軌跡是相似的.然而,若相機(jī)自由運(yùn)動(dòng),則上述結(jié)論不再成立.為了消除相機(jī)自運(yùn)動(dòng)對(duì)目標(biāo)運(yùn)動(dòng)分析的影響,我們可以在二維圖像空間中嘗試相機(jī)自運(yùn)動(dòng)補(bǔ)償,或者將二維觀測(cè)反投影回三維空間中進(jìn)行運(yùn)動(dòng)分析.后者的優(yōu)點(diǎn)是受場(chǎng)景及相機(jī)運(yùn)動(dòng)限制較小.本文采取后一種方法,首先利用文獻(xiàn)[20?21]提出運(yùn)動(dòng)目標(biāo)三維軌跡重建算法恢復(fù)運(yùn)動(dòng)目標(biāo)的三維軌跡.

令攝像機(jī)在第t幀的投影矩陣為P(t)∈R3×4,按透視射影變換將空間中一點(diǎn)X(t)=[X(t)Y(t)Z(t)]T投影到二維像點(diǎn)x(t)=[x(t)y(t)]T,根據(jù)相機(jī)成像模型有

其中,X=[X(1)T,···,X(F)T]T為重建的運(yùn)動(dòng)目標(biāo)三維軌跡.假設(shè)軌跡可以采用離散余弦變換(Discrete cosine transform,DCT)基以較少的低頻分量線性表示.

如果該目標(biāo)的三維軌跡同時(shí)被另外一臺(tái)攝像機(jī)捕捉到,類似地,我們可以得到

為了提高公式的易讀性,本文用相同符號(hào)加角號(hào)表示與第二個(gè)圖像序列相關(guān).由于Θ是正交矩陣,基系數(shù)β和理論上應(yīng)相同.若空間中有P個(gè)點(diǎn)同時(shí)被兩個(gè)攝像機(jī)看到,當(dāng)滿足不等式3K≥2P時(shí),基系數(shù)矩陣的秩最大不超過P.若兩序列同步,M的秩減小,相反,若兩序列不同步,則M的秩增加.因此,我們可以通過比較不同偏移量下M的秩,來估算時(shí)域映射關(guān)系.值得注意的是,P不是一個(gè)上確界,這取決于P個(gè)點(diǎn)間的剛性約束關(guān)系.無論如何,基系數(shù)矩陣M的秩在同步時(shí)的下降量不低于非同步時(shí)的下降量.

令Sr={Ir(1),Ir(2),···,Ir(Nr)}和So={Io(1),Io(2),···,Io(No)}分別表示由獨(dú)立運(yùn)動(dòng)相機(jī)拍攝的參考圖像序列和觀測(cè)圖像序列,其中Nr和No分別為兩個(gè)序列的幀數(shù).可檢驗(yàn)的整數(shù)時(shí)間偏移量?的取值范圍是R=[?No+F,Nr?F].

在上述關(guān)于秩約束的推導(dǎo)中,我們用到了三個(gè)假設(shè):1)視頻間的圖像點(diǎn)對(duì)應(yīng)已知;2)圖像點(diǎn)跟蹤持續(xù)整個(gè)圖像序列;3)視頻間的時(shí)域關(guān)系為常量偏移模型.本節(jié)先討論第一個(gè)假設(shè),其余兩個(gè)假設(shè)在下一節(jié)中進(jìn)行論述.

若視頻間的點(diǎn)對(duì)應(yīng)關(guān)系未知,我們可以使用一個(gè)弱假設(shè)[9?10]令秩約束仍然成立:觀測(cè)序列中跟蹤點(diǎn)對(duì)應(yīng)的三維點(diǎn),其空間位置可以用參考序列中所有跟蹤點(diǎn)對(duì)應(yīng)的三維點(diǎn)集的子集的線性組合描述,即滿足下列關(guān)系

同理,當(dāng)滿足不等式3K≥Pr+Po時(shí),新基系數(shù)矩陣的秩最大不超過Pr.引入這一弱假設(shè)的好處是,在省去了估計(jì)視頻間圖像點(diǎn)對(duì)應(yīng)的同時(shí),還使得該算法能夠處理寬基線條件下的視頻同步,即被兩個(gè)相機(jī)同時(shí)看到的三維點(diǎn)數(shù)量有限或者為零.

圖2 測(cè)試序列對(duì)同步和不同步時(shí)基系數(shù)矩陣 的奇異值Fig.2 An example of the singular values of in synchronized case and non-synchronized cases

進(jìn)一步地,我們將距離函數(shù)dst轉(zhuǎn)換為歸一化的代價(jià)函數(shù)c.

1.2 非線性時(shí)域?qū)?zhǔn)

上述算法雖然不依賴視頻間已知的像點(diǎn)對(duì)應(yīng),但仍然假設(shè)圖像點(diǎn)跟蹤持續(xù)整個(gè)圖像序列.實(shí)際應(yīng)用中,由于遮擋、光線局部變化等原因,多數(shù)跟蹤算法很難維持長(zhǎng)時(shí)間的精確跟蹤.此外,假設(shè)視頻間時(shí)域關(guān)系為一維常量偏移模型,這也限制了同步算法的適用范圍.為此,本文提出一種能夠利用不同長(zhǎng)度圖像點(diǎn)軌跡的非線性時(shí)域?qū)?zhǔn)算法.

我們將Sr和So分別劃分為若干F幀長(zhǎng)的子序列段,令每個(gè)子序列段的中間幀為參考幀.然后針對(duì)候選子序列對(duì)(fr(j),fo(k)),選擇跟蹤持續(xù)fr(j)的Pr個(gè)圖像點(diǎn)和跟蹤持續(xù)fo(k)的Po個(gè)圖像點(diǎn),重建這些點(diǎn)的三維軌跡并計(jì)算基系數(shù)矩陣.其中,fr(j)表示Sr中參考幀為Ir(j)的子序列,fo(k)同理.最后利用代價(jià)函數(shù)c估算(fr(j),fo(k))的對(duì)齊程度,記為cjk.這樣,我們得到代價(jià)矩陣,其中是地板函數(shù).

Pr和Po的確定依據(jù)以下兩個(gè)規(guī)則:1)以參考圖像序列為例,將持續(xù)跟蹤子序列段fr(j)的圖像點(diǎn)個(gè)數(shù)記為Pr(j),則.對(duì)Po同理.2)滿足兩個(gè)不等式,2F≥3K和3K≥Pr+Po.前者為了確保運(yùn)動(dòng)目標(biāo)軌跡重建時(shí)的超定系統(tǒng),后者則保證了的秩最大不超過Pr.

式(6)的成立基于常量時(shí)間偏移模型的假設(shè),即tr=to+?.當(dāng)圖像序列對(duì)的幀率不同但相近,或者存在輕微的丟幀現(xiàn)象時(shí),該等式仍然近似成立.由此,相較于不同步的子序列對(duì),由時(shí)域同步或者最相近的子序列對(duì)構(gòu)造的基系數(shù)矩陣仍然具有較小的秩.非線性時(shí)域關(guān)系可以用一個(gè)離散映射函數(shù)ω(to)=tr,to=1,···,N表示,其中N≤No,表示觀測(cè)序列中有N幀圖像在參考序列中有時(shí)域?qū)?zhǔn)的圖像.該函數(shù)在基于圖的方法中為經(jīng)過代價(jià)矩陣的一條路徑.為了應(yīng)對(duì)局部時(shí)域重疊,受文獻(xiàn)[16]的最優(yōu)路徑搜索算法啟發(fā),首先,我們基于Dijkstra算法計(jì)算候選路徑集,每一條候選路徑可以開始和結(jié)束于參考序列或觀測(cè)序列的任何幀,該路徑的代價(jià)為其經(jīng)過代價(jià)矩陣中各節(jié)點(diǎn)值加和的平均值.然后,基于候選路徑集選擇最優(yōu)路徑.為了避免選擇長(zhǎng)度過短的路徑,根據(jù)路徑結(jié)束于Sr或者So,我們將候選路徑集劃分為兩個(gè)池,分別在每個(gè)池中選擇最小代價(jià)路徑.多數(shù)情況下,一條路徑被完全包含在另一條路徑中(圖3(a)),這時(shí)我們選擇較短那條作為最優(yōu)路徑.若兩條候選路徑不重疊(圖3(b)),則選擇較長(zhǎng)那條作為最優(yōu)路徑.圖中代價(jià)矩陣的橫軸和縱軸分別表示Sr和So的幀索引,其元素的顏色越深,對(duì)應(yīng)值越小.

圖3 代價(jià)矩陣和最優(yōu)路徑(白實(shí)線)Fig.3 Cost matrix and optimal path(white solid curve)

雙序列時(shí)域?qū)?zhǔn)算法的具體流程如圖4所示.其中跟蹤二維點(diǎn)軌跡和重建三維軌跡都是針對(duì)單個(gè)圖像序列獨(dú)立執(zhí)行的,唯一需要聯(lián)合雙序列的步驟是估算代價(jià)矩陣和最優(yōu)路徑.注意,我們分別選擇fr(j)中的Pr個(gè)點(diǎn)和fo(k)中的Po個(gè)點(diǎn)進(jìn)行三維軌跡重建,然后計(jì)算(fr(j),fo(k))的對(duì)齊代價(jià),這一步驟需要重復(fù)T次,最后取中值作為最終的cjk.通常地,當(dāng)Pr和Po值一定時(shí),重復(fù)次數(shù)越多,算法魯棒性越好,相應(yīng)地,時(shí)間復(fù)雜度越高.非線性時(shí)域?qū)?zhǔn)算法的時(shí)間復(fù)雜度為O(Nr×No×T).試驗(yàn)中,我們根據(jù)跟蹤結(jié)果的精度和跟蹤點(diǎn)數(shù)量決定T.一般地,跟蹤結(jié)果越準(zhǔn)確,跟蹤點(diǎn)數(shù)越少,T值越小.若已知時(shí)域映射為線性或常量偏移模型,可以利用線性時(shí)域?qū)?zhǔn)算法使時(shí)間復(fù)雜度降為O(Nr+No).

2 多序列時(shí)域?qū)?zhǔn)

理論上,我們可以將上述雙序列時(shí)域?qū)?zhǔn)算法簡(jiǎn)單地?cái)U(kuò)展到多序列的情況,即增加代價(jià)矩陣的維度,并搜索最優(yōu)映射p:R→RD,其中D為待同步圖像序列的數(shù)量.然而在實(shí)際應(yīng)用中,這種方法是不可取的.假設(shè)有五個(gè)待同步的序列,每個(gè)序列以30fps的幀率持續(xù)10秒,即有300幀圖像.那么代價(jià)矩陣的元素?cái)?shù)量達(dá)到3005.若采用32位浮點(diǎn)數(shù)存儲(chǔ)這個(gè)代價(jià)矩陣,需要約8.8TB的內(nèi)存.這顯然已經(jīng)超出了現(xiàn)有的硬件支持能力.本文采用文獻(xiàn)[16]中基于最小生成樹(Minimum spanning tree,MST)的方法尋找雙序列對(duì)準(zhǔn)集合,將多對(duì)多(Allto-all)的多序列時(shí)域?qū)?zhǔn)問題簡(jiǎn)化為只利用最優(yōu)的雙序列對(duì)準(zhǔn)獲取全局的時(shí)域映射變換.

圖4 雙序列時(shí)域?qū)?zhǔn)算法流程圖Fig.4 The fl ow chart of pairwise alignment

3 仿真實(shí)驗(yàn)

本文基于文獻(xiàn)[21]提供的人體運(yùn)動(dòng)捕捉數(shù)據(jù)(倒地、站立和步行)生成仿真數(shù)據(jù).通過隨機(jī)合成相機(jī)投影矩陣,將13個(gè)人體關(guān)節(jié)點(diǎn)的三維運(yùn)動(dòng)軌跡投影到兩組不斷變化的圖像平面上.重建后的三維運(yùn)動(dòng)軌跡及其真實(shí)值如圖5所示.我們將其中一個(gè)圖像序列作為參考序列,將另外一個(gè)圖像序列時(shí)域偏移? 幀后,再隨機(jī)去掉若干幀(丟幀率不高于5%),作為觀測(cè)序列.每組實(shí)驗(yàn)重復(fù)10次,每次采用不同的隨機(jī)相機(jī)運(yùn)動(dòng)軌跡.該實(shí)驗(yàn)中所有二維點(diǎn)軌跡均持續(xù)完整的圖像序列,計(jì)算代價(jià)矩陣時(shí)令采樣次數(shù)T=1.本文采用原始DCT基重建三維軌跡,令每個(gè)維度上基的數(shù)量K=30.

圖5 仿真數(shù)據(jù)重建結(jié)果(黑)和真實(shí)值(灰)Fig.5 Reconstruction(black)and ground truth(gray)of simulated data

3.1 魯棒性

為了驗(yàn)證跟蹤誤差、數(shù)據(jù)丟失和圖像點(diǎn)數(shù)量對(duì)新算法精度的影響,我們?cè)O(shè)置了如下三組實(shí)驗(yàn).如不做特殊說明,認(rèn)為無數(shù)據(jù)丟失.1)不同跟蹤誤差和子序列段長(zhǎng)度與時(shí)域?qū)?zhǔn)誤差間的關(guān)系,結(jié)果如圖6(a)所示.從圖中可以看出,子序列段越長(zhǎng),算法受跟蹤誤差影響越小,其同步精度越高.但是,延長(zhǎng)子序列段會(huì)縮小代價(jià)矩陣,相應(yīng)地,時(shí)域映射關(guān)系中自變量的取值范圍變小,表現(xiàn)在圖中就是最優(yōu)路徑變短.注意,像素單位的跟蹤偏移誤差是通過用跟蹤誤差級(jí)α乘上一個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的偽隨機(jī)數(shù)得到.2)造成跟蹤過程中目標(biāo)數(shù)據(jù)丟失的原因有遮擋、自遮擋、度量失敗等.圖6(b)為不同程度的數(shù)據(jù)丟失(0%,5%,10%)與時(shí)域?qū)?zhǔn)誤差間的關(guān)系.只要跟蹤到足夠多幀數(shù)的觀測(cè)值能確保三維軌跡重建時(shí)的超定系統(tǒng),新算法的精度基本不受數(shù)據(jù)丟失的影響.3)不同圖像點(diǎn)數(shù)量與時(shí)域?qū)?zhǔn)誤差間的關(guān)系,結(jié)果如圖6(c)所示.理論上,如果一個(gè)三維點(diǎn)的運(yùn)動(dòng)足夠快并且隨機(jī),它被兩個(gè)獨(dú)立運(yùn)動(dòng)的相機(jī)同時(shí)捕獲到,那么僅用這一個(gè)點(diǎn)就可以同步兩個(gè)相機(jī).實(shí)際應(yīng)用中考慮到單個(gè)點(diǎn)重復(fù)性運(yùn)動(dòng)的情況,加入空間相對(duì)位置關(guān)系的約束,綜合多個(gè)位于不同剛性物體上的點(diǎn)能大大提高時(shí)域?qū)?zhǔn)的精度.

圖6 跟蹤誤差、數(shù)據(jù)丟失和圖像點(diǎn)數(shù)量對(duì)同步結(jié)果的影響Fig.6 Comparisons of robustness with regard to tracking error,missing data and point number

3.2 準(zhǔn)確性

本文在仿真數(shù)據(jù)基礎(chǔ)上對(duì)比了本文方法與現(xiàn)有方法的時(shí)域同步精度,包括文獻(xiàn)[17]中基于反向投影的方法BPM 和文獻(xiàn)[8]中基于透視模型對(duì)極幾何的方法ECM.其中,BPM用到3組不同的對(duì)應(yīng)點(diǎn)集,每組點(diǎn)集包含5個(gè)圖像點(diǎn).這兩種方法均假設(shè)線性時(shí)域映射關(guān)系,為了對(duì)比公平,在它們計(jì)算代價(jià)矩陣的基礎(chǔ)上,利用本文提出的基于圖的最優(yōu)路徑搜索算法,尋找非線性時(shí)域映射函數(shù).

除上述兩種方法外,我們還提出以下對(duì)比基準(zhǔn).基于不同序列重建對(duì)應(yīng)點(diǎn)的三維運(yùn)動(dòng)軌跡,當(dāng)觀測(cè)序列和參考序列精確同步時(shí),同步幀索引的空間點(diǎn)重合;當(dāng)觀測(cè)序列和參考序列為子幀級(jí)別同步時(shí),即幀和幀之間的時(shí)域偏移量為非整數(shù),則同步幀索引的空間點(diǎn)距離最小.因此,我們將新算法中基于秩約束的時(shí)域?qū)R度量準(zhǔn)則替換為基于三維重建點(diǎn)距離的度量準(zhǔn)則,記為PDM.

圖7(a)為步行數(shù)據(jù)集上各算法受跟蹤誤差影響的時(shí)域?qū)?zhǔn)精度曲線圖,是仿真數(shù)據(jù)集上各算法試驗(yàn)結(jié)果對(duì)比.隨著跟蹤誤差逐漸變大,本文算法表現(xiàn)出更好的魯棒性.ECM方法的時(shí)域?qū)?zhǔn)誤差與跟蹤誤差不成正比,這可能歸結(jié)于試驗(yàn)中的非線性時(shí)域映射,相比原始方法的線性時(shí)域映射假設(shè),非參數(shù)模型大大增加了解空間的維度,導(dǎo)致當(dāng)輸入有噪聲時(shí)該算法的準(zhǔn)確度降低.圖7(b)～7(i)是針對(duì)倒地?cái)?shù)據(jù)集中一個(gè)測(cè)試序列對(duì)(常量偏移量?=35)各算法的同步結(jié)果.圖7(b)～7(e)為沒有跟蹤誤差時(shí),各算法計(jì)算的代價(jià)矩陣和最優(yōu)路徑.圖7(f)～7(i)為當(dāng)跟蹤誤差級(jí)α=0.30時(shí),各算法計(jì)算的代價(jià)矩陣和最優(yōu)路徑.注意,與本文算法基于子序列對(duì)計(jì)算代價(jià)矩陣不同,三種對(duì)比方法均計(jì)算任意幀對(duì)的時(shí)域?qū)R程度,生成代價(jià)矩陣的維度為No×Nr.

圖7 仿真數(shù)據(jù)集上各算法在不同跟蹤誤差下的實(shí)驗(yàn)結(jié)果對(duì)比以及估算的代價(jià)矩陣示例Fig.7 Comparisons of alignment accuracy using different methods regarding tracking noise level and representative cost matrices with estimated optimal paths superimposed

4 第一人稱視角數(shù)據(jù)

為了驗(yàn)證新算法在實(shí)際應(yīng)用中的性能,我們提出一個(gè)基于第一人稱視角的社交場(chǎng)景視頻數(shù)據(jù)集,包括積木、健身毯、籃球和玩具火車四個(gè)場(chǎng)景.其中,前兩個(gè)場(chǎng)景記錄了4個(gè)5～6歲兒童的交互式行為,籃球場(chǎng)景記錄了兩組成年球員之間的5 vs 5對(duì)抗性比賽,玩具火車場(chǎng)景是簡(jiǎn)單的剛體運(yùn)動(dòng).對(duì)象在場(chǎng)內(nèi)可以自由運(yùn)動(dòng),固定在其頭部的GoPro相機(jī)以第一人稱視角拍攝整個(gè)動(dòng)態(tài)場(chǎng)景,相機(jī)運(yùn)動(dòng)可近似認(rèn)為相互獨(dú)立.區(qū)別于一般監(jiān)控相機(jī)通常采取固定的位置和視角,以第三人稱視角從場(chǎng)景外部向場(chǎng)景內(nèi)部進(jìn)行拍攝,第一人稱視角相機(jī)是從場(chǎng)景內(nèi)部佩戴者的視角出發(fā)“觀察”場(chǎng)景,通過不斷變換位置或姿勢(shì)獲得對(duì)感興趣目標(biāo)的持續(xù)最佳觀測(cè)視角.每個(gè)場(chǎng)景的數(shù)據(jù)包括多個(gè)圖像序列,單個(gè)圖像序列持續(xù)時(shí)間約5～10秒,伴隨著相機(jī)平移運(yùn)動(dòng)約3～12米,繞光軸旋轉(zhuǎn)運(yùn)動(dòng)約20～60度.

數(shù)據(jù)采集時(shí),所有相機(jī)被設(shè)置到相同的拍攝模式,例如圖像尺寸、幀率等.前期我們利用FFmpeg工具包從同一場(chǎng)景的不同視頻源文件中提取圖像幀作為測(cè)試序列.該試驗(yàn)中,參考序列和觀測(cè)序列的生成幀率分別為48fps和46fps.我們利用外置閃光燈在數(shù)據(jù)采集開始時(shí)、采集中(多次)和采集結(jié)束時(shí)標(biāo)記若干同步幀,并手動(dòng)同步余下幀,以此作為視頻序列同步的真實(shí)值.

對(duì)于包含關(guān)節(jié)人體的場(chǎng)景,本文采用雙粒度跟蹤算法[23]獲取二維點(diǎn)軌跡,其優(yōu)勢(shì)在于能夠跟蹤到大量位于人體軀干及四肢靠近上端部位的點(diǎn),從而確保其空間位置線性相關(guān)假設(shè)的成立.另外,該算法提供了一個(gè)控制空間采樣率的參數(shù),可以避免像點(diǎn)分布過于集中.缺點(diǎn)是基于稠密光流估計(jì)的點(diǎn)軌跡計(jì)算開銷較大.在玩具火車場(chǎng)景中,我們利用KLT算法[24]跟蹤特征點(diǎn)軌跡.基于跟蹤算法的輸出結(jié)果,我們需要選擇位于運(yùn)動(dòng)目標(biāo)上的點(diǎn)軌跡,并去掉長(zhǎng)度過短以及明顯錯(cuò)誤的軌跡.除上述自動(dòng)跟蹤點(diǎn)軌跡外,我們還手動(dòng)標(biāo)記運(yùn)動(dòng)目標(biāo)上若干特征點(diǎn)的二維運(yùn)動(dòng)軌跡.由于遮擋導(dǎo)致某特征點(diǎn)不可見時(shí),我們根據(jù)前后相繼幀以及輔助視角推測(cè)當(dāng)前幀中該特征點(diǎn)的位置.由于超出視角范圍導(dǎo)致特征點(diǎn)不可見,我們則不做標(biāo)記.

本文利用運(yùn)動(dòng)恢復(fù)結(jié)構(gòu)算法[25?27]估計(jì)每一幀相機(jī)的空間姿態(tài).圖8展示了對(duì)各場(chǎng)景的三維重建結(jié)果,包括相機(jī)軌跡、靜態(tài)場(chǎng)景和部分運(yùn)動(dòng)點(diǎn)軌跡.在積木和健身毯場(chǎng)景中,我們?cè)噲D同步三個(gè)圖像序列.其中,相較于2號(hào)圖像序列,3號(hào)圖像序列和參考圖像序列的相機(jī)視角差別更大,相機(jī)朝向幾乎相反的方向.本文用#1和#2分別表示各場(chǎng)景中的兩組測(cè)試序列對(duì).

圖8 三維重建結(jié)果(從左到右對(duì)應(yīng)場(chǎng)景依次為:積木,健身毯,籃球#1,籃球#2和玩具火車)Fig.8 The 3D reconstruction results(From left to right:block building,exercise mat,basketball(#1),basketball(#2)and toy train.)

在重建空間點(diǎn)的運(yùn)動(dòng)軌跡時(shí),如果相機(jī)運(yùn)動(dòng)緩慢,其運(yùn)動(dòng)軌跡也可以用DCT基的線性組合表示,這會(huì)導(dǎo)致軌跡重建的精度降低[21].由于不同時(shí)刻的圖像集合可以模擬相機(jī)的快速隨機(jī)運(yùn)動(dòng),為了提高軌跡重建的質(zhì)量,我們引入非測(cè)試用圖像序列輔助軌跡重建,并人工標(biāo)注對(duì)應(yīng)點(diǎn).

除了仿真實(shí)驗(yàn)中提到的三種方法,這里還額外對(duì)比了兩種基于二維特征的方法:基于二維運(yùn)動(dòng)特征的方法MFM[16]和基于SIFT特征匹配的方法SMM[19].表1列出了各算法在真實(shí)數(shù)據(jù)集上的歸一化時(shí)域?qū)?zhǔn)誤差ε(式(11)),除玩具火車場(chǎng)景外,本文算法在各測(cè)試序列對(duì)上的同步誤差最小.當(dāng)自動(dòng)跟蹤點(diǎn)數(shù)量較少或者不滿足空間位置線性相關(guān)假設(shè)時(shí),本文算法的同步精度下降.這時(shí),可以通過添加手動(dòng)標(biāo)注圖像點(diǎn)軌跡的方法提高同步質(zhì)量.由于SMM假設(shè)同步幀在圖像內(nèi)容上最相似,從而不適用于寬基線條件下的相機(jī)同步,在積木和健身毯場(chǎng)景中的同步誤差較大.圖9～13展示了不同場(chǎng)景中各算法的幀同步結(jié)果,各算法的輸入圖像點(diǎn)疊加顯示在對(duì)應(yīng)圖像幀上,空白表示觀測(cè)序列中不存在同步幀.由于空間有限,這里僅給出了本文算法在自動(dòng)跟蹤點(diǎn)軌跡輸入下的同步結(jié)果.試驗(yàn)中令K=30,F=81,λ=0.99.關(guān)于有效秩定義中閾值λ的取值,圖14給出了本文算法在積木#1上的一組對(duì)比結(jié)果.圖14(a)為不同有效秩對(duì)同步結(jié)果的影響,圖14(b)～14(e)是不同有效秩對(duì)應(yīng)的代價(jià)矩陣.當(dāng)λ＜0.99時(shí),同步結(jié)果的精度出現(xiàn)明顯下降.而當(dāng)λ越接近于1時(shí),同步結(jié)果的精度越好.

由于本文算法只適用于幀率相同或者相近的圖像序列對(duì),幀率相差越大,秩約束越弱.圖15對(duì)比了不同幀率比時(shí)本文算法的同步誤差.圖15(a)為不同幀率比對(duì)同步結(jié)果的影響.圖15(b)～15(d)是當(dāng)觀測(cè)序列幀率分別為46fps、40fps和24fps時(shí)的代價(jià)矩陣,圖中最優(yōu)路徑的估算值和真實(shí)值分別用實(shí)線和虛線標(biāo)識(shí).試驗(yàn)中我們令參考圖像序列的生成幀率為48fps,僅改變觀測(cè)圖像序列的幀率.當(dāng)幀率比接近于2時(shí),序列同步時(shí)基系數(shù)矩陣具有較小秩的特征幾乎不明顯.

表1 真實(shí)數(shù)據(jù)集上各算法的歸一化時(shí)域?qū)?zhǔn)誤差對(duì)比(幀)Table 1 Quantitative comparisons of alignment error on real scenes(frame)

圖9 積木場(chǎng)景中各算法的時(shí)域?qū)?zhǔn)結(jié)果對(duì)比(從左到右依次為:參考序列中的圖像幀、本文算法、PDM、BPM、ECM、MFM和SMM找到的第二個(gè)序列中的對(duì)應(yīng)幀(上)及第三個(gè)序列中的對(duì)應(yīng)幀(下))Fig.9 Synchronization results on the blocks scene(From left to right:sample frames from the reference sequence,corresponding frames from the second sequence(top)and the third sequence(bottom)by our method,PDM,BPM,ECM,MFM and SMM,respectively.)

圖10 健身毯場(chǎng)景中各算法的時(shí)域?qū)?zhǔn)結(jié)果對(duì)比(同圖9)Fig.10 Synchronization results on the exercise mat scene idem as Fig.9

圖11 籃球#1場(chǎng)景中各算法的時(shí)域?qū)?zhǔn)結(jié)果對(duì)比(從左到右依次為:參考序列中的圖像幀、本文算法、PDM、BPM、ECM、MFM和SMM找到的第二個(gè)序列中的對(duì)應(yīng)幀)Fig.11 Synchronization results on the basketball scene(#1)(From left to right:sample frames from the reference sequence,corresponding frames from the second sequence by our method,PDM,BPM,ECM,MFM and SMM,respectively.)

圖12 籃球#2場(chǎng)景中各算法的時(shí)域?qū)?zhǔn)結(jié)果對(duì)比(同圖11)Fig.12 Synchronization results on the basketball scene(#2)idem as Fig.11

圖13 玩具火車場(chǎng)景中各算法的時(shí)域?qū)?zhǔn)結(jié)果對(duì)比(同圖11)Fig.13 Synchronization results on the toy train scene idem as Fig.11

圖14 不同有效秩對(duì)同步結(jié)果的影響及不同有效秩對(duì)應(yīng)的代價(jià)矩陣Fig.14 Comparisons of alignment accuracy with different λ values for efficient rank and cost matrices computed with different λ values

圖15 不同幀率比對(duì)同步結(jié)果的影響及觀測(cè)序列幀率為46fps、40fps和24fps時(shí)的代價(jià)矩陣Fig.15 Comparisons of alignment accuracy with different frame rate ratios and cost matrices computed when the frame rate of the observed sequence is 46,40 and 24,respectively

實(shí)驗(yàn)選用了如下測(cè)試環(huán)境:CPU為Inter i5-4570 4-Core 3.20GHz,8GB內(nèi)存,MATLAB R2010a編程環(huán)境.對(duì)分辨率為640像素×480像素的一幀圖像來說,預(yù)處理階段平均花費(fèi)時(shí)間為204s,其中195s用于圖像點(diǎn)軌跡跟蹤,6s用于相機(jī)空間姿態(tài)估計(jì),完整同步算法的平均運(yùn)行時(shí)間為453ms,其中429ms用于三維點(diǎn)軌跡重建.如果序列間點(diǎn)對(duì)應(yīng)關(guān)系已知,將算法中基于秩約束的度量準(zhǔn)則替換為基于三維重建點(diǎn)距離的度量準(zhǔn)則,可以大大提高算法效率,算法平均運(yùn)行時(shí)間縮短到每幀2.8ms.原因在于,對(duì)每個(gè)空間點(diǎn),后者僅需要執(zhí)行一次三維軌跡重建即可,而在基于秩約束的方法中,計(jì)算每組子序列對(duì)的對(duì)齊代價(jià)時(shí)都要執(zhí)行一次三維軌跡重建,從而保證參考序列和觀測(cè)序列具有相同的軌跡基.

5 結(jié)論

本文提出一種針對(duì)獨(dú)立運(yùn)動(dòng)相機(jī)和動(dòng)態(tài)場(chǎng)景的視頻時(shí)域同步算法.對(duì)于給定的軌跡基,利用不同圖像序列重建的空間點(diǎn)運(yùn)動(dòng)軌跡的系數(shù)能夠用于同步這些圖像序列.我們提出一種基于軌跡基系數(shù)的秩約束,結(jié)合基于圖的最優(yōu)路徑搜索算法,實(shí)現(xiàn)視頻間的非線性時(shí)域?qū)?zhǔn).本文提出方法不要求圖像點(diǎn)軌跡持續(xù)整個(gè)序列,也不依賴已知的視頻間點(diǎn)對(duì)應(yīng)關(guān)系,從而能夠處理動(dòng)態(tài)場(chǎng)景下由獨(dú)立運(yùn)動(dòng)相機(jī)拍攝的視頻間的時(shí)域同步.

本文方法僅限于若干相機(jī)同時(shí)拍攝同一場(chǎng)景的情形,類似問題例如人體動(dòng)作識(shí)別或視頻檢索,是若干相機(jī)在不同時(shí)刻拍攝相似的場(chǎng)景.本文作者在接下來的工作中會(huì)繼續(xù)研究這類問題的視頻同步方法.

1 Caspi Y,Irani M.Spatio-temporal alignment of sequences.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(11):1409?1424

2 Caspi Y,Simakov D,Irani M.Feature-based sequence-tosequence matching.International Journal of Computer Vision,2006,68(1):53?64

3 Lu C,Mandal M.A robust technique for motion-based video sequences temporal alignment.IEEE Transactions on Multimedia,2013,15(1):70?82

4 Pundik D,Moses Y.Video synchronization using temporal signals from epipolar lines.In:Proceedings of the 11th European Conference on Computer Vision.Heraklion,Crete,Greece:Springer Berlin Heidelberg,2010.15?28

5 P′adua F,Carceroni F,Santos G,Kutulakos K.Linear sequence-to-sequence alignment.IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(2):304?320

6 Yilmaz A,Shah M.Matching actions in presence of camera motion.Computer Vision and Image Understanding,2006,104(2?3):221?231

7 Rao C,Gritai A,Shah M,Syeda-Mahmood T.Viewinvariant alignment and matching of video sequences.In:Proceedings of the 9th IEEE International Conference on Computer Vision.Nice,France:IEEE,2003.939?945

8 Tresadern P A,Reid I D.Video synchronization from human motion using rank constraints.Computer Vision and Image Understanding,2009,113(8):891?906

9 Wolf L,Zomet A.Correspondence-free synchronization and reconstruction in a non-rigid scene.In:Proceedings of the 7th European Conference on Computer Vision,Workshop on Vision and Modelling of Dynamic Scenes.Copenhagen,Denmark:Springer Berlin Heidelberg,2002.

10 Wolf L,Zomet A.Wide baseline matching between unsynchronized video sequences.International Journal of Computer Vision,2006,68(1):43?52

11 Sand P,Teller S.Video matching.ACM Transactions on Graphics,2004,23(3):592?599

12 Evangelidis G D,Bauckhage C.Efficient subframe video alignment using short descriptors.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(10):2371?2386

13 Serrat J,Diego F,Lumbreras F,′Alvarez J M.Synchronization of video sequences from free-moving camreas.In:Proceedings of the 3rd Iberian Conference on Pattern Recognition and Image Analysis,Part II.Girona,Spain:Springer Berlin Heidelberg,2007.620?627

14 Diego F,Ponsa D,Serrat J,L′opez A M.Video alignment for change detection.IEEE Transactions on Image Processing,2011,20(7):1858?1869

15 Diego F,Serrat J,L′opez A M.Joint spatio-temporal alignment of sequences.IEEE Transactions on Multimedia,2013,15(6):1377?1387

16 Wang O,Schroers C,Zimmer H,Gross M,Sorkine-Hornung A.VideoSnapping:interactive synchronization of multiple videos.ACM Transactions on Graphics,2014,33(4):77:1?77:10

17 Tuytelaars T,van Gool L.Synchronizing video sequences.In:Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D C,USA:IEEE,2004.762?768

18 Lei C,Yang Y.Trifocal tensor-based multiple video synchronization with subframe optimization.IEEE Transactions on Image Processing,2006,15(9):2473?2480

19 Dexter E,P′erez P,Laptev I.Multi-view synchronization of human actions and dynamic scenes.In:Proceedings of the 2009 British Machine Vision Conference.London,UK:BMVA Press,2009.122:1?122:11

20 Akhter I,Sheikh Y,Khan S,Kanade T.Nonrigid strcture from motion in trajectory space.In:Proceedings of the 2008 Advances in Neural Information Processing Systems.Vancouver,Canada:NIPS,2008.41?48

21 Park H S,Shiratori T,Matthews I,Sheikh Y.3D reconstruction of a moving point from a series of 2D projections.In:Proceedings of the 11th European Conference on Computer Vision.Heraklion,Crete,Greece:Springer,2010.158?171

22 Kutulakos K N,Vallino J.Affine object representations for calibration-free augmented reality.In:Proceedings of the 1996 IEEE Virtual Reality Annual International Symposium.Washington DC,USA:IEEE,1996.25?36

23 Fragkiadaki K,Zhang W J,Zhang G,Shi J B.Twogranularity tracking:mediating trajectory and detection graphs for tracking under occlusions.In:Proceedings of the 12th European Conference on Computer Vision.Florence,Italy:Springer,2012.552?565

24 Lucas B D,Kanade T.An interative image registration technique with an application to stereo vision.In:Proceedings of the 7th International Joint Conference on Arti fi cial Intelligence.Vancouver,Canada:Morgan Kaufmann Publishers Inc.,1981.674?679

25 Snavely N,Seitz S M,Szeliski R.Photo tourism:exploring photo collections in 3D.ACM Transactions on Graphics,2006,25(3):835?846

26 Hartley R I,Zisserman A.Multiple View Geometry in Computer Vision(2nd edition).Cambridge:Cambridge University Press,2004.

27 Park H S,Jain E,Sheikh Y.3D gaze concurrences from head-mounted cameras.In:Proceedings of the 2012 Advances in Neural Information Processing Systems.Nevada,USA:NIPS,2012.422?430