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

馮 斌，鄧新蒲，馬 超

FENG Bin,DENG Xinpu,MA Chao

國防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院，長沙410073

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

1 引言

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

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

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

2 地標邊緣匹配算法

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

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

算法的基本原理：

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

（2）計算地標模板邊緣圖像上所有邊緣點到遙感邊緣圖像對應(yīng)子圖的邊緣點的最小距離，并在當前搜索位置上記錄最小距離的值，其余非邊緣點位置值均為0，生成距離變換圖像。如圖1 所示，地標模板邊緣圖像1（b），計算其邊緣點到圖1（a）所示遙感邊緣圖像子圖中距其最近的邊緣點的距離，得到距離變換圖上相應(yīng)位置的值，結(jié)果如圖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點之間的距離（街區(qū)距離）。

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

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

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

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

2.2 算法性能分析

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

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

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

（2）重復(fù)冗余計算多

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

圖2 分析圖

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

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

圖3 邊緣圖像對比圖

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

3.1 算法性能優(yōu)化

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

（1）計算量的優(yōu)化

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

圖4 分析圖

（2）搜索效率的優(yōu)化

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

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

改進算法的具體步驟：

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

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

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

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

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

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

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

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

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

4 實驗仿真及結(jié)果分析

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

圖6 實驗圖像

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

表1 匹配時間對比表

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

圖7 地標模板（III）匹配結(jié)果圖

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

圖8 地標模板（III）匹配結(jié)果相關(guān)曲面圖

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

5 結(jié)束語

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

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

[1] 楊磊，楊忠東.遙感衛(wèi)星圖像自動導(dǎo)航方法研究[J].計算機工程與應(yīng)用，2009，45（10）：204-207.

[2] 郭強，楊磊.氣象衛(wèi)星圖像導(dǎo)航的地標匹配算法研究與優(yōu)化[J].計算機工程與應(yīng)用，2013，49（24）：152-156.

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

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

[5] Cesetti A，F(xiàn)rontoni 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].計算機工程與應(yīng)用，2004，40（19）：42-45.

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

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

[10] Zitova B，F(xiàn)lusser 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] 張志佳，黃莎白，史澤林.新的基于邊緣特征的圖像相關(guān)匹配方法[J].紅外與激光工程，2003，32（6）：365-368.

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

[14] 李偉.地面場景光學(xué)圖像輔助導(dǎo)航技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，2008.

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

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