基于码本模型和压缩跟踪算法的遗留物检测

张 辉，徐 伟，谢正光，蒋小燕，马文萱

(南通大学电子信息学院，江苏南通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)