基于吞噬聚類的關鍵幀提取新算法

吳開興，沈志佳

（河北工程大學 信息與電氣工程學院，河北 邯鄲 056038）

1 關鍵幀提取技術

關鍵幀提取是基于內(nèi)容視頻檢索中最重要的技術之一。關鍵幀是一個鏡頭的某一幀或某幾幀，它們就像一本書中的目錄頁，能夠反映鏡頭的梗概信息。通過關鍵幀對視頻進行索引，能夠極大地減少視頻檢索的數(shù)據(jù)量，對于視頻檢索十分重要。目前關鍵幀提取技術主要可以分為以下4大類。

1）基于鏡頭邊界的方法[1-2]

這種方法主要是通過固定選取鏡頭的首幀、中間幀、尾幀等來提取關鍵幀。此種方法簡單易行，但是它提取關鍵幀的位置和數(shù)目都是固定的。如果鏡頭大小不一，或物體和攝像頭處于高速運動中，此種關鍵幀提取方法的效果十分不理想。

2）基于內(nèi)容的方法[3-4]

基于內(nèi)容的方法，主要是通過鏡頭中視頻幀內(nèi)容的變化來提取關鍵幀。它的基本思想是當幀的顏色、紋理、形狀等底層特征具有顯著變化時，便認為其是關鍵幀。這種關鍵幀提取方法具有自適應性，會根據(jù)鏡頭內(nèi)容自適應地在不同位置提取不同數(shù)量的關鍵幀。文獻[3]通過結(jié)合直方圖交集及非均勻分塊加權的直方圖方法，切割視頻鏡頭，之后在HSV顏色空間基礎上，通過計算每幀的圖像熵得到關鍵幀。文獻[4]通過比較相鄰幀的灰度直方圖，并通過與閾值作比較來提取關鍵幀。但是，如果當鏡頭的內(nèi)容變化較大時，用這種方法提取出的關鍵幀往往數(shù)目過多，算法的冗余性較大。

3）基于運動的方法[5-6]

基于運動的方法主要是以物體或攝像機運動的幅度來提取關鍵幀，當物體或攝像機的運動達到局部最小值時，便定義此處的幀為關鍵幀。通過這種方法能夠很好地表現(xiàn)鏡頭內(nèi)全局性的內(nèi)容變化，具有自適應性，并且與肉眼判斷關鍵幀的準則一致。文獻[5]中Worf提出了一種基于光流分析的關鍵幀提取算法，通過光流計算鏡頭中的運動量，并且在局部運動極小值處獲得關鍵幀，文獻[6]提出一種結(jié)合視頻幀顏色特征和利用圖像分塊計算運動信息的方法來提取關鍵幀。但是由于這些算法復雜度較高，限制了它們的應用。

4）基于聚類的方法[7-9]

基于聚類的方法通過將鏡頭中相似的視頻幀聚成相同的類，然后提取不同類中距離聚類中心最近的視頻幀作為關鍵幀?；诰垲惖姆椒軌蚝芎玫乇磉_視頻中內(nèi)容的變化，是目前比較主流的關鍵幀提取算法。文獻[7]中假設，越重要的內(nèi)容需要的視頻幀數(shù)越多，并且提出了一種基于統(tǒng)計模型的無監(jiān)督聚類關鍵幀提取方法。文獻[8]在模糊C均值聚類的基礎上，加入了特征權重，使關鍵幀提取更準確。文獻[9]利用蟻堆算法對鏡頭幀的顏色和邊緣進行初始聚類，并利用凝聚算法優(yōu)化聚類，提取距離聚類中心最近的幀為關鍵幀。

2 基于吞噬聚類的關鍵幀提取算法

本文借鑒蟻堆聚類算法、DBSCAN聚類算法，以及K-均值聚類算法的思想，提出了一種基于吞噬聚類的關鍵幀提取新算法。

DBSCAN是一種基于密度的算法，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇。但是它在劃分簇時，需要計算與中心點距離為e的其他數(shù)據(jù)對象的個數(shù)，為此，它需要掃描完所有剩余的數(shù)據(jù)對象，算法復雜度較高，而且此算法需要2個初始參數(shù)：半徑e和最小數(shù)據(jù)對象數(shù)目MinPts。這兩個參數(shù)的取值直接影響算法的聚類效果。為此，本文借鑒了蟻堆算法中螞蟻運動的思想，將數(shù)據(jù)對象表現(xiàn)為可以隨機移動的吞噬體，吞噬體通過吞噬其他相近的數(shù)據(jù)對象，在保證其聚類密度沒有減少的情況下，增大吞噬能力。吞噬主體吞噬其他客體概率的計算，也參考了蟻堆算法中螞蟻放下或者拾取數(shù)據(jù)對象的概率公式。而吞噬體吞噬中心的確定，則借鑒了K-均值聚類算法中聚類中心的計算公式。

利用吞噬聚類算法提取鏡頭關鍵幀的步驟如下：

1）提取視頻幀的特征矢量，本文采用文獻[10]中基于HSV顏色直方圖的特征向量提取方法，將色調(diào)空間H分為8份，飽和度空間S分為3份，亮度空間V分為3份，然后根據(jù)人眼對不同特征的感知程度，確定量化級數(shù)，把顏色分量合成一維特征矢量，即

式中：W的取值范圍為[0,71]。通過計算基于W的直方圖，便可得到關于視頻幀的72維特征向量。

2）將所有數(shù)據(jù)對象隨機分布在M×M的二維網(wǎng)格中，每個數(shù)據(jù)對象可以看作一個吞噬體，吞噬體具有吞噬中心和吞噬半徑。其中吞噬中心為數(shù)據(jù)對象的特征向量，初始吞噬半徑設為r。

3）所有吞噬體在二維網(wǎng)格上隨機移動，當吞噬體遇到可以吞噬的客體后，會以一定幾率將客體吞噬。吞噬后，吞噬主體的吞噬中心和吞噬半徑將會隨著吞噬客體而改變。

4）吞噬的機制：吞噬主體吞噬其他客體的概率公式為

式中：d(os,oo)為吞噬主客體間吞噬中心的距離；rs為吞噬主體的吞噬半徑。

d(os,oo)采用歐氏距離，計算公式為

式中：xsi為吞噬主體吞噬中心的第i維分量；xoi為吞噬客體吞噬中心的第i維分量；n為吞噬中心的向量維數(shù)，此處n=72。

吞噬后，新吞噬中心的計算公式為

式中：os1為吞噬主體新的吞噬中心；ks和ko分別為吞噬主客體內(nèi)數(shù)據(jù)對象的個數(shù)。

吞噬后，新的吞噬半徑計算公式為

式中：rs1為吞噬主體新的吞噬半徑；ρ為標準聚類密度，即當吞噬體的聚類密度大于ρ時，吞噬半徑將擴展，吞噬體的吞噬能力進一步加強。

5）當吞噬進行到一定次數(shù)后，如果吞噬聚類效果不理想，依然存在較多吞噬密度小于ρ的吞噬體，則可以遞減標準吞噬密度ρ，按照步驟4）中的公式重新定義吞噬半徑，繼續(xù)進行吞噬。

6）最后所剩余的吞噬體的吞噬中心即為聚類中心，選取與聚類中心距離最近的向量所代表的視頻幀作為關鍵幀。

DBSCAN算法需要初始參數(shù)：半徑e和最小數(shù)據(jù)對象數(shù)目MinPts，而本算法僅僅需要一個標準聚類密度ρ，并且ρ的值會隨著聚類效果的優(yōu)劣而自動改變。

蟻群算法容易出現(xiàn)局部極值問題，即本應該屬于相同聚類的數(shù)據(jù)對象，卻在不同的位置分別聚類，而本算法，則可以簡單地通過吞噬體的互相吞噬，合并相近的聚類。

K-均值算法需要初始的聚類中心和聚類個數(shù)，本算法則會根據(jù)數(shù)據(jù)對象的復雜程度，自動確定聚類中心和聚類個數(shù)，具有自適應性。

3 實驗結(jié)果與討論

利用吞噬聚類算法提取出的某個鏡頭的關鍵幀如圖1所示。

圖1 鏡頭關鍵幀序列（截圖）

可見提取出的關鍵幀代表了某一汽車躲避警察抓捕的全過程，提取出的關鍵幀具有代表意義。

利用本算法提取出的某個演講鏡頭的關鍵幀如圖2所示。

圖2 演講鏡頭關鍵幀

由于該演講鏡頭內(nèi)視頻內(nèi)容變化很少，所以僅提取出了唯一的關鍵幀，由此可見，本算法具有自適應性，能夠根據(jù)鏡頭內(nèi)容的復雜程度，自適應地提取出不同數(shù)量的關鍵幀。

為了驗證算法的有效性，本文采用了120個不同的鏡頭來對算法進行分析，其中體育類型、新聞類型、動畫類型、電影類型各30個，以查全率和查準率來作為算法有效性的衡量標志。

為了對比算法的效果，本文以K-均值聚類算法、DBSCAN算法、蟻堆聚類算法與本文算法在查全率和查準率上作對比，具體的實驗結(jié)果如表1、表2所示。

表1 各算法查準率對比表

表2 各算法查全率對比表

可見，在體育類、新聞類、動畫類、電影類的視頻中，本文算法的查準率均優(yōu)于其他的傳統(tǒng)算法。但是在查全率方面，針對體育類和動畫類視頻，本算法效果略低于蟻群算法。

4 小結(jié)

本文章借鑒了蟻堆聚類算法、DBSCAN聚類算法，以及K-均值聚類算法的思想，提出了一種基于吞噬聚類的關鍵幀提取新算法，與傳統(tǒng)算法作對比，雖然對于體育類視頻和動畫類視頻在查全率方面，本算法略低于蟻堆聚類算法，但是總體來說，本算法的提取效果優(yōu)于其他的聚類算法，具有一定的應用價值。

：

[1]TANIGUCHI Y.An intuitive and efficient access interface to real—time incoming video based on automatic indexing[C]//Proc.3rd ACM International Conference on Multimedia.New York，USA：ACM Press，1995：25-33.

[2]ZHANG Hongjian，WU Jianhua，ZHONG Di，et al.An integrated system for content-based video retrieval and browsing[J].Pattern Recognition，1997，30（4）：643-658.

[3]瞿中，高騰飛，張慶慶.一種改進的視頻關鍵幀提取算法研究[J].計算機科學，2012（8）：300-303.

[4]柴饒軍，馬彩文.圖像序列中目標關鍵幀快速搜索算法[J].光子學報，2004（10）：1233-1235.

[5]WORF W.Key frame selection by motion analysis[C]//Proc.IEEE International Conference on Acoustics,Speech and Signal Processing.Atlanta，USA：IEEE Computer Society，1996：1228-1231.

[6]顧家玉，覃團發(fā)，陳慧婷.一種基于MPEG-7顏色特征和塊運動信息的關鍵幀提取方法[J].廣西大學學報：自然科學版，2010（2）：310-314.

[7]YANG Shuping，LIN Xinggang.Key frame extraction using unsupervised clustering based on a statistical model[J].Tsinghua Science and Technology，2005（2）：169-173.

[8]HUA M，JIANG P.A feature weighed clustering based key-frames extraction method[C]//Proc.the 2009 International Forum on Information Technology and Applications.Piscataway：IEEE Computer Society，2009：69-72.

[9]張建明，劉海燕，孫淑敏.改進的蟻群算法與凝聚相結(jié)合的關鍵幀提取[J].計算機工程與應用，2013（3）：222-225.

[10]王娟，孔兵，賈巧麗，等.基于顏色特征的圖像檢索技術[J].計算機系統(tǒng)應用，2011（7）：160-164.