基于動態滑動窗口和折半查找的鏡頭檢測算法

明 巍,鹿秀麗（.湖北師范學院數學與統計學院；.黃石市中心醫院信息部，湖北 黃石 43500）

基于動態滑動窗口和折半查找的鏡頭檢測算法

明 巍1,鹿秀麗2
（1.湖北師范學院數學與統計學院；2.黃石市中心醫院信息部，湖北 黃石 435002）

摘 要：針對視頻數據處理的數據量比較大的問題，提出了一種基于動動窗口和折半查找的鏡頭檢測算法，實驗結果表明，相對傳統的計算相鄰兩幀差值的鏡頭檢測算法，算法的檢測效果很好，算法復雜度低，易于實現。

關鍵詞：滑動窗口；折半查找；鏡頭檢測；HSV顏色直方圖

1　引言

鏡頭（shot）是視頻的基本物理單元，它由一個攝像機拍攝得到的連續若干幀組成[1]。鏡頭檢測是基于內容的視頻檢索的重要內容和關鍵步驟，直接關系到視頻檢索的效率。

鏡頭的轉換方式主要有兩大類[1]：切變（突變）和漸變。鏡頭切變檢測的方法主要有[1-3]：像素對比較方法、模板比較方法、似然比較方法、直方圖比較方法、滑動窗口法等。鏡頭漸變的特點是兩個鏡頭之間的切換過程是逐漸完成的，從一個鏡頭變化到另一個鏡頭經常延續十幾或者幾十幀。目前鏡頭漸變檢測的方法主要有[4]：雙閾值方法、基于模型的方法等。

傳統計算相鄰兩幀之間的差值進行鏡頭檢測的算法將耗費大量的時間在每一幀信息的提取和計算相鄰兩幀之間的差值上。通過對視頻特征數據的分析，同一鏡頭中兩幀之間的差值相差較小，不同鏡頭中兩幀的差值相差較大，而且同一鏡頭中的幀數比較多。根據視頻的這一特點，提出了動態滑動窗口和折半查找對鏡頭檢測的算法。

2　兩幀差值的計算

兩幀差值的計算需要利用視頻HSV顏色直方圖的特征來計算視頻中任意兩幀之間的差值。設視頻幀序列集合為， HSV顏色分割采用HSV(12×5×5)制，即H分量等分為12塊，S、V分量各自等分為5塊，HSV顏色空間的直方圖定義為式（1）：表示視頻幀序列集合中的第m幀，Hi、Si、Vi分別表示第i像素點的H、S、V值，其中Hj、Sj、Vj表示第j像素點的H、S、V值，L為每一幀圖像像素點的個數,

3　自動選取閾值的方法

對于任一視頻數據，任意選取連續的k幀作相鄰兩幀之間的幀間差值，可以得到一個由k-1個差值所構成的集合。通過幀間差值的分析，得到集合中明顯比兩邊差值大很多的特征差值。在這些特征差值中得到最大差值maxdistance和最小差值mindistance，定義鏡頭檢測閾值：

4　動態滑動窗口和折半查找

由以上的公式（1）和公式（2）可知，提取每一幀的HSV顏色直方圖信息和計算兩幀之間的差值所需要的時間在整個鏡頭檢測算法中所占的時間的比例是比較大的。傳統計算相鄰兩幀之間的差值進行鏡頭檢測的算法將耗費大量的時間在每一幀信息的提取和計算相鄰兩幀之間的差值上。根據視頻同一鏡頭中兩幀之間的相似性，可以推斷同一鏡頭中兩幀的差值和不同鏡頭中兩幀的差值有顯著的差異。又根據視頻同一鏡頭中包含的幀數一般比較大的特點，提出了動態滑動窗口和折半查找對鏡頭檢測的算法。

5　實驗及結果分析

對鏡頭邊界檢測結果的評價方法一般使用查全率和查準率這兩個參數，它們的定義如下：

查全率和查準率越高，說明算法的效果越好。本文在采用查全率和查準率作為視頻鏡頭檢測算法的衡量標準的基礎上，從算法的時間復雜度方面將本文的算法與傳統計算相鄰兩幀之間的差值進行鏡頭檢測的算法進行比較。

本實驗在Visual C++6.0環境中進行，建立包括體育，電影，廣告，紀錄片在內的實驗視頻庫，總幀數是5867幀，幀速率為25幀/秒，視頻被轉化為320×240標準尺寸。

本文算法的結果與文獻中的算法進行對比，查準率相差不大。本文算法的誤檢主要原因在于對于鏡頭切換較快的視頻，誤檢會增多，查準率會下降。但是從算法效率來看，本文的算法不需要計算每相鄰兩幀的差值，算法效率大大提高。

參考文獻：

[1]章毓晉.基于內容的視覺信息檢索[M].北京:科學出版社,2003.

[2]錢剛，曾貴華．典型視頻鏡頭分割方法的比較[J].計算機工程與應用，2004(32):5l-55．

[3]肖治民，林坤輝，周昌樂.基于HSV顏色空間的視頻鏡頭檢測[J].廈門大學學報（自然科學版），2008,47(05):665-668

[4]原野，宋擒豹，沈鈞毅.一個自動閾值選擇的鏡頭檢測算法[J].小型微型計算機系統.2004,25(07):1337-1340.