王華秋+殷志恒

摘 要： 視頻鏡頭分割和關(guān)鍵幀提取是當(dāng)前數(shù)字視頻系統(tǒng)發(fā)展的關(guān)鍵步驟。在AP聚類算法之上做了兩點改進(jìn)：一是在初始相關(guān)系數(shù)矩陣中增加權(quán)重，提高聚類精度；二是自適應(yīng)調(diào)整阻尼系數(shù)，提高收斂速度。先利用顏色信息加權(quán)和相鄰幀間差方法把視頻分割成鏡頭，再利用改進(jìn)的AP聚類算法對鏡頭提取關(guān)鍵幀。實驗結(jié)果表明，所提出的方法有效地解決了關(guān)鍵幀提取方法中耗時高和視覺信息低效的問題。

關(guān)鍵詞： 數(shù)字視頻； 鏡頭分割； 關(guān)鍵幀提?。?AP聚類

中圖分類號：TP391.41 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2016）12-90-05

Abstract： Video shot segmentation and key frame extraction is the critical step in the current digital video system development. In this paper， the AP （affinity propagation） clustering algorithm is improved in the two points： first， the weight is increased in the initial correlation coefficient matrix to improve the clustering accuracy； second， the damping coefficient is adjusted adaptively to improve the convergence rate. Use the weighted color information and adjacent frame difference method to divide the video into shots， and then use the improved AP clustering algorithm to extract the key frames from the shots. The experimental results show that the method proposed can effectively solve the problems of high time consuming and low efficiency of capturing visual information in the key frame extraction methods.

Key words： digital video； shot segmentation； key frame extraction； affinity propagation clustering

0 引言

隨著視頻采集、存儲與分布技術(shù)上的進(jìn)步，教學(xué)視頻在學(xué)生日常生活中的訪問次數(shù)呈現(xiàn)指數(shù)級增長。如何幫助學(xué)生有效地瀏覽及檢索其感興趣的視頻，將具有重要的理論意義和實用價值。作為基于內(nèi)容的視頻檢索[1-2]基礎(chǔ)，如何把視頻數(shù)據(jù)組織成為更加緊湊的關(guān)鍵幀則是本文要探討的問題。

多年來，各種聚類算法被應(yīng)用于關(guān)鍵幀提取。通常來說，當(dāng)聚類完成后，在每個類別中選擇一幅圖像作為關(guān)鍵幀。這種聚類算法的性能在很大程度上依賴于用戶輸入值的大小或設(shè)置閾值參數(shù)值高低（例如，簇的數(shù)目）。此外，用于測量幀之間的相似度的標(biāo)準(zhǔn)也顯著地影響了關(guān)鍵幀設(shè)置。并且，許多現(xiàn)有的視頻檢索方法在預(yù)處理階段使用均勻采樣方法會導(dǎo)致一些信息幀的排斥。

本文描述了一種新型的有效利用改進(jìn)的AP聚類提取視頻關(guān)鍵幀的方法。該方法按照圖像幀顏色信息分布不均勻特征對AP聚類的輸入矩陣（也稱為相似度矩陣）增加權(quán)重且自適應(yīng)調(diào)整阻尼系數(shù)，避免了提取關(guān)鍵幀的不可靠和用戶手動設(shè)置阻尼系數(shù)的隨機(jī)性的影響，提高了關(guān)鍵幀的準(zhǔn)確性和有效性。

1 鏡頭分割

視頻根據(jù)其自身的結(jié)構(gòu)特征，被劃分為場景、鏡頭和視頻幀三個層次，鏡頭邊緣檢測（也稱為鏡頭分割）是視頻檢索和視頻摘要的第一步，主要是將視頻進(jìn)行有效地分割[3]。其基本流程如圖1所示。

先把視頻轉(zhuǎn)化為m個幀，然后將m個幀分為

B（3×3）個區(qū)域，接著計算每一個區(qū)域的灰度直方圖，最后通過對B個區(qū)域中進(jìn)行加權(quán)得到最后的相似度。根據(jù)m個幀之間的相似度和高低閾值系數(shù)可以對鏡頭進(jìn)行突變檢測和漸變檢測。

1.1 相鄰幀幀差值計算

YUV顏色空間是一種顏色編碼方法，該方法經(jīng)常被用于電視系統(tǒng)，其特點是可以隔離亮度信號Y和色度信號U、V[4]。它可以不通過解壓縮而直接通過壓縮視頻獲取。其中信號Y表示明亮度，信號U和V表示色度，即描述影像色彩及飽和度并指定像素的顏色[5]。

YUV顏色空間可以通過RGB空間轉(zhuǎn)換得到，具體情況如公式⑴。

⑴

在對幀進(jìn)行直方圖統(tǒng)計時，會丟失位于幀中像素點的位置信息，導(dǎo)致反映視頻的空間信息困難，所以本文采用分塊直方圖作為解決方案[5]。事實上，一個幀中不同部位的顏色提供的信息量各不相同，一般幀的信息主要集中在幀的正中央，而邊緣部分作為背景，由此，本文對幀進(jìn)行簡單的分塊處理，對幀中的每一塊賦予不同的權(quán)重[6]。分塊方法有等距離環(huán)形分塊方法、不均勻分塊方法等。本文采用不均勻分塊方法，如圖2所示。

從圖2可以看出，將m個幀不均勻分為M×N（文中為3×3）大小的子塊，A區(qū)域位于幀的中心，它包含了一幅幀的主要信息，賦予較大的權(quán)重；相對于A而言，B、C、D、E區(qū)域中所包含的幀信息量較少，則賦予較小的權(quán)重；F、G、H、I區(qū)域含有的幀信息量最小，賦予最小的權(quán)重。

計算m個相鄰幀之間對應(yīng)子塊的直方圖差值為：

⑵

公式⑵中的變量Y_valuek代表當(dāng)前第k幀的Y分量直方圖，而變量Y_valuek+1則為第k+1幀子塊的Y分量直方圖[7]。視頻幀與分塊權(quán)值相對應(yīng)的加權(quán)矩陣W由公式⑶計算可以得出。

⑶

相鄰兩個視頻幀之間對應(yīng)的Y分量的直方圖差值FramDiffk，k+1可以通過幀之間差值和加權(quán)矩陣計算得到，F(xiàn)ramDiffk，k+1為：

⑷

1.2 高低閾值選取

在一個視頻中，同一組鏡頭內(nèi)各個幀表示的信息相似，而鏡頭間的幀表示的信息差別較大。鏡頭的突變是根據(jù)幀之間的Y分量直方圖幀差值較大形成的，而鏡頭的漸變則是根據(jù)幀的亮度不斷變化來實現(xiàn)的。

計算當(dāng)前檢測鏡頭的幀差值總和FramDiffAll為：

⑸

其中i的初始值取視頻中首幀編號，n表示鏡頭當(dāng)前位置幀到第一幀直接的幀數(shù)目[7]，代表待測鏡頭內(nèi)的平均幀差值為：

⑹

突變鏡頭檢測的自適應(yīng)高閾值為：

⑺

漸變鏡頭檢測的自適應(yīng)低閾值為：

⑻

其中公式⑺和公式⑻中的高閾值系數(shù)μ值和低閾值系數(shù)υ值對鏡頭檢測準(zhǔn)確度影響很大，經(jīng)過大量的實驗對比，這里取μ的值為3.5，υ的值為1.6。

1.3 鏡頭檢測模塊

由公式⑺和公式⑻的高閾值和低閾值與相鄰幀之間的相似度矩陣D中的相似度做比較，進(jìn)行鏡頭的切變檢測和漸變檢測。如果相似度比低閾值小，表明兩個幀之間存在突變；反之則表明兩個幀之間存在漸變。

2 關(guān)鍵幀提取

2.1 AP算法

AP（affinity propagation clustering）算法是由Frey等人于2007年提出的一種新型無監(jiān)督聚類算法[8]，該算法無需預(yù)先指定聚類數(shù)目，在迭代過程中不斷搜索合適的聚類中心，避免了聚類結(jié)果受初始類代表點影響的缺點。同時該算法在處理多類數(shù)據(jù)時運算速度較快，性能更優(yōu)。

算法以n個數(shù)據(jù)點兩兩之間的相似度組成的相似度矩陣Sn×n作為算法的輸入，數(shù)據(jù)點k成為聚類中心的衡量準(zhǔn)則依賴于相似度矩陣中的對角線上的數(shù)值S（k，k）大小[9]。初始時將所有樣本點當(dāng)作是一個潛在的聚類中心點，根據(jù)各結(jié)點間傳遞吸引力消息來確定聚類中心，吸引力消息包括吸引度（responsibility）和歸屬度（availability），吸引度r（i，k）表示數(shù)據(jù)點k作為數(shù)據(jù)點i聚類中心的適合程度；歸屬度a（i，k）表示數(shù)據(jù)點i選擇數(shù)據(jù)點k作為聚類中心的合適程度，消息傳遞過程如圖3所示[10]。

公式⑼中是計算相似度矩陣S（i，j）的大小，其中p（i）稱之為參考度p（preference），它影響著AP聚類的數(shù)目。假設(shè)潛在的聚類中心都是由每個數(shù)據(jù)點組成，那么參考度的取值相等；如若參考度的取值為相似度矩陣S（i，j），則迭代后的聚類數(shù)目相等；如若參考度取值最小，則迭代生成的聚類數(shù)目最少[9]。

公式⑿和⒀中λ為收斂系數(shù)，可以通過調(diào)節(jié)收斂系數(shù)的大小控制算法的收斂速度及穩(wěn)定性。聚類中心在迭代次數(shù)范圍內(nèi)不發(fā)生變化或者迭代次數(shù)超過預(yù)期設(shè)置的最大閾值條件下，程序停止計算，并確定各類的樣本點以及聚類中心，否則在其他條件下，程序繼續(xù)迭代[11]。

2.2 改進(jìn)的AP算法

2.2.1 增加相似度矩陣權(quán)重

傳統(tǒng)的AP聚類算法對不同幀之間的相似度矩陣S的值是通過計算兩個不同幀之間的平方歐式距離，并且對一個幀的相似度矩陣S（k，k）的值參考度p取值為S的均值。采用該方法計算簡便、時間復(fù)雜度低，但是容易導(dǎo)致在最后聚類之后得到的關(guān)鍵幀類別不精確（也就是說本應(yīng)該在該類中的關(guān)鍵幀卻在另外一類中），查準(zhǔn)率不高；也忽略了幀與幀之間的相互關(guān)聯(lián)關(guān)系。

為了減小不同幀之間的相似度矩陣的誤差和精確地找出關(guān)鍵幀并提高聚類的精度，本文在傳統(tǒng)的AP聚類算法上對相似度矩陣增加了權(quán)重。在各幀之間計算視頻幀的相似度的時候，幀和幀之間會存在關(guān)聯(lián)關(guān)系，具體計算方式如公式⒂和⒃公式。

⒂

⒃

公式⒂和⒃中，S（i，j）是輸入數(shù)據(jù)和的相似度矩陣，其中wk是表示計算單元的權(quán)重。

2.2.2 調(diào)整收斂系數(shù)

傳統(tǒng)的AP聚類算法收斂系數(shù)固定不變，文獻(xiàn)[8]通過實驗發(fā)現(xiàn)，收斂系數(shù)越大則收斂過程越穩(wěn)定，迭代曲線較平穩(wěn)，但收斂速度較慢，相反，收斂系數(shù)越小迭代過程振蕩程度越高收斂速度較快，因此，找到一個合適的收斂系數(shù)對AP算法有較大的影響。本文借鑒上述思想，提出一種收斂系數(shù)動態(tài)調(diào)整方案，在AP算法更新迭代過程中動態(tài)調(diào)整收斂系數(shù)，使之在保證收斂精度的同時具有較快的收斂速度。

假設(shè)共有n個數(shù)據(jù)點，兩兩之間的相似度組成相似度矩陣Sn×n，由于我們希望AP算法在開始時具有較快的收斂速度，快速接近收斂狀態(tài)，而在接近收斂時減少振蕩，逐漸趨于收斂狀態(tài)，同時AP算法中數(shù)據(jù)點k成為聚類中心的衡量準(zhǔn)則常常是依賴于相似度矩陣中的對角線上的數(shù)值S（k，k）大小，由此我們根據(jù)聚類算的迭代過程中Sn×n對角線上數(shù)值的變化速率來確定收斂系數(shù)的大小，具體方法如下：

⒄

公式⒄中λ0為初始收斂系數(shù)，本文中設(shè)置λ0=0.75。，表示數(shù)據(jù)點k在第i次迭代后為聚類中心的合適程度。α和β代表范圍參數(shù)，分別用來調(diào)整算法收斂系數(shù)的波動區(qū)間和改變速率，參數(shù)α的數(shù)值越大，迭代過程中的波動情況對收斂系數(shù)的影響因素越大。β主要用于配合α，使得收斂系數(shù)的變化范圍在合理范圍內(nèi)，本文中α=0.4，β=0.5。從式中可以看出，當(dāng)兩次迭代變化較大時，說明此時迭代仍處于初期，未進(jìn)入穩(wěn)定階段，應(yīng)使其保持快速收斂狀態(tài)，快速收斂至較穩(wěn)定狀態(tài)。當(dāng)兩次迭代變化較小時，說明此時已進(jìn)入穩(wěn)定狀態(tài)，通過上式可以增大收斂系數(shù)，使其不至于振蕩，逐漸趨于穩(wěn)定狀態(tài)。

3 實驗結(jié)果及分析

3.1 實驗環(huán)境

實驗在Windows7 64位操作系統(tǒng)下進(jìn)行，軟件測試環(huán)境為MATLABR2010b，實驗的硬件環(huán)境為CPU：Intel（R） Core（TM）2 Duo，內(nèi)存：4G。

3.2 聚類效果評價指標(biāo)

本研究通過兩個指標(biāo)衡量聚類算法的性能：F-度量值[13]，收斂次數(shù)。F-度量值是用來反映關(guān)鍵幀提取中查準(zhǔn)率和查全率的評價指標(biāo)。用于度量聚類算法的準(zhǔn)確性，而收斂次數(shù)指AP算法更新迭代至穩(wěn)定狀態(tài)所花費的迭代次數(shù)。

假設(shè)ni是代表類別i的視頻幀的數(shù)量，nj是代表聚類j的視頻幀數(shù)目，nij是聚類j中屬于類別i的幀數(shù)目，則查準(zhǔn)率P（i，j）和查全率R（i，j）的定義[14]如下：

⒅

對應(yīng)的F-度量值F（i，j）的定義如下：

⒆

全局聚類的F-度量值的定義為：

⒇

其中n為幀總數(shù)和，F(xiàn)值越高，證明聚類效果越好。

3.3 改進(jìn)的AP聚類算法在關(guān)鍵幀提取中的應(yīng)用

為了衡量文中提出的在關(guān)鍵幀提取中所用改進(jìn)AP算法與傳統(tǒng)的AP算法之間的優(yōu)劣性，從C語言程序設(shè)計、機(jī)器學(xué)習(xí)、Web智能與大數(shù)據(jù)和數(shù)據(jù)挖掘四個教學(xué)視頻中抽取了部分視頻進(jìn)行測試，其中視頻序列從1500多幀到8000幀之間，每一幀為640×360像素。四類視頻提取的關(guān)鍵幀的結(jié)果如表1。

從影視中選取一部視頻教程 《數(shù)據(jù)挖掘》中的某一段視頻，分別利用傳統(tǒng)的方法與改進(jìn)的方法來提取該教學(xué)視頻中的關(guān)鍵幀，最后得出實驗結(jié)果如圖5和圖6中所示。

從圖5和圖6中的對比實驗結(jié)果圖中可以看出，利用本文提出的方法提取出來的關(guān)鍵幀的數(shù)目要比傳統(tǒng)算法的關(guān)鍵幀數(shù)目少，并且本文方法的聚類精度比傳統(tǒng)的AP算法的高。

4 結(jié)束語

本文通過考慮視頻幀之間的區(qū)域相關(guān)性和人工設(shè)置阻尼系數(shù)的偶然性，提出了一種新型且有效的利用區(qū)域相關(guān)和自適應(yīng)閾值的AP聚類方法。該方法根據(jù)視頻幀中的顏色信息分布不均勻特征對AP聚類的輸入矩陣增加權(quán)重并且根據(jù)相似度值的變化速率自動阻尼系數(shù)來提取教學(xué)視頻中的關(guān)鍵幀。經(jīng)過實驗驗證，該方法有效地避免了提取關(guān)鍵幀的過程中產(chǎn)生隨機(jī)性的阻尼系數(shù)的的影響，同時也通過增加相似度矩陣的權(quán)重提高了關(guān)鍵幀的準(zhǔn)確性和有效性。根據(jù)教學(xué)視頻本身的海量數(shù)據(jù)的特點，接下來的工作將在本文方法的基礎(chǔ)上考慮并行處理技術(shù)，在保證聚類精度的同時，提高在海量的教學(xué)視頻中聚類的效率。

參考文獻(xiàn)（References）：

[1] Collomosse J P， McNeill G， Qian Y， Storyboard sketches

for Content Based Video Retrieval[C]//IEEE 12th International Conference on Computer Vision，2009：245-252

[2] Huang Zi， Li Yi-jun， ShaoJie， et al. Content-Based Video

search： Is there a Need， and Is it Possible[C]//International Workshop on Tnformation-Explosion and Next Generation Search，2008：12-19

[3] 蔣元友.一種基于聚類的關(guān)鍵幀提取算法[J].數(shù)字技術(shù)與應(yīng)

用，2014.

[4] 周海燕.片上LCD控制器中多層顯示的設(shè)計與實現(xiàn)[D].東南

大學(xué)，2010.

[5] 劉艷紅.視頻鏡頭分割算法綜述[J].科技創(chuàng)新與應(yīng)用，2014.

[6] 王華秋，王重陽，聶珍.空間密度聚類在數(shù)字圖書館圖像檢索

中的應(yīng)用[J].現(xiàn)代情報，2016.36（2）：129-131

[7] 汪翔，羅斌，翟素蘭.基于顏色空間的自適應(yīng)閾值鏡頭分割算

法[J].計算機(jī)技術(shù)與發(fā)展，2012.22（9）：37-40

[8] B J Fery， D Dueck. Clustering by Passing Messages

Between Data Points.Science，2007.315（5814）：972-976

[9] 甘月松，陳秀宏，陳曉暉.一種AP算法的改進(jìn)：M-AP聚類算

法[J].計算機(jī)科學(xué)，2015.42（1）：137-141

[10] 錢雪忠，趙建芳，賈志偉.基于約束投影的近鄰傳播聚類算

法[J].計算機(jī)工程與科學(xué)，2014.36（2）：524-529

[11] 李輝，丁世飛.基于AP二次聚類的神經(jīng)網(wǎng)絡(luò)聚成算法研究[J].

計算機(jī)科學(xué)，2015.2.

[12] Liu Xiao-yong， Fu Hui. A fast affinity propagation

clustering algorithm[J].Journal of Shandong university（Engineering Science），2011.41（4）：20-23

[13] Huang Cheng-hui， Yin Jian， HouFang.A Text Similarity

Measurement Combining Word Semantic Information with TF-IDF Method[J].Chinese Journal of Computers，2011.34（5）：856-864

[14] 王寅.基于紋理的視頻鏡頭邊界檢測系統(tǒng)研究[D].北京郵電

大學(xué)，2010.