1 引 言

直线是影像上重要的几何信息，能够用于准确描述影像上的线状特征如建筑物、道路等人造物体的形状，被广泛用于影像匹配、建模、分析、解译过程中。因此，直线提取一直是摄影测量和计算机视觉领域的研究热点。

现有直线提取算法主要可以分为以下3类：①Hough变换算法^{[1, 2, 3, 4]}；②基于链码的直线提取算法^{[5, 6, 7]}；③相位编组直线提取算法^[8]，该算法首先依据梯度区域划分，将梯度方向属于同一区域且相邻的像素点编为一组，生成直线支持区，然后利用直线段对支持区内边缘进行拟合。与前两种算法相比，相位编组算法受阈值、噪声影响较小，因此被广泛应用于道路提取^{[9, 10, 11]}、海天线检测^{[12, 13]}、人手识别^[14]、三维超声图像中针状物体检测^{[15, 16]}等方面。但该算法存在两方面问题：一是在编组过程中，当梯度角接近于区域边界角度时，由于角度分区量化误差，相邻的像素产生交错编组现象，导致提取结果在区域分界线附近产生边缘断裂，分区越多，断裂越多。针对这一问题，相继出现了重置分区算法^[8]、支持区连接算法^[9]、自适应相位分区算法^[17]、最优分区算法^[18]、LSD（line segment detector）算法^{[19, 20]}等。上述算法没有考虑另一方面问题，即曲线边缘直线化。重置分区及连接算法都会增加曲线边缘的概率。重置分区后，对于两种分区方式下具有不同区域编码的像素，将其标记为直线支持区长度较长的区域编码。该过程增大了同一支持区内梯度方向差，会使部分拟合直线和原边缘之间存在较大的距离。

针对现有相位编组算法存在的两方面问题，本文提出一种叠置分区辅助的相位编组直线提取算法。该算法通过两次四分区划分生成交互重叠的八分区，解决了区域分界线处直线提取的断裂问题，后续通过相互连接的直线段对支持区内边缘进行拟合，实现以直代曲的过程，特别对于曲线边缘，可以得到较好的拟合效果。

如图 1所示，首先利用Canny算子对影像进行边缘检测，采用Sobel算子3×3模板计算各边缘像素梯度方向，然后通过两次分区的相位编组算法实现直线提取。设定一次分区区域范围，并设定二次分区分界线与一次分区的区域中心线重合。依据一次分区原则，将各个像素按梯度方向进行编码，对编码后的边缘像素跟踪生成直线支持区，即对相邻的且编码相同的边缘像素组成边缘组。一次分区后将长度小于阈值的边缘组所包含的像素再依据二次分区原则重新编组生成直线支持区，最后对满足条件的支持区内的边缘进行分裂，提取直线。

图 1 算法流程图 Fig. 1 Flow chart of the proposed algorithm

图选项

利用Sobel算子计算得到边缘像素梯度方向后，将梯度方向的值域按照量化方式分为几个固定区域。通过两次独立分区处理，将0°~360°分为8个交互重叠分区，如图 2所示。具体实现过程如下：

（1） 一次分区：按照图 2所示，首先将0°~360°分等为0°~90°、…、270°~360°等4个区域，每个分区跨度为90°，分别标记为1、2、3、4；对每一个边缘像素，依据梯度方向，判断其属于哪个区域，对其进行相应的区域编码；最后根据编码生成直线支持区，将长度（即像素总数）大于阈值T1的直线支持区用于后续的直线提取，同时，将所有长度小于阈值的直线支持区内的像素点保留，进行二次分区。

图 2 叠置分区 Fig. 2 Overlapped-partition

图选项

（2） 二次分区：将0°~360°等分为315°~45°、…、225°~315°等4个区域，每个分区跨度仍为90°，分别标记为5、6、7、8。二次分区的分界线与一次分区的扇形中心线相重合，与之对应，一次分区的分界线与二次分区的扇形中心线相重合。因此，两次分区的相邻分区存在50%的交互重叠区域。依据二次分区原则，再对一次分区后保留的像素重复之前的操作，判断其属于哪个分区，并进行编码。最后，根据编码生成直线支持区，将长度大于阈值T₂的直线支持区用于后续的直线提取。

一次分区后，影像上梯度方向接近于区域中心的像素，能有效地通过编组得到直线，但梯度方向接近区域分界线的像素，由于量化误差的影响，易发生交错分区现象，因此，很难通过编组生成长的直线支持区，即影像上方向角接近0°、90°、180°、270°直线不能被有效提取，导致连续边缘断裂，直线提取结果存在漏洞。针对这一问题，算法对一次分区后剩余的边缘像素再进行二次分区。鉴于分区编组的直线提取算法对位于区域中心的像素能被有效处理，而剩余的边缘点大都位于一次分区的区域分界线附近，因此，二次分区时，将区域中心线设置与一次分区的分界线相重合，这样能有效保证剩余像素的直线提取效果。例如，依据一次分区划分原则，位于0°附近的连续边缘点，可能会被交错划分到1、4两个区域，而在二次分区这些像素会被划分到第5区域内。综上所述，叠置分区可以有效避免区域分界线处边缘断裂问题。

利用分区后的像素编码对离散的边缘点进行编组，将具有相同编码且相互连接的边缘点进行编组生成直线支持区。该过程借鉴八邻域链码跟踪方法，具体步骤如下：

步骤1：给定i=1，用来标记第i个支持区。

步骤2：建立新的直线支持区L_i。按照从上到下，从左到右的顺序搜索二值图像边缘点。将搜索到第一个边缘点作为起点，添加到支持区L_i中，记录起点的编码值n,（n∈[1, 8]），并将该边缘点的灰度值赋值为0，不再参与后续搜索。转到步骤3；如果搜索不到初始边缘点，转到步骤5。

步骤3：将支持区中最后一个点作为当前点进行跟踪，按顺时针方向搜索当前点八邻域内是否存在编码为n的边缘点。如果不存在，转到步骤4；如果存在，将八邻域内搜索到的第一个编码为n的边缘点增加到支持区，并将该点灰度值赋值为0，不再参与后续搜索。重复步骤3。 步骤4：得到一个直线支持区。令i=i+1，转到步骤2。

步骤5：跟踪结束，共得到i－1个直线支持区。

跟踪后生成的直线支持区实际是由离散像素组成的一条直线或曲线边缘。对于曲线边缘，需要进一步从中提取直线。本文采用文献^{[21, 22]}中的方法对其进行边缘分裂及直线拟合。该方法基本原理是依据边缘曲率对边缘进行迭代分裂，得到若干近似直线元，再对其进行最小二乘拟合。在误差允许的情况下，通过相互连接的直线段逼近曲线，可以较好地拟合原曲线边缘，最终实现以直代曲的过程。

该方法具体实现过程为：假设一曲线边缘L，连接边缘线两端点得到直线l，计算边缘L上每一像素到直线l的距离。如果最大距离d大于给定的阈值d_t，则在距离最大的边缘点处进行分裂。分别将原边缘两端点与分裂点连接，将原边缘分为两段新的边缘，再分别对其进行上述判断，直到所有边缘像素的最大距离d都小于给定的阈值，不再分裂出新的边缘为止。最后采用最小二乘对每一段边缘进行直线拟合。图 3为d_t值取1、2的情况下得到的曲线边缘分裂结果。d_t越小，边缘分裂得到的直线段数目越多，拟合效果越好。一般情况下，当d_t=2时，基本满足要求。

图 3 边缘分裂及直线拟合 Fig. 3 Edge splitting and line fitting

图选项

为了验证本文算法的有效性，分别进行3组试验：首先选用圆形建筑物的航空影像，按本文算法分步操作，得到具体试验结果；然后选取两幅影像，分别采用不同的直线提取算法进行试验，并与本文算法直线提取结果进行对比分析；最后将本文算法应用于噪声影像，验证该算法的抗噪性。

采用本文算法对图 4(a)所示的圆形建筑物的航空影像进行直线提取试验，图像大小为967像素×1054像素。Canny算子边缘检测结果如图 4(b)。本文算法直线提取结果如图 4(c)。其中，红色表示一次分区后直线提取结果。由图 4可以看出，在分界线附近，直线提取结果存在漏洞和断裂。而在扇形中心区域，边缘提取效果较好。在一次分区结果基础上进行二次分区，直线提取结果如图 4(c)中绿色边缘线所示。可以看出，二次分区直线提取结果有效地弥补了一次分区区域分界线处的断裂问题。这是由于二次分区的中心线正好位于一次分区的分界线处，因此可以有效地提取该区域直线特征。两次分区过程中，边缘跟踪生成直线支持区数目共2422个，其中一次分区和二次分区分别为1793和629。对支持区内边缘进行分裂及直线拟合，得到直线数目共2670条，与原影像叠加显示如图 4(d)，直线端点显示如图 4(e)，其中局部方框内结果放大显示如图 4(f)。算法共耗时6.54s。内部参数设置如表 1所示，后续试验过程中参数等同，试验过程中无须进行参数调整。

图 4 本文算法提取直线结果 Fig. 4 Line extraction results by proposed algorithm

图选项

为了验证本文算法的有效性，选取如图 5中所示的两幅影像进行直线提取试验。图 5（a）为近景影像，影像内容单一，包含丰富的曲线特征；图 5（b）为信息量较为丰富的航空影像，其包含丰富的直线特征，影像中包含建筑物，道路、树木等。分别采用Hough变换、链码、相位编组3类直线提取算法中具有代表性的算法对上述两幅影像进行直线提取试验，并与本文算法进行对比分析。原始影像及直线提取结果分别如图 5所示。从左到右依次为原始影像、Canny算子边缘检测结果、传统Hough变换算法^[1]、改进Hough变换算法、文献^[6]算法、BL（blob-based line detection）算法^[7]、文献^[18]算法、Burns算法^[8]、LSD算法^[19]和本文算法的直线提取结果。其中，试验图像及LSD运行结果来自http://www.ipol.im/pub/art/2012/gjmr-lsd/网站。直线提取数目如表 2所示。

图 5 原始影像及不同算法直线提取结果 Fig. 5 Original images and line extraction results by different algorithms

图选项

从试验结果可以看出：传统Hough变换算法提取直线存在严重的过连接问题，得到错误的直线提取结果；改进Hough变换算法结果较为理想，但是由于参数离散化问题，在较长边缘线上，仍存在重复交错产生的虚假直线；文献^[6]算法受限于参数设置，如果严格按照其文献中的参数，仅提取较少数目的直线。本文将其参数固定链码长度值L_t和直线段相似度阈值S_t设置分别为20和0.80，提取直线的数目仍较少，并且由于直线相似度较低使得提取直线里仍存在曲线边缘。该算法参数设置过于固定和苛刻，不利于不同数据类型的灵活处理；BL算法直线提取结果存在断裂问题。这是由于BL算法利用链码跟踪生成的方向码进行约束，其中仅考虑单方向码和相邻两方向码的两种情况，因此受噪声影响较大，不利于曲线边缘提取。同时该算法判据较多，过程较为复杂；文献^[18]算法直线提取结果同样存在严重断裂现象，这是由于该算法最终只选择一种相对最优的固定分区方式进行分区。固定分区方式不能解决分界线处直线提取断裂问题，同时分区越多，断裂越多；Burns算法由于参数设置较严密，提取的直线数目较少，对于影像上直线边缘的提取结果要好于曲线边缘，提取结果中部分相邻的直线端存在交错现象；LSD算法直线提取结果较好，其中图 5（b）直线提取结果优于本文算法，而对于图 5（a）影像而言，本文算法的直线提取结果优于LSD算法。图 6为本文算法和LSD算法直线提取结果叠加显示在原始影像上，并将局部窗口放大显示。其中，红色直线为LSD算法直线提取结果，黄色直线为本文算法直线提取结果。从图中可以看出，本文算法直线提取结果更好地保持了边缘的连续性，拟合效果更佳。

图 6 本文算法同LSD算法直线提取结果叠加显示 Fig. 6 Overlay line extraction results by proposed and LSD algorithms on the test image

图选项

为了验证本文算法的抗噪性，首先对原始影像加入椒盐噪声，参数设置分别为0.02和0.15，然后利用本文算法和其他4种算法分别对原始影像和噪声影像进行直线提取。结果如图 7所示，从左到右依次为试验影像、改进Hough变换、BL算法、Burns算法、LPS算法和本文算法的直线提取结果。不同算法直线提取数目见表 3。从图 7和表 3可以看出，针对该组试验影像，本文算法直线提取结果要优于其他算法。对于图 7（c）的噪声影像，改进Hough变换算法提取结果中存在较多的错误直线，本文算法同其他算法均提取到较少数目的直线，直线提取失败，但是也没有产生错误的直线提取结果。

图 7 对原始影像及噪声影像采用不同算法的直线提取 结果 Fig. 7 Line extraction results by different algorithms for original image and noise image

图选项

叠置分区辅助的相位编组直线提取算法能快速、准确地提取影像上的特征线，尤其对于曲线边缘，该算法也能得到较其他方法更为理想的提取结果。该算法特点可总结如下：

（1） 通过两次四分区生成交互重叠八分区。两次分区独立进行编组生成直线支持区，二次分区利用一次分区编组后剩余的边缘点进行。由于二次分区中心线与一次分区分界线重合，因此二次分区直线提取结果可以有效地弥补一次分区在分界线附近产生的边缘断裂，提高直线提取结果的连续性。

（2） 初始四分区编组增加了每个分区内直线支持区的长度，加大支持区内曲线边缘的概率。本文进一步引入边缘分裂算法，对支持区内边缘进行分裂得到若干近似直线元，再对其进行最小二乘拟合，最终实现以直代曲的过程。

（3） 该算法内置固定3个参数，对于所有的试验影像，都不需要进行参数调整，均能取得理想的直线提取结果，避免了其他直线提取算法参数难以调整，结果受参数影响较大等问题。