开头

  本文主要讲述的是霍夫变换的一些内容,并加入一些在生活中的应用,希望能对读者对于霍夫变换的内容有所了解。   首先我先说的是,霍夫变换是一个特征提取技术。其可用于隔离图像中特定形状的特征的技术,应用在图像分析、计算机视觉和数字图像处理领域。目的是通过投票程序在特定类型的形状内找到对象的不完美实例。这个投票程序是在一个参数空间中进行的,在这个参数空间中,候选对象被当作所谓的累加器空间中的局部最大值来获得,所述累加器空间由用于计算霍夫变换的算法明确地构建。此处我们主要介绍的是比较基本的霍夫变换在直线中的应用,例如在图像中检测直线(线段),Hough变换的主要优点是对于噪声有良好的鲁棒性。  

基础原理介绍

  正如我们上面所介绍的那样,霍夫变换最简单的是检测直线。我们知道,直线的方程表示可以由斜率k和截距b表示(这种表示方法,称为斜截式,也就是高中的时候学习到的一种常用形式),如下所示:  
y=kx+b
  如果我们用参数空间表示则为(b,k),即,我们可以用斜率和截距就能表示一条直线。但这种形式会产生一个问题,那就是当我们的直线斜率k为无限大的时候(即垂线),这会使得该直线无法使用斜截式来进行表示,此处我们需要使用到另一种直线的表现形式:黑塞法线式(或者简称为法线式):  
r=xcosθ+ysinθ
其中r是原点到直线上最近点的距离(其他人可能把这记录为ρ,下面也可以把r看成参数ρ,两者含义相同),θ是x轴与连接原点和最近点直线之间的夹角。如图1所示。  
图1
  从而我们可以将图像的每一条直线与一对参数(r,θ)相关联。由参数(r,θ)构成的平面有时被称为霍夫空间,用于表示二维直线所构成的集合。   我们经过Hough变换后,我们圆来笛卡尔坐标系中的一个点可以映射到Hough空间中去,如图2所示。  
图2
(注:图2表示的是原坐标系中,过该点的所有可能直线的集合在Hough空间中的表示。)   图2显示了经过原笛卡尔坐标系中的定点(3,4),通过该点的所有可能直线的(r,θ)的关系。显示了在极坐标对极径极角平面绘出所有通过该定点的直线, 将得到一条正弦曲线。正弦曲线的形状取决于,点到所定义原点的距离r。通常,r越大,正弦曲线的振幅越大,反之则会越小。   所以我们可以得到一个结论,给定平面中的单个点,那么通过该点的所有直线的集合对应于(r,θ)平面中的正弦曲线,这对于该点是独特的。一组两个或更多点形成一条直线将产生在该线的(r,θ)处交叉的正弦曲线。因此,检测共线点的问题可以转化为找曲线相交点的问题。  

例:

  考虑下面三个点,这里显示为黑点。  
图3
  (注:此处也展示了霍夫变换的几个基本步骤:首先,对每个点均绘制不同角度的线条,这些线全部经过各自的对应点并显示为实线。其次,对于每条实线,找到经过原点的对应垂线并显示为虚线。然后找到虚线的长度和角度。这些值显示在图表下方的表格中。这对被转换的三个点中的每一个都重复该过程。然后将结果绘制成图,有时称为霍夫空间图,如图4所示)  
图4
  图4中曲线相交的点给出的距离和角度表示各个测试点相交的线。在图4中,所示的线条在粉红点相交; 这对应于图3中的实线粉红线,其穿过三个点。   分析上下文,边缘段的点(一个或多个)的坐标(xi,yi)在图像中是已知的,并且因此作为参数线等式中的常量,而r与θ是未知变量是我们要寻找的。如果我们绘制由(r,θ)每个定义的可能值(xi,yi),笛卡尔图像空间中的点映射到霍夫参数空间中的曲线(正弦曲线)。这个点到曲线的变换是直线的霍夫变换。当在霍夫参数空间中查看时,在笛卡尔图像空间中共线的点变得很明显,因为它们产生在相同(r,θ)点相交的曲线。  

霍夫变换提取直线

  我们通过将霍夫参数空间量化为有限间隔或累加器单元来实现变换。随着算法的运行,每个算法都把(xi,yi)转换为一个离散化的 (r,θ)曲线,并且沿着这条曲线的累加器单元被递增。累加器阵列中产生的峰值表示图像中存在相应的直线的相应证明。   此时需要注意的是,现在我们考虑的是直线的霍夫变换。累加器阵列的维度是二维的(也就是r和θ)。 那么对于图像来说,(x,y)处的每个像素及其邻域,霍夫变换算法被用于确定该像素是否有足够的直线证据。如果是,它将计算该线的参数 (r,θ),然后查找参数落入的累加器箱,并增加该箱的值(投票值)。通过查找具有最高值的箱,通常通过查找累加器空间中的局部最大值,可以提取最可能的线,并且读出它们的(近似的)几何定义。   找到这些峰值的最简单方法是通过应用某种形式的阈值,但其他技术可能在不同情况下产生更好的结果。由于返回的行不包含任何长度信息,因此通常有必要在下一步中查找图像的哪些部分与哪些行匹配。此外,由于边缘检测步骤中存在缺陷误差,通常会在累加器空间中出现错误,这可能使得找到合适的峰值以及适当的线条变得非常重要。   线性霍夫变换的最终结果是类似于累加器的二维阵列(矩阵),该矩阵的一个维度是量化角度θ,另一个维度是量化距离r。矩阵的每个元素的值等于位于由量化参数 (r,θ)表示的线上的点或像素的总和。所以具有最高值的元素表示输入图像中代表最多的直线。我们也可以把累计器单元的结果认为是投票值。换句话说,将每个交点看成一次投票,也就是说A(r,θ)=A(r,θ)+1,所有点都如此进行计算后,可以设置一个阈值,投票大于这个阈值的可以认为是找到的直线。  

霍夫变换提取圆

  而当我们需要去进行圆检测的时候,我们累加器是三维累加器,在圆检测的情况下,我们可以知道的是其对应的参数方程为:  
(x−a)2+(y−b)2=r2
其中a和b是圆心的坐标并且是r半径。在这种情况下,算法的计算复杂度开始增加,因为我们现在在参数空间和三维累加器中有三个坐标。(通常,累加器阵列的计算和大小随着参数数量的增加而多项式增加,因此,基本霍夫技术仅适用于简单曲线。)   它的算法步骤如下: 1.首先创建累加器空间,由每个像素单元格构成。最初每个单元格都设置为0。 2.然后对于每个图像中的边缘点(i,j),按照圆方程(i−a)2+(j−b)2=r2将那些可能是一个圆中心的单元格值进行累加。这些单元格在等式中由字母a表示。 3.然后在前面的步骤中由每个可能找到的值a,区找到满足等式的所有可能值b 4.搜索累加器空间中的局部最大值。这些单元格表示算法检测到的圆圈。 如果我们不知道事先定位的圆的半径,可以使用三维累加器空间来搜索具有任意半径的圆。当然,这在计算上更加昂贵。 该方法还可以检测部分位于累加器空间外部的圆,只要该圆的区域内仍有足够的圆。  

总结

  霍夫变换在很多地方都有着应用,如果是在OpenCV(Python)下想要使用霍夫变换,只需要使用函数cv2.HoughLinesP函数,需要注意的是该函数并不是标准的霍夫变换,其为:概率霍夫变换,它只分析点的子集并估计这些点都属于一条直线的概率,这是标准霍夫变换的优化版本。该函数计算代价少,执行更快,但准确度有一定程度的下降。   cv2.HoughLinesP函数的语法如下:  
cv2.HoughLinesP(image,rho,theta,threshold,minLineLength,maxLineGap)
  其参数分别解释如下:  
·image:要处理的二值图像;
·rho:线段的几何表示,表示取距离的间隔,一般取1;
·theta:线段的几何表示,表示取角度的间隔,一般取np.pi/180;
·threshold:阈值,低于该阈值的会被忽略;
·minLineLength:最小直线长度,小于该长度会被忽略;
·maxLineGap:最大线段间隙,大于此间隙才被认为是两条直线。
  霍夫变换在自动驾驶中也有所应用,可以如下面一个简单例子所示,其实现的是对我们画面中的道路直线进行的检测:  
import os
import re
import cv2
import numpy as np


# 初始化一个掩膜
def mask_create():
    img = cv2.imread('0.png')
    zero = np.zeros_like(img[:, :, 0])
    poly = np.array([[50, 270], [220, 160], [345, 160], [480, 270]])
    zero_fixed = cv2.fillConvexPoly(zero, poly, (255, 255, 255))
    return zero_fixed

# 掩膜计算,传入的图像需要是BGR图
def mask_calc(frame, mask):
    img = cv2.bitwise_and(frame[:, :, 0], frame[:, :, 0], mask=mask)
    return img

# 图像阈值操作,传入的图片需要是灰度图
def threshold(low, high, img):
    ret, thresh = cv2.threshold(img, low, high, cv2.THRESH_BINARY)
    return thresh

# 对图像进行霍夫变换,输入的图像需要是二值图,距离r为1,旋转角为1度,投票阈值为30,最远距离为200像素
# 并在原图上进行绘制图像
def hough(thresh, img):
    lines = cv2.HoughLinesP(thresh, 1, np.pi/180, 30, maxLineGap=200)
    try:
        for line in lines:
            x1, y1, x2, y2 = line[0]
            img = cv2.line(img, (x1, y1), (x2, y2), (255, 255, 255), 3)
    except:
        return img
    else:
        return img
# 主函数
def mainn():
    # 读取数据
    col_frames = os.listdir('../frames/')
    # 排序
    col_frames.sort(key=lambda f: int(re.sub('\D', '', f)))
    # 读取画面每一帧
    for i in col_frames:
        img = cv2.imread(i)
        # 构建一个掩膜
        mask = mask_create()
        # 对原图像进行掩膜计算
        masked_frame = mask_calc(img, mask)
        thresh = threshold(135, 255, masked_frame)
        img = hough(thresh, img)
        cv2.imshow('img', img)
        if cv2.waitKey(40) == ord('q'):
            break
    cv2.destroyAllWindows()


mainn()
该代码对我们在frames这个文件夹下的图片进行直线检测(文件夹下的图片在源于行车记录仪所拍下的行车记录的部分采样),运行结果如图5所示。  
图5
本文到此为止,谢谢大家!