hough变换.doc

什么是hough变换Hough变换利用图像空间和Hough参数空间的点线对偶性，把图像空间中的检测问题转换到参数空间。通过在参数空间里进行简单的累加统计，然后在Hough参数空间寻找累加器峰值的方法检测直线。例如，图1(a)中的九条线段对应于如图1(b)所示的其Hough参数空间的九个累加器峰值。图1(b)中，Hough参数空间的横纵坐标分别为直线极坐标方程:xcos() + ysin() 的两个参数和。九个峰值的和值唯一的确定其对应线段所在直线的两个参数。并且线段的长度决定坐标(,)处的累加值的大小。应用领域理论与实践向来是形影不离，相辅相成，Hough变换之所以有如此长足的发展，主要原因还是在于实践应用上的广泛需求；而在实践中所暴露出的不足又进而促进了它的发展，循环往复，就如同生命的演化。现枚举其主要应用领域如下： 生物医学Hough变换已被成功应用于基于人工智能的专家诊断系统；X射线人体照片和CT图像的处理和判读；光学显微镜和电子显微镜中的细胞核自动分析系统；从超声波诊断中提取三维动脉特征，等等。 自动化、机器人视觉Hough变换已被用于产品部件的自动监视、缺陷诊断、生产过程的自动监控、计算机辅助制造（CAM）等。例如基于Hough变换的机械零件检测和定位系统；基于Hough变换采用直线、圆弧等作为基本特征的工业产品检查系统。 空间技术、军事防御Hough变换已被用于运动目标轨迹的检测与识别，高空侦察机、间谍卫星和军事雷达等目标自动识别系统的特征提取。例如应用Hough变换对战斗机的外形特征进行提取和自动识别；应用Hough变换辅以信号检测理论解决并行多运动目标的跟踪问题。 办公自动化Hough变换在许多应用系统中得到了很好的应用。例如采用Hough变换进行英文字符特征提取并自动识别，其对印刷体字符识别率为99.6%，对手写体字符的平均识别率也达到了86.9%，并已成功应用于邮政信件的自动分拣、文件处理等。 由以上分析可见，Hough变换有着广泛的关注程度以及良好的应用前景。在计算机视觉和自动目标识别系统中，Hough变换是一个用于边缘线条特征提取的强有力工具。基本原理Hough变换是图像处理中从图像中识别几何形状的基本方法之一，即它可以检测已知形状的目标，而且受噪声和曲线间断的影响小。Hough变换的基本思想是利用点-线的对偶性。如下图1所示： 从图1中可看出，x-y坐标和k-b坐标有点-线的对偶性。x-y坐标中的点P1、P2对应于k-b坐标中的L1、L2；而k-b坐标中的点P0对应于x-y坐标中的线L0 。由于x-y坐标中的垂直线的k值为无穷大，给计算带来不便，故使用点-正弦曲线对偶变换解决这一问题。直角坐标X-Y中的一点(x,y)，经过点-正弦曲线对偶变换： p = x * cos(a) + y * sin(a)在极坐标a-p中变为一条正弦曲线，a取(0-180)。可以证明，直角坐标X-Y中直线上的点经过Hough变换后，它们的正弦曲线在极坐标a-p有一个公共交点，如图2所示。 也就是说，极坐标a-p上的一点(a，p)，对应于直角坐标X-Y中的一条直线，而且它们是一一对应的。为了检测出直角坐标X-Y中由点所构成的直线，可以将极坐标a-p量化成许多小格。根据直角坐标中每个点的坐标(x,y)，在a = 0-180内以小格的步长计算各个p值，所得值落在某个小格内，便使该小格的累加记数器加1。当直角坐标中全部的点都变换后，对小格进行检验，计数值最大的小格，其(a，p)值对应于直角坐标中所求直线。（摘自图像处理技术：直线检测 Lipton,2002.05）Hough变换原理&Hough检测直线,圆,椭圆的部分代码 一、简单介绍Hough变换是图像处理中从图像中识别几何形状的基本方法之一。Hough变换的基本原理在于利用点与线的对偶性，将原始图像空间的给定的曲线通过曲线表达形式变为参数空间的一个点。这样就把原始图像中给定曲线的检测问题转化为寻找参数空间中的峰值问题。也即把检测整体特性转化为检测局部特性。比如直线、椭圆、圆、弧线等。二、Hough变换的基本思想设已知一黑白图像上画了一条直线，要求出这条直线所在的位置。我们知道，直线的方程可以用y=k*x+b 来表示，其中k和b是参数，分别是斜率和截距。过某一点(x0,y0)的所有直线的参数都会满足方程y0=kx0+b。即点(x0,y0)确定了一族直线。方程y0=kx0+b在参数k-b平面上是一条直线，(你也可以是方程b=-x0*k+y0对应的直线)。这样，图像x-y平面上的一个前景像素点就对应到参数平面上的一条直线。我们举个例子说明解决前面那个问题的原理。设图像上的直线是y=x, 我们先取上面的三个点：A(0,0), B(1,1), C(22)。可以求出，过A点的直线的参数要满足方程b=0, 过B点的直线的参数要满足方程1=k+b, 过C点的直线的参数要满足方程2=2k+b, 这三个方程就对应着参数平面上的三条直线，而这三条直线会相交于一点(k=1,b=0)。同理，原图像上直线y=x上的其它点(如(3,3),(4,4)等)对应参数平面上的直线也会通过点(k=1,b=0)。这个性质就为我们解决问题提供了方法，就是把图像平面上的点对应到参数平面上的线，最后通过统计特性来解决问题。假如图像平面上有两条直线，那么最终在参数平面上就会看到两个峰值点，依此类推。简而言之，Hough变换思想为：在原始图像坐标系下的一个点对应了参数坐标系中的一条直线，同样参数坐标系的一条直线对应了原始坐标系下的一个点，然后，原始坐标系下呈现直线的所有点，它们的斜率和截距是相同的，所以它们在参数坐标系下对应于同一个点。这样在将原始坐标系下的各个点投影到参数坐标系下之后，看参数坐标系下有没有聚集点，这样的聚集点就对应了原始坐标系下的直线。在实际应用中，y=k*x+b形式的直线方程没有办法表示x=c形式的直线(这时候，直线的斜率为无穷大)。所以实际应用中，是采用参数方程p=x*cos(theta)+y*sin(theta)。这样，图像平面上的一个点就对应到参数p-theta平面上的一条曲线上，其它的还是一样。三、Hough变换推广1、已知半径的圆 其实Hough变换可以检测任意的已知表达形式的曲线，关键是看其参数空间的选择，参数空间的选择可以根据它的表达形式而定。比如圆的表达形式为 ，所以当检测某一半径的圆的时候，可以选择与原图像空间同样的空间作为参数空间。那么圆图像空间中的一个圆对应了参数空间中的一个点，参数空间中的一个点对应了图像空间中的一个圆，圆图像空间中在同一个圆上的点，它们的参数相同即a，b相同，那么它们在参数空间中的对应的圆就会过同一个点（a，b），所以，将原图像空间中的所有点变换到参数空间后，根据参数空间中点的聚集程度就可以判断出图像空间中有没有近似于圆的图形。如果有的话，这个参数就是圆的参数。2、未知半径的圆 对于圆的半径未知的情况下，可以看作是有三个参数的圆的检测，中心和半径。这个时候原理仍然相同，只是参数空间的维数升高，计算量增大。图像空间中的任意一个点都对应了参数空间中的一簇圆曲线。 ，其实是一个圆锥型。参数空间中的任意一个点对应了图像空间中的一个圆。3、椭圆椭圆有5个自由参数，所以它的参数空间是5维的，因此他的计算量非常大，所以提出了许多的改进算法。四、总结 图像空间中的在同一个圆，直线，椭圆上的点，每一个点都对应了参数空间中的一个图形，在图像空间中这些点都满足它们的方程这一个条件，所以这些点，每个投影后得到的图像都会经过这个参数空间中的点。也就是在参数空间中它们会相交于一点。所以，当参数空间中的这个相交点的越大的话，那么说明元图像空间中满足这个参数的图形越饱满。越象我们要检测的东西。 Hough变换能够查找任意的曲线，只要你给定它的方程。Hough变换在检验已知形状的目标方面具有受曲线间断影响小和不受图形旋转的影响的优点，即使目标有稍许缺损或污染也能被正确识别。1.hough检测直线typedef struct MAXVALUEint iDist;int iAngle;int iMax;MAXVALUE;/* 检测直线*/void TraceBeeline(int ImageWidth,int ImageHeight,LPBYTE lpSrc,LPBYTE lpDest,int len)/ #define pi 3.1415927int iMaxAngle = 90;int iAngleNumber = 0;/最大值MAXVALUE MaxValue1;memset(&MaxValue1,0,sizeof(MAXVALUE);/循环变量int i;int j;int off = 0;int iMaxDistance = 0,iDistance = 0;iMaxDistance = (int)sqrt(ImageWidth * ImageWidth + ImageHeight * ImageHeight);int *lpTrans = new intiMaxDistance * iMaxAngle;memset(lpTrans,0,iMaxDistance * iMaxAngle * sizeof(int); /去掉孤立点 for(j=1,off=0;jImageHeight-1;j+) for(i=1;iImageWidth-1;i+,off) if(1=lpSrcoff) if(lpSrcoff-1=0&lpSrcoff+1=0&lpSrcoff-ImageWidth=0&lpSrcoff+ImageWidth=0 / lpSrcoff-ImageWidth-1=0&lpSrcoff-ImageWidth+1=0&lpSrcoff+ImageWidth-1=0&lpSrcoff+ImageWidth+1=0) lpSrcoff=0; /for(j=0;jImageHeight;j+) for(i=0;iImageWidth;i+) off = j * ImageWidth + i; if(1=lpSrcoff) for(iAngleNumber=0;iAngleNumber=0&iDistanceiMaxDistance) lpTransiDistance * iMaxAngle + iAngleNumber+; /找到最大值 for(i = 0;i iMaxDistance;i+) for(iAngleNumber=0;iAngleNumberMaxValue1.iMax) MaxValue1.iMax = (int)lpTransi * iMaxAngle + iAngleNumber; MaxValue1.iAngle = iAngleNumber; MaxValue1.iDist = i; / for(j=0;jImageHeight;j+) for(i=0;i(R.bottom - R.top)?(R.bottom - R.top):(R.right - R.left); int memsize = (int)(minrr+2*firstBase) * secendBase *secendBase;BYTE * lpabr = new BYTEmemsize;memset(lpabr,0,sizeof(BYTE)*memsize);int maxcount = -1;/* 局部hough变换检测圆曲线段的一部分*/for(k=0;kptNumber;k+=pos) for(aa=(int)(R.left+R.right)/2 - firstBase;aa=(int)(R.left+R.right)/2 + firstBase;aa+) if(aaImageWidth) break; for(bb=(int)(R.top+R.bottom)/2 -firstBase;bb=(int)(R.top+R.bottom)/2 + firstBase;bb+) if(bbImageHeight) break; temp1 = (ptk.x-aa)*(ptk.x-aa) + (ptk.y-bb)*(ptk.y-bb); rr = (int)sqrt(temp1); if(rr=10&rr=(int)(minrr/2) + firstBase) lpabrrr*secendBase*secendBase+(aa-aaBase)*secendBase+(bb-bbBase)+; for(rr=10;rr=(int)(minrr/2) + firstBase;rr+) for(aa=(int)(R.left+R.right)/2 - firstBase;aa=(int)(R.left+R.right)/2 + firstBase;aa+) if(aaImageWidth) break; for(bb=(int)(R.top+R.bottom)/2 - firstBase;bb=(int)(R.top+R.bottom)/2 + firstBase;bb+) if(bbImageHeight) break; if(maxcount=4)/记录保存中心,半经 saverr = rr; saveaa = aa; savebb = bb;3.hough变换检测椭圆的程序一个MATLAB程序，有些地方你自己修改以下就可以了。row col=size(fedge);minofa=a;maxofa=round(row/2);minofy0=round(col/2)-30;maxofy0=round(col/2)+30;minofb=round(col/2)-60;maxofb=round(col/2);maxofx=round(row/2);scalor=4;H=zeros(floor(maxofa-minofa)/scalor)+1,floor(maxofa-minofa)/scalor)+1,.floor(maxofy0-minofy0)/scalor)+1,floor(maxofb-minofb)/scalor)+1);for x=1:maxofxfor y=1:coltemp=fedge(x,y);if temp=255for a=minofa:scalor:maxofafor x0=a:scalor:maxofafor b=minofb:scalor:maxofbfor y0=minofy0:scalor:maxofy0temp=(y-y0)/b)2+(x-x0)/a)2;if abs(temp-1)=0.01xtemp=floor(x0-minofa)/scalor)+1;atemp=floor(a-minofa)/scalor)+1;ytemp=floor(y0-minofy0)/scalor)+1;btemp=floor(b-minofb)/scalor)+1;H(xtemp,atemp,ytemp,btemp)=H(xtemp,atemp,ytemp,btemp)+1;endendendendendendendendmaxofH=max(max(max(max(H);for i=1:floor(maxofa-minofa)/scalor)+1for j=1:floor(maxofa-minofa)/scalor)+1for m=1:floor(maxofy0-minofy0)/scalor)+1for n=1:floor(maxofb-minofb)/scalor)+1temp=H(i,j,m,n);if temp=maxofHxtemp=i;atemp=j;ytemp=m;btemp=n;break;endendendendendx0=(xtemp-1)*scalor+minofa;a=(atemp-1)*scalor+minofa;y0=(ytemp-1)*scalor+minofy0;b=(btemp-1)*scalor+minofb;figure;imshow(fedge,);hold on;plot(y0,x0,r+);t=0:pi/180:2*pi;plot(y0+b*sin(t),x0+a*cos(t),r-);hold off; void CImageCompressView:DoHough() int temp=0; for(int i=0;itheApp.ROW-1;i+) for(int j=0;jtheApp.COL-1;j+)/取每个象素 temp=theApp.iImageDataTempij; int value9;/存入当前3*3窗口内的象素 GetPixelValueEx(value,i,j); long t=0,t1=0; for(int k=0;k4;k+) for(int m=0;mt) t=t1; if(tm_iValve) theApp.iIma