在图像处理和计算机视觉领域，目标识别是一个重要的课题，而直线的检测又是其中最为基本的内容之一。本文通过对基于最小二乘修正的随机Hough变换直线检测进行了一些分析，文章是一篇武汉理工大学学报信息工程版投稿的论文范文。
摘要：利用Hough变换进行直线检测时，由于直线在参数空间中的映射容易受到邻近目标、噪声以及本身非理想状态的干扰，算法中的投票过程较易出现无效累积，进而导致虚检、漏检及端点定位不准等问题。针对传统方法的上述缺陷，提出了一种基于ρθ域最小二乘拟合修正的随机Hough变换的直线检测方法。首先， 在随机抽样时利用像素-长度比值对抽样的有效性进行判定，剔除不在直线上的抽样点对;然后， 对邻域相关点进行ρθ域的最小二乘拟合，得到修正后的直线参数用于累加投票，投票过程中设定累加阈值，通过检测峰值点逐次检出疑似长直线;最后， 通过设定断裂阈值对每条长直线进行筛选和分段，定位出直线段的端点。仿真实验表明，所提方法在投票时有效抑制了复杂环境对局部最大值的干扰，使直线检测的准确率得到显著提升。
关键词：直线检测,随机Hough变换,投票有效性,最小二乘法,参数空间
0引言
直线检测之前通常需要对图像进行预处理，如去噪、增强、分割、边缘检测等，将图像转换为只包含边缘信息的二值图像再进行直线检测[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变换的无效累加，提高了累加效率，并避免了在参数空间累加网格中搜索局部最大值的过程，有效减少了直线检测的误检和漏检，得到定位准确的直线段。
1基于最小二乘修正的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检测到的直线。
图片
图2通过δ阈值筛选直线示意图
传统的RHT有效降低了传统HT的计算复杂度，但仍然存在无效累积的问题，给ρθ域的局部最大值搜索带来较大噪声，在复杂场景下易检测出虚假直线目标，或漏检实际直线目标。
1.2ρθ域的最小二乘拟合
传统的RHT方法为克服虚检、漏检提供了思路，本文在RHT基础上利用距离阈值中的点进行参数域的最小二乘修正。
最小二乘法(Least Square Method， LSM)是一种经典的优化手段。传统的最小二乘直线拟合采用直线的斜率和截距两个参数，优化的目标函数是观测点到直线竖直距离的二次方，亦即y方向上坐标差值的二次方，这使得优化过程严重依赖坐标系。因此本文采用在参数域的直接最小二乘拟合。
图像空间的直线L可由式(1)表示，对于空间一点Pk(xk，yk)，Pi到直线L的距离可以由式(4)表示。于是，基于最小二乘准则的直线拟合也可描述为以下约束优化问题：
min f=∑nk=1(ρ-yk sin θ-xk cos θ)2(5)
s.t. -π/2 < θ ≤ π/2
或其等效约束优化问题：
min g(a，b，c)=∑nk=1(axk+byk+c)2(6)
s.t. a2+b2=1
式(5)所描述的优化问题，其优化函数是一个拟凸函数，在非边界处有全局最小值，因此求偏导化简可得：
tan (2θop)=2∑ni=1∑nj=1xiyj-n∑ni=1xiyi∑ni=1∑nj=1(xixj-yiyj)-n∑ni=1(x2i-y2i)
ρop=1nsin θop∑ni=1yi+cos θop∑ni=1xi
f(θop，ρop)≤f(θ，ρ)
-π/2< θop <π/2(7)
式中：θop、 ρop为最优解; n为参与拟合的样本点个数。
实际求解过程中会遇到反正切函数值对应多解的问题。解决方法是先将可能的两组最优θop求解出来，再代入优化函数通过判断f是否达到最小来得到唯一的最优解。
这里对1.1节得到δ邻域点集ΓL中所有点在参数域进行最小二乘拟合，通过求解降低偏差较大噪声点的干扰，得到较为准确的直线参数参与投票。
1.3提出的直线检测算法流程
正如第1.1节所述，标准RHT在参数累加时，不考虑参数的有效性，将通过两个没有关联的点的直线参数作为一次累加，这样既降低了累加的效率，同时也给ρθ域的局部最大值搜索引入噪声。
本文在标准RHT的基础上，在累加之前通过两点连线的邻域内点的密度判断当前累加参数的有效性，并通过ρθ域的最小二乘拟合邻域内点得到累加参数。当累加网格的最大值等于累加阈值时，记录这个最大值并根据网格分辨率解算出一条直线，将这条直线从图像中去除，然后重新进行累加。这个过程重复直到某次有效累加达到最大累加次数或者无效累加达到最大失败次数为止。
将本文方法与标准Hough变换(SHT)在参数域的比较映射结果。图3(a)是包含两条非理想直线的二值图像。图3(b)、(c)分别是标准Hough变换及本文方法的参数域映射。图3(d)～(f)是(a)中添加了短线噪声之后的相应结果。标准Hough变换映射的峰有明显的“拖尾”，且随着短线噪声的加入更加显著，甚至出现了多个伪峰。而提出的方法映射的峰能量集中，即使增加短线噪声干扰也没有“拖尾”和伪峰出现。这与前面所作的理论分析结论相一致。可以看出，提出方法的累积修正对提高参数域的局部最大值搜索精度，进而降低直线检测虚检、漏检率，有重大意义。
假设已给定累加阈值Amax、最大累加次数Nmax和最大失败次数Fmax，以及直线宽容度阈值(距离阈值)δ和连线内点比例阈值Pth，则算法的详细步骤为：
步骤1初始化累加网格，累加次数n和失败次数f置零。
步骤2从二值图像所有边缘点中随机抽取两个。
步骤3考查选取的两点间连线的δ邻域内边缘点个数与两点之间距离的比值： 若比值大于Pth，则累加次数n加1并跳到步骤4; 否则失败次数f加1，跳到步骤5。
步骤4对δ邻域内所有点进行最小二乘拟合，计算直线参数 (ρ，θ)，并将其对应的网格累加值加1。若累加网格的最大值等于Amax，则记录直线参数，并直线δ邻域内边缘点从边缘点集合去除，跳到步骤1;否则，继续步骤5。
步骤5若累加次数n等于Nmax或失败次数f等于Fmax，则算法结束。
2断裂尺度阈值定位线段
改进的RHT得到的是若干条长直线贯穿整幅图像。实际应用中，定位出具体直线段的两个端点才具有更大的实用价值。本文提出用断裂尺度阈值来获取直线端点的位置。
将检测到的长直线δ邻域内的边缘点垂直投影到直线上，计算出投影点在直线上的相对位置，并按这个位置将边缘点进行排序。根据设定的断裂阈值Thgap和最短尺度阈值Thseg，先利用相对位置间隔大于Thgap的条件，将邻域边缘点划分到几条直线段中，然后将线段长度低于Thseg的线段作为短线噪声剔除。 经过断裂尺度阈值分段的直线段，既能避免因引入短线噪声而出现虚假线段，也有较好的抗断裂性能，防止出现过分割。
3仿真实验结果
3.1检测结果评价指标
为了对实验结果进行量化，需要确定具体评价指标。本文采用漏检率和虚检率表征检测准确度。
假设实验原图中有Nr条直线段，经过检测，得到的Nd条标注，漏检记为Nm条，虚检记为Ne条，规定如下：
1)对于一条标注，标注直线段与原直线段走向大于2°的，或夹角小于等于2°但标注线段被原直线段覆盖长度小于50%，认为错检(虚检)，Ne加1;
2)对于一条原始直线段，原直线段与标注直线段走向大于2°的，或夹角小于等于2°但标注线段共同覆盖原直线段长度小于80%，认为漏检，Nm加1。
于是仿真实验的漏检率ηm和虚检率ηe可以分别定义为：
ηm=Nm/Nr
ηe=Ne/Nd (8
直线检测结果的精度可用上述指标进行衡量，漏检率和虚检率越低，直线检测的精度越高。
3.2结果和评价
图4(a)是一幅512×512像素的仿真图像，其中有13条长短不同且部分存在相交、平行或共线的近似直线段，同时添加40条随机短线噪声。
图片
图4仿真实验结果
对仿真图像分别采用标准Hough变换、随机Hough变换和本文方法进行直线提取，其中直线断裂阈值设为20像素，最短检测直线阈值设为30像素。图中检测到的直线段两端分别用“×”符号表示。
对比采用同样参数设置的三组结果，图4 (b)标准Hough变换的检测结果有显著漏检产生，主要集中于直线较短或弯折较为明显的地方，即使检测到的直线段，也存在端点定位不准的情况。SHT对于尺度较小的直线目标检测性能较差，并且易受到直线弯折、短线噪声等的影响。
图4(c)随机Hough变换的直线虚检率略有上升，但漏检率明显低于标准Hough变换，原图的每条线段目标都能被部分检出;但线段的端点仍然不够准确，而且存在同一线段目标被检出为多条断开短线目标，这些问题在右侧平行线处尤其显著。这组结果表明，RHT虽然在漏检性能上优于SHT，但难以解决邻近平行线目标和直线段目标过度分段问题。
图4(d)本文方法精确检出原图存在的每条直线，没有出现虚检漏检的情况，并且每条直线段的端点定位准确，尤其在面对右侧两组平行线交叉这种复杂的情况时，仍然没有出现SHT、RHT存在的漏检、虚检、过度分段等问题，保持了优异的检测性能。
检测结果的漏检虚检指标如表1所示。
继续探究三种方法在不同噪声条件下的检测性能。仍然采用上述直线，但随机添加不同数目的短线噪声，依次得到图5中两种指标的变化曲线。从图中可以看出，三种方法的检测准确度大体上随着短线扰动数目的增加而下降;对比已有两种算法，SHT的抗虚检性能较好而RHT的抗漏检性能较好，并且两种方法都随噪声变化出现较大波动;本文方法在漏检、虚检性能方面都是要优于两种已有算法的，并且其检测性能并没有随噪声的变化发生明显波动，有着较好的稳定性和鲁棒性。
图片
图5在不同短线噪声影响下的检测结果
4结语
本文提出通过参数域的最小二乘修正来改进随机Hough变换直线检测：直接在参数空间引入最小二乘拟合方法，并对随机Hough变换的投票步骤提出改进，最后在提取长直线的基础上引入断裂尺度阈值确定线段端点。
仿真图像的直线提取实验可以证明，本文提出的基于最小二乘估计修正改进的随机Hough算法可以有效地改进标准Hough变换以及随机Hough变换的固有缺陷。经过有效性筛选和最小二乘拟合之后的累加效率更高，噪声像素和邻近直线像素的干扰更小，虚检率和漏检率显著降低;同时，对直线形变的宽容度更好，直线端点的定位性能更加优越。
参考文献：
[1]DONG J， YANG X， YU Q. Fast line segment detection based on edge connection[J]. Acta Optica Sinica， 2013， 33(3)：213-220. (董晶， 杨夏， 于起峰. 基于边缘连接的快速直线段检测算法[J]. 光学学报， 2013， 33(3)：213-220.)
相关期刊简介：《武汉理工大学学报》是教育部主管、武汉理工大学期刊社主办的人文社会科学类综合性学术期刊。本刊主要刊登文史哲、政治学、经济学、管理学、社会学、教育学、新闻传播与出版、文化学、心理学、美学、思想政治教育等人文与社会科学学科及其相关学科、边缘学科、交叉学科的最新理论研究成果，欢迎社会各界从事人文社科研究的学者和学人及作者惠赐佳稿，欢迎各高校、图书馆和院系资源室征订收藏本刊，欢迎社会图书馆和科研院所图书馆征订和收藏本刊。
