计算机视觉（本科）北京邮电大学鲁鹏第一次作业钱币检测

任务

编写一个钱币定位系统，其不仅能够检测出输入图像中各个钱币的边缘，同时，还能给出各个
钱币的圆心坐标与半径。

步骤1 ：使用 Canny 算法提取图像边缘

步骤2：在边缘图上利用Hough变换计算圆心与半径

高斯滤波器可以针对服从高斯分布的噪声进行平滑。

图像在 $x$ 方向的偏导数可以用核 $\begin{pmatrix} -1 & 1 \\ \end{pmatrix}$ 卷积以近似求解，在 $y$ 方向的偏导数可以用核 $\begin{pmatrix} -1 \\ 1 \\ \end{pmatrix}$ 卷积以近似求解。也就可以求得每点的梯度。

为了解决上图中边缘太粗的问题，进行非极大化抑制。从被识别为边缘的点中去除那些比周围点梯度幅值更小的点（即只保留边缘最中心的点）。

为解决上图中边缘断裂的问题，使用双阈值法进行补全。遍历所有在高阈值下被识别为边缘的点，查看梯度方向上的邻近点的梯度幅值是否位于低阈值与高阈值间，若是则将该邻近点的幅值提升为高阈值，即将其变为边缘点。

对直线：转为极坐标系，每点对穿过它的直线投票，将 $\theta$ 离散化，遍历 $\theta$ ，计算 $\rho$ 即可枚举穿过一点的直线。

对圆：对于一个点，枚举经过且圆心在该点的梯度方向的圆。在 $x,y,r$ 三维空间中投票，找到得票数最大的位置坐标。

同样需要离散化，以 step 为块大小进行分块。

对于一个点，遍历 $x,y,r$ 投票，每次应该只走会使得其中一个改变的最小步数，否则会错过一些圆。

在参考实现代码中，每次 $x$ 都走 step 步，这样对于那些梯度方向接近竖直的点，会错过一些圆。由于进行了分块，所以原图中的 $x$ 坐标为整数不代表在整除 step 下也是整数，也就会被忽略，但这些被忽略的点可能 $y$ 坐标不同，即可能有新的圆出现却被忽略。

但是在实际上，虽然理论上复杂度相同，但实践时时间相差很大，且由于圆上有很多点，上述影响会变小，所以还是使每次 $x$ 都走 step 步。

Hough 变换中的非极大化抑制：在参考实现代码中，按照 $(x,y)$ 坐标将距离小于某个阈值的点聚簇，取均值为簇的中心。聚簇两次。

这样以 $(x,y)$ 为坐标的聚簇的一个显然的问题是会导致一组同心圆中只能识别一个，半径取为均值。如下图。红色线为识别出的圆（比较细）

一个简单的做法是改为以 $(x,y,r)$ 为坐标进行聚簇。