ABSTRACT

对象跟踪是视频和图像处理领域中的一个基本问题。尽管在灰色视频上使用跟踪算法在实际应用中很方便，但由于考虑到的信息较少，因此与使用色彩功能的算法相比，它们更难以开发。很少有研究致力于使用边缘信息跟踪对象。

在本文中，我们提出了一种基于边缘信息的灰色视频跟踪算法。

该方法采用组合粒子滤波和改进的倒角匹配方法。

改进的倒角匹配是旋转不变的，并且能够通过orientation distance transform来估计观察到的图像块和模板之间的偏移。

采用了一种针对差异的改进的判别似然性测量方法。这些值被标准化，并用作预测和跟踪对象的粒子的权重。

实验结果表明，我们对倒角匹配的改进提高了其在视频跟踪问题中的性能。该算法稳定，鲁棒，可以有效地处理旋转畸变。

可以在更新模板上做进一步的工作，以适应跟踪过程中物体的明显视点和比例变化。

Keyword: chamfer matching, orientation distance transform, particle filter

INTRODUCTION

视频跟踪是视频和图像处理领域中的一个基本问题。 从对象轨道中检索到的信息是进一步应用的基础。
视频跟踪问题包括两个主要部分。

首先是提取在时间t和t + 1处的图像特征，这些特征可以有效地区分对象和背景。
第二个是将提取的特征与模板进行比较，并根据对象在t处的状态，估计对象在t + 1处的位置。

边缘信息被广泛用于匹配两个图像。

倒角匹配由Barrow于1977年首次提出[1]。
该算法引入了距离变换以从不同图像中找到边缘点的最佳拟合。由于直接计算精确的欧几里得距离需要大量资源，因此Gunilla Borgefors [2]提出了一种简化的方法3-4 DT来估算距离。

3-4 DT算法通过对二进制边缘图像进行两次遍历来获得距离图像，并且距离欧几里得距离的最大差异为8％。

2004年，Pedro F. Felzenszwalb和Daniel P. Huttenlocher [3]引入了线性时间算法，通过计算抛物线的下包络来计算任意函数的精确欧几里德距离变换。

Borgefors [2]提出了一种分层倒角匹配算法来寻找最佳匹配
通过从粗到精的搜索。
它通过遍历实现旋转和比例不变，这将利用每个可能的角度和比例并确定全局最小值。

Chen [4]提出了一种改进的版本，可以通过模拟退火获得最佳拟合。

Thayananthan等[5]使用倒角匹配来，追踪手形，在混乱的图像中。他们的论文中的倒角算法使用欧几里德距离来测量相似度，并且无法使用单个模板来处理旋转变化。此外，他们无需任何预测步骤即可跟踪目标。

最近，粒子滤波，例如Israd和Blake提出的“Condensation ” [6]，已经在跟踪领域得到了更广泛的应用，因为它不需要众所周知的卡尔曼滤波器[7]所要求的任何高斯假设。

此外，Lei [8]和Pupilli [9]的作品证明了粒子滤波器在视频跟踪中的有效性和鲁棒性。 所有这些方法贪婪地产生新的粒子
仅根据先前的高斯分布假设。

本文提出的方法是针对灰色视频的目标跟踪而设计的。

a condensation particle filter and an improved chamfer matching.
它结合了粒子滤波和改进的倒角匹配功能。

在当前帧中粒子指示的位置提取图像补丁。
所有边缘点都位于补丁中。

然后采用本征分解，在二进制边缘补丁上获取边缘点的分布参数，这样就能将其用于将补丁旋转到与模板相同的方向。

归一化后，将补丁和模板之间的似然值作为权重分配给粒子。

粒子滤波器用于跟踪和预测对象的状态。

根据通过改进的倒角匹配估计的偏移矢量，试探性地生成新粒子。

实验结果表明，改进的倒角匹配算法更适合于目标跟踪问题。借助位移矢量，可以用更少的粒子获得类似的性能。改进的倒角匹配和凝结粒子过滤器的结合，可以独立，稳定，有效地跟踪物体旋转。

本文的其余部分安排如下。 第2节详细讨论了改进的倒角匹配算法。 在第3节中，描述了粒子滤波。 实验结果在第4节中显示。最后在第5节中得出结论。

2. IMPROVED CHAMFER MATCHING

在倒角匹配中，图像的所有边缘点都首先通过边缘检测算法（例如canny方法）进行检测，本文将不进行介绍。

其次，通过特征分析对二值边缘图像进行预处理
从而纠正其主要方向。

第三，对二进制边缘图像进行distance transformation距离变换以获得距离图像。
在此步骤中，边缘像素的值设置为零。
每个非边缘像素的值设置为到其最近边缘像素的距离

2.1 Rotation invariance

原始倒角匹配对旋转很敏感。

结果容易受到旋转失真的影响。
因此，必须首先校正图像的旋转。

Borgefors [2]采用全局搜索来找到一个主要方向，在该方向上获得最小的匹配距离，以弥补这一缺点。

我们对二进制边缘图像采用特征分解来实现旋转不变性。

它不需要多个模板或全局搜索，因此比全局搜索更加有效和准确。

二进制边缘图像中所有边缘点的坐标均视为数据集：

where （x，y） are the coordinates of the ith edge point in the binary edge image, N is the total number of edge points. The covariance matrix C of the coordinates is given by:
其中（x，y）是二值边缘图像中第i个边缘点的坐标，N是边缘点的总数。 坐标的协方差矩阵C由下式给出：

其中x^ 和 y^ 是平均值，所有边缘点的所有横坐标和纵坐标。

矩阵C的大小为2x2。C的最大特征值和对应的特征向量V0通过特征分解来计算。

V0代表图像的主要方向。 主方向和水平线之间的角度由下式给出：

跟踪视频中的对象时，每个图像旋转其主方向与模板之间的角度差。

旋转方程如下：

H_t和H_p是将模板和图像映射到归一化方向的变换矩阵。

在校正了图像的方向之后，第2.3节中描述的匹配测量能够在没有旋转失真干扰的情况下得出似然估计。

Orientation Distance transformation (ODT)

传统的距离变换生成距离图，该距离图可用于估计两个二进制边缘图像之间的似然性。

但是在视频对象跟踪的情况下，目标是使用给定的模板跟踪对象。 对象所处的位置可能比图像与模板的相似程度更多。

因此，我们引入了定向距离变换（ODT），该函数为每个像素分配了一个复数。

像素值的大小和相位角分别表示到最近边缘像素的距离和方向。

因此，对于图像时，其方向距离图不仅意味着：相对于对象模板的相似可能性，而且表明了其可能的位置。

Felzenszwalb [3]证明，可以通过沿着图像的每一行执行一维变换，然后沿着每一列执行一维变换来计算二维欧几里德距离变换。

我们对此程序进行了修改，以获取精确的方向距离图。

首先，将所有边缘像素设置为零，将非边缘像素设置为无限。

一维变换
在 real parts 实际部分上
沿每一行。

代替[3]中那样计算欧几里德距离的平方，我们计算一个有符号的距离值。

正值表示最近的边缘点位于右侧；
负值表示最近的边缘点位于左侧。

此步骤的结果分配给 real parts 。

因此，在那些至少包含一个边缘点的行中，像素的所有实部都具有有限的距离值。

并且其他行中的那些保持无限。

然后，沿每一列对 real parts 实部执行一维变换。
到最近像素的符号距离值
具有有限的 real parts 实部
被分配给像素的imaginary parts,虚部，
并将最近像素的实部分配给像素的 real parts 实部。

该过程确保每个像素的虚部指示包含最近边缘点的行的相对位置，并且每个像素的实部指示包含最近边缘点的列的相对位置。

因此，可以从取向距离图像中的任何像素精确地定位最近的边缘点。

该过程的伪代码在算法1中显示。

斜体部分引自[3]；粗体部分是我们的修改。

数组f，dR和dC代表ODT输入图像，
ODT的实部和imaginary parts,虚部分别得到。

显然，dR和dC是整数。

图1给出了二值图像上定向距离转换的结果。
黑白像素代表边缘和非边缘像素。

箭头的长度和方向代表到最近边缘点的距离和方向。

2.3 Likelihood measurement

为了测量两个相同大小的二进制图像之间的似然性，将其中一个作为掩模，而将另一个作为模板并由ODT处理。

经典倒角匹配[2]使用均方根平均值如下，以测量可能性：

其中n是图像中正像素的数量，vi是距离图像中被蒙版中正像素命中的像素的值。

此方法可分别描述蒙版和模板之间的差异。

我们基于信号检测理论采用了一种不同的测量方法，该方法比经典方法更具区分性。

掩模叠加在orientation distance image取向距离图像上。

然后，所有正像素都击中orientation distance image定向距离图像中的一些。

如果将掩模中的正像素视为边缘点的检测结果，则可以通过命中边缘像素的比率和命中非边缘像素的比率定义真正率（TPR）和假正率（FPR）为 ：