阴阳师图像识别脚本--霍夫圆检测

上一章讲到当用霍夫变换来检测圆时，确定一个圆的参数有三个 $(a,b,R)$ ,分别为圆心的x轴坐标，y轴坐标，和半径R。圆的参数方程如下

$x=a+R\cos \theta$

$y=b+R\sin \theta$

即

$a=x-R\cos \theta$

$b=y-R\sin \theta$

在检测圆时，霍夫变换的映射不同于直线。直线的映射是 $(x,y)\rightarrow (\theta ,\rho )$ ,圆的映射是 $(x,y,R )\rightarrow (a,b,R,\theta)$ 。直观的讲就是查找每一个特殊像素点 $(x,y)$ ，并枚举R值，代表该特殊像素点在半径为R的圆上（这里的R值可以自己取，比如你想找半径为2的圆，R值可以设为2，在houghcicle函数里可以取一个R的范围）。之后枚举 $\theta$ （这里 $\theta$ 可以取 $(0^\circ ,360^\circ )$ ），然后用上面的公式算出对应的 $(a,b)$ 坐标（圆心坐标）。这一步类似于之前讲的投票过程，可以参考上一章霍夫变换。

通过查看之前的过程可以看出当R值是一个范围时，需要搜索的不止是特殊像素点 $(x,y)$ 还需要搜索所有可能的R值，复杂度从 $O^2$ 变为 $O^3$ ，当数据量较大时需要用到优化算法。opencv里的优化算法是霍夫梯度法。

在讲霍夫梯度法之前引入卷积和sobel算子的概念

卷积算法如下（简单介绍一下算法，原理可以参考https://www.zhihu.com/question/22298352）

假设有一卷积核（卷积运算单位）如下

（这就是sobel算子）

有一待处理矩阵

矩阵计算分三步，第一步将卷积核转制180度，这一步这里先略过（查了很多篇博客都没有这一步，我最后说一下我的理解），先用最初的卷积核

第二步将矩阵卷积核中心对准待处理矩阵的第一个元素，对应元素相乘，没有元素的地方补零

新矩阵的（1，1）位置的值为所有对应元素相乘的求和，此处为

$1*0+2*0+1*0+0*0+0*1+0*2+-1*0+-2*5+-1*6=-16$

重复此操作，并对每一个原矩阵中的元素进行运算，最终得到一个新矩阵，就是卷积之后的矩阵，结果如下

图片转载自https://blog.csdn.net/xvshu/article/details/81302441

sobel算子的原理就是用sobel算子对原图像的像素矩阵进行卷积运算并得到新矩阵。sobel算子有含有两个方向的运算

左边为x轴方向，右边为y轴方向

假设我们想处理（x，y）像素点，并对其用sobel算子进行卷积操作，被处理的像素矩阵如下

先用第一个矩阵相乘求和

$f(x,y)=(f(x+1,y+1)-f(x-1,y+1)) + (2(f(x+1,y)-f(x-1,y))+(f(x+1,y-1)-f(x-1,y-1))$

可以看到 $f(x,y)$ 的值变为右边三个元素减去左边三个元素的加权求和（第二行元素的权重为2）。新的值可以理解成该像素点沿x轴像素的变化量。同y轴额sobel算子可以得到沿外轴的像素变化量。

我们将用x轴sobel算子算出来的新像素值定为 $G_x$ ，y轴sobel算子算出来的新像素值定为 $G_y$

$g(x,y)=\vert G_x \vert +\vert G_y \vert$

g(x,y)反映的就是该点像素的总的变化量，这里讲一下之所以前面的sobel算子在卷积计算时不翻转180度是因为翻转之后算出来新 $G_x$ 是原 $G_x$ 的相反数，取绝对值之后没有变化，所以不需要翻转，而在别的卷积运算中是需要进行翻转操作的。

介绍完sobel算子后终于可以讲霍夫梯度法了。。。好累啊

霍夫梯度法的原理分三步，第一步是先对图片进行边缘检测（canny边缘检测，有时间也会讲讲这个算法），获得图片中所有边缘

第二步：用sobel算子计算所有非边缘像素的梯度

第三步：利用得到的梯度，在累加器中累加该梯度直线上的每一个像素点（投票过程）

介绍一下梯度的概念，梯度代表该点像素变化速度最快的方向，原公式为

这里我们用 $(G_x,G_y)$ 近似梯度（x,y方向的变化量），并得出梯度的方向（这里sobel算子要反转了）

在霍夫梯度法当中，我们已经对图像进行了边缘处理（canny边缘检测），所有边缘上像素变化最大的方向是垂直于该边缘的方向，所以梯度的方向就可以看成是边缘的垂直方向，以下图为例

从上图中可以看出当所有特殊像素点围成一个圆时，其梯度方向的直线全部相交于圆心，假如我们用上面提到的方法，可以得到圆心像素点的累加器的值最高。我们就可以通过这个方法，查找累加器中最高的值获得圆心坐标。这里还想再提一下的是，当我们用上面的方法对直线上每一个点的累加器加一，得到的累加平面与原图有相同的分辨率（假设原图是8*8像素，累加平面也是8*8）而在opencv中的houghcircle函数第四个参数dp，代表的是原图分辨率与累加平面分辨率的比值。以8*8像素为例，若原图的分辨率是8*8像素，此时设dp值为4，累加平面的分辨率就为2*2像素。

在得到所有可能的圆心坐标后，遍历每一个圆心坐标，枚举所选R值的范围（也可以在houghcircle函数中定义），统计在这个半径上所有特殊像素，设定阈值，只要在该半径上特殊像素超过阈值，就可以认为存在该半径的圆，并在图中标记出来。

这个方法相比于标准的霍夫变换少了一个枚举 $\theta$ 的过程，时间复杂度降低了不少，但是好像还是 $O^3$ 。。。

效果图（边缘用黑色加粗有点不明显）