基于－模型的自适应车辆跟踪算法

1．目标图像的初始化

ST－MRF应通过像素来优化时间图像的分割，意味着一个具有27个像素的空间基团取代一个只具有9个像素的平面基团。然而，这种情况只在目标运动很慢的时候发生，因为实际运动车辆速度比较快，车辆的像素移动一般会在数十个像素以内，目前视频检测技术不能以足够高的帧率去捕获到这些信息。因此，空间相邻的像素块在相邻块的图像之间不可能有任何的联系。基于这种考虑，在时空马尔可夫随机模型中，把图像分成若干块，相邻图像间的像素块将通过它们的运动矢量联系起来。

2．目标地图和运动矢量地图的初始化

在图像分割中，单个像素作为考虑的场景，而在车辆跟踪算法中，如果只考虑单个像素将不足以作为ST－MRF中的一个场景（site），需要一个较大的像素组。因此，需要把一幅像素值为720×640的图像分割成90×80的像素块，即每个像素块由8×8个像素组成。在车辆跟踪算法中，像素块与ST－MRF中的场景是一一对应的。即把每个像素块和一个车辆联系起来，也就是给每个像素块赋予一个对应的车辆的标号。在使用跟踪算法的时候，首先决定一个初始标号分配，然后通过ST－MRF中的能量函数把标号分配进行提炼及优化处理。在提炼过程中，算法考虑块在时间域和空间（二维x－y坐标）的联系，也就是连续图像之间的块的联系以及与相邻块之间的联系，通过马尔可夫随机场模型，把标号赋给像素块。

当ST－MRF有一个好的初始估计值时，它将快速收敛到一个稳定情况。可以采用自适应车辆跟踪的算法去确定一个初始标号分配。自适应的车辆跟踪算法步骤如下：

（1）初始化及新车辆标号的产生。首先建立一个研究区域的背景图像，在算法中，设置检测矩形框，在矩形内的车辆能被检测到，超出矩形框的车辆就不能检测。这样做的目的是为了避免对向车辆被检测，妨碍检测结果。并在矩形框上检测前景与背景灰度图像的变化，用于判断是否进入车辆。在检测矩形框上，每一个块的当前灰度和背景灰度的差值一直在被检测。当这个差值大于一定的阈值时，算法就判断检测到一辆新车，并产生一个新的标号，这个标号赋予目标块。如果新的目标块与早前检测到的目标块部分重叠，这时把以前检测到的目标块的标号更新为新的标号。在这里，仅仅只有块才具有来自背景图像的不同纹理作为车辆区域被标号，但是这些块随着背景图像一起具有相同的纹理，而不能给其他车辆区域进行标号。车辆跟踪算法流程图如图3．2所示。

（2）目标地图的初始化。在车辆跟踪的基础上，把具有相同标号的块集合在一起形成车辆的投影，初始的投影边缘比较毛糙，也不是车辆形状的几何体，如图3．3所示，特别是一个块代表两辆车的时候，这时需要对目标地图优化进行块的分离。

图3．2 基于ST－MRF的车辆跟踪算法流程图

别是一个块代表两辆车的时候，这时需要对目标地图优化进行块的分离。

图3．3 目标地图的初始化

（3）估计目标运动矢量。当车辆区域离开检测矩形框时，算法沿着时间序列自动更

新车辆的形状。对于这个更新，算法在车辆区域的块中估计运动矢量。在每一个像素块上，运用块的匹配方法（采用基于最小平均绝对差值函数（MAD）准则的三步块的匹配算法，其基本思想如图3．4所示）估计每一个目标块在时间t和t－1时的运动矢量。即块在时间t的坐标值为［x（t）， y（t）］，在时间t－1的坐标值为：［x（t－1），y（t－1）］＝［x（t）－u（t），y（t）－v（t）］，通过该公式可以估计式（3－1）。其中G（t；x，y）是像素（x，y）在时间t的灰度强度。大概10个目标块属于一个对象。这个对象的运动矢量被目标块中一些高频运动向量所代表。这些高频运动向量的集合就组成了运动矢量地图。

其中，G（t－1）＝g，G（t）＝h：图像G在时刻t－1时的值为g，在时刻t时，值为h。对于每一个像素，可以表示为：G（t－1；i，j）＝g（i，j），G（t；i，j）＝h（i，j）。

图3．4 块匹配算法示意图

Dxk：代表图像G（t－1）和G（t）之间的纹理相关性。块的Dyk值是通过对其运用欧几里得平方范数结合标号的矢量：

－V＝（－umi，－vmj）

累加计算得到。

（4）更新目标块。在具有代表性的运动矢量的基础上，将有标号的块从前一时刻的位置移到下一时刻的位置，在这些块移动后，在新的位置前景与背景差异性小于给定的最初值，算法判定块不属于车辆区域，反之，如果新的车辆区域的相邻块前景与背景具有比较大的差异性时，算法判定块属于车辆区域，并赋予相同的车辆标号。

（5）划分目标块。在特殊情况下，多个对象同时通过矩形框可以被认为是一个单独的对象。为了划分这些对象，需要检查连通性及目标块的运动矢量分布。如果由几部分组成的单个车辆区域具有几个不同的运动矢量，这些部分将会被分离，并且被分配不同的车辆标号。怎么对多个对象进行分离，在目标地图最优化中将详细介绍。

跟踪算法得到的结果将作为后续研究中优化算法的初始标号。由于遮挡，第3步中一个块可能出现属于两个不同的块时（即长时间遮挡情况下），无法判断属于哪个标号。这个问题可以用基于反向ST－MRF模型的车辆跟踪来解决。

在自适应的车辆跟踪算法中，每一个块将被简单的块匹配技术所估计。然后在所有块的组成中一个代表集群的运动矢量将被确定为最常见的运动矢量，如图3．5（a）。在确定目标地图的最初状态时，集群的所有块通过参照这些具有代表性的运动矢量将移动到另一个目标地图，如图3．5（b）。移动结束后，检查相邻的块，删除那些不属于目标的块，并延伸那些与目标有联系的块，如图3．5（c）。如果移动块的相邻块具有不同的纹理，它们将被标号为一个集群。尽管一开始集群可能包括2～3辆车，但是经过一段时间的运动后，它们将会被背景图像分开。

图3．5 运动矢量地图的初始化

3．目标地图的最优化

目标地图是车辆标号的集合，同一辆车的相同标号的组成是车辆形状相似的几何体，它能对遮挡的车辆进行分离。当一个块被检测为属于两个对象时，必须确定这个块到底是属于哪一个对象。实际上，在这种情况下是很难确定的。这时可以运用ST－MRF模型结合随机松弛算法去优化这种复杂情况。ST－MRF模型是二维MRF模型的扩展，这个模型不仅仅优化图像的空间分布，还将优化图像序列沿着时间轴的分布。在一个图像序列中，沿着时间轴上相邻的对应像素位置之间都有着联系。ST－MRF模型考虑这种时间轴上的联系，建立时间算子（观察场）的ST－MRF的能量函数模型。在空间域上建立空间算子（标号场）的ST－MRF的后验概率模型。目标地图［X（t）＝y］优化问题最终变成了确定目标地图最小能量的问题，以及后验概率的最大问题。主要包括以下步骤：

（1）构建ST－MRF的能量函数。

其中，

G（t－1）＝g，G（t）＝h：图像G在时刻t－1时的值为g，在时刻t时，值为h。对于每一个像素，可以表示为：G（t－1；i，j）＝g（i，j），G（t；i，j）＝h（i，j）；

X（t－1）＝x，X（t）＝y：目标地图X在时刻t－1时被检测到标号分布为x，在时刻t时被检测到的标号分布为y。对于每一个块，可以表示为：Xk（t－1）＝xk，Xk（t）＝yk， k为块的编号；

U：能量函数；

Ny：指一个块的相邻块中和该块有相同标号块的数目，如果考虑使用8－邻域基团，则μNy＝8为最大值；

Dyk：代表图像G（t－1）和G（t）之间的纹理相关性，在发生遮挡时，分别计算属于各辆车的概率，哪个小更可能属于哪辆车。当运动矢量为，这时：：在当前的目标地图X（t）＝y下，前一目标地图X（t－1）＝x的有效值，即部分遮挡的两个块中遮挡部分的像素个数，显然为最大值；

U（yk）：ST－MRF的能量函数，可以通过松弛算法最小化。

（2）建立后验概率模型，并最大化。

针对目标地图X在时刻t－1时被检测到标号分布为x，在时刻t时被检测到的标号分布为y，图像G在时刻t－1时的值为g，在时刻t时，值为h。可以建立后验概率模型，并将其最大化。可以得到车辆标号场的一个最大可能实现，该后验概率可用贝叶斯表示为：式中，P［G（t－1）＝g，X（t－1）＝x，G（t）＝h］是常数，所以后验概率的最大值取决于式（3－4）的分子。

P［X（t）＝y］是块Ck的概率，并且Xk（t－1）＝yk，yk是车辆标号。对于每一个Ck，即每个块的概率看成高斯分布，可以用Blolzmann分布。

式中，是Ck块的相邻块数，如图3．6所示，这些块都属于相同的车辆标号，当Ny＝8时，能量函数的值最小，当Ny＝0时，能量函数的值最大。

图3．6 相邻块

则似然概率的最大值为：

（3）通过能量函数UM（Mxyk）判断块的归属性。是t时刻给定的目标地图x（t）＝y在时刻t－1时的目标地图的有效值。假设在当前的目标地图x（t）上，在大量被检测到的运动矢量中，Ck朝反方向移动。如在前一帧的图像中车辆标号OM的矢量为，重叠的部分被估计为，块与块之间的重叠像素的部分具有相同的车辆标号。越多的像素具有相同的车辆标号，块Ck越有可能属于车辆的标号的最大值为64，当时能量函数为最小值，当时，能量函数值最大。

要判断一个块属于车辆O1，还是属于O2，可以通过能量函数来判断。具体步骤如下：

步骤1 假设块属于车辆O1，通过参照其运动矢量，得到能量函数；

步骤2 假设块属于车辆O2，通过参照其运动矢量得到能量函数；

（4）通过能量函数判断块的归属性。

步骤3 比较这两个结果，如果要小于，那么块属于车辆M1。

Dxyk代表图像在时刻t－1与t之间的纹理相关性指标。假设Ck块在t－1时刻图像g按照估计的运动矢量朝反方向移动。纹理相关性指标的值为：

在时，能量函数的值最大 值越大，Ck块越有可能属于相对应的车辆。也就是越小，Ck块越有可能属于相对应的车辆。

要判断一个块属于车辆O1，还是属于O2，可以通过能量函数来判断。具体步骤如下：

步骤1 假设块属于车辆O1，通过参照其运动矢量 得到能量函数

步骤2 假设块属于车辆O2，通过参照其运动矢量）得到能量函数；

步骤3 比较这两个结果，如果UD1要小于UD2，那么块属于车辆UD1。

（5）求解能量函数的最小值

通过上述4个步骤，发现最优化的问题变成了在图像x（t）＝y时，求能量函数最小值的问题。

U（yk）被认为是ST－MRF的能量函数，U（yk）可以结合ST－MRF和松弛算法来判断块属于哪辆车。具体计算过程如下：

通过简单变形，式（3－9）变为：

由于块Ck被属于车辆O1和车辆O2的块包围，因此有：

Ny（yk＝O1）＋Ny（yk＝O2）＝μNy Mxy（yk＝O1）＋Mxy（yk＝O2）＝μMxy （3－11）

式（3－11）代入式（3－10），能量函数变为：式（3－12）是关于车辆O1和车辆O2对称的方程，如果U12（yk）是负数，则块Ck就属于车辆O1，如果U12（yk）是正数，则相反。

4．松弛算法

在问题中，求优化估计时将原问题转化成了求解后验能量U最小值所对应的状态，通常U有多个极小，即是非凸的，所以是一个组合优化问题。因此，本书根据Metropolis算法原理，具体见2．4．2，结合设计的跟踪算法和ST－MRF模型，设计了松弛算法步骤如下：

图3．7 松弛算法流程图

5．基于ST－MRF的车辆跟踪模块开发

系统开发的环境是Windows XP，采用的开发工具是Open CV和VC＋＋6．0。采用的视频图像是在淮安市淮海北路（淮海西路到黄河东路）自拍的一段30分钟视频录像。路段实况图如图3．8所示。

图3．8 路段google地图

本模块包括两部分，先使用一种基于检测矩形框处的阈值差法对车辆的存在进行检测，然后使用ST－MRF模型对车辆进行跟踪。先对车辆检测进行介绍。基于检测矩形框的车辆检测算法如图3．9所示。具体步骤如下：

图3．9 车辆检测流程图

（1）图像初始化，把一个720×640的图像分割成90×80块，即每块由8×8个像素组成。

（2）设置检测矩形框矩形大小可以手动调节，根据矩形的大小可以检测不同车道的车辆，如图3．10所示。

图3．10 检测矩形框示意图

（3）图像分割。

（4）计算检测矩形框上块的平均灰度。

（5）计算图像检测矩形框上的分割阈值。

阈值，又称为临界值，它目的是要确定一个范围，然后在这个范围内的部分使用同一种方法处理，而阈值之外的部分则使用另一种处理方法或者保持原样。阈值的分割实质上就是按照某个方法准确求出最佳阈值的过程。常用的全局阈值选取方法有很多，本书将采用最小误差法来确定检测矩形框位置和检测区域位置的阈值T。最小误差法是一种基于灰度值分布的概率模型方法。下面详细介绍最小误差法。

首先假设图像中“有意义”的目标的像素点灰度做正态分布，密度为P1（x），均值和方差分别为μ1和σ21。设背景点的灰度也做正态分布，密度为P2（x），均值和方差分别为μ2和σ22。整个密度函数可以看作是两个单峰密度函数的混合，如图3．11所示。从图上设法找到一个阈值，使划分目标和背景的错误分割概率为最小。

图3．11 目标点和背景点的坐标分布

设目标的像素点数占图像总点数的百分比为Q，背景点占（1－Q），则混合概率密度为：

当选定阈值为T时，目标点错划为背景点的概率为：

把背景点错划为目标点的概率为：

则总的错误概率为：

E（T）＝QE1（T）＋（1－Q）E2（T）（3－16）

则有：

这里，令：

－QP1（T）＋（1－Q）P2（T）＝0

由此可得：

当

若先验概率为已知，例如Q＝1／2，则有：

以上推导过程表示当满足正态分布时，最佳阈值可按公式（3－17）、（3－18）求得。若P1（x），P2（x）不是正态分布时，可用公式（3－16）来确定最小误差的阈值T。

（6）比较检测矩形框上块的平均灰度与阈值大小，若块的灰度大于阈值，说明有车辆存在，并给车辆标号，为了验证车辆跟踪算法，车辆标号从1开始累计。

车辆进入检测矩形框后，需要对车辆进行跟踪。基于ST－MRF模型的自适应车辆跟踪算法沿着时间序列自动更新车辆的形状。对于这个更新，算法在车辆区域的块中估计运动矢量。在每一个块上，运用块的匹配方法估计每一个目标块在相邻帧的运动矢量。

由图3．12车辆跟踪流程图可以看出，检测矩形框上的块对车辆的检测计算与图像帧之间运动矢量的计算是随着时间的推移运行的。即，当t时间检测矩形框上检测车辆存在后，得到车辆的初始标号，接着跟踪模块就开始用块匹配方法计算块在相邻帧所对应的运动矢量，并对检测矩形框上的初始车辆标号进行移位，得到通过检测矩形框后序列图像的车辆标号。

图像块匹配技术将检测模块中得到的初始车辆标号以及已经进入检测区域的车辆标号进行移动，从而将运动车辆图像序列转化为车辆标号序列。该标号序列是整个视频事件检测技术中的重要底层技术，为遮挡难题的解决提供技术平台，同时标号序列为交通参数的提取提供数据来源。

图3．12 车辆跟踪流程图

6．实验及结果分析

为了验证算法的跟踪效果，本次实验拍摄的视频为2012年11月14日上午9：30在淮安市淮海北路拍摄的一段视频，其中共有100辆车经过，22辆车被遮挡。图3．13为车辆跟踪显示图，通过该实验结果表明，在运用本文提供的方法检测到车辆87辆，检测率为87％，当用本方法跟踪不遮挡的车辆时达到的跟踪成功率为95％，如图3．14车辆遮挡时连续帧图像所示。用该方法跟踪遮挡情况的车辆时，误检率比较高，这时需要对遮挡图像进行处理，才能提高检测成功率。使用基于ST－MRF的车辆跟踪算法对输入的视频序列图像获得两种地图。一种是目标地图，表示车辆ID分布图的分割结果，如图3．15 （a）所示；另一种是运动矢量地图，表示与车辆ID号对应的块的运动矢量分布，如图3．15 （b）所示。从目标地图和运动矢量地图可以获得不同的交通参数，如交通量、速度、密度和加速度，为以后的交通事件检测提供重要的数据基础。

图3．13 车辆跟踪界面

图3．14 车辆跟踪图像

（a）目标地图

图3．15 ST－MRF跟踪实验结果

当车辆出现严重遮挡时，目标地图模糊，不能把遮挡的两辆车清晰地分开。当车辆遮挡不严重时，目标地图能将车辆分开。所以针对严重遮挡情况，还需进一步对ST－MRF的跟踪算法进行改进，可以考虑把遮挡的图像倒退到前一帧，这时每一辆车都可以分隔开，即反向ST－MRF的车辆跟踪算法。