基于RTH原理的图形检测

1引言通过对随机霍夫变换文献的学习，了解了随机霍夫变换的原理及其应用，本次作业基于随机霍夫变换的原理检测所给图像中的圆形元素。基于VS平台及OPENCV库函数，编写了相应的检测程序。实验后证明，程序能够检测出简单图像中圆形元素。2随机霍夫变换的基本思想随机霍夫变换（RHT）的基本思想是通过传统的霍夫变换(HT)思想所启发得到的。现以检测直线为例，一直线在直角坐标系中表示为：12yx------------------------------（1a）传统的HT将点空间11(,)xy转换为以斜率1，截距2为参数的空间12(,)。然而我们发现我们通过两个点（1x,1y）及（2x,2y）便能将直线描绘出来。RHT的算法思想是这样的：（1）将所有前景点设为域D，D存放每个前景点的坐标(,)xy，设一参数域P，P存放直线的斜率K及截距A，以向量(,)KA表示。再设参数N,表示P域中每个元素被命中的次数。（2）在D中随机抽取一点111=(,)dxy，再在剩余的点中随机抽取一点222=(,)dxy，其中12dd。通过计算可得11(,)KA，在域P中寻找是否存在iP11(,)KA，若存在则iP对应的iN加一。若不存在，则在域P中添加iP11(,)KA，其所对应的iN设置为1。（3）重复步骤2，我们可以在域P中寻找到命中次数较大的元素iP，则iP即为我们所要求的直线。本作业采用VC++6.0完成3利用RHT检测圆的基本步骤及程序解释通过对RHT的基本思想的阐述，我们知道当我们要检测直线时，只要随机选取两个点便可得到直线的参数K及A。同样对于一个圆，令它的直角坐标方程为222()()xaybr-------------------------(1b)其参数有3个，分别为a，b，r。因此我们必须选取3个不共线的点来得到参数a，b，r。由于式（1b）为非线性方程，要求得a，b，r是比较困难的。现介绍一种容易实现的方法：首先我们在域D中随机选取3个不共线的点111=(,)dxy222(,)dxy333(,)dxy=求线段12dd的中垂线及13dd的中垂线。可表示为：12121212()22yyxxxxyxyy-------------(1c)13131313()22yyxxxxyxyy--------------(1d)式1c及式1d联立方程组可求的圆心坐标a，b。将11()xy，及求得的a，b带入式1b便可求的半径r。2.1圆检测的具体步骤(1).首先利用Canny算子提取待检测的图像的边缘，得到一幅二值图像。然后扫描二值图像，寻找到前景点（像素值为255），将前景点的坐标存入到int型数组中，记为D。并记录前景点个数，记Dcount。(2).定义结构体P，成员函数为intX,YfloatR，记作圆心坐标及半径；intlie[1000]用来存放圆所对应在D上的点；intpcount记作点的个数；structP*基于RTH原理的图形检测陆源南京理工大学自动化学院,南京210094E-mail:[e-mail]摘要:图像的曲线检测是计算机视觉基本任务之一，目前霍夫变换是曲线检测的最为广泛应用的方法，本次作业将采用基于传统的霍夫变换而提出的新的方法——随机霍夫变换。随机霍夫变换解决了传统的霍夫变换内存开销大，运行时间长的缺点，而且具有较高的精度。本次作业将检测所给图像中的圆，经实验证明，采用随机变换原理，可以得到较好的结果。关键词:随机霍夫变换检测圆next记指向下个元素的指针。程序将使用链表数据结构来存放P中的数据。(3).利用rand()函数，在D中随机取3个不共线的点别记做111=(,)dxy,222(,)dxy,333(,)dxy=，计算圆心(,)dxy及半径r。在P中寻找元素iP，令id、iR为iP的圆心及半径，设置阈值1及2，若1idd且2irR，则表示找到iP，到步骤4。否则即未找到，到步骤5。(4).iP中的成员pcount加一。并将1d2d3d对应在D中的位置存放入iP中的lie数组中。设置pcount的最大值为max，若pcountmax,则到步骤3，否则到步骤6。(5).在P链表中插入新元素iP，为iP中的各成员赋予步骤3所的圆心坐标及半径，并将1d2d3d对应在D中的位置存放入iP中的lie数组中。Pcount初始为一。到步骤3。(6).我们认为iP为可能存在的圆的参数，计算iP成员lie数组中记录点的个数N（不算重复点）设置最小个数min，若Nmin，则认为是假圆，置iP中的pcount为0，到步骤3。若N=min，则认为是真圆，并将D中对应iP的lie数组的点移除。将iP保存起来，并将iP从链表结构中移除。到步骤3，继续检测其他圆。2.2相关程序解释(1)图像的转换及边缘提取cvCvtColor(Img,Img1,CV_BGR2GRAY);将图像转换为灰度图像，Img-Img1cvSmooth(Img1,Img1,CV_BLUR,3,3,0);将图像进行平滑，Img1-Img1cvCanny(Img1,Img2,a,3*a,3);从Img1提取边缘图像到Img2,Img1-Img2(2)随机取三个不共线的点(3)圆的检测对随机取的三个点计算其圆心坐标及半径判断head是否为0对head指针所指的元素赋值从head开始寻找是否有符合的元素否Pi-pcount++记录三点在D中的位置pcountmin?否在链表中添加新元素，并对起赋值是lie数组中点的个数Nmax?是否检测出圆的参数Pi，并保存是在链表中移除Pi,并在D中移除相应的点否for(i=0;i3;i++)进行3次循环随机取一点放入point[i]中判断point[i]是否已取是判断是否共线是4实验结果对所给图形circle进行圆形检测结果如下：5结论使用RHT的圆形检测方法，解决了传统的HT所带来的高内存消耗及运行时间长的问题，并且有着较好的精度，能够得到较好的实验结果。参考文献(References)[1]LeiXu,ErkkiOJAandPekkaKULTANEN.Anewcurvedetectionmethod:RandomizedHoughTransform,LappeenrantaUniversityofTechnology,DepartmentofInformationTechnologyBox20,53851Lappeenranta,Finland[2]刘瑞祯,于仕琪.OpenCV教程基础篇,北京航空航天大学出版社,20076.