李校林，劉 欣

(1.重慶郵電大學(xué)，重慶400065;2.重慶信科設(shè)計(jì)有限公司，重慶400065)

基于ASIFT的圖像快速匹配算法

李校林1，2，劉 欣1

(1.重慶郵電大學(xué)，重慶400065;2.重慶信科設(shè)計(jì)有限公司，重慶400065)

ASIFT特征在圖像旋轉(zhuǎn)、尺度變換和視角變化的條件下具有良好的不變性，較傳統(tǒng)的SIFT算法具有完全的仿射不變性，且在圖像配準(zhǔn)中能夠獲得更多精確的匹配點(diǎn)。但是，ASIFT匹配效率比較低，耗時(shí)較長(zhǎng)?；贏SIFT的圖像快速匹配算法是結(jié)合基于BBF查詢機(jī)制的KD－Tree索引的近似最近鄰搜索即先建立數(shù)據(jù)集索引，然后進(jìn)行快速匹配的算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法比傳統(tǒng)的ASIFT圖像匹配算法和SIFT匹配算法在匹配速度、匹配精度方面優(yōu)勢(shì)明顯。

ASIFT;匹配效率;SIFT;BBF;KD－Tree

圖像匹配技術(shù)［1］是圖像處理中一項(xiàng)重要的技術(shù)，同時(shí)也是計(jì)算機(jī)視覺研究中一項(xiàng)非常重要的工作。隨著科學(xué)技術(shù)的發(fā)展，圖像匹配技術(shù)在醫(yī)學(xué)圖像處理分析、圖像三維重建、天氣預(yù)測(cè)、圖像數(shù)據(jù)庫檢索、圖像拼接、目標(biāo)識(shí)別等多個(gè)領(lǐng)域中都有廣泛的應(yīng)用。所謂圖像匹配，就是將相同或者不同場(chǎng)景的二幅或者多幅圖片在空間上進(jìn)行配準(zhǔn)。目前的圖像匹配方法主要有基于區(qū)域灰度的匹配方法［2］、基于圖像解析的匹配方法［3］以及基于特征的匹配方法［4］。其中最常用的是基于特征的圖像匹配方法，該方法通過對(duì)圖像特征點(diǎn)分析，提高圖像的匹配速度，且提取的圖像特征點(diǎn)對(duì)旋轉(zhuǎn)、亮度變化、尺度縮放保持不變性，對(duì)視角變化、仿射變化、噪聲也具有良好的穩(wěn)定性。

SIFT(Scale Invariant Feature Transform)算法［5－6］是1999年Lowe提出的，于2004年加以完善。SIFT算法將斑點(diǎn)檢測(cè)和特征矢量生成、特征點(diǎn)搜索匹配等步驟完整地結(jié)合在一起，能夠很好地解決環(huán)境因素、成像器材本身的成像特性因素、目標(biāo)遮擋等影響造成的圖像變形問題。但是SIFT在對(duì)一些目標(biāo)傾斜的圖片不能檢測(cè)到更多精確的特征點(diǎn)進(jìn)行配準(zhǔn)，并且存在錯(cuò)誤匹配，不能滿足實(shí)時(shí)配準(zhǔn)的要求。

ASIFT(Affine Scale Invariant Feature Transform)［7］是一種完全仿射不變的局部圖像特征提取算法，由Jean－Michel Morel和Guoshen Yu在2009年提出。ASIFT算法除了對(duì)旋轉(zhuǎn)、縮放、平移具有完全不變性以外，還對(duì)SIFT不具備的相機(jī)軸方向和相機(jī)角度方向具有完全不變性，所以ASIFT在仿射較大造成變形的圖像上能夠得到更多精準(zhǔn)的特征點(diǎn)，在配準(zhǔn)方面具有良好的效果。但由于算法本身計(jì)算復(fù)雜，所以算法存在運(yùn)算速度較慢、配準(zhǔn)重復(fù)、誤匹配等問題。所以，在實(shí)時(shí)性上存在一定缺陷。

通過對(duì)SIFT和ASIFT算法進(jìn)行深入研究，在ASIFT特征點(diǎn)匹配階段結(jié)合基于BBF(Best－Bin－First)查詢機(jī)制的KD－Tree索引的最近鄰搜索策略實(shí)現(xiàn)圖像快速匹配。KD－Tree的BBF查詢算法的引入能夠較大程度地減少計(jì)算量，大大提高ASIFT的匹配速度。

1 ASIFT匹配算法介紹

ASIFT算法是在SIFT算法的基礎(chǔ)上提出，該算法對(duì)攝像機(jī)的經(jīng)度角和緯度角同樣具有完全不變性，這就解決了傳統(tǒng)SIFT算法在仿射較大引起的圖片之間匹配精確度不足的缺陷。

1.1 ASIFT算法原理

1.1.1 攝像機(jī)仿射模型

攝像機(jī)采集到的空間平面景物都可以用仿射模型描述為

式中:參數(shù)u表示最終得到數(shù)字圖像;u0表示景物平面圖像;S1表示采樣操作;G1表示高斯卷積;T和R分別表示由攝像機(jī)引起的圖像平移和旋轉(zhuǎn)變換;A表示空間平面景物的仿射變換。

以上模型中A可以簡(jiǎn)化為一個(gè)仿射變換。任何一個(gè)線性仿射變換由于仿射矩陣不存在相似矩陣，所以只存在唯一的分解式子

式中:λ＞0，λt為A的行列式;φ∈［0，π);Tt表示傾斜變換的矩陣，且第一個(gè)特征值t＞1，第二個(gè)特征值t=1;Ri表示旋轉(zhuǎn)變換的矩陣。攝像機(jī)仿射模型由圖1給出，其中參數(shù)u表示平面景物圖像，右上角小平行四邊形代表觀看u的攝像機(jī)的角度位置，參數(shù)φ和θ=arccos(1/t)，分別為攝像機(jī)的經(jīng)度角和緯度角，參數(shù)λ為縮放尺度變化。

圖1 攝像機(jī)仿射模擬

1.1.2 不同傾斜角度拍攝仿射模型

將攝像機(jī)通過不同傾斜角度得到的2張圖片進(jìn)行仿射模擬。用A和B分別表示得到的2張不同的圖片，并有u1(x，y)=u(A(x，y))，u2(x，y)=u(B(x，y))。那么二張圖片的變換矩陣BA－1可以描述為

1.2 ASIFT算法主要步驟

1)得到攝像機(jī)經(jīng)度角和緯度角采樣序列

ASIFT算法首先利用式(3)對(duì)攝像機(jī)的經(jīng)度角φ和緯度角θ進(jìn)行采集，來模擬所有可能由攝像機(jī)光軸造成的仿射變形來實(shí)現(xiàn)圖像變換。其中緯度角的采樣對(duì)應(yīng)傾斜t，且遵循等比數(shù)列采樣的原則，即按1，a，a2，…，an采樣，a＞1，a =時(shí)，算法精確度可以達(dá)到最佳，所以在本文中取該值，另外n≥5。經(jīng)度角的采集隨傾斜t變化，且遵循等差數(shù)列采樣原則，即按0，b/t，…，kb/t采樣，取b= 72°［7］，k為滿足條件kb/t＜π的最后一個(gè)整數(shù)值。

2)將待匹配圖像進(jìn)行傾斜旋轉(zhuǎn)變換

利用采用得到的參數(shù)序列，根據(jù)式(1)首先將圖像進(jìn)行經(jīng)度角度為φ的旋轉(zhuǎn)變換，將旋轉(zhuǎn)變換后的圖像進(jìn)行模擬傾斜，最終得到仿射變換下的模擬圖片，其中傾斜t=|1/cosθ|。

3)圖像特征點(diǎn)檢測(cè)和匹配

將生成的模擬圖片根據(jù)SIFT算法進(jìn)行特征點(diǎn)檢測(cè)和圖片匹配。

1.3 ASIFT算法優(yōu)缺點(diǎn)

綜上可知，ASIFT算法在仿射較大圖像之間的匹配性能優(yōu)越，也能夠獲取更多精確的匹配特征點(diǎn)。但是，ASIFT算法在匹配階段采用的傳統(tǒng)SIFT用的全局最近鄰搜索方式，該方式?jīng)]有利用數(shù)據(jù)集本身包含的任何結(jié)構(gòu)信息，搜索效率比較低，所以造成ASIFT算法在匹配效率上比較低。

2 基于BBF查詢機(jī)制的KD－Tree近似最近鄰搜索算法

2.1 KD－Tree算法描述

KD－Tree［8］(K－Demension Tree)是數(shù)據(jù)點(diǎn)在K維空間中劃分的一種數(shù)據(jù)結(jié)構(gòu)。通過建立有效的數(shù)據(jù)索引結(jié)構(gòu)來大大加快檢索的速度。該算法由Jon Louis Bentley在1975年提出。它與二叉樹的不同點(diǎn)是，它的每個(gè)節(jié)點(diǎn)表示K維空間的一個(gè)點(diǎn)，且每一層都會(huì)根據(jù)該層的分辨器對(duì)應(yīng)的對(duì)象做出分枝決策。

2.2 基于BBF的KD－Tree查詢算法

標(biāo)準(zhǔn)的KD－Tree算法主要分為KD－Tree的構(gòu)建和數(shù)據(jù)最近鄰查詢。標(biāo)準(zhǔn)KD－Tree的最近鄰查詢算法，并沒有考慮查詢路徑數(shù)據(jù)本身的性質(zhì)，所以該算法不適合高維度數(shù)據(jù)的應(yīng)用?？梢灾?，ASIFT描述矢量長(zhǎng)度為128，所以采用傳統(tǒng)的KD－Tree最近鄰算法，搜索效率會(huì)下降，并且會(huì)接近無窮搜索算法，造成圖像匹配效率較低。而通過基于BBF機(jī)制的KD－Tree查詢算法，能夠滿足高維數(shù)據(jù)下對(duì)檢索速度的要求，大大提高了圖片匹配的效率。

2.2.1 KD－Tree構(gòu)建［9］過程

1)確定split域的值。通過計(jì)算數(shù)據(jù)點(diǎn)在x，y維度上的數(shù)據(jù)方差，取方差值最大的維度作為split域的值。

2)確定Node－data域。根據(jù)得到的split域的值，將數(shù)據(jù)在該維度上排序，根據(jù)數(shù)據(jù)的中值得到Node－data域數(shù)據(jù)點(diǎn)，這樣，就確定了該節(jié)點(diǎn)的分割超面。

3)確定左、右子空間。分割超面把整個(gè)空間分為兩部分，分割超面左邊的點(diǎn)為左子空間，分割超面右邊的點(diǎn)為右子空間。

4)然后根據(jù)左子空間和右子空間可以得到一級(jí)子節(jié)點(diǎn)，再分別將空間和數(shù)據(jù)集進(jìn)一步細(xì)分，直到空間中只包含一個(gè)數(shù)據(jù)點(diǎn)。

2.2.2 基于BBF機(jī)制的KD－Tree查詢算法［9］流程

1)根據(jù)數(shù)據(jù)點(diǎn)集建立KD－Tree。

2)建立優(yōu)先級(jí)隊(duì)列，首先把KD－Tree的根節(jié)點(diǎn)壓入隊(duì)列。

3)檢測(cè)該樹節(jié)點(diǎn)表示的空間中是否有更好的最近鄰，提取出最優(yōu)先節(jié)點(diǎn)。

4)繼續(xù)檢索該最優(yōu)先節(jié)點(diǎn)，重復(fù)步驟2)，直到優(yōu)先隊(duì)列為空。

3 算法實(shí)現(xiàn)及結(jié)果分析

本文利用C++語言在VS2010平臺(tái)上驗(yàn)證該算法的性能，算法驗(yàn)證圖片取自攝像機(jī)的拍攝。在這里，利用傾斜角度較大的圖片進(jìn)行了圖像匹配。匹配結(jié)果如圖2和圖3，算法性能參數(shù)見表1。

圖2 基于全局搜索的SIFT算法圖片匹配

從圖2中看出，圖片在匹配過程中，得到的匹配特征點(diǎn)比較少，匹配精確度較差，存在較多的誤匹配。與圖3對(duì)比，明顯看出，ASIF算法和SIFT算法相比，不僅能夠檢測(cè)到更多的匹配特征點(diǎn)，而且在特征點(diǎn)匹配精度上也具有突出的優(yōu)勢(shì)。除此之外，從表1的數(shù)據(jù)可以看出，基于KD－Tree BBF查詢的ASIFT算法匹配速度比基于全局搜索的ASIFT算法在圖片匹配階段時(shí)間將近縮短一半，該算法綜合了圖片在匹配精度和匹配效率兩方面，是一種比較出色的匹配算法。

圖3 結(jié)合KD－Tree BBF查詢的ASIFT算法圖片匹配

表1 算法性能比較

4 小結(jié)

本文研究了基于BBF查詢機(jī)制的KD－Tree搜索和AISF圖像匹配算法。在提取圖像特征點(diǎn)和生成描述圖像的特征向量前，采用了比SIFT算法更具精準(zhǔn)的ASIFT算法。在圖像匹配特征點(diǎn)階段，采取結(jié)合BBF KD－Tree查詢算法，提升圖像在匹配階段的耗時(shí)。通過二者的結(jié)合，從而形成了一種快速的圖像匹配技術(shù)。實(shí)驗(yàn)結(jié)果顯示，該算法同時(shí)兼顧了圖像匹配精確性和圖像匹配效率，且更具有完全的仿射不變性。圖像匹配技術(shù)目前是圖像處理應(yīng)用領(lǐng)域一項(xiàng)重要的技術(shù)，在后續(xù)的研究工作中，該算法的匹配實(shí)時(shí)性和技術(shù)應(yīng)用將是下一步的重點(diǎn)。

［1］張銳娟.圖像配準(zhǔn)理論及算法研究［D］.西安:西安電子科技大學(xué)，2009.

［2］MORTANIM，SATIONH F.Image templatematching base on ratio ofmean and cent－ral pixel in local area［EB/OL］.［2013－06－02］.http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=829671.

［3］BARBARA Z，JAN F.Image registration methods:a survery［J］.Image and Vison Computing，2003，21(11):97－100.

［4］王宏力，賈萬波.圖像匹配算法研究綜述［J］.計(jì)算機(jī)技術(shù)與應(yīng)用，2008(6):17－19.

［5］LOWE D.Object recognition from local scale－invariant features［C］// Proc.International Journal of Computer Vision.［S.l.］:IEEE Press，2004:1150－1157.

［6］LOWE D.Distinctive image features from scale invariant keypoints［J］.International Journal of Computer Vision，2004(60):91－110.

［7］MOREL J，YU G.ASIFT:a new framework for fully affine invariant image comparison［J］.SIAM Journal on Imaging Sciences，2009(2): 438－469.

［8］BENTLEY J.Multidimensional binary search trees used for associative searching［J］.Commun.ACM，1975，18(2):509－517.

［9］王永明，王貴錦.圖像局部不變性特征與描述［M］.北京:國防工業(yè)出版社，2010.

Fast Image M atching Algorithm Based on ASIFT

LIXiaolin1，2，LIU Xin1
(1.Chongqing University of Posts and Telecommunications，Chongqing 400065，China; 2.Chongqing Information Technology Designing Co.Ltd.，Chongqing 400065，China)

ASIFT in image rotation，scaling and perspective changing conditions have good invariance，compared with the traditional SIFT algorithm，ASIFT have fully affine invariant，and in the image registration，ASIFT can getmore precisematching points.But，ASIFTmatching efficiency is relatively low and time－consuming.Based ASIFT imagematching algorithm is a combination of BBF fast KD－Tree indexes approximate nearest neighbor search for a data set index，then a quick match.Experimental results show that the improved algorithm than the traditional ASIFT imagematching algorithm and SIFT imagematching algorithm in thematching rate，matching accuracy obvious advantages.

ASIFT;matching efficiency;SIFT;BBF;KD－Tree

TP391.41

A

李校林(1968— )，碩士生導(dǎo)師，正高級(jí)工程師，主要研究方向?yàn)樾乱淮苿?dòng)通信技術(shù)、物聯(lián)網(wǎng)與視頻監(jiān)控技術(shù)、天線與電波傳播;

?? 雯

2013－08－28

【本文獻(xiàn)信息】李校林，劉欣.基于ASIFT的圖像快速匹配算法［J］.電視技術(shù)，2014，38(13).

科技型中小企業(yè)技術(shù)創(chuàng)新基金項(xiàng)目(11C26215113601)

劉 欣(1990— )，碩士生，主研智能視頻監(jiān)控、圖像處理。