三維蟻堆算法在視頻關(guān)鍵幀提取中的應(yīng)用

吳開興, 沈志佳

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

隨著計算機(jī)的普及和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，越來越多的視頻數(shù)據(jù)不斷涌現(xiàn)。如何對這些數(shù)據(jù)進(jìn)行高效的存儲、瀏覽和檢索便顯得十分重要[1-2]。在基于內(nèi)容的視頻檢索中，關(guān)鍵幀提取是最關(guān)鍵的技術(shù)之一。目前關(guān)鍵幀提取技術(shù)方法很多[3-10]，但多數(shù)存在提取效果不理想或算法復(fù)雜等問題。本文主要是在傳統(tǒng)蟻堆算法的基礎(chǔ)上，提出了一種改進(jìn)的三維蟻堆算法，將傳統(tǒng)算法的螞蟻運(yùn)動路徑擴(kuò)展到三維平面。則三維平面與三維視頻幀特征向量的幀數(shù)一致，從而提高了聚類的查全率和查準(zhǔn)率。

1傳統(tǒng)的蟻堆算法

螞蟻是一種社會性昆蟲，具有自組織、自適應(yīng)、分布式、相互通信、相互合作等特點(diǎn)。模擬螞蟻的這些特性，我們可以解決許多很復(fù)雜的問題。Deneubourg等人從螞蟻堆積尸體中受到啟發(fā)，提出了一種基本模型BM(Basic Model)。Lumer和Faieta在BM的基礎(chǔ)上進(jìn)行了改進(jìn)，增加了數(shù)據(jù)對象的相似性表達(dá)式，提出了用于數(shù)據(jù)聚類的LF算法。LF算法的基本思想如下：將N個數(shù)據(jù)對象隨機(jī)的投入到M×M的網(wǎng)格中，將A只螞蟻也隨機(jī)的投入到該網(wǎng)格中，螞蟻沿著網(wǎng)格隨機(jī)移動，螞蟻遇到數(shù)據(jù)對象后，根據(jù)該數(shù)據(jù)對象與螞蟻可視范圍內(nèi)數(shù)據(jù)對象的相似度，以一定的概率負(fù)載數(shù)據(jù)對象，負(fù)載數(shù)據(jù)對象的螞蟻沿著網(wǎng)格隨機(jī)移動，當(dāng)遇到空網(wǎng)格后，根據(jù)負(fù)載與可視范圍內(nèi)數(shù)據(jù)對象的相似度，以一定的概率卸載負(fù)載，然后未負(fù)載的螞蟻繼續(xù)隨機(jī)移動。

設(shè)螞蟻的可視范圍為r，則相似度計算函數(shù)為如下公式[8]：

(1)

d(oi,oj)為數(shù)據(jù)對象oi與oj的距離，通常用歐式距離，a為相似性參數(shù)，neigh(r)表示以r為半徑的圓形區(qū)域。

Pp和Pd分別為螞蟻拾起對象和放下對象的概率，計算如公式(2)(3)[8]所示。

(2)

(3)

2 改進(jìn)的蟻堆算法在關(guān)鍵幀提取中的應(yīng)用

傳統(tǒng)的蟻堆算法，是基于二維平面的，數(shù)據(jù)對象是以隨機(jī)的方式投入到二維網(wǎng)格上。本文在傳統(tǒng)蟻堆算法的基礎(chǔ)上，將其擴(kuò)展到三維平面，數(shù)據(jù)對象以其在H-S-V空間中的三維特征向量為坐標(biāo)，分布在三維立體網(wǎng)格上。這樣，數(shù)據(jù)對象之間的歐式距離，便是其在三維空間中的直線距離，距離近的數(shù)據(jù)對象聚集在一起，因此，數(shù)據(jù)對象已在一定程度完成了初始聚類。

首先進(jìn)行視頻幀特征向量的提取。視頻幀的每個像素均可以在H-S-V空間中表現(xiàn)出來，其中H的取值范圍為[0,360]，S和V的取值范圍均為[0,1]，為了使視頻幀的距離計算更加有效，將S和V的取值乘以360，使S和V的取值范圍也擴(kuò)展到[0,360]，這樣就得到了關(guān)于每個象素的三維特征向量。計算第n幀整幅圖像的平均特征向量Xn，兩幀之間的歐式距離d(oi,oj)便可由公式(4)表示：

(4)

其中xnk為特征向量Xn的k維分量。

將每一個視頻幀映射到三維的歐式空間，這樣，兩幀之間的歐式距離便可由三維空間中兩點(diǎn)的直線距離表示。

一段鏡頭便可由三維空間中一系列的散點(diǎn)表示，如下圖1。

之后，我們通過對傳統(tǒng)蟻堆算法進(jìn)行改進(jìn)，使其適應(yīng)于H-S-V三維空間。具體的改進(jìn)方面如下，

(1)將數(shù)據(jù)對象按照其在H-S-V中的坐標(biāo)放在三維數(shù)據(jù)空間中，由于數(shù)據(jù)對象在三維空間中的實(shí)際距離，即是其歐式距離，從某種程度說，數(shù)據(jù)對象，已經(jīng)完成了初始聚類。

(2)由于數(shù)據(jù)對象在三維空間中已經(jīng)有一定的聚類性質(zhì)，初始放置螞蟻時，將螞蟻均勻的分布在三維空間中，并且使每一只螞蟻，在一個已有數(shù)據(jù)對象的網(wǎng)格內(nèi)，避免螞蟻對于負(fù)載的饑餓。

(3)數(shù)據(jù)對象周圍的數(shù)據(jù)對象有很大幾率屬于同一聚類，因此，螞蟻放下負(fù)載后，自動尋找與此數(shù)據(jù)對象最近的負(fù)載點(diǎn)，減少螞蟻的無意義運(yùn)動。

(4)螞蟻拾起負(fù)載后，有很大概率，在其負(fù)載周圍再次放下負(fù)載，因此，螞蟻以負(fù)載初始位置為圓點(diǎn)，在半徑r1為1的球面內(nèi)運(yùn)動，如果在此球面內(nèi)不能放下負(fù)載，則半徑r1+1，直到螞蟻放下負(fù)載為止。此改進(jìn)點(diǎn)的目的是使螞蟻在較短的步數(shù)內(nèi)，在正確位置放下負(fù)載，這也是因為數(shù)據(jù)對象之間的歐式距離就是其實(shí)際距離，歐式距離近的數(shù)據(jù)對象已經(jīng)聚集在一起的緣故。

(5)如果螞蟻欲放下負(fù)載的位置已有其它的數(shù)據(jù)對象，則在此位置的鄰域內(nèi)求其放下對象的概率。如果所有的領(lǐng)域都不能放下，則螞蟻回到原先的運(yùn)動路徑，繼續(xù)在以r1為半徑的球面內(nèi)移動。

(6)定義數(shù)據(jù)對象的優(yōu)先級，如果，螞蟻經(jīng)過較少的步驟，即放下數(shù)據(jù)對象，說明數(shù)據(jù)對象已經(jīng)在其正確位置，則此數(shù)據(jù)對象需要再次移動的概率很低，我們就賦予此數(shù)據(jù)對象較低的優(yōu)先級，否則賦予較高的優(yōu)先級，當(dāng)條件一樣時，即步驟3中存在多個最近負(fù)載點(diǎn)時，螞蟻優(yōu)先負(fù)載優(yōu)先級較高的負(fù)載點(diǎn)，如果優(yōu)先級一致則隨機(jī)選取。

(7)參數(shù)a的確定非常依賴使用者的經(jīng)驗，使算法缺少普適性。算法中a初始值設(shè)為0.1，如果迭代時，螞蟻放下對象失敗次數(shù)與迭代次數(shù)的比值大于0.99，則a增加0.01，否則減少0.01。

(8)當(dāng)蟻堆算法迭代到一定次數(shù)t后，數(shù)據(jù)對象已完成了進(jìn)一步的聚類，按照文獻(xiàn)[11]所述方法，再一次提取每一幀的H-S-V顏色直方圖。之后以每一幀中H-S-V顏色直方圖的72維特征向量為標(biāo)準(zhǔn)，以蟻堆算法提取的聚類中心和聚類個數(shù)作為參考，通過K-均值聚類算法完成最終的聚類。則最終聚類中，距離每一個最終聚類中心距離最小的維特征向量所代表的視頻幀，即為我們所需要的關(guān)鍵幀。最終聚類選取72維顏色直方圖作為特征向量是因為，采用72維特征向量，比前述三維特征向量在計算歐式距離時更精確，最終聚類的結(jié)果也會更準(zhǔn)確。

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

利用三維蟻堆算法提取出的基于前圖1所代表鏡頭的關(guān)鍵幀如下圖2所示。

可見提取出的關(guān)鍵幀分別代表了停車場某一個車位，汽車的動態(tài)變化，提取出的關(guān)鍵幀具有代表性。

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

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

為了驗證算法的有效性，本文采用了120個不同的鏡頭來對算法進(jìn)行分析。具體的實(shí)驗結(jié)果如下圖4、圖5所示。

可見，無論是在體育類，新聞類，動畫類，電影類的視頻中，本文算法的查全率和查準(zhǔn)率，都優(yōu)于其它的傳統(tǒng)算法。

4 結(jié)論

(1)本算法能夠根據(jù)鏡頭內(nèi)容的復(fù)雜程度，自適應(yīng)地提取出不同數(shù)量，且具有代表性的關(guān)鍵幀。

(2)在體育類、新聞類、動畫類、電影類的視頻中，本文算法的查全率和查準(zhǔn)率都優(yōu)于傳統(tǒng)的直方圖法，運(yùn)動分析法和二維蟻堆算法。

參考文獻(xiàn)：

[1] TANIGUCHI Y. An intuitive and efficient access interface to real- time incoming video based on automatic indexing [C]// Proc of ACM Multimedia. San Francisco，1995: 25-33.

[2] 汪 勤. 基于視頻圖像處理的無人值守變電站在線檢測的研究[J]. 四川理工學(xué)院學(xué)報: 自然科學(xué)版, 2013, 26(3): 91-94.

[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 of IEEE International Conference on Acoustics Speech and Signal Processing. Atlanta, 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 MAN, JIANG PENG. A feature weighed clustering based key-frames Extraction method[C]. // Proceedings of the 2009 International Forum on Information Technology and Applications. Piscataway，2009: 69-72.

[9] 張建明, 劉海燕, 孫淑敏. 改進(jìn)的蟻群算法與凝聚相結(jié)合的關(guān)鍵幀提取[J]. 計算機(jī)工程與應(yīng)用, 2013(3): 222-226.

[10] 賈存鋒, 朱加雷, 焦向東, 等. GMAW熔滴過渡高速攝像系統(tǒng)與熔滴邊緣提取[J]. 河北科技大學(xué)學(xué)報, 2013, 34(4): 316-319.

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