一種基于L1范數(shù)最小化的全局運動估計算法

馮 欣,張 潔,張 杰,蔣友妮,楊 武

(重慶理工大學(xué)a.計算機科學(xué)與工程學(xué)院;b.電氣與電子工程學(xué)院,重慶 400054)

在當(dāng)前互聯(lián)網(wǎng)、移動終端和媒體技術(shù)飛速發(fā)展的時代，以視頻為主流媒介的自媒體已迅速普及，并極大地改變了信息的傳播生態(tài)。在自媒體時代，普通民眾可以通過個人攝錄、通訊工具(如智能手機等)隨時隨地拍攝記錄目擊事件，并在互聯(lián)網(wǎng)上分享傳播。然而，這種拍攝行為具有自由開放性和非正式性，使得自媒體視頻普遍存在內(nèi)容雜亂、失實的現(xiàn)象。因此，自媒體視頻內(nèi)容的有效監(jiān)管技術(shù)是目前媒體內(nèi)容管理的迫切需求。視頻內(nèi)容的分析和理解往往從對視頻對象的特征感知出發(fā)，而運動特征是分析視頻目標(biāo)對象行為的關(guān)鍵。但事實上，自媒體視頻往往是由業(yè)余拍攝者(普通民眾)采用手持設(shè)備拍攝，視頻因此普遍存在較明顯的相機運動，而這種運動會掩蓋對象的真實運動。例如，若視頻拍攝者隨著目標(biāo)對象一起運動，相機的全局運動就會抵消對象的真實運動，造成對象處于靜止?fàn)顟B(tài)的假象。對視頻全局運動進(jìn)行有效估計，并得到目標(biāo)對象的真實運動軌跡，對于視頻內(nèi)容描述、對象行為分析、面向?qū)ο蟮囊曨l編碼，及自動駕駛場景中的目標(biāo)測距等應(yīng)用起著至關(guān)重要的作用。

視頻序列圖像由前景和背景構(gòu)成，其中背景的運動通常由相機位置變化造成，稱為全局運動；而圖像中的運動對象代表前景，前景運動是運動對象相對于攝像機的運動，為局部運動。全局運動估計是對視頻序列的背景運動進(jìn)行建模，找到背景運動的規(guī)律。但在具有復(fù)雜背景的動態(tài)視頻中，前景和背景中往往存在較多噪聲，從而導(dǎo)致全局運動估計存在誤差。多年來，對全局運動估計和補償?shù)难芯恳逊e累了一定基礎(chǔ)。其中，大多數(shù)方法采用基于參數(shù)的全局運動估計，例如，基于六參數(shù)仿射模型的全局運動估計[1-2]和基于八參數(shù)透視模型的估計方法[3-4]。在基于參數(shù)的全局運動估計方法中，主要應(yīng)用運動參數(shù)模型預(yù)測當(dāng)前幀運動，并通過最小化與經(jīng)過運動補償后參考幀的匹配誤差來確定模型參數(shù)。一種確定模型參數(shù)的實現(xiàn)方案是采用梯度下降方法來最小化殘差的L2范數(shù)[5-6]。但由于序列圖像中存在前景對象的局部運動和噪聲，而最小化殘差平方和會盡量包含這些局外數(shù)據(jù)，因此對于背景復(fù)雜的全局運動估計，該類方法將會失效。另一種方案是利用隨機采樣一致性算法(RANSAC, random sample consensus)[7-11]來確定模型參數(shù)。這種方法迭代地尋找只有全局運動的內(nèi)點，而將有局部運動的前景對象和噪聲視為外點。Alibay M等人[12]使用搶占式RANSAC算法，并引入了一種運動模型的拉格朗日混合評分方法來計算運動參數(shù)。相較于普通的RANSAC算法，搶占式RANSAC算法的速度和精度都有明顯提升。但總體來說，基于RANSAC的算法得到可信模型的概率與迭代次數(shù)有關(guān)，且對內(nèi)點閾值敏感，因此可能無法得到最優(yōu)估計。在匹配方面，基于塊匹配的兩步法是經(jīng)典的全局運動估計方法[13]，近兩年也有基于SIFT特征[14]、角點特征[15]、深度卷積神經(jīng)網(wǎng)絡(luò)特征[16]等特征匹配的全局運動估計方法，但在全局運動參數(shù)估計方面大多采用基于最小二乘或RANSAC的方法。

L1范數(shù)是信號的絕對值之和，在L1范數(shù)約束下的最優(yōu)解具有稀疏性，是L0范數(shù)的最優(yōu)凸近似。L1范數(shù)最小化是尋求欠定線性系統(tǒng)b=Ax的L1范數(shù)解。在壓縮感知理論中已被證明，在一定約束條件下，最小化L1范數(shù)的解也是最優(yōu)稀疏解。與L2范數(shù)相比，L1范數(shù)對噪聲和局外點的影響更具有魯棒性。文獻(xiàn)[17]將求解誤差(由污損、遮擋等噪聲等引起的稀疏誤差)的最小化L1范數(shù)成功應(yīng)用于解決人臉對齊問題，并提出一種基于增廣拉格朗日方法(ALM, augmented lagrangian methods)的快速凸優(yōu)化求解方法。文獻(xiàn)[18]也將L1范數(shù)最小化應(yīng)用于基于對象的視頻編碼中。提出一種基于L1范數(shù)最小化的全局運動參數(shù)估計方法，并實現(xiàn)一套有效的全局補償方案。假設(shè)視頻相鄰兩幀圖像包含遵循六參數(shù)仿射變換模型的全局運動，通過最小化當(dāng)前幀經(jīng)過運動補償?shù)膮⒖紟c當(dāng)前幀誤差的L1范數(shù)進(jìn)行全局運動模型參數(shù)估計；并在此基礎(chǔ)上，提出將每幀對象的坐標(biāo)迭代映射到視頻中間幀來揭示對象真實運動軌跡的全局運動補償方案。通過在大量包含復(fù)雜相機運動的視頻上進(jìn)行實驗，結(jié)果表明方法能夠準(zhǔn)確地對復(fù)雜場景中的全局運動進(jìn)行估計和補償，且基于L1范數(shù)最小化的運動參數(shù)估計方法具有較好魯棒性。

1 基于L1范數(shù)最小化的全局運動參數(shù)估計和補償算法

不同內(nèi)容的視頻中包含不同對象的運動軌跡，對象的運動軌跡由水平和垂直方向的坐標(biāo)表示?；谀繕?biāo)對象原始運動軌跡已知的前提，即目標(biāo)對象已通過應(yīng)用現(xiàn)有的目標(biāo)檢測算法[19](Faster RCNN)定位及跟蹤算法[20](采用基于稀疏編碼的跟蹤算法)獲得原始運動軌跡。

自然場景視頻往往包含由攝像機運動導(dǎo)致的全局運動和被全局運動掩蓋的目標(biāo)對象的局部運動。如圖1所示，(a)中黃色曲線是通過直接應(yīng)用跟蹤算法得到的兩目標(biāo)對象的原始運動軌跡；(b)中黃色曲線是經(jīng)過全局運動補償后目標(biāo)對象的真實軌跡。目標(biāo)對象是場景中間的2個人，2人的真實運動軌跡是沿著街道有較長距離的位移如圖1(b)，但對比2幅軌跡圖可以發(fā)現(xiàn)，由于攝像機與目標(biāo)對象的相對運動較小，直接應(yīng)用跟蹤算法得到的原始目標(biāo)軌跡如圖1(a)與對象的真實運動不符。

圖1 示例視頻中目標(biāo)對象的原始軌跡(a)和真實軌跡(b)示意圖。

1.1 基于迭代變換映射的全局運動補償方法

(1)

其中

圖2 基于相鄰幀運動參數(shù)迭代映射的全局運動補償方法

1.2 基于L1范數(shù)最小化的全局運動參數(shù)估計

(2)

(3)

式中：p∈Ω，Ω為圖像像素空間。對于仿射模型，給定一個像素(px,py)，其對應(yīng)仿射變換位置為(p′x,p′y)

(4)

式中：N是R中的像素數(shù)。將R沿著X和Y方向的梯度圖像分別設(shè)為Rx和Ry，則Jacobian矩陣J可變?yōu)?/p>

J=[RxpxRxpyRxRypxRypyRy],

(7)

(8)

(9)

從而，公式(9)在無約束的增廣拉格朗日函數(shù)L中可以寫為以下形式

(10)

(子問題w.r.t S)

(11)

(12)

(更新拉格朗日乘子)

(13)

表1 基于最小化L1范數(shù)的全局運動估計算法

相對于全局運動估計，具有全局運動的運動對象是不符合其運動規(guī)律的異常點。因此，為減少異常點對全局運動的估計的影響，利用對象檢測的矩形區(qū)域?qū)γ恳粋€對象定義一個二值掩模M，以使運動對象對應(yīng)像素點不參與全局運動估計的計算。M中運動對象對應(yīng)位置的元素為0，其余背景像素對應(yīng)位置的元素為1。

于是上述全局運動參數(shù)估計的目標(biāo)函數(shù)轉(zhuǎn)變?yōu)?/p>

(14)

公式(14)根據(jù)表1算法步驟進(jìn)行求解。

2 數(shù)據(jù)集及實驗結(jié)果分析

在多個自媒體用戶拍攝的視頻上進(jìn)行了實驗，其中包括7個選自哥倫比亞消費者視頻(CCV, columbia consumer video)數(shù)據(jù)集[23]，5個選自VOT[24]、OTB[25]、MOT[26]等目標(biāo)跟蹤數(shù)據(jù)集，以及一些來自媒體網(wǎng)站的自媒體視頻樣本。整個實驗數(shù)據(jù)集包含了豐富的場景、內(nèi)容及全局/局部運動模式。每個視頻被預(yù)處理成約為10 s(幀率30 FPS)，且只包含單個場景鏡頭的視頻段。數(shù)據(jù)集示例視頻幀如圖3所示。

圖3 全局運動補償實驗數(shù)據(jù)集示例幀

圖4給出了示例視頻段的10幀圖像?？梢钥吹?，該視頻記錄了2名女子在公園沿路慢跑的場景。圖5分別給出了由運動跟蹤算法得到的對象原始軌跡(如圖5(a)中黃色曲線)，利用全局運動補償后的運動軌跡(如圖5(b)中黃色曲線)和基于RANSAC方法補償后的運動軌跡(如圖5(c)中黃色曲線)。由于視頻拍攝跟隨了兩名女子的運動，原跟蹤軌跡顯示2名女子在原地?zé)o序地運動，而經(jīng)過全局運動糾正的軌跡(如圖5(b)、(c)所示)則揭示出2名女子在跑道上長距離運動的真實情況。結(jié)合圖4中視頻原幀序列，對比圖5(b)、(c)可以看出，雖然基于RANSAC的全局運動估計算法能夠在一定程度上反映對象的運動趨勢，但與對象的真實運動軌跡仍有一定距離，而本文提出的基于L1范數(shù)最小化的全局運動參數(shù)估計方法能夠更好地對全局運動進(jìn)行估計，其經(jīng)過補償后的軌跡更符合對象的真實運動。

圖4 視頻段原序列幀(從連續(xù)300幀中以均勻間隔抽取10幀)

圖5 對應(yīng)圖4示例視頻段的對象運動軌跡與利用基于不同運動補償方法糾正后的運動軌跡。

圖6分別給出了視頻中2個目標(biāo)對象使用2種全局運動估計算法在X方向和Y方向上軌跡進(jìn)行糾正的前后對比。可以看出，基于L1范數(shù)最小化的全局運動估計算法和運動補償方法能夠很好地揭示運動對象在視頻中沿著道路的慢跑運動軌跡，而基于RANSAC的方法則沒有很好的找到全局運動規(guī)律并將運動對象的真實運動恢復(fù)出來。圖7給出了更多基于全局運動補償?shù)倪\動對象軌跡與原對象運動軌跡的對比。實驗結(jié)果表明，提出的基于L1范數(shù)最小化進(jìn)行全局運動參數(shù)估計能夠準(zhǔn)確地反應(yīng)視頻的全局運動規(guī)律，并通過全局運動補償方案恢復(fù)出運動對象的真實運動軌跡。

圖6 全局運動補償結(jié)果對比

注：圖中為示例視頻段的中間幀，黃色曲線為對象運動軌跡

3 結(jié)束語

視頻序列中通常包含具有不穩(wěn)定的相機運動，這種圖像的全局運動會掩蓋目標(biāo)對象的真實運動軌跡。為了估計出全局運動的規(guī)律，從而恢復(fù)出目標(biāo)對象的真實運動，本文提出了基于L1范數(shù)最小化的全局運動參數(shù)估計算法，和基于相鄰幀運動參數(shù)迭代映射的全局運動補償方法從視頻的原始軌跡中獲得出對象的真實運動軌跡。實驗結(jié)果表明本文提出的全局運動參數(shù)估計和補償算法能有效地把握全局運動的規(guī)律，并從中準(zhǔn)確恢復(fù)出目標(biāo)對象的真實運動軌跡。本文提出的方法目前只能離線分析視頻的全局運動，如何在線高效地對視頻全局運動進(jìn)行有效估計和補償將是本文進(jìn)一步的工作。