引言

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

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

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

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

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

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

1基于視頻聚類的關(guān)鍵幀提取過(guò)程

1.1特征提取

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

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

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

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

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

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

1.2計(jì)算幀間相似度

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

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

1.3利用層次聚類得到初始聚類結(jié)果

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

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

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

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

初始化：首先，將每個(gè)樣本單獨(dú)歸為一類，依次計(jì) 算每?jī)深愔g的相似度；

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

重新計(jì)算新生成的這個(gè)類與各個(gè)舊類之間的相似度；

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

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

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

具體步驟如下：

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

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

重新計(jì)算每個(gè)類的聚類中心；

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

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

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

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

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

本文采用查全率和準(zhǔn)確率這兩個(gè)參量來(lái)檢驗(yàn)算法的有效 性［11］。其中，查全率和準(zhǔn)確率的定義如下公式所示：

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

準(zhǔn)確率=正確檢測(cè)數(shù)/(正確檢測(cè)數(shù)+誤檢數(shù))

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

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

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

3結(jié)語(yǔ)

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

20211221_61c1dea1a3293__基于視頻聚類的關(guān)鍵幀提取算法