多項式擬合的尺度不變特征變換改進算法

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

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

0 引言

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

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

1 算法設計

1.1 SIFT算法簡介

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

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

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

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

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

1.2 圖像直方圖分析

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

圖1 影像直方圖

1.3 二次多項式擬合直方圖

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

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

圖2 二次多項式擬合

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

y=a0+a1x+a2x2

(1)

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

1.4 標準差

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

(2)

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

1.5 系數分析

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

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

(3)

式中：C代表正確匹配率；cm代表正確匹配的關鍵點數量；fm代表錯誤匹配的關鍵點數量。

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

圖3 平移匹配結果

圖4 旋轉匹配結果

圖5 縮放匹配結果

圖6 模糊匹配結果

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

綜上所述，采用單一系數a2對關鍵點進行初步篩選較為合適。

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

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

根據上述標準對圖7中的圖像進行匹配。對匹配結果進行分析，發現初步篩選關鍵點占比與圖像B關鍵點數量的相關性較為明顯，因此對初步篩選關鍵點占比與圖像B關鍵點總數進行統計，生成散點圖，如圖8所示。

圖8 初步篩選散點圖

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

y=0.172 5×x-0.129

(4)

式中：x代表圖像B關鍵點的數量;y代表初步篩選關鍵點占比。

2 算法模型

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

圖9 算法流程圖

具體步驟如下：

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

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

③統計高斯金字塔中每個關鍵點周圍領域窗口的像素值，生成直方圖，并利用二次函數進行擬合，獲得系數a2；

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

3 實驗與分析

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

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

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

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

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

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

圖10 GF-1影像匹配結果

表1 關鍵點匹配結果統計表

4 結束語

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