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

李校林，刘 欣

(1.重庆邮电大学，重庆400065;2.重庆信科设计有限公司，重庆400065)

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

李校林1，2，刘 欣1

(1.重庆邮电大学，重庆400065;2.重庆信科设计有限公司，重庆400065)

ASIFT特征在图像旋转、尺度变换和视角变化的条件下具有良好的不变性，较传统的SIFT算法具有完全的仿射不变性，且在图像配准中能够获得更多精确的匹配点。但是，ASIFT匹配效率比较低，耗时较长。基于ASIFT的图像快速匹配算法是结合基于BBF查询机制的KD－Tree索引的近似最近邻搜索即先建立数据集索引，然后进行快速匹配的算法。实验结果表明，改进的算法比传统的ASIFT图像匹配算法和SIFT匹配算法在匹配速度、匹配精度方面优势明显。

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

图像匹配技术［1］是图像处理中一项重要的技术，同时也是计算机视觉研究中一项非常重要的工作。随着科学技术的发展，图像匹配技术在医学图像处理分析、图像三维重建、天气预测、图像数据库检索、图像拼接、目标识别等多个领域中都有广泛的应用。所谓图像匹配，就是将相同或者不同场景的二幅或者多幅图片在空间上进行配准。目前的图像匹配方法主要有基于区域灰度的匹配方法［2］、基于图像解析的匹配方法［3］以及基于特征的匹配方法［4］。其中最常用的是基于特征的图像匹配方法，该方法通过对图像特征点分析，提高图像的匹配速度，且提取的图像特征点对旋转、亮度变化、尺度缩放保持不变性，对视角变化、仿射变化、噪声也具有良好的稳定性。

SIFT(Scale Invariant Feature Transform)算法［5－6］是1999年Lowe提出的，于2004年加以完善。SIFT算法将斑点检测和特征矢量生成、特征点搜索匹配等步骤完整地结合在一起，能够很好地解决环境因素、成像器材本身的成像特性因素、目标遮挡等影响造成的图像变形问题。但是SIFT在对一些目标倾斜的图片不能检测到更多精确的特征点进行配准，并且存在错误匹配，不能满足实时配准的要求。

ASIFT(Affine Scale Invariant Feature Transform)［7］是一种完全仿射不变的局部图像特征提取算法，由Jean－Michel Morel和Guoshen Yu在2009年提出。ASIFT算法除了对旋转、缩放、平移具有完全不变性以外，还对SIFT不具备的相机轴方向和相机角度方向具有完全不变性，所以ASIFT在仿射较大造成变形的图像上能够得到更多精准的特征点，在配准方面具有良好的效果。但由于算法本身计算复杂，所以算法存在运算速度较慢、配准重复、误匹配等问题。所以，在实时性上存在一定缺陷。

通过对SIFT和ASIFT算法进行深入研究，在ASIFT特征点匹配阶段结合基于BBF(Best－Bin－First)查询机制的KD－Tree索引的最近邻搜索策略实现图像快速匹配。KD－Tree的BBF查询算法的引入能够较大程度地减少计算量，大大提高ASIFT的匹配速度。

1 ASIFT匹配算法介绍

ASIFT算法是在SIFT算法的基础上提出，该算法对摄像机的经度角和纬度角同样具有完全不变性，这就解决了传统SIFT算法在仿射较大引起的图片之间匹配精确度不足的缺陷。

1.1 ASIFT算法原理

1.1.1 摄像机仿射模型

摄像机采集到的空间平面景物都可以用仿射模型描述为

式中:参数u表示最终得到数字图像;u0表示景物平面图像;S1表示采样操作;G1表示高斯卷积;T和R分别表示由摄像机引起的图像平移和旋转变换;A表示空间平面景物的仿射变换。

以上模型中A可以简化为一个仿射变换。任何一个线性仿射变换由于仿射矩阵不存在相似矩阵，所以只存在唯一的分解式子

式中:λ＞0，λt为A的行列式;φ∈［0，π);Tt表示倾斜变换的矩阵，且第一个特征值t＞1，第二个特征值t=1;Ri表示旋转变换的矩阵。摄像机仿射模型由图1给出，其中参数u表示平面景物图像，右上角小平行四边形代表观看u的摄像机的角度位置，参数φ和θ=arccos(1/t)，分别为摄像机的经度角和纬度角，参数λ为缩放尺度变化。

图1 摄像机仿射模拟

1.1.2 不同倾斜角度拍摄仿射模型

将摄像机通过不同倾斜角度得到的2张图片进行仿射模拟。用A和B分别表示得到的2张不同的图片，并有u1(x，y)=u(A(x，y))，u2(x，y)=u(B(x，y))。那么二张图片的变换矩阵BA－1可以描述为

1.2 ASIFT算法主要步骤

1)得到摄像机经度角和纬度角采样序列

ASIFT算法首先利用式(3)对摄像机的经度角φ和纬度角θ进行采集，来模拟所有可能由摄像机光轴造成的仿射变形来实现图像变换。其中纬度角的采样对应倾斜t，且遵循等比数列采样的原则，即按1，a，a2，…，an采样，a＞1，a =时，算法精确度可以达到最佳，所以在本文中取该值，另外n≥5。经度角的采集随倾斜t变化，且遵循等差数列采样原则，即按0，b/t，…，kb/t采样，取b= 72°［7］，k为满足条件kb/t＜π的最后一个整数值。

2)将待匹配图像进行倾斜旋转变换

利用采用得到的参数序列，根据式(1)首先将图像进行经度角度为φ的旋转变换，将旋转变换后的图像进行模拟倾斜，最终得到仿射变换下的模拟图片，其中倾斜t=|1/cosθ|。

3)图像特征点检测和匹配

将生成的模拟图片根据SIFT算法进行特征点检测和图片匹配。

1.3 ASIFT算法优缺点

综上可知，ASIFT算法在仿射较大图像之间的匹配性能优越，也能够获取更多精确的匹配特征点。但是，ASIFT算法在匹配阶段采用的传统SIFT用的全局最近邻搜索方式，该方式没有利用数据集本身包含的任何结构信息，搜索效率比较低，所以造成ASIFT算法在匹配效率上比较低。

2 基于BBF查询机制的KD－Tree近似最近邻搜索算法

2.1 KD－Tree算法描述

KD－Tree［8］(K－Demension Tree)是数据点在K维空间中划分的一种数据结构。通过建立有效的数据索引结构来大大加快检索的速度。该算法由Jon Louis Bentley在1975年提出。它与二叉树的不同点是，它的每个节点表示K维空间的一个点，且每一层都会根据该层的分辨器对应的对象做出分枝决策。

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

标准的KD－Tree算法主要分为KD－Tree的构建和数据最近邻查询。标准KD－Tree的最近邻查询算法，并没有考虑查询路径数据本身的性质，所以该算法不适合高维度数据的应用。可以知道，ASIFT描述矢量长度为128，所以采用传统的KD－Tree最近邻算法，搜索效率会下降，并且会接近无穷搜索算法，造成图像匹配效率较低。而通过基于BBF机制的KD－Tree查询算法，能够满足高维数据下对检索速度的要求，大大提高了图片匹配的效率。

2.2.1 KD－Tree构建［9］过程

1)确定split域的值。通过计算数据点在x，y维度上的数据方差，取方差值最大的维度作为split域的值。

2)确定Node－data域。根据得到的split域的值，将数据在该维度上排序，根据数据的中值得到Node－data域数据点，这样，就确定了该节点的分割超面。

3)确定左、右子空间。分割超面把整个空间分为两部分，分割超面左边的点为左子空间，分割超面右边的点为右子空间。

4)然后根据左子空间和右子空间可以得到一级子节点，再分别将空间和数据集进一步细分，直到空间中只包含一个数据点。

2.2.2 基于BBF机制的KD－Tree查询算法［9］流程

1)根据数据点集建立KD－Tree。

2)建立优先级队列，首先把KD－Tree的根节点压入队列。

3)检测该树节点表示的空间中是否有更好的最近邻，提取出最优先节点。

4)继续检索该最优先节点，重复步骤2)，直到优先队列为空。

3 算法实现及结果分析

本文利用C++语言在VS2010平台上验证该算法的性能，算法验证图片取自摄像机的拍摄。在这里，利用倾斜角度较大的图片进行了图像匹配。匹配结果如图2和图3，算法性能参数见表1。

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

从图2中看出，图片在匹配过程中，得到的匹配特征点比较少，匹配精确度较差，存在较多的误匹配。与图3对比，明显看出，ASIF算法和SIFT算法相比，不仅能够检测到更多的匹配特征点，而且在特征点匹配精度上也具有突出的优势。除此之外，从表1的数据可以看出，基于KD－Tree BBF查询的ASIFT算法匹配速度比基于全局搜索的ASIFT算法在图片匹配阶段时间将近缩短一半，该算法综合了图片在匹配精度和匹配效率两方面，是一种比较出色的匹配算法。

图3 结合KD－Tree BBF查询的ASIFT算法图片匹配

表1 算法性能比较

4 小结

本文研究了基于BBF查询机制的KD－Tree搜索和AISF图像匹配算法。在提取图像特征点和生成描述图像的特征向量前，采用了比SIFT算法更具精准的ASIFT算法。在图像匹配特征点阶段，采取结合BBF KD－Tree查询算法，提升图像在匹配阶段的耗时。通过二者的结合，从而形成了一种快速的图像匹配技术。实验结果显示，该算法同时兼顾了图像匹配精确性和图像匹配效率，且更具有完全的仿射不变性。图像匹配技术目前是图像处理应用领域一项重要的技术，在后续的研究工作中，该算法的匹配实时性和技术应用将是下一步的重点。

［1］张锐娟.图像配准理论及算法研究［D］.西安:西安电子科技大学，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］.计算机技术与应用，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］.北京:国防工业出版社，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— )，硕士生导师，正高级工程师，主要研究方向为新一代移动通信技术、物联网与视频监控技术、天线与电波传播;

�� 雯

2013－08－28

【本文献信息】李校林，刘欣.基于ASIFT的图像快速匹配算法［J］.电视技术，2014，38(13).

科技型中小企业技术创新基金项目(11C26215113601)

刘 欣(1990— )，硕士生，主研智能视频监控、图像处理。