数字化转型浪潮中,金融行业如何破局?获取学习视频 了解详情
写点什么

如何用霍夫变换算法实现直线检测

  • 2020 年 5 月 28 日
  • 本文字数:5826 字

    阅读完需:约 19 分钟

如何用霍夫变换算法实现直线检测

原文最初发表于 Medium 博客,经原作者 Socret Lee 授权,InfoQ 中文站翻译并分享。


导读:如果告诉你一张图里面有一条看起来挺直的线,让你指出来线在哪、线的指向是向哪个方向。你肯定可以不假思索地告诉我线的位置和方向。但这个任务对计算机来说,可不是一件简单的事,因为图片在计算机中的存储形式就是 0001101111001010110101…,根本没有办法从这个序列中直接给出是否有直线以及直线的位置。要怎么才能让计算机自己学会找直线呢?这就要用霍夫变换了。霍夫变换是一种特征提取,广泛应用于在图像分析、计算机视觉以及数字影像处理。霍夫变换是用来识别找出目标中的特征,例如线条。它的算法过程大致如下:给定一个对象,要辨别的形状的种类,算法会在参数空间中执行投票来决定对象的形状,而这是由累加空间里的局部最大值来决定。本文阐述了一种在图像中寻找直线的算法。



I. 动机

最近,我发现自己需要在一个 APP 中加入一个文档扫描功能。在做了一些研究之后,我偶然看到了 Dropbox 机器学习团队成员 Ying Xiong 写的一篇文章《快速、准确的扫描文档检测》(Fast and Accurate Document Detection for Scanning)。这篇文章解释了 Dropbox 机器学习团队如何实现文档扫描的功能,并重点介绍了他们所经历的步骤和每一步所使用的算法。正是通过这篇文章,我了解到一种叫做霍夫变换(Hough Transform)的算法,以及如何利用霍夫变换来检测图像中的直线。因此,在本文中,我想讲解一下霍夫变换算法,并提供霍夫变换算法在 Python 中的“从头开始”实现。


II. 霍夫变换

霍夫变换是 Paul V.C. Hough 在 1962 年申请为专利的一种算法,最初是为了识别照片中的复杂线条而发明的。自该算法发明以来,经过不断的修改和增强,现在已经能够识别其他形状,如圆形和四边形等特定类型的形状。为了了解霍夫变换算法的工作原理,就必须了解这四个概念:边缘图像、霍夫空间和边缘点到霍夫空间的映射、表示直线的另一种方式,以及如何检测直线。


边缘图像


Canny 边缘检测算法。来源:https://aishack.in/tutorials/canny-edge-detector/


边缘图像是边缘检测算法的输出。边缘检测算法通过确定图像的亮度或强度急剧变化的位置来检测图像中的边缘(摘自《边缘检测:用 Python 进行图像处理》(Edge Detection — Image Processing with Python),2020 年)。边缘检测算法的示例包括:CannySobelLaplacian 等。通常边缘图像是二值化的,二值化意味着图像所有的像素都是 1 或 0。对于霍夫变换算法,关键是首先要进行边缘检测,以生成边缘图像,然后将其作为算法的输入。


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


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


霍夫空间是一个二维平面,其中横轴表示斜率,纵轴表示直线在边缘图像上的截距。边缘图像上的线以 的形式表示。边缘图像上的一条线在霍夫空间上产生一个点,因为一条线的特征是其斜率为 ,截距为 。另一方面,边缘图像上的边缘点 ,可以有无限多条线穿过它。因此,一个边缘点在霍夫空间中以 的形式产生一条线。在霍夫变换算法中,霍夫空间用于确定边缘图像是否存在直线。


表示直线的另一种方式


用于计算直线斜率的方程式


的形式来表示直线,用斜率和截距表示霍夫空间,这种方法存在一个缺陷。在这种形式下,该算法将无法检测出垂直线,因为对于垂直线来说,斜率 是不确定的/无穷大。从编程的角度来说,这意味着计算机需要无限数量的内存来表示 的所有可能值。为避免出现这个问题,直线改为由一条称为法线的直线表示,这条线穿过原点并垂直于这条直线。法线的形式为 ,其中, 是法线的长度, 是法线与 x 轴之间的夹角。



直线的另一种表示及其对应的霍夫空间


使用这个方法,不再用斜率 和截距 来表示霍夫空间,而是用 表示,其中横轴为 值,纵轴为 值。边缘点映射到霍夫空间的工作原理与此类似,只是边缘点 现在在霍夫空间生成的是余弦曲线而不是直线。这种正常的直线表示法消除了在处理垂直线时出现的 的无界值的问题。


直线检测


在图像中检测直线的过程。护肤空间中的黄点表示直线存在,并由 θ 和 ρ 对表示


如前所述,边缘点在霍夫空间中产生了余弦曲线。由此,如果我们将所有的边缘点从边缘图像映射到霍夫空间,它将产生大量的余弦曲线。如果两遍边缘点位于同一直线上,则它们对应的余弦曲线将在特定的 对上彼此相交。因此,霍夫变换算法是通过查找交叉点数量大于某一阈值的 对来检测直线。值得注意的是,如果不进行一些预处理的话,比如在霍夫空间上进行邻域抑制,以去除边缘图像中类似的直线,这种阈值的方法可能不一定能得到最好的结果。


III.算法

  1. 确定 的范围。通常, 的范围为 ,其中 是边缘图像的对角线的长度。重要的是要对 的范围进行量化,这意味着这一范围的可能值的数量应该是有限的。

  2. 创建一个名为累加器的二维数组,该数组表示具有维数 的霍夫空间,并将其所有制初始化为零。

  3. 对原始图像进行边缘检测。这可以用你选择的任何边缘检测算法来完成。

  4. 对于边缘图像上的每个像素,检查改像素是否为边缘像素。如果是边缘像素,则循环遍历 的所有可能值,计算相应的 ,在累加器中找到 的索引,并基于这些索引对递增累加器。

  5. 循环遍历累加器中的所有制。如果该值大于某一阈值,则获取 的索引,从索引对中获取 的值,然后可以将其转换回 的形式。


IV. 代码实现

非向量化解决方案

import cv2import numpy as npimport matplotlib.pyplot as pltimport 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 cv2import numpy as npimport matplotlib.pyplot as pltimport 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)
复制代码


V. 结论

最后,本文以最简单的形式介绍了霍夫变换算法。如前所述,该算法可以扩展到直线检测之外。多年来,这种算法得到了许多改进,现在能够检测其他形状了,如圆形、三角形,甚至是特定形状的四边形等。由此产生了许多有用的现实世界应用,从文档扫描到自动驾驶汽车的车道检测。我相信,在可预见的未来,还会有更多令人惊叹的技术在这一算法的推动下问世。


参考文献


原文链接


https://towardsdatascience.com/lines-detection-with-hough-transform-84020b3b1549


2020 年 5 月 28 日 16:322857

评论

发布
暂无评论
发现更多内容

CSS技巧 | 优雅的处理文本溢出截断

devpoint

CSS 6月日更

建信金科大咖访谈:人脸识别技术的发展与应用

金科优源汇

🌏【架构师指南】总结分库分表的实现方案

浩宇天尚

分库分表 架构师 6月日更 实现方案

基于WebRTC的1对1通话实战(一)环境搭建

IT酷盖

音视频 WebRTC

从货币流动性角度看区块链流动性发展

CECBC

现代分布式架构设计原则-可观测性

余朋飞

微服务 监控 日志 可观测性 链路追踪

面试官问“你有什么问题要问我”,如何完美回答?

架构精进之路

6月日更

「SQL数据分析系列」4. 过滤操作

数据与智能

数据库 SQL语言

Linux之ls命令

入门小站

Linux

云上 ARM 实例应用优化?现在带你读懂它!

亚马逊云科技 (Amazon Web Services)

前端开发华为鸿蒙系统应用 OpenHarmony JS

孙叫兽

华为 鸿蒙 OpenHarmony 鸿蒙开发 引航计划

页面怎么布局,当然是Grid ԅ(¯﹃¯ԅ)

空城机

JavaScript 大前端 6月日更 页面布局

百度的云图丹青

脑极体

阿里P8工作10年,离职时发现只剩这份《Java架构速成》笔记了

Java架构师迁哥

Python分类预测模型

Qien Z.

Python 预测模型 6月日更

Kubernetes手记(12)- StatefulSet 控制器

雪雷

k8s 6月日更

区块链技术让传统旅游业焕发新机

CECBC

VS code常用插件推荐(总结整理篇)

孙叫兽

vscode 大前端 插件 Vue 3 引航计划

别闹,那个在加密世界拿着长枪的库币

猫Buboo

区块链 区块链+ 加密资产

小伙伴们在催更Spring系列,于是我写下了这篇注解汇总!!

冰河

spring 程序员 架构师 aop ioc

5分钟速读之Rust权威指南(二十二)迭代器

码生笔谈

rust

夯实区块链产业发展根基是当务之急 标准体系、知识产权是国际竞争角力之焦点

CECBC

前端 JS 之 AJAX 简介及使用

编程三昧

JavaScript ajax 大前端 异步请求

企业如何成功应用机器学习?看这四点就够了!

亚马逊云科技 (Amazon Web Services)

JDK 工具大合集

看山

Java 6月日更

详解 SQL 的集合运算

悟空聊架构

数据库 sql 6月日更 集合运算

MySQL基础之十三:约束

打工人!

MySQL 6月日更

发布60分钟!霸榜Github的阿里面试指导小册,啃透涨薪10k

Java架构师迁哥

话题讨论|从2021苹果全球开发者大会中,你得到了什么启发?

石云升

wwdc 话题讨论 6月日更

论现代科技发展趋势:停滞、减速 OR 蓄力?

老猿Python

发展 科技 软件技术

OpenVINO+微软黑客松比赛项目简介

IT蜗壳-Tango

IT蜗壳 6月日更

“一键上链”技术大牛教你快速构建链上应用

“一键上链”技术大牛教你快速构建链上应用

如何用霍夫变换算法实现直线检测_AI_Socret Lee_InfoQ精选文章