一种基于CamShift算法和随机Hough变换的球形目标跟踪算法

张晨+王红茹+丁文+王云辉+钱康

摘 要 为提高视觉移动机器人对球形目标的跟踪精度与实时性，文章利用CamShift算法具有依靠颜色模型能够对目标快速跟踪的特点，并结合随机Hough圆变换提出一种实效球形目标跟踪算法。实验结果表明，提出的方法能够实现简单室内环境下球形目标的快速准确跟踪。

关键词 目标跟踪；球形目标；CamShift算法；随机Hough变换

中图分类号：TP391.41 文献标识码：A 文章编号：1671-7597（2014）04-0054-02

计算机视觉应用中，目标跟踪一直是研究的热点内容之一。而在目标跟踪研究中，最值得关心的就是跟踪算法的实时性和准确性。为此，相关学者提出了很多不同的方法，其中应用最为广泛的是Gary R Bradski提出的基于自适应均值漂移（Continuously adaptive mean shift，CamShift）算法。CamShift算法依靠视频图像的色彩信息来实现对目标的跟踪，其运算速度快且比较适合不太复杂的背景下的目标跟踪，因此适合室内移动机器人对目标的跟踪。

而对于基于视觉的室内移动机器人目标跟踪，仅仅依靠CamShift这种依靠颜色模型的跟踪方法，无法在照度不均的情况下获得圆形目标物的精确位置信息。而随机Hough圆变换具有对圆形目标识别精度高且速度快的特点。为此，本文提出采用CamShift算法与随机Hough变换结合的方法以实现对球形目标的快速、准确跟踪。

1 算法原理

1.1 CamShift算法介绍

CamShift算法实际上是连续自适应的MeanShift算法的简称。该算法降低了由光照亮度变化对跟踪效果的影响，并且利用基于像素颜色概率分布信息进行目标跟踪的方法，使算法的效率比较高。CamShift算法采用基于概率密度的梯度攀升来寻找局部最优的思想对每一帧图像运用MeanShift算法做处理。根据前一帧图像的搜索结果自适应调整搜索窗的大小，从而实现对当前图像中目标的定位。

算法主要步骤如下。

1）首先将当前帧图像由RGB空间转换到HSV空间，并将当前图像整幅都作为搜索范围。

2）设定搜索窗口（SearchWindow）大小与位置的初始值并计算窗口内的色度（Hue）分量概率分布直方图。

3）对当前图像的每一个像素采用其颜色的概率值进行替换，从而得到颜色概率分布图。

4）在颜色概率分布图中选取搜索窗。

5）计算零阶矩：

计算一阶矩：

计算搜索窗的质心：

6）调整搜索窗大小，窗口宽度为；长度为1.2w。

7）将SearchWindow的中心移动到质心位置，当移动距离超过了设定的阈值时，则跳转到步骤5），当SearchWindow的中心与质心间的距离小于一个预设值或者迭代次数达到最大时，停止计算。

8）在下一帧输入的图像中用上一步中的结果再一次计算搜索窗口的参数，然后跳转到步骤2）继续目标搜索。

1.2 随机Hough圆变换介绍

Hough变换是一种在图像中寻找直线、圆以及其他简单形状的方法。其基本思想是将原始图像中的曲线或者直线检测问题转变成在参数空间中聚类求峰值问题。由于圆形包含3个自由参数，需要在三维空间中投票求峰值，其计算量很大且对内存消耗大，算法运算时间长。因此XU等人提出了随机Hough变换（Randomized Hough Transform，RHT），使用了3个新的操作机制，即在图像空间中的随机抽样、参数空间中的动态链接列表以及连接图像空间和参数空间的收敛映射，从而加快了运算速度和提高了内存的利用率。然而随机采样会引入大量的无效累积和无效采样，在处理复杂背景和较大图像时对算法识别性能有较大的影响。因此有学者提出了改进的RHT算法，但不可否认的是在处理背景简单尤其是小图像的识别时，随机Hough变换运算速度很快，识别精度高。

1.3 基于CamShift与RHT的球体跟踪方法

由于CamShift算法是运用物体颜色信息和聚类的方式跟踪视频序列中的运动目标，因此算法具有较高的执行效率。而在双目移动机器人运用视差法计算球体目标三维坐标时，需要输入球体在图像中的二维坐标位置，二维坐标位置的误差过大会影响目标的定位及机器人姿态的调整。但是仅仅依靠CamShift算法返回的搜索区域的质心无法较精确的识别圆形目标的圆心及半径，考虑针对小图像运用随机Hough圆变换的具有高识别精度和运算速度快的特点，因此将CamShift和RHT两种算法结合并运用在简单的室内环境下对球形目标的跟踪上。在前文阐述的CamShift算法步骤中，步骤5）、6）、7）其实就是MeanShift算法的主要步骤，则CamShift与RHT结合的球体跟踪识别方法主要步骤表述如下。

1）确定初始目标的位置及区域并计算目标的H分量直方图。

2）利用直方图计算反向投影图。

3）采用MeanShift算法在上一步的反向投影图中进行迭代搜索，当计算结果收敛或达到最大迭代次数时停止计算。

4）利用MeanShift算法返回的搜索窗口的中心位置，取输入帧图像在周围的局部图像保存为子图像（SubImage），子图像的高度（subheight）和宽度度（subwidth）与搜索窗的宽度和长度相等。

采用随机Hough圆变换对SubImage进行圆形特征检测。

在子图像中若识别出圆形特征则返回其在原始图像当中的位置，假设子图像中圆心坐标为，原始图像中的圆心位置由如下坐标变换公式求得：

5）将步骤3）中获得的新的搜索窗口参数带入到步骤2）中，继续下一帧图像的目标位置搜索。endprint

2 实验结果与分析

本实验是在配置为Intel酷睿双核i5-2450M（2.5GHz）内存为1G的计算机上用Visual Studio 2010编程实现的。

所用移动机器人为自搭的简易四轮全自主移动机器人，摄像头为百脑通高清网络摄像头。

图1所示为移动机器人跟踪移动乒乓球在不同位置的四幅图像，图像大小均为640×480像素。表1是四幅跟踪图像中乒乓球的图像像素坐标位置。由图1和表1可知本文算法运用在移动机器人上能够对简单室内环境中的球体进行跟踪识别，识别精度高。

表1 移动乒乓球球心图像像位置

图像 a b c d

圆心坐标 （328，377） （304，379） （239，377） （347，409）

图2为只采用随机Hough变换对同样一张图像的检测结果，图3为用CamShift算法结合Hough变换识别小球的图像。由图2和图3可知仅采用随机Hough变换对球形物体跟踪会引入大量无效累积，且对背景稍微复杂的图像检测效果不理想。而用本文提出的球体检测算法可以达到比较好的检测效果。

图2 仅用随机Hough变换检测结果 图3 本文算法检测结果

3 结束语

本文研究了CamShift算法与随机Hough圆变换的主要原理，融合了两种算法的优点，提出一种基于CamShift算法与随机Hough圆变换结合的算法来跟踪识别球形目标的方法。在室内运动球体的跟踪实验中，此方法运行效果良好，跟踪识别精度高，实时性强。但还存在对于有颜色干扰和稍复杂的背景下跟踪效果不够理想，这还需在后续研究中进一步改进和完善。

参考文献

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]刘延杰，赖日飞，等.基于改进随机Hough变换的快速中心检测方法[J].纳米技术与精密工程，2011，9（4）：298-304.

[5]付琰，卢荣胜，等.基于重要性采样的随机Hough变换圆检测算法[J]. 电子测量技术，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者简介

张晨（1991-），男，江苏泰州人，大学本科生，机械电子工程专业。

通信作者：王红茹（1979-），女，河南南阳人，讲师，博士，研究方向：智能机器人技术。endprint

2 实验结果与分析

本实验是在配置为Intel酷睿双核i5-2450M（2.5GHz）内存为1G的计算机上用Visual Studio 2010编程实现的。

所用移动机器人为自搭的简易四轮全自主移动机器人，摄像头为百脑通高清网络摄像头。

图1所示为移动机器人跟踪移动乒乓球在不同位置的四幅图像，图像大小均为640×480像素。表1是四幅跟踪图像中乒乓球的图像像素坐标位置。由图1和表1可知本文算法运用在移动机器人上能够对简单室内环境中的球体进行跟踪识别，识别精度高。

表1 移动乒乓球球心图像像位置

图像 a b c d

圆心坐标 （328，377） （304，379） （239，377） （347，409）

图2为只采用随机Hough变换对同样一张图像的检测结果，图3为用CamShift算法结合Hough变换识别小球的图像。由图2和图3可知仅采用随机Hough变换对球形物体跟踪会引入大量无效累积，且对背景稍微复杂的图像检测效果不理想。而用本文提出的球体检测算法可以达到比较好的检测效果。

图2 仅用随机Hough变换检测结果 图3 本文算法检测结果

3 结束语

本文研究了CamShift算法与随机Hough圆变换的主要原理，融合了两种算法的优点，提出一种基于CamShift算法与随机Hough圆变换结合的算法来跟踪识别球形目标的方法。在室内运动球体的跟踪实验中，此方法运行效果良好，跟踪识别精度高，实时性强。但还存在对于有颜色干扰和稍复杂的背景下跟踪效果不够理想，这还需在后续研究中进一步改进和完善。

参考文献

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]刘延杰，赖日飞，等.基于改进随机Hough变换的快速中心检测方法[J].纳米技术与精密工程，2011，9（4）：298-304.

[5]付琰，卢荣胜，等.基于重要性采样的随机Hough变换圆检测算法[J]. 电子测量技术，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者简介

张晨（1991-），男，江苏泰州人，大学本科生，机械电子工程专业。

通信作者：王红茹（1979-），女，河南南阳人，讲师，博士，研究方向：智能机器人技术。endprint

2 实验结果与分析

本实验是在配置为Intel酷睿双核i5-2450M（2.5GHz）内存为1G的计算机上用Visual Studio 2010编程实现的。

所用移动机器人为自搭的简易四轮全自主移动机器人，摄像头为百脑通高清网络摄像头。

图1所示为移动机器人跟踪移动乒乓球在不同位置的四幅图像，图像大小均为640×480像素。表1是四幅跟踪图像中乒乓球的图像像素坐标位置。由图1和表1可知本文算法运用在移动机器人上能够对简单室内环境中的球体进行跟踪识别，识别精度高。

表1 移动乒乓球球心图像像位置

图像 a b c d

圆心坐标 （328，377） （304，379） （239，377） （347，409）

图2为只采用随机Hough变换对同样一张图像的检测结果，图3为用CamShift算法结合Hough变换识别小球的图像。由图2和图3可知仅采用随机Hough变换对球形物体跟踪会引入大量无效累积，且对背景稍微复杂的图像检测效果不理想。而用本文提出的球体检测算法可以达到比较好的检测效果。

图2 仅用随机Hough变换检测结果 图3 本文算法检测结果

3 结束语

本文研究了CamShift算法与随机Hough圆变换的主要原理，融合了两种算法的优点，提出一种基于CamShift算法与随机Hough圆变换结合的算法来跟踪识别球形目标的方法。在室内运动球体的跟踪实验中，此方法运行效果良好，跟踪识别精度高，实时性强。但还存在对于有颜色干扰和稍复杂的背景下跟踪效果不够理想，这还需在后续研究中进一步改进和完善。

参考文献

[1]Gary R B. Real time face and object tracking as a component of a perceptual user interface[A]. Proceedings of 4th Workshop on Applications of Computer Vision[C]. Princeton， USE： IEEE， 1998： 214-219.

[2]Cheng Yizong. MeanShift mode seeking and clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence， 1995， 17（8）： 790-799.

[3]XU L， OJA E. A new curve detection method： Randomized Hough Transform（RHT）[J]. Pattern Recognition Letters，1990， 11（5）： 331-338.

[4]刘延杰，赖日飞，等.基于改进随机Hough变换的快速中心检测方法[J].纳米技术与精密工程，2011，9（4）：298-304.

[5]付琰，卢荣胜，等.基于重要性采样的随机Hough变换圆检测算法[J]. 电子测量技术，2012，35（5）：45-48.

[6]Christoper Hollit. A convolution approach to the circle Hough transform for arbitrary radius[J].Machine Vision and Applications， 2013，24（4）：683-694.

作者简介

张晨（1991-），男，江苏泰州人，大学本科生，机械电子工程专业。

通信作者：王红茹（1979-），女，河南南阳人，讲师，博士，研究方向：智能机器人技术。endprint