基于Hough变换的月表陨坑检测算法改进及应用研究

周兰凤 李 玲 方 华* 章民融

1(上海应用技术大学计算机科学与信息工程学院 上海 201418) 2(上海市计算技术研究所有限公司 上海 200040)

0 引 言

目前有许多目标需要先进行迅速准确的类圆形检测,因此,从一幅图片中快速准确地检测出类圆,是一个有必要的研究问题,但在图片数据量日益增大的情况下,所有现有的圆形或椭圆形检测方法在不同的方面均存在一些问题。

近些年来,人们致力于圆形、椭圆形等的识别,以便能快速从一幅图片中快速、准确地检测出类圆,从而进一步进行目标检测。由于图像的复杂性以及类圆形参数较多,至今没有统一的方法来检测和识别类圆形图像。对于标准圆检测,文献[1]总结了在各种研究中圆检测常用的几种算法,如经典Hough算法、随机Hough算法和广义Hough算法,并提出将其应用到自动测试织物防水性能中。尚璐等[2]提出从椭圆的弧长着手,椭圆的一般方程及参数通过同一段弧长的边缘点的位置信息和梯度信息确定,该算法的有效性和检测时间均优于一般的检测算法。韦宏强等[3]结合边界跟踪算法与Hough变换能够快速准确地计算出椭圆参数,并形成椭圆边界链码,消除噪声及非闭合的数据,达到较好的实验效果。王艳芳[4]利用椭圆的闭合边界的特点,给出了一种高效检测椭圆的方法,提出椭圆边界链码的概念对椭圆进行边缘检测和跟踪,并使用滤波消除噪声及非闭合的数据使得边缘检测更加清晰,以形成椭圆边界链码,在链码上寻找对偶点并进行Hough变换,从而精确检测出椭圆。本文结合类圆形状的具体特征,应用几何概念对所要识别的图像进行灰度转换及二值化,依次获取图像的边缘,舍弃较为分散的点,构成图形边缘,除此之外,使用Hough变换进行类圆参数的提取,得到该类圆形的中心。文献[15]提出多圆检测,通过区域生长沿水平和垂直方向搜索候选圆并用Helmholtz原则进行验证。可以有效检测重叠圆形轮廓。

Fourie[6]基于噪声影响和大型复杂图像,改善了在圆检测中使用“和谐搜索”(HS),使算法能够在较大的数据集中稳健地找到多个圆圈。综上,本文对Hough圆变换做出一系列改进,并对类圆形的具体轮廓进行分析,来对该类圆形进行检测并识别出边缘。

1 Hough圆变换

取二维图像空间中任意圆,圆半径为R、横纵坐标分别为x、y,转换为三维参数空间中的一个点,该过程称为Hough变换[7],即将二维图像空间中的边缘像素点对应为极坐标中的点,然后把三维参数空间中的坐标点元素对应的值依次累加,得到的累积最大值即圆心所在点[8]。

圆的一般方程如下:

(x-a)2+(y-b)2=R2

(1)

具体参数如图1所示。

图1 圆参数示意图

由图1可知,(a,b)为该圆圆心,R为该圆半径。在直角坐标系中,将圆上的点(x,y)转换到三维空间中,对应的公式如下:

x=a+Rcosθ

y=b+Rsinθ

(2)

在参数空间中任取一边缘点(x0,y0),以半径R0映射到参数空间。将这个边缘点代入式(2),变换后可得:

(3)

式中:θ∈[0,2π)。由式(3)可得,对θ进行遍历,图像空间上的点(x0,y0)全部映射到参数空间即为一个圆。由此我们可以推出,在参数空间中的任意一个边缘点对应到参数空间相连后均生成一个圆[9]。

对原始图像使用Hough变换进行圆检测时,具体的检测步骤如下:

(1) 首先原始图像进行分析预处理,对图像做灰度化和二值化操作。

(2) 对目标图像进行类圆形的边缘检测,发现可能的边界。

(3) 在参数空间ρ-θ中建立一个累加数组,数组初值为0。

(4)
图像中被检测类圆形的参数ρ和θ由峰值检测取得。

参数空间需等分成m行、n列,m为θ的等分数,n为ρ的等分数,并设置累加值矩阵。设置半径最小刻度、角度最小刻度、半径的最大值和最小值。遍历所有的像素点,求出a和b的值。然后判断(a,b)是否在矩阵(m,n)中,如果(a,b)在该范围内,累加器加1,从而获得Hough累积矩阵[10]。

在圆的检测中需要设置阈值,使用最大累加值确定阈值。搜索超过阈值的点对应的参数即圆的参数。使用不同的阈值将获得不同的检测效果,如果阈值设置为0.75,那么大于最大累加值的75%的累积矩阵对应的圆都可以检测出来[11]。具体圆形检测原理如图2所示。

图2 Hough变换原理

2 本文的类圆检测改进算法

2.1 系统功能流程

具体算法功能流程如图3所示。

图3 系统功能流程

2.2 基于圆周角的类圆检测算法

类圆圆心的获取方式如下:首先,需要对已经获取的图像边界点进行过滤,以获取一种连续边界。假设类圆圆心为O点,在该图像所在的平面建立一条水平扫描线,依次从该类圆形的边缘向下扫描,在一维空间中,中点计数采用Hough变换的方法,计数最大值对应的中点即可看作类圆心O[12]。

本文首先通过边缘检测查找出该目标图形的轮廓,依次遍历轮廓上的每一个点,进行数值比对以获得轮廓上最远距离的两个点,取圆上任意一点(除这两点之外),最远距离的两点的连线视为该类圆形的直径,判断该直径所对的角度范围是否在80°～100°左右,若是,则对该边缘进行描绘并给出中心点O。具体参数如图4所示。

图4 圆周角a

在该算法中,首先需要对原图进行边缘检测,在保留原有图像属性的情况下,显著减少图像的数据规模,具体边缘检测步骤如下[13]:

(1) 使用高斯滤波去除噪声达到平滑图像的目的。

(2) 寻找该类圆形边界的强度梯度,即根据不同像素值对图像进行划分。

(3) 用非最大抑制技术沿边缘方向追踪边缘点来消除边缘误检。

(4) 使用双阈值的方法来决定可能的边界,并绘出边界。

在边缘检测成功之后查找图片中所需要判断点的轮廓,依次遍历轮廓上的每一个点来得到轮廓上最远的两个点,如图4所示的AB,在圆上任取一点(除这两点之外),判断AB边所对应的角a是否在80°～100°之间,若该角度在该范围内,则可以对该图形进行标记,可用于进一步的识别。

下面给出该算法核心函数的具体实现:

(1) 获取类圆直径的平方,和直径与圆周的轮廓的两个交点。

1. # 读其中一个轮廓序列,开始提取,读其中一个序列中的元

# 素点

2. # 对轮廓上的每一个点进行遍历,找出最远的两个点,作为

# 直径,中心点为圆心,

3. # 轮廓上任一点,该三点构成圆周角进行判断,若在90°左

# 右,则画圆

4. def get_center_diam(data=np.ndarray):

5. max=0

# 直径的平方

6. point_max=[]

# 轮廓上距离最远点

7. points=data.tolist()

8. count=len(data.tolist()) # 一个轮廓序列的点个数

9. for i in range(count):

10. points[i][0][0]

11. # i是取第i个点,第一个0去除一层外括号,第二个0是取

# 第一个值

12. length=(points[i][0][0]-points[0][0][0])**2+(points[i][0][1]-points[0][0][1])**2

#判断直径

13. if length>max:

14. max=length

15. point_max=points[i][0]

16. return max,point_max,points[0][0]

17. # max为直径的平方,point_max为距离最远点,points[0][0]

# 为起始点

(2) 圆周角计算函数如下:

1. def get_angle(pointa=[],pointb=[],pointc=[]):

2. # 定义直径所在的两端点和圆上一点

3. a=pointa[0]

4. # 三点构成的三角形,计算所需要余弦角的各个线段长度

5. dx1=pointa[0]-pointc[0]

6. dy1=pointa[1]-pointc[1]

7. dx2=pointb[0]-pointc[0]

8. dy2=pointb[1]-pointc[1]

9. angle_line=(dx1*dx2+dy1*dy2)/cmath.sqrt((dx1*dx1+dy1*dy1)*(dx2*dx2+dy2*dy2)+1e-10)

10. return cmath.acos(angle_line)*180/3.141592653

11. # 采用反余弦公式计算出该角度数

(3) 获取直径和具体角度判断如下:

1. def get_result(max=0,point_max=[],data=np.ndarray):

2. if point_max==[]:

3. return False

4. max=cmath.sqrt(max*1.0)

5. # 获取直径长度

6. points=data.tolist()

7. # 转化为列表形式

8. count=len(data.tolist())

9. # 一个轮廓序列的点个数

10. for i in range(count):

11. # 遍历轮廓序列,调用角度函数计算该圆周角,判断圆周#角是否在80°～100°之间

12. if i>0:

13. t=abs(get_angle(points[0][0],point_max,points[i][0]))

14. if t>80 and t<100 and points[i]!=point_max:

15. return True

16. return False

2.3 基于圆半径的类圆检测算法

本文算法基于圆半径的特点,从其中心到其周边的任何线段都相等,提出若某一图形上的任何一点到判定后的中点都在该半径内波动,则该图形可近似看成圆形。

在此算法中,首先需要通过边缘检测识别出该图像轮廓,依次遍历该轮廓上的点,由此,可以得到轮廓上距离最远的两个点,如图5所示,AB的中点O假定为圆心,则该两点间距离可假设为直径。若在识别出的边缘上每个点到这个中点的距离在这个半径数值附近波动,即m和n的长度可近似相等,在此还需对该半径数据做归一化处理,以解决直径大的直径小的波动范围不一致问题,由此可近似判定该图形类圆。

图5 椭圆参数及点O到曲线边缘的距离

3 实验结果分析

本文算法使用Python语言实现,采用Python 3.7、OpenCV 3.4.3.18。本文算法对于图像的基础处理步骤如下:代码首先需要对原图像进行边缘检测,二值化操作后确定该类圆形的边缘。对于图像边缘的任意一个非零点都需要采用Sobel算子,对于参数指定的每一个像素都需要在累加器中叠加并做出标记。累加器图像的反比分辨为1,Canny边缘函数的高阈值设置为60,圆心检测阈值设置为26。圆心检测阈值需要根据图像中的圆大小设置,当这幅图片中的圆越小,那么此值就应该被设置得越小,避免噪声的产生。在实验结果上,该类圆的边缘检测在实验中达到了很好的实验效果。

本实验在Windows 10系统,基于x64的处理器,具体处理器为Inter(R) Core(TM) i7-10510U CPU @ 1.80 GHz 2.30 GHz上实现,内存大小为12.0 GB。

与Hough圆变换相比,在某些情况下本实验对于类圆形的检测成功率较高,第一幅测试图的具体参数为675×446(24-bit color),该测试图仅用于测试该算法识别的精确度。第二幅测试图的具体参数为309×163(24-bit color),该陨石坑测试图来源于中国探月工程。第三幅数字高程图(DEM)来源于月球探测轨道器(LRO)和Kaguya数字高程图的随机截图。具体实验结果如图6-图12所示。

图6 原图

图7 Hough圆算法运行结果

图8 改进算法运行结果

图9 陨石坑测试

图10 陨石坑测试结果

图11 陨石坑DEM截图

图12 测试结果

可以发现该算法对于类似圆形的识别成功率较高,在边缘清晰度较高的情况下可以准确描绘出图像的边缘。但在边缘清晰度不高的情况下,可以直接对该图像边缘进行描绘,对于数字高程图而言,边缘检测的阈值范围设置为(30,70),阈值分割后得到的图像的检测效果较好,如图12所示。在本实验中,Canny边缘检测算法发挥了很好的作用,对边缘描绘的准确度较高,但本实验依旧存在一些不足,对于圆周角变化较大的圆形识别成功率较低且在实际应用中需要对阈值参数进行调节,才可以得到更好的实际应用效果。

类圆形的识别与检测的算法在工业检测线、生物医学监测设备、自动化装配线上,都有广泛的应用。文献[4]将基于直径累积的Hough变换检测圆算法应用到人头轮廓统计和人数统计上。但是该算法在人数较多或人头轮廓非圆形时,会出现漏检等情况,且该算法对于直径的判断复杂度较高。文献[15]中提出一种基于曲线拟合的圆形检测算法,对公路上的交通信号灯进行识别。但该算法仅针对圆形曲线拟合情况来判断该标志是否是圆心,对圆形的检测成功率不高。

本文提出的针对圆形基本特点的类圆形检测算法,对于类圆形检测成功率能达到90%,在检测目标数目较多时也能达到很好的识别效果且当圆形重叠时也可以很好地对该类圆形的边缘进行描绘,具有很好的鲁棒性,可应用于公交客流统计、自动识别棒材半径、自动识别圆形汽车零件,可以满足工业生产实时性的要求。

本文算法在陨石坑的识别上可以得到很好的应用。在月球车的路径规划方面,对于陨石坑的识别与检测可以给路径规划提供较好的数据依据以规避障碍,因此本文算法的提出是有必要的。下一步的研究重点是将深度学习与本文算法结合,期望能在陨石坑的识别中得到很好的效果。

4 结 语

Hough变换在各种形状检测方面取得了很好的成果,但在对椭圆以及类圆形的检测上,由于参数的增多,Hough变换检测成功率急剧降低。但在很多实际应用中比如人流统计、对人头轮廓进行检测计数,以及在月球地形中关于陨石坑的识别上均需要对类圆形进行边缘检测。本文结合类圆形的特点,提出两种检测方案,应用Canny算法进行边缘检测,分别从圆周角和圆心距对该图形进行判断,并勾画出该图形的轮廓和中心,该实验在某些时候可以取得较好的实验效果,在类圆圆心的选取上与标准Hough变换相比,计算复杂度降低,因此具有更高的检测精度且该算法对于圆形重叠也有很好的检测效果。将该算法更精确地应用到月球陨石坑的检测中,将是进一步研究的重点。