采用2 b深度像素的彈性運動估計算法

宋傳鳴 閔 新 謝維冬 尹寶才 王相海

1(遼寧師范大學計算機與信息技術學院 遼寧大連 116029) 2(大連理工大學計算機科學與技術學院 遼寧大連 116024) 3(東北大學計算機科學與工程學院 沈陽 110169) 4(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023)

運動估計是一項去除視頻冗余的時間域預測技術，為H.264和高效率視頻編碼(high efficiency video coding, HEVC)等編碼標準貢獻了大部分的性能提升[1-2].提高運動估計的效率，使其搜索過程更加健壯和高效不僅是視頻編碼領域的熱點問題，也是進一步改善視頻編碼效率的重要途徑之一.

多年來，視頻編碼標準始終采用了僅能刻畫水平、豎直等平移運動的塊匹配算法，可是塊平移模型既無法有效預測由物體旋轉、縮放、變形和攝像機運動產生的非剛性復合運動，又不能準確表示具有復雜形狀的運動區域，導致在運動物體邊緣產生大幅值的預測殘差.并且，隨著塊尺寸的減小和運動向量精度的提高，用于編碼運動向量、塊劃分方式的碼流開銷以及各種軟硬件資源開銷的增加幅度甚至超過了率失真性能的提升幅度[2].故此，研究能有效表示復雜運動場的運動模型及相應的幀間運動估計方法，對下一代視頻編碼效率的提升具有重要意義[3-6].

鑒于平移運動模型的不足，研究人員將高階運動模型引入運動估計，利用高階函數產生1個或多個扭曲的參考幀實現了更高質量的運動補償.依據模型顯式表現形式的不同，本文將這些運動估計補償算法劃分為4類：1)基于網格模型的運動估計[7-9]；2)基于多項式模型的運動估計[10-12]；3)基于縮放模型的運動估計[13-15]；4)基于彈性模型的運動估計[16-20].其中，算法1對編碼率失真的優化較為困難[21]；算法2的參數偏多，搜索復雜度高，且對局部運動的刻畫能力不足；算法3無法有效描述物體的旋轉、錯切和局部變形運動；算法4可刻畫物體的平移、錯切和扭曲運動，既能表示全局和局部運動，又可通過調整模型參數個數來控制運動估計的計算復雜度.因此，對比各類高階運動模型并綜合現有研究結論，彈性運動模型是一種表示復雜運動場的高效模型.

本文首先簡要介紹彈性運動估計的相關工作，然后針對其存在的計算量高的問題，引進一種視頻幀的2 b深度像素表示方法，進而提出低位深度的彈性運動模型，并從模型的快速計算和自適應步長選取策略2個方面展開論述，提出一種采用2 b深度像素加速的彈性運動估計算法.本文的主要貢獻有3個方面：

1) 利用Prewitt梯度算子和梯度模長的均值、標準差提取視頻幀的紋理信息，設計了一種將像素從8 b深度向2 b深度進行變換的方法，可避免視頻幀在像素深度降采樣后出現大面積的光滑區域；

2) 引進基于位操作的矩陣乘法和基于比較操作的偏導運算，提出了一種基于2 b深度像素的彈性運動估計模型，并根據8 b乘法運算的符號表，進一步給出求解該模型的簡化高斯-牛頓法，其優點在于用異或操作替代乘法運算，且無需反復計算黑塞矩陣及其逆矩陣，計算復雜度明顯降低；

3) 根據運動補償誤差的分布特性，利用1階線性逼近策略，推導出高斯-牛頓法的自適應步長與彈性運動向量增量、運動補償誤差之間的函數關系，進而得出其近似計算方法，保證了算法具有較穩定的收斂性.

1 相關工作

彈性運動模型采用離散余弦函數、小波函數和樣條函數等調和函數來描述物體的非剛性運動，最初主要應用于醫學影像配準、物體跟蹤等領域.文獻[16-17]將彈性模型引進視頻編碼中，提出了基于彈性模型的運動估計，在相同碼率下獲得了比塊平移運動估計高出0.70 dB的運動補償峰值信噪比(peak signal-to-noise ratio, PSNR)；文獻[18]的結論顯示，彈性運動模型可將H.265的輸出碼率降低3%～12%；文獻[19-20,22]則通過優化彈性模型的求解方法取得了更加理想的預測效率，將傳統彈性運動估計的平均PSNR又提高了1.42～1.77 dB，比基于塊平移模型的全搜索算法高出1.73～2.54 dB.然而，上述文獻均采用高斯-牛頓法來迭代地求解彈性運動模型，在每次迭代過程中需計算偏導數、黑塞矩陣、逆矩陣和矩陣乘法，其計算復雜度甚至高于塊平移模型的全搜索(full search, FS).盡管經過文獻[19-20,22]改進后的彈性運動估計僅需2～3次迭代即可達到塊匹配全搜索的補償質量，可是仍然無法避免黑塞矩陣及其逆矩陣等的反復求解，計算量約為FS的25.62%，高于菱形搜索(diamond search, DS)和測試域搜索(test zone search, TZSearch)等快速塊匹配運動估計.

為了增強高階運動模型求解的實時性，文獻[23]提出一種1 b深度像素的高斯-牛頓迭代法，并將其應用到基于6-參數仿射變換的圖像配準中.然而，由于1 b匹配誤差曲面的梯度較小，該算法至少需迭代50次才能緩慢趨于收斂，計算復雜度并未顯著降低.文獻[24-25]進一步將文獻[23]的思路推廣到2 b深度像素，實現了一種基于仿射模型的2 b全局運動估計.可是，為節省逆矩陣的計算量，該方法要求保持迭代步長固定不變，無法實現自適應，且只能朝著單一方向進行迭代.而文獻[19-20,22]的研究結論卻表明，高斯-牛頓法對初始迭代步長和迭代方向均較為敏感，這就不可避免地導致文獻[24-25]在大多數情況下都無法求解出全局最優解.同時，文獻[23-25]均利用8 b深度表示的圖像計算1階偏導，再結合經過位截斷后的低位深度圖像得到匹配誤差和最速下降方向.由于低位深像素的梯度往往不同于8 b深度像素，兩者混合作用很難保證下降方向的準確性；另一方面，文獻[26-27]指出，匹配誤差往往產生在較低的位，直接截斷低位無法有效保留圖像的邊緣特征，還將使位于最佳匹配塊周圍的一定區域內的所有像素被量化成相同值，以致失去對最優向量的判斷能力.綜合來看，無論是運動估計的精度，抑或收斂速度，文獻[23-25]的方法尚不夠令人滿意，且只能求解仿射模型下的運動向量.因此，研究更加有效的、基于低位深度像素的高斯-牛頓法和彈性運動估計，有助于以彈性模型為代表的高階運動估計走向實用，對新一代視頻編碼的發展具有一定意義.從本文作者所掌握的文獻來看，目前尚鮮見相關研究.

本文提出的2 b深度像素的彈性運動估計，利用梯度均值和標準差提取圖像的邊緣和紋理特征，將像素從8 b深度向2 b深度進行轉換，并實現了基于位操作的快速高斯-牛頓優化求解.不僅解決了初始迭代步長的自適應選取和迭代方向的多樣性，也使得1階偏導與最速下降方向均在2 b深度像素域進行統一計算，從而保證基于低位深像素的彈性運動估計精度和收斂速度.

2 彈性運動模型及其高斯-牛頓求解方法

為便于下文工作的論述，本節首先介紹彈性運動模型的定義，再給出求解彈性運動向量的高斯-牛頓方法.

2.1 彈性運動模型的基本定義

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

(1)

其中，xij和yij分別表示當前待預測塊中i行j列像素的x坐標和y坐標，m表示某種運動模型w下的運動向量.對于彈性運動模型，采用彈性基函數φk建立待預測塊中每個像素的坐標及其匹配像素的坐標映射，其定義為

(2)

(3)

其中，p表示運動矢量的分量數目，mk表示m的第k個分量，且φk為離散余弦函數：

φk(i,j)=φk+p2(i,j)=

(4)

2.2 彈性運動模型的高斯-牛頓解法

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

(5)

(6)

為取得式(6)的最小值，將其對Δm取導并令導數為0，整理后得到：

(7)

(8)

(9)

顯然，H是1個p×p階的黑塞矩陣，并且根據求導的鏈式法則和eij(m)、式(2)、式(3)的定義，有：

(10)

Fig. 1 Flowchart of elastic motion estimation usingthe Gauss-Newton Method圖1 基于高斯-牛頓法的彈性運動估計流程圖

3 基于Prewitt梯度算子的2 b變換

由2.2節可見，彈性運動模型的高斯-牛頓解法需反復計算偏導數、黑塞矩陣、逆矩陣和矩陣乘法，計算量明顯高于塊平移模型的全搜索.為此，我們引進基于低位深度像素的策略，將像素從8 b深度降采樣為2 b深度，以達到降低計算開銷的目的.

3.1 本文的2 b變換算法

將像素從8 b深度轉換至2 b深度，勢必會丟失視頻幀的部分信息，尤其是細膩的紋理細節，產生大面積的平滑區域，這是導致基于低位截斷的低位深度像素運動估計出現性能下降的重要原因[26-27].故此，在像素深度變換過程中盡可能保持視頻的紋理特征，對于衡量像素深度降采樣的有效性、保證運動估計精度具有重要意義.為了達到這一目的，我們首先通過Prewitt算子計算待預測幀的梯度；其次，假定像素梯度的模長服從正態分布，若用均值μC和標準差σC將概率密度劃分為4個區間，則知梯度模長位于區間(-∞,μC-0.68σC)，[μC-0.68σC,μC)，[μC,μC+0.68σC)，[μC+0.68σC,+∞)的概率均近似等于0.25，根據這一規律，本文以像素塊為單位，將每個像素處的邊緣和紋理強度平均分為弱、較弱、較強、強4個等級，從而實現將像素(x,y)的深度從8 b變換為2 b：

(11)

本文提出的基于梯度均值和標準差的2 b變換過程如圖2所示：

Fig. 2 Flowchart of the proposed 2 b transform圖2 本文提出的2 b變換流程圖

圖3給出了分別采用低位截斷方法[28]、基于亮度均值和方差的2 b變換方法[29]，以及本文方法處理Football序列和Foreman序列第2幀的結果.從圖3不難發現，基于低位截斷的變換方法損失了Football序列包含的復雜背景紋理(圖3(b))；雖然基于亮度均值和方差的2 b變換方法[29]在一定程度上避免了位截斷方法的不足，可是未充分考慮正態分布的特點，選用亮度均值μ、標準差σ及其線性組合μ-σ和μ+σ作為變換閾值，這將導致約有68%的像素會從8 b深度被降采樣為00和01，產生較大面積的平滑區，如Football的運動員身體和Foreman的臉部區域中大量像素被轉換為相同值，易使運動估計陷入局部最優，甚至失去對最優向量的判斷能力；而本文方法無論在復雜的背景紋理區，還是在平滑的漸變區(如Foreman的臉部)，均能保持適當的圖像細節，進而形成能有效區分錯誤運動向量的特征.

Fig. 3 Comparison among different 2 b transform results圖3 不同的2 b變換方法的效果對比

3.2 2 b深度像素的匹配誤差曲面的特點

由于位深度變換過程難免丟失少量紋理細節，會出現2種情況：1)當一定區域內的像素均被變換為相同值時，像素值的變化率降低、自相關系數增大.這樣，當待預測塊在該區域內搜尋最佳匹配塊時，匹配誤差的變化趨于平緩.我們稱這樣的區域為“曲面平滑區域”.2)在2個曲面平滑區的交界線兩側，像素值被變換為不同值，像素值的變化率提高，而自相關系數減小.對2 b深度的像素而言，由于匹配誤差的值域顯著小于8 b深度像素，即使匹配誤差增加1，也意味著25%的增幅，這相當于8 b誤差增幅的32倍.因此，在交界區域中不同候選向量的運動補償誤差易產生較大變化.2 b匹配誤差曲面的這種“區域內平滑、區域間銳化”的分布特點，會使其呈現更加明顯的單調性和梯度變化.

圖4給出了Stefan序列第2幀內左上角坐標為(144,112)的塊和Football序列第2幀內左上角坐標為(176,176)的塊，分別進行基于8 b深度像素和基于本文2 b深度像素的整數精度全搜索后得到的匹配誤差曲面，搜索窗口為33×33.對比可見：首先，8 b深度像素的匹配誤差曲面(圖4(a)(c))較之2 b深度像素的匹配誤差曲面(圖4(b)(d))具有更強的波動性，局部極值點也更多，易導致典型的快速搜索陷入局部最優.其次，在曲面平滑區域，8 b深度像素的匹配誤差的變化幅度和頻率均大于2 b深度像素的匹配誤差；而在極值點的一定鄰域以及2個局部極值區域的交界，8 b深度像素匹配誤差的變化趨勢卻較平滑，其數值梯度和衰減速度明顯小于2 b深度像素的匹配誤差曲面.這不僅印證了上一段的理論分析，也充分說明2 b深度像素的運動估計陷入局部最優的概率更小，且能通過梯度下降策略以更快的速度向全局最優點收斂，尤其是當搜索初始點較為準確、位于全局極值點的單調區間時，從而有利于提高運動補償精度和運動估計效率.

Fig. 4 Comparison between matching error surfaces of 8 b pixel and 2 b pixel under full search圖4 8 b全搜索與2 b全搜索的匹配誤差曲面比較

4 低位深度的彈性運動模型

傳統高斯-牛頓法的每次迭代都需要計算待預測塊的偏導數、黑塞矩陣、逆矩陣、矩陣乘法和運動補償誤差等，其計算復雜度達到了max{O(p3),O(p2B2)}.若能降低反復執行上述操作的運算量，則可進一步改善彈性運動估計補償的效率.同時，經過第3節的處理，視頻幀的全部像素已由8 b深度降采樣到2 b深度，若繼續延用傳統高斯-牛頓法中基于8 b整數的偏導、矩陣乘法等運算，則達不到通過精度下采樣來提高計算效率的目的.故此，本文對匹配誤差eij(m)及其1階偏導數也進行了位深度變換，利用異或運算取代乘法運算，提出了面向低位深度像素的彈性運動模型，從而加快彈性運動估計的速度.

(12)

(13)

Table 1 Sign of 8 b Multiplication Operation表1 8 b乘法運算的符號表

Table 2 Truth Table of 1 Bit-Wise XOR Operation表2 1 b異或運算的真值表

為了解決這個問題，本文通過將匹配誤差進行2次互為相反數的2值化轉換，提出了基于2 b深度的彈性運動模型，即：

(14)

(15)

(16)

(17)

Table 3 Truth Table of Improved XOR Operation表3 改進的異或運算真值表

5 迭代步長的自適應計算

Δm=-s×sgn(b),

(18)

其中，sgn(·)表示符號函數.但是，這種做法無異于放棄了黑塞矩陣對高斯-牛頓迭代過程的控制.而文獻[19-20,22]的研究結論卻表明，高斯-牛頓法對初始迭代步長較為敏感，文獻[25]的這種固定初始步長的方式顯然不利于迭代過程收斂到全局最優解.為了驗證這一推論，我們選取Akiyo，Tempete，Football這3個運動特性和紋理復雜度各異的視頻序列的前10幀，應用固定步長的2 b深度彈性模型進行了運動估計補償實驗.圖5給出了在不同的初始步長s下，3個序列經過15次迭代后所獲得的平均運動補償PSNR曲線.從圖5可見，Akiyo序列的運動幅度很小、畫面紋理細節簡單，隨著初始步長的縮小，該序列的運動補償PSNR明顯升高(圖5(a))，但是即使初始步長縮小至1×10-6，仍未取得最高的PSNR；Tempete序列的運動幅度中等，可是紋理細節復雜，且包含攝像機的拉攝運動，其運動補償的平均PSNR在初始步長為4×10-6時取得極值，然后隨著初始步長的增大迅速下降(圖5(b))；Football序列既包含快速的前景運動和中等復雜度的紋理，又存在物體的局部形變，它在初始步長等于3×10-5時取得了運動補償PSNR的極值(圖5(c))，而此時，Akiyo的平均PSNR已比其最高值下降了4.74 dB.

Fig. 5 The motion-compensated PSNR comparison among with different initial step size s圖5 不同初始步長s下的運動補償PSNR對比

對比這3個視頻序列的實驗結果可知，不同序列的最優初始步長相差幾十倍.對于運動幅度較小、畫面細節較多的視頻，應為其選取一個較小的迭代步長；反之，對于運動速度較快、局部形變較多的視頻，為其設定一個較大的迭代步長則更加合適.可見，文獻[25]固定初始步長的方式不僅無法保證運動補償的質量，而且在現實中亦很難做到折中選擇.為此，本節采用一種自適應步長s來近似H-1，下面討論其計算方法.

由式(6)可知，高斯-牛頓法的基本思路是在每次迭代中利用2次函數來逼近匹配誤差D(m)，并求解近似函數的極小點作為下一個迭代點，則第k+1次迭代的彈性運動向量mk+1有：

mk+1=mk+H-1b,

(19)

(20)

(21)

(22)

而由微分的1階近似性質Δf(x)≈f′(x)·Δx，可知：

(23)

進一步，將式(20)代入式(23)，得到：

(24)

再由式(22)易知H≈-ΔbΔm，整理后即可得到自適應步長s：

(25)

式(25)表明：自適應步長s與運動向量的變化量Δm成正比，而與匹配誤差的變化量及其關于m的導數呈反比.對比圖5的實驗結果，Akiyo序列的運動幅度很小，其Δm幾乎為0，而由于播音員的頭部和嘴部存在局部運動，第1次迭代后產生的匹配誤差必然大于0，這就使得該序列的最優初始步長趨近于0；盡管Tempete序列存在中等幅度的運動(即Δm>0)，可是復雜紋理細節勢必產生較大的匹配誤差，故此，由式(25)可推知Tempete序列的最優初始步長也相對較小；考慮到Football序列包含快速運動，其Δm將明顯超過Akiyo和Tempete，且紋理細節的復雜度一般，匹配誤差變化量在預期上不會顯著大于Tempete序列，于是Football序列的最優初始步長較大.綜合上述分析，式(25)的結論與圖5的實驗結果一致.

為了進一步降低式(25)所需要的計算量，本文采用取絕對值運算代替乘法和開平方運算來近似取模長運算：

(26)

(27)

其中，Δmk，Δbk分別表示Δm和Δb的第k個分量.同時，本文僅利用式(25)～(27)確定初始迭代步長，而對于后續的迭代，為保證算法具有較穩定的收斂性，本文在步長值滿足以下條件時將其減半[25]：b的符號在連續3次迭代中改變3次，即在某個解的局部鄰域內發生往返式的迭代.如第4節所述，本文的低位深度的彈性運動模型能朝著2個不同方向進行迭代，若發生折返式迭代，則表明算法很可能處于某個全局局部最優解的單調區間內，且當前步長較大，導致每次迭代均越過該最優解，故應選取更小的步長向這個解進行逼近.

6 2 b深度像素的彈性運動估計步驟

在第5節算法的基礎上，本節給出一種基于2 b深度像素的彈性運動估計方法，具體步驟如圖6所示，其中，xi，yi表示I中某個像素的橫、縱坐標，0≤xi,yi≤B-1；m0表示只包含平移分量的初始運動向量，且m0=(m1,0,…,mp2+1,0,…)；Th表示預設的迭代次數閾值；R′(·)表示參考幀中位于坐標“·”處的2 b深度的像素值；8 b深度像素的菱形搜索和彈性運動估計的搜索窗口尺寸為W×W像素.

Fig. 6 Flowchart of the proposed 2 b elastic motion estimation圖6 本文提出的2 b彈性運動估計流程圖

7 實驗結果與分析

為了驗證本文算法的有效性，以通用中間格式(common intermediate format, CIF)、4CIF和高清格式的34個標準視頻序列(見表4)的1～90f為例進行實驗，并將結果與基于8 b深度像素的菱形運動估計[31](簡稱8 b-DS)、基于8 b深度像素的塊平移全搜索(簡稱8 b-FS)、基于8 b深度像素的彈性運動估計[16](簡稱8 b-Elastic)、基于傳統2 b深度像素的塊平移全搜索算法[29](簡稱2 b-FS)以及未引進自適應初始步長的本文算法(簡稱2 b-Elastic-NAStep)進行比較.

實驗參數選取為：搜索窗口為33×33像素，宏塊尺寸為B=16像素，這與文獻[16,29,31]的參數取值相同，也是視頻編碼器的典型設置.為了在預測精度和收斂速度之間實現折中，令迭代次數閾值Th=5，7.2節還將對此進行深入討論.同時，為公平起見，將傳統8 b-Elastic的迭代次數也設置為5次.運動補償質量采用PSNR進行評價.

Table 4 Test Video Sequences’ Names and Their Formats表4 測試視頻序列名稱及其格式

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

表5羅列了各個測試序列的亮度分量采用不同運動估計算法所得到的平均PSNR.從表5可見，相對于傳統的2 b深度像素的全搜索算法2 b-FS[29]，未引進自適應初始步長的本文算法2 b-Elastic-NAStep將PSNR平均提高了1.15 dB，表明基于Prewitt算子的2 b變換和2 b深度像素的彈性運動模型能夠進行更有效的運動估計補償.2 b-Elastic-NAStep算法的平均PSNR比傳統的8 b深度彈性運動估計8 b-Elastic[16]提高了0.46 dB，其根本原因在于8 b像素的匹配誤差曲面富含局部極值點，在缺少初始搜索的情況下易陷入局部最優，并且8 b匹配誤差曲面的下降梯度為高斯-牛頓法提供的迭代驅動力不足，收斂速度較慢；而2 b-Elastic-NAStep算法則利用8 b-DS計算彈性運動向量的水平和豎直分量，將起始搜索點置入全局最優點的單調區間，再沿著梯度下降方向進行迭代，這表明起始搜索點對于提高彈性運動估計的精度有重要作用，該結論與文獻[19-20,22]的研究結果一致.同時，2 b-Elastic-NAStep算法的平均PSNR較之8 b深度像素的菱形運動估計8 b-DS高出0.90 dB，并且比8 b深度像素的塊平移全搜索8 b-FS提高0.23 dB，說明本文提出的低位深度彈性運動模型在初始搜索的基礎上取得了進一步的性能增益.在引進了自適應初始步長之后，本文算法的運動補償PSNR比2 b-Elastic-NAStep又提高了0.92 dB，這表明通過自適應步長實現黑塞矩陣對迭代過程的控制，有助于彈性運動估計收斂到全局最優解，進而表現出與8 b深度像素的阻尼高斯-牛頓法相近的準確程度.

圖7給出了Akiyo，Husky，City，Flowervase序列的PSNR逐幀比較情況.其中，Akiyo序列僅含有局部慢速運動，且細節簡單；Husky序列則與之相反，前景具有較大幅度的平移運動且紋理復雜性高；City序列含有攝像機的中速搖攝運動和豐富的細節信息；而Flowervase序列則包含攝像機的慢速拉攝運動和中等復雜性的紋理.如圖7所示，盡管4個序列的運動類型、速度和紋理復雜度各有不同，本文算法的運動補償質量均較為穩定，在絕大部分情況下都取得了最高的PSNR，而其他算法的運動估計精度卻會隨著視頻特點的不同出現一定波動.

Table 5 Motion-Compensated PSNR Comparison表5 運動補償的PSNR 比較

Fig. 7 PSNR comparison among different algorithms on the first 90 frames of Akiyo, Husky, City, and Flowervase圖7 Akiyo,Husky,City，Flowervase的前90幀采用不同運動估計算法所得到的PSNR比較

需要指出，作為逆黑塞矩陣的1階近似，本文的自適應步長對于前景運動慢、紋理細節簡單或者含有慢速搖攝、拉攝運動的視頻(如Akiyo,Johnny,Flowervase)尤為有效，而對于含有快速運動和復雜紋理的視頻(如Husky和City)，其性能增益則不夠明顯.究其原因在于，后者的匹配誤差曲面非常復雜，導致每次迭代的最優步長之間存在較大差異，尤其當迭代過程從搜索起始點所在的單調區間進入其他單調區間時，初始步長的普適性難免會受到影響.這也是除了像素深度降采樣這個原因以外，本文算法在Mobile，Waterfall，Harbour等序列上的運動補償PSNR低于傳統8 b-Elastic運動估計的根本緣故.當然，作為一種基于低位深度像素的快速運動估計算法，本文工作的基本目的是在計算量和運動估計精度之間盡量實現折中，而不是通過精確估計阻尼步長來取得最理想的補償質量.從這個意義上講，本文提出的低位深度的彈性模型及其初始步長的自適應計算能夠滿足較低計算負載下的彈性運動估計需要.

7.2 收斂速度與迭代次數的討論

收斂速度是衡量彈性運動估計效率的指標之一.圖8所示為Akiyo，Husky，City序列第2幀采用本文算法的前15次迭代結果.從圖8中能夠發現，對于運動幅度小、細節簡單的Akiyo序列，本文算法在第1次迭代后就趨于收斂；對于運動幅度較大、紋理復雜的Husky序列，運動補償的PSNR隨著迭代次數的增加而不斷升高，但是經過5次迭代就已達到最高PSNR值的99.97%；而對于含有搖攝運動且紋理豐富的City序列，本文算法在第8次迭代時取得了最高的運動補償質量，之后出現PSNR的下降，不過在第5次迭代后已達到PSNR峰值的99.99%；由于Flowervase序列的情況與City類似，這里不再贅述.圖8結果表明，一方面，本文算法在視頻具有不同運動模式和空間分布特點的情況下，均能取得較快的收斂速度.另一方面，視頻的運動幅度和模式，以及空間紋理復雜性對本文算法的收斂速度存在一定影響：當匹配誤差曲面在全局局部最優解附近呈現單峰分布時(如Akiyo)，本文算法將快速收斂，這與3.2節所討論的2 b匹配誤差曲面具有“區域內平滑、區域間銳化”的分布特點一致，下降梯度能提供足夠的迭代驅動力；反之，當迭代過程需越過不同的單峰區間時，可能引起運動補償質量的波動甚至小幅下降.這種情況與7.1節末尾的討論一致，源于本文為了節省計算量，僅求解1次自適應步長并且未對相鄰2次迭代的均方誤差進行比較(若設1個視頻幀包含N個像素，則計算均方誤差的時間復雜度為O(Th×N)).

Fig. 8 Result of the second frame of Akiyo, Husky, and City during the first 15 iterations圖8 Akiyo,Husky,City的第2幀的前15次迭代結果

7.3 計算復雜度分析

設宏塊尺寸為B×B像素，搜索窗口為W×W像素，則不同運動估計算法處理1個宏塊的計算量為：

1) 8 b-FS和2 b-FS的時間復雜度均為O(B2W2).另外，2 b-FS在像素深度變換階段還需O(B2)的復雜度.

2) 由文獻[31-32]可知，8 b-DS的計算復雜度約為8 b-FS的7%，即O(0.07B2W2).

3) 用高斯-牛頓法求解8 b深度彈性運動模型的每次迭代需計算偏導數、黑塞矩陣、逆矩陣、矩陣乘法、雙線性插值和當前的運動補償誤差，其漸近時間復雜度分別為O(pB2)，O(p2B2)，O(p3)，O(pB2)，O(B2)，O(B2).

4) 由于省去了黑塞矩陣及其逆矩陣的計算，本文算法的每次迭代過程只需求解偏導數、向量乘法、雙線性插值和運動補償誤差，其漸近時間復雜度分別為O(pB2)，O(pB2)，O(B2)，O(B2)，基于菱形搜索的初始點預測還需約為O(0.07B2W2)的計算復雜度.

當搜索窗口W=33、塊尺寸B=16、迭代次數閾值Th=5時，本文算法的時間復雜度約為8 b-FS算法和2 b-FS算法的15.26%、8 b-Elastic算法的39.58%，但是高于8 b-DS.若進一步將迭代次數Th減少到2～3次，本文算法則可在8 b-FS算法的10.31%～11.60%的時間復雜度內，獲得與之相當的運動估計精度.

具體地，表6給出了各種算法求解1個塊的運動向量所需的平均操作次數，其中運動估計階段的“Addition”操作包括8 b定點加法和浮點加法.從表6可見，本文方法的操作次數顯著少于8 b-FS，2 b-FS和8 b-Elastic.盡管8 b加法、2 b加法、乘法、取絕對值、比較、位運算等各類操作所需的CPU周期數和計算代價存在明顯差異，可是這些指標依賴于具體的硬件設計和指令集，已超出本文的討論范圍，所以在此不予進一步的定量比較，詳細了解可參見文獻[28].不過，考慮到本文算法采用位操作和比較操作來求解偏導數、向量乘法和運動補償誤差，其計算開銷將低于8 b像素的加法和乘法，且有利于實現多個像素的并行計算，其實際開銷比漸近時間復雜度更低.

Table 6 Average Operation Number Comparison Among Various Motion Estimation Algorithms on Each Block表6 不同運動估計算法對每個塊的平均操作次數比較

8 結 論

為進一步改善彈性運動估計的實時性，本文引進了基于Prewitt梯度算子和正態分布的像素深度變換，以及基于位操作和比較操作的矩陣乘法和偏導運算，推導出高斯-牛頓法的自適應初始步長的1階逼近方法，從而提出了一種基于2 b深度像素的彈性運動估計.其優點在于盡可能地簡化求解彈性運動模型的高斯-牛頓法，用異或運算替代乘法運算，且無需反復計算黑塞矩陣及其逆矩陣.實驗結果表明，該算法的運動補償質量和計算效率優于8 b深度像素的塊平移全搜索算法、菱形搜索算法、傳統彈性搜索算法，以及傳統2 b深度像素的塊平移全搜索算法.

另外，本文算法仍存在若干問題可臻完善，如快速預測起始搜索點、根據匹配誤差曲面的曲率變化來自適應地更新初始步長，以及設計能夠高效執行本文算法的硬件電路等，我們將在今后的工作中進一步深入研究這些問題的解決思路.