用于遙感圖像目標快速匹配識別的改進混合溢出樹算法

陳彥彤，徐　偉，樸永杰，王燦進，陳　娟

(1.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033；2.中國科學院大學，北京 100049)

?

用于遙感圖像目標快速匹配識別的改進混合溢出樹算法

陳彥彤1，2，徐偉1*，樸永杰1，王燦進1，陳娟1

(1.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033；2.中國科學院大學，北京 100049)

提出一種基于標記的混合溢出樹(SHSPT)特征匹配算法，用于遙感圖像的目標匹配識別。針對特征數據建立和預處理，提出了基于中心點的數據分割方法，通過定義數據密集區域的中心，舍去邊緣稀疏數據，提取出分割后的數據。進行特征匹配時，使用二進制數組表示數據空間，標記分割后的特征向量數據，通過比特操作計算特征向量間的距離，縮短計算時間。最后對特征匹配方法進行改進，采用待匹配特征距離的均值代替尺度不變特征變換(SIFT)匹配算法的次臨近特征距離，從而得到更多的匹配點。實驗證明，基于標記的混合溢出樹特征匹配算法占用內存空間比傳統的混合溢出樹算法減少約68%，匹配準確度與原算法接近，匹配時間平均縮短了約32.8%，解決了航天遙感圖像數據量大，特征維數較高，匹配識別時間長，占用計算機內存大等問題。

遙感目標識別；特征標記；數據分割；圖像匹配；混合溢出樹算法

1　引　言

近年來，我國航天遙感技術不斷發展，遙感圖像在空間分辨率、時間分辨率和光譜分辨率方面不斷提高，其應用領域也愈加廣闊[1]。特別是在軍事方面，遙感圖像目標匹配識別對于戰場偵察、戰術規劃、軍事測繪、海洋監測等都有著重要的戰略意義[2-3]。

目標匹配識別技術[4-7]主要是利用特征匹配來識別目標，特征匹配是從兩組特征點集中找到兩兩距離最臨近的特征匹配對，匹配對的集合即為所識別到的目標[8-10]。目前尋找特征匹配對的方法大致可分為兩種，一種是窮舉法[11]，即將數據集中的點與查詢點逐一進行距離比較，這種方法不需要進行數據預處理，實現簡單，但是搜索效率較低，不適用于大規模數據集的檢索；第二種是建立數據索引，然后進行快速匹配，例如M-tree[12]搜索算法、Kd-tree[13]搜索算法、寬度優先搜索算法(Breadth First Search，BFS)[14]等。這些搜索算法雖然提高了搜索效率，但為保證搜索的準確性，需要耗費大量的時間進行“回溯”操作，降低了搜索速度。

針對這個問題，學者們提出了很多改進方案。其中Lee提出了Spill-tree算法[15]，采用冗余分割的方式，避免了回溯操作，但同時也降低了查詢的準確率；Moore提出了Hybrid Spill-tree的搜索策略[16]，該方法結合了M-tree的深度優先搜索算法(Depth First Search，DFS)[17]和Spill-tree的冗余分割算法，在非重疊結點使用回溯搜索，在重疊結點使用失敗搜索，從而提高了查詢精度，也適用于較高維數據的檢索，但面對遙感圖像大規模的數據量，仍然不能滿足快速處理的需求。

目前對于遙感圖像的特征匹配仍然存在以下問題：(1)遙感圖像背景復雜，特征數據分布較廣，這給建立數據索引時的數據分割帶來了困難；(2)遙感圖像數據量巨大，且生成的特征維數較高，給算法的計算效率和計算機存儲帶來挑戰；(3)在高分辨情況下，特征的獨特性不高，傳統的特征匹配方法會導致大量的誤匹配。針對這些問題，本文提出了適用于遙感圖像的基于標記的混合溢出樹特征匹配識別方法(Signed Hybrid Spill-tree，SHSPT)，首先通過篩選數據中心點的分割方式，更準確地對大規模遙感數據進行分割；然后應用基于二進制標記的方法，提高特征匹配速度，降低計算機存儲占用空間；最后通過改進尺度不變特征變換(Scale Invariant Feature Transform，SIFT)的特征匹配方法，提出了基于比值的K臨近均值匹配，從而能得到更多的匹配點，并去除誤匹配點，優化匹配結果。

2　中心點數據分割

數據分割是建立數據索引的第一步，Hybrid Spill-tree算法通過選取給定數據集中距離最遠的點作為端點，然后將數據以遞增的方式排序，采用冗余分割的方式把數據平均分為兩組。但在實際應用中，往往會因為數據分布的不均勻或偏移較大，導致冗余分割后的重疊節點較少。根據文獻[13]方法，對一組分布不均勻的二維數據集{a，b，c，d，e，f，g，h，i}進行分割，若采取平均分割的方式，則數據集被分為{a，b，c，d，e，f}和{g，h，i}，如圖1(a)所示。若以中心點e為分割點，雖然數據被平均分為{a，b，c，d，e}和{e，f，g，h，i}，但依然無法判斷處于冗余區域中待匹配點的歸屬問題，如圖1(b)所示。

(a)平均分割方式(a)Average separate method(b)中心點分割方式(b)Center point separate method

本文采用基于“中心點”的方法，構建分裂樹。假定數據集為{a，b，c，d，e，f，g，h，i}，具體步驟如下：

(1)以中心點e(mid)作為數據中心，令數據密集端的a點作為左端點(left point)，在右端選取到e的距離與a到e的距離最接近的點作為右端點(right point)，在這里為h點，然后舍去數據稀疏端的邊緣點i，如圖2所示。

圖2　中心點的分割示意圖

(2)過中心點e作一條垂直于坐標軸的直線L，將數據集平均分為兩部分，再作兩條與L距離都為t的平行分割直線LL和LR，將它們分別作為區域RC與LC的邊界，在坐標軸上選取距離右端點為2t的兩點M、N，這樣就將數據分為3組，如圖3所示。

圖3　分裂樹構建示意圖

(3)對于數據集中的任意一點x，定義x到左端點的距離為D(left，x)，x到M的距離為D(M，x)，x到N的距離為D(N，x)，則：

(1)

原數據集被冗余分割為兩組，其中LC={a，b，c，d，e}，RC={d，e，f，g，h}，重疊部分為{d，e}。

3　二進制數據標記

二進制數據能夠大幅降低計算機的存儲空間，并且簡化數據運算。根據二維數據集{a，b，c，d，e，f}，以點的形式在坐標軸上表示，因此，本文提出將平面劃分為不同的區域，把數據集以區域代碼的形式表示出來，如圖4所示。

圖4　二進制數據空間

通過二進制數據空間，將數據集以二進制的形式表示出來，如表1所示。

表1　標記后的數據集

二進制數組將數據空間劃分為16個數據子空間，根據二進制數據空間，原始數據被轉換為二進制數組的形式，但會出現不同數據對應同一標記的情況，如表1中：c(0.3，0.7)，d(0.4，0.6)，對應同一標記0110。根據二進制數據空間，不同數據對應同一標記的概率P為：

P=(1/2n)D，

(2)

其中：n為二進制數據空間的比特個數；D為數據的向量維數。在實際應用中，由于遙感圖像的特征維數較高，這種情況發生的概率較小，因此并不會影響最終的匹配識別結果。

4　SHSPT特征匹配

針對遙感圖像數據量大、特征分布廣的特點，本文提出基于二進制標記的SHSPT數據搜索算法，其構造過程如下：首先對每個SIFT算法生成的128維遙感圖像特征數據進行標記處理，將特征數據的兩個維度作為一組，共需要標記64組，如圖5所示。為了提高標記的精度，采用4位二進制數進行標記，因此可將特征空間劃分為256(24×24)個子空間。

圖5　遙感圖像特征標記方式

然后由Hybrid Spill-tree算法和中心點數據分割方法可知，閾值ρ<1，實驗中取為0.7。對每個根結點v，設其包含的點數為N(v)，使用重疊緩沖區分裂點集，若其任意子結點包含的點數超過ρ*N(v)，則停止分裂，將t設為0，即該結點的左右子樹沒有重疊區域，并且標記v為一個非重疊的結點；若該結點的兩個子結點包含的點數均不超過ρ*N(v)，則標記為重疊結點。這樣可以保證每次分裂后，子結點包含的點數均小于父結點包含的點數，最后SHSPT的索引深度為O(log(n))。

SHSPT算法中，在非重疊結點使用回溯搜索，在重疊結點使用Defeatist搜索，通過標記數據，可以在特征匹配階段使用異或運算，以大幅提高匹配速度。

5　基于比值的K臨近均值匹配

原有的SIFT特征匹配利用最鄰近匹配特征d(1)和次鄰近匹配特征d(2)的比值[18]，如公式(3)所示：

d(1)/d(2)≤t.

(3)

(4)

實驗中K取總數據的5%，t=0.85toriginal，toriginal與原匹配方法的閾值相同時，認為特征正確匹配。

6　實驗結果與分析

為了驗證算法的效率，本文取M-tree、Hybrid Spill-tree算法作為對比算法，做了3組實驗：(1)3種算法占用計算機內存空間統計實驗；(2)特征匹配準確度對比實驗；(3)特征匹配時間對比實驗。本文實驗的硬件環境為：Intel(R) Core(TM) i5-4570 CPU@3.2 GHz，4 G內存，Window 7系統；實驗軟件平臺為Visual Studio2010 + OpenCV 2.4.11。實驗選用美國Astrium和Digital Globe公司的高分辨遙感影像數據庫中的600幅圖像進行算法驗證，其中包含Spot6衛星拍攝的像元分辨率為1.5 m的圖像200幅，以圖6(a)為例；QuickBird衛星拍攝的像元分辨率為0.61 m的圖像200幅，以圖6(b)為例；WorldView-2衛星拍攝的像元分辨率為0.5 m 的圖像200幅，以圖6為例。

(a)北京機場圖像(a)Beijing airport　(b)墨西哥機場圖像(b)Mexico airport　(c)紐約機場圖像(c)New York airport

6.1計算機內存占用實驗

實驗中使用M-tree、Hybrid Spill-tree、SHSPT三種算法，對SIFT提取到的特征進行匹配識別，其中3幅遙感圖像中包含的特征向量數據分別為2 721組、4 177組和10 782組，每個數據為128維，圖7(彩圖見期刊電子版)顯示的是3種算法計算機內存占用情況對比。

圖7　3種算法占用內存對比

如圖7所示，M-tree算法平均占用內存量為63.03 MB，占用量適中；而Hybrid Spill-tree算法平均占用內存量為103.7 MB，占用量較大，這主要因為其采用了冗余分割的算法，處于冗余區域的特征數據需要重復占用內存空間，從而增大了內存消耗；SHSPT算法平均占用內存僅為33.2 MB，相比于Hybrid Spill-tree算法減少了68%。這是因為SHSPT將提取到的特征向量轉變為了二進制數組，在計算機的存儲機制中，原有算法為浮點型數據，每個數據需要4個字節的存儲空間，即32比特，而本文算法中每兩組數據僅需1個字節即8比特數據，大幅節省了占用空間。

6.2特征匹配識別精確度比較

遙感圖像目標匹配識別的關鍵因素是匹配識別的精確程度，實驗中使用3種算法對3幅遙感圖像分別進行飛機目標的匹配識別，但本文算法使用了改進后的匹配方法，識別結果如圖8～10(彩圖見期刊電子版)所示。

(a)M-Tree(b)Hybrid Spill-Tree(c)SHSPT

(a)M-Tree　(b)Hybrid Spill-Tree　(c)SHSPT

(a)M-Tree　(b)Hybrid Spill-Tree　(c)SHSPT

從實驗結果可以看出，M-tree算法的匹配準確度最好，Hybrid Spill-Tree算法和本文算法由于都采用了冗余分割的方式，導致誤匹配點增加，但本文算法通過改進特征匹配方法，獲得了更多的匹配點，最終提高了匹配識別的正確率，結果優于Hybrid Spill-Tree算法，且與M-tree 算法的準確率接近。表2為3種算法匹配識別正確率的統計結果。

表2　3種算法匹配識別正確率比較

6.3計算復雜度比較

在計算復雜度對比實驗中，分別比較了3種算法在特征匹配上的耗時，并得到每種算法的總耗時，如表3所示。

從表3可以看出，M-tree算法的耗時最長，這主要因為其采用了回溯的搜索方式，Hybrid Spill-tree算法耗時次之，而本文算法耗時最短，且隨著圖像特征點的增加，算法的優勢更加明顯。這是因為本文方法采用了二進制的匹配方式，在匹配時可以通過異或方式計算特征間的距離，比傳統的計算歐式距離的方法計算量更小。

表3　特征提取算法耗時比較

7　結　論

本文在Hybrid Spill-tree算法的基礎上，提出一種基于標記的混合溢出樹的特征匹配算法，并應用于遙感圖像的目標匹配識別。在特征數據建立和預處理階段，采用基于中心點的分割方式，解決了由于數據偏移導致的冗余分割區域特征點過少的問題；在特征匹配階段，采用標記的方式，將遙感圖像特征向量轉換為二進制數據，以減少計算機內存消耗，并通過異或運算度量特征向量間的距離，以縮短計算時間；最后改進了SIFT特征匹配方法，采用K鄰近匹配特征距離的均值代替次鄰近距離，最大限度地保留了匹配特征點。實驗證明，應用SHSPT搜索算法對遙感圖像進行目標匹配識別時，計算機內存占用量較傳統算法減少約68%，匹配的準確度更高，耗時縮短了約32.8%，適用于遙感圖像目標的快速匹配識別。

[1]金光，徐偉. “吉林一號”小型高分辨率多光譜遙感衛星[J]. 空間對地觀測工程與技術，2014，12(2)：25-32.

JIN G， XU W. Light weight high resolution multispectral small satellite [J].SpaceEarthObservationEngineeringAndTechnology， 2014， 12(2): 25-32. (in Chinese)

[2]陳彥彤，王紹舉. 高分辨遙感圖像目標識別技術綜述[J]. 中國光學，2014，7(增)：17-23.CHEN Y T， WANG SH J. Review of target recognition technology for high resolution remote sensing image [J].ChineseOptics， 2014， 7(S): 17-23. (in Chinese)

[3]張仲瑜，焦淑紅. 多特征融合的紅外艦船目標檢測方法[J]. 紅外與激光工程，2015，44(增)：29-34.

ZHANG ZH Y， JIAO SH H. Infrared ship target detection method based on multiple feature fusion [J].InfraredandLaserEngineering， 2015， 44(S): 29-34. (in Chinese)

[4]田浩南，張葉. 基于邊緣及特征點匹配的立體圖像質量評價[J]. 液晶與顯示，2015，30(4)：666-672.

TIAN H N， ZHANG Y. Quality evaluation of stereo image based on edge and characteristic point matching [J].ChineseJournalofLiquidCrystalsandDisplays， 2015， 30(4): 666-672. (in Chinese)

[5]BURGHARDT T， DAMEN D. Correspondence，matching and recognition [J].InternationalJournalofComputerVision， 2015， 113(3): 161-162.

[6]趙立榮，朱瑋，曹永剛，等. 改進的加速魯棒特征算法在特征匹配中的應用[J]. 光學 精密工程，2013，21(12)：3263-3271.ZHAO L R， ZHU W， CAO Y G，etal.. Application of improved SURF algorithm to feature matching [J].Opt.PrecisionEng.， 2013， 21(12): 3263-3271. (in Chinese)[7]張博研，李廣澤，武星星. Quickbird遙感影像的車輛自動檢測與運動參數估計[J]. 液晶與顯示，2015，30(4)：687-694.

ZHANG B Y， LI G Z， WU X X. Speed estimation and automatic detection of moving vehicle from Quickbird satellite image [J].ChineseJournalofLiquidCrystalsandDisplays， 2015， 30(4): 687-694. (in Chinese)

[8]ZAMIR A R， SHAH M. Image Geo-Localization based on multiple nearest neighbor feature matching using generalized graphs [J].IEEETrans.onPatternAnalysisandMachineIntelligence， 2014， 36(8): 1546-1558.

[9]邵振峰，陳敏. 尺度旋轉以及亮度穩健的高分辨率影像直線特征匹配[J]. 光學 精密工程，2013，21(3)：790-798.

SHAO ZH F， CHEN M. Line-based matching for high-resolution images with robustness for scale， rotation andillumination [J].Opt.PrecisionEng.， 2013， 21(3): 790-798. (in Chinese)

[10]王志強，程紅，楊桄，等. 全局圖像配準的目標快速定位方法[J]. 紅外與激光工程，2015，44(增)：225-229.

WANG ZH Q， CHENG H， YANG G，etal.. Fast target location method of global image registration [J].InfraredandLaserEngineering， 2015， 44(S): 225-229. (in Chinese)

[11]CHOI H H， BAE S J. Fast parallelk-NN search in high-dimensional spaces[C].Proc.oftheFourthInternationalConferenceonCreativeContentTechnologies， 2012: 32-37.

[12]LIU B Y， SADEGHI F， TAPPEN M. Probabilistic label trees for efficient large scale image classification [C]. 2013IEEEConferenceonComputerVisionandPatternRecognition(CVPR)， 2013: 843-850.

[13]BINDICK S， STIEBLER M， KRAFCZYK M. Fast kd-tree-based hierarchical radiosity for radiative heat transport problems [J].InternationalJournalforNumericalMethodsinEngineering， 2011， 86(9): 1082-1100.

[14]CHEN Y， XU M， LIU H L，etal.. An improved image mosaic based on Canny edge and an 18-dimensional descriptor [J].Optik， 2014， 125(17): 4745-4750.

[15]LI Z H， NEE A Y C， ONG S K，etal.. Tampered image detection using image matching [C]. 5thInternationalConferenceonComputerGraphics，ImagingandVisualization(CGIV)， 2008: 174-179.

[16]LEE H J， KIM H L， CHANG J W. An efficient high-dimensional indexing scheme using a clustering technique for content-based retrieval [C].Proc.oftheInternationalConferenceonComputationalScienceandEngineering， 2009: 318-323.

[17]MAHMUD M S， SARKER U， ISLAM M M. A greedy approach in path selection for DFS based maze-map discovery algorithm for an autonomous robot [C].Proc.ofInternationalConferenceonComputerandInformationTechnology(ICCIT)， 2012: 22-24.

[18]ANDREA COSTANZO， IRENE AMERINI， ROBERTO CALDELLI. Forensic analysis of SIFT keypoint removal and injection [J].IEEETrans.OnInformationForensicsandSecurity， 2014， 9(9): 1450-1464.

陳彥彤(1989-)，男，遼寧沈陽人，博士研究生，2012年于吉林大學獲得學士學位，主要從事模式識別及機器視覺方面的研究。E-mail: chenyantong1@yeah.net

導師簡介：

徐偉(1981-)，男，黑龍江大慶人，博士，研究員，2003年于吉林大學獲得學士學位，2008年于中國科學院長春光學精密機械與物理研究所獲得博士學位，主要從事星載一體化衛星技術及高可靠一體化航天電子學系統等方面的研究。E-mail: xwciomp@126.com

(版權所有未經許可不得轉載)

Improved hybrid spill-tree algorithm for fast target matching recognition of satellite images

CHEN Yan-tong1， 2， XU Wei1*， PIAO Yong-jie1， WANG Can-jin1， CHEN Juan1

(1.ChangchunInstituteofOptics，FineMechanicsandPhysics，ChineseAcademyofSciences，Changchun130033，China；2.UniversityofChineseAcademyofSciences，Beijing100049，China)*Correspondingauthor，E-mail：xwciomp@126.com

An improved Hybrid Spill-tree algorithm based on the signed method defined as Signed Hybrid Spill-tree (SHSPT) was proposed for target matching of remote sensing images. For establishing data and preprocessing， a data separate method based on a center point was proposed， the separated data were extracted by defining the center of dense data， and the edge data were abandoned. In the feature matching， binary array were used to express the data space and to mark the feature vector. Then， the bit operation was used to compute the distance between the feature vectors and to shorten the computing time. Finally， the feature matching algorithm was improved. The average value of the feature distance was used to replace the secondary characteristic distance from the Scale Invariant Feature Transform(SIFT)matching algorithm to obtain more matching points. The test results show that the computer memory by proposed algorithm is reduced 68% than that of traditional hybrid spill-tree method， and matching accuracy is closed to that of the traditional one. In addition， the method reduces 32.8% matching time. It solves the problems of remote sensing images in larger data amounts， higher dimensions， longer matching time and larger computer memory.

remote target recognition; feature mark; data partition; image matching; hybrid spill-tree algorithm

2016-01-18；

2016-03-04.

國家863高技術研究發展計劃資助項目(No.2012AA121502)

1004-924X(2016)09-2310-08

TP753

A

10.3788/OPE.20162409.2310