采用自適應聚類的教學視頻關鍵幀研究

王華秋+殷志恒

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

關鍵詞： 數字視頻； 鏡頭分割； 關鍵幀提取； AP聚類

中圖分類號：TP391.41 文獻標志碼：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 引言

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

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

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

1 鏡頭分割

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

先把視頻轉化為m個幀，然后將m個幀分為

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

1.1 相鄰幀幀差值計算

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

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

⑴

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

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

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

⑵

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

⑶

相鄰兩個視頻幀之間對應的Y分量的直方圖差值FramDiffk，k+1可以通過幀之間差值和加權矩陣計算得到，FramDiffk，k+1為：

⑷

1.2 高低閾值選取

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

計算當前檢測鏡頭的幀差值總和FramDiffAll為：

⑸

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

⑹

突變鏡頭檢測的自適應高閾值為：

⑺

漸變鏡頭檢測的自適應低閾值為：

⑻

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

1.3 鏡頭檢測模塊

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

2 關鍵幀提取

2.1 AP算法

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

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

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

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

2.2 改進的AP算法

2.2.1 增加相似度矩陣權重

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

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

⒂

⒃

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

2.2.2 調整收斂系數

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

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

⒄

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

3 實驗結果及分析

3.1 實驗環境

實驗在Windows7 64位操作系統下進行，軟件測試環境為MATLABR2010b，實驗的硬件環境為CPU：Intel（R） Core（TM）2 Duo，內存：4G。

3.2 聚類效果評價指標

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

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

⒅

對應的F-度量值F（i，j）的定義如下：

⒆

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

⒇

其中n為幀總數和，F值越高，證明聚類效果越好。

3.3 改進的AP聚類算法在關鍵幀提取中的應用

為了衡量文中提出的在關鍵幀提取中所用改進AP算法與傳統的AP算法之間的優劣性，從C語言程序設計、機器學習、Web智能與大數據和數據挖掘四個教學視頻中抽取了部分視頻進行測試，其中視頻序列從1500多幀到8000幀之間，每一幀為640×360像素。四類視頻提取的關鍵幀的結果如表1。

從影視中選取一部視頻教程 《數據挖掘》中的某一段視頻，分別利用傳統的方法與改進的方法來提取該教學視頻中的關鍵幀，最后得出實驗結果如圖5和圖6中所示。

從圖5和圖6中的對比實驗結果圖中可以看出，利用本文提出的方法提取出來的關鍵幀的數目要比傳統算法的關鍵幀數目少，并且本文方法的聚類精度比傳統的AP算法的高。

4 結束語

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

參考文獻（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] 蔣元友.一種基于聚類的關鍵幀提取算法[J].數字技術與應

用，2014.

[4] 周海燕.片上LCD控制器中多層顯示的設計與實現[D].東南

大學，2010.

[5] 劉艷紅.視頻鏡頭分割算法綜述[J].科技創新與應用，2014.

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

中的應用[J].現代情報，2016.36（2）：129-131

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

法[J].計算機技術與發展，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算法的改進：M-AP聚類算

法[J].計算機科學，2015.42（1）：137-141

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

法[J].計算機工程與科學，2014.36（2）：524-529

[11] 李輝，丁世飛.基于AP二次聚類的神經網絡聚成算法研究[J].

計算機科學，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] 王寅.基于紋理的視頻鏡頭邊界檢測系統研究[D].北京郵電

大學，2010.