王光澤，邵 巍，郗洪良，姚文龍，黃翔宇

（1.青島科技大學(xué) 自動化與電子工程學(xué)院，青島 266100；2.北京控制工程研究所，北京 100094）

引 言

近年來，各國紛紛開展了小天體著陸與采樣返回任務(wù)[1-2]，為獲得有價值的科學(xué)素材，需要探測器著陸到具有較高的科學(xué)價值的特定區(qū)域，這就需要探測器具備精確導(dǎo)航的能力。視覺導(dǎo)航是目前發(fā)展較為成熟的自主導(dǎo)航方法，并在各種深空探測任務(wù)中得到不同程度的發(fā)展與應(yīng)用，其利用光學(xué)敏感器件獲取天體及其表面圖像，通過圖像中提取的特征來確定探測器空間位置等信息。

當(dāng)前用于視覺導(dǎo)航的地標(biāo)主要分為兩類。一類是使用圖像中的特征點信息進(jìn)行導(dǎo)航，例如使用角點檢測算法來估計檢測器的速度[3-5]，Bakambu等[6]提出這類算法通常不如使用圖像區(qū)域匹配穩(wěn)定。特征點反映的信息量遠(yuǎn)低于邊緣特征曲線，尤其對于多尺度特征點，存在無法與圖像中物理紋理相對應(yīng)的情況，其應(yīng)用場景受限。

另一類是將天體表面的巖石和火山口等自然特征用作導(dǎo)航陸標(biāo)。同時，這些特征還能在著陸階段用于障礙物躲避。許多學(xué)者對隕石坑的探測和匹配方法做了很多研究[7-9]。這些算法中大多數(shù)都使用隕石坑形狀、陰影等信息進(jìn)行匹配，在處理溝壑、重疊的坑或不規(guī)則的巖石時容易發(fā)生誤匹配[10]。

不規(guī)則曲線特征在天體表面普遍存在，可作為導(dǎo)航陸標(biāo)進(jìn)行導(dǎo)航。對曲線精準(zhǔn)匹配是進(jìn)行視覺導(dǎo)航的重要前提[11]。國內(nèi)外眾多學(xué)者針對曲線匹配方法展開研究。

基于描述符的方法是曲線匹配重要分支。Liu 等[12]通過按亮度劃分曲線支撐區(qū)域構(gòu)建了描述符IOCD（Intensity Order Curve Descriptor）。王志衡等[13]為解決描述符主方向難以確定的問題，提出了描述符IOMSD（Intensity Order based Mean Standard Deviation Descriptor），在圖像受到模糊、噪聲干擾時，可以保持不變性。Chen 等[14]提出梯度階曲線描述符，對光照變化與噪聲干擾有較好的魯棒性?；谇€描述符曲線匹配方法根據(jù)曲線支撐區(qū)域相似度來進(jìn)行匹配，當(dāng)局部判斷為匹配時，則認(rèn)為整條曲線匹配，因此基于曲線描述符曲線匹配計算量較小，但難以實現(xiàn)曲線精準(zhǔn)匹配。

基于曲率的方法也是曲線匹配重要方向。Cohen等[15]提出使用B樣條來近似擬合曲線，通過曲率等曲線特征的計算進(jìn)一步完成曲線匹配工作。Taniai[16]等提出基于圖像分割的空間曲線局部匹配算法，該算法可以得到空間曲線分段描述，并保證了曲線的光滑性[17]。Cui 等[18]通過計算等積分間隔下曲率實現(xiàn)曲線精準(zhǔn)匹配，該算法具有尺度與旋轉(zhuǎn)不變性?；谇实那€匹配，適于處理圖像中兩條曲線匹配問題，當(dāng)對多條曲線匹配時計算量過于龐大。

為實現(xiàn)曲線精準(zhǔn)匹配，提出一種曲線描述符與曲率相結(jié)合的曲線精準(zhǔn)匹配算法，通過描述符完成曲線粗匹配，再根據(jù)曲率完成精準(zhǔn)匹配。本文具體結(jié)構(gòu)安排如下：第一部分介紹了多尺度紋理曲線提取算法與曲線描述符構(gòu)建方法；第二部分在曲線描述符粗匹配基礎(chǔ)上，介紹尺度不變曲率計算與匹配；第三部分在光照、尺度及旋轉(zhuǎn)變換下分析實驗結(jié)果；第四部分對文章進(jìn)行總結(jié)。

1 曲線描述符匹配

1.1 不規(guī)則曲線提取

曲線特征提取是匹配的基礎(chǔ)，為綜合多尺度紋理特征，對原始圖像降采樣處理，獲得一系列不同分辨率圖像，建立高斯金字塔模型。

基于Topal等[19]提出的Edge Drawing算法對每層圖像分別進(jìn)行曲線提取。根據(jù)邊緣像素特點，使用Sobel算子計算梯度圖，為加快計算速度，設(shè)置閾值篩選像素梯度，剔除小梯度像素。

為獲得連續(xù)邊緣曲線，放棄逐像素點邊緣判斷的思路，而采用基于節(jié)點的方法。首先根據(jù)梯度圖，選擇局部梯度極大值對應(yīng)像素點作為節(jié)點。之后由節(jié)點開始進(jìn)行像素連接，當(dāng)滿足以下條件之一停止。

1）當(dāng)不處于邊緣區(qū)域時，即當(dāng)前像素點經(jīng)梯度閾值篩選后，屬于被剔除部分；

2）當(dāng)檢測邊緣重復(fù)時，即對所在曲線進(jìn)行像素連接過程中，當(dāng)前像素點已被檢測過一次。

將曲線上所有點變換到原尺度后，對離散點進(jìn)行線性插值。在原尺度空間，對曲線上相鄰兩點坐標(biāo)（x1，y1）與（x2，y2），在區(qū)間[x1，x2]上某一位置x處縱坐標(biāo)取值為+

經(jīng)過坐標(biāo)變換與插值，高斯金字塔各層曲線提取結(jié)果被變換原尺度空間。多尺度曲線提取結(jié)果如圖1（b）所示，相比單尺度提取結(jié)果如圖1（a），所得曲線更加全面。同時基于Edge Drawing算法提取的邊緣曲線更加連續(xù)，并保證單像素寬度，另外曲線基于節(jié)點生成，邊緣圖像噪聲較少。

圖1 曲線提取結(jié)果Fig.1 Curve extraction result

1.2 曲線描述符構(gòu)建

對曲線進(jìn)行描述時，采用分段描述的方法，將每段曲線近似作為直線進(jìn)行描述符構(gòu)建[10,20]，該描述符包含曲線自身特征同時加入其周圍紋理信息，具備良好的辨識性。

描述時，將近似直線兩側(cè)區(qū)域劃分為m條矩形帶如圖2所示將近似直線兩側(cè)區(qū)域劃分為m條矩形帶，記作{B1，B2，B3，···，Bm}，每條矩形帶寬度為w，每個矩形帶都是曲線支撐區(qū)域的子區(qū)域。為保證描述符的旋轉(zhuǎn)不變性，將像素梯度向近似直線方向與正交方向投影。假設(shè)子區(qū)域中某像素梯度值為g，擬合直線方向為dL，與直線正交方向為d⊥，則局部梯度可表示為

圖2 曲線描述符結(jié)構(gòu)Fig.2 Curve descriptor structure

對于第i段曲線支撐區(qū)域的Bj矩形帶，通過對第k行不同方向梯度值求和可得

對所有曲線段梯度值求和，可得整條曲線Bj矩形帶的第k行梯度信息

將每行不同方向梯度之和堆疊，可得曲線Bj矩形帶梯度矩陣

其中：n為計算第j條矩形帶所需行數(shù)

對Hj每行進(jìn)行均值向量Uj與標(biāo)準(zhǔn)差向量Sj的求解計算，同時為滿足光照不變性進(jìn)行歸一化處理，兩者共同構(gòu)成曲線矩形帶Bj的描述符BDj可表示為

通過對所有矩形帶描述符進(jìn)行求解，獲得曲線描述符CBD

根據(jù)最近鄰距離比例原則，采用BF匹配算法匹配曲線描述符，曲線粗匹配結(jié)果如圖3所示。

圖3 曲線粗匹配Fig.3 Curves rough matching

2 曲線曲率匹配

2.1 三次B樣條曲線擬合

基于曲線描述符的曲線匹配算法僅能對曲線粗略匹配，難以實現(xiàn)最相似部分匹配，影響后續(xù)導(dǎo)航精度。本文在此基礎(chǔ)上加入基于曲率的曲線匹配算法，以實現(xiàn)對曲線的精準(zhǔn)匹配。原始曲線為離散數(shù)據(jù)形式，為盡可能準(zhǔn)確計算曲線曲率，需對曲線數(shù)據(jù)進(jìn)行平滑擬合，同時削弱噪聲的影響。

傳統(tǒng)的貝塞爾曲線擬合方法僅需少量控制點即可生成復(fù)雜平滑曲線，控制簡便且具有較強控制能力，但靈活性較差，難以修改局部特征，某一控制點發(fā)生改變對擬合曲線整體都有影響。針對貝塞爾算法的缺點，B樣條擬合算法被提出，該算法逼近多邊形特征精度更高，且具備局部修改性[21]，B樣條算法曲線擬合表達(dá)式為

其中：n表示用來擬合曲線的點個數(shù)；Pi表示擬合曲線的離散點；Fi，k（t）表示的K階基函數(shù)定義為

三次B樣條曲線相比二次B樣條曲線更加光滑，同時計算量在可接受范圍。通過4個相鄰離散點計算可得三次B樣條曲線，對式（11）進(jìn)行求解可得

將式（12）代入式（10），得到三次B樣條曲線表達(dá)式為

分別用2種算法擬合曲線，結(jié)果如圖4所示。與3次B樣條曲線擬合圖4（b）相比，貝塞爾曲線擬合結(jié)果圖4（a）整體趨勢平滑，但對曲線細(xì)節(jié)表現(xiàn)力較差?；谇实那€匹配算法是根據(jù)曲線彎曲程度進(jìn)行匹配，對曲線細(xì)節(jié)擬合要求高，貝塞爾擬合曲線易造成誤匹配，故B樣條曲線擬合算法更適合。

圖4 曲線擬合結(jié)果Fig.4 Curve fitting results

2.2 尺度不變性曲率計算

對于圖5中連續(xù)曲線，曲率表示為曲線弧切線轉(zhuǎn)角與弧長之比

圖5 連續(xù)曲線曲率Fig.5 Curvature of continuous curve

在曲線曲率基礎(chǔ)上進(jìn)行曲率積分計算，由于曲線中存在拐點，且有符號曲率積分非單調(diào)變化，導(dǎo)致同一積分?jǐn)?shù)值可能對應(yīng)多個曲率值，因此本文選擇使用無符號曲率積分。給定弧長為l的曲線，曲線曲率絕對值積分為

其中，K（0∶l）為曲率絕對值之和。將該曲線縮放a倍得到新曲線，其曲率絕對值之和為

將式（17）與式（18）代入式（16）可得

由式（19）可得曲率積分的尺度不變性，即如果兩輸入曲線具有相同的部分，則對曲線進(jìn)行尺度變換，且兩者尺度因子為m，則它們在弧長軸上（坐標(biāo)軸橫軸）的跨度之比也為m，且曲率積分（坐標(biāo)軸縱軸）跨度相等[19]，如圖6所示。

圖6 曲率積分尺度不變性Fig.6 Scale invariance of curvature integral

利用曲率絕對值積分尺度不變性，以等曲率積分間隔對曲率進(jìn)行采樣，使采樣后曲率具有尺度不變特性。對于尺度不同但存在相似部分的兩條曲線，其曲率在經(jīng)過采樣處理后，其相同部分在橫軸上跨越相同長度，兩條曲線精準(zhǔn)匹配問題轉(zhuǎn)換為采樣后兩曲率曲線的精準(zhǔn)匹配問題，簡化匹配難度。

等積分間隔采樣后，原曲率曲線變化劇烈處被拉長，而變化較平緩處被壓縮。在設(shè)置采樣間隔時，曲率積分間隔越小，曲線細(xì)節(jié)信息越準(zhǔn)確，但同時會保留更多噪聲，且計算量大；而間隔增大時會丟失部分?jǐn)?shù)據(jù)信息，但可以削弱噪聲影響并且減小計算量，如圖7所示。經(jīng)實驗，積分間隔設(shè)置為5時，能保證數(shù)據(jù)精度同時加快運行速度。

圖7 原曲率與采樣后曲率Fig.7 Original curvature and sampled curvature.

2.3 歸一化互相關(guān)匹配

對于兩條曲線采樣后曲率匹配，采用歸一化互相關(guān)算法進(jìn)行相似度計算，計算公式為

其中：f為較短曲線中的一部分，作為模板窗口沿著較長曲線滑動；u為兩條曲線的偏移量；為模板內(nèi)曲率均值；為滑動窗口在第二條曲線上曲率均值；v取值范圍為[–1，1]，數(shù)值越大相似度越高。

為確定兩曲線最相似部分，從較短曲線a中截取所有可能曲線段與另一曲線b進(jìn)行曲率匹配。對于截取的第i條曲線段ci在曲線b上滑動匹配時，將互相關(guān)系數(shù)最大處（圖8 P點）作為曲線段ci與曲線b的匹配度。曲線a上所有可能曲線段完成計算后，將匹配度最高曲線段作為兩曲線最相似部分。

圖8 曲線段匹配度Fig.8 Curve segment matching score

對于所有可能曲線段進(jìn)行匹配時，曲線段越短通常相關(guān)系數(shù)越大，直接利用歸一化互相關(guān)系數(shù)暴力匹配，計算量大且得到的大多是長度短、難以利用的曲線如圖9所示。

圖9 暴力匹配結(jié)果Fig.9 Brute force match results

為提高匹配效果并減小計算量采取以下策略。

1）設(shè)置曲線段長度與步長

精準(zhǔn)匹配時對曲線a中所有曲線段進(jìn)行互相關(guān)計算效率較低。經(jīng)多次試驗，設(shè)置步長與截取曲線長度為

其中：step為步長；nj為截取曲線長度；A為截取曲線長度集合；ns為曲線a長度。

2）修改曲線段匹配度計算方式

考慮到曲線長度較長時，計算所得相關(guān)系數(shù)一般較低，為獲得較長曲線匹配結(jié)果，計算匹配得分時加入曲線長度作為權(quán)重系數(shù)

其中：S為匹配結(jié)果最終得分；L為曲線段c的長度。

設(shè)曲線a長度為ns與b長度為nl，暴力匹配方法截取曲線長度nj∈[1,ns]，此時匹配計算復(fù)雜度

采取兩策略后，匹配時間復(fù)雜度為

比較式（23）與式（24）可知，匹配時間復(fù)雜度最高次項由2次降為0次，計算量大幅減少，同時匹配效果得到提升如圖10所示。

圖10 采取策略后匹配結(jié)果Fig.10 The matching result after adopting strategies.

3 實驗結(jié)果分析

對于本文提出的曲線精準(zhǔn)匹配算法，從時間復(fù)雜度與精準(zhǔn)匹配率兩方面進(jìn)行分析。

曲線匹配時間與硬件環(huán)境密切相關(guān)，因此使用算法執(zhí)行所需要的計算工作量即時間復(fù)雜度來進(jìn)行比較。基于描述符進(jìn)行曲線匹配時，采用最近鄰比率原則，需要找到最近鄰和次近鄰匹配項，設(shè)兩匹配圖像提取到的曲線數(shù)分別為n1與n2，則描述符匹配時間復(fù)雜度為

如2.3節(jié)中所述，在曲率匹配中一對曲線計算時間復(fù)雜度為O（1），則曲率匹配總體時間復(fù)雜度為

其中nd為基于描述符匹配得到的匹配曲線對數(shù)。

將描述符與曲率結(jié)合后算法時間復(fù)雜度為

比較式（25）、式（26）、式（27）可得，在基于描述符匹配基礎(chǔ)上，加入曲率匹配后時間復(fù)雜度仍然為O（n2）。本文提出曲線精準(zhǔn)匹配算法與基于描述符的匹配算法相比，算法時間復(fù)雜度保持不變。

在精準(zhǔn)匹配率方面，由于探測器下降階段，圖像紋理特征會發(fā)生縮放、旋轉(zhuǎn)及光照變換，故分別在3種情況下進(jìn)行實驗。為評價不同變換下曲線精準(zhǔn)匹配效果，對匹配曲線進(jìn)行離散弗雷歇距離計算[22]。對于2條匹配曲線，根據(jù)兩者長度之比設(shè)置采樣間隔，得到長度相等的兩曲線A、B。之后通過旋轉(zhuǎn)、平移將兩曲線端點重合如圖11所示。

圖11 弗雷歇距離計算Fig.11 Fréchet distance calculation.

計算兩曲線弗雷歇距離時，對于曲線B上一點m，計算該點到曲線A上各點歐氏距離，將所有歐氏距離中最小值作為候選弗雷歇距離。對曲線B中各點完成計算后，將候選弗雷歇距離最大值作為曲線A與曲線B的弗雷歇距離。經(jīng)實驗，在評估時將弗雷歇距離小于5的結(jié)果作為精準(zhǔn)匹配。

實驗所用為從NASA官網(wǎng)得到的真實小天體圖像。圖12為尺度、旋轉(zhuǎn)與光照變換下描述符匹配算法實驗結(jié)果，表1為3種變換下相應(yīng)精準(zhǔn)匹配率。結(jié)合圖12與表1可知，基于描述符匹配算法在尺度與旋轉(zhuǎn)變換下精準(zhǔn)匹配效果較差。

圖12 不同變換下描述符匹配算法實驗結(jié)果Fig.12 The experimental results of descriptor matching algorithm under different transformations

表1 不同變換下描述符匹配算法精準(zhǔn)匹配率Table 1 The accurate matching rate of descriptor matching algorithm under different transformations

圖13～15展示了尺度、旋轉(zhuǎn)與光照變換下本文所述曲線精準(zhǔn)匹配算法實驗結(jié)果，表2為3種變換下相應(yīng)精準(zhǔn)匹配率。結(jié)合圖13～15與表2可以看出，在尺度、旋轉(zhuǎn)與光照變換下，本文描述的描述符與曲率相結(jié)合的曲線精準(zhǔn)匹配算法可以達(dá)到84%以上精準(zhǔn)匹配率。

表2 不同變換下精準(zhǔn)匹配率Table 2 The accurate matching rate under different transformations

圖13 尺度變換下實驗結(jié)果Fig.13 The experiment results with scale variation

圖14 旋轉(zhuǎn)變換下實驗結(jié)果Fig.14 Matching score with illumination variation

圖15 光照亮度變換下實驗結(jié)果Fig.15 The experiment results with illumination variation

4 結(jié) 論

針對曲線描述符難以精準(zhǔn)匹配、曲率匹配僅能處理兩條曲線的問題，本文提出一種將兩者相結(jié)合的曲線精準(zhǔn)匹配算法，主要包括曲線提取、描述符匹配與曲率匹配3部分。曲線提取部分根據(jù)Edge Drawing算法進(jìn)行邊緣曲線檢測；描述符匹配部分對曲線及周圍支撐區(qū)域信息進(jìn)行描述，根據(jù)最近鄰距離比率原則完成粗匹配；曲率匹配部分根據(jù)無符號曲率積分對曲率曲線重采樣，并根據(jù)歸一化互相關(guān)算法完成曲線精準(zhǔn)匹配。實驗結(jié)果表明，本文提出的算法可以達(dá)到84%以上的精準(zhǔn)匹配率。