宋傳鳴, 閔 新, 閆小紅, 王相海, 尹寶才

1(遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,遼寧 大連 116029)

2(大連理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,遼寧 大連 116024)

運(yùn)動(dòng)估計(jì)是一項(xiàng)高效率的去除視頻時(shí)間域冗余的預(yù)測(cè)技術(shù),為H.26x、MPEG和AVS等系列編碼標(biāo)準(zhǔn)貢獻(xiàn)了大部分的性能提升[1,2].然而,多項(xiàng)研究結(jié)果表明[1,3,4],僅整數(shù)像素精度的運(yùn)動(dòng)估計(jì)所耗費(fèi)的計(jì)算資源就占編碼器全部資源的 40%～80%;若將分?jǐn)?shù)像素精度的運(yùn)動(dòng)估計(jì)也考慮在內(nèi),其運(yùn)算代價(jià)無(wú)疑更高.因此,為了在計(jì)算復(fù)雜度、硬件實(shí)現(xiàn)難度和預(yù)測(cè)精度之間進(jìn)行折中,現(xiàn)有視頻編碼標(biāo)準(zhǔn)多年來(lái)始終采用了僅能刻畫(huà)水平、豎直等平移運(yùn)動(dòng)的塊匹配算法,并陸續(xù)提出了多種快速運(yùn)動(dòng)估計(jì)策略,大致可分為以下7類.

(1) 基于候選向量下采樣的策略[5-13]:這類策略的基本思想是只計(jì)算搜索窗口中一部分候選向量的匹配誤差,從中找出誤差最小的向量作為最優(yōu)運(yùn)動(dòng)向量,如菱形搜索、非對(duì)稱十字多層次六邊形格點(diǎn)搜索UMHexagonS、測(cè)試域搜索TZSearch和拋物線搜索等.

(2) 基于像素下采樣的策略[14-19]:該類策略的基本思想是只計(jì)算當(dāng)前宏塊中一部分像素的匹配誤差,并將其作為該宏塊的誤差用于最優(yōu)運(yùn)動(dòng)向量的判斷,如多分辨率搜索、梅花形下采樣搜索和自適應(yīng)像素下采樣搜索等.

(3) 基于像素預(yù)排序的策略[20-23]:此類算法的主要思路是在計(jì)算某個(gè)候選向量的匹配誤差時(shí),優(yōu)先對(duì)當(dāng)前宏塊的較大匹配誤差進(jìn)行累加,當(dāng)累計(jì)誤差和大于已知的最小誤差時(shí)就提前中止該候選向量的判斷,從而達(dá)到降低計(jì)算量的目的,如部分失真搜索等.

(4) 基于低復(fù)雜度匹配函數(shù)的策略[24-28]:該類算法的主要思想是采用較低復(fù)雜度的匹配誤差函數(shù)替代傳統(tǒng)的均方誤差函數(shù),進(jìn)而降低誤差匹配過(guò)程的計(jì)算量,常用函數(shù)包括像素誤差分類(pel difference classification,簡(jiǎn)稱PDC)、相異像素?cái)?shù)目(different pixel count,簡(jiǎn)稱DPC)、改進(jìn)的異或函數(shù)等.

(5) 基于低比特深度像素的策略[29-34]:這類策略的基本思路是通過(guò)某種映射方法將8bit深度的像素變換為低位深的像素,以此來(lái)減少運(yùn)動(dòng)估計(jì)的計(jì)算開(kāi)銷,如1bit搜索和2bit搜索等,常與第(4)類策略結(jié)合使用.

(6) 基于哈希映射的策略[35,36]:這類算法主要通過(guò)哈希函數(shù)將待匹配塊映射為一個(gè)哈希值,從而借助哈希表來(lái)提高較大搜索窗口下的塊匹配效率.

(7) 基于塊分類的策略[1,37]:該種策略的核心思想是按照率失真準(zhǔn)則將待匹配塊分成不同運(yùn)動(dòng)幅度的類,并為不同類別的待匹配塊選取恰當(dāng)?shù)倪\(yùn)動(dòng)估計(jì)算法完成預(yù)測(cè),從而在保證預(yù)測(cè)效率的情況下盡量降低計(jì)算量.

一方面,盡管眾多研究人員對(duì)基于平移模型的塊匹配運(yùn)動(dòng)估計(jì)算法進(jìn)行了上述改進(jìn),但仍未從根本上解決運(yùn)動(dòng)估計(jì)環(huán)節(jié)計(jì)算負(fù)載過(guò)高的問(wèn)題.另一方面,塊平移模型既無(wú)法有效預(yù)測(cè)由物體旋轉(zhuǎn)、縮放、變形和攝像機(jī)運(yùn)動(dòng)產(chǎn)生的非剛性復(fù)合運(yùn)動(dòng),又不能準(zhǔn)確表示具有復(fù)雜形狀的運(yùn)動(dòng)區(qū)域,導(dǎo)致在運(yùn)動(dòng)物體邊緣產(chǎn)生大幅值的預(yù)測(cè)殘差,影響后續(xù)的熵編碼效率.為此,H.264/AVC(advanced video coding)和H.265/HEVC(high efficiency video coding)等新一代編碼標(biāo)準(zhǔn)將早期的正方形宏塊改進(jìn)為對(duì)稱或非對(duì)稱的精細(xì)矩形塊,并進(jìn)一步采用復(fù)雜的分層次可變尺寸塊結(jié)構(gòu)、分?jǐn)?shù)像素運(yùn)動(dòng)向量、多參考幀和廣義B幀等多種優(yōu)化手段來(lái)逼近復(fù)雜運(yùn)動(dòng)場(chǎng)和運(yùn)動(dòng)物體.然而,文獻(xiàn)[4]通過(guò)實(shí)驗(yàn)統(tǒng)計(jì)發(fā)現(xiàn),隨著塊尺寸的減小和運(yùn)動(dòng)向量精度的提高,用于編碼運(yùn)動(dòng)向量、塊劃分方式的碼流開(kāi)銷和各種軟/硬件計(jì)算開(kāi)銷也逐漸增加,尤其是當(dāng)矩形塊尺寸減小至4×4像素、向量精度達(dá)到1/16像素時(shí),軟/硬件開(kāi)銷的增加幅度甚至超過(guò)了率失真性能的提升幅度.這個(gè)結(jié)論說(shuō)明,僅僅依靠塊平移模型來(lái)實(shí)現(xiàn)運(yùn)動(dòng)估計(jì)愈來(lái)愈無(wú)法很好地滿足高清/超高清視頻、面向視頻通信的桌面視頻和面向虛擬現(xiàn)實(shí)應(yīng)用的全景視頻等視頻編碼的需求[38,39].因此,越來(lái)越多的學(xué)者認(rèn)為,研究能有效表示復(fù)雜運(yùn)動(dòng)場(chǎng)的高階運(yùn)動(dòng)模型及其參數(shù)求解策略是幀間運(yùn)動(dòng)估計(jì)的未來(lái)發(fā)展方向之一[40-42],對(duì)于下一代視頻編碼效率的大幅提升有重要意義.

本文首先對(duì)比分析典型的高階運(yùn)動(dòng)模型的優(yōu)勢(shì)和不足,進(jìn)而介紹彈性運(yùn)動(dòng)模型的基本思想.然后,針對(duì)彈性運(yùn)動(dòng)估計(jì)仍然存在的計(jì)算量高、收斂不穩(wěn)定的問(wèn)題,引進(jìn)Levenberg-Marquardt方法進(jìn)行優(yōu)化求解,并從黑塞矩陣(Hessian matrix)的快速計(jì)算和對(duì)角矩陣阻尼系數(shù)的自適應(yīng)更新兩方面做出改進(jìn),提出一種基于改進(jìn)Levenberg-Marquardt法的視頻彈性運(yùn)動(dòng)估計(jì)算法.實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性.

1 相關(guān)工作

鑒于平移模型的不足,研究人員將高階運(yùn)動(dòng)模型引入到運(yùn)動(dòng)估計(jì)中,利用高階函數(shù)產(chǎn)生 1個(gè)或多個(gè)扭曲的參考幀,實(shí)現(xiàn)更高質(zhì)量的運(yùn)動(dòng)補(bǔ)償.依據(jù)模型顯式表現(xiàn)形式的不同,本文將這些運(yùn)動(dòng)估計(jì)/補(bǔ)償算法劃分為4類.

(1) 基于網(wǎng)格模型的運(yùn)動(dòng)估計(jì)[43-49]:該類算法主要利用三角形網(wǎng)格或四邊形網(wǎng)格來(lái)刻畫(huà)視頻圖像中的運(yùn)動(dòng)物體或內(nèi)容,能夠?qū)崿F(xiàn)較為可靠的運(yùn)動(dòng)/靜止區(qū)域劃分,并可緩解運(yùn)動(dòng)補(bǔ)償幀的塊效應(yīng),取得更高的主觀質(zhì)量.但是,文獻(xiàn)[50]發(fā)現(xiàn),基于網(wǎng)格模型的運(yùn)動(dòng)估計(jì)對(duì)于相鄰網(wǎng)格共有節(jié)點(diǎn)的控制和對(duì)編碼率失真的優(yōu)化較為困難,尚缺少有效的優(yōu)化方法,而且需要額外傳輸網(wǎng)格劃分方式的同步信息.

(2) 基于多項(xiàng)式模型的運(yùn)動(dòng)估計(jì)[38,50-56]:這類算法的基本思路是采用4-參數(shù)的一元一次縮放變換模型、6-參數(shù)的二元一次仿射變換模型、8-參數(shù)的二元二次投影變換模型、12-參數(shù)的二元二次變換模型及其混合模型產(chǎn)生全局扭曲的參考幀,能夠比平移模型更加有效地捕獲物體的平移、旋轉(zhuǎn)、拉伸、仿射、透視和景深變化等豐富的運(yùn)動(dòng)形式.但是,隨著模型參數(shù)的增多,其搜索復(fù)雜度明顯提高,并且對(duì)局部運(yùn)動(dòng)的刻畫(huà)能力不足.

(3) 基于縮放模型的運(yùn)動(dòng)估計(jì)[57-59]:考慮到多參數(shù)模型的運(yùn)算復(fù)雜度,該類算法簡(jiǎn)化了基于多項(xiàng)式模型的運(yùn)動(dòng)估計(jì),通過(guò)在平移模型基礎(chǔ)上引進(jìn)縮放因子來(lái)表示物體的拉伸運(yùn)動(dòng)和景深變化等全局運(yùn)動(dòng),但卻不能描述3D錯(cuò)切和由于攝像機(jī)的俯仰而產(chǎn)生的物體旋轉(zhuǎn)以及物體的局部變形運(yùn)動(dòng)等.

(4) 基于彈性模型的運(yùn)動(dòng)估計(jì)[42,60-63]:該類算法采用離散余弦函數(shù)、小波基函數(shù)或樣條函數(shù)刻畫(huà)物體的平移、錯(cuò)切和扭曲運(yùn)動(dòng),既能表示全局和局部運(yùn)動(dòng),又可通過(guò)調(diào)整模型參數(shù)個(gè)數(shù)來(lái)控制運(yùn)動(dòng)估計(jì)的計(jì)算復(fù)雜度.文獻(xiàn)[60]的實(shí)驗(yàn)結(jié)果表明,基于彈性模型的運(yùn)動(dòng)估計(jì)在相同碼率下獲得了比塊平移運(yùn)動(dòng)估計(jì)高0.7dB的運(yùn)動(dòng)補(bǔ)償峰值信噪比(peak signal-to-noise ratio,簡(jiǎn)稱PSNR);文獻(xiàn)[61]的結(jié)論顯示,彈性運(yùn)動(dòng)模型可將H.265的輸出碼率降低3%～12%,而運(yùn)動(dòng)補(bǔ)償失真僅損失1%;文獻(xiàn)[62,63]則通過(guò)優(yōu)化彈性模型的求解方法取得了更加理想的預(yù)測(cè)效率,其平均PSNR比傳統(tǒng)彈性運(yùn)動(dòng)估計(jì)提高了1.42dB,并且比基于塊平移模型的全搜索算法高出1.73dB.

因此,綜合各個(gè)模型之間的對(duì)比和現(xiàn)有研究結(jié)論可知,彈性運(yùn)動(dòng)模型是一種表示復(fù)雜運(yùn)動(dòng)場(chǎng)的高效率模型.

目前,關(guān)于視頻彈性運(yùn)動(dòng)估計(jì)的研究主要集中在以下兩個(gè)方面.

(1) 彈性運(yùn)動(dòng)模型與視頻編碼標(biāo)準(zhǔn)的結(jié)合方式.文獻(xiàn)[42]將彈性運(yùn)動(dòng)估計(jì)引進(jìn)到H.264中,依據(jù)圖像的幾何特征,采用不同斜率的線段劃分待預(yù)測(cè)塊,獲得其三角形或四邊形網(wǎng)格表示,從而使彈性模型能夠更準(zhǔn)確地描述復(fù)雜形狀的運(yùn)動(dòng)區(qū)域,更好地適應(yīng)多樣的局部運(yùn)動(dòng).文獻(xiàn)[39]將彈性運(yùn)動(dòng)估計(jì)作為 HEVC的一種可選模式,通過(guò)已解碼幀計(jì)算彈性運(yùn)動(dòng)場(chǎng),再利用該運(yùn)動(dòng)場(chǎng)重建彈性變形后的參考幀,進(jìn)而根據(jù)率失真準(zhǔn)則在平移模型和彈性模型之間進(jìn)行自適應(yīng)的選擇.但是,文獻(xiàn)[39,42]簡(jiǎn)單地使用傳統(tǒng)的高斯-牛頓法求解彈性運(yùn)動(dòng)向量,既未能避免彈性運(yùn)動(dòng)估計(jì)的高計(jì)算量,又無(wú)法避免搜索陷入局部最優(yōu),這會(huì)從根本上影響彈性運(yùn)動(dòng)估計(jì)的有效性和實(shí)用性.

(2) 彈性運(yùn)動(dòng)向量的優(yōu)化求解.文獻(xiàn)[64]提出了基于1bit深度像素的高斯-牛頓迭代法,文獻(xiàn)[65,66]又進(jìn)一步將其推廣到了2bit深度像素的情況下.盡管這3種算法通過(guò)避免黑塞矩陣及其逆矩陣的計(jì)算并固定迭代步長(zhǎng)的方式實(shí)現(xiàn)了較快的運(yùn)動(dòng)估計(jì)速度,但是由于只采用了兩個(gè)梯度下降方向,并且低位深像素的梯度往往不同于 8 bit深度像素,其預(yù)測(cè)質(zhì)量與基于8bit深度像素的彈性運(yùn)動(dòng)估計(jì)尚存在較大差距.文獻(xiàn)[62,63]則通過(guò)大量實(shí)驗(yàn)發(fā)現(xiàn),彈性運(yùn)動(dòng)模型的高斯-牛頓解法對(duì)初始迭代點(diǎn)和迭代步長(zhǎng)較為敏感,即固定的初始迭代點(diǎn)和迭代步長(zhǎng)無(wú)法求解出全局最優(yōu)解,進(jìn)而采用 2bit深度像素和均勻搜索模板將初始迭代點(diǎn)置于全局最優(yōu)解的單調(diào)區(qū)間內(nèi),再利用離散余弦變換的低頻能量比率和黃金分割法調(diào)整迭代步長(zhǎng),使之適應(yīng)目標(biāo)函數(shù)的線性程度,明顯提升了彈性運(yùn)動(dòng)估計(jì)的計(jì)算效率和補(bǔ)償質(zhì)量.然而,作為一類牛頓型優(yōu)化求解方法,文獻(xiàn)[62,63]的快速算法在本質(zhì)上仍不能避免牛頓型方法存在的不足,也就是說(shuō),目標(biāo)函數(shù)偏離線性的程度越大,初始迭代點(diǎn)距離全局最優(yōu)點(diǎn)越遠(yuǎn),高斯-牛頓法的收斂速度就越慢,甚至出現(xiàn)遠(yuǎn)離最優(yōu)點(diǎn)或不收斂的現(xiàn)象[67].事實(shí)上,視頻數(shù)據(jù)以及運(yùn)動(dòng)補(bǔ)償誤差的復(fù)雜性,匹配誤差曲面往往不會(huì)呈現(xiàn)給我們期望的理想線性性,文獻(xiàn)[62]也已驗(yàn)證了這一點(diǎn).

因此,對(duì)于上述兩方面的研究工作來(lái)講,將現(xiàn)有彈性運(yùn)動(dòng)模型的高斯-牛頓求解方法做出改進(jìn)乃至改變是非常必要的,進(jìn)而在降低其計(jì)算量的同時(shí),使之收斂到更優(yōu)解.這一問(wèn)題的解決將有助于彈性運(yùn)動(dòng)估計(jì)走向?qū)嵱?而從我們所掌握的文獻(xiàn)來(lái)看,目前尚鮮見(jiàn)相關(guān)研究.

2 彈性運(yùn)動(dòng)模型以及傳統(tǒng)彈性運(yùn)動(dòng)估計(jì)算法

為了便于下文工作的論述,本節(jié)首先介紹彈性運(yùn)動(dòng)模型,然后介紹運(yùn)動(dòng)向量的典型求解方法.

2.1 彈性運(yùn)動(dòng)估計(jì)模型簡(jiǎn)介

視頻運(yùn)動(dòng)估計(jì)的目標(biāo)是在參考幀的某個(gè)搜索窗口內(nèi),為當(dāng)前待預(yù)測(cè)塊I(尺寸為B×B像素)搜索到一個(gè)運(yùn)動(dòng)向量(矢量),使得I與其最佳匹配塊R之間的誤差平方和(sum of squared difference)最小,即:

其中,xij和yij分別表示當(dāng)前塊中i行j列像素的x坐標(biāo)和y坐標(biāo);m表示彈性運(yùn)動(dòng)向量;w(·)表示彈性運(yùn)動(dòng)函數(shù),其定義為

其中,p表示運(yùn)動(dòng)矢量的分量數(shù)目;φk表示彈性運(yùn)動(dòng)模型的基函數(shù).雖然樣條函數(shù)、仿射函數(shù)、小波函數(shù)都可作為基函數(shù),但是文獻(xiàn)[60]經(jīng)過(guò)對(duì)比發(fā)現(xiàn),選取離散余弦函數(shù)作為基函數(shù)對(duì)連續(xù)運(yùn)動(dòng)場(chǎng)具有較高的表示效率,即:

2.2 彈性運(yùn)動(dòng)估計(jì)的高斯-牛頓求解方法

為了獲得彈性運(yùn)動(dòng)向量 m,文獻(xiàn)[39,42,60-63]均采用了高斯-牛頓法進(jìn)行求解,其主要思想是對(duì)匹配誤差函數(shù)(公式(1))進(jìn)行線性逼近,再通過(guò)反復(fù)迭代求出極小值.具體地,假設(shè)當(dāng)前迭代點(diǎn)是 m,并令像素(xij,yij)處的預(yù)測(cè)誤差為eij(m)=R(w(xij,m),w(yij,m))-I(xij,yij),則函數(shù)eij(m)可用其在m處的1階泰勒展開(kāi)式近似表示.

為取得上式的最小值,將其對(duì)Δm取導(dǎo)并令導(dǎo)數(shù)為0,整理后,則有:

其中,上標(biāo)T表示向量轉(zhuǎn)置.令

顯然,H是一個(gè)p×p階的黑塞矩陣,并且根據(jù)求導(dǎo)的鏈?zhǔn)椒▌t和eij(m)、公式(2)、公式(3)的定義,有:

其中,?R?xi′j和?R?yi′j分別表示匹配塊沿著水平和豎直方向的梯度分量;?w?m是一個(gè)雅克比矩陣,并且?w?mk=?w?mp/2+k=φk(i,j),k∈［1,p/2］.于是有Δm=H-1b,進(jìn)而得到更新后的彈性運(yùn)動(dòng)向量m:m←m+Δm.

3 基于Levenberg-Marquardt法的彈性運(yùn)動(dòng)估計(jì)

對(duì)于彈性運(yùn)動(dòng)估計(jì)這類非線性無(wú)約束最小二乘問(wèn)題,主要有兩類典型的優(yōu)化解法:牛頓型方法(如牛頓法和高斯-牛頓法)和負(fù)梯度方法(如最速下降法和對(duì)角線近似法)[67].理論表明,當(dāng)初始迭代點(diǎn)距離局部極小點(diǎn)較近時(shí),牛頓法和高斯-牛頓法的收斂速度更快;反之,牛頓法和高斯-牛頓法則收斂較慢,甚至?xí)捎诤谌仃嚻娈惢虿B(tài)導(dǎo)致無(wú)法收斂的情形發(fā)生[68],而此時(shí)最速下降法和對(duì)角線近似法的收斂效率更高.故而,彈性運(yùn)動(dòng)估計(jì)的高斯-牛頓解法對(duì)初始搜索點(diǎn)存在一定的敏感性,文獻(xiàn)[62,63]的研究也驗(yàn)證了這一結(jié)論.在這種情況下,文獻(xiàn)[69,70]將對(duì)角線近似法與高斯-牛頓法相結(jié)合,修正了高斯-牛頓黑塞矩陣,提出了一種 Levenberg-Marquardt(下文簡(jiǎn)稱L-M)黑塞矩陣:

從其定義可見(jiàn),當(dāng)δ<<1時(shí),HLM近似為高斯-牛頓黑塞矩陣H;而當(dāng)δ>>1時(shí),HLM則近似為對(duì)角矩陣(僅差1個(gè)步長(zhǎng)因子1/δ).

在HLM的基礎(chǔ)上,本文提出了基于L-M算法的彈性運(yùn)動(dòng)估計(jì),其計(jì)算步驟如下所示.

Step 1. 輸入當(dāng)前待預(yù)測(cè)塊I和迭代次數(shù)T,并將彈性運(yùn)動(dòng)向量m初始化為0,令δ←1,迭代次數(shù)t←1.

Step 2. 根據(jù)彈性運(yùn)動(dòng)向量m和彈性運(yùn)動(dòng)函數(shù)(公式(2)、公式(3))計(jì)算I的匹配塊R(w(xij,m),w(yij,m)).

Step 3. 計(jì)算初始運(yùn)動(dòng)補(bǔ)償誤差eij(m)及其平方和D0.

Step 4. 計(jì)算匹配塊的梯度?R.

Step 5. 計(jì)算雅克比矩陣?w?m.

Step 9. 根據(jù)公式(11)計(jì)算L-M黑塞矩陣HLM.

Step 11. 更新當(dāng)前塊I的匹配塊R(w(xij,m),w(yij,m)),并計(jì)算它與當(dāng)前塊I的匹配誤差平方和Dt.

Step 12. 若Dt＞Dt-1,則令δ←δ×λ(λ為對(duì)角矩陣阻尼系數(shù)的更新因子,傳統(tǒng) L-M 算法一般將其設(shè)置為10),轉(zhuǎn)入 Step 9;否則,轉(zhuǎn)入 Step 13.

與高斯-牛頓優(yōu)化算法相比,L-M 算法對(duì)于光滑目標(biāo)函數(shù)體現(xiàn)出收斂速度快、穩(wěn)定性能好等優(yōu)點(diǎn).但是,一方面它在每次迭代時(shí)均需計(jì)算黑塞矩陣及逆矩陣,其漸近時(shí)間復(fù)雜度達(dá)到了max｛O(p3),O(p2B2)｝;另一方面,現(xiàn)有文獻(xiàn)往往將對(duì)角矩陣阻尼系數(shù)的更新因子λ設(shè)置成正數(shù),這對(duì)于階數(shù)較低的、形式簡(jiǎn)單的顯式目標(biāo)函數(shù)較為有效.但是,視頻運(yùn)動(dòng)補(bǔ)償?shù)恼`差曲面非常復(fù)雜,甚至無(wú)法用任何一個(gè)顯式函數(shù)表示出來(lái).實(shí)驗(yàn)結(jié)果表明,λ為正數(shù)在某些情況下反而會(huì)增大運(yùn)動(dòng)補(bǔ)償誤差,而將其設(shè)置為負(fù)數(shù)卻更有效.基于上述考慮,下文從黑塞矩陣的快速計(jì)算和對(duì)角矩陣系數(shù)的自適應(yīng)更新兩方面改進(jìn)L-M算法,進(jìn)一步提高彈性運(yùn)動(dòng)估計(jì)/補(bǔ)償?shù)男?

4 黑塞矩陣的快速計(jì)算方法

由第 2節(jié)和第 3節(jié)可知,黑塞矩陣的計(jì)算與參考?jí)K梯度、彈性基函數(shù)有關(guān),并且黑塞矩陣本身也具有明顯的對(duì)稱性.為此,本文從兩個(gè)角度加快黑塞矩陣的計(jì)算:(a) 根據(jù)2D離散余弦函數(shù)矩陣的特點(diǎn)減少基函數(shù)的計(jì)算量;(b) 利用黑塞矩陣的對(duì)稱性避免重復(fù)計(jì)算.

4.1 彈性運(yùn)動(dòng)基函數(shù)的快速計(jì)算

根據(jù)公式(4),彈性運(yùn)動(dòng)模型共有4種基函數(shù).以B=8為例,圖1給出了4種基函數(shù)對(duì)應(yīng)的8×8矩陣的數(shù)值分布.其中,符號(hào)A～H分別代表 cos(π/16)、cos(3π/16)、cos(5π/16)、cos(7π/16)、cos(9π/16)、cos(11π/16)、cos(13π/16)和 cos(15π/16).

從圖1可見(jiàn):① 第1個(gè)基函數(shù)矩陣只包含元素1;② 第2個(gè)基函數(shù)矩陣的元素只與縱坐標(biāo)有關(guān);③ 第3個(gè)基函數(shù)矩陣的元素只與橫坐標(biāo)有關(guān);④ 第4個(gè)基函數(shù)矩陣的元素為第2個(gè)和第3個(gè)基函數(shù)矩陣的對(duì)應(yīng)元素之積.故此,基函數(shù)矩陣可通過(guò)少量計(jì)算和大量賦值得到,即:首先,φ1對(duì)應(yīng)的矩陣只需全部賦值為 1;其次,φ2對(duì)應(yīng)的矩陣只需計(jì)算一行,其余各行通過(guò)賦值得到,轉(zhuǎn)置后再賦值給φ3的各列;最后,將φ2和φ3矩陣的上三角元素對(duì)應(yīng)相乘得到φ4矩陣的上三角元素,而下三角元素可通過(guò)轉(zhuǎn)置賦值獲得.這樣,需要計(jì)算的元素個(gè)數(shù)僅占全部基函數(shù)矩陣元素?cái)?shù)量的17%.

4.2 高斯-牛頓黑塞矩陣的快速計(jì)算

由黑塞矩陣的定義可知,其上三角元素和下三角元素關(guān)于主對(duì)角線對(duì)稱,即Ha,b=Hb,a(1≤a≤b≤B).

此外,根據(jù)黑塞矩陣的計(jì)算過(guò)程和第 4.1節(jié)的基函數(shù)矩陣數(shù)值分布特點(diǎn)還可進(jìn)一步發(fā)現(xiàn)高斯-牛頓黑塞矩陣中各元素之間的相等關(guān)系,從而降低黑塞矩陣的計(jì)算量,下面以H1,4和H2,3為例來(lái)分析.由兩個(gè)元素的定義,有:

同理可得,

而由圖1所示的基函數(shù)矩陣數(shù)值分布可知,φ1和φ4對(duì)應(yīng)元素的乘積與φ2和φ3對(duì)應(yīng)元素的乘積相同,即對(duì)于?i,j∈[1,8],有φ1(i,j)φ4(i,j)=φ2(i,j)φ3(i,j).因此有 H1,4=H2,3.

采用與上述相同的推導(dǎo)過(guò)程以及公式(14)的等價(jià)關(guān)系,就可得到圖 2所示的高斯-牛頓黑塞矩陣的數(shù)值分布.可見(jiàn),我們只需計(jì)算64個(gè)元素中的27個(gè):A～H、a～s,其余的37個(gè)元素只需簡(jiǎn)單賦值即可得到.同時(shí),L-M黑塞矩陣(見(jiàn)公式(11))第2項(xiàng)的對(duì)角元素與高斯-牛頓黑塞矩陣的對(duì)角元素A～H相同,無(wú)需計(jì)算.

綜上,L-M黑塞矩陣HLM中需要計(jì)算的元素個(gè)數(shù)僅占全部元素?cái)?shù)量的37.5%.

5 對(duì)角矩陣阻尼系數(shù)的自適應(yīng)更新方法

5.1 λ的取值對(duì)彈性運(yùn)動(dòng)估計(jì)效率的影響

為此,文獻(xiàn)[71,72]分別將每次迭代后的目標(biāo)函數(shù)值及其0.01倍作為阻尼系數(shù)δ.但當(dāng)初始迭代點(diǎn)距離全局最優(yōu)點(diǎn)較遠(yuǎn)時(shí),文獻(xiàn)[71,72]的方法將由于目標(biāo)函數(shù)值過(guò)大導(dǎo)致迭代步長(zhǎng)很小而無(wú)法快速收斂;反之,該方法又會(huì)產(chǎn)生過(guò)小的δ,使得對(duì)角矩陣喪失梯度下降作用.盡管文獻(xiàn)[73]進(jìn)一步采用目標(biāo)函數(shù)值的s-范數(shù)(s∈[1,2])來(lái)更新δ,能夠在一定程度上克服上述不足,但是如何根據(jù)迭代點(diǎn)與全局最優(yōu)點(diǎn)的距離選擇合適的s也并不容易,并且不能有效避免目標(biāo)函數(shù)值在迭代后期出現(xiàn)反復(fù)振蕩.于是,文獻(xiàn)[74]提出一種基于對(duì)數(shù)線性函數(shù)的對(duì)角矩陣系數(shù)更新方法,增強(qiáng)了傳統(tǒng)L-M算法的收斂穩(wěn)定性,而其初始迭代速度卻較慢.針對(duì)這一不足,文獻(xiàn)[75]提出通過(guò)迭代向量m之間的內(nèi)積來(lái)計(jì)算更新因子λ,加快了初始迭代效率,同時(shí)引進(jìn)對(duì)角優(yōu)勢(shì)矩陣(diagonally dominant matrix),減少了為使矩陣 HLM正定而反復(fù)更新δ所需的嘗試次數(shù);文獻(xiàn)[76]根據(jù)目標(biāo)函數(shù)值的實(shí)際下降量與預(yù)測(cè)下降量之比確定更新因子λ;文獻(xiàn)[77]則利用測(cè)地線距離來(lái)修正迭代步長(zhǎng).然而,這 3種方法需要的計(jì)算量均較大,分別需多次判斷HLM的正定性、根據(jù)泰勒展開(kāi)式計(jì)算匹配誤差的預(yù)測(cè)下降量、計(jì)算目標(biāo)函數(shù)的測(cè)地線距離,不能滿足彈性運(yùn)動(dòng)對(duì)低運(yùn)算量的要求.故此,下文提出一種用來(lái)自適應(yīng)更新δ的快速策略.

5.2 基于步長(zhǎng)平方商的對(duì)角矩陣阻尼系數(shù)交替更新

但是,公式(15)給出的自適應(yīng)因子依然是正數(shù),其目的是通過(guò)保證 HLM正定性使迭代求解沿著運(yùn)動(dòng)補(bǔ)償誤差曲面的下降方向進(jìn)行.盡管這是一種穩(wěn)妥的做法,但文獻(xiàn)[77]的研究結(jié)論卻表明,當(dāng)?shù)c(diǎn)陷入由多個(gè)運(yùn)動(dòng)補(bǔ)償誤差曲面峰所圍的狹長(zhǎng)谷底時(shí),保持自適應(yīng)因子為正數(shù)會(huì)形成一條鋸齒狀搜索路徑,若適當(dāng)允許朝著函數(shù)值增長(zhǎng)的方向迭代則可更快地收斂到更小點(diǎn).基于這一思路,本文在搜索中借助梯度方向提出一種δ的正、負(fù)交替更新策略.直觀起見(jiàn),圖 5給出了這一過(guò)程的示意圖,其中,灰度越淺的區(qū)域表示補(bǔ)償誤差越大.可見(jiàn),當(dāng)前迭代點(diǎn)處于兩峰之間的谷底,其負(fù)梯度指向遠(yuǎn)離全局極小點(diǎn)的方向,且由于距離全局最優(yōu)解較遠(yuǎn),沿高斯-牛頓方向搜索會(huì)出現(xiàn)收斂速度慢甚至無(wú)法收斂的情況,而此時(shí)利用梯度方向與高斯-牛頓方向的矢量和控制迭代卻有望將搜索引導(dǎo)向全局最優(yōu)點(diǎn).具體地,δ的正、負(fù)交替更新方法是

其中,Dt和Dt-1分別表示第t次迭代和第(t-1)次迭代的匹配誤差平方和,從而以高斯-牛頓方向HGN為中心,沿著當(dāng)前搜索方向的對(duì)稱方向進(jìn)行搜索(如圖 3所示的H*LM和H′*LM),使搜索方向可達(dá)整個(gè)運(yùn)動(dòng)向量空間,提高了算法收斂到全局最優(yōu)解的概率.

6 采用改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)步驟

在第3節(jié)算法的基礎(chǔ)上,結(jié)合第4節(jié)和第5節(jié)的改進(jìn)思路,下面給出基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)步驟.對(duì)于每個(gè)待預(yù)測(cè)塊I,其運(yùn)動(dòng)估計(jì)/補(bǔ)償?shù)脑敿?xì)步驟如下.

Step 2. 利用整數(shù)像素精度的菱形搜索估計(jì)平移分量m1和mp/2+1,將其余分量置0,并計(jì)算I的初始運(yùn)動(dòng)補(bǔ)償誤差eij(m)及其平方和D0.

Step 3. 根據(jù)第4.1節(jié)計(jì)算彈性運(yùn)動(dòng)基函數(shù)φ1～φp.

Step 4. 計(jì)算匹配塊的梯度?R以及雅克比矩陣?w?m.

Step 5. 根據(jù)第4.2節(jié)計(jì)算高斯-牛頓黑塞矩陣H.

Step 6. 將H及其主對(duì)角線元素、eij(m)、δ代入公式(8)、公式(11),計(jì)算向量b和L-M黑塞矩陣HLM.

Step 8. 將運(yùn)動(dòng)向量m代入公式(2)和公式(3),建立I的每個(gè)像素與其匹配像素的坐標(biāo)映射,并利用雙線性插值計(jì)算匹配像素的值,從而得到運(yùn)動(dòng)補(bǔ)償誤差eij(m)及其平方和Dt.

7 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的有效性,以CIF(common intermediate format)、4CIF和高清格式的37個(gè)標(biāo)準(zhǔn)視頻序列(見(jiàn)表1)的1～90幀為例進(jìn)行大量實(shí)驗(yàn),并將基于塊平移模型的全搜索(full search,簡(jiǎn)稱FS)、基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)[62]、基于菱形搜索(diamond search,簡(jiǎn)稱DS)+傳統(tǒng)L-M法的彈性運(yùn)動(dòng)估計(jì)、基于菱形搜索+對(duì)角優(yōu)勢(shì)矩陣的L-M法的彈性運(yùn)動(dòng)估計(jì)[75]和基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)的預(yù)測(cè)結(jié)果進(jìn)行比較.

Table 1 Test video sequences’ names and their formats表1 測(cè)試視頻序列名稱及其格式

實(shí)驗(yàn)參數(shù)設(shè)置如下:搜索窗口為33×33像素,塊尺寸為16×16像素,λmin=2,λmax=10,Tm=0.0001,T=15(這與文獻(xiàn)[60,62]的設(shè)置相同);文獻(xiàn)[75]的參數(shù)與原文相同.運(yùn)動(dòng)補(bǔ)償幀的質(zhì)量采用PSNR進(jìn)行評(píng)價(jià).

7.1 運(yùn)動(dòng)估計(jì)/補(bǔ)償質(zhì)量的比較

表2給出了各個(gè)測(cè)試序列的亮度分量采用不同運(yùn)動(dòng)估計(jì)算法所得到的平均PSNR.

Table 2 Motion-compensated PSNR comparison表2 運(yùn)動(dòng)補(bǔ)償?shù)腜SNR比較

由表2可知:

● 盡管 FS是目前編碼標(biāo)準(zhǔn)中預(yù)測(cè)精度最高的運(yùn)動(dòng)估計(jì)/補(bǔ)償算法,但是由于運(yùn)動(dòng)模型本身的局限,其平均PSNR比本文算法低2.54dB.

● 基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)利用初始迭代點(diǎn)預(yù)測(cè)和一維線搜索取得了優(yōu)于 FS的性能(比后者高出0.77dB),但其PSNR卻比本文提出的基于菱形搜索+傳統(tǒng)L-M法的彈性運(yùn)動(dòng)估計(jì)低0.79dB,這表明,L-M法比高斯-牛頓法更適用于彈性運(yùn)動(dòng)模型的求解.

● 基于菱形搜索+對(duì)角優(yōu)勢(shì)矩陣的 L-M 法的彈性運(yùn)動(dòng)估計(jì)利用迭代向量?jī)?nèi)積更新對(duì)角矩陣阻尼系數(shù),其PSNR比基于菱形搜索+傳統(tǒng)L-M法的彈性運(yùn)動(dòng)估計(jì)提高了0.04dB,表明自適應(yīng)選取阻尼系數(shù)有利于獲得更高的運(yùn)動(dòng)補(bǔ)償質(zhì)量.然而,由于文獻(xiàn)[75]修改 L-M 黑塞矩陣的方式無(wú)法保證其是嚴(yán)格對(duì)角占優(yōu)的,且被修改的對(duì)角元素難免不會(huì)使迭代過(guò)程偏離真實(shí)的梯度下降方向,其PSNR較之基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)低0.95dB,這說(shuō)明本文的系數(shù)自適應(yīng)交替更新策略可更有效地提高彈性運(yùn)動(dòng)估計(jì)預(yù)測(cè)精度.

● 表2第7列和第8列進(jìn)一步對(duì)比了基于步長(zhǎng)平方商和基于交替策略(λ=10)的對(duì)角矩陣阻尼系數(shù)更新方法的性能增益,兩者的平均PSNR比基于菱形搜索+傳統(tǒng)L-M法的彈性運(yùn)動(dòng)估計(jì)分別提高了0.15dB和0.87dB.可見(jiàn),正、負(fù)交替更新策略為本文算法貢獻(xiàn)了大部分的性能提升.

另外,對(duì)于高清視頻的運(yùn)動(dòng)估計(jì),H.264和HEVC通過(guò)縮小塊尺寸的方式提高了預(yù)測(cè)準(zhǔn)確率;而且,在相同的塊尺寸條件下,塊平移模型的運(yùn)動(dòng)向量數(shù)量?jī)H為彈性模型的 1/4.為此,本文統(tǒng)計(jì)了當(dāng)塊尺寸為 8×8像素時(shí),塊匹配FS對(duì)10個(gè)高清視頻序列的運(yùn)動(dòng)補(bǔ)償PSNR(結(jié)果見(jiàn)表2第3列),雖然它在這10個(gè)序列上的平均PSNR比16×16像素的塊匹配 FS提高了 1.15dB,但是仍較基于改進(jìn) L-M法的彈性運(yùn)動(dòng)估計(jì)(16×16塊)低 1.16dB.可見(jiàn),即使采用了更精細(xì)的塊結(jié)構(gòu),在同等的運(yùn)動(dòng)向量開(kāi)銷下,基于塊平移模型的全搜索性能仍與本文算法存在一定差距.

需要指出,本文算法在高清VenueVu序列上的PSNR與8×8像素的塊匹配FS、基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)存在一定差距.其原因在于:該視頻是由計(jì)算機(jī)生成的動(dòng)畫(huà)序列,紋理細(xì)膩且存在快速的全局形變,而本文算法在初始搜索時(shí)選用的菱形運(yùn)動(dòng)估計(jì)精度低于后兩種算法的全搜索.如果采用與基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)相同的初始搜索,本文算法對(duì)VenueVu序列的運(yùn)動(dòng)補(bǔ)償PSNR將達(dá)到29.51dB.這表明,本文的對(duì)角矩陣自適應(yīng)更新方法在個(gè)別情況下也不能完全克服傳統(tǒng)L-M算法對(duì)于初始迭代點(diǎn)的敏感性.

圖6(a)～圖6(d)進(jìn)一步給出了Akiyo、Foreman、Mobile和Husky序列的PSNR逐幀比較情況.

如圖 6所示,這 4個(gè)序列的紋理細(xì)節(jié)和運(yùn)動(dòng)復(fù)雜度依次增高,且包含攝像機(jī)的拉攝、搖攝運(yùn)動(dòng)和物體的局部形變.從圖中可見(jiàn),對(duì)于具有不同紋理、運(yùn)動(dòng)特點(diǎn)的視頻序列,基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)均取得了最高的運(yùn)動(dòng)補(bǔ)償質(zhì)量.并且,對(duì)于快速搖攝、紋理細(xì)節(jié)復(fù)雜的序列(如Mobile、Husky),本文提出的兩種算法均明顯優(yōu)于塊匹配 FS和基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì);而對(duì)于慢速運(yùn)動(dòng)或存在局部形變的序列(如 Akiyo、Foreman),基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)較之塊匹配FS亦有穩(wěn)定提高.

7.2 收斂性和收斂速度比較

收斂性和收斂速度是衡量彈性運(yùn)動(dòng)估計(jì)效率的重要指標(biāo)之一.圖7所示分別為Husky和Akiyo序列采用基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)、基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)的前14次迭代結(jié)果.可見(jiàn),首先,前者在紋理和運(yùn)動(dòng)較為復(fù)雜的序列(如 Husky)上收斂效率較高,反之,卻不夠理想(如 Akiyo).其次,本文算法最多經(jīng)過(guò) 4次迭代就可達(dá)到與最優(yōu)解相差不到2%的PSNR,而經(jīng)過(guò)1～2次迭代即可取得明顯高出塊匹配FS的補(bǔ)償質(zhì)量.這表明,本文算法的阻尼步長(zhǎng)和更新因子符合匹配誤差函數(shù)的分布特點(diǎn),能夠高效地逼近其最優(yōu)解.

圖8給出了Husky序列第2幀以(48,304)像素為左上角的宏塊和Foreman序列第2幀以(0,336)像素為左上角的宏塊在第2～15次迭代的誤差曲線(第1次迭代的誤差較大,為了清晰地展現(xiàn)曲線變化的細(xì)節(jié),這里未予繪制),以及在此過(guò)程中本文算法的δ值與λ值的變化情況.不難發(fā)現(xiàn),盡管傳統(tǒng) L-M 算法和基于對(duì)角優(yōu)勢(shì)矩陣的L-M 算法[75]的運(yùn)動(dòng)補(bǔ)償誤差均出現(xiàn)了振蕩,但是本文算法卻能保持穩(wěn)定的下降趨勢(shì).并且,隨著算法的收斂,δ與λ也逐漸趨于定值,從而保證了本文的改進(jìn) L-M 算法在靠近全局最優(yōu)解時(shí)表現(xiàn)出高斯-牛頓法的快速收斂特性.

7.3 計(jì)算復(fù)雜度分析

下面對(duì)比分析基于塊平移模型的全搜索、基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)和基于改進(jìn) L-M 法的彈性運(yùn)動(dòng)估計(jì)處理1個(gè)宏塊的計(jì)算量.設(shè)塊尺寸為B×B像素,搜索窗口為W×W像素,彈性基函數(shù)為p個(gè).

首先,基于塊平移模型的全搜索的計(jì)算復(fù)雜度為O(B2W2).

其次,根據(jù)文獻(xiàn)[62],基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)的計(jì)算復(fù)雜度為O(Tp2B2+73B2).

最后,基于改進(jìn) L-M 法的彈性運(yùn)動(dòng)估計(jì)需進(jìn)行 1次菱形搜索,其復(fù)雜度約為塊匹配 FS的 6%[6],即O(0.06B2W2);每次迭代需計(jì)算對(duì)角矩陣阻尼系數(shù)、黑塞矩陣、逆矩陣、矩陣乘法、雙線性插值和運(yùn)動(dòng)補(bǔ)償誤差,結(jié)合第4節(jié)的快速實(shí)現(xiàn),其計(jì)算復(fù)雜度分別為O(1)、O(0.375p2B2)、O(p3)、O(pB2)、O(8B2)和O(B2),T次迭代的漸近時(shí)間復(fù)雜度為O(0.375Tp2B2).

具體地,當(dāng)B=16,W=33,T=15,p=8時(shí),本文算法的總計(jì)算量約為基于塊平移模型的全搜索的65%,為基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)的51%.此外,由第7.2節(jié)可知,本文算法一般僅需1～2次迭代就能取得高于兩者的PSNR,從這個(gè)意義上講,基于改進(jìn)L-M法的彈性運(yùn)動(dòng)估計(jì)的計(jì)算量約是塊匹配FS的9.9%～13.9%,是基于改進(jìn)高斯-牛頓法的彈性運(yùn)動(dòng)估計(jì)的7.8%～10.8%.

8 結(jié) 論

彈性運(yùn)動(dòng)模型是一種表示非剛性復(fù)合運(yùn)動(dòng)的有效方法,現(xiàn)有工作均采用高斯-牛頓法進(jìn)行求解,但仍存在迭代計(jì)算量高、收斂不穩(wěn)定的不足.為避免高斯-牛頓黑塞矩陣出現(xiàn)奇異或病態(tài),本文引進(jìn)L-M優(yōu)化算法求解彈性運(yùn)動(dòng)模型,并進(jìn)行了兩方面的改進(jìn):第一,根據(jù)黑塞矩陣的數(shù)值分布,給出一種快速計(jì)算黑塞矩陣的方法,降低了多次迭代所需的計(jì)算量;第二,通過(guò)理論和實(shí)驗(yàn)探討了L-M對(duì)角矩陣阻尼系數(shù)的更新因子對(duì)彈性運(yùn)動(dòng)估計(jì)的影響,設(shè)計(jì)了一種自適應(yīng)交替更新策略.在此基礎(chǔ)上,提出一種基于改進(jìn) L-M 法的視頻彈性運(yùn)動(dòng)估計(jì)算法.實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性.同時(shí),本文算法對(duì)于視頻處理中相關(guān)的無(wú)約束最優(yōu)化問(wèn)題求解具有一定的參考價(jià)值.

另外,本文方法仍存在若干問(wèn)題可臻完善,如減少逆矩陣的反復(fù)計(jì)算、快速預(yù)測(cè)初始迭代點(diǎn)等,我們將在今后的工作中進(jìn)一步深入研究這些問(wèn)題的解決思路.