俞文靜，張明軍，王 影

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

一種基于圖像背景減除的菱形運(yùn)動(dòng)估計(jì)算法

俞文靜，張明軍，王 影

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

運(yùn)動(dòng)估計(jì)是視頻圖像處理技術(shù)中解決時(shí)間冗余的關(guān)鍵技術(shù)，在視頻圖像恢復(fù)、序列圖像超分辨率等領(lǐng)域有非常重要的應(yīng)用。菱形搜索算法(Diamond Search，DS)是一種較好的視頻圖像處理塊搜索算法，但其效率與搜索模板和空間有很大關(guān)系。針對(duì)視頻監(jiān)控圖像序列運(yùn)動(dòng)目標(biāo)變化小，背景固定的特點(diǎn)，對(duì)菱形搜索算法進(jìn)行了改進(jìn)，設(shè)計(jì)了一種“大十字”粗搜索模板和“小菱形”細(xì)搜索模板相結(jié)合的新搜索模板，使其更符合監(jiān)控視頻圖像中運(yùn)動(dòng)矢量的特性?；诒尘安脸蟮囊曨l圖像，改變了搜索的初始搜索點(diǎn)，改進(jìn)的搜索算法不搜索背景，只搜索運(yùn)動(dòng)物體所在塊，減小了搜索空間。通過改進(jìn)搜索算法和減小搜索空間的手段來提高算法效率。實(shí)驗(yàn)結(jié)果表明，與基本菱形算法相比，改進(jìn)的搜索算法搜索效率提高顯著。

視頻圖像；運(yùn)動(dòng)估計(jì)；菱形搜索；搜索模板

0 引 言

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

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

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

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

菱形搜索算法[8]先使用LDSP進(jìn)行搜索，當(dāng)其MBD點(diǎn)(MAD值最小的點(diǎn))出現(xiàn)在中心點(diǎn)處時(shí)，認(rèn)為找到了最優(yōu)匹配點(diǎn)所在的區(qū)域，然后再用SDSP進(jìn)行更為精細(xì)的定位搜索，最后小模板5個(gè)點(diǎn)中的MBD點(diǎn)即為最終獲得的運(yùn)動(dòng)矢量。在視頻搜索中，假設(shè)選擇M×N的塊，且同一塊內(nèi)的像素運(yùn)動(dòng)是一致的，則搜索的絕對(duì)平均誤差函數(shù)如式(1)：

MAD(i,j)=

(1)

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

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

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

步驟2：以上一次找到的MBD點(diǎn)為中心，構(gòu)建新的LDSP并計(jì)算其他8個(gè)搜索點(diǎn)的匹配誤差，找到新模板的MBD點(diǎn)。若它位于中心位置，則轉(zhuǎn)到步驟3，否則重復(fù)步驟2。

步驟3：以上一次得到的MBD點(diǎn)為中心，構(gòu)建SDSP，在其5個(gè)搜索點(diǎn)處進(jìn)行匹配和比較，找出MBD點(diǎn)，該位置即對(duì)應(yīng)最終得到的運(yùn)動(dòng)矢量。

DS算法從大模板搜索到小模板搜索是一個(gè)由粗到細(xì)的優(yōu)化過程，其搜索方向不定，可以在各個(gè)方向上進(jìn)行，且搜索步驟之間有很強(qiáng)的相關(guān)性，性能上相對(duì)其他塊算法有很大提高，是一種在搜索速度和搜索質(zhì)量上達(dá)到很好平衡的算法。

然而，在視頻監(jiān)控領(lǐng)域[10]，特定場景下的多幀圖像，圖像序列之間的變動(dòng)較小，重點(diǎn)表現(xiàn)為移動(dòng)物體所在空間位置的差異，有時(shí)甚至監(jiān)控圖像中沒有運(yùn)動(dòng)物體，是保持靜止的圖像序列。菱形法要經(jīng)歷由大模板到小模板的變化過程，要對(duì)13個(gè)點(diǎn)進(jìn)行搜索，運(yùn)算量大，而理想情況僅需要5個(gè)搜索點(diǎn)，即DS在靜止或者小運(yùn)動(dòng)序列圖像的搜索中尚有改進(jìn)空間。

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

2 改進(jìn)的搜索算法

2.1 背景差分法運(yùn)動(dòng)目標(biāo)的提取

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

2.2 改進(jìn)的運(yùn)動(dòng)估計(jì)算法

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

圖1 搜索模板及起始點(diǎn)示意圖

改進(jìn)的算法流程圖如圖2所示。

圖2 菱形搜索算法流程圖

3 仿真實(shí)驗(yàn)與數(shù)據(jù)分析

仿真實(shí)驗(yàn)環(huán)境為Intel(R)Core(TM)i3CPU530,2.93GHz，內(nèi)存2GB，仿真平臺(tái)為MatlabR2010。采用室內(nèi)監(jiān)控視頻下的1組連續(xù)3幀的圖像作為初始圖像，如圖3所示。

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

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

表1 改進(jìn)的菱形搜索算法與基本 菱形搜索算法的比較

其次，圖5將兩種算法按搜索步長及對(duì)應(yīng)搜索時(shí)間進(jìn)行了對(duì)比。

圖3 視頻連續(xù)3幀原始圖像

圖4 運(yùn)動(dòng)目標(biāo)提取后的圖像序列

圖5 兩種算法搜索步長對(duì)應(yīng)搜索時(shí)間對(duì)比示意圖

從數(shù)據(jù)對(duì)比以及折線圖走勢可以得到，改進(jìn)的菱形算法在監(jiān)控視頻序列圖像擦除背景運(yùn)動(dòng)目標(biāo)提取之后，在搜索初始點(diǎn)上進(jìn)行改進(jìn)。在搜索的前面幾步，改進(jìn)菱形算法搜索時(shí)間效率沒有明顯優(yōu)勢，然而，從整體搜索過程看，搜索步數(shù)減少了很多，整個(gè)算法過程的平均搜索點(diǎn)數(shù)、搜索時(shí)間以及搜索步數(shù)等指標(biāo)都有下降，對(duì)算法搜索效率有很大的提高。

4 結(jié)束語

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

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

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

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

[4] 唐澤鵬,秦 雷,朱秀昌,等.運(yùn)動(dòng)估計(jì)算法分析[J].電視技術(shù),2001(12):10-13.

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

[6] 涂亞明.基于塊匹配的快速運(yùn)動(dòng)估計(jì)算法研究及應(yīng)用[D].北京:北京航空航天大學(xué),2001.

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

[8] 李 淳,馬力妮.基于菱形搜索的改進(jìn)運(yùn)動(dòng)估計(jì)算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(11):117-119.

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

[10] 劉海峰,郭寶龍,馮宗哲.用于塊匹配運(yùn)動(dòng)估值的正方形-菱形搜索算法[J].計(jì)算機(jī)學(xué)報(bào),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] 朱明旱,羅大庸.基于幀間差分背景模型的運(yùn)動(dòng)物體檢測與跟蹤[J].計(jì)算機(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

時(shí)間：2017-03-07

2015年廣東高校省級(jí)重點(diǎn)平臺(tái)和重大科研項(xiàng)目(2015KQNCX202)；廣州大學(xué)華軟軟件學(xué)院2014年教學(xué)研究、科學(xué)研究資助立項(xiàng)項(xiàng)目(ky201410)

俞文靜(1982-)，女，碩士，講師，研究方向?yàn)橛?jì)算機(jī)圖形圖像處理、優(yōu)化算法等。

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