学习笔记：基于Hough变换的直线和圆检测（1）

Hough变换：一种使用表决方式的参数估计方式（表决=投票=累加==）
原理：图像空间和hough参数空间的线-点对偶性，将图像空间的问题转移到参数空间进行。
why用到参数空间？比如：在图像空间直线方程：y=ax+b，那么如果要检测垂直于x轴的直线的时候，a→无穷→导致计算量增大，而检测直线时，极坐标（ρ，θ）就没有这种问题
hough直线检测：

图来源于文章：hough变换（很好的文章）
在直角坐标系上，点P的坐标为（x，y），对于极坐标而言p（rcos∅，rsin∅）而转换到极坐标的话ρ即O到经过P点直线的垂直距离，θ即图上标示
因此给出极坐标中的一个点（ρ，θ），可以确定直角坐标系中确定的一条直线。(即直角坐标系中的一条直线在极坐标系中为一个点)
在这里，原始图像=直角坐标系，参数空间=极坐标系
所以对原始图像中任何一个边缘点，找到所有可能经过该点的直线→所有在参数空间中的点→无穷的直线对应的点形成一条曲线
(1个边缘点-无数条直线-一条曲线(参数空间)，n个边缘点-n条曲线)
而所有边缘点在参数空间形成无数曲线的交点→原始图像所有边缘点的共同支线（表决：参数空间中交于一点的数目做多的曲线，这点对应原始图像的一条直线，这条直线经过的边缘点最多）
这就是hough变化检测直线的方法。
而hough针对圆检测：
1.线检测是（ρ，θ），圆检测采用（a，b，r） (x-a)²+(y-b)²=r²
圆检测参数空间为三维
图像空间一个点（x，y）→参数空间一个圆锥
图像空间一个圆→参数空间一堆圆锥的交点
与hough线检测一样，圆检测也是累加，但是三维参数空间累加时间空间太过庞大→计算量大→需要改进

2.基于梯度的hough变换圆检测：
对圆方程求导:2(x-a)+2(y-b)(dy/dx)=0
参数空间由原始方法1的三维变成了二维(a,b)
计算量减少，但精度也下降了
原因：利用了边界斜率
本质上边界斜率是用曲线在某一点弦的斜率来代替的，若要保证没有误差，弦长要=0
实际上经过图像预处理之后原始图像曲线的表现形式是离散的，某一点斜率→某点右向n步的斜率
弦长小→斜率量化误差大→适用于干扰较少的完整圆形目标

3.随机hough变换圆检测：
随机抽样（3点，不共线，累加，到达阈值(圆)）→降低了内存和计算时间，但是无效累加量大，效率不高，精度低于1

4快速随机hough变换（王建峰）
基本思想:圆必定在外接正方形之内→只对正方形内的像素进行计算
减少了无效累计和计算时间