2.6　形状检测

除边缘、角点外，基本的几何形状在计算机视觉中也是重要的监测对象。常见的包括直线、直线段、圆和椭圆等具有解析表达式的形状的检测。

2.6.1　标准Hough变换及圆形Hough变换

实际上，这些几何形状的检测往往在先前获得的边缘图像上进行，而由于在边缘检测中，噪声往往会使检测出来的边缘不连续，因此出现了几何形状，但是形状不连续。如何将这些具有标准几何形状的边缘点连接成标准的形状呢？如果通过对边缘点进行投票来确定哪些点是几何形状上的点，那么实现起来并不简单，故目前标准的做法是通过Hough变换来解决这个问题。

Hough变换最简单的情况就是检测直线。一般直线可以用下面的解析表达式表示

其中，参数a和b分别表示斜率和截距，两个参数共同确定一条直线，所有参数的集合（a,b）形成一个参数空间。注意，原方程既表示（x,y）平面的一条直线，又表示（a,b）平面内的一个点，形成了对偶关系，若（x,y）平面内有共线l的两点（x1,y1）和（x2,y2），则在参数空间中有两条相交的直线l1和l1，且其交点表示原直线的参数（al,bl）。但对于垂直线的表示则存在问题，即垂直线的表达式为x=c，这条直线无法用上面的方程表达。因此将参数空间采用极坐标来表示

其中，ρ表示原点到直线的距离，实际上就是原点到直线上最近点的距离，角度θ表示这条过原点与直线垂直的线与横轴的夹角。注意，一对（ρ,θ）就与一条直线相关联，这时（ρ,θ）形成参数空间，此时（a,b）平面内的一条直线就变换成（ρ,θ）平面内的一条曲线。

从图2.30可以看出，若任意给定图像平面直线上的一个点（x,y）则可以计算出相应的（ρ,θ），同一条直线上的所有点（x,y）所对应的（ρ,θ）都一样，因此我们可以根据这种性质来设计和检测直线的算法。

首先对原始图像进行边缘检测，然后设计一个称为累计器的二维阵列，分别表示（ρ,θ）的离散空间，一般可以设置ρ为图像的宽度与高度的最大值，角度θ的取值范围为（0,360°）。对图像的每个边缘像素点（xi,yi）和变化θ的值，求出对应的ρ值，然后在（ρ,θ）对应的二维矩阵中的对应位置加1。显然，即使边缘不连续，但只要在同一条直线上，对应的（ρ,θ）也会增加，从而通过对累计器求其局部极值来检测对应的直线。累计器中有多少个极值，就存在多少条直线。

同样，Hough变换也可以用来检测其他更复杂的形状对象，尤其是具有解析表达式的形状，此时称为广义Hough变换。例如，圆有对应的圆形Hough变换，此时包含圆心坐标和半径三个参数，可以表示为以点（a,b）为圆心，以r为半径，表达式为

其基本思想为：若以该圆上的任意一点为圆心，以r为半径画圆，则该圆必定经过圆心（a,b）。因此，图像中存在半径为r的圆，但经过边缘检测后，若其边界不连续，则这时以每个边缘像素为圆心画半径为r的圆，这些圆的交点必定是原圆的圆心，从而确定了原圆的圆心。

图2.31表示了圆心为O、半径为r的圆，边界上出现三个像素点（x1,y1）、（x2,y2）、（x3,y3），若以这些点为圆心，画半径为r的圆，则这些圆必在圆心O相交。在图像经过边缘检测后，在已知圆半径r的情况下，对每个像素做半径为r的圆，这与直线检测中的二维累计阵列类似，即对该圆通过的位置的值加1，故二维阵列中的局部极大值点就对应半径为r的圆的圆心。

而若在半径未知的情况下，则需要进一步假定半径的范围。在限定范围内，对所有可能的半径值进行遍历，然后设定阈值，对所有这些累计阵列取其局部极大值点，这样可检测出图像中的所有圆。

显然，半径的范围对算法性能的影响巨大，这时需要存储所有的累计矩阵的值，还可以通过选定网格的大小来减少计算量，但由于圆形物体的尺寸未知，因此可能会省略比网格尺寸还小的圆形。

在计算机视觉领域中，可以利用圆形的一些先验性质来减少计算量。例如，在航天器上利用标靶来对接，这时需要通过检测标靶来计算偏移量，进而对齐接口，若标靶上的目标是圆形，且预先知道尺寸，则可以利用这些信息来减少计算量。其次，处于圆上的边缘像素点具有类似的曲率信息，这时可以利用曲率信息来减少要计算的边缘像素点。例如，假设已经计算出边缘图以及相应的Ix,Iy,Ixx,Iyy,Ixy，则可以计算出局部方向和曲率k

然后统计曲率直方图，找出峰值对应的边缘点而舍弃其余的边缘点，这样就减少了计算量，从而加快了检测过程。

2.6.2　广义Hough变换

1981年，Ballard首先引入了广义Hough变换。通过模板匹配的方式使Hough不仅可以处理有解析式的形状，而且可以检测用模型描述的任意形状的对象。

首先对任意需要检测的形状通过建立R表来表示，选定待检测对象内部的一个点作为参考点（xr,yr）。然后对于任意边界点（xi,yi），连接参考点与边界点的距离用ri表示。在边界点处连接线与水平轴的夹角为αi，切线方向与水平轴夹角为φi。此时模板形状由边界点到参考点的距离，以及边界点的梯度方向完全确定。R表如表2.1所示，注意，表格第二列为参数的离散化形式，第三列中的每项对应一个边缘像素点。广义Hough变换原理如图2.32所示。

在进行对象检测时，同样使用称为二维累计阵列的Hough计数空间或者参数空间，边缘点根据其梯度方向和R表值在这个空间中对假设的参考点进行投票。图像中的对象等同于模板对象，则累计阵列中对应这个参考点的位置的元素值会获得最高投票数。理想上，其峰值就表示这个对象边界点的数目。

一旦要求形状检测具有旋转和尺度的不变性，这时就需要增加旋转和尺度两个参数，并相应地进行离散化，这里不再详细描述。请参考相关文献。

2.6.3　三种常见Hough变换的区别

目前，常见的Hough变换分为三种，分别是标准的Hough变换（SHT）、广义的Hough变换（GHT）和随机的Hough变换（RHT）。SHT和GHT显然都是一对多的映射，即每个边缘像素点对参数空间矩阵的很多位置都有贡献。但RHT变换从边缘像素的子集来进行处理，每次随机选取都对应同一个形状，这时是多对一的映射，如两个随机选取的像素可以定义一条直线。对于有n个参数的曲线形状，随机选取n个点来计算该曲线的n个参数。同时维持包括一个实值向量和整数投票值的动态累计矩阵。对于计算得到的参数集合，若在一定误差情况下匹配一个已有集合，则其投票值加一；否则新的参数集合计数值加一。最终从累计矩阵中根据阈值选取候选的曲线形状，由于在参数空间不进行离散化，因此可以获得高分辨率的效果。

从可处理的图像类型来看，三种变换都可以处理二值图像，但只有GHT可以处理灰度图像。

从检测的目标来看，三种变换都可以检测圆和参数型形状，但SHT和RHT不能检测任意形状的目标而GHT可以。并且SHT和RHT可以检测直线，而GHT不能检测直线。

从检测速度来看，RHT最快速，SHT和GHT都比较慢；从存储要求来看，RHT要求少量存储，而SHT和GHT对存储量的要求比较大；从检测精度来看，RHT的精度比较高，而SHT和GHT的精度适中，精度与参数空间的量化的要求有关；从参数的分辨能力来看，SHT和GHT都需要对参数进行离散化，因此其参数分辨能力与参数离散化的精度有关，而RHT不需要离散参数空间，因此其精度高。