基于特征场景的快速图像匹配方法

收稿日期:2011-01-17;修回日期:2011-03-09。

基金项目:住房和城乡建设部软科学研究项目（2010-K9-43）；吉林省教育厅“十一五”科学技术研究项目（吉教科合字［2010］第303号）。

作者简介:杨磊（1986-）,男，湖北武汉人，硕士研究生，主要研究方向：计算机视觉、图像处理; 郭秀娟（1961-），女，吉林德惠人，教授，博士，主要研究方向：人工智能、数据挖掘、数值计算、GIS。

文章编号:1001-9081（2011）07-1850-03doi:10.3724/SP.J.1087.2011.01850

（吉林建筑工程学院 电气与电子信息工程学院,长春 130018）

（）

摘 要:提出基于特征场景的快速图像匹配方法，一定程度上解决了基于主流的局部特征匹配算法无法描述全局特征的问题。通过采集场景图像，使用主成分分析（PCA）重构特征场景，进而用于匹配范围划分；在划分后的匹配范围中使用SURF算法进行快速局部特征匹配。实验结果表明，此方法结合大尺度全局特征和尺度不变局部特征，使近似目标的区分能力得到了加强。在鲁棒性和时效性上,此方法达到了较好的平衡，拓展了主流局部特征匹配方法的应用范围。最后提出了对本方法的改进方向，表明了此方法的可拓展性。

关键词:特征场景；主成分分析；全局特征；SURF；匹配范围划分

中图分类号:TP391.4文献标志码:A

Fast image matching method based on eigen-scene

YANG Lei, GUO Xiu-juan

（School of Electrical and Electronic Information Engineering, Jilin Institute of Architecture and Civil Engineering, ChangchunJilin 130018,China）

Abstract: In this paper, a new method based on eigen-scene for fast image matching was presented, and it could solve the problem that mainstream matching algorithm with local features cannot describe the global features. By extracting scene images, the eigen-scene using Principal Component Analysis （PCA） could be reconstructed, and then it could be used for matching scope division. In the divided matching scope, SURF algorithm was used to match fast local features. The experimental results indicate this method combines the large scale global features and scale invariant local features so that the discrimination ability is enhanced for similar object. The robustness and timeliness of this method achieve good balance so that it extends the application fields of mainstream matching method with local features. In the end, improvement direction is suggested for this paper, which shows the scalability of this method.

Key words: eigen-scene;Principal Component Analysis （PCA）;global feature;Speeded-Up Robust Features （SURF）;matching scope division

0 引言

目前，主流的图像匹配算法都是试图提取目标的某种条件下的不变量［1］作为特征，随后在不同的图像中匹配这些特征，以达到对目标进行识别的目的，因此特征的提取是图像匹配的关键。随着尺度空间理论全面引入图像领域［2］，不同尺度下提取的特征可分为大尺度的全局特征和小尺度的局部特征两大类。由于形成线性尺度空间的孔径函数的核函数是唯一的，使得基于线性尺度空间的局部特征的匹配算法有了巨大的发展，最具代表性的是Lowe于1999年在ICCV上提出［3］并于2004年发展成熟［4］的尺度不变特征变换（Scale-Invariant Feature Transform,SIFT）算法。

由于SIFT算法拥有抵抗尺度、旋转变化，以及部分抗光照均匀变化的能力，研究人员已尝试将其应用于局域图像导航避障［5］领域，但该算法存在着特征提取及匹配速度慢，在灰度变化相似的区域产生误匹配的缺陷。这两点极大地限制了该算法的应用场合，尤其是在讲求实时性且存在明显视角变化的图像导航中的应用，使得该算法更多地用于高质量图像的静态查找。学者们因此从降低描述器维数［6］，及增强描述器鲁棒性［7］两方面对其进行了有效的改进。然而，目前基于主流的局部特征算法的匹配方法往往为保证局部特征的尺度不变性而舍弃全局特征，只是在底层图像进行梯度搜索，因而无法很好地完成上层视觉的任务。

1 算法描述

1.1 基于局部匹配的SURF算法的描述

鲁棒特征加速（Speeded-Up Robust Features,SURF）是Bay等人于2006年在ECCV上提出的针对SIFT运算速度慢而进行改进的算法［8］，已被研究人员用于快速虹膜检测［9］。SURF是目前最成功的针对SIFT改进的算法之一，计算速度较SIFT快，且鲁棒性较SIFT并未有较明显地下降。

1.1.1 基于Hessian矩阵的快速特征点检测器方案

令图像I中任意一点X（x,y），则X点处尺度为δ的Hessian矩阵Η（x,y,δ）可定义为：

H（x,y,δ）（1）

定义*为卷积运算，则（1）中各项可表示为：

Lxx（x,y,δ）*I（x,y）

Lyy（x,y,δ）*I（x,y）

Lxy（x,y,δ）*I（x,y）（2）

当det（H）>0时，x点处存在极值，且Hessian阵正定时为极小值，负定时为极大值。

SURF采用了积分图像计算盒形滤波器对高斯拉普拉斯核（Laplacian Of Guass,LoG）进行快速逼近，因此在形成图像尺度空间时可令图像保持不变，对相应尺度的滤波器进行亚抽样，产生滤波器尺度金字塔，明显提高了特征点提取速度。考虑到误差的产生，可由基础尺度下的LoG与高斯差（Difference Of Gaussian,DOG）的F范数比值得到约束系数：

≈0.9（3）

由式（4）进行约束以克服近似误差：

det（Happroximation）DxxDyy－（0.9Dxy）2（4）

在尺度空间进行非极值抑制过程中，通过设定特征点响应的最小阈值来提取鲁棒性强的特征点，舍弃鲁棒性差的特征点，以此减小后续描述的计算量，并保证所提取的特征点对尺度变化具有较强的鲁棒性。

1.1.2 基于Haar小波的局部特征描述器方法

SURF描述器采用x方向和y方向的Haar小波，以获得图像沿x方向和y方向的梯度变化所产生的响应。类似SIFT，SURF也对特征点周围区域通过高斯平滑对响应强度进行加权，并以响应最强烈的π/3区域的梯度方向作为区域响应的方向。由于限定Haar小波在4×4的局部区域内获得响应，每个响应点的响应分别存储为x方向和y方向响应之和，以及x方向和y方向响应的绝对值之和，因此每个局部区域描述器最终会存储为一个4×4×464维的描述器向量，也即SURF-64方案：

Vi（∑dx1,∑dy1,∑dx1,∑dy1,…,∑dx16,

∑dy16,∑dx16,∑dy16）Τ（5）

1.2 基于全局匹配的PCA重构特征场景算法

主成分分析（Principal Component Analysis,PCA）作为对高维数据进行降维，并提取其主要信息的有效方法〖10〗被广泛地应用于数据量较大且往往呈指数型分布的图像领域。由PCA重构的特征场景，可用于描述场景中的全局性信息。

令X′为一个m×n维矩阵，其中m为每次抽样所采集的各标定维度产生的原始信息，n为抽样次数，为均值矩阵，均值矩阵中每一列各行的元素都是X′中该行所有元素产生的均值，可定义协方差矩阵Cx为：

Cx（6）

若P为投影矩阵，Y为映射矩阵，Pi为P的行向量，k为映射基的个数，Xi为X的列向量：

（7）

当Y按照相应特征值的大小重排时，对应较大特征值的Xi称为X的主成分，当信噪比大于1时，主成分体现为信息。设Y为经过PCA后的特征图像矩阵，Y的列向量Yi为对应不同特征值归一化后的特征向量，当X为均值场景，特征场景可按下式重构：

ESλ1Y1+λ2Y2+…+λnYn+X（8）

现有同一目标在一系列场景下的图像X{Xi}，令X为体现X全局大致信息的均值图像，Y是X的协方差矩阵，P是Cx的投影矩阵，Cx经PCA后产生的包含主要细节信息的主成分图像。若需要对S进行识别，则有如下表示：

DsPPΤ－Y （9）

Y表示X在特征空间的细节部分的投影，Ds所体现的应为S与X场景在特征空间投影后体现出的差异，这个差异可表示为Ds的欧氏范数DsEuclid。存在系列场景（S1,S2,…，Sn），当DsiEuclid最小时，本质上相当于主分量和均值重构后的特征场景与Si最相似。

2 基于特征场景的图像匹配方法

场景匹配需要综合场景信息进行场景理解，在此基础上进行带有先验（prior）性的目标搜索，即在全局匹配划分的范围中进行精确查找。然而，大尺度特征不同于基于像素级灰度变化的局部特征，由于变化缓慢而难以作为局部特征被局部特征匹配算法所提取。而SURF/SIFT为保证特征点尺度不变几乎完全舍弃了大尺度全局特征，因此无法抵抗明显视角变化，并且使得误匹配现象在目标密集、灰度变化相似且视角多变的场景下尤为明显。

为克服上述缺陷，应当在不影响局部匹配算法鲁棒性的前提下对全局尺度特征的进行综合描述。由于PCA重构特征场景过程中的形成的均值图像中包含了整体信息，主分量图像中包含了大尺度细节信息，因而可以描述全局特征。由于PCA损失了局部细节信息，需要采用基于局部特征匹配的SURF算法完成精确匹配的步骤，因此形成了基于特征场景划分匹配范围，而后SURF快速精确匹配的方法，最终达到局域图像定位与导航的目的。

快速匹配方案流程如图1所示。

图1 快速匹配方案流程

3 实拍实验及其结果分析

3.1 实验设计

此方案应用于建筑物较多并有明显的视角变化，距离变化以及光照、天气变化的局域。因此选择了某校园场景内A、B两栋外观相似的建筑物进行实拍，分别对光照强烈时段、光照较弱时段和阴雨天时段进行取景。场景范围为两建筑物的正面150°内视角所观察到的景象。将每个建筑物的正面都分为5个视角区域，每次取景都在固定位置对该侧进行拍照，并在拍照中加入不超过±10°的视角变化以模拟实际应用的场景。用于构成特征场景库的图像共计450幅，用于构成局部基准库的图像共有121幅。本次测试图片为三种光照条件下对景物以不同视角拍摄的共计为30幅，每个区域3张图片，编号规则：左上角第一幅图为A（1），左上角第二幅图为A（2），依此类推至右下角最后一幅图为B（3）号。其中A（1）至A（15）为A楼场景，B（1）至B（15）为B楼场景。如图2。

图2 测试图片

图3 用训练场景数据库重构的特征场景

3.2 实验结果及分析

A匹配数据：A场景为A（1）至A（15），匹配结果根据场景编号进行True（1）或False（0）判定，如图4。

图4 A场景匹配

B匹配数据：B场景为B（1）至B（15），匹配结果根据场景编号进行True（1）或False（0）判定，如图5。

图5 B场景匹配

匹配成功率：A场景的A（4）以及B场景的B（11）、B（15）均发生了首次误匹配，其中B（15）经过3轮自校正环节最终得到正确的匹配，A（4）及B（11）校正失败。A（4）发生了场景内不同视角区域间的误匹配，属于场景内误匹配，是由于视角区域边缘处的场景区分度小，因此重构的特征场景难以描述此类场景的特征；可通过提高图像的分辨率加以解决，但这将导致运算速度明显下降。B（11）发生了不同场景目标的误匹配，属场景间的误匹配，是由于光照变化强烈且距离过远使小尺度特征难以提取所致；可通过训练更多场景图像重构鲁棒性更强的特征场景解决，但是需要更多的主分量描述细节，将使数据维数提高引发“高维灾难”并直接导致匹配速度下降。

匹配速度：各场景目标需匹配局部特征库和特征场景共计131幅图，在C/Matlab平台上平均匹配用时2.32s，快于标准的SIFT算法，可以满足类似人类行走速度（1.5m/s）条件下的导航避障等应用；这是由于SURF的匹配速度大约3倍快于SIFT且采用了粗匹配划分匹配范围所致。由于范围划分只与特征场景数量有关，可以预见，当目标越多，局部特征库越大时，本方案的速度优势将越明显。但是若发生了类似B（11）的情况，则需要设定时间阈值，以防止时间大量消耗在反复的自校正过程上，导致时效性大大降低。

4 结语

本文针对动态场景中目标局部特征相似，视角变化明显，可能导致局部匹配算法误匹配的问题，建立了基于特征场景，并进行搜索范围划分，用尺度不变的局部特征匹配算法进行精确匹配。经过实景测试，该方法在匹配成功率和匹配速度上达到了预期的效果。该方案在人力充足时将有较大的改进空间：1）结合广义普罗克拉斯特分析（Generalized Procrustes Analysis,GPA）与PCA，重构鲁棒性更强的特征场景，提升鲁棒性和匹配速度;2）采集场景显著特征，由主动外表模型（Active Appearance Model,AAM）［11］直接生成描述场景显著特征的特征模板，通过一系列特征模板进行局部查找，可极大提升鲁棒性。

参考文献:

［1］ 丁雪梅,王维雅,黄向东. 基于差分和特征不变量的运动目标检测和跟踪［J］ .光学精密工程,2007,15（4） : 570-576.

［2］ LINDEBERGE T. Scale-space theory: A basic tool for analysing structures at different scales［J］. Journal of Applied Statistics, 1994,21（2）:224-270.

［3］ LOWE D G. Object recognition from local scale-invariant features［C］// Proceedings of the 7th International Conference on Computer Vision.Washington, DC: IEEE Computer Society, 1999:1150-1157.

［4］ LOWE D G. Distinctive imag e features from scale invariant keypoints［J］. International Journal of Computer Vision, 2004, 60（2） : 91-110.

［5］ CHAVES A, GUSTAFUSON D. Vision-based obstacle avoidance using SIFT features［C］//Proceedings of the 5th International Symposium on Advances in Visual Computing. Berlin: Springer-Verlag,2009:550-557.

［6］ KEY, SUKTHANKA R. PCA-SIFT: A more distinctive representation for local image descriptors〖C〗// IEEE Conference on Computer Vision and Pattern Recognition.New York:IEEE,2004:506-513.

［7］ 纪华,吴元昊,孙宏海,等. 结合全局信息的SIFT 特征匹配算法［J］.光学精密工程,2009,17（2）:439-444.

［8］ BAY H, TUVTELLARS T, GOOL L V. SURF: Speeded up robust features［C］// Proceedings of the European Conference on Computer Vision, LNCS 3951.Berlin:Springer,2006:404-417.

［9］ MEHROTRA H,MAJHI B,GUPTA P. Annular iris recognition using SURF［C］// Proceedings of the International Conference on Pattern Recognition and Machine Intelligence, LNCS 5909. Berlin:Springer,2009:464-469.

［10］ SHLENS J. A tutorial on principal component analysis［M］.2nd ed.San Diego:University of California,2005:1-13.

［11］ COOTES T,EDWARDS G J,TAYLOR C J. Active appearance models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23（6）:681-68.