Introduction 介绍

当图像要用于分析图像中的不同区域(如目标识别)时,减少图像中的数据量,同时保留重要的特征结构信息是非常重要的。

边缘检测(Edge Detection)可以显着减少图像中的数据量。然而,边缘检测器的输出仍然是由像素描述的图像。 如果线条,椭圆等可以通过它们的特征方程来定义,那么数据量将会减少得更多。

Hough变换最初是为了识别直线(Line)而开发的,并且后来被广义化为涵盖任意形状。

Hough space and Hough Transform 霍夫空间与霍夫变换

直线在 Hough space 中的表示

直线可以唯一地由两个参数来表示,经过点 (x,y)(x, y) 的直线可表示为:

\begin{equation} y=a·x+b \tag{1} \end{equation}

其中参数 aa 为斜率, bb 为截距,通过点 (x,y)(x,y) 的直线有无数条,且对应于不同的 aabb 值, 如果将 xxyy 视为常数,而将原本的参数 aabb 看作变量,则 (1) 可以表示为:

b=xa+yb=-x·a+y

这样直线 y=ax+by=a·x+b 就变换到了参数为 (a,b)(a,b) 的 Hough 空间,这就是直角坐标系中对于 (x,y)(x,y) 点的 Hough Transform 霍夫变换

我们可以发现在直角坐标系(即欧式空间)中的一条直线,对应于 Hough 空间中的一个点,如下图所示

1

欧式空间中的一条直线对应于Hough空间中的一个点,反过来Hough空间中的一条线自然对应于欧式空间的一个点,如下图所示

2

这时我们就可以想到,对于欧式空间的多个点,映射到Hough空间,即为多条直线。

如果我们可以找到一条穿过这些点的直线,每个点映射到Hough空间的线必然相交于一个点,而这个点就是我们需要的直线参数,即完成了对于直线的检测。

3

极坐标系下

上面的内容已经将Hough变换检测直线的原理呈现出来了,但是在直角坐标系下的表示形式,存在无法表示垂直于x轴的直线的问题,此时a=a=\infty

所以我们将(1)改写为极坐标表示:

\begin{equation} r=x·cos\theta + y·sin\theta \tag{2} \end{equation}

并保持与 (1) 的形式一致:

\begin{equation} y=-\frac{cos\theta}{sin\theta}·x+\frac{r}{sin\theta} \tag{3} \end{equation}

θ[0,180]\theta \in [0, 180]rRr \in \mathbf{R}(或者θ[0,360]\theta \in [0, 360]r0r\geqslant 0)时,极坐标系中所有的直线都可以用这种形式表示。

Hough空间因此具有这两个维度: θ\thetarr,并且极坐标系下直线由Hough空间的单个点表示,对应于唯一的一组参数(θ0\theta_0r0r_0

与直角坐标系相同,极坐标系下的多点,对应于Hough空间中的多个曲线,若存在过这些点的一条直线,则Hough空间中的曲线必然相交于一点。

4

Algorithm 算法

Transformation to Hough Space

如之前所述,每个edge point被转换成Hough空间中的一条线,并且大多数Hough空间线,相交的区域在Edge Image中对应于一条直线。

即欧式空间中可能被拟合为一条直线的多点,对应于与Hough空间中的多条线,并且这些线可以相交于一点,该点参数即为欧式空间中直线的参数;

同理,如果可以拟合成多条直线,则Hough空间中必定存在多个曲线相交的点。

The Hough Space Accumulator

为了确定霍夫空间中大多数线相交的区域(点),使用一个覆盖Hough空间的累加器(Accumulator)

当一个Edge point被转换到Hough空间时,对于Hough空间位置的累加器的值增加,同时也很好理解,累加器的分辨率决定了检测直线的精度。

这样我们也可以看到,累加器的维数对应于Hough变换问题中未知参数的个数。

对于椭圆而言,需要5个参数(其中心的坐标,其主轴和副轴的长度以及角度),对于直线,只需两个维度(rrθ\theta)就足够了

Detection of Infinite Lines

当所有Edeg points 已经被转换到Hough空间时,通过检测累加器的值来检测直线。

检测直线最基本的方法是为累加器设置一些阈值,然后保留高于阈值的值。阈值可以是累加器中最大值的50%,这种方法偶尔可以满足要求,但在许多情况下,必须采用其他的约束条件。

从下图中可以看出,Hough Transform累加器最大值周围的点,也具有较大的值。因此,仅设置一个简单的阈值,将会检测到与真实直线相近的多个直线。

为了避免这种情况,可以定义一个抑制邻域的方法,这样在检测到两条线之前,必须有两条线显著的不同。

5

Finite line

经典的Hough transform检测仅由参数 rrθ\theta给出直线,并且没有关于长度的信息。 因此,所有检测到的线的长度都是无限的。

如果需要有限长的直线,则必须执行一些附加分析以确定图像的哪些区域存在直线。

有以下几种算法:

  • 一种方法是存储累加器中所有点的坐标信息,并使用这些信息来限制线条。 但是,这会导致累加器使用更多的内存。
  • 另一种方法是沿Edge图像中无限长的直线搜索以找到有限长度的直线。 这种方法的一种变体称为 Progressive Probabilistic Hough Transform(渐进概率霍夫变换)

Progressive Probabilistic Hough Transform 渐进概率霍夫变换

霍夫变换不是一个查找图像中长度无限的线快速算法,由于需要附加的分析以检测长度有限的线,则会更慢。加快Hough变换算法速度,并同时寻找长度有限的直线的方法是 Progressive Probabilistic Hough Transform渐进概率霍夫变换(PPHT)

这种方法的想法是将Edge图像中随机选择的像素,转换到累加器。 当在累加器可确认一个特定的无限长度的直线时,沿该条直线搜索Edge图像,以查看是否存在一个或多个有限长度的线。

然后在该直线的所有像素被从Edge图像中除去。通过这种方式,算法返回有限长度的直线。 如果搜索阈值较高,则在累加器中评估的像素数量会变小。

该算法可以概括如下:

  1. 创建输入边 Edge 图像(IMG1)的副本(IMG2)。
  2. 用从 IMG2 随机选择的像素更新累加器。
  3. 从 IMG2 中删除像素。
  4. 如果修改的累加器(BINX)中具有最大值的较低阈值,转到第1点。
  5. 沿着由BINX指定的线在 IMG1 中搜索,找到连续或间隙不超过给定阈值的间隔的最长像素段。
  6. 从 IMG2 中删除段中的像素。
  7. 清除BINX。
  8. 如果检测到的线段比给定的最小长度长,请将其添加到输出列表中。
  9. 转到第2点

问题

该算法的一个问题是,多次运行可能会产生不同的结果。 如果许多直线共享像素,则会出现这种情况。

如果两条线交叉,要检测的第一条线将去除公共像素(以及其周围的部分),从而导致另一条线上出现凹陷。 如果多条线交叉,则许多像素可能会错过最后一行,并且累加器中的投票可能无法达到阈值。

步骤与应用

直线检测算法可以分为以下几个步骤:

  1. 边缘检测(edge detection),例如:Canny edge detection
  2. 将edge point映射到霍夫空间并存储在累加器中。
  3. 通过阈值和可能的其他限制,寻找累加器中最合理的点(例如,寻找累加器中值最大的一点 或者 大于阈值的点),产生无限长度的直线。
  4. 将无限长度的直线转换为有限长度,并重叠在原始图像上。

Hough Transform 霍夫变换本身应用在第2点

opencv 以及 skimage 库都实现了 Hough transform 以及 ** Progressive Probabilistic Hough Transform** ,以直接调用其提供的算法接口。

1
2
3
4
5
6
7
import cv2
import matplotlib.pyplot as plt

img = cv2.imread('building.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
plt.imshow(gray, cmap='gray')
plt.show()

6

1
2
3
4
5
6
# Using canny edge detection
low_threshold = 50 # Canny edge detection low threshold
high_threshold = 200 # Canny edge detection high threshold
edges = cv2.Canny(gray, low_threshold, high_threshold)
plt.imshow(edges, cmap='gray')
plt.show()

7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import numpy as np
rho = 1
theta = np.pi / 180
threshold = 100
min_line_length = 30
max_line_gap = 10

def draw_lines(img, lines, color=[255, 0, 0], thickness=2):
for line in lines:
for x1, y1, x2, y2 in line:
cv2.line(img, (x1, y1), (x2, y2), color, thickness)

def hough_lines(img, rho, theta, threshold,
min_line_len, max_line_gap):
lines = cv2.HoughLinesP(img, rho, theta, threshold, np.array([]),
minLineLength=min_line_len,
maxLineGap=max_line_gap)
line_img = np.zeros((img.shape[0], img.shape[1], 3), dtype=np.uint8)
draw_lines(line_img, lines)
return line_img


line_img = hough_lines(edges, rho, theta, threshold, min_line_length, max_line_gap)
plt.imshow(line_img, cmap='gray')
plt.show()

8

1
2
3
4
threshold = 10 # 修改门限值
line_img = hough_lines(edges, rho, theta, threshold, min_line_length, max_line_gap)
plt.imshow(line_img, cmap='gray')
plt.show()

9