采用自適應(yīng)聚類的教學(xué)視頻關(guān)鍵幀研究

1、采用自適應(yīng)聚類的教學(xué)視頻關(guān)鍵幀研究摘要：視頻鏡頭分割和關(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)鍵幀提?。籥p 聚類中圖分類號:tp391.41文獻(xiàn)標(biāo)志碼：a文章編號: 1006-8228 (2016) 12-90-05abstract： video shot

2、 segmentation and key frame extraction is the critical step in the current digital video system development. in this paper,the ap (affinitypropagation) clustering algorithm is improved in the two points： first， the weight is in creased in the initial correlation coefficient matrix to improve the clu

3、stering accuracy； second， the damping coefficient is adjusted adaptively to improve the con verge nee rate. use the weighted color in formati on and adjace nt frame differenee method to divide the video into shots, and then use the improved ap clustering algorithm to extract the key frames from the

4、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 methodskey words： digital video； shot segmentation； key frame extraction； affinity propagation cluster

5、ing0引言隨著視頻采集、存儲與分布技術(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ù)處理階段使用均勻采樣方法會

6、導(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)行有效地分割。其基本流程如圖1所示。先把視頻轉(zhuǎn)化為m個幀，然后將m個幀分為b (3x3)個區(qū)域，接著計算每一個區(qū)域的灰度直方圖，最后通過對b個區(qū)域中進(jìn)行

7、加權(quán)得到最后的相 似度。根據(jù)m個幀之間的相似度和高低閾值系數(shù)可以 對鏡頭進(jìn)行突變檢測和漸變檢測。1.1相鄰幀幀差值計算yuv顏色空間是一種顏色編碼方法，該方法經(jīng)常 被用于電視系統(tǒng)，其特點是可以隔離亮度信號y和色 度信號u、v4o它可以不通過解壓縮而直接通過壓 縮視頻獲取。其中信號丫表示明亮度，信號u和v表 示色度，即描述影像色彩及飽和度并指定像素的顏色 。yuv顏色空間可以通過rgb空間轉(zhuǎn)換得到，具體 情況如公式。(1)在對幀進(jìn)行直方圖統(tǒng)計時，會丟失位于幀中像素 點的位置信息，導(dǎo)致反映視頻的空間信息困難，所以 本文采用分塊直方圖作為解決方案。事實上，一個 幀中不同部位的顏色提供的信息量各不相同

8、，一般幀 的信息主要集中在幀的正中央，而邊緣部分作為背景, 由此，本文對幀進(jìn)行簡單的分塊處理，對幀中的每一 塊賦予不同的權(quán)重。分塊方法有等距離環(huán)形分塊方 法、不均勻分塊方法等。本文采用不均勻分塊方法， 如圖2所示。從圖2可以看出，將m個幀不均勻分為mxn(文 中為3x3)大小的子塊，a區(qū)域位于幀的中心，它包 含了一幅幀的主要信息，賦y較大的權(quán)重；相對于a 而言，b、c、d、e區(qū)域中所包含的幀信息量較少，則 賦予較小的權(quán)重；f、g、h、i區(qū)域含有的幀信息量最 小，賦予最小的權(quán)重。計算m個相鄰幀之間對應(yīng)子塊的直方圖差值為:(2) 公式中的變量y_valuek代表當(dāng)前第k幀 的y分量直方圖，而變量y

9、_valuek+1則為第k+1幀子 塊的y分量直方圖。視頻幀與分塊權(quán)值相對應(yīng)的加 權(quán)矩陣w由公式計算可以得出。(3)相鄰兩個視頻幀之間對應(yīng)的y分量的直方圖差值 framdiffk, k+1可以通過幀之間差值和加權(quán)矩陣計算 得到，framdiffk, k+1 為：1.2高低閾值選取在一一個視頻中，同一組鏡頭內(nèi)各個幀表示的信息 相似，而鏡頭間的幀表示的信息差別較大。鏡頭的突 變是根據(jù)幀之間的y分量直方圖幀差值較大形成的，而鏡頭的漸變則是根據(jù)幀的亮度不斷變化來實現(xiàn)的。 計算當(dāng)前檢測鏡頭的幀差值總和framdiffaii為:其中i的初始值取視頻中首幀編號，n表示鏡頭當(dāng) 前位置幀到第一幀直接的幀數(shù)目7,

10、代表待測鏡頭內(nèi) 的平均幀差值為：突變鏡頭檢測的自適應(yīng)高閾值為: 漸變鏡頭檢測的自適應(yīng)低閾值為: 其中公式和公式中的高閾值系數(shù)口值和低閾 值系數(shù)u值對鏡頭檢測準(zhǔn)確度影響很大，經(jīng)過大量的 實驗對比，這里取口的值為3.5, u的值為1.6。13鏡頭檢測模塊由公式和公式的高閾值和低閾值與相鄰幀之 間的相似度矩陣d中的相似度做比較，進(jìn)行鏡頭的切 變檢測和漸變檢測。如果相似度比低閾值小，表明兩 個幀之間存在突變；反之則表明兩個幀之間存在漸變。2關(guān)鍵幀提取2.1 ap算法ap (affinity propagation cluster!ng) 算法是由 frey等人于2007年提出的一種新型無監(jiān)督聚類算法,

11、 該算法無需預(yù)先指定聚類數(shù)目，在迭代過程中不斷搜 索合適的聚類中心，避免了聚類結(jié)果受初始類代表點 影響的缺點。同時該算法在處理多類數(shù)據(jù)時運(yùn)算速度 較快，性能更優(yōu)。算法以n個數(shù)據(jù)點兩兩之間的相似度組成的相似 度矩陣snxn作為算法的輸入，數(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

12、) 表示數(shù)據(jù)點i選擇數(shù)據(jù)點k作為聚類中心的合適程度, 消息傳遞過程如圖3所示10o公式中是計算相似度矩陣s (i, j)的大小，其 中p (i)稱之為參考度p (preference),它影響著ap 聚類的數(shù)目。假設(shè)潛在的聚類中心都是由每個數(shù)據(jù)點 組成，那么參考度的取值相等；如若參考度的取值為 相似度矩陣s (i, j),則迭代后的聚類數(shù)目相等；如 若參考度取值最小，則迭代生成的聚類數(shù)目最少。公式(和(中入為收斂系數(shù)，可以通過調(diào)節(jié)收斂 系數(shù)的大小控制算法的收斂速度及穩(wěn)定性。聚類中心 在迭代次數(shù)范圍內(nèi)不發(fā)生變化或者迭代次數(shù)超過預(yù)期 設(shè)置的最大閾值條件下，程序停止計算，并確定各類 的樣本點以及聚類

13、中心，否則在其他條件下，程序繼 續(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)重。在各幀之間計 算視頻幀的相似度的時

14、候，幀和幀之間會存在關(guān)聯(lián)關(guān) 系，具體計算方式如公式(15)和(公式。(15) (16)公式(15)和(16)中，s (i, j)是輸入數(shù)據(jù)和的相似度 2.2.2調(diào)整收斂系數(shù)矩陣,其中wk是表示計算單元的權(quán)重。傳統(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ù)點，兩兩之間的相似度組成相 似度矩陣snxn,由于我們希望ap算法在開始時具有 較快的收斂速度，快速接近收斂狀態(tài)，而在接近收斂 時減少振蕩，逐漸趨于收斂狀態(tài)，同時ap算法中數(shù) 據(jù)點k成為聚類中心的衡量準(zhǔn)則常常是依賴于相似度 矩陣中的對角線上的數(shù)值s (k, k)大小，由此我們 根據(jù)聚類算的迭代過程中snxn對角線上數(shù)值的變化 速率來確定收斂系數(shù)的大小，具體方法如下：(17)公式(中入0為初始收斂系數(shù)，本文中設(shè)置入 0=0.75。，表示數(shù)據(jù)點k在第i次迭代后為聚類中心的 合適程度。