第五章 目标分 （Shape Analysis）.ppt

2002, Ver1.0 任明武，南京理工大学计算机系 第五章 目标分析 (Shape Analysis) 问题：(1)问图象中有几类目标，几个目标。 (2)问面积大于S的有几类目标，几个目标。 (3问满足一定形状的有几个目标。 诸如此类的问题都需要用到连通性分析和形状分析。 2002, Ver1.0 任明武，南京理工大学计算机系 * 2002, Ver1.0 任明武，南京理工大学计算机系 * 5.1 霍夫变换(Hough Transform) 5.1.1线条检测(Line Detection) 1.思想： 统计学生的众数….。 2.Hough变换：从区域的边界(空间域)到参数空间的变换，用大多数边界点(众数)满足的对应的参数来描述区域的边界。 3.(k,b)空间：如果知道很多 个边缘点(x0 ,y0)……( xn , yn )，检测其中是否有直线。假设有直线且该直线的方程为y =kx +b ，则有: y0 =kx0 +b ,y1=kx1 +b,……,yn=kxn +b同时满足。若构造一个计数器 count[k][b]；则有 count[k][b]=n+1。现在的情况是：求 k，b 和多少个点落到该直线 y=k x+b上。 for (k = k1; k k2; k++ ) for ( b = b1; b b2; b++ ) { for ( i= 0; i n+1; i ++) if ( yi = k*xi +b ) count[k][b]++; } 因此，寻找count中的最大值，则该最大值对应的(k,b)即为所求。 4.(ρ,θ)空间: 在直角坐标系XOY中，任一直线L均可由参数空间(ρ,θ)中的一个点(ρ’，θ’)来表示，ρ’是原点到直线L的距离，θ’是X轴与直线L的法线间的夹角。即y=kx + b 变成求 x*cosθ’+y*sinθ’ = ρ’。即：给定一个（ ρ’，θ’），则唯一确定一条直线。算法如下： for (ρ=ρ1;ρ=ρ2;ρ+=stepρ) for(θ=θ1;θ=θ2;θ+=stepθ) { for(i=0;i=n;i++) if(ρ==xi*cos(θ)+yi*sin(θ)) count[ρ][θ]++; } 问题： (1) for(θ=θ1;θ=θ2;θ+=stepθ) for(i=0;i=n;i++) { ρ==xi*cos(θ)+yi*sin(θ); count[ρ][θ]++; } (2)cos (θ)和sin(θ)变成查找表cos[θ]和sin[θ]。 (3)ρ和θ的定义域的确定。 (4)坐标原点的选择。 (5)精确性取决于stepρ和stepθ，显然它们越小，精确度越高。 但越小，count[ρ][θ]越不容易形成峰值。可先用Hough变换，再用直线拟和。 高效编程：直线的Hough变换： int cosV, sinV; for(theta = theta1; thetatheta2; theta+=step_theta) { cosV = cos(theta)*2048; sinV = sin(theta)*2048; for(i=0; in; i++) { thro = (x[i]*cosV + y[i] *sinV) 9; // 相当于除以512 ….. } } 望同学们好好思考该程序的优点。 二值图像 水平扫描:最左和最右 垂直扫描:最上和最下 并集 当并集有若干条直线时，则在count[ρ][θ]表现出有若干个极大值，从而可以检测出多条直线。 例：印签识别系统中的方章检测 在实际应用中，当被鉴印鉴仅有略微倾斜时，可仅使用最左点集合进行Hough变换求得印鉴的左边界，此时仅需要在count找一个最大值即可，而且由于中相邻的 点之间纵坐标是加1的关系，可以简化计算。同理，可以求右边界、上边界和下边界。 5.1.2圆检测(Circle Detection) 圆的Hough变换：(x – a)2 + (y – b)2 = R。对(a,b,R)的求解，若用穷举法，则需要三重循环，则速度慢。所以实际应用中常根据被处理对象的具体特征，来设计不同的简化算法。 例：印签识别系统中的圆章检测 由于被鉴印鉴图像中只有一枚印鉴，在理想情况下，当逐行扫描图像时，在每一行中