趙樹言　路艷雪　韓曉霞

摘要：針對嵌入式設備對視頻背景的實時提取問題，提出一種基于最近鄰域像素梯度（N2PG）穩(wěn)定性的視頻背景快速提取方法。首先，以視頻中任意幀作為初始背景，并計算此背景圖像的N2PG矩陣；然后，以背景幀之后若干幀圖像作為背景更新圖像，同理計算N2PG矩陣；最后，將背景圖像N2PG矩陣與更新圖像N2PG矩陣進行差分，并通過實時估計的梯度穩(wěn)定性閾值快速判斷背景模型中各像素點是靜態(tài)背景像素點還是非背景像素點，進而對其更新或替換，以得到視頻當前背景。經計算機仿真測試，與常用的卡爾曼濾波法和混合高斯法相比，基于N2PG的視頻背景提取方法得到相同質量背景僅需10～50幀圖像，并且平均處理速度分別提高36%和75%；和改進的視覺背景提?。╒iBe）算法相比，在所需幀數和所得背景質量相近的情況下，該算法背景更新速度提升一倍。實驗結果表明，基于N2PG的視頻背景提取算法具有很強的自適應性，并且速度快、內存消耗小，背景提取準確度達到90%以上，可滿足真實自然環(huán)境下嵌入式視覺設備的應用。

關鍵詞：快速背景提取；鄰域像素梯度；視頻背景；嵌入式系統(tǒng)；機器視覺

中圖分類號：TP391.41

文獻標志碼：A

0引言

隨著機器視覺技術的不斷發(fā)展成熟，以及嵌入式智能視覺設備越來越多的產生和應用，對真實自然環(huán)境下視頻背景提取的要求也越來越高，尤其需要兼顧背景提取速度和質量[1]，比如智能車載監(jiān)控系統(tǒng)、無人駕駛圖像檢測系統(tǒng)、移動機器人視覺系統(tǒng)和無人機視覺系統(tǒng)等。因為統(tǒng)計表明視覺系統(tǒng)的研究對象80%均為運動物體，而背景相減法[2]又是對視頻中運動物體檢測最簡單、最有效的方法。

真實復雜環(huán)境下，嵌入式視覺設備對視頻背景實時、準確、快速提取和建模的主要困難和挑戰(zhàn)在于一方面要求算法復雜度要低、內存消耗要小，另一方面又要求能適應復雜的自然環(huán)境變化影響，比如天氣、光線和場景、攝像頭本身移位、晃動等[3]。而目前已有的背景提取算法多針對于某種特定場景有效，或高度依賴于實驗室高性能計算機，或過多依賴于先驗知識，相對普適性較低、實時性不強，難以滿足嵌入式智能視覺系統(tǒng)的要求。對此，本文提出了一種基于最近鄰域像素梯度（Nearest Neighbor Pixel Gradient，N2PG）穩(wěn)定性的視頻背景快速提取方法。

1相關工作

目前比較常用的背景提取方法主要可分為兩類：基于像素時間分布特征和基于像素空間分布特征?；谙袼貢r間分布特征的背景建模方法主要有均值法[4]、幀間差分法[5]、基于區(qū)間分布的自適應算法[6]等；基于空間分布特征的代表性算法如視覺背景提?。╒isual Background Extractor， ViBe）算法[7]。

其中均值法以視頻前n幀圖像各像素的平均值作為背景圖像，該方法簡單容易，但過于粗糙，不適合復雜變化環(huán)境。后來文獻[8]提出了改進的差分均值算法，部分解決了均值法所造成的殘影影響，但實用性依然不強。

對于差分法，在實驗室等理想環(huán)境可以快速準確提取背景，但是對于有光照影響等自然環(huán)境明顯失效，也不能解決背景有變化的情況。對此，Koller等[9]提出了卡爾曼濾波法解決了背景光線變化問題，再后來Stauffer等[10]提出的混合高斯法也解決了背景變化問題，但這兩種方法都需要比較漫長的背景初始化過程，同時也大大增加了算法復雜度，提高了對硬件的要求，這些不足使其難以應用于實時性要求較高的嵌入式系統(tǒng)。

區(qū)間分布自適應背景建模算法不需要復雜的初始化過程，相對適合實時系統(tǒng)。但是其區(qū)間劃分數目對先驗知識依賴性高，所以普適性較低；而且區(qū)間劃分多，背景精度才高，這又會大大增加算法復雜度。

對于基于像素的非參數化隨機樣本模型算法，即ViBe算法，以及其后的多種改進ViBe算法，如文獻[11-12]所述，雖然都具有較好的魯棒性，尤其對動態(tài)背景中的前景檢測均有較好的效果，但是ViBe算法是假設相鄰像素點具有相似的時空分布，所以對前景與背景的交界處不能較好地作出判斷，常常因為誤判而導致所得前景輪廓有殘缺或拖影現象，這對后續(xù)的深度測量和識別等操作都不利。同時，ViBe算法所得背景是一種近似背景，對相似度閾值、鄰域半徑等參數依賴性大，若采用固定的相似度閾值，通常會降低算法魯棒性；若采用變化的相似度閾值，又會大大增加運算量。

2最小鄰域像素梯度分析

2.1相關定義

若將視頻看作是多幀圖像的順序組合，則可以用集合表示為{Ik（x，y）}，其中：k表示幀序號，I表示視頻的單幀圖像?，F將單幀圖像各像素點的灰度值用坐標表示為v（x，y），則N2PG算法中相關定義如下：

最近鄰域像素：規(guī)定某像素點上、下、左、右四個方向最近相鄰的n個像素點為該像素的最近鄰域像素。依次用該中心像素點坐標表示為vi（x，y）（i=1，2，…，n，習慣以中心像素點鄰域由內向外第一層左像素為起點，逆時針順序編號，默認i取值1～4），以后將該中心像素點稱作核像素點。對于每幀圖像邊緣的像素，為計算方便，默認其所缺失的所有最近鄰域像素灰度值等于其核像素值。

范值矩陣：為計算和描述方便，文中將與視頻像素大小相同且只有0和1兩種元素的矩陣稱為范值矩陣。其中0值元素所對應像素值無效，1值元素所對應像素有效，并且在不同情況會有不同的具體含義。

2.2最近鄰域像素梯度值特征分析

為了明顯地觀察視頻中各像素點的N2PG值在不同幀間的分布特征，現利用室外自然環(huán)境下所拍攝的一段視頻前800幀，以各像素點分別為核，對其N2PG值進行統(tǒng)計分析。實驗中隨機確定核像素點，共統(tǒng)計200個樣本。以樣本點（99，151）為例（在圖1所示兩幀抽樣圖像中均以字母P標出），首先，測量每幀中P像素點灰度值v及其四個最近鄰域像素的灰度值v1～v4（本實驗中為彩色視頻，故以各像素紅（R）、綠（G）、藍（B）三個顏色分量的算數平均值作為該像素灰度值）。再按照式（1）計算P點在各幀的N2PG值；然后對相鄰幀的N2PG值作差運算并取絕對值；最后以2維離散點統(tǒng)計圖表示出來，如圖2所示。通過所有樣本點的統(tǒng)計圖分析可以得到如下結論：自然場景下的視頻圖像，其靜態(tài)背景像素點的最近鄰域像素梯度值在鄰近幀間有一定的穩(wěn)定性。

圖2中第345幀圖像如圖1（a）所示，第759幀圖像如圖1（b）所示，可以看到除了第345幀到第356幀之間和756幀到763幀之間的N2PG值有較大跳變之外（臨界點分別以A、B、C、D示出），其余N2PG值在鄰近幀間變化很小，甚至為零。而從A點所對應第345幀的圖像中可以看到一行人正好到達P點（此時稱P點為動態(tài)進入點）；并且，從B所對應第356幀圖像中可以觀察到該行人恰好完全離開P點（此時稱P點為動態(tài)退出點）。同樣，從圖2中C點所對應第756幀圖像可以看到正好有一輛汽車要通過P點，在第763幀圖像中該汽車正好離開P點。

通過上述實驗很容易得出，N2PG（x，y）值的穩(wěn)定程度很好地代表了其核像素點的狀態(tài)特征，可以據此判斷出此核像素點在當前幀屬于背景像素點還是動態(tài)像素點。若圖2中以水平實線表示穩(wěn)定性閾值，則很容易區(qū)分出P作為動態(tài)像素點所在幀和作為靜態(tài)背景像素點所在幀，如P作為運動物體輪廓像素時的A、B、C、D點，并且可以很好地容忍自然光照變化等。

綜上實驗可知N2PG值具有很好的時空代表性，在空間分布上它代表了核像素點與其鄰域像素的相關程度，在時間分布上間接反映了其核像素點的穩(wěn)定性。

2.3二值圖像模型算法分析

為了更形象、更直觀地分析N2PG算法，此時簡化視頻模型，假設像素為4×4，并且只有黑白兩色（黑色像素值為1，白色像素值為0）。如圖3（a）所示，A、B、C為從該視頻中依次抽取的三幀原始圖像，圖像中每個小方格代表一個像素點，黑色像素點表示運動物體，背景像素均為白色。

首先指定A圖像作為背景初始圖像，B和C作為背景更新圖像。再根據式（1）分別以每幀各像素點為核，求取A、B和C的N2PG矩陣。各N2PG矩陣圖像分別如圖3（b）中A′、B′和C′所示，圖中白色方框表示該像素的N2PG值為0，斜線陰影表示N2PG值為1，黑色方框表示N2PG值為2。

然后對N2PG矩陣A′和B′作差分運算，并對結果按照非零元素置1的規(guī)則處理可得準范值矩陣WA-B，若1值元素用陰影表示，0值元素用白色表示，則如圖3（c）中A-B所示。很顯然此矩陣圖像中1值元素所構成的所有閉合連通區(qū)域邊緣正好是運動物體在背景圖像A和背景更新圖像B上像素點并集的外邊緣。因此可以去掉各連通區(qū)域每行和每列的第一個和最后一個1值元素（即元素值由1變?yōu)?），得到黑色矩形框所表示的動態(tài)像素區(qū)域，此時所得范值矩陣記為W1。同理，對N2PG矩陣A′和C′作差分得WA-C，歸一化、去陰影得到運動物體在A和C中的像素點并集的范值矩陣W2，如圖3（c）中A-C所示。同理，求得運動物體在圖像B和C中像素點并集的范值矩陣W3，如圖3（c）中B-C所示。因為簡化模型的特殊性，導致WA-C求取過程中產生邊緣梯度正好相消的情況，如圖中兩個灰色方框所表示的像素點，但實際圖像中此情況幾乎不存在，并且影響可以忽略，所以人為填補了圖中的兩個灰色像素點，將其值由0變成1。

分析上述規(guī)則所得W1、W2和W3，以非零元素表示動態(tài)有效像素點，可知：W1與W2的交集，再去除與W3重疊的部分，則得到原始背景圖像A中絕對動態(tài)像素點（理論上為部分黑色像素點），該像素區(qū)域用δ1表示，就可以用B或C中的相同像素區(qū)域替換；而W1和W2并集在I中的補集，則一定為原始背景圖像A中靜態(tài)背景像素點（理論上為部分白色像素點），該像素區(qū)域用δ2表示，就可以用B或C中的相同區(qū)域加權更新。

3基于N2PG的算法實現

基于N2PG的背景提取算法可以從視頻任意幀開始，先以開始幀作為初始背景，并計算背景N2PG矩陣；再以其后至少兩幀圖像作為背景更新圖像，計算出參考N2PG矩陣；最后，將背景N2PG矩陣與參考N2PG矩陣進行差分運算，通過運動物體邊緣像素的N2PG變化，確定背景模型中的靜態(tài)背景像素點，對其加權更新，同時鎖定背景模型中的動態(tài)像素點區(qū)域，并對其進行替換。

3.1N2PG算法實現步驟

步驟1任意抽取視頻中的一幀圖像I作為背景初始化圖像，存儲并記為B（x，y），再按照式（1）計算各像素點的N2PG值，以各N2PG值為元素，構建背景圖像N2PG矩陣，記為WB（x，y）。

3.2穩(wěn)定性閾值動態(tài)估計

通過分析可知，穩(wěn)定性閾值η的選擇對基于N2PG的視頻背景提取方法結果至關重要，而且在實際應用中背景N2PG矩陣和參考N2PG矩陣間的幀序號間隔并不確定，也就是說不宜采用固定參數。因此，假設視頻中任意時刻運動物體像素分布所占比例遠小于背景像素比例，則可以設計了一個計算比較簡單的穩(wěn)定性閾值動態(tài)估計方法，具體操作如下：

在3.1節(jié)所述算法步驟3中，當每次按式（2）計算得到中間矩陣DISN2PG時，隨機生成N個不同自然數（N一般取值10～100），然后將這N個數排序并按視頻像素大小分別沿X軸方向和Y軸方向對N個自然數進行放縮，組成遍布圖像I的N×N個隨機坐標。讀取所有相應坐標的DISN2PG（x，y）值，計算其平均值，最后以該平均值的3～5倍作為本次式（3）標準范值矩陣計算的穩(wěn)定性閾值，估算公式為：

4實驗結果及分析

為測試基于N2PG的視頻背景提取方法的實用性，并對該算法與目前常用算法在速度和效果方面進行對比，本文對一室外自然環(huán)境下固定攝像頭所拍攝的視頻進行背景提取實驗，視頻共2890幀，像素為320×240，所對比的背景建模方法分別為均值法、卡爾曼濾波法、混合高斯法和文獻[11]提供的改進ViBe算法，所比較參數為建立可用背景圖像所需要視頻幀數、平均每幀所需時間和背景準確度。仿真測試實驗中所用計算機CPU為Intel Core i3，內存2GB，VS2010搭建OpenCV2.49開發(fā)環(huán)境。分別用各算法對該視頻進行多次背景提取實驗，實驗測試結果統(tǒng)計如表1所示。

從表1可以明顯看到，除了均值法所得背景準確度較低，基于N2PG算法、卡爾曼濾波法、混合高斯法和ViBe算法均可以提取較好的視頻背景，并且通常情況下所得背景質量區(qū)別不大，相對ViBe算法所得背景準確度更高些。而從背景建模周期來看，基于N2PG算法和ViBe算法又具有明顯優(yōu)勢，并且基于N2PG的算法周期最短，少于50幀，原因是這兩種算法均不需要像卡爾曼濾波法和混合高斯法那樣較為復雜的背景初始化操作。最后從算法處理速度的角度，基于N2PG算法較ViBe算法相比，優(yōu)勢更明顯，完全可以滿足實時性要求較高的系統(tǒng)。

圖4所示為用基于N2PG算法在視頻第528幀和第876幀所提取背景圖像。直觀來看，所得背景均很好地消除了當前畫面的運動物體，保留了純凈的靜態(tài)背景。并且在第876幀的背景中也很好地融入了已經駐停在路口拐角處的一輛汽車，即接受了該汽車所投射像素點由動態(tài)到靜態(tài)的變化。為了更明顯地觀察基于N2PG的算法所提取背景在運動物體檢測中的效果，選擇提取背景準確度最高的ViBe算法作比較，兩種算法在528幀和876幀中運動物體檢測效果如圖5所示。觀察圖5可以看到，雖然ViBe算法對噪聲抑制能力相對較好，但再觀察所得二值圖像中運動物體的輪廓，很明顯基于N2PG的算法所得物體輪廓完整性、連通性更好，而ViBe算法所得物體輪廓殘缺嚴重，甚至檢測結果為光斑狀，這對后續(xù)的深度測量、識別等操作均造成不利影響，從此角度出發(fā)，基于N2PG的視頻背景提取方法更具研究價值。

綜上分析，從應用的角度，基于N2PG的視頻背景提取算法和ViBe算法較適合嵌入式系統(tǒng)應用，但是綜合考慮速度和質量，基于N2PG的算法更適合應用于嵌入式視覺設備，因為該算法在保證提取視頻背景質量的同時，內存需求壓力更小，背景提取速度更快，背景實時更新周期更短。

5結語

為了滿足真實自然環(huán)境下對視頻背景快速度提取和高質量跟蹤的要求，本文提出的基于N2PG的視頻背景提取算法兼顧各像素點的時空分布特點，空間分布上用各像素最近鄰域梯度值替代像素值，提高魯棒性，時間分布上，通過鄰近幀N2PG穩(wěn)定性準確判斷靜態(tài)背景像素點和動態(tài)非背景像素點。對N2PG穩(wěn)定性閾值的實時估計，保證了算法的自適應性。實驗證明了基于N2PG快速背景提取算法具有較高的魯棒性、實時性、高效性，滿足嵌入式視覺系統(tǒng)的應用要求。

不過基于N2PG的快速背景提取算法的穩(wěn)定性閾值估計方法是建立在靜態(tài)背景像素點分布比例遠大于運動物體像素點所占比例的假設前提下，雖然此假設符合普遍情況，但忽略此假設條件而設計更具一般意義的N2PG穩(wěn)定性閾值估計方法依然具有現實意義。

參考文獻：

[1]胡瓊，秦磊，黃慶明.基于視覺的人體動作識別綜述[J].計算機學報，2013，36（12）：2513-2515. （HU Q， QIN L， HUANG Q M. A survey on visual action recognition [J]. Chinese Journal of Computers， 2013， 36（12）： 2513-2515.）

[2]付文秀，李冰，溫翔.基于自適應耦合模型的運動目標跟蹤方法[J].北京交通大學學報，2014，38（2）：50-55. （FU W X， LI B， WEN X. A moving object tracking method based on adaptive coupled model [J]. Journal of Beijing Jiaotong University， 2014， 38（2）： 50-55.）

[3]呂嘉卿，劉立程，郝祿國，等.基于視覺背景提取的自適應運動目標提取算法[J].計算機應用，2015，35（7）：2029-2032. （LYU J Q， LIU L C， HAO L G， et al. Adaptive moving object extraction algorithm based on visual background extractor [J]. Journal of Computer Applications， 2015， 35（7）： 2029-2032.）

[4]HULL J J. Incorporating language syntax in visual text recognition with a statistical model [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1996， 18（12）： 1251-1256.

[5]李剛，曾銳利，林凌，等.基于幀間顏色梯度的背景建模[J].光學精密工程，2007，15（8）：1257-1262. （LI G， ZENG R L， LIN L， et al. A novel background modeling method based on color grade of different frames [J]. Optics and Precision Engineering， 2007， 15（8）： 1257-1262.）

[6]劉勃，魏銘旭，周荷琴.一種基于區(qū)間分布的自適應背景提取算法[J].模式識別與人工智能，2005，18（3）：317-321. （LIU B， WEI M X， ZHOU H Q. A Zone-Distribution based adaptive back ground abstraction algorithm [J]. Pattern Recognition and Artificial Intelligence， 2005， 18（3）： 317-321.）

[7]BARNICH O， VAN DROOGENBROECK M. ViBe： a universal back-ground subtraction algorithm for video sequences [J]. IEEE Transactions on Image Processing， 2011， 20（6）： 1709-1724

[8]韓超，鄧甲昊，鄒金慧，等.基于差分均值背景提取和矩陣分區(qū)目標檢測算法的研究[J].北京理工大學學報，2012，32（12）：1247-1251，1257. （HAN C， DENG J H， ZOU J H， et al. Background extraction based on differential mean method and shadow detection using matrix sub-region partition[J]. Transactions of Beijing Institute of Technology， 2012， 32（12）： 1247-1251，1257.）

[9]KOLLER D， WEBER J， HUANG T， et al. Towards robust automatic traffic scene analysis in real-time [C]// Proceedings of the 12th IAPR International Conference on Pattern Recognition. Piscataway， NJ： IEEE， 1994： 126-131.

[10]STAUFFER C， GRIMSON W E L. Adaptive background mixture models for real-time tracking [C]// Proceedings of the 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1999： 246-252.

[11]陳星明，廖娟，李勃，等.動態(tài)背景下基于改進視覺背景提取的前景檢測[J].光學精密工程，2014，22（9）：2545-2549. （CHEN X M， LIAO J， LI B， et al. Foreground detection based on modified ViBe in dynamic background [J]. Optics and Precision Engineering， 2014， 22（9）： 2545-2549.）

[12]DROOGENBROECK M V， PAQUOT O. Background subtraction： experiments and improvements for ViBe [C]// CVPRW 2012： Proceedings of the 2012 IEEE Computer Vision and Pattern Recognition Workshops. Washington， DC： IEEE Computer Society， 2012： 32-37.