基于ap聚類算法的視頻調(diào)節(jié)技術(shù)研究

基于ap聚類算法的視頻調(diào)節(jié)技術(shù)研究

0基于改進(jìn)的ap聚類算法的關(guān)鍵幀提取隨著視頻采集、存儲和分發(fā)技術(shù)的進(jìn)步，學(xué)生日常訪問視頻的數(shù)量顯著增加。如何幫助學(xué)生有效地瀏覽及檢索其感興趣的視頻,將具有重要的理論意義和實(shí)用價值。作為基于內(nèi)容的視頻檢索多年來,各種聚類算法被應(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視頻的分割和相關(guān)圖像的形成視頻根據(jù)其自身的結(jié)構(gòu)特征,被劃分為場景、鏡頭和視頻幀三個層次,鏡頭邊緣檢測(也稱為鏡頭分割)是視頻檢索和視頻摘要的第一步,主要是將視頻進(jìn)行有效地分割先把視頻轉(zhuǎn)化為m個幀,然后將m個幀分為B(3×3)個區(qū)域,接著計算每一個區(qū)域的灰度直方圖,最后通過對B個區(qū)域中進(jìn)行加權(quán)得到最后的相似度。根據(jù)m個幀之間的相似度和高低閾值系數(shù)可以對鏡頭進(jìn)行突變檢測和漸變檢測。1.1分塊直方圖的改進(jìn)YUV顏色空間是一種顏色編碼方法,該方法經(jīng)常被用于電視系統(tǒng),其特點(diǎn)是可以隔離亮度信號Y和色度信號U、VYUV顏色空間可以通過RGB空間轉(zhuǎn)換得到,具體情況如公式⑴。在對幀進(jìn)行直方圖統(tǒng)計時,會丟失位于幀中像素點(diǎn)的位置信息,導(dǎo)致反映視頻的空間信息困難,所以本文采用分塊直方圖作為解決方案從圖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_value相鄰兩個視頻幀之間對應(yīng)的Y分量的直方圖差值FramDiff1.2鏡頭的漸變與鏡頭的漸變在一個視頻中,同一組鏡頭內(nèi)各個幀表示的信息相似,而鏡頭間的幀表示的信息差別較大。鏡頭的突變是根據(jù)幀之間的Y分量直方圖幀差值較大形成的,而鏡頭的漸變則是根據(jù)幀的亮度不斷變化來實(shí)現(xiàn)的。計算當(dāng)前檢測鏡頭的幀差值總和FramDiffAll為:其中i的初始值取視頻中首幀編號,n表示鏡頭當(dāng)前位置幀到第一幀直接的幀數(shù)目突變鏡頭檢測的自適應(yīng)高閾值為:漸變鏡頭檢測的自適應(yīng)低閾值為:其中公式⑺和公式⑻中的高閾值系數(shù)μ值和低閾值系數(shù)υ值對鏡頭檢測準(zhǔn)確度影響很大,經(jīng)過大量的實(shí)驗(yàn)對比,這里取μ的值為3.5,υ的值為1.6。1.3相似度矩陣d的檢測由公式⑺和公式⑻的高閾值和低閾值與相鄰幀之間的相似度矩陣D中的相似度做比較,進(jìn)行鏡頭的切變檢測和漸變檢測。如果相似度比低閾值小,表明兩個幀之間存在突變;反之則表明兩個幀之間存在漸變。2關(guān)鍵組件的提取2.1基于ap算法的聚類更新迭代算法AP(affinitypropagationclustering)算法是由Frey等人于2007年提出的一種新型無監(jiān)督聚類算法算法以n個數(shù)據(jù)點(diǎn)兩兩之間的相似度組成的相似度矩陣S初始r(i,k)和a(i,k)均為0,r(i,k)和a(i,k)的值的大小與k點(diǎn)成為聚類中心的可能性正相關(guān)。AP算法的核心是吸引度和歸屬度兩個消息的更新迭代過程,具體過程如下:公式⑼中是計算相似度矩陣S(i,j)的大小,其中p(i)稱之為參考度p(preference),它影響著AP聚類的數(shù)目。假設(shè)潛在的聚類中心都是由每個數(shù)據(jù)點(diǎn)組成,那么參考度的取值相等;如若參考度的取值為相似度矩陣S(i,j),則迭代后的聚類數(shù)目相等;如若參考度取值最小,則迭代生成的聚類數(shù)目最少公式⑿和⒀中λ為收斂系數(shù),可以通過調(diào)節(jié)收斂系數(shù)的大小控制算法的收斂速度及穩(wěn)定性。聚類中心在迭代次數(shù)范圍內(nèi)不發(fā)生變化或者迭代次數(shù)超過預(yù)期設(shè)置的最大閾值條件下,程序停止計算,并確定各類的樣本點(diǎn)以及聚類中心,否則在其他條件下,程序繼續(xù)迭代2.2改進(jìn)的ap算法2.2.1基于ap聚類的聚類分析方法傳統(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ù)2.2.2調(diào)整選集系數(shù)傳統(tǒng)的AP聚類算法收斂系數(shù)固定不變,文獻(xiàn)假設(shè)共有n個數(shù)據(jù)點(diǎn),兩兩之間的相似度組成相似度矩陣S公式⒄中λ3結(jié)果與分析3.1實(shí)驗(yàn)環(huán)境及硬件環(huán)境實(shí)驗(yàn)在Windows764位操作系統(tǒng)下進(jìn)行,軟件測試環(huán)境為MATLABR2010b,實(shí)驗(yàn)的硬件環(huán)境為CPU:Intel(R)Core(TM)2Duo,內(nèi)存:4G。3.2聚類效果保證本研究通過兩個指標(biāo)衡量聚類算法的性能:F-度量值假設(shè)n對應(yīng)的F-度量值F(i,j)的定義如下:全局聚類的F-度量值的定義為:其中n為幀總數(shù)和,F值越高,證明聚類效果越好。3.3算法收斂效果對比為了衡量文中提出的在關(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。表2中通過AP算法收斂情況對比圖給出了各種系數(shù)所對應(yīng)的收斂次數(shù)。由表2可知,本文提出的自適應(yīng)動態(tài)調(diào)整阻尼系數(shù)方法的收斂次數(shù)比手動設(shè)置的收斂系數(shù)的收斂次數(shù)要少,同時能提升視頻聚類的精度和效率。圖4中反映了AP算法在各收斂系數(shù)下的收斂情況,X軸為迭代次數(shù),Y軸為每次迭代過后E矩陣對角線上數(shù)據(jù)之和。可以看出,收斂系數(shù)越大,收斂速度越慢,而本文提出的收斂系數(shù)自動調(diào)整算法在收斂剛開始時能夠較快的接近穩(wěn)定狀態(tài),之后快速進(jìn)入穩(wěn)定狀態(tài)。本文從C語言程序設(shè)計、機(jī)器學(xué)習(xí)、Web智能與大數(shù)據(jù)和數(shù)據(jù)挖掘四個教學(xué)視頻中選取視頻,并且通過F-度量值評價指標(biāo),把傳統(tǒng)的AP聚類算法與改進(jìn)的AP聚類算法做對比實(shí)驗(yàn),通過考慮相鄰幀之間的相似性,聚類實(shí)驗(yàn)中把增加了權(quán)重的相似度矩陣作為輸入,得到各視頻流所對應(yīng)的F-度量值,其結(jié)果如表3。從表3可以看出,分別在四個不同的層次視頻中,改進(jìn)的AP聚類算法的F-度量值要比傳統(tǒng)的AP聚類算法的F-度量值高,因此改進(jìn)后的算法的聚類效果要比傳統(tǒng)的算法好。從影視中選取一部視頻教程《數(shù)據(jù)挖掘》中的某一段視頻,分別利用傳統(tǒng)的方法與改進(jìn)的方法來提取該教學(xué)視頻中的關(guān)鍵幀,最后得出實(shí)驗(yàn)結(jié)果如圖5和圖6中所示。從圖5和圖6中的對比實(shí)驗(yàn)結(jié)果圖中可以看出,利用本文提出的方法提取出來的關(guān)鍵幀的數(shù)目要比傳統(tǒng)算法的關(guān)鍵幀數(shù)目少,并且本文方法的聚類精度比傳統(tǒng)的AP算法的高。4實(shí)驗(yàn)驗(yàn)證與分析本文通過考慮視頻幀之間的區(qū)域相關(guān)性和人工設(shè)置阻尼系數(shù)的偶然性,提出了一種新型且有效的利用區(qū)域相關(guān)和自適應(yīng)閾值的AP聚類方法。該方法根據(jù)視頻幀中的顏色信息分布不均勻特征對AP聚類的輸入矩陣增加權(quán)重并且根