一种基于多尺度边缘提取的陨石坑检测算法

席莎，邵巍

（青岛科技大学 自动化与电子工程学院，青岛 266042）

一种基于多尺度边缘提取的陨石坑检测算法

席莎，邵巍

（青岛科技大学 自动化与电子工程学院，青岛 266042）

针对星体表面的陨石坑可用于探测器的自主导航、障碍识别等任务，提出一种基于多尺度边缘提取的陨石坑检测算法。该算法首先利用高斯金字塔得到不同尺度的陨石坑图像；其次，针对不同尺度的陨石坑图像，利用EDPF边缘提取算法对陨石坑进行边缘提取，并连接关键边缘像素点为直线段来近似表示图像边缘；然后将具有相同偏转方向的边缘直线段连接成圆弧，并将有相似半径和中心的圆弧拟合成候选圆和椭圆；最后对候选圆、椭圆进行验证。该算法的优点在于，能够准确地检测出陨石坑，有较高的检测率，且对存在较多陨石坑的图像有较好的检测结果。

陨石坑检测；高斯金字塔；边缘提取；圆、椭圆拟合

0 引 言

从1958年美国和前苏联启动探月计划开始，各航空大国先后开展了多种类型的深空探测活动。实现探测器在行星表面的自主着陆是实现深空探测的关键技术之一。而陨石坑是一种广泛存在于行星、卫星、小行星和其他太阳系星体表面的自然路标，具有一致的几何特征和清晰的轮廓，将其作为自主导航系统中着陆器位姿估计中的跟踪目标显得越发重要[1-3]。

由于陨石撞击会出现陨石坑不完整或者重叠的情况，或者受风化等因素影响造成陨石坑边缘不明显，增加了陨石坑检测的难度，也对检测的准确性和稳定性提出了更高的要求。丁萌等人提出基于特征点的陨石坑检测算法[4]，该算法通过区域生长的方法提取陨石坑亮、暗两区域并通过椭圆拟合的方式获得陨石坑所在的圆或者椭圆。Yue等人提出一种基于面向对象方法的陨石坑检测算法[5]。Cheng等人提出了一种针对受光照和视角等因素影响的陨石坑检测算法[6]，通过定位点检测和边缘分组来选取椭圆弧，最后通过椭圆拟合来获取检测结果。针对陨石坑的分类问题，Cohen等人提出了一种基于遗传算法的陨石坑检测和分类算法[7]。Jin等人提出一种利用神经网络的方法来自动检测陨石坑及分类的方法[8]。这些算法大都利用机器学习或者区域生长的方法来获取陨石坑的边缘信息进而提取陨石坑，但是这些边缘提取算法并不能精确地确定陨石坑的边缘，且对于存在较多陨石坑的图像提取效果较差，检测率低。

针对上述问题，本文提出了一种基于多尺度边缘提取的陨石坑检测算法，利用高斯金字塔对陨石坑图像进行不同尺度的降采样，并结合边缘检测算法来提取更多的细节边缘信息，提高了检测准确度，之后采用圆弧和椭圆弧的提取，候选圆和椭圆检测，候选圆和椭圆的验证等步骤进行后续检测。文章最后分析了此算法的有效性和准确性，并计算了检测率、漏检率和误检率。

1 多尺度边缘检测

由于陨石坑的检测精度和图像分辨率有着重要关系：即分辨率越高，图像中陨石坑的细节特征越多；分辨率越低，细节特征会减少，比较明显的特征更加突出。因此为提高检测精度，本文提出利用高斯金字塔改变图像分辨率来对陨石坑进行检测。首先对陨石坑原始图像进行检测，估计图中陨石坑的大小及数目，并根据图像的分辨率确定合适的降采样尺度及金字塔的层数来获取不同分辨率的图像，然后对不同尺度的陨石坑图像分别进行检测。

图像边缘检测作为数字图像处理的基本方法，已经有了大量的研究，常用的Canny边缘检测[9]采用两种不同的阈值分别检测强边缘和弱边缘，使得检测出的陨石坑的边缘位置会有一定范围的误差，检测出的细节较多，且重要的边缘突出不明显。针对此问题，本文采用EDPF（earliest deadline and processing timefirst）边缘检测算法[10]，其步骤如下：

1）计算图像中每一个像素点的梯度值g（x，y）和梯度方向α：

其中：I（x，y）为像素点（x，y）的灰度值；gx（x，y）和gy（x，y）分别为像素点水平和垂直方向的梯度值。

2）选取四邻域内梯度值最大的像素点作为关键点，然后将具有相似梯度方向的关键点连接成线段。

3）验证边缘段。通过计算NFA（number of alarms），如公式（2）所示，剔除无效连接线段，生成边缘图像。

其中：ε=1；N为一段边缘段S上像素点的数目；p为一个像素点为对齐像素点的概率，这里取p=1/8，对齐像素是指两个像素点的梯度方向相似，即梯度角之差小于阈值。

边缘检测结果如图 1所示。从图 1可以看出EDPF算法提取的边缘比Canny算子更加平滑和完整，且没有过多的细节，陨石坑边缘显示突出；通过高斯金字塔之后的边缘检测结果可以看出，随着图像分辨率的降低，可以更精确地提取到图像中较大陨石坑的边缘，有利于后续的检测过程。

2 圆弧和椭圆弧的提取

对于边缘检测结果中闭合的边缘段，采用最小二乘算法[11]拟合成圆或者椭圆，并作为候选圆或者椭圆直接用于最后的验证。那么对于其余不闭合边缘段，则采用EDLines算法[12]用直线段来近似表示图像边缘，即用最小二乘算法将每一个边缘段拟合为直线段，并使得拟合误差小于一个像素精度，直线边缘段示意图如图 2所示。

图1 多尺度边缘检测结果Fig.1 Results of multiscale edge detection

图2 直线边缘段Fig.2 Line segments

假设每条直线段均为矢量，且一个圆弧至少由3条直线段组成。

首先计算直线段中任意相邻两条直线段之间的夹角，以及每条直线段的偏转方向：向右为-，向左为+；然后将夹角在所设阈值范围之内，且偏转方向相同的三条相邻直线段连接成圆弧或椭圆弧，这里夹角阈值范围取（6°，60°），其提取示意图如图 3所示。

图3 圆弧、椭圆弧提取示意图Fig.3 Circular，elliptic arc extraction

3 候选圆和椭圆的检测

由于弧长越长越接近完整的圆或者椭圆，所以根据圆弧或者椭圆弧的长度进行排序，把最长的圆弧或者椭圆弧作为基准弧，将满足半径约束和中心距离约束的圆弧或者椭圆弧与之连接在一起。半径约束是指，两个弧的半径差要小于所设阈值；中心距离约束是指两个弧的中心距离要小于所设阈值。候选圆和椭圆检测示意图如图 4、5所示。

图4 候选圆检测Fig.4 The candidate circle detection

图5 候选椭圆检测Fig.5 The candidate ellipse detection

图4（a）中，弧A1为基准弧，弧A2的半径超出了阈值范围，不满足半径约束，弧A3和A4可以与A1相连；图 4（b）中弧A3不满足中心距离约束，A2和A4可以与A1相连；同样图 5（a）中，弧A4的半径超出了阈值范围，弧A2和A3可以与A1相连，图 5（b）中弧A3不满足中心距离约束，A2和A4可以与A1相连。

对于满足上述两个约束的圆弧或者椭圆弧，用最小二乘算法拟合为圆或者椭圆，作为候选圆和椭圆用于最后的验证。

4 候选圆和椭圆的验证

由于经上述方法所检测的圆或者椭圆存在误检测，所以通过计算NFA对候选圆或者椭圆进行验证来剔除错误的检测，定义如下：

对于大小为N×N的图像，候选圆的NFA

候选椭圆的NFA

其中：ε=1；n为一个候选圆或者椭圆中像素点的数目；k为候选圆或椭圆中对齐像素点的数目；p为一个像素点为对齐像素点的概率，这里取p=1/8；因为圆和椭圆分别有4个和5个自由度，故N4和N5分别为图像中候选圆和候选椭圆的数目。

5 实验仿真与结果分析

利用NASA发布的月球上的陨石坑图像对该算法的准确性和有效性进行实验仿真验证。

由于陨石坑的检测精度不仅与图像的分辨率有关系，且与图像中陨石坑的大小以及拍摄高度有重要关系，可以结合原始图像的检测结果估计出图中陨石坑的大小，确定陨石坑直径所处范围，并根据图像的分辨率来确定将采样尺度和高斯金字塔的层数。

应用图 6～8给出的陨石坑原始图像进行实验验证，经过多次验证，且保证了有较高的检测率和较低的漏检率和误检率。图 6的原始图像分辨率小于500×500，利用高斯金字塔进行3次降采样，每次采样尺度为0.8；对于分辨率大于500×500的图 7和图 8，利用高斯金字塔进行3次降采样，每次采样尺度为0.5。首先对陨石坑原始图像进行检测，估计图中陨石坑的大小和数目，如图 6～8中的（a）所示；然后对降采样得到的不同尺度的陨石坑图像分别进行检测，如图6～8中的（b）和（c）所示；最后将检测结果均放到原始图像中进行显示，如图 6～8中的（d）所示。

图6 图像仿真结果Fig.6 The simulation result of images

图7 图像仿真结果Fig.7 The simulation result of images

图8 图像仿真结果Fig.8 The simulation result of images

根据图 6～8中陨石坑的原始总数目以及所检测到的数目可以计算出其检测率、误检率以及漏检率。

检测率是指所检测到的陨石坑数目占原始总数目的比例；漏检率是指未检测到的陨石坑数目所占的比例；误检率是指所检测到的陨石坑中错误检测的陨石坑数目占原始总数目的比例，检测结果如表1所示。

表1 陨石坑检测结果参数Table 1 Parameters of crater detection results

从仿真结果图 6～8可以看出，本文所提出的方法，可以有效地提取陨石坑的边缘信息，并且边缘较为平滑和完整，为之后的检测过程提供有效信息，原始图像的检测结果显示出对较小的陨石坑有比较准确的检测效果。从最终的陨石坑检测结果可以看出，本文算法可以检测到图像中绝大多数陨石坑，并且对于图像背景复杂且陨石坑数目较多的图像有较好的检测结果。经过大量实验验证，一般情况下，该算法的检测率高于85%且漏检率和误检率均为10%左右。

6 结 论

本文提出一种基于多尺度边缘提取的陨石坑检测算法。为提高检测率，首先利用高斯金字塔来获取不同尺度的陨石坑图像，通过EDPF提取陨石坑边缘，并用直线段近似表示边缘，检测出候选圆和椭圆之后通过计算NFA来验证。仿真实验表明这种方法具有较高的检测率和较低的漏检率。但是由于陨石坑受光照、重叠等因素影响，导致边缘信息提取不准确，从而影响陨石坑的检测结果。在以后的研究中将考虑把这些因素与此算法相结合进行分析，以提高检测精度和有效性。

[1]Leroy B，Medioni G，Johnson E，et al.Crater detection for autonomous landing on asteroids[J].Image and Vision Computing，2001，19（11）：787-792.

[2]何江.基于陨石坑匹配的月球精确着陆导航方法研究[D].哈尔滨：工业大学，2010.He J.Research on crater matching based navigation method for lunar precise landing[D].Harbin：Institute of Technology，2010.

[3]Paolo L，Marco C，Michele L.A multiayer perceptron hazard detector for vision-based autonomous planetary landing[J].Advances in Space Research，2016，58（1）：131-144.

[4]丁萌，曹云峰，吴庆宪.一种从月面图像检测陨石坑的方法[J].宇航学报，2009，30（3）：1243-1248.Ding M，Cao Y F，Wu Q X.A method of craters detection from the surface imagery of Moon[J].Journal of Astronautics，2009，30（3）：1243-1248.

[5]Yue Z Y，Liu J Z，Wu G G.Automated detection of lunar crater based on object-oriented approach[J].Chinese Science Bulletin，2008，53（23）：3699-3704.

[6]Cheng Y，Miller J.Autonomous landmark based spacecraft navigation system[C]//In 13th Annual AAS/AIAA Space Flight Mechanics Meeting.Puerto Rico：AAS/AIAA，2003：9-13.

[7]Cohen J P，Ding W.Crater detection via genetic search methods to reduce image features[J].Advances in Space Research，2014，53（12）：1768-1782.

[8]Jin S G，Zhang T Y.Automated detection of impact craters on Mars using a modified adaboosting method[J].Planetary and Space Science，2014，99（1）：112-117.

[9]Canny J.A computation approach to edge detection[J].Pattern Analysis and Machine Intelligence，1986，8（6）：679-698.

[10]Akinlar C，Topal C.EDPF：a parameter-free edge segment detector with a false detector control[J].International Journal of Pattern Recognition and Artifical Intelligence，2012，23（6）：862-872.

[11]Gander W，Golub G H，Strebel R，et al.Least-squares fitting of circles and ellipses[J].Bit Numerical Mathematics，1994，34（4）：558-578.

[12]Akinlar C，Topal C.EDLines：a real-time line detector with a false detector control[J].Pattern Recognition Letters，2011，32（13）：1633-1642.

通信地址：青岛市郑州路53号青岛科技大学自动化与电子工程学院（266042）

电话：（0532）84022684

E-mail：xisha_emma@126.com

A Craters Detection Algorithm Based on Multiscale Edge Extraction

XI Sha，SHAO Wei
（College of Automation & Electronic Engineering，Qingdao University of Science and Technology，Qingdao 266042，China）

As for the craters on the surface of planets can be used to autonomous navigation and obstacle recognition，the craters detection algorithm based on multiscale edge extraction is proposed.In this algorithm，different scale craters are detected through the Gaussian pyramid.For the different scales of crater images，firstly，using edge drawing parameter free（EDPF）to get edge segment of crater，and connecting critical edge pixels into line segment for representing the edge segment；then joining the line segments with the same turn direction into circular arcs，and fitting circular arcs with similar radius and center into candidate circles or ellipse，finally validating candidate circles and ellipses through calculating the number of false alarm（NFA）.Especially，the algorithm can be used to detect craters accurately with high detection rate，and has good performances in images with many craters.

craters detection；Gaussian pyramid；edge detection；circles,ellipses fitting

V448.224

A

2095-7777(2016)04-0384-5

10.15982/j.issn.2095-7777.2016.04.011

席莎，邵巍.一种基于多尺度边缘提取的陨石坑检测算法[J].深空探测学报，2016，3（4）：384-388.

Reference format：Xi S，Shao W.A Craters detection algorithm based on multiscale edge extraction [J].Journal of Deep Space Exploration，2016，3（4）：384-388.

席莎（1991- ），女，硕士研究生，主要研究方向：数字图像处理。

[责任编辑：高莎]

2016-07-28；

2016-08-12

国家重点基础研究发展计划“973”计划（2012CB720000）