基于雙向自適應時空切片的關鍵幀提取算法

韓震博

（四川大學計算機學院，成都610065）

1 視頻關鍵幀提取概述

隨著大數據時代的到來，網絡上的視頻數量大幅增加，如何快速且有效地在大量的視頻中找到所需要的視頻片段成為人們關注的熱點問題。

視頻是由連續變化的圖像幀組合而成，人們將這段連續的圖像幀中能夠有效地代表視頻主要內容的幀稱為關鍵幀。關鍵幀提取技術在視頻處理領域中發揮著重要作用，通過對視頻中關鍵幀的提取，能有效地減少冗余信息，使得需要處理的數據量大大減少，為后續的視頻處理提供便捷。

目前，關鍵幀提取技術主要包括以下4類[1]：

（1）基于視頻運動信息的關鍵幀提取：

視頻中包含著大量的運動信息，可以通過對視頻中運動信息的提取及分析，實現視頻關鍵幀的提取，具體的方法包括基于運動特征的關鍵幀提取方法[2]、基于運動分析的關鍵幀提取方法[3]等。

（2）基于視頻內容的關鍵幀提取：

這類方法使用視頻幀序列中每一幀圖像的紋理、顏色、形狀等底層特征作為關鍵幀提取的依據[4]。相鄰幀間特征差異的大小可以有效地反映出視頻內容變化的顯著程度，因此可以通過這類方法完成關鍵幀的提取。

（3）基于視頻鏡頭信息的關鍵幀提取：

這類方法首先通過一定的方式，將視頻分割成若干個獨立的鏡頭，然后按照一定的規則在每個獨立的鏡頭中完成關鍵幀的提取。常用的方法有基于像素的關鍵幀提取方法[5]以及基于直方圖的關鍵幀提取方法[6]等。

（4）基于聚類的關鍵幀提取：

這類方法對視頻鏡頭間以及視頻鏡頭內信息的關聯性進行充分利用，基于幀間圖像的相似性對視頻序列進行聚類，并從每一類聚類結果中選出一幀作為關鍵幀。常用的聚類方法包括K-means算法、層次聚類算法[7]等，各聚類算法有著不同的優缺點。

2 基于雙向自適應時空切片的關鍵幀提取算法

針對現有關鍵幀提取算法中常出現的存在漏幀、冗余幀等問題，本文提出了一種基于雙向自適應時空切片的關鍵幀提取算法。這一部分將對本文中采用的關鍵技術及算法流程進行介紹。

2.1 基于活動強度圖的時空切片位置選擇

時空切片是一種高效的視頻時空分析方法，具有計算量低、抗干擾能力強等特點[8]。時空切片是將視頻幀序列中每一幀在選定的同一位置上的像素信息進行提取，并組合成一幅具有完整的視頻時間維度信息的二維圖像。時空切片通常有三種取法：垂直切片、水平切片和對角線切片[9]，如圖1所示。

圖1時空切片示意圖

在進行時空切片時，基本都是基于視頻幀中心點橫（縱）向的延伸線作為切片位置，但該切片位置并不一定屬于視頻中物體運動的區域，因此，基于該位置提取出的時空切片并不一定能較好地包含視頻中的物體運動信息。

為了獲取視頻中內容變化的區域及強度，本文定義了活動強度圖，其計算方式如下：首先，對圖像幀序列進行灰度化處理；其次，從第一幀開始，計算相鄰兩幀在同一像素點上灰度值的差值，當該值的絕對值大于設定的閾值時，則認為該像素點在相鄰兩幀間變化明顯；如果同一像素點在相鄰兩幀間灰度值的差值的絕對值大于設定的閾值，那么將此值進行累加，并將得到的值稱為該像素點的灰度變化累加值；最后將各個像素點的灰度變化累加值歸一化到[0,255]，即可得到活動強度圖。活動強度圖的計算公式如下：

式（4）中，I(x,y)為最終得到的活動強度圖。

對一段“投擲鉛球”的視頻進行活動強度圖的提取，提取結果如圖2所示。

圖2活動強度圖

在活動強度圖中，灰度值越大的點代表該像素點的信息變化強度越大。因此在進行時空切片時，可以選擇信息變化強度最大的行（列），作為時空切片的位置，使得提取到的時空切片中能夠包含更多的視頻信息。

2.2 基于切片位置自適應的雙向時空切片方法

基于時空切片的關鍵幀提取效果在很大程度上受時空切片包含視頻中物體運動的信息量的影響，也就是說，為了得到更好地關鍵幀提取效果，時空切片中就要盡可能多地包含視頻中的物體運動信息。

本文提出的基于切片位置自適應的雙向時空切片方法能夠有效地解決這一問題，一方面，基于活動強度圖的時空切片位置選擇能夠保證在單一方向的時空切片中包含更多的圖像信息；另一方面，采用雙向時空切片可以在一定程度上解決單一方向的時空切片時空間信息匱乏的問題。仍以上述“投擲鉛球”的視頻為例，本文提取出的雙向時空切片圖像如圖3所示。

圖3雙向時空切片圖像

2.3 算法描述

下面是本文算法的整體步驟：

步驟一：提取視頻幀序列的活動強度圖

對灰度化處理后的視頻幀序列進行活動強度圖的提取；

步驟二：選擇最佳時空切片位置

統計活動強度圖中像素值最大的行和列，并將該行和該列分別作為此視頻幀序列進行水平切片及垂直切片的位置；

步驟三：提取出視頻的雙向時空切片

根據最佳時空切片位置，提取出視頻幀序列的雙向時空切片；

步驟四：通過改進K-means算法對提取出的雙向時空切片進行聚類

使用改進K-means算法對雙向時空切片圖進行聚類。圖4所示為圖3的聚類結果。

圖4聚類結果

在聚類結果中，不同的顏色代表不同的類別。值得注意的是，由于視頻具有時間上的連續性，因此，將顏色相同但不連續的類視為不同的類別。

步驟五：對連續視頻幀數量少的類進行處理

在對雙向的時空切片進行聚類時，可能會出現較少數量的連續視頻幀被聚為一類的情況，這種情況往往是由于視頻中存在干擾信息所致，因此在這一類中提取出的關鍵幀往往不能很好地表達視頻信息。對此，本文采用如下的處理方案：當連續3幀及以下的視頻幀被分為一類時，將這一類歸并到其相鄰的類中，若這一類兩側相鄰的類顏色相同，則將這一類與其兩側相鄰的類合并為一類；若這一類兩側相鄰的類顏色不同，則將這一類合并到相鄰兩類中聚類中心間的距離更近的那一類中。

步驟六：候選關鍵幀的提取

在完成對雙向時空切片的聚類后，選取每一類的聚類中心作為候選關鍵幀。

步驟七：篩選最終的關鍵幀

雙向的時空切片圖可以在一定程度上彌補單一方向時空切片的空間信息不足的問題，但二者一般會包含冗余信息，進而導致提取出的候選關鍵幀存在冗余，因此需要對候選關鍵幀進行進一步的篩選。本文采用的篩選方法是通過計算相鄰候選關鍵幀之間的時間間隔進行的，若相鄰候選幀間的時間間隔大于5幀，則認為這兩幀間不存在冗余，均為最終的關鍵幀；否則，兩幀間存在冗余，保留兩幀中與各自聚類中心距離更近的幀作為最終的關鍵幀。

算法流程圖如圖5。

圖5算法流程圖

3 實驗設計與結果分析

本文實驗環境如表1所示。

表1 實驗環境

3.1 實驗數據與評價指標

本文方法是對整個視頻區域進行活動強度圖的提取，在視頻背景區域變化較小時，提取到的活動強度圖能更為精確的反映視頻中物體的運動信息。因此，本文從體育、演講、汽車、太空四類視頻中分別選取三個視頻背景區域變化較小的視頻作為測試視頻。實驗數據來源于UCF101數據集[10]以及開放的標準視頻庫[11]，實驗中使用的測試視頻長度不一、分辨率不同、內容差別明顯，能夠充分驗證各關鍵幀提取方法的有效性。

目前，在視頻關鍵幀提取領域中存在多個較為通用的評價指標，本文選取了查全率與查準率兩個指標來評價本文方法的性能。

（1）查全率

該指標可以用來衡量關鍵幀漏檢的程度。計算公式如下：

式（5）中，Nc為提取正確的關鍵幀數量，Nm為漏檢的關鍵幀數量。

（2）查準率

該指標可以用來衡量提取到關鍵幀的準確程度。計算公式如下：

式（6）中，Nf為誤檢的關鍵幀數量。

3.2 實驗結果與分析

分別使用本文方法與直方圖法、文獻[12]提出的方法、文獻[13]提出的方法對測試視頻進行關鍵幀的提取，并通過查全率、查準率來衡量各方法的性能。實驗結果如表2所示。

從實驗結果可以看出，在不同的視頻類別下，本文方法提取關鍵幀的查全率與查準率相較于各對比算法均有明顯的提升。由此可見，本文提出的基于雙向自適應時空切片的關鍵幀提取算法性能優良，使用該算法提取出的關鍵幀能夠較為準確地完成對視頻主要內容的表達。

表2 在不同視頻類別下各方法的查全率與查準率統計

4 結語

本文提出了一種基于雙向自適應時空切片的關鍵幀提取算法，通過引入活動強度圖充分利用視頻的運動信息，進而實現了垂直與水平方向上切片位置自適應的時空切片方法，在使得后續聚類結果具有時間信息的同時，解決了傳統的固定位置時空切片、單一方向時空切片導致提取信息不足的問題，然后通過改進Kmeans算法實現了閾值自適應的候選關鍵幀提取，最終，對從兩幅時空切片圖中提取出的候選關鍵幀進行進一步的篩選，得到最終的關鍵幀。實驗結果表明，本文方法在能夠保證較低壓縮比的情況下，查全率與查準率明顯優于同類算法，提取出的視頻幀能夠有效地反映視頻的主要內容。