基于空間金字塔的鏡頭檢測

1.北京信息科技大學 中文信息處理研究中心，北京 100101

2.北京拓爾思信息技術(shù)股份有限公司，北京 100101

1.北京信息科技大學 中文信息處理研究中心，北京 100101

2.北京拓爾思信息技術(shù)股份有限公司，北京 100101

1 引言

視頻是一種非結(jié)構(gòu)化、大信息量的數(shù)據(jù)，基于文本檢索的傳統(tǒng)方法人力財力耗費巨大，并且視頻內(nèi)容受個體主觀因素影響較大，因而基于內(nèi)容的視頻檢索（Content Based Video Retrieve，CBVR）成為研究熱點。鏡頭檢測是將隨時間變化的圖像流分割出內(nèi)容不同的一個個鏡頭，是CBVR的基礎(chǔ)，直接影響到檢索結(jié)果的準確性。鏡頭檢測（即鏡頭的邊界檢測），通過比較視頻幀的幀間差異，尋找鏡頭的邊界變化。

對鏡頭進行檢測，首先要解決的問題是何為一個鏡頭。一個鏡頭是由一個攝像機連續(xù)拍攝得到的時間上連續(xù)的若干幀圖組成[1]。

2 相關(guān)研究

鏡頭檢測，是根據(jù)視頻中圖像的內(nèi)容特征差異來區(qū)分，不同的鏡頭其圖像視覺內(nèi)容也不同，從而其圖像特征也會不同。因此，鏡頭檢測的效果很重要一部分是依賴于特征的選擇，在選擇檢測特征時需注意：（1）應(yīng)該體現(xiàn)出幀間的視覺差異；（2）對攝像機、物體運動有一定的魯棒性；（3）能有效克服或消除光照變化對檢測結(jié)果的影響。

文獻[2]采用直方圖變換率HCR（Histogram Change Ratio）法，其對單一的使用直方圖的方法進行了改進，仍然沒有考慮像素的位置信息，其效果也是有限的。文獻[3]將小波與神經(jīng)網(wǎng)絡(luò)結(jié)合進直方圖的方法，其運算量太大，對性能的限制大。文獻[4]使用了SVM進行鏡頭檢測，其也是用了HSV的顏色統(tǒng)計特征，也沒有用像素的位置信息特征；并且其需要對視頻進行抽樣取足夠大的訓練集進行訓練，確定分類的標準，通用性需要進一步考證，其實驗結(jié)果顯示對平移或運動較易誤檢。文獻[5]雖然考慮了像素特征，同時也考慮了像素位置信息，使用的是金字塔的思想，但是其使用的顏色直方圖的算法與人類的視覺感知不相符，而且其位置信息考慮過多，得到的效果不是很理想。所以本文提出了空間金字塔與直方圖結(jié)合的改進方法，既考慮像素的視覺信息又考慮像素的空間信息，相較于以上文獻在查全率和查準率上都有很大的提高。

3 空間金字塔

3.1 分塊空間金字塔

空間金字塔是一種考慮圖像的全局像素信息的方法。文獻[5]使用的是如圖1所示的空間金字塔方法。

圖1 空間金字塔及各層量化信息

從圖1可以看出，隨著層數(shù)的增加，分的小塊越來越多、越來越細，考慮的位置信息越來越多，相對地，每一塊的像素信息直方圖的劃分會越來越粗糙。算法如下：

圖像 f(x，y)在單個維度上像素所屬塊的位置確定為：

其中a表示行和列分的塊數(shù)（本文中要求行和列分的塊數(shù)相同），width和height表示圖像的寬和高。每個像素點對應(yīng)的塊編號為：

其中l(wèi)表示每個塊所要提取的特征向量的維數(shù)，bin∈[0，a2-1]。最后得到這一層的特征向量為：

其中H[bin+1]表示每個塊的圖像內(nèi)容特征的特征向量，i表示特征向量的下標索引。

較低的級的位置信息較少，可以去掉單個抖動和噪聲的干擾，越往級數(shù)高的層像素的位置信息考慮得越多，從而可以識別出相鄰的重復(fù)幀。

3.2 采樣空間金字塔

一種多尺度的的金字塔方法，通過計算不同分辨率的圖像信息來獲得圖像的多尺度表達，如圖2所示。

其思想是，對于一幅N×M的圖像，在行和列兩個方向上對其進行1∶2的亞采樣，可構(gòu)成原圖像的一幅(N/2)× (M/2)的縮略圖。將亞采樣重復(fù)進行，隨著層數(shù)的增加，每一層的圖像是下一層圖像的寬和高的一半，就得到構(gòu)成金字塔的各層圖像[6]。

在亞采樣過程中，可使用C(↓2)表示亞采樣算子，則幀圖像每一層的單個采樣用下式表示：

圖2 亞采樣金字塔

公式表明第k+1層的亞采樣圖像可由第k層的亞采樣圖像計算得出，其中符號“↓”后的數(shù)字表示亞采樣率，C是卷積模板，表示壓縮算子。

亞采樣可能會丟失一部分細節(jié)信息，圖像的質(zhì)量不能保證。實際應(yīng)用時，在采樣的過程中也可同步加入圖像的平滑，例如各種低通濾波器，像均值濾波器或高斯濾波器等。但是，鏡頭檢測不關(guān)注圖像的細節(jié)信息，只要有足夠的信息可以將不同鏡頭分開即可，所以本文不進行平滑運算，只取亞采樣操作，所構(gòu)成的金字塔是亞采樣金字塔。

4 鏡頭檢測

4.1 特征選擇

現(xiàn)在的視頻多以彩色為主，顏色又是圖像的一種非常重要的視覺特征，并且顏色特征以其定義明確、抽取容易，已經(jīng)在圖像檢索應(yīng)用中證明非常有效，所以本文采用顏色特征作為幀圖像的底層特征。HSV模型與人對顏色的感知接近，本文將HSV空間等間隔量化為8×4×4=128級，作為只含像素信息不含像素位置信息的直方圖特征。

本文使用均勻量化對HSV的三個分量進行量化。H(Hue)色調(diào)平均分為8個區(qū)間，從0°開始每45°劃分一個區(qū)間，分別對應(yīng)的量化編碼為0到7。S（Saturation）飽和度與V（Value）亮度均分為4個區(qū)間，分別為[0，0.25]，（0.25，0.5），（0.5，0.75），（0.75，1]，對應(yīng)于量化編碼為0到3。將HSV合成一維特征矢量是：G=16H+4S+V，其中G∈[0，127]。組成一個128維特征向量，再將特征向量進行歸一化處理。

4.2 空間信息選擇

根據(jù)前面的分析，空間金字塔可看成圖像中像素位置信息的一種表現(xiàn)形式，亞采樣表現(xiàn)的是空間中單個像素點之間的位置關(guān)系，塊分割表現(xiàn)的是像素的集合的位置關(guān)系。所以本文將兩種金字塔結(jié)合起來使用。經(jīng)過大量實驗觀察出，像素的空間位置信息是不可少的，否則其查準率到達一定程度后總是無法提向更高。但是如果考慮過多的位置信息，會受到小的物體運動的影響，其查全率就會急速地下降。

首先，將原幀圖像進行兩次亞采樣運算，分別得到Level 1和level 2兩層的圖像信息。接著將得到的Level 1的圖像均分成四塊，如圖1中的第二層所示。最后得到Level 2和Level 1的四個塊，及得到一個全局位置信息和四個局部位置信息，總共五個塊的信息。

4.3 鏡頭檢測

同一個鏡頭內(nèi)的各幀圖像的內(nèi)容大致相似，不同鏡頭內(nèi)的圖像內(nèi)容也存在比較大的不同。圖像的內(nèi)容相似度，根據(jù)其特征向量的相似度度量。根據(jù)像素的位置信息選擇，再提取顏色信息，整個圖像的特征提取過程如圖3所示。

圖3 直方圖特征提取過程圖

直方圖匹配的算法很多，本文使用既簡單又容易理解的直方圖相交的方法計算相似度。鏡頭檢測的總體算法步驟為：

步驟1將原圖像幀F(xiàn)i進行第一次降采樣操作，得到圖像Fi1。

步驟2根據(jù)分塊空間金字塔的算法，將Fi1的行與列各區(qū)二等分，總共分成大小相等的四塊像素區(qū)域，分別提取每一塊的HSV特征，得到整幅圖像的特征向量。

步驟3將圖像Fi2進行一次亞采樣，得到圖像Fi2，計算此圖像的hsv特征。

步驟4將以上步驟計算得到的兩個特征向量級聯(lián)，得到該幀總的特征向量。

步驟5使用直方圖相交算法計算幀間的相似度，大于閾值的認為是出現(xiàn)新的鏡頭，并提取作為關(guān)鍵幀。

5 實驗

5.1 實驗數(shù)據(jù)

本文采用信息檢索的通用評價方法，即使用查全率和查準率對鏡頭檢測進行評價，查全率（Recall）和查準率（Precision）分別表示為：

其中，Nc表示正確檢測到的鏡頭數(shù)，Nm表示漏檢的鏡頭數(shù)，Ne表示檢測到的錯誤的鏡頭數(shù)。

本文對多種視頻類型進行測試實驗，視頻多是從文獻[7]處下載，各個視頻的信息如表1所示。

表1 所用視頻信息

5.2 對比實驗

表2 實驗比較的部分數(shù)據(jù)

直方圖變化率HCR是文獻[2]提出的方法，文獻[5]中使用IOO三個變量表示其特征，所用本文中用IOO表示文獻[5]的方法，本文是使用的直方圖空間金字塔HSP（Histogram Space Pyramid）方法，所以用HSP表示本文方法，實驗結(jié)果如表2所示。表中所用到的符號說明：No.表示視頻序號，T表示閾值，R表示查全率，P表示查準率，N表示檢測出的鏡頭總數(shù)，Nc表示正確檢測到的場景數(shù)。

從圖4中的實驗結(jié)果可以推出，本文的方法與HCR方法相比，雖然查全率沒有HCR方法高，但是查準率卻比HCR的方法高很多。與IOO方法相比，查準率沒有IOO方法高，但是查準率卻比IOO方法高。HCR的準確率比較低的原因是，HCR根據(jù)的是視頻幀邊緣的改變率，對于圖像幀的像素位置信息考慮不足，將顏色直方圖分布相近，而內(nèi)容不同的鏡頭幀給丟失了。IOO方法的查全率比較差的原因是，其特征直方圖雖然也是根據(jù)像素顏色特征提出，但是與人的時間感知不太貼合，容易造成漏檢，而且其考慮像素的位置信息過多，對于運動比較敏感，將很多相同的鏡頭判定為不同的鏡頭，所以造成較多的漏檢。

圖4 各視頻的實驗結(jié)果對比圖

對于視頻檢測來說，查全率高而查準率低的方法，檢測出相同的鏡頭比較多，即冗余信息比較多，數(shù)據(jù)庫中冗余信息就會很多；而查準率高而查全率低的方法，檢測出的鏡頭會比較少，會丟失很多重要的鏡頭，對于視頻檢索的高層語義構(gòu)建不能提供足夠的信息。所以本文的方法是很有優(yōu)勢的，在閾值調(diào)整到比較合適的值時，可以使查全率和查準率都相對比較高，例如對于電影視頻查全率和查準率都可以在90%以上。

文獻[8]是使用小波變換算出視頻幀的顏色特征和紋理特征，再根據(jù)相鄰幀的顏色特征互信息與紋理特征的信息熵差計算相似度。雖然顏色特征體現(xiàn)的是像素的信息，紋理特征體現(xiàn)一定的像素位置信息，但是小波變換的計算復(fù)雜度太高，在實際中的應(yīng)用有限。文獻[9]是使用小波分析與統(tǒng)計量綜合的方法，對于小的運動誤檢嚴重，而且同樣的計算量很大，不實用。文獻[10]是使用SIFT特征進行鏡頭的檢查，雖然SIFT特征在匹配過程中效果還可以，但是其運行速度是讓人難以接受的，一個普通的1小時視頻，處理大概要2天以上，無法實現(xiàn)web實時服務(wù)的要求。

綜合考慮，本文的優(yōu)點是：（1）既考慮像素信息，又考慮了像素的位置信息；（2）既考慮了像素位置的全局特性，又考慮了其局部特性；（3）對視頻中物體的運動有好的魯棒性；（4）均衡考慮了查全率與查準率兩個屬性；（5）算法簡單直觀，有較高的實用價值。

6 總結(jié)與展望

本文方法對顏色直方圖的方法進行了改進，將空間金字塔與HSV顏色直方圖結(jié)合。有實驗結(jié)果得出，在取合適的閾值的時候，其綜合檢索效果比HCR和IOO方法好一些。從實驗結(jié)果可以分析出，查全率與查準率之間會存在一個權(quán)衡，根本原因在于圖像的像素信息與像素的位置信息之間存在一定的取舍關(guān)系，考慮的位置信息過多雖然可以提高查準率，但是可能會造成漏檢情況比較嚴重。所以，對于位置信息的考量可以作為今后研究的重點。

[1]章毓晉.基于內(nèi)容的視覺信息檢索[M].北京：科學出版社，2003：221-223.

[2]秦劍鵬，符茂勝，涂錚錚，等.基于顏色直方圖變化率的視頻鏡頭檢測[J].計算機應(yīng)用與軟件，2011，28（4）：17-20.

[3]周順勇.基于小波神經(jīng)網(wǎng)絡(luò)的鏡頭檢測[D].成都：電子科技大學，2009.

[4]盧悅.基于內(nèi)容的視頻鏡頭檢測與分類研究[D].山東：山東師范大學，2010.

[5]Chum O，Philbin J，Isard M，et al.Scalable near identical image and shot detection[C]//Proceedings of the 6th ACM International Conference on Image and Video Retrieval.New York， USA：ACM，2007：549-556.

[6]章毓晉.圖像工程（上冊）圖像處理[M].北京：清華大學出版社，2006.

[7]The open video project[EB/OL].[2011-07-11].http：//www.openvideo.org/.

[8]李玉峰，趙政.基于特征信息的鏡頭檢測研究[J].計算機工程與應(yīng)用，2009，45（6）：168-169.

[9]葉軍，吳菲，李建良.基于綜合相似度的二次差分法在鏡頭檢測中的應(yīng)用[J].計算機工程與科學，2008，30（3）.

[10]劉根濤.基于內(nèi)容的視頻結(jié)構(gòu)分析[D].北京：北京郵電大學，2010.

基于空間金字塔的鏡頭檢測

都云程1，2，任紹美1，王 濤1，2，呂學強1，2

DU Yuncheng1，2,REN Shaomei1,WANG Tao1，2,LV Xueqiang1，2

1.Chinese Information Processing Research Center,Beijing Information Science and Technology University,Beijing 100101,China
2.Beijing TRS Information Technology Co.,Ltd.,Beijing 100101,China

In this paper,it proposes a new method,which takes into account both pixels’information and its location,combining the HSV histogram and the spatial pyramid of pixels to detect shots.A sub-sampling image,which is the first layer of the sub-sampling pyramid,is evenly split to four blocks.It is to extract color features from the four blocks respectively.Making another sub-sampling is to get a second layer image,and it extracts the color feature.It is to connect five vectors to be this frame image’s color feature,and calculate the similarity of adjacent frames.This algorithm considers not only the pixel information, but also the location information both of the global and local ones.Experimental results show that this method gives a better balance about recall and precision rates.

spatial pyramid;sub-sampling;blocking;histogram

提出一種HSV顏色直方圖與像素的位置空間金字塔結(jié)合的方法，該方法既考慮像素的信息，又考慮了像素的位置信息，來進行視頻鏡頭分割。將圖像進行一次亞采樣，對得到的第一層亞采樣圖像進行均勻的四分割；對得到的四塊小區(qū)域分別計算其顏色直方圖，獲得四個特征向量；將第一層亞采樣的圖像再進行一次亞采樣，得到第二層亞采樣圖像，并計算其顏色特征向量；將五個特征向量級聯(lián)，作為圖像幀的特征，并計算相鄰兩個幀的相似度。該算法不僅考慮了像素信息，還考慮了像素位置信息，而且考慮的是全局位置信息和局部位置信息。實驗結(jié)果顯示，該方法較好地權(quán)衡了查全率和查準率。

空間金字塔；亞采樣；分塊；直方圖

A

TP37

10.3778/j.issn.1002-8331.1111-0146

DU Yuncheng,REN Shaomei,WANG Tao,et al.Shot detection based on spatial pyramid.Computer Engineering and Applications,2013,49（11）：187-190.

國家自然科學基金（No.60872133）；北京市自然科學基金（No.4092015）；北京市教委科技發(fā)展計劃項目（No.KM201110772021）；國家科技支撐計劃課題（No.2011BAH11B03）。

都云程（1967—），男，高級工程師，主要研究領(lǐng)域為中文信息處理、信息檢索與Web應(yīng)用；任紹美（1986—），女，碩士在讀。E-mail：renshaomei2008@126.com

2011-11-09

2012-01-17

1002-8331（2013）11-0187-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1721.068.html