基于方向梯度直方圖的隕坑預(yù)檢測(cè)算法

郭永茂，周石博，高 艾

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081；2.北京理工大學(xué) 深空探測(cè)技術(shù)研究所，北京 100081)

0 引言

行星探測(cè)是深空探測(cè)的一種重要探測(cè)方式，行星表面大多布滿(mǎn)隕石坑或撞擊坑。隕石坑具有明顯的特征，規(guī)則的幾何形狀等特點(diǎn)，適合對(duì)行星地質(zhì)進(jìn)行分析。同時(shí)隕坑可以作為探測(cè)器自主導(dǎo)航的自然路標(biāo)，提高導(dǎo)航精度，隕坑也是探測(cè)器著陸過(guò)程中障礙檢測(cè)和規(guī)避的主要目標(biāo)之一。由于隕坑檢測(cè)的效率和準(zhǔn)確性決定了導(dǎo)航的可靠性與精度，因此隕坑檢測(cè)算法成為學(xué)術(shù)界研究的熱門(mén)。國(guó)內(nèi)外學(xué)者針對(duì)這一問(wèn)題進(jìn)行了深入的研究。由于隕坑邊緣在圖像上顯示清晰，因此可以通過(guò)邊緣檢測(cè)并進(jìn)行擬合方式檢測(cè)隕坑。在這方面，Meng D[1]和馮軍華[2]等人通過(guò)對(duì)陰影區(qū)的選擇與邊緣檢測(cè)實(shí)現(xiàn)隕坑檢測(cè)。Yu M[3]和Qin T[4]等人確定光照方向矢量，提高了隕坑檢測(cè)的準(zhǔn)確率。Leroy B[5]和Templeton T[6]等人對(duì)小天體表面的隕坑檢測(cè)進(jìn)行了研究，并通過(guò)邊緣匹配實(shí)現(xiàn)了隕坑檢測(cè)；另一方面，由于多數(shù)隕坑形狀相似，且多為圓形，因此可以通過(guò)采用建立圖像模板進(jìn)行隕坑檢測(cè)。 Kim J R[7]和Bandeira L[8]等人生成相應(yīng)的隕坑模版，然后通過(guò)模版匹配實(shí)現(xiàn)隕石坑的檢測(cè)。Wang Y[9]和Schmied S A[10]等人通過(guò)boosting投票方法對(duì)隕坑進(jìn)行檢測(cè)，同樣取得了較好的效果。Kamarudin[11]、Yue Z Y[12]、Bue B D[13]、Vijayan S[14]和 Loncaric S[15]等人對(duì)隕坑檢測(cè)的圖形圖像特性進(jìn)行分析，取得了很大進(jìn)展。丁萌[16]、于正湜[17]和陳建清[18]等人也分別提出了隕坑圖像檢測(cè)方法。這些方法對(duì)隕坑檢測(cè)方法的發(fā)展做出了貢獻(xiàn)，但是由于隕坑地形天然的復(fù)雜性，隕坑檢測(cè)方法依然面臨精度、效率與實(shí)時(shí)性不足等困難。多數(shù)隕坑檢測(cè)方法對(duì)圖像內(nèi)包括單一隕坑區(qū)域的檢測(cè)性能較好，對(duì)全景圖像的檢測(cè)則存在實(shí)時(shí)性和準(zhǔn)確性不高的困難。因此需要一種能夠?qū)D像進(jìn)行預(yù)處理并快速?gòu)娜皥D像中提取出包含單一隕坑的子圖的方法。方向梯度直方圖(HOG)是近年來(lái)提出的一種基于梯度信息描述物體的特征，因此十分適合解決隕坑檢測(cè)問(wèn)題，同時(shí)運(yùn)行效率較高，適合實(shí)時(shí)應(yīng)用。結(jié)合HOG特征可以很好地解決目前隕坑檢測(cè)過(guò)程中遇到的困境。

本文針對(duì)隕坑檢測(cè)對(duì)復(fù)雜全景圖像檢測(cè)的難點(diǎn)，提出了一種基于方向梯度直方圖(HOG)特征的隕坑預(yù)檢測(cè)方法，對(duì)圖像提取可能存在隕坑的區(qū)域，提高隕坑檢測(cè)的效率與精度。該方法首先通過(guò)建立標(biāo)準(zhǔn)隕坑模型并生成一定數(shù)量的隕坑地形圖與隨機(jī)地形圖，對(duì)地形圖提取HOG特征，作為訓(xùn)練正負(fù)樣本并采用支持向量機(jī)(SVM)進(jìn)行分類(lèi)器學(xué)習(xí)。然后通過(guò)圖像梯度對(duì)圖像進(jìn)行閾值分割，將圖像梯度較大的區(qū)域作為潛在目標(biāo)區(qū)域。最后通過(guò)訓(xùn)練后的支持向量機(jī)在潛在目標(biāo)區(qū)域中進(jìn)行滑窗檢測(cè)，得到隕坑預(yù)檢測(cè)的子區(qū)域，為隕坑檢測(cè)算法提供較好的檢測(cè)樣本。仿真實(shí)驗(yàn)表明該方法能夠提高隕坑檢測(cè)的效率，預(yù)檢測(cè)提供的圖像子區(qū)域降低了隕坑匹配的錯(cuò)誤率。

1 建立隕坑地形圖像樣本集

1.1 隕坑數(shù)學(xué)模型

盡管通過(guò)軌道器或天文觀測(cè)可以獲得大量的行星地表地貌圖像數(shù)據(jù)，但是通過(guò)這些圖像數(shù)據(jù)進(jìn)行隕坑提取與檢測(cè)并建立樣本數(shù)據(jù)庫(kù)依然十分困難。同時(shí)受到觀測(cè)條件等限制，提取的隕坑圖像并不一定能夠包含全部可能光照或者形態(tài)，這樣通過(guò)建立數(shù)據(jù)庫(kù)實(shí)現(xiàn)隕坑檢測(cè)是十分困難的；另一方面，隕坑的幾何外形具有一定規(guī)律性，一般可以采用一個(gè)旋轉(zhuǎn)曲面函數(shù)進(jìn)行表示，因此可以通過(guò)人工手段生成隕坑圖像。Golombek M[19]等人對(duì)月球表面的隕坑形狀、大小和分布進(jìn)行分析，所采用的隕坑模型通過(guò)多段線(xiàn)方程進(jìn)行表示。由于隕坑形成時(shí)間的不同，其幾何外形也有區(qū)別，所采用的描述方程也不一樣。Pike[20]對(duì)大量月球隕石坑作了測(cè)量和計(jì)算，對(duì)于形成年代較近的隕坑或撞擊坑，其剖面函數(shù)可以通過(guò)下式的經(jīng)驗(yàn)公式近似。隕坑剖面示意圖如圖1所示。

式中，D為隕坑直徑；H為隕坑高度；Hr為隕坑邊沿高度；Pike給出月球隕坑可選參數(shù)為rin=1.01，ain=0.196，rout=1.014，aout=0.036，調(diào)整a，r的大小即可得到不同形態(tài)的隕坑剖面函數(shù)。基于以上分析，本文采用2個(gè)獨(dú)立的方程來(lái)近似表達(dá)隕坑的邊緣部分和碗形內(nèi)部，并采用旋轉(zhuǎn)面來(lái)近似整個(gè)隕坑。

圖1 隕坑剖面示意

1.2 隕坑圖像模擬

直接通過(guò)隕坑的數(shù)學(xué)模型模擬得到的隕坑地形缺乏真實(shí)感，主要是由于缺乏真實(shí)地形的起伏感和粗糙感，因此需要在數(shù)學(xué)模型的基礎(chǔ)上疊加基礎(chǔ)地形模型增加地形真實(shí)感。隨機(jī)分形是指采用隨機(jī)機(jī)制生成的一組分形集。行星表面作為自然地形，具有分形的自相似性，因此可以采用隨機(jī)分形生成行星地形，增加模型真實(shí)感。分形地形可以通過(guò)多種方式生成，本文采用Perlin噪聲算法生成地形，該方法生成的地形尖峰較少，適合作為基礎(chǔ)地表地形。

Perlin噪聲算法的原理是將地形平面離散為不同尺度的矩陣，不同尺度記為頻率f，在每一個(gè)頻率f下的矩陣中的每一個(gè)點(diǎn)為一個(gè)隨機(jī)數(shù)。隨機(jī)數(shù)的大小受振幅A限制，這樣就得到了多組不同頻率f和振幅A的地形矩陣。記最大頻率為fmax，將其他頻率f的矩陣離散插值為fmax大小，并將插值后的全部地形疊加即為基于Perlin噪聲的地形模型。采用不同的隨機(jī)數(shù)發(fā)生算法、插值算法和振幅A的大小即可得到不同形態(tài)的模擬地形。本文采用的頻率f和幅值A(chǔ)共6組，變化規(guī)律如下式所示，生成的不同插值地形圖如圖2所示。

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

圖2 不同幅值的地形數(shù)據(jù)

疊加后的地形圖如圖3(a)所示，整體地形起伏程度可以通過(guò)調(diào)整噪聲幅值A(chǔ)進(jìn)行調(diào)整?；A(chǔ)地形與隕坑疊加的結(jié)果如圖3(b)所示，可以看出隕坑地形已經(jīng)具有一定的真實(shí)性。

圖3 行星表面地形模擬

隕坑圖像往往包含由光照引起的陰影，在人工模擬隕坑圖像的過(guò)程中不能忽視陰影的存在。OpenGL是一個(gè)跨編程語(yǔ)言、跨平臺(tái)的編程接口規(guī)格的專(zhuān)業(yè)的圖形程序接口。利用OpenGL可以方便快捷地實(shí)現(xiàn)計(jì)算機(jī)圖形圖像的渲染和顯示。因此本文采用OpenGL對(duì)隕坑模型進(jìn)行渲染，得到增加光照渲染后的模擬隕坑圖像如圖4所示。

圖4 隕坑地形模擬渲染

2 基于HOG特征的支持向量機(jī)分類(lèi)方法

2.1 HOG特征提取

灰度梯度直方圖(HOG)特征是一種基于局部物體輪廓分布的特征描述子，通過(guò)將圖像進(jìn)行分割并統(tǒng)計(jì)梯度方向與大小得到該區(qū)域的梯度特征分布的統(tǒng)計(jì)結(jié)果。由于圖像梯度直接反應(yīng)物體在圖像中的輪廓特征，因此對(duì)不同形狀的物體，其梯度的統(tǒng)計(jì)結(jié)果也會(huì)有所不同。因此可以通過(guò)HOG特征對(duì)圖像中不同類(lèi)型的物體進(jìn)行分類(lèi)檢測(cè)。HOG特征的檢測(cè)步驟如下：

① 對(duì)輸入圖像進(jìn)行梯度計(jì)算，具體方法為計(jì)算水平和垂直方向的梯度(gx，gy)，計(jì)算梯度大小和梯度方向。

② 將輸入圖像分割成等大小的小格(cell)，并將幾個(gè)小格合并為一個(gè)小塊(block)。塊與塊之間可以存在重疊，記塊內(nèi)格數(shù)為m。

③ 將梯度方向范圍進(jìn)行分割，例如0°～360°可以以40°為步長(zhǎng)，分割為9個(gè)不同通道。步長(zhǎng)的大小可以根據(jù)實(shí)際需要進(jìn)行調(diào)整，記通道數(shù)為n。

④ 對(duì)每個(gè)小格統(tǒng)計(jì)內(nèi)部每個(gè)像素的梯度方向直方圖，直方圖橫坐標(biāo)為通道數(shù)n，縱坐標(biāo)為該通道內(nèi)梯度幅值的疊加。每個(gè)小格可以構(gòu)成一個(gè)n維向量。

⑤ 對(duì)每一個(gè)小塊內(nèi)的所有小格的向量進(jìn)行歸一化處理，降低陰影或光照對(duì)描述向量的影響。歸一化方法為將塊內(nèi)所有向量串連得到mn維向量，采用L2歸一化方法進(jìn)行歸一化，記v*為歸一化后的向量，則

式中，v為歸一化之前的向量；‖v‖2表示v的2階范數(shù)；ε為一個(gè)較小的常數(shù)，避免分母為零。

⑥ 將所有按塊歸一化后的向量串連起來(lái)得到的特征向量即HOG特征向量。

隕坑的形狀在圖像中多為圓形或橢圓形，其輪廓特征與其他物體區(qū)別明顯，利用HOG特征可以明顯地區(qū)分隕坑和其他物體。

2.2 支持向量機(jī)分類(lèi)學(xué)習(xí)方法

在提取出HOG特征后，本文采用支持向量機(jī)(Support Vector Machine，SVM)進(jìn)行分類(lèi)，SVM在解決小樣本、非線(xiàn)性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并且能夠快速有效地區(qū)分高維向量，對(duì)非線(xiàn)性分類(lèi)有較好的應(yīng)用。SVM通過(guò)核技巧(kernel trick)可以將非線(xiàn)性分類(lèi)問(wèn)題變換為高維線(xiàn)性可分問(wèn)題，將向量映射到一個(gè)高維空間里，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有2個(gè)互相平行的超平面，分隔超平面使2個(gè)平行超平面的距離最大化。具體方法為：

① 構(gòu)造正負(fù)樣本集合

Φ{(x1，y1)，(x2，y2)，…，(xN，yN)}，xi∈Rn，yi∈{+1，-1}。選取適當(dāng)?shù)暮撕瘮?shù)k(x，x′)和適當(dāng)?shù)膮?shù)C，構(gòu)造并求解最優(yōu)化問(wèn)題。

② 選擇一個(gè)α*的分量，計(jì)算b*，

通過(guò)決策函數(shù)得到測(cè)試樣本的正負(fù)集分類(lèi)。

3 仿真實(shí)驗(yàn)

通過(guò)隕坑模擬函數(shù)生成約500幅不同光照角度與形態(tài)的隕坑圖像作為SVM訓(xùn)練數(shù)據(jù)的正樣本來(lái)源，同時(shí)根據(jù)隨機(jī)地形生成算法生成同樣數(shù)量不同光照條件與角度的普通模擬地形圖像作為負(fù)樣本。選取其中的50組正負(fù)樣本圖像如圖5所示。

圖5 正負(fù)樣本數(shù)據(jù)

取其中一個(gè)正樣本，小格大小為64*64，提取其中每個(gè)小格的HOG特征的結(jié)果如圖6所示，可以看出HOG特征很好地表達(dá)了隕坑的形狀特征，即梯度方向分布具有圓形的規(guī)律性。

圖6 隕坑每個(gè)小格灰度方向特征統(tǒng)計(jì)

為了進(jìn)一步降低檢測(cè)時(shí)間，可以對(duì)圖像進(jìn)行一定的簡(jiǎn)單前背景篩選過(guò)程。方法是對(duì)梯度圖像進(jìn)行閾值分割，將梯度較高的區(qū)域進(jìn)行二值膨脹，從而將窗口掃描的區(qū)域限制在膨脹后的前景圖像區(qū)域內(nèi)，降低檢測(cè)時(shí)間。給出月球表面的實(shí)際照片作為測(cè)試圖像，選擇30*30、50*50和120*120等3個(gè)掃描窗口進(jìn)行掃描，將窗口圖像縮放至64*64的標(biāo)準(zhǔn)大小，預(yù)檢測(cè)得到的包含隕坑的子圖如圖7所示。

檢測(cè)效率與精度受到窗口數(shù)量和掃描步長(zhǎng)的限制，是一個(gè)不斷調(diào)節(jié)的過(guò)程，因此需要在實(shí)際飛行任務(wù)中提前設(shè)計(jì)合適的檢測(cè)窗口尺寸與掃描步長(zhǎng)以適應(yīng)實(shí)際需要。經(jīng)過(guò)調(diào)整，本文對(duì)圖中的隕坑預(yù)檢測(cè)過(guò)程耗時(shí)約10 s，單一子圖的分類(lèi)檢測(cè)時(shí)間約為10 ms，同類(lèi)型隕坑檢測(cè)方法，如基于Haar特征的Adaboost方法的檢測(cè)耗時(shí)約為60 s，單一子圖的分類(lèi)檢測(cè)時(shí)間約為5 ms。由于Haar特征提取過(guò)程需要在圖像檢測(cè)前得到整幅圖像的積分圖，因此消耗的時(shí)間較長(zhǎng)，不適合在線(xiàn)應(yīng)用。在檢測(cè)效率方面，本文采用的方法檢測(cè)正確率為95%，相比Adaboost方法的檢測(cè)正確率約為90%，但耗時(shí)更短。針對(duì)真實(shí)的環(huán)境檢測(cè)，采用月球表面的實(shí)際照相作為測(cè)試圖像，但是可以看出預(yù)檢測(cè)能夠?qū)㈦E坑從背景圖像中分割出，但是總體精度較低，存在大量錯(cuò)誤區(qū)域，因此還需要更好的篩選過(guò)程。同時(shí)由于僅僅標(biāo)記出隕坑可能存在的位置，對(duì)隕坑的精確定位無(wú)法完成，依然需要更加準(zhǔn)確的隕坑檢測(cè)方法，但是這些預(yù)檢測(cè)區(qū)域已經(jīng)大大降低了目前圖像檢測(cè)運(yùn)行時(shí)間，并提高了檢測(cè)精度，為后續(xù)更加準(zhǔn)確的隕坑檢測(cè)提供了幫助。

圖7 月球表面隕坑圖像與檢測(cè)結(jié)果

4 結(jié)束語(yǔ)

針對(duì)于全景隕坑圖像檢測(cè)的實(shí)時(shí)性和有效性的難點(diǎn)，本文提出一種基于HOG特征的圖像隕坑預(yù)檢測(cè)算法，經(jīng)過(guò)仿真分析可以發(fā)現(xiàn)本算法能夠極大地縮小單一子圖的分類(lèi)和檢測(cè)時(shí)間，同時(shí)檢測(cè)正確率也在90%以上。在深空探測(cè)領(lǐng)域，面對(duì)大量的全景圖像數(shù)據(jù)以及處理時(shí)效性的需求，該預(yù)檢測(cè)算法能夠快速有效地提取大量滿(mǎn)足檢測(cè)需求的備選隕坑圖像，為后續(xù)深度數(shù)據(jù)處理提供了良好的基礎(chǔ)。

[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] 馮軍華，崔祜濤，崔平遠(yuǎn)，等.行星表面隕石坑檢測(cè)與匹配方法[J].航空學(xué)報(bào)，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] 丁萌，曹云峰，吳慶憲.一種基于被動(dòng)圖像的隕石坑自主檢測(cè)方法研究(英文)[J].Chinese Journal of Aeronautics，2009(3)：81-86.

[17] 于正湜，朱圣英，馬冬梅，等.行星表面非規(guī)則隕石坑檢測(cè)與識(shí)別方法[J].宇航學(xué)報(bào)，2013，34(3)：320-326.

[18] 陳建清，朱圣英，崔祜濤，等.應(yīng)用灰度特征的行星隕石坑自主檢測(cè)方法與著陸導(dǎo)航研究[J].宇航學(xué)報(bào)，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.