基于吞噬聚類的關(guān)鍵幀提取新算法

吳開興，沈志佳

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

1 關(guān)鍵幀提取技術(shù)

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

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

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

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

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

3）基于運(yùn)動的方法[5-6]

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

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

基于聚類的方法通過將鏡頭中相似的視頻幀聚成相同的類，然后提取不同類中距離聚類中心最近的視頻幀作為關(guān)鍵幀。基于聚類的方法能夠很好地表達(dá)視頻中內(nèi)容的變化，是目前比較主流的關(guān)鍵幀提取算法。文獻(xiàn)[7]中假設(shè)，越重要的內(nèi)容需要的視頻幀數(shù)越多，并且提出了一種基于統(tǒng)計模型的無監(jiān)督聚類關(guān)鍵幀提取方法。文獻(xiàn)[8]在模糊C均值聚類的基礎(chǔ)上，加入了特征權(quán)重，使關(guān)鍵幀提取更準(zhǔn)確。文獻(xiàn)[9]利用蟻堆算法對鏡頭幀的顏色和邊緣進(jìn)行初始聚類，并利用凝聚算法優(yōu)化聚類，提取距離聚類中心最近的幀為關(guān)鍵幀。

2 基于吞噬聚類的關(guān)鍵幀提取算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：rs1為吞噬主體新的吞噬半徑；ρ為標(biāo)準(zhǔn)聚類密度，即當(dāng)吞噬體的聚類密度大于ρ時，吞噬半徑將擴(kuò)展，吞噬體的吞噬能力進(jìn)一步加強(qiáng)。

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與討論

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

圖1 鏡頭關(guān)鍵幀序列（截圖）

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

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

圖2 演講鏡頭關(guān)鍵幀

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

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

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

表1 各算法查準(zhǔn)率對比表

表2 各算法查全率對比表

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

4 小結(jié)

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

：

[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ìn)的視頻關(guān)鍵幀提取算法研究[J].計算機(jī)科學(xué)，2012（8）：300-303.

[4]柴饒軍，馬彩文.圖像序列中目標(biāo)關(guān)鍵幀快速搜索算法[J].光子學(xué)報，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]顧家玉，覃團(tuán)發(fā)，陳慧婷.一種基于MPEG-7顏色特征和塊運(yùn)動信息的關(guān)鍵幀提取方法[J].廣西大學(xué)學(xué)報：自然科學(xué)版，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]張建明，劉海燕，孫淑敏.改進(jìn)的蟻群算法與凝聚相結(jié)合的關(guān)鍵幀提取[J].計算機(jī)工程與應(yīng)用，2013（3）：222-225.

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