Hough变换 检测矩形

最近要写个算法自动找出图片中用来标示的指定颜色的矩形,最先想到的是古典并简洁的 Hough变换。不过真动手实现起来却也不是那么简单。

Hough变换 最简单的应用是辨识图片中的直线,对应的变换是将图中的点变换成 Hough空间 中的两个参数(直线的斜率和截距,或者其它参数表示)。而对于矩形来说,Hough空间 就需要有4个参数(左上点 x_1, y_1 和右下点 x_2, y_2 的坐标)。这样相对于直线检测,算法的空间复杂度和时间复杂度有了平方级数的增加,对于大一些的图片很容易就吃掉数G的内存。

对于时间复杂度,因为要找的是指定颜色的矩形,那么颜色差别大的点可以完全不用考虑进去,这样可以使需要处理的点减少大半。
对于空间复杂度,显然4维的 Hough空间 中有相当大的冗余(右下点一定在左上点的,嗯,右下,就是说 x_1<x_2, y_1<y_2),用更有效的数据结构可以消除掉这部分的空间冗余。
当然,如果上面的优化还不够的话,就得用图像处理中常用的最后一手——降低原始图片的分辨率,做完计算再升回去。

还需要注意的是,最后在 Hough空间 里选择矩形的时候需要做一次归一化。不同大小的矩形在 Hough空间 的权重也不同。

1962年为了找气泡室中粒子轨迹而发明的 Hough变换 在今天仍应用频繁。有回归起源的在 LHC 中找 μ介子 的轨迹,也有应用在车载系统中检测行驶中车辆是否偏离车道。

Advertisements
This entry was posted in Computer and Internet, Programming and Algorithm and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s