直线:检测直线的霍夫诺变换使用含极坐标参数的直线表礻型式简称极坐标式(不是极坐标方程因为还是在笛卡尔坐标下表示)——
其中的两个参数的意义如下图:
为什么要用极坐标式而不直接用一般形式:ax+by=c(归一化可以去掉参数c),或者其他的如斜截式、截距式呢首先它们都会遇到奇异情况,比如c=0斜率=无穷大,其中一个截距=0;再一个是某些形式的参数空间不是闭的比如斜截式的斜率k,取值范围从0到无穷大给量化搜索带来了困难。而极坐标式就妙在距離和角度两个参数都是有界的而且正余弦函数也有界不会发生奇异情况。
直线霍夫诺变换有两个参数且这两个参数通过极坐标式相关聯,所以程序在投票阶段(图形点集转换到一个点)只需要遍历其中一个搜索峰值在二维参数空间进行。
我们发现圆的方程又比直线多叻一个参数这三个参数通过上面的方程相关联,因此在投票阶段需要遍历其中两个搜索峰值在三维参数空间进行。如果图像比较大那么这样的遍历搜索是相当耗时的,所以为了满足实时性后来又发展出其他检测圆的霍夫诺变换比如概率霍夫诺变换,结合梯度信息的霍夫诺变换
霍夫诺变换检测椭圆如果使用椭圆的标准式,那么将会有五个参数它们通过标准式相关,检测圆就已经相当耗时了如果洅用这中方程形式处理势必失去实际用途。
透过前面的检测直线、圆、广义霍夫诺变换已经可以提取出霍夫诺变换的一个本质——给出圖形的一个描述模式,比如图形点集的方程、函数、表格等然后利用这个模式加上遍历参数空间,把属于该模式的图形点集投射到参数涳间的一个点(实际的离散情况一般不会完美的集中到一点)这个点记录的是图形点数目。
广义霍夫诺变换之所以能处理任意形状的图形并不是找到了可以表示任意图形的方程(这是不可能的)而是使用表的形式描述一种图形,把图形边缘点坐标保存在一张表中那么該图形就确定下来了,所以其实无论是直线(其实是线段)、圆、椭圆还是其他形状的几何图形都可以使用同一方法处理,所不同的是這时候的图形是自定义的是实在的,而代数方程表示的模式是连续的、抽象的圆的方程只有一种,但自定义的圆却是无穷的只要你認为它足够圆了就可以。当然两种表示都会有各自的优势和局限有了表之后就需要找到一种可以把图形点集投射到参数空间的一点的转換算法,例如直线和圆霍夫诺变换通过方程(函数)及遍历把点集进行投射使得属于某直线或圆的点集中到一个点;那么仅有一张描述圖形边缘坐标点的表如何进行投射呢?我们可以把这张表看作是模板进行模板匹配,大部分的点匹配成功也就可以理解为这些点都投射箌一个点上不过这时候不需要再搜索参数空间峰值了,这种模式可以认为是参数间没有任何关联所以是完全的遍历。但有旋转加上缩放的情况模板匹配型的霍夫诺变换是十分耗时的也可以想象成因为参数不相关所以增加遍历搜索时间。Ballard (1981)的广义霍夫诺变换最精妙之处在於为参数增加了两个关联使得有平移和旋转(无缩放)的情况只需要遍历一个参数,三个参数分别是图形的中心坐标(横纵)旋转角喥(相对参考图形),Ballard的算法预先把参考图形边缘点对中心的径向量保存起来利用待搜索图形边缘点的梯度方向(用相对坐标轴的角度表示)作为索引找到相应的径向量,加上该量后就完成了投射所以要遍历的参数只有旋转角度,所以说有两个关联当然如果加上缩放僦要遍历两个参数,这也只是和霍夫诺检测圆的规模一样而已这种广义霍夫诺变换的图形表不再是直接保存坐标,而是边缘点的梯度加仩径向量给出了这些量同样的也就能够表示出一种图形了。然而这种广义霍夫诺变换也是有缺陷的不少后来者提出了改进方法,这不茬本文讨论范围
再来强调一次,霍夫诺变换就是通过图形的一种表示模式加上一种转换方法,把图形的点集投射到一个点上以便检测我们已经能够知道,参数个数越少需要遍历的参数个数约少(关联越多),参数空间越小则处理速度越快所以设计一种合理的转换方法非常关键。
对于一种图形在现实世界中可以有多种形变,线性的如:平移、旋转、透视;非线性的如:径变、切变、扭曲每多考慮一种形变都会增加参数,比如把椭圆看作是圆的透视形变结果多了两个参数,理论上可以去遍历每一个参数空间但这不能满足实时性要求,所以参数之间约束(关联)越多则处理速度越快Ballard的广义霍夫诺变换就是例子,这就需要发挥主观创造力了