计算机视觉理论笔记 (8) - 形状检测 (Shape Detection)
形状检测
总览
为了识别物体,我们需要提取和分析其结构元素(structural elements)。典型的结构元素是线条(lines)和基本几何结构(basic geometric shapes)。
直线检测 (line detection)
直线是一个抽象的几何对象,在数学上由等式描述:
y = a * x + b, a 和 b 是描述直线的系数。
假设你需要在一个包含N点的二进制图像中找到直线。 有什么可能的解决方案?
可能解决方案:查找由每对点确定的所有线。 将那些具有相似参数的行组合在一起。 计算平均参数,以一条平均线代表每个组。但是当点很多的时候,我们会创建出非常多直线。
Hough Transform (霍夫变换)
通过转换
将坐标系 y = ax + b 转化为
坐标系 b = -x a + y
a和b的取值能够代表在某一点上形成的直线的可能情况。因此我们能够从多个点中寻找其在 a-b 图上的最多交汇点,该交汇点的a值和b值能够描述拟合的直线。
整个数组的元素初始化都为0,对于(a, b) 坐标系中的每一行,将获得的值a和b舍入到最接近的单元格。如果一条线穿过一个单元格,则其累计值将会增加一。算法的准确性(accuracy)取决于数组大小。
垂直线的问题 (The Problem of Vertical Lines)
垂直线的参数a是个无限大值 x = y / a + C。
一种可能的解决方案是使用极坐标系 (Polar Coordinate System) 而不是笛卡尔坐标系 (Cartesian Coordinate System)。
x * cos θ + y * sin θ = ρ (其中,ρ不能大于图像的对角线 diagonal,θ的值范围是 0 ~ 360°)
红线:θ = -45°,ρ = 10
蓝线:θ = 135°,ρ = 10
黄线:θ = 45°,ρ = 10
其中,红线和蓝线是平行的且ρ都是正数。若θ的值被限定在 [-90,…,90],则蓝线的表示应该更改为:θ = -45°,ρ = -10。同时,ρ的范围也就是 [-H, … +D],H代表原图像的高,W代表原图像的宽。
对于图像空间中的每一个点xi, yi:
- 对于所有θ的使用公式计算ρ:ρ = xi * cosθ + yi * sinθ
- 在坐标 (θ,ρ) 处,递增与单元格对应的数字。
在累加器矩阵 (accumulator array) 中的峰 (peak) 对应了检测到的线的参数。
直线定位(Line Localisation)
对于不同的点组 (point group),霍夫变换可能会产生完全相同的结果,这些点分布在由相同参数 (same parameters) 描述的直线上。
可能需要进行连通性分析 (connectivity analysis) 以识别连续的直线。 小于特定最小长度的段(segment)可以忽略。
直线粗细
只有抽象几何直线未定义粗细。如果图像线的粗度为几个像素,则霍夫变换可以找到由不同点组合产生的多条线。
这个问题可以通过以下方法消除:
- 闭合线 (close line) 的参数平均 (parameter averaging)。
- 通过形态学腐蚀 (morphological erosion) 使图像直线变细。
形状检测
路标识别
我们如何从霍夫变换中推断出图像中存在三角路标呢?
- 首先,使用颜色信息提取候选对象 (candidates)。
- 接着,使用角度与角度之和为180属性之间的关系,得出这三条线之间的关系是等边三角形。
圆形检测 (Circle Detection)
在 (x - cx)2 + (y - cy)2 = R2 中,对于红色圆上的每一个 (x, y),都有
(cx - x)2 + (cy - y)2 = R2
交汇的点(cx, cy) 就是 目标半径下 的圆心点。
应用
- 自动装配线必须检测橡胶垫圈和垫片的存在和位置。(内部半径 15pix,外部半径 20pix)
- 使用霍夫变换的圆检测结果如下所示。 结果的质量在很大程度上取决于您可以找到的边缘的质量,并且还取决于您对要检测的圆的大小有多少先验知识。
霍夫变换的注意事项
- 霍夫变换可用于定位直线,圆和简单的多边形。
- 计算的复杂度和内存要求很高。
- 可能需要连通性分析(connectivity analysis)以丢弃不相关的点或短线段。
- 如果可以解决歧义(ambiguities),则横向直方图技术(Lateral Histogram Techiniques)是形状检测和定位(shape detection and location)的低复杂度替代方案。