小天體表面紋理曲線精準(zhǔn)匹配算法

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

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

引 言

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

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

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

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

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

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

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

1 曲線描述符匹配

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 曲線曲率匹配

2.1 三次B樣條曲線擬合

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

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

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

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

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

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

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

2.2 尺度不變性曲率計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）修改曲線段匹配度計(jì)算方式

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

圖12 不同變換下描述符匹配算法實(shí)驗(yàn)結(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)匹配算法實(shí)驗(yà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 尺度變換下實(shí)驗(yàn)結(jié)果Fig.13 The experiment results with scale variation

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

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

4 結(jié) 論

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