基于随机Hough变换的圆形目标检测实验
2014-02-10程宇龙
张 佳， 程宇龙
(北京理工大学 自动化学院，北京 100081)
0 引 言
实验教学是高等院校教育教学过程的重要组成部分，也是创新教育最为重要的基础[1]。目前，高校实验教学的一个重要发展方向就是开设综合性设计实验，以培养学生分析问题的能力[2]。
1 REVS-50M小型光电跟踪系统
REVS-50M小型光电跟踪系统是一个开放的实验平台，其中结合了图像处理[3]、自动控制[4]以及智能控制[5]相关的各项技术。该实验系统通过对一个三自由度的黑色圆形移动靶标进行图像处理，采用自动控制或智能控制的方法实现转台对靶标的实时跟踪。在目标检测部分，原实验系统采用的是颜色阈值[6-7]的方法检测手动靶标，当检测过程中有相近颜色的人或物体进入图像检测区域时会引起误跟踪[8]。改用常规的Hough变换检测靶标形状的方法能够达到检测要求，并能避免误跟踪的问题。然而常规Hough变换[9-10]的计算量大、精确度不高，并且无法排除噪声点的干扰。为了克服这些缺点，本实验引导学生采用随机Hough变换及其改进方法进行靶标的检测，得到了比较满意的实验结果。
本实验系统的图像处理和控制部分从整体上看由计算机、电控箱以及伺服转台组成。计算机主要负责系统软件部分的代码编写工作与系统的控制操作。计算机通过PCI总线连接至运动控制器、图像采集卡与多串口卡，并通过数据线与电机驱动器、相机和激光测距仪，从而分别实现电机驱动器的控制、图像采集与显示以及距离和跟踪信息的获取与反馈。其具体控制结构图如图1所示。
图1 光电跟踪系统组成
图2所示的手动靶标，是一个三轴运动平台，用于模拟目标的位置及速度的变化。
图2 手动靶标
2 常规Hough变换圆检测
Hough变换利用目标的形状特征而非颜色特征来进行检测，可以避免由于颜色相近所引起的误跟踪。
计算机所获取的靶标原始图像如图3(a)所示。首先用Canny算子对原始图像进行图像分割处理[11]，得到图3(b)中的边缘图像，再对此图像进行Hough变换得到如图3(c)中的结果。
由此可见，采用常规Hough变换能够检测到圆形手动靶标，但常规Hough变换的图像空间到参数空间的映射是一到多的映射，计算量大，需要占用大量内存空间，并且受到参数空间离散化的严重影响，精确度不高。另外这种方法对所有特征点进行平等投票，无法排除噪声点的干扰，如背景更复杂就不能达到很好的效果。
(a)
(b)(c)
图3 常规Hough变换圆检测结果
3 随机Hough变换圆检测
为了克服常规Hough变换检测时的缺陷，实验决定改用随机Hough变换[12、13]。随机Hough变换随机选取边缘点不集中在同一条直线上的3个点，计算出对应的圆的参数并将其映射到参数空间一个点，将原来的一到多的映射变为多到一的映射，省去了许多计算量。同时，随机Hough变换采用了动态链表结构，只对有效参数单元进行累计，大大减轻了内存的负担，节省大量内存空间。具体算法步骤如下[14]：
(1) 构造边缘点集D，初始化参数单元集P=NULL。
(2) 从D中随机选取3个点。
(3) 计算这3点所确定的圆参数p，若有解转(4)，否则转(7)。
(4) 从P中找一个pc满足‖p-pc‖≤δ，δ是容许误差，若找到了则转(6)，否则转(5)。
(5) 将p插入P中，令其值为1，转(7)。
(6) 将pc的值加1，若小于指定的阈值N0转2，否则转(7)。
(7)pc为候选圆的参数，若该参数对应的圆上的点数Value>minValue，则转(8)，否则为虚假圆，从P中去除pc然后转(2)。
(8) 检测到参数为pc的真实圆，提取圆心和边缘点，结束。
其中需要说明以下几点：
(a) 阈值N0的确定。在随机采样中，如果有2～3次计算出的圆参数相同或者相似，那么很有可能该圆就是要找的圆，又因为后面还会进一步验证候选圆是否为真圆，因此阈值N0取小一些即可，取大了不仅会增加计算量，也没有什么意义。一般取N0=3。
(b) 圆参数的求解。圆的任意两条弦的中垂线相交于圆心，可以利用此性质求解圆参数[]。假设随机选取到三点坐标为(x1,y1),(x2,y2),(x3,y3)，则可以得到两条弦的中垂线所在直线方程如下：
(1)
(2)
式(1)与式(2)联立可得圆心坐标(a,b)，从而由下式可求得半径r：
(3)
(c) 确认候选圆为真圆的方法。对图像中的边缘点，求它们到圆心的距离d，如果d近似等于半径r，即|d-r|<ε，则认为该边缘点在圆上。为了避免开平方运算，提高算法执行速度，将|d-r|<ε改写为下式，其中(xi,yi)为当前边缘点坐标，(a,b)为圆心坐标：
(r-ε)2<(xi-a)2+(yi-b)2<(r+ε)2
(4)
由于随机采样会取到大量无效的点，这些点经过计算得到的圆一定是虚假圆，却仍然将其插入参数空间链表，会造成大量的无效累积，增加了搜索时的难度和计算时间，严重时还会给真圆的定位带来困难。圆的个数越多，随机采样的3点落在同一圆上的概率就越小，导致无效累积增多。
4 随机Hough变换的改进
4.1 利用梯度信息减少无效累积
为了减少随机Hough变换时的无效累积，可以在计算圆参数之前先利用3个点的梯度信息计算判断这3点是否位于同一个圆上，如果3点不在同一个圆上，那么则继续随机选取3点，直到选到的3点位于同一个圆上才进行累积，这样便能节省许多计算和搜索链表的时间。
设当前像素点为A5(x0,y0)，图4给出了该点与其周围8邻域像素点的位置关系。
图4 当前像素A5和周围像素的位置关系
设A5点的梯度在x方向和y方向分别为Gx和Gy，其梯度方向角为θ，下面用Sobel边缘算子来计算梯度：
Gx=(A3+2A6+A9)-(A1+2A4+A7)
(5)
Gy=(A7+2A8+A9)-(A1+2A2+A3)
(6)
由此得过A5点沿梯度方向的斜率kt：
kt=tanθ=Gy/Gx
(7)
因此得到过A5且沿梯度方向的直线方程为：
y-y0=kt(x-x0)
(8)
设通过随机采样得到的3点为A，B，C，则对A，B和C通过上述方法分别计算出其所在沿梯度方向的直线方程LA、LB、LC，并联立LA，LB得交点坐标为(x,y)。如果该点到LC：y=Kx+B的距离D满足下式：
(9)
则认为该三点符合要求，从而继续计算其对应的圆的参数，在参数空间中进行搜索和累积。式(9)中的σ为考虑到图像的数字化误差而设置的容许误差。
4.2 判断候选圆为真圆时的改进算法
(1) 在验证候选圆上的点的时候，可以只靠虑位于该圆内切正方形和外接正方形之间的区域，位于此区域外的其他点可以不予考虑。因为候选圆上的点只可能位于这个区域内。这样，便可直接排除很多边缘点，节省了时间。
图5 候选圆的内切外接正方形示意图
如图5所示，只需验证位于阴影区域的点，计算边界坐标时，考虑到数字化误差，应留一个小余量δ。若圆心坐标为(a,b)，半径为r，得到如下方程：
(13)
因此要验证的边缘点坐标(x,y)应满足：
(14)
(2) 若尚未验证的点数为t，当前有效计数为Value1，只要出现t+Value1
5 实验结果及分析
图6中，(a)为原始图像，用Canny算子进行图像分割之后得到(b)，之后对其进行改进的随机Hough变换，得到(c)中的圆形，即完成了对黑色圆形靶标的检测，从(d)中可以看到白色十字架准确而稳定地定位在圆心位置。
(a)(b)(c)(d)
图6 随机Hough变换检测圆形的结果
表1中给出了常规Hough变换和改进的随机Hough变换两种算法的执行时间和圆半径的检测精度对比。
表1 两种方法比较
可以看出，改进的随机Hough变换能够更精确地检测出圆形移动靶标的位置，并且具有较好快速性。
6 结 语
本实验针对原小型光电跟踪系统在图像检测部分产生误跟踪的问题，设计了利用形状特征检测目标的实验。逐步引导学生采用Hough变换、随机Hough变换以及改进的随机Hough变换的方法对圆形进行检测，分析每种方法的优点及缺陷，从而引出一种更为合适的解决方法。在实验过程中，锻炼了学生分析问题、解决问题的能力，提高了学生的创新能力，获得了良好的教学效果。
[1] 郑蓓蓉. 改革实验教学 培养创新人才[J]. 中国高教研究，2002(2):87-88.
ZHENG Pei-rong. Reform experimental teaching and cultivate innovative talents[J]. China Higher Education Research, 2002(2):87-88.
[2] 何丽丽. 高校计算机专业综合性实验探索与研究[J]. 科技信息, 2011(15):13-13.
HE Li-li. Comprehensive experimental exploration and research of college computer science[J]. Science & Technology Information, 2011(15):13-13.
[3] 蒋 伟，杨庭庭，刘亚威,等. 数字图像处理研究性实验教学的改革与实践--基于分数阶偏微分的图像边缘检测[J]. 实验技术与管理, 2013,30(6): 124-128.
JIANG Wei, YANG Ting-ting, LIU Ya-wei,etal. Reform and practice of research-style experimental teaching by digital image processing: Image edge detection based on fractional-order partial differential[J]. Experimental Technology and Management, 2013, 30(6): 124-128.
[4] 孙 洁. “自动控制原理”实验教学改革的实践[J]. 电气电子教学学报, 2009, 31(6):69-70.
SUN Jie. Experimental teaching reform of automatic control theory[J]. Journal of Electrical & Electronic Education, 2009, 31(6):69-70.
[5] 罗 兵，甘俊英，张建民. 智能控制技术[M]．北京：清华大学出版社，2011.
[6] 李云红, 屈海涛. 数字图像处理[M]. 北京：北京大学出版社，2012.
[7] 张 培. 复杂背景下交通标志的颜色分割[D]. 武汉理工大学，2012.
[8] 张 佳，窦丽华，陈 杰. 基于光电跟踪系统的系列实验开发[J]. 实验室科学, 2012(6):40-43.
ZHANG Jia, DOU Li-hua, CHEN Jie. Development of serial experimental courses based on optical tracking system[J]. Laboratory Science, 2012(6):40-43.
[9] Hough PVC. Method and mean s for recognizing complex patterns: United States, 3069654[P]. 1962-12-18.
[10] 朱桂英，张瑞林. 基于Hough变换的圆检测方法[J]. 计算机工程与设计，2008，29(6):1462-1464.
ZHU Gui-ying, ZHANG Rui-lin. Circle detection using Hough transform[J]. Computer Engineering and Design, 2008，29(6):1462-1464.
[11] 焦玉斌，徐艳蕾，陈喜龙. 图像分割研究综述[J]. 科技创新导报, 2009(13):11-11.
JIAO Yu-bin, XU Yan-lei, CHEN Xi-long. Summary of image segmentation[J]. Science and Technology Innovation Herald, 2009(13):11-11.
[12] Xu L, Oja E, Kutanen P. A new curve detection method: randomized Hough transform(RHT)[J]. Pattern recognition letters, 1990, 11(5): 331-338.
[13] 陈燕新，戚飞虎. 基于随机Hough变换的快速圆检测方法[J]. 上海交通大学学报, 1998,32(10):17-20.
CHEN Yan-xin, Qi Fei-hu. Fast Circle Detection Using Randomized Hough Transform[J]. Journal of Shanghai Jiaotong University, 1998,32(10):17-20.
[14] Jiang L. Efficient randomized Hough transform for circle detection using novel probability sampling and feature points[J]. Optik-International Journal for Light and Electron Optics, 2012，123(20):1834-1840.
[15] 岳 健, 项学智. 一种改进的 Hough 圆检测算法[J]. 应用科技, 2006, 33(6): 74-76.
YUE Jian, XIANG Xue-zhi. An improved algorithm of hough circle detection[J]. Applied Science and Technology, 2006, 33(6): 74-76.
