数字图像处理

数字图像处理

Github 的 README.md 并不支持公式的渲染,所以部分原理讲解的东西移到这个篇章的博客中。

本篇包含:

  • 骨架提取
  • 霍夫变换
  • Canny 边缘检测
  • RANSAC

Skeleton

前一段时间在看折痕消除的一篇论文的时候提到了提取文字的骨架,就重新复习一下《数字图像处理》这本书中关于骨架的知识。

集合 的骨架的 概念上很简单:

的一点, 内以 为圆心的最大圆盘,则不存在包含 且位于 内的更大圆盘,满足这些条件的圆盘 称为最大圆盘

是一个最大圆盘,则它在两个或多个不同的位置与 的边界接触。

的骨架可以用腐蚀和开运算来表示:

式中, 是一个结构元, 表示 的连续 次腐蚀,同时, 被腐蚀为一个空集前的最后一个迭代步骤:

Canny

只使用梯度做边缘检测的一个很大的问题是:对噪声过于敏感,所以提出了 Canny 边缘检测算子。

Canny 算法基于以下三个目标:

  • 低错误率:所有边缘都应该被找到,并且不应有虚假响应。
  • 边缘点应该被很好的定位:已定位的边缘必须尽可能接近真实边缘,也就是说,由检测子标记为边缘的一点和真实边缘的中心之间的距离应最小。
  • 单个边缘点响应:对于每个真实的边缘点,监测子应该只返回一个点,也就是说,真实边缘周围的局部最大数应该是最小的,这意味着检测子不应识别只存在单个边缘的多个边缘像素。

与之对应的,Canny 边缘检测包含 5 个步骤:

  • 平滑(Suppress noise)
  • 梯度计算(Compute gradient magnitude and direction)
  • 非最大值抑制(Apply non-maximum suppression)
  • 滞后阈值法/双阈值法(Hysteresis thresholding/Double thresholding)
  • 连通性分析(Connectivity analysis to detect edges)

首先采用高斯模糊来平滑图像。令 表示输入图像,并令 表示高斯函数:

用 G 和 f 的卷积得到平滑后的图像

在这之后计算梯度幅度和方向:

由于梯度图像通常在局部极大值附近包含一些宽脊,下一步非极大值抑制就是细化这些宽脊。

我们首先将所有可能的边缘方向量化为 4 个方向范围,如 0,45,90,135 如果该点处梯度的幅值小于该方向上的相邻两个点(在该点两侧),则抑制(赋值为 0),否则不变。

得到的图像 是只包含细化边缘的结果,然后我们对 进行阈值处理,以减少假边缘点。 Canny 算法使用滞后阈值处理,一个高阈值 和一个低阈值 。高低阈值的比率应该在 2 到 3 之间。

阈值运算可以看做创建了两个新的图像

这两个分别代表“强”边缘像素和“弱”边缘像素,所有的强边界像素均被假设为有效的边缘像素,并被立即标记,如果弱边缘的像素连接到了强边缘(8邻域),则这些弱边缘也被认为是图像的边界,所以最后一步就是用BFS 判断一遍弱边缘是不是连接到了强边缘,如果连接到了,该点也可以认为是强边缘,就从该点继续向 8 邻域搜索。

Hough Transform

已知一副图像中的 n 个点,假设我们希望找到这些点中位于直线上的子集,一种可能的解决方法是。首先找到由每对点确定的直线,然后寻找特定直线的哪些点的所有子集。这种方法涉及寻找 条直线,然后将每个直线执行 次比较,计算困难。

Hough 提出了一种方法,通常称为霍夫变换。令 表示 平面上的一点。并考虑一条直线的斜截式:

满足过点 的直线有无数条,此时我们考虑 平面,并将直线改写成为:

在该空间下,通过原直线的两个点 一定在某个点相交,这个点就是直线的斜率和截距。事实上,直线上的所有的点在该平面上都相交于一个点。

为了解决直线斜率无穷大的问题,我们用另外一种直线的标准式:

在具体的算法计算上,霍夫变换首先将参数空间划分为多个累加单元。假设其中 是期望的参数值范围。坐标 处具有累加值 的单元对应参数空间 的方格。最初,这些单元格被设置为 0,对 平面的非背景点 ,对于所有可以取的 ,求得 ,将该值四舍五入到 轴上最接近的单元格,若选择一个 的值解得 ,则令:

最后,当 大于一个特定的值时,认为存在一条对应的直线。

Author

Ctwo

Posted on

2021-09-29

Updated on

2021-10-09

Licensed under

Comments