基于K-means聚類算法的視頻關鍵幀提取的研究

司若妍，張明（上海海事大學信息工程學院，上海　201306）

基于K-means聚類算法的視頻關鍵幀提取的研究

司若妍，張明
（上海海事大學信息工程學院，上海201306）

關鍵幀是視頻處理中的一個關鍵技術。通過對視頻進行關鍵幀提取，來有效地獲取視頻信息，從而提高人們在視頻庫中檢索信息的準確性和效率。K-means聚類算法是視頻關鍵幀提取的一個重要方法，但是，聚類閾值設定不合理，往往會導致關鍵幀的提取效果不理想，所以，針對以上問題提出一種自適應閾值的方法，并通過實驗證明該方法的有效性。

K-means聚類算法；關鍵幀提取；自適應閾值

0　引言

隨著現代計算機網絡和多媒體信息技術的快速發展，越來越多的人依賴于網絡作為自己的信息獲取渠道。視頻、音頻、圖像和文本是網絡信息傳遞的主要媒介。視頻由于其直觀，內容豐富的特點，愈發成為人們欣然接受的一種信息獲取方式和娛樂休閑方式。視頻被廣泛應用于生活中的各個領域，例如醫療、廣告、影視、教育、體育競賽等。但是，如何快速有效地在豐富的網絡視頻資源里，找出人們所需要的視頻信息并非是一件易事，所以，這也越發引起人們的關注。

人們看到的視頻是由一系列視頻圖像幀組合而成，而關鍵幀是可以代表視頻的主要內容和事件的變化過程那些圖像幀，所以，可以通過提取出視頻中的關鍵幀來獲取視頻中的相關信息。關鍵幀的提取是視頻處理的一個關鍵技術，是將對視頻的處理轉化為圖像處理的一個重要的方法，它可以在很大程度上減少了計算機處理信息的數據量，同時也可以提高人們在視頻庫中檢索視頻信息的準確性和效率。

1　主要的關鍵幀提取方法

目前，關鍵幀的提取方法多種多樣，主要可以歸納為以下幾種：

只提取視頻鏡頭序列中第一幀和最后一幀作為該視頻的關鍵幀［1］的基于鏡頭邊界的關鍵幀提取方法。分析和計算光流得出視頻序列的運動量，然后比較各幀運動量的值，并選取局部最小值處的幀為關鍵幀的基于運動分析的關鍵幀提取方法［2］，通過對每一幀圖像的顏色、紋理等視覺特征信息的比較，選取幀間的特征顯著變化的幀作為關鍵幀的基于視頻內容的關鍵幀提取方法［3］，無需對視頻進行解壓處理，可直接從MPEG壓縮視頻流上，進行關鍵幀的提取操作的基于壓縮視頻的關鍵幀提取方法［4］，以及依據幀圖像間相似度的大小，將各個視頻幀序列進行聚類，然后依次從每個聚類簇中選取一幀作為關鍵幀［5］的基于視頻聚類的關鍵幀提取方法。

本文主要針對K-means聚類的關鍵幀提取方法展開研究，對于如何選取聚類中心和聚類數目的問題，提出一種自適應的閾值確定方法，來解決這一問題。

2　K-means聚類算法

K-means聚類算法是聚類分析中運用最為廣泛的算法之一。無論在數據處理或是圖像、視頻處理中，都運用地相當廣泛。

K-means算法在進行關鍵幀的提取的過程中，首先在n個數據對象中隨機選取K個對象來作為初始的聚類中心，之后再計算當前幀與隨機選取的K個聚類中心之間的距離，并把當前幀劃分到距離其最近的聚類中心所屬的聚類當中。再根據每個聚類中所有對象的均值（即中心對象），計算樣本集中每個對象與這些中心對象的距離，再按照以上規則再次進行分類。循環往復以上步驟，直至聚類中心的變化小于某個預設的閾值，則運算停止，即可得到最后的聚類結果。通過該聚類算法，可以把圖像序列中的圖像幀劃分為K類，并且每個類中的關鍵幀都是有一定相似性的，從而提高關鍵幀提取的效率。

但是K-means算法也有它的不足之處，K-means算法對初始中心敏感，不同的初始中心會導致不同的聚類結果。這便使得K-means算法會導致最后的聚類結果是局部最優而不是全局最優。

在進行K-means聚類算法的關鍵幀提取的過程中，因為關鍵幀的數目是由指定的閾值來確定，所以，閾值的選取對關鍵幀的提取效果影響很大，尤其是在對視頻內容一無所知的情況下，預先選取合適的閾值是很困難的一件事，如果閾值設定過大，就會提取過多的關鍵幀，若設定的閾值過小，提取到的關鍵幀不能代表鏡頭。

2.1特征選取

為了能有效進行聚類，選取合適的聚類特征參數也是很重要的。目前，使用比較普遍的方法是顏色直方圖，本文選用每一幀的HSV顏色空間中的顏色直方圖和紋理特征因子組合成的特征因子作為視覺特征。

（1）顏色特征選取

HSV顏色模型是色調（H，Hue）、飽和度（S，Saturation）、亮度（V，Value）三個英文單詞的首字母縮寫，由A.R.Smith在1978年創建的一種顏色空間，與傳統的RGB顏色空間模型相比，HSV顏色模型因為其具備有線性伸縮性的性質，所以更加符合人類視覺的特點，與人類的視覺感知更接近，因此人們更傾向于用HSV顏色模型來描述顏色。

然而在通常的情況下，由于RGB顏色模型的簡便性，我們依然習慣于采用RGB顏色空間模型來描述圖像，因此我們首先需對顏色空間模型進行轉換，把RGB顏色空間轉換成HSV顏色空間。設（r，g，b）分別是一個顏色的紅、綠、藍坐標，它們均為0到1之間的實數。那么，HSV空間中的（h，s，v）可以表示如下：

其中，h∈［0，360°）是角度的色相角，而s，v∈［0，1］分別表示飽和度和亮度。在進行提取的過程中，因為一個圖像幀中所包含的顏色信息十分豐富，如果直接采用HSV空間的顏色直方圖來描述一個圖像幀，計算量會非常大，為了計算的簡便，本文按照文獻［6］的方法，來對HSV顏色模型進行等間隔量化，將色調H 以20°為一間隔，分為18份，飽和度S和亮度V以0.3為一間隔分為3份，這樣就把HSV顏色空間劃分為166種顏色來進行顏色特征的提取。經過量化后，為了減少計算量，因為人的視覺對于分量H較為敏感，S次之，V最弱，所以，本文再按照公式（4）將H，S，V合成為一個一維矢量。

（2）紋理特征

在對圖像幀處理的過程中，如果僅僅是以顏色特征作為特征提取的參數，對于種類繁多的視頻資源來說，顯得過于單一，所以，本文在原本的顏色特征的基礎上，引入紋理特征算子。

本文利用LBP［7］（局部二值模式）紋理特征描述算子來對幀圖像的紋理特征進行處理。因為其所具有的灰度不變和旋轉不變的性質很巧妙地避免了由光照顯著改變而引起的實驗結果的誤差。

LBP算子的基本思想是選取所要計算的區域的中心像素并將其灰度值設為閾值，再對周圍圓形鄰域內的像素進行二值化處理，即將周圍圓形鄰域內的像素灰度值與該閾值進行比較，若像素值大于該閾值則此鄰域的像素值為1，反之為0，由此可得一串二進制的值，再對不同位置的像素值進行加權求和，即可得到該區域的LBP值。表示在半徑為R的圓形鄰域內有P個像素點。

圖1　基本的LBP算子計算示意圖

用公式可以表示為：

其中，P表示為在半徑為R的圓形鄰域內有P個像素點。bi為像素點的像素值，bc為中心點的像素值。如果bi-bc的值大于0，則s（x）的值為1，反之，s（x）值為0。

本文在原本LBP算子的基礎上，運用LBP算子的等價模式，將其降維，以減少計算量。LBP等價模式是：如果某個LBP所對應的循環二進制數的序列所包含的0到1或從1到0最多有2次躍變時，那么，該LBP所對應的二進制就稱為一個等價模式類。例如，00000000，00011111，10000011分別有0次，1次，2次躍變，它們都可以劃歸為等價模式類。若對于二進制10101111而言，因為它有4次躍變，所以不可以劃歸為等價模式類，這種模式被劃歸為混合模式類。用公式可以表示為：

其中，u表示循環二進制數中0-1躍變的次數。

在經過LBP算子等價模式的處理之后，原先LBP算子中256維的計算維度可以簡化為59維，這就起到了降維的目的。

2.2計算幀間的相似度

因為本文是利用顏色特征和紋理特征共同來對幀圖像進行描述，所以，兩幀之間的相似度可以用二者差值來表示。在本文中，首先計算兩幀圖像之間的顏色直方圖的差值，再計算兩幀圖像之間的LBP紋理算子的差值，再將這兩個差值進行加權計算，最后得到的總差值即可表示為兩幀之間的相似度，差值越大，說明兩幀之間相似度越大，反之，相似度越小。

其中，I代表幀圖像，C代表幀圖像的顏色直方圖矢量值，V代表采用LBP紋理算子方法計算得到的紋理特征值，D（Cc，Cc+1）和D（Vc，Vc+1）則可以分別表示兩幀圖像的顏色特征及紋理特征的歸一化相似度，數值越大，說明相似度越低，ω1，ω2分別代表顏色相似度以及紋理相似度的權重，且滿足權值關系：ω1+ω2=1，在本文的實驗中，ω1和ω2均取值0.5。

3　自適應閾值關鍵幀提取

在進行聚類算法的關鍵幀提取過程中，因為要隨機選取聚類中心和人為設定聚類閾值，而使得算法計算量過大，用時過多，導致算法效率不高，所以為了提高K-means算法的提取關鍵幀效率，本文從聚類中心和聚類閾值這兩個方面上進行研究，改進一種自適應閾值的聚類計算方法。

（1）假設一個視頻鏡頭中有N幀｛f1，f2，f3，…，fn｝，利用公式（7）求相鄰兩幀之間的相似度，計算相鄰兩幀之間的幀差可以得到一個幀差序列D=｛D1，D2，D3，…，Dn-1｝

（2）根據幀差序列，設定一個參數T，令

其中，令M=n-c-1

μc為當前幀差的平均值，為當前幀差的方差。用表示當前聚類的離散度。

（3）若相鄰兩幀之間的幀差≥DT，那么開始新的聚類；否則，若當前幀與當前類中心的聚類≥DT，那么開始新的聚類。

（4）算法停止，得到初始聚類的劃分，和初始聚類個數。

對于一個視頻鏡頭聚類，最理想的聚類效果是在聚類中各個鏡頭幀之間特征越相似，聚類外，各個鏡頭幀之間差異越大。所以，我們希望聚類內的分散度越小，而各聚類間的分散度越大。本文用表示聚類間的離散度，用示聚類內的離散度。

所以，我們可以用二者的一個比值衡量聚類效果的好壞，這個比值越大說明此時的聚類效果最優。再將這個最大值取反函數，即可得到第T個幀差處可以取得該最大值，即表示此處可以取得最優聚類數。

4　實驗結果與分析

本文在Intel i3，2.13GHz CPU，6GB內存，Windows 7（64位）實驗環境下和MATLAB平臺進行該算法的實現，用來檢驗該算法的有效性。本文選取動畫、電影、音樂MV、新聞幾種不同類別的視頻片段，實驗中使用的視頻長度從幾百到幾千幀不等，按照本文的方法進行了關鍵幀的提取實驗。

目前，對于視頻關鍵幀的提取效果還沒有統一性的指標來進行判定，所以，本文依照查全率和查準率這兩個參數來檢驗視頻關鍵幀的提取效果。其中，查全率和查準率的定義如下所示：

查全率=正確檢測到的幀數/（正確檢測到的幀數+漏檢幀數）

查準率=正確檢測到的幀數/（正確檢測到的幀數+誤檢幀數）

本文通過按照傳統的顏色直方圖在設定閾值為0.8的情況下，與本文提出的算法進行對比實驗，通過查全率和查準率這兩個指標進行對比，實驗結果如表1所示。

表1　查全率和查準率比較

從表格中可以發現，對于不同類型的視頻片段，本文所使用的方法更能夠準確地提取關鍵幀，而顏色直方圖的方法還存在相對較大的誤差，本文的方法在查全率和查準率這兩個指標上也明顯高于顏色直方圖的方法。雖然，關鍵幀的提取效果會受到視頻類型和內容變化的影響，視頻內容變化激烈的提取的關鍵幀相對就多，視頻內容變化平緩的相對就少，但是，對于實驗結果來看，本文的方法在一定程度上，對聚類算法的關鍵幀提取能夠起到一定的改進作用，更能實現對視頻內容的完整描述。本文選取實驗中包含4390幀的影視劇片段，作為參考對象，運用本文的方法提取出的一些關鍵幀來說明該算法提取出的關鍵幀是否具有代表性，部分關鍵幀如圖（2）所示：

圖2　兩種方法視頻各關鍵幀提取比較

從圖2（a）中提取出的關鍵幀中可以看出視頻的一系列變化過程，2位自行車車手在比賽，首先藍色衣服的車手在后面。之后，藍衣車手一步步逼近騎行在前面的黑衣車手，直至反超黑衣車手。從本文的算法中可以明確地看出藍衣車手的一系列超車過程。但是，運用預設閾值為0.8的K-means算法對該段視頻進行關鍵幀提取時，整段過程就提取了兩幀，并沒有完整的描述整個超車的過程。

從本文的算法提取的關鍵幀中，可以準確地反映出兩位車的比賽過程。而運用傳統預設的閾值來處理時，關鍵幀提取的效果并不好，只有兩幀。從實驗結果中，不難發現本文所提出的基于聚類算法的關鍵幀提取的改進方法，具有較高的查全率以及查準率，能提取出較為準確的關鍵幀來描述視頻的內容。

5　結語

本文針對基于聚類算法的關鍵幀提取方法進行有效的改進。針對K-means聚類算法中，聚類中心數目和聚類閾值無法確定的問題提出改進方法。通過視頻中各個圖像幀之間的幀差，自適應地得到該視頻的閾值。并通過實驗論證，本算法有效地將原本算法中存在的不足進行了改進，避免了原本聚類算法中，閾值設定不合理而造成的關鍵幀提取效果不理想的問題。但是，本文算法的時間復雜度過高，可以在以后的研究中，在針對時間復雜度的問題上進行改進。

K-means Clustering Algorithm；Key Frame Extraction；Adaptive Threshold

［1］方勇，戚飛虎.一種新的視頻鏡頭邊界檢測及關鍵幀提取方法［J］.華東理工大學學報∶自然科學版，2004（S1）∶18-23.

［2］Wolf W.Key Frame Selection by Motion Analysis［C］.Proc.IEEE Int Conf.On Acoustics，Speech，and Signal Processing，ICASSP，Ailanta.1996，2∶1228-1231.

［3］楊華芬，鄭歡鳴.基于內容的視頻關鍵幀提取技術研究［D］.福建電腦，2010，05∶49-51

［4］朱映映，周洞汝.一種從壓縮視頻流中提取關鍵幀的方法［D］.計算機工程與應用，2003，18∶13-14

［5］劉華詠，郝會芬，李濤.基于視頻聚類的關鍵幀提取算法［D］.物聯網技術，2014，08∶59-61

［6］Michel Lantagne，Marc Parizeau，Robert Bergevin.VIP∶Vision Tool for Comparing Images of People［DB/OL］.http∶∥vision.gel.ulaval. ca/～lantagne/LantagneVI2003.pdf，2007-11-26.

［7］王瑋，黃非非，李見為，馮海亮.使用多尺度LBP特征描述與人臉識別［D］.光學精密工程，2008，04（16）∶697-704.

Research on Video Key Frame Extraction by K-means Clustering Algorithm

SI Ruo-yan，ZHANG Ming
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

The key frame is a key technology of video processing.People can get information of the video effectively，through extracting key frame of video.It can improve the accuracy and efficiency of people to retrieve information from video library.K-means clustering algorithm is a key method of video key frame extraction.However，setting unreasonable clustering threshold can lead the consequence of key frame extraction to be unsatisfactory.Thus，puts forward an adaptive threshold method to solve above problems，and the experimental results show the effectiveness of the proposed method.

1007-1423（2016）20-0059-05

10.3969/j.issn.1007-1423.2016.20.012

司若妍（1991-），女，江蘇南京人，碩士研究生，研究方向為模式識別與圖像處理技術與開發

張明（1957-），男，博士，教授，研究方向為多媒體信息處理、分布式多媒體技術、多媒體數據庫、視覺信息檢索與分析、網絡信息安全、人工智能、航運信息化技術等

2016－05－04

2016－07－13