摘要：利用Hough变换进行直线检测时，由于直线在参数空间中的映射容易受到邻近目标、噪声以及本身非理想状态的干扰，算法中的投票过程较易出现无效累积，进而导致虚检、漏检及端点定位不准等问题。针对传统方法的上述缺陷，提出了一种基于ρθ域最小二乘拟合修正的随机Hough变换的直线检测方法。首先， 在随机抽样时利用像素-长度比值对抽样的有效性进行判定，剔除不在直线上的抽样点对;然后， 对邻域相关点进行ρθ域的最小二乘拟合，得到修正后的直线参数用于累加投票，投票过程中设定累加阈值，通过检测峰值点逐次检出疑似长直线;最后， 通过设定断裂阈值对每条长直线进行筛选和分段，定位出直线段的端点。仿真实验表明，所提方法在投票时有效抑制了复杂环境对局部最大值的干扰，使直线检测的准确率得到显著提升。
关键词：直线检测;随机Hough变换;最小二乘法;参数空间;投票有效性
引言
在图像处理和计算机视觉领域，目标识别是一个重要的课题，而直线的检测又是其中最为基本的内容之一。直线检测之前通常需要对图像进行预处理，如去噪、增强、分割、边缘检测等，将图像转换为只包含边缘信息的二值图像再进行直线检测[1-2]。图像直线检测的难点在于，既要正确捕获直线目标，又要保证一定的宽容度以适应非理想直线的情形。
Hough变换(Hough Transform， HT)是处理直线检测问题的一种经典算法，在诸多领域得到了广泛应用[3-5]。它的主要思想是，在参数空间的离散化网格中，利用“多对一”映射将各个像素点映射到参数空间，然后通过累加“投票”得到共线的像素点在参数空间的映射，进而得到图像中直线的参数。这种方法为在参数域进行直线检测提供了新的思路，但实际应用中由于非理想直线和复杂场景干扰，效果不佳。一方面图像中的潜在直线往往因为噪声的干扰而偏离理想状态，出现诸如局部弯曲或断裂的现象，参数空间峰值点不容易被检测到，导致漏检;另一方面，潜在直线周边的其他非直线目标像素的存在，使参数空间相应位置出现伪峰，导致虚检。
利用较小采样集合代替全点集的改进方法取得了较好的效果，最早且有代表性的是Xu等[6]的随机Hough变换(Randomized Hough Transform， RHT)和Kiryati等[7]的概率Hough变换(Probabilistic Hough Transform， PHT)，但因全局采样而引入大量无效累积，复杂场景效果不佳。毛俊勇等[8]在所建立的点属于某直线上不确定性度量概率模型基础上，根据随机选择的两点间直线参数，按照Bayesian法则用基于不确定度量的参数空间软投票，但检测算法的分辨率受到度量模型和投票网格的限制。Ji等[9]引入局部增强算子，通过增加参数空间中直线峰值和噪声之间的差异，得到更准确的局部最大值，但累加过程仍然基于标准Hough变换(Standard Hough Transform， SHT)，需要全局计算，效率不高。王竞雪等[10]在Hough变换前采用相位编组(Phase Grouping)方法进行边缘跟踪，降低了直线间干扰，但对多条直线相交的等复杂连通情形效果不理想。Lee等[11]和Chung等[12]采用多参数的离散Hough变换，在孤立直线检测中比SHT具有更高检测率，但多参数的引入导致了较大计算量。
RHT随机选取点对，避免了传统Hough变换“多对一”映射的缺陷，却使得累积具有很大的盲目性，而且噪声和互相干扰使得参数计算精度受到影响。基于此，本文提出了一种在参数空间进行最小二乘修正的随机Hough变换方法。首先进行边缘点随机抽样，对抽样两点之间是否可能存在直线进行判断并筛选; 然后对其所有邻域相关点进行ρθ域的最小二乘拟合，根据修正后的直线参数在累加网格进行累加，通过搜索累加最大值计算得到检测直线参数; 最后通过断裂-尺度阈值定位出线段的端点，完成直线段的检测。这种方法有效地减少了随机Hough变换的无效累加，提高了累加效率，并避免了在参数空间累加网格中搜索局部最大值的过程，有效减少了直线检测的误检和漏检，得到定位准确的直线段。
一、基于最小二乘修正的RHT算法
1.1随机Hough变换
Hough变换是一种经典的利用参数空间的累加统计来完成图像空间检测任务的方法。它将图像xy空间的点映射为参数ρθ空间的一条曲线，而将图像空间的一条给定形状的曲线映射为参数空间的一个点，图像空间曲线上的点在参数空间的像经过累加，就得到了一个累加权值较高的点，反向映射得到前面所述的图像空间的`曲线。
Hough变换的基本原理如图1所示，设L是图像空间的直线，在图像空间直角坐标系下的方程为：
ρ=x cos θ+y sin θ(1)
式中：ρ为直角坐标系原点到直线L的距离，θ为直线L与y轴的夹角。点P(θ， ρ)就是直线L在参数ρθ空间的映射。标准的Hough变换针对每个前景像素进行映射，其计算复杂度比较高，不适合实时处理。因此，一种基于概率统计的随机Hough变换开始应用于数字图像处理领域。
图片
图1直线在参数空间的映射
随机Hough变换(RHT)的基本思想是在图像空间的前景像素(通常为边缘点)中随机选取两个点，将通过这两点的直线映射到参数空间。通过这种多到一的映射，RHT避免了标准Hough变换(SHT)中一到多映射所需的庞大计算量。
设边缘像素点集Γ={P(x，y)}，从中随机选取两个相异点P1(x1，y1)、P2(x2，y2)，得到通过这两点的唯一直线L12，且其参数可依次由式(2)、(3)计算得到。
θ12=tan-1y1-y2x2-x1(2
ρ12=y1+y22 sin θ12+x1+x22 cos θ12(3 将该组参数(θ12， ρ12)作为索引进行累加，即令该参数所属的网格的累加值递加一。经过一定数目的累加之后，在网格累加值中搜索局部最大值，这些网格的参数(θmax， ρmax)对应的直线就构成了一个直线集合，它包含但不限于实际图像中的直线L，需要进行进一步筛选。
点集Γ中的边缘点Pk到该直线L的距离为：
disk=ρ-xk cos θ-yk sin θ(4
通过判断点到直线的距离是否小于某一阈值δ，距离小于该阈值的点就认为从属于该直线L，构成集合ΓL，如图2所示。另外，事先确定一个数目门限Nth，如果点集内的点的个数大于Nth，则直线L是实际直线;否则不为实际直线，将其排除。这样就能判断直线L在距离阈值δ下是否实际存在。排除后剩余的直线就是RHT检测到的直线。