藍章禮，帥 丹，李益才

( 重慶交通大學 信息科學與工程學院，重慶 400047)

基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法

藍章禮，帥 丹，李益才

( 重慶交通大學 信息科學與工程學院，重慶 400047)

為從固定攝像頭的道路監(jiān)控視頻中有效地提取出關鍵幀，提出了基于相關系數(shù)的關鍵幀提取算法。算法將監(jiān)控視頻中圖像幀的RGB值處理為灰度值，結(jié)合滑動窗口機制，通過當前幀和當前關鍵幀之間相關系數(shù)的絕對值與閾值比較判斷當前幀是否為關鍵幀。實驗結(jié)果表明：算法在有效提取關鍵幀的同時還具有流程清晰、避免了冗余關鍵幀的特性。最后利用基于歐式距離的幀間差異性對提取的關鍵幀進行評價，驗證了算法的有效性和合理性。

交通運輸工程；關鍵幀；相關系數(shù)；滑動窗口；道路監(jiān)控

隨著網(wǎng)絡和多媒體技術的飛速發(fā)展，涌現(xiàn)出了大量多媒體信息。為方便管理和索引海量的視頻數(shù)據(jù)，視頻數(shù)據(jù)庫管理系統(tǒng)得到了廣泛應用。視頻數(shù)據(jù)庫管理系統(tǒng)中需要有效地視頻摘要、視頻檢索技術，而這些技術的基礎和關鍵是如何有效地提取關鍵幀[1-5]。尤其在道路監(jiān)控中，存在大量的視頻數(shù)據(jù)需要存儲和分析、處理。

關鍵幀是鏡頭中最具有代表性、最重要的一幀或者多幀圖像。提取的關鍵幀一般滿足兩個基本原則：盡可能完整、準確地反映鏡頭的主要內(nèi)容；數(shù)據(jù)量小，計算簡潔。關鍵幀提取技術的使用，大大減少了視頻數(shù)據(jù)的處理量，為視頻摘要和檢索提供了組織框架。

1 典型的關鍵幀提取算法

關鍵幀提取技術因其在視頻摘要和視頻檢索中的重要地位，近幾年得到了廣大研究者的廣泛關注，同時也有一些重要的研究成果。關鍵幀的提取主要有以下幾種方法。

1.1 基于鏡頭邊界提取關鍵幀

當一段視頻分割為鏡頭之后，將每個鏡頭的第一幀或者最后一幀作為該鏡頭的關鍵幀，如視頻鏡頭邊界檢測及關鍵幀提取算法[6]，及基于多種視頻特征的鏡頭邊界檢測算法[7]。此類方法實現(xiàn)簡單，運算量小，關鍵幀數(shù)目一般固定，但選取的關鍵幀多數(shù)情況下不能完整的反映一個鏡頭的信息，不具有代表性。

1.2 基于聚類提取關鍵幀

鏡頭聚類主要研究鏡頭之間的關系，即如何將內(nèi)容相近的鏡頭組合起來，先初始類中心，再將當前幀的特征值與某個類的距離進行比較，判斷當前幀是歸于某個類還是作為一個新類，最后對鏡頭中的幀進行聚類分析，關鍵幀為與類中心距離最小的幀，如改進的蟻群算法與凝聚相結(jié)合的關鍵幀提取[2]，基于聚類的關鍵幀提取算法[8]。此類方法綜合考慮了鏡頭內(nèi)和鏡頭間的相關性，但不能有效地保存原鏡頭中圖像幀的動態(tài)信息和時間順序，同時計算量很大。

1.3 基于運動分析提取關鍵幀

通過光流分析來計算鏡頭中的運動量，包括基于局部運動和基于全局運動的方法，如W0LF光流法，利用光流與熵統(tǒng)計法對花卉生長視頻進行關鍵幀提取[9]。此類方法能很好地表達視頻內(nèi)的全局性運動，但在分析運動時，所需要的計算量較大，且局部最小值也不一定準確。

1.4 基于視覺內(nèi)容提取關鍵幀

通過每一幀圖像視覺內(nèi)容的變化程度提取關鍵幀，如圖像的紋理、顏色等視覺信息，當圖像的這些信息有顯著變化時，當前幀即為關鍵幀，如利用改進的互信息量對關鍵幀提取的研究[10]，對基于鏡頭內(nèi)容的視頻檢索系統(tǒng)研究[11]。此類方法選取的關鍵幀數(shù)目由鏡頭變化程度決定，選取的關鍵幀能夠反映鏡頭內(nèi)圖像的變化，但選取的幀不一定具有代表意義，同時物體快速運動時，容易選取出過多連續(xù)的關鍵幀。筆者針對現(xiàn)有基于圖像信息提取關鍵幀存在的問題，結(jié)合滑動窗口機制，提出了基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法。

2 基于相關系數(shù)的關鍵幀提取算法

2.1 算法提出

道路監(jiān)控中，主要關注車輛信息和異常信息，因此道路監(jiān)控視頻關鍵幀可以定義為有車輛運行和出現(xiàn)異常信息的幀，即圖像幀間變化較大的圖像幀。在道路監(jiān)控中，攝像頭位置固定，監(jiān)控視頻鏡頭單一，不需要鏡頭分割，不能直接使用上述4種典型的關鍵幀提取算法，筆者結(jié)合滑動窗口提出了基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法。

道路監(jiān)控視頻中，兩個圖像幀之間的相關系數(shù)絕對值越小，其圖像的變化越大；反之，圖像變化越小?；谙嚓P系數(shù)的道路監(jiān)控視頻關鍵幀提取算法是通過比較當前幀與關鍵幀的相關系數(shù)絕對值與自定義閾值θ的大小判別當前幀是否為關鍵幀。筆者將圖像幀的RGB值轉(zhuǎn)化為灰度值Y進行處理和分析，降低了算法復雜度，減小了計算量；使用滑動窗口，有效地防止提取過多連續(xù)重復關鍵幀，得到與前一關鍵幀相比差別更大、更具有代表性的關鍵幀。

2.2 算法流程

算法的基本過程描述為：

輸入：視頻文件自定義閾值θ，滑動窗口寬度w。

輸出：視頻關鍵幀序列。

1)從視頻文件中分離視頻流，讀取圖像幀數(shù)目N；

2)初始化，定義關鍵幀F(xiàn)k=F0，從第1幀開始遍歷視頻幀序列，index=1；

3)判斷視頻中的所有圖像幀是否遍歷完成，即index

4)N幀內(nèi)，滑動窗口(Findex,Findex+1,Findex+2,…,Findex+w-1)內(nèi)的幀與關鍵幀F(xiàn)k的相關系數(shù)絕對值最小值的第l幀F(xiàn)l，相關系數(shù)絕對值最小值記為|r(Fk，F(xiàn)l)|；

5)判別第l幀F(xiàn)l是否為關鍵幀，若g(Fk，F(xiàn)l)=|r(Fk，F(xiàn)l)|-θ>0，則Fl不是關鍵幀，轉(zhuǎn)至步驟7)；若g(Fk，F(xiàn)l)=|r(Fk，F(xiàn)l)|-θ<0，則Fl是關鍵幀，輸出關鍵幀信息，并轉(zhuǎn)向下一步；

6)重新定義當前關鍵幀F(xiàn)k=Fl，更改遍歷序列下標index=l+1，轉(zhuǎn)至步驟3)；

7)改變遍歷序列下標index=index+w，轉(zhuǎn)至步驟3)。

2.3 圖像幀預處理

從道路監(jiān)控視頻流中獲取的圖像幀中，包含了圖像中像素點的RGB信息，筆者用相關系數(shù)分析圖像幀的差別，注重的是圖像的輪廓信息，灰度圖像是像素點之間只有亮度差別而沒有顏色差別的圖像，因此可以利用圖像的灰度值進行分析[12]。彩色圖像灰度化公式為：

Y=0.299R+0.578G+0.114B

(1)

式中：Y是圖像的灰度值集合；R，G，B分別代表彩色圖像的紅、綠、藍三個顏色通道的數(shù)值集合，將第l幀圖像的灰度信息集合記為Fl，其表達式為：

Fl={Y(1,1),Y(1,2),…,Y(1,n),Y(2,1),Y(2,2),…,Y(m,n)}

(2)

式中：Y(i,j)為圖像第i行第j列像素點的灰度值；Y(1,1)為第l幀圖像第1行第1列像素點的灰度值；m為圖像的寬度；n為圖像的高度。

將原來圖像幀的RGB值轉(zhuǎn)化為圖像幀的灰度信息Fl進行分析，可以有效降低算法復雜度，減小計算量。

2.4 關鍵幀判別

通過與當前關鍵幀F(xiàn)k比較，判別第l幀F(xiàn)l是否為關鍵幀。關鍵幀判別函數(shù)g(Fk,Fl)的表達式為：

g(Fk，F(xiàn)l)=|r(Fk，F(xiàn)l)|-θ

(3)

式中：θ為自定義閾值；r(Fk，F(xiàn)l)為關鍵幀F(xiàn)k與第l幀F(xiàn)l的相關系數(shù)，其表達式為：

(4)

(5)

cov(Fk,Fl)=E[(Fk-E[Fk])(Fl-E[Fl])]=

(6)

(7)

關鍵幀F(xiàn)k與第l幀F(xiàn)l的相關系數(shù)r(Fk,Fl)為：

(8)

式中：m為圖像像素列數(shù)；n為圖像像素行數(shù)。

相關系數(shù)絕對值|r(Fk,Fl)|越大，表示關鍵幀F(xiàn)k與第l幀F(xiàn)l的相關性越小，變化越大；反之，變化越小。判別函數(shù)g(Fk，F(xiàn)l)<0時，判別第l幀F(xiàn)l相對于當前關鍵幀F(xiàn)k為關鍵幀；反之，第l幀F(xiàn)l不是關鍵幀。

2.5 滑動窗口

在關鍵幀的提取過程中，為了避免提取出連續(xù)重復的關鍵幀，采用滑動窗口機制?；瑒哟翱谑菍⑦B續(xù)的w個圖像幀組成一個集合，用關鍵幀判別函數(shù)g(Fk，F(xiàn)l)判斷滑動窗口中相關性絕對值最小的幀F(xiàn)l相對于當前關鍵幀F(xiàn)k是否為關鍵幀，不存在關鍵幀，滑動窗口移動到窗口中最后一幀的下一幀；存在關鍵幀，滑動窗口移動到關鍵幀的后一幀。

關鍵幀的提取過程中，滑動窗口機制描述為：

1) 依次計算當前關鍵幀F(xiàn)k與滑動窗口內(nèi)的圖像幀(Fi,Fi+1,Fi+2,…,Fi+w-1)相關系數(shù)的絕對值|r(Fk，F(xiàn)i)|，|r(Fk，F(xiàn)i+1)|，|r(Fk，F(xiàn)i+2)|,…,|r(Fk，F(xiàn)i+w-1)|；

2) 找出相關系數(shù)絕對值最小的第l幀F(xiàn)l，其最小的相關系數(shù)絕對值表示為|r(Fk，F(xiàn)l)|；

3) 利用關鍵幀判別函數(shù)g(Fk,Fl)判別第l幀F(xiàn)l是否為關鍵幀，是則轉(zhuǎn)至步驟5)，否則轉(zhuǎn)向下一步；

4) 將滑動窗口移動至第(i+w)幀，繼續(xù)查找下一個滑動窗口(Fi+w,Fi+w+1,Fi+w+2,…,Fi+2w-1)中的關鍵幀；

5) 將滑動窗口移動至第(l+1)幀，繼續(xù)查找下一個滑動窗口(Fl+1,Fl+2,Fl+3,…,Fl+w)中的關鍵幀。

其中，滑動窗口大小的選取主要考慮2方面的因素：① 滑動窗口不宜選取過大，防止漏選取關鍵幀；② 滑動窗口不宜選取過小，防止提取過多的冗余關鍵幀。因此需要結(jié)合監(jiān)控區(qū)域大小、車速及車輛通過監(jiān)控區(qū)域的時間選取合適大小的滑動窗口。

實驗中，在車速正常的情況下，一般車輛通過監(jiān)控區(qū)域的時長為1～2 s且分析的視頻為PAL制式、AVI格式，幀速率為25幀/s，因此滑動窗口選取25～50幀之間均可，若滑動窗口大小比25小很多，可能出現(xiàn)冗余幀；若滑動窗口比50大，可能漏提取關鍵幀。文中滑動窗口的大小w取25，以圖1說明滑動窗口工作原理。

圖1 滑動窗口(w=25)工作原理Fig.1 Working principle of sliding window

(w=25)

圖1(a)中，滑動窗口含有圖像幀(F1,F2,F3,…,F25)，若滑動窗口中無關鍵幀，滑動窗口移動至第26幀，包含圖像幀(F26,F27,F28,…,F50)；若滑動窗口中有關鍵幀，如第2幀為關鍵幀，滑動窗口移動至第3幀，包含圖像幀(F3,F4,F5,…,F27)。

3 實驗與分析

3.1 實驗結(jié)果

提出的基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法在VC++平臺實現(xiàn)。對學校車行道上一段60 s、1 500幀的監(jiān)控視頻進行分析，視頻中有2輛車分別通過監(jiān)控區(qū)域，在閾值θ不同的情況下，使用滑動窗口和不使用滑動窗口提取的關鍵幀結(jié)果如表1。其中提取出的關鍵幀分為含有車輛和不含車輛，若關鍵幀中含有車輛，則提取的關鍵幀為符合需求的關鍵幀；若不含車輛的關鍵幀，則為誤檢關鍵幀；若提取的關鍵幀沒有包含2輛車，則存在漏檢關鍵幀。

從表1分析得出以下結(jié)論：

1)未使用滑動窗口的情況下，當閾值θ≤0.905，不能提取出關鍵幀；當閾值θ為0.970，0.930時，誤提取出關鍵幀；在閾值θ≥0.910時，有效地提取出關鍵幀。

2)隨閾值θ的增加，關鍵幀冗余度明顯增加，當閾值θ的增加到一定值時，存在誤檢驗幀。

3)使用滑動窗口的，提取有效關鍵幀的同時，冗余度明顯降低，冗余關鍵幀的數(shù)目明顯減少。

4)滑動窗口拓寬了閾值θ的取值范圍，降低了閾值θ的選取難度。未使用滑動窗口，閾值θ在0.910附近，提取關鍵幀效果最佳；使用滑動窗口，在0.910≤θ≤0.925時，能提取出有效地關鍵幀。

表1 有無滑動窗口實驗結(jié)果對比

在使用滑動窗口機制，閾值θ=0.910時，提取的關鍵幀序列如圖2。

圖2 閾值θ=0.910提取的幀序列(滑動窗口)

由圖2可知，提取的關鍵幀分別為2輛車通過監(jiān)控區(qū)域，并可以清晰的看見車輛信息的圖像幀。實驗結(jié)果表明：結(jié)合滑動窗口，基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法可以提取包含清晰的車輛信息的關鍵幀，能夠?qū)④囕v進入和離開監(jiān)控區(qū)域的信息很清晰的體現(xiàn)。

3.2 關鍵幀評價

利用本文算法提取的關鍵幀，符合道路監(jiān)控特點，包含了清晰的車輛信息，同時通過基于歐式距離的幀間差異性進行評價。

為判斷提取出的關鍵幀是否為有效關鍵幀和最佳關鍵幀，筆者提出利用基于歐式距離的幀間差異性進行評價。如果2個相連關鍵幀F(xiàn)k1，F(xiàn)k2之間的差異Dis(Fk1,Fk2)是關鍵幀F(xiàn)k1與幀F(xiàn)l之間的差異的最大值，其中k1≤l≤k2，那么選取的關鍵就是正確、有效地。實現(xiàn)的過程中，允許存在σ=0.001的誤差，即提取出的關鍵幀滿足式(9)，提取的關鍵幀為有效關鍵幀和最佳關鍵幀：

(9)

式中：Max[Dis(Fk1,Fl)]為關鍵幀F(xiàn)k1與幀F(xiàn)l之間的差異的最大值；Dis(Fk1,Fk2)為關鍵幀F(xiàn)k1,Fk2之間歐式距離；Dis(Fk1,Fl)為關鍵幀F(xiàn)k1與幀F(xiàn)l之間歐式距離。

兩幀之間的歐式距離越大，差異性越大，第k幀和l幀的歐式距離公式如式(10)：

(10)

式中：m為圖像像素點列數(shù)；n為圖像像素點行數(shù)。分析實驗過程中的當前幀和當前關鍵幀之間的歐式距離，得關鍵幀之間的歐式距離是所在區(qū)間中最大的，證明了提取的關鍵幀的有效性和合理性。

在利用滑動窗口機制，閾值取0.970和0.910時的幀序列和相關系數(shù)(圖中虛線)，歐式距離(圖中實現(xiàn))的曲線圖如圖3、圖4。為了圖像更加清晰，在圖3(a)、圖4(a)顯示1 500幀圖像序列的曲線圖的同時，還增加了圖3(b)、4(b)顯示前200幀圖像序列的曲線圖；將歐式距離線性的轉(zhuǎn)化到相關系數(shù)的區(qū)間，轉(zhuǎn)化后的距離d的公式如式(11)：

Min(R)

(11)

式中：d為顯示距離；Max，Min分別為求最大值、最小值函數(shù)；Dis為所有圖像幀的歐式距離的集合；R為所有圖像幀的相關系數(shù)的集合；dis為當前需要轉(zhuǎn)化的原始歐式距離。

圖3 閾值θ=0.970的幀序列——歐式距離、相關系數(shù)Fig.3 Euclidean distance and correlation coefficient of frame sequence when threshold θ is 0.970

圖4 閾值θ=0.910的幀序列——歐式距離、相關系數(shù)Fig.4 Euclidean distance and correlation coefficient of frame sequence when threshold θ is 0.910

4分析圖3、圖得出以下結(jié)論：

1)隨著幀間相關系數(shù)的增大，歐式距離減??；反之，歐式距離變大。

2)相關系數(shù)相應區(qū)間極小值對應歐式距離極大值。

3)相關系數(shù)減小速度加劇時，歐式距離增大速度也加劇，此時存在關鍵幀。

4)兩個關鍵幀的區(qū)間內(nèi)，關鍵幀之間的相關系數(shù)是第一個關鍵幀和任意幀相關系數(shù)的最小值；關鍵幀之間的歐式距離是第一個關鍵幀和任意幀歐式距離的最大值。

4 結(jié) 語

結(jié)合滑動窗口機制，提出基于相關系數(shù)的道路監(jiān)控視頻關鍵幀提取算法，實驗表明，在固定攝像頭的道路監(jiān)控中可以有效地提取出具有代表性的關鍵幀，同時通過基于歐式距離的幀間差異性驗證得出提取的關鍵幀之間差異性是最大的。算法流程清晰，結(jié)合的滑動窗口機制有效降低了關鍵幀的冗余度，使得關鍵幀更具有代表性，拓寬了閾值的取值范圍，降低了閾值選取難度。但是算法中閾值還是需要根據(jù)不同的應用場景，憑經(jīng)驗選取，有待進一步研究、完善算法，使得閾值可以自動選取。

[1] JADON R J,CHAUDHURY S,BISWAS K K.A fuzzy theoretic approach for video segmentation using syntactic features [J].PatternRecognitionletters,2001,22:1359-1369.

[2] 張建明,劉海燕,孫淑敏.改進的蟻群算法與凝聚相結(jié)合的關鍵幀提取[J].計算機工程與應用,2013,49(3):222-225. ZHANG Jianming,LIU Haiyan,SUN Shumin.Key frame extraction based on improved ant algorithm and agglomerative [J].ComputerEngineeringandApplications,2013,49(3):222-225.

[3] 程照輝,毋立芳,劉健.基于運動特征的視頻檢索[J].信號處理,2011,27(5):765-770. CHENG Zhaohui,WU Lifang,LIU Jian.Motion feature based video retrieval [J].SignalProcessing,2011,27(5):765-770.

[4] 劉帷,賈克斌,王卓崢,等.融合視頻指紋和時空信息的視頻檢索算法[J].北京工業(yè)大學學報,2014,40(2):200-205. LIU Wei,JIA Kebin,WANG Zhuozheng,et al.Video retrieval method based on video fingerprints and spatial-temporal information [J].JournalofBeijingUniversityofTechnology,2014,40(2):200-205.

[5] 陸燕,陳福生.基于內(nèi)容的視頻檢索技術[J].計算機應用研究,2003,20(11):1-4. LU Yan,CHEN Fusheng.Content-based video retrieval techniques [J].ApplicationResearchofComputers,2003,20(11):1-4.

[6] 方勇,戚飛虎.一種新的視頻鏡頭邊界檢測及關鍵幀提取方法[J].華南理工大學學報(自然科學版),2004.32(增刊1):18-23. FANG Yong,QI Feihu.A new method of video shot boundary detection and key frame extraction [J].JournalofSouthChinaUniversityofTechnology(NaturalScience),2004.32(Sup1):18-23.

[7] 杜奎然,肖國強,江健民.基于多種視頻特征的鏡頭邊界檢測算法[J].計算機工程,2009,35(11):243-245. DU Kuiran,XIAO Guoqiang,JIANG Jianmin.Shot boundary detection algorithm based on multiple video features [J].ComputerEngineering,2009,35(11):243-245.

[8] MOIR G L,GRAHAM B W,DAVIS S E,et al.An efficient method of key-frame extraction based on a cluster algorithm [J].JournalofHumanKinetics,2013,39(1):15-23.

[9] 王璐,高林,閆磊,等.基于光流與熵統(tǒng)計法的花卉生長視頻關鍵幀提取算法[J].農(nóng)業(yè)工程學報,2012,17(28):125-130. WANG Lu,GAO Lin,YAN Lei,et al.Key-frame retrieval method based on optical flow and entropy statistic for blooming video [J].TransactionsoftheChineseSocietyofAgriculturalEngineering,2012,17(28):125-130.

[10] 劉高軍,楊麗.改進的互信息量相似度曲線關鍵幀提取研究[J].計算機應用與軟件,2014,31(2):153-156. LIU Gaojun,YANG Li.On key frame extraction based on improved mutual information similarity survey [J].ComputerApplicationsandSoftware,2014,31(2):153-156.

[11] 姜靜,張棟梁.基于鏡頭內(nèi)容的視頻檢索系統(tǒng)[J].山東理工大學學報(自然科學版),2013,27(3):21-24. JIANG Jing,ZHANG Dongliang.Video retrieval system based on shot contents [J].JournalofShandongUniversityofTechnology(NaturalScience),2013,27(3):21-24.

[12] 曹建秋,王華清,藍章禮.基于改進YCrCb顏色空間的膚色分割[J].重慶交通大學學報(自然科學版),2010,29(3):488-492. CAO Jianqiu,WANG Huaqing,LAN Zhangli.Skin color division base on modified YCrCb color space [J].JournalofChongqingJiaotongUniversity(NaturalScience),2010,29(3):488-492.

An Algorithm of Key Frame Extraction in Road Monitoring VideoBased on Correlation Coefficient

LAN Zhangli, SHUAI Dan, LI Yicai

(School of Information Science & Engineering, Chongqing Jiaotong University, Chongqing 400074, P.R.China)

In order to effectively extract the key frame from the road monitoring video photographed by fixed cameras, the algorithm of extracting key frame based on correlation coefficient was proposed. Firstly, theRGBvalues of the video monitoring video were translated into gray values by the proposed algorithm. Secondly, combining with the sliding window, whether the current frame was the key frame was determined by comparing the threshold and absolute value between the correlation coefficient of the current frame and the current key frame. Experimental results show that the algorithm can not only extract the key frame effectively, but also has the clear process and can avoid redundant key frame. Finally, the extracted key frame was evaluated by the frame difference based on Euclidean distance, which verified the validity of the algorithm and the correctness of the key frame.

traffic and transportation engineering; key frame; correlation coefficient; sliding window; road monitoring

2014-08-06；

2014-10-27

重慶市教委科學技術研究項目(KJ130421); 重慶市自然科學基金項目(CSTC2011jjA10054); 重慶市科技攻關項目(CSTC2011AC6102)

藍章禮(1973—)，男，重慶人，教授，主要從事數(shù)字圖像處理與模式識別、交通信息化、太陽能光伏發(fā)電方面的研究。E-mail: 674437004@qq.com。

10.3969/j.issn.1674-0696.2016.01.25

U.491.1+16

A

1674-0696(2016)01-129-05