黃永鋒，熊澤東，王紹宇

（東華大學 計算機科學與技術學院，上海 201620）

基于DCE算法的壓縮域視頻鏡頭分割方法

黃永鋒，熊澤東，王紹宇

（東華大學 計算機科學與技術學院，上海 201620）

鏡頭分割是視頻檢索的結構化基礎，為此提出一種高效的視頻鏡頭分割方法.首先，在壓縮域中提取視頻流中I幀攜帶的特征信息，并生成幀間特征分布曲線；然后，利用離散曲線演化（DCE）算法對預處理過的曲線進行分析與演進；最后，分割出視頻鏡頭并提取關鍵幀.試驗結果表明：該方法充分考慮了視頻編碼的時序特點，具有較好的分割效果，魯棒性強.

壓縮域；鏡頭分割；關鍵幀；DCE算法

隨著多媒體技術的飛速發(fā)展，視頻數(shù)據(jù)量呈現(xiàn)爆炸式增長，而視頻信息又具有海量性和無序性的特點.如何對這種非結構化數(shù)據(jù)進行有效的組織、管理、索引與查詢是一個關鍵問題，視頻檢索技術為解決這一問題提供了可行途徑，并已成為近年來的研究熱點，而鏡頭分割更是研究的焦點.在視頻索引與檢索系統(tǒng)中，把具有相同語義的鏡頭自動分類并有效組織，為用戶檢索提供合理的反饋信息［1］.

鏡頭是視頻的基本結構單元和內(nèi)容表示單元，根據(jù)視頻的變換方式鏡頭可以分為切變（cut）和漸變（gradual transition）兩種.壓縮域的視頻鏡頭分割根據(jù)其使用的信息不同主要分為兩類：一類比較幀的 DCT（discrete cosine transform）系數(shù)［2－4］；另一類則比較幀宏塊的運動補償信息［5－7］.前者主要使用視頻流中I幀的信息，根據(jù)國際視頻編碼標準MPEG（moving pictures experts group）規(guī)定大約每13幀中有一I幀，因此，該類方法資源消耗少，時間效率高；而相比之下，后者需比較所有幀的宏塊信息，時間效率低，計算量大.本文考慮到處理效率問題，選用前者進行數(shù)據(jù)處理.

鏡頭的檢測方法也大致分為兩類：一是基于閾值的方法［8－9］，這種方法比較簡單，程序上容易實現(xiàn)；二是基于機器學習的方法［10－11］，在這種方法中，一般是通過訓練得到視頻變換的特有統(tǒng)計模型去實現(xiàn)視頻變換檢測，該方法能有效檢測出漸變，但是復雜度較大.與上述兩類方法不同，本文不直接對視頻數(shù)據(jù)進行處理，而是應用文獻［12］提出的DCE（discrete curve evolution）算法，通過輪廓消解的方法對視頻特征分布曲線進行處理來實現(xiàn)視頻鏡頭分割與關鍵幀提取.

1 壓縮域視頻特征描述

在視頻壓縮編碼中，MPEG標準以GOP（group of pictures）為編碼單元，其結構如圖1所示.GOP主要由3種幀組成，分別為I幀、B幀和P幀，其中B幀和P幀采用運動補償機制的幀間編碼方式，而I幀采用幀內(nèi)編碼.因此，可以直接在視頻流中通過熵解碼、反量化的方法獲得I幀的DCT系數(shù)，方便快捷地提取所攜帶的視頻信息，而其他兩種幀則不能直接提取DCT系數(shù).

圖1 GOP結構圖Fig.1 The GOP structure

對于MPEG壓縮域的視頻特征提取，最自然的解決方法是利用與基色調(diào)相關的DC（direct current）系數(shù)和與紋理相關的 AC（alternating current）系數(shù)，即用MEPG數(shù)據(jù)流中的離散余弦變換的直流分量來提取視頻幀的基色調(diào)，用交流分量來提取幀的紋理信息.定義式（1）和（2）分別用來量化I幀的特征信息及其差值.

其中：Cn和Sim （Cn，Cn＋1）分別為第n幀的特征量及其差值；DCn（i，j）和ACn（i，j）分別為第n幀的第（i，j）個子塊的基色調(diào)和紋理信息；α和β分別為基色調(diào)和紋理信息對幀特征的影響因子，且滿足α＋β＝1（α＞β，α，β∈［0，1］），本文中α和β分別取值為0.75和0.25.由于一個子塊有63個AC系數(shù)，考慮到計算量及紋理信息分布特點，此處只選取Zigzag掃描順序的前9個最大值.

2 鏡頭分割方法

通過上述提取的視頻特征差值并不能直接應用于下文的鏡頭分割，因為同一鏡頭內(nèi)幀的特征量具有很大的相似性，數(shù)據(jù)波動性很小，這些數(shù)據(jù)對鏡頭分割意義不大，可以看成是噪聲，需要對其進行預處理來簡化后續(xù)操作.然后，對預處理后的數(shù)據(jù)曲線應用DCE算法實現(xiàn)鏡頭分割及關鍵幀提取.

2.1 數(shù)據(jù)預處理

首先通過高斯濾波除去數(shù)據(jù)中的噪聲，然后求取曲線局部的谷值與峰值，并通過連接谷值與峰值點的方法重繪曲線.為了求取曲線局部的谷值與峰值，采用類似數(shù)學理論中求解曲線局部極值的方法，計算相鄰兩點的微增量dxi，若dxi×dxi＋1＜0，則說明第i幀處存在谷點或峰點.

2.2 DCE算法

DCE算法［12］是以類比發(fā)散方程為導向，除去那些對曲線整體特征沒有影響或者影響較小的曲線段，并保留曲線整體特征的曲線演進算法.首先，把曲線分成m 段，即Dm＝s0，s1，…，sm－1；然后，計算相鄰兩段曲線的權值K（si，si＋1）來確定該段曲線對曲線整體輪廓的影響大小；最后，根據(jù)關鍵點數(shù)N來控制程序的循環(huán)次數(shù)，程序每循環(huán)一次都會合并掉K（si，si＋1）最小的曲線段.DCE算法流程如圖2所示.

圖2 DCE算法流程圖Fig.2 Flowchart of the DCE algorithm

為了同時考慮特征差值和幀間距對曲線的總體波動性的影響，確定權值K（si，si＋1）的計算式如式（3）所示.

其中：Smax為相鄰兩曲線段中最大特征差值；Lmax為曲線段的起始點與結束點間的幀間距.

2.3 鏡頭分割及關鍵幀提取方法描述

對一段MPEG視頻流的輸入，鏡頭和關鍵幀的輸出按下述步驟進行：

Step 1 在視頻流中提取I幀的DCT系數(shù)，并依據(jù)式（1）和（2）分別計算由基色調(diào)和紋理信息表征的幀特征量和特征差值；

Step 2 對Step 1提取的視頻幀特征差值進行高斯濾波去除數(shù)據(jù)中的噪聲，然后對濾波處理后的數(shù)據(jù)曲線求谷值與峰值點；

Step 3 根據(jù)谷值與峰值點生成新的數(shù)據(jù)曲線圖，并對其應用DCE算法進行處理，然后得到滿足關鍵點數(shù)的曲線圖；

Step 4 依據(jù)Step 3生成的目的曲線圖實現(xiàn)鏡頭分割和關鍵幀提取，曲線圖中的峰值點說明鏡頭內(nèi)容發(fā)生了極大變化，而谷值點說明幀間內(nèi)容變化較小，相對穩(wěn)定，相似性極強，可作為代表鏡頭內(nèi)容的關鍵幀.

以New Indians（Segment 004）視頻段為例，該視頻段共有2 572幀.首先，在壓縮域提取視頻中I幀的特征值及特征差值，其分布如圖3和4所示，圖4中存在大量噪聲；然后，預處理特征數(shù)據(jù)，生成圖5，噪聲被濾除，谷值、峰值點明顯；最后，對預處理數(shù)據(jù)應用DCE算法，得到目的特征數(shù)據(jù)分布如圖6所示，關鍵點數(shù)N設為40.圖6中峰值點對應鏡頭變化處，谷值點為關鍵幀；橢圓標記點的峰值相對較小，但幀間距較大，說明發(fā)生鏡頭漸變.

3 試驗結果與分析

試驗選用北卡羅萊納大學信息與圖書館學院的開放式數(shù)字視頻庫 （http：//www.open－video.org）作為視頻測試集，并通過 Matlab R2008（b）編程實現(xiàn).試驗環(huán)境為Windows XP SP3，硬件配置為Pentium（R）Dual－Core CPU，主頻2.10GHz，2GB內(nèi)存.為了評價本算法性能，采用查全率（Recall）和查準率（Precision）作為評價指標［13］，定義如式（4）和（5）所示.

其中：Nc，Nm和Nf分別表示正確檢測鏡頭數(shù)、漏檢鏡頭數(shù)和誤檢鏡頭數(shù).

采用式（6）自適應地確定曲線的關鍵點數(shù)N.

其中：θ為加權因子，取值范圍一般為［1.0，1.5］；Si的取值如式（7）所示.

對所選用視頻庫中的視頻數(shù)據(jù)進行試驗，并將本文算法與文獻［4］中的鏡頭檢測算法進行了比較，結果如表1所示.

表1 鏡頭分割結果數(shù)據(jù)統(tǒng)計表Table 1 The results of shot segmentation

由表1可知，本文結合DCE算法對壓縮域視頻鏡頭進行檢測與分割，取得了令人滿意的效果，查全率和查準率較文獻［4］都有很大的提高，其中，切變鏡頭的查全率和查準率的平均值都達到了90%以上，漸變鏡頭的查全率和查準率的平均值也在80%以上.本文算法對視頻庫中的視頻有普遍適用性，魯棒性較強.

4 結 語

本文算法在壓縮域對視頻流中I幀所攜帶的特征信息進行量化、比較與分析，并結合DCE算法的應用來實現(xiàn)鏡頭直觀快速的分割，且可以方便地提取視頻鏡頭關鍵幀.該算法充分地考慮了視頻編碼的時序特點，能夠準確有效地檢測鏡頭的切變和漸變，適用范圍廣、魯棒性強，并且資源消耗少.

［1］王鵬，楊士強，劉志強.信息論聯(lián)合聚類算法及其在視頻鏡頭聚類中的應用［J］.計算機學報，2005，28（10）：1693－1699.

［2］YEO B L，LIU B.On the extraction of DC sequences from MPEG compressed video ［C］//Proceedings of the 1995 International Conference on Image Processing.Washington：IEEE Computer Society，1995：260－263.

［3］智敏，蔡安妮.基于基色調(diào)的鏡頭邊界檢測方法［J］.自動化學報，2007，33（6）：654－657.

［4］WANG J Y，LUO W.A self－adapting dual－threshold method for video shot transition detection［C］//IEEE International Conference on Networking，Sensing and Control.Sanya，2008：704－707.

［5］NANG J H，HONG S W，IHM Y G.An efficient video segmentation scheme for MPEG video stream using macro block information ［C］//Proceeding of the seventh ACM International Conference on Multimedia.New York，1999：23－26.

［6］CHAU W S，AU O C，CHAN T W，et al.Optimal key frame selection using visual content metric［C］//2005International Conference on Communications circuits. New York：Association for Computing Machinery，2005：551－555.

［7］CALIC J，IZQUIERDO E.Efficient key－frame extraction and video analysis ［C ］//Proceedings of the International Conference on Information Technology：Coding and Computing.Washington：IEEE Computer Society，2002：28－33.

［8］ZHAO N，LV N，LIU H Y.Content－based cut shot detecting algorithm of news video ［J］.Journal of Jilin University：Information Science Edition，2009，27（1）：50－55.

［9］WANG Y，WEN X M，LIN X Q，et al.A novel video shot segmentation based on textural features［C］// 2009Fifth International Conference on Information Assurance and Security.Xi'an：IEEE Computer Society，2009：119－122.

［10］LI L，ZENG X L，LI X，et al.Video shot segmentation using graph－based dominant－set clustering［C］//Proceedings of the First（ACM）International Conference on Internet Multimedia Computing and Service.New York，2009：166－169.

［11］CAO J R，CAI A N.Algorithm for shot boundary detection based on support vector machine in compressed domain ［J］.Acta Electronic Sinica，2008，36（1）：203－208.

［12］LATECKI L J，LAKIMPER R.Convexity rule for shape decomposition based on discrete contour evolution ［J］.Computer Vision and Image Understanding，1999，73（3）：441－454.

［13］GARGI U，STRAYER S.Performance characterization of video－shot－change detection methods ［J］.IEEE Trans on Circuits and Systems for Video Technology，2000，10（1）：1－13.

A Method of Compressed Domain Video Shot Segmentation Based on DCE Algorithm

HUANG Yong－feng，XIONG Ze－dong，WANG Shao－yu
（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

Shot segmentation is structural base for video retrieval.An efficient video shot segmentation method is proposed.Firstly，the features are extracted from I frame of video stream in the compressed domain，and the curve of feature information is drawn.Then，the discrete curve evolution （DCE）algorithm is used to evolved the curve.Finally，video shots are segmented and key frames are extracted by the key points of the curve.The experimental results show that the method is efficient and robust，because it takes fully into account the timing features of video encoding.

compressed domain；shot segmentation；key frames；DCE algorithm

TP 391

A

2011－06－09

中央高校基本科研業(yè)務費專項資金科研計劃資助項目（2011D11206）

黃永鋒（1971—），男，山東泰安人，副教授，博士，研究方向為圖像處理與模式識別.E－mail：yfhuang＠dhu.edu.cn

1671－0444（2012）03－0308－04