下载文档原格式
sift特征点检测算法原理SIFT特征点检测算法原理SIFT（Scale-Invariant Feature Transform）是一种用于在图像中检测和描述局部特征的算法。
它的原理是通过在不同尺度空间中寻找关键点，并计算这些关键点的局部特征描述子，从而实现图像的特征匹配和识别。
1. 尺度空间构建SIFT算法首先通过高斯金字塔构建尺度空间，以便在不同尺度下检测出特征点。
高斯金字塔是通过对原始图像进行多次降采样得到的一系列图像，每个图像都是前一层图像的二分之一。
在每一层图像上应用高斯滤波器，得到一系列平滑图像。
2. 关键点检测在构建好的尺度空间中，SIFT算法使用Difference of Gaussian （DoG）来检测关键点。
DoG是通过对相邻两层平滑图像进行相减得到的，可以有效地检测出图像中的边缘和角点。
在DoG图像中，局部极值点被认为是潜在的关键点。
3. 关键点定位为了准确定位关键点的位置，SIFT算法采用了尺度空间极值点的精确定位方法。
它使用T aylor展开式对DoG图像进行拟合，通过求解极值点的二阶导数来精确定位关键点的位置。
同时，为了排除低对比度的关键点和边缘响应的干扰，SIFT算法会对关键点进行一定的筛选。
4. 方向分配为了使特征描述子具有旋转不变性，SIFT算法对每个关键点分配一个主方向。
它通过计算关键点周围像素的梯度方向直方图，找出主要梯度方向，并将其作为关键点的方向。
这样可以保证特征描述子在旋转变换下具有一定的稳定性。
5. 特征描述在关键点的周围区域内构建特征描述子，用于表示关键点的局部特征。
SIFT算法将关键点周围的图像区域划分为若干个子区域，并在每个子区域内计算梯度方向直方图。
最后将这些直方图连接起来，得到一个具有128维特征向量的特征描述子。
通过以上步骤，SIFT算法可以在图像中检测出大量的关键点，并为每个关键点生成一个128维的特征描述子。
这些特征描述子具有尺度不变性、旋转不变性和光照不变性等特点，可以用于图像匹配、物体识别和三维重建等应用领域。
图像识别中的局部特征提取方法比较在当今信息时代，图像识别技术逐渐成为人工智能领域的热点研究。
图像识别的核心问题是如何自动从图像中提取出有意义的特征并进行分类或识别。
在图像识别的过程中，局部特征提取方法起着至关重要的作用。
本文将对几种常见的局部特征提取方法进行比较，并探讨它们的优缺点。
一、SIFT（尺度不变特征变换）SIFT是一种局部特征提取算法，该算法通过检测图像中的尺度空间极值点来提取特征点，并对特征点进行领域方向估计和描述子计算。
SIFT算法具有尺度不变性和旋转不变性的特点，对于光照、噪声等干扰也具有较好的稳定性。
然而，SIFT算法在大规模图像数据中的计算效率较低，特征点数量不稳定，且对旋转和图像缩放的变化较为敏感。
此外，SIFT算法对于一些正负样本分布差别较大的图像分类问题效果不佳。
二、SURF（加速稳健特征）SURF是一种基于SIFT算法的改进算法，它采用了快速哈尔小波变换来加速特征点的检测和匹配过程。
SURF算法运算速度更快，具有尺度、旋转和仿射不变性，适用于实时性要求较高的图像识别任务。
然而，SURF算法在提取特征点时对于缩放和旋转变换的不变性较弱，并且在存在大视角变化和光照变化的图像中效果较差。
虽然SURF算法在一定程度上解决了SIFT算法的计算效率问题，但仍然存在一定局限性。
三、ORB（Oriented FAST and Rotated BRIEF）ORB是一种计算速度较快且具有旋转不变性的局部特征描述子算法。
它采用FAST角点检测器提取关键点，并使用BRIEF描述子进行特征描述。
ORB算法在计算效率和特征描述的准确性方面具有明显的优势，适用于移动机器人、实时目标跟踪等应用场景。
然而，ORB算法对于光照和视角变化的不变性相对较差，对于一些复杂场景和背景干扰较大的图像识别任务效果有限。
此外，ORB算法的匹配精度相对较低，对于图像中存在大量重复纹理的区域容易出现误匹配。
四、CNN（卷积神经网络）CNN是一种深度学习算法，近年来在图像识别领域取得了巨大的突破。
常用的特征描绘子在计算机视觉和图像处理领域，特征描绘子是用于描述图像中的特定属性或纹理信息的数学表示。
特征描绘子对于图像匹配、对象识别和图像检索等任务非常重要。
下面将介绍一些常用的特征描绘子。
1.SIFT（尺度不变特征变换）：SIFT是一种用于在不同尺度上检测和描述局部特征的算法。
它通过应用高斯滤波器来寻找具有高灵敏度的关键点，并使用关键点周围的局部图像区域来构建描述子。
SIFT特征具有尺度不变性和旋转不变性，因此在大规模图像检索和对象识别中广泛应用。
2. SURF（加速稳健特征）：SURF是一种基于Hessian矩阵的局部特征描述子。
它通过计算图像中的灰度变化率来检测特征点，并构建了一种基于梯度直方图的描述子。
SURF特征具有尺度不变性、旋转不变性和光照不变性，且计算速度比SIFT更快，因此适用于实时图像处理任务。
3.ORB（方向鲁棒特征）：ORB是一种结合了FAST角点检测器和BRIEF特征描述子的特征描绘子。
它通过检测图像中的角点，并使用二进制描述子来描述这些角点的特征。
ORB特征具有尺度不变性、旋转不变性和仿射不变性，且计算速度比SIFT和SURF都更快，因此适用于实时图像处理应用。
4.HOG（方向梯度直方图）：HOG是一种用于物体检测和人体姿态估计的特征描述子。
它通过计算图像中局部区域的梯度直方图来描述图像的形状和纹理信息。
HOG特征在人体检测和行人识别等任务中表现出色，并且对于图像的尺度和旋转变化具有一定的鲁棒性。
5.LBP（局部二值模式）：LBP是一种用于纹理分析和表情识别的特征描述子。
它通过将局部图像区域与其周围像素比较，并将比较结果编码为二进制数来描述纹理特征。
LBP特征在纹理分类和人脸识别等任务中表现出色，并且对于光照变化和噪声干扰具有一定的鲁棒性。
除了上述特征描绘子，还有许多其他的常用特征描绘子，如GIST（总体图像特征）、BRISK（加速旋转不变特征）、FREAK（快速稳定特征）等。
SIFT算法原理SIFT（Scale-Invariant Feature Transform）算法是一种用于检测和描述图像中的局部特征的算法，它具有尺度不变性和旋转不变性的特点。
SIFT算法由David G. Lowe在1999年提出，被广泛应用于计算机视觉领域的图像匹配、目标识别等任务。
1.尺度空间的构建：SIFT算法首先构建图像的尺度空间，通过对原始图像进行高斯模糊操作得到一组图像。
具体操作是利用高斯核对图像进行卷积，每次卷积后将图像尺寸缩小一半，得到不同尺度的图像。
这样可以在不同尺度上寻找到特征点，使算法具有尺度不变性。
2.关键点的检测：在不同尺度的图像中，SIFT算法通过在每个像素点周围进行高斯差分操作，来寻找潜在的关键点。
具体操作是计算每个像素点的高斯差分空间，找到极大值和极小值点。
这些极值点成为候选关键点。
3.关键点的定位：在候选关键点的基础上，SIFT算法通过对梯度方向和梯度幅值进行计算，进一步筛选出具有稳定性的关键点。
具体操作是在关键点周围的邻域内，计算图像的梯度方向和梯度幅值，并将邻域划分为8个方向的子区域，求出每个子区域内的梯度方向直方图。
通过梯度方向直方图的峰值来确定关键点的主要方向。
4.关键点的描述：SIFT算法通过关键点的主方向，对其周围的图像区域进行描述。
具体操作是在关键点周围的邻域内，将邻域划分为多个子区域，并计算每个子区域内的梯度方向和梯度幅值。
这样可以得到一个向量组成的特征向量，用来描述关键点周围的图像区域。
为了保持对尺度和旋转的不变性，SIFT算法对特征向量进行归一化和抗干扰处理。
5.特征点的匹配：在进行目标识别等任务时，SIFT算法需要对图像中的特征点进行匹配。
为了提高匹配的准确性，在进行特征点匹配时，SIFT算法采用了一种特殊的匹配方法，基于最近邻和次近邻的比值。
对于每个特征点，找到其在另一幅图像中的最近邻点和次近邻点，通过计算这两个点之间的距离比值，进行匹配判断。
sift方法
SIFT是一种计算机视觉特征检测和描述算法。
它是Scale-invariant feature transform的缩写，即尺度不变特征转换。
SIFT 算法用于在数字图像中检测和描述局部特征，这些局部特征在尺度、旋转和仿射失真下都具有不变性。
SIFT算法通过找到关键点和描述其特征向量来实现特征检测和描述。
SIFT算法包含四个主要步骤：尺度空间极值检测、关键点定位、方向估计和特征描述。
在尺度空间极值检测中，SIFT通过高斯差分空间来检测可能的关键点。
在关键点定位中，SIFT对于每个检测到的极值点计算其稳定性。
在方向估计中，SIFT通过检测图像的梯度方向来计算每个关键点的主方向。
在特征描述中，SIFT通过将关键点周围的梯度方向分布转换为特征向量来描述每个关键点的局部特征。
SIFT算法在计算机视觉和图像处理领域有广泛的应用，包括目标识别、图像匹配和三维重建等方面。
SIFT算法的不变性和描述特点使得其能够处理多种不同类型的图像，并获得较好的匹配效果。
常用的特征描绘子特征描述子是计算机视觉领域中的一种技术，用于对图像或视频中的对象进行描述和识别。
它们可以根据对比度、纹理、形状等特征对对象进行唯一、稳定和可重复的描述。
在下面，我将介绍一些常用的特征描述子。
1. 尺度不变特征变换（Scale-Invariant Feature Transform，SIFT）：SIFT是一种常用的特征描述子，能够提取出在尺度、旋转和光照变化等条件下具有独特性的图像特征。
它使用高斯差分金字塔的图像梯度来检测兴趣点，并通过局部邻域的直方图统计来描述这些点的特征。
2. 加速稳健特征（Speeded Up Robust Features，SURF）：SURF是另一种基于尺度不变特征的描述子。
它通过使用快速哈尔小波变换来加速特征提取，并使用各方向图像积分将梯度信息捕捉到特征描述子中。
3. 方向梯度直方图（Histogram of Oriented Gradients，HOG）：HOG是一种用于检测和识别图像中物体的特征描述子。
它基于图像的局部梯度方向和强度来描述对象的形状。
HOG特征在行人检测和行为识别等任务中得到了广泛应用。
4. 颜色直方图（Color Histogram）：颜色直方图是用来描述图像中颜色分布的一种特征描述子。
它将图像中的像素按照颜色分布统计到不同的直方图区间内，以实现对颜色特征的描述。
颜色直方图在图像检索和物体识别等任务中常用。
5. 尺度不变特征点变换（Scale-Invariant Feature Point Transform，SIFTPT）：SIFTPT是一种基于尺度不变特征点的描述子。
它通过检测图像中的兴趣点和特征点，并描述其周围的局部区域，以实现对图像的描述和识别。
6. 零均值归一化亮度梯度（Zero-mean Normalized Gradient，ZMNG）：ZMNG是一种用于图像识别和目标跟踪的特征描述子，它通过归一化图像的亮度梯度来捕捉图像中的纹理和形状特征。
SIFT算法详解及应用SIFT（Scale-Invariant Feature Transform）是一种在计算机视觉中常用的特征点提取算法，由David Lowe在1999年提出，并在2004年的论文中进行了详细阐述。
SIFT算法可以在不同尺度和旋转下保持图像的特征点不变性，因此在图像拼接、目标识别、图像匹配等领域具有广泛的应用。
1.尺度空间构建：SIFT算法使用高斯差分函数来检测不同尺度下的特征点。
通过在图像中采用不同尺度的高斯滤波，构建尺度空间，从而检测到不同尺度的图像特征。
2.关键点提取：在构建的尺度空间中，SIFT算法通过在每个像素点检测局部极值点来获取关键点。
具体的做法是对每个像素点在尺度空间上进行比较，找出该点与它相邻像素点和尺度上的极值，从而得到关键点。
3. 关键点定位：在关键点提取后，SIFT算法通过利用二阶偏导数的Hessian矩阵来对关键点进行进一步定位。
Hessian矩阵可以描述图像对灰度变化的响应，通过计算关键点周围像素点的Hessian矩阵，可以对关键点进行精确定位。
4.方向分配：在关键点定位后，SIFT算法为每个关键点分配一个主导方向。
通过对关键点周围的图像梯度进行统计，找到梯度方向分布最大的方向作为主导方向，以此来保证关键点对旋转具有不变性。
5.特征描述：在分配了主导方向后，SIFT算法使用局部图像梯度的方向直方图来描述关键点的局部特征。
将关键点周围的16x16邻域划分为4x4的小格子，计算每个小格子内的梯度方向直方图，最终得到一个128维的特征向量来表示关键点的局部特征。
1.尺度不变性：SIFT算法通过在不同尺度下检测特征点，使得算法对于图像缩放具有不变性。
这一特性使得SIFT在目标识别和图像匹配等领域具有广泛应用，可以应对不同尺寸的目标和场景。
2.旋转不变性：SIFT算法通过为每个关键点分配主导方向，使得算法对于图像旋转具有不变性。
这一特性使得SIFT在图像拼接和图像匹配中能够应对图像的旋转变换。
SIFT特征匹配算法简介1、SIFT算法基本概念Sift是David Lowe于1999年提出的局部特征描述子，可以处理两幅图像之间发生平移、旋转、仿射变换情况下的匹配问题，具有良好的不变性和很强的匹配能力。
SIFT算法是一种提取局部特征的算法，也是一种模式识别技术，其基本思想是在尺度空间寻找极值点，提取位置，尺度，旋转不变量，它主要包括两个阶段，一个是Sift特征的生成，即从多幅图像中提取对尺度缩放、旋转、亮度变化无关的特征向量；第二阶段是Sift特征向量的匹配。
Sift及其扩展算法已被证实在同类描述子中具有最强的健壮性，目前是国内外研究的热点。
2、SIFT算法的主要特点：a) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性，而对物体运动、遮挡、噪声等因素也保持较好的可匹配性，从而可以实现差异较大的两幅图像之间特征的匹配。
b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配，比原有的harris点匹配方式具有更高的匹配准确度。
c) 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。
d) 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。
e) 可扩展性，可以很方便的与其他形式的特征向量进行联合。
SIFT算法基于图像特征尺度选择的思想，建立图像的多尺度空间，在不同尺度下检测到同一个特征点，确定特征点位置的同时确定其所在尺度，以达到尺度抗缩放的目的。
剔除一些对比度较低的点以及边缘响应点，并提取旋转不变特征描述符以达到抗仿射变换的目的。
3、SIFT算法步骤：1）构建尺度空间，检测极值点，获得尺度不变性；2）特征点过滤并进行精确定位；3）为每个关键点指定方向参数4）生成关键点的描述子5）当两幅图像的Sift特征向量生成以后，下一步就可以采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。
机器视觉中的特征描述和匹配算法机器视觉的应用已经渗透到了我们的日常生活中。
从无人驾驶到人脸识别，从医学影像诊断到安防监控，机器视觉技术正在飞速发展，广泛应用于各个领域。
而特征描述和匹配算法则是机器视觉技术中最为关键、也是最为基础的部分之一。
特征描述是机器视觉中的一种重要的算法，它从图像中提取出图像的本质特征，用于后续的图像匹配、物体识别、姿态估计等应用。
特征描述主要有两种方式：局部特征和全局特征。
局部特征是指从图像中提取出某些局部区域的特征。
常用的局部特征算法包括SIFT算法、SURF算法、HOG算法、ORB算法等。
SIFT算法是局部特征提取的先锋算法，它通过对图像空间中多个尺度上的高斯差分图像进行计算，来提取图像的关键点和对应的描述子。
SURF算法则是SIFT算法的改进版，它使用的是基于海森矩阵的特征描述子，计算效率比SIFT更快。
HOG算法是一种计算图像梯度的方法，用于描述图像中的纹理和形状信息。
ORB算法是基于FAST特征点检测和BRIEF描述子的一种算法，它具有计算速度更快、鲁棒性更高等优点。
全局特征是指从整幅图像中提取出的一些特定的整体特征。
常用的全局特征算法包括LBP算法、PCA算法、CNN算法等。
LBP算法是一种描述图像纹理信息的算法，它通过计算每个像素周围像素的灰度级差异来描述图像的纹理。
PCA算法是一种线性降维方法，它可以将高维的图像数据映射到低维空间中，用于图像的压缩和重构。
而CNN算法则是一种基于深度学习的特征提取算法，它可以自动学习图像中的特征，具有非常强的鲁棒性和泛化能力。
特征匹配是机器视觉中的另一个基础算法，它将两个或多个图像中的特征点进行匹配，用于物体识别、姿态估计等应用。
特征匹配主要有两种方法：基于相似度的匹配和基于约束条件的匹配。
基于相似度的匹配是指将两个特征描述子之间的相似度作为匹配度量，来匹配两个特征点。
常用的基于相似度的匹配算法包括暴力匹配算法、FLANN算法、ANN算法、KD树算法等。
第40卷第4期自动化学报Vol.40,No.4 2014年4月ACTA AUTOMATICA SINICA April,20142DPCA-SIFT:一种有效的局部特征描述方法颜雪军1赵春霞1袁夏1摘要PCA-SIFT(Principal component analysis–scale invariant feature transform)方法通过对归一化梯度向量进行PCA降维,在保留特征不变性的同时,有效地降低了特征矢量的维数,从而提高了局部特征的匹配速度.但PCA-SIFT中对本征向量空间的求解非常耗时,极大地限制了PCA-SIFT的灵活性与应用范围.本文提出采用2DPCA对梯度向量块进行降维的特征描述方法.该方法相比于PCA-SIFT,可以快速地求解本征空间.实验结果表明:2DPCA-SIFT在多种图像变换匹配和图像检索实验中可以实现与PCA-SIFT相当的性能,并且从计算效率上看,2DPCA-SIFT具有更好的扩展性.关键词2DPCA降维,局部特征描述,图像匹配,图像检索引用格式颜雪军,赵春霞,袁夏.2DPCA-SIFT:一种有效的局部特征描述方法.自动化学报,2014,40(4):675−682DOI10.3724/SP.J.1004.2014.006752DPCA-SIFT:An Efficient Local Feature DescriptorYAN Xue-Jun1ZHAO Chun-Xia1YUAN Xia1Abstract Principal component analysis–scale invariant feature transform(PCA-SIFT)applies principal components analysis(PCA)to the normalized gradient vector.It effectively reduces the dimension of feature representation and improves the matching speed while maintaining the descriptor s invariance.However,PCA-SIFT needs an additional step of eigenspace computation which is time-consuming.This step greatly limits theflexibility and applications of PCA-SIFT. In this paper,we adopt the2DPCA to reduce the descriptor s dimension and build the pared to the PCA-SIFT,this method canfinish the eigenspace calculation in real time.The experiments show that the proposed method can get competitive performance when compared to PCA-SIFT in different image matching and image retrieval applications,and can be easier to be expanded for its good computational efficiency.Key words2DPCA dimension reduction,local descriptor,image matching,image retrievalCitation Yan Xue-Jun,Zhao Chun-Xia,Yuan Xia.2DPCA-SIFT:an efficient local feature descriptor.Acta Automatica Sinica,2014,40(4):675−682局部特征对图像尺度、旋转、光照和视角等图像变换具有不变性,并在噪声、遮挡等因素的影响下仍然具有很好的匹配性能,正在越来越广泛地应用于图像匹配[1]、目标检测与跟踪[2−4]、图像检索[5]等视觉领域.局部特征的提取方法主要包括特征点检测和特征描述生成两个步骤.Mikolajczyk等[6]的研究表明,相对于检测算法的选择,局部特征描述设计算法对局部特征性能具有更显著的影响.因此,目前局部特征方法的研究主要集中在如何构建具有鲁棒性和独特性的特征描述子.构建特征描述子的目标是建立特征点邻域信收稿日期2012-12-26录用日期2013-03-04Manuscript received December26,2012;accepted March4, 2013国家自然科学基金(61272220),江苏省自然科学青年基金(BK2012399)资助Supported by National Natural Science Foundation of China (61272220)and Natural Science Foundation of Jiangsu Province (BK2012399)本文责任编委黄庆明Recommended by Associate Editor HUANG Qing-Ming1.南京理工大学计算机科学与工程学院南京2100941.School of Computer Science and Engineering,Nanjing Uni-versity of Science and Technology,Nanjing210094息的描述,并在此描述的基础上构建该特征点的描述向量.这些描述子按照其构建方法大致可以分为基于区域分布、基于空间频率、基于微分等类型. Mikolajczyk等[6]在2005年对各种描述子作了系统全面的分析比较,实验比较结果表明,基于梯度分布的尺度不变特征变换算法(Scale invariant feature transform,SIFT)[1]和GLOH(Gradient location and orientation histogram)明显优于其他描述子.因而,大多数特征描述子也是基于局部区域信息(包括梯度、灰度等)的分布来构建的[7−8].最为典型的特征描述子是Lowe提出的SIFT特征[1],该特征描述子是通过对特征点邻域构建三维梯度方向直方图来产生128维特征向量.SIFT特征对尺度变换与旋转具有不变性,并且对光照变化、图像变换以及噪声也有较强的适应能力,在匹配中具有较好的容错性.但SIFT特征维数较高,存在匹配效率不高的问题.Bay等在SURF(Speeded up robust features)[9]中利用Harr小波的局部响应构建64维描述向量,该方法可以达到与SIFT相似的性能[10]. Huang等[11]利用环形扇区构建对比度上下文直方676自动化学报40卷图(Contrast context histogram,CCH)产生64维描述向量,该方法直接利用对比度信息来构建特征描述,构建速度更快,产生的特征除了在视点变换中比SIFT性能略差,性能基本与SIFT相当.刘萍萍等[12]基于CCH方法,对局部邻域进行像素强度规一化预处理,然后,采用CCH的方法构建特征向量.杨恒等[13]通过对特征点周围的6个环形邻域构建8方向梯度直方图,最后,产生48维的GDOH (Gradient distance and orientation histogram)特征.这些特征描述方法在特征维数上比SIFT有了较大的降低,但独特性上并没有得到改进.针对局部特征描述向量的高维数问题,还可以采用主成分分析(Principal component analysis, PCA)对特征向量进行降维.最早采用PCA进行局部特征描述降维的是Ke等[14]提出的PCA-SIFT,该方法将特征点邻域像素的梯度分量所构成高维向量投影到前20维本征向量空间,产生20维的特征描述.Mikolajczyk等[6]采用PCA方法将GLOH 的原始272维直方图降到128维.Winder等[15]根据DAISY的实验结果结合Shan等[16]的成果认为,在高维描述本身就具有独特性而且没有分类标签的前提下,应用PCA方法进行特征降维是极为有效的方法.PCA-SIFT方法虽然可以产生紧凑的低维数特征描述向量,但该方法需要事先计算本征向量空间,而且本征向量空间的求解通常需要对高维向量的总体散布矩阵进行奇异值(Sigular value decomposition,SVD)分解,计算过程十分耗时.本文针对PCA-SIFT的该缺点,提出采用二维主成分分析方法(2DPCA)[17]对梯度向量描述块进行降维来构建特征描述子.虽然本方法也要事先进行数据块散布矩阵进行奇异值分解,但由于散布矩阵的低维数特性,使得求解速度得到了极大的改善.12DPCA-SIFT描述子的设计1.1PCA-SIFT描述子PCA-SIFT方法保留了SIFT方法中的尺度空间极值检测、特征点亚像素定位、主方向分配等主要步骤,主要对特征描述向量生成方式进行改进[14]. PCA-SIFT方法在特征点的邻域,以特征主方向为基准方向提取41×41的像素块.计算该像素块中的水平和垂直两个方向的梯度分量,产生的初始向量包含2×39×39=3042个元素.为减少光照变化影响,需要对初始向量做归一化处理.将归一化后的初始向量往预先计算的本征空间投影即可得到低维数的PCA-SIFT特征描述向量.由于PCA-SIFT 采用的是投影降维的方式构建特征描述,因此在保持相当的特征独特性的同时,可以产生比直方图方法[10−13]更低维数的特征描述.在PCA-SIFT方法中,需要预先计算初始向量的本征空间.本征空间是通过求解训练样本总体散布矩阵的本征值和本征向量得到的,总体散布矩阵的维数为min(3042,n)×min(3042,n).这里的n 为训练样本个数,由于特征检测算法通常可以产生数量可观的特征点而且多数情况下是对多幅图像产生的初始向量集进行训练,因而在大多数情况下n>3042.这使得实际上要求解本征值和本征向量的散布矩阵大小为3042×3042维,高维矩阵的奇异值分解十分耗时,直接影响PCA-SIFT方法的灵活性.1.22DPCA方法2DPCA方法[17]直接将图像块往投影轴上投影,得到图像投影特征向量.考虑m×n的图像A,将投影到n×d维投影矩阵X,得到图像的2DPCA 特征矩阵表示为Y=AX其中,Y为m×d维矩阵.在2DPCA方法中,需要求解最佳投影矩阵X 使得投影后的所得到的特征矩阵Y的散布最大化.对最佳投影矩阵X的求解最后可转化为对训练图像总体散布矩阵求解最大的前d个本征值所对应的单位本征向量.假设有M个m×n维训练样本图像A k,k=1,2,···,M,则训练图像的总体散布矩阵为G t=1MMi=1(A i−¯A)T(A i−¯A)(1)其中,¯A=1MMi=1A i为训练样本的均值矩阵.从式(1)可知,总体散布矩阵G t的大小为n×n,而且其维数的大小与训练图像大小相关,与训练样本个数无关.因此,在样本数量较大的情况下,2DPCA 在本征空间求解效率上相比于PCA方法具有明显的优势.原始版本的2DPCA方法[17]投影后产生的投影矩阵Y大小为m×d,在存储效率上弱于PCA方法.Yang等[18]为克服2DPCA存储上的不足,提出了2DPCA的一个变种Bi-2DPCA.该方法在对2DPCA产生的特征矩阵在垂直方向上又进行了一次投影,使得两次投影后的特征矩阵维数得到进一步的降低,有效地解决了2DPCA存在的存储效率问题.因此,本文也采用Bi-2DPCA方法对原始数据块进行降维.1.32DPCA-SIFT描述子设计2DPCA-SIFT与PCA-SIFT方法相同,以特征主方向为基准方向提取41×41的像素块作为描4期颜雪军等:2DPCA-SIFT:一种有效的局部特征描述方法677述算法的输入,并计算像素块水平和垂直方向的梯度分量.因此,2DPCA-SIFT的初始特征描述块也包含3042个元素.与PCA-SIFT中将归一化处理后的3042个梯度分量构造成向量不同,本文将计算得到的梯度分量构造成矩阵形式使得其适合采用2DPCA方法进行处理.为构建2DPCA-SIFT梯度分量矩阵,直接的想法是将PCA-SIFT中的高维向量转化为矩阵块的形式.如图1(a)所示,将PCA-SIFT中3042维向量转化成39×78维梯度分量矩阵.矩阵中每一行元素由41×41像素块中对应像素产生的各39个水平梯度分量和垂直梯度分量交替排列而成的.得到的矩阵按Bi-2DPCA方法,首先在水平方向进行投影得到39×n1维的2DPCA 特征描述.对得到的特征描述在垂直方向上进行第二次投影,最终产生n2×n1维的2DPCA-SIFT 特征描述.为了简化特征匹配,需要将矩阵形式的2DPCA-SIFT特征描述转化为向量形式.(a)39×78维梯度分量矩阵构建特征描述方法(a)Building feature descriptor from39×78gradient patch(b)采用水平和垂直梯度矩阵构建特征描述方法(b)Building feature descriptor from horizontal andvertical patchs图1两种2DPCA-SIFT特征描述构建方法Fig.12DPCA-SIFT descriptors采用图1(a)方法构建的梯度矩阵块内的元素在隔列抽取之后才满足特征点邻域像素块的原始位置排列.按奇数列和偶数列抽取分别得到如图1(b)所示的两个39×39梯度分量矩阵.这样做的动机是我们认为2DPCA是对图像矩阵进行投影,在构建梯度矩阵时,希望保留邻域像素的空间位置关系.因此,采用水平梯度分量矩阵和垂直梯度分量矩阵双矩阵来表示特征点邻域的梯度信息.值得注意的是,此时需要对两个分量矩阵分别进行强度归一化预处理.预处理之后各自进行水平和垂直两个方向的投影,得到两个n2×n1维的向量.最终的2DPCA-SIFT特征描述由这两个向量合并而成,维数为n2×n1+n2×n1.为区分两种2DPCA-SIFT构建方法,在后续的描述中我们将图1(a)采用单个梯度矩阵的特征描述方法命名为Original2DPCA-SIFT(Ori 2DPCA-SIFT),图1(b)采用两个分量矩阵计算特征描述的方法称为2DPCA-SIFT.2实验结果与分析为验证提出算法的性能,我们在Dell360硬件平台上采用VS2008+OpenCV2.3来实现SIFT, PCA-SIFT,Ori2DPCA-SIFT和2DPCA-SIFT 方法.本文采用Mikolajczyk数据集[6]来探讨本文所述的Ori2DPCA-SIFT和2DPCA-SIFT特征描述子的特征匹配性能.匹配结果采用查全率–查错率(Recall vs.1-Precision)来进行评价,特征之间的相似性采用欧氏距离来度量,与PCA-SIFT方法[14]原文采用的度量准则一致,当特征之间的距离小于某个阈值(Threshold),则认为是一对匹配. Mikolajczyk等[6]的研究认为,不同的评价准则对算法性能排序的影响不大,但相比于最近邻(Near-est neighbor)准则和最近邻距离与次近邻距离比(Nearest neighbor distance ratio)准则,基于阈值(Threshold-based)的方法更适合在数据库中的特征搜索,并且能反映出特征描述在空间中的分布情况.2.12DPCA-SIFT参数选择从图1中可以看出,Ori2DPCA-SIFT和2DPCA-SIFT在构建特征描述向量过程中都需要确定水平方向上的投影向量个数n1和垂直方向上的投影向量个数n2.参数n1和n2直接决定了Ori 2DPCA-SIFT和2DPCA-SIFT的特征描述维数.Ke等[14]和Mikolajczyk等[6]的实验认为PCA-SIFT在特征维数为36时匹配性能较好,并且还能有效地控制特征描述长度.本文方法与PCA-SIFT方法一样,目标是寻找一种有效的低维数特征描述方法.因此,我们以36维特征描述为基准,讨论参数n1和n2的不同选择对本文方法特征独特性的影响.图2的结果显示在Ori2PCA-SIFT和678自动化学报40卷2DPCA-SIFT中,当n1≈2·n2时,算法产生的特征描述具有较好的性能.可以看出在大多数情况下,n1>n2时,得到的结果要优于n1<n2的情况.我们对比两次投影空间最大特征值与第10大特征值的比值,发现水平方向投影空间两个特征值之间的比值为4,而在垂直方向上比值约为19,而且发现虽然参数n1会影响垂直方向特征空间散布矩阵的构建,但特征值之间的比值却恒定在19左右.所以我们认为垂直方向散布矩阵的特征值衰减更快,n1>n2的参数选择能保留更多的样本信息.在限定特征维数为36的情况下,Ori2DPCA-SIFT 选择参数n1=9,n2=4,2DPCA-SIFT选择参数n1=6,n2=3分别达到最优的性能.(a)Ori2DPCA-SIFT(b)2DPCA-SIFT图2参数n1,n2对特征描述方法性能的影响Fig.2Evaluation for different selection of n1and n22.2图像匹配我们在Mikolajczyk数据集[6]上测试本文方法在各种图像变换下的匹配性能,该数据集中的测试图像包含尺度变换、旋转变换、视角变换、模糊变换、光照变换和JPEG压缩等6种图像变换,能全面地测试特征描述方法的性能.对比算法选择最为流行的SIFT算法和同样采用降维来产生特征描述的PCA-SIFT方法.在实验中, SIFT产生标准的128维特征描述,PCA-SIFT采用36维特征描述,本文方法采用上一节的结果Ori 2DPCA-SIFT(n1=9,n2=4)和2DPCA-SIFT (n1=6,n2=3),也都产生36维的特征描述.在尺度和旋转变换实验中,New York图像包含近90度的纯旋转,Boat图像包含尺度因子为1∼2.5的尺度变换,并伴随着30∼45度的旋转.从图3可以看出,在查错率<0.4时,PCA-SIFT、Ori 2DPCA-SIFT和2DPCA-SIFT方法具有比SIFT 方法更高的查全率,而在查错率>0.4时,SIFT 方法的查全率上升更快.这说明基于降维的方法在低响应率情况下能保持更高的匹配正确率,这在图像检索等计算匹配特征数目的应用中更具优势.在纯旋转变换中,PCA-SIFT和Ori2DPCA-SIFT、2DPCA-SIFT的曲线基本一致,在具有尺度变换的Boat图像中,2DPCA-SIFT方法略优于其他两种方法.(a)New York(b)Boat图3旋转与尺度变换效果图Fig.3Performance of rotation and scale changes图像的模糊变换会影响图像像素强度和边缘4期颜雪军等:2DPCA-SIFT:一种有效的局部特征描述方法679信息.图4给出了模糊变换图像间的匹配,我们发现SIFT在低查错率的情况下要弱于其他三种方法.有趣的是2DPCA-SIFT与PCA-SIFT和Ori2DPCA-SIFT的对比中,在Bikes图像的低差错率中略微占优,但在Trees图像的高查错率部分曲线稍低,总的来说在模糊变换中三者性能相当.图5(a)给出了光照变化对特征描述方法的影响,PCA-SIFT性能最好,2DPCA-SIFT与Ori2DPCA-SIFT次之.JPEG压缩变换结果见图5(b),4种算法都显示了较好的匹配性能.(a)Trees(b)Bikes图4模糊变换效果Fig.4Performance of blur images图像视角变换主要由相机位置移动引起的,并会伴随着一定的尺度和光照变换.本文测试在大约50度视角变换下各算法在结构图像(Graffies)和纹理图像(Walls)中的性能.从图6的结果我们发现,各算法在结构图像和纹理图像中呈现完全不同的结果.SIFT在纹理图像中明显优于其他算法,但在结构图像中也处于明显的劣势.4种算法在结构图像匹配中效果都比较差,在查错率达到0.5时, 2DPCA-SIFT才有0.1的响应率.我们认为这是由于DOG(Difference of Gaussians)算子本身不具有仿射不变性造成的,Mikolajczyk等[6]的研究发现,在实际仿射变换中,尺度的变化并不是各向同性的.因此,在视角变换中,DOG算子检测同一位置极值点会发生一定的偏移,这种偏移在没有交叉垂直边缘的涂鸦图像(Graffies)中更为明显[6].另外,Ke等[14]在DOG检测结果中人为添加定位误差后发现,随着误差的增大,SIFT方法比PCA-SIFT方法性能下降更快.这与特征描述的生成方式有关, SIFT采用邻域分块的梯度直方图统计方法,邻域分割对特征点定位精度有更高的要求.PCA-SIFT 和本文方法是对整个邻域向低维空间投影来产生特征描述,因而对定位误差更为鲁棒.从图6(b)总体性能好于图6(a)可以看出,由于纹理图像中含有大量的交叉边缘,实际上DOG的特征点检测结果还是比较精确的.此外,纹理信息本身就具有相似性,因此,纹理相对于特征点的位置成为区分不同特征点的重要依据,显然采用分块统计直方图的方式的SIFT描述子可以更好地表示这种信息.(a)Leuven(Illumination)(b)Ubc(JPEG)图5光照变换和JPEG压缩效果图Fig.5Performance of illumination changes andJPEG compression总的来说,PCA-SIFT和本文的两种方法在680自动化学报40卷各种图像变换中性能基本一致,PCA-SIFT与Ori 2DPCA曲线基本相同,我们认为这是由于三种方法采用相同的梯度分量作为算法输入造成的.而2DPCA-SIFT采用的保留空间位置的双梯度矩阵方法在低查错率(小于0.1)和较大定位误差的情况略优于PCA-SIFT和Ori2DPCA-SIFT算法,但在总体表现不好的纹理图像中效果也更差.SIFT算法在查错率低于0.4的情况下总体表现不如其他三种算法,但我们也发现在查错率高于0.4时,其他三种算法的响应率会趋于稳定,而SIFT会持续上升,说明SIFT实际可以得到的正确特征匹配总数要多于其他三种方法.因此,SIFT比PCA-SIFT以及本文方法更适用于图像变换估计等对正确匹配数有要求而且可以通过最近邻和模型约束来排除错误匹配的应用.本文的方法以及PCA-SIFT方法因为其压缩的特征表示以及在低查错率下更高的响应率,适合数据库中的特征匹配与搜索.(a)Graffis(b)Walls图6视角变换效果Fig.6Performance of viewpoint images2.3图像检索实验我们在一个小型数据库1上进行图像检索实验.该数据库包含10组不同的场景,每个场景包含3幅不同图像变换下的图像,共30幅图像组成.我们在此数据库中讨论本文方法与PCA-SIFT和SIFT在图像检索应用中的性能.两幅图像之间的相似性由两幅图像之间的匹配特征个数来度量.采用与文献[14]中相同的记分规则来表示图像检索的正确率,对每一幅测试图像返回两幅检索到的最相似图像,如果两幅图像与测试图像在同一组,则加2分;若只有一幅图像与测试图像同组,则加1分;否则,不加分.因此,整个系统的总分为60分,算法的图像检索正确率可由其得分除以60得到.我们采用基于阈值的方法来度量特征之间匹配的相似性.在数据库中进行两幅图像相似性度量时,当发现当前特征与被检索图像某一特征距离小于阈值时,直接返回其匹配,不需要继续计算与被检索图像后续特征之间的距离,与最近邻方法需要遍历数据库中所有特征相比,可以明显减少匹配计算次数,有利于提高整个图像检索系统的速度.但我们也发现同一算法在不同阈值下呈现不同的检索正确率,我们取该算法最高的正确率结果作为其在图像检索应用中的性能度量.表1给出了SIFT、PCA-SIFT以及本文两种方法的图像检索正确率,可以看到SIFT方法的正确率明显低于其他三种方法.我们认为这与SIFT方法在低响应率下查错率高于PCA-SIFT以及本文方法有关.查错率高意味着要产生相同数量的正确匹配,SIFT方法会引入更多的误匹配,这会影响其在图像检索中的性能.PCA-SIFT、Ori2DPCA-SIFT和2DPCA-SIFT方法匹配结果相同,均为66.7%.这是由于三种方法本身性能差别不大,并使用相同维数的特征描述造成的.表1图像检索准确率Table1Percentage of images correctly retrieved inretrieval application特征描述方法(特征维数)正确率(%)SIFT(128)56.7PCA-SIFT(36)66.7 Ori2DPCA-SIFT n1=9,n2=4(36)66.72DPCA-SIFT n1=6,n2=3(36)66.72.4算法运行时间测试本文方法运行时间包括局部特征描述生成时间和Bi-2DPCA本征空间的求解时间.本征矩阵通常是事先训练计算得到,在产生局部特征时直接对梯度向量块进行两次投影得到特征描述.PCA-SIFT 中的PCA训练和降维投影采用OpenCV中的cv-CalcPCA和cvProjectPCA函数,我们认为其是一1/˜yke/pcasift4期颜雪军等:2DPCA-SIFT:一种有效的局部特征描述方法681种较为优化的PCA处理方法.为减少计算机I/O 等外部因素对运行时间的影响,我们对图像检索实验中的30幅图像进行连续的特征提取来估算各算法的计算效率.30幅图像产生大约33700个特征点.特征匹配速度测试中采用穷举匹配,这样能保证各算法在产生相同特征个数的情况下进行的匹配次数也是相同的.表2给出了SIFT、PCA-SIFT(36)、Ori 2DPCA-SIFT(n1=9,n2=4)和2DPCA-SIFT (n1=6,n2=3)生成2000个特征描述以及4000000次特征匹配所需要的时间.从中可以看出,虽然PCA-SIFT和本文方法在生成特征描述时,需要计算邻域范围(41×41)要大于SIFT方法生成梯度直方图所需的邻域(约为20×20),但4种方法的特征生成时间基本是相同的.PCA-SIFT和本文方法对单位像素只进行垂直和水平方向的梯度分量计算,因此,在计算效率上与SIFT相比并不处于劣势.在特征匹配效率上,我们发现36维的特征匹配速度明显快于128维的SIFT特征匹配,高维数特征不仅需要占用更多的存储,在计算特征间距离时也需要更多次数的减法和乘法运算.表2特征描述生成与匹配时间Table2Performance of descriptors representation andmatching特征描述方法(特征维数)特征生成时间(s)匹配时间(s)SIFT(128) 2.29 3.69 PCA-SIFT(36) 2.37 1.79 Ori2DPCA-SIFT(36) 2.33 1.802DPCA-SIFT(36) 2.29 1.79本文的方法以及PCA-SIFT需要事先对本征向量空间进行求解计算,我们对33700个特征点产生的梯度分量进行训练,求解PCA-SIFT(36)、Ori 2DPCA-SIFT(n1=9,n2=4)和2DPCA-SIFT (n1=6,n2=3)的本征空间.表3给出了三种方法的本征空间求解时间以及用本征矩阵对33700个梯度分量进行投影产生特征描述的时间.PCA-SIFT 的本征矩阵求解时间需要45分钟左右,而本文的两种方法都在10秒之内,而且虽然2DPCA-SIFT 由于将梯度分量拆分成两个矩阵会比Ori2DPCA-SIFT多进行两次奇异值分解,但求解速度却更快.我们认为本征空间的解算速度与对应方法的散布矩阵维数和样本散布情况直接相关.在本测试中, PCA-SIFT方法的散布矩阵维数为3042×3042, Ori2DPCA-SIFT的两个散布矩阵维数分别为78×78和39×39.2DPCA-SIFT需要计算4个本征矩阵,其维数都为39×39.在对散布矩阵进行奇异值分解时,我们发现对Ori2DPCA-SIFT的水平方向78×78维散布矩阵求解大约需要6.8s,而2DPCA-SIFT水平方向39×39维散布矩阵求解只需要1.8s.第二次垂直方向散布矩阵求解时,由于样本经过一次投影后相对散布比较集中,虽然同样是求解39×39维散布矩阵,Ori2DPCA-SIFT和2DPCA-SIFT的求解时间分别为0.546s 和0.406s.在对33700个梯度分量进行投影时,发现PCA-SIFT投影速度最慢,Ori2DPCA-SIFT次之,2DPCA-SIFT最快,虽然总体来说投影速度对特征描述生成时间影响很小,但从表2的特征生成时间上可以看出,三者之间存在细微的差别.一个PCA-SIFT的3042维初始向量向3042×36维的本征矩阵投影,需要109512次乘法和109476次加法运算.在Ori2DPCA-SIFT中,39×78维梯度分量矩阵依次向78×9维的水平方向本征空间和39×4维的垂直方向本征空间投影得到36维特征共需要28728次乘法和28395次加法运算.而2DPCA-SIFT产生36维特征共需4次投影,乘法和加法运算次数分别为19656和19152.可见,本文方法在求解本征空间和投影计算效率上都优于PCA-SIFT方法,在存储上,PCA-SIFT方法的本征空间矩阵也明显大于本文的方法.表3本征矩阵生成以及投影时间Table3Performance of eigenspace calculation andprojecting特征描述方法(特征维数)投影矩阵生成时间(s)投影时间(s) PCA-SIFT(36)2736.7 3.11Ori2DPCA-SIFT(36)8.17 1.762DPCA-SIFT(36) 5.160.743结论本文将2DPCA方法引入到局部特征描述的构建中,提出的Ori2DPCA-SIFT和2DPCA-SIFT 在图像变换和图像检索测试中与PCA-SIFT方法性能相当,在特征描述维数、检索正确率以及低差错率下的匹配响应率等方面优于SIFT方法.尽管如此,由于采用和PCA-SIFT相同数量的梯度分量作为描述的输入,本文方法相比与PCA-SIFT方法特征描述的独特性没有显著的提高.相比于PCA 降维方法,2DPCA方法在本征空间求解和投影计算速度有了明显的提高.从Ori2DPCA-SIFT和2DPCA-SIFT方法的计算效率分析中可以看出,采用两个分量矩阵分别进行投影的计算效率优于高维数的单个矩阵.这为2DPCA-SIFT方法的进一步扩展提供了可能.在未来的工作中,我们希望用更多的邻域信息如灰度、对比度、色彩等对2DPCA-SIFT方法进行扩展,对每一类信息构造二维矩阵,。
