基于改进Hough变换的线性目标检测

张国英，程益钰，朱 红

（中国矿业大学 （北京）计算机系，北京100083）

0 引 言

在遥感影像处理中，线性目标的检测和提取具有重要的地位。在一幅遥感影像中，道路、机场跑道等都是重要的线性地物，因此线性目标提取具有重要的意义。针对如何提取线性目标的问题，现在已经有很多研究，但都有一定的不足。线性目标检测具有代表性的方法主要是聚类方法，代表方法有：朱昌盛等人运用Hough变换，提出基于平行线对的线性目标检测［1］。这类方法具有较强的鲁棒性，在检测直线时，受噪声和曲线间断的影响特别小，其缺点是由于是全搜索，计算量和存储量都很大，不利于实时处理。另外，潘建平等提出的基于数学形态学的线性目标检测方法［2］，许华荣等人的基于最小二乘B样条曲线的线性目标检测［3］，王义敏等的基于区域生长的线性目标检测［4］和Yoshihiko的基于神经网络的线性目标检测［5］。其优点是计算不复杂，处理速度快，缺点在于跟踪边缘时不能处理有间断的直线，边缘检测算法一定程度上制约这类算法的性能。

Hough变换［5－7］是一种用来在卫星影像中提取线性目标边缘特征的简便而有效的方法。其原理是把在图像空间中的直线检测转换到参数空间里对点的检测，通过在参数空间里进行累加统计完成检测任务。检测直线时，对参数空间的二维数组累加统计，得到最大值所对应的第一条直线，然后依次寻找次最大值对应的其他直线，但在这个过程中容易重复检测直线。另外，传统Hough变换算法的处理对象是整幅图像数据，导致计算量和存储量都很大，不利于实时处理。Freeman编码［9，10］是一种描述边界的方法，用边界方向作为编码依据，一般描述的是边界点集，只需保存起点和边界链码，即可描述目标的形态。因此，用Freeman编码描述每个区域目标，大大简化了目标区域，可以节省大量内存空间，并且同时保留了目标的几何形态，在卫星影像中得到大量的使用。根据以上分析，本文以提取平行对线对为原型，分析了Hough变换和Freeman链码提取直线的优缺点，提出了基于Freeman编码的改进Hough变换检测线性目标算法。

改进后的Hough变换算法，其处理对象由整幅影像的数据改为图像分割后各区域的边界链码数据。在寻找图像中直线的时候，删除已找到的直线链码数据，继续寻找后续其他直线，从而避免了重复的直线检测。在检测平行线对之前，对图像进行分割，然后对分割得到的各个区域使用Hough变换，这样就能找出整个影像中所有平行线段，从而完成对所有线性目标的检测。最后，为了验证检测出来的准道路是否为实际道路，设计了平行线对模型算法，来提高提取的正确率。

1 Freeman 编码

Freeman编码是图像处理中最基本的目标描述手段。用不同斜率的8个方向基元来描述轮廓边界，得到的编码即为Freeman编码。对任一闭合区域，从某个起点开始，将边界的走向按Freeman编码的方式记录下来，就形成连续的方向序列即为边界编码。数字化二值轮廓曲线用八方向Freeman链码表示，可以形成n条链，每条链指向8个方向中的一个，即ai∈｛0，1，2，…，7｝。如图1所示，其中i为像素索引值，ai表示由像素 （i）指向像素 （i＋1）的链码方向，最终n条链的曲线链码表示为

式中：S——边界的起点像素，n——边界点的个数。当边界闭合时，会回到起点，S可省略。

图1 Freeman 链码的方向取值

如图2所示的图像轮廓边界，使用Freeman编码表示则为：077666654533212122。

Freeman链码检测直线应满足3 个条件，请参见文献［8］。Freeman检测直线的一般过程是：对图像进行去噪、二值化处理后，使用上述的3个约束条件遍历直线，来完成对直线的初步识别，后续通过直线段的合并操作能较好地检测出直线段，不过该算法对噪音较敏感。

2 算法流程

图2 闭合边界的Freeman编码

本文算法以平行线特征为依据，检测卫星影像中线性目标主要按以下几个步骤进行。首先对采集到的遥感影像进行平滑滤波预处理消除椒盐噪声，然后通过以灰度一致性为原则，像素生长法为手段对图像进行分割，分割后得到的各个区域会具有各自的形态几何特征和颜色信息。接下来使用Freeman链码提取区域边界来描述分割后的各个局部目标，计算各目标的面积、周长、外接矩形的长和宽及长宽比、复杂度等几何特征，去除面积较小、长宽比小，复杂度偏小的区域目标。最后，对剩下的区域的边界链码进行Hough变换得到构成线性目标平行边的直线。对检测出来的准平行边，使用平行边的数学模型进行鉴别，以确定其是否确实为平行边。最后，根据得到的平行边来确定线性目标的位置。整个算法过程如图3所示。

图3 算法流程

2.1 双边滤波

本文采用式 （2）所示的双边滤波器对图像进行滤波。双边滤波是一种非线性的滤波方法，是结合图像的空间邻近度和像素值相似度的一种折衷处理，同时考虑空域信息和灰度相似性，达到保边去噪的目的，具有简单、非迭代、局部的保留边缘特点，参见文献 ［11］。

双边滤波器中，输出像素的值g（i，j）依赖于邻域像素的值的加权组合

式中：z——中心点（k，l）的大小为 （2N＋1）× （2N＋1）的邻域，权重系数w（i，j，k，l）取决于空间邻近度因子

和亮度相似度因子

的乘积，即

双边滤波器受邻域半径N、参数σs和σr等参数控制。N 值越大，平滑作用越明显；σs和σr分别为控制着空间邻近度因子ws和亮度相似度因子wr的衰减程度的参数。

2.2 区域分割

本文采用基于生长的分割方法，具体步骤如下：初始点集合A 为一个像素点，灰度平均值Avg 为当前集合A 中所有像素点灰度值的平均值；点集合A 中像素点周围邻域的像素点作为候选点，如果候选点的灰度值和Avg 之差小于初始设定的阈值，则将该点加入点集合A 中，并更新Avg 的值。重复该步骤，直到没有新的点加入，此时集合A 即为具有灰度一致性的区域。然后用Freeman链码描述这个区域。

2.3 去除小目标

结合道路特征，可根据几何形状筛分出道路段目标。本文通过计算周长C、面积S、长宽比R、复杂度E 等几何特征进行小目标的去除［12］。面积S 很小的区域可直接判定为干扰物体。长宽比

式中：L——目标区域的长；W——目标区域的宽；长宽比R 较小的区域明显也是干扰区域。

定义了复杂度

式中：C——目标区域的周长；S——面积；复杂度E 反应了平面内物体形状的复杂程度。复杂度E 过小的区域也为干扰区域。根据这些几何特征去除图像中的小目标。

2.4 平行线模型

平行线模型包括长度特征和平行特征。①长度特征，对于一条曲线来说，不能简单地采用端点之间的距离来表示其长度，应该为其所包含像素的个数。构成线性目标的边缘曲线具有一定长度，定义线性目标的长度特征为

式中：C（L）为曲线L 所包含像素的个数，Tlength为线性目标边缘的最短长度阈值。②平行特征，一般地，平行线的判断依据是斜率，由于使用斜率时误差较大，在本文中使用的是一种平行线对模型。对于两条光滑的线L 与S，如果他们间的任一点在任意方向上到达L 与S的距离之和为定值。如果两条直线L 与S同时满足上述两个条件，则认为它们构成一组平行线对，用L／／S表示。如图4所示。

图4 平行线对模型

图4中，L和S为一对直线，现任意取这对直线内部两个点A0和B0，｜A1A2｜和｜B1B2｜分别是A0和B0在取定的某个方向上 （图4中的虚线方向）到直线L 与S的距离之和。若｜A1A2｜＝｜B1B2｜＝常数，对于所有的内部点均成立，则可判定这两条线为一组平行线对。

2.5 标绘目标

在统计参数域中的每一对 θ，（ ）ρ 时，记录参与统计这对 θ，（ ）ρ 的所有点的x 坐标，再根据得到的ρ 和θ，按求出的式 （9）将平行线上的像素点 （x，y）用不同的颜色标示出来，从而可以标绘出线性目标的位置

2.6 实验对比

图5 实验结果对比

实验的硬件平台：CPU 为Intel Core（TM），主频2.8 GHz，内存4GB。在相同的实验平台下，运行耗时越少表示算法效率越高。实验结果对比如下：①传统Hough变换在提取平行线对的第二条直线时出现了重复检测第一条直线的情况，而改进后的算法不会出现重复检测的情况并且可以准确检测出线性目标的两条平行边。②在检测平行线对的数量上，当图像中有多个线性目标时，本文检测算法能检测出所有线性目标的平行线对，而传统Hough变换法只能检测出最规则的那对平行线。③在检测性能上，从表1可以看出，平行线对检测算法优于传统算法，识别精度有了很大提高。在运算耗时上，由于改进算法只需对边界链码数据进行运算，大大降低了Hough 变换过程中的复杂度，使得本文检测算法耗时更少。

表1 测试结果

3 实验结果及分析

实验系统采用Visual studio2010平台开发，实验中使用的遥感影像大小为580＊508，图中的道路、隔离带和车辆都可以很容易被人眼识别出来。使用本文算法识别道路的过程，如图6所示。其中图6 （a）为原始卫星影像，图6（b）是进行中值滤波和图像分割后得到的结果，图6 （c）是使用基于区域生长的灰度一致化方法去除小目标得到的灰度图像，图6 （d）为对图6 （c）中的灰度图像进行二值化后得到的结果，图6 （e）为对二值图像使用形态学方法进行膨胀、腐蚀和填充后的结果，图6 （f）为Hough变换提取出平行线对后标绘出线性目标的位置。实验中，由于原始图像中有树阴遮挡、车辆等因素的干扰，导致分割后的图像有很多孔洞，所以使用形态学方法对其进行填充后才进行后续平行线对的提取。从结果看，对于线条状的线性道路目标能被有效地提取出来，但对呈弧线型的弯曲支路，没有提取出来，对提取这类弯曲的支路部分还需进一步研究处理。

4 结束语

图6 实验处理过程

在总结现有线性目标检测算法的基础上，本文根据遥感影像中线性道路具有宽度一定、灰度一致、道路有一定的长度等特征提出了一种结合Freeman链码和Hough变换的道路检测算法。通过实验分析，改进后的算法，效率高、计算结果更精准、允许少数点的扰动、内存使用上更灵活、适用性强。但是，在检测路面噪声信息较多、局部灰度变化较大的影像中道路时，其性能会受到明显影响。另外，该算法仅适合检测直线形道路，在道路宽度忽然改变的情况效果也不是很好，这些都有待改进。

［1］ZHU Changsheng，ZHOU Wei，GUAN Jian.Main roads ex－traction from SAR imagery based on parallel pairs detection［J］.Journal of Image and Graphics，2011，16 （10）：1908－1917 （in Chinese）.［朱昌盛，周伟，关键.基于平行线对检测的SAR 图像主干道提取算法 ［J］.中国图象图形学报，2011，16 （10）：1908－1917.］

［2］PAN Jianping，WU Mingquan.Road detection based on morphology ［J］.Computer Engineering and Applications，2008，44（11）：232－233 （in Chinese）.［潘建平，邬明权.基于数学形态学的道路提取 ［J］.计算机工程与应用，2008，44 （11）：232－233.］

［3］XU Huarong，WANG Xiaodong，FANG Qiu.Structure road detection algorithm based on B－spline curve model［J］.Acta Automatica Sinica，2011，37 （3）：270－275 （in Chinese）.［许华荣，王晓栋，方遒.基于B样条曲线模型的结构化道路检测算法 ［J］.自动化学报，2011，37 （3）：270－275.］

［4］WANG Yiming，Qin Yongyuan.Target detection in SAR images based on region growing ［J］.Journal of Computer Applications，2009，29 （1）：45－46 （in Chinese）.［王义敏，秦永元.基于区域生长的SAR 图像目标检测方法研究 ［J］.计算机应用，2009，29 （1）：45－46.］

［5］WANG Ping，DONG Yude，LUO Zheshuai.Freeman encodingbased line－segments recognition ［J］.Computer Engineering，2005，31 （10）：171－173 （in Chinese）.［王平，董玉德，罗喆帅.基于Freeman 链码的直线识别方法 ［J］.计算机工程，2005，31 （10）：171－173.］

［6］Yoshihiko Mochizuki，Akihiko Torii，Atsushi Imiya.N－Point hough transform for line detection ［J］.J Vis Commun Image R，2009，20 （4）：242－253.

［7］KANG Wenjing，DING Xuemei，CUI Jiwen.Fast straight－line extraction algorithm based on improved hough transform ［J］.Opto－Electronic Engineering，2007，34 （3）：105－108.

［8］Mokhtarzdae M，Valadan Zoej M J.Road detection from high resolution satellite images using artificial neural networks［J］.International Journal of Applied Earth Observation and Geoinformation，2007，9 （1）：32－40.

［9］Vaddi R S，Boggavarapu L N P，Vankayalapati H D.Contour detection using Freeman chain code and approximation methods for the real－time object detection ［J］.Asian Journal of Computer Science and Information Technology，2011，1 （1）：15－17.

［10］LU Guangquan，XU Hongguo，LI Yibing.Line segment detection based on chain code detection ［J］.Computer Engineering，2006，32 （14）：1－3 （in Chinese）.［鲁光泉，许洪国，李一兵.基于链码检测的直线段检测方法 ［J］.计算机工程，2006，32 （14）：1－3.］

［11］ZHANG Zhiqiang，WANG Wanyu.A modified bilateral filtering algorithm ［J］.Journal of Image and Graphics，2009，14 （3）：443－447（in Chinese）.［张志强，王万玉.一种改进的双边滤波算法［J］.中国图象图形学报，2009，14 （3）：443－447.］

［12］LEI Xiaoqi，WANG Weixing，LAI Jun.A method of road extraction from high－resolution remote sensing images based on shape features［J］.Acta Geodaetica et Cartographica Sinica，2009，38 （5）：457－465 （in Chinese）.［雷小奇，王 卫星，赖均.一种基于形状特征进行高分辨率遥感影像道路提取方法［J］.测绘学报，2009，38 （5）：457－465.］