基于碼本模型和壓縮跟蹤算法的遺留物檢測

張 輝，徐 偉，謝正光，蔣小燕，馬文萱

(南通大學電子信息學院，江蘇南通226019)

基于碼本模型和壓縮跟蹤算法的遺留物檢測

張 輝，徐 偉，謝正光，蔣小燕，馬文萱

(南通大學電子信息學院，江蘇南通226019)

針對一般遺留物檢測算法復雜度高和跟蹤效果不理想的問題，提出了一種基于碼本模型和壓縮跟蹤算法相結合的遺留物檢測方法。首先通過碼本模型建模和適時匹配背景更新算法來獲取靜止目標區域信息;然后利用稀疏測量矩陣對靜止目標區域的多尺度特征進行降維，得到分類器的正負樣本;最后用樸素貝葉斯分類器對提取的特征進行分類，當分類器響應最優時得到當前幀中跟蹤到的目標位置，即使目標被部分遮擋，也能實現對遺留目標的準確跟蹤。實驗結果表明，該方法不僅簡單高效、實時性好，而且可以消除由物體短暫停留而帶來的干擾。

遺留物檢測;碼本模型;背景更新;壓縮跟蹤;實時

近年來，由于發生在如機場、公共停車場、公共車站、地鐵站、學校等公共場所的恐怖襲擊事件急劇增加，為了保障安全，人們對視覺監控系統的需求日益加大。在視覺監控系統中，往往需要對運動目標進行檢測、跟蹤、分類和分析等。這其中遺留物檢測已經成為視頻監控系統中安防的一個重要應用分支。及時準確地檢測出可疑的遺留物品或危險物品可對保護廣大公民人身財產安全和公共財產安全給予很大的幫助，因此研究出良好的遺留物檢測算法是非常重要的［1］。

遺留物［2］是指原本不屬于場景背景、在場景中駐留時間超過一定閾值、無人看管的靜止物體。因此，在研究遺留物檢測算法時，需要考慮如下問題［3-4］:1)如何準確檢測出可疑的遺留目標;2)在遺留物被部分或完全遮擋時依然能準確檢測出來;3)應具有很好的實時性，能夠應用于對實時性要求較高的視頻監控系統。近年來，國內外很多研究者針對實際的應用場景提出了許多不同的遺留物檢測算法［2，5-9］，現有的遺留物檢測算法主要可以分為兩類:第一類是基于跟蹤的遺留物檢測方法［6-8］，第二類是基于背景模型的遺留物檢測方法［10-11］。基于跟蹤的遺留物檢測方法在很多場合面臨諸如目標區域的合并、分離、遮擋及其他干擾等問題［1，10-11］，所以算法很難對所有運動和靜止目標區域進行準確有效的跟蹤，尤其是在非常擁擠的公共場合下。相反，基于背景模型的遺留物檢測方法在很多擁擠場合下能夠發揮很好的作用。大體可將近來提出的背景建模方法分為基于幀到幀分析的方法以及基于幀級子采樣分析的方法。不過一般的遺留物檢測方法也面臨算法的復雜度高、目標在有遮擋情況下跟蹤效果不理想和實時性低等問題，一些研究學者也根據各自的應用進行了改進［1，4，9-13］。其中很多方法都采用了不同的背景模型和更新方法相結合來檢測候選的遺留目標，例如文獻［10-11］使用混合高斯模型建模，而文獻［12-13］采用碼本模型建模等。例如文獻［5］中介紹了一套實時遺留物檢測系統，包括了圖像預處理模塊，如圖像去噪和平滑等，基于背景差分的靜止物體檢測模塊，基于塊跟蹤方法的靜止物體跟蹤模塊以及目標部分遮擋處理模塊，為本文提供了一個有效的遺留物檢測模型和研究方案。

基于以上分析，本文提出了一種碼本模型(CBM)算法和壓縮跟蹤(CT)算法相結合的遺留物檢測方法。通過碼本模型進行背景建模和適時匹配背景更新方法來獲取候選靜止目標;再通過投影算法降維，提取低維空間特征信息，作為在線學習更新分類器的正負樣本;最后使用樸素貝葉斯分類器去分類，得到當前幀圖像的目標位置信息，從而實現遺留物檢測和跟蹤。

1 靜止目標檢測

在基于背景模型的遺留物檢測算法中，首先需要準確檢測出候選的遺留目標。由于碼本模型算法［12］是一種非參數化的運動目標檢測方法，它魯棒性好，計算效率高，能夠有效地適應背景變化，因此被廣泛應用于運動目標檢測中，但很少有人論及遺留目標的檢測方法。本文通過碼本模型建模和適時匹配更新算法來檢測出候選的靜止目標，為后續遺留目標跟蹤打好基礎。

1.1 碼本模型建模方法

Kim等人提出的碼本建模算法［12，14］是為每個像素建立一個碼本模型(包含多個碼字)。根據匹配條件判斷像素是否匹配對應像素已存在的碼字，得到前景目標。此算法計算量小、占用內存空間少，對全局或局部光照變化有較好的魯棒性。在建立的碼本中，一個碼本C是由許多碼字{c1，c2，…，cL}組成，而每個像素對應的碼字數L有可能是不同的，同時每個碼字是由9個元素{Ri，Gi，Bi，Imax，Imin，fi，M，p，q}組成的集合，在碼字中，各元素含義如下:

1)Ri，Gi，Bi:相應像素的RGB顏色值;

2)Imax，Imin:所有屬于該碼字的像素中亮度的最大和最小值;

3)fi:對該碼字匹配的像素個數;

4)M:沒有被匹配的最大時間間隔;

5)p，q:首次和末次成功匹配此碼字的訪問時間。

在背景建模階段，用當前幀的像素值xt和碼本模型進行匹配，如果碼本中有任何一個碼字cm與像素值xt滿足色度失真度和亮度匹配條件，則xt與此碼字匹配，否則不匹配。

設當前幀像素值xt的RGB顏色值為{R，G，B}，而對應碼本中的碼字ci(i=1，2，…，L)對應像素的RGB顏色值為{Ri，Gi，Bi}，具體的碼本模型建模方法的偽代碼如下:

1)L=0，C=Φ(空集);

2)For t=1 to N do;

3)For當前幀的每個像素點xt(x，y)do;

(2)從碼本C集合{c1，c2，…，cL}中找出是否有碼字ci與xt滿足以下2個匹配公式:

(a)colordist(xt，ci)≤ε;

(b)brightness(I，{Imin，Imax})=true。

(3)如果C=Φ(空集)或者沒有找到匹配的碼字:

(a)L=L+1;

(b)為對應碼本創建并添加一個新的碼字cL={R，G，B，I，I，1，t-1，t，t}。

(4)否則，更新已匹配的碼字ci:

4)End For;

5)End For;

6)計算每個像素每個碼字被匹配的最大時間間隔λi(i=1，2，…，L)，即λi=max(λi，(M-q+p-1))，將C中所有λi≥N/2的碼字刪除掉，得到精簡后的碼本模型。

上述代碼中的2個匹配公式如下

其中各變量的計算方法如下

式中:ε，α，β都是先驗參數，而且α＜1，β＞1，本文選取α=0.5，β=1.5。碼本模型建模成功后，就可以利用得到的碼本對后續幀中各像素進行前景檢測。

1.2 靜止目標區域檢測

完成碼本模型建模后，對后續圖像序列中的各像素進行前景檢測(FD)，其過程與建模過程中的步驟3)相似，也需要用式(1)和式(2)的匹配條件來加以判斷［14］。

當像素值與對應碼本模型中某個碼字滿足匹配條件時，則對碼字進行更新，并且判定該像素點為背景點，否則就判定該點為前景點，如式(7)所示

經典碼本模型背景更新運用每幀更新的辦法，這對一般運動目標的檢測效果較好。但是過于頻繁、不加區別的更新會將對應的碼字信息更新到更接近于前景目標像素的區間上，這很可能會造成目標離開后背景暴露區域像素與已經偏離了真實區間的碼字不匹配，從而造成誤檢［15］。另外當場景中出現物體遺留情況時，隨著碼本模型的更新，遺留目標區域也會被更新為背景，導致無法檢測出遺留目標。因此，本文在經典碼本模型上增加了適時匹配更新算法和陰影去除算法，從而準確檢測出候選的靜止目標區域，算法流程如圖1所示。

圖1 靜止目標檢測算法流程圖

如圖1所示，當像素點xt(x，y)與碼本模型中的所有碼字都不匹配時，則該像素點所屬的區域可能為運動目標、遺留目標或陰影區域。本文借鑒文獻［1］中所用的陰影抑制方法，其主要思想是當前幀中陰影區域的像素點強度值與背景模型中對應點強度值之間的比值接近一個固定值，故可以利用這點來檢測陰影。

考慮到遺留目標在場景中會駐留較長時間，那么遺留目標區域在駐留期間會一直與碼本模型不匹配，同時相鄰幀之間該區域卻幾乎沒有變化。因此創建了一個計分圖map(x，y)，統計在T幀之內，與(x，y)點像素值xt(x，y)的不匹配次數，同時統計差分二值圖像中對應點DB(x，y)為0的次數，記為count。計分圖map(x，y)的定義如下式中:a是一個容忍值，可以根據場景較復雜程度來調整a的值，一般a取0～3。T幀之后，如果map(x，y)＞T/2，且count＞3/5T，那么可以認定該點屬于靜止目標區域，然后通過連通域標定與分塊操作，得到候選的靜止目標區域信息，主要包括區域的質心點、頂點坐標和區域大小等。

在完成陰影檢測后，由于遺留物是在場景中駐留時間超過一定閾值的物體，但場景中存在運動物體短暫停留的情況，所以這里先對所有滿足靜止目標區域判斷條件的遺留目標的區域進行保存，同時設定最小目標區域面積閾值S(本文取200)，舍棄小于S的目標區域，對符合條件的靜止目標區域在隨后的跟蹤環節進行細判斷，準確地得到遺留目標。

2 遺留目標跟蹤

在獲取候選的遺留目標區域信息后，本文采用文獻［16］中基于壓縮感知的跟蹤算法來對靜止目標區域進行實時跟蹤，該跟蹤算法簡單，執行效率高，在有部分遮擋情況下依然能夠準確跟蹤。

2.1 壓縮跟蹤的相關理論

壓縮跟蹤算法［16］的主要思想為:首先利用滿足壓縮感知中約束等距性(Restricted Isometry Property，RIP)條件的稀疏測量矩陣有效地將目標區域的多尺度特征空間投影到一個低維壓縮子空間，并且該低維壓縮子空間能夠很好地保留高維圖像特征空間信息;然后在降維后的特征信息上采用樸素貝葉斯分類器進行分類，隨后每幀通過在線學習更新分類器，在當前幀中得到被跟蹤目標的位置信息，從而實現對目標的跟蹤。

Johnson-Lindenstrauss引理［17］表明:隨機選擇一個適當的高維子空間(比原始空間維度小)，將原始空間兩點的距離投影到這個子空間中，該子空間依然能高概率地保留這種距離關系。同時Baraniuk等人證明了滿足此引理的隨機矩陣同樣滿足壓縮感知理論中的RIP條件［18］，這個極強的理論使得可以通過低維隨機投影來分析高維信號。那么就需要找到一個不僅滿足此引理，而且又能使得跟蹤算法實時的稀疏矩陣。

2.2 區域特征的投影算法

在完成了遺留目標檢測步驟并獲取了遺留目標的位置信息后，與廣義Haar-like特征提取方法相似，隨后在每幀圖像中靠近遺留目標中心位置的區域采集正樣本，而在離遺留目標中心位置較遠的區域采集負樣本。同時為了實現多尺度特征提取工作［16］，對每一個樣本z∈Rw×h，將其與不同尺度的多個矩形濾波器{h1，1，h1，2，…，hw，h}進行卷積。任意尺度的矩形濾波器定義如下

式中:i和j分別為矩形濾波器的寬和高。將濾波展開后的多個列向量連接起來可得多尺度圖像特征向量x= (x1，x2，…，xm)T，這是一個維度非常高的向量，維度為(w×h)×(w×h)。

基于上文的分析，如果一個n×m的隨機矩陣R，它可以將一個高維圖像空間(m維)的x變換為一個低維空間的v(n維)，就可以用數學形式v=Rx來表示(n?m)。當矩陣R滿足Johnson-Lindenstrauss引理，就認為x是可壓縮的。那么通過最小化誤差可以從低維空間的v高概率重建高維空間中的x。文獻［16］采用了一個非常稀疏的隨機測量矩陣R，該矩陣元素的定義如下

式中:s取2或3時，矩陣滿足上述引理。尤其當s取3時，矩陣變得非常稀疏，計算量將會減少2/3。本文取s=m/4，由此矩陣R的每一行僅需計算k元素的值，其中k＜4，故計算復雜度為O(kn)。另外，由于只需存儲R中的非零元素即可，因此所需存儲空間也較少。投影算法示意圖如圖2所示。

圖2 投影算法示意圖

在本文中，圖2可以看成是通過滿足RIP條件的稀疏測量矩陣R對高維的多尺度圖像特征向量進行了壓縮，而且壓縮感知理論［16］保證壓縮后的特征能高概率地保留原有的圖像特征信息。那么可以對低維空間中的圖像特征進行分類，當分類器實現最佳分類時得到當前幀跟蹤到的目標位置，從而實現對遺留目標的準確跟蹤。

2.3 分類器構建與更新

在完成高維特征投影算法后，每個樣本z(m維)對應的低維可以表示為v=(v1，v2，…，vn)T(n維，且n?m)。假定v中各個元素之間相互獨立，那么可以通過樸素貝葉斯分類器［19］來建模，其公式如下

參數更新遵循下面的公式

2.4 遺留目標區域跟蹤

通過上面的分析，本文針對遺留目標區域采用基于壓縮感知理論和樸素貝葉斯分類器相結合的跟蹤算法，可以很好地解決前面提出的問題(2)和(3)。針對場景中存在運動物體短暫停留的情況，所以本文采用了靜止目標區域質心距離判斷和三幀差分相結合的方法，以減少誤判。具體的遺留目標跟蹤算法步驟如下:

輸入:第t幀圖像

2)使用式(10)中的分類器H(v)對特征向量v進行分類，統計分類分數，其最大值所在圖像片的位置It，作為當前幀目標位置;

3)如果同時滿足:(1)靜止目標的原始質心點坐標和當前幀的目標區域質心點坐標的距離P It-It-1P≥distance;(2)對t-1幀中目標區域進行三幀差分處理［20］，得到二值化圖像B，統計B中像素值為255的點的總數，大于區域面積的15%時，就判定該靜止目標區域離開場景，刪除該目標區域位置信息，轉到輸出。否則轉入下一步;

5)提取上面2個樣本集的特征，根據式(12)來更新分類器參數;

輸出:分類器參數和It。

在上述的壓縮跟蹤算法中，不僅能夠準確地跟蹤遺留目標，而且針對運動物體短暫停留的情況也進行了判斷，簡單高效地檢測出真正的遺留物，實現最終的遺留物檢測。

3 實驗結果及分析

本文主要是在計算機視覺類庫OpenCV的基礎上，通過VS2008編程來實現上述算法的，其中N=100，T= 150，distance=5。測試序列1是PETS2006標準測試視頻中的一個，大小是320×240像素點，幀率是30 f/s (幀/秒)，視頻描述的內容是一個人在車站候車廳里遺留了一個行李。實驗結果如圖3所示。

圖3 測試1的實驗結果圖

如圖3所示，圖3a是經過靜止目標檢測后得到的候選遺留目標區域的二值化圖像;圖3b中用矩形框標定出待跟蹤的靜止目標區域;圖3c是圖像某一幀目標被部分遮擋時，對候選遺留目標進行跟蹤得到的結果。

測試序列2的大小是320×256像素點，幀率是25 f/s，這段測試視頻描述的內容是車輛A和B先后停留在停車場中，經過較長的一段時間后，車輛A駛離了停車場，而車輛B一直沒有離開。實驗結果如圖4所示。

在圖4中，圖4a是視頻序列的某一幀圖像;圖4b是經過靜止目標檢測后，得到候選靜止目標區域的二值化圖像;圖4c中用矩形框標出待跟蹤的靜止目標區域;圖4d是某一時刻對候選的遺留目標進行跟蹤得到的結果;圖4e是當車輛A開始駛離場景時所跟蹤的結果;圖4f當車輛A滿足駛離判斷條件后的跟蹤結果。

圖4 測試2的實驗結果圖

上述實驗結果表明，本文算法可以準確高效地檢測出遺留目標區域，同時可以對該目標區域實時跟蹤，即使目標有部分遮擋，也能夠對目標進行準確跟蹤。另外當有運動物體短暫停留時，也能很好地進行判斷，消除干擾。測試結果如表1所示。

表1 視頻序列檢測結果分析

這些測試視頻來源于以下標準測試視頻庫: PETS2006、VISOR(Video Surveillance Online Repository)和AVSS(Advanced Video and Signal based Surveillance)。通過在不同測試視頻序列中進行檢測，本文算法能夠準確檢測并實時跟蹤候選遺留目標，從而準確實現遺留目標檢測。本文算法運行于Windows7 64位系統，CPU型號為AMD A8-3850，主頻2.9 GHz和內存4 Gbyte的計算機上。

4 小結

本文提出了一種高效易行的遺留物檢測方法。首先利用碼本模型建模和適時匹配背景更新方法相結合來獲取候選靜止目標;然后結合壓縮感知理論和樸素貝葉斯分類器來準確跟蹤候選靜止目標，從而實現遺留物檢測和跟蹤。實驗結果表明，本文提出的方法不僅能夠對背景模型進行動態更新，而且能夠實時高效地檢測遺留目標，同時可以消除由運動物體短暫停留所造成的干擾。本文方法可以應用于車輛停車檢測和拋灑物檢測等交通事件檢測領域。

［1］ZIN T T，TIN P，TORIU T，etal.A probability-basedmodel for detecting abandoned objects in video surveillance systems［C］//Proc.the World Congress on Engineering.London:WCE，2012:1936-1941.

［2］孔英會，張新新，王蘊珠.智能視頻監控系統中物體遺留檢測方法的研究［J］.計算機工程與科學，2010，32(6):118-121.

［3］周飛.基于背景建模的遺棄物檢測［D］.上海:上海交通大學，2008.

［4］ZIN TT，TIN P，TORIU T，etal.A novel probabilistic video analysis for stationary object detection in video surveillance systems［J］.IAENG International Journal of Computer Science，2012，39(3):295-306.

［5］BANGARE P S，UKE N J，BANGARE S L.An approach for detecting abandoned object from real time video［J］.International Journal of Engineering Research and Applications(IJERA)，2012，2(3): 2646-2649.

［6］RINCON JM，HERRERO-JARABA J，GOMEZ JR，et al.Automatic left luggage detection and tracking using multi-camera ukfF［C］// Proc.the 9th IEEE InternationalWorkshop on Performance Evaluation in Tracking and Surveillance.New York:IEEE Press，2006:59-66.

［7］BABENKO B，YANG M H，BELONGIE S.Robust object tracking with onlinemultiple instance learning［J］.IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2011，33(8):1619-1632.

［8］KAIHUA Z，LEIZ，MING-HSUAN Y.Real-time object tracking via online discriminative feature selection［J］.IEEE Trans.Image Processing，2013，22(12):4664-4677.

［9］蔡睿妍，田全.視頻序列中目標的檢測與跟蹤［J］.電視技術，

2012，36(15):127-129.

［10］LIX，ZHANGC，ZHANGD.Abandoned objects detection using double illumination invariant foreground masks［C］//Proc.2010 20th International Conference on Pattern Recognition(ICPR).Istanbul:IEEE Press，2010:436-439.

［11］TIAN Y，FERIS R，HAMPAPUR A.Real-time detection of abandoned and removed objects in complex environments［EB/OL］.［2014-02-10］.http://academic.research.microsoft.com/Publication/6394815/real-time-detection-of-abandoned-and-removed-objects-in-complex-environments.

［12］SAJITH K，NAIR K N R.Abandoned or removed objects detection from surveillence video using codebook［J］.International Journal of Engineering Research and Technology，2013，2(5):400-406.

［13］寧文鑫，王貴錦，何禮，等.基于多層碼本模型的遺棄行李檢測算法［J］.計算機應用研究，2012，29(1):386-388.

［14］KIM K，CHALIDABHONGSE T H，HARWOOD D，et al.Real-time foreground-background segmentation using codebookmodel［J］.Real -time Imaging，2005，11(3):172-185.

［15］姜柯，李艾華，蘇延召.基于改進碼本模型的視頻運動目標檢測算法［J］.電子科技大學學報，2012，6(41):932-936.

［16］ZHANG K，ZHANG L，YANG M H.Real-time compressive tracking［M］.Computer Vision-ECCV 2012.［S.l.］:Springer Berlin Heidelberg，2012.

［17］ACHLIOPTAS D.Database-friendly random projections:Johnson-Lindenstrausswith binary coins［J］.Journal of computer and System Sciences，2003，66(4):671-687.

［18］BARANIUK R，DAVENPORTM，DEVORER，etal.A simple proof of the restricted isometry property for random matrices［J］.Constructive Approximation，2008，28(3):253-263.

［19］RISH I.An empirical study of the naive Bayes classifier［C］//Proc. IJCAI 2001 Workshop on Empirical Methods in Artificial Intelligence. Seattle:IJCAI，2001，3(22):41-46.

［20］丁磊，宮寧生.基于改進的三幀差分法運動目標檢測［J］.電視技

術，2013，37(1):151-153.

Abandoned Object Detection Based on Codebook M odel and Compressive Tracking Algorithm

ZHANG Hui，XUWei，XIE Zhengguang，JIANG Xiaoyan，MAWenxuan
(College of Electronics and Information，Nantong University，Jiangsu Nantong 226019，China)

The general abandoned object detection algorithms proposed are either highly complex orweak in tracking abandoned object.Therefore，an abandoned object detectionmethod based on codebook model and compressive tracking algorithm is proposed.Firstly，the stationary target area information is obtained through codebook backgroundmodeling and timelymatching background update algorithm.Then，a very sparsemeasurementmatrix is used to reduce the dimensions ofmulti-scale image features，which are acted as the positive and negative samples in the classifier，for the stationary target area.At last，those features extracted above are classified via a naive Bayes classifier.As a result，the tracking location is found in the current frame with themaximal classifier response.Even when partially covered，the abandoned object can still be accurately tracked.The results show that the proposed method is not only simple，efficient and real-time，but also can efficiently eliminate the interference caused by the shortterm stay of the objects.

abandoned object detection;codebook model;background update;compressive tracking;real-time

TN911.73

A

張 輝(1989—)，碩士生，CCF會員，主要研究方向為圖像處理、智能交通、計算機視覺;

徐 偉(1988—)，碩士生，CCF會員，主要研究方向為圖像處理、智能交通、計算機視覺;

謝正光(1967—)，教授，主要研究方向為智能信息處理、圖像視頻信號處理與傳輸;

蔣小燕(1989—)，女，碩士生，主要研究方向為數字信號處理、壓縮感知;

馬文萱(1988—)，女，碩士生，主要研究方向為視頻編解碼、壓縮感知。

??健男

2014-04-21

【本文獻信息】張輝，徐偉，謝正光，等.基于碼本模型和壓縮跟蹤算法的遺留物檢測［J］.電視技術，2014，38(23).

國家自然科學基金面上項目(61171077);交通部應用基礎研究項目(2011-319-813-510);南通大學創新人才基金項目(2009);南通大學研究生科技創新計劃項目(YKC13003)