一種改進的遙感圖像地標邊緣匹配方法

馮 斌，鄧新蒲，馬 超

FENG Bin,DENG Xinpu,MA Chao

國防科學技術大學 電子科學與工程學院，長沙410073

College of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China

1 引言

遙感圖像地標匹配是利用圖像匹配算法在遙感圖像中尋找與地標模板圖像相同或相似區域的過程。基于地標匹配的衛星圖像導航系統[1-2]、無人飛行器定位系統[3-6]主要采用圖像匹配技術來保證定位精度。楊磊、郭強等[1-2]對我國氣象衛星地標自動導航的方法進行了深入的研究，李耀軍、吉祥等[3-4]對無人飛行器定位的方法進行了詳細的研究；Mostafa 等[5-6]對基于特征的遙感圖像匹配技術在定位系統的應用進行了全面的研究。這些研究為遙感衛星自動導航、無人飛行器定位奠定了基礎。

文獻[7-11]對圖像匹配技術的原理、方法以及研究進展作了較為全面的分析和總結。文獻[8]中基于Hausdorff距離來進行邊緣圖像匹配的方法，是通過計算邊緣圖像邊緣點的Hausdorff 距離來衡量兩幅邊緣圖像的相似程度，具有較好的可靠性，但計算復雜。文獻[12]提出一種基于邊緣的相似距離（ESD）進行圖像匹配的方法，該方法的實質是統計兩邊緣圖像具有相同像素點的個數，具有較高的可靠性和魯棒性，但對邊緣提取精度要求較高。文獻[13]提出了改進的距離變換的圖像匹配方法，能使正確匹配位置的相關峰更顯著，但計算量大。

本文提出邊緣距離擴展和設置相似門限的距離變換方法，通過優化距離計算和區域搜索，減少了匹配計算時間，提高了算法匹配效率，與文獻[14]中傳統的距離變換算法以及文獻[13]中改進距離變換算法作比較實驗，結果表明本文算法在保證匹配精度的基礎上，計算時間有很大優勢。

2 地標邊緣匹配算法

2.1 基于距離變換的地標邊緣匹配算法

基于距離變換的地標邊緣匹配算法是以地標邊緣圖像邊緣點之間的距離測度作為相似性度量的一種匹配方法。

算法的基本原理：

（1）對地標模板圖像和遙感圖像進行邊緣檢測，轉化為二值的邊緣圖像。

（2）計算地標模板邊緣圖像上所有邊緣點到遙感邊緣圖像對應子圖的邊緣點的最小距離，并在當前搜索位置上記錄最小距離的值，其余非邊緣點位置值均為0，生成距離變換圖像。如圖1 所示，地標模板邊緣圖像1（b），計算其邊緣點到圖1（a）所示遙感邊緣圖像子圖中距其最近的邊緣點的距離，得到距離變換圖上相應位置的值，結果如圖1（c）所示。

圖1 距離變換圖生成示意圖

對于平移量(i,j)，記地標模板邊緣圖像I1上點p到遙感邊緣圖像的子圖I2上點q的最小距離為dij(p)，則有dij(p)=min{dij(p,q)}，其中p∈I1，q∈I2，dij(p,q)為在該平移量下p點和q點之間的距離（街區距離）。

（3）計算地標模板邊緣圖像上所有搜索位置上記錄值的算術平均值。

其中，N為地標模板邊緣圖像的邊緣點的數量，D(i,j)是相似性度量，表示匹配程度，D(i,j)的值越小，匹配度越高。

（4）在遙感邊緣圖像上遍歷，尋找最佳匹配位置，即

在D(i,j)取得最小值時匹配度最高，為最佳匹配位置。對于完全匹配的情況，即邊緣重合度最大時，D(i,j)趨于零或等于零。

2.2 算法性能分析

通過對算法基本原理分析可以得知，該算法存在求取最小距離值計算量大、重復冗余計算多和遍歷計算相似度量值效率低等問題[2]。

（1）求取最小距離值計算量大

dij(p,q)計算需要遍歷圖像I1和I2上的所有邊緣點才能求取最小距離值dij(p)，計算量大。以圖1 為例，地標模板I1邊緣點的數量為9，遙感邊緣圖像子圖I2的邊緣點數量為7，此時，遍歷兩圖像邊緣點的計算次數為9×7。地標模板邊緣圖像在遙感邊緣圖像上平移滑動的區域尺寸為4×4，那么，總的計算量為Z=4×4×9×n，其中0 ≤n≤25，n為遙感邊緣圖像子圖邊緣點的數量。由于地標模板邊緣點數量是確定的，遙感圖像和地標模板圖像的尺寸也是可以獲得的固定數據，遙感邊緣圖像子圖的邊緣點數量隨著平移量(i,j) 位置的變化而變化，因此，計算量隨著遙感邊緣圖像子圖邊緣點數量遞增而增加。如果地標模板與遙感邊緣圖像子圖的邊緣點數量和匹配搜索區域增加一個數量級，那么，計算量將會增加四個數量級數甚至更多，計算時間也相應快速增加。

（2）重復冗余計算多

對不同平移量(i,j)的最小距離值dij(p)計算過程中重復冗余計算多。以圖1 為例，當在平移位置(2,2)時，如圖1（a）所示，得到圖1（c）所示的距離變換圖。在平移位置(2,3)時得到圖2（a）所示的距離變換圖。對比兩幅距離變換圖可知，紅色位置的距離值，如圖2（b）所示，在圖1（c）所示的距離變換圖中已經得到，而此時需要重新計算。由于平移量的變化，使得相同位置的最小距離值重新計算，這些計算是重復冗余計算。因此，可以得出一個結論：當地標模板邊緣圖像在遙感邊緣圖像上平移滑動計算距離值時，某個像素點位置的最小距離值經過一次計算得到后是固定不變的。以圖1（a）為例，得到如圖2（c）所示距離變換圖。

圖2 分析圖

（3）遍歷計算相似度量值效率低

地標模板圖像在遙感邊緣圖像中平移滑動進行相似性度量值D(i,j)的計算時，地標模板對于所有可能的平移量(i,j)位置都需計算。以圖1 為例，假設當遙感邊緣圖像子圖處于如圖3（a）所示平移位置(4,4)時，子圖邊緣點的數量為3；如圖3（b）所示，地標模板邊緣點的數量為9。此時模板和子圖兩幅圖像邊緣點數量差別比較大，通過比較可以得出，兩幅圖像不匹配。在計算相似性度量值D(i,j)時，對于類似情況都進行了計算，由于無效的計算多，從而導致遍歷效率低。因此，為了提高效率，類似情況在遍歷搜索時可以排除，以此避免無效計算。

圖3 邊緣圖像對比圖

3 改進的地標邊緣匹配算法

3.1 算法性能優化

從以上算法性能分析知道，對算法進行優化主要從降低求取最小距離值的計算量，去除重復冗余計算和提高搜索效率方面來進行。

（1）計算量的優化

由2.2 節中分析得出結論：某個像素點位置的最小距離值經過一次計算得到后是固定不變的。因此，采用邊緣距離擴展的方法可以實現減少算法計算量和去除重復冗余計算的目的。由于地標模板一般為地理結構明顯且相對固定的圖像，因此，可以對地標模板邊緣圖像采用邊緣距離擴展的方法，預先計算出地標模板邊緣圖像上所有位置的最小距離值，即對地標模板邊緣圖像進行距離擴展至全圖像素點，從而生成邊緣距離擴展圖像，使最小距離值模板化。邊緣距離擴展圖像在遙感邊緣圖像上平移滑動，遙感邊緣圖像子圖上邊緣點所對應邊緣距離擴展圖像的值就是求取的最小距離值。以圖1為例，模板邊緣圖像經邊緣距離擴展后生成邊緣距離擴展圖，如圖4（a）所示，與圖1（a）子圖進行匹配時，不再需要計算最小距離值dij(p)，只需將子圖邊緣點位置與圖4（b）所對應位置的值相加求算術平均，即計算相似度量值D(i,j)。邊緣距離擴展的方法，不僅可以降低遍歷兩圖像邊緣點來計算最小距離值計算量大的問題，而且能去除不同平移量(i,j) 求取最小距離值的重復冗余計算，從而達到了減少計算量，提高計算速度的目的。

圖4 分析圖

（2）搜索效率的優化

采用設置相似門限的方法可以實現搜索的優化。通過2.2 節的算法性能分析（3）可知，在最佳匹配位置上，地標模板邊緣圖像上的邊緣點數量與遙感邊緣圖像子圖的邊緣點數量應該相差不大。基于這一思想，如果兩幅匹配圖像邊緣點的數量相差比較大，那么可以認為該位置為非匹配位置，則不必計算相似性度量值，直接予以剔除。因此，可以通過設定子圖邊緣點數量占地標模板邊緣點數量的比例來判斷兩圖像是否匹配，即設置子圖邊緣點數量與模板邊緣點數量的相似門限，對遙感邊緣圖像子圖中邊緣點數量過少或過多的位置予以剔除。通過設置相似門限，可以直接剔除遙感圖像上絕大部分的非匹配圖像點，從而縮小搜索范圍，提高搜索效率。

3.2 改進的距離變換匹配算法

改進算法的具體步驟：

（1）提取邊緣圖像。對地標模板圖像和遙感圖像進行邊緣檢測，轉化為二值的邊緣圖像。

（2）生成邊緣距離擴展圖像：

①對地標模板邊緣圖像進行邊緣擴展并相加，得到相加圖像。第一，對地標模板邊緣圖像，如圖5（a）所示，進行形態學膨脹[15]，結構元素如圖5（b）所示，得到一次膨脹圖像，如圖5（c）所示。第二，將一次膨脹圖像與地標模板邊緣圖像相加，得到一次相加圖像，如圖5（d）所示。第三，對一次膨脹圖像進行第二次形態學膨脹，得到二次膨脹圖像，如圖5（e）所示。第四，將二次膨脹圖像與一次相加圖像相加，得到二次相加圖像，如圖5（f）所示。依此類推，進行多次膨脹至距原邊緣點較遠位置停止，最后得到多次相加圖像。膨脹次數可依據需要進行設定。

②形成邊緣距離擴展圖像并賦值。選取多次相加圖像中的最大值（等于膨脹次數加1）形成最大值圖像，用其減去多次相加圖像，得到邊緣距離擴展圖像，如圖5（g）所示。為了加大遠距離邊緣點之間的非對應性，在邊緣距離擴展圖像的最大值處（即邊緣沒有膨脹到的位置）直接賦一個更大值，如圖5（h）所示。這樣，在邊緣距離擴展圖像中，離原邊緣點越近的值越小，越遠的值越大。

（3）對于平移量(i,j)計算相似性度量值D(i,j)。計算出遙感邊緣圖像(i,j)處子圖像中邊緣點的數量和地標模板邊緣圖像中邊緣點的數量。設置相似門限值，即子圖邊緣點數量占模板邊緣點數量的最小和最大比例，取大于最小比例和小于最大比例之間的子圖位置為搜索范圍。相似門限可根據需要設定。在比例系數范圍以外的區域剔除，直接賦予相似性度量值（相似性度量值的設置可依據邊緣未擴展區域賦值確定）。在搜索范圍以內的區域則計算匹配相似性度量值D(i,j)，即

其中，dij(g)為子圖邊緣點位置對應邊緣距離擴展圖位置的值，S為子圖邊緣點的數量，D(i,j)是相似性度量值，表示匹配程度，D(i,j)的值越小，匹配度越高。

（4）定位最佳匹配位置。在遙感邊緣圖像上遍歷搜索，尋找最佳匹配位置，即

在D(i,j)取得最小值時，邊緣圖像的匹配度最高，即為最佳匹配位置。

圖5 邊緣距離擴展圖像生成示意圖

4 實驗仿真及結果分析

為了驗證算法的性能進行了實驗仿真，仿真環境為MATLAB R2013a，主頻2.34 GHz。仿真實驗采用的遙感圖像選自某地區的MODIS 圖像，尺寸為512×512，如圖6（a）所示。為了驗證本文算法的有效性和2.2 節分析所得結論，選取三個不同尺寸大小的模板進行實驗仿真，三個模板圖像分別取自遙感圖像中的一部分：模板（I）位置為（448，45），尺寸為38×30；模板（II）位置為（225，84），尺寸為53×56；模板（III）位置為（434，244），尺寸為76×63，如圖6（b）所示。遙感圖像和模板圖像均采用Canny 算子提取邊緣[16]，轉化為二值的邊緣圖像。分別采用傳統的距離變換算法、改進的距離變換算法以及本文算法進行遙感圖像和模板圖像的匹配，得到的地標匹配時間如表1 所示。

圖6 實驗圖像

從表1 的實驗結果可以看出，三個不同的地標模板利用傳統距離變換算法進行匹配，匹配時間隨著模板尺寸的增大而快速增加，與2.2 節中分析的結論一致；利用改進的距離變換算法進行匹配，匹配時間不但快速增加，而且比傳統算法匹配時間還長；利用本文算法進行匹配，匹配時間只有傳統距離變換算法匹配時間的0.1%～0.5%，與3.1 節（1）中計算量優化所得結論相同，同時也可以看出本文算法匹配時間不會隨模板尺寸的增大而快速增加。結果表明，采用邊緣距離擴展的優化方法解決了算法計算量大的問題，驗證了本文算法對計算量優化的有效性。

表1 匹配時間對比表

圖7 是地標模板（III）的匹配結果，此時本文算法中參數的設置為：擴展次數為3，未擴展空白區賦為10，子圖邊緣點數量占地標模板邊緣點數量的最小和最大比例系數分別為0.5 和1.5，剔除的圖像點相似性度量值賦為10。從圖7（b）相似性度量值的空間分布可以看出，遙感圖像中的絕大部分非匹配圖像點（白色部分）被剔除在匹配搜索范圍以外，其所占的比例為70.29%，匹配搜索區域（灰色部分）不到原來搜索范圍的30%。結果表明，采用設置相似門限的方法可以有效地減少匹配搜索區域，提高匹配搜索效率，驗證了本文算法對搜索優化的有效性。

圖7 地標模板（III）匹配結果圖

圖8 是地標模板（III）分別利用三種算法匹配所得結果的相關曲面圖，圖中相關曲面的最高峰對應最佳匹配位置[13]。對比圖8（a）、（b）和（c）可以看出，傳統距離變換算法的相關曲面非常平緩，最高峰不明顯，改進距離變換算法的相關曲面最高峰比較明顯，本文算法的相關曲面最高峰位置明顯，相關峰尖銳，表明本文算法匹配定位精度很高。

圖8 地標模板（III）匹配結果相關曲面圖

仿真結果表明，本文提出的邊緣距離擴展和設置相似門限的距離變換算法在保證匹配精度的基礎上，大大減少了匹配的時間，實現了快速匹配，能滿足匹配的高時效性要求。

5 結束語

針對距離變換算法存在的問題，采用邊緣距離擴展和設置相似門限的方法解決了算法計算和搜索時間長的問題。通過將地標模板邊緣圖像進行距離擴展生成邊緣距離擴展圖像，從而解決了要遍歷兩圖像所有邊緣點來計算距離值以及其中重復冗余計算的問題。基于最佳匹配位置兩圖像邊緣點數量相差不大的基本思想，通過判斷子圖邊緣點數量占地標模板邊緣點數量比例的方法，直接剔除了遙感圖像上絕大部分的非匹配圖像點，從而縮小了搜索的范圍，解決了搜索效率低的問題。

最后，采用不同地標模板進行仿真實驗，將傳統的距離變換算法和本文算法作了對比。實驗結果表明，本文算法在計算時間上有很大程度的提升，能滿足圖像匹配的實時性要求。

[1] 楊磊，楊忠東.遙感衛星圖像自動導航方法研究[J].計算機工程與應用，2009，45（10）：204-207.

[2] 郭強，楊磊.氣象衛星圖像導航的地標匹配算法研究與優化[J].計算機工程與應用，2013，49（24）：152-156.

[3] 李耀軍.基于空間關系幾何約束的無人機景象匹配導航[J].計算機應用研究，2010，27（10）：3822-3835.

[4] 吉祥.基于景象匹配的無人飛行器定位方法[J].系統仿真學報，2014，26（6）：1291-1296.

[5] Cesetti A，Frontoni E，Mancini A，et al.Vision-based guidance system for UAV navigation and safe landing using natural landmarks[J].Journal of Intelligent & Robotic Systems，2010，57（1/4）：233-257.

[6] Mostafa K，Majid B，Ali P.UAV navigation based on PIIFD/INS method[J].International Journal of Computer Theory and Engineering，2012，4（2）：283-287.

[7] 王紅梅，張科，李言俊.圖像匹配研究進展[J].計算機工程與應用，2004，40（19）：42-45.

[8] 王鯤鵬，徐一丹，余起峰.紅外與可見光圖像配準方法分類及現狀[J].紅外技術，2009，31（5）：270-274.

[9] 汪漢云，王程.多源遙感圖像配準技術綜述[J].計算機工程，2011，37（19）：17-21.

[10] Zitova B，Flusser J.Image registration methods：a survey[J].Image Vision Computing，2003，21：977-l000.

[11] Brown L G.A survey of image registration[J].ACM Computing Surveys，l992（4）：325-376.

[12] 張志佳，黃莎白，史澤林.新的基于邊緣特征的圖像相關匹配方法[J].紅外與激光工程，2003，32（6）：365-368.

[13] 張衛煒.基于邊緣的紅外與可見光圖像匹配方法研究[D].長沙：國防科學技術大學，2010.

[14] 李偉.地面場景光學圖像輔助導航技術研究[D].長沙：國防科學技術大學，2008.

[15] 高展宏，徐文波.基于Matlab 的圖像處理案例教程[M].北京：清華大學出版社，2011：217-219.

[16] Nixon M S，Aguado A S.特征提取與圖像處理[M].2 版.李實英，楊高波，譯.北京：電子工業出版社，2013：92-109.