遥感图像中基于Hough变换的直线提取算法

邢坤 何红艳 岳春宇 周楠

（北京空间机电研究所，北京100094）

0 引言

在遥感图像中，人工目标往往具有比较规则的直线特征，对目标的识别和定位起到关键作用[1]，但是景物与成像条件的限制会加大提取直线特征的难度[2]。现有的直线提取方法主要分为两类：一是基于图像域的直线提取方法。该方法的主要思想是直接在图像空间中对图像的梯度或灰度等信息进行处理，分割成很多短的近似位于同一直线上的离散直线段（discrete line segments，DLS），然后通过一定的规则将这些DLS进行合并，相位编组法[3]和启发式连接法[4]都是基于该思想。此类方法的特点是局部性好，能够保持良好的边缘特性，但对噪声敏感，易产生断裂的直线，很难保证结果的全局最优。二是基于变换域的直线提取方法，是在图像的变换域空间中对图像进行间接处理，如 Hough变换[5-6]和 Radon变换[7]，其特点是全局性好，能够处理由于噪声或其它原因导致图像边界部分丢失的情况，但其参数的离散化导致结果不精确，分布效应容易产生虚假直线；此外难以确定直线的端点和长度，算法比较耗时。文献[8-12]对上述两类方法进行了一定改进，但缺陷依然存在。

本文提出一种新的算法，在保持Hough变换全局性好的基础上加以改进，结合图像域处理的优点，提取直线特征。改进方案的特点如下：

1）对边缘图像采用八方向链码法编码，根据新设计的算法快速提取类直线，既完整检测到了Hough变换所使用的直线上的特征点，又降低了计算量；

2）算法对图像空间的每条类直线分别进行 Hough变换，改进投票过程的映射方式，寻找类直线中最多特征点所在的那条直线，只取一个投票峰值，既减小了计算复杂度和空间复杂度，又去掉了虚假峰值的影响；

3）对累加器中的特征点进行动态融合和分组，确定线段的端点，不用像许多算法那样从参数空间反变换回图像空间确定线段的端点；

4）根据变换得到的直线参数以及端点坐标，判定直线之间的位置关系，为下一步的目标识别做好准备。

1 基于类直线提取的改进Hough变换

1.1 初步提取类直线

对二值图像直接进行Hough变换，不同直线的边缘点会互相干扰，影响准确性，另外遥感图像的大信息量也影响Hough变换的运算速度。本文在Hough变换之前初步提取一些曲线，既约束了Hough变换所使用的直线上的特征点，改进了直接进行Hough变换时不同直线的特征点互相干扰的缺点，又降低了计算量。这些曲线保留有直线的信息，可以拟合为一条直线，所以本文定义为类直线。一些经典的直线跟踪算法如Freeman链码和启发式链接，从纯理论角度讲，这些跟踪算法是准确的和严格的，但是实际应用起来总是有差距。比如，数字图像中机场跑道边缘上的点由于像元的关系不是严格地沿直线分布，另外边缘图像中存在许多拐点，这些拐点并不是单像素分布，进而影响了直线的跟踪。文献[13]设计了一种卡尔曼滤波的基于方向预测的跟踪算法提取直线，但比较复杂，计算效率差，生成许多无意义直线段，不适于结合Hough变换使用。

本文根据链码的思想设计了一种算法快速提取类直线。链码法的基本思想是分析相邻点的方向关系。对每个图像点，相邻点用接续方向来代表方向编码，定义八方向链码如图1所示。从上一个点移到下一个点，一定对应8个基元之一，这是因为每个像素的8个相邻像素的方向及距离，恰恰与链码的8个基元的方向及长度一致。这样，位于坐标系内的曲线便可以由一个数字序列来表示。设扫描边缘图像的顺序是从下往上，则本文定义遍历一条类直线必须进行三个方向的移动，即0、1、2方向，或者1、2、3方向，或者2、3、4方向。

图1 八方向链码Fig.1 8-direction chain coding

定义 Lm表示检测的第 m (m ≥ 1) 条类直线，表示第m条类直线点组成的空间， Lm(num)表示第m条类直线的像素个数，定义 T1为提取类直线中的长度阈值，它规定了类直线提取的最少像素数目，本文设计的扫描类直线的步骤如下：

1）记录图像中的每个边缘点相对于相邻边缘点的链码方向（由于边缘并不完全是单像素连接，一些点可能包括多个方向）；

2）抽取步骤1）中链码方向含有0、1、2的边缘点组成一幅新的边缘图像，扫描新图像中的边缘点，把互相连通的像素进行聚类标记，每个标号相同的聚类构成一条类直线，记录像素坐标，存入，判断 Lm(num)，把阈值小于 T1的类直线记录删掉；

3）抽取步骤1）中链码方向含有1、2、3的边缘点组成一幅新的边缘图像，扫描新图像中的边缘点，把互相连通的像素进行聚类标记，记录类直线的步骤同2）；

4）抽取步骤1）中链码方向含有2、3、4的边缘点组成一幅新的边缘图像，扫描新图像中的边缘点，把互相连通的像素进行聚类标记，记录类直线的步骤同2），但记录像素坐标的顺序从下往上、从右往左；

5）根据各步骤提取的类直线形成类直线图像。

上述步骤中的连通像素聚类常用的方法有扫描法和区域生长法，其中扫描法又分一次扫描法和两次扫描法。一次扫描法是在传统的两次扫描法基础上予以改进，将递归思想和重复扫描方式结合起来，通过一次扫描完成连通区域标记；两次扫描法的思想是对图像按一定的顺序两次逐行逐列逐像素的扫描，第一次扫描时，将临时标记存储在一个与图像一样大小的二维数组中并形成等价关系对，第二次扫描时，通过一定的搜索和处理方式对等价关系对进行处理。两次扫描法因为速度优势成为现在研究的热点，并且也证明是速度最快的标记方法。

本文在两次扫描法的基础上针对带有链码值的边缘图像设计标记算法，算法只需要一次逐行逐列逐像素扫描，不需要二次扫描处理等价关系的点。以上述链码方向含有0、1、2的边缘点组成的边缘图像为例，算法步骤为：对图像进行从左到右、从下到上逐行逐列逐像素的扫描，假设扫描当前点A点为特征点，对A点4、5、6方向的点进行判断，若4、5、6方向的点都是非特征点，则A点标记为新的一条类直线的起始点，记录像素坐标，存入；若4、5、6方向有特征点，则把A点标记为与上述特征点相同类直线上的点，记录像素坐标，存入。因为图像是链码方向含有 0、1、2的边缘点组成一幅新的边缘图像，邻域连接只可能如图2所示的8种单元，按从左到右扫描，所以不会出现4、5、6方向的点标记值不一样的情况，所以不需要二次扫描处理等价关系的点。同理，链码方向含有1、2、3的边缘点组成的边缘图像，考虑邻近点5、6、7方向的点像素值；链码方向含有2、3、4的边缘点组成的边缘图像，考虑邻近点0、6、7方向的点像素值。

图2 邻域连接单元Fig. 2 Neighborhood connection unit

1.2 改进Hough变换投票过程

在算法执行之前，定义2T为全局阈值，表示图像坐标系下的长度；3T为累加器阈值，表示累加个数；定义δ为局部距离阈值，同样是图像坐标系下的长度。对第m条类直线 Lm(x,y)执行改进Hough变换的描述如下：

若

4）重复步骤1）～3），直到所有符合要求的点对计算完毕，是计数器中的最大值，若

成立，则认为该计数器对应累加器中的点为实际存在的直线，投票完成。

1.3 线段融合

1）累加器合并，比较各累加器中的(R,θ)值，满足式（7）可认为和确定的两条直线为同一条直线，两个累加器中元素合并，其中Δθ和ΔR为参数空间的量化值，一般分别取1。

2 实验分析

仿真实验的硬件环境为3.00GHz Pentium(R)、内存2Gbyte的微机，在Windows XP平台上Visual C++编程实现。

用某机场遥感图像测试改进的直线提取算法的过程（如图3所示）。图3（a）为原始图像，大小600×800像素，5m分辨率；图3（b）为Canny算子提取边缘结果；图3（c）为提取类直线结果，长度阈值1T为20；图3（d）为本文改进Hough变换算法提取直线的最终结果，其中阈值δ为1，2T为10，3T为30。图3（d）中机场跑道轮廓的主要直线特征基本上被检测出来，边缘线段损失少，线段细节清晰、连续，同时也保持了较高的定位精度。图3（e）是在图3（d）的基础上按照KHT[12]的思想改进Hough变换，然后加入端点判定提取直线特征的结果。KHT使用椭圆核函数和高斯分布优化投票过程，但根本上仍然是“一对多”映射。图3中可以看出虽然主要的直线特征也被提取出来，但是图像空间的大量边缘没有必要都进行Hough变换的投票过程。

图3 机场目标直线提取Fig.3 Airport line segments extraction

表1显示了图3各步骤的运行时间。相对于传统的Hough变换本文算法由于加入了提取类直线这一步骤，不仅减少了其它直线上特征点的干扰，而且不需考虑投票峰值的影响，对于得到线段的端点坐标和长度等参数非常重要。根据同一直线上的特征点计算出的ρ仅在很小的范围内变化，δ的设置进一步减少了噪声点干扰。许多对Hough变换的改进算法在投票过程中都是“一对多”映射，需要在整个参数空间内建立累加器，而本文算法将同一直线上的特征点映射到参数空间的一个点，建立有限个动态累加器，空间复杂度大大减少。从计算复杂度来说，不需要计算每个特征点生成参数空间特征曲线，仅需判断特征点是否在直线上；另外还有一些细节减少算法的计算复杂度，如从类直线特征点空间中选取的两个特征点相距一定的距离、对累加器中的特征点进行动态融合和分组等，所以在时间上比 KHT算法具有优势。

表1 机场目标直线提取运算时间比较Tab. 1 Runtime of airport line segments extraction

改进Hough变换提取直线特征算法不仅适用于机场目标，对其它大型人工目标的直线特征同样使用。图4显示了遥感图像某港口目标直线特征提取过程，其中图4（a）为原始图像，368×295像素，图4（b）为Canny算子提取边缘结果，图4（c）为提取类直线结果，长度阈值1T为40，图4（d）为本文算法提取直线的结果，直线数目是10，其中阈值δ为1，2T为10，3T为30，可以看出图中港口轮廓的主要直线特征基本上被检测出来。图4（e）同样是边缘检测后按照KHT算法提取直线的结果，由于算法使用高斯核卷积去除参数空间的虚假峰值，导致相邻的平行直线也被去除。表2显示了上述步骤的运算时间，实验表明本文算法整体上性能优于KHT算法。

图4 港口目标直线特征提取Fig.4 Harbor line segments extraction

表2 港口目标直线提取运算时间Tab. 2 Runtime of harbor line segments extraction

下面来讨论阈值 T1，T2和 T3对算法结果的影响。T1直接影响后续算法的效率和结果，如果设置过小，达不到初步提取类直线的效果，如果设置过大，则会造成边缘丢失。根据大量实验，一般将阈值 T1设置为目标长度的110～15。表3显示了对图3进行Canny算子边缘检测后，在保证不影响最后直线特征提取效果的前提下，不同 T1取值对算法处理时间的影响。可以看出 T1取值对初步提取类直线的影响不大，但随着取值的增大而逐渐减少改进Hough变换算法的运行时间，直到初步提取类直线的条数固定，改进Hough变换运行时间稳定。 T2是全局距离阈值，根据实验一般设为。是累加器阈值，在数值上基本等于 T1，也可以使用另一种设置方式——取整幅图像中累加器阈值最大的几条直线。 T2和 T3对改进Hough变换算法运行时间影响不大。

表3 不同 1T取值的算法运行时间Tab. 3 Runtime with different1T

3 结束语

针对大型目标的直线特征提取问题，本文提出了一种基于类直线提取的改进Hough变换算法。首先从图像中提取类直线，保持边缘特性的同时也检测到了Hough变换所需要的特征点；然后对每条初步提取的类直线分别进行Hough变换，改进投票过程，设置一维参数空间进行映射，从类直线中寻找最多特征点对应的那条直线，只取一个峰值，减少峰值扩散和虚假峰值的影响，动态确定线段的端点。理论分析和实验表明，本文提出的方法简单高效，可为遥感影像的识别、配准和导航等提供良好的预处理手段。

References)

[1]杨萍, 姜志国, 刘滨涛. 一种遥感图像建筑物检测新方法[J]. 航天返回与遥感, 2013, 34(5): 70-77.YANG Ping, JIANG Zhiguo, LIU Bintao. A New Approach to Building Detection in Remote Sensing Images[J]. Spacecraft Recovery and Remote Sensing, 2013, 34(5): 70-77. (in Chinese)

[2]陈世平. 景物和成像条件对遥感图像品质的影响[J]. 航天返回与遥感, 2010, 31(1): 1-6.CHEN Shiping. The Effects on Remote Sensing Image Quality from Scenes and Imaging Conditions[J]. Spacecraft Recoveryand Remote Sensing, 2010, 31(1): 1-6. (in Chinese)

[3]Burns J, Hanson A, Riseman E. Extracting Straight Lines[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1986, 8(4): 425-455.

[4]Venkateswar V, Chellappa R. Extraction of Straight Lines in Aerial Images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(11): 1111-1114.

[5]徐胜华, 朱庆, 刘纪平, 等. 基于预存储权值矩阵的多尺度 Hough变换直线提取算法[J]. 测绘学报, 2008, 37(1):83-88.XU Shenghua, ZHU Qing, LIU Jiping, etal. Straight Line Extraction via Multi-scale Hough Transform Based on Pre-storage Weight Matrix[J]. 2008, 37(1): 83-88. (in Chinese)

[6]Kalviainen H, Hirvonen P, Xu L, etal. Probabilistic and Non-probabilistic Hough Transforms: Overview and Comparisions[J]. Image and Vision Computing, 1995, 13(4): 239-252.

[7]Li J, Pan Q, Zhang H, etal. Image Recognition Using Radon Transform[C]. The IEEE 6th International Conference on Intelligent Transportation Systerms IV: Image Analysis, Shanghai, China, IEEE Computer Society, 2003, 4: 741-744.

[8]Rowe N C, Grewe L L. Change Detection for Linear Features in Aerial Photographs Using Edge-finding[J]. IEEE Transaction on Geoscience and Remote Sensing, 2001, 39(7): 1608-1612.

[9]Wu F, Schweitzer H. Fast Selection of Linear Features in Image Data[C]. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Washington, DC, USA, 2005, 3: 49-54.

[10]Bonci A, Leo T, Longhi S. A Bayesian Approach to the Hough Transform for Line Detection[J]. IEEE Transaction on Systems, Man and Cybernetics, 2005, 35(6): 945-955.

[11]Bandera A, Perez-lorenzo J M, Bandera J P, etal. Mean Shift Based Clustering of Hough Domain for Fast Line Segment Detection [J]. Pattern Recognition Letters, 2006, 27(6): 578-586.

[12]Fernandes L, Oliveira M. Real-time Line Detection through an Improved Hough Transform Voting Scheme[J]. Pattern Recognition, 2008, 41(1): 299-314.

[13]文贡坚, 王润生. 一种稳健的直线提取算法[J]. 软件学报, 2001, 12(11):1660-1666.WEN Gongjian, WANG Runsheng. A Robust Approach to Extracting Straight Lines[J]. Journal of Software, 2001, 12(11):1660-1666.(in Chinese)