一種基于圖像背景減除的菱形運動估計算法

俞文靜，張明軍，王 影

(廣州大學華軟軟件學院，廣東 廣州 510990)

一種基于圖像背景減除的菱形運動估計算法

俞文靜，張明軍，王 影

(廣州大學華軟軟件學院，廣東 廣州 510990)

運動估計是視頻圖像處理技術中解決時間冗余的關鍵技術，在視頻圖像恢復、序列圖像超分辨率等領域有非常重要的應用。菱形搜索算法(Diamond Search，DS)是一種較好的視頻圖像處理塊搜索算法，但其效率與搜索模板和空間有很大關系。針對視頻監控圖像序列運動目標變化小，背景固定的特點，對菱形搜索算法進行了改進，設計了一種“大十字”粗搜索模板和“小菱形”細搜索模板相結合的新搜索模板，使其更符合監控視頻圖像中運動矢量的特性。基于背景擦除后的視頻圖像，改變了搜索的初始搜索點，改進的搜索算法不搜索背景，只搜索運動物體所在塊，減小了搜索空間。通過改進搜索算法和減小搜索空間的手段來提高算法效率。實驗結果表明，與基本菱形算法相比，改進的搜索算法搜索效率提高顯著。

視頻圖像；運動估計；菱形搜索；搜索模板

0 引 言

運動估計[1-2]和運動補償是視頻圖像處理技術中解決時間冗余的關鍵技術，運動估計算法的好壞直接影響著視頻圖像的顯示效果。在運動估計方法研究領域[3-4]，一些先進的思想、算法和技術相繼提出，已經形成了一套基本理論，并取得了不錯的研究成果。其中塊匹配法因原理簡單、便于實現等優點得到了廣泛應用。在塊匹配法中[5-6]，菱形搜索算法(Diamond Search，DS)是目前公認的一種較好的塊搜索算法，已被MPEG4標準采用。然而，在視頻監控領域，特定場景下的多幀圖像、圖像序列之間的變動較小，重點表現為移動物體所在空間位置的差異，有時甚至監控圖像中并沒有運動物體，是保持靜止的圖像序列，菱形算法的搜索形狀有時得不到全搜索，其次搜索點數較多，制約著算法效率。

針對視頻監控這種特定應用場景下的多幀圖像運動估計方法進行研究。為了進一步提高性能，加快搜索速度，提出了利用背景差分法分離監控視頻背景，從而快速預測菱形塊的起始搜索點，并根據序列圖像中的運動矢量十字中心的偏置特性，設計了從“大十字”到“小菱形”塊的搜索模板，并根據視頻背景塊的獲取，可提前終止搜索。

1 基本菱形搜索算法(DS算法)

在塊匹配算法中[7]，搜索模板的形狀和大小不但影響整個算法的運行速度，而且也影響算法的搜索質量。搜索窗口太小，容易陷入局部最優；搜索窗口太大，容易產生錯誤的搜索路徑。DS[8]利用視頻序列中運動矢量中心點偏移的特點，采用了兩種搜索模板：分別是9個搜索點的大菱形搜索模板(LDSP)和5個點的小菱形搜索模板(SDSP)。

菱形搜索算法[8]先使用LDSP進行搜索，當其MBD點(MAD值最小的點)出現在中心點處時，認為找到了最優匹配點所在的區域，然后再用SDSP進行更為精細的定位搜索，最后小模板5個點中的MBD點即為最終獲得的運動矢量。在視頻搜索中，假設選擇M×N的塊，且同一塊內的像素運動是一致的，則搜索的絕對平均誤差函數如式(1)：

MAD(i,j)=

(1)

其中，fk和fk-1分別為當前幀和上一幀的灰度值；(i,j)為位移量。

基本DS算法的步驟如下[9]：

步驟1：初始化原點(0，0)為LDSP的中心點，用大菱形模塊在搜索區域中心和周圍8個點處進行匹配，如果最小塊誤差MBD位于中心位置，則轉到步驟3，否則轉到步驟2。

步驟2：以上一次找到的MBD點為中心，構建新的LDSP并計算其他8個搜索點的匹配誤差，找到新模板的MBD點。若它位于中心位置，則轉到步驟3，否則重復步驟2。

步驟3：以上一次得到的MBD點為中心，構建SDSP，在其5個搜索點處進行匹配和比較，找出MBD點，該位置即對應最終得到的運動矢量。

DS算法從大模板搜索到小模板搜索是一個由粗到細的優化過程，其搜索方向不定，可以在各個方向上進行，且搜索步驟之間有很強的相關性，性能上相對其他塊算法有很大提高，是一種在搜索速度和搜索質量上達到很好平衡的算法。

然而，在視頻監控領域[10]，特定場景下的多幀圖像，圖像序列之間的變動較小，重點表現為移動物體所在空間位置的差異，有時甚至監控圖像中沒有運動物體，是保持靜止的圖像序列。菱形法要經歷由大模板到小模板的變化過程，要對13個點進行搜索，運算量大，而理想情況僅需要5個搜索點，即DS在靜止或者小運動序列圖像的搜索中尚有改進空間。

因此在研究DS算法的基礎上，提出利用背景差分法分離監控視頻背景，從而快速預測菱形塊的起始搜索點，根據序列圖像中運動矢量十字中心的偏置特性，設計了改進的菱形塊搜索模板，并根據擦除背景后相鄰幀圖像中運動目標的角點位置，指導搜索模板的搜索方向，從而快速搜索到目標范圍。

2 改進的搜索算法

2.1 背景差分法運動目標的提取

背景差分法[11-12]是采用圖像序列中的當前幀和背景參考模型進行比較來檢測運動物體的一種方法。由于監控視頻的背景固定，背景建模容易實現，因此采用背景差分法進行視頻運動目標檢測，在檢測的基礎上擦除背景，提取運動目標。然而，該方法檢測運動目標時容易受圖像采集過程中誤差、背景光線以及環境等因素的干擾，使背景擦除效果受到影響。因此，對背景模型的獲取采用了多種環境下的動態背景[13]，使用人工背景模型選擇，根據視頻的當時天氣環境特點，光亮度(同位置像素HSI模型中的亮度I的差)，通過視頻序列的幀間信息[14]，在動態背景里選擇相應的背景圖像，再做背景擦除。

2.2 改進的運動估計算法

利用背景差分法進行運動目標的背景擦除之后，可以初步估計運動目標的位置。考慮到監控視頻中運動對象速度的不一致性，而基于視頻監控畫面背景固定，相鄰幀之間變化小的特點，對基本菱形算法進行了如下兩個方面的改進：首先，利用背景差分法分離監控視頻背景，從而快速預測菱形塊的起始搜索點，對菱形搜索算法起始搜索點進行改進，其初始搜索點由原來的原點(0,0)，變為擦除背景外的運動目標角點：即運動目標上x坐標與左y坐標構成的左上角交匯點(x0,y0)，如圖1所示。這樣省去了視頻圖像背景區域的搜索計算，提高了搜索效率。其次，根據序列圖像中運動矢量十字中心的偏置特性[10]，對基本菱形搜索算法的搜索模板進行改進。大搜索模板是搜索的粗估計，采用大十字模板，符合運動矢量的偏置特性，細搜索模板依舊采用SDSP，采用如圖1所示的9個搜索點的LCSP和5個點的SDSP，另外在LCSP中，利用前面相鄰兩幀圖像中得到的運動目標角點(x0,y0)位置變化屬性，來指導搜索方向，可以快速地粗搜索到目標。

圖1 搜索模板及起始點示意圖

改進的算法流程圖如圖2所示。

圖2 菱形搜索算法流程圖

3 仿真實驗與數據分析

仿真實驗環境為Intel(R)Core(TM)i3CPU530,2.93GHz，內存2GB，仿真平臺為MatlabR2010。采用室內監控視頻下的1組連續3幀的圖像作為初始圖像，如圖3所示。

首先，假設監控環境良好，利用背景差分法進行運動目標提取，可以得到如圖4所示的擦除了背景的圖像序列。該圖像序列可以根據運動物體的提取位置，確定運動目標的角點作為進一步改進菱形搜索算法的LCSP的初始中心點，如圖4所示的(x0,y0)。應用改進菱形搜索算法進行運動目標的運動估計，從而得到視頻中運動物體的運動矢量。

實驗表明，改進的菱形搜索算法初始搜索點由原來的原點(0,0)，變化為擦除背景后運動物體上x坐標與左y坐標構成的左上角交匯點(x0,y0)，省去了視頻圖像背景區域的搜索步長，并且大十字搜索模板利用去除背景后的前后幾幀中運動物體的位置關系，可以快速確定搜索方向。例如，圖4中室內監控下人行走的運動估計，分別用基本菱形搜索算法和所提出的改進菱形搜索算法進行實現，表1統計了實驗中兩種算法運行時的參數比較。

表1 改進的菱形搜索算法與基本 菱形搜索算法的比較

其次，圖5將兩種算法按搜索步長及對應搜索時間進行了對比。

圖3 視頻連續3幀原始圖像

圖4 運動目標提取后的圖像序列

圖5 兩種算法搜索步長對應搜索時間對比示意圖

從數據對比以及折線圖走勢可以得到，改進的菱形算法在監控視頻序列圖像擦除背景運動目標提取之后，在搜索初始點上進行改進。在搜索的前面幾步，改進菱形算法搜索時間效率沒有明顯優勢，然而，從整體搜索過程看，搜索步數減少了很多，整個算法過程的平均搜索點數、搜索時間以及搜索步數等指標都有下降，對算法搜索效率有很大的提高。

4 結束語

針對視頻監控這種特定環境下的視頻圖像運動估計問題，在研究基本菱形搜索算法的基礎上，提出了一種基于視頻圖像背景擦除的改進菱形塊搜索運動估計算法。實驗結果表明，搜索效率和步長都得到了顯著的提高。但在實驗中，背景減除法對背景模型的要求很高，不同光照條件及環境背景的選擇不同，如何提高通過視頻圖像判斷背景選擇的速度，快速更新適合的背景將是下一步的研究重點。

[1]GonzalezRC,WoodsRE.數字圖像處理[M].阮秋琦，阮宇智，譯.第2版.北京：電子工業出版社，2003.

[2]TekalpAM.Digitalvideoprocessing[M].北京:清華大學出版社，1998.

[3] 黃新生,楊慶偉,王亦平,等.圖像序列運動估計技術綜述[J].計算機仿真,2008,25(5):180-184.

[4] 唐澤鵬,秦 雷,朱秀昌,等.運動估計算法分析[J].電視技術,2001(12):10-13.

[5]ZhuS,MaKK.Anewdiamondsearchalgorithmforfastblockmatchingmotionestimation[J].IEEETransactionsonImageProcessing,2005,9:287-290.

[6] 涂亞明.基于塊匹配的快速運動估計算法研究及應用[D].北京:北京航空航天大學,2001.

[7] 陳 宮,牛秦洲.圖像序列運動估計中經典塊匹配算法研究[J].計算機應用與軟件,2012,29(5):147-151.

[8] 李 淳,馬力妮.基于菱形搜索的改進運動估計算法研究[J].計算機技術與發展,2008,18(11):117-119.

[9]Anewpredictivediamondsearchalgorithmforblockmotionestimation[EB/OL].2000.http://citeseer.nj.nec.com/tourapis00new.htm.

[10] 劉海峰,郭寶龍,馮宗哲.用于塊匹配運動估值的正方形-菱形搜索算法[J].計算機學報,2002,25(7):747-752.

[11]WrenC,AzarbayA,DarrellT,etal.Pfinder:realtimetrackingofthehumanbody[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1997,19(7):780-785.

[12]HaritaogluL,HarwoodD,DavisLS.W4:real_timesurveillanceofpeopleandtheiractivities[J].IEEETransactionsonPatternAnalysisandMachineIntelligenee,2000,22(8):809-813.

[13] 朱明旱,羅大庸.基于幀間差分背景模型的運動物體檢測與跟蹤[J].計算機測量與控制,2006,14(8):1004-1006.

[14]ZhuC,LinX,ChauLP.Hexagon-basedsearchpatternforfastblockmotionestimation[J].IEEETransactionsonCircuitsandSystemforVideoTechnology,2002,12(5):349-355.

A Diamond Motion Estimation Algorithm for Image Based on Background Erasure

YU Wen-jing,ZHANG Ming-jun,WANG Ying

(South China Institute of Software Engineering,Guangzhou 510990,China)

Motion estimation is the key technology to solve the time redundancy in video image processing and plays an important role in the field of video image restoration,image super resolution and so on.Diamond Search (DS) is a kind of better video image processing block search algorithm,but its efficiency is connected with the search space.According to the small change of the video surveillance image sequence and the characteristics of the fixed background,a diamond search algorithm has been improved.A new search pattern combined LCSP (Large Cross Search Pattern) with SDSP (Small Diamond Search Pattern) has been designed,which is more consistent with the characteristics of motion vectors in the surveillance video image.Based on the background eraser video image,by changing the initial search point,the improved search algorithm does not search the background but only searches the block of moving objects,so as to reduce the search space.The efficiency of the algorithm has been increased by improving the search algorithm and reducing the search space.Experimental results show that compared with the basic diamond search algorithm,the efficiency of the improved algorithm has been greatly improved.

video image;motion estimation;diamond search;search pattern

2016-04-29

2016-08-17

時間：2017-03-07

2015年廣東高校省級重點平臺和重大科研項目(2015KQNCX202)；廣州大學華軟軟件學院2014年教學研究、科學研究資助立項項目(ky201410)

俞文靜(1982-)，女，碩士，講師，研究方向為計算機圖形圖像處理、優化算法等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0920.012.html

TP301.6；TP391.9

A

1673-629X(2017)04-0042-04

10.3969/j.issn.1673-629X.2017.04.010