馮 斌,鄧新蒲,馬 超
FENG Bin,DENG Xinpu,MA Chao
國(guó)防科學(xué)技術(shù)大學(xué) 電子科學(xué)與工程學(xué)院,長(zhǎng)沙410073
College of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China
遙感圖像地標(biāo)匹配是利用圖像匹配算法在遙感圖像中尋找與地標(biāo)模板圖像相同或相似區(qū)域的過程?;诘貥?biāo)匹配的衛(wèi)星圖像導(dǎo)航系統(tǒng)[1-2]、無(wú)人飛行器定位系統(tǒng)[3-6]主要采用圖像匹配技術(shù)來(lái)保證定位精度。楊磊、郭強(qiáng)等[1-2]對(duì)我國(guó)氣象衛(wèi)星地標(biāo)自動(dòng)導(dǎo)航的方法進(jìn)行了深入的研究,李耀軍、吉祥等[3-4]對(duì)無(wú)人飛行器定位的方法進(jìn)行了詳細(xì)的研究;Mostafa 等[5-6]對(duì)基于特征的遙感圖像匹配技術(shù)在定位系統(tǒng)的應(yīng)用進(jìn)行了全面的研究。這些研究為遙感衛(wèi)星自動(dòng)導(dǎo)航、無(wú)人飛行器定位奠定了基礎(chǔ)。
文獻(xiàn)[7-11]對(duì)圖像匹配技術(shù)的原理、方法以及研究進(jìn)展作了較為全面的分析和總結(jié)。文獻(xiàn)[8]中基于Hausdorff距離來(lái)進(jìn)行邊緣圖像匹配的方法,是通過計(jì)算邊緣圖像邊緣點(diǎn)的Hausdorff 距離來(lái)衡量?jī)煞吘増D像的相似程度,具有較好的可靠性,但計(jì)算復(fù)雜。文獻(xiàn)[12]提出一種基于邊緣的相似距離(ESD)進(jìn)行圖像匹配的方法,該方法的實(shí)質(zhì)是統(tǒng)計(jì)兩邊緣圖像具有相同像素點(diǎn)的個(gè)數(shù),具有較高的可靠性和魯棒性,但對(duì)邊緣提取精度要求較高。文獻(xiàn)[13]提出了改進(jìn)的距離變換的圖像匹配方法,能使正確匹配位置的相關(guān)峰更顯著,但計(jì)算量大。
本文提出邊緣距離擴(kuò)展和設(shè)置相似門限的距離變換方法,通過優(yōu)化距離計(jì)算和區(qū)域搜索,減少了匹配計(jì)算時(shí)間,提高了算法匹配效率,與文獻(xiàn)[14]中傳統(tǒng)的距離變換算法以及文獻(xiàn)[13]中改進(jìn)距離變換算法作比較實(shí)驗(yàn),結(jié)果表明本文算法在保證匹配精度的基礎(chǔ)上,計(jì)算時(shí)間有很大優(yōu)勢(shì)。
基于距離變換的地標(biāo)邊緣匹配算法是以地標(biāo)邊緣圖像邊緣點(diǎn)之間的距離測(cè)度作為相似性度量的一種匹配方法。
算法的基本原理:
(1)對(duì)地標(biāo)模板圖像和遙感圖像進(jìn)行邊緣檢測(cè),轉(zhuǎn)化為二值的邊緣圖像。
(2)計(jì)算地標(biāo)模板邊緣圖像上所有邊緣點(diǎn)到遙感邊緣圖像對(duì)應(yīng)子圖的邊緣點(diǎn)的最小距離,并在當(dāng)前搜索位置上記錄最小距離的值,其余非邊緣點(diǎn)位置值均為0,生成距離變換圖像。如圖1 所示,地標(biāo)模板邊緣圖像1(b),計(jì)算其邊緣點(diǎn)到圖1(a)所示遙感邊緣圖像子圖中距其最近的邊緣點(diǎn)的距離,得到距離變換圖上相應(yīng)位置的值,結(jié)果如圖1(c)所示。
圖1 距離變換圖生成示意圖
對(duì)于平移量(i,j),記地標(biāo)模板邊緣圖像I1上點(diǎn)p到遙感邊緣圖像的子圖I2上點(diǎn)q的最小距離為dij(p),則有dij(p)=min{dij(p,q)},其中p∈I1,q∈I2,dij(p,q)為在該平移量下p點(diǎn)和q點(diǎn)之間的距離(街區(qū)距離)。
(3)計(jì)算地標(biāo)模板邊緣圖像上所有搜索位置上記錄值的算術(shù)平均值。
其中,N為地標(biāo)模板邊緣圖像的邊緣點(diǎn)的數(shù)量,D(i,j)是相似性度量,表示匹配程度,D(i,j)的值越小,匹配度越高。
(4)在遙感邊緣圖像上遍歷,尋找最佳匹配位置,即
在D(i,j)取得最小值時(shí)匹配度最高,為最佳匹配位置。對(duì)于完全匹配的情況,即邊緣重合度最大時(shí),D(i,j)趨于零或等于零。
通過對(duì)算法基本原理分析可以得知,該算法存在求取最小距離值計(jì)算量大、重復(fù)冗余計(jì)算多和遍歷計(jì)算相似度量值效率低等問題[2]。
(1)求取最小距離值計(jì)算量大
dij(p,q)計(jì)算需要遍歷圖像I1和I2上的所有邊緣點(diǎn)才能求取最小距離值dij(p),計(jì)算量大。以圖1 為例,地標(biāo)模板I1邊緣點(diǎn)的數(shù)量為9,遙感邊緣圖像子圖I2的邊緣點(diǎn)數(shù)量為7,此時(shí),遍歷兩圖像邊緣點(diǎn)的計(jì)算次數(shù)為9×7。地標(biāo)模板邊緣圖像在遙感邊緣圖像上平移滑動(dòng)的區(qū)域尺寸為4×4,那么,總的計(jì)算量為Z=4×4×9×n,其中0 ≤n≤25,n為遙感邊緣圖像子圖邊緣點(diǎn)的數(shù)量。由于地標(biāo)模板邊緣點(diǎn)數(shù)量是確定的,遙感圖像和地標(biāo)模板圖像的尺寸也是可以獲得的固定數(shù)據(jù),遙感邊緣圖像子圖的邊緣點(diǎn)數(shù)量隨著平移量(i,j) 位置的變化而變化,因此,計(jì)算量隨著遙感邊緣圖像子圖邊緣點(diǎn)數(shù)量遞增而增加。如果地標(biāo)模板與遙感邊緣圖像子圖的邊緣點(diǎn)數(shù)量和匹配搜索區(qū)域增加一個(gè)數(shù)量級(jí),那么,計(jì)算量將會(huì)增加四個(gè)數(shù)量級(jí)數(shù)甚至更多,計(jì)算時(shí)間也相應(yīng)快速增加。
(2)重復(fù)冗余計(jì)算多
對(duì)不同平移量(i,j)的最小距離值dij(p)計(jì)算過程中重復(fù)冗余計(jì)算多。以圖1 為例,當(dāng)在平移位置(2,2)時(shí),如圖1(a)所示,得到圖1(c)所示的距離變換圖。在平移位置(2,3)時(shí)得到圖2(a)所示的距離變換圖。對(duì)比兩幅距離變換圖可知,紅色位置的距離值,如圖2(b)所示,在圖1(c)所示的距離變換圖中已經(jīng)得到,而此時(shí)需要重新計(jì)算。由于平移量的變化,使得相同位置的最小距離值重新計(jì)算,這些計(jì)算是重復(fù)冗余計(jì)算。因此,可以得出一個(gè)結(jié)論:當(dāng)?shù)貥?biāo)模板邊緣圖像在遙感邊緣圖像上平移滑動(dòng)計(jì)算距離值時(shí),某個(gè)像素點(diǎn)位置的最小距離值經(jīng)過一次計(jì)算得到后是固定不變的。以圖1(a)為例,得到如圖2(c)所示距離變換圖。
圖2 分析圖
(3)遍歷計(jì)算相似度量值效率低
地標(biāo)模板圖像在遙感邊緣圖像中平移滑動(dòng)進(jìn)行相似性度量值D(i,j)的計(jì)算時(shí),地標(biāo)模板對(duì)于所有可能的平移量(i,j)位置都需計(jì)算。以圖1 為例,假設(shè)當(dāng)遙感邊緣圖像子圖處于如圖3(a)所示平移位置(4,4)時(shí),子圖邊緣點(diǎn)的數(shù)量為3;如圖3(b)所示,地標(biāo)模板邊緣點(diǎn)的數(shù)量為9。此時(shí)模板和子圖兩幅圖像邊緣點(diǎn)數(shù)量差別比較大,通過比較可以得出,兩幅圖像不匹配。在計(jì)算相似性度量值D(i,j)時(shí),對(duì)于類似情況都進(jìn)行了計(jì)算,由于無(wú)效的計(jì)算多,從而導(dǎo)致遍歷效率低。因此,為了提高效率,類似情況在遍歷搜索時(shí)可以排除,以此避免無(wú)效計(jì)算。
圖3 邊緣圖像對(duì)比圖
從以上算法性能分析知道,對(duì)算法進(jìn)行優(yōu)化主要從降低求取最小距離值的計(jì)算量,去除重復(fù)冗余計(jì)算和提高搜索效率方面來(lái)進(jìn)行。
(1)計(jì)算量的優(yōu)化
由2.2 節(jié)中分析得出結(jié)論:某個(gè)像素點(diǎn)位置的最小距離值經(jīng)過一次計(jì)算得到后是固定不變的。因此,采用邊緣距離擴(kuò)展的方法可以實(shí)現(xiàn)減少算法計(jì)算量和去除重復(fù)冗余計(jì)算的目的。由于地標(biāo)模板一般為地理結(jié)構(gòu)明顯且相對(duì)固定的圖像,因此,可以對(duì)地標(biāo)模板邊緣圖像采用邊緣距離擴(kuò)展的方法,預(yù)先計(jì)算出地標(biāo)模板邊緣圖像上所有位置的最小距離值,即對(duì)地標(biāo)模板邊緣圖像進(jìn)行距離擴(kuò)展至全圖像素點(diǎn),從而生成邊緣距離擴(kuò)展圖像,使最小距離值模板化。邊緣距離擴(kuò)展圖像在遙感邊緣圖像上平移滑動(dòng),遙感邊緣圖像子圖上邊緣點(diǎn)所對(duì)應(yīng)邊緣距離擴(kuò)展圖像的值就是求取的最小距離值。以圖1為例,模板邊緣圖像經(jīng)邊緣距離擴(kuò)展后生成邊緣距離擴(kuò)展圖,如圖4(a)所示,與圖1(a)子圖進(jìn)行匹配時(shí),不再需要計(jì)算最小距離值dij(p),只需將子圖邊緣點(diǎn)位置與圖4(b)所對(duì)應(yīng)位置的值相加求算術(shù)平均,即計(jì)算相似度量值D(i,j)。邊緣距離擴(kuò)展的方法,不僅可以降低遍歷兩圖像邊緣點(diǎn)來(lái)計(jì)算最小距離值計(jì)算量大的問題,而且能去除不同平移量(i,j) 求取最小距離值的重復(fù)冗余計(jì)算,從而達(dá)到了減少計(jì)算量,提高計(jì)算速度的目的。
圖4 分析圖
(2)搜索效率的優(yōu)化
采用設(shè)置相似門限的方法可以實(shí)現(xiàn)搜索的優(yōu)化。通過2.2 節(jié)的算法性能分析(3)可知,在最佳匹配位置上,地標(biāo)模板邊緣圖像上的邊緣點(diǎn)數(shù)量與遙感邊緣圖像子圖的邊緣點(diǎn)數(shù)量應(yīng)該相差不大?;谶@一思想,如果兩幅匹配圖像邊緣點(diǎn)的數(shù)量相差比較大,那么可以認(rèn)為該位置為非匹配位置,則不必計(jì)算相似性度量值,直接予以剔除。因此,可以通過設(shè)定子圖邊緣點(diǎn)數(shù)量占地標(biāo)模板邊緣點(diǎn)數(shù)量的比例來(lái)判斷兩圖像是否匹配,即設(shè)置子圖邊緣點(diǎn)數(shù)量與模板邊緣點(diǎn)數(shù)量的相似門限,對(duì)遙感邊緣圖像子圖中邊緣點(diǎn)數(shù)量過少或過多的位置予以剔除。通過設(shè)置相似門限,可以直接剔除遙感圖像上絕大部分的非匹配圖像點(diǎn),從而縮小搜索范圍,提高搜索效率。
改進(jìn)算法的具體步驟:
(1)提取邊緣圖像。對(duì)地標(biāo)模板圖像和遙感圖像進(jìn)行邊緣檢測(cè),轉(zhuǎn)化為二值的邊緣圖像。
(2)生成邊緣距離擴(kuò)展圖像:
①對(duì)地標(biāo)模板邊緣圖像進(jìn)行邊緣擴(kuò)展并相加,得到相加圖像。第一,對(duì)地標(biāo)模板邊緣圖像,如圖5(a)所示,進(jìn)行形態(tài)學(xué)膨脹[15],結(jié)構(gòu)元素如圖5(b)所示,得到一次膨脹圖像,如圖5(c)所示。第二,將一次膨脹圖像與地標(biāo)模板邊緣圖像相加,得到一次相加圖像,如圖5(d)所示。第三,對(duì)一次膨脹圖像進(jìn)行第二次形態(tài)學(xué)膨脹,得到二次膨脹圖像,如圖5(e)所示。第四,將二次膨脹圖像與一次相加圖像相加,得到二次相加圖像,如圖5(f)所示。依此類推,進(jìn)行多次膨脹至距原邊緣點(diǎn)較遠(yuǎn)位置停止,最后得到多次相加圖像。膨脹次數(shù)可依據(jù)需要進(jìn)行設(shè)定。
②形成邊緣距離擴(kuò)展圖像并賦值。選取多次相加圖像中的最大值(等于膨脹次數(shù)加1)形成最大值圖像,用其減去多次相加圖像,得到邊緣距離擴(kuò)展圖像,如圖5(g)所示。為了加大遠(yuǎn)距離邊緣點(diǎn)之間的非對(duì)應(yīng)性,在邊緣距離擴(kuò)展圖像的最大值處(即邊緣沒有膨脹到的位置)直接賦一個(gè)更大值,如圖5(h)所示。這樣,在邊緣距離擴(kuò)展圖像中,離原邊緣點(diǎn)越近的值越小,越遠(yuǎn)的值越大。
(3)對(duì)于平移量(i,j)計(jì)算相似性度量值D(i,j)。計(jì)算出遙感邊緣圖像(i,j)處子圖像中邊緣點(diǎn)的數(shù)量和地標(biāo)模板邊緣圖像中邊緣點(diǎn)的數(shù)量。設(shè)置相似門限值,即子圖邊緣點(diǎn)數(shù)量占模板邊緣點(diǎn)數(shù)量的最小和最大比例,取大于最小比例和小于最大比例之間的子圖位置為搜索范圍。相似門限可根據(jù)需要設(shè)定。在比例系數(shù)范圍以外的區(qū)域剔除,直接賦予相似性度量值(相似性度量值的設(shè)置可依據(jù)邊緣未擴(kuò)展區(qū)域賦值確定)。在搜索范圍以內(nèi)的區(qū)域則計(jì)算匹配相似性度量值D(i,j),即
其中,dij(g)為子圖邊緣點(diǎn)位置對(duì)應(yīng)邊緣距離擴(kuò)展圖位置的值,S為子圖邊緣點(diǎn)的數(shù)量,D(i,j)是相似性度量值,表示匹配程度,D(i,j)的值越小,匹配度越高。
(4)定位最佳匹配位置。在遙感邊緣圖像上遍歷搜索,尋找最佳匹配位置,即
在D(i,j)取得最小值時(shí),邊緣圖像的匹配度最高,即為最佳匹配位置。
圖5 邊緣距離擴(kuò)展圖像生成示意圖
為了驗(yàn)證算法的性能進(jìn)行了實(shí)驗(yàn)仿真,仿真環(huán)境為MATLAB R2013a,主頻2.34 GHz。仿真實(shí)驗(yàn)采用的遙感圖像選自某地區(qū)的MODIS 圖像,尺寸為512×512,如圖6(a)所示。為了驗(yàn)證本文算法的有效性和2.2 節(jié)分析所得結(jié)論,選取三個(gè)不同尺寸大小的模板進(jìn)行實(shí)驗(yàn)仿真,三個(gè)模板圖像分別取自遙感圖像中的一部分:模板(I)位置為(448,45),尺寸為38×30;模板(II)位置為(225,84),尺寸為53×56;模板(III)位置為(434,244),尺寸為76×63,如圖6(b)所示。遙感圖像和模板圖像均采用Canny 算子提取邊緣[16],轉(zhuǎn)化為二值的邊緣圖像。分別采用傳統(tǒng)的距離變換算法、改進(jìn)的距離變換算法以及本文算法進(jìn)行遙感圖像和模板圖像的匹配,得到的地標(biāo)匹配時(shí)間如表1 所示。
圖6 實(shí)驗(yàn)圖像
從表1 的實(shí)驗(yàn)結(jié)果可以看出,三個(gè)不同的地標(biāo)模板利用傳統(tǒng)距離變換算法進(jìn)行匹配,匹配時(shí)間隨著模板尺寸的增大而快速增加,與2.2 節(jié)中分析的結(jié)論一致;利用改進(jìn)的距離變換算法進(jìn)行匹配,匹配時(shí)間不但快速增加,而且比傳統(tǒng)算法匹配時(shí)間還長(zhǎng);利用本文算法進(jìn)行匹配,匹配時(shí)間只有傳統(tǒng)距離變換算法匹配時(shí)間的0.1%~0.5%,與3.1 節(jié)(1)中計(jì)算量?jī)?yōu)化所得結(jié)論相同,同時(shí)也可以看出本文算法匹配時(shí)間不會(huì)隨模板尺寸的增大而快速增加。結(jié)果表明,采用邊緣距離擴(kuò)展的優(yōu)化方法解決了算法計(jì)算量大的問題,驗(yàn)證了本文算法對(duì)計(jì)算量?jī)?yōu)化的有效性。
表1 匹配時(shí)間對(duì)比表
圖7 是地標(biāo)模板(III)的匹配結(jié)果,此時(shí)本文算法中參數(shù)的設(shè)置為:擴(kuò)展次數(shù)為3,未擴(kuò)展空白區(qū)賦為10,子圖邊緣點(diǎn)數(shù)量占地標(biāo)模板邊緣點(diǎn)數(shù)量的最小和最大比例系數(shù)分別為0.5 和1.5,剔除的圖像點(diǎn)相似性度量值賦為10。從圖7(b)相似性度量值的空間分布可以看出,遙感圖像中的絕大部分非匹配圖像點(diǎn)(白色部分)被剔除在匹配搜索范圍以外,其所占的比例為70.29%,匹配搜索區(qū)域(灰色部分)不到原來(lái)搜索范圍的30%。結(jié)果表明,采用設(shè)置相似門限的方法可以有效地減少匹配搜索區(qū)域,提高匹配搜索效率,驗(yàn)證了本文算法對(duì)搜索優(yōu)化的有效性。
圖7 地標(biāo)模板(III)匹配結(jié)果圖
圖8 是地標(biāo)模板(III)分別利用三種算法匹配所得結(jié)果的相關(guān)曲面圖,圖中相關(guān)曲面的最高峰對(duì)應(yīng)最佳匹配位置[13]。對(duì)比圖8(a)、(b)和(c)可以看出,傳統(tǒng)距離變換算法的相關(guān)曲面非常平緩,最高峰不明顯,改進(jìn)距離變換算法的相關(guān)曲面最高峰比較明顯,本文算法的相關(guān)曲面最高峰位置明顯,相關(guān)峰尖銳,表明本文算法匹配定位精度很高。
圖8 地標(biāo)模板(III)匹配結(jié)果相關(guān)曲面圖
仿真結(jié)果表明,本文提出的邊緣距離擴(kuò)展和設(shè)置相似門限的距離變換算法在保證匹配精度的基礎(chǔ)上,大大減少了匹配的時(shí)間,實(shí)現(xiàn)了快速匹配,能滿足匹配的高時(shí)效性要求。
針對(duì)距離變換算法存在的問題,采用邊緣距離擴(kuò)展和設(shè)置相似門限的方法解決了算法計(jì)算和搜索時(shí)間長(zhǎng)的問題。通過將地標(biāo)模板邊緣圖像進(jìn)行距離擴(kuò)展生成邊緣距離擴(kuò)展圖像,從而解決了要遍歷兩圖像所有邊緣點(diǎn)來(lái)計(jì)算距離值以及其中重復(fù)冗余計(jì)算的問題?;谧罴哑ヅ湮恢脙蓤D像邊緣點(diǎn)數(shù)量相差不大的基本思想,通過判斷子圖邊緣點(diǎn)數(shù)量占地標(biāo)模板邊緣點(diǎn)數(shù)量比例的方法,直接剔除了遙感圖像上絕大部分的非匹配圖像點(diǎn),從而縮小了搜索的范圍,解決了搜索效率低的問題。
最后,采用不同地標(biāo)模板進(jìn)行仿真實(shí)驗(yàn),將傳統(tǒng)的距離變換算法和本文算法作了對(duì)比。實(shí)驗(yàn)結(jié)果表明,本文算法在計(jì)算時(shí)間上有很大程度的提升,能滿足圖像匹配的實(shí)時(shí)性要求。
[1] 楊磊,楊忠東.遙感衛(wèi)星圖像自動(dòng)導(dǎo)航方法研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(10):204-207.
[2] 郭強(qiáng),楊磊.氣象衛(wèi)星圖像導(dǎo)航的地標(biāo)匹配算法研究與優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(24):152-156.
[3] 李耀軍.基于空間關(guān)系幾何約束的無(wú)人機(jī)景象匹配導(dǎo)航[J].計(jì)算機(jī)應(yīng)用研究,2010,27(10):3822-3835.
[4] 吉祥.基于景象匹配的無(wú)人飛行器定位方法[J].系統(tǒng)仿真學(xué)報(bào),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ìn)展[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(19):42-45.
[8] 王鯤鵬,徐一丹,余起峰.紅外與可見光圖像配準(zhǔn)方法分類及現(xiàn)狀[J].紅外技術(shù),2009,31(5):270-274.
[9] 汪漢云,王程.多源遙感圖像配準(zhǔn)技術(shù)綜述[J].計(jì)算機(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].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2010.
[14] 李偉.地面場(chǎng)景光學(xué)圖像輔助導(dǎo)航技術(shù)研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2008.
[15] 高展宏,徐文波.基于Matlab 的圖像處理案例教程[M].北京:清華大學(xué)出版社,2011:217-219.
[16] Nixon M S,Aguado A S.特征提取與圖像處理[M].2 版.李實(shí)英,楊高波,譯.北京:電子工業(yè)出版社,2013:92-109.