席莎，邵巍

（青島科技大學 自動化與電子工程學院，青島 266042）

一種基于多尺度邊緣提取的隕石坑檢測算法

席莎，邵巍

（青島科技大學 自動化與電子工程學院，青島 266042）

針對星體表面的隕石坑可用于探測器的自主導航、障礙識別等任務(wù)，提出一種基于多尺度邊緣提取的隕石坑檢測算法。該算法首先利用高斯金字塔得到不同尺度的隕石坑圖像；其次，針對不同尺度的隕石坑圖像，利用EDPF邊緣提取算法對隕石坑進行邊緣提取，并連接關(guān)鍵邊緣像素點為直線段來近似表示圖像邊緣；然后將具有相同偏轉(zhuǎn)方向的邊緣直線段連接成圓弧，并將有相似半徑和中心的圓弧擬合成候選圓和橢圓；最后對候選圓、橢圓進行驗證。該算法的優(yōu)點在于，能夠準確地檢測出隕石坑，有較高的檢測率，且對存在較多隕石坑的圖像有較好的檢測結(jié)果。

隕石坑檢測；高斯金字塔；邊緣提?。粓A、橢圓擬合

0 引 言

從1958年美國和前蘇聯(lián)啟動探月計劃開始，各航空大國先后開展了多種類型的深空探測活動。實現(xiàn)探測器在行星表面的自主著陸是實現(xiàn)深空探測的關(guān)鍵技術(shù)之一。而隕石坑是一種廣泛存在于行星、衛(wèi)星、小行星和其他太陽系星體表面的自然路標，具有一致的幾何特征和清晰的輪廓，將其作為自主導航系統(tǒng)中著陸器位姿估計中的跟蹤目標顯得越發(fā)重要[1-3]。

由于隕石撞擊會出現(xiàn)隕石坑不完整或者重疊的情況，或者受風化等因素影響造成隕石坑邊緣不明顯，增加了隕石坑檢測的難度，也對檢測的準確性和穩(wěn)定性提出了更高的要求。丁萌等人提出基于特征點的隕石坑檢測算法[4]，該算法通過區(qū)域生長的方法提取隕石坑亮、暗兩區(qū)域并通過橢圓擬合的方式獲得隕石坑所在的圓或者橢圓。Yue等人提出一種基于面向?qū)ο蠓椒ǖ碾E石坑檢測算法[5]。Cheng等人提出了一種針對受光照和視角等因素影響的隕石坑檢測算法[6]，通過定位點檢測和邊緣分組來選取橢圓弧，最后通過橢圓擬合來獲取檢測結(jié)果。針對隕石坑的分類問題，Cohen等人提出了一種基于遺傳算法的隕石坑檢測和分類算法[7]。Jin等人提出一種利用神經(jīng)網(wǎng)絡(luò)的方法來自動檢測隕石坑及分類的方法[8]。這些算法大都利用機器學習或者區(qū)域生長的方法來獲取隕石坑的邊緣信息進而提取隕石坑，但是這些邊緣提取算法并不能精確地確定隕石坑的邊緣，且對于存在較多隕石坑的圖像提取效果較差，檢測率低。

針對上述問題，本文提出了一種基于多尺度邊緣提取的隕石坑檢測算法，利用高斯金字塔對隕石坑圖像進行不同尺度的降采樣，并結(jié)合邊緣檢測算法來提取更多的細節(jié)邊緣信息，提高了檢測準確度，之后采用圓弧和橢圓弧的提取，候選圓和橢圓檢測，候選圓和橢圓的驗證等步驟進行后續(xù)檢測。文章最后分析了此算法的有效性和準確性，并計算了檢測率、漏檢率和誤檢率。

1 多尺度邊緣檢測

由于隕石坑的檢測精度和圖像分辨率有著重要關(guān)系：即分辨率越高，圖像中隕石坑的細節(jié)特征越多；分辨率越低，細節(jié)特征會減少，比較明顯的特征更加突出。因此為提高檢測精度，本文提出利用高斯金字塔改變圖像分辨率來對隕石坑進行檢測。首先對隕石坑原始圖像進行檢測，估計圖中隕石坑的大小及數(shù)目，并根據(jù)圖像的分辨率確定合適的降采樣尺度及金字塔的層數(shù)來獲取不同分辨率的圖像，然后對不同尺度的隕石坑圖像分別進行檢測。

圖像邊緣檢測作為數(shù)字圖像處理的基本方法，已經(jīng)有了大量的研究，常用的Canny邊緣檢測[9]采用兩種不同的閾值分別檢測強邊緣和弱邊緣，使得檢測出的隕石坑的邊緣位置會有一定范圍的誤差，檢測出的細節(jié)較多，且重要的邊緣突出不明顯。針對此問題，本文采用EDPF（earliest deadline and processing timefirst）邊緣檢測算法[10]，其步驟如下：

1）計算圖像中每一個像素點的梯度值g（x，y）和梯度方向α：

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

2）選取四鄰域內(nèi)梯度值最大的像素點作為關(guān)鍵點，然后將具有相似梯度方向的關(guān)鍵點連接成線段。

3）驗證邊緣段。通過計算NFA（number of alarms），如公式（2）所示，剔除無效連接線段，生成邊緣圖像。

其中：ε=1；N為一段邊緣段S上像素點的數(shù)目；p為一個像素點為對齊像素點的概率，這里取p=1/8，對齊像素是指兩個像素點的梯度方向相似，即梯度角之差小于閾值。

邊緣檢測結(jié)果如圖 1所示。從圖 1可以看出EDPF算法提取的邊緣比Canny算子更加平滑和完整，且沒有過多的細節(jié)，隕石坑邊緣顯示突出；通過高斯金字塔之后的邊緣檢測結(jié)果可以看出，隨著圖像分辨率的降低，可以更精確地提取到圖像中較大隕石坑的邊緣，有利于后續(xù)的檢測過程。

2 圓弧和橢圓弧的提取

對于邊緣檢測結(jié)果中閉合的邊緣段，采用最小二乘算法[11]擬合成圓或者橢圓，并作為候選圓或者橢圓直接用于最后的驗證。那么對于其余不閉合邊緣段，則采用EDLines算法[12]用直線段來近似表示圖像邊緣，即用最小二乘算法將每一個邊緣段擬合為直線段，并使得擬合誤差小于一個像素精度，直線邊緣段示意圖如圖 2所示。

圖1 多尺度邊緣檢測結(jié)果Fig.1 Results of multiscale edge detection

圖2 直線邊緣段Fig.2 Line segments

假設(shè)每條直線段均為矢量，且一個圓弧至少由3條直線段組成。

首先計算直線段中任意相鄰兩條直線段之間的夾角，以及每條直線段的偏轉(zhuǎn)方向：向右為-，向左為+；然后將夾角在所設(shè)閾值范圍之內(nèi)，且偏轉(zhuǎn)方向相同的三條相鄰直線段連接成圓弧或橢圓弧，這里夾角閾值范圍?。?°，60°），其提取示意圖如圖 3所示。

圖3 圓弧、橢圓弧提取示意圖Fig.3 Circular，elliptic arc extraction

3 候選圓和橢圓的檢測

由于弧長越長越接近完整的圓或者橢圓，所以根據(jù)圓弧或者橢圓弧的長度進行排序，把最長的圓弧或者橢圓弧作為基準弧，將滿足半徑約束和中心距離約束的圓弧或者橢圓弧與之連接在一起。半徑約束是指，兩個弧的半徑差要小于所設(shè)閾值；中心距離約束是指兩個弧的中心距離要小于所設(shè)閾值。候選圓和橢圓檢測示意圖如圖 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 候選圓和橢圓的驗證

由于經(jīng)上述方法所檢測的圓或者橢圓存在誤檢測，所以通過計算NFA對候選圓或者橢圓進行驗證來剔除錯誤的檢測，定義如下：

對于大小為N×N的圖像，候選圓的NFA

候選橢圓的NFA

其中：ε=1；n為一個候選圓或者橢圓中像素點的數(shù)目；k為候選圓或橢圓中對齊像素點的數(shù)目；p為一個像素點為對齊像素點的概率，這里取p=1/8；因為圓和橢圓分別有4個和5個自由度，故N4和N5分別為圖像中候選圓和候選橢圓的數(shù)目。

5 實驗仿真與結(jié)果分析

利用NASA發(fā)布的月球上的隕石坑圖像對該算法的準確性和有效性進行實驗仿真驗證。

由于隕石坑的檢測精度不僅與圖像的分辨率有關(guān)系，且與圖像中隕石坑的大小以及拍攝高度有重要關(guān)系，可以結(jié)合原始圖像的檢測結(jié)果估計出圖中隕石坑的大小，確定隕石坑直徑所處范圍，并根據(jù)圖像的分辨率來確定將采樣尺度和高斯金字塔的層數(shù)。

應(yīng)用圖 6～8給出的隕石坑原始圖像進行實驗驗證，經(jīng)過多次驗證，且保證了有較高的檢測率和較低的漏檢率和誤檢率。圖 6的原始圖像分辨率小于500×500，利用高斯金字塔進行3次降采樣，每次采樣尺度為0.8；對于分辨率大于500×500的圖 7和圖 8，利用高斯金字塔進行3次降采樣，每次采樣尺度為0.5。首先對隕石坑原始圖像進行檢測，估計圖中隕石坑的大小和數(shù)目，如圖 6～8中的（a）所示；然后對降采樣得到的不同尺度的隕石坑圖像分別進行檢測，如圖6～8中的（b）和（c）所示；最后將檢測結(jié)果均放到原始圖像中進行顯示，如圖 6～8中的（d）所示。

圖6 圖像仿真結(jié)果Fig.6 The simulation result of images

圖7 圖像仿真結(jié)果Fig.7 The simulation result of images

圖8 圖像仿真結(jié)果Fig.8 The simulation result of images

根據(jù)圖 6～8中隕石坑的原始總數(shù)目以及所檢測到的數(shù)目可以計算出其檢測率、誤檢率以及漏檢率。

檢測率是指所檢測到的隕石坑數(shù)目占原始總數(shù)目的比例；漏檢率是指未檢測到的隕石坑數(shù)目所占的比例；誤檢率是指所檢測到的隕石坑中錯誤檢測的隕石坑數(shù)目占原始總數(shù)目的比例，檢測結(jié)果如表1所示。

表1 隕石坑檢測結(jié)果參數(shù)Table 1 Parameters of crater detection results

從仿真結(jié)果圖 6～8可以看出，本文所提出的方法，可以有效地提取隕石坑的邊緣信息，并且邊緣較為平滑和完整，為之后的檢測過程提供有效信息，原始圖像的檢測結(jié)果顯示出對較小的隕石坑有比較準確的檢測效果。從最終的隕石坑檢測結(jié)果可以看出，本文算法可以檢測到圖像中絕大多數(shù)隕石坑，并且對于圖像背景復(fù)雜且隕石坑數(shù)目較多的圖像有較好的檢測結(jié)果。經(jīng)過大量實驗驗證，一般情況下，該算法的檢測率高于85%且漏檢率和誤檢率均為10%左右。

6 結(jié) 論

本文提出一種基于多尺度邊緣提取的隕石坑檢測算法。為提高檢測率，首先利用高斯金字塔來獲取不同尺度的隕石坑圖像，通過EDPF提取隕石坑邊緣，并用直線段近似表示邊緣，檢測出候選圓和橢圓之后通過計算NFA來驗證。仿真實驗表明這種方法具有較高的檢測率和較低的漏檢率。但是由于隕石坑受光照、重疊等因素影響，導致邊緣信息提取不準確，從而影響隕石坑的檢測結(jié)果。在以后的研究中將考慮把這些因素與此算法相結(jié)合進行分析，以提高檢測精度和有效性。

[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].哈爾濱：工業(yè)大學，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- ），女，碩士研究生，主要研究方向：數(shù)字圖像處理。

[責任編輯：高莎]

2016-07-28；

2016-08-12

國家重點基礎(chǔ)研究發(fā)展計劃“973”計劃（2012CB720000）