基于颜色匹配的密集多目标快速跟踪算法

1、基于颜色匹配的密集多目标快速跟踪算法摘 要：基于公共场所的监控场景，提出了一种适用于目标密集环境的多运动目标快速跟踪算法。该方法运用形态学方法准确提取目标后，根据卡尔曼原理得到目标在下一帧的预测位置，并以此确定搜索框的位置，提高匹配速率；然后在搜索框内运用基于简化的颜色匹配跟踪方案,用于实现密集运动目标的快速跟踪；且通过设定稳定度数组，来迅速排除碰撞、遮挡情况形成的干扰。仿真表明，该方法能在多目标跟踪过程中正确处理目标的碰撞、遮挡等问题，可实现公共场所的实时监控。关键词：多密集目标跟踪,颜色匹配,稳定度,卡尔曼预测a fast tracking algorithm of multiple an

2、d dense targets based on color matchingchen yu-ting1 cao yan2 zeng xiao-shan3(school of electronic and information engineering, south china university of technology, guangzhou 510640)abstract based on the video detection scene in the public, a fast tracking algorithm of multiple and dense targets is

3、 proposed. the targets are obtained accurately through morphology methods, then the position of the searching box in the next frame is predicted by kalman filer. in the searching box, the tracking algorithm based on simplified color matching is applied to track multiple and dense targets. moreover,

4、by setting a stability array, occlusion and collision can be solved fast. simulation results show that this method can deal with the occlusion and the collusion accurately during tracking multiple and dense targets, and achieve the video detection scene in the public.keywords tracking of multiple an

5、d dense targets, color matching, stability, kalman prediction1 引言视频监控系统在公共休闲娱乐场所具有越来越广泛的应用前景。以泳池监控为例，游泳池内泳者密集，泳技参差不齐，存在安全隐患，同时泳池的安保人员发现险情及实施救援也有一定的难度，有必要对泳者进行监控。公共场所视频监控便是多目标的匹配与跟踪技术的应用之一，其设计难点是目标密集情况和发生碰撞遮挡情况的目标匹配与跟踪。多运动目标匹配的常用方法有基于距离的匹配1，基于目标位置、形状或速度等目标特征的匹配2，上下帧目标重叠像素数的匹配3，区域生长4，基于颜色的匹配5-6等。其中，基于

6、颜色的匹配方案比较适合目标密集情况下对外观相似的目标进行跟踪。常规的颜色模型，从采样点的角度分为手工采样和自动采样；从算法角度，颜色模型的建立方法主要有均值方差法、颜色直方图统计法及其改进等。均值方差法需要对目标的所有点都要参与运算，计算量较大；颜色直方图统计法由于在rgb 颜色模型中，一共有2563种颜色，如果再考虑在此基础上进行直方图计算，计算量非常大，严重降低处理速度。基于此，本文考虑采用基于颜色的匹配方案。在采样点的选取上采用自动采样，即系统按照目标的结构比例自动完成采样过程；从算法角度，本文则选取目标少量的特殊颜色点，将特殊点的各维度颜色直接与颜色模型进行比较，简化匹配过程。在对碰撞

7、和遮挡问题的处理上，已提出的方法如动态贝叶斯网络模型7、颜色直方图的粒子滤波8、网格模型9等，它们有较高的精确度，但较复杂。本文拟仅通过稳定度，对目标存在的可能性进行判断。这样设计的优势是：（1）不需设计专门的模块识别或应对碰撞和遮挡的情况；（2）目标遮挡和碰撞均被视为目标粘连的情况，不需分开讨论。该方法虽然在目标粘连时无法实现匹配，但却不会导致目标丢失，同时省去了目标链、指针等许多参数的设置，在碰撞遮挡发生频繁的跟踪环境，可极大地提高算法的效率。由此，本文提出了一种适用于目标密集环境的跟踪方案。该方案将简化的颜色匹配与卡尔曼预测相结合，实现密集多目标的快速准确跟踪；同时设置稳定度数组，在碰撞

8、、遮挡现象结束后几帧内，即可快速去除虚假目标，且保证原目标的正确跟踪。2 核心思想2.1 简化的颜色匹配模型颜色匹配比较适合外观相似的目标。本文提出的简化颜色匹配方案，首先是在第一帧中，按照目标的结构比例，选取能代表目标颜色特征的区域作为颜色的采样区域。再将各目标的采样区域的若干点记作采样点，同时记录这些点相对于目标质心的位置。取各目标的采样点对应的rgb三个维度的颜色值，依次存入颜色模型矩阵,记为colormode(k,j,v)，k、j、v分别表示采样点总数、目标总数及维度。元素colormode(k,j,v)表示第j个目标的第k 个采样点对应的原rgb图像中的第v维的颜色值。其中，k(1,

9、k), j(1,j), v(1,v)。然后在此后的各帧中，如第i(i>1)帧，按同样的选取采样点的规则对目标进行颜色采样，再与已有的colormode对比。|f(k,j,1)-colormode(k,j,1)|<a （1）|f(k,j,2)-colormode(k,j,2)|<a （2）|f(k,j,3)-colormode(k,j,3)|<a （3）其中，f(k,j,1)、f(k,j,2)、f(k,j,3)分别表示目标j的第k个采样点在r、g、b维度的颜色值，a为各维度匹配时允许的色差阈值。若同时满足式（1）-（3），则认为该采样点与颜色模型匹配，即实现了简化的颜色匹

10、配。若目标j 实现了匹配，则将第i 帧中目标j的各采样点的颜色值f(k,j,v)替换colormode中相应位置的原值，实现颜色模型的更新。对检测确认的新生目标，按照同样方法建立颜色模型，并采用简化的颜色匹配方法实现目标匹配。各帧中每个目标都在相同的特殊点处采样，并将前后帧相同采样处的颜色值进行比对，这样可避免目标不同的位置客观存在的颜色误差，但该方法仍可能会因为光线、浪花等产生的白点影响到某个采样点的颜色值而失配，解决方法是选取k>>1个采样点，根据具体跟踪情况设定一个匹配数的阈值，若实现匹配的采样点数超过该阈值，则认定该目标实现了匹配。2.2 碰撞遮挡问题的处理碰撞和遮挡的情况

11、在目标密集环境下会时常发生，因此系统应能保证这些特殊情况下的正确跟踪。当碰撞和遮挡发生时，两目标发生了粘连，系统会误认为出现了一个新生目标，两目标跟踪失败。为了避免这种情况，本文在跟踪过程中建立一个稳定度数组stablej,j表示目标总数。stablej的值即为第j个目标的稳定度，初始化为1，最大值为smax（经验值）。其意义为：每个目标在刚出现时，都被视为不稳定的，初始化为1，随着跟踪成功次数的增加，其稳定度也增加；若匹配不成功，其稳定度减小，当稳定度减小到stablej=0时，即可认为目标j已消失，不再对该目标进行跟踪。目标粘连的情况（遮挡或碰撞）及跟踪结果如图1所示，在进行目标1的跟踪时

12、，系统会将位于目标1的搜索框内的粘 连目标误认为一个目标与目标1进行匹配，得到失配的结果。但由于建立了稳定度数组，目标1不会立即被认为消亡，在下一帧仍然对其进行检测与匹配；而且由卡尔曼预测（详见目标预测部分），仍能估计出目标在本帧的位置并显示。目标2的跟踪过程同上。而发生粘连的两目标会被系统当做一个新生目标（记为目标3）进行记录，稳定度置为1。在目标分离后，目标3因不会被检测到，致使稳定度逐次减1，直至为0，目标3被系统认为已消亡，不再参与任何计算和显示。目标1目标1的位置预测框目标1的搜索框目标2被误认的目标3的位置框 图1 目标粘连示意图2.3 多目标的快速匹配本方案在完成目标检测后，并不

13、判断是否发生了目标粘连，而是无论发生粘连与否，都进行简化的颜色匹配。若颜色匹配成功，则必然没有粘连的情况发生，更新稳定度数组。这样便仅使用较少的采样点，实现了跟踪。若颜色匹配失败，则有两种可能：一是发生了目标粘连，二是目标消亡。对这两种可能，无需设计专门的模块进行判断，只需将stablej的相应元素减1，然后用卡尔曼预测估计这一帧目标的真实位置。系统会在稳定度减至0之前始终保留该目标的相关数据，当发生碰撞或遮挡的两目标分离后，即可重新实现跟踪。如果该目标的稳定度已降为0，则认为目标消亡，删除该目标相应的跟踪参数。另外，当碰撞遮挡发生时，由于粘连目标无法实现匹配，因此系统会将粘连目标误认为新生目

14、标（如图1中目标1和2发生粘连，被标记为目标3）。本文没有设计专门的模块对目标是新生目标还是粘连目标进行判断，而是通过稳定度数组对目标存在的可能性大小进行标记：新生目标会随着跟踪的进行稳定度逐次增加至smax；而粘连目标则会在目标分离后稳定度逐次减小至0，之后便不再参与任何计算和显示。通过以上方法，匹配过程大大减化。3 基于颜色匹配的密集多目标快速跟踪算法实现3.1 目标检测检测模块运用多种形态学方法，可得到较清晰的目标二值图像。通过背景差分可以得到目标的大致轮廓，但轮廓不够清晰准确。采用腐蚀方法，可有效去除边缘噪声，得到较清晰的目标二值图像。通过目标区域标注，可将n个目标依次标记为1，2，n

15、，n即为搜索范围内的目标总数。为了防止出现虚假目标，对于目标外形相似的情况，利用目标的像素面积基本一致这一特点，可认为小于某面积的目标为虚假目标并消除，由此去除了虚假目标。通过上述方法，便得到了清晰、准确的目标二值图像。返回的目标总数和目标坐标、半径等参数，将作为跟踪部分的相关参数被使用。3.2目标位置预测在i>1的各帧中，可通过上一帧的真实位置，利用卡尔曼10状态预测方程：x(i|i-1)=ax(i-1|i-1)+ w(i) （4）预测出下一帧可能出现的位置x(i|i-1)，考虑了预测可能存在的误差，及目标运动方向突然发生变化（如碰撞分离后）等情况，可将位置预测框扩大为目标大小的若干倍

16、作为搜索框。这样，目标检测只在搜索框内进行，缩小了搜索范围，同时可将上一帧目标直接与搜索框内的目标进行匹配，判断是否为同一目标，缩小了匹配范围，提高了匹配速度，又大大降低因颜色相近的其他目标的干扰，而导致误判的可能。位置预测的另一个重要作用是，当发生碰撞或遮挡时，系统无法在目标粘连区域内区分出原目标，但通过公式（4）的计算，仍可估计出目标的位置，并将预测位置作为真实位置，显示真实位置框，继续参与下一帧的卡尔曼滤波的迭代计算。3.3多目标跟踪算法的实现step1 相关参数的初始化。第1帧图像，进行目标检测，初始化stable数组、卡尔曼滤波参数。将每个目标采样点处的rgb颜色值存入colormo

17、de颜色模型矩阵。step2 目标的预测与检测。第i（i>1）帧图像，依次对第j（j=1,2n，n为目标总数）个目标，计算其搜索框，在搜索框内进行目标检测（若目标密集，可能检测到多个目标）。step3 简化的颜色匹配。对搜索框内检测到的目标l（l=1,2l，l为搜索框内检测到的目标总数），依次与目标j进行颜色匹配。a.若目标l与目标j颜色匹配成功，则实现了跟踪，搜索框内序号在l之后的目标不再与目标j进行匹配。目标j的稳定度加1（加至smax为止），且记录目标j的检测框（即目标l的位置）；b.若搜索框内检测到的l个目标全部与目标j颜色匹配失败（包括目标检测模块没有检测到目标的情况，即l=0

18、），则目标j的稳定度减1（减至0为止）。step4 检测新生目标。对图像中不属于任何检测框的区域进行目标检测，检测到的目标记为新生目标，初始化过程同step1。step5 更新相关参数，显示目标位置。更新卡尔曼参数及colormode矩阵。对于目标j，若该目标实现匹配，则显示检测框和真实位置框（由卡尔曼滤波算法得到）；若匹配失败，但稳定度不为0，则根据式（4），将预测位置作为真实位置显示真实位置框；若匹配失败且稳定度为0，则认为目标j 消亡，删除该目标的所有参数。step6 跳转至步骤step4，进行下一帧图像的跟踪计算。4 实验仿真本文对基于简化颜色匹配的多目标跟踪方案进行了仿真。首先通过4

19、个运动小球的图像序列，展示了检测跟踪的结果，并对碰撞情况的跟踪结果进行了说明。接着对该方案稍加修改，即可应用于公共场所的视频监控。 4.1 碰撞情况的跟踪实验 图2b 红绿两球碰撞的目标跟踪示意图图2c 碰撞后目标跟踪示意图图2b 蓝紫两球碰撞的目标跟踪示意图实验一：五个不同颜色的运动小球的多目标检测和跟踪。开始阶段，五个小球沿各自初始方向运动。在第3帧，蓝、紫两球发生碰撞，在第4帧，红、绿两球碰撞，两组球均在碰撞后的下一帧弹开。根据目标的特点，采样点为沿着目标的运动方向，在目标质心的前后4/5半径处的两个像素点即k=2，色差阀值a=12,稳定度最大值smax=5，匹配数阀值为2。图3 小球的

20、运动轨迹图2展示了目标的跟踪结果。图2a-2c分别展示出第三帧、第四帧发生碰撞时及第五帧碰撞结束后的跟踪结果，白色“+”线表示被检测并成功匹配的目标；黑色“-”线表示本帧目标经过卡尔曼滤波后得到的真实位置。可见，在发生碰撞时而由于篮球与紫球、红球与绿球分别发生粘连，两组目标都没有被检测到，而是被误认为新生目标。但由于它们的稳定度stablej未降至0，因此仍通过卡曼预测原理，对四个球的位置进行较准确的估计（如“-”线所示）。在第4帧（图2b），蓝、紫球又重新实现检测与匹配，在第5帧（图2c）,红、绿球又重新实现检测与匹配。同时因粘连而产生的虚假目标稳定度降为0，不再被跟踪。图3则显示了五个小球

21、的运动轨迹。x、y坐标分别表示小球在各帧中横纵方向的位置。由图3可见，该算法在存在碰撞的情况下仍能对目标的位置进行正确的估计。4.2 公共场所的多目标跟踪实验二：公路监控视频的多目标跟踪。实验对公路上的机动车进行跟踪，采用的图像序列的分辨率为640*480，帧率为6/s，时长t=10s。在简化的颜色匹配部分，将车尾和车顶区域作为采样区域，两区域分别选取了两个采样点来与每个目标的颜色模型colormode比较。四个颜色采样点位置为汽车运动方向的前后距质心距离为7/10半径，垂直运动方向的左右距质心水平距离为1/5半径处的四个像素点，k=4。色差阀值a=10,稳定度最大值smax=3。图4展示了公

22、路机动车监控视频对其中一组机动车（共7辆）的跟踪结果。由图可见，采用提出的算法，能够对公共场所的多运动目标进行准确的跟踪。4.3 计算量分析本文采用对特征区域进行颜色采样的简化的颜色匹配方案。由式（1）-（3）可知，当采样点数为k时，只需4k-1次加减法，2k次逻辑与运算；当目标像素点总数为nm时，文献5中的均值法,每个图4 公路机动车的跟踪目标颜色模型的建立需要6 nm次加减法，nm+2次乘除法；文献6的改进直方图方法，由于采用的颜色量化级为32 × 32 × 32，因此共有323种颜色，每种颜色从计算直方图颜色概率u到映射至（0,255）转换为灰度图的过程，共需3 nm

23、+1次加减法，3 nm+2次乘除法。由于k<< nm，可见本文算法的计算量大大降低。在发生碰撞时，通过稳定度数组的设置，没有增加额外的计算量，使碰撞和遮挡发生时的匹配被大大简化，在保证正确跟踪的同时，进一步提高了跟踪速度。结束语本文提出了一种简化的基于颜色的匹配算法，且通过设置稳定度数组并与卡尔曼预测相结合，便可实现密集环境中碰撞、遮挡等情况下的多目标快速准确跟踪。具体实现上，首先在搜索框内综合使用多种形态学方法检测目标位置；再对目标采样点进行颜色匹配；根据匹配结果更新稳定度数组并显示跟踪结果。实验证明了该系统能够应对碰撞、遮挡等特殊情况，且能实现公共场所的多目标快速准确跟踪。参考文献1隆武林,陈颖琪.基于图像分割与特征匹配的目标检测及跟踪j.信息技术,2009,11:18-23 2 coll insr t. mean-shift blob tra