1引言

動態目標檢測是計算機視覺研究的一個重要的課題，廣泛應用于智能視頻監控、目標追蹤等領域。背景差法是當前常用的一種運動目標檢測方法，由于現實中的背景非常復雜，一方面存在各種噪聲，另一方面光照等因素也不會穩定不變。為了應對復雜的現實環境，學者們提出了各種各樣的背景建模方法，其中最普遍采用的模型是混合高斯MG(Mixture of Gaussians)模型^[1,2]，它能夠適用于非常復雜的或具有動態背景噪聲（如背景中的雨點、晃動的樹枝）情況的背景建模。但是，對于快速變化的背景，很難用有限的幾個的高斯模型來精確描述，且混合高斯模型的學習效率很難控制在既不過檢又不漏檢的理想狀態。于是，有學者嘗試提出其他的檢測模型，Kim等提出了碼書模型^[3]，甘新勝等研究表明，該方法比混合高斯模型有更優的檢測效果^[4]。

碼書模型的思想是先對圖像序列進行學習，使每一像素點得到一本碼書，然后根據前景點和背景點在圖像序列中的分布特性分離出背景碼字，利用背景碼字構造出背景。再用構造的背景去分離視頻中的目標。為了精確獲取統計信息，碼書模型的碼字采用了多個參數進行描述，不僅使碼書模型訓練的時間和空間復雜度高，檢測過程中的算法復雜度也高。而在實時監控追蹤等領域，往往需要達到幾十幀的處理頻率。所以，傳統碼書模型較高的時間空間復雜度大大限制了它在實時環境中的應用。

本文在碼書建模的基礎上，通過優化模型參數和模型訓練方法，降低了碼書模型的時間和空間復雜度，設計了一種信息塊快速獲取方法來獲取目標信息塊和時間軸變化信息塊，利用目標信息塊和時間軸變化信息塊融合決策得到背景，實現了在檢測過程中獲取背景直接訓練背景碼書，提高了背景碼書的背景分離效率和碼書訓練效率。最后使基于優化碼書模型背景建模的目標檢測算法效率大大提高，算法已成功應用到了實時視頻監控軟件中。最后本文對算法性能進行了實驗，驗證了優化后的碼書模型效率提高的同時，檢測性能并未降低。

2方法原理

2.1碼書模型的優化

碼書模型是對圖像的每一個像素建立一本碼書，每本碼書包含若干個碼字，碼字是基于色彩標準和亮度界限聚類得到的。所有像素的碼書就形成了碼書模型。背景碼字和前景碼字是基于統計信息從碼書模型中分離出來。碼書模型通常采用五個參數來描述每個碼字^[4]：〈v,σ, f,λ, T_last〉。其中, v是聚類形心; σ是聚類距離偏差, f是碼字出現的頻率, λ是碼字相鄰兩次出現的最長時間間隔, T_last是碼字最后出現的時間。背景碼包含一個或多個碼字,依據出現頻率較高、 相鄰兩次出現的時間間隔都比較短的特點進行分離。

5個參數的碼書模型有諸多不足。首先，碼書空間復雜度高，一方面每個碼字需要記錄5個參數，另一方面碼書的長度不固定，需要的計算機內存空間不僅大，而且難估計。其次，時間復雜度高，要計算5個參數的值，需要統計計算大量的圖像數據，而且統計計算完成后，還要根據分布特征分離出背景碼字和前景碼字。另外，存在數據冗余，因為在大多數時候，除去背景碼字，就是前景碼字，二者只需存儲其一即可；另外，背景碼字也具有一定的時效性，只需要對應時刻相關的背景碼字信息，不需要全體的背景碼字信息。

針對不足之處，本文對5個參數的碼書模型進行了優化。首先，把碼書的長度固定下來，濾除數據冗余的目標碼字，只記錄背景碼字，當訓練得到的背景碼字的個數超出碼書的長度時，則按統計信息對碼書進行篩選，把最低時效價值的碼字剔除。其次，把碼書的頁碼參數利用起來，碼字按隊列結構算法在碼書中加入和刪除，這樣就可以利用頁碼來計算碼書中的兩個時間參數。利用聚類中心x和權值參數w代替聚類形心v和出現頻率f，把判別一個樣本是否屬于聚類x的聚類距離σ設成一個固定值。精簡后的碼書模型Y的碼字只含有兩個參數：<x,w>。綜合上述，建立精簡后的碼書模型Y：

               (1)

Y為N×2維矩陣，元素y_i =[x_i,w_i]^T，其中x_i為第i頁的聚類中心，w_i為第i頁的權值。聚類中心碼X=[x₁,x₂,x₃…x_i…]和碼權值W=[w₁,w₂,w₃…w_i…]均為1×N維矩陣。碼權值矩陣W的1范數恒等于1：

                               (2)

2.2碼書的訓練

碼書模型的訓練過程是用背景像素去修改模型參數的過程，本文訓練方法的核心思想是把碼書被當成一個固定長度的隊列數據結構，數據按先進先出(FIFO)的算法進行訓練，用隊列元素的位置來表征碼字的時間參數，用權值的大小來表征碼字出現的頻率，始終保持所有碼字的權值元素的和為1，通過權值增減分配達到即表征碼字的出現頻率，又實現最低利用價值碼字的刪除。按這種核心直到思想，本文設計了碼書的詳細訓練方法，主要包括聚類中心碼的訓練和權值的訓練兩個部分的內容。

聚類中心碼 的訓練：①當碼書存在空白頁，待加入的中心碼與碼書中沒有同類碼時，按照頁碼從小到大把中心碼依次加入到碼書。②當碼書各頁已經填滿，待加入的中心碼與碼書中沒有相同值時，需要剔除碼書某一頁的中心碼x_i，x_i所在頁碼后面的中心碼依次向前頁移動一頁，新加入的中心碼加到最后一頁，需要剔除的中心碼按照中心碼書剔除規則選擇。③當待加入的中心碼與碼書中有相同值時，x_i所在頁碼后面的中心碼依次向前頁移動一頁，并按照式(3) 更新中心碼x_i，把更新后的中心碼x_{i_new}填入到最小空白頁。式(3）中β表示更新前中心碼的權值，α為更新速率，由式(4)定義。

                      (3)

                         (4)

式（4）中，T為正整數。權值的更新速率決了碼書更新的快慢。

中心碼剔除規則：①當碼權值更新后值減少到0時，中心碼被刪除。②當碼書要主動刪除時，選擇按權值頁碼積最小的碼書刪除，刪除后的碼書權值先分配給待加入碼，再把剩下的權值按照頁碼從大到小分配給其他頁碼。

權值的訓練：始終保持權值矩陣的1范數為1，權值隨著中心碼的加入而更新，當只有一頁中心碼時，其對應權值為1，后面每次新加入或更新一個中心碼，第一頁的權值減少α。新加入或更新的中心碼權值增加α，中心碼的權值更新后最大值為1。

2.3基于碼書模型的運動目標實時檢測算法

算法檢測過程中，有兩個初始化操作。一是前景分離閾值T_k的初始化，本文把分離初始閾值定為15，T_k會會隨著視頻流的時間軸分析得到更新，當計算出來的分離閾值不合理時，則保留前一次計算出來的分離閾值。另一個是背景碼書模型的初始化訓練，本文把當前幀全部內容作為背景進行初始訓練，在檢測過程中，背景碼書會得到不斷的優化。

圖 1檢測算法框架

目標實時檢測和碼書模型實時訓練的算法框架見圖1示。實時視頻流流向檢測和分析兩個線程，視頻時間軸分析用當前幀與前一幀做差分運算，分析出視頻參數，得出背景是否改變，若背景有大的改變，則初始化背景碼書，運動信息塊置空。若背景沒有變化，則提取出運動塊信息。目標檢測線程進行目標提取，目標提取先從背景碼書中選擇權值最大前提下頁碼最大的碼字作為背景，再用背景差檢測算法提取出目標，并運算出目標信息塊，然后融合檢測和分析線程獲得的信息塊對對檢測出的目標進行校正。利用校正后的目標，從當前幀中分離出背景，對背景碼書參數進行訓練。

3實驗與分析

3.1 實驗設計

為了驗證優化碼書模型算法的性能，本文針對背景建立性能和目標檢測性能兩個方面進行對比。背景建模性能對比中，先對已經采集到得視頻分別使用原始的多參數碼字和本文的精簡參數碼字建立碼書模型，在時間軸上對比分析二者訓練得到的碼書模型所建立的背景的差異。針對目標檢測性能，文獻[4]已經對比了碼書模型與混合高斯模型的檢測性能，所以本文主要考察多參數碼書模型與本文優化參數的碼書模型的檢測性能，另外還把快速的差分算法的檢測性能做了參照對比。實驗采用普通的監控場景圖像。

實驗中碼書模型取初始分離閾值T_k取15，本文提出的碼書模型長度取4，碼字聚類距離取固定值5，碼書更新時間取為0.1。 實驗均在配置為Intel (R) Celeron® CPU 420 1.6 GHZ 和512mB內存的PC機器上完成，采用的編程工具為Matlab7.6。

3.2 背景建立準確度對比分析

實驗中，先采用原始的多參數碼書模型訓練得到碼書，依據出現頻率較高、相鄰兩次出現的時間間隔比較短的特點從中分離出各幀對應的背景。再采用本文的優化碼書模型訓練得到碼書，并依據權值最大條件下頁碼最大的特點從中分離出各幀對應的背景。然后分別把二種方法獲得的背景進行差分運算，統計灰度差異值超過聚類距離5的總像素的和，計算差異像素占圖像總像素的比值。

圖2體現了兩種碼書模型訓練得到的背景差異的實圖對比�？梢钥闯�，本文優化碼書模型算法初始化時，目標也被建立到了背景中，此時訓練的背景與全參數碼書模型差異也最大，隨著檢測過程中的不斷訓練，優化碼書模型恢復的背景中的目標逐漸消失，到27幀時，融入背景的目標已消失了大部分，在第45幀，優化參數的背景與全參數的背景已達到一致，融入背景的目標也完全消失。

圖3為各序號幀對應背景的相對差異參數走勢圖�？v坐標表示各幀背景的相對差異值，橫坐標表示按時間順序排列的幀編號。從背景差異走勢圖可以看出，隨著時間的推進，優化碼書模型獲得的背景與原始多參數碼書模型獲得的背景差異越來越小，在第30幀時，二者形成了一致，在隨后的檢測過程中，二者的差異小幅度地波動。

 圖2  背景訓練過程中的差異對比實圖     

圖3 訓練背景差異走勢

優化碼書模型建立的背景與原始多參數碼書模型建立的背景有較小的差異，只說明優化后的碼書模型與原始多參數碼書模型的差異小，并非說明本文優化模型的性能不如原始多參數碼書模型。因為二者提取的背景準確度沒有可參考的準確背景對比。由于背景建立的準確性能決定了目標檢測性能，所以可以通過目標檢測性能對比。

3.3算法性能分析

為了驗證本算法的檢測性能，實驗分別用原始多參數基于全局訓練的碼書模型檢查算法DBGT (detect based on global  training)、本文提出的優化參數實時訓練的碼書模型檢測算法DBRT (detect based on real-time training)及差分檢測算法DBD(detect based on difference)去對同一組圖像進行檢測，把各自檢查結果分別保存下來，再用PS工具手工分離出理想目標，利用理想目標分別計算出三個檢測算法的像素誤檢率比率Er和漏檢率比率Mr。

 圖4 三種算法的漏檢率(Mr)和誤檢率(Er)對比

Mr與Er對比分析結果見圖5示，可以看出，DBRT算法與DBGT算法的Mr與Er均優于DBD算法。DBRT算法在開始檢測時的Mr和Er略高于DBGT,與DBD接近，但隨著檢測幀數的增多，DBRT算法很快就與DBGT算法相等了。

4總結

背景的差異分析和目標檢測性能參數對比分析說明本算法在大大提高算法效率的同時，仍與原始5個參數的背景碼書模型有相近的檢測性能。本文優化碼書模型算法有以下幾點改進：一是算法效率上的提高，本文在實驗中發現，經優化的碼書模型算法的運算時間和內存消耗有數量級的提高。二是優化碼書模型能實時訓練檢測，而原始碼書模型需要訓練幾幀后才能分離出目標。三是本文采用了時間軸快速分析后，能快速適應場景的變化。所以，在實用化過程中，本文的優化的碼書模型算法具有一定的參考性。本算法已經應用到了實時視頻輔助監控軟件中，用于目標追逐和目標行為分析的前期處理。具有較好的綜合性能。

參考文獻 (References)

1         Zhu Z J, Jiang G Y, Yu M, Wang R D, Wu X W. New algorithm for extracting and tracking moving object in object-based video coding[J].  cta Electronica Sinica,2003,31(9):1426-1428.

2         Ming X, Tim E. Augmented tracking with incomplete observation and probabilistic reasoning[J]. Image and Vision Computing, 2006, 24: 1202-1217.

3         Kyungnam K, Thanarat H, Chalidabhongse, David H, Larry D. Real-time foreground– background segmentation using codebook model. Real-Time Imaging, 2005, 11: 172–185.

4         甘新勝，基于碼書的運動目標檢測方法，中國圖象圖形學報，2008, 2:13.

5         Horn B K P, Schunk B. Determining optical flow. Artif. Intell, 1981, 17: 185-203.

6         Lipton A, Fujiyosh I H, Patil R. Moving target classification and tracking from real-time video[A]. Proc IEEE Workshop on Application of Computer Vision[C]. Princeton, NJ, 1998.8-14.

作者簡介：

劉先剛（1983-），男，碩士研究生，主要研究方向為智能化信息技術及系統。