氣象衛星圖像導航的地標匹配算法研究與優化

郭強，楊磊，趙現綱，馮小虎，林維夏，張志清，魏彩英

國家衛星氣象中心，北京 100081

氣象衛星圖像導航的地標匹配算法研究與優化

郭強，楊磊，趙現綱，馮小虎，林維夏，張志清，魏彩英

國家衛星氣象中心，北京 100081

1 引言

氣象衛星是重要的天基氣象觀測平臺，廣泛應用于氣象業務、環境監測、防災減災、軍事活動、科學研究等領域。氣象衛星按軌道的不同分為靜止軌道氣象衛星和極軌氣象衛星。我國是世界上少數幾個同時擁有靜止和極軌氣象衛星的國家之一，與美國、歐盟一起構成全球氣象衛星觀測系統。目前，我國發展的氣象衛星有風云二號靜止軌道氣象衛星、風云一號和風云三號極軌氣象衛星，以及正在研究的新一代風云四號靜止軌道氣象衛星，在軌運行的衛星達到7顆[1]。

氣象衛星利用星上搭載的可見光和紅外掃描輻射計獲取衛星遙感圖像，經過預處理的圖像導航得到精確的圖像定位信息。目前，國際上氣象衛星大多采用基于地標匹配的圖像導航技術來保證定位精度，以獲得高質量的衛星定量產品。地標導航有人工地標導航和自動地標導航兩種方法。人工地標導航通過人工選取地標進行交互式地標導航[2-3]，需要大量的重復性人力勞動，不能保證準確性和一致性，無法滿足實時、自動、準確的地標導航要求。因此，國內外科學家對自動地標導航技術進行了大量研究[4-7]。Emery等人針對極軌氣象衛星觀測數據開展了自動地標導航方法的研究[4]，美國SSEC對靜止軌道GOES衛星設計了自動地標導航系統[5]，楊磊等分別研究了我國靜止和極軌氣象衛星的自動地標導航方法[6-7]，這些研究工作成為實現我國氣象衛星自動地標導航系統的基礎。

地標匹配算法主要有基于邊界的匹配方法[8]、基于特征的地標匹配方法[9]和基于灰度相關的地標匹配方法[4，6-7]等。其中，基于相關的地標匹配方法在地標導航中應用最為廣泛，該方法易于實現，匹配精度高，但計算量大。在自動地標導航方法的研究中，針對地標匹配算法研究及優化的討論并不多。Emery等利用基本的最大互相關方法進行衛星圖像自動導航[4]，楊磊等利用最大互相關地標匹配方法設計了我國氣象衛星的自動地標導航系統[6-7]，朱永松等研究了基于相關系數的圖像匹配算法和改進方法[10]，劉瑩等討論了灰度相關圖像匹配算法的改進方法[11]。本文在此基礎上，針對氣象衛星遙感圖像的特點，采用最大互相關地標匹配算法，綜合利用計算優化、搜索優化、并行優化等技術，有效降低算法復雜度，提高算法執行效率，以滿足氣象衛星圖像自動地標導航的定位精度和實效性要求。

2 自動地標導航

氣象衛星的自動地標導航功能是基于地標匹配進行衛星圖像導航來實現的。風云二號靜止軌道氣象衛星的自動地標導航中，實時衛星遙感圖像采用標稱圖數據，地標模板圖像由許多有明顯特征的地標組成，可以從標準的海陸地標模板庫中提取，與衛星圖像有相同的投影方式。根據地標信息，在實時衛星圖像中提取對應的地標區域數據，并利用云檢測處理剔除云污染因素，以避免造成圖像導航偏移。對衛星地標區域圖像與地標模板圖像進行自動匹配，利用地標匹配算法計算地標偏移量。完成對標稱圖中所有地標點的匹配后，經過質量控制得到有效的偏移結果，然后對衛星圖像重新導航，得到精確的圖像定位結果。

圖1是風云二號氣象衛星圖像自動地標導航的流程圖。極軌氣象衛星自動地標導航的處理過程與靜止軌道氣象衛星大致相同。

圖1 風云二號氣象衛星圖像自動地標導航流程圖

3 地標匹配方法

3.1 地標匹配算法

地標匹配是利用圖像匹配算法在實時衛星圖像中尋找與地標模板圖像相同或相似區域的過程，可以得到實際圖像相對于標準地標模板圖像的偏移量。地標匹配算法主要有基于特征的地標匹配方法、基于灰度相關的地標匹配方法、基于邊界的匹配方法等。基于特征的地標匹配方法，通過從原始圖像中提取點、線、區域等顯著特征作為匹配基元來進行特征匹配，該算法的效率較高，但匹配精度不夠。基于相關的地標匹配方法利用空間域的一維或二維滑動模板進行圖像匹配，該算法易于實現，匹配精度高，但通常計算量較大[10]。

考慮到氣象衛星遙感圖像需要很高的定位精度，通常采用基于灰度相關的地標匹配方法來進行圖像導航。相關匹配算法主要有最小誤差法和相關系數法等方法，前者利用圖像之間的差別程度進行匹配，而后者利用圖像之間的相似程度進行匹配。最小誤差法在衛星圖像區域中搜索與地標模板圖像絕對差最小的位置，作為地標匹配位置，算法計算速度快，但可靠性低，無法滿足衛星圖像導航的高可靠性要求。相關系數法將地標模板圖像在實時衛星圖像上滑動，計算每一位置上對應的相關系數值，選取相關系數最大的點作為地標匹配點，相關系數描述了圖像間的線性相似度。相關系數法在地標導航中應用最為廣泛，該方法易于實現，匹配精度高，但計算量大。本文將對這一算法進行優化，以滿足自動地標導航應用需求。

3.2 基于最大相關系數的地標匹配算法

對于給定的衛星圖像f(x,y)和地標模板圖像w(x,y)，圖像大小分別為M×N和J×K，如圖2所示。基于最大相關系數的地標匹配算法的基本原理是在衛星圖像中搜索與標準地標模板圖像相匹配的位置，將地標模板圖像w(x,y)作為一個空間濾波器在衛星圖像f(x,y)中的每個位置計算相關系數R(x,y)。為克服相關系數隨幅度的變化，采用歸一化互相關系數（Normalized Maximum Cross Correlation），即

圖2 地標模板與衛星圖像在(x0,y0)位置的匹配

其中x=0,1,…,M-1，y=0,1,…,N-1，fˉ為地標模板與衛星圖像重疊區域的像素平均值，wˉ為地標模板圖像的像素平均值，求和運算在w和f重疊區域內進行。歸一化互相關系數R(x,y)在[-1,1]范圍內，相關系數越接近于1，代表圖像匹配的相似度越高。

4 地標匹配算法優化

根據最大相關系數匹配算法的原理，可以看到其處理過程需要在圖像范圍內每個可能的位置進行搜索計算，而且相關系數求取也涉及到大量的計算。通過對式（2）的分析，可以得到一次地標匹配過程所需要的計算量：加法運算約12MNJK次，乘法運算約3MNJK次。由于在整個圖像上進行相關系數計算，這種傳統的地標匹配算法計算速度慢，算法復雜度高，有待進一步優化。

地標匹配算法的優化研究，可以從降低算法復雜度和提高算法計算速度兩個方面來開展。由于地標匹配算法的計算量與相關系數計算和搜索位置數直接相關，所以利用計算優化和搜索優化來降低算法復雜度。另一方面，針對地標匹配算法的特點，對圖像進行分區并行處理，利用并行計算來提高算法計算速度。

4.1 算法復雜度優化

地標匹配算法最佳匹配位置的搜索過程中包括很多重復和無效的計算，搜索范圍過大也是影響算法復雜度的直接原因。針對算法的特點，在保證地標匹配精度前提下，通過減小相關系數運算量和搜索范圍來降低算法總的計算量。

（1）計算優化

歸一化互相關系數的計算優化可以通過簡化相關系數的計算公式和去除冗余計算來實現，即通過優化A和優化B的處理過程來完成。

優化A：簡化相關系數計算。根據式（1），相關系數公式的分子為協方差，分母可以通過方差求得，簡化方差和協方差的計算過程可以減少計算量[13]。根據式（2）將協方差和方差展開并進行簡化后，可以分別得到式（3）和式（4）。

協方差計算簡化：

優化B：去除冗余計算。相關系數計算中涉及到大量重復和無效的冗余計算，可以通過下面的方法進行優化：在一次地標匹配過程中，地標模板圖像保持不變，地標模板圖像的像素平均值wˉ只計算一次；在實際衛星圖像窗口范圍內計算相關系數時，模板圖像方差為常數，可提前計算并直接代入運算；相關系數計算中分子協方差小于零時相關系數為負值，圖像之間的匹配程度很小，此位置不是匹配點，可以不進行后續的方差計算等處理。

經過上述處理去除冗余計算后，相關系數計算量將大大減少。假設相關系數為正值的概率為X，那么單獨利用此優化步驟可以使相關系數的計算量降低為：

加法運算6MNJK+2XJK(MN+2MK+2JN-2JK)次；乘法運算MNJK+XJK(MN+MK+JN-JK)次。有效剔除了冗余計算。

（2）搜索優化

在圖像范圍內進行相關系數運算的搜索位置數是影響地標匹配算法復雜度的另一重要因素。為減少計算量，采用網格搜索（Grid Search）算法對搜索范圍進行優化。

優化G：采用網格搜索算法。

為保證地標匹配的精度，選取網格搜索步長為2，盡量覆蓋圖像區域。在每個格點位置計算相關系數，找到最大相關系數對應的格點Gm，然后求取原圖像中Gm周圍各點對應的相關系數，這些點中有相關系數最大的就是最佳的匹配位置。具體的網格搜索步驟如下：

步驟1遍歷圖像網格各個位置，計算各格點對應的相關系數，得到相關系數矩陣RG。

步驟2在RG中搜索具有最大相關系數GRm(xm,ym)的格點位置。

步驟3在原圖像區域中計算(xm,ym)周圍8個點的相關系數，取9個點中相關系數最大者為匹配點。

根據衛星圖像的特點，地標匹配位置鄰近范圍內各點對應的相關系數也比較大，其變化過程是漸變的。由于搜索步長為2，這種網格搜索算法可以基本覆蓋到每個可能的地標匹配位置，最大程度地保證地標匹配的精度。通過搜索優化，算法搜索位置數可以減少到原來的1/4。

利用計算優化和搜索優化降低算法復雜度后，地標匹配算法的計算量減少為：

加法運算約MNJK+(1/4)XJK(MN+3MK+3JN-3JK)次；乘法運算約(1/4)[MNJK+XJK(MN+MK+JN-JK)]次。

可以看到，優化地標匹配算法相對于經典算法的計算量大大減少，有效降低了算法的復雜度，提高了相關系數的計算速度。

4.2 并行地標匹配算法

根據地標匹配算法的特點，在圖像各個位置的相關系數計算是相互獨立的，利用這種低耦合性可以在圖像上進行分區處理。采用并行計算技術[14]，充分利用處理器資源，多線程并行地在不同圖像區域上計算相關系數，可以大大提高算法的執行效率，縮短地標匹配時間。

優化P：并行優化。地標匹配算法的并行優化（Parallel Optimization）思路如下：將衛星圖像劃分為n個均勻大小的區域，可以按行、列分割，或者行列同時分割；對每一個圖像區域調用一個線程進行處理，計算得到的相關系數存儲到統一的相關系數矩陣R中；等待所有線程計算完成后，調用后續的算法處理指令計算地標匹配位置。并行計算的圖像區域劃分如圖3所示，其中實線和虛線分別代表行和列方向的圖像劃分，黑點表示網格搜索時的匹配點，白點表示其周圍的8個像素點。由于同時采用網格搜索優化，圖像劃分的粒度不能太大。如果采用雙線程進行并行計算，相關系數計算將節省近一半時間。

圖3 并行計算的圖像區域劃分示意圖

綜合利用上述的計算優化、搜索優化和并行優化步驟，得到改進的最大互相關地標匹配算法。經過優化的地標匹配算法，能夠保證算法精確性和穩定性的同時，有效降低算法復雜度，提高算法的執行效率，滿足衛星圖像導航的高可靠、高時效性要求。

5 實驗分析

為驗證優化地標匹配算法的性能，利用FY-2D氣象衛星2012年10月11日UT04：30（世界時）的多通道掃描輻射計可見光圖像數據對算法進行測試。選取實際衛星圖像區域的大小為201像素×201像素，地標模板圖像的大小為51×51，如圖4所示。衛星圖像相對于地標模板圖像的實際偏移量在東西方向和南北方向預置為0，便于進行地標匹配精度測試。算法搜索優化的網格步長選為2，以保證地標匹配的準確性。算法并行優化采用雙線程并行計算，衛星圖像在行方向以圖像中心點劃分為南北兩個區域，并行進行相關運算，提高算法執行效率。

圖4 待匹配的衛星圖像區域和地標模板圖像

算法實驗分析的步驟如下：第一步，利用經典的最大互相關地標匹配算法進行地標匹配，測試經典算法的執行效率。第二步，利用簡化的相關系數計算公式進行算法測試，驗證優化A步驟的效果。第三步，測試去除冗余計算后的算法性能，即單獨進行優化B步驟的結果。第四步，測試計算優化后的算法性能，即同時利用優化A和優化B步驟對算法性能的改進。第五步，利用優化G的網格搜索對經典算法進行改進，測試優化后的算法性能。第六步，利用優化P的并行計算對經典算法進行改進，測試并行算法的運算性能。第七步，驗證經過計算優化和搜索優化降低算法復雜度后算法的執行效率，即同時利用優化A、優化B和優化G步驟。最后，對綜合利用計算優化、搜索優化和并行優化后的算法進行測試，驗證優化地標匹配算法的性能，并對算法執行效率進行對比分析。

地標匹配算法的性能測試結果見表1。可以看到，經過相關系數計算簡化后的算法性能略有提高，這是因為優化步驟A只減少了加法運算，而乘法運算量保持不變，對算法性能的改進有限；經過優化B去除冗余計算后，算法性能大約提高了一倍，這是因為經典地標匹配算法中含有大量的重復和無效運算；利用搜索優化進行網格搜索，搜索位置數減少到原來的1/4，所以算法執行時間也減少到原來的1/4左右；同時利用計算優化和搜索優化的改進算法，性能進一步明顯提高；利用雙線程的并行計算技術，可以將原始算法的執行速度提高近一倍，加速比達到1.83；經過綜合優化的算法性能大大提高，一次地標匹配過程的執行時間只有經典算法的6.68%。如果改變搜索優化和并行優化策略，算法性能還有很大的提升空間。圖5是對應的地標匹配結果，由圖中相關系數的空間分布可見，最大的相關系數值出現在最佳地標匹配點附近，輸出的最佳地標匹配點和偏移量與預設參數一致，地標匹配算法有很高的精確度。根據實驗分析結果，本文提出的優化地標匹配算法能夠在保證地標匹配精度的同時，有效降低算法復雜度，明顯提高執行效率，滿足衛星自動地標導航系統的可靠性和時效性要求。

表1 地標匹配算法性能對比

圖5 地標匹配結果

6 結束語

本文討論了氣象衛星圖像導航的地標匹配算法優化問題，針對地標導航系統和衛星遙感圖像的特點研究了地標匹配的方法，采用基于最大相關系數的地標匹配算法來保證匹配精度。在此基礎上，對地標匹配算法的優化方法進行了深入研究，通過相關系數的計算優化和搜索優化，簡化計算過程，去除冗余計算，減少搜索量，有效降低了算法的復雜度。利用并行優化，在圖像范圍內進行分區并行計算，顯著提高了算法的執行效率。測試結果表明，利用該算法能夠快速完成地標匹配，同時有很高的匹配精度，能夠滿足衛星圖像自動地標導航的應用需求。

[1]許健民，楊軍，張志清，等.我國氣象衛星的發展與應用[J].氣象，2010，17（3）：94-100.

[2]Illera P，Delgado J A，Calle A.A navigation algorithm for satellite images[J].International Journal of Remote Sensing，1996，17（3）：577-588.

[3]Ho D，Asem A.NOAA AVHRR image referencing[J].International Journal of Remote Sensing，1986，7（6）：895-904.

[4]Emery W J，Baldwin D G，Matthews D.Maximum cross correlation automatic satellite image navigation and attitude corrections for open ocean image navigation[J].IEEE Transactions on Geoscience and Remote Sensing，2003，41（1）：33-42.

[5]SSEC.McIDAS navigation manual[Z].Madison：University of Wisconsin-Madison，1986.

[6]楊磊，馮小虎，郭強，等.風云二號氣象衛星圖像自動幾何精校正[J].計算機工程與應用，2011，47（3）：202-206.

[7]楊磊，楊忠東.極軌氣象衛星自動地標導航方法[J].應用氣象學報，2009，20（3）：329-336.

[8]Eugenio F，Marque S F.Automatic satellite image georeferencing using a contour-matching approach[J].IEEE Transactions on Geoscience and Remote Sensing，2003，41（12）：2869-2880.

[9]Dai Xiaolong，Korran S.A feature-based image registration algorithm using improved chain-code representation combined with invariant moments[J].IEEE Transactions on Geoscience and Remote Sensing，1999，37（5）：2351-2362.

[10]朱永松，國澄明.基于相關系數的相關匹配算法的研究[J].信號處理，2003，19（6）：531-534.

[11]劉瑩，曹劍中，許朝暉，等.基于灰度相關的圖像匹配算法的改進[J].應用光學，2007，28（5）：536-540.

[12]Gonzalez C R.Digital image processing[M].2nd ed.[S.l.]：Publishing House of Electronics Industry，2003.

[13]Sun Changming.Multi-resolution rectangular subregioning stereo matching using fast correlation and dynamic programming techniques，CMIS Report No.98/246[R].1998.

[14]Grama A，Gupta A，Karypis G，et al.Introduction to parallel computing[M].2nd ed.Pearson：Addison Wesley，2003.

GUO Qiang,YANG Lei,ZHAO Xiangang,FENG Xiaohu,LIN Weixia,ZHANG Zhiqing,WEI Caiying

National Satellite Meteorological Center,Beijing 100081,China

This paper studies the landmark matching algorithm in automatic landmark navigation system of the meteorological satellite.The landmark matching algorithm based on maximum correlation coefficient method is used to guarantee the matching precision.The optimized algorithm is proposed using computing optimization,search optimization and parallel optimization comprehensively.The experimental results show that this algorithm can effectively reduce the complexity of the algorithm and significantly improve the execution efficiency.The optimized algorithm can meet the high reliability and time-sensitive requirements of automatic landmark navigation system,and guarantee the matching precision at the same time.

automatic landmark navigation;landmark matching;maximum correlation coefficient;algorithm optimization

對氣象衛星圖像自動地標導航系統中的地標匹配算法進行了深入研究，采用基于最大相關系數的地標匹配算法來保證匹配精度，綜合利用計算優化、搜索優化、并行優化等技術得到優化的地標匹配算法。實驗結果表明，該算法能夠有效降低算法復雜度，明顯提高算法執行效率，同時保證地標匹配的準確性，滿足自動地標導航系統的高可靠性和高時效性需求。

自動地標導航；地標匹配；最大相關系數；算法優化

A

TP751

10.3778/j.issn.1002-8331.1305-0212

GUO Qiang,YANG Lei,ZHAO Xiangang,et al.Research and optimization of landmark matching algorithm for meteorological satellite image navigation.Computer Engineering and Applications,2013,49（24）：152-156.

國家公益性行業（氣象）科研專項（No.GYHY201006046）。

郭強（1986—），男，工程師，研究領域為衛星通信和高性能計算；楊磊（1978—），男，博士，副研究員，研究領域為遙感圖像處理和模式識別；趙現綱（1976—），男，博士，高級工程師，研究領域為計算機應用；馮小虎（1970—），男，高級工程師，研究領域為衛星地面應用系統。E-mail：cscowboy@126.com

2013-05-17

2013-08-27

1002-8331（2013）24-0152-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.009.html