薛理，楊樹文，馬吉晶，劉燕

(1.蘭州交通大學(xué) 測繪與地理信息學(xué)院，蘭州 730070；2.甘肅省地理國情監(jiān)測工程實(shí)驗(yàn)室，蘭州 730070)

0 引言

目前，圖像匹配算法通常分為兩大類[1]。一類是基于像素的匹配算法[2-7]，該類算法根據(jù)圖像的灰度進(jìn)行匹配，匹配精度高，但計(jì)算量大，而且對圖像非線性形變，光照和尺度變化的魯棒性不強(qiáng)。另一類是基于特征的匹配[8-15]，該類算法需要提取圖像上的特征點(diǎn)，然后對特征點(diǎn)進(jìn)行比較，來實(shí)現(xiàn)圖像的匹配，計(jì)算量相對較少。其中，David Lowe[11-12]于1999年提出尺度不變特征變換(scale-invariant feature transform，SIFT)匹配算法非常具有代表性。由于SIFT算法能夠?qū)D像旋轉(zhuǎn)、尺度縮放和亮度變化保持不變性，同時對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性，因此使用較為廣泛。Mikolajczyk和Schmid[16]進(jìn)一步對各種匹配方法進(jìn)行比較，表明SIFT算法具有非常強(qiáng)的魯棒性。然而，相關(guān)研究表明[17-18]，SIFT算法計(jì)算復(fù)雜，內(nèi)存消耗大，當(dāng)圖像較大時算法運(yùn)行時間較長。為此，學(xué)者們對該問題進(jìn)行了大量卓有成效的研究[19-21]。如Ke和Sukthankar[17]提出的基于尺度不變特征變換的主成分算法(principal components analysis based on representation for local features，PCA-SIFT)，即利用主成分分析歸一化權(quán)重直方圖來代替SIFT算法中平滑直方圖，并對SIFT描述符進(jìn)行降維，從而降低計(jì)算量，提高圖像匹配速度。Mikolajczyk和Schmid[18]提出的梯度位置方向直方圖算法(gradient location and orientation histogram，GLOH)，利用對數(shù)極坐標(biāo)分級結(jié)構(gòu)同心圓來降低算法的復(fù)雜性，提高算法效率。劉佳等[19]對圖像進(jìn)行多分辨率小波變換，去除高頻成分，采用“回”字形雙層方鄰窗將特征點(diǎn)鄰域區(qū)域劃分成四部分，建立32 維特征點(diǎn)描述符向量，從而提高匹配精度和效率。程德志等[20]利用準(zhǔn)歐氏距離代替歐氏距離作為特征描述符之間的相似性度量來提高SIFT特征匹配效率。

然而，上述改進(jìn)算法多以照片為研究對象，針對高分辨率遙感影像的研究較少，二者之間在算法精度和效率上存在較大差異。由此，作者通過實(shí)驗(yàn)對比分析，發(fā)現(xiàn)采用二次多項(xiàng)式能夠較為理想地?cái)M合影像直方圖；對關(guān)鍵點(diǎn)進(jìn)行初步篩選時，單一系數(shù)篩選較為合適，且最合適的系數(shù)為二次多項(xiàng)式的二次項(xiàng)系數(shù)；關(guān)鍵點(diǎn)初步篩選占比函數(shù)(key-points preliminary filtering proportion function，KPFPF)能夠在保證較高的匹配準(zhǔn)確率的前提下，明顯地提高算法匹配效率。因此，本文提出一種基于高分辨率遙感影像的多項(xiàng)式擬合的SIFT改進(jìn)算法。

1 算法設(shè)計(jì)

1.1 SIFT算法簡介

SIFT算法主要由4個部分組成：尺度空間極值點(diǎn)檢測、關(guān)鍵點(diǎn)精確定位、關(guān)鍵點(diǎn)方向確定和關(guān)鍵點(diǎn)描述符生成。

首先，使用不同的σ(正態(tài)分布標(biāo)準(zhǔn)差)對原始影像進(jìn)行高斯模糊，形成高斯金字塔。然后，每層金字塔中相鄰影像相減，形成高斯差分金字塔。其次，將高斯差分影像中每一個像素與周圍相鄰 8個像素和上下對應(yīng)9×2 個像素進(jìn)行對比[12，20]，尋找極值點(diǎn)。

上述檢測的極值點(diǎn)為離散空間的極值點(diǎn)，這些極值點(diǎn)位置并不精確，因此需要通過三維二次函數(shù)來精確確定極值點(diǎn)的位置，去除低對比度和邊緣響應(yīng)的極值點(diǎn)，形成關(guān)鍵點(diǎn)。

為了使描述符具有旋轉(zhuǎn)不變形，需要給每個關(guān)鍵點(diǎn)分配一個局部方向。首先，統(tǒng)計(jì)關(guān)鍵點(diǎn)領(lǐng)域窗口內(nèi)的像素值梯度和方向[20]。由于距離關(guān)鍵點(diǎn)越遠(yuǎn)的像素，對關(guān)鍵點(diǎn)的影響越小，因此需要對梯度進(jìn)行高斯加權(quán)。其次，將0～360°平均分成36 分，每份10°，生成方向直方圖，以直方圖最大值為關(guān)鍵點(diǎn)的主方向。同時為了增加算法的魯棒性，保留主方向峰值的80%的方向?yàn)楦狈较颉?/p>

按照關(guān)鍵點(diǎn)的方向?qū)﹃P(guān)鍵點(diǎn)領(lǐng)域區(qū)域進(jìn)行旋轉(zhuǎn)，以確保旋轉(zhuǎn)不變形。然后，選取關(guān)鍵點(diǎn)周圍8×8 窗口區(qū)域，將該區(qū)域分為4×4 個子區(qū)域，計(jì)算每個子區(qū)域8 個方向的梯度，共128 維向量。最后，為了去除光照變化的影響，需要對128 維向量進(jìn)行歸一化處理。

1.2 圖像直方圖分析

遙感影像直方圖能夠有效反映圖像灰度的分布規(guī)律、亮度值分布范圍、峰值的位置、均值以及亮度值分布的離散程度等特征。由此，論文通過對高分一號(GF-1)、高分二號(GF-2)、資源三號(ZY-3)和快鳥影像(QB-2)的灰度直方圖進(jìn)行分析，發(fā)現(xiàn)直方圖大體呈瘦鐘形分布，如圖1所示(圖中橫坐標(biāo)代表像素值，縱坐標(biāo)代表像素?cái)?shù)量)。

圖1 影像直方圖

1.3 二次多項(xiàng)式擬合直方圖

論文采用C#語言和地理空間數(shù)據(jù)抽象庫(geospatial data abstraction library，gdal)，利用編程的方式逐像素地讀取遙感影像數(shù)據(jù)，并將數(shù)據(jù)歸一化到0～255，然后統(tǒng)計(jì)0～255中每個像素值的頻率，最終生成散點(diǎn)圖。

通過實(shí)驗(yàn)得出使用二次多項(xiàng)式擬合散點(diǎn)圖能較為理想地反應(yīng)散點(diǎn)圖的整體趨勢，進(jìn)而間接反映圖像像素值的整體特征，如圖2所示，圖中紅線是擬合曲線。

圖2 二次多項(xiàng)式擬合

二次多項(xiàng)式擬合公式如公式(1)所示。

y=a0+a1x+a2x2

(1)

式中：a0、a1、a2為二次多項(xiàng)式的系數(shù)；x為像素值；y為像素值數(shù)量。

1.4 標(biāo)準(zhǔn)差

標(biāo)準(zhǔn)差能夠反應(yīng)組內(nèi)個體間的離散程度，因此，利用標(biāo)準(zhǔn)差可以反映遙感圖像像素值的整體離散特性。標(biāo)準(zhǔn)差的計(jì)算公式為：

(2)

式中：σ’為標(biāo)準(zhǔn)差；n為所有像素的數(shù)量；xi為第i個像素的值；μ為像素平均值。

1.5 系數(shù)分析

1)系數(shù)選取。通過上述分析發(fā)現(xiàn)，二次多項(xiàng)式函數(shù)和標(biāo)準(zhǔn)差都能夠反應(yīng)局部區(qū)域像素值的整體特性。因此，在圖像B的所有關(guān)鍵點(diǎn)中尋找圖像A中某關(guān)鍵點(diǎn)的匹配點(diǎn)之前，論文采用二次多項(xiàng)式系數(shù)和標(biāo)準(zhǔn)差對圖像B中所有關(guān)鍵點(diǎn)進(jìn)行初步篩選，然后，再用關(guān)鍵點(diǎn)128 維向量進(jìn)行匹配。

為了能更加直觀地分析實(shí)驗(yàn)結(jié)果，對算法的耗時、匹配點(diǎn)數(shù)量和匹配正確率[10]進(jìn)行統(tǒng)計(jì)，以曲線圖的形式進(jìn)行顯示，如圖3～圖6所示。正確匹配率如公式(3)所示。

(3)

式中：C代表正確匹配率；cm代表正確匹配的關(guān)鍵點(diǎn)數(shù)量；fm代表錯誤匹配的關(guān)鍵點(diǎn)數(shù)量。

圖3至圖6中時間比代表關(guān)鍵點(diǎn)初步篩選后的算法時間與SIFT算法時間的比值，預(yù)選點(diǎn)占比代表關(guān)鍵點(diǎn)初步篩選點(diǎn)的數(shù)量占圖像B中所有關(guān)鍵點(diǎn)的比率，匹配點(diǎn)數(shù)量代表關(guān)鍵點(diǎn)初步篩選后的算法關(guān)鍵點(diǎn)匹配數(shù)量，正確率代表正確匹配率。

圖3 平移匹配結(jié)果

圖4 旋轉(zhuǎn)匹配結(jié)果

圖5 縮放匹配結(jié)果

圖6 模糊匹配結(jié)果

通過分析圖3至圖6，可以得出以下結(jié)論：①平移、旋轉(zhuǎn)和縮放結(jié)果的時間比曲線和匹配點(diǎn)曲線大致呈線性分布，正確率曲線大致呈對數(shù)分布。②系數(shù)a0、a1、a2和σ’的平移、旋轉(zhuǎn)和縮放結(jié)果的匹配點(diǎn)相差不大，因此采用多個系數(shù)聯(lián)合對關(guān)鍵點(diǎn)進(jìn)行初步篩選的方式和單個系數(shù)篩選效果類似。③在系數(shù)a0、a1、a2和σ’的正確率曲線中，a2正確率收斂到1，預(yù)選點(diǎn)占比最大為20%。a1正確率收斂到1，預(yù)選點(diǎn)占比最大為25%，a0和σ’的正確率在縮放結(jié)果中達(dá)不到100%。因此采用系數(shù)a2和a1來初步篩選關(guān)鍵點(diǎn)較為合適。④在平移、旋轉(zhuǎn)和縮放結(jié)果中，系數(shù)a1和a2的時間占比大致相等，然而在模糊結(jié)果中a1的時間占比明顯大于a2。

綜上所述，采用單一系數(shù)a2對關(guān)鍵點(diǎn)進(jìn)行初步篩選較為合適。

2)關(guān)鍵點(diǎn)初步篩選占比分析。雖然上述分析確定了關(guān)鍵點(diǎn)篩選的系數(shù)，但是關(guān)鍵點(diǎn)的篩選數(shù)量的問題并沒有解決，因此接下來主要分析關(guān)鍵點(diǎn)初步篩選的比例。論文選擇GF-1、GF-2和QB-2影像中的7張圖像，分別對每張圖像做平移、旋轉(zhuǎn)、縮放和模糊處理，實(shí)驗(yàn)結(jié)果如圖7所示。

當(dāng)初步篩選結(jié)果的匹配點(diǎn)數(shù)量占原算法的1/5左右時，匹配點(diǎn)數(shù)量足夠，匹配準(zhǔn)確率高，同時耗時少。因此以原SIFT算法1/5左右匹配點(diǎn)數(shù)來限定初步篩選結(jié)果的匹配點(diǎn)數(shù)量，來觀察初步篩選點(diǎn)占比，即初步篩選關(guān)鍵點(diǎn)占圖像B關(guān)鍵點(diǎn)數(shù)量的比例。

根據(jù)上述標(biāo)準(zhǔn)對圖7中的圖像進(jìn)行匹配。對匹配結(jié)果進(jìn)行分析，發(fā)現(xiàn)初步篩選關(guān)鍵點(diǎn)占比與圖像B關(guān)鍵點(diǎn)數(shù)量的相關(guān)性較為明顯，因此對初步篩選關(guān)鍵點(diǎn)占比與圖像B關(guān)鍵點(diǎn)總數(shù)進(jìn)行統(tǒng)計(jì)，生成散點(diǎn)圖，如圖8所示。

圖8 初步篩選散點(diǎn)圖

圖中，橫坐標(biāo)代表圖像B關(guān)鍵點(diǎn)數(shù)量，縱坐標(biāo)代表初步篩選關(guān)鍵點(diǎn)占比。從圖中可以發(fā)現(xiàn)，散點(diǎn)大致呈冪函數(shù)分布，因此用冪函數(shù)擬合這些散點(diǎn)，擬合曲線如圖中紅線所示。從圖中可以看出擬合效果較為理想，因此關(guān)鍵點(diǎn)占比與圖像B關(guān)鍵點(diǎn)數(shù)量之間的函數(shù)，如公式(4)所示。

y=0.172 5×x-0.129

(4)

式中：x代表圖像B關(guān)鍵點(diǎn)的數(shù)量;y代表初步篩選關(guān)鍵點(diǎn)占比。

2 算法模型

根據(jù)上述原理，本文提出一種基于高分辨率遙感影像的多項(xiàng)式擬合的SIFT改進(jìn)算法，流程圖如圖9所示。

圖9 算法流程圖

具體步驟如下：

①采用高斯函數(shù)對原圖像A和B進(jìn)行模糊，生成高斯金字塔。然后每層金字塔相鄰圖像相減生成高斯差分金字塔；

②在高斯差分金字塔中尋找極值點(diǎn)，并采用三維二次函數(shù)精確定位關(guān)鍵點(diǎn)；

③統(tǒng)計(jì)高斯金字塔中每個關(guān)鍵點(diǎn)周圍領(lǐng)域窗口的像素值，生成直方圖，并利用二次函數(shù)進(jìn)行擬合，獲得系數(shù)a2；

④取出圖像A中的關(guān)鍵點(diǎn)ki，根據(jù)初步篩選占比函數(shù)，利用系數(shù)a2對圖像B中的關(guān)鍵點(diǎn)進(jìn)行初步篩選。然后利用128維向量計(jì)算歐式距離最近的2個點(diǎn)，如果次近鄰點(diǎn)歐式距離小于最近鄰點(diǎn)的0.49倍，則該2個關(guān)鍵點(diǎn)相互匹配，否則ki在圖像B中沒有相互匹配的關(guān)鍵點(diǎn)。重復(fù)上述過程直到圖像A中所有關(guān)鍵點(diǎn)遍歷一遍，算法結(jié)束。

3 實(shí)驗(yàn)與分析

實(shí)驗(yàn)選取位于甘肅省蘭州市的GF-1影像，影像大小為800 像素×600 像素，如圖10(a)所示。對該影像進(jìn)行平移、旋轉(zhuǎn)、縮放和模糊處理，處理結(jié)果如圖10(b)所示。采用文獻(xiàn)[12]提出的SIFT算法和論文改進(jìn)算法對圖像10(a)和圖10(b)進(jìn)行圖像匹配，實(shí)驗(yàn)結(jié)果分別如圖10(c)和圖10(d)所示。

從圖10中容易得出改進(jìn)算法相互匹配的關(guān)鍵點(diǎn)分布均勻，且關(guān)鍵點(diǎn)之間的距離較遠(yuǎn)。原SIFT算法關(guān)鍵點(diǎn)較為密集，且存在大量距離較為接近的關(guān)鍵點(diǎn)。

為了驗(yàn)證算法的魯棒性，本文又分別對GF-2、ZY-3和QB-2進(jìn)行實(shí)驗(yàn)，以GF-2影像為例，實(shí)驗(yàn)結(jié)果如圖11所示。

為了能直觀地比較論文改進(jìn)算法與原算法的匹配精度，統(tǒng)計(jì)GF-1和GF-2匹配結(jié)果的匹配點(diǎn)數(shù)，匹配準(zhǔn)確率和算法時間，如表1所示。

從表1容易得出：①GF-1和GF-2的改進(jìn)算法匹配點(diǎn)數(shù)分別占SIFT算法匹配點(diǎn)數(shù)的17.1%和22.3%；②改進(jìn)算法的正確匹配率平均為0.986%，SIFT算法的正確匹配率平均為0.998%，2種算法的正確匹配率大致相等；③GF-1和GF-2的改進(jìn)算法時間與SIFT算法時間的比值分別為0.551和0.565。

通過上述分析得出：改進(jìn)算法的匹配點(diǎn)分布均勻，其匹配點(diǎn)數(shù)占SIFT算法的1/5左右，改進(jìn)算法的匹配準(zhǔn)確率與原算法大致相等，同時改進(jìn)算法能夠明顯加快算法的時間效率。因此改進(jìn)后的算法能夠在保正較高匹配準(zhǔn)確率的前提下，明顯提高原算法的匹配效率，適用于遙感影像匹配。

圖10 GF-1影像匹配結(jié)果

表1 關(guān)鍵點(diǎn)匹配結(jié)果統(tǒng)計(jì)表

4 結(jié)束語

本文提出一種SIFT改進(jìn)算法，該算法能夠?qū)崿F(xiàn)整體粗匹配，局部精匹配相結(jié)合的方式對關(guān)鍵點(diǎn)進(jìn)行匹配，提高了算法效率。由于SIFT算法中關(guān)鍵點(diǎn)描述子計(jì)算復(fù)雜，導(dǎo)致算法計(jì)算量大，耗時長。雖然本文對該算法進(jìn)行改進(jìn)，加快了算法效率，但計(jì)算時間依然較長。因此在今后的研究中希望分析出一種更為簡單的關(guān)鍵點(diǎn)描述子，從而提高算法的實(shí)時性和適用性。