专栏首页深度学习和计算机视觉实战:基于霍夫变换进行线检测

实战:基于霍夫变换进行线检测

一、目的

最近,我们发现自己不得不在应用程序中加入文档扫描功能。在做了一些研究之后,我们偶然发现了一篇熊英写的文章,他是Dropbox机器学习团队的成员。该文章介绍了如何Dropbox的的机器学习团队通过强调他们通过去的步骤,并在每个步骤使用的算法来实现他们的文档扫描仪。通过那篇文章,我们了解了一种称为霍夫变换的方法, 以及如何将其用于检测图像中的线条。因此,在本文中,我们想解释Hough变换算法,并提供该算法在Python中的“从头开始”的实现。

二、霍夫变换

Hough变换是Paul VC Hough专利的一种算法,最初是为了识别照片中的复杂线条而发明的(Hough,1962)。自从创建以来,该算法已进行了修改和增强,使其能够识别其他形状,例如特定类型的圆形和四边形。为了了解霍夫变换算法的工作原理,重要的是要了解四个概念:边缘图像,霍夫空间以及边缘点到霍夫空间的映射,表示线的替代方法以及如何检测线。

边缘图像

坎尼边缘检测算法

边缘图像是边缘检测算法的输出。边缘检测算法通过确定图像的亮度/强度急剧变化的位置来检测图像中的边缘(“边缘检测-使用Python进行图像处理”,2020年)。边缘检测算法的示例包括:Canny,Sobel,Laplacian等。对边缘图像进行二值化是很常见的,意味着其所有像素值均为1或0。根据你们的情况,为1或0可以表示边缘像素。

霍夫空间和边缘点到霍夫空间的映射

霍夫空间是2D平面,其水平轴表示坡度,而垂直轴表示边缘图像上直线的截距。边缘图像上的一条线以y = ax + b的形式表示(Hough,1962年)。边缘图像上的一条线在霍夫空间上产生一个点,因为一条线的特征在于其斜率a和截距b。另一方面,边缘图像上的边缘点(xᵢ,yᵢ)可以有无数的线通过。因此,边缘点在Hough空间中以b =axᵢ+yᵢ的形式生成一条线(Leavers,1992)。在霍夫变换算法中,霍夫空间用于确定边缘图像中是否存在线条。

表示线的另一种方法

用y = ax + b形式的直线 和带有斜率和截距的霍夫空间代表着一种缺陷。在这种形式下,该算法将无法检测垂直线,因为斜率a对于垂直线是不确定的/无穷大(Leavers,1992)。编程,这意味着,一个计算机将需要的存储器的无限量来表示的所有可能的值一个。为避免此问题,一条直线由一条称为法线的线表示,该线穿过原点并垂直于该直线。法线的形式为ρ = x cos( θ )+ y sin( θ ),其中ρ 是法线的长度,θ是法线与x轴之间的角度。

使用此方法,不再用坡度a和截距b表示霍夫空间,而是用ρ和θ表示,其中水平轴表示θ值,垂直轴表示ρ值。边缘点到霍夫空间的映射以类似的方式工作,除了边缘点(x,y)现在在霍夫空间中生成余弦曲线,而不是直线(Leavers,1992)。线的这种正常表示消除了在处理垂直线时出现的a的无限值的问题。

线检测

如前所述,边缘点在霍夫空间中产生余弦曲线。由此,如果我们将边缘图像中的所有边缘点映射到霍夫空间上,它将生成许多余弦曲线。如果两个边缘点位于同一条线上,则它们对应的余弦曲线将在特定的(ρ,θ)对上彼此相交。因此,霍夫变换算法通过找到交叉点数量大于某个阈值的(ρ,θ)对来检测线。值得注意的是,如果不对霍夫空间进行邻域抑制等预处理以去除边缘图像中的相似线条,这种阈值化方法可能不会总是产生最佳结果。

三、算法

  1. 确定ρ和θ的范围。通常,θ的范围是[0,180]度,而ρ是[ -d,d ],其中d是边缘图像对角线的长度。量化ρ和θ的范围很重要,这意味着应该有数量有限的可能值。
  2. 创建一个称为累加器的二维数组,该数组表示维度为(num_rhos,num_thetas)的霍夫空间,并将其所有值初始化为零。
  3. 对原始图像执行边缘检测。可以使用你们选择的任何边缘检测算法来完成。
  4. 对于边缘图像上的每个像素,请检查该像素是否为边缘像素。如果是边缘像素,则循环遍历所有可能的θ值,计算对应的ρ,在累加器中找到θ和ρ索引,并基于这些索引对递增累加器。
  5. 循环遍历累加器中的所有值。如果该值大于某个阈值,则获取ρ和θ索引,从索引对获取ρ和θ的值,然后可以将其转换回y = ax + b的形式。

四、代码

非向量化解决方案

import cv2
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.lines as mlines


def line_detection_non_vectorized(image, edge_image, num_rhos=180, num_thetas=180, t_count=220):
  edge_height, edge_width = edge_image.shape[:2]
  edge_height_half, edge_width_half = edge_height / 2, edge_width / 2
  #
  d = np.sqrt(np.square(edge_height) + np.square(edge_width))
  dtheta = 180 / num_thetas
  drho = (2 * d) / num_rhos
  #
  thetas = np.arange(0, 180, step=dtheta)
  rhos = np.arange(-d, d, step=drho)
  #
  cos_thetas = np.cos(np.deg2rad(thetas))
  sin_thetas = np.sin(np.deg2rad(thetas))
  #
  accumulator = np.zeros((len(rhos), len(rhos)))
  #
  figure = plt.figure(figsize=(12, 12))
  subplot1 = figure.add_subplot(1, 4, 1)
  subplot1.imshow(image)
  subplot2 = figure.add_subplot(1, 4, 2)
  subplot2.imshow(edge_image, cmap="gray")
  subplot3 = figure.add_subplot(1, 4, 3)
  subplot3.set_facecolor((0, 0, 0))
  subplot4 = figure.add_subplot(1, 4, 4)
  subplot4.imshow(image)
  #
  for y in range(edge_height):
    for x in range(edge_width):
      if edge_image[y][x] != 0:
        edge_point = [y - edge_height_half, x - edge_width_half]
        ys, xs = [], []
        for theta_idx in range(len(thetas)):
          rho = (edge_point[1] * cos_thetas[theta_idx]) + (edge_point[0] * sin_thetas[theta_idx])
          theta = thetas[theta_idx]
          rho_idx = np.argmin(np.abs(rhos - rho))
          accumulator[rho_idx][theta_idx] += 1
          ys.append(rho)
          xs.append(theta)
        subplot3.plot(xs, ys, color="white", alpha=0.05)

  for y in range(accumulator.shape[0]):
    for x in range(accumulator.shape[1]):
      if accumulator[y][x] > t_count:
        rho = rhos[y]
        theta = thetas[x]
        a = np.cos(np.deg2rad(theta))
        b = np.sin(np.deg2rad(theta))
        x0 = (a * rho) + edge_width_half
        y0 = (b * rho) + edge_height_half
        x1 = int(x0 + 1000 * (-b))
        y1 = int(y0 + 1000 * (a))
        x2 = int(x0 - 1000 * (-b))
        y2 = int(y0 - 1000 * (a))
        subplot3.plot([theta], [rho], marker='o', color="yellow")
        subplot4.add_line(mlines.Line2D([x1, x2], [y1, y2]))

  subplot3.invert_yaxis()
  subplot3.invert_xaxis()

  subplot1.title.set_text("Original Image")
  subplot2.title.set_text("Edge Image")
  subplot3.title.set_text("Hough Space")
  subplot4.title.set_text("Detected Lines")
  plt.show()
  return accumulator, rhos, thetas


if __name__ == "__main__":
  for i in range(3):
    image = cv2.imread(f"sample-{i+1}.png")
    edge_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    edge_image = cv2.GaussianBlur(edge_image, (3, 3), 1)
    edge_image = cv2.Canny(edge_image, 100, 200)
    edge_image = cv2.dilate(
        edge_image,
        cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)),
        iterations=1
    )
    edge_image = cv2.erode(
        edge_image,
        cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)),
        iterations=1
    )
    line_detection_non_vectorized(image, edge_image)

向量化解决方案

import cv2
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.lines as mlines


def line_detection_vectorized(image, edge_image, num_rhos=180, num_thetas=180, t_count=220):
  edge_height, edge_width = edge_image.shape[:2]
  edge_height_half, edge_width_half = edge_height / 2, edge_width / 2
  #
  d = np.sqrt(np.square(edge_height) + np.square(edge_width))
  dtheta = 180 / num_thetas
  drho = (2 * d) / num_rhos
  #
  thetas = np.arange(0, 180, step=dtheta)
  rhos = np.arange(-d, d, step=drho)
  #
  cos_thetas = np.cos(np.deg2rad(thetas))
  sin_thetas = np.sin(np.deg2rad(thetas))
  #
  accumulator = np.zeros((len(rhos), len(rhos)))
  #
  figure = plt.figure(figsize=(12, 12))
  subplot1 = figure.add_subplot(1, 4, 1)
  subplot1.imshow(image)
  subplot2 = figure.add_subplot(1, 4, 2)
  subplot2.imshow(edge_image, cmap="gray")
  subplot3 = figure.add_subplot(1, 4, 3)
  subplot3.set_facecolor((0, 0, 0))
  subplot4 = figure.add_subplot(1, 4, 4)
  subplot4.imshow(image)
  #
  edge_points = np.argwhere(edge_image != 0)
  edge_points = edge_points - np.array([[edge_height_half, edge_width_half]])
  #
  rho_values = np.matmul(edge_points, np.array([sin_thetas, cos_thetas]))
  #
  accumulator, theta_vals, rho_vals = np.histogram2d(
      np.tile(thetas, rho_values.shape[0]),
      rho_values.ravel(),
      bins=[thetas, rhos]
  )
  accumulator = np.transpose(accumulator)
  lines = np.argwhere(accumulator > t_count)
  rho_idxs, theta_idxs = lines[:, 0], lines[:, 1]
  r, t = rhos[rho_idxs], thetas[theta_idxs]

  for ys in rho_values:
    subplot3.plot(thetas, ys, color="white", alpha=0.05)

  subplot3.plot([t], [r], color="yellow", marker='o')

  for line in lines:
    y, x = line
    rho = rhos[y]
    theta = thetas[x]
    a = np.cos(np.deg2rad(theta))
    b = np.sin(np.deg2rad(theta))
    x0 = (a * rho) + edge_width_half
    y0 = (b * rho) + edge_height_half
    x1 = int(x0 + 1000 * (-b))
    y1 = int(y0 + 1000 * (a))
    x2 = int(x0 - 1000 * (-b))
    y2 = int(y0 - 1000 * (a))
    subplot3.plot([theta], [rho], marker='o', color="yellow")
    subplot4.add_line(mlines.Line2D([x1, x2], [y1, y2]))

  subplot3.invert_yaxis()
  subplot3.invert_xaxis()

  subplot1.title.set_text("Original Image")
  subplot2.title.set_text("Edge Image")
  subplot3.title.set_text("Hough Space")
  subplot4.title.set_text("Detected Lines")
  plt.show()
  return accumulator, rhos, thetas


if __name__ == "__main__":
  for i in range(3):
    image = cv2.imread(f"sample-{i+1}.png")
    edge_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    edge_image = cv2.GaussianBlur(edge_image, (3, 3), 1)
    edge_image = cv2.Canny(edge_image, 100, 200)
    edge_image = cv2.dilate(
        edge_image,
        cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)),
        iterations=1
    )
    edge_image = cv2.erode(
        edge_image,
        cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)),
        iterations=1
    )
    line_detection_vectorized(image, edge_image)

五、结论

综上所述,本文以最简单的形式展示了Hough变换算法,该算法可以扩展到检测直线以外。多年来,对该算法进行了许多改进,使其可以检测其他形状,例如圆形,三角形甚至特定形状的四边形。这导致了许多有用的现实世界应用,从文档扫描到自动驾驶汽车的车道检测。

本文分享自微信公众号 - 小白学视觉(NoobCV),作者:小白

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++ OpenCV霍夫变换---直线检测

    霍夫变换是图像处理中从图像中识别几何形状的基本方法之一,应用很广泛,也有很多改进算法。主要用来从图像中分离出具有某种相同特征的几何形状(如,直线,圆等)。最基本...

    Vaccae
  • 【走进OpenCV】霍夫变换检测直线和圆

    学习计算机视觉最重要的能力应该就是编程了,为了帮助小伙伴尽快入门计算机视觉,小白准备了【走进OpenCV】系列,主要帮助小伙伴了解如何调用OpenCV库,涉及到...

    小白学视觉
  • Matlab 使用Hough霍夫变换进行直线检测+寻找最长直线

    先使用上文介绍的Prewitt算子将输入的图像边缘化处理,再使用霍夫变换检测直线。 其中使用到了matlab的hough,houghpeaks,houghl...

    大鹅
  • OpenCV与图像处理(四)

    以下代码均在python3.6,opencv4.2.0环境下试了跑一遍,可直接运行。

    Must
  • OpenCV与图像处理(十)

    图像处理是利用计算机对图像进行去噪、增强、复原、重建、编码、压缩、几何变换、分割,提取特征等的理论、方法和技术。图像处理中,输入的是低质量的图像,输出的...

    Must
  • OpenCV系列之霍夫线变换 | 三十二

    如果可以用数学形式表示形状,则霍夫变换是一种检测任何形状的流行技术。即使形状有些破损或变形,也可以检测出形状。我们将看到它如何作用于一条线。

    磐创AI
  • 独家 | 无人驾驶项目实战: 使用OpenCV进行实时车道检测

    大约十年前,我瞥见了第一辆自动驾驶汽车,当时Google仍在对初代无人车进行测试,而我立刻被这个想法吸引了。诚然,在将这些概念开源给社区之前,我必须等待一段时间...

    数据派THU
  • 计算机视觉 OpenCV Android | 基本特征检测之 霍夫圆检测

    凌川江雪
  • 用霍夫变换&SCNN码一个车道追踪器

    大多数车道都设计得相对简单,这不仅是为了鼓励有序,还为了让人类驾驶员更容易以相同的速度驾驶车辆。因此,我们的方法可能会通过边缘检测和特征提取技术先检测出摄像机馈...

    机器之心
  • 算法集锦(18) | 自动驾驶 | 车道线检测算法

    识别道路上的车道是所有司机的共同任务,以确保车辆在驾驶时处于车道限制之内,并减少因越过车道而与其他车辆发生碰撞的机会。

    用户7623498
  • 计算机视觉 OpenCV Android | 基本特征检测之 霍夫直线检测 详析

    对于每个平面空间的像素点坐标(x,y), 随着角度θ的取值不同,都会得到r值, (%+++%要点.B)而对于任意一条直线来说,在极坐标空间它的(r,θ...

    凌川江雪
  • OpenCV学习+常用函数记录③:霍夫变换与轮廓提取

    小黑鸭
  • OpenCV图像处理笔记(三):霍夫变换、直方图、轮廓等综合应用

    MiChong
  • Python opencv图像处理基础总结(六) 直线检测 圆检测 轮廓发现

    叶庭云
  • 何恺明团队最新研究:3D目标检测新框架VoteNet,两大数据集刷新最高精度

    当前的3D目标检测方法受2D检测器的影响很大。为了利用2D检测器的架构,它们通常将3D点云转换为规则的网格,或依赖于在2D图像中检测来提取3D框。很少有人尝试直...

    朱晓霞
  • 何恺明团队最新研究:3D目标检测新框架VoteNet,两大数据集刷新最高精度

    当前的3D目标检测方法受2D检测器的影响很大。为了利用2D检测器的架构,它们通常将3D点云转换为规则的网格,或依赖于在2D图像中检测来提取3D框。很少有人尝试直...

    新智元
  • CV学习笔记(十五):直线检测

    在这一篇文章中我们将学习使用OpenCV中的 HoughLines 函数和 HoughLinesP 函数来检测图像中的直线.

    云时之间
  • CV学习笔记(十五):直线检测

    在这一篇文章中我们将学习使用OpenCV中的 HoughLines 函数和 HoughLinesP 函数来检测图像中的直线.

    云时之间
  • OpenCV 系列教程5 | OpenCV 图像处理(中)

    霍夫变换是一种特征提取技术,主要应用于检测图像中的直线或者圆。 OpenCV 中分为霍夫线变换和霍夫圆变换。

    机器视觉CV

扫码关注云+社区

领取腾讯云代金券