PCA-SIFT特征匹配算法研究

李　钦，游　雄，李　科，张彦喜

(1.郑州测绘学院，河南 郑州 450052；2.65014部队，辽宁 沈阳 110000)



PCA-SIFT特征匹配算法研究

李钦1，游雄1，李科1，张彦喜2

(1.郑州测绘学院，河南 郑州 450052；2.65014部队，辽宁 沈阳 110000)

摘要：SIFT特征具有旋转、尺度和明暗变化的不变性，在图像匹配中得到广泛应用。针对SIFT特征匹配中耗时长、匹配点对少、准确率低的问题，提出PCA-SIFT特征匹配的方法。使用更加精简的方法构建特征点描述向量，通过预先构建的投影矩阵对描述向量进行主成分分析，降低描述向量的维度从而提高了特征匹配的速度，同时降维也对描述向量进行了去噪提纯，使得匹配更加准确。实验证明，利用PCA-SIFT特征进行匹配在降低匹配耗时的同时，增加了匹配点对，匹配准确率也得到提高。

关键词：PCA-SIFT；特征匹配；描述向量；主成分分析

数字图像匹配技术广泛应用于图像拼接与融合、目标识别跟踪、摄影测量遥感、图像检索等图像处理和机器视觉领域[1]。SIFT算法因为对物体旋转、背景遮挡、尺度缩放、明暗变化、外界噪声等复杂情形，都有很好的处理效果，因此在图像匹配领域得到广泛应用。但是利用SIFT特征进行匹配过程特别复杂，存在着耗时长、匹配点对少以及匹配准确率低的问题。

针对SIFT特征提取需要消耗大量时间的问题，Bay H，Tuytelaars T等提出了SURF特征提取的方法[2,3]。SURF特征提取可大大缩短特征点匹配时间，但是匹配性能也大幅度下降，匹配准确率平均只能达到SIFT算法的30%～40%；Rublee等[4]在2011年的ICCV上提出了ORB(Oriented FAST and Rotated BRIEF)特征算子。这种基于ORB的特征提取的速度比基于SIFT、SURF的方法都有了极大的提高，但是特征匹配的准确性易受到图像纹理和不均匀光照的影响；郭文静等针对SIFT算法中描述向量计算耗时长，维数多的问题，提出了用CS-LBP(center-symmetric local binary pattern)算子结合SIFT特征点生成描述向量的方法[5]，首先提取SIFT特征点，对每个特征点生成81维的CS-LBP特征描述向量然后进行匹配，这种方法能够有效减少运算量，加快运算速度，然而匹配准确度却明显下降。

以上的解决方法中，加快特征提取匹配速度的同时，匹配准确度都有所下降，针对这一问题，许多学者研究了将主成分分析的方法应用于SIFT特征提取构造PCA-SIFT特征。主成分分析是从多指标分析出发，运用统计分析原理与方法提取少数几个彼此不相关的综合性指标而保持其原指标所提供的大量信息的一种统计方法，也是考察多个变量间相关性的一种多元统计方法。具体地说，就是将高维空间的问题转化到低维空间去处理，使问题变得比较简单、直观，而且这些较少的综合指标之间互不相关，又能提供原有指标的绝大部分信息[6]。目前，主成分分析方法已经广泛地应用于图像识别、分析应用中。

传统的PCA-SIFT算法[7,8]的做法是提取两幅待匹配图像的特征点，利用这些特征点的128维描述向量构造投影矩阵，最后利用该投影矩阵将这些特征点的描述向量变换至低维空间，实现描述向量的主成分分析。传统的PCA-SIFT算法虽然实现了描述向量的降维，然而构造投影矩阵的过程却消耗了大量的时间，且描述向量的复杂构建过程并未改变，因此在提高特征匹配耗时上，效果并不明显。本文采用的PCA-SIFT算法，投影矩阵是预先构建的，且适用于相关场景的任意一幅图像，其构建时间无需计入特征点的匹配用时，同时采用一种更加精简的方法构建特征点描述向量，这就大大提高了特征点的匹配速度。实验表明，PCA-SIFT特征不仅加快了匹配速度，而且可以得到更多的匹配点对，匹配准确性也得到提高。

1SIFT特征提取

SIFT算法是David G.Lower在1999年提出[9]，并在2004年加以完善[10]，其具有旋转、缩放、平移变化的不变性。SIFT特征提取过程一般包括尺度空间极值点检测、特征点精确定位、确定特征点主方向、计算特征点描述向量以及特征点匹配。

SIFT算法首先通过对图像进行不同尺度的高斯模糊和降采样建立高斯图像金字塔，对高斯图像金字塔同一组中上下相邻图像相减得到高斯差分金字塔，在高斯差分空间中遍历每一像素检测极值点；在极值点处Taylor展开进行曲线拟合，得到修正后的位置、尺度信息，从而精确定位极值点，通过设定阈值的方法，以及运用海森矩阵的性质，保留最优特征点；计算特征点5×5邻域范围内的每一个像素的梯度幅值和方向,统计梯度方向直方图确定特征点的主方向；将坐标轴旋转至特征点主方向以保证描述向量具有旋转不变性，将以特征点为圆心的16×16圆形区域等分为4×4的子区域，在每个子区域上计算8个方向的梯度方向直方图，最终为每个子区域形成一个8维矢量，这样便可为每个特征点构建4×4×8=128维的描述向量，归一化处理生成最终的特征点描述向量。

2PCA-SIFT特征提取

SIFT特征提取过程中描述向量计算复杂，且维数较高，匹配过程涉及到计算特征点之间的欧氏距离，描述向量的高维性无疑是这一过程计算耗时的主要原因。因此无论是描述向量的计算过程，还是特征匹配过程，都需要消耗较多的时间，难以满足实时性的要求。另外，提取SIFT特征进行匹配识别的应用中，也会出现错误匹配的情况，因此为了提高匹配准确度，有必要对SIFT特征进行改进。

针对这些问题，在精确确定特征点位置之后，以一种更加精简的方法构建描述向量，再进行主成分分析降低描述向量维度，在加快匹配速度的同时匹配准确度也有所提高。

PCA-SIFT特征和SIFT特征具有相同的描述过程，即它们具有相同的精确定位位置、尺度及主方向[11]，所不同的是PCA-SIFT采用特征点周围的m×m的像素块(本文实验中采用41×41的像素块)计算它的描述向量，并利用主成分分析的方法将描述向量降低至合适的维度(本文实验中将描述向量降低至36维)，以达到更精简的表示方法。PCA-SIFT描述向量的构建流程如图1所示。

2.1PCA-SIFT投影矩阵的预先构建

构建PCA-SIFT描述向量时，预先生成投影矩阵并存储，之后直接利用这些预先存储的投影矩阵与描述向量相乘实现描述向量的主成分分析，归一化后生成最终的PCA-SIFT描述向量，这样投影矩阵是预先生成并存储的不计入计算耗时，大大精简了计算过程。同时，投影矩阵的适用广泛，对于相应场景的任意一幅图像提取的特征点描述向量，都可以直接利用该预先生成的投影矩阵进行主成分分析，无须重新生成新的投影矩阵。本文预先构建投影矩阵的一般步骤如下：

图1　PCA-SIFT描述向量的构建流程

1)选择一系列有代表性的图像(这里代表性图像要求是待匹配图像所在场景及周围拍摄的系列图片，本文实验中，通过拍摄待匹配图像所在的场景视频，按照固定间隔提取视频关键帧作为代表性图像，视频捕捉范围覆盖了待匹配图片捕捉的场景)，利用SIFT特征点检测方法精确确定这些图像的所有特征点，设特征点总数为k。

2)对于检测到的每一个特征点，将坐标轴旋转至特征点主方向，选择特征点m×m邻域范围的像素块，计算像素块中每一个非边缘像素的垂直和水平梯度，如图2所示。

图2　遍历像素块中每一个非边缘像素

水平和垂直梯度计算公式如式(1)、式(2)所示，这样就形成了大小为dim=(m-2)×(m-2)×2维的矢量。

4)计算协方差矩阵covA的特征值，并按照大小顺序排列，获取对应的特征向量，选择前n个特征向量组成大小为n×dim的矩阵并存储即为投影矩阵，其中n为最终PCA-SIFT描述向量的维数，它可以是根据经验设置的固定值，也可以基于特征值动态选择(本文实验中将n设置成36)。

2.2PCA-SIFT描述向量生成

通过以上步骤预先生成投影矩阵，该投影矩阵是针对测试图像所在场景，拍摄场景中一些列图像作为代表性图像构建而成的，这里要求代表性图像捕捉的场景范围应尽可能地覆盖测试图像包含的场景。该投影矩阵的适应性很强，对于代表性图像所捕捉场景范围内，任意拍摄的不同测试图像，都可以结合该投影矩阵完成图像特征点描述向量的主成分分析。

如果测试图像来自另一场景，且与构建投影矩阵所用的场景差别很大，则需要重新构建投影矩阵。另外，由于室外场景复杂，范围较大，获取代表性图片构建投影矩阵的困难较大，这里的PCA-SIFT特征匹配算法一般用于室内局部场景下的图像。

任意拍摄场景中的具有一定重叠的两幅图像作为待匹配测试图像，检测测试图像上的每一个特征点，按照以下步骤计算其PCA-SIFT描述向量：

确定了特征点的PCA-SIFT描述向量，测试图像对的特征匹配过程与SIFT特征匹配有着类似的过程，即查找一幅图像中的每个特征点在另一幅图像中的最邻近和次临近距离，设定阈值确定匹配点对。

3实验分析

3.1实验条件

为了综合对比两种特征的匹配速度、准确率及匹配点对数量，拍摄场景视频，按照一定间隔提取视频帧作为代表性图像用于预先构建PCA-SIFT特征中的投影矩阵，任意拍摄具有部分重叠的两幅图像(见图3)作为测试图像用于特征点匹配实验。

图3　部分阈值条件下两种特征匹配对比

另外根据以往实验经历，选取特征点周围41×41的邻域像素块计算特征点的PCA-SIFT描述向量以获得较好的匹配效果。本文实验环境为64位Linux Debian7.5，Intel(R) Core(TM) i7-3632QM CPU @ 2.20 GHz处理器，4 G内存。

3.2实验步骤

结合实验目的，实验条件，总结实验步骤如下：

1)选取具有部分重叠的测试图像，并利用SIFT特征点检测方法检测出两幅图像中的所有特征点；

2)针对待匹配测试图片所在的场景，拍摄该场景视频，按照一定间隔抽取关键帧作为代表性图像构建投影矩阵并存储；

3)分别利用SIFT算法和本文的PCA-SIFT算法计算特征点的描述向量，并且统计各自消耗的计算时间；

4)利用两种特征计算的描述向量各自进行匹配，统计各自所用的匹配时间，改变匹配阈值(threshold),统计不同阈值条件下匹配点对数量以及错误匹配点对数量；

5)拍摄该场景内的其它具有部分重叠图像作为测试图像(场景视频捕捉的场景范围应尽量覆盖测试图像包含的场景)，重复步骤3)、4)进行多次实验，汇总实验结果。

3.3算法匹配准确率比较

任意选取一对测试图像，分别利用SIFT和PCA-SIFT特征进行匹配，不同阈值条件下的特征点匹配情况如图3所示，图中黄色圆圈即为检测到的特征点(左图检测到的特征点数量为746，右图为615)，蓝线连接的点对即为正确的匹配点对，红线连接的点对为错误的匹配点对。

针对该测试图像，统计在不同匹配阈值条件下，利用两种特征进行特征点匹配时的匹配点对数量和匹配准确率，汇总实验结果如表1所示。

表1　特定阈值下匹配点对数量与准确率汇总

图4　匹配阈值与匹配点数、匹配准确率关系图

为了直观对比SIFT与PCA-SIFT特征的匹配性能，分别绘制利用两种特征进行匹配时的匹配阈值与匹配点数、匹配准确率关系折线图如图4所示。

分析实验结果可以得到，相比于SIFT特征，PCA-SIFT特征可以获得较多的匹配点对，尤其是随着匹配阈值的增大，两者之间的差异更加明显。另外，随着匹配阈值的增大，PCA-SIFT特征匹配准确率始终保持在90%以上，明显优于SIFT特征。因此可以得到以下结论：相对于SIFT特征，利用PCA-SIFT特征进行匹配可以得到更多的匹配点对，且准确率明显较高，描述向量维度的降低，并未使得匹配准确率有所下降，反而使其得到提高，这是因为对特征点描述向量进行主成分分析，不仅是对其进行简化，也是对其进行去噪声、去冗余、提纯的过程，消除了描述向量里的干扰成分，使得其更加精简紧凑。PCA-SIFT特征仅保留描述向量的本质信息，去除了多余的干扰信息，使得匹配准确率得到提高。

3.4算法执行速度比较

PCA-SIFT特征匹配算法中，投影矩阵是预先构建的，选取测试场景中的任意一组图像都可以利用该投影矩阵完成主成分分析的过程。其中构建投影矩阵所用时间主要由代表性图像数量和每幅图像所需的处理时间决定(实验中选取了1 254帧作为代表性图像，构建投影矩阵用时约为298 s)。选取不同的测试图像进行多次实验，统计利用两种特征进行实验时，描述向量计算的平均耗时，以及测试图像特征点匹配的平均耗时，汇总实验结果如表2所示。

表2　两种特征匹配耗时对比　ms

通过表2可以明显看出，相对于SIFT特征，PCA-SIFT特征在描述向量的计算上耗时稍少，但是差别并不明显，然而在特征匹配过程中，PCA-SIFT特征匹配的耗时却明显减少，几乎缩短了一个量级。这主要是因为PCA-SIFT特征经过主成分分析的作用维数较低，使得在特征匹配过程中，通过计算欧氏距离来选择最邻近和次邻近距离的用时大大减少，从而提高了匹配速度。

4结束语

本文在分析SIFT特征匹配一般过程的基础上，总结了利用SIFT特征进行匹配存在的耗时长、匹配点对少、准确率低的问题，针对这些问题提出了PCA-SIFT特征匹配的方法。采用一种更加精简的方法构建特征点的初始描述向量，利用预先构建的投影矩阵实现对初始描述向量的主成分分析，从而降低了描述向量的维度保证了匹配速度的提高，同时降维不仅是对描述向量进行简化，也是对其进行去噪、提纯的过程，使得生成的低维描述向量更能反映特征点的本质，从而保证匹配更加准确，匹配点对数量也明显增多。实验表明，利用PCA-SIFT特征进行匹配，在降低匹配耗时的同时，增加了匹配点对，提高了匹配准确率。

参考文献：

[1]牛俊伟，郝向阳，刘松林.一种改进的SIFT 特征提取算法[J].测绘科学技术学报，2014，31(2):173-176.

[2]BAY H，TUYTELAARST，GOOL L V.Speeded-Up Robust Features[C].European Conference on Computer Vision，2006，1:404-417.

[3]BAY H，TUYTELAARS T，GOOL L V.Speeded-Up Robust Features(SURF)[J].Computer Vision and Image Understanding，2008，110(3):346-359.

[4]RUBLEE E，RABAUD V，KONOLIGE K,et al.ORB：an efficient alternative to SIFT or SURF[C].ICCV 2011：Proceedings of the 2011 International Conference of Computer Vision.Piscataway：IEEE,2011:2564-2571.

[5]郭文静，李军.基于改进SIFT的图像拼接算法[J].工业控制计算机，2014，27(11):17-19.

[6]浮丹丹，周绍光，徐洋,等.基于主成分分析的点云平面拟合技术研究[J].测绘工程，2014,23(4)：20-23.

[7]肖明亮.基于PCA-SIFT的虹膜识别研究[D].天津：中国民航大学,2008.

[8]王鹤.基于PCA-SIFT算法的车牌识别技术研究[D].太原：太原理工大学，2013.

[9]LOWE D G.Object recognition from local scale-invariant feature[C].Los AlaIIlitos:The 7thIEEE International Conference on Computer Vision，1999.

[10] LOWE D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004,60(2):91-110.

[11] YAN K，SUKTHANKAR R.PCA-SIFT：A More Distinctive Representation for Local Descripters[C].Proc.CVPR 2004.[S.l.]:IEEE Press，2004:506-513.

[12] 郑守住，程朋根，陈晓勇，等.结合改进特征算法和狄洛尼三角网的图像匹配方法[J].测绘科学，2015，40(2)：155-159.

[责任编辑：刘文霞]

Research on the matching algorithm of PCA-SIFT

LI Qin1，YOU Xiong1，LI Ke1，ZHANG Yanxi2

(1.Zhengzhou Institute of Surveying and Mapping，Zhengzhou 450052，China；2.Troops 65012，Shenyang 110000，China)

Abstract：SIFT is widely used in the feature matching because it is resistant to the rotation，scale and illumination changes.The matching method of PCA-SIFT is proposed aiming at the problems of time-consuming，fewer matching points and low accuracy rate in SIFT.A simplified method is adopted to build the descriptor.The process of PCA reduces the dimensionality of the key point descriptors and improves the matching efficiency.In addition，reducing the dimension is also helpful to denoise the description vector，which makes feature matching more accurate.The experiments prove that the PCA-SIFT proposed in the paper can reduce the matching time，increase the number of matching points and improve the accuracy rate.

Key words：PCA-SIFT；feature matching；description vectors；principal component analysis

中图分类号：TP391.41

文献标识码：A

文章编号：1006-7949(2016)04-0019-06

作者简介：李钦(1990-)，男，硕士研究生.

基金项目：国家自然科学基金资助项目(41201390)

收稿日期：2015-07-26