基于特征跟蹤和網格路徑運動的視頻穩像算法*

熊 煒，王傳勝，管來福，童 磊，劉 敏，曾春艷

(1.湖北工業大學電氣與電子工程學院,湖北 武漢 430068; 2.美國南卡羅來納大學計算機科學與工程系，南卡 哥倫比亞 29201)

1 引言

通過智能手機等個人設備拍攝短視頻已經成為人們記錄生活的主流方式。在手持移動設備拍攝視頻的過程中，由于設備內部或者外在因素的影響，獲得的視頻通常不穩定。抖動視頻降低了視頻圖像的質量，使得觀看者有暈眩感。視頻穩像技術的目的主要是消除或減少視頻的抖動，以便生成穩定的視頻[1]。

視頻穩像方法一般包含3個部分，分別是運動估計、運動平滑和運動補償。根據運動估計中運動模型的不同，又可以分成2D方法[2,3]、2.5D方法[4]和3D[5]方法。3D方法魯棒性差、速度慢。2.5D方法需要跟蹤很長的運動軌跡，僅適用于專業設備，不適用手持設備拍攝的視頻。由于2D方法處理速度快、魯棒性好，常被用來處理視頻去抖問題。

2D視頻穩像方法中的相機運動估計先進行局部運動估計，再通過局部運動向量估計全局運動向量。局部運動估計方法主要包括2類：基于像素點的方法和基于特征點的方法[1]。基于像素點的方法主要包括塊匹配法、相位相關法、灰度投影法以及光流法等。塊匹配法原理簡單、實現方便、應用廣泛，但是在有快速運動的場景中效果并不好；相位相關法是一種非線性的算法，基本原理是傅里葉變換，有較高的匹配精度，且具有一定的抗干擾能力，但是計算時間過長，不適用于實時場景；光流法盡管不需要了解相關場景信息就能準確地檢測識別運動目標位置，但有計算量大、耗時長、對光線敏感等缺點。基于特征點的方法主要將高維的圖像數據進行簡化表達，常見方法包括角點檢測法、斑點檢測法、邊檢測法等。角點是指在某方面屬性特別突出的點，一般角點檢測法有Harris角點檢測法、FAST(Features from Accelerated Segment Test)算法等。斑點檢測法主要對特征點周圍像素灰度值大的區域進行檢測，常見方法有SIFT(Scale-Invariant Feature Transform)算法、SURF(Speeded Up Robust Features)算法等。2011年,Grundmann等人[2]提出L1優化處理的運動平滑方法來處理抖動視頻；2013年，Liu等人[6]提出捆綁相機路徑框架算法進行視頻穩像；2016年，Liu等人[7]提出一種新型MeshFlow運動模型算法來實時穩定抖動視頻；2017年，熊晶瑩[8]提出基于特征提取與匹配的車載電子穩像方法；2018年，Nie等人[9]在視頻拼接中考慮視頻穩像，提出一種結合識別視頻背景和捆綁相機路徑的方法來拼接視頻；隨著計算機視覺及深度學習的發展，2019年，Wang等人[10]提出一種StabNet神經網絡模型處理抖動視頻，該方法對計算機顯卡及內存要求較高。

針對手持設備拍攝的抖動視頻問題，本文提出一種基于特征跟蹤和多網格路徑運動的視頻穩像算法。根據SIFT與KLT(Kanade-Lucas-Tomasi)相結合的特征跟蹤方法[11]，首先通過SIFT算法檢測視頻幀的特征點；再對檢測出來的SIFT特征點通過KLT算法進行特征追蹤匹配；然后根據匹配到的特征點，利用RANSAC(RANdom SAmple Consensus)算法估計相鄰幀間的仿射變換矩陣；再根據文獻[6]思想，將視頻幀劃分為均勻的網格，選取均勻網格中的一格，把相鄰幀間仿射矩陣與前一幀相機運動路徑累乘，由此計算視頻的運動軌跡。再通過極小化能量函數優化平滑多條網格路徑。最后由原相機路徑與平滑相機路徑的關系，計算相鄰幀間的補償矩陣，利用補償矩陣對每一幀進行幾何變換，從而得到穩定的幀序列。本文算法框架如圖1所示。

Figure 1 Block diagram of the algorithm in this paper圖1 本文算法框圖

2 基于特征跟蹤的全局運動估計

基于特征跟蹤的全局運動估計主要分為以下4步:

首先選取視頻第1幀作為基準，而后進行相鄰幀間的處理，通過直方圖均衡化、高斯或卡爾曼濾波等方法進行預處理；然后進行SIFT[12]特征點的檢測及KLT跟蹤，主要檢測圖像中梯度變化較大的點，對相鄰幀間的特征點進行跟蹤；再根據之前跟蹤匹配的特征點，估計出幀間的仿射變換；最后將幀間的仿射變換進行累積，得到相機的路徑。

2.1 SIFT特征點提取

SIFT算法對視角變化、仿射變換、噪聲等保持較好的穩定性；同時，在圖像旋轉、尺度縮放、亮度變化等方面具有很好的不變性。SIFT算法步驟如下所示：

(1)尺度空間和極值點的檢測。圖像I(x,y)的高斯尺度空間(如圖2a左側)可用式(1)表示:

L(x,y,σ)=G(x,y,σ)·I(x,y)

(1)

得出不同尺度下的特征點后，進一步由高斯尺度空間生成高斯差分尺度空間DOG(Difference Of Gaussian)。其DOG(如圖2a右側)可用式(2)表示：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))·I(x,y)

(2)

其中，k為組內總層數的倒數。

接下來在DOG尺度空間通過比較每一個像素和它所有相鄰像素的值，從而得到極值點，如圖2b所示。

Figure 2 Schematic diagram of feature point acquisition圖2 特征點獲取示意圖

(2)關鍵點定位及其主方向確定。關鍵點是由DOG空間的局部極值點組成的。首先利用擬合關系確定關鍵點的精確位置和尺度。在完成關鍵點的梯度計算后，使用直方圖統計鄰域內像素的梯度和方向，然后建立關鍵點鄰域像素的梯度方向直方圖，直方圖的峰值方向代表了關鍵點的主方向。如圖3所示。

Figure 3 Main gradient direction determination圖3 主梯度方向確定

(3)關鍵點描述子的生成。先將坐標軸移動到關鍵點的主方向，以關鍵點為中心取8×8窗口，計算圖像每個像素的梯度。然后建立45°的等間隔梯度直方圖，計算得到不同方向的累加值。最后利用歸一化處理得到的累加值作為一個描述子。如圖4所示。

Figure 4 Key point descriptor generation圖4 關鍵點描述子生成

通過SIFT算法提取視頻每一幀特征點，得到特征點如圖5所示。

Figure 5 Feature points of a sample video frame extracted by SIFT algorithm圖5 SIFT算法提取視頻幀的特征點

2.2 KLT算法跟蹤

提取視頻中相鄰2幀間的SIFT特征點后，需要對其特征點進行跟蹤。主要的匹配跟蹤方法有K最近鄰算法、快速最近鄰逼近搜索算法、KLT算法[13]等。KLT算法是基于最優估計的匹配跟蹤算法，也是一種基于特征點匹配算法。由于其在運動速度小的情況下匹配精度較高、耗時較少[11]，所以本文采用該算法進行特征點跟蹤。

KLT跟蹤算法假設目標在視頻流中只產生一致性的小位移，并且目標的灰度變化不大。那么，算法必須是在以下3個假設成立的前提下產生良好的效果：(1)亮度一致；(2)時間連續或者運動位移小；(3)空間一致性，鄰近點有相似運動，保持相鄰。本文使用的抖動視頻都由移動設備拍攝所得，運動速度較小，幀間位移也較少，滿足上述的3點假設。因此，使用KLT算法匹配可以縮小匹配過程中的搜索范圍，減少匹配時間，且有較高的匹配精度。

KLT算法是一種以待跟蹤窗口在視頻相鄰幀間的灰度差平方和(SSD)作為度量的匹配算法[11]。假設一個包含特征紋理信息的特征窗口W，設t時刻對應的視頻幀用I(x,y,t)表示，t+τ時刻對應的視頻幀用I(x,y,t+τ)，其對應的位置滿足式(3)：

I(x,y,t+τ)=I(x-Δx,y-Δy,t)

(3)

其中，Δx和Δy為特征點X(x,y)的偏移量。在I(x,y,t+τ)中的每個像素點，都可以根據I(x,y,t)中相對應的像素點平移d(Δx,Δy)求得。

假設給定的相鄰幀I和J，定義ε為：

(4)

其中，W是給定的特征窗口，ω(X)為權重函數，且常設為1。

將式(4)中J(X)-I(X-d)替換成其對稱的形式J(X+d/2)-I(X-d/2)，可改寫為式(5)：

(5)

為了得到最佳匹配點，將J(X+d/2)進行泰勒展開，去掉最高次項，僅保留前2項，g是泰勒展開式的一階泰勒系數，gx和gy分別為x和y方向上的一階泰勒系數。根據式(5)對d進行求導，可得式(6)：

(6)

(7)

其中，d表示特征窗口W中心的平移，dk表示第k次牛頓迭代計算所得d值。在迭代過程中，計算d需要使用初始估計值d0，設初始值d0=0。

通過KLT跟蹤算法得出視頻幀的跟蹤點，如圖6所示。

Figure 6 Feature points of a sample video frame tracked by KLT algorithm圖6 KLT算法跟蹤視頻幀的特征點

2.3 幀間全局運動估計

相鄰視頻幀間的全局運動主要表現為平移、縮放、旋轉等變換,其他更加復雜的變換形式都由這些基本變換組合而成，比如相似變換、剛性變換和仿射變換[14]等。本文采取仿射變換作為相鄰幀間的全局運動，利用RANSAC算法估計出幀間的仿射變換矩陣。

其基本數學模型如下所示：

(8)

對于輸入視頻相鄰的2幀圖像I和J，分別設為第t幀和第t+1幀。先用SIFT算法檢測圖像的特征點，再對檢測出來的SIFT特征點通過KLT算法進行特征追蹤匹配，最后對跟蹤匹配到的特征點利用RANSAC算法估計相鄰幀間的仿射變換矩陣。

(9)

其中，Ht-1表示第t-1幀與第t幀的仿射變換矩陣。

通過幀間運動計算相機的運動軌跡。網格i運動路徑計算如圖7所示。

Figure 7 Motion path of the grid圖7 網格的運動路徑

3 基于多網格路徑的運動平滑

選擇基于2D捆綁相機路徑[6]框架來穩定視頻。本文將求出的相鄰幀間仿射變換矩陣，應用于下一幀均勻的網格中。具體地，設輸入的視頻共有N幀，將視頻的每一幀劃分為m×n的均勻網格。通過求解相鄰幀間的仿射變換矩陣，可以得出相鄰網格運動。進一步，計算相機的運動路徑軌跡。

(10)

設相機的原始運動路徑為Ci,i=1,2,3,…,m×n,而相機的運動路徑軌跡是由所有網格的路徑合成的。

先針對一條路徑進行平滑。給定路徑C，若要得到處理后的平滑路徑P，則C=Ct，P=Pt。根據文獻[6]的思想，P可以通過極小化能量函數得到，該能量函數如式(11)所示：

(11)

其中，λt為自定義參數；Ωt表示第t幀的相鄰幀；‖Pt-Ct‖2項使得平滑處理后的路徑盡可能地接近原始路徑，確保穩像后的視頻的裁剪率與扭曲率較小；‖Pt-Pr‖2為平滑項，用于穩定原始路徑。

如果對于每一條網格路徑都采取式(11)平滑相機運動軌跡，則視頻幀對應的空間網格不能被保留，會導致穩像后的視頻出現扭曲率較大的情況。所以，相機運動軌跡的平滑是通過極小化能量函數來平滑所有的空間網格。其能量函數如式(12)所示：

(12)

i=1,2,3,…,m×n;t=1,2,3,…,N

(13)

通過基于Jacobi的迭代[15]的方法求解式(13)稀疏線性方程組，迭代形式用式(14)表示：

(14)

4 運動補償

由運動平滑得到相機運動軌跡后，根據原相機運動軌跡和求得的新的運動軌跡之間的關系，可得到新的運動網格。依據新的運動網格和原視頻網格間的位置差異，可求得相鄰每幀的運動補償，最后對每一幀進行運動補償，進而獲得穩定的視頻。

通過運動平滑對相機路徑Ct平滑處理之后，將對視頻的每一幀進行補償。假設補償矩陣為Bt，則得到的視頻幀間的路徑Pt滿足：

Pt=CtBt

(15)

通過式(15)計算得出相鄰幀間的補償矩陣Bt。計算每一幀的補償矩陣后，利用Bt對每一幀圖像進行幾何變換，從而得到穩定的幀序列，也就得到了穩定的視頻。

5 實驗結果與分析

將本文提出的算法與Liu等人[6]的捆綁相機路徑算法、Liu等人[7]的MeshFlow模型算法以及Javier[16]的參數模型算法進行了大量對比實驗。圖8展示了實驗中使用的視頻數據集，編號為1～8。測試視頻來源于文獻[6,10]提供的公開數據集，其中視頻1～6來自文獻[6]，視頻7、視頻8來自文獻[10]，且視頻的分辨率均為640×360。視頻1具有單個前景運動物體，視頻2具有多個運動物體，視頻3有小范圍鏡頭移動，視頻4有快速移動的部分，視頻5和視頻6都有小范圍的左右搖晃，視頻7是沿著同一方向的移動，視頻8具有大范圍的左右搖晃。

本文采用相鄰幀間的PSNR(Peak Signal to Noise Ratio)[8]和SSIM(Structural Similarity Index)[17]均值及相對應的標準差作為客觀質量評價指標。本文在Intel酷睿i5-3230M 2.6 GHz CPU和4 GB內存的計算機上,利用未經優化的Matlab 2017b進行實驗。實驗中，在運動估計階段，把視頻每一幀都劃分為8×8的均勻網格。

實驗結果如表1和表2所示。由于視頻8的運動復雜性，采用文獻[7]的MeshFlow未能生成最終的穩定視頻，因此未記錄其PSNR值與SSIM值。

Figure 8 Video data used in the experiment,numbered from 1～8圖8 實驗中使用的1～8號視頻數據

Table 1 Comparison of PSNR mean and standard deviation between frames

Table 2 Comparison of SSIM mean and standard deviation between frames

通過表1可以發現，實驗選取的8個視頻，穩像后的PSNR值與原視頻相比得到了明顯提高，說明相鄰幀間的灰度差變小，視頻幀序列穩定。8個視頻原始PSNR值平均值為21.9 dB，本文算法的平均值為33.1 dB。穩像后的PSNR值平均提升了11.2 dB。捆綁相機路徑算法平均PSNR值為30.8 dB，相比提升2.3 dB。通過表2可以發現，本文的穩像算法有效提高了圖像間的結構相似性，穩像后比穩像前SSIM大約提升了59%。相比捆綁相機路徑算法平均SSIM值提升3.3%。

本文算法主體包含2部分：使用SIFT算法與KLT算法相結合的特征跟蹤和基于多網格路徑的運動平滑。本文采用SIFT算法對視頻幀進行特征提取，并使用KLT算法對特征點進行跟蹤。SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化具有不變性，對視角變化、仿射變換、噪聲也具有一定程度的穩定性。SIFT算法對于部分物體遮蔽的特征提取效果也十分不錯，因此對所選的8個視頻都有很好的特征提取效果，這樣使得KLT算法跟蹤更加精確，使仿射矩陣計算更加準確，也將使得最終的穩像效果較好。在多網格路徑的運動平滑部分，文獻[6]將視頻每一幀劃分為均勻的網格，并求出相鄰每個均勻網格的單應性變換矩陣，應用于下一幀均勻網格中。本文算法將全局運動估計用于幀間的局部運動估計，相比文獻[6]更能使抖動視頻變得穩定。相比文獻[7]，本文算法更加準確地表示了視頻全局運動軌跡，且計算量小。文獻[7]提出的MeshFlow是平滑圖像空間稀疏運動，僅在網格頂點處具有運動矢量。匹配的特征點上的運動矢量被傳遞到它們對應的附近網格頂點，運動軌跡變復雜，整個變換矩陣計算也變得復雜。相比文獻[16]直接估計幀與幀之間的全局變換，本文算法提出的基于SIFT與KLT相結合的特征跟蹤能夠更加精確地匹配跟蹤特征點并計算出全局變換矩陣，使得最終穩像效果較好。

6 結束語

針對手持移動設備拍攝的抖動視頻問題，本文提出了一種基于特征跟蹤和多網格路徑運動的視頻穩像算法。通過SIFT算法提取視頻幀的特征點，采用KLT算法追蹤特征點，利用RANSAC算法估計相鄰幀間的仿射變換矩陣，將視頻幀劃分為均勻的網格，計算視頻的運動軌跡，再通過極小化能量函數優化平滑多條網格路徑。最后由原相機路徑與平滑相機路徑的關系，計算相鄰幀間的補償矩陣，利用補償矩陣對每一幀進行幾何變換，從而得到穩定的視頻。實驗表明，該算法在手持移動設備拍攝的抖動視頻中有較好的結果。