流水线多目标跟踪的点匹配投票校正算法

罗三定，杨  芳

 (中南大学 信息科学与工程学院，湖南 长沙，410083)

摘  要：针对工业视觉检测系统中流水线多目标实时跟踪问题，提出一种目标中心点快速匹配方法与目标图像水平投影曲线投票校正技术相融合的多目标跟踪算法。其过程是：利用多个目标在连续帧图像中的整体分布的稳定性进行整体匹配，得到多点匹配的一一映射关系；针对局部目标的晃动、跳动问题，利用目标图像水平投影曲线，采用投票校正技术消除局部运动所带来的误差，对映射关系进行校正。该算法应用于某钢铁厂的棒材计数系统，有效地排除了复杂环境下多目标跟踪时的误识别、漏识别和位置交叉的问题，保证了计数的准确性与快速性，当目标数小于50时，跟踪时间小于1 ms。

关键词：多目标跟踪；实时算法；点匹配；校正

中图分类号：TP391         文献标识码：A         文章编号：1672-7207(2007)03-0528-05

Dots matching algorithm based on voting correction for

 multi-object tracking on assembly line

LUO San-ding, YANG fang

 (School of Information Science and Engineering, Central South University, Changsha 410083, China)

Abstract：For real-time tracking of multi-object on assembly line, a novel algorithm was presented based on fusion of object-center-fast-matching technique and image horizontal projection-curves voting-correction technique. Based on the stability of integral distribution of multi-objects don’t change too much in consecutive frames, this algorithm makes integral matching and obtains the mapping relation for dots matching, and secondly projects image to horizontal axis and uses voting-correction technique to remove errors in mapping relation caused by objects’ local movement. This algorithm was used in a certain steel-bar counting system. The results show that it can solve the problem of misrecognition, un-recognition and position crossing, and tracking time for each frame is less than 1 ms when objects are less than 50.

Key words：multi-object tracking; real-time algorithm; dots matching; correction

基于图像视觉的生产流水线多目标跟踪是计算机视觉系统应用于工业生产检测的一类具有普遍意义的问题，如轧钢厂的棒材计数、元件质量检测与分拣等。这类问题具有以下特性：被跟踪目标为团块状物体，目标大小和形状均相近，以随传送带整体单向运动为主，但存在局部相对运动，背景单一、静止。多目标跟踪的基本算法有：光流法，模板匹配法，特征点法，图像分割法等。光流法需对每一个像素点进行计    算^[1-2]，复杂度高，不能满足流水线跟踪的实时性要求；模板匹配最大限度地利用了图像信息，但只适合于跟踪少数目标^[2-5]，用于多目标跟踪同样存在复杂度高的问题；特征点法具有计算速度快的优点，但在提取特征的过程中损失了有用的图像信息^[6]，目标局部移动时将导致跟踪失败。图像分割法用较简单的方法提取目标特征，又保留了目标的区域信息，便于综合利用图像信息与特征信息，但对于形状相同或相似的多个目标难以区分^{[5, 7]}。鉴于单一方法的局限性以及实时性要求，需要采用多技术融合的方法^[8-9]。针对流水线多目标跟踪的问题，本文作者提出目标中心点快速匹配技术与目标图像水平投影曲线投票校正技术相融合的多目标跟踪方法，即首先利用目标整体分布特征进行快速对位得到初始结果，再利用目标图像水平投影曲线对初始结果进行投票校正得到最终结果。

1  技术融合框架

         技术融合过程如图1所示。首先，原始图像经图像分割处理后得到目标前景图；其次，对前景图分别进行提取目标中心和水平投影得到投影曲线2种处理结果；对投影曲线也分别进行 2 种处理：一是进行投影匹配得到整体偏移量，二是进行积分得到积分曲线；再次，利用整体偏移量确定目标中心的偏移值，实现整体对位；最后，用积分曲线对整体对位结果进行校正，得到最终跟踪结果。

图1  多技术融合的数据流图

Fig.1  Data flow graph of multi-technique fusion

为了便于描述，设CF表示当前帧的目标中心提取图，PF表示前一帧的目标中心提取图。这里定义1个直角坐标系，它的原点是CF或PF的左下角，x轴水平向右， y轴垂直x轴向上。

2  对位与校正

2.1  整体对位

多个目标随传送带向前移动时，整体分布保持一定的状态。如果整体分布不变，则可以用目标图像水平投影曲线进行匹配求出整体偏移量，实现前、后2幅图像中目标的快速对位。

2.1.1 投影

设p′(x)和p(x)分别为当前帧和前一帧目标图像的水平投影曲线，二者定义如下：

2.1.2  整体偏移量计算

目标整体作x轴上的单向运动，故可采用模板匹配技术将p′(x)和p(x)进行匹配，通过计算得到整体偏移量^[10]。

2.1.3  整体匹配

由于整体分布不变，若CF中的目标A与PF中的目标B两者的y坐标值相近，且A的x坐标值减整体偏移量后与B的x坐标值相近，则认为A和B为同一个目标。

定义1　设整体对位结果为S，其中每一个匹配对为S中的1个元素。

2.2  投票校正

         由于存在目标的局部位移，S中存在部分错误。为纠正这种错误，同时满足实时性要求，采用图像水平投影曲线的投票校正技术进行对位校正。即通过对图像的水平投影曲线进行积分得到积分曲线，再通过积分曲线由S中的已知匹配对推导其他匹配对并进行投票，S中所有元素均投票完后，计算每个被投票的匹配对所获票数，若票数超过给定阈值，则认为该匹配对正确，否则错误。

2.2.1　投影投票算法

将投影曲线p′(x)和p(x)沿x轴进行积分得到积分曲线c′(x)和c(x)。

在理想情况下，2对匹配对之间在前后帧中所夹目标数相同，故两者之间在前后帧中的投影值的累加值相同，即积分曲线差值相同。因此，若已知1个匹配对，则可由积分曲线推导出其他所有匹配对。但由于光照不均，某些目标在前后2帧投影值变化较大，造成积分曲线的误差累积，且越靠后，误差越大。为了避免误差累积，采用由当前匹配对推导邻近的匹配对并传递推导的投票方法。

a. 投票。连续2帧中相邻2个目标之间的投影积分值变化很小，故可由S中的单个已知元素a推导出与其相邻的匹配对，再由相邻的匹配对推导出下一个相邻匹配对，依次递推，直至遍历所有匹配对为止。单次投票过程描述如下：已知CF中第i个目标与PF中第j个目标相匹配。用X′(i)表示CF中第i个目标中心的x坐标值，X(i)表示PF中的第j个目标的x坐标值，则PF中第j-1个目标的x坐标值为：

这些推导出来的匹配对为a的投票对象，称此过程为a的投票过程。对S中的每个元素均进行投票运算，则得到一系列匹配对，称为初投票结果。

b. 表决。由于S中的匹配对整体可靠性不高，而当元素本身为错时，其推导出的匹配对均错，反之均对。故需要对初投票结果中的匹配对进行可靠性考察，以确定其是否为正确匹配对。

令m表示S的元素个数，由于S中的每一个元素置信度有差异，故令V(i)(i=0，…，m)表示其置信度。元素投票后，将自身置信度累加到投票对象的票数上。当V(i)均为1时，若m个匹配对中半数以上是对的，则初投票结果中票数过半的匹配对为正确的匹配对，否则为错误的匹配对。若不能满足S中半数以上是对的条件，在时间允许的情况下，采用模板匹配或目标相对位置关系检测的方法检测S中若干元素的正确性，若正确，则将这些元素的置信度提高，否则就降低，最终使得正确匹配对的置信度总和大于错误匹配对的置信度总和。这样，采用投影投票算法仍然得到正确的跟踪结果。

2.2.2  投影投票算法优化

由S中某一元素可推导出另一元素时，2个元素的投票结果相同，故可不必每次逐一投票，只需将已有投票结果中的每一投票对象的票数加上新元素的置信度即可。据此，可对快速投影投票算法进行优化。优化过程描述如下：

// 遍历S中的每一元素

       // 遍历投票结果

       // 总置信度累加

       If 元素已经存在

     // 累加每个对象的置信度

Else

       // 对元素投票

       // 累加每个对象的置信度

定义2　如果由S中的某一元素a通过投影投票法可以得出S中的其他1个或一些元素，则称a与这些元素属于同一类。

令n表示在CF中所识别出来的目标数，w表示S中的类数目，C_k (k=1，…，w)表示第k个类。设每个类C_k包含r_k个元素，这些元素的投影投票结果相同，设为A_k，并设在A_k中寻找某一匹配对所需的平均时间为t，由某一已知匹配对推出相邻某一匹配对所需的操作时间为t₀，用投影投票算法所需的操作时间为m(n-1)t₀，则用快速算法所需的操作时间为：

由于t₀远大于t，故快速算法的操作时间近似为w(n-1)t₀，所以，2种算法的时间差为(m-w)(n-1)t₀。在一般情况下，w小于5，即1帧中类的总数很小，而原始配对数m相对较大。

2.2.3  进一步校正

在中心提取过程中，通常存在以下2种错误：误识别和漏识别。在校正结果的基础上，通过邻近匹配法估计漏识别或误识别目标在对应帧中可能存在的位置，可改正这2种错误。2个或多个目标位置在前后帧中发生位置交叉时，可导致投影投票法跟踪错误。将整体匹配法运用到邻近匹配法中可避免交叉错误的影响，重获正确结果。

3  实验

这里将该算法用于解决棒材在线计数中的跟踪问题。传送带上众多棒材紧密排列并存在堆叠现象^[11]，所有棒材的端面都呈现类圆形^[12]，存在局部晃动、跳动的现象。

图2(a)所示为当前帧和前一帧的原始图像，图2(b)所示是2(a)经颜色分割法^[13]后得到的前景图，以及采用边缘集聚算法和环匹配算法^[12]所得的目标中心识别结果。前景图的投影曲线及积分曲线如图3所示。

(a) 原图; (b) 前景分割图及中心识别结果

图(a)和(b)中，上层表示当前帧图像，下层表示前一帧图像

图2  原始图像与前景分割图

Fig.2  Initial image and segmented image of foreground

(a) 当前帧投影曲线; (b) 前一帧投影曲线;

(c) 当前帧积分曲线; (d) 前一帧积分曲线

图3  灰度图的2种曲线

Fig.3  Two curves of gray-level image

图4(a)所示为当前帧和前一帧的原始图像，图4(b)所示为整体对位结果。可以看到大多数匹配对是正确

的，但由于局部晃动，使得整体对位结果发生错误，如CF中的第6根棒材匹配了PF中的第5根棒材，正确率为81%。在本实验中，V(i) 取为1。图4(c)所示为由投影投票算法所得结果，全部匹配正确。

(a) 原图，上层表示当前帧图像，下层表示前一帧图像;(b) 整体对位结果; (c) 投影投票结果

图4  整体对位与投影投票算法的跟踪结果

Fig.4  Tracking results of integral matching and projection-voting algorithm

图5显示了误识别、漏识别和位置交叉3种情况下该算法的跟踪结果。图中用矩形框指出了这3种情况的具体位置。其中：左图表示原始图片及棒材端面中心识别结果，右图表示跟踪结果，矩形框内箭头表示估计位置。利用跟踪结果，采用K级容错计数法^[10]，即可得到准确的计数结果。

(a) 误识别；(b) 漏识别；(b) 位置交叉

图5  3种情况下的棒材分布及跟踪结果

Fig.5  Images of tracking results in three cases

表1所示为模板匹配法、投影投票算法和快速投影投票算法3种算法的执行时间比较结果。其中，模板匹配法是将CF的每一个目标中心点通过整体偏移量在PF中寻找对应的中心点，然后，采用传统模板匹配算子^[3]，用R×R(R为棒材端面直径)的连通域模板在对应中心点及其邻近2点的4×4区域进行匹配。所以，算法的执行时间为48t_p(其中t_p为单次模板匹配时间)，而t₀为只有1次快速搜索和1次加减运算所需时间，所以，t_p远大于t₀，且m通常小于48，故投影投票算法速度比模板匹配算法速度快。

表1  模板匹配法、投影投票算法和快速投影投票算法的执行时间

Table 1  Execution time of template matching algorithm, projection voting algorithm and its optimized algorithm

从表1可以看出：投影投票算法的执行时间远小于模板匹配算法执行时间；投影投票算法经优化后在某些帧次下比优化前快10倍，其时间波动比较小，这说明它的复杂度低。

4  结　论

a. 所提出的方法鲁棒性强，可以解决多目标跟踪中的误识别、漏识别和位置交叉的问题。在目标数小于50的单帧图像的跟踪中，进行整体对位的时间小于0.8 ms，投票校正时间小于0.2 ms，故该算法总执行时间小于1 ms，即在目标中心识别的基础上，只用了很少的时间用于跟踪。这使得该方法可应用于流水线的实时多目标跟踪。

b. 当目标堆叠层数超过3层时， 目标图像的水平投影曲线不能准确反映单个目标的水平方向位置，故进行投票校正时容易出错。该问题有待于进一步研究。

参考文献：

[1] 马颂德, 张正友. 计算机视觉[M]. 北京: 科学出版社, 1998.

MA Song-de, ZHANG Zheng-you. Computer vision[M]. Beijing: Science Press, 1998.

[2] 万　缨, 韩　毅, 卢汉清. 运动目标检测算法的探讨[J]. 计算机仿真, 2006, 23(10): 222-223.

WANG Ying, HAN Yi, LU Han-qing. The methods for moving object detection[J]. Computer Simulation, 2006, 23(10): 222-223.

[3] 何 斌, 马天予, 王运坚, 等. 数字图像处理[M]. 北京: 人民邮电出版社, 20001.

HE Bin, MA Tian-yu, WANG Yun-jian, et al. Digital image processing[M]. Beijing: Peoples’ Posts & Telecommunications Press, 2001.

[4] Betke M, Haritaoglu E, Larry S D. Real-time multiple vehicle detection and tracking from a moving vehicle[J]. Machine Vision and Applications, 2000, 12(2): 69-83.

[5] Xu L Q, Landabaso J L, Lei B. Segmentation and tracking of multiple moving objects for intelligent video analysis[J]. BT Technology Journal, 2004, 22(3): 142-147.

[6] Chetverikov D, Verestoy J. Feature point tracking for incomplete trajectories[J]. Computing, 1999, 62(4): 321-338.

[7] Chantelau K. Segmentation of moving images by the human visual system[J]. Biological Cybernetics, 1997, 77(2): 91-100.

[8] 王麟琨, 徐 德, 谭 民. 机器人视觉伺服研究进展[J]. 机器人, 2004, 26(3): 279.

WANG Lin-kun, XU De, TAN Min. Survey of research on robotic visual serving[J]. Robot, 2004, 26(3): 279.

[9] 冷晓艳, 薛模根, 韩裕生, 等. 基于区域特征与灰度交叉相关的序列图像拼接[J]. 红外与激光工程, 2005, 34(5): 602-603.

LENG Xiao-yan, XUE Mo-gen, HAN Yu-sheng, et al. Sequence image swtitching based on area feature and cross correlation[J]. Infrared and Laser Engineering, 2005, 34(5): 602-603.

[10] 罗三定, 李第平. K级容错计数算法的设计与实现[J]. 计算机工程与应用, 2004, 40(16): 94-95.

LUO San-ding, LI Di-ping. Design and implementation of K-time-count fault tolerance algorithm[J]. Computer Engineering and Application, 2004, 40(16): 94-95.

[11] 罗三定, 沙 莎, 沈德耀, 等. 棒材生产在线视觉计数系统研究[J]. 小型微型计算机系统, 2004(4): 672-673.

LUO San-ding, SHA Sha, SHEN De-yao, et al. On-line visual counting system for production of steel bar[J]. Minimicro Systems, 2004(4): 672-673.

[12] 罗三定, 肖 飞. 不规则类圆形团块目标图像识别的新方法[J]. 中南大学学报: 自然科学版, 2004, 35(8): 633-636.

LUO San-ding, XIAO Fei. A new method of recognizing quasi-circular object[J]. Journal of Central South University: Science and Technology, 2004, 35(4): 633-636.

[13] 林开颜, 吴军辉, 徐立鸿. 彩色图像分割方法综述[J]. 中国图像图形学报, 2005, 10(1): 2.

LIN Kai-yan, WU Jun-hui, XU Li-hong. A survey on color image segmentation techniques[J]. Journal of Image and Graphics, 2005, 10(1): 2.

收稿日期：2006-12-11

基金项目：国家自然科学基金资助项目(60573079)

作者简介：罗三定(1955-)，男，湖南浏阳人，教授，从事图像处理和智能信息处理研究

通讯作者：杨  芳，女，硕士研究生；电话：0731-8830982；E-mail: onlysfang@hotmail.com