袁東華，趙化啟，王宇春，程 巖，郭 浩，劉 琳，李國晶，劉曉敏

（1 佳木斯大學(xué) 信息電子技術(shù)學(xué)院，黑龍江 佳木斯 154000；2 佳木斯大學(xué) 材料科學(xué)與工程學(xué)院，黑龍江 佳木斯 154007）

0 引言

無人系統(tǒng)的感知與導(dǎo)航已經(jīng)受到國內(nèi)外廣泛重視。美國發(fā)布了《無人系統(tǒng)綜合路線圖》，而中國科協(xié)將無人系統(tǒng)中高精度智能導(dǎo)航列為十大工程技術(shù)難題之一［1］。而基于視覺目標(biāo)定位方法是無人機技術(shù)中研究的熱點［2］。

本文研究的機載下視目標(biāo)定位定義為給定目標(biāo)圖像（衛(wèi)星圖像）找到目標(biāo)圖像在參考圖像（無人機圖像）中的位置。目前基于深度學(xué)習(xí)的方法用于目標(biāo)定位中，代表性的算法有Faster RCNN［3］、Strong-CNN［4］和CVM-Net［5］。相較于基于深度學(xué)習(xí)的目標(biāo)定位方法，基于特征匹配的方法能夠更好地完成智能定位任務(wù)［6］。傳統(tǒng)的特征匹配方法是SIFT 特征匹配［7］，大量的改進(jìn)算法用于自然圖像的目標(biāo)定位［8-11］已產(chǎn)生了好的效果。然而針對機載下視目標(biāo)定位效果不好。微分同胚的非剛性點集匹配廣泛用于醫(yī)學(xué)圖像處理，可解決大尺度形變問題［12-15］。綜上所述，針對機載下視目標(biāo)定位任務(wù)存在的問題本文提出有效方案，存在問題如下：

（1）傳統(tǒng)點集匹配模型［7］具有固定自由度，無法解決大尺度形變的問題。

（2）現(xiàn)有的點集匹配算法［7］并未考慮噪聲對變換模型的影響，當(dāng)有異常點時得到的變換模型不準(zhǔn)確。

（3）現(xiàn)有微分同胚大多為稠密微分同胚點集匹配方法［16］，無法用于機載下視目標(biāo)定位中。

針對以上問題，本文提出以下創(chuàng)新：

（1）提出了新的非剛性變換的目標(biāo)定位框架，創(chuàng)新在于隨機采樣微分同胚點集匹配的使用。

（2）現(xiàn)有微分同胚點集匹配通常是稠密的，本文創(chuàng)新提出關(guān)鍵點約束的微分同胚點集匹配用于機載下視目標(biāo)定位。

（3）創(chuàng)新提出使用K-means 分類算法與隨機采樣結(jié)合的微分同胚點集匹配方法。

1 基于隨機采樣微分同胚點集匹配的目標(biāo)定位方法

針對機載下視目標(biāo)定位中的大尺度形變問題，本文提出了基于隨機采樣微分同胚點集匹配的目標(biāo)定位方法，研究內(nèi)容包括目標(biāo)定位方法整體框架、圖像關(guān)鍵點檢測、特征匹配、隨機采樣微分同胚點集匹配方法以及目標(biāo)定位相似性計算。

1.1 目標(biāo)定位方法整體框架

本文提出了一種基于隨機采樣微分同胚點集匹配的目標(biāo)定位方法，框架如圖1 所示，該框架包括：關(guān)鍵點檢測、特征點匹配、隨機采樣微分同胚點集匹配和目標(biāo)定位相似性計算四個部分。給定目標(biāo)圖像和參考圖像，首先利用SIFT 關(guān)鍵點檢測方法確定目標(biāo)圖像和參考圖像中的關(guān)鍵點集，通過隨機K-D 樹最近鄰算法得到一致性關(guān)鍵點集，為了降低異常點對匹配性能的影響，如圖1（b）所示，其中C11，C12，C13，C14表示每一個子集中的隨機像素點，并構(gòu)成C1像素點集合，使用微分同胚點集匹配方法擬合變換模型f1，迭代隨機采樣相同大小數(shù)據(jù)集，將數(shù)據(jù)集元素帶入擬合變換模型，并統(tǒng)計符合模型的點集個數(shù)k1進(jìn)行輸出，使用同樣方法確定點集C2至Cn，確定變換模型f2至fn，輸出點集個數(shù)k2至kn，通過選擇k1至kn中最大值確定最優(yōu)變換模型，最后計算變換圖像與參考圖像的SSD 值確定目標(biāo)定位結(jié)果。

圖1 本文目標(biāo)定位方法框架圖Fig. 1 The framework of target localization method in this paper

1.2 關(guān)鍵點檢測與特征點匹配

隨機采樣微分同胚點集匹配方法是基于關(guān)鍵點檢測與特征點匹配基礎(chǔ)之上，為了更好地確定目標(biāo)圖像和參考圖像間的空間變換模型，本文使用SIFT算法檢測目標(biāo)圖像和參考圖像的關(guān)鍵點集。SIFT算法主要包括尺度空間極值檢測、關(guān)鍵點的定位、確定特征點主方向和生成特征向量4 個步驟［7］：

（1）尺度空間極值檢測：使用DOG（Difference of gaussian）算子構(gòu)造尺度空間，并在尺度空間中搜尋極值點作為候選的特征點。

（2）關(guān)鍵點的定位：將候選的特征點定位到亞像素精度，并剔除不穩(wěn)定的候選點。

（3）確定特征點主方向：利用特征點鄰域像素的梯度分布特性確定每個特征點的主方向。

（4）生成特征向量：統(tǒng)計以特征點為中心的局部區(qū)域梯度，形成128 維梯度特征向量，并對其歸一化。

為了獲得一致性關(guān)鍵點集，本文使用隨機K-D樹最近鄰算法計算特征點的相似性，隨機K-D 樹算法的主要思想是將K-D 樹算法中的一棵樹拓展為多棵樹。首先，算法在數(shù)據(jù)集的所有維度上進(jìn)行方差計算并按大小排序，然后在方差最大的前D個結(jié)果中隨機選擇一個維度來構(gòu)建隨機樹。在搜索樹時，首先用所有隨機化的K-D 樹構(gòu)成一個優(yōu)先隊列，然后將此前一棵樹的搜索變換成在多棵樹上同時進(jìn)行搜索，最后對結(jié)果進(jìn)行排序獲得最優(yōu)相似性結(jié)果［14］，得到了一致性關(guān)鍵點集。

1.3 隨機采樣微分同胚點集匹配方法

微分同胚點集匹配屬于非剛性點集匹配方法，與剛性點集匹配相比，非剛性點集匹配具有更多的自由度，這使得微分同胚更加適合具有大尺度形變的目標(biāo)檢測任務(wù)。然而在整個點集中直接使用微分同胚點集匹配方法會導(dǎo)致過擬合，使得定位結(jié)果不準(zhǔn)確，因此本文引入K-means 聚類算法將一致性關(guān)鍵點集進(jìn)行分類，并在多個子集上利用隨機采樣方法獲得生成變換模型所需的子集，該方法有效地降低了異常點對目標(biāo)定位性能的影響。以下內(nèi)容針對微分同胚點集匹配和基于隨機采樣微分同胚點集匹配方法進(jìn)行詳細(xì)介紹。

1.3.1 基于微分同胚的點集匹配

給定二維圖像的圖像域是二維歐式空間，記為R2。目標(biāo)圖像X和參考圖像Y的2 組對應(yīng)特征點集，分別為：｛xi∈Ω1｜i ＝1，2，…，n｝和｛yi∈Ω2｜i ＝1，2，…，n｝，其中Ω1?R2和Ω2?R2。微分同胚點集匹配是要找到一個變換g：Ω1→Ω2，滿足g（xi）＝y(tǒng)i，?i ＝1，2，…，n。

微分同胚點集匹配有2 個重要特性：光滑性和拓?fù)浔３中裕?5］。分別闡釋如下。

（1）光滑性：當(dāng)變換g的所有偏導(dǎo)數(shù)都存在且是連續(xù)的，那么變換g：Ω1→Ω2具有光滑性。

（2）拓?fù)浔３中裕浩ヅ鋾r如果Ω1和Img（g）＝｛x2∈Ω2｜?y1∈Ω1，x2＝g（y1）｝有相同的拓?fù)浣Y(jié)構(gòu)，那么變換g：Ω1→Ω2具有拓?fù)浔３中浴?/p>

由微分同胚的特性可知，不僅能使圖像在變換前后的拓?fù)浣Y(jié)構(gòu)不發(fā)生變化，并且還保留了原有幾何結(jié)構(gòu)的光滑性。因此，該類模型能擬合較大程度的非剛體形變。

微分同胚變換的構(gòu)造先使用時間依賴的速度矢量場s（t）和相關(guān)聯(lián)流來構(gòu)造微分同胚變換群；再通過再生核希爾伯特空間方法來生成速度矢量空間S；在速度矢量空間S的約束下，計算能量泛函E（s）的最優(yōu)解，生成滿足微分同胚非剛體變換的形變場［16］。

假設(shè)s：［0，1］｜→S為時間依賴的速度矢量場，用其來構(gòu)造微分同胚變換時，速度矢量場s（t，·）須滿足下列方程：

使用再生核希爾伯特空間方法來構(gòu)建速度矢量場空間S是構(gòu)建微分同胚變換群的核心步驟。根據(jù)Riesz 定理，必存在空間S中Kx使得對于所有s∈S均有：

其中，＜·，·＞是希爾伯特空間S上的內(nèi)積，記（x），則Kx（y）＝K（x，y）為S上的再生核。根據(jù)矢量空間樣條插值相關(guān)原理可知，在空間S中插值問題的最優(yōu)解形式可表現(xiàn)為：

其中，α為再生核的系數(shù)矢量，這里根據(jù)希爾伯特空間S的范數(shù)定義可得：

基于微分同胚非剛體變換的匹配的能量泛函如下：

1.3.2 基于隨機采樣微分同胚點集匹配方法

將微分同胚點集匹配方法直接用于一致性點集上會受到大量異常點的干擾，這導(dǎo)致微分同胚點集匹配結(jié)果很差，因此本文使用K-means 聚類方法有效地將一致性點集劃分成若干子集，在多個子集上使用隨機采樣一致性算法來確定微分同胚變換模型，下面內(nèi)容詳細(xì)介紹了隨機采樣一致性算法、Kmeans 聚類方法以及基于K-means 隨機采樣微分同胚點集匹配方法。對此可做解析闡述如下。

（1）隨機采樣一致性算法。Fischler 等人［17］提出的隨機采樣一致性算法是一種通用的參數(shù)估計方法，用于處理數(shù)據(jù)中存在較大比例的異常值時，該方法具有一定的魯棒性。假設(shè)可以被模型描述的數(shù)據(jù)稱為內(nèi)點（inliers），而無法適應(yīng)模型的數(shù)據(jù)稱為離群點（outliers）。隨機采樣一致性算法的思想是使用盡可能小的初始數(shù)據(jù)集得到初始解，并將可能的內(nèi)點數(shù)據(jù)并入到內(nèi)點集合中。不斷重復(fù)，得到一個最大的內(nèi)點集合，該集合對應(yīng)的解為最佳解。

隨機采樣一致性算法的一般步驟如下：

輸入數(shù)據(jù)集U，最大迭代次數(shù)N，判定為內(nèi)點的閾值δ，內(nèi)點數(shù)目閾值τ

輸出內(nèi)點集合U'

步驟1從U中隨機選擇確定模型參數(shù)所需最小的數(shù)據(jù)。

步驟2使用公式（1）求解模型參數(shù)。

步驟3從U中確定誤差滿足閾值δ的數(shù)據(jù)點，記為內(nèi)點。

步驟4若內(nèi)點與總點數(shù)的比值大于閾值τ，則用已找到的內(nèi)點重新估計模型參數(shù)，輸出內(nèi)點集合U'并終止。

步驟5否則重復(fù)步驟1～4，最多不超過N次。

（2）K-means 聚類。K-means 算法是經(jīng)典的基于劃分的無監(jiān)督聚類算法，能很好地將數(shù)據(jù)劃分開，使得同一類中的數(shù)據(jù)具有較高的相似性，而不同的類之間的數(shù)據(jù)相似性較低，本文將一致性關(guān)鍵點集中目標(biāo)圖像的關(guān)鍵點集進(jìn)行聚類，相應(yīng)的一致性關(guān)鍵點集分成了若干個子集，接下來的微分同胚點集匹配方法將作用于若干子集上。

K-means 算法的核心思想如下：首先從數(shù)據(jù)集中隨機選取p個初始聚類中心，計算剩余數(shù)據(jù)到每個初始聚類中心的歐式距離，選擇距離最近的聚類中心形成p簇。接著，計算每個簇中數(shù)據(jù)的平均值來更新聚類中心并進(jìn)行下一次迭代，直到聚類中心不再改變或達(dá)到預(yù)設(shè)的迭代次數(shù)才停止［18］。

（3）基于K-means 的隨機采樣微分同胚點集匹配。為了能夠進(jìn)一步降低一致性關(guān)鍵點集中的異常點對目標(biāo)檢測帶來的影響，本文提出基于K-means聚類與微分同胚結(jié)合匹配方法，有效完成了目標(biāo)檢測任務(wù)。該方法首先通過K-means 聚類方法將一致性關(guān)鍵點集分成多個子集，在每個子集中隨機采樣關(guān)鍵點集，通過優(yōu)化方法獲得最佳微分同胚變換模型，基于K-means 的隨機采樣微分同胚點集匹配算法步驟具體如下。

輸入一致性關(guān)鍵點集，最大迭代次數(shù)L，判定為內(nèi)點的閾值σ，內(nèi)點數(shù)目閾值T，相似性閾值S

輸出微分同胚模型f

步驟1使用K-means 算法將一致性關(guān)鍵點集劃分為m類。

步驟2分別從m類中隨機采樣，記為Ci1，Ci2，Ci3，Ci4，這里i ＝1，…，n，且合并為Ci（i ＝1，…，n）。

步驟3使用數(shù)據(jù)樣本Ci（i ＝1，…，n）通過公式（1）和公式（6）擬合微分同胚模型fi（i ＝1，…，n）。

步驟4還未被采樣的目標(biāo)圖像關(guān)鍵點通過fi（i ＝1，…，n）得到對應(yīng)的映射點。

步驟5計算映射點與參考圖像關(guān)鍵點之間的誤差e，若e ＜δ，則判定為內(nèi)點，否則為外點。

步驟6統(tǒng)計內(nèi)點數(shù)目，記為ki（i ＝1，…，n）。

步驟7將ki與內(nèi)點數(shù)目閾值T進(jìn)行比較，若ki ＞T，輸出對應(yīng)的微分同胚變換模型fi，否則迭代次數(shù)加1，并重復(fù)步驟2～7。

步驟8若當(dāng)前迭代次數(shù)為L、且ki ＜T，則輸出ki中最大值對應(yīng)的微分同胚模型fi。

1.4 目標(biāo)定位相似性計算

記目標(biāo)圖像為I1，參考圖像為I2。目標(biāo)圖像根據(jù)最優(yōu)微分同胚模型進(jìn)行變換得到變化后圖像記為I3。變換后圖像與參考圖像之間相似性根據(jù)下面的公式進(jìn)行計算：

其中，W和H分別為圖像的寬和高；I3（x，y）為變換后圖像在坐標(biāo)（x，y）處的像素值；I2（x，y）為參考圖像在坐標(biāo)（x，y）的像素值。SSD值越小，說明相似性越高，當(dāng)SSD小于設(shè)定閾值時，認(rèn)為本次目標(biāo)定位結(jié)果有效。

2 實驗結(jié)果與分析

2.1 實驗環(huán)境與實驗數(shù)據(jù)

實驗平臺為：內(nèi)存8 GB、處理器3.12 GHz、操作系統(tǒng)Win10 的PC。實驗環(huán)境為：Matlab R2016b、Visual Studio 2015 和OpenCV 2.4.9。

實驗數(shù)據(jù)為悉尼科技大學(xué)針對無人機地理定位問題發(fā)布的University-1652 數(shù)據(jù)集，該數(shù)據(jù)集以全球72 所大學(xué)的1 652 座建筑為目標(biāo)位置，包含了衛(wèi)星圖像、無人機圖像和每個位置的地面圖像。University-1652 數(shù)據(jù)集具有多源、多視角特點，首先，該數(shù)據(jù)集的數(shù)據(jù)來源于3 個不同平臺，分別是衛(wèi)星、無人機和手機攝像頭；其次，地面圖像是從目標(biāo)建筑的不同視角收集的，而無人機圖像是從不同的距離和方向收集的［4］。本文實驗選取University-1652 數(shù)據(jù)集的前101 類的衛(wèi)星圖像（每類1 張圖片）及對應(yīng)的101 類無人機圖像（每類54 張圖片），衛(wèi)星圖像和無人機圖像大小均為512×512 像素。

2.2 評價指標(biāo)

本文評價不同算法的優(yōu)劣是通過比較相應(yīng)的ROC曲線下的面積、即AUC值來判斷的，AUC值越高代表算法性能越好。

ROC曲線的縱軸為真正例率，橫軸為假正例率，兩者定義如下：

其中，TP表示正類被預(yù)測為正類；FN表示正類被預(yù)測成負(fù)類；FP表示負(fù)類被預(yù)測成正類；TN表示負(fù)類被預(yù)測成負(fù)類。

假設(shè)ROC曲線是由有限個坐標(biāo)為｛（x1，y1），（x2，y2），…，（xn，yn）｝ 的點按順序相連得到，其中（x1＝0，xn ＝1），那么計算AUC值的公式可表示為：

2.3 基于微分同胚的非剛體變換模型與投影變換模型的比較

基于微分同胚的非剛體變換模型比投影變換模型具有更高的自由度，無論是剛體變換、還是非剛體變換，最小二乘法是最通用的模型擬合方法，本節(jié)使用最小二乘法對變換模型進(jìn)行擬合，實驗比較了微分同胚的變換模型和投影變換模型檢測結(jié)果，結(jié)果如圖2 所示。圖2 中，曲線a）是基于最小二乘法的微分同胚點集匹配算法，曲線b）是SIFT＋最小二乘法投影變換算法。

圖2 非剛性模型和剛性模型比較Fig. 2 Comparison of non-rigid and rigid models

圖2 中，曲線a）對應(yīng)算法的AUC值要遠(yuǎn)大于曲線b）對應(yīng)算法的AUC值，因此基于微分同胚的非剛體變換模型比投影變換模型能更好地完成機載下視目標(biāo)定位的任務(wù)。

2.4 隨機采樣微分同胚匹配實驗結(jié)果與分析

本節(jié)使用隨機采樣一致性算法對基于微分同胚的非剛體模型和投影變換模型進(jìn)行擬合，并與在一致性關(guān)鍵點集上直接進(jìn)行微分同胚模型擬合加以比較，實驗結(jié)果如圖3 所示。圖3 中，曲線a）表示隨機采樣微分同胚算法，曲線b）表示SIFT＋隨機采樣投影變換算法，曲線c）表示微分同胚點集匹配算法。

圖3 隨機采樣微分同胚算法比較Fig. 3 Comparison of random sampling differential homozygous models

首先從圖3 中曲線c）對應(yīng)算法可以得出，直接在一致性關(guān)鍵點集上進(jìn)行微分同胚模型擬合的結(jié)果是非常差的，因此需要對一致性關(guān)鍵點集進(jìn)行處理。再比較圖3 中曲線a）和曲線b）各自對應(yīng)算法可得出，在一致性關(guān)鍵點集上使用隨機采樣一致性算法進(jìn)行變換模型擬合效果更好，同時微分同胚比投影變換的隨機采樣算法要好。

2.5 K-means 聚類個數(shù)實驗結(jié)果與分析

本節(jié)將討論使用K-means 算法對一致性關(guān)鍵點集進(jìn)行劃分對隨機采樣微分同胚點集匹配算法的影響。

K 均值聚類是基于劃分的聚類，該方法必須先指定聚簇個數(shù)，隨后得到的聚類結(jié)果與初始選擇的聚簇個數(shù)直接相關(guān)。雖然文獻(xiàn)［16］指出最優(yōu)的聚簇個數(shù)會落在的區(qū)間內(nèi)（m為數(shù)據(jù)集大?。?，但經(jīng)過實驗發(fā)現(xiàn)一致性關(guān)鍵點集最大的聚簇個數(shù)為5。因此，本節(jié)實驗分別將一致性關(guān)鍵點集劃分為1（相當(dāng)于未聚類）、2、3、4 和5 類，并在劃分后的子集上使用隨機采樣微分同胚點集匹配算法進(jìn)行實驗對比，實驗結(jié)果如圖4 所示。

圖4 不同聚簇個數(shù)的影響Fig. 4 Effect of different number of clusters

由圖4 可看到，曲線b）、曲線c）、曲線d）和曲線e）各自對應(yīng)算法的AUC值均大于曲線a）對應(yīng)算法的AUC值，且曲線d）對應(yīng)算法的AUC值最大。因此，使用K-means 算法對一致性關(guān)鍵點集進(jìn)行劃分，在每一個稀疏化子集中使用隨機采樣方法能有效提高隨機采樣微分同胚點集匹配算法的性能，且將一致性關(guān)鍵點集劃分為4 類時，對隨機采樣微分同胚點集匹配算法性能的提升最大。

2.6 現(xiàn)有目標(biāo)定位算法比較

為了證明本文提出的目標(biāo)定位算法的優(yōu)勢，本節(jié)將建議的算法與DEMONS 算法、LDDMM 算法、CVM-NET 算法、Faster RCNN 算法、Strong-CNN 算法和基于SIFT 的隨機采樣投影變換算法進(jìn)行比較，其對比結(jié)果如圖5 所示。

圖5 主流算法比較Fig. 5 Comparison of mainstream algorithms

傳統(tǒng)SIFT 投影變換方法具有最小的準(zhǔn)確率；常用的幾種目標(biāo)定位方法CVM-NET、Faster RCNN 和Strong-CNN 算法優(yōu)于SIFT 算法，但是準(zhǔn)確率沒有達(dá)到最高。從實驗看出，基于微分同胚的目標(biāo)定位方法DEMONS 和LDDMM 算法在本文任務(wù)中具有較大優(yōu)勢。而本文建議的方法比現(xiàn)有的微分同胚的目標(biāo)定位方法準(zhǔn)確率提高了24%，實驗結(jié)果表明本文提出的方法可有效地用于機載下視目標(biāo)定位任務(wù)中。

上述算法的時間效率對比見表1。由表1 可知，本文算法檢測一幅圖像所需的時間要高于DEMONS 算法、LDDMM 算法、Faster RCNN 算法、Strong-CNN 算法、CVM-NET 算法以及SIFT＋隨機采樣投影變換算法。因此需要進(jìn)一步改進(jìn)來提高算法的檢測速度，這也是后續(xù)擬將探討研究的方向。

表1 時間效率對比Tab.1 Time efficiency comparison min

3 結(jié)束語

針對機載下視目標(biāo)定位中目標(biāo)圖像與參考圖像之間存在的大尺度形變問題，本文提出了一種非剛性點集匹配的目標(biāo)定位方法。首先，使用SIFT 算法提取目標(biāo)圖像和參考圖像的關(guān)鍵點，隨機K-D 樹最近鄰算法用于獲得一致性關(guān)鍵點集。然后，Kmeans 分類方法將一致性關(guān)鍵點集劃分成多個子集，并在多個子集上使用隨機采樣微分同胚點集匹配方法優(yōu)化空間變換模型。最后，通過SSD大小來確定最優(yōu)目標(biāo)位置。實驗結(jié)果表明，本文提出方法的準(zhǔn)確率比現(xiàn)有方法高24%，能夠有效地完成機載下視目標(biāo)定位任務(wù)。但是由于基于微分同胚的非剛性點集匹配自由度較大，因此算法運行時間較長，如何提高算法的實時性是下一步需要研究的內(nèi)容。