基于圖像檢索與GPS定位相結合的地標識別系統

于嶺嶺，李 莉

（天津職業技術師范大學電子工程學院，天津 300222）

隨著無線網絡的發展和移動智能手機的普及，面向移動設備的地標識別成為當今學者們研究的熱點之一。地標識別的對象一般是標志性建筑物或自然物。用戶通過移動設備捕捉地標的視覺特征，便可獲取該地標背景知識及其周邊的商業信息、交通狀況、景點環境等相關信息[1]。徐祥振[2]提出了一種基于SIFT 算法的地標識別方法，通過尺度不變特征變換（scale-invariant feature transform，SIFT） 圖像匹配算法，完成對旅游景點的信息確認，但圖像匹配并不能完全準確。羅文城[3]根據慣性導航數據規劃建筑結構的路徑圖，實現慣性導航數據和圖像地標相結合的室內定位方法，但由于傳感器的限制，隨著時間的增加，海拔信息的精度將下降。孫亞麗[4]設計了基于多傳感器融合的室內地標識別系統，由于采集數據的傳感器設備可能存在硬件性偏差，會對分析造成細微的誤差。范音[5]提出了一種面向全景圖的地標識別方法，若拍攝的圖像間無重疊部分時，則無法實現有效拼接且易出現耗時長的問題。針對圖像匹配的優勢和不足，本文提出了一種使用圖像檢索與全球定位系統相結合的地標識別系統，旨在提高檢索正確率和縮短檢索時間，該研究采用加速穩健特征（speeded up robust features，SURF）算法對地標圖像進行特征匹配，采用隨機抽樣一致性（random sample consensus，RANSAC）算法對特征點進行提純，再次驗證其有效性。

1 地標識別匹配算法

在用于地標識別的匹配算法中，SIFT 算法首先由Lowe[6]于1999 年在計算機視覺國際會議上提出，2004年再次經Lowe[7]完善后發表。該算法對于光線、噪聲、微視角改變的容忍度很高，擁有大量信息，能夠在海量數據庫中快速準確地匹配。SURF算法由Bay 等[8]于2006 年提出，作為一種新興的特征提取方法，它在可重復性、唯一性和魯棒性方面接近或超越過去提出的類似方法，并在計算效率方面具有明顯的優勢。SURF算法的速度約為SIFT 算法的3 倍，檢測到的特征點數約為SIFT 算法的1/3。此外，SURF算法還與圖像大小、紋理復雜度和算法參數設置有關[9]。

SURF算法一般分4 步進行[10]，算法匹配基本步驟如圖1所示。

圖1 算法匹配基本步驟

1.1 尺度空間的建立

圖像的尺度空間可定義為原始圖像和可變尺度的二維高斯函數的卷積運算[11]。在計算機領域中，尺度空間被象征性地表述為一個圖像金字塔。其中，對于SIFT 算法的尺度空間建立，需要重復使用高斯函數對圖像進行平滑處理并且下一層圖像由上一層圖像降采樣得到，通過連續采樣，一層一層直到塔頂，因此在特征點檢測時運算量過大，消耗時間較長。而SURF算法是通過改變矩形濾波器的大小而不是改變圖像的大小來獲得尺度空間，同時使用積分圖像來加速卷積運算。SURF算法直接使用不同尺寸的濾波器，實現多層圖像同時被處理，從而減少時間，提高了運算速度。高斯金字塔如圖2所示，從圖2（a）中可知，SIFT 算法采用傳統方式建立位于金字塔結構，并且圖像的大小需要重置。

1.2 特征點提取

SURF算法在建立尺度空間之后，對于特定尺度圖像下的關鍵點提取是基于Hessian 矩陣實現的。圖像中像素點的Hessian 矩陣：

圖2 高斯金字塔

因為特征點要具備尺度無關性，所以先要經過高斯濾波再構造Hessian 矩陣。經過濾波后的Hessian矩陣為：

式中：Lxx（x，σ）、Lxy（x，σ）、Lyy（x，σ）分別為高斯濾波二階導數同I（x，y）卷積的結果

最后通過計算H 行列式的值判別特征點，為了方便應用，使用近似值代替。每個像素的Hessian 矩陣行列式的近似值為：

式中：Dxx，Dxy，Dyy為矩形濾波器同圖像卷積運算后的值；w 為權重系數，一般取0.9，其為平衡準確值與近似值的誤差而被引入。

1.3 特征描述子

SURF 中，在特征點的一個圓形區域中找到一個主方向，并且根據主方向選擇邊長為20 s（采樣步長取s）的正方形窗口區域[12]，然后將該區域分成16 個子區域，每個子區域計算5 s×5 s 范圍內的小波響應。因此，在每個子區域中形成四維分量的向量并且求出每個子區域的特征向量，形成4×4×4=64 維的描述向量。該64 維的描述向量即為構成特征點的SURF 描述子，對于SIFT 算法而言，其描述子是4×4×8=128 維的描述向量。

1.4 特征匹配

描述子生成后，將兩圖像中各個尺度的描述子進行歐氏距離計算，距離越短則匹配度越高，再根據Hessian 矩陣跡（矩陣特征值的和）的正負號是否相同判斷2 個特征點能否匹配。SIFT 算法與SURF算法基本類似，唯一不同的是SURF算法添加了Hessian 矩陣跡的判斷，優點是當2 個特征點歐氏距離為0 時，若它們的Hessian 矩陣跡的正負號不同，則這2 個特征點不能匹配。

1.4.1 RANSAC算法

由于兩圖像中不同的2 點的紋理屬性或顏色亮度相同而使得2 點的特征描述也很相似，進而導致了兩圖像之間出現大量誤匹配[13]。因此，本文中的特征匹配過程中結合了RANSAC 算法剔除誤匹配。RANSAC算法最早由Fischler 等[14]于1981 年提出，是一種魯棒性的參數估計方法。該算法可以接受金字塔構造過程中產生的圖像噪聲，且最大程度地剔除誤匹配點[15-16]。其原理是先隨機抽取觀測數據子集，假設所選取的子集是內點（即滿足估計參數的點），然后使用該內點擬合適合于假設內點的模型，通過不斷地迭代數據子集找到符合足夠多數據的模型。

RANSAC 算法從SURF算法預匹配的數據集中隨機刪除一些匹配點對，并計算變換矩陣H，記為模型M。然后計算模型M 與數據集中數據的投影誤差，如果誤差小于閾值，則加入內點集I。最后，判斷當前內點集I 是否大于最優內點集，若大于則更新最優內點集為I，同時更新迭代次數k。若此時得到的模型符合足夠多的數據，則退出；否則迭代次數增加1 并重復上述步驟。迭代次數k 計算式為：

式中：p 為置信度，一般取0.995；w 為內點個數與所有點的比例；m 為計算模型需要的樣本數，最小樣本數一般取4。

2 系統設計與實現

2.1 地標識別系統

地標識別系統主要分為用戶端和服務端兩大部分。用戶端部分主要是圖像采集與獲取定位結果，在圖像采集過程中移動設備的GPS 服務需要處于開啟狀態。服務端部分包括數據庫模塊、位置信息提取模塊、特征提取模塊和地標識別匹配模塊。數據庫模塊用于存儲數據集的數據信息，供查詢使用；位置信息提取模塊的作用是提取圖像位置信息為數據庫模塊實現基于位置信息的初步篩選；特征提取模塊是提取圖像的特征；地標識別匹配模塊將候選圖像與查詢圖像進行特征匹配，最后通過特征點數量的多少判定匹配的結果，將結果輸出。地標識別系統結構如圖3所示。

圖3 地標識別系統結構

2.2 系統實驗

移動設備在拍攝圖像時通過內部GPS 定位獲取信息。該系統實驗的圖像數據來源于OPPO 手機拍攝的天津職業技術師范大學的建筑物，共有4 個不同的地標收集圖像數據集。取其中30 幅圖像作為數據庫圖像，剩余的16 幅圖像視為查詢圖像。數據庫中的地標位置信息使用的是谷歌地球上的定位位置。

本系統實驗的查詢圖像利用SURF算法和RANSAC 算法與經過位置信息篩選的候選圖像進行匹配。對于匹配準確度而言，采用內部測試的方法，即將數據庫里的圖像逐一與其余的圖像進行匹配查詢，并將其結果視為本系統的準確度。選取的4 個建筑物的相對位置如圖4所示。

圖4 4個建筑物的相對位置

2.3 實驗結果與分析

2.3.1 RANSAC提純

SURF算法特征點匹配結果如圖5所示。相應地，RANSAC 算法提純的最優匹配結果如圖6所示。從圖6 中能夠看出，提純后匹配點數明顯減少，提純的效果比較可觀，剔除了誤匹配。

圖5 SURF算法特征點匹配結果

圖6 RANSAC 算法提純的最優匹配結果

2.3.2 不同因素影響下的圖像匹配

不同因素影響的圖片匹配效果對比如圖7所示。SURF算法針對圖片的平移、旋轉、光度變化做了測試，通過測試驗證了SURF算法不會因為照片拍攝的不良因素對檢測結果造成較大的影響。

2.3.3 檢測精確度與時間

本文測試數據集的內部準確性，精度對比結果如表1所示。SIFT 算法、SURF算法分別在無GPS 位置信息與結合GPS 位置信息的情況下進行測試。

圖7 不同因素影響的圖片匹配效果對比

表1 精度對比結果

從表1 中可以看出，SURF算法在有GPS 位置信息的判別下，得到的識別精度比無GPS 位置信息精準，精度可高達96.67%。SIFT 算法同SURF算法一樣，在無GPS 位置信息的輔助下識別精度比較差，結合GPS 位置信息后，其精度也達到96.67%。還可觀察到SURF算法識別的準確率很大程度上依賴GPS 位置信息的輔助，才能達到理想效果。實驗中發現，因為學校建筑物較為集中，某些建筑物的距離很近，在某些位置有多于1 個建筑物的GPS 信息且都在計算的距離差值之內，則只對距離差值最小的前3 個建筑物進行圖像匹配識別，并最終選取匹配點數最多的建筑物為結果。此外，校園中樹木、高樓等遮擋比較多的地方，GPS 信號比較弱，初始定位誤差較大，導致SURF算法無法實現匹配；遇到植物較多、圖像復雜的情況，則定位結果主要依賴GPS，如果此時GPS 信號也弱，則無法實現正確匹配。

對于檢測時間而言，將同一圖片在不同的條件下進行檢測，每個條件下分別測試了500 次并對獲得的檢測時間結果求平均值，測試時間對比如表2所示。

表2 測試時間對比

從表2 中可以看出，SURF算法結合GPS 位置信息篩選候選圖像在一定程度上提高了算法時間效率，但SIFT 算法如預期一樣消耗時間最長。實驗表明，與圖像特征提取SIFT 算法相比，SURF算法在時間效率上有了很大的提高，并且在結合GPS 位置信息后檢測時間進一步縮短。對一幅480×640 的建筑物圖片分別用SURF算法和SIFT 算法檢測，在執行時間上相差3～4 倍，這與SURF算法采用了Haar 小波響應和積分圖像的概念有很大的關系。

3 結 語

本文提出了一種基于圖像檢索與GPS 定位相結合的地標識別系統。通過實驗驗證了結合GPS 定位信息對地標圖像匹配精度提高明顯，以及SURF算法結合GPS 位置信息識別地標過程在時間上的優勢。后續將針對地標識別算法做更進一步的優化研究，使系統運行時間更快，精度更高并能完成手機端的系統設計，然后運用公共數據庫對其進行驗證。