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

1(遼寧師范大學 計算機與信息技術學院,遼寧 大連 116029)

2(大連理工大學 計算機科學與技術學院,遼寧 大連 116024)

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

因此,綜合各個模型之間的對比和現(xiàn)有研究結論可知,彈性運動模型是一種表示復雜運動場的高效率模型.

目前,關于視頻彈性運動估計的研究主要集中在以下兩個方面.

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

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

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

2 彈性運動模型以及傳統(tǒng)彈性運動估計算法

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

2.1 彈性運動估計模型簡介

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

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

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

2.2 彈性運動估計的高斯-牛頓求解方法

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

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

其中,上標T表示向量轉置.令

顯然,H是一個p×p階的黑塞矩陣,并且根據(jù)求導的鏈式法則和eij(m)、公式(2)、公式(3)的定義,有:

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

3 基于Levenberg-Marquardt法的彈性運動估計

對于彈性運動估計這類非線性無約束最小二乘問題,主要有兩類典型的優(yōu)化解法:牛頓型方法(如牛頓法和高斯-牛頓法)和負梯度方法(如最速下降法和對角線近似法)[67].理論表明,當初始迭代點距離局部極小點較近時,牛頓法和高斯-牛頓法的收斂速度更快;反之,牛頓法和高斯-牛頓法則收斂較慢,甚至會由于黑塞矩陣奇異或病態(tài)導致無法收斂的情形發(fā)生[68],而此時最速下降法和對角線近似法的收斂效率更高.故而,彈性運動估計的高斯-牛頓解法對初始搜索點存在一定的敏感性,文獻[62,63]的研究也驗證了這一結論.在這種情況下,文獻[69,70]將對角線近似法與高斯-牛頓法相結合,修正了高斯-牛頓黑塞矩陣,提出了一種 Levenberg-Marquardt(下文簡稱L-M)黑塞矩陣:

從其定義可見,當δ<<1時,HLM近似為高斯-牛頓黑塞矩陣H;而當δ>>1時,HLM則近似為對角矩陣(僅差1個步長因子1/δ).

在HLM的基礎上,本文提出了基于L-M算法的彈性運動估計,其計算步驟如下所示.

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

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

Step 3. 計算初始運動補償誤差eij(m)及其平方和D0.

Step 4. 計算匹配塊的梯度?R.

Step 5. 計算雅克比矩陣?w?m.

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

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

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

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

4 黑塞矩陣的快速計算方法

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

4.1 彈性運動基函數(shù)的快速計算

根據(jù)公式(4),彈性運動模型共有4種基函數(shù).以B=8為例,圖1給出了4種基函數(shù)對應的8×8矩陣的數(shù)值分布.其中,符號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可見:① 第1個基函數(shù)矩陣只包含元素1;② 第2個基函數(shù)矩陣的元素只與縱坐標有關;③ 第3個基函數(shù)矩陣的元素只與橫坐標有關;④ 第4個基函數(shù)矩陣的元素為第2個和第3個基函數(shù)矩陣的對應元素之積.故此,基函數(shù)矩陣可通過少量計算和大量賦值得到,即:首先,φ1對應的矩陣只需全部賦值為 1;其次,φ2對應的矩陣只需計算一行,其余各行通過賦值得到,轉置后再賦值給φ3的各列;最后,將φ2和φ3矩陣的上三角元素對應相乘得到φ4矩陣的上三角元素,而下三角元素可通過轉置賦值獲得.這樣,需要計算的元素個數(shù)僅占全部基函數(shù)矩陣元素數(shù)量的17%.

4.2 高斯-牛頓黑塞矩陣的快速計算

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

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

同理可得,

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

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

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

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

5.1 λ的取值對彈性運動估計效率的影響

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

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

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

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

6 采用改進L-M法的彈性運動估計步驟

在第3節(jié)算法的基礎上,結合第4節(jié)和第5節(jié)的改進思路,下面給出基于改進L-M法的彈性運動估計步驟.對于每個待預測塊I,其運動估計/補償?shù)脑敿毑襟E如下.

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

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

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

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

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

Step 8. 將運動向量m代入公式(2)和公式(3),建立I的每個像素與其匹配像素的坐標映射,并利用雙線性插值計算匹配像素的值,從而得到運動補償誤差eij(m)及其平方和Dt.

7 實驗結果與分析

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

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

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

7.1 運動估計/補償質量的比較

表2給出了各個測試序列的亮度分量采用不同運動估計算法所得到的平均PSNR.

Table 2 Motion-compensated PSNR comparison表2 運動補償?shù)腜SNR比較

由表2可知:

● 盡管 FS是目前編碼標準中預測精度最高的運動估計/補償算法,但是由于運動模型本身的局限,其平均PSNR比本文算法低2.54dB.

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

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

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

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

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

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

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

7.2 收斂性和收斂速度比較

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

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

7.3 計算復雜度分析

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

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

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

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

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

8 結 論

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

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