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

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

0 引言

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

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

1 算法設(shè)計

1.1 SIFT算法簡介

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

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

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

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

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

1.2 圖像直方圖分析

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

圖1 影像直方圖

1.3 二次多項式擬合直方圖

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

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

圖2 二次多項式擬合

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

y=a0+a1x+a2x2

(1)

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

1.4 標準差

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

(2)

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

1.5 系數(shù)分析

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

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

(3)

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

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

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

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

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

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

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

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

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

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

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

圖8 初步篩選散點圖

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

y=0.172 5×x-0.129

(4)

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

2 算法模型

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

圖9 算法流程圖

具體步驟如下：

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

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

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

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

3 實驗與分析

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

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

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

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

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

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

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

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

4 結(jié)束語

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