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

席莎，邵巍

（青島科技大學(xué) 自動(dòng)化與電子工程學(xué)院，青島 266042）

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

席莎，邵巍

（青島科技大學(xué) 自動(dòng)化與電子工程學(xué)院，青島 266042）

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

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

0 引 言

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

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

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

1 多尺度邊緣檢測(cè)

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

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

1）計(jì)算圖像中每一個(gè)像素點(diǎn)的梯度值g（x，y）和梯度方向α：

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

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

3）驗(yàn)證邊緣段。通過(guò)計(jì)算NFA（number of alarms），如公式（2）所示，剔除無(wú)效連接線段，生成邊緣圖像。

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

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

2 圓弧和橢圓弧的提取

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

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

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

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

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

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

3 候選圓和橢圓的檢測(cè)

由于弧長(zhǎng)越長(zhǎng)越接近完整的圓或者橢圓，所以根據(jù)圓弧或者橢圓弧的長(zhǎng)度進(jìn)行排序，把最長(zhǎng)的圓弧或者橢圓弧作為基準(zhǔn)弧，將滿足半徑約束和中心距離約束的圓弧或者橢圓弧與之連接在一起。半徑約束是指，兩個(gè)弧的半徑差要小于所設(shè)閾值；中心距離約束是指兩個(gè)弧的中心距離要小于所設(shè)閾值。候選圓和橢圓檢測(cè)示意圖如圖 4、5所示。

圖4 候選圓檢測(cè)Fig.4 The candidate circle detection

圖5 候選橢圓檢測(cè)Fig.5 The candidate ellipse detection

圖4（a）中，弧A1為基準(zhǔn)弧，弧A2的半徑超出了閾值范圍，不滿足半徑約束，弧A3和A4可以與A1相連；圖 4（b）中弧A3不滿足中心距離約束，A2和A4可以與A1相連；同樣圖 5（a）中，弧A4的半徑超出了閾值范圍，弧A2和A3可以與A1相連，圖 5（b）中弧A3不滿足中心距離約束，A2和A4可以與A1相連。

對(duì)于滿足上述兩個(gè)約束的圓弧或者橢圓弧，用最小二乘算法擬合為圓或者橢圓，作為候選圓和橢圓用于最后的驗(yàn)證。

4 候選圓和橢圓的驗(yàn)證

由于經(jīng)上述方法所檢測(cè)的圓或者橢圓存在誤檢測(cè)，所以通過(guò)計(jì)算NFA對(duì)候選圓或者橢圓進(jìn)行驗(yàn)證來(lái)剔除錯(cuò)誤的檢測(cè)，定義如下：

對(duì)于大小為N×N的圖像，候選圓的NFA

候選橢圓的NFA

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

5 實(shí)驗(yàn)仿真與結(jié)果分析

利用NASA發(fā)布的月球上的隕石坑圖像對(duì)該算法的準(zhǔn)確性和有效性進(jìn)行實(shí)驗(yàn)仿真驗(yàn)證。

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

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

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

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

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

6 結(jié) 論

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

[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ǎo)航方法研究[D].哈爾濱：工業(yè)大學(xué)，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]丁萌，曹云峰，吳慶憲.一種從月面圖像檢測(cè)隕石坑的方法[J].宇航學(xué)報(bào)，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號(hào)青島科技大學(xué)自動(dòng)化與電子工程學(xué)院（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

席莎，邵巍.一種基于多尺度邊緣提取的隕石坑檢測(cè)算法[J].深空探測(cè)學(xué)報(bào)，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ù)字圖像處理。

[責(zé)任編輯：高莎]

2016-07-28；

2016-08-12

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃“973”計(jì)劃（2012CB720000）