Hough Transform

概念

Hough转换是由Hough于1959年首次提出的,是图像分析、计算视觉中的一种特征提取算法,这个算法的目的是通过投票程序找到具有特定形状物体的不完美实例,其中投票程序在参数空间完成。在参数空间中,目标候选是选取名为累积空间的局部最大。

在数字图像处理领域,存在寻找直线、圆、椭圆的子问题。许多情况下,边界检测是此问题的预处理步骤,然而,由于数据本身、边界检测算法存在的不足,可能会导致边界数据缺失、空间错位等问题。所以,需要将提取的边界特征组合成一些规则的图形(线、圆、椭圆)。Hough转换的目标就是将边界特征组合成物体候选

内容

Hough转换最简单的应用是检测直线,一条直线可以由斜率$k$和截距$b$确定,这里$$就构成了参数空间的一个点。给定一个点,可以找到经过这个点的无数条直线,每个直线在参数空间都对应一个点。但是这种方法有个缺陷,就是直线的斜率可能无限大。所以一般都把Hesse normal形式当做参数空间。

parameter space

具体地,以$y=kx+b$为例,可以将其写成$r=x\cos\theta+y\sin\theta$,如上图所示,$r$是直线到原点的距离,所以一条直线就对应参数空间中的一个点$$,这个参数空间就是直线对应的Hough Space

经过平面中的一个点可以确定无数条直线,每个直线都在参数空间对应一个点,这些点构成一个正弦波行。也就是说一个点在参数空间中对应一个正弦线。并且,共线的点在参数空间中会交于点$$,这个点就是这个直线对应的参数空间中的点。所以,查找共线点问题可以转化为检测共点曲线问题

数值计算方法

直线检测的方法如下,以二维直线为例。构建一个二维累加器,记录对应的离散$r,\theta$对应的累加值。对每一个点及其邻居点

  • 算法决定这两个点之间是否会构成直线,如果是,计算出这条直线对应的$$值
  • 在二位累加器中找到对应的位置,加一

计算完后,检查二维累加器,局部极大值点可能就对应一条直线,当然直线的数量需要合适阈值决定。下图是一个例子,example

泛化

To Be Continue
上面是直线检测的方法,参数空间是二维的。同理地,圆和椭圆都可以通过三维参数空间搞定。方法同上。

广义的方法于1981年由Dana H. Ballard提出,见https://en.wikipedia.org/wiki/Generalised_Hough_transform


引用

[1]. Hough transform. From Wikipedia, the free encyclopedia

分享到