基于方向梯度直方图的陨坑预检测算法

郭永茂，周石博，高 艾

(1.中国电子科技集团公司第五十四研究所，河北 石家庄 050081；2.北京理工大学 深空探测技术研究所，北京 100081)

0 引言

行星探测是深空探测的一种重要探测方式，行星表面大多布满陨石坑或撞击坑。陨石坑具有明显的特征，规则的几何形状等特点，适合对行星地质进行分析。同时陨坑可以作为探测器自主导航的自然路标，提高导航精度，陨坑也是探测器着陆过程中障碍检测和规避的主要目标之一。由于陨坑检测的效率和准确性决定了导航的可靠性与精度，因此陨坑检测算法成为学术界研究的热门。国内外学者针对这一问题进行了深入的研究。由于陨坑边缘在图像上显示清晰，因此可以通过边缘检测并进行拟合方式检测陨坑。在这方面，Meng D[1]和冯军华[2]等人通过对阴影区的选择与边缘检测实现陨坑检测。Yu M[3]和Qin T[4]等人确定光照方向矢量，提高了陨坑检测的准确率。Leroy B[5]和Templeton T[6]等人对小天体表面的陨坑检测进行了研究，并通过边缘匹配实现了陨坑检测；另一方面，由于多数陨坑形状相似，且多为圆形，因此可以通过采用建立图像模板进行陨坑检测。 Kim J R[7]和Bandeira L[8]等人生成相应的陨坑模版，然后通过模版匹配实现陨石坑的检测。Wang Y[9]和Schmied S A[10]等人通过boosting投票方法对陨坑进行检测，同样取得了较好的效果。Kamarudin[11]、Yue Z Y[12]、Bue B D[13]、Vijayan S[14]和 Loncaric S[15]等人对陨坑检测的图形图像特性进行分析，取得了很大进展。丁萌[16]、于正湜[17]和陈建清[18]等人也分别提出了陨坑图像检测方法。这些方法对陨坑检测方法的发展做出了贡献，但是由于陨坑地形天然的复杂性，陨坑检测方法依然面临精度、效率与实时性不足等困难。多数陨坑检测方法对图像内包括单一陨坑区域的检测性能较好，对全景图像的检测则存在实时性和准确性不高的困难。因此需要一种能够对图像进行预处理并快速从全景图像中提取出包含单一陨坑的子图的方法。方向梯度直方图(HOG)是近年来提出的一种基于梯度信息描述物体的特征，因此十分适合解决陨坑检测问题，同时运行效率较高，适合实时应用。结合HOG特征可以很好地解决目前陨坑检测过程中遇到的困境。

本文针对陨坑检测对复杂全景图像检测的难点，提出了一种基于方向梯度直方图(HOG)特征的陨坑预检测方法，对图像提取可能存在陨坑的区域，提高陨坑检测的效率与精度。该方法首先通过建立标准陨坑模型并生成一定数量的陨坑地形图与随机地形图，对地形图提取HOG特征，作为训练正负样本并采用支持向量机(SVM)进行分类器学习。然后通过图像梯度对图像进行阈值分割，将图像梯度较大的区域作为潜在目标区域。最后通过训练后的支持向量机在潜在目标区域中进行滑窗检测，得到陨坑预检测的子区域，为陨坑检测算法提供较好的检测样本。仿真实验表明该方法能够提高陨坑检测的效率，预检测提供的图像子区域降低了陨坑匹配的错误率。

1 建立陨坑地形图像样本集

1.1 陨坑数学模型

尽管通过轨道器或天文观测可以获得大量的行星地表地貌图像数据，但是通过这些图像数据进行陨坑提取与检测并建立样本数据库依然十分困难。同时受到观测条件等限制，提取的陨坑图像并不一定能够包含全部可能光照或者形态，这样通过建立数据库实现陨坑检测是十分困难的；另一方面，陨坑的几何外形具有一定规律性，一般可以采用一个旋转曲面函数进行表示，因此可以通过人工手段生成陨坑图像。Golombek M[19]等人对月球表面的陨坑形状、大小和分布进行分析，所采用的陨坑模型通过多段线方程进行表示。由于陨坑形成时间的不同，其几何外形也有区别，所采用的描述方程也不一样。Pike[20]对大量月球陨石坑作了测量和计算，对于形成年代较近的陨坑或撞击坑，其剖面函数可以通过下式的经验公式近似。陨坑剖面示意图如图1所示。

式中，D为陨坑直径；H为陨坑高度；Hr为陨坑边沿高度；Pike给出月球陨坑可选参数为rin=1.01，ain=0.196，rout=1.014，aout=0.036，调整a，r的大小即可得到不同形态的陨坑剖面函数。基于以上分析，本文采用2个独立的方程来近似表达陨坑的边缘部分和碗形内部，并采用旋转面来近似整个陨坑。

图1 陨坑剖面示意

1.2 陨坑图像模拟

直接通过陨坑的数学模型模拟得到的陨坑地形缺乏真实感，主要是由于缺乏真实地形的起伏感和粗糙感，因此需要在数学模型的基础上叠加基础地形模型增加地形真实感。随机分形是指采用随机机制生成的一组分形集。行星表面作为自然地形，具有分形的自相似性，因此可以采用随机分形生成行星地形，增加模型真实感。分形地形可以通过多种方式生成，本文采用Perlin噪声算法生成地形，该方法生成的地形尖峰较少，适合作为基础地表地形。

Perlin噪声算法的原理是将地形平面离散为不同尺度的矩阵，不同尺度记为频率f，在每一个频率f下的矩阵中的每一个点为一个随机数。随机数的大小受振幅A限制，这样就得到了多组不同频率f和振幅A的地形矩阵。记最大频率为fmax，将其他频率f的矩阵离散插值为fmax大小，并将插值后的全部地形叠加即为基于Perlin噪声的地形模型。采用不同的随机数发生算法、插值算法和振幅A的大小即可得到不同形态的模拟地形。本文采用的频率f和幅值A共6组，变化规律如下式所示，生成的不同插值地形图如图2所示。

f=2i+1，A=27-i，i=1…6。

图2 不同幅值的地形数据

叠加后的地形图如图3(a)所示，整体地形起伏程度可以通过调整噪声幅值A进行调整。基础地形与陨坑叠加的结果如图3(b)所示，可以看出陨坑地形已经具有一定的真实性。

图3 行星表面地形模拟

陨坑图像往往包含由光照引起的阴影，在人工模拟陨坑图像的过程中不能忽视阴影的存在。OpenGL是一个跨编程语言、跨平台的编程接口规格的专业的图形程序接口。利用OpenGL可以方便快捷地实现计算机图形图像的渲染和显示。因此本文采用OpenGL对陨坑模型进行渲染，得到增加光照渲染后的模拟陨坑图像如图4所示。

图4 陨坑地形模拟渲染

2 基于HOG特征的支持向量机分类方法

2.1 HOG特征提取

灰度梯度直方图(HOG)特征是一种基于局部物体轮廓分布的特征描述子，通过将图像进行分割并统计梯度方向与大小得到该区域的梯度特征分布的统计结果。由于图像梯度直接反应物体在图像中的轮廓特征，因此对不同形状的物体，其梯度的统计结果也会有所不同。因此可以通过HOG特征对图像中不同类型的物体进行分类检测。HOG特征的检测步骤如下：

① 对输入图像进行梯度计算，具体方法为计算水平和垂直方向的梯度(gx，gy)，计算梯度大小和梯度方向。

② 将输入图像分割成等大小的小格(cell)，并将几个小格合并为一个小块(block)。块与块之间可以存在重叠，记块内格数为m。

③ 将梯度方向范围进行分割，例如0°～360°可以以40°为步长，分割为9个不同通道。步长的大小可以根据实际需要进行调整，记通道数为n。

④ 对每个小格统计内部每个像素的梯度方向直方图，直方图横坐标为通道数n，纵坐标为该通道内梯度幅值的叠加。每个小格可以构成一个n维向量。

⑤ 对每一个小块内的所有小格的向量进行归一化处理，降低阴影或光照对描述向量的影响。归一化方法为将块内所有向量串连得到mn维向量，采用L2归一化方法进行归一化，记v*为归一化后的向量，则

式中，v为归一化之前的向量；‖v‖2表示v的2阶范数；ε为一个较小的常数，避免分母为零。

⑥ 将所有按块归一化后的向量串连起来得到的特征向量即HOG特征向量。

陨坑的形状在图像中多为圆形或椭圆形，其轮廓特征与其他物体区别明显，利用HOG特征可以明显地区分陨坑和其他物体。

2.2 支持向量机分类学习方法

在提取出HOG特征后，本文采用支持向量机(Support Vector Machine，SVM)进行分类，SVM在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并且能够快速有效地区分高维向量，对非线性分类有较好的应用。SVM通过核技巧(kernel trick)可以将非线性分类问题变换为高维线性可分问题，将向量映射到一个高维空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有2个互相平行的超平面，分隔超平面使2个平行超平面的距离最大化。具体方法为：

① 构造正负样本集合

Φ{(x1，y1)，(x2，y2)，…，(xN，yN)}，xi∈Rn，yi∈{+1，-1}。选取适当的核函数k(x，x′)和适当的参数C，构造并求解最优化问题。

② 选择一个α*的分量，计算b*，

通过决策函数得到测试样本的正负集分类。

3 仿真实验

通过陨坑模拟函数生成约500幅不同光照角度与形态的陨坑图像作为SVM训练数据的正样本来源，同时根据随机地形生成算法生成同样数量不同光照条件与角度的普通模拟地形图像作为负样本。选取其中的50组正负样本图像如图5所示。

图5 正负样本数据

取其中一个正样本，小格大小为64*64，提取其中每个小格的HOG特征的结果如图6所示，可以看出HOG特征很好地表达了陨坑的形状特征，即梯度方向分布具有圆形的规律性。

图6 陨坑每个小格灰度方向特征统计

为了进一步降低检测时间，可以对图像进行一定的简单前背景筛选过程。方法是对梯度图像进行阈值分割，将梯度较高的区域进行二值膨胀，从而将窗口扫描的区域限制在膨胀后的前景图像区域内，降低检测时间。给出月球表面的实际照片作为测试图像，选择30*30、50*50和120*120等3个扫描窗口进行扫描，将窗口图像缩放至64*64的标准大小，预检测得到的包含陨坑的子图如图7所示。

检测效率与精度受到窗口数量和扫描步长的限制，是一个不断调节的过程，因此需要在实际飞行任务中提前设计合适的检测窗口尺寸与扫描步长以适应实际需要。经过调整，本文对图中的陨坑预检测过程耗时约10 s，单一子图的分类检测时间约为10 ms，同类型陨坑检测方法，如基于Haar特征的Adaboost方法的检测耗时约为60 s，单一子图的分类检测时间约为5 ms。由于Haar特征提取过程需要在图像检测前得到整幅图像的积分图，因此消耗的时间较长，不适合在线应用。在检测效率方面，本文采用的方法检测正确率为95%，相比Adaboost方法的检测正确率约为90%，但耗时更短。针对真实的环境检测，采用月球表面的实际照相作为测试图像，但是可以看出预检测能够将陨坑从背景图像中分割出，但是总体精度较低，存在大量错误区域，因此还需要更好的筛选过程。同时由于仅仅标记出陨坑可能存在的位置，对陨坑的精确定位无法完成，依然需要更加准确的陨坑检测方法，但是这些预检测区域已经大大降低了目前图像检测运行时间，并提高了检测精度，为后续更加准确的陨坑检测提供了帮助。

图7 月球表面陨坑图像与检测结果

4 结束语

针对于全景陨坑图像检测的实时性和有效性的难点，本文提出一种基于HOG特征的图像陨坑预检测算法，经过仿真分析可以发现本算法能够极大地缩小单一子图的分类和检测时间，同时检测正确率也在90%以上。在深空探测领域，面对大量的全景图像数据以及处理时效性的需求，该预检测算法能够快速有效地提取大量满足检测需求的备选陨坑图像，为后续深度数据处理提供了良好的基础。

[1] MENG D，CAO Y F，WU Q X.Autonomous Craters Detection from Planetary Image[C]∥International Conference on Innovative Computing Information and Control，IEEE，2008：443-443.

[2] 冯军华，崔祜涛，崔平远，等.行星表面陨石坑检测与匹配方法[J].航空学报，2010，31(9)：1858-1863.

[3] YU M，CUI H，TIAN Y.A New Approach Based on Crater Detection and Matching for Visual Navigation in Planetary Landing[J].Advances in Space Research，2014，53(12)：1810-1821.

[4] QIN T，ZHU S，CUI P，et al.An Innovative Navigation Scheme of Powered Descent Phase for Mars Pinpoint Landing[J].Advances in Space Research，2014，54(9)：1888-1900.

[5] LEROY B，MEDIONI G，JOHNSON E，et al.Crater Detection for Autonomous Landing on Asteroids[J].Image & Vision Computing，2001，19(11)：787-792.

[6] TEMPLETON T，SHIM D H，GEYER C，et al.Autonomous Vision-based Landing and Terrain Mapping Using an MPC-controlled Unmanned Rotorcraft[C]∥IEEE International Conference on Robotics and Automation，IEEE，2007：1349-1356.

[7] KIM J R，MULLER J P，GASSELT S V.Automated Crater Detection，A New Tool for Mars Cartography and Chronology[J].Photogrammetric Engineering & Remote Sensing，2005，71(10)：1205-1218.

[8] BANDEIRA L，SARAIVA J，PINA P.Impact Crater Recognition on Mars Based on a Probability Volume Created by Template Matching[J].IEEE Transactions on Geoscience & Remote Sensing，2007，45(12)：4008-4015.

[9] WANG Y，YANG G，GUO L.A Novel Sparse Boosting Method for Crater Detection in the High Resolution Planetary Image[J].Advances in Space Research，2015，56(5)：982-991.

[10] SCHMIED S A，BINNS J R，RENILSON M R，et al.A Novel Method for Generating Continuously Surfable Waves-comparison of Predictions with Experimental Results[C]∥International Conference on Ocean，Offshore and Arctic Engineering，2011：83-93.

[11] KAMARUDIN N D，MAKHTAR S N，HIDZIR H D M.Craters Detection on Lunar[C]∥IEEE International Conference on Space Science and Communication,IEEE，2011：190-195.

[12] YUE Z Y，LIU J Z，WU G G.Automated Detection of Lunar Craters Based on Object-oriented Approach[J].Chinese Science Bulletin，2008，53(23)：3699-3704.

[13] BUE B D，STEPINSKI T F.Machine Detection of Martian Impact Craters From Digital Topography Data[J].IEEE Transactions on Geoscience & Remote Sensing，2006，45(1)：265-274.

[14] VIJAYAN S，VANI K，SANJEEVI S.Topographical Analysis of Lonar Crater Using Cartosat-1 DEM[J].Journal of the Indian Society of Remote Sensing，2013，41(2)：345-354.

[16] 丁萌，曹云峰，吴庆宪.一种基于被动图像的陨石坑自主检测方法研究(英文)[J].Chinese Journal of Aeronautics，2009(3)：81-86.

[17] 于正湜，朱圣英，马冬梅，等.行星表面非规则陨石坑检测与识别方法[J].宇航学报，2013，34(3)：320-326.

[18] 陈建清，朱圣英，崔祜涛，等.应用灰度特征的行星陨石坑自主检测方法与着陆导航研究[J].宇航学报，2014，35(8)：908-915.

[19] GOLOMBEK M，BERNARD D.Crater and Rock Hazard Modeling for Mars Landing[C]∥AIAA Space 2001 Conference and Exposition，2001：519-527.

[20] PIKE R J.Depth/Diameter Relations of Fresh Lunar Craters：Revision from Spacecraft Data[J].Geophysical Research Letters，1974，1(7)：291-294.