司若妍，張明（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

基于K-means聚類算法的視頻關(guān)鍵幀提取的研究

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

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

K-means聚類算法；關(guān)鍵幀提取；自適應(yīng)閾值

0　引言

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

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

1　主要的關(guān)鍵幀提取方法

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

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

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

2　K-means聚類算法

K-means聚類算法是聚類分析中運(yùn)用最為廣泛的算法之一。無論在數(shù)據(jù)處理或是圖像、視頻處理中，都運(yùn)用地相當(dāng)廣泛。

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

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

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

2.1特征選取

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

（1）顏色特征選取

HSV顏色模型是色調(diào)（H，Hue）、飽和度（S，Saturation）、亮度（V，Value）三個(gè)英文單詞的首字母縮寫，由A.R.Smith在1978年創(chuàng)建的一種顏色空間，與傳統(tǒng)的RGB顏色空間模型相比，HSV顏色模型因?yàn)槠渚邆溆芯€性伸縮性的性質(zhì)，所以更加符合人類視覺的特點(diǎn)，與人類的視覺感知更接近，因此人們更傾向于用HSV顏色模型來描述顏色。

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

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

（2）紋理特征

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

本文利用LBP［7］（局部二值模式）紋理特征描述算子來對幀圖像的紋理特征進(jìn)行處理。因?yàn)槠渌哂械幕叶炔蛔兒托D(zhuǎn)不變的性質(zhì)很巧妙地避免了由光照顯著改變而引起的實(shí)驗(yàn)結(jié)果的誤差。

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

圖1　基本的LBP算子計(jì)算示意圖

用公式可以表示為：

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

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

其中，u表示循環(huán)二進(jìn)制數(shù)中0-1躍變的次數(shù)。

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

2.2計(jì)算幀間的相似度

因?yàn)楸疚氖抢妙伾卣骱图y理特征共同來對幀圖像進(jìn)行描述，所以，兩幀之間的相似度可以用二者差值來表示。在本文中，首先計(jì)算兩幀圖像之間的顏色直方圖的差值，再計(jì)算兩幀圖像之間的LBP紋理算子的差值，再將這兩個(gè)差值進(jìn)行加權(quán)計(jì)算，最后得到的總差值即可表示為兩幀之間的相似度，差值越大，說明兩幀之間相似度越大，反之，相似度越小。

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

3　自適應(yīng)閾值關(guān)鍵幀提取

在進(jìn)行聚類算法的關(guān)鍵幀提取過程中，因?yàn)橐S機(jī)選取聚類中心和人為設(shè)定聚類閾值，而使得算法計(jì)算量過大，用時(shí)過多，導(dǎo)致算法效率不高，所以為了提高K-means算法的提取關(guān)鍵幀效率，本文從聚類中心和聚類閾值這兩個(gè)方面上進(jìn)行研究，改進(jìn)一種自適應(yīng)閾值的聚類計(jì)算方法。

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

（2）根據(jù)幀差序列，設(shè)定一個(gè)參數(shù)T，令

其中，令M=n-c-1

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

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

（4）算法停止，得到初始聚類的劃分，和初始聚類個(gè)數(shù)。

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

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

4　實(shí)驗(yàn)結(jié)果與分析

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

目前，對于視頻關(guān)鍵幀的提取效果還沒有統(tǒng)一性的指標(biāo)來進(jìn)行判定，所以，本文依照查全率和查準(zhǔn)率這兩個(gè)參數(shù)來檢驗(yàn)視頻關(guān)鍵幀的提取效果。其中，查全率和查準(zhǔn)率的定義如下所示：

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

查準(zhǔn)率=正確檢測到的幀數(shù)/（正確檢測到的幀數(shù)+誤檢幀數(shù)）

本文通過按照傳統(tǒng)的顏色直方圖在設(shè)定閾值為0.8的情況下，與本文提出的算法進(jìn)行對比實(shí)驗(yàn)，通過查全率和查準(zhǔn)率這兩個(gè)指標(biāo)進(jìn)行對比，實(shí)驗(yàn)結(jié)果如表1所示。

表1　查全率和查準(zhǔn)率比較

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

圖2　兩種方法視頻各關(guān)鍵幀提取比較

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

從本文的算法提取的關(guān)鍵幀中，可以準(zhǔn)確地反映出兩位車的比賽過程。而運(yùn)用傳統(tǒng)預(yù)設(shè)的閾值來處理時(shí)，關(guān)鍵幀提取的效果并不好，只有兩幀。從實(shí)驗(yàn)結(jié)果中，不難發(fā)現(xiàn)本文所提出的基于聚類算法的關(guān)鍵幀提取的改進(jìn)方法，具有較高的查全率以及查準(zhǔn)率，能提取出較為準(zhǔn)確的關(guān)鍵幀來描述視頻的內(nèi)容。

5　結(jié)語

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

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

［1］方勇，戚飛虎.一種新的視頻鏡頭邊界檢測及關(guān)鍵幀提取方法［J］.華東理工大學(xué)學(xué)報(bào)∶自然科學(xué)版，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］楊華芬，鄭歡鳴.基于內(nèi)容的視頻關(guān)鍵幀提取技術(shù)研究［D］.福建電腦，2010，05∶49-51

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

［5］劉華詠，郝會芬，李濤.基于視頻聚類的關(guān)鍵幀提取算法［D］.物聯(lián)網(wǎng)技術(shù)，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］.光學(xué)精密工程，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-），女，江蘇南京人，碩士研究生，研究方向?yàn)槟Ｊ阶R別與圖像處理技術(shù)與開發(fā)

張明（1957-），男，博士，教授，研究方向?yàn)槎嗝襟w信息處理、分布式多媒體技術(shù)、多媒體數(shù)據(jù)庫、視覺信息檢索與分析、網(wǎng)絡(luò)信息安全、人工智能、航運(yùn)信息化技術(shù)等

2016－05－04

2016－07－13