[科普中国]-直线检测算子

研究现状

图像检测作为图像分析技术的一个研究内容，它也是伴随着数字图像处理的发展而发展的。数字图像处理这门学科的形成也是和社会生产力发展的需要分不开的。它已经广泛的应用到科学研究、工农业生产、军事技术、政府部门、医疗卫生等许多领域，进一步推动着社会生产力的发展。

图像检测是图像分析研究内容的一部分。目前，在图像分析领域已经有很大的发展。图像分析是一种从一幅图像中通过自动的或半自动的方法提取图像尺寸、数据或信息的方法。图像分析方法通常因图像分析系统最后的输出是数字而不是画面，使它与其他类型的图像处理方法，如编码、恢复、放大等不同。图像分析源于经典的模式识别方法，根据定义，分析系统并不局限于对一个固定数量类别的场景区域的分类，而是更倾向于可设计成用于描绘复杂场景。根据事先预测，该场景的种类可能是非常多的和不确定的。目前，图像分析领域主要包括形态学图像处理、边缘检测、图像特征提取、图像分割、形状分析、图像检测和配准等几个方面的内容。1

Hough直线检测算法基本方法Hough算法及其改进算法是利用坐标域变换的代表。此类算法的优点是抗干扰能力强，对图像中的噪声不敏感。但是由于其算法特点使得其时间复杂度和空间复杂度都很高，并且在变换过程中丢失了线段的长度信息。

Hough 变换的基本思想是点线的对偶性。一方面,图像空间中共线的点对应在参数空间里相交的线;另一方面,在参数空间中相交于同一个点的所有直线在图像空间里都有共线的点与之对应。因此Hough 变换把在图像空间中的直线检测问题转换到参数空间中对点的检测问题,通过在参数空间里进行简单的累加统计完成检测任务。1

改进方法随机Hough变换(RHT)：

RHT 的基本思想是随机选取两个边缘点，由这两点唯一确定参数空间的一个点，这是多到一的映射，避免了传统Hough 变换一到多映射的庞大计算量。在实现累积时，采用动态链表结构，只对多到一映射所得到的参数分配单元进行累积，从而降低了内存需求，提高运算速度。

基于随机Hough变换与最小二乘法进行直线检测算法RHT-LSM：

首先用随机Hough变换确定直线的大致位置；然后，利用所得直线参数，计 算图像中的点到直线的距离，根据距离，可以确定每条直线附近的点集，剔除干扰点和噪声；最后，用LSM对点集中的各点进行拟合，得到精确的直线参量。

基于局部PCA方向统计分析的Hough直线检测算法(PCA-HT)：

首先通过边缘检测获得图像边缘，对边缘像素进行分块处理，利用PCA所得到所有掩膜范围内的主元方向，将获得的局部方向信息映射到参数空间，侧重利用其统计规律来模糊约束Hough变换极角范围，达到减少运算量和存储累计矩阵的目的。

Freeman直线检测算法Hough由于其应用广泛和简洁获得了很大程度上的认可，但同时有学者对Hough算法的低效率和高空间占用并不满意，而且在Hough变换时直线将丧失其长度和具体位置的问题也令一些学者不满意。于是，他们提出了改进的方案。与Hough算法通过坐标转换的方式不同，改进的方案更倾向与从直线的直接特征中寻找突破点。

Yuan 等提出了一种在链码中检测直线的算法。该算法从起始链码开始，对每一链码确定一个直线穿行区域以及两条用于确定下一链码是否属于同一直线的上下边界线。如果下一链码位于上下边界线之内，则该链码与上一链码属于同一直线；否则该链码属于另一直线 。

一条直线在图像中是一系列离散点的集合，通过一个直线的离散极坐标公式，可以表达出直线的离散点几何等式如下：

X *cos(theta) + y * sin(theta) = r

其中角度theta指r与X轴之间的夹角，r为到直线几何垂直距离。任何在直线上点，x、y都可以表达，其中 r、theta是常量。该公式图形表示如下：

然而在实现的图像处理领域，图像的像素坐标P(x，y)是已知的，而r、theta则是我们要寻找的变量。如果我们能绘制每个(r，theta)值根据像素点坐标P(x，y)值的话，那么就从图像笛卡尔坐标系统转换到极坐标霍夫空间系统，这种从点到曲线的变换称为直线的霍夫变换。变换通过量化霍夫参数空间为有限个值间隔等分或者累加子。当霍夫变换算法开始，每个像素坐标点P(x， y)被转换到(r， theta)的曲线点上面，累加到对应的格子数据点，当一个波峰出现时候，说明有直线存在。2

尺蠖蠕行算法对应于尺蠖的仿生学特点，CCA 在边缘像素子集内检测直线的原理如下：3

（1）选择直线的初始搜索点

在选择直线的初始搜索点时 ，尺蠖是在地面爬行碰到树干时才向上探行。 因此 CCA 检测直线时也首先从图像的左下角 (本文将图像的左下角定义为图像的坐标原点) 开始逐行扫描，搜索图像中的边缘点。 当扫描到第一个边缘点时 ，将其作为直线的初始搜索点 (XS0 ，YS0) ，该点对应于尺蠖在树干上的第一个攀援点。

（2）直线搜索的方向选择

尺蠖在向前行进时 ,将根据自身当前的状态来判断行进的方向 ，将下一个落足点限制在以身体为轴线的小扇形区域内 ，从而使运动轨迹在身体附近的小区域内近似为一条直线。在直线像素的搜索过程中 ，为了减少扫描区域 ，增加搜索的准确性 ，同样可以将直线的搜索方向角限定在一定范围内。

（3）直线特征搜索

尺蠖利用身体的屈伸运动依次带动身体后端和前端的足 ,从而完成向前的爬行。 它的身体中间没有足分布 ,其身体中部的轴线在爬行平面上的投影始终为一直线段。 由于它身体自身的柔性特性 ,其前后足间的距离δ可在一定范围内伸缩 (0