一种背景轨迹找回方法和装置

摘要

本发明公开了一种基于前景轨迹位置和相似度衡量的背景轨迹找回方法和装置，所述方法包括：确定每条前景轨迹的空间相邻轨迹，并确定所述空间相邻轨迹被标记为背景轨迹的数量是否大于第一预定数量；如果所述空间相邻轨迹被标记为背景轨迹的数量大于预定数量，则计算被标记为背景轨迹的所述空间相邻轨迹与所述前景轨迹之间的相似度度量值；如果所述相似度度量值大于相似度度量值判别阈值的所述空间相邻轨迹数量大于第二预定数量，则将所述前景轨迹标记为背景轨迹。

说明书

技术领域

本发明涉及数字图像处理和智能交通技术领域，尤其涉及一种背景轨迹找回方法和装置。

背景技术

近些年，随着汽车工业的蓬勃发展，交通安防监控设备越来越广泛的用于道路车辆的监控。由于受到外界因素的干扰，车载或手持等移动交通安防监控设备拍摄时难免抖动。抖动的监控视频严重影响观看效果，对判断车辆的行驶行为也会造成干扰。因此，消除视频抖动在视频监控、智能交通等领域成为一个重要的方向。

交通视频通常包含快速移动的交通工具和相对固定的道路、天空、绿化带等背景物体这两部分。为与背景物体对应，把快速移动的物体称为前景物体。对于移动设备拍摄的视频，背景物体和前景物体都在运动，前景的运动量包含前景本身和摄影器材的运动，而背景的运动量只是摄影器材本身的运动。由此可见，降低和消除交通视频抖动即是抑制背景运动中的抖动成分。因此，从抖动的交通视频中筛选出足够丰富用以抑制抖动的背景特征轨迹是消除交通视频抖动的前提和重要一环。

针对移动设备拍摄的视频，现有的去抖方法很多，总体上可以分为两大类：借助于特征匹配等图像配准技术的2D方法和基于SFM方法恢复相机3D运动和特征点三维轨迹信息的3D方法(见参考文献【1】R.I.Hartley and A.Zisserman，Multiple View Geometry in Computer Vision.Cambridge Univ.Press，2000.2341-2353)。对于只包含平面运动的场景，2D方法处理速度快，平滑效果好。但是该方法无法处理非平面内的运动，对视差敏感，遇到明显的景深变化时彻底失效。3D方法虽然从根本上解决了视差的影响，但在遇到明显的平面运动时会过处理，且SFM方法复杂，耗时严重。

近年来，研究者们纷纷致力于将二者的优势结合起来，尽量避免二者的劣势。参考文献【2】(LIU，F.，GLEICHER，M.，WANG，J.，JIN，H.，AND AGARWALA，A.，“Subspace video stabilization”.ACM Trans.Graph.30，2011)针对近乎静止背景的视频，提出不恢复3D场景信息，而是利用子空间特性(见参考文献【3】M.Irani，“Multi-frame correspondence estimation using subspace constraints，”International Journal of Computer Vision，vol.48，no.3，pp.173-194，2002)将轨迹矩阵限制在二维，并根据降维前后的误差可以有效检测出运动物体的特征轨迹。用这种方法区分出属于前景物体的特征轨迹并剔除之，改善了近似静止拍摄的视频的去抖效果。参考文献【4】(A.Goldstein and R.Fattal，“Video Stabilization Using Epipolar Geometry，”ACM Trans.Graphics，vol.31，pp.1-10，2012)提出使用“外极约束”来剔除属于前景运动物体的特征轨迹，极大地提高了算法对背景快速运动和包含大的前景运动物体的视频的鲁棒性。另外，受视差干扰的特征轨迹也会因为不满足外极约束被检测出来。所以，该方法能有效判定出一条轨迹是否受属于前景运动物体和视差。

但是针对一些由于错误匹配或者阈值设定过于严格导致被错判的轨迹，上述两种算法并没有丝毫的容忍度和后续处理，而这种错判在很多情况下是不可避免的。实际上，这些轨迹在错判之后是完全有可能恢复正常的，比如连续多帧错误匹配之后，该轨迹会变为另一条背景轨迹；而由于阈值设定过于严格导致的错判的轨迹，其实本身可能就是背景轨迹。在背景轨迹数量降低到一定程度之后，将某些被错判的轨迹的重新加入到背景轨迹行列，是可以大大提高对视频去抖算法的精度，并将大大有益于后续帧的前景轨迹判定过程的正确执行。

背景轨迹找回的依据是该轨迹所处的位置和它与周围已知背景轨迹的相似度。参考文献【5】(K.-Y.Lee，Y.-Y.Chuang，B.-Y.Chen，and M.Ouhyoung，“Video Stabilization Using Robust Feature Trajectories，”Proc.IEEE 12th Int'l Conf.Computer Vision(ICCV)，pp.1397-1404，2009)使用德劳内三角剖分算法划分当前帧的特征点，把三角网格内拥有共同边的特征点对视作空间相邻点，检验特征点链接而成特征轨迹的空间相邻位置关系的一致性而获得稳健的特征轨迹。借鉴这一划分特征点位置的思路，我们使用德劳内三角剖分算法划分每个当前帧的特征点，找出每条前景轨迹的空间相邻轨迹。查看相邻轨迹的判定情况，如果其相邻轨迹中有超过2条背景轨迹，那么该前景轨迹被认为是可能被误判的背景轨迹，再比较其与已知相邻背景轨迹的相似度。目前有许多关于轨迹间相似度衡量的方法，参考文献【6】(Zhang Zhang，Kaiqi Huang，Tieniu Tan.Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes.in ICPR'06：Proceedings of the 18th International Conference on Pattern Recognition(ICPR'06).Pages 1135--1138)中提供了六种用于户外监控场景的轨迹聚类相似性度量方法性能优劣的比较。实验结果显示，Hausdorff未考虑轨迹方向的影响且耗时最多，HMM的训练方法要求大量的特征点，否则将出现过拟合现象，这二者在处理交通视频时度量的准确率较差。LCSS和DTW均具备了较高的相似性度量准确率，也有一定的抗干扰能力，但是它们在描述柔性物体形状变化方面的优势带来了严重的时间开销，而这个优势并不能在处理交通视频的特征轨迹时起作用。权衡度量的准确性、时间开销和抗噪能力，欧式距离和PCA+欧式距离更适用于处理交通视频的轨迹相似性度量。更进一步，PCA+欧氏距离方法在筛选主要成分环节需要一定计算量，却未能带来明显的效果提升，因而被排除出相似性度量方法的选择。

发明内容

有鉴于此，本发明提出了一种背景轨迹找回方法和装置，其采用背景轨迹找回机制，作为前景轨迹判定过程的后续操作，以便背景轨迹样本数量偏少时增加背景轨迹数量，提高用于生成稳定帧的单应矩阵的计算精度，优化视频去抖的效果。

根据本发明一方面，提供了基于前景轨迹位置和相似度衡量的背景轨迹找回方法，包括：

确定每条前景轨迹的空间相邻轨迹，并确定所述空间相邻轨迹被标记为背景轨迹的数量是否大于第一预定数量；

如果所述空间相邻轨迹被标记为背景轨迹的数量大于预定数量，则计算被标记为背景轨迹的所述空间相邻轨迹与所述前景轨迹之间的相似度度量值；

如果所述相似度度量值小于相似度判别阈值的所述空间相邻轨迹数量大于第二预定数量，则将所述前景轨迹标记为背景轨迹。

根据本发明另一方面，提供了一种基于前景轨迹位置和相似度衡量的背景轨迹找回装置，包括：

空间相邻轨迹确定模块，用于确定每条前景轨迹的空间相邻轨迹，并确定所述空间相邻轨迹被标记为背景轨迹的数量是否大于第一预定数量；

相似度度量值计算模块，用于如果所述空间相邻轨迹被标记为背景轨迹的数量大于预定数量，则计算被标记为背景轨迹的所述空间相邻轨迹与所述前景轨迹之间的相似度度量值；

背景轨迹找回模块，用于如果所述相似度度量值小于相似度判别阈值的所述空间相邻轨迹数量大于第二预定数量，则将所述前景轨迹标记为背景轨迹。

本发明提出的方案能够针对基于视频去抖算法中轨迹判别阈值设置过于严格导致部分视频图像帧的正常背景轨迹数量偏少，能够找回被误判的特征轨迹；本发明还针对视频去抖算法中由于几次偶然的特征轨迹匹配错误导致部分视频图像帧的正常背景轨迹数量偏少，找回部分已经回归正常的特征轨迹。

附图说明

图1是前景轨迹与背景轨迹的运动不一致性示意图；

图2是本发明中基于前景轨迹位置和相似度衡量的背景轨迹找回方法流程图；

图3是本发明中德劳内三角剖分进行空间相邻轨迹的分配示意图；

图4是本发明中利用本发明找回的背景轨迹示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明作进一步的详细说明。

本发明的技术方案分利用特征轨迹的位置和其与背景轨迹之间的相似度来找回该背景轨迹；首先，本发明基于德劳内三角剖分的连续轨迹位置划分，该划分可以有效地找出每条前景轨迹的空间相邻轨迹，用以判定该前景轨迹存在误判可能性的大小；然后进行轨迹相似度衡量，针对筛选出潜在被误判的前景轨迹，一一衡量该前景轨迹与相邻已知背景轨迹的相似度，从而判定该轨迹是否存在误判。

本发明提出的方案中背景轨迹找回依据包括：

首先，特征轨迹代表的是前景或背景物体的运动量，而物体在图像中都是一块或一片的，因此可以认定前景或背景轨迹都将成堆或成片的出现。其次，前景物体的运动量源于其本身和摄影器材运动的叠加，背景物体的运动量只源于摄影器材，这两者的不同必然导致前景轨迹与背景轨迹的延伸曲线的形状的不一致。

如果一条前景轨迹空间相邻轨迹中没有背景轨迹存在，那么其被判为前景轨迹是合理的；相反，如果它的空间相邻轨迹中背景轨迹数量超过一定阈值，比如2条，并且陔轨迹与这些已知背景轨迹足够相似，那么就很可能存在错判。由这两个依据，本发明制定出先查看前景轨迹相邻轨迹的分布情况再进行相似度衡量的背景轨迹找回策略。

对于包含大前景物体的交通视频，大前景物体的运动趋势与背景物体的运动趋势通常不一致。由于特征轨迹代表物体或视差块的运动趋势，因此，可以推断前景轨迹和背景轨迹形状的差异很大。直观感受上，物体在视频图像中都是一块或一片的，假定同类属性的特征轨迹也将成堆、成片的出现。

基于以上两点假设，本发明通过反复标记大量视频图像的所有特征轨迹，得到的实验结果均与图1类似。图1中每条轨迹的长度均相等，圆圈圈定的是当前判定为前景的轨迹，长线条标记的是连续轨迹。从实验的图中可以得出，代表前景(或背景)物体运动趋势的前景(或背景)轨迹聚集且相似度高，前景轨迹和背景轨迹的形状差异性很大。

图2示出了本发明提出的基于前景轨迹位置和相似度衡量的背景轨迹找回方法的流程图。如图2所示，所述方法包括：

在步骤101中，确定每条前景轨迹的空间相邻轨迹，并确定所述空间相邻轨迹被标记为背景轨迹的数量是否大于第一预定数量；

德劳内三角剖分是对平面内点集三角化分割而形成位置关系的经典方法。它将点与点之间建立位置关系，由是否拥有共同边而筛选出空间相邻的一组点。在一实施例中，本发明利用德劳内三角剖分对连续特征点轨迹在当前帧中对应的特征点的位置进行三角划分，找出每条前景轨迹的空间相邻轨迹，一一查看空间相邻轨迹的判定标记情况。

所述第一预定数量为所述前景轨迹全部相邻空间轨迹的一半。

如果某条前景轨迹的空间相邻轨迹标记为背景轨迹的数量超过阈值如2条，则有必要进行下一步轨迹相似度的衡量。

在一实施例中，步骤101包括：

对所有连续特征点轨迹在当前帧所处的位置集合进行德劳内三角剖分；

在德劳内三角剖分形成的三角形中，确定两两特征点轨迹所在三角形之间是否拥有共同边判定是否为空间相邻，从而获得每条特征点轨迹的空间相邻轨迹。

本发明提出的上述方法对视频图像帧的每条连续轨迹进行位置划分，找出每条前景轨迹的空间近邻。划分的位置关系如图3所示。任何两个共同拥有一条边的两条轨迹为相邻轨迹。

在步骤102中，当空间相邻轨迹被标记为背景轨迹的数量超过预定数量，则计算所述前景轨迹与相邻背景轨迹的之间的相似度度量值。

在一实施例中，相似度度量值是计算两条轨迹间相应特征点位置之间的差值变化之和，和越小说明特征点位置越接近。也就是相似度度量值越小，相似的可能性越大。

在一实施例中，由于权衡度量的准确性、时间开销和抗噪能力，而且所处理的轨迹长度都相等，因此可采用欧式距离作为衡量轨迹间相似度的方法。

在另一实施例中，可选择使用L1范数来衡量轨迹间的相似度度量值，即相邻轨迹坐标差的绝对值的累积和(SAD)作为衡量标准。本发明中用此方法把潜在的误判轨迹即空间相邻轨迹数目大于阈值的前景轨迹和空间相邻轨迹中的背景轨迹一一进行相似度衡量，若该前景轨迹与多数相邻背景轨迹足够相似，则可以确定为需要找回的轨迹。

在另一实施例中，在进行相似性判定之前，必须对前景轨迹和空间相邻轨迹进行归一化处理，即每条轨迹都减去各自特征点的第一个坐标值。

在一实施例中，用SAD值作为两条轨迹的相似性度量。SAD计算方法如公式(1)所示，其中N为轨迹长度。

$\mathrm{SAD}=\frac{1}{N}{\Sigma }_{n=1}^N\left(\right|a_n^x-b_n^x|+|a_n^y-b_n^y\left|\right)---\left(1\right)$

式中为组成前景轨迹的特征点坐标，为组成某一相邻背景轨迹的特征点坐标。若SAD＜ReThresh(ReThresh＞0，相似度判别阈值)，则认为该前景轨迹是被误判了的背景轨迹。对于被误判的背景轨迹，将其轨迹属性恢复为背景轨迹。

在步骤103中，当与所述前景轨迹的相似度度量值小于相似度判别阈值的相邻背景轨迹的数量大于第二预定数量时，将所述前景轨迹标记为背景轨迹。

所述第二预定数量大于所述前景轨迹的所有相邻背景轨迹的数量的一半。

针对上面的例子，实验结果如图4所示，其中圆圈所示为找回的背景轨迹。可见，该轨迹在最近N帧中确实展现了与背景轨迹的运动趋势的相似性，所以被找回也是非常合理的。

通过设置合理的轨迹相似性阈值ReThresh，可以在每帧视频图像中找回的背景轨迹数量一般为1～10条。试验表明，ReThresh的值在10-40之间最佳。实验证明，被找回的轨迹，在最近若干帧中的运动趋势都是与背景轨迹呈现一定相似性的轨迹，从而证明了该找回算法的合理性和有效性。而且，被找回的轨迹将与正常的背景轨迹地位相同，都将被用于轨迹平滑和最后的用于生成稳定帧的单应矩阵计算，从而大大提高了最终单应矩阵计算结果的精确性，提高了去抖算法的性能。

交通视频存在大前景物体，大前景物体上的轨迹的运动趋势与背景物体的运动趋势通常是不一致的。再者，大前景物体导致的前景轨迹在视频图像中都是成片出现的。因此，可以推断相似的特征轨迹也是成片出现，前景轨迹与背景轨迹的形状存在明显差异。通过试验中标记了大量视频图像的特征轨迹，实验统计结果证明我们的推断是正确的。这一论证为我们提供了找回背景轨迹的依据，使我们寻找到了解决背景轨迹被误判的方法。该依据合理地利用了每条轨迹的位置信息，从而在第一步就剔除了许多不太可能被错判的轨迹，更是免除了许多不必要的计算。

为寻找背景轨迹找回方法，论证发现了同类属性的轨迹会聚集出现这一现象。本发明利用德劳内三角剖分来划分所有连续轨迹在当前帧对应特征点的位置关系。德劳内三角剖分高效地划分了庞杂点集的位置关系，对于拥有三角网格内共同边的特征点对，可以认定为相邻点。这一划分有效地找出了一条轨迹的相邻轨迹，为我们查看相邻轨迹的属性奠定了基础。在找出的空间相邻轨迹集合里，一一对照每条轨迹的属性，以此来推断该聚集处的轨迹属性，而一条轨迹的相邻轨迹中包含一定数量的背景轨迹才有可能是被误判和需要被找回的轨迹。德劳内三角划分是个成熟稳定而快速的方法，免除了直接利用位置、距离等信息需要对不同分辨率视频设定自适应阈值的麻烦。

一条轨迹的相邻轨迹大多数是背景轨迹也并不能推断出该轨迹是背景轨迹，还必须进行轨迹相似度衡量。我们最终选择相邻轨迹的SAD值作为轨迹相似度衡量的方法。这一方法具有度量的准确性较高、时间开销少等优点，非常适合于交通视频的特征轨迹相似度衡量。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。