陳逸韜，宮寧生，王淑敏

（南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816）

基于分塊直方圖幀差變化率的鏡頭分割算法研究

陳逸韜，宮寧生，王淑敏

（南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816）

在介紹了目前主流的鏡頭分割算法后，文章提出一種基于分塊直方圖幀差變化率的鏡頭分割算法。該算法主要分為兩部分：突變檢測和漸變檢測。首先利用圖像的HSV分塊直方圖特征計(jì)算相鄰幀幀差，將其與自適應(yīng)的突變閾值比較從而確定突變鏡頭的位置。然后利用突變分割得到的視頻段進(jìn)行鏡頭漸變的檢測。對每一個視頻段利用相鄰幀幀差變化率的規(guī)律來判定漸變位置。實(shí)驗(yàn)結(jié)果表明，該方法具有較高的準(zhǔn)確率，并且易于實(shí)現(xiàn)。

HSV色彩模型；分塊直方圖；鏡頭突變；鏡頭漸變；幀差變化率

隨著互聯(lián)網(wǎng)和多媒體技術(shù)的蓬勃發(fā)展，越來越多的多媒體內(nèi)容涌入到人們的日常生活當(dāng)中來。面對網(wǎng)絡(luò)上涌現(xiàn)出越來越多的視頻，依靠傳統(tǒng)的人工標(biāo)定整理的方式已經(jīng)無法滿足時代的需求。于是基于內(nèi)容的視頻檢索孕育而生，而鏡頭分割就是關(guān)鍵的第一步，也是后續(xù)視頻高層內(nèi)容分析的基礎(chǔ)。現(xiàn)在已經(jīng)有很多成熟的視頻分割研究成果［1］。鏡頭的分割方法有兩大類，一種是基于壓縮域的，另一種是基于非壓縮域的?；趬嚎s域的鏡頭檢測方法主要有Yeo和Liu提出的一種利用MPEG壓縮視頻的DC（離散余弦）序列進(jìn)行鏡頭邊界檢測的方法。基于非壓縮域的鏡頭檢測方法主要有［2-3］：基于圖像像素的方法、基于圖像直方圖的方法和基于運(yùn)動邊緣的方法等。

本文提出一種基于分塊直方圖幀差變化率的自適應(yīng)鏡頭分割方法，它的實(shí)現(xiàn)思路是：充分利用HSV符合人眼視覺特征的特性，使用該色彩空間的分塊直方圖來表示一幀圖像。利用自適應(yīng)的閾值先對整個視頻進(jìn)行突變的鏡頭分割，然后再在任意兩個突變鏡頭之間根據(jù)幀差變化率進(jìn)行漸變檢測。

1　圖像特征和差異性度量

1.1 視頻幀圖像的特征表達(dá)

本文選取基于HSV色彩空間的分塊直方圖作為幀圖像的描述特征參與到邊界檢測中來。HSV是一種符合人眼視覺特征的彩色模型。其中H代表色調(diào)（Hue），S代表飽和度（Saturation），V代表明度或亮度（Value）。

當(dāng)選定了HSV空間模型直方圖來表示視頻幀圖像的顏色特征后，出于存儲效率的考慮，還要進(jìn)行非等間隔量化。這里采用論文［4］的量化方法。方法是將H分量量化成8份，S 和V分別分成3份。因?yàn)槿搜蹖分量的感知比其它兩個分量更細(xì)致一些，因此量化的份數(shù)也更多一些。這樣這個直方圖矢量的分量個數(shù)就減少為8×3×3=72個了。

考慮到一般的直方圖難以反映圖像的空間位置信息，因此本文采用分塊的直方圖方法，文［5］考慮的不同區(qū)塊的重要性不同，采用了類似高斯加權(quán)的方式，但是卻是采用了簡單平均的分塊方式，如圖1（a）所示。文［6］使用了一種改進(jìn)的分塊策略—黃金分割比分塊策略。如圖1（b）所示。此方法將圖像的長寬分別按照3∶5∶3類黃金的比例進(jìn)行分割。這種方案相較第一種能更好地突出圖像的主要內(nèi)容，并且能有效地降低圖像周邊的影響。本文在參考了上述的方法后提出了一種新的改進(jìn)的直方圖分塊策略。如圖1（c）所示。采用這種方法的原因是視頻中的人物關(guān)系，以及各種事物的呈現(xiàn)都是橫向結(jié)構(gòu)的，經(jīng)過研究也發(fā)現(xiàn)，在視頻中（尤其是電影），人物往往會占滿縱向空間，而基本不會占滿橫向空間。因此圖像的上下分塊不需要分那么多，而左右的分割要盡可能擴(kuò)大中間的區(qū)域，從而容納更多有用的信息。

圖1　不同的直方圖分塊策略（圖像內(nèi)的數(shù)字為權(quán)值）

1.2 幀間差異性度量

比較兩個直方圖之間的差異，其實(shí)就是定義一種合適的距離度量方式來計(jì)算兩個直方圖的距離。這里設(shè)定兩個直方圖的距離為：

由于一幀圖像被分為了若干塊，且每塊被賦予了不同的權(quán)值，因此兩幀圖像的差值為：

其中為加權(quán)系數(shù)，就是某個分塊直方圖的差值。就是m，n兩幀的差值。

2 鏡頭分割算法詳述

2.1 鏡頭突變的檢測

鏡頭的突變切換是突然的，切換前的最后一幀和切換后的第一幀之間是沒有過渡幀的。所以從人眼視覺的直觀感受上看畫面出現(xiàn)了一個明顯的跳變，實(shí)際原因就是視頻中運(yùn)動物體的運(yùn)動軌跡出現(xiàn)了斷裂，失去了連續(xù)性。所以從理論上來說切變的前后兩幀中的畫面內(nèi)容應(yīng)該相差很大，它們的直方圖差異也會比較明顯，實(shí)驗(yàn)觀察的確如此，如圖2所示。

圖2　突變變換

是相鄰兩幀 的差值（見公式3），公式左邊代表從該鏡頭第一幀到當(dāng)前幀的前一幀的所有相鄰幀間差的和。需要的是幀間差平均值：

則鏡頭突變檢測的自適應(yīng)閾值為：

突變檢測的方式為，用當(dāng)前幀跟前一幀得到的幀差與這個閾值比較，如果大于這個閾值則判定為鏡頭突變的位置。這里需要考慮系數(shù)a的選取，根據(jù)大量實(shí)驗(yàn)結(jié)果表明，在本論文的數(shù)量級空間下，絕大部分突變位置的幀差是當(dāng)前平均幀差（）的20倍以上，也就是說當(dāng)前幀的幀差值如果大于平均值的20倍基本就可以確定為突變幀。

2.2 鏡頭漸變的檢測

在完成了突變鏡頭的檢測后，一個完整的視頻就被分割成了若干小視頻段，視頻段的兩端就是鏡頭的突變幀。下面就是要在這些視頻段里找尋鏡頭漸變幀的位置。如圖3所示，這是發(fā)生了鏡頭漸變切換的視頻段的幀差直方圖。

圖3　含有漸變變換的幀差

圖3（a）中橢圓圈住的部分就是鏡頭漸變發(fā)生的區(qū)域。箭頭指出在鏡頭發(fā)生漸變變換時相鄰幀差的變化趨勢。從圖中可以看出漸變部分呈現(xiàn)出一個凸包的形狀，整體上從左往右看變化趨勢是先遞增再遞減。其中圖3（a）是包含一個漸變鏡頭的情況，圖3（b）是包含多個漸變鏡頭的情形。由此本文提出一種根據(jù)幀差值變化率來檢測鏡頭漸變的方法。

首先對算法中用到的變量進(jìn)行說明：設(shè)某一個小視頻段的長度為L（幀），將其分割成M子段，每個子段取等長設(shè)為K（幀）（一般取5到8即可），則M=L/K。設(shè)Li為第i子段幀差代表值（i = 1， … ，M），inum， dnum分別為子段的L值連續(xù)增加和遞減的個數(shù)。W為判斷是否還屬于一個漸變鏡頭的判定閾值，設(shè)為一個漸變鏡頭幀數(shù)的一半，由大量實(shí)驗(yàn)測試得出，一般鏡頭的漸變變換都要持續(xù)3秒以上也就是接近80幀，所以這里設(shè)W的值為35/K。w為發(fā)生連續(xù)遞增和遞減之間的子段間隔。具體流程如下：

（1）令i=1， w= 0。inum=0， dnum=0。

（2）若i > M，則轉(zhuǎn)（6），否則將第i子段中的K幀按照其幀差值排序，找出中位數(shù)和求取幀差平均值，分別記為Mid 和Mean。若Mid > Mean，則Li= Mean，若Mean≥Mid，則Li= Mid。若inum≥3轉(zhuǎn)（5），否則轉(zhuǎn)（3）。

（3）若i為1，則轉(zhuǎn)（2），否則轉(zhuǎn)（4）。

（4）若Li＞Li-1，inum=inum+1，i=i+1，轉(zhuǎn)（2）。

若Li≤Li-1：

a.若inum＜3，inum=0，i=i+1，轉(zhuǎn)（2）。

b.若inum≥3，dnum=1，i=i+1，轉(zhuǎn)（2）。

（5）若Li＜Li-1，dnum=dnum+1，w=w+1，i=i+1，轉(zhuǎn)（2）。

若Li≥Li-1：

a.若dnum≥3，則確定一個漸變區(qū)域，設(shè)第i子段中的最后一幀為分割幀。inum=dnum=w=0，i=i+1，轉(zhuǎn)（2）。

b.若dnum＜3，若w≥W，則inum=dnum=w =0，i=i+1，轉(zhuǎn)（2）。否則dnum=0，w=w+1，i=i+1，轉(zhuǎn)（2）。

（6）若dnum≥3，則說明鏡頭漸變結(jié)束之后緊接著發(fā)生了鏡頭的突變切換，因此這時就可以用已經(jīng)檢測出的突變幀作為鏡頭的分割處，轉(zhuǎn)（7）。

（7）算法結(jié)束。

整個算法的核心思路是：只要出現(xiàn)連續(xù)3段的L值遞增的情況就認(rèn)為一個可能的漸變開始，然后在設(shè)定的寬度內(nèi)出現(xiàn)連續(xù)三段L值遞減的情況就判定該算法該算法為一個漸變區(qū)域。

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

作為對論文算法有效性的檢驗(yàn)，隨機(jī)選取4部電影的片段進(jìn)行檢驗(yàn)，并且跟文獻(xiàn)［8］中的方法作了比較。該論文提出一種基于亮度直方圖幀差的自適應(yīng)鏡頭分割算法，用亮度直方圖作為圖像幀的特征向量，并且采用雙閾值。將相鄰兩幀的亮度直方圖幀差跟自適應(yīng)的雙閾值比較，如果大于大的閾值則進(jìn)入突變檢測模塊，如果介于兩個閾值之間，則進(jìn)入漸變檢測模塊，在漸變模塊中采用了基于幀間差方差的方法檢測漸變。

這里采用論文中常用的評估指標(biāo)查全率和查準(zhǔn)率來評價(jià)對比兩種算法，如表1所示。

表1　實(shí)驗(yàn)結(jié)果對比

01視頻段里全部是突變鏡頭，且整段視頻相對比較平和，因此兩種算法的準(zhǔn)確率都非常之高。03和04兩端視頻里包含了數(shù)量較多的漸變鏡頭，且鏡頭突變間的畫面變化較為激烈，因此兩種算法的查全率和查準(zhǔn)率都有所下降，但是實(shí)驗(yàn)表明本文算法仍然優(yōu)于對比算法。尤其在鏡頭漸變檢測中的誤檢率要小于對比方法。

4　結(jié)語

文中提出用HSV彩色模型做出的直方圖作為視頻幀圖像的量化表達(dá)，充分利用了HSV模型符合人眼直觀視覺感受的特性，并且利用分塊直方圖的方法有效克服了一般直方圖會丟失圖像空間位置信息的弊端，再通過加權(quán)的方式，突出一幅圖像不同位置重要性的不同，從而能更好地區(qū)分視頻幀之間的差異。在鏡頭分割過程中，本文采用先做突變分割再做漸變分割的策略，利用突變檢測分割好的視頻段進(jìn)行鏡頭的漸變檢測，忽略掉一些間隔較短的視頻，對符合要求的視頻段采用幀差變化率的方法來檢測。實(shí)驗(yàn)結(jié)果表明該方法具有較高的準(zhǔn)確率和實(shí)用性。

［1］朱耀麟，李倩.視頻檢索常用的鏡頭分割方法的研究［J］.電視技術(shù)，2014（3）：178-181.

［2］陶明明，周源華.一種基于亮度幀差的自適應(yīng)鏡頭邊界檢測算法［J］.電視技術(shù)，2004（12）：62-65.

［3］劉政凱，湯曉鷗.視頻檢索中鏡頭分割方法綜述［J］.計(jì)算機(jī)工程與應(yīng)用，2002（23）：84-87.

［4］彭波，李弼程.一種因果的突變鏡頭檢測方法［J］.計(jì)算機(jī)工程與應(yīng)用，2004（5）：91-92，114.

［5］ZHONG Y，KARU K，JAIN A K.Locating text in complex color images［J］.Analysis and Recognition，1995（1）：146-149.

［6］周藝華，曹元大，張洪欣.一種基于二次幀差的突變鏡頭檢測方法［J］.計(jì)算機(jī)工程與應(yīng)用，2005（6）：22-25.

［7］汪翔，羅斌，翟素蘭，等.基于顏色空間的自適應(yīng)閾值鏡頭分割算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2012（9）：37-40.

［8］印勇，侯海珍.基于直方圖幀差的自適應(yīng)鏡頭分割算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010（9）：186-189.

A Shot Segmentation Algorithm Based on Partitioned Histogram Change Rate of Frame Difference

Chen Yitao， Gong Ningsheng， Wang Shumin
（ College of Computer Science and Technology， Nanjing Technical University， Nanjing 211816， China）

After introducing the current mainstream video shot segmentation algorithms， an adaptive shot segmentation algorithm based on partitioned histogram change rate of frame difference is proposed. The algorithm is mainly divided into two parts： abrupt change detection and gradual change detection. Firstly using the HSV partitioned histogram to calculate the frame difference of adjacent frames. Compare it with the adaptive threshold of abrupt change， and then determine the position of the abrupt change shot. Then using video segments， which is from abrupt change cut， to detect the gradual changes of video shot. Using regular pattern of neighbor frame difference change rate to determine the position of gradual change. Experimental results show that the method in this paper has high accuracy， and it is easy to implement.

HSV color model； partitioned histogram； abrupt change shot； gradual change shot； change rate of frame difference

陳逸韜（1989— ），男，江蘇南京，碩士；研究方向：圖像處理。

項(xiàng)目名稱：國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目；項(xiàng)目編號：2005CB321901。項(xiàng)目名稱：軟件開發(fā)環(huán)境國家重點(diǎn)開放實(shí)驗(yàn)室開放課題；項(xiàng)目編號：BUAA-SKLSDE-09KF-03。