用于遙感圖像目標(biāo)快速匹配識(shí)別的改進(jìn)混合溢出樹算法

陳彥彤，徐　偉，樸永杰，王燦進(jìn)，陳　娟

(1.中國(guó)科學(xué)院 長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033；2.中國(guó)科學(xué)院大學(xué)，北京 100049)

?

用于遙感圖像目標(biāo)快速匹配識(shí)別的改進(jìn)混合溢出樹算法

陳彥彤1，2，徐偉1*，樸永杰1，王燦進(jìn)1，陳娟1

(1.中國(guó)科學(xué)院 長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林 長(zhǎng)春 130033；2.中國(guó)科學(xué)院大學(xué)，北京 100049)

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

遙感目標(biāo)識(shí)別；特征標(biāo)記；數(shù)據(jù)分割；圖像匹配；混合溢出樹算法

1　引　言

近年來(lái)，我國(guó)航天遙感技術(shù)不斷發(fā)展，遙感圖像在空間分辨率、時(shí)間分辨率和光譜分辨率方面不斷提高，其應(yīng)用領(lǐng)域也愈加廣闊[1]。特別是在軍事方面，遙感圖像目標(biāo)匹配識(shí)別對(duì)于戰(zhàn)場(chǎng)偵察、戰(zhàn)術(shù)規(guī)劃、軍事測(cè)繪、海洋監(jiān)測(cè)等都有著重要的戰(zhàn)略意義[2-3]。

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

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

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

2　中心點(diǎn)數(shù)據(jù)分割

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

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

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

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

圖2　中心點(diǎn)的分割示意圖

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

圖3　分裂樹構(gòu)建示意圖

(3)對(duì)于數(shù)據(jù)集中的任意一點(diǎn)x，定義x到左端點(diǎn)的距離為D(left，x)，x到M的距離為D(M，x)，x到N的距離為D(N，x)，則：

(1)

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

3　二進(jìn)制數(shù)據(jù)標(biāo)記

二進(jìn)制數(shù)據(jù)能夠大幅降低計(jì)算機(jī)的存儲(chǔ)空間，并且簡(jiǎn)化數(shù)據(jù)運(yùn)算。根據(jù)二維數(shù)據(jù)集{a，b，c，d，e，f}，以點(diǎn)的形式在坐標(biāo)軸上表示，因此，本文提出將平面劃分為不同的區(qū)域，把數(shù)據(jù)集以區(qū)域代碼的形式表示出來(lái)，如圖4所示。

圖4　二進(jìn)制數(shù)據(jù)空間

通過(guò)二進(jìn)制數(shù)據(jù)空間，將數(shù)據(jù)集以二進(jìn)制的形式表示出來(lái)，如表1所示。

表1　標(biāo)記后的數(shù)據(jù)集

二進(jìn)制數(shù)組將數(shù)據(jù)空間劃分為16個(gè)數(shù)據(jù)子空間，根據(jù)二進(jìn)制數(shù)據(jù)空間，原始數(shù)據(jù)被轉(zhuǎn)換為二進(jìn)制數(shù)組的形式，但會(huì)出現(xiàn)不同數(shù)據(jù)對(duì)應(yīng)同一標(biāo)記的情況，如表1中：c(0.3，0.7)，d(0.4，0.6)，對(duì)應(yīng)同一標(biāo)記0110。根據(jù)二進(jìn)制數(shù)據(jù)空間，不同數(shù)據(jù)對(duì)應(yīng)同一標(biāo)記的概率P為：

P=(1/2n)D，

(2)

其中：n為二進(jìn)制數(shù)據(jù)空間的比特個(gè)數(shù)；D為數(shù)據(jù)的向量維數(shù)。在實(shí)際應(yīng)用中，由于遙感圖像的特征維數(shù)較高，這種情況發(fā)生的概率較小，因此并不會(huì)影響最終的匹配識(shí)別結(jié)果。

4　SHSPT特征匹配

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

圖5　遙感圖像特征標(biāo)記方式

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

SHSPT算法中，在非重疊結(jié)點(diǎn)使用回溯搜索，在重疊結(jié)點(diǎn)使用Defeatist搜索，通過(guò)標(biāo)記數(shù)據(jù)，可以在特征匹配階段使用異或運(yùn)算，以大幅提高匹配速度。

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

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

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

(3)

(4)

實(shí)驗(yàn)中K取總數(shù)據(jù)的5%，t=0.85toriginal，toriginal與原匹配方法的閾值相同時(shí)，認(rèn)為特征正確匹配。

6　實(shí)驗(yàn)結(jié)果與分析

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

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

6.1計(jì)算機(jī)內(nèi)存占用實(shí)驗(yàn)

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

圖7　3種算法占用內(nèi)存對(duì)比

如圖7所示，M-tree算法平均占用內(nèi)存量為63.03 MB，占用量適中；而Hybrid Spill-tree算法平均占用內(nèi)存量為103.7 MB，占用量較大，這主要因?yàn)槠洳捎昧巳哂喾指畹乃惴ǎ幱谌哂鄥^(qū)域的特征數(shù)據(jù)需要重復(fù)占用內(nèi)存空間，從而增大了內(nèi)存消耗；SHSPT算法平均占用內(nèi)存僅為33.2 MB，相比于Hybrid Spill-tree算法減少了68%。這是因?yàn)镾HSPT將提取到的特征向量轉(zhuǎn)變?yōu)榱硕M(jìn)制數(shù)組，在計(jì)算機(jī)的存儲(chǔ)機(jī)制中，原有算法為浮點(diǎn)型數(shù)據(jù)，每個(gè)數(shù)據(jù)需要4個(gè)字節(jié)的存儲(chǔ)空間，即32比特，而本文算法中每?jī)山M數(shù)據(jù)僅需1個(gè)字節(jié)即8比特?cái)?shù)據(jù)，大幅節(jié)省了占用空間。

6.2特征匹配識(shí)別精確度比較

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

(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

從實(shí)驗(yàn)結(jié)果可以看出，M-tree算法的匹配準(zhǔn)確度最好，Hybrid Spill-Tree算法和本文算法由于都采用了冗余分割的方式，導(dǎo)致誤匹配點(diǎn)增加，但本文算法通過(guò)改進(jìn)特征匹配方法，獲得了更多的匹配點(diǎn)，最終提高了匹配識(shí)別的正確率，結(jié)果優(yōu)于Hybrid Spill-Tree算法，且與M-tree 算法的準(zhǔn)確率接近。表2為3種算法匹配識(shí)別正確率的統(tǒng)計(jì)結(jié)果。

表2　3種算法匹配識(shí)別正確率比較

6.3計(jì)算復(fù)雜度比較

在計(jì)算復(fù)雜度對(duì)比實(shí)驗(yàn)中，分別比較了3種算法在特征匹配上的耗時(shí)，并得到每種算法的總耗時(shí)，如表3所示。

從表3可以看出，M-tree算法的耗時(shí)最長(zhǎng)，這主要因?yàn)槠洳捎昧嘶厮莸乃阉鞣绞?，Hybrid Spill-tree算法耗時(shí)次之，而本文算法耗時(shí)最短，且隨著圖像特征點(diǎn)的增加，算法的優(yōu)勢(shì)更加明顯。這是因?yàn)楸疚姆椒ú捎昧硕M(jìn)制的匹配方式，在匹配時(shí)可以通過(guò)異或方式計(jì)算特征間的距離，比傳統(tǒng)的計(jì)算歐式距離的方法計(jì)算量更小。

表3　特征提取算法耗時(shí)比較

7　結(jié)　論

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

[1]金光，徐偉. “吉林一號(hào)”小型高分辨率多光譜遙感衛(wèi)星[J]. 空間對(duì)地觀測(cè)工程與技術(shù)，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]陳彥彤，王紹舉. 高分辨遙感圖像目標(biāo)識(shí)別技術(shù)綜述[J]. 中國(guó)光學(xué)，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]張仲瑜，焦淑紅. 多特征融合的紅外艦船目標(biāo)檢測(cè)方法[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]田浩南，張葉. 基于邊緣及特征點(diǎn)匹配的立體圖像質(zhì)量評(píng)價(jià)[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ìn)的加速魯棒特征算法在特征匹配中的應(yīng)用[J]. 光學(xué) 精密工程，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遙感影像的車輛自動(dòng)檢測(cè)與運(yùn)動(dòng)參數(shù)估計(jì)[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]邵振峰，陳敏. 尺度旋轉(zhuǎn)以及亮度穩(wěn)健的高分辨率影像直線特征匹配[J]. 光學(xué) 精密工程，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]王志強(qiáng)，程紅，楊桄，等. 全局圖像配準(zhǔn)的目標(biāo)快速定位方法[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-)，男，遼寧沈陽(yáng)人，博士研究生，2012年于吉林大學(xué)獲得學(xué)士學(xué)位，主要從事模式識(shí)別及機(jī)器視覺(jué)方面的研究。E-mail: chenyantong1@yeah.net

導(dǎo)師簡(jiǎn)介：

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

(版權(quán)所有未經(jīng)許可不得轉(zhuǎn)載)

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，F(xiàn)ineMechanicsandPhysics，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.

國(guó)家863高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(No.2012AA121502)

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

TP753

A

10.3788/OPE.20162409.2310