改進的核密度估計目標檢測方法

夏桂華，楊 楠，蔡成濤，徐從營

(哈爾濱工程大學自動化學院，黑龍江哈爾濱150001)

0 引言

常用的目標檢測方法主要有幀間差分法、背景減除法和光流法。背景法［1，2］是一種應用廣泛且有效的目標檢測方法。當前常用的背景建模方法主要有混合高斯模型法［3］和非參數(shù)模型法［4］?；旌细咚鼓Ｐ托枰孪仍O定模型及參數(shù)優(yōu)化方法，不利于背景復雜的全景運動目標檢測［5，6］?；诜菂?shù)模型的核密度估計算法［7，8］，其使用不需要事先給出具體的背景分布模型，也不需要進行參數(shù)估計就可以進行背景建模。但此方法運算量大，實時性不高，不適合應用在實時性要求較高的智能視頻監(jiān)控系統(tǒng)中。文獻［9］提出一種利用三角核函數(shù)與幀間差分法結合的方法來減小算法的運算量，取得一定效果，但只是針對于某個具體的核函數(shù)進行運算量簡化，適用范圍有限。文獻 ［10］提出一種針對原始樣本的典型采樣方法，但是該算法沒有完全擺脫原始樣本參與背景估計值計算，算法受到一定限制。文獻［11，12］分別提出兩種核函數(shù)目標檢測方法在全景目標檢測的應用，但其使用將全景圖像展開的算法進一步加劇了實時性不足的問題，并且需要強大的硬件支持才能保證實時性要求，普通的處理器無法完成。本文提出一種基于典型采樣與多樣性權值的核密度背景估計算法，其完全擺脫了原始樣本參與背景估計計算，只用占原始樣本1/10的典型樣本與多樣性權值組合即可計算出背景估計值，并提出一種靈活的樣本更新算法，不但大大減少了算法的運算量而且增強了算法抗背景擾動的能力，具有很好的效果。

1 背景建模

1.1 非參數(shù)模型

非參數(shù)背景模型利用核密度估計算法從樣本中估計出一個背景模型，通過此背景模型與當前幀進行比較即可分割出前景圖像，估計出的樣本值理論上收斂于背景值。

設 x1(i，j)，x2(i，j)，…，xN(i，j)為 (i，j)位置像素值的樣本集合，那么在(i，j)處的原始核密度估計 P(x(i，j))可以由下式計算

式中:Kh——核函數(shù)，h——窗寬，N——樣本容量，αi——權值。

本文選擇高斯函數(shù)作為核函數(shù)。根據(jù)文獻［11］，假設(i，j)位置的灰度像素值的分布為 N(μ，h)，則 (x(i，j)－xk(i，j))服從N(0，2h2)。根據(jù)高斯分布及中位數(shù)的定義，樣本的絕對差中位數(shù)m滿足

查標準高斯分布側分位數(shù)表，得μ025=0.68，則

所以窗寬可以由樣本估計得到

1.2 典型采樣

在式 (1)中N為樣本容量，可知在對一個像素點進行背景估計時，當前像素值要與每個樣本進行運算，而一幀圖像至少有幾萬個像素點，一個視頻圖像序列至少有幾百幀，這樣算來整個算法需要很大的運算量。這僅僅是針對單通道圖像來說，如果是彩色圖像，運算量至少還要翻幾倍。由此考慮通過減少樣本的數(shù)量來減少運算量，下面通過幾個實驗進行分析，對多個固定背景的視頻圖像序列的多個位置的像素值進行分析，以 (100，100)位置為例進行統(tǒng)計得出統(tǒng)計直方圖，如圖1(a)所示。

圖1 典型采樣分析

由直方圖可以看出100個像素值被分為11次不同像素值的數(shù)據(jù)，也就是說如果把這100個像素值作為核密度函數(shù)的樣本，在進行前景估計時運算時，只有11次運算是有效的，其他的89次運算都是重復之前的運算并沒有實際意義。這些無用的運算量幾乎占原來使用普通樣本運算的90%。通過以上實驗分析可以假設一個改進思路，即使用原來樣本中具有代表性的樣本值構成新樣本，使用新樣本來進行核密度背景估計運算。

通過觀察樣本重復度而提出的改進設想還遠遠不能證明設想是正確的，還要通過更加可靠的證據(jù)來證明假設的可行性。由此給出下一步分析。隨機在任何固定背景的視頻圖像序列的某個位置取一組樣本數(shù)據(jù)，樣本容量仍然取100。然后計算這組數(shù)據(jù)每個元素的重復度，再保存原始樣本中重復度最高的10個樣本作為新樣本，這個新樣本就是前面提到的原樣本的代表性數(shù)據(jù)。對這兩個樣本進行概率密度估計，如圖1(b)、(c)、(d)所示?？梢钥闯鰞蓚€密度分布的峰值橫坐標相差不多，這是因為典型樣本提取了普通樣本的主要信息。普通樣本的概率密度分布高且窄，而新樣本的概率密度分布矮且寬。不難理解新樣本的矮且寬的形狀是由于去掉了重復的樣本和丟失了部分不重復的樣本 (新樣本的容量可能比原樣本不重復樣本的個數(shù)少)，如圖1所示，再任意再取多個點進行分析，結果相似。同時在實際的監(jiān)控場景中，背景是不斷變化的，為了彌補完全舍掉原始樣本給背景更新帶來的麻煩，在此設置一個與典型樣本的樣本容量同樣大小的差值樣本，來為背景的變化提供接口，作為背景多樣化的保證，由此可總結出典型采樣理論。

基于傳統(tǒng)樣本的樣本重復性的缺點提出典型采樣算法，設圖像在(i，j)位置的n幀圖像序列中的灰度值為S(i，j)= {x1，x2，…，xn}，xk為該像素點的灰度值，在此將由S(i，j)構成的樣本集合稱為原始樣本，用S表示。另設兩個樣本點集合為 R(i，j)= {y1，y2，…，ym} D(i，j)= {z1，z2，…，zm}，稱由R(i，j)構成的樣本集合為典型樣本，用R表示;稱由D(i，j)構成的樣本集合為差值樣本，用D表示。兩者的樣本容量都為m。典型樣本表示在原始樣本中灰度值中出現(xiàn)頻率較高的樣本集合，差值樣本表示在原始樣本中與典型樣本差值最大的樣本集合。典型樣本與差值樣本都通過對原始樣本的計算得到，其具體算法步驟如下:

(1)計算該像素點出現(xiàn)頻率最大的像素值

其中，p表示n幀圖像中不同像素值的個數(shù)，nxi表示n幀圖像中像素值為xi的像素個數(shù)。

(2)提取與y1差值最大的灰度值

在此與重復度大的像素值的差值最大的像素值可能是噪聲，也有可能是背景變化的跡象，所以將其采樣到差值樣本中，之后將為其賦一個較小的權值，這樣如果該像素值確實為噪聲也不會產生大的影響。

(3)從剩下的像素值中選取出現(xiàn)頻率最高的像素值

(4)提取與該像素值差值最大的像素值

以此類推直到典型樣本與差值樣本的容量都滿為止。可以看出當m=p時，典型樣本中包含了原始樣本中所有的灰度值類型。

1.3 多樣性權值

傳統(tǒng)的權值采用平均方法，即ω=1/N。在典型采樣的樣本中，各樣本值對概率密度估計的貢獻顯然不同，所以需要不同大小的權值來調節(jié)不同像素值在背景估計計算中的比重。不難看出典型樣本的樣本值對應在原始樣本的樣本值的重復程度越高，該樣本值在背景估計計算的過程中所參與的比重應該越大，典型樣本的樣本值是以像素值出現(xiàn)的頻率從大到小而提取的，所以將權值設定為原始樣本中該像素值重復的個數(shù)與原來樣本容量的比值可以代表典型樣本值的比重，如式 (9)所示

式中:nyi——重復樣本值的個數(shù)。根據(jù)核函數(shù)概率密度背景估計理論可知，核函數(shù)的權值應該滿足歸一性，即所有權值相加的和必須為1，所以可以將沒有采樣到典型樣本中的剩下的m－i個權值平均分配給差值樣本。如下所示

這樣既保證了權值滿足歸一性要求，也給差值樣本一個較小的權值滿足背景多樣性要求。

因此，基于典型采樣的高斯核密度估計函數(shù)的概率密度可表示為

其中，xt(i，j)表示t時刻在(i，j)位置的像素值，m為典型采樣的樣本容量，h為窗寬。

1.4 樣本更新

由于場景背景的不斷變化，已經(jīng)建立好的樣本會隨著時間的推移而過時，進而失去貢獻的價值，所以需要對建立好的樣本進行不斷更新。

根據(jù)背景模型理論和實驗測得，背景的狀態(tài)大概可以分為3種狀態(tài)。一是某一背景點處于穩(wěn)定狀態(tài)，此時其像素值會分布在某個值的周圍，此點的概率分布近似為高斯分布，此時當前樣本值與典型樣本比較時其差值多數(shù)會小于2h，所以是不更新樣本的情況，與樣本穩(wěn)定時不更新樣本的實時相符;二是背景的某個部分被某個物體遮擋，然后遮擋的物體處于靜止狀態(tài)，此時該物體應該作為背景處理。對應當前像素值與典型樣本比較時，會連續(xù)出現(xiàn)差值大于2h的情況，差值樣本會連續(xù)更新，當差值樣本的更新率大于某個值P時，就將此時的差值樣本與典型樣本進行交換。由此典型樣本中包含了新背景的信息，并且隨著時間推移典型樣本會充滿新背景信息，而原來的典型樣本值轉換為差值樣本，作為背景多樣性的補充;三是背景的某個部分是動態(tài)的背景，如樹葉晃動、窗簾晃動等，此時的當前像素值處于波動狀態(tài)，其與典型樣本的差值也會在大于2h與小與2h之間波動，差值樣本也會波動性更新，當差值樣本的更新率大于P時，典型樣本值與差值樣本值交換，這個交換是波動性的，此時典型樣本中保存了兩類背景的信息。

樣本更新可分為3個步驟:

步驟1 對當前幀按像素點進行檢索，根據(jù)前一幀的檢測結果判斷是否為前景點，即前一幀閥值分割后的圖像的像素值為255，則為前景點，分割后的像素值為0，則為背景點。如果為前景點不進行更新。為了清楚的說明步驟2與步驟3，畫出其操作如圖2所示。

步驟2 判定背景點后，用當前像素值與典型樣本的對應值比較，如果兩者的差值小于2h，則不進行樣本更新，如果大于2h，則用當前像素值替換差值樣本中對應的樣本值。

步驟3 計算差值樣本的更新概率，如果差值樣本的更新概率大于一個設定的閥值P，則將此時對應的典型樣本值與差值樣本值進行交換。

1.5 核函數(shù)估計算法檢測運動目標

圖2 樣本更新

建立好背景后，對當前幀全景圖像進行檢索，并進行閥值分割。為了能更好地適應背景變化和抗背景擾動，使用一個動態(tài)的閥值T來進行閥值分割。根據(jù)在1.4樣本更新一節(jié)的介紹，差值樣本保存的內容主要是目標和背景干擾兩種 (背景干擾包括背景噪聲、背景中物體變化、光照變化等)。如果當前的像素值為目標像素值，那么它與差值樣本的均值和方差會滿足公式

其中，μ為差值樣本的均值，σ為差值樣本的方差，為了彌補差值樣本容量較小的不足和靈活性的要求設置一個調節(jié)系數(shù)β。由此可以得出求閥值T的公式

其中，α是調節(jié)參數(shù)，由式 (15)可以看出如果當前像素點xk(i，j)是運動目標，并且差值樣本中保存的是運動目標的像素值，那么T的值變大，進而將此點判定為運動目標的概率變高。如果當前像素點xk(i，j)為目標，并且差值樣本中保存的是噪聲的像素值，那么閥值T的值會變小，從而將該點判定為運動目標的概率降低，避免誤判定。如果當前像素點xk(i，j)為背景，那么無論差值樣本保存的是目標信息還是背景擾動信息，閥值T的值都會變小，進而增大了將該像素點判定為背景的概率。

最后根據(jù)閥值T進行閥值分割，如果當前估計的概率值大于閥值T，則認為是背景，相反如果當前估計的概率值小于閥值則判定為運動目標。公式如下

至此就提取出了背景圖像Bk(i，j)和前景圖像Fk(i，j)。

1.6 改進后的算法流程圖

對改進后的算法繪制算法流程圖，流程如圖3所示。

圖3 改進算法流程

第一步是初始化:首先從輸入的視頻中提取原始樣本，然后對原始樣本進行處理，提取典型樣本和差值樣本并為典型樣本計算多樣性權值。第二步是前景檢測:根據(jù)背景估計值與當前像素值的差值判斷該像素點是否為運動目標點。第三步是樣本更新。

2 實驗結果及分析

運行環(huán)境:PC機配置酷睿四核處理器，主頻2.3Hz，4G內存，Matlab 2010b下實現(xiàn)提出的算法，原始樣本容量取N=100，典型樣本容量取m=10，典型樣本更新閥值取P=0.71，經(jīng)過多次效果測試閥值調節(jié)參數(shù)α=1.19、β=1.26，對含有機器人運動的全景視頻進行仿真實驗。視頻每幀圖像大小為240*320的彩色圖像，共含540幀，試驗結果如圖4所示。

從實驗結果可以看出，僅僅使用10幀典型樣本的改進算法就清晰的檢測出了全景視頻中的移動機器人，效果基本與使用100幀樣本的原始算法相同，并且改進算法相比原始算法含有更少的噪聲點。從程序運行時間角度比較，見表1。

表1 算法運行時間對比

圖4 實驗結果

由表1可以看出在使用同樣的核函數(shù)的情況下，改進算法的總運行時間約是原始算法的1/3，平均每幀處理時間約是原始算法的1/4，對比之下改進算法程序的運行時間大大縮短。數(shù)據(jù)對比中改進算法的平均每幀處理時間更短是由于背景穩(wěn)定時樣本更新的概率較低，導致程序的運算量下降，可見當場景背景穩(wěn)定時算法的實時性更強。

3 結束語

本文針對核密度估計算法運算量大、不適合應用在實時視頻監(jiān)控的缺點，提出了一種基于典型采樣和多樣性權值的改進核密度估計算法，并且采用一種全新的樣本更新方法，該方法不僅可以實時將背景的變化信息更新到樣本中，而且可以針對背景變化的不同情況做出調整，適應性較好。配合樣本信息的特點，提出一種自適應的閥值求取方法，使檢測準確性更高，靈活性更強。最后通過實驗對改進算法進行驗證，實驗結果表明，該算法不僅能有效的檢測到視頻圖像中的運動目標，而且可以大大減少原來核密度估計算法的運算量，同時增強算法抗背景擾動的能力。

［1］JIANGWei，ZHANG Jian，ZENG Hao.Intelligent video surveillance system based onmoving target detection and tracking［J］.E-lectronic Technology，2012，3(5):256-261(in Chinese).［蔣巍，張建，曾浩.基于智能視頻監(jiān)控系統(tǒng)的運動目標檢測和跟蹤 ［J］.電子技術，2012，3(5):256-261.］

［2］CAO Peng，ZHANGPeng.A new hybridmodel formotion detection algorithm ［J］.Computer Engineering and Applications，2012，8(3):171-175(in Chinese).［曹朋，張鵬.一種新的混合模型運動檢測算法 ［J］.計算機工程與應用，2012，8(3):171-175.］

［3］ZHANG Zhenghua，XU Hua.Differential and mixed differential based on backgroundmoving target detection［J］.Signal and Information Processing，2012，14(5):45-50(in Chinese).［張正華，許華.基于背景差分與混合差分的運動目標檢測［J］.信號與信息處理，2012，14(5):45-50.］

［4］SONG Yang，YIN Fuliang.Moving target detection algorithm based gaussianmixture model［D］.Dalian:Dalian University of Technology，2008(in Chinese).［宋楊，殷福亮.基于高斯混合模型的運動目標檢測算法研究 ［D］.大連:大連理工大學，2008.］

［5］ZHANG Zhongmin，LIYingjing.A moving target detection method is based on the visual panorama［J］.Computer Engineering and Applications，2012，25(6):6-9(in Chinese).［張忠民，李穎晶.一種基于全景視覺的運動目標檢測方法［J］.電子科技，2012，25(6):6-9.］

［6］SIHongwei，QUAN Lei.Motion detection algorithm based on background estimation ［J］.Computer Applications and Design，2011，30(4):14-17(in Chinese).［司紅偉，全蕾.基于背景估計的運動檢測算法 ［J］.計算機應用與設計，2011，30(4):14-17.］

［7］ZHANG Zhenghua，XU Ye.Moving target detection based on background subtraction and mixed frame difference［J］.Signal and Information Processing，2012，4(5):262-265(in Chinese).［張正華，許曄.基于背景差分和混合幀差的運動目標檢測［J］.信號與信息處理，2012，4(5):262-265.］

［8］WANG Jinsong，YAN Yi'an.Gaussian kernel density estimation in moving target detection method［J］.Infrared and Laser Engineering，2009，8(4):373-376(in Chinese).［王勁松，演繹安.利用高斯核密度估計得運動目標檢測方法［J］.紅外與激光工程，2009，8(4):373-376.］

［9］QIMeibin，WEIXing.Moving target detectionmethod based on triangulation estimation model［J］.Hefei University of Technology，2009(4):389-402(in Chinese).［齊美彬，魏星.基于三角核估計模型的運動目標檢測方法 ［J］.合肥工業(yè)大學學報，2009(4):389-402.］

［10］MAO Yanfen，SHIPengfei.A moving target detectionmulti-modal non-parametric background model［J］.Shanghai Jiaotong University Newspaper，2009，26(9):134-137(in Chinese).［毛艷芬，施鵬飛.一種運動目標檢測的多模態(tài)非參數(shù)背景模型［J］.上海交通大學報，2009，26(9):134-137.］

［11］Stefano Ghidoni，Alberto Pretto.Cooperative tracking of mo-ving objects and face detection with a dual camera sensor［C］//IEEE International Conference on Robotics and Automation Anchorage Convention District，2010:2568-2573.

［12］Yan Lu，Shahram Payandeh.Ineelligent cooperative tracking in multi-camera syatems［C］//9th International Conference on Intelligent Systems Design and Applications，2009:608-613.