吳紹根
(廣東輕工職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系 廣州 510300)
?
基于小波變換的視頻流鏡頭切分及關(guān)鍵幀提取*
吳紹根
(廣東輕工職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系廣州510300)
視頻鏡頭切分及關(guān)鍵幀提取是基于內(nèi)容的視頻檢索的基礎(chǔ)。通過使用色彩直方圖向量來表征視頻幀特征,使用余弦夾角來度量視頻幀的相似性并建立相鄰視頻幀的相似性數(shù)據(jù)序列,再通過小波變換尋找其中的突變數(shù)據(jù)點(diǎn)或數(shù)據(jù)點(diǎn)集來完成對(duì)視頻鏡頭的切分,最后通過最小直方圖特征標(biāo)準(zhǔn)差在每個(gè)鏡頭中提取關(guān)鍵幀。實(shí)驗(yàn)表明,該方法能有效地找到鏡頭的邊界,所提取的關(guān)鍵幀可以表達(dá)鏡頭的主要內(nèi)容。
小波變換; 視頻; 鏡頭切分; 關(guān)鍵幀
Class NumberTP391
基于內(nèi)容的視頻檢索是當(dāng)前視頻檢索領(lǐng)域的研究熱點(diǎn)[1]。對(duì)視頻的檢索顯然不能使用傳統(tǒng)的基于文字的方式進(jìn)行,而只能對(duì)視頻進(jìn)行特征抽取,建立視頻的特征信息,并在此基礎(chǔ)上進(jìn)行基于視頻特征的檢索。為了建立視頻特征信息,需要首先對(duì)視頻進(jìn)行結(jié)構(gòu)進(jìn)行分析。
視頻的基礎(chǔ)結(jié)構(gòu)從語(yǔ)義角度由下至上劃分為: 幀、鏡頭、場(chǎng)景、視頻。在視頻結(jié)構(gòu)化研究中,其主要內(nèi)容是以鏡頭為單位對(duì)視頻內(nèi)容進(jìn)行劃分,即鏡頭切割或切分[2],然后在分割的視頻段內(nèi)提取關(guān)鍵幀,在此基礎(chǔ)上才能進(jìn)行后續(xù)的工作,例如基于內(nèi)容的視頻檢索等。
視頻鏡頭的切換包括突變切換和漸變切換兩種類型。突變切換是指將鏡頭直接從一個(gè)鏡頭切換到另一個(gè)鏡頭,中間沒有過濾幀;而漸變切換則從一個(gè)鏡頭切換到另一個(gè)鏡頭時(shí),中間包括一些過濾幀。所謂鏡頭切分,就是從視頻流中找到這些鏡頭的切換點(diǎn)。而關(guān)鍵幀提取則是從已經(jīng)切分的視頻鏡頭中提取最能代表各個(gè)視頻鏡頭的圖像幀。
本文提出一種基于Daubechies小波變換的視頻鏡頭切分方法和基于最小標(biāo)準(zhǔn)差的鏡頭關(guān)鍵幀提取方法。實(shí)驗(yàn)結(jié)果表明,本文所介紹的方法在鏡頭切分上優(yōu)于線性切分算法,同時(shí),從視覺判斷上,本文方法所提取的鏡頭關(guān)鍵幀能較好地反映視頻鏡頭的主要內(nèi)容。本文后續(xù)內(nèi)容將從算法的數(shù)學(xué)模型、算法描述、實(shí)驗(yàn)結(jié)果及其分析幾個(gè)方面對(duì)算法進(jìn)行介紹。
在進(jìn)行算法設(shè)計(jì)之前,首先對(duì)算法中涉及到的數(shù)學(xué)模型進(jìn)行介紹,包括:視頻幀特征表示方式、視頻幀相似性度量方法、使用小波變換檢測(cè)視頻幀突變及漸變的方法和鏡頭關(guān)鍵幀度量的方式。
2.1視頻幀的特征表示
為了進(jìn)行視頻鏡頭切分,需要首先建立視頻幀的特征表示并依據(jù)所建立的特征進(jìn)行視頻幀的相似性計(jì)算。由于色彩直方圖能夠從全局的層面表示視頻幀的特征,因此,本文采用色彩直方圖建立視頻幀的特征。建立視頻幀的特征過程包括兩個(gè)步驟:第一步,對(duì)彩色視頻幀進(jìn)行灰度化處理;第二步,構(gòu)建視頻幀的灰度直方圖向量。
2.1.1對(duì)視頻幀進(jìn)行灰度化處理
由于現(xiàn)有的大多數(shù)視頻都是彩色視頻,因此,在建立視頻的特征信息之前,需要對(duì)視頻幀進(jìn)行灰度化處理。采用如下的計(jì)算方法進(jìn)行RGB的彩色視頻幀到灰度視頻幀的轉(zhuǎn)換:
GL=0.2989*R+0.5870*G+0.1140*B
(1)
其中,R、G、B分別表示原像素點(diǎn)的紅、綠、藍(lán)的值。
2.1.2構(gòu)建視頻幀的灰度直方圖特征
對(duì)彩色視頻幀進(jìn)行灰度化處理后,視頻幀的每個(gè)像素點(diǎn)的值都在0~255這個(gè)區(qū)間。對(duì)每一個(gè)視頻幀,統(tǒng)計(jì)每一級(jí)灰度的像素個(gè)數(shù),進(jìn)而得到的一個(gè)256維的向量,這個(gè)向量稱為灰度直方圖向量,本文將這個(gè)向量作為視頻幀的特征。視頻幀的灰度直方圖計(jì)算方法如下:
HG=〈v0,v1,v2,…,v255〉
(2)
其中,vb(0≤b≤255)表示灰度為b的像素點(diǎn)個(gè)數(shù),vb的計(jì)算方法如下:
其中,M表示視頻幀的高度,N表示視頻幀的寬度,Pi,j表示在(i,j)空間位置上像素點(diǎn)的灰度值,b表示從0~255的一個(gè)灰度級(jí)。δ是符號(hào)函數(shù),其定義如下:
2.2建立視頻幀的相似性度量序列
通過為每一幀視頻幀計(jì)算其灰度直方圖,建立了每一視頻幀的特征表示。然后,采用向量的余弦夾角來度量視頻幀的相似度,計(jì)算方法如下:
(3)
其中,HGi、HGj分別表示第i個(gè)視頻幀與第j個(gè)視頻幀的灰度直方圖向量,〈HGi,HGj〉表示向量HGi與向量HGj的內(nèi)積,|HGi|、|HGj|分別表示向量HGi與向量HGj的模長(zhǎng)。
對(duì)視頻的所有相鄰視頻幀進(jìn)行相似度計(jì)算,得到如下所示的相鄰視頻幀的相似性離散序列SM:
SM=(SM〈1,2〉,SM〈2,3〉, …,
SM〈i,i+1〉,…,SM〈n-1,n〉)
(4)
其中,n表示視頻的總幀數(shù),所建立的視頻幀相似度序列是一個(gè)具有n-1個(gè)元素的序列。視頻鏡頭分割的目標(biāo)就是從該序列中找到發(fā)生突變或漸變的數(shù)據(jù)點(diǎn)或數(shù)據(jù)點(diǎn)集。本文采用消失矩為2的Daubechies小波db2來檢測(cè)這些數(shù)據(jù)點(diǎn)或數(shù)據(jù)點(diǎn)集。
2.3利用db2小波變換檢測(cè)突變或漸變數(shù)據(jù)點(diǎn)或數(shù)據(jù)點(diǎn)集
2.3.1小波變換
小波變換是繼傅里葉變換之后的又一個(gè)有力的數(shù)學(xué)工具,它解決了傅里葉變換導(dǎo)致時(shí)域信息丟失的問題。小波變換能從時(shí)域及頻域兩個(gè)維度來觀察一個(gè)函數(shù)或一個(gè)數(shù)據(jù)序列的變化性質(zhì)。小波變換如下式所示[3]:
(5)
其中,f(t)是被變換的函數(shù),ψ(t)為小波函數(shù),*表示函數(shù)的復(fù)數(shù)共軛。從上式可以看出,小波變換將函數(shù)f(t)映射為一個(gè)二元函數(shù)C(a,b),其中,a表示尺度,b表示時(shí)移。小波變換的實(shí)質(zhì)就是計(jì)算函數(shù)f(t)與特定的小波函數(shù)在尺度為a和時(shí)移為b時(shí)的相關(guān)度。如果將尺度參數(shù)a和移位參數(shù)b的選取以2的冪次方的方式離散取值,即可得到離散小波變換。離散小波變換可采用矩陣形式計(jì)算。本文采用消失矩為2的Daubechies小波db2來檢測(cè)視頻幀相似序列的突變點(diǎn)或漸變點(diǎn)集。
2.3.2構(gòu)建db2小波變換矩陣
小波變換矩陣包括兩個(gè)矩陣:分解矩陣和重組矩陣。
小波變換的分解矩陣由低通濾波矩陣和高通濾波矩陣兩個(gè)子矩陣構(gòu)成,其中低通濾波矩陣由低通濾波器參數(shù)通過逐行移位2列而構(gòu)成,高通濾波矩陣則由高通濾波器通過逐行移位2列構(gòu)成,在矩陣的最后一行需要進(jìn)行回卷;由于所構(gòu)建的小波分解矩陣是一個(gè)單位正交矩陣,因此,小波變換的重構(gòu)矩陣就是小波分解矩陣的轉(zhuǎn)置。
db2的低通濾波器參數(shù)[4]h=(-0.12940.22410.83650.4830),高通濾波器參數(shù)g=(-0.48300.8365-0.2241-0.1294)。基于這些參數(shù),構(gòu)建db2的分解矩陣WN如下:
(6)
WN是一個(gè)N×N的矩陣,其中N表示需要進(jìn)行變換的數(shù)據(jù)的維度。由于WN是一個(gè)正交單位矩陣,因此,重構(gòu)矩陣就是WN的轉(zhuǎn)置,即:
利用這一性質(zhì)可以方便的計(jì)算小波逆變換。
2.3.3對(duì)相鄰視頻幀的相似性序列SM的分解和對(duì)細(xì)節(jié)的重構(gòu)
應(yīng)用構(gòu)建的db2小波分解矩陣WN對(duì)相鄰視頻幀相似序列SM進(jìn)行分解,得到相似性近似序列系數(shù)A和細(xì)節(jié)序列系數(shù)D,如下所示:
(7)
其中的細(xì)節(jié)序列系數(shù)D的維度是SM維度的1/2,它表示數(shù)據(jù)序列SM中的突變成分。為了過濾掉D中的微小波動(dòng),采用累積能量法對(duì)細(xì)節(jié)序列系數(shù)D進(jìn)行處理。數(shù)據(jù)序列累積能量的計(jì)算方式如下:
(8)
其中v是要進(jìn)行累積能量計(jì)算的原數(shù)據(jù)序列或向量,y是對(duì)v的每個(gè)元素取絕對(duì)值后,從大到小排序而形成的數(shù)據(jù)序列。|y|是數(shù)據(jù)序列的y模長(zhǎng)。本文選擇保留原數(shù)據(jù)能量99.5%的元素值作為閾值對(duì)細(xì)節(jié)序列系數(shù)D進(jìn)行過濾,得到經(jīng)過過濾處理后的細(xì)節(jié)序列系數(shù)D′。
由于只需要從原數(shù)據(jù)序列找到突變點(diǎn)或突變點(diǎn)集,因此,可以將近似序列系數(shù)A全部設(shè)置為0,然后與細(xì)節(jié)序列系數(shù)D′構(gòu)成向量來重構(gòu)細(xì)節(jié)序列,細(xì)節(jié)重構(gòu)的計(jì)算方式如下:
(9)
其中0表示元素全為0的向量。由上式(8)得到的數(shù)據(jù)序列D*就是相鄰視頻幀的相似性序列SM的變化點(diǎn)。下一步,需要對(duì)D*進(jìn)行精化,從中找到視頻幀的突變點(diǎn)和漸變點(diǎn)集。
2.4通過精化來確定視頻幀的突變點(diǎn)和漸變點(diǎn)集
細(xì)節(jié)序列D*中的非0點(diǎn)就是發(fā)生變化的點(diǎn)。這些變化的點(diǎn)由兩類點(diǎn)構(gòu)成:鏡頭的突變點(diǎn)和由于鏡頭漸變而導(dǎo)致的一系列具有序列連續(xù)的變化點(diǎn)。考慮到漸變的過渡特性,設(shè)定當(dāng)兩個(gè)變化點(diǎn)的間隔小于視頻幀速率的1/2時(shí),則認(rèn)為這兩個(gè)相鄰的變換點(diǎn)之間的視頻幀為漸變過渡幀。在進(jìn)行鏡頭切分時(shí),舍棄這些過渡幀,取過渡幀的兩邊邊界幀作為視頻鏡頭的切分點(diǎn),這將有利于更為有效地提取鏡頭關(guān)鍵幀。
2.5鏡頭關(guān)鍵幀的提取
有句俗語(yǔ)叫做“多姿多彩”,其含義是一幅多姿多彩的圖像包含有更多的信息。一幅多姿多彩的圖像在數(shù)學(xué)上的度量可以表達(dá)為圖像的灰度直方圖的標(biāo)準(zhǔn)差達(dá)到最小。為此,本文在為各個(gè)視頻鏡頭中選取關(guān)鍵幀時(shí),選取具有最小標(biāo)準(zhǔn)差的視頻幀作為視頻鏡頭的關(guān)鍵幀。視頻幀灰度直方圖標(biāo)準(zhǔn)差的計(jì)算方式如下:
(10)
xi(0≤i≤255)是視頻幀直方圖向量的元素。
依據(jù)第2節(jié)的數(shù)學(xué)模型及其相關(guān)的計(jì)算方法,本文設(shè)計(jì)了對(duì)視頻流進(jìn)行鏡頭切分及關(guān)鍵幀提取算法。為了簡(jiǎn)化算法描述,算法中所提及的公式是指第2節(jié)中的相應(yīng)編號(hào)的公式。
算法名稱:視頻流進(jìn)行鏡頭切分及關(guān)鍵幀提取
輸入:視頻流
輸出:鏡頭切分區(qū)間及各鏡頭區(qū)間的關(guān)鍵幀編號(hào)
算法描述:
①對(duì)視頻流中的每一視頻幀 do
利用式(1)對(duì)該視頻幀進(jìn)行灰度化處理;
利用式(2)計(jì)算該視頻幀的灰度直方圖特征;
if 不是第一幀視頻幀
利用式(3)計(jì)算該視頻幀的灰度直方圖與前一視頻幀的相似度;
end if
end do
②利用式(4)建立相鄰視頻幀的相似度序列SM;
③利用式(6)建立db2小波變換矩陣WN;
④利用式(7)對(duì)SM進(jìn)行小波分解,得到細(xì)節(jié)系數(shù)D;
⑤利用式(8)對(duì)D進(jìn)行累計(jì)能量計(jì)算,利用得到的閾值對(duì)D進(jìn)行過濾,得到D‘;
⑥利用式(9)得到細(xì)節(jié)序列D*;
⑦對(duì)D*進(jìn)行精化,丟棄漸變幀,確定鏡頭邊界,并將結(jié)果存儲(chǔ)為如下形式:
[(開始幀,結(jié)束幀),(開始幀,結(jié)束幀),……,(開始幀,結(jié)束幀)]
⑧利用式(10)在每個(gè)視頻鏡頭中選取關(guān)鍵幀,并存儲(chǔ)關(guān)鍵幀編號(hào)為如下形式:
[ 第一個(gè)鏡頭的關(guān)鍵幀編號(hào),第二個(gè)鏡頭的關(guān)鍵幀編號(hào),…… ]
⑨返回鏡頭切分的結(jié)果和關(guān)鍵幀提取的結(jié)果。
為了測(cè)試算法的有效性,本文使用Matlab實(shí)現(xiàn)了算法,并從三個(gè)方面做了實(shí)驗(yàn):對(duì)視頻突變和漸變的檢測(cè)能力、視頻鏡頭切分的有效性、視頻鏡頭關(guān)鍵幀的提取有效性。
4.1對(duì)視頻突變和漸變的檢測(cè)能力分析
為了測(cè)試算法對(duì)視頻突變和漸變的檢測(cè)能力,本文對(duì)一段由7個(gè)鏡頭組成,時(shí)長(zhǎng)為30s共901幀的測(cè)試視頻采用本文的算法求出其細(xì)節(jié)序列D*。然后,對(duì)該視頻進(jìn)行人工編輯,在第1和第2個(gè)鏡頭中加入淡入/淡出(Fade In/Fade Out)漸變,在第6和第7個(gè)鏡頭之間加入了掃換(Wipe)漸變,再利用本文算法求出編輯后的視頻的細(xì)節(jié)序列D*,結(jié)果如圖1所示。
圖1 算法對(duì)突變和漸變的檢測(cè)有效性測(cè)試結(jié)果
從圖1可以看出,本文算法能夠檢測(cè)出視頻鏡頭的切變,同時(shí),在加入了漸變的視頻的細(xì)節(jié)序列中,可以清晰地觀察到在視頻的第1和第2個(gè)鏡頭間及第6和第7個(gè)鏡頭間的細(xì)節(jié)序列比原始視頻具有更寬的變化序列,因此,本文算法也能檢測(cè)到視頻的漸變鏡頭。不僅如此,通過對(duì)這些連續(xù)變化序列的精化,可以在鏡頭切分時(shí),丟棄這些漸變視頻幀,使得鏡頭的切分和關(guān)鍵幀的提取更為合理。
4.2對(duì)視頻鏡頭切分的有效性分析
為了驗(yàn)證算法對(duì)視頻鏡頭切分的有效性,將本文算法與線性切分算法[5]進(jìn)行比較,使用信息檢索中最常用的度量指標(biāo)“查全率”和”查準(zhǔn)率”來衡量鏡頭切分的結(jié)果[6],計(jì)算公式如下:
并采用綜合因子對(duì)算法的整體效果進(jìn)行度量,綜合因子的計(jì)算公式如下:
用于測(cè)試視頻數(shù)據(jù)包括一段媒體演示視頻、一段廣告視頻、一段新聞視頻、一段電影片段和一段自行拍攝的視頻,實(shí)驗(yàn)結(jié)果如表1和圖2所示。
表1 查全率和查準(zhǔn)率實(shí)驗(yàn)結(jié)果
圖2 算法的切分有效性對(duì)比
圖2中的視頻類型1、2、3、4、5分別是媒體演示視頻、新聞視頻、廣告視頻、電影片段視頻和自行拍攝的視頻。在實(shí)驗(yàn)時(shí),以第一段媒體演示視頻為基礎(chǔ)調(diào)試并設(shè)定相關(guān)閾值參數(shù),該參數(shù)使得對(duì)第一段媒體演示視頻的查全率和查準(zhǔn)率均達(dá)到100%,然后,以得到的閾值為參數(shù)對(duì)其他的視頻進(jìn)行切分。從表1和圖2可以看出,無論從查全率、查準(zhǔn)率及從綜合因子對(duì)整體效果進(jìn)行度量,本文算法均優(yōu)于線程切分算法。
4.3對(duì)視頻鏡頭關(guān)鍵幀提取的有效性分析
目前沒有一個(gè)通用的可以定量度量視頻關(guān)鍵幀提取質(zhì)量的計(jì)算標(biāo)準(zhǔn),因此,對(duì)視頻關(guān)鍵幀提取的有效性分析還僅限于直觀觀察。實(shí)驗(yàn)中,利用本文的算法對(duì)某媒體演示視頻進(jìn)行鏡頭分割并提取每個(gè)鏡頭的關(guān)鍵幀。該視頻時(shí)長(zhǎng)為30s,共有901幀,7個(gè)鏡頭轉(zhuǎn)換,圖3是鏡頭切分及關(guān)鍵幀的提取結(jié)果,從直覺觀察判斷,算法提取的視頻關(guān)鍵幀能夠反映每個(gè)鏡頭的主要內(nèi)容。
圖3 某媒體演示視頻的關(guān)鍵幀提取結(jié)果
對(duì)視頻鏡頭的切分和對(duì)關(guān)鍵幀的提取是基于內(nèi)容的視頻檢索的基礎(chǔ),自被提出以來[7],業(yè)界對(duì)這個(gè)問題進(jìn)行了廣泛的探討和研究[8~10],并取得一定的成果,但是目前沒有一個(gè)得到業(yè)界公認(rèn)的算法。本文采用小波變換對(duì)視頻鏡頭進(jìn)行切分并進(jìn)行關(guān)鍵幀提取,取得了較好的效果。如何動(dòng)態(tài)確定能量閾值和漸變寬度閾值(目前分別設(shè)定為總能量的99.5%和幀速率的1/2)是后續(xù)的研究?jī)?nèi)容。
[1] 朱莉樂,朱習(xí)軍,董國(guó)華.基于內(nèi)容的視頻檢索中的鏡頭分割算法[J].計(jì)算機(jī)與數(shù)字工程,2015,313(11):2047-2051.
ZHU Lile,ZHU Xijun,DONG Guohua.Shot Segmentation Algorithms in Content-Based Video Retrieval[J].Computer & Digital Engineering,2015,313(11):2047-2051.
[2] 熊偉,吳春明,姜明.使用線性分割和序列合并的視頻鏡頭分割方法[J].電子學(xué)報(bào),2014,42(4):640-645.
XIONG Wei,WU Chun-ming,JIANG Ming.Video Shot Segmentation Method Using Linear Segmentation and Sequences Combination[J]. Electronica Sinica,2014,42(4):640-645.
[3] MathWorks Inc. Wavelet Toolbox Getting Started Guide[M]. Natick:MathWorks Inc,2015:25-30.
[4] David K. Ruch. Wavelet Theory:An Elementary Approach with Applications[M]. New Jersey: John Wiley&Sons,Inc,2009:234-246.
[5] 俞璐,喬瑞萍,胡宇平等.基于顏色直方圖的快速鏡頭分割方法[J].微電子學(xué)與計(jì)算機(jī),2014,31(2):72-76.
YU Lu, QIAO Ruiping, HU Yuping,et al. A Fast Shot Boundary Detection Method Based on Color Histogram[J]. Microelectronics & Computer,2014,31(2):72-76.
[6] 印勇,侯海珍.基于直方圖幀差的自適應(yīng)鏡頭分割算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(9):186-189.
YIN Yong,HOU Haizhen. Adaptive shot segmentation method based on histogram frame difference[J].Computer Engineering and Applications,2010,46(9):186-189.
[7] H. J. ZHANG, J. H. WU, D. ZHONG. An Integrated System for Content-Based Video Retrieval and Browsing[J]. Pattern Recognition,1997,30(4):643-658.
[8] 黃茜,張海泉,楊文亮.基于灰度和直方圖的閾值自適應(yīng)鏡頭邊界檢測(cè)[J].科學(xué)技術(shù)與工程,2008,8(14):3787-3792.
HUANG Qian, ZHANG Haiquan, YANG Wenliang,et al.Gray Value and Histogram Based Shot Boundary Detection with Adaptive Threshold[J]. Science Technology and Engineering,2008,8(14):3787-3792.
[9] 瞿中,高騰飛,張慶慶.一種改進(jìn)的視頻關(guān)鍵幀提取算法研究[J].計(jì)算機(jī)科學(xué),2012,39(8):300-303.
QU Zhong,GAO Tengfei, ZHANG Qingqing.Study on an Improved Algorithm of Video Key Frame Extraction[J]. Computer Science,2012,39(8):300-303.
[10] 朱耀麟,李倩.視頻檢索常用的鏡頭分割方法的研究[J].電視技術(shù),2014,38(3):178-181.
ZHU Yaolin, LI Qian. Survey of Used Methods for Partitioning Video into Shots in Video Indexing[J]. Video Engineering,2014,38(3):178-181.
Wavelet-Based Video Shot Segmentation and Key Frame Extraction
WU Shaogen
(School of Computer Engineering, Guangdong Industry Technical College, Guangzhou510300)
Video shot segmentation and key frame extraction are the basis of content-based video retrieval. By using histogram vector to represent the video frame characteristics, the cosine angle value is used to represent the similarity of neighbouring frames and establish the similarity series, using the wavelet transformation to find the abrupt data point or data point set, camera shots can be founded in video. At last, the minimum standard deviation is used to extract the key frames in each shot. Experiment indicates that this method is effective and can find the camera shots, also the extracted key frames are effective too.
wavelet transformation, video stream, shot segmentation, key frame
2016年3月4日,
2016年4月26日
吳紹根,男,碩士,副教授,研究方向:模式識(shí)別、圖像處理和計(jì)算機(jī)視覺領(lǐng)域的研究與應(yīng)用。
TP391DOI:10.3969/j.issn.1672-9722.2016.09.040