多項(xiàng)式擬合的尺度不變特征變換改進(jìn)算法

薛理，楊樹(shù)文，馬吉晶，劉燕

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

0 引言

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

然而，上述改進(jìn)算法多以照片為研究對(duì)象，針對(duì)高分辨率遙感影像的研究較少，二者之間在算法精度和效率上存在較大差異。由此，作者通過(guò)實(shí)驗(yàn)對(duì)比分析，發(fā)現(xiàn)采用二次多項(xiàng)式能夠較為理想地?cái)M合影像直方圖；對(duì)關(guān)鍵點(diǎn)進(jìn)行初步篩選時(shí)，單一系數(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算法簡(jiǎn)介

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

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

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

為了使描述符具有旋轉(zhuǎn)不變形，需要給每個(gè)關(guān)鍵點(diǎn)分配一個(gè)局部方向。首先，統(tǒng)計(jì)關(guān)鍵點(diǎn)領(lǐng)域窗口內(nèi)的像素值梯度和方向[20]。由于距離關(guān)鍵點(diǎn)越遠(yuǎn)的像素，對(duì)關(guān)鍵點(diǎn)的影響越小，因此需要對(duì)梯度進(jìn)行高斯加權(quán)。其次，將0～360°平均分成36 分，每份10°，生成方向直方圖，以直方圖最大值為關(guān)鍵點(diǎn)的主方向。同時(shí)為了增加算法的魯棒性，保留主方向峰值的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)周?chē)?×8 窗口區(qū)域，將該區(qū)域分為4×4 個(gè)子區(qū)域，計(jì)算每個(gè)子區(qū)域8 個(gè)方向的梯度，共128 維向量。最后，為了去除光照變化的影響，需要對(duì)128 維向量進(jìn)行歸一化處理。

1.2 圖像直方圖分析

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

圖1 影像直方圖

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

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

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

圖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)個(gè)體間的離散程度，因此，利用標(biāo)準(zhǔn)差可以反映遙感圖像像素值的整體離散特性。標(biāo)準(zhǔn)差的計(jì)算公式為：

(2)

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

1.5 系數(shù)分析

1)系數(shù)選取。通過(guò)上述分析發(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)差對(duì)圖像B中所有關(guān)鍵點(diǎn)進(jìn)行初步篩選，然后，再用關(guān)鍵點(diǎn)128 維向量進(jìn)行匹配。

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

(3)

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

圖3至圖6中時(shí)間比代表關(guān)鍵點(diǎn)初步篩選后的算法時(shí)間與SIFT算法時(shí)間的比值，預(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é)果

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

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

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

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

根據(jù)上述標(biāo)準(zhǔn)對(duì)圖7中的圖像進(jìn)行匹配。對(duì)匹配結(jié)果進(jìn)行分析，發(fā)現(xiàn)初步篩選關(guān)鍵點(diǎn)占比與圖像B關(guān)鍵點(diǎn)數(shù)量的相關(guān)性較為明顯，因此對(duì)初步篩選關(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)，擬合曲線(xiàn)如圖中紅線(xià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ù)對(duì)原圖像A和B進(jìn)行模糊，生成高斯金字塔。然后每層金字塔相鄰圖像相減生成高斯差分金字塔；

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

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

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

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

實(shí)驗(yàn)選取位于甘肅省蘭州市的GF-1影像，影像大小為800 像素×600 像素，如圖10(a)所示。對(duì)該影像進(jìn)行平移、旋轉(zhuǎn)、縮放和模糊處理，處理結(jié)果如圖10(b)所示。采用文獻(xiàn)[12]提出的SIFT算法和論文改進(jìn)算法對(duì)圖像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)證算法的魯棒性，本文又分別對(duì)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)確率和算法時(shí)間，如表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)算法時(shí)間與SIFT算法時(shí)間的比值分別為0.551和0.565。

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

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

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

4 結(jié)束語(yǔ)

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