基于視頻聚類的關鍵幀提取算法

引言

隨著互聯(lián)網(wǎng)和多媒體技術的飛速發(fā)展，形象生動的數(shù)字視頻已經(jīng)逐漸取代單調(diào)的文本信息，成為了人們網(wǎng)絡生活中傳播信息的重要方式之一。面對互聯(lián)網(wǎng)上大量的視頻，能否在較短的時間內(nèi)找到需要的視頻片段，已經(jīng)成為了人們越來越關注的問題。在視頻幀序列中，包含視頻重要內(nèi)容的幀可以簡單有效地概括視頻的主要內(nèi)容，稱為視頻的關鍵幀。關鍵幀的提取技術在基于內(nèi)容的視頻檢索中有著舉足輕重的地位。在實際應用中，關鍵幀的提取技術可以分為以下4大類：

基于運動分析的關鍵幀提取技術。運動分析一般是基于流光運算的，通過分析和計算光流得出視頻序列的運動量。然后比較運動量的值，并選取局部最小值處的幀為關鍵幀。這種方法提取關鍵幀的最大優(yōu)點是:針對不同結構的鏡頭,可以根據(jù)實際情況提取數(shù)量合適的關鍵幀。但這種方法計算復雜，時間開銷大，而且由局部最小值得到的關鍵幀不一定能準確描述視頻內(nèi)容。

基于鏡頭邊界的關鍵幀提取技術。這種方法首先將視頻分割成若干個鏡頭，然后在每個鏡頭內(nèi)部分別提取第一幀、中間幀和最后一幀作為關鍵幀。這種方法容易設計，計算簡單，適合視頻內(nèi)容簡單或場景固定的情況，但當鏡頭變換頻繁且變換方式多樣時，有可能導致提取的關鍵幀不能準確地描述視頻的內(nèi)容。

基于視覺內(nèi)容的關鍵幀提取技術。該方法根據(jù)每一幀圖像的形狀、紋理、顏色等視頻信息的改變來提取關鍵幀。這種方法可以根據(jù)視頻內(nèi)容變化的顯著程度靈活的確定要選取的關鍵幀的數(shù)目，但缺點是：當鏡頭變化頻繁時容易導致選取的關鍵幀過多，造成信息冗余。

基于聚類分析的關鍵幀提取技術。該方法充分考慮了鏡頭內(nèi)以及鏡頭間的相關性，依據(jù)幀圖像間相似度的大小，將視頻幀序列進行聚類，然后依次從每類中選取一幀作為關鍵幀。大多數(shù)情況下，基于聚類分析提取關鍵幀能準確的描述視頻主要的內(nèi)容。但該方法最大的不足之處在于：需要在聚類前提前設定好聚類的數(shù)目和聚類中心。在視頻內(nèi)容不確定的的情況下，提前設定聚類的數(shù)目和中心是十分困難的，且運算時間較長，這一缺陷極大的制約了這類方法的進一步發(fā)展。

層次聚類算法無需提前設定聚類中心和聚類數(shù)目，但該算法收斂速度相對較慢。K-means算法設計簡單、容易實現(xiàn),且收斂速度較快，但其對初始聚類中心較敏感，容易陷入局部最優(yōu)解［10］。針對這兩種算法在提取關鍵幀過程中出現(xiàn)的不足，本文提出一種改進的基于視頻聚類的關鍵幀提取算法。該算法過程為：首先，依次提取幀圖像的信息熵，并使用歐式距離公式計算幀間相似度；然后，運用層次聚類算法對所有幀進行聚類，得到初始聚類結果；運用K-means算法優(yōu)化并完成最終聚類；最后，將距離聚類中心最近的幀作為關鍵幀輸出。

1基于視頻聚類的關鍵幀提取過程

1.1特征提取

1948年，信息論創(chuàng)始人shannon首次提出信息熵的概念,用以描述隨機變量X所包含的平均信息量。X的信息熵定義為:

其中，X={xiIi=1，2，3，???,"}表示隨機變量；(x)表示Xi出現(xiàn)的概率。

對于一段包含N幀的視頻序列：=(/1"???,￡},假設

該視頻序列的每一幀均為256級的灰度圖像。本文首先將圖 像分割為B塊，每塊圖像的信息熵定義為:

其中,P 3,)表示圖像中灰度值為i的像素出現(xiàn)的概率。圖像 的特征向量定義為：

其中,H表示第j塊圖像的信息熵。

1.2計算幀間相似度

我們用歐式距離表示幀間的相似度。歐式距離越小，幀 間相似度就越高。幀間的歐式距離定義為：

其中，N為視頻中幀的數(shù)量,F?和Fb分別表示圖像a和圖像b 的特征向量，d (Fa, Fb)為幀間的相似度。

1.3利用層次聚類得到初始聚類結果

本文使用凝聚型的層次聚類算法對視頻序列進行初始聚 類，其主要思想是：先將每個待聚類的樣本做為一類，然后 依據(jù)幀間相似度的大小，合并相似的類使之成為一類，直到 滿足終止條件。

假設視頻序列有N個待聚類的樣本，基本步驟為：

確定終止條件。設要提取的關鍵幀的數(shù)量為計 算特征向量的均值M和方差V:

其中,D={di| i=1, 2, 3,…,N}表示距離向量。本文中,K 的值與幀間距離d(F”Fb)4V的幀的數(shù)量相等。

初始化：首先，將每個樣本單獨歸為一類，依次計 算每兩類之間的相似度；

尋找距離最近的兩個類，并把他們歸為一類；

重新計算新生成的這個類與各個舊類之間的相似度；

重復3和4,直到聚類數(shù)目為K,結束。

1.4利用K-means聚類算法優(yōu)化聚類結果

本文將層次聚類產(chǎn)生的結果作為K-means算法的輸入， 將層次聚類產(chǎn)生的每一類的中心，作為K-means算法的初始 聚類中心，這樣可以避免隨機產(chǎn)生初始聚類中心對K-means 算法的聚類結果產(chǎn)生的影響。由于層次聚類后，樣本已經(jīng)基 本聚類成功，故K-means算法迭代的次數(shù)將大大減少。

具體步驟如下：

計算層次聚類產(chǎn)生的聚類的中心，即每個聚類對象 的平均值；

計算每一幀與聚類中心的距離，并根據(jù)最小距離準 則對相應幀重新進行分類;

重新計算每個類的聚類中心；

重復2和3,直到每個聚類中的對象不再發(fā)生變化；

( 5)計算每一類的聚類中心，將距離聚類中心最近的幀 作為關鍵幀輸出。

本文將每個視頻幀分為B塊并提取每塊的信息熵，然后 組成特征向量，充分考慮了每個視頻幀的特征。同時，該算法 利用了層次聚類能在短時間內(nèi)得到聚類結果的優(yōu)勢，大大提 高了工作效率。此外，本文將已經(jīng)初步分類成功的層次聚類的 結果作為K-means算法的輸入，避免了人為定義初始聚類中心 對K-means聚類結果的影響。

2實驗結果與分析

本文在 Intel i7, 2.4 GHz CPU, 4 GB 內(nèi)存，Windows 8 ( 64位)環(huán)境下和Matlab平臺上實現(xiàn)該算法，以檢驗該算法的 有效性。本文使用的實驗視頻長度從幾百幀到幾千幀，類型豐 富全面，包括廣告、電影、新聞、卡通等。同時，人工對數(shù)據(jù) 集進行關鍵幀的識別統(tǒng)計作為算法的比較標準。

本文采用查全率和準確率這兩個參量來檢驗算法的有效 性［11］。其中，查全率和準確率的定義如下公式所示：

查全率=正確檢測數(shù)/ (正確檢測數(shù)+漏檢數(shù))

準確率=正確檢測數(shù)/(正確檢測數(shù)+誤檢數(shù))

由于傳統(tǒng)的直方圖法［12］廣泛應用于關鍵幀的提取，且該 方法具有較好的檢測性能和較快的運算速度，故本文采用其 作為對比實驗。提取關鍵幀的結果如表1所列。

由表1可知，對于廣告、電影、新聞、卡通等不同類型 的視頻片段，使用本文的算法提取關鍵幀具有較大優(yōu)勢。例如， 在隨機選取的卡通類視頻中，本文提出的算法查全率為86.9% 和準確率為85.7%,比直方圖法的查全率和準確率高很多。由 此可見，本文提出的算法能很好的描述視頻的主要內(nèi)容，且 查全率和準確率較高。本文選取了一段包含1 348幀的卡通視 頻序列，以驗證該算法提取的關鍵幀具有代表性，部分關鍵 幀如圖1所示。

圖1列舉了從視頻序列中提取的部分關鍵幀。其中，前10個關鍵幀內(nèi)容變換較大，準確反映了汽車在空曠的平原上靜止、加速、超車等一系列過程，因此提取為關鍵幀。后8個關鍵幀內(nèi)容變化不大，關鍵幀序列特寫了黑色轎車超過紅色轎車的過程。從以上實驗結果可以看出，本文提出的基于視頻聚類的關鍵幀提取算法，有較高的查全率和準確率，提取的關鍵幀能較為準確的描述視頻的主要內(nèi)容。

3結語

本文提出了基于視頻聚類的關鍵幀提取算法，有效地改進了傳統(tǒng)聚類算法在提取關鍵幀過程中出現(xiàn)的不足。該算法將層次聚類和K-means算法的優(yōu)勢充分結合，并揚長避短，使用K-means算法對層次聚類的結果再次優(yōu)化，最終得到了視頻的關鍵幀。從大量的實驗數(shù)據(jù)可以看出，該算法有很好的適應性，可以針對不同類型的視頻提取適當數(shù)目的關鍵幀，且提取關鍵幀的查全率和準確率高于傳統(tǒng)方法。

20211221_61c1dea1a3293__基于視頻聚類的關鍵幀提取算法