此算法建立在Canny算法的基础上，对Canny算法检测出的边缘图像进行拟合，因此要用到Canny算法返回的边缘图像及梯度方向矩阵。Canny算法相关内容详见上一篇博客：Canny边缘检测算法原理及代码实现

1. 算法原理

  Hough Transform(霍夫变换)是早期的一种以投票方案进行图形拟合的算法。所谓拟合就是要将图像中的一些边缘用数学方式来描述，可以使人们更好的操作使用图像提供的信息。相比较最小二乘法、鲁棒估计以及RANSAC方法，霍夫变换的优点在于可以进行多目标的拟合。本次在此讨论研究霍夫圆的拟合原理。

  霍夫圆算法的实现一共可分为两个步骤：

1. 建立霍夫参数三维空间，并对空间内各个单元进行投票
2. 设置阈值从投票结果中筛选合适的圆，并做非极大化抑制

1.1 建参数空间并投票

  与直线的拟合不同，在霍夫变换中圆的拟合需要三个参数，即(x，y，r)，此处x与y表示坐标，r表示圆的半径。参数是根据以下公式做定的：
$$y=mx+b(X-x{)}^2+(Y-y{)}^2=r^2$$  参数空间的建立及如何投票见下图：
  上图解析：在遍历整个图像的边缘图时，如果它是边缘点，那么就要拿这个点来对参数空间投票，因为圆上一点处的法线定过圆心，所以在此只考虑法线方向，即梯度方向。而对参数空间量化主要是为了降低计算量，同时扩大投票空间，使结果更可控。
  对于（x,y）点处可投的参数空间计算如下：
$$x=x\pm stepy=y\pm step\times tan\theta$$$$r=r\pm \sqrt{x^2+y^2}$$  step为设置的步长，theta为梯度方向角度。初设x与y为图像的横纵坐标，r为0。还要注意参数范围，x，y非负且不可大于图像长宽，r非负且不可大于图像对角线长度。

1.2 筛选结果并做非极大化抑制

  筛选是对参数空间的投票结果进行筛选。设定阈值，遍历参数空间，当投票数大于阈值时初步认定为可能的圆，将参数放入列表。之后遍历列表，设定圆心最小距离，检查相邻圆圆心的距离是否大于最小圆心距离，如果大于，则仍定为不同的圆，如果小于，则认为是同一圆，此时做非极大化抑制，此处可采用均值的思想。

2. 代码实现

'''
在实现Canny算法的基础上
需要Canny算法得到的梯度矩阵与边缘检测结果图
'''

import numpy as np
import math

class Hough_transform:
    def __init__(self, img, angle, Hough_transform_MinDis, Hough_transform_step, Hough_transform_threshold):
        '''
        :param img: 输入的图像
        :param angle: 输入的梯度方向矩阵
        :param Hough_transform_MinDis: 两个圆心之间的最小距离
        :param Hough_transform_step: Hough变换步长大小
        :param Hough_transform_threshold: 筛选单元的阈值
        '''

        self.img = img
        self.angle = angle
        self.y, self.x = img.shape[0:2]
        self.radius = math.ceil(math.sqrt(self.y**2 + self.x**2))   #图像对角线长度，圆直径的最大长度
        self.Hough_transform_MinDis = Hough_transform_MinDis
        self.Hough_transform_step = Hough_transform_step
        self.vote_matrix = np.zeros([math.ceil(self.y / self.Hough_transform_step), math.ceil(self.x / self.Hough_transform_step), math.ceil(self.radius / self.Hough_transform_step)])
        self.Hough_transform_threshold = Hough_transform_threshold
        self.circles = []

    def Hough_transform_algorithm(self):
        '''
        按照 x,y,radius 建立三维空间，根据图片中边上的点沿梯度方向对空间中的所有单
        元进行投票。每个点投出来结果为一折线。
        :return:  投票矩阵
        '''
        print ('Hough_transform_algorithm')
        # ------------- write your code bellow ----------------

        for i in range(1, self.y - 1):
            for j in range(1, self.x - 1):
                if self.img[i][j] > 0:
                    x = j
                    y = i
                    r = 0
                    while x > 0 and y > 0 and x < self.x and y < self.y:
                        self.vote_matrix[math.floor(y / self.Hough_transform_step)][math.floor(x / self.Hough_transform_step)][math.floor(r / self.Hough_transform_step)] += 1
                        x = x + self.Hough_transform_step
                        y = y + self.angle[i][j] * self.Hough_transform_step
                        r = r + math.sqrt(self.Hough_transform_step ** 2 + (self.angle[i][j] * self.Hough_transform_step) ** 2)
                    x = j - self.Hough_transform_step
                    y = i - self.angle[i][j] * self.Hough_transform_step
                    r = math.sqrt(self.Hough_transform_step ** 2 + (self.angle[i][j] * self.Hough_transform_step) ** 2)
                    while x > 0 and y > 0 and x < self.x and y < self.y:
                        self.vote_matrix[math.floor(y / self.Hough_transform_step)][math.floor(x / self.Hough_transform_step)][math.floor(r / self.Hough_transform_step)] += 1
                        x = x - self.Hough_transform_step
                        y = y - self.angle[i][j] * self.Hough_transform_step
                        r = r + math.sqrt(self.Hough_transform_step ** 2 + (self.angle[i][j] * self.Hough_transform_step) ** 2)

        print(self.vote_matrix.shape)
        # for i in range(0, self.vote_matrix.shape[0]):
        #     for j in range(0, self.vote_matrix.shape[1]):
        #         for k in range(0, self.vote_matrix.shape[2]):
        #             if self.vote_matrix[i][j][k] > self.Hough_transform_threshold:
        #                 print(self.vote_matrix[i][j][k])

        # ------------- write your code above ----------------
        return self.vote_matrix


    def Select_Circle(self):
        '''
        按照阈值从投票矩阵中筛选出合适的圆，并作极大化抑制。
        此处的极大化抑制并非单纯选取极大值作为最终结果，而是将临界点进行平均处理得到结果。
        :return: None
        '''
        print ('Select_Circle')
        # ------------- write your code bellow ----------------
        
        candidateCircles = []
        for i in range(0, self.vote_matrix.shape[0]):
            for j in range(0, self.vote_matrix.shape[1]):
                for k in range(0, self.vote_matrix.shape[2]):
                    if self.vote_matrix[i][j][k] > self.Hough_transform_threshold:
                        y = i * self.Hough_transform_step + (self.Hough_transform_step / 2)
                        x = j * self.Hough_transform_step + (self.Hough_transform_step / 2)
                        r = k * self.Hough_transform_step + (self.Hough_transform_step / 2)
                        candidateCircles.append([math.ceil(x), math.ceil(y), math.ceil(r)])
        print("候选圆：{}".format(candidateCircles))

        # 将可能的圆归类并做极大化抑制
        x, y, r = candidateCircles[0]
        possibleCircles = []
        middleCircles = []
        for circle in candidateCircles:
            if math.sqrt((x - circle[0])**2 + (y - circle[1])**2) <= self.Hough_transform_MinDis:
                possibleCircles.append([circle[0], circle[1], circle[2]])
            else:
            	#.mean(axis=__) 对矩阵数据平均，axis可空，axis=0按列平均、axis=1按行平均
                result = np.array(possibleCircles).mean(axis=0)     
                middleCircles.append([result[0], result[1], result[2]])
                possibleCircles.clear()
                x, y, r = circle
                possibleCircles.append([x, y, r])
        result = np.array(possibleCircles).mean(axis=0)
        middleCircles.append([result[0], result[1], result[2]])

        # 此处是为了将middleCircles内的各项按每项第一个元素大小进行升序排列
        def takeFirst(element):
            return element[0]

        middleCircles.sort(key=takeFirst, reverse=False)
        x, y, r = middleCircles[0]
        possibleCircles = []
        for circle in middleCircles:
            if math.sqrt((x - circle[0])**2 + (y - circle[1])**2) <= self.Hough_transform_MinDis:
                possibleCircles.append([circle[0], circle[1], circle[2]])
            else:
                result = np.array(possibleCircles).mean(axis=0)
                print("Circle core: (%f, %f), Radius: %f" % (result[0], result[1], result[2]))
                self.circles.append([result[0], result[1], result[2]])
                possibleCircles.clear()
                x, y, r = circle
                possibleCircles.append([x, y, r])
        result = np.array(possibleCircles).mean(axis=0)
        print("Circle core: (%f, %f), Radius: %f" % (result[0], result[1], result[2]))
        self.circles.append([result[0], result[1], result[2]])

        # ------------- write your code above ----------------
        return self.circles

    def Calculate(self):
        '''
        按照算法顺序调用以上成员函数
        :return: 圆形拟合结果图，圆的坐标及半径集合
        '''
        self.Hough_transform_algorithm()
        self.Select_Circle()
        return self.circles

  运行程序，得到最终结果图为：

  本博客主要内容参考课程：计算机视觉，鲁鹏，北京邮电大学
  如有错误，恳请在评论区指正，同时欢迎在评论区交流学习！！！