雷少帥，曹長青，古 赟，謝 剛

（太原理工大學 信息工程學院，太原 030024)

視頻是時間連續(xù)的一系列圖像幀的集合，是一種沒有結(jié)構(gòu)的圖像流。如果把視頻看作一本沒有目錄和索引的書，那么一幅圖像幀就相當于書中的一頁。由于視頻這部書缺乏目錄和索引信息，人們無法對它進行高效瀏覽和檢索，于是人們提出利用關鍵幀作為基本訪問單元為視頻建立有效的目錄結(jié)構(gòu)。關鍵幀是原始視頻中最有代表性的一幅或多幅圖像。關鍵幀提取就是研究如何用最少的視頻幀來反映視頻的主要內(nèi)容。它的使用極大地減少了視頻檢索的數(shù)據(jù)量，并為視頻摘要和視頻檢索提供了內(nèi)容組織框架。關鍵幀的數(shù)量取決于視頻內(nèi)容的復雜度，一般視頻內(nèi)容越復雜，內(nèi)容變化越快，提取的關鍵幀應越多。關鍵幀的提取原則是在保存主要視頻內(nèi)容的前提下盡量消除冗余。理論上講，鏡頭中的主要信息，如鏡頭中出現(xiàn)的主要物體、發(fā)生的主要運動和事件等，都應該通過關鍵幀被選取出來。

目前常用的關鍵幀提取方法有：

1)基于鏡頭的方法［1］。首先將視頻分割成若干個鏡頭，然后選取每個鏡頭的首幀或尾幀作為關鍵幀。此方法簡單，但關鍵幀的數(shù)量和位置都是固定的，對于存在攝像機運動和物體運動的視頻鏡頭效果非常不理想。

2)基于內(nèi)容的方法。此方法將顏色、形狀、紋理等底層特征發(fā)生顯著變化的幀作為關鍵幀。文獻［2］先把鏡頭中的第一幀選為關鍵幀，然后計算當前幀與上一關鍵幀的直方圖距離，如果大于某閾值，則被選為關鍵幀。文獻［3］計算當前幀的直方圖和前N幀的平均直方圖之間的距離來確定關鍵幀。文獻［4］首先創(chuàng)造一張參考幀（對于參考幀的創(chuàng)造方法，有興趣的讀者可參考文獻［5］)，然后比較當前幀與此參考幀的直方圖距離，然后與閾值比較選擇關鍵幀。該方法是根據(jù)鏡頭內(nèi)容的變化程度自適應地確定關鍵幀的數(shù)量。但對于內(nèi)容變化較快的視頻，此方法選取的關鍵幀往往過多，冗余性較大。

3)基于聚類的方法。通過聚類算法，將鏡頭中相似的視頻幀聚成相同的類，從每個類中選取距離類心最近的幀作為關鍵幀［6］，即聚類個數(shù)等同于關鍵幀數(shù)目。文獻［7］通過應用聚類有效性分析，能自動確定最優(yōu)聚類個數(shù)。該方法能有效地消除冗余，提取的關鍵幀能夠較好地反映鏡頭內(nèi)容。但此方法選取的關鍵幀打破了原有視頻幀的時間序列，將畫面相似但時間并不連續(xù)的視頻幀歸為一類，難以體現(xiàn)視頻的時間信息。例如一個人從房間走出再進來，聚類的結(jié)果是只體現(xiàn)人走進或者走出的過程，沒有體現(xiàn)人走出再走進的過程，即難以體現(xiàn)視頻時間性。

4)基于運動的方法。利用視頻鏡頭中物體或攝像機的運動信息來提取關鍵幀。文獻［8］通過光流分析來計算鏡頭中的運動量，在運動量局部最小值處選取關鍵幀。另外有很多學者通過MPEG視頻流中的運動向量來分析視頻中物體和鏡頭的運動情況，從而提取關鍵幀。這種方法可以根據(jù)物體或攝像機的運動量大小進行關鍵幀提取，但是，計算量相當大。

現(xiàn)有方法都是利用視頻幀的空間信息進行關鍵幀提取，而忽略了視頻幀之間存在的時間信息，難以動態(tài)反映視頻內(nèi)容，不符合人眼視覺感知。因此，必須加強對視頻時空特性的分析，力爭從時空聯(lián)合特性上確定關鍵幀數(shù)目和位置。但視頻時空特性分析是關鍵幀提取領域中的一個難點，面臨極大的挑戰(zhàn)。

由于時空切片包含了視頻鏡頭的物體和攝像機的運動信息，能反映視頻的動態(tài)特性，因此本文提出了一種基于視頻時空切片的關鍵幀提取方法。

1 視頻時空切片

時空切片的概念是E.H.Adelson和J.Bergen于1985年在“Spationtemporal Energy Models for the Perception of Motion”一文中首次提出的。所謂視頻時空切片，是將連續(xù)的視頻圖像在時間軸上展開，然后在各幀相同的位置進行采樣，如提取所有圖像的某一行（列)像素組合而成的一幅二維圖像［9］。因此時空切片能得到該視頻內(nèi)容在指定位置上隨時間變化的信息。時空切片通常有三種取法：垂直切片、水平切片、和對角線切片，切片方法如圖1所示。

圖1 時空切片分割方式示例

對長度為L的視頻序列V，本文采用水平切片法提取每幀中間位置的橫向像素線，因此共計L條像素線，然后將它們按列排列拼成一張新圖片，即此段視頻的時空切片。下面分析時空切片中像素間的時空特性。以圖2-a所示的時空切片為例，以該幀左上角為原點，右方作為X正向，下方作為Y正向建立坐標系FXOY。在FXOY中，時空切片在Y方向上的相鄰像素點是同一幀中同一像素線上的相鄰點，反映的是像素點在空間分布的相關性，X方向上的相鄰像素點則是相鄰幀中位于同一位置上的像素點，反映了不同視頻幀的時間相關性，這表明時空切片融合了視頻片段的時空聯(lián)合特性。

圖2是從幾個視頻鏡頭中提取的視頻時空切片。圖2-a所對應的視頻鏡頭是飛機起飛的過程。開始飛機在地上緩慢向前移動，所以鏡頭基本上是靜止的，圖2-a開始處的平行紋理就反映了這一點；隨著飛機的快速起飛，攝像機隨飛機快速移動，背景逐漸發(fā)生變化，此過程可由圖2-a中的紋理變得傾斜以及紋理顏色變白就可看出。變白是因為飛機已經(jīng)飛上天空，顯示的是背景白云的顏色。

圖2-b所對應的視頻鏡頭是一個人在說話，視頻內(nèi)容基本沒有變化，這可由視頻切片的紋理反映出來。切片的紋理基本是平行的沒有發(fā)生變化，其中中間顏色較深的部分代表了畫面中的人物，由此看出畫面中的人物也沒有發(fā)生運動。

圖2-c所對應的鏡頭是一個人在跑步，一會跑進鏡頭，一會跑出鏡頭，背景不變。由其切片圖可以看出黑色的線代表跑步的人，由此可清楚的看出人的運動軌跡。由于背景不變，所以時空切片的背景是純色的，沒有其他紋理和顏色變化。

圖2 從幾個視頻鏡頭中提取的視頻時空切片

2 基于時空切片的關鍵幀提取

由以上分析可見，顏色和紋理包含了對應視頻的大量信息，包括攝像機的運動，物體的運動，背景的變化等等。顏色和紋理的不連續(xù)性意味著新的鏡頭內(nèi)容出現(xiàn)，因此通過分析時空切片特性就可很好地表征顏色紋理等特征。正是由于視頻時空切片不同程度地表現(xiàn)了視頻內(nèi)容的變化情況，提出了基于視頻時空切片的關鍵幀提取方法。具體算法可描述如下：

1)首先提取鏡頭的視頻水平時空切片，設視頻圖像的高和寬分別為H和W，將每幀灰度化后，提取各幀H／2處的水平方向像素線，隨后將水平像素線按列排序拼接出視頻的時空切片。水平方向像素線由（x，H／2)處的像素組合生成，其中x＝1，2，...；W 代表像素在原始視頻中的橫坐標。時空切片的每一列可由每列像素的像素值表示，即可由一個W×1的列向量hi表示。

2)對時空切片進行K均值聚類。先選取K個聚類中心，K可以根據(jù)用戶的需求自己選擇。實驗所選K＝4，聚類中心根據(jù)鏡頭長度平均分成4份，取每份的中心作為聚類中心。然后，以時空切片的列向量hi為特征進行K均值聚類。如圖3所示，黑色代表的類在時間上是不連續(xù)的，如按聚類方法它們會被合并為一類。因此定義，如聚類特征相同但時間不連續(xù)的像素線不能被聚成同一類。

3)聚類完成后，在時空切片中還會出現(xiàn)只有極少量幀同屬一類的現(xiàn)象。由于視頻內(nèi)容表達具有時間持續(xù)性，極少量的幀難以表達語義內(nèi)容，因此，補充如下定義：如果少于5幀被單獨聚成一類，且這個類兩邊的聚類顏色相同，則認為這幾幀聚類錯誤，應和其前后類被歸結(jié)為同一類；如果這個類兩邊的聚類顏色不同，則將它歸到與其聚類中心較近的那一類。

圖3 聚類后的時空切片示意圖

4)提取候選關鍵幀。聚類后，每一個類（相同顏色但是時間不連續(xù)的看做不同的類)代表一個子鏡頭，然后從每個子鏡頭中提取一個關鍵幀。提取的方法為：計算每個類內(nèi)的相鄰幀差，選取幀間差最大的兩幀中的后者作為候選關鍵幀。

5)提取關鍵幀。為了減少冗余，對候選幀進一步篩選。相鄰兩個候選關鍵幀的對應像素相減，P＝｜pk-pk-1｜，pk為候選關鍵幀中的像素，如果P＞3，則認為兩個像素不相同，統(tǒng)計相鄰兩個候選關鍵幀中不相同的像素個數(shù)P，如果P＞PN／3，PN為每幀的像素個數(shù)，則認為相鄰兩個候選幀不相似。如圖4所示，第一行代表7個候選幀，第二行代表相鄰兩幀之間是否相似，0代表相似，1代表不相似。我們定義如下的關鍵幀提取準則：如果第二行有單獨為0的（連續(xù)兩幀相似)，則對應的前一幀保留，此時候選幀間的相似程度如圖5所示；針對圖5，如果第二行有連續(xù)2或2個以上個為0（連續(xù)3幀以上相似)，則只保留連續(xù)相似幀的第一幀和最后一幀，其余去掉。

圖4 候選幀間第一次相似性度量

圖5 侯選幀間第二次相似性度量

3 實驗結(jié)果分析

為了驗證本方法的有效性，本文從標準視頻庫OPENVIDEO中選取了大量不同類型的視頻進行了實驗，下面選取了5個不同類型的視頻鏡頭進行分析說明。

視頻Broken是一個特技效果類視頻，描述的是盤子在特技作用下慢慢聚攏，然后突然破碎的過程，提取結(jié)果如圖6所示。

圖6 視頻Broken的實驗結(jié)果

視頻ROAD是個攝像機運動的鏡頭，描述的是攝像機隨汽車前進、拐彎、拍攝路邊景象，最后行駛在新在道路上的過程。圖7為提取的關鍵幀。

圖7 視頻ROAD的實驗結(jié)果

視頻vipmen是一個攝像機不動，物體運動的鏡頭。畫面描述了白衣男子走到拐角等待另一個男子的到來，然后兩人握手交談，最后白衣男子原路返回。利用本文算法的實驗結(jié)果如圖8所。

圖8 視頻vipmen的實驗結(jié)果

視頻BOR10-002是個存在物體和攝像機雙重運動的鏡頭，描述的是一架飛機滑行、起飛，最后飛向天空并漸漸消失的過程。圖9為提取的關鍵幀結(jié)果。

視頻hcil-2002是個靜止的鏡頭，描述的是一個人在說話，視頻畫面基本沒有變化。圖10為提取的關鍵幀結(jié)果。

圖9 視頻BOR10-002的實驗結(jié)果

圖10 視頻hcil-2002的實驗結(jié)果

由以上實驗結(jié)果可見，我們的算法具有良好的魯棒性，針對不同類型的視頻鏡頭均能取得良好效果。由于關鍵幀提取目前尚無統(tǒng)一的評價標準，且評價主觀性較大，因此并未與其他算法進行性能比較。但實驗結(jié)果表明，本算法能準確捕捉視頻主要內(nèi)容，以最少的關鍵幀反映了視頻動態(tài)特性，具有良好的人眼視覺感知。

4 結(jié)論

提出了一種基于視頻時空切片和K均值聚類的關鍵幀提取方法，由于視頻切片中包含了物體和鏡頭的運動信息，所以提取的關鍵幀能夠很好的描述視頻鏡頭所描述的過程及內(nèi)容，反映了視頻的時空特性。通過K均值聚類，選取的關鍵幀能以極低的冗余度反映視頻連續(xù)性，具有良好的人眼視覺感知。

目前的聚類個數(shù)還是人為定義的參數(shù)，下一步的研究重點是研究自適應聚類個數(shù)方法，從而滿足視頻多樣性的需求。另外，還要加深對時空切片的物理特性研究，挖掘更多可以利用的信息，為關鍵幀的提取提供更加有效的聚類依據(jù)。

［1］Taniguchi Y.An Intuitive and Efficient Access Interface to Real-time Incoming Video Based on Automatic Indexing［C］.Proc of ACM Multimedia，1995：25-33.

［2］Zhang H J，Wu J，Zhong D，et al.An integrated system for content-based video retrieval and browsing［J］.Pattern Recognit，1997，30（4)：643-658.

［3］Ferman A M，Tekalp A M.Two-stage Hierarchical Video Summary Extraction to Match Low-level User Browsing Preferences［J］.IEEE Transactions on Multimedia，2003，5（2)：244-256.

［4］Z.Sun，K.Jia，and H.Chen.Video Key Frame Extraction Based on Spatial-Temporal Color Distribution［C］.Proc.Conference on Intelligent Information Hiding and Multimedia Signal Processing，2008：196-199.

［5］Sze K W，Lam K M，Qiu G P.A New Key Frame Representation for Video Segment Retrieval［J］.IEEE Transactions on Circuits and Systems for Video Technology，2005，15（9)：1148-1155.

［6］羅森林，馬舒潔，梁靜，等.基于子鏡頭聚類方法的關鍵幀提取技術(shù)［J］.北京理工大學學報，2011，31（33)：348-352.

［7］Huiyu Zhou，Abdul H Sadka，Mohammad R Swash.Feature extraction and clustering for dynamic video summarisation［J］.Neurocomputing，2010，73（10)：1718-1729.

［8］Wolf W.Key selection by motion analysis［C］.In Proc IEEE Int Conf Acoust，Speech Signal Proc，1996：1228-1231.

［9］潘雪峰，李錦濤，張勇東，等.基于視覺感知的時空聯(lián)合視頻拷貝檢測方法［J］.計算機學報，2009，32（1)：107-114.