【图像处理】霍夫变换

Hough 简介

霍夫变换是一种特征提取技术，通过从 xy 空间转换到参数空间，计算累计结果的局部最大值得到一个符合特定形状的集合作为霍夫变换结果。最早由 Paul Hough 在 1962 年提出，现在使用的是由 Richard Duda 和 Peter Hart 所发明的成为“广义霍夫变换”。经典霍夫变换用来检测图像中的直线，后来霍夫变换扩展到任意形状物体的识别。

霍夫变换的主要优点是能够识别具有间隔的边界，并且相对受噪声影响比较小。

Hough 直线检测原理

直线的表示

在笛卡尔坐标系中，一条直线可以由两个点确定，如左图所示，由 $A=(x_1,y_1)$ 和 $B=(x_2,y_2)$ 确定的直线的表达式为 $y=kx+q$ ；而在霍夫空间中使用 $(\rho,\theta)$ 表示， $\rho$ 指的是 xy 平面中的直线到原点的距离， $\theta$ 是 $\rho$ 与横轴的夹角。

笛卡尔坐标系与参数空间的关系

现在考虑在笛卡尔坐标系中的一个点 $(x_i,y_i)$ 在霍夫空间中的表现形式。经过这个点可以有无数条直线 $y_i=kx_i+b$ ，这些直线在霍夫空间中可以用 $\rho=x_i*cos(\theta)+y_i*sin(\theta)$ 表示，故点 $(x_i,y_i)$ 在霍夫空间中是一条曲线。同理，霍夫空间中的一个点对应着笛卡尔 xy 平面上的一条直线。

笛卡尔坐标系内一条直线上的多个点

上图中的三点共线，经过坐标转换在右侧的霍夫空间中三条曲线交于一点，该点便是笛卡尔坐标中直线的表达。

霍夫变换提取直线

霍夫变换就是假设一个点有 n 个方向的直线，分别计算这 n 条直线的 $(\rho,\theta)$ 坐标，这相当于把霍夫空间量化为有限间隔的累加器，在计算过程中，每个点都在霍夫空间中生成一个离散的曲线，并且沿着这条曲线的累加器单元被递增，累加器阵列中的峰值表示图像中存在相应的直线。
对于二维图像而言，霍夫空间中的累加器就是一个二维矩阵，一个维度是量化角度 $\theta$ ，一个维度是量化的 $\rho$ 。如果二维图像的一个像素点经过霍夫变换后生成的离散曲线落在某累加器单元中时，该累加器单元值增 1。当整个二维图像遍历一遍后，累加器中的峰值就是表示最有可能提取出的直线。找到这些峰值的最简单方式就是设置阈值，同时其他技术在不同情况下也可能产生较好的结果。
有时也将这些累加器单元结果认为是投票值，这些曲线每产生一个交点，就被看做该位置投票值加 1，遍历之后，设置一个阈值，投票值大于该阈值的可以认为是找到的直线。

霍夫变换实例

左上图为原始的图片，一个简单的正方形；右上图为经过 canny 边缘检测后的结果；左下图是经过霍夫变换后霍夫空间；右下图是选取了峰值最高的四个点。

直线检测代码实现

算法描述

初始化 $(\rho,\theta)$ 空间， $N(\rho,\theta)=0$ ( $N(\rho,\theta)=0$ 表示在该参数表示的直线上的像素点的个数)
对于每一个像素点 $(x,y)$ ，在参数空间中找出满足 $\rho=x*cos(\theta)+y*sin(\theta)$ 的 $(\rho,\theta)$ 对，然后令 $N(\rho,\theta)=N(\rho,\theta)+1$
统计所有 $N(\rho,\theta)$ 的大小，取出 $N(\rho,\theta)>\tau$ 的参数( $\tau$ 是预设的阈值)

Python 实现

Opencv-python 中提供了 cv2.HoughLines()和 cv2.HoughLinesP()两个接口。
cv2.HoughLines()返回值是一个数组 $(\rho,\theta)$ ，其中 $\rho$ 以像素为单位， $\theta$ 以角度为单位。第一个参数是一个二值图像，所以在进行透视变换之前通常进行二值化或者边缘检测；第二、三个参数是 $\rho$ 和 $\theta$ 的精度，通常以 1 像素和 1° 为单位；第四个是在参数空间中认为是直线的阈值。

import cv2
import numpy as np

img = cv2.imread("./demo.png")
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray, 50, 150)
lines = cv2.HoughLines(edges, 1, np.pi / 180, 150)
for line in lines:
    rho, theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a * rho
    y0 = b * rho
    x1 = int(x0 + 1000 * (-b))
    y1 = int(y0 + 1000 * (a))
    x2 = int(x0 - 1000 * (-b))
    y2 = int(y0 - 1000 * (a))
    cv2.line(img, (x1, y1), (x2, y2), (0, 0, 255, 2))

cv2.imshow('img', img)
cv2.waitKey(0)

cv2.HoughLinesP()是对霍夫变换的一种优化，它从图像中随机选取一个点集进行计算，减少了运算量，但需要降低检测的阈值。
这个函数增加了两个参数:minLineLength，最短线段长度，比这小的直线将被忽略； MaxLineGap，两条直线的最大间隔，大于该值的直线会被看作是一条直线。并且返回值也更加强大，返回的是直线的起点和终点。

import cv2
import numpy as np

img = cv2.imread("./demo.png")
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray, 50, 150)
lines = cv2.HoughLinesP(edges,
                        1,
                        np.pi / 180,
                        120,
                        minLineLength=30,
                        maxLineGap=10)
for line in lines:
    x1, y1, x2, y2 = line[0]
    cv2.line(img, (x1, y1), (x2, y2), (0, 0, 255, 2))

cv2.imshow('img', img)
cv2.waitKey(0)

检测圆

相同的原理同样可以检测圆形，圆的参数方程为 $(x-a)^2+(y-b)^2=r^2$ ，因此所需的参数空间和累加器均为三维，算法复杂度变高，所以霍夫变换适合于简单曲线。

算法步骤

首先创建累加器空间，由每个像素单元格构成。最初每个单元格都设置为 0。
然后对于每个图像中的边缘点 $(i,j)$ ，按照圆方程 $(i-a)^2+(j-b)^2=r^2$ 将那些可能是一个圆中心的单元格值进行累加。这些单元格在等式中由字母 $a$ 表示。
然后在前面的步骤中由每个可能找到的值 $a$ ，区找到满足等式的所有可能值 $b$
搜索累加器空间中的局部最大值。这些单元格表示算法检测到的圆圈。

如果不确定圆的半径，也可以搜索任意半径的圆，只不过计算会更加复杂。

广义霍夫变换

当我们所查找到形状边界不能够简单解析时，就可以使用广义霍夫变换，这也就使得霍夫变换可以用来检测所有的形状。广义霍夫变换，通过查找表来定义边界位置和方向与霍夫参数之间的关系。
因为找不到图形的方程，所以采用一种表的形式记录图形的边缘点坐标，再通过找到一种转换方法使得点集可以映射到参数空间中的一点。为了找到这个方法，可以将表看作是模板，进行模板匹配，大部分的点能够匹配上就可以，这种方法的参数之间没有任何关联，所以是完全遍历的，再加上旋转、缩放，十分耗时。
Ballard(1981)提出的广义霍夫变换方法将图形边缘点对中心点的径向量保存起来，利用边缘点的梯度方向与相应的径向量的旋转角度作为另一个参数，这就与利用圆的检测方法相同，并且旋转、缩放不会引入第三个量。

reference: