霍夫变换

霍夫变换

Hough变换是图像处理中从图像中识别几何形状的基本方法之一。Hough变换的基本原理在于利用点与线的对偶性，将原始图像空间的给定的曲线通过曲线表达形式变为参数空间的一个点。这样就把原始图像中给定曲线的检测问题转化为寻找参数空间中的峰值问题。也即把检测整体特性转化为检测局部特性。比如直线、椭圆、圆、弧线等。

1、直线检测

直线方程：y=kx+b$y=kx+b$，其中，k和b为参数，x为变量
转换之后：b=−xk+y$b=-xk+y$，其中，k为变量，x和y为参数

x-y坐标系中直线上的一个点（x-y坐标系的一个点确定一族k、b不同的过该点的直线），对应k-b坐标系中的一条直线，所以x-y坐标系中同一直线上的点可以确定k-b坐标系中的很多条过同一点的直线（因为x-y坐标系中同一直线的k和b相同）。

所以从x-y坐标系变换为k-b坐标系，同一直线上的点会相交于同一点，所以参数坐标系下的聚集点就对应了原始坐标系下的直线。

表达存在的问题：当直线为垂直于x轴的线时，斜率为无穷大，无法用y=kx+b$y=kx+b$来表示，所以实际应用中利用参数方程p=x∗cos(θ)+y∗sin(θ)$p=x\ast cos(\theta )+y\ast sin(\theta )$来表示直线。此时，图像平面上的点就对应到参数p-theta系上的一条曲线。

(ρ−θ)$(\rho -\theta )$ 的关系是sin函数

ρ>=0,θ∈[0,360]$\rho >=0,\theta \in [0,360]$
ρ为实数（有正有负）,θ∈[0,180]$\rho 为实数（有正有负）,\theta \in [0,180]$

划分bin，找到投票值最大的点，就是直线可能的位置。

程序实现，一种只检测梯度方向的投票，还有一种方法就是先粗搜索，找到一个可能的点，之后在细搜索找到精确的点（粗细搜索的方法）。

投票的点越亮，得到的线越长，因为点越亮表示该线的点越多。

只有该简单结构能写出解析式，就肯定能用霍夫变换来检测出来。

目的：找到二值图像中，经过足够多数量的点的所有直线，并分析每个单独的像素点，识别出可能穿过它的直线，一条直线可以穿过很多点，也就是说它足够明显，使用二维累加器，统计直线被识别了多少次，

二、检测圆：

1. 半径确定——映射后还是圆
2. 半径不确定——映射后是圆锥（很多半径不同的圆的累积）

1、已知半径的圆

其实Hough变换可以检测任意的已知表达形式的曲线，关键是看其参数空间的选择，参数空间的选择可以根据它的表达形式而定。比如圆的表达形式为 ，所以当检测某一半径的圆的时候，可以选择与原图像空间同样的空间作为参数空间。那么圆图像空间中的一个圆对应了参数空间中的一个点，参数空间中的一个点对应了图像空间中的一个圆，圆图像空间中在同一个圆上的点，它们的参数相同即a，b相同，那么它们在参数空间中的对应的圆就会过同一个点（a，b），所以，将原图像空间中的所有点变换到参数空间后，根据参数空间中点的聚集程度就可以判断出图像空间中有没有近似于圆的图形。如果有的话，这个参数就是圆的参数。

2、未知半径的圆

对于圆的半径未知的情况下，可以看作是有三个参数的圆的检测，中心和半径。这个时候原理仍然相同，只是参数空间的维数升高，计算量增大。图像空间中的任意一个点都对应了参数空间中的一簇圆曲线。 ，其实是一个圆锥型。参数空间中的任意一个点对应了图像空间中的一个圆。

3、椭圆

椭圆有5个自由参数，所以它的参数空间是5维的，因此他的计算量非常大，所以提出了许多的改进算法。

圆形需要的参数，x,y,r，用霍夫梯度法来实现：

canny->对每个边缘点考虑局部梯度->在梯度的方向进行投票