王文詩，黃樟欽，王偉東，田 銳

(1.北京工業(yè)大學(xué) 北京未來網(wǎng)絡(luò)科技高精尖創(chuàng)新中心，北京 100124；2.北京工業(yè)大學(xué) 北京市物聯(lián)網(wǎng)軟件與系統(tǒng)工程技術(shù)研究中心，北京 100124)

隨著互聯(lián)網(wǎng)及存儲媒介的發(fā)展，視頻數(shù)據(jù)量正快速增長.存儲、管理、分類、索引、檢索和瀏覽等應(yīng)用中有效地處理視頻數(shù)據(jù)成為一個迫切的問題[1].在這些應(yīng)用中，關(guān)鍵幀提取方法已經(jīng)受到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注，并且取得了大量的研究成果[2].提取的關(guān)鍵幀集合必須包含與視頻相關(guān)度最高的內(nèi)容和避免冗余，同時保留視頻的原始信息[3-4].對視頻數(shù)據(jù)的充分表示有助于有效的信息檢索和快速瀏覽整個視頻內(nèi)容.

通常，關(guān)鍵幀提取是在利用鏡頭邊界檢測技術(shù)將視頻分割為鏡頭之后進行.Priya等[5]采用基于HSV空間的顏色特征和最小二乘逼近方法檢測鏡頭邊界.該方法首先使用卡方檢驗測度(chi-square test)和基于閾值的算法檢測切變邊界，然后提取剩余的視頻幀進行漸變邊界檢測，在這個過程中，采用亞基莫夫斯基似然比(Yakimovsky likelihood ratio, YLR)檢驗測度計算幀間相似度.為了降低相機或目標(biāo)等運動對邊界檢測性能的影響，該方法采用了新的思想，即使用最小二乘多項式逼近方法進一步計算相似度的近似值.接著，使用漸變邊界檢測算法檢測視頻的淡變和溶解區(qū)域.Baber等[6]采用圖像全局特征和局部特征檢測視頻淡變和突變邊界.Lu等[7]針對交互應(yīng)用中對實時性的要求，首先采用自適應(yīng)閾值預(yù)測鏡頭邊界的位置和漸變鏡頭的長度，同時移除大多數(shù)非邊界幀.然后在可能包含鏡頭邊界的候選視頻片段中利用顏色直方圖和奇異值分解降低圖像特征向量的維數(shù).最后通過一個基于相似度測度的模式匹配方法檢測視頻突變和漸變鏡頭.Priya等[8]提出了一種新的鏡頭邊界檢測方法.Chasanis等[9]采用經(jīng)典的基于顏色直方圖的方法檢測鏡頭邊界.在每一個鏡頭內(nèi)，采用改進的譜聚類算法提取關(guān)鍵幀.Guan等[10]首次提出基于關(guān)鍵點特征的關(guān)鍵幀提取框架，該方法在每個鏡頭內(nèi)采用一個貪婪算法提取關(guān)鍵幀.實驗結(jié)果表明，該方法具有很好的性能.Souza等[11]提出一種基于顏色直方圖和SIFT局部特征描述子的關(guān)鍵幀提取方法.Zong等[12]提出一種基于動態(tài)的顏色直方圖和快速的小波直方圖的關(guān)鍵幀提取方法.

為了提供視頻序列有效的表示和檢索，本文提出了一種包含有效鏡頭邊界檢測的關(guān)鍵幀提取方法.在每個分割的鏡頭內(nèi)，采用顏色特征直方圖、小波統(tǒng)計特征和SIFT局部特征描述子計算視頻的幀間綜合相似度矩陣.最后使用改進的譜聚類算法將鏡頭幀分組，每一組的中心幀被選為關(guān)鍵幀.實驗結(jié)果表明，提出的方法提取的關(guān)鍵幀可以獲得較高的保真度和重構(gòu)度提出的鏡頭邊界檢測方法獲得的F1分數(shù)為93.4%.

1 提出的方法

1.1 鏡頭分割

視頻序列可以被看作一個從上到下的層級結(jié)構(gòu)，包括原始視頻序列、場景、鏡頭和幀.這樣，視頻分析可以針對不同的目的在不同的層級上進行.通常，關(guān)鍵幀提取在檢測到的每個鏡頭中實現(xiàn)，即在每個分割的鏡頭中提取有代表性的幀作為關(guān)鍵幀.本文中，我們通過鏡頭邊界檢測方法[13]進行鏡頭分割.假設(shè)視頻序列F={f1,f2,…,fn}，其中n是視頻幀的數(shù)目，以及視頻相鄰幀間相似度θ′.為了檢測視頻鏡頭，采用聚類方法將視頻幀分組.

首先考慮空類Cd，即d=1，將第一個相似度θ′賦值到類C1中.通過順序遍歷所有幀比較相似度θ′與閾值δ，θ′被賦值到已存在的類或新的類中.視頻幀聚類步驟如下：

(1) 初始化d=1，i=1；

(2) 賦值Cd={θ′(i,i+1)}；// 這里θ′(i,i+1)指的是兩相鄰幀i和i+1，通過它們之間的相似度表示.

(3) Fori=2,3,…,n-1//n是視頻的總幀數(shù).

(4) Ifθ′(i,i+1) <δ,θ′(i,i+1)被賦值到Cd中；

(5) Else if類Cd中元素的個數(shù)等于1，then

(6) 分配類Cd中的元素到類Cd-1；

(7) Else if類Cd中元素的個數(shù)大于1且小于5，then

(8) 考慮類Cd-1中最后項θ′(l)、類Cd中第一項θ′(f)和第二項θ′(s)，并且

(9) If (θ′(f)-θ′(l))-(θ′(f)-θ′(s)) < 0.5δ

(10)連接類Cd到類Cd-1；

(11) Elsed=d+1// 新的聚類索引

(12) Endif; endif; endif;

(13) Endfor; //重復(fù)步驟(3)～(12)，直到所有的幀按順序包含在各自相關(guān)的類中.

由于某些情況引起的干擾，例如視頻中目標(biāo)和相機同時發(fā)生運動，不能被有效地消除，所以應(yīng)用步驟(5)～(10)避免單個鏡頭被錯誤地分成多個鏡頭.由于鏡頭邊界檢測的目標(biāo)是提取關(guān)鍵幀，用于視頻索引和檢索，所以沒有考慮鏡頭的變化類型.

1.2 關(guān)鍵幀提取

為了在每個鏡頭中提取關(guān)鍵幀，采用改進的譜聚類算法[9]將鏡頭中的視頻幀分組.每一組中與其他所有幀的相似度平均值最大的幀被記為關(guān)鍵幀.

假設(shè)將鏡頭S=s1,s2,…,sN分成K組，改進的譜聚類算法的主要步驟如下：

(1) 計算鏡頭S的幀間相似度矩陣A∈RN×N；

(2) 定義對角矩陣D，它的對角線元素(i,i)等于矩陣A的第i行元素的和.計算拉普拉斯矩陣L=I-D-1/2AD-1/2.

(3) 計算矩陣L的K個主特征向量x1,x2,…,xK，并且構(gòu)造N×K階矩陣X=[x1,x2, …,xK].

(5) 使用快速全局k均值聚類算法將矩陣Y的行分成K組.

(6) 分配幀si到類j中當(dāng)且僅當(dāng)矩陣Y第i行被分配到類j中.每一類中與其他所有幀的相似度平均值最大的幀被記為關(guān)鍵幀.

2 實驗結(jié)果與分析

提出的方法在Intel i5，3.2 GHz CPU，4 GB 內(nèi)存，Windows 10 (64位)環(huán)境下和Matlab平臺上實現(xiàn)和評估.測試視頻數(shù)據(jù)類型包括新聞、教育、體育、動畫等，詳細信息如表1所示.另外，人工對數(shù)據(jù)集進行鏡頭邊界的識別統(tǒng)計作為算法的比較標(biāo)準(zhǔn).對提出的方法的評估分為兩部分：鏡頭邊界檢測；關(guān)鍵幀提取.

采用查全率(V)、查準(zhǔn)率(P)和F1分數(shù)(F1)評估鏡頭邊界檢測方法的性能.這些比率值越大，說明算法性能越好.在視頻邊界檢測算法中，參數(shù)δ的取值需要實驗確定，通常選擇范圍為[-3,8]，實驗中選取固定值δ=2.

提出的方法與基于全局與局部特征的方法[6]進行比較,查準(zhǔn)率、查全率、F1分數(shù)及其平均值實驗結(jié)果如表2所示.可以觀察到，提出的方法具有更好的結(jié)果，查準(zhǔn)率、查全率和F1分數(shù)三個測度的平均值分別為95.6%、91.2%和93.4%.其中產(chǎn)生的誤差主要由視頻內(nèi)容的變化造成，當(dāng)相鄰兩個鏡頭具有很相似的內(nèi)容時，相應(yīng)的鏡頭可能被漏檢.

表1 測試視頻數(shù)據(jù)Tab.1 Details of the test video sequences

表2 不同方法的性能比較結(jié)果Tab.2 Comparative results of different methods

在視頻分析領(lǐng)域，對由不同關(guān)鍵幀提取算法產(chǎn)生的摘要進行評估是最具挑戰(zhàn)性的問題之一.提出的方法采用兩種客觀的評價標(biāo)準(zhǔn)：保真度和鏡頭重構(gòu)度[19].設(shè)鏡頭V={F1,F2,…,FN}及提取的關(guān)鍵幀集合keys，其中N表示鏡頭中的圖像幀數(shù).保真度定義為關(guān)鍵幀與鏡頭中所有幀之間的距離.歸一化的鏡頭保真度(Fid)定義如下

提出的方法在實驗中與基于顏色直方圖方法(HSV)、基于SIFT特征描述子方法和基于小波統(tǒng)計方法(Wavelet)進行了比較，保真度測度及其平均值的實驗結(jié)果如表3所示.首先，沒有一個特征描述子的性能能針對所有視頻內(nèi)容超過其他描述子.從表3中可以看出，與所有單特征方法比較，提出的方法獲得了最好的結(jié)果.保真度越高說明提取的關(guān)鍵幀對視頻內(nèi)容的全局描述越準(zhǔn)確.

表3 基于保真度測度(Fid)的單特征方法和多特征方法的實驗結(jié)果比較Tab.3 Comparative results of fidelity by using single feature method and multiple features method

表4 基于鏡頭重構(gòu)度測度(SRD)的單特征方法和多特征方法的實驗結(jié)果比較Tab.4 Comparative results of SRD by using single feature method and multiple features method

為了判斷提出的方法相對于其他單特征方法的性能改進，采用下式計算相對改進測度ΔP.

ΔP=(提出的方法測度-單特征方法測度)/單特征方法測度

經(jīng)過計算，提出的方法的保真度值相對于其他單特征方法的改進都超過了20%，主要是因為單特征描述子不能全面地描述整個圖像的內(nèi)容.圖1給出了不同方法的鏡頭保真度測度的標(biāo)準(zhǔn)差比較結(jié)果.可以看出，相對于其他單特征方法，提出的方法的鏡頭保真度離散程度更小.為了評估關(guān)鍵幀提取方法對視頻內(nèi)容的局部描述質(zhì)量，表4給出了鏡頭重構(gòu)度測度的實驗結(jié)果，可以看出與其他基于單特征的方法比較，提出的方法取得了更好的結(jié)果.

3 結(jié)束語

由于視頻內(nèi)容種類繁多，而且沒有任何單個圖像特征描述子能針對所有視頻內(nèi)容比其他特征描述子優(yōu)越，所以基于單特征提取關(guān)鍵幀并不總是有效.因此，本文提出了基于多特征的關(guān)鍵幀提取方法.提出的方法包括兩個部分：鏡頭邊界檢測和關(guān)鍵幀選取.在每個鏡頭內(nèi)，通過采用顏色特征直方圖、小波統(tǒng)計特征、SIFT局部特征描述子分別對圖像描述計算幀間綜合相似度測度，然后使用一個改進的譜聚類方法提取關(guān)鍵幀.通過提出的方法提取的關(guān)鍵幀能夠代表視頻的主要內(nèi)容，并能解決視頻內(nèi)容多樣性帶來的困難.實驗結(jié)果表明，提出的多特征方法獲得的平均保真度值和平均鏡頭重構(gòu)度值分別為0.826和6.612，平均保真度性能相對其他單特征方法的提高都超過了20%.