基于決策樹(shù)的多媒體視頻關(guān)鍵幀實(shí)時(shí)提取方法研究

陳少偉，王志固

(漳州城市職業(yè)學(xué)院 文化藝術(shù)創(chuàng)意系，福建 漳州 363000)

0 引言

5G時(shí)代的到來(lái)快速推動(dòng)了社會(huì)發(fā)展進(jìn)程.多媒體短視頻代替?zhèn)鹘y(tǒng)媒介成為一種新的傳播方式[1]，其中的海量視覺(jué)信息顛覆人們固有思維.人們通過(guò)視覺(jué)方式獲取信息量占比超過(guò)85%，最為生動(dòng)形象的視頻成為最高效的交流方式[2].在全球范圍內(nèi)采集及傳輸過(guò)程中，由于傳統(tǒng)海量視覺(jué)信息未能獲得高效處理，導(dǎo)致很多資源的浪費(fèi)[3].為解決此類問(wèn)題，多媒體技術(shù)在視頻處理方面的技術(shù)獲得推動(dòng)式迅猛發(fā)展，視頻關(guān)鍵幀作為該問(wèn)題的核心環(huán)節(jié)，受到高度重視[4].多媒體網(wǎng)絡(luò)技術(shù)，涉及各行各業(yè)，能夠幫助用戶快速精確搜索到感興趣的內(nèi)容[5]，這對(duì)多媒體視頻中關(guān)鍵幀進(jìn)行實(shí)時(shí)提取極為重要[6-7].為此，相關(guān)研究者進(jìn)行了很多研究，并取得了一定成果.

仲夢(mèng)潔等[8]提出一種基于視覺(jué)顯著性的視頻關(guān)鍵幀提取方法，該方法以多特征融合圖像為參考，利用視覺(jué)顯著性有效提取關(guān)鍵幀圖像并壓縮，并有效提取車輛關(guān)鍵幀信息，但該方法需測(cè)量多方面特征，時(shí)間成本極高，無(wú)法適用于普通視頻的需求.張曉宇等[9]提出一種視頻關(guān)鍵幀提取方法，該方法利用融合特征提取視頻特征并分割關(guān)鍵幀，缺點(diǎn)是在關(guān)鍵幀分割時(shí)存在錯(cuò)誤劃分.為解決上述方法中存在的問(wèn)題，本文提出基于決策樹(shù)的多媒體視頻關(guān)鍵幀實(shí)時(shí)提取方法.決策樹(shù)作為預(yù)測(cè)模型，其實(shí)質(zhì)上是一種監(jiān)督模式機(jī)器學(xué)習(xí)方法，決策樹(shù)依據(jù)選定特征屬性對(duì)視頻樣本集進(jìn)行層級(jí)分類，再判斷特征分類.決策樹(shù)具有效率高、易操作、可同步處理數(shù)據(jù)型以及常規(guī)型屬性等多種優(yōu)勢(shì)，廣泛應(yīng)用于歸類信息以及選取特征等應(yīng)用場(chǎng)景中.將其應(yīng)用到本文方法中，精準(zhǔn)高效提取分割視頻關(guān)鍵幀，促使用戶更為快捷的瀏覽、檢索感興趣視頻，同時(shí)能高效地掌握視頻的核心內(nèi)容，使檢索效率進(jìn)一步提升.

1 多媒體視頻關(guān)鍵幀提取方法

1.1 基于信息增益比率的多媒體視頻關(guān)鍵幀特征選擇

多媒體視頻關(guān)鍵幀實(shí)時(shí)提取之前，為了提升提取的精度，首先需要利用信息增益比率選擇多媒體視頻中的關(guān)鍵幀特征.

設(shè)S為多媒體視頻幀樣本集，用Ci,i=1,2,…,n描述多媒體視頻幀樣本類別標(biāo)號(hào)，通過(guò)公式(1)描述：

(1)

其中：多媒體視頻幀樣本集S中樣本總數(shù)量以及歸屬Ci類別樣本數(shù)量分別用|S|、mum(Ci,S)表示；熵代表樣本集的純度(purity).

考量訓(xùn)練樣本集純度的參考指標(biāo)為熵，信息增益作為衡量關(guān)鍵幀特征歸類訓(xùn)練樣本能力的準(zhǔn)則，利用關(guān)鍵幀特征分割樣本集，達(dá)到熵變小的目的[10]，擬定用S和A分別描述樣本集與關(guān)鍵幀特征，通過(guò)公式(2)計(jì)算信息增益，表示為：

(2)

在信息增益應(yīng)用熵過(guò)程中，僅衡量視頻幀樣本集S內(nèi)各關(guān)鍵幀數(shù)值的熵，視頻幀樣本集S內(nèi)關(guān)鍵幀特征A中每個(gè)值的熵為分裂數(shù)據(jù)，通過(guò)公式(3)得到分裂數(shù)據(jù)為：

(3)

其中：多媒體視頻幀樣本集S被c個(gè)數(shù)值的關(guān)鍵幀特征A切割，切割后獲取到c個(gè)樣本子集為S1-Sc.

信息增益比率利用信息熵及信息增益、分裂信息求解獲取[11]，用公式(4)描述信息增益比率：

(4)

通過(guò)分支產(chǎn)生有效數(shù)據(jù)比率即為信息增益比率，信息增益比率數(shù)值越低，代表分支內(nèi)擁有的有效數(shù)據(jù)占比越低，反之，則代表該分支內(nèi)存在較多有效數(shù)據(jù)[12].

1.2 基于優(yōu)化ID3決策樹(shù)的視頻關(guān)鍵幀提取

ID3決策樹(shù)是一種利用信息增益比率確定關(guān)鍵幀特征選取準(zhǔn)則，可將最高信息增益比率的關(guān)鍵幀點(diǎn)當(dāng)作最新節(jié)點(diǎn)，并在此基礎(chǔ)上進(jìn)行子樹(shù)繁衍.

1.2.1 ID3決策樹(shù)算法

依據(jù)數(shù)據(jù)獲取分類器且多方應(yīng)用的邏輯方法即決策樹(shù).決策樹(shù)隸屬于監(jiān)督學(xué)習(xí)，是一種機(jī)器學(xué)習(xí)方法.決策樹(shù)的重要構(gòu)成要素如圖1所示，包含決策樹(shù)的決策節(jié)點(diǎn)、分支節(jié)點(diǎn)和葉子節(jié)點(diǎn).

圖1 決策樹(shù)重要構(gòu)成要素

結(jié)合圖1可以看出，決策樹(shù)是一種樹(shù)狀構(gòu)造.其中，各節(jié)點(diǎn)表示測(cè)試或選擇各個(gè)屬性的取值，測(cè)試或者選擇結(jié)果則用分支描述；類別選用決策樹(shù)的各個(gè)葉節(jié)點(diǎn)描述.根節(jié)點(diǎn)選擇樹(shù)的最高層節(jié)點(diǎn)作為決策樹(shù)的起始點(diǎn).

ID3決策樹(shù)算法作為使用時(shí)間最久、范圍最廣的決策樹(shù)算法，于上世紀(jì)末提出，已經(jīng)取得較高成就.該算法實(shí)現(xiàn)流程如圖2所示.

(1)確定最佳劃分屬性

ID3決策樹(shù)內(nèi)對(duì)信息熵進(jìn)行初步界定，確定的最佳劃分屬性取決于信息熵結(jié)果.多媒體視頻幀樣本的純度為信息熵含義，表示為：

(5)

其中：視頻幀樣本集信息熵指標(biāo)用Ent(S)描述；該視頻樣本集內(nèi)第k類樣本占比用pk描述；視頻幀樣本總類型為y；當(dāng)信息熵?cái)?shù)值偏高則代表視頻幀樣本集純度偏小，反之，則偏大.

圖2 決策樹(shù)算法的訓(xùn)練步驟

因此，最佳關(guān)鍵幀特征選取信息熵增益最高的幀特征需要滿足以下條件，即：

(6)

其中：最佳劃分關(guān)鍵幀特征用a*描述；視頻幀樣本集S依據(jù)關(guān)鍵幀特征a分割相應(yīng)信息熵增益為Gain(S,a)；各屬性取值數(shù)量用Va描述；視頻幀樣本子集信息熵為Ent(Sv)；視頻幀樣本集樣本數(shù)目以及在視頻幀樣本集內(nèi)關(guān)鍵幀特征a且取值v視頻幀樣本子集Sv分別用|Sv|和|S|描述.

(2)分支衍生

依據(jù)最佳劃分屬性，將選取的值進(jìn)行分割操作，分支數(shù)為關(guān)鍵幀特征取值數(shù)值.

(3)循環(huán)判斷

遞歸問(wèn)題決策過(guò)程即決策樹(shù)的演變過(guò)程.判斷是否繼續(xù)返回時(shí)要符合下述條件之一：①視頻幀樣本集為空集；②最佳關(guān)鍵幀特征為空集；③分割后獲取視頻幀樣本子集為同類時(shí)則結(jié)束循環(huán)分割.

1.2.2 ID3決策樹(shù)關(guān)鍵幀分類

以信息增益比率最高關(guān)鍵幀特征作為參考指標(biāo)，選取決策樹(shù)各個(gè)節(jié)點(diǎn)上屬性即關(guān)鍵幀特征，并利用各個(gè)非葉節(jié)點(diǎn)完成測(cè)試，獲取被測(cè)試記錄有關(guān)最大類別數(shù)據(jù).詳細(xì)步驟為：①對(duì)全部關(guān)鍵幀特征進(jìn)行檢測(cè)并選取其中信息增益最高的關(guān)鍵幀特征當(dāng)作決策樹(shù)節(jié)點(diǎn);②依據(jù)該關(guān)鍵幀特征的各個(gè)取值確定分支，之后調(diào)用該方法遞歸操作各個(gè)分支的多媒體視頻子集，搭建決策樹(shù)節(jié)點(diǎn)分支;③當(dāng)全部多媒體視頻幀子集內(nèi)部只有同一個(gè)類型的信息時(shí)結(jié)束分支構(gòu)建.確定關(guān)鍵幀數(shù)據(jù)類型及關(guān)鍵幀特征之間的關(guān)系，并以此獲取決策樹(shù)，歸類最新視頻幀樣本[13].詳細(xì)流程如下：

步驟1：對(duì)全部關(guān)鍵幀特征的信息增益進(jìn)行求解，根節(jié)點(diǎn)選取其中信息增益數(shù)值最高的關(guān)鍵幀特征來(lái)表示.

(1)對(duì)已知的訓(xùn)練數(shù)據(jù)集歸類信息期望I進(jìn)行求解.

設(shè)含有s個(gè)信息的多媒體視頻幀樣本集合用S描述，其類別關(guān)鍵幀特征，分別選取m個(gè)值同時(shí)產(chǎn)生m個(gè)類別Ci,i=1,2,…,m，若Ci類內(nèi)部樣本數(shù)量用si描述，用公式(7)描述歸類給定視頻幀樣本信息的信息量：

(7)

其中：隨機(jī)選取一個(gè)信息數(shù)據(jù)Si歸屬于Ci的概率用pi描述.

(2)對(duì)關(guān)鍵幀特征各個(gè)取值的信息預(yù)期值E(A)進(jìn)行求解.

擬定n為關(guān)鍵幀特征A內(nèi)包含的各個(gè)取值{a1,a2,…,an}，多媒體視頻幀樣本集S分割是通過(guò)關(guān)鍵幀特征A實(shí)現(xiàn)，拆分為n類集合{S1,S2,…Sn}，其中，多媒體視頻幀樣本集關(guān)鍵幀特征A取值為aj，且該值存在Sj中.

假設(shè)用測(cè)試節(jié)點(diǎn)屬性定義關(guān)鍵幀特征A，將其應(yīng)用在分割樣本集過(guò)程中，擬設(shè)多媒體視頻幀樣本子集Sj內(nèi)歸屬為Ci類的樣本數(shù)總和用sij描述，則信息熵的求解結(jié)果為：

(8)

用公式(9)描述多媒體視頻幀樣本子集Sj的信息量求解，即

(9)

其中：多媒體視頻幀樣本子集內(nèi)隨機(jī)挑選一個(gè)數(shù)據(jù)樣本在Ci在類別內(nèi)的概率為pij.

(3)求解關(guān)鍵幀特征A的信息增益InfoGain(A).

利用關(guān)鍵幀特征A對(duì)當(dāng)前分支節(jié)點(diǎn)進(jìn)行對(duì)應(yīng)多媒體視頻幀樣本集劃分，用公式(10)獲取的信息增益為：

InfoGain(A)=
I(S1j,S2j,…,Smj)-E(A).

(10)

劃分多媒體視頻幀樣本集InfoGain(A)獲取信息熵降低數(shù)量是通過(guò)關(guān)鍵幀特征A取值結(jié)果實(shí)現(xiàn)的.當(dāng)信息增益數(shù)值偏高，則表示關(guān)鍵幀特征A在歸類過(guò)程中為其提供較多信息量，降低了取值的不確定性，保障數(shù)據(jù)的可靠性[14].求解每個(gè)關(guān)鍵幀特征的信息增益并將其進(jìn)行比較；

步驟2：由根節(jié)點(diǎn)屬性的各類取值繼續(xù)構(gòu)建決策樹(shù)分支[15].

步驟3：通過(guò)遞歸方法選取信息增益最高的關(guān)鍵幀特征，作為子節(jié)點(diǎn)后直至全部子集內(nèi)搜集完同類信息，實(shí)現(xiàn)多媒體視頻關(guān)鍵幀提取.

1.2.3 多媒體視頻關(guān)鍵幀提取流程設(shè)計(jì)

ID3決策樹(shù)缺點(diǎn)表現(xiàn)在無(wú)法協(xié)調(diào)矛盾特征及模糊特征信息之間的關(guān)系，因此，本文選用優(yōu)化ID3決策樹(shù)分類方法.以提取的關(guān)鍵幀特征作為優(yōu)化ID3決策樹(shù)的屬性值，對(duì)多媒體視頻幀數(shù)據(jù)集中連續(xù)屬性取值進(jìn)行離散化處理，并求解每個(gè)條件屬性重要性，此處采取k-means++算法完成.其中，分裂節(jié)點(diǎn)選取重要性最高的屬性，以上為優(yōu)化的ID3算法的主要思想.經(jīng)過(guò)循環(huán)迭代，當(dāng)全部條件屬性成為分裂節(jié)點(diǎn)時(shí)，結(jié)束循環(huán).剪枝處理，生成最終決策樹(shù).優(yōu)化ID3算法詳細(xì)流程為：

(1)初始化多媒體視頻數(shù)據(jù)信息；

(2)對(duì)屬性值離散與否進(jìn)行判定.當(dāng)屬性值離散時(shí)，則進(jìn)行下一步驟.當(dāng)不能存在離散情況時(shí)，要確定離散化后取值數(shù)量，并對(duì)其使用k-means++算法進(jìn)行離散化處理，用離散值代替原有連續(xù)值；

(3)對(duì)活躍條件屬性重要程度進(jìn)行求解；

(4)對(duì)多媒體視頻樣本集進(jìn)行劃分，分裂節(jié)點(diǎn)選取其中重要程度最高的條件屬性；

(5)再次劃分多媒體視頻樣本集，重復(fù)(3)和(4)，選取其余條件屬性劃分多媒體視頻樣本集，當(dāng)全部條件屬性都被當(dāng)作分裂節(jié)點(diǎn)時(shí)，結(jié)束循環(huán)操作；

(6)剪枝，決策樹(shù)完成優(yōu)化.

將提取到的關(guān)鍵幀特征輸入優(yōu)化后的ID3決策樹(shù)進(jìn)行分類，實(shí)現(xiàn)多媒體視頻關(guān)鍵幀提取.

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

2.1 實(shí)驗(yàn)環(huán)境

選用Matlab2021軟件進(jìn)行仿真實(shí)驗(yàn)，選取多媒體數(shù)據(jù)庫(kù)中500段視頻作為本次實(shí)驗(yàn)對(duì)象，分別從提取效果以及性能兩方面進(jìn)行分析驗(yàn)證.

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

從數(shù)據(jù)庫(kù)中選取一段籃球比賽視頻片段進(jìn)行投籃時(shí)的關(guān)鍵幀提取，部分圖像關(guān)鍵幀提取效果如圖3 所示.

分析圖3可知，該方法可有效提取籃球比賽視頻投籃的部分關(guān)鍵幀，依據(jù)該關(guān)鍵幀提取結(jié)果可分析該運(yùn)行員投籃動(dòng)作.

圖3 關(guān)鍵幀提取效果

為全面評(píng)價(jià)本文方法提取效果，開(kāi)展密集型實(shí)驗(yàn)，分別選出新聞、動(dòng)畫(huà)、綜藝、電影和體育賽事5種不同特征類型的多媒體視頻作為樣本集，設(shè)定視頻長(zhǎng)度區(qū)間范圍為5 000到6 000幀，利用本文方法提取各類型視頻關(guān)鍵幀，驗(yàn)證其與人工檢測(cè)實(shí)際關(guān)鍵幀效果，關(guān)鍵幀提取效果如圖4 所示.

圖4 關(guān)鍵幀提取結(jié)果

分析圖4可知，本文方法檢測(cè)出的各類型視頻關(guān)鍵幀數(shù)量與人工檢測(cè)的關(guān)鍵幀總數(shù)幾乎一致，鑒于動(dòng)畫(huà)、體育及綜藝3種視頻皆屬于復(fù)雜運(yùn)動(dòng)類型，提取關(guān)鍵幀總數(shù)與人工檢測(cè)關(guān)鍵幀總數(shù)相比僅存在1項(xiàng)漏洞，總體效果良好.另外，視頻關(guān)鍵幀提取受所選視頻的分辨率因素影響，由于這些視頻存在噪聲干擾，因此，結(jié)果中存在微少的誤判視為正?，F(xiàn)象.

為驗(yàn)證本文方法的關(guān)鍵幀提取精度，將多媒體視頻幀樣本集等分為3部分，訓(xùn)練數(shù)據(jù)選取前兩部分，其余一部分則作為測(cè)試集.驗(yàn)證ID3決策樹(shù)優(yōu)化前后在遭受各類攻擊狀態(tài)下的關(guān)鍵幀提取準(zhǔn)確率，擬設(shè)ID3決策樹(shù)優(yōu)化前后的節(jié)點(diǎn)數(shù)量及葉子節(jié)點(diǎn)數(shù)可進(jìn)行自適應(yīng)調(diào)節(jié)，驗(yàn)證關(guān)鍵幀提取準(zhǔn)確率是否受外界干擾影響，即驗(yàn)證本文方法的關(guān)鍵幀提取性能是否穩(wěn)定.遭受各種攻擊狀態(tài)下ID3決策樹(shù)優(yōu)化前后的準(zhǔn)確率對(duì)比結(jié)果如表1 所列.

分析表1可知，ID3決策樹(shù)優(yōu)化前在遭受各類攻擊狀態(tài)時(shí)其準(zhǔn)確率維持在82.5%到88.6%區(qū)間范圍內(nèi)，整體偏低，性能略差；ID3決策樹(shù)優(yōu)化后的節(jié)點(diǎn)數(shù)及葉子節(jié)點(diǎn)數(shù)均為最少，同時(shí)準(zhǔn)確率最高，全程保持在96.9%到98.8%，各種攻擊狀態(tài)下性能表現(xiàn)極佳，實(shí)驗(yàn)證明該方法能夠準(zhǔn)確提取海量多媒體視頻關(guān)鍵幀.

選用DR、ACC作為衡量本文方法關(guān)鍵幀提取性能的兩個(gè)指標(biāo)，繼續(xù)開(kāi)展實(shí)驗(yàn).DR代表多媒體視頻關(guān)鍵幀提取率；ACC代表決策樹(shù)能夠準(zhǔn)確識(shí)別出假陰性及真陽(yáng)性的占比，結(jié)果如圖5所示，橫坐標(biāo)為多媒體視頻幀數(shù)量，圖中曲線表示隨著視頻幀數(shù)量的變化，DR、ACC兩者之間關(guān)系變化浮動(dòng)大小.

分析圖5可知，隨著視頻幀數(shù)量的增加，DR及ACC兩項(xiàng)指標(biāo)始終保持平穩(wěn)狀態(tài)，不會(huì)過(guò)多受視頻幀數(shù)量干擾，證明本文方法的多媒體視頻關(guān)鍵幀提取性能整體優(yōu)秀.

表1 遭受各種攻擊狀態(tài)下2種方法的準(zhǔn)確率

圖5 視頻幀數(shù)量對(duì)關(guān)鍵幀提取性能的影響

3 結(jié)語(yǔ)

當(dāng)前，傳統(tǒng)視頻幀提取方法中由于視頻內(nèi)含有較多的冗余信息，難以提升關(guān)鍵幀的提取效果.本文提出基于決策樹(shù)的多媒體視頻關(guān)鍵幀實(shí)時(shí)提取方法.對(duì)視頻樣本集進(jìn)行視頻幀的關(guān)鍵幀特征提取，將獲取的關(guān)鍵幀特征輸入優(yōu)化后的ID3決策樹(shù)，完成視頻關(guān)鍵幀提取.實(shí)驗(yàn)結(jié)果證明，該方法能夠高效分類提取海量多媒體視頻關(guān)鍵幀，在不同視頻幀數(shù)量下提取性能較好.