基于多层定位的多目标跟踪算法

姜 明 新， 王 洪 玉

（1.大连理工大学 电子信息与电气工程学部，辽宁 大连 116024；2.大连民族学院 信息与通信工程学院，辽宁 大连 116600）

0 引 言

在复杂的监控环境中，由于多目标的密度大，相互之间的遮挡频繁发生.在这种情况下，多目标的稳定跟踪具有一定的难度.近年来，很多学者进行了这方面的研究[1、2].文献[3]提出利用粒子滤波方法进行多目标跟踪和数据融合，但算法无法达到实时性要求.文献[4]提出了基于核的多目标跟踪算法，该算法在目标外观比较接近时的鲁棒性能比较差.文献[5]提出了利用贝叶斯框架实现对多目标的跟踪.文献[6、7]提出了利用多相机之间的单应性的多目标跟踪算法，但算法需要对相机进行完全标定.

为解决遮挡问题，本文提出一种基于多层定位的目标跟踪算法.该算法利用多相机间基于多个高度层的单应性变换对多目标进行定位.即将多个同步相机放置在不同的视角上，通过对背景建模得到多个视角的前景信息，选择其中任意一个相机的像平面作为参考图像.选择地平面作为参考平面，垂直地面的方向作为参考方向，在参考方向上分多层.在每一层上，利用单应性将其他视角的信息映射到参考场景中，通过多相机信息的融合实现对多个目标的定位.然后利用图割算法，根据每层的定位信息实现对多目标的跟踪.

1 前景检测

本文采用码本模型对背景进行建模，获得每个像素属于前景的概率，即获得每一个相机拍摄场景图像的前景似然信息.文献[8]提出了码本模型，获得码本后，检测前景似然信息的过程如下：

假设目标检测过程中新输入像素为xi＝（RGB），其对应的码本为M.减背景操作BGS（xi）可以大致分为3步：

步骤1 计算当前像素的亮度I＝R＋G＋B，定义布尔变量match＝0，并给阈值变量ε赋值.

步骤2 根据以下两个条件从码本M中找出与当前像素相匹配的码字Cm，如果能够找到码字Cm，则match＝1，否则，match＝0：

为了判断前景和背景，运动目标检测中亮度变化有一个范围，对于每个码字，其范围为[Ilow，Ihi].亮度函数的定义为

步骤3 判断前景运动目标像素：

图1是利用混合高斯模型和码本模型进行前景检测的实验结果对比.可以看出，利用码本模型进行前景检测能够很好地克服运动目标的阴影问题和空洞现象.

图1 利用不同模型检测前景的结果Fig.1 Results of foreground detection using different models

2 定位算法

2.1 单应性矩阵

本文选择地平面作为参考平面，两个相机拍摄的图像（简称像平面）分别记为Ii和Ij.设π是不通过两个相机任一光心的空间参考平面，令X是平面π上的任意一点，X在Ii和Ij中的像分别为mi＝ （xiyi1）T和mj＝ （xjyj1）T，定义一个3×3的矩阵：

使得mj＝Hiπjmi，即

满足式（4）的矩阵Hiπj称为平面π诱导的两个像平面间的单应性矩阵，式（4）称为单应性变换[9].利用单应性矩阵Hiπj，从一个像平面上的点可以得到另一个像平面上的对应点.单应性矩阵Hiπj具有8个自由度.在实验过程中，在地面上放置4个标志物，来计算基于参考平面（地面）的单应性矩阵.

2.2 垂直方向的灭点

为了获得平行于地面的多个高度层的单应性矩阵，需要计算垂直方向上的灭点.直线上无穷远点的像称为该直线的灭点.由于平行直线与无穷远平面相交于同一个无穷远点，平行直线有一个相同的灭点，即灭点只与直线的方向有关而与直线的位置无关[10].为了计算基于多层的单应性矩阵，必须先检测垂直方向上的灭点.因为建筑物的边缘一般存在很多相互平行的直线，本文利用监控场景中的建筑物进行灭点的求解.本文检测灭点的方法可以大致归纳为以下几个步骤：

步骤1 利用Canny算子提取图像中的边缘信息.

步骤2 利用Hough变换从边缘信息中提取出垂直于地面方向的线段.

步骤3 利用下式求出垂直方向上的灭点VY：

2.3 利用灭点进行多目标多层定位

本文在平行于参考平面的多个高度层上对目标进行定位，然后融合多层定位的信息，对目标进行跟踪，这样大大提高了多目标跟踪的鲁棒性和准确性.

π为参考平面，垂直于参考平面的方向为参考方向.为平行于参考平面的任意平面.Ii为相机i的像平面，选择Ii的前景似然图像作为参考图像.

平面π诱导的任意两个像平面Ii和Ij间的单应性矩阵Hiπj可以分解为

同理，由平面诱导的单应性矩阵Hi j也可

以分解为

根据文献[11]，可以得到

式中：vrefj是相机j的像平面Ij垂直方向上的灭点，γj是控制多层之间距离的标量.

式中g＝trace（（0｜γivrefi）Hitoπ）.把式（8）、（9）代入式（7），可以得到

注意到Hitoπ是一个平面到另一个平面的中心投影，g＝trace（（0｜γivrefi）Hitoπ）＝γi，将此结果和式（6）代入式（10），经过线性代数推导可得由平面诱导的Ii和Ij间的单应性矩阵为

在实验过程中选用3个相机对多目标进行跟踪，得到3个视角的图像，简记为view1、view2、view3.选择其中一个视角的前景似然图像作为参考图像，利用式（11）将其他两个视角的前景似然图像映射到参考图像中，得到多相机的多层融合图像，多层融合图像上的高亮点即为多目标在多层上的定位信息.

3 跟踪算法

本文利用图割理论[12]对多层定位信息进行处理，进而实现对多目标的跟踪.空间中的某一个位置在某一个时刻只能被一个目标所占据，所以在一段时间内，这个目标多个时刻位置的集合就构成了它的轨迹.利用第2章得到的多目标在多层上的定位信息，构建能量函数：

式中：P（p）为多层融合图像上的像素p属于前景的概率；N为所有相邻元素的集合；dist（p，q）为相邻元素p和q的欧几里得距离；α、β为数据项和平滑项比例关系的系数；τ为归一化因数.

在实验过程中，为了提高跟踪的准确度，采取了时间滑动窗口进行处理.所谓时间滑动窗口就是每15帧处理一次，第一帧为初始化帧，最后一帧作为下一个时间滑动窗口的初始帧.在每次处理中保证有一帧的交叠，这种交叠方式是为了传递ID（目标的标签值）.ID的传递则是通过由初始化帧中每个目标位置在其余14帧中的位置预测一个区域，同时赋予相应的标签值.然后利用图割理论实现能量函数最小化，进而得到每个目标在不同层上的标签值.将多层图割后的结果融合起来就可以实现对多目标的稳定跟踪，本文在实验中用矩形框表示跟踪结果.

4 实验结果及分析

为了说明本文的多层定位跟踪算法对遮挡的鲁棒性，利用3台相机从不同视角拍摄实验视频进行实验，实验视频分辨率均为320pixel×240 pixel，算法实现基于 Windows操作系统，采用Visual Studio 2008和opencv2.0作为软件平台，计算机配置为Pentium（R）Dual－Core CPU 2.0 GHz.

实验过程中，本文计算垂直方向上的灭点，实验结果如图2所示，选取其中1个视角来进行说明，其他2个视角的求法与此相同.图2（b）是利用Canny算子提取出的视频图像中的边缘信息，图2（c）是利用Hough变换从边缘信息中手动选取的垂直于地面方向的线段.利用式（5）求出垂直方向上的灭点VY，垂直方向上灭点坐标为（254，460）.

图3是对多目标进行多层定位的实验结果，图3（a）是3台相机从3个视角拍摄的原始视频图像，在实验中选取第3个视角的前景图像作为参考图像，平行于地面共分为8层.图3（b）～（d）分别表示实验视频基于地平面、第3层和第6层的多目标定位信息.图4是参考视角多目标跟踪的实验结果.

图2 实验视频垂直方向上的灭点检测Fig.2 Detection of vanishing points for the vertical direction of experimental video

图3 本文定位算法多层定位的结果Fig.3 The results of localizing algorithm in this paper at multiple planes

图4 参考视角的多目标跟踪结果Fig.4 Multi－object tracking results of the reference view

5 结 论

本文在平行于地面的多个参考平面上对多人进行定位，利用多层定位信息构建能量函数，采用图割理论实现能量函数的最小化，进而实现对多目标的稳定跟踪.本文提出的算法不需要标定相机，只需要计算相机的灭点，所以在很大程度上简化了跟踪算法的计算复杂度.实验结果表明算法对遮挡具有很强的鲁棒性.

[1] JIANG Ming－xin，LI Min， WANG Hong－yu.A robust combined algorithm of object tracking based on moving object detection [C]//Proceedings of 2010 International Conference on Intelligent Control and Information Processing，ICICIP 2010.Piscataway：IEEE Computer Society，2010：619－622.

[2] Brendel W，Amer M，Todorovic S. Multi－object tracking as maximum weight independent set[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway：IEEE Computer Society，2011：1273－1280.

[3] Hue C，Le Cadre J P，Perez P.Sequential Monte Carlo methods for multiple target tracking and data fusion[J].IEEE Transactions on Signal Processing，2002，50（2）：309－325.

[4] Han Bo－hyung，ZHU Ying，Comaniciu D，etal.Kernel－based Bayesian filtering for object tracking[C]//Proceedings －2005IEEE Computer Society Conference on Computer Vision and Pattern Recognition， CVPR 2005. Piscataway：IEEE Computer Society，2005：227－234.

[5] Mittal A，Davis L S. M2tracker：A multi－view approach to segmenting and tracking people in a cluttered scene[J].International Journal of Computer Vision，2003，51（3）：189－203.

[6] TONG Xiao－ming，YANG Tao，XI Run－ping，etal.A novel multi－planar homography constraint algorithm for robust multi－people location with severe occlusion[C]//Proceedings of the 5th International Conference on Image and Graphics，ICIG 2009.Piscataway：IEEE Computer Society，2010：349－354.

[7] Han Bo－hyung，Joo Seong－wook，Davis L S.Multicamera tracking with adaptive resource allocation[J].International Journal of Computer Vision，2011，91（1）：45－58.

[8] Kim K，Chalidabhongse T H，Harwood D，etal.Real－time foreground－background segmentation using codebook model [J].Real－Time Imaging，2005，11（3）：167－256.

[9] Hartley R，Zisserman A.Multiple View Geometry in Computer Vision [M]. Cambridge：Cambridge University Press，2003：237－253.

[10] Rother C.A new approach for vanishing point detection in architectural environments[J].Image and Vision Computing，2002，20（9）：647－655.

[11] Criminisi A，Reid I，Zisserman A.Single view metrology [C] // Proceedings of the IEEE International Conference on Computer Vision.Piscataway：IEEE Computer Society，1999：434－441.

[12] Nicolas P，Aurelie B.Tracking with occlusions via graph cuts [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）：144－157.