1.1 直线提取的研究现状
影像上的特征直线，简称直线（段），也称直线特征，可以看作影像局部区域特征不相同的区域间的分界线，多存在于影像上不同地物或者不同面片之间。影像中的特征直线以规则离散点集的形式存在，直线提取得到的是具有端点的直线段。直线提取是直线匹配的前提。经过多年的研究与发展，诸多学者在直线提取领域取得了丰硕的成果。现有的直线提取算法大体可分为3类［15-16］：基于变换域的直线提取方法、基于边缘连接的直线提取方法、基于梯度信息的直线提取方法。
1.基于变换域的直线提取方法
基于变换域的直线提取方法大多是基于Hough变换［17］进行的，该变换被广泛应用于直线提取和边缘检测。Hough变换利用图像空间和参数空间的点—线对偶性，将图像空间中的直线检测问题转化为参数空间中对点的检测问题，通过在参数空间寻找峰值来完成直线检测。1972年，Duda等人［18］通过改变直线表达式对Hough变换进行改进并推广使用，该方法利用极坐标直线方程代替笛卡儿坐标系下斜率—截距式的直线方程，解决了参数空间取值范围过大或当直线与x轴垂直时斜率不存在的问题，后续将这种方法称为标准Hough变换（Standard Hough Transform，SHT）。该方法几何解析简单，抗噪声干扰能力强，具有可处理局部遮挡、覆盖等优点。Hough变换通过穷举搜索所有可能的直线，将影像空间所有像素点映射到参数空间参与投票获取峰值，该过程属于一种概率事件，这也导致Hough变换用于图像直线提取存在许多问题。例如，参数离散化过大或过小都将导致结果不精确；离散点会增大其在参数空间中的影响力，同时累积峰值分布效应会导致虚假直线产生；参数空间有效峰值难以检测；计算复杂度和空间复杂度较高，尤其对于较大影像，运算速度慢。因此，很多学者对Hough变换方法进行不断改进，半个世纪以来，形成了数以千计的研究论文和大量应用文献，Mukhopadhyay等人［19］和Hassanein等人［20］对这些研究进行了全面综述。除上述标准Hough变换外，多尺度Hough变换（Multi-Scale Hough Transform，MSHT）和累计概率Hough变换（Progressive Probabilistic Hough Transform，PPHT）［21］也是两种经典的Hough变换改进算法。其中，多尺度Hough变换为标准Hough变换在多尺度下的一种拓展；而累计概率Hough变换是标准Hough变换算法的一个改进算法，其利用检测直线段所需的投票点比例的差异，减少在投票过程中使用点的比例，以最小化检测直线段的计算量。
一些研究侧重于增强Hough变换检测的准确性。Ji等人［22］在参数空间中定义了一个局部算子来增大真实线段上的点投票产生的峰值点与噪声点参与投票产生的峰值点之间的差异，通过对局部算子效果的分析，得出增强累积器的全局阈值，实现复杂背景图像中的线段检测。2012年，Tsenoglou等人［23］提出基于区域加权的Hough方法，用于检测建筑物立面直线，该方法利用最小边界矩形来计算各区域对累加器的贡献度，提高了Hough变换的准确率。2014年，王竞雪等人［24］提出结合边缘分组的局部Hough变换直线提取方法，该方法对相邻像素聚类得到的边缘像素组逐一进行局部Hough变换，通过单峰值确定及迭代Hough变换增强了算法的稳健性。2015年，Xu等人［25］将局部峰值区域的每一列看作一个随机变量，非零单元的均值和方差被计算，通过对Hough空间的投票分布进行统计分析，确定拟合统计方差函数的最小值为角度参数θ，结合角度和拟合均值函数确定距离参数ρ，提高了直线提取的可靠性。2017年，Almazan等人［26］提出一种马尔可夫链边缘线段检测器（Markov Chain Marginal Line Segment Detector，MCMLSD）算法，该算法融合了图像感知聚类和全局概率Hough变换的优点，首先利用全局概率变换检测直线，再使用标准动态规划算法精确计算出概率最优解，准确度优于LSD（Line Segment Detector）直线提取算法及EDLines（Edge Drawing Lines）边缘检测算法，但运行效率不高，不适用于实时计算。
此外，还有很多研究致力于降低算法复杂度，提高算法的运行效率。Kiryati等人［27］通过随机选取影像上小子集边缘点进行Hough变换，在检测结果轻微受损的情况下，显著地缩短运行时间。2017年，Yan等人［28］针对传统Hough变换计算效率低的问题，提出GPU并行计算加速Hough变换过程，实现直线特征的快速提取。2018年，刁燕等人［29］提出基于概率的局部Hough变换算法，通过对有序边界和无序边界采用不同的处理方式，大大减少了Hough变换需要的存储空间，加快了运算速度。针对标准Hough变换盲目投票产生的计算消耗，2019年，Luo等人［30］提出一种基于方向性编码的快速直线提取方法，该方法设计一个嗅探器来预测直线的方向，对不同方向的像素点采用不同的处理方式，通过设置角度范围，避免无意义的投票，缩短了算法的执行时间。针对Hough变换的计算复杂性，Novikov等人［31］提出一种基于曲率特征的直线提取方法，该方法认为直线是曲率为零的曲线，即曲线函数在轮廓点处的二阶导数为零，基于这一特性可以采用滑动卷积计算每个像素点的二阶导数来确定轮廓点，并用最小二乘法拟合直线。
2.基于边缘连接的直线提取方法
20世纪60年代，Freeman［32］从链码的角度对边缘像素的跟踪和直线提取进行研究，提出Freeman八方向链码概念和直线链码准则。顾创等人［33］对直线链码准则进行的验证和补充，为基于链码的直线提取提供了强有力的理论基础。这类方法原理简单易懂、运算量小，适合实时处理和局部直线提取。但是由于直线链码准则过于苛刻，如果严格按照直线链码三原则约束直线链码提取，会产生连续边缘的断裂，因此不同的改进方法相继被提出。这些方法主要可分为两类：一类是在链码跟踪过程中，利用直线链码准则加以约束，在多边缘交叉处结合链码跟踪优先级进行判断［34-37］，这类方法受直线链码准则束缚，抗噪性不强，容易造成直线断裂，后续需要进行直线合并；另一类方法是首先通过传统的链码跟踪提取边缘链码，然后对边缘链码进行分裂拟合，如提取角点［38］或提取直线链码段［39-43］，其中，典型的是BL（Blob-based Line Detection）算法［39］，该算法直接利用链码方向约束从初始链码中提取直线链码，对于两个方向码的情况，需要利用点到直线距离进一步验证，算法较为复杂。孙涵等人［41］在已有链码跟踪结果的基础上，从起点开始对链码串逐段进行直线段相似性判断，这种固定长度逐段判断的方法灵活性较差，不具备自适应能力，易产生断裂直线，从而影响直线提取的效果。除上述不同提取策略外，这类方法的直线提取结果直接受限于初始链码跟踪结果。传统链码跟踪过程中易产生连续边缘的断裂，究其原因，主要有以下3个方面：一是在链码跟踪过程中，将每次扫描到的初始边缘像素点作为链码的起点，如果该点不是边缘的起点，则会导致连续边缘的断裂，得到的短边缘会因其长度小于长度阈值而被删除；二是在链码跟踪过程中没有利用边缘方向加以约束，在多边缘交叉处可能会选择非边缘方向进行跟踪，造成连续边缘的断裂；三是现有方法将跟踪过程中扫描到的点设置为非边缘点，后续不再进行扫描，在多边缘交叉处，这个过程会引起其他方向边缘的断裂。针对这个问题，潘大夫等人［40］通过优先选择当前边缘方向上的点，并记录分支点位置，再以分支点为起点进行跟踪，这样就解决了上述第三种情况引起的边缘断裂问题，而对于其他因素引起的断裂，如因屏蔽跟踪点而产生的断裂，后续还需要通过直线合并等方式来避免。针对边缘链码跟踪过程中直线断裂的问题，王竞雪等人［24］对链码跟踪方式做了进一步改进，在链码跟踪过程中，首先记录链码起点，并将其作为下一个链码跟踪的初选点，优先跟踪边缘方向上的点，对当前点先进行八邻域内链码跟踪，在八邻域内链码没有边缘点的情况下，再进行八邻域外链码跟踪。戴激光等人［44］在对Canny算子检测到的边缘点进行边缘细化的基础上，通过端点检测、交叉点跟踪、闭合边缘跟踪方法确保边缘链码提取的完整性。尽管上述方法从不同方面提出了相应的改进方案，但受限于Freeman链码跟踪方式，边缘链码交叉处无法被准确定义，没有其他信息加以约束，使得直线提取结果中易产生断裂直线及虚假直线。
Akinlar等人［45］提出一种新的边缘检测器，ED（Edge Drawing）边缘检测器，与现有边缘检测算子得到的二值图像不同，该检测器可提取得到一系列边缘像素链。结合ED边缘检测器的边缘检测结果及最小二乘线段检测方法，Akinlar等人［46］进一步提出EDLines边缘检测算法用于直线提取。受益于前期快速的边缘检测算法及结果，在与LSD直线提取结果相当的条件下，EDLines边缘检测算法比LSD直线提取算法速度提升了10倍，因而具有较高的直线检测效率。同LSD直线提取算法一致，EDLines边缘检测算法最后采用Helmholtz原理，通过计算误报次数（Number of False Alarms，NFA）来消除检测错误的直线段，实现高效稳健的直线提取。Lu等人［47］提出CannyLines直线提取算法，首先利用无参的Canny算子稳健地提取边缘，然后利用高效的边缘连接及分裂技术集合共线的边缘点，利用最小二乘法拟合初始线段，再通过有效的扩展和合并提取长线段，最后结合梯度信息，根据Helmholtz原理对所有提取的线段进行验证。
3.基于梯度信息的直线提取方法
上述两类基于边缘的方法依赖边缘提取结果的准确性和完整性，然而，在进行图像边缘提取的过程中不可避免地会产生信息损失。为此，Burns等人［48］提出一种直接基于图像梯度的直线段检测思路，即相位编组直线提取算法。与经典的基于边缘的线段检测器相比，该算法计算图像中所有像素点的梯度方向，将相邻且具有相近梯度方向的像素点分为一组，得到线支持域，然后利用相关强度面结构来确定边缘位置和属性，该算法具有很强的稳健性，能准确地识别许多对比不明显的直线，但是对断裂直线的处理效果不佳。之后，Kahn等人［49-50］对该算法进行了改进，使得提取的线段具有良好的局部性，但合适阈值的选择仍然是难点。针对参数阈值难以设定的问题，Desolneux等人［51-52］对此进行了深入的研究，分析在噪声环境下出现错误检测的概率，建立了一种数学模型，用来抑制虚假直线段的出现。Helmholtz准则是其主要理论之一，当候选直线段在噪声环境下的期望值小于某个阈值时，认为其具有感知意义，由此确保在噪声干扰条件下，能够有效地控制误报次数，记录梯度相位与线段大致呈正交分布的点的数量，在反证模型中寻找线段作为非结构化的异常值。基于上述研究，Gioi等人［53］提出具有线性运行时间的线段检测器（Line Segment Detector，LSD），这是一种基于空间的直线提取算法，在反证模型和相位编组直线提取算法的基础上，根据Helmholtz准则将梯度相位和直线验证有效地结合，对初步提取的候选直线段区域进行验证，将错误检测的数量控制在一个较低的水平，提高线段提取的准确性。鉴于LSD具有运行速度快、算法稳健性强、参数能够自适应，并且错误检测率能被有效控制等优点，其可被看作目前直线提取算法的标杆。针对现有直线提取算法在高分辨率图像上易产生过分割的现象，Salaün等人［54］提出多尺度LSD直线提取算法，利用不同尺度的高斯滤波对输入图像进行处理，利用LSD直线提取算法对每个滤波图像进行直线提取，融合多尺度图像的直线提取结果为最终的提取直线。该算法不仅解决了高分辨率图像直线提取过分割问题，保留LSD直线提取算法已有的优势，而且进一步增强了原始LSD直线提取算法的抗噪性和稳健性。类似地，针对高分辨率彩色图像，罗午阳等人［55］提出一种多通道、多尺度的LSD直线提取算法，通过对不同通道、不同尺度下的LSD检测结果进行筛选融合提取直线。
综上，3类直线提取方法对比分析如表1-1所示，第一类基于变换域的直线提取方法，指利用图像空间和参数空间的点线对偶性，通过确定参数空间累积矩阵峰值点确定直线，此类方法有很强的稳定性，能有效抵抗外界不确定因素的影响，但不足之处是计算量大、消耗内存，不适用于实时计算；第二类基于边缘连接的直线提取方法通过链码跟踪或邻域跟踪等方式提取初始链码串或边缘链，在此基础上通过直线拟合获取直线，此类方法原理易懂、操作简单，但易受噪声影响产生断裂直线；第三类基于梯度信息的直线提取方法利用携带直线相关信息较丰富的梯度幅度和相位作为主要的度量，可快速检测出对比度不明显处的特征，该类方法具有提取直线速度快、可实时处理的优势，它所获得的直线提取结果不仅包含直线端点坐标，同时还包含有关于直线的多种属性信息，但缺点是无法抑制噪声干扰，容易产生断裂直线。总之，现有的直线提取方法均试图对图像中所有直线结构特征进行完整提取，以简化图像解译的复杂度及实现地物的完整重构。但受遮挡、成像、复杂背景、强噪声、线状地物灰度差异等因素的影响，数字图像中目视清晰的连续线状结构提取有时仍会出现断裂或漏提取现象，或许通过认知心理学、神经生物学和计算机视觉等多学科交叉来实现直线提取能有所突破。
表1-1 直线提取方法对比分析
