基于塊匹配運動估計的視頻場景切換檢測算法

段淑玉 陳艷

摘 要：提出一種應用于幀率提升系統的，根據內插幀各匹配塊的均值SAD為檢測依據的場景切換檢測算法，解決場景切換時ME/MC算法因匹配失誤產生嚴重塊效應的問題.將當前內插幀的均值SADcurr與前面已生成的內插幀的均值SADpre相除，所得商與經驗閾值進行比較，若大于經驗閾值則判定發生場景切換；否則，沒有場景切換.幀率提升系統根據判定結果選擇不同的算法產生內插幀.實驗結果表明；與傳統的檢測算法相比，本文算法在場景切換檢測的準確率上有明顯的提升.

關鍵詞：場景切換檢測；塊匹配；運動估計；幀率提升

中圖分類號：TP317.4 DOI：10.16375/j.cnki.cn45-1395/t.2018.04.015

0 引言

場景切換是視頻中較為常見的特征，場景切換檢測是數字視頻后處理中的關鍵技術之一.在時域降噪、視頻編碼、基于運動估計運動補償的幀率提升等應用中，準確檢測場景切換對降噪效果、編碼效率、內插幀質量等具有明顯的改善作用.目前較為流行的場景切換檢測算法主要有灰度分割法[1]、直方圖分割法[2]、邊緣分割法[3]、基于DCT系數的檢測法[4]、基于運動矢量的檢測法和基于宏塊編碼類型的檢測法[5]等，其中應用最為廣泛的屬灰度分割法和直方圖分割法.方宏俊等[6]在直方圖和平均亮度檢測法的基礎上提出一種適配分辨率動態變化的低復雜度場景切換算法，在視頻源分辨率發生變化時保持較低的錯判率；劉輝等[7]將場景切換檢測應用于HEVC碼率控制中來提高視頻編碼質量.

基于ME/MC（Motion Estimation/Motion Compensation）的幀率提升算法利用相鄰幀之間的運動相關性進行運動估計和運動補償[8]，產生的內插幀質量完全取決于運動估計的準確性.當發生場景切換時，相鄰幀之間的相關性下降，運動估計算法失效，因此產生的內插幀會出現嚴重的塊效應，嚴重影響幀率提升效果.如圖1所示，圖1（c）為發生場景切換時生成的內插幀，該內插幀具有嚴重的塊效應，將造成視頻的抖動，嚴重影響觀看效果.文獻[9]將場景切換應用于自適應電影源模式檢測算法中，并提出多級分塊χ2直方圖檢測算法，但復雜度過高.文獻[10]采用改進的直方圖檢測法用于無縫自適應數字視頻后處理中，并且先進行場景切換檢測，再做運動估計運動補償的幀率轉換.本文利用幀率提升系統中運動估計階段（即ME）產生的匹配塊SAD值，提出以內插幀最佳匹配塊SAD值的均值為判決依據的場景切換檢測算法，實驗表明，該算法對各種場景切換具有較好的檢測效果.

1 基于塊匹配運動估計的視頻場景切換檢測算法描述

1.1 塊匹配雙向運動估計算法

運動估計算法是幀率提升系統的核心部分，其目的是根據幀間的運動信息得到幀內每一個像素點的運動位移（運動矢量），運動補償產生的內插幀質量依賴于運動矢量的準確性.基于塊的運動估計是最常用的搜索算法，雙向運動估計方法能克服單向運動估計方法固有的重疊、空洞問題而被廣泛使用，其示意圖如圖2所示.其中f（n-1）和f（n+1）為前后原始參考幀，fn為內插幀，Bn為內插幀中的待插塊，B（n-1）和B（n+1）為搜索到的最佳匹配塊，兩者位移的一半即為Bn的運動矢量.搜索最佳匹配塊時用的最多的匹配準則是SAD（Sum of Absolute Difference）準則.該準則只需做減法和加法運算，硬件實現簡單，運算量小，計算公式如式（1）所示.其中，M和N為匹配塊大小，fc（m，n）和fr（m，n）分別為前后參考幀.

[SAD（i，j）=m=1Mn=1Nfc（m，n）-fr（m+i，n+j）] （1）

如果前后參考幀之間發生了場景切換，則使用SAD匹配準則尋找最佳匹配塊的算法失效，在搜索范圍內找到的SAD值最小的匹配塊，并不是真正的匹配塊，此時SAD值將是一個較大的值.對于整個內插幀來說，所有待插塊的運動估計都是失效的，每一個待插塊的最佳匹配塊的SAD值都很大，所有這些SAD值求和取平均，得到的均值SAD也很大.若未發生場景切換，最佳匹配塊對應的SAD值將是一個較小值，在整個內插幀中，即使存在個別待插塊匹配失誤（即個別SAD值較大），但對所有SAD值求和取平均后，得到的均值SAD也較小.因此內插幀的均值SAD可作為衡量是否發生場景切換的參量.

1.2 視頻場景切換檢測算法及步驟

對相鄰兩幀圖像做運動估計時，如果發生場景切換，則SAD匹配準則失效，在搜索范圍內找到的最佳匹配塊對應的最小SAD值也將是一個較大的值.因此，本文使用當前內插幀均值SAD作為場景切換檢測的基礎，均值SAD計算如下：

CurrSADavg （n）=[1M×N][i=1M][j=1N]SAD（i，j） （2）

其中，[M×N]為內插幀中待插塊的個數，SAD（i，j）是第（i，j）個待插塊的最佳匹配塊SAD值.CurrSADavg （n）不能單獨作為場景切換的判斷依據，但沒有發生切換的場景中匹配塊搜索策略、搜索范圍的大小、運動物體運動的快慢都會對CurrSADavg （n）的值產生影響.為消除這種影響，應將當前內插幀的均值SAD與前面已生成的內插幀均值SAD進行比較，若與已生成內插幀的均值SAD相比，當前內插幀的均值SAD發生突變，則可判定當前內插幀處于場景切換的兩幀之間.

PreSADavg（n）= α×CurrSADavg（n）+（1-α）×PreSADavg （n-1） （3）

式（3）是一個計算所有內插幀的均值SAD的加權和的過程，PreSADavg（n）與前面各內插幀的均值SAD都有關，并且離當前內插幀越近，其均值SAD對PreSADavg（n）的影響也就越大.α是權重因子，表明的是與當前內插幀的距離對PreSADavg（n）的影響，α越大則表示距離近的內插幀的均值SAD影響越大.本文實驗中設置α為0.5.視頻序列第一幀內插幀以及場景切換后第一幀內插幀的PreSADavg（n）就等于CurrSADavg（n）.判斷當前是否發生場景切換的依據K（n）為：

K（n）=[CurrSADavg （n）PreSADavg （n-1）] （4）

視頻序列的第一幀內插幀對應的K（n）為1，場景切換發生后的第一幀內插幀的K（n）也為1.將K（n）與經驗閾值Th進行比較，大于Th則表示當前發生場景切換.算法具體實現步驟如下：

Step 1 從視頻流中獲取用于產生內插幀的前后參考幀F（n）和F（n+1）；

Step 2 采用基于SAD塊匹配的雙向運動估計算法計算內插幀中每一待插塊的運動矢量，記錄下每一最佳匹配塊的SAD值；

Step 3 當前內插幀的運動矢量搜索完畢，計算各匹配塊的SAD的平均值CurrSADavg （n）；

Step 4 如果是第一幀內插幀，則K（1）=1，PreSADavg（1）=CurrSADavg（1），場景切換標記SceneChangeFlag=0，轉Step 6；否則，轉Step 5；

Step 5 判斷SceneChangeFlag是否為1，如果為1，說明F（n-1）與F（n）之間發生了場景切換，F（n）與F（n-1）之間不可能再發生場景切換，所以置K（n）=1，PreSADavg重新被賦值，即PreSADavg（n）=CurrSADavg （n），并將切換標記SceneChangeFlag置回0；如果SceneChangeFlag為0，說明F（n-1）與F（n）之間沒有發生場景切換，則K（n）=CurrSADavg （n）/ PreSADavg（n-1），并且更新PreSADavg（n）= α×CurrSADavg（n）+（1-α）×PreSADavg （n-1）；

Step 6 將K（n）與閾值Th比較，大于Th，則SceneChangeFlag=1，表示F（n）和F（n+1）之間發生了場景切換；

Step 7 如果SceneChangeFlag為1，無需進行運動補償，內插幀直接復制F（n）即可；否則，采用運動補償方法產生內插幀.

2 算法仿真結果及對比分析

2.1 仿真平臺及實驗步驟

在MATLAB R2016a上進行仿真實驗，實驗對象選擇8段mp4格式的電視電影片段，幀速率為25幀/秒，分辨率為640 × 480.這8段電視電影片段特征不同，如表1所示.

實驗步驟如下：

Step 1 將視頻序列轉換成幀圖像，并將彩色的幀圖像轉換成灰度圖像；

Step 2 為了提高切換的頻率，在原始圖像序列基礎上剪輯掉一些未發生場景切換的中間幀，以減少實驗時間；

Step 3 依次讀取圖像序列，采用雙向運動估計方法及SAD值匹配準則進行內插幀的運動估計，再根據本文提出的場景切換檢測算法判斷前后幀之間是否發生場景切換；

Step 4 用像素絕對差值法和平均亮度統計法去檢測相同的視頻序列；

Step 5 將3種算法的檢測結果進行對比分析，驗證本文算法的優越性.

2.2 分場景的仿真實驗

根據視頻片段的特征，將視頻序列分成2種場景進行實驗，分別為普通場景和切換前后圖像亮度變化較小場景.

1）普通場景

所謂普通場景即是場景發生切換時，前后兩幀圖像的內容、紋理結構和亮度發生明顯改變.如圖3所示.

設置閾值Th為3，權重因子[α]為0.5，3個測試序列的實驗結果如圖4所示.其中，橫坐標為圖像幀序號，縱坐標為式（4）中的K值，判斷是否發生場景切換取決于K值與閾值的比較.

（a）《新聞》視頻序列的K值

從圖4中可以看出，在發生場景切換時，K發生突變，其值遠遠大于未發生場景切換時的值，故根據K值判斷是否發生場景切換是可行的.

2）切換前后圖像亮度變化較小場景

在一些球賽或是整體過暗或過亮的視頻序列中，發生場景切換時，切換前后圖像亮度沒有明顯變化，如圖5所示.

實驗中，設置閾值Th為2，[α]為0.5.其中，橫坐標為圖像幀序號，縱坐標為式（4）中的K值.

從圖6、圖7中可以看出，在過暗或亮度變化不大的視頻序列中，發生場景切換時部分幀圖像的K值并沒有突變，因此誤判率和漏檢率會比普通場景的高，K的閾值Th選取更復雜.

2.3 仿真結果對比分析

選取錯判率[Rf]和漏檢率[Rm]作為場景切換算法的評價標準，漏檢表示真實發生了場景切換但是沒有被算法檢測到的情況，誤判是指實際沒有發生場景切換卻被算法判斷為發生了切換的情況.其公式分別如下：

[Rm=NmNc+Nm] （5）

[Rf=NfNc+Nf] （6）

其中，[Nc]——正確檢測出場景切換的次數，[Nm]——遺漏檢測出場景切換的次數，[Nf]——錯誤判斷了場景切換的次數.將本文算法與傳統的用于數字圖像視頻后處理芯片中的場景切換檢測算法如像素絕對差值法[11]、平均亮度統計法[12]和參考文獻[6]提出的算法進行比較.比較結果如表2所示.

從表2中可以看出，像素絕對差值法的平均錯判率達到0.238，漏檢率是0.169；平均亮度統計法比前者略有優勢，錯判率和漏檢率分別為0.232和0.116；參考文獻[6]的錯判率和漏檢率較前兩者都有較大改善，分別為0.160和0.043.本文算法的錯判率和漏檢率分別為0.047和0.098，較前兩種算法，錯判率提升幅度分別為80%和79%，漏檢率提升幅度為42%和16%，尤其在過暗或亮度變化不大的場景下，本文算法優勢明顯.這是因為像素絕對插值法和平均亮度統計法是基于像素或每一幀圖像內容的亮度變化來判斷場景是否發生了切換，因此對一些場景切換但圖像平均亮度并未發生變化，或者沒有場景切換而有部分圖像內容發生較大亮度變化的情況，存在較高的“漏檢”和“錯判”可能.文獻[6]是對基于直方圖分布統計法的優化算法，能有效解決場景切換前后亮度變化不大而可能漏檢的問題，因此本文算法與之相比，漏檢率略高，但錯判率更低.

3 結論

本文提出的場景切換檢測算法是應用于幀率提升系統的，根據運動估計階段內插幀的最佳匹配塊對應SAD值的均值作為檢測依據的一種算法，該算法與兩種傳統的用于視頻后處理芯片中的檢測算法即像素絕對差值法、平均亮度統計法以及參考文獻[6]的算法相比，在以錯判率和漏檢率表征的檢測準確率上有了明顯的提升.

參考文獻

[1]LUO L J，ZOU C R，HE Z Y. A new algorithm on MPEG-2 target bit-number allocation at scene changes[J]. IEEE Transactions on Circuits and Systems for Video Technology，1997，7（5）：815-819.

[2]FERNANDO W A C，CANAGARARAJAH C N，BULL D R. Fade-in and fade-out detection in video sequences using histograms[C]// IEEE International Symposium on Circuits and Systems，2000.

[3]RAINER L. Reliable transition detection in videos：a survey and practitioner's guide[J]. International Journal of Image and Graphics，2001，1（3）：469-486.

[4]戴寧赟，朱光喜. 一種場景切換的碼率控制方法[J].計算機應用，2007，27（S1）：369-371.

[5]PEI S C，CHOU Y Z. Efficient MPEG compressed video analysis using macroblock type information[J]. IEEE Transactions on Multimedia，1999，1（4）：321-333.

[6]方宏俊，宋利，楊小康. 適配分辨率動態變化的低復雜度視頻場景切換檢測方法[J].計算機科學，2017，44（2）：290-295.

[7]劉輝，劉立程，郝祿國，等. 一種場景切換下的HEVC碼率控制算法[J].電視技術，2017，41（6）：1-5.

[8]段淑玉，徐奕奕，李春貴，等. 一種基于運動矢量時域遞歸的運動估計算法[J].廣西科技大學學報，2015，26（2）：36-40.

[9]袁高陽. 自適應逐行電影源模式檢測算法研究[D].西安：西安電子科技大學，2015.

[10]方宏俊. 適配智能電視分辨率動態變化的視頻后處理技術研究[D].上海：上海交通大學，2015.

[11]史久根，許林，張超. 一種場景自適應的H.264幀層碼率控制算法[J].計算機應用研究，2010，27（5）：1968-1969.

[12]王悅，薛永林. 基于場景切換的碼率控制方法[J].電視技術，2009，33（12）：17-20.

Scene change detection algorithm based on block matching motion estimation

DUAN Shuyu， CHEN Yan

（School of Computer Science and Communication Engineering， Guangxi University of Science and Technology， Liuzhou 545006， China）

Abstract： This paper proposes a scene change detection algorithm based on the mean SAD of the interpolated frames matching blocks， which is used in frame rate up system. This algorithm is used to solve the serious block effect problems due to mismatch in ME/MC algorithm when the scene is changed. We divide the average of the current interpolated frame SADcurr by the average of the previously generated interpolated frames SADpre and compare the resulting quotient with the empirical threshold， if we find the quotient is greater than the threshold， it is determined that a scene change occurs； otherwise， there has no scene change. The frame rate up system uses different interpolating algorithms based on the comparison results. Compared with the traditional detection algorithms， the experimental results show that the proposed algorithm has a significant improvement in the accuracy of scene change detection.

Key words： scene change detection； block match； motion estimation； frame rate up

（學科編輯：黎 婭）