霍夫变换中直线拟合的最小二乘法
ichriZ
1. 基本概念 （1） 霍夫变换
霍夫变换(Hough Transform) 是图像处理中从图像中识别几何形状的基本方法之一，应用很广泛，也有很多改进算法。最基本的霍夫变换是从黑白图像中检测直线或线段。 （2） 最小二乘法
曲线拟合方法的一种，通过最小化误差的平方和寻找数据的最佳函数匹配。 2. 适用情况
霍夫变换是基于统计的方法，能将图像中的噪声或干扰点的影响消除，但其结果存在精度不够与直线有效区间不易控制的问题；最小二乘法是直线拟合的有效方法，但直接用于拟合时易受干扰点或噪声点影响。在检测图像中的直线段时，先利用霍夫变换消除无效点的影响，再结合最小二乘法法进行拟合，可以提高检测效果。 3. 霍夫变换原理与实现方法 (一) 霍夫变换原理
在平面直角坐标系
中一条直线
表示参数平面
中的一条直线
。再取
表示参数平面
中直线
即：同一直线上的不同的点在对应的参数平面中对应不同的直线，但都交于同一点，所以可以通过坐标系
中的交点来寻找坐标系
中的直线。当坐标系
中的直中的R
中的一条直线
。
与
相交于一点
，对应于坐标系
上另一点
则有
，任取其上一点
，有
线数量为R时，坐标系条直线。
此种方法不能够表示
中对应R个峰值交点，它们对应于坐标系
这类直线，实际中常将原有直线表示为参数方程
此直线上的点对应坐标系中的一族三角函数曲线，它们在有效区间内交于一点
，对应于坐标系中的。下图是一个具体例子：
霍夫变换—>
(二) 最小二乘法原理
对于给定数据
，使
交点坐标
，要求在某个函数类中寻求一个函数
本文中讨论的是直线的最小二乘法，故
均取一次多项式。
设具有如下格式
其中
质，就是要适当的选择参数
是待定参数，求具有这种形式的最小二乘法的实
，使相应的函数
满足条件。也就是说，点是多元函数
的极小点，从而
满足方程组
因此，可以通过解此方程组（称为法方程组）来求取获得最小二乘解。 当讨论的曲线为代数多项式时，不妨取
则有
，以便
令得方程组
即
本文中模拟的是直线，使用一次多项式，则约束条件为
其中直线表达式为
(三) 霍夫变换的实现方法
图像处理中的二值边缘图，一般是处理离散数据，则根据霍夫变换可按下列步骤实现直线检测：
（1）参数空间量化成m*n（m为累加器矩阵
；
，并把累加器的初始值置
的等分数，n为
的等分数）个单元，并设置
（2）给参数空间中的每个单元分配一个累加器为0；
（3）取出直角坐标系中的点
带入式
，并以量化的
值计算出
和
；
所对应的单元，并将该单元的累加器加1，即
（5）当直角坐标系中的点都经过（3）（4）两步遍历后，检测参数空间中每个累加
和
即为直角坐标系中直线方程式
的参
（4）在参数空间中，找到
器的值，累加器最大的单元所对应的数。
由上述霍夫变换过程可知，如果参数空间中的
和
和量化过粗，则参数空间中的和
量化过细，那么计算
凝聚效果较差，找不出直线的准确参数；反之，
量将增大。 另外，当直角坐标系中的点分布在R条直线附近时，可在第5步检测累加器时，取出累加器中前R个值最大的单元所对应的线方程式
和
，以
和
为直角坐标系中直
的参数，即可同时实现多条直线的拟合。
4. 霍夫变换与最小二乘法相结合的直线拟合方法
假设采集到的数据为
，s为数据集中的数据点
数，M中改的数据点分布在R调直线附近，根据实验目的要求给定误差阈值为dk。 （1）霍夫变换。将
式改写成
根据式
，对M作霍夫变换，可得拟合直线的参数
附近的点集
。将式
。
表示的法线式直线方程改写成
（2）找出拟合直线斜截式
其中
计算M中的点到由式
确定的直线的距离
如果 则
为符合误差阈值要求的第k条霍夫变换直线附近的点集。 （3）以点集
为拟合数据，分别拟合各直线，可得直线方程式
的参数
。
以即
和为端点，可确定各直线段的区间，
5. 简单实现
编程环境：Windows7+Qt5+OpenCV2.4.3 实验测得数据： X坐标 36 Y坐标 78 48 88 63 101 72 109 84 119 97 130 108 140 120 150 143 170
原图像 经过二值化处理的图像 检测结果
6.参考文献
曾接贤, et al. \霍夫变换与最小二乘法相结合的直线拟合.\南昌航空工业学院学报 (自然科学版) 4 (2003).
Hough, Paul VC. \18 Dec. 1962.