S04-CH05基于Hough变换的圆检测仿真实验

软件版本：VIVADO2017.4

操作系统：WIN10 64bit

硬件平台：适用米联客 ZYNQ系列开发板

米联客(MSXBO)论坛：www.osrc.cn答疑解惑专栏开通，欢迎大家给我提问！！

5.1 概述

      本章介绍了如何使用HLS设计一个基于Hough变换的圆检测算法，通过一组仿真验证了整个算法的有效性。在一些特征物体具有特定的形状时，此算法可方便对目标进行识别，方便定位，具有一定得实用价值。使用者可以对其进行拓展，设计基于Hough变换的直线检测算法，感兴趣的可以尝试一下。

5.2 Hough变换原理介绍

      霍夫变换(Hough Transform)是图像处理中的一种特征提取技术，该过程在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特定形状的集合作为霍夫变换结果。霍夫变换于1962年由Paul Hough 首次提出，后于1972年由Richard Duda和Peter Hart推广使用，经典霍夫变换用来检测图像中的直线，后来霍夫变换扩展到任意形状物体的识别，多为圆和椭圆。霍夫变换运用两个坐标空间之间的变换将在一个空间中具有相同形状的曲线或直线映射到另一个坐标空间的一个点上形成峰值，从而把检测任意形状的问题转化为统计峰值问题。

5.2.1 Hough变换直线检测

      我们知道，一条直线在直角坐标系下可以用y=kx+b表示, 霍夫变换的主要思想是将该方程的参数和变量交换，即用x,y作为已知量k,b作为变量坐标，所以直角坐标系下的直线y=kx+b在参数空间表示为点(k,b)，而一个点(x1,y1)在直角坐标系下表示为一条直线y1=x1·k+b，其中(k,b)是该直线上的任意点。为了计算方便，我们将参数空间的坐标表示为极坐标下的γ和θ。因为同一条直线上的点对应的(γ,θ)是相同的，因此可以先将图片进行边缘检测，然后对图像上每一个非零像素点，在参数坐标下变换为一条直线，那么在直角坐标下属于同一条直线的点便在参数空间形成多条直线并内交于一点。因此可用该原理进行直线检测。

参数空间变换结果

      如图所示，对于原图内任一点(x,y)都可以在参数空间形成一条直线，以图中一条直线为例有参数(γ,θ)=(69.641,30°)，所有属于同一条直线上的点会在参数空间交于一点，该点即为对应直线的参数。

5.2.2 Hough变换圆检测

      继使用hough变换检测出直线之后，顺着坐标变换的思路，提出了一种检测圆的方法。
1 如何表示一个圆？
与使用（r,theta）来表示一条直线相似，使用（a,b,r）来确定一个圆心为（a,b）半径为 r的圆。
2 如何表示过某个点的所有圆？
某个圆过点（x1,y1），则有：(x1-a1)^2 + (y1-b1)^2 = r1^2 。
那么过点（x1,y1）的所有圆可以表示为（a1(i),b1(i),r1(i)），其中r1∈（0，无穷），每一个 i 值都对应一个不同的圆，（a1(i),b1(i),r1(i)）表示了无穷多个过点（x1,y1）的圆。
3 如何确定多个点在同一个圆上？
如(2)中说明，过点（x1,y1）的所有圆可以表示为（a1(i),b1(i),r1(i)），过点（x2,y2）的所有圆可以表示为（a2(i),b2(i),r2(i)），过点（x3,y3）的所有圆可以表示为（a3(i),b3(i),r3(i)），如果这三个点在同一个圆上，那么存在一个值（a0,b0,r0），使得 a0 = a1(k)=a2(k)=a3(k) 且b0 = b1(k)=b2(k)=b3(k) 且r0 =  r1(k)=r2(k)=r3(k)，即这三个点同时在圆（a0,b0,r0)上。
从下图可以形象的看出：

       首先，分析过点（x1,y1）的所有圆（a1(i),b1(i),r1(i)），当确定r1(i)时 ，（a1(i),b1(i)）的轨迹是一个以（x1,y1,r1(i)）为中心半径为r1(i)的圆。那么，所有圆（a1(i),b1(i),r1(i)）的组成了一个以（x1,y1,0）为顶点，锥角为90度的圆锥面。
三个圆锥面的交点A 既是同时过这三个点的圆。

5.2.3 Hough变换圆检测算法实现流程

      Hough变换时一种利用图像的全局特征将特定形状边缘链接起来。它通过点线的对偶性，将源图像上的点影射到用于累加的参数空间，把原始图像中给定曲线的检测问题转化为寻找参数空间中的峰值问题。由于利用全局特征，所以受噪声和边界间断的影响较小，比较鲁棒。

      Hough变换思想为：在原始图像坐标系下的一个点对应了参数坐标系中的一条直线，同样参数坐标系的一条直线对应了原始坐标系下的一个点，然后，原始坐标系下呈现直线的所有点，它们的斜率和截距是相同的，所以它们在参数坐标系下对应于同一个点。这样在将原始坐标系下的各个点投影到参数坐标系下之后，看参数坐标系下有没有聚集点，这样的聚集点就对应了原始坐标系下的直线。

      因此采用hough变换主要有以下几个步骤：

     1）Detect the edge

     检测得到图像的边缘

     2）Create accumulator 

     采用二维向量描述图像上每一条直线区域，将图像上的直线区域计数器映射到参数空间中的存储单元，p为直线区域到原点的距离，所以对于对角线长度为n的图像，p的取值范围为（0， n），θ值得取值范围为（0， 360），

定义为二维数组HoughBuf[n][360]为存储单元。

     对所有像素点（x，y）在所有θ角的时候，求出ρ.从而累加ρ值出现的次数。高于某个阈值的ρ就是一个直线。这个过程就类似于横坐标是θ角，ρ就是到直线的最短距离。横坐标θ不断变换，根据直线方程公司，ρ = xcosθ + ysinθ 对于所有的不为0的像素点，计算出ρ，找到ρ在坐标(θ,ρ)的位置累加1.

     3)  Detect the peaks, maximal  in the accumulator

     通过统计特性，假如图像平面上有两条直线，那么最终会出现2个峰值，累加得到最高的数组的值为所求直线参数。

5.3 Hough在HLS上的实现

      我们看下面一个实际问题：我们要从一副图像中检测出半径以知的圆形来。我们可以取和图像平面一样的参数平面，以图像上每一个前景点为圆心，以已知的半径在参数平面上画圆，并把结果进行累加。最后找出参数平面上的峰值点，这个位置就对应了图像上的圆心。在这个问题里，图像平面上的每一点对应到参数平面上的一个圆。

      把上面的问题改一下，假如我们不知道半径的值，而要找出图像上的圆来。这样，一个办法是把参数平面扩大称为三维空间。就是说，参数空间变为x–y–R三维，对应圆的圆心和半径。图像平面上的每一点就对应于参数空间中每个半径下的一个圆，这实际上是一个圆锥。最后当然还是找参数空间中的峰值点。不过，这个方法显然需要大量的存储空间，运行速度也会是很大问题。

      那么有什么比较好的解决方法么?我们前面假定的图像都是黑白图像(二值图像)，实际上这些二值图像多是彩色或灰度图像通过边缘提取来的。我们前面提到过，图像边缘除了位置信息，还有方向信息也很重要，这里就用上了。根据圆的性质，圆的半径一定在垂直于圆的切线的直线上，也就是说， 在圆上任意一点的法线上。这样，解决上面的问题，我们仍采用2维的参数空间，对于图像上的每 一前景点，加上它的方向信息，都可以确定出一条直线，圆的圆心就在这条直线上。这样一来，问题就会简单了许多。

      接下来我们来设计利用Hough变换来进行圆检测。

5.3.1 工程创建

Step1：打开HLS，按照之前介绍的方法，创建一个新的工程，命名为Hough。

Step2：右单击Source选项，选择New File，创建一个名为Top.cpp的文件。

Step3:在打开的编辑区中，把下面的程序拷贝进去：

       代码中有一段非常需要注意的如下几行代码，这段代码中使用了动态分配内存的函数malloc，另外HLS中不支持C++中使用new关键字分配内存的方法。该函数只能用于在综合文件中进行仿真，主要是解决大数组所造成的的编译出问题，详细介绍可参考ug902关于Array的章节。

        另外需要注意的是malloc 函数返回的是 void * 类型。对于C++，如果你写成：

int *count = malloc(Size * sizeof(int