吳紹根

(廣東輕工職業(yè)技術(shù)學(xué)院計算機工程系　廣州　510300)

?

基于小波變換的視頻流鏡頭切分及關(guān)鍵幀提取*

吳紹根

(廣東輕工職業(yè)技術(shù)學(xué)院計算機工程系廣州510300)

視頻鏡頭切分及關(guān)鍵幀提取是基于內(nèi)容的視頻檢索的基礎(chǔ)。通過使用色彩直方圖向量來表征視頻幀特征,使用余弦夾角來度量視頻幀的相似性并建立相鄰視頻幀的相似性數(shù)據(jù)序列,再通過小波變換尋找其中的突變數(shù)據(jù)點或數(shù)據(jù)點集來完成對視頻鏡頭的切分,最后通過最小直方圖特征標(biāo)準(zhǔn)差在每個鏡頭中提取關(guān)鍵幀。實驗表明,該方法能有效地找到鏡頭的邊界,所提取的關(guān)鍵幀可以表達鏡頭的主要內(nèi)容。

小波變換; 視頻; 鏡頭切分; 關(guān)鍵幀

Class NumberTP391

1　引言

基于內(nèi)容的視頻檢索是當(dāng)前視頻檢索領(lǐng)域的研究熱點[1]。對視頻的檢索顯然不能使用傳統(tǒng)的基于文字的方式進行,而只能對視頻進行特征抽取,建立視頻的特征信息,并在此基礎(chǔ)上進行基于視頻特征的檢索。為了建立視頻特征信息,需要首先對視頻進行結(jié)構(gòu)進行分析。

視頻的基礎(chǔ)結(jié)構(gòu)從語義角度由下至上劃分為: 幀、鏡頭、場景、視頻。在視頻結(jié)構(gòu)化研究中,其主要內(nèi)容是以鏡頭為單位對視頻內(nèi)容進行劃分,即鏡頭切割或切分[2],然后在分割的視頻段內(nèi)提取關(guān)鍵幀,在此基礎(chǔ)上才能進行后續(xù)的工作,例如基于內(nèi)容的視頻檢索等。

視頻鏡頭的切換包括突變切換和漸變切換兩種類型。突變切換是指將鏡頭直接從一個鏡頭切換到另一個鏡頭,中間沒有過濾幀；而漸變切換則從一個鏡頭切換到另一個鏡頭時,中間包括一些過濾幀。所謂鏡頭切分,就是從視頻流中找到這些鏡頭的切換點。而關(guān)鍵幀提取則是從已經(jīng)切分的視頻鏡頭中提取最能代表各個視頻鏡頭的圖像幀。

本文提出一種基于Daubechies小波變換的視頻鏡頭切分方法和基于最小標(biāo)準(zhǔn)差的鏡頭關(guān)鍵幀提取方法。實驗結(jié)果表明,本文所介紹的方法在鏡頭切分上優(yōu)于線性切分算法,同時,從視覺判斷上,本文方法所提取的鏡頭關(guān)鍵幀能較好地反映視頻鏡頭的主要內(nèi)容。本文后續(xù)內(nèi)容將從算法的數(shù)學(xué)模型、算法描述、實驗結(jié)果及其分析幾個方面對算法進行介紹。

2　算法的數(shù)學(xué)模型

在進行算法設(shè)計之前,首先對算法中涉及到的數(shù)學(xué)模型進行介紹,包括：視頻幀特征表示方式、視頻幀相似性度量方法、使用小波變換檢測視頻幀突變及漸變的方法和鏡頭關(guān)鍵幀度量的方式。

2.1視頻幀的特征表示

為了進行視頻鏡頭切分,需要首先建立視頻幀的特征表示并依據(jù)所建立的特征進行視頻幀的相似性計算。由于色彩直方圖能夠從全局的層面表示視頻幀的特征,因此,本文采用色彩直方圖建立視頻幀的特征。建立視頻幀的特征過程包括兩個步驟：第一步,對彩色視頻幀進行灰度化處理；第二步,構(gòu)建視頻幀的灰度直方圖向量。

2.1.1對視頻幀進行灰度化處理

由于現(xiàn)有的大多數(shù)視頻都是彩色視頻,因此,在建立視頻的特征信息之前,需要對視頻幀進行灰度化處理。采用如下的計算方法進行RGB的彩色視頻幀到灰度視頻幀的轉(zhuǎn)換：

GL=0.2989*R+0.5870*G+0.1140*B

(1)

其中,R、G、B分別表示原像素點的紅、綠、藍的值。

2.1.2構(gòu)建視頻幀的灰度直方圖特征

對彩色視頻幀進行灰度化處理后,視頻幀的每個像素點的值都在0～255這個區(qū)間。對每一個視頻幀,統(tǒng)計每一級灰度的像素個數(shù),進而得到的一個256維的向量,這個向量稱為灰度直方圖向量,本文將這個向量作為視頻幀的特征。視頻幀的灰度直方圖計算方法如下：

HG=〈v0,v1,v2,…,v255〉

(2)

其中,vb(0≤b≤255)表示灰度為b的像素點個數(shù),vb的計算方法如下：

其中,M表示視頻幀的高度,N表示視頻幀的寬度,Pi,j表示在(i,j)空間位置上像素點的灰度值,b表示從0～255的一個灰度級。δ是符號函數(shù),其定義如下：

2.2建立視頻幀的相似性度量序列

通過為每一幀視頻幀計算其灰度直方圖,建立了每一視頻幀的特征表示。然后,采用向量的余弦夾角來度量視頻幀的相似度,計算方法如下：

(3)

其中,HGi、HGj分別表示第i個視頻幀與第j個視頻幀的灰度直方圖向量,〈HGi,HGj〉表示向量HGi與向量HGj的內(nèi)積,|HGi|、|HGj|分別表示向量HGi與向量HGj的模長。

對視頻的所有相鄰視頻幀進行相似度計算,得到如下所示的相鄰視頻幀的相似性離散序列SM：

SM=(SM〈1,2〉,SM〈2,3〉, …,

SM〈i,i+1〉,…,SM〈n-1,n〉)

(4)

其中,n表示視頻的總幀數(shù),所建立的視頻幀相似度序列是一個具有n-1個元素的序列。視頻鏡頭分割的目標(biāo)就是從該序列中找到發(fā)生突變或漸變的數(shù)據(jù)點或數(shù)據(jù)點集。本文采用消失矩為2的Daubechies小波db2來檢測這些數(shù)據(jù)點或數(shù)據(jù)點集。

2.3利用db2小波變換檢測突變或漸變數(shù)據(jù)點或數(shù)據(jù)點集

2.3.1小波變換

小波變換是繼傅里葉變換之后的又一個有力的數(shù)學(xué)工具,它解決了傅里葉變換導(dǎo)致時域信息丟失的問題。小波變換能從時域及頻域兩個維度來觀察一個函數(shù)或一個數(shù)據(jù)序列的變化性質(zhì)。小波變換如下式所示[3]：

(5)

其中,f(t)是被變換的函數(shù),ψ(t)為小波函數(shù),*表示函數(shù)的復(fù)數(shù)共軛。從上式可以看出,小波變換將函數(shù)f(t)映射為一個二元函數(shù)C(a,b),其中,a表示尺度,b表示時移。小波變換的實質(zhì)就是計算函數(shù)f(t)與特定的小波函數(shù)在尺度為a和時移為b時的相關(guān)度。如果將尺度參數(shù)a和移位參數(shù)b的選取以2的冪次方的方式離散取值,即可得到離散小波變換。離散小波變換可采用矩陣形式計算。本文采用消失矩為2的Daubechies小波db2來檢測視頻幀相似序列的突變點或漸變點集。

2.3.2構(gòu)建db2小波變換矩陣

小波變換矩陣包括兩個矩陣：分解矩陣和重組矩陣。

小波變換的分解矩陣由低通濾波矩陣和高通濾波矩陣兩個子矩陣構(gòu)成,其中低通濾波矩陣由低通濾波器參數(shù)通過逐行移位2列而構(gòu)成,高通濾波矩陣則由高通濾波器通過逐行移位2列構(gòu)成,在矩陣的最后一行需要進行回卷；由于所構(gòu)建的小波分解矩陣是一個單位正交矩陣,因此,小波變換的重構(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是一個N×N的矩陣,其中N表示需要進行變換的數(shù)據(jù)的維度。由于WN是一個正交單位矩陣,因此,重構(gòu)矩陣就是WN的轉(zhuǎn)置,即：

利用這一性質(zhì)可以方便的計算小波逆變換。

2.3.3對相鄰視頻幀的相似性序列SM的分解和對細(xì)節(jié)的重構(gòu)

應(yīng)用構(gòu)建的db2小波分解矩陣WN對相鄰視頻幀相似序列SM進行分解,得到相似性近似序列系數(shù)A和細(xì)節(jié)序列系數(shù)D,如下所示：

(7)

其中的細(xì)節(jié)序列系數(shù)D的維度是SM維度的1/2,它表示數(shù)據(jù)序列SM中的突變成分。為了過濾掉D中的微小波動,采用累積能量法對細(xì)節(jié)序列系數(shù)D進行處理。數(shù)據(jù)序列累積能量的計算方式如下：

(8)

其中v是要進行累積能量計算的原數(shù)據(jù)序列或向量,y是對v的每個元素取絕對值后,從大到小排序而形成的數(shù)據(jù)序列。|y|是數(shù)據(jù)序列的y模長。本文選擇保留原數(shù)據(jù)能量99.5%的元素值作為閾值對細(xì)節(jié)序列系數(shù)D進行過濾,得到經(jīng)過過濾處理后的細(xì)節(jié)序列系數(shù)D′。

由于只需要從原數(shù)據(jù)序列找到突變點或突變點集,因此,可以將近似序列系數(shù)A全部設(shè)置為0,然后與細(xì)節(jié)序列系數(shù)D′構(gòu)成向量來重構(gòu)細(xì)節(jié)序列,細(xì)節(jié)重構(gòu)的計算方式如下：

(9)

其中0表示元素全為0的向量。由上式(8)得到的數(shù)據(jù)序列D*就是相鄰視頻幀的相似性序列SM的變化點。下一步,需要對D*進行精化,從中找到視頻幀的突變點和漸變點集。

2.4通過精化來確定視頻幀的突變點和漸變點集

細(xì)節(jié)序列D*中的非0點就是發(fā)生變化的點。這些變化的點由兩類點構(gòu)成：鏡頭的突變點和由于鏡頭漸變而導(dǎo)致的一系列具有序列連續(xù)的變化點。考慮到漸變的過渡特性,設(shè)定當(dāng)兩個變化點的間隔小于視頻幀速率的1/2時,則認(rèn)為這兩個相鄰的變換點之間的視頻幀為漸變過渡幀。在進行鏡頭切分時,舍棄這些過渡幀,取過渡幀的兩邊邊界幀作為視頻鏡頭的切分點,這將有利于更為有效地提取鏡頭關(guān)鍵幀。

2.5鏡頭關(guān)鍵幀的提取

有句俗語叫做“多姿多彩”,其含義是一幅多姿多彩的圖像包含有更多的信息。一幅多姿多彩的圖像在數(shù)學(xué)上的度量可以表達為圖像的灰度直方圖的標(biāo)準(zhǔn)差達到最小。為此,本文在為各個視頻鏡頭中選取關(guān)鍵幀時,選取具有最小標(biāo)準(zhǔn)差的視頻幀作為視頻鏡頭的關(guān)鍵幀。視頻幀灰度直方圖標(biāo)準(zhǔn)差的計算方式如下：

(10)

xi(0≤i≤255)是視頻幀直方圖向量的元素。

3　算法設(shè)計

依據(jù)第2節(jié)的數(shù)學(xué)模型及其相關(guān)的計算方法,本文設(shè)計了對視頻流進行鏡頭切分及關(guān)鍵幀提取算法。為了簡化算法描述,算法中所提及的公式是指第2節(jié)中的相應(yīng)編號的公式。

算法名稱：視頻流進行鏡頭切分及關(guān)鍵幀提取

輸入：視頻流

輸出：鏡頭切分區(qū)間及各鏡頭區(qū)間的關(guān)鍵幀編號

算法描述：

①對視頻流中的每一視頻幀 do

利用式(1)對該視頻幀進行灰度化處理；

利用式(2)計算該視頻幀的灰度直方圖特征；

if 不是第一幀視頻幀

利用式(3)計算該視頻幀的灰度直方圖與前一視頻幀的相似度；

end if

end do

②利用式(4)建立相鄰視頻幀的相似度序列SM；

③利用式(6)建立db2小波變換矩陣WN；

④利用式(7)對SM進行小波分解,得到細(xì)節(jié)系數(shù)D；

⑤利用式(8)對D進行累計能量計算,利用得到的閾值對D進行過濾,得到D‘；

⑥利用式(9)得到細(xì)節(jié)序列D*；

⑦對D*進行精化,丟棄漸變幀,確定鏡頭邊界,并將結(jié)果存儲為如下形式：

[(開始幀,結(jié)束幀),(開始幀,結(jié)束幀),……,(開始幀,結(jié)束幀)]

⑧利用式(10)在每個視頻鏡頭中選取關(guān)鍵幀,并存儲關(guān)鍵幀編號為如下形式：

[ 第一個鏡頭的關(guān)鍵幀編號,第二個鏡頭的關(guān)鍵幀編號,…… ]

⑨返回鏡頭切分的結(jié)果和關(guān)鍵幀提取的結(jié)果。

4　算法實驗及結(jié)果分析

為了測試算法的有效性,本文使用Matlab實現(xiàn)了算法,并從三個方面做了實驗：對視頻突變和漸變的檢測能力、視頻鏡頭切分的有效性、視頻鏡頭關(guān)鍵幀的提取有效性。

4.1對視頻突變和漸變的檢測能力分析

為了測試算法對視頻突變和漸變的檢測能力,本文對一段由7個鏡頭組成,時長為30s共901幀的測試視頻采用本文的算法求出其細(xì)節(jié)序列D*。然后,對該視頻進行人工編輯,在第1和第2個鏡頭中加入淡入/淡出(Fade In/Fade Out)漸變,在第6和第7個鏡頭之間加入了掃換(Wipe)漸變,再利用本文算法求出編輯后的視頻的細(xì)節(jié)序列D*,結(jié)果如圖1所示。

圖1　算法對突變和漸變的檢測有效性測試結(jié)果

從圖1可以看出,本文算法能夠檢測出視頻鏡頭的切變,同時,在加入了漸變的視頻的細(xì)節(jié)序列中,可以清晰地觀察到在視頻的第1和第2個鏡頭間及第6和第7個鏡頭間的細(xì)節(jié)序列比原始視頻具有更寬的變化序列,因此,本文算法也能檢測到視頻的漸變鏡頭。不僅如此,通過對這些連續(xù)變化序列的精化,可以在鏡頭切分時,丟棄這些漸變視頻幀,使得鏡頭的切分和關(guān)鍵幀的提取更為合理。

4.2對視頻鏡頭切分的有效性分析

為了驗證算法對視頻鏡頭切分的有效性,將本文算法與線性切分算法[5]進行比較,使用信息檢索中最常用的度量指標(biāo)“查全率”和”查準(zhǔn)率”來衡量鏡頭切分的結(jié)果[6],計算公式如下：

并采用綜合因子對算法的整體效果進行度量,綜合因子的計算公式如下：

用于測試視頻數(shù)據(jù)包括一段媒體演示視頻、一段廣告視頻、一段新聞視頻、一段電影片段和一段自行拍攝的視頻,實驗結(jié)果如表1和圖2所示。

表1　查全率和查準(zhǔn)率實驗結(jié)果

圖2　算法的切分有效性對比

圖2中的視頻類型1、2、3、4、5分別是媒體演示視頻、新聞視頻、廣告視頻、電影片段視頻和自行拍攝的視頻。在實驗時,以第一段媒體演示視頻為基礎(chǔ)調(diào)試并設(shè)定相關(guān)閾值參數(shù),該參數(shù)使得對第一段媒體演示視頻的查全率和查準(zhǔn)率均達到100%,然后,以得到的閾值為參數(shù)對其他的視頻進行切分。從表1和圖2可以看出,無論從查全率、查準(zhǔn)率及從綜合因子對整體效果進行度量,本文算法均優(yōu)于線程切分算法。

4.3對視頻鏡頭關(guān)鍵幀提取的有效性分析

目前沒有一個通用的可以定量度量視頻關(guān)鍵幀提取質(zhì)量的計算標(biāo)準(zhǔn),因此,對視頻關(guān)鍵幀提取的有效性分析還僅限于直觀觀察。實驗中,利用本文的算法對某媒體演示視頻進行鏡頭分割并提取每個鏡頭的關(guān)鍵幀。該視頻時長為30s,共有901幀,7個鏡頭轉(zhuǎn)換,圖3是鏡頭切分及關(guān)鍵幀的提取結(jié)果,從直覺觀察判斷,算法提取的視頻關(guān)鍵幀能夠反映每個鏡頭的主要內(nèi)容。

圖3　某媒體演示視頻的關(guān)鍵幀提取結(jié)果

5　結(jié)語

對視頻鏡頭的切分和對關(guān)鍵幀的提取是基于內(nèi)容的視頻檢索的基礎(chǔ),自被提出以來[7],業(yè)界對這個問題進行了廣泛的探討和研究[8～10],并取得一定的成果,但是目前沒有一個得到業(yè)界公認(rèn)的算法。本文采用小波變換對視頻鏡頭進行切分并進行關(guān)鍵幀提取,取得了較好的效果。如何動態(tài)確定能量閾值和漸變寬度閾值(目前分別設(shè)定為總能量的99.5%和幀速率的1/2)是后續(xù)的研究內(nèi)容。

[1] 朱莉樂,朱習(xí)軍,董國華.基于內(nèi)容的視頻檢索中的鏡頭分割算法[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é)報,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é)與計算機,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].計算機工程與應(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)鏡頭邊界檢測[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] 瞿中,高騰飛,張慶慶.一種改進的視頻關(guān)鍵幀提取算法研究[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日

吳紹根,男,碩士,副教授,研究方向：模式識別、圖像處理和計算機視覺領(lǐng)域的研究與應(yīng)用。

TP391DOI:10.3969/j.issn.1672-9722.2016.09.040