基于梯度方向约束的边缘跟踪直线段快速检测装置及方法

摘要

本发明公开了基于梯度方向约束的边缘跟踪直线段快速检测装置及方法，该方法包括：获得图像的单像素的边缘点；根据梯度的约束，当且仅当搜索到的相邻边缘点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于阈值时才对相邻边缘点进行连接，获得直线段；对得到的初始直线段，即边缘段，求出其两个端点间的距离l与边缘段上的各点到连接两个端点的直线间的最大距离d之间的比值，该比值表征该边缘段作为直线的显著程度，判断该边缘段是否应作为曲线段而被分割为多个直线段；以及进行直线段判定，剔除虚假直线段。本发明进行直线段检测的速度快，对不同的图像尺度和对比度水平的适应能力强。

权利要求

1.一种基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，包括：

（1）获得图像的单像素的边缘点；

（2）根据梯度的约束，当且仅当搜索到的相邻边缘点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于阈值时才对相邻边缘点进行连接，获得直线段；包括：线段的延伸方向角在边缘跟踪过程中使用如下公式进行估计式中，Gi为第i个点的梯度幅值，θi为第i个点的梯度切向角，若记Gix和Giy分别为第i个点的横向和纵向的梯度值，则有每连接一个新的边缘点，就重新估计一次线段延伸方向，直到不再有新的满足方向条件的边缘点为止；

（3）对得到的初始直线段，即边缘段，求出其两个端点间的距离l与边缘段上的各点到连接两个端点的直线间的最大距离d之间的比值，该比值表征该边缘段作为直线的显著程度，判断该边缘段是否应作为曲线段而被分割为多个直线段；如果在距离连接两个端点的直线最远处将边缘段断开得到的两个边缘段中任何一个比原边缘更为显著则执行该分割；

重复进行以上步骤，直到分割后不能得到更为显著的边缘段，或者分割后所得的两个边缘段所包含的像素数量均小于设定的阈值TL；以及（4）进行直线段判定，剔除虚假直线段。

2.如权利要求1所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，所述（1）进一步包括：（1.1）采用7×7的高斯核对图像进行平滑滤波，然后采用3阶Sobel算子进行梯度计算；

（1.2）得到图像梯度后，进行阈值化处理以得到图像中仅包含边缘信息的像素集合，剔除小梯度幅值点，式中：ρ为梯度幅值阈值，q为在256级灰度量化中可能带来的最大灰度级误差，τ表示允许的梯度方向最大误差，所有梯度幅值小于该阈值的图像点在后续的处理过程中被忽略；

（1.3）对得到的结果沿梯度方向进行非极大值抑制处理以得到细化的边缘，经过非极大值抑制，仅有那些在自己梯度方向上是局部最大值的像素点被保留下来，其余的像素点将被剔除，得到单像素的边缘。

3.如权利要求1所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，所述（2）进一步包括：对梯度幅度值进行伪排序，以选择种子点：在0和最大梯度幅值之间等间隔的划分若干个等级，每个像素根据其对应的梯度幅值分类到这些等级之中，伪排序完成之后，种子点从梯度值最高的等级开始选择，依次往下，直至遍历所有等级。

4.如权利要求1所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，所述（4）进一步包括：统计候选直线段上相位方向和所拟合的直线方向近似垂直的边缘点数量，虚假直线段的剔除转化为判断其是否为非结构的背景噪声假设下的例外；为每条直线段选择一个局部背景区域，即直线支撑区域，该区域选择为矩形，矩形的中心选择为线段上所有点的加权平均，主方向为所有点的加权分布的协方差矩阵的最大特征值对应的特征向量所在的方向，其中每个点的权值为其梯度幅度，矩形的长度和宽度分别选择为使矩形刚好能够完全覆盖对应线段上所有的点时的值，此外，计算出的矩形中心和主方向也作为沿矩形主方向通过其中心的直线段的拟合结果。

5.如权利要求4所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，所述（4）进一步包括：假设背景模型为白噪声模型，也即图像中每个像素点的相位方向在[0, 2π]内满足独立均匀随机分布，图像上灰度变化平缓的区域认为符合这种假设，有效直线段则是相位方向高度一致的区域，否则就应该是虚假直线段，在N×M 的图像中，所有可能的直线数量为 C(N×M，2) 条，直线支撑区域的宽度在从1到N之间变化，所有可能的直线支撑区域数量为 (N×M)2.5；产生特定的直线支撑区域中图像点相位方向分布情况的虚警数为，

式中：n表示直线支撑区域中的总点数，k表示直线支撑区域中与直线方向一致的点数，p由角度阈值决定，图像点的局部主方向设为其梯度切向，NF≤ε的直线段被接受，NF>ε的直线段被作为虚假直线段剔除，ε为根据经验设定的阈值，B(n,k,p)为二项分布累积概率。

6.如权利要求5所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，其特征在于，所述（4）进一步包括：在一条候选直线段被剔除之前，以1个像素为步长逐步增加矩形的宽度并重新进行NF的计算，直至判定结果为真或达到设定的最大容许宽度TW，若判定结果始终为假，则保留使NF值最小的宽度值用以通过调整p 值进行进一步的判定；

在完成矩形宽度调整之后，对每条候选线段除p外依次再取p/2、p/4、p/8、p/16和p/32五个值进行NF的计算，若所述五个值其中任意一个的计算结果使判定为真，则接受该直线段。

7.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有计算机可执行指令，所述计算机可执行指令被处理器执行时实现如权利要求1至6中任意一项所述的方法中的步骤。

说明书

基于梯度方向约束的边缘跟踪直线段快速检测装置及方法

技术领域

[0001] 本发明属于视觉检测技术领域，涉及一种基于梯度方向约束的边缘跟踪直线段快速检测装置及方法。

背景技术

[0002] 直线边缘是描述图像中物体形状和结构的主要几何特征之一。直线段检测一直是计算机视觉和摄影测量中的一个基本任务和研究热点，在摄像机标定、目标识别和匹配、工业检测等许多领域都有着广泛的应用。

[0003] Line Segment Detector（LSD）算法由于在速度、检测性能稳定性方面取得了较好的平衡而成为目前具有代表性的高性能直线段检测方法。LSD算法的基本思想是在改进的相位编组算法的基础上，采用Desolneux等提出的一种称为背景反例模型的通用阈值决策理论，对虚假直线段进行判别和剔除。但是LSD 算法并没有摆脱相位编组类算法固有的被操作像素点数量繁多的缺点，其速度上的优势主要是通过采用简化的梯度求解算子获得。此外，该算法为保证直线段检测的准确性，在一个直线支撑区域被判定为虚假检测前设计了一系列的参数调整措施对其进行优化，也在一定程度上影响了算法的执行效率。

发明内容

[0004] 本发明的目的在于提供一种基于梯度方向约束的边缘跟踪直线段快速检测装置及方法，在保证检测性能的前提下，提高运算效率。

[0005] 根据本发明的第一方面，提供一种基于梯度方向约束的边缘跟踪直线段快速检测装置，包括：

[0006] 单像素边缘图像获取模块，用于获得图像的单像素的边缘点；

[0007] 直线段提取模块，用于仅根据梯度的约束，当且仅当搜索到的相邻边缘点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于阈值时才对相邻边缘点进行连接，获得直线段；

[0008] 曲线分割模块，用于判断得到的初始直线段是否应作为曲线段而被分割为多个直线段；以及

[0009] 验证模块，用于在曲线分割模块完成分割后进行直线段判定，剔除虚假直线段。

[0010] 根据本发明的第二方面，提供一种基于梯度方向约束的边缘跟踪直线段快速检测方法，包括：

[0011] （1）获得图像的单像素的边缘点；

[0012] （2）根据梯度的约束，当且仅当搜索到的相邻边缘点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于阈值时才对相邻边缘点进行连接，获得直线段；包括：线段的延伸方向角在边缘跟踪过程中使用如下公式进行估计

[0013]

[0014] 式中，Gi为第i个点的梯度幅值，θi为第i个点的梯度切向角。若记Gix和Giy分别为第i个点的横向和纵向的梯度值，则有

[0015]

[0016] 每连接一个新的边缘点，就重新估计一次线段延伸方向，直到不再有新的满足方向条件的边缘点为止；

[0017] （3）对得到的初始直线段，即边缘段，求出其两个端点间的距离l与边缘段上的各点到连接两个端点的直线间的最大距离d之间的比值，该比值表征该边缘段作为直线的显著程度，判断该边缘段是否应作为曲线段而被分割为多个直线段；如果在距离连接两个端点的直线最远处将边缘段断开得到的两个边缘段中任何一个比原边缘更为显著则执行该分割；重复进行以上步骤，直到分割后不能得到更为显著的边缘段，或者分割后所得的两个边缘段所包含的像素数量均小于设定的阈值TL；以及

[0018] （4）验证模块进行直线段判定，剔除虚假直线段。

[0019] 可选的，对于所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，进一步包括：

[0020] （1.1）采用7×7的高斯核对图像进行平滑滤波，然后采用3阶Sobel算子进行梯度计算；

[0021] （1.2）得到图像梯度后，进行阈值化处理以得到图像中仅包含边缘信息的像素集合，剔除小梯度幅值点，

[0022]

[0023] 式中：ρ为梯度幅值阈值，q为在256级灰度量化中可能带来的最大灰度级误差，τ表示允许的梯度方向最大误差，所有梯度幅值小于该阈值的图像点在后续的处理过程中被忽略；

[0024] （1.3）对得到的结果沿梯度方向进行非极大值抑制处理以得到细化的边缘，经过非极大值抑制，仅有那些在自己梯度方向上是局部最大值的像素点被保留下来，其余的像素点将被剔除，得到单像素的边缘。

[0025] 可选的，对于所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，进一步包括：

[0026] 对梯度幅度值进行伪排序，以选择种子点：在0和最大梯度幅值之间等间隔的划分若干个等级，每个像素根据其对应的梯度幅值分类到这些等级之中，伪排序完成之后，种子点从梯度值最高的等级开始选择，依次往下，直至遍历所有等级。

[0027] 可选的，对于所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，进一步包括：

[0028] 统计候选直线段上相位方向和所拟合的直线方向近似垂直的边缘点数量，虚假直线段的剔除转化为判断其是否为非结构的背景噪声假设下的例外；为每条直线段选择一个局部背景区域，即直线支撑区域，该区域选择为矩形，矩形的中心选择为线段上所有点的加权平均，主方向为所有点的加权分布的协方差矩阵的最大特征值对应的特征向量所在的方向，其中每个点的权值为其梯度幅度，矩形的长度和宽度分别选择为使矩形刚好能够完全覆盖对应线段上所有的点时的值，此外，计算出的矩形中心和主方向也作为沿矩形主方向通过其中心的直线段的拟合结果。

[0029] 可选的，对于所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，进一步包括：假设背景模型为白噪声模型，也即图像中每个像素点的相位方向在[0, 2π]内满足独立均匀随机分布，图像上灰度变化平缓的区域认为符合这种假设，有效直线段则是相位方向高度一致的区域，否则就应该是虚假直线段，在N×M 的图像中，所有可能的直线数量为 C(N×M，2) 条，C(N×M，2)为从N×M个点中随机取两个不重复的点所得组合数[0030]

[0031] 直线支撑区域的宽度在从1到N之间变化，所有可能的直线支撑区域数量为 (N×M)2.5；产生特定的直线支撑区域中图像点相位方向分布情况的虚警数为

[0032] ，

[0033] 式中：n表示直线支撑区域中的总点数，k表示直线支撑区域中与直线方向一致的点数，p由角度阈值决定，图像点的局部主方向设为其梯度切向，NF≤ε的直线段被接受，NF>ε的直线段被作为虚假直线段剔除，ε为根据经验设定的阈值，B(n,k,p)为二项分布累积概率， 。

[0034] 可选的，对于所述的基于梯度方向约束的边缘跟踪直线段快速检测方法，进一步包括：在一条候选直线段被剔除之前，以1个像素为步长逐步增加矩形的宽度并重新进行NF的计算，直至判定结果为真或达到设定的最大容许宽度TW，若判定结果始终为假，则保留使NF值最小的宽度值用以通过调整p 值进行进一步的判定；

[0035] 在完成矩形宽度调整之后，对每条候选线段除p外依次再取p/2、p/4、p/8、p/16和p/32五个值进行NF的计算，若所述五个值其中任意一个的计算结果使判定为真，则接受该直线段。

[0036] 根据本发明的第三方面，提供一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机可执行指令，所述计算机可执行指令被处理器执行时实现如第二方面所述的方法中的步骤。

[0037] 相对于现有技术，本发明提供的一种基于梯度方向约束的边缘跟踪直线段快速检测装置及方法，首先在细化的边缘图像上，利用梯度方向约束的边缘跟踪算法进行直线段的快速扫描和提取；然后对初步得到的直线段进行基于背景反例模型的有效性判定，剔除无效的检测结果，得到最终的直线段集合。本发明对常见真实场景图片进行直线段检测的速度比目前经典的高性能算法提高了接近1倍，而且对不同的图像尺度和对比度水平的适应能力更强，更能满足各种视觉检测系统对直线段检测性能和实时性的要求。

附图说明

[0038] 图1是本发明一实施例中基于梯度方向约束的边缘跟踪直线段快速检测方法的流程图。

[0039] 图2是本发明一实施例中正确跟踪方向的示意图。

[0040] 图3是本发明一实施例中错误跟踪方向的示意图。

[0041] 图4是本发明一实施例中梯度切向的示意图。

[0042] 图5是本发明一实施例中两条线段角度相差小于阈值τ的示意图。

[0043] 图6为本发明一实施例中线段分割的示意图。

具体实施方式

[0044] 在以下的叙述中，为了使读者更好地理解本申请而提出了许多技术细节。但是，本领域的普通技术人员可以理解，即使没有这些技术细节和基于以下各实施方式的种种变化和修改，也可以实现本申请各项权利要求所要求保护的技术方案。

[0045] 为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明的实施方式作进一步地详细描述。

[0046] 实施例1

[0047] 本发明实施例1提供了一种基于梯度方向约束的边缘跟踪直线段快速检测装置。下面对本实施例的实现细节进行具体的说明，以下内容仅为方便理解提供的实现细节，并非实施本方案的必须。本实施例1包括：

[0048] 单像素边缘图像获取模块，用于获得图像的单像素的边缘点；

[0049] 直线段提取模块，用于根据梯度的约束，连接至少是相邻的所述边缘点，获得直线段；

[0050] 曲线分割模块，用于判断得到的初始直线段是否应作为曲线段而被分割为多个直线段；以及

[0051] 验证模块，用于进行直线段判定，剔除虚假直线段。

[0052] 由此，本发明实施例把基于梯度方向约束的边缘跟踪直线段快速检测的实现提供了结构上的保证。

[0053] 实施例2

[0054] 本发明实施例2提供了一种深度图人像边缘优化处理装置。下面对本实施例的实现细节进行具体的说明，以下内容仅为方便理解提供的实现细节，并非实施本方案的必须。本实施例中，具体包括：

[0055] 单像素边缘图像获取模块至少具备如下功能：

[0056] （1.1）能够采用7×7的高斯核对图像进行平滑滤波，然后采用3阶Sobel算子对其进行梯度计算。

[0057] （1.2）在得到图像梯度后，对其幅度进行阈值化处理以得到图像中仅包含边缘信息的像素集合，即边缘图像。小梯度幅值点往往出现在平滑区域，其存在往往会严重影响梯度方向的计算，从而导致错误的梯度方向。对于这些像素点，无论是利用梯度幅度信息还是方向信息都已无法准确从其中检测出边缘信息，反而可能导致虚假的检测结果，因而在本发明中予以剔除。为此，单像素边缘图像获取模块采用如下梯度幅值阈值来完成：

[0058]                                     (1)

[0059] 式中：ρ为梯度幅值阈值，q为在256级灰度量化中可能带来的最大灰度级误差，τ表示允许的梯度方向最大误差，所有梯度幅值小于该阈值的图像点在后续的处理过程中将被忽略。

[0060] 在一个具体例子中，可以取q=2，τ=22.5°，这是本发明中推荐的两个经验值，实践表明可以得到比较好的结果。当然，本领域技术人员也可以根据实际情况，灵活设置其他具体值，上述经验值的选择并不作为本发明的特别限定。

[0061] （1.3）进一步的，边缘跟踪在单像素边缘上进行能得到更好的结果，因而在进行了梯度计算和阈值化以后，单像素边缘图像获取模块还可以对得到的结果沿梯度方向进行非极大值抑制处理以得到细化的边缘。经过非极大值抑制，仅有那些在自己梯度方向上是局部最大值，即梯度幅值比前面和后面的该像素点都大的像素点被保留下来，其余的像素点将被剔除，从而可以得到单像素的边缘。

[0062] 所述直线段提取模块至少能够利用梯度方向信息对跟踪过程进行约束。当且仅当搜索到的相邻边界点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于一定的阈值τ时才对其进行链接。在一个具体选择中，τ=22.5°。

[0063] 其中两个像素相邻的定义可以采用8邻域方式，梯度切向的定义如图4所示，与梯度方向垂直且指向右侧。

[0064] 具体的，直线段提取模块至少具备如下功能：

[0065] （2.1）线段的延伸方向角在边缘跟踪过程中使用如下公式进行估计：

[0066]                         （2）

[0067] 式中，Gi为第i个点的梯度幅值，θi为第i个点的梯度切向角。若记Gix和Giy分别为第i个点的横向和纵向的梯度值，则有

[0068]                            （3）

[0069] 式(2)中使用梯度幅值进行加权的目的是为了确保显著的边缘点对线段延伸方向的影响更大。每连接一个新的边缘点，就重新估计一次线段延伸方向，直到不再有新的满足方向条件的边缘点为止。

[0070] 考虑到边缘跟踪算法的输出结果对初始选择的种子点有一定的依赖性。对于一个显著的直线边缘段，无论种子点如何选择都将得到相同的跟踪结果。但是，当非直曲线段或折线段被直线段逼近时，种子点选择不同可能会产生不同的跟踪结果。一个比较容易理解的例子是图像中含有圆时，不同的种子点虽然都能将圆分解为若干的线段，但是线段的起点和终点不会一样，因而线段也不一样。

[0071] 发明人进一步研究发现，梯度值越大的边缘点更适合作为种子点。但是，对梯度值进行完全排序是一个时耗性很高的工作，其复杂度一般为O(nlogn) 以上。

[0072] 为此，使得直线段提取模块的功能进一步包括：

[0073] （2.2）对梯度幅度值进行伪排序，以选择种子点：在0和最大梯度幅值之间等间隔的划分若干个等级，每个像素根据其对应的梯度幅值分类到这些等级之中。伪排序完成之后，种子点从梯度值最高的等级开始选择，依次往下，直至遍历所有等级。

[0074] 在本发明实施例的伪排序时，选择的等级数量为1024，对于256级的灰度图像，1024个等级的伪排序结果与完全排序结果的差别已经不大，因而不必使用更多的等级。当然，如若选择更多的等级，也是可以的。

[0075] 对于曲线分割模块，考虑的是虽然本发明中加入了梯度方向约束，但是对于图5中这种两条线段角度相差小于阈值τ的特殊情况，或者是一段曲率半径很大的曲线段（如图6），算法仍然不能区分。为此，在连接过程结束之后仍然需要对输出结果进行分割。曲线分割模块在分割时的具体过程如下：如果在距离连接两个端点的直线最远处将边缘段断开得到的两个边缘段中任何一个比原边缘更为显著则执行该分割；重复进行以上步骤，直到分割后不能得到更为显著的边缘段，或者分割后所得的两个边缘段所包含的像素数量均小于某个设定的阈值TL，例如，在本发明实施例中TL中选为6个像素，此外，阈值TL还可以是其他值，例如2 10个像素等等。
~

[0076] 如图6所示，符合分割条件的边缘段AB将在点C断开，得到新边缘段AC和CB。

[0077] 对于所述验证模块，进行直线段判定检测，其可以统计候选直线段上相位方向和所拟合的直线方向近似垂直的边缘点数量，由此虚假直线段的剔除问题可转化为判断其是否为非结构的背景噪声假设下的例外。

[0078] 由于实际图像上的几何结构（包括线段）都要在一定的背景区域内才能展现出来，因而为实现上述判定，为每条线段选择一个局部背景区域，也就是直线支撑区域。本发明实施例中的验证模块将该区域一般选择为矩形，矩形的中心选择为线段上所有点的加权平均，主方向为所有点的加权分布的协方差矩阵的最大特征值对应的特征向量所在的方向，其中每个点的权值为其梯度幅度。矩形的长度和宽度分别选择为使矩形刚好能够完全覆盖对应线段上所有的点时的值。此外，计算出的矩形中心和主方向也作为沿矩形主方向通过其中心的直线段的拟合结果。

[0079] 进一步的，验证模块可以假设背景模型为白噪声模型，也即图像中每个像素点的相位方向在[0, 2π]内满足独立均匀随机分布，图像上灰度变化平缓的区域认为符合这种假设，有效直线段则是相位方向高度一致的区域，否则就应该是虚假直线段，在N×M 的图像中，所有可能的直线数量为 C(N×M，2) 条，直线支撑区域的宽度在从1到N之间变化，所2.5
有可能的直线支撑区域数量为 (N×M) ；产生特定的直线支撑区域中图像点相位方向分布情况的虚警数为

[0080]                  （4）

[0081] 式中：n表示直线支撑区域中的总点数，k表示直线支撑区域中与直线方向一致的点数，p由角度阈值决定。在一个具体的例子中，角度阈值选择为22.5°，则对应的p= 22.5/180 = 1/8。图像点的局部主方向设为其梯度切向。NF≤ε的直线段被接受，NF>ε的直线段被作为虚假直线段剔除，ε为根据经验设定的阈值。

[0082] 需要注意的是，在这一步的计算当中，那些在非极大值抑制过程中被剔除的点也参与数量统计，这是因为背景反例模型需要利用大部分的像素点——但是在阈值化过程中被判定为噪声的像素点除外——的相位信息来进行判定。

[0083] 实际上，本发明的检测结果对阈值ε的依赖性是非常弱的，因而直接取ε为一固定值即可满足绝大多情况下的需要，ε的取值例如为0.01 1，例如0.05、0.1、0.5等。~

[0084] 对于一条潜在的直线段，表征直线支撑区域的矩形参数以及p值的选取都有可能影响到NF的计算结果，因此为了尽可能不出现漏检情况还需要进行更周密的判定过程。考虑到本算法提取出潜在直线段的过程，对矩形的长度进行调整有可能破坏曲线段分割的效果，因而我们选择通过调整矩形宽度进行进一步的判定。在一条候选直线段被剔除之前，以1个像素为步长逐步增加其支撑矩形的宽度并重新进行NF的计算，直至判定结果为真或达到设定的最大容许宽度TW，例如，本发明实施例中TW选为4个像素，可以理解的是，还可以是其他值，本发明对此并不做特别限定。若判定结果始终为假，则保留使NF值最小的宽度值用以通过调整p 值进行进一步的判定。需要说明的是，候选直线段是从单像素边缘中得到的，因而减小矩形宽度没有意义。

[0085] 由于p值的大小直接对应角度阈值的大小，增加p值虽然倾向于使NF变小，但同时增加了角度阈值，相当于放松了梯度方向的约束。但是，对于结构性很好的线段，小的p值反而能够得到更小的NF，因而为了确保结构性好的线段不被错误剔除，在完成支撑矩形宽度调整之后，对每条候选线段除p外依次再取p/2、p/4、p/8、p/16和p/32五个值进行NF的计算，若所述五个值其中任意一个的计算结果使判定为真，则接受该候选直线段。

[0086] 实施例3

[0087] 本发明实施例3提供了一种基于梯度方向约束的边缘跟踪直线段快速检测方法。下面对本实施例的实现细节进行具体的说明，以下内容仅为方便理解提供的实现细节，并非实施本方案的必须。本实施例的示意图可参考图1，包括：

[0088] （1）获得图像的单像素的边缘点；

[0089] （2）根据梯度的约束，当且仅当搜索到的相邻边缘点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于阈值时才对相邻边缘点进行连接，获得直线段；

[0090] （3）对得到的初始直线段，即边缘段，求出其两个端点间的距离l与边缘段上的各点到连接两个端点的直线间的最大距离d之间的比值，该比值表征该边缘段作为直线的显著程度，判断该边缘段是否应作为曲线段而被分割为多个直线段；以及

[0091] （4）进行直线段判定，剔除虚假直线段。

[0092] 本方法在保证检测性能的前提下，运算效率相对LSD等传统算法具有明显的改善。

[0093] 实施例4

[0094] 本发明实施例4提供了一种基于梯度方向约束的边缘跟踪直线段快速检测方法，并且可以是在实施例3的基础上进一步优化，其中，相同或相似的部分省略其描述。下面对本实施例的实现细节进行具体的说明，以下内容仅为方便理解提供的实现细节，并非实施本方案的必须。本实施例的示意图可参考图2-4，包括：

[0095] LSD算法算法使用一种2×2的简单模板进行梯度计算，对于相位编组类算法可以满足要求，但是对于边缘跟踪类算法则难以保证梯度计算精度。此外使用该模板计算输出的梯度在位置上是位于(x+0.5，y+0.5)处，必须在后面的过程中对该偏差进行补偿。

[0096] 于是在本发明实施例中，对于步骤（1），具体包括：

[0097] （1.1）采用7×7的高斯核对图像进行平滑滤波，然后采用3阶Sobel算子对其进行梯度计算。

[0098] （1.2）得到图像梯度后，对其幅度进行阈值化处理以得到图像中仅包含边缘信息的像素集合，即边缘图像。小梯度幅值点往往出现在平滑区域，其存在往往会严重影响梯度方向的计算，从而导致错误的梯度方向。对于这些像素点，无论是利用梯度幅度信息还是方向信息都已无法准确从其中检测出边缘信息，反而可能导致虚假的检测结果，因而在本发明中予以剔除。为此，采用如下梯度幅值阈值来完成：

[0099]                                     (1)

[0100] 式中：ρ为梯度幅值阈值，q为在256级灰度量化中可能带来的最大灰度级误差，τ表示允许的梯度方向最大误差，所有梯度幅值小于该阈值的图像点在后续的处理过程中将被忽略。

[0101] 在一个具体例子中，可以取q=2，τ=22.5°，这是本发明中推荐的两个经验值，实践表明可以得到比较好的结果。当然，本领域技术人员也可以根据实际情况，灵活设置其他具体值，上述经验值的选择并不作为本发明的特别限定。

[0102] （1.3）进一步的，边缘跟踪在单像素边缘上进行能得到更好的结果，因而在进行了梯度计算和阈值化以后，还可以对得到的结果沿梯度方向进行非极大值抑制处理以得到细化的边缘。经过非极大值抑制，仅有那些在自己梯度方向上是局部最大值，即梯度幅值比前面和后面的该像素点都大的像素点被保留下来，其余的像素点将被剔除，从而可以得到单像素的边缘。

[0103] 在本发明实施例中，对于步骤（2），边缘跟踪是由梯度图中的一个边缘点出发，依次搜索并连接相邻的边缘点从而逐步检测出图像边缘的一种方法。但是通常仅仅利用了梯度的幅值信息而没有利用其相位(方向)信息，同时也没有利用已经检测到的边缘点的分布信息。因而在边缘跟踪的过程中不能保证跟踪方向的稳定，从而可能导致一些不合理的检测结果。如图2所示，对于图2中的情况理想的检测结果应该如图2中箭头所示，但是实际的检测结果则还有可能如图3中箭头所示，其决定因素为所选择的邻域遍历顺序，例如逆时针方向输出图2中的结果，顺时针方向输出图3中的结果。

[0104] 在本发明实施例中利用梯度方向信息对跟踪过程进行约束。当且仅当搜索到的相邻边界点的梯度切向与已经跟踪到的直线段的延伸方向的差值小于一定的阈值τ时才对其进行链接。在一个具体选择中，τ=22.5°。

[0105] 其中两个像素相邻的定义可以采用8邻域方式，梯度切向的定义如图4所示，与梯度方向垂直且指向右侧。

[0106] 具体的，步骤（2）包括：

[0107] （2.1）线段的延伸方向角在边缘跟踪过程中使用如下公式进行估计：

[0108]                       （2）

[0109] 式中，Gi为第i个点的梯度幅值，θi为第i个点的梯度切向角。若记Gix和Giy分别为第i个点的横向和纵向的梯度值，则有

[0110]                            （3）

[0111] 式(2)中使用梯度幅值进行加权的目的是为了确保显著的边缘点对线段延伸方向的影响更大。每连接一个新的边缘点，就重新估计一次线段延伸方向，直到不再有新的满足方向条件的边缘点为止。

[0112] 边缘跟踪算法的输出结果对初始选择的种子点有一定的依赖性。对于一个显著的直线边缘段，无论种子点如何选择都将得到相同的跟踪结果。但是，当非直曲线段或折线段被直线段逼近时，种子点选择不同可能会产生不同的跟踪结果。一个比较容易理解的例子是图像中含有圆时，不同的种子点虽然都能将圆分解为若干的线段，但是线段的起点和终点不会一样，因而线段也不一样。

[0113] 发明人进一步研究发现，梯度值越大的边缘点更适合作为种子点。但是，对梯度值进行完全排序是一个时耗性很高的工作，其复杂度一般为O(nlogn) 以上。

[0114] 为此，本步骤（2）进一步包括：

[0115] （2.2）对梯度幅度值进行伪排序，以选择种子点：在0和最大梯度幅值之间等间隔的划分若干个等级，每个像素根据其对应的梯度幅值分类到这些等级之中。伪排序完成之后，种子点从梯度值最高的等级开始选择，依次往下，直至遍历所有等级。

[0116] 在本发明实施例的伪排序时，选择的等级数量为1024，对于256级的灰度图像，1024个等级的伪排序结果与完全排序结果的差别已经不大，因而不必使用更多的等级。当然，如若选择更多的等级，也是可以的。

[0117] 对于步骤（3），考虑的是虽然本发明中加入了梯度方向约束，但是对于图5中这种两条线段角度相差小于阈值τ的特殊情况，或者是一段曲率半径很大的曲线段（如图6），算法仍然不能区分。为此，在连接过程结束之后仍然需要对输出结果进行分割。分割的具体过程如下：如果在距离连接两个端点的直线最远处将边缘段断开得到的两个边缘段中任何一个比原边缘更为显著则执行该分割；重复进行以上步骤，直到分割后不能得到更为显著的边缘段，或者分割后所得的两个边缘段所包含的像素数量均小于某个设定的阈值TL，例如，在本发明实施例中TL中选为6个像素，此外，阈值TL还可以是其他值，例如2 10个像素等等。~

[0118] 如图6所示，符合分割条件的边缘段AB将在点C断开，得到新边缘段AC和CB。

[0119] 经过上述操作，我们就完成了基本的直线段检测算法。虽然其间也采取了方向约束和曲线段分割等措施确保算法只输出直线段，但是实验结果表明其在纹理复杂的图像区域仍会检测出一些虚假直线段，因而还需要进一步的判定和剔除。

[0120] 在本发明实施例中，对于步骤（4），进行直线段判定检测，可以统计候选直线段上相位方向和所拟合的直线方向近似垂直的边缘点数量，由此虚假直线段的剔除问题可转化为判断其是否为非结构的背景噪声假设下的例外。

[0121] 由于实际图像上的几何结构（包括线段）都要在一定的背景区域内才能展现出来，因而为实现上述判定，为每条线段选择一个局部背景区域，也就是直线支撑区域。该区域一般选择为矩形，矩形的中心选择为线段上所有点的加权平均，主方向为所有点的加权分布的协方差矩阵的最大特征值对应的特征向量所在的方向，其中每个点的权值为其梯度幅度。矩形的长度和宽度分别选择为使矩形刚好能够完全覆盖对应线段上所有的点时的值。此外，计算出的矩形中心和主方向也作为沿矩形主方向通过其中心的直线段的拟合结果。

[0122] 进一步的，假设背景模型为白噪声模型，也即图像中每个像素点的相位方向在[0, 2π]内满足独立均匀随机分布，图像上灰度变化平缓的区域认为符合这种假设，有效直线段则是相位方向高度一致的区域，否则就应该是虚假直线段，在N×M 的图像中，所有可能的直线数量为 C(N×M，2) 条，直线支撑区域的宽度在从1到N之间变化，所有可能的直线支撑区域数量为 (N×M)2.5；产生特定的直线支撑区域中图像点相位方向分布情况的虚警数为[0123]         （4）

[0124] 式中：n表示直线支撑区域中的总点数，k表示直线支撑区域中与直线方向一致的点数，p由角度阈值决定。在一个具体的例子中，角度阈值选择为22.5°，则对应的p= 22.5/180 = 1/8。图像点的局部主方向设为其梯度切向。NF≤ε的直线段被接受，NF>ε的直线段被作为虚假直线段剔除，ε为根据经验设定的阈值。

[0125] 需要注意的是，在这一步的计算当中，那些在非极大值抑制过程中被剔除的点也参与数量统计，这是因为背景反例模型需要利用大部分的像素点——但是在阈值化过程中被判定为噪声的像素点除外——的相位信息来进行判定。

[0126] 实际上，本发明的检测结果对阈值ε的依赖性是非常弱的，因而直接取ε为一固定值即可满足绝大多情况下的需要，ε的取值例如为0.01 1，例如0.05、0.1、0.5等。~

[0127] 对于一条潜在的直线段，表征直线支撑区域的矩形参数以及p值的选取都有可能影响到NF的计算结果，因此为了尽可能不出现漏检情况还需要进行更周密的判定过程。考虑到本算法提取出潜在直线段的过程，对矩形的长度进行调整有可能破坏曲线段分割的效果，因而我们选择通过调整矩形宽度进行进一步的判定。在一条候选直线段被剔除之前，以1个像素为步长逐步增加其支撑矩形的宽度并重新进行NF的计算，直至判定结果为真或达到设定的最大容许宽度TW，例如，本发明实施例中TW选为4个像素，可以理解的是，还可以是其他值，本发明对此并不做特别限定。若判定结果始终为假，则保留使NF值最小的宽度值用以通过调整p 值进行进一步的判定。需要说明的是，候选直线段是从单像素边缘中得到的，因而减小矩形宽度没有意义。

[0128] 由于p值的大小直接对应角度阈值的大小，增加p值虽然倾向于使NF变小，但同时增加了角度阈值，相当于放松了梯度方向的约束。但是，对于结构性很好的线段，小的p值反而能够得到更小的NF，因而为了确保结构性好的线段不被错误剔除，在完成支撑矩形宽度调整之后，对每条候选线段除p外依次再取p/2、p/4、p/8、p/16和p/32五个值进行NF的计算，若所述五个值其中任意一个的计算结果使判定为真，则接受该候选直线段。

[0129] 相应地，本发明的其他实施方式还可以提供一种计算机可读存储介质，其中存储有计算机可执行指令，该计算机可执行指令被处理器执行时实现本申请的各方法实施方式。计算机可读存储介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括但不限于，相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。

[0130] 需要说明的是，在本专利的申请文件中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。本专利的申请文件中，如果提到根据某要素执行某行为，则是指至少根据该要素执行该行为的意思，其中包括了两种情况：仅根据该要素执行该行为、和根据该要素和其它要素执行该行为。多个、多次、多种等表达包括2个、2次、2种以及2个以上、2次以上、2种以上。

[0131] 在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。