2DPCA-SIFT:一种有效的局部特征描述方法

第40卷第4期2014年4月

自动化学报ACTA AUTOMATICA SINICA

Vol. 40, No. 4April, 2014

颜雪军1

赵春霞1

袁夏1

摘要PCA-SIFT (Principalcomponent analysis –scale invariant feature transform) 方法通过对归一化梯度向量进行PCA 降维, 在保留特征不变性的同时, 有效地降低了特征矢量的维数, 从而提高了局部特征的匹配速度. 但PCA-SIFT 中对本征向量空间的求解非常耗时, 极大地限制了PCA-SIFT 的灵活性与应用范围. 本文提出采用2DPCA 对梯度向量块进行降维的特征描述方法. 该方法相比于PCA-SIFT, 可以快速地求解本征空间. 实验结果表明:2DPCA-SIFT 在多种图像变换匹配和图像检索实验中可以实现与PCA-SIFT 相当的性能, 并且从计算效率上看, 2DPCA-SIFT 具有更好的扩展性. 关键词引用格式DOI

2DPCA 降维, 局部特征描述, 图像匹配, 图像检索

颜雪军, 赵春霞, 袁夏. 2DPCA-SIFT:一种有效的局部特征描述方法. 自动化学报, 2014, 40(4):675−682

10.3724/SP.J.1004.2014.00675

2DPCA-SIFT:An EﬃcientLocal Feature Descriptor

YAN Xue-Jun 1

ZHAO Chun-Xia 1

YUAN Xia 1

Abstract Principal component analysis –scale invariant feature transform (PCA-SIFT)applies principal components analysis (PCA)to the normalized gradient vector. It eﬀectivelyreduces 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 the ﬂexibilityand applications of PCA-SIFT. In this paper, we adopt the 2DPCA to reduce the descriptor s dimension and build the descriptors. Compared to the PCA-SIFT, this method can ﬁnishthe eigenspace calculation in real time. The experiments show that the proposed method can get competitive performance when compared to PCA-SIFT in diﬀerentimage matching and image retrieval applications, and can be easier to be expanded for its good computational eﬃciency.Key words

2DPCA dimension reduction, local descriptor, image matching, image retrieval

Citation Yan Xue-Jun, Zhao Chun-Xia, Yuan Xia. 2DPCA-SIFT:an eﬃcientlocal feature descriptor. Acta Automatica Sinica , 2014, 40(4):675−682

局部特征对图像尺度、旋转、光照和视角等图像变换具有不变性, 并在噪声、遮挡等因素的影响下仍然具有很好的匹配性能, 正在越来越广泛地应用于图像匹配[1]、目标检测与跟踪[2−4]、图像检索[5]等视觉领域. 局部特征的提取方法主要包括特征点检测和特征描述生成两个步骤. Mikolajczyk 等[6]的研究表明, 相对于检测算法的选择, 局部特征描述设计算法对局部特征性能具有更显著的影响. 因此, 目前局部特征方法的研究主要集中在如何构建具有鲁棒性和独特性的特征描述子.

构建特征描述子的目标是建立特征点邻域信

录用日期2013-03-04

Manuscript received December 26, 2012; accepted March 4, 2013

国家自然科学基金(61272220),江苏省自然科学青年基金(BK2012399)资助

Supported by National Natural Science Foundation of China (61272220)and Natural Science Foundation of Jiangsu Province (BK2012399)本文责任编委黄庆明收稿日期2012-12-26

Recommended by Associate Editor HUANG Qing-Ming 1. 南京理工大学计算机科学与工程学院南京210094

1. School of Computer Science and Engineering, Nanjing Uni-versity of Science and Technology, Nanjing 210094

息的描述, 并在此描述的基础上构建该特征点的描述向量. 这些描述子按照其构建方法大致可以分为基于区域分布、基于空间频率、基于微分等类型. Mikolajczyk 等[6]在2005年对各种描述子作了系统全面的分析比较, 实验比较结果表明, 基于梯度分布的尺度不变特征变换算法(Scaleinvariant feature transform, SIFT) [1]和GLOH (Gradientlocation and orientation histogram) 明显优于其他描述子. 因而, 大多数特征描述子也是基于局部区域信息(包括梯度、灰度等) 的分布来构建的[7−8]. 最为典型的特征描述子是Lowe 提出的SIFT 特征[1], 该特征描述子是通过对特征点邻域构建三维梯度方向直方图来产生128维特征向量. SIFT 特征对尺度变换与旋转具有不变性, 并且对光照变化、图像变换以及噪声也有较强的适应能力, 在匹配中具有较好的容错性. 但SIFT 特征维数较高, 存在匹配效率不高的问题. Bay 等在SURF (Speededup robust features) [9]中利用Harr 小波的局部响应构建64维描述向量, 该方法可以达到与SIFT 相似的性能[10]. Huang 等[11]利用环形扇区构建对比度上下文直方

图(Contrastcontext histogram, CCH) 产生64维描述向量, 该方法直接利用对比度信息来构建特征描述, 构建速度更快, 产生的特征除了在视点变换中比SIFT 性能略差, 性能基本与SIFT 相当. 刘萍萍等[12]基于CCH 方法, 对局部邻域进行像素强度规一化预处理, 然后, 采用CCH 的方法构建特征向量. 杨恒等[13]通过对特征点周围的6个环形邻域构建8方向梯度直方图, 最后, 产生48维的GDOH (Gradientdistance and orientation histogram) 特征. 这些特征描述方法在特征维数上比SIFT 有了较大的降低, 但独特性上并没有得到改进.

针对局部特征描述向量的高维数问题, 还可以采用主成分分析(Principalcomponent analysis, PCA) 对特征向量进行降维. 最早采用PCA 进行局部特征描述降维的是Ke 等[14]提出的PCA-SIFT, 该方法将特征点邻域像素的梯度分量所构成高维向量投影到前20维本征向量空间, 产生20维的特征描述. Mikolajczyk 等[6]采用PCA 方法将GLOH 的原始272维直方图降到128维. Winder 等[15]根据DAISY 的实验结果结合Shan 等[16]的成果认为, 在高维描述本身就具有独特性而且没有分类标签的前提下, 应用PCA 方法进行特征降维是极为有效的方法. PCA-SIFT 方法虽然可以产生紧凑的低维数特征描述向量, 但该方法需要事先计算本征向量空间, 而且本征向量空间的求解通常需要对高维向量的总体散布矩阵进行奇异值(Sigularvalue decomposition, SVD) 分解, 计算过程十分耗时. 本文针对PCA-SIFT 的该缺点, 提出采用二维主成分分析方法(2DPCA)[17]对梯度向量描述块进行降维来构建特征描述子. 虽然本方法也要事先进行数据块散布矩阵进行奇异值分解, 但由于散布矩阵的低维数特性, 使得求解速度得到了极大的改善.

2DPCA-SIFT 描述子的设计

1.1

PCA-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 1 M t =

M (A i −A ¯) T (A i −A ¯) (1)i =1

其中, A ¯=1 M M

i =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的像素块作为描

述算法的输入, 并计算像素块水平和垂直方向的梯度分量. 因此, 2DPCA-SIFT 的初始特征描述块也包含3042个元素. 与PCA-SIFT 中将归一化处理后的3042个梯度分量构造成向量不同, 本文将计算得到的梯度分量构造成矩阵形式使得其适合采用2DPCA 方法进行处理. 为构建2DPCA-SIFT 梯度分量矩阵, 直接的想法是将PCA-SIFT 中的高维向量转化为矩阵块的形式. 如图1(a)所示, 将PCA-SIFT 中3042维向量转化成39×78维梯度分量矩阵. 矩阵中每一行元素由41×41像素块中对应像素产生的各39个水平梯度分量和垂直梯度分量交替排列而成的. 得到的矩阵按Bi-2DPCA 方法, 首先在水平方向进行投影得到39×n 1维的2DPCA 特征描述. 对得到的特征描述在垂直方向上进行第二次投影, 最终产生n 2×n 1维的2DPCA-SIFT 特征描述. 为了简化特征匹配, 需要将矩阵形式的2DPCA-SIFT 特征描述转化为向量形式.

(a)39×78维梯度分量矩阵构建特征描述方法

(a)Building feature descriptor from 39×78gradient patch

(b)采用水平和垂直梯度矩阵构建特征描述方法

(b)Building feature descriptor from horizontal and

vertical patchs

图1两种2DPCA-SIFT 特征描述构建方法Fig. 1

2DPCA-SIFT descriptors

采用图1(a)方法构建的梯度矩阵块内的元素在隔列抽取之后才满足特征点邻域像素块的原始位置排列. 按奇数列和偶数列抽取分别得到如图1(b)所示的两个39×39梯度分量矩阵. 这样做的动

机是我们认为2DPCA 是对图像矩阵进行投影, 在构建梯度矩阵时, 希望保留邻域像素的空间位置关系. 因此, 采用水平梯度分量矩阵和垂直梯度分量矩阵双矩阵来表示特征点邻域的梯度信息. 值得注意的是, 此时需要对两个分量矩阵分别进行强度归一化预处理. 预处理之后各自进行水平和垂直两个方向的投影, 得到两个n 2×n 1维的向量. 最终的2DPCA-SIFT 特征描述由这两个向量合并而成, 维数为n 2×n 1+n 2×n 1.

为区分两种2DPCA-SIFT 构建方法, 在后续的描述中我们将图1(a)采用单个梯度矩阵的特征描述方法命名为Original 2DPCA-SIFT (Ori2DPCA-SIFT), 图1(b)采用两个分量矩阵计算特征描述的方法称为2DPCA-SIFT.

2实验结果与分析

为验证提出算法的性能, 我们在Dell 360硬件平台上采用VS2008+OpenCV2.3来实现SIFT, PCA-SIFT, Ori 2DPCA-SIFT 和2DPCA-SIFT 方法.

本文采用Mikolajczyk 数据集[6]来探讨本文所述的Ori 2DPCA-SIFT 和2DPCA-SIFT 特征描述子的特征匹配性能. 匹配结果采用查全率–查错率(Recallvs. 1-Precision) 来进行评价, 特征之间的相似性采用欧氏距离来度量, 与PCA-SIFT 方法[14]原文采用的度量准则一致, 当特征之间的距离小于某个阈值(Threshold),则认为是一对匹配. Mikolajczyk 等[6]的研究认为, 不同的评价准则对算法性能排序的影响不大, 但相比于最近邻(Near-est neighbor) 准则和最近邻距离与次近邻距离比(Nearestneighbor distance ratio) 准则, 基于阈值(Threshold-based)的方法更适合在数据库中的特征搜索, 并且能反映出特征描述在空间中的分布情况.

2.12DPCA-SIFT 参数选择

从图1中可以看出, Ori 2DPCA-SIFT 和2DPCA-SIFT 在构建特征描述向量过程中都需要确定水平方向上的投影向量个数n 1和垂直方向上的投影向量个数n 2. 参数n 1和n 2直接决定了Ori 2DPCA-SIFT 和2DPCA-SIFT 的特征描述维数.

Ke 等[14]和Mikolajczyk 等[6]的实验认为PCA-SIFT 在特征维数为36时匹配性能较好, 并且还能有效地控制特征描述长度. 本文方法与PCA-SIFT 方法一样, 目标是寻找一种有效的低维数特征描述方法. 因此, 我们以36维特征描述为基准, 讨论参数n 1和n 2的不同选择对本文方法特征独特性的影响. 图2的结果显示在Ori 2PCA-SIFT 和

2DPCA-SIFT 中, 当n 1≈2·n 2时, 算法产生的特征描述具有较好的性能. 可以看出在大多数情况下, n 1>n 2时, 得到的结果要优于n 1n 2的参数选择能保留更多的样本信息. 算法选择最为流行的SIFT 算法和同样采用降维来产生特征描述的PCA-SIFT 方法. 在实验中, SIFT 产生标准的128维特征描述, PCA-SIFT 采用36维特征描述, 本文方法采用上一节的结果Ori 2DPCA-SIFT (n 1

=9, n

2=4) 和2DPCA-SIFT (n 1=6, n 2=3), 也都产生36维的特征描述.

在尺度和旋转变换实验中, New York 图像包含近90度的纯旋转, Boat 图像包含尺度因子为1∼2.5的尺度变换, 并伴随着30∼45度的旋转. 从图3可以看出, 在查错率

(a)Ori 2DPCA-SIFT

(b)2DPCA-SIFT

图2参数n 1, n 2对特征描述方法性能的影响

Fig. 2

Evaluation for diﬀerentselection of n 1and n 2

2.2图像匹配

我们在Mikolajczyk 数据集[6]上测试本文方法在各种图像变换下的匹配性能, 该数据集中的测试图像包含尺度变换、旋转变换、视角变换、模糊变换、光照变换和JPEG 压缩等6种图像变换, 能全面地测试特征描述方法的性能. 对比

2DPCA-SIFT 和2DPCA-SIFT 方法具有比SIFT 方法更高的查全率, 而在查错率>0. 4时, SIFT 方法的查全率上升更快. 这说明基于降维的方法在低响应率情况下能保持更高的匹配正确率, 这在图像检索等计算匹配特征数目的应用中更具优势. 在纯旋转变换中, PCA-SIFT 和Ori 2DPCA-SIFT 、2DPCA-SIFT 的曲线基本一致, 在具有尺度变换的Boat 图像中, 2DPCA-SIFT 方法略优于其他两种方法.

(a)New York

(b)Boat

图3

旋转与尺度变换效果图

Fig. 3

Performance of rotation and scale changes

图像的模糊变换会影响图像像素强度和边缘

信息. 图4给出了模糊变换图像间的匹配, 我们发现SIFT 在低查错率的情况下要弱于其他三种方法. 有趣的是2DPCA-SIFT 与PCA-SIFT 和Ori 2DPCA-SIFT 的对比中, 在Bikes 图像的低差错率中略微占优, 但在Trees 图像的高查错率部分曲线稍低, 总的来说在模糊变换中三者性能相当. 图5(a)给出了光照变化对特征描述方法的影响, PCA-SIFT 性能最好, 2DPCA-SIFT 与Ori 2DPCA-SIFT 次之. JPEG 压缩变换结果见图5(b),4种算法都显示了较好的匹配性能.

(a)Trees

(b)Bikes

图4

模糊变换效果

Fig. 4

Performance of blur images

图像视角变换主要由相机位置移动引起的, 并会伴随着一定的尺度和光照变换. 本文测试在大约50度视角变换下各算法在结构图像(Graﬃes)和纹理图像(Walls)中的性能. 从图6的结果我们发现, 各算法在结构图像和纹理图像中呈现完全不同的结果. SIFT 在纹理图像中明显优于其他算法, 但在结构图像中也处于明显的劣势. 4种算法在结构图像匹配中效果都比较差, 在查错率达到0.5时, 2DPCA-SIFT 才有0.1的响应率. 我们认为这是由于DOG (Diﬀerenceof Gaussians) 算子本身不具

有仿射不变性造成的, Mikolajczyk 等[6]的研究发现, 在实际仿射变换中, 尺度的变化并不是各向同性的. 因此, 在视角变换中, DOG 算子检测同一位置极值点会发生一定的偏移, 这种偏移在没有交叉垂直边缘的涂鸦图像(Graﬃes)中更为明显[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 and

JPEG compression

总的来说, PCA-SIFT 和本文的两种方法在

各种图像变换中性能基本一致, PCA-SIFT 与Ori 2DPCA 曲线基本相同, 我们认为这是由于三种方法采用相同的梯度分量作为算法输入造成的. 而2DPCA-SIFT 采用的保留空间位置的双梯度矩阵方法在低查错率(小于0.1) 和较大定位误差的情况略优于PCA-SIFT 和Ori 2DPCA-SIFT 算法, 但在总体表现不好的纹理图像中效果也更差. SIFT 算法在查错率低于0.4的情况下总体表现不如其他三种算法, 但我们也发现在查错率高于0.4时, 其他三种算法的响应率会趋于稳定, 而SIFT 会持续上升, 该数据库包含10组不同的场景, 每个场景包含3幅不同图像变换下的图像, 共30幅图像组成. 我们在此数据库中讨论本文方法与PCA-SIFT 和SIFT 在图像检索应用中的性能. 两幅图像之间的相似性由两幅图像之间的匹配特征个数来度量. 采用与文献[14]中相同的记分规则来表示图像检索的正确率, 对每一幅测试图像返回两幅检索到的最相似图像, 如果两幅图像与测试图像在同一组, 则加2分; 若只有一幅图像与测试图像同组, 则加1分; 否则, 不加分. 因此, 整个系统的总分为60分, 算法的图像检说明SIFT 实际可以得到的正确特征匹配总数要多于其他三种方法. 因此, SIFT 比PCA-SIFT 以及本文方法更适用于图像变换估计等对正确匹配数有要求而且可以通过最近邻和模型约束来排除错误匹配的应用. 本文的方法以及PCA-SIFT 方法因为其压缩的特征表示以及在低查错率下更高的响应率, 适合数据库中的特征匹配与搜索.

(a)Graﬃs

(b)Walls

图6

视角变换效果

Fig. 6

Performance of viewpoint images

2.3图像检索实验

我们在一个小型数据库1上进行图像检索实验.

http://www.cs.cmu.edu/˜yke/pcasift

索正确率可由其得分除以60得到.

我们采用基于阈值的方法来度量特征之间匹配的相似性. 在数据库中进行两幅图像相似性度量时, 当发现当前特征与被检索图像某一特征距离小于阈值时, 直接返回其匹配, 不需要继续计算与被检索图像后续特征之间的距离, 与最近邻方法需要遍历数据库中所有特征相比, 可以明显减少匹配计算次数, 有利于提高整个图像检索系统的速度. 但我们也发现同一算法在不同阈值下呈现不同的检索正确率, 我们取该算法最高的正确率结果作为其在图像检索应用中的性能度量. 表1给出了SIFT 、PCA-SIFT 以及本文两种方法的图像检索正确率, 可以看到SIFT 方法的正确率明显低于其他三种方法. 我们认为这与SIFT 方法在低响应率下查错率高于PCA-SIFT 以及本文方法有关. 查错率高意味着要产生相同数量的正确匹配, SIFT 方法会引入更多的误匹配, 这会影响其在图像检索中的性能. PCA-SIFT 、Ori 2DPCA-SIFT 和2DPCA-SIFT 方法匹配结果相同, 均为66. 7%.这是由于三种方法本身性能差别不大, 并使用相同维数的特征描述造成的.

表1

图像检索准确率

Table 1

Percentage of images correctly retrieved in

retrieval application

特征描述方法(特征维数)

正确率(%)

SIFT (128)56.7PCA-SIFT (36)

66.7Ori 2DPCA-SIFT n 1=9, n 2=4(36)66.72DPCA-SIFT n 1=6, n 2=3(36)

66.7

2.4算法运行时间测试

本文方法运行时间包括局部特征描述生成时间和Bi-2DPCA 本征空间的求解时间. 本征矩阵通常是事先训练计算得到, 在产生局部特征时直接对梯度向量块进行两次投影得到特征描述. PCA-SIFT 中的PCA 训练和降维投影采用OpenCV 中的cv-CalcPCA 和cvProjectPCA 函数, 我们认为其是一

种较为优化的PCA 处理方法. 为减少计算机I/O等外部因素对运行时间的影响, 我们对图像检索实验中的30幅图像进行连续的特征提取来估算各算法的计算效率. 30幅图像产生大约33700个特征点. 特征匹配速度测试中采用穷举匹配, 这样能保证各算法在产生相同特征个数的情况下进行的匹配次数也是相同的.

表2给出了SIFT 、PCA-SIFT (36)、Ori 2DPCA-SIFT (n 1=9, n 2=4) 和2DPCA-SIFT (n 1=6, n 2=3) 生成2000个特征描述以及4000000次特征匹配所需要的时间. 从中可以看出, 虽然PCA-SIFT 和本文方法在生成特征描述时, 需要计算邻域范围(41×41) 要大于SIFT 方法生成梯度直方图所需的邻域(约为20×20), 但4种方法的特征生成时间基本是相同的. PCA-SIFT 和本文方法对单位像素只进行垂直和水平方向的梯度分量计算, 因此, 在计算效率上与SIFT 相比并不处于劣势. 在特征匹配效率上, 我们发现36维的特征匹配速度明显快于128维的SIFT 特征匹配, 高维数特征不仅需要占用更多的存储, 在计算特征间距离时也需要更多次数的减法和乘法运算.

表2

特征描述生成与匹配时间

Table 2

Performance of descriptors representation and

matching

特征描述方法(特征维数) 特征生成时间(s)匹配时间(s)

SIFT (128)2.293.69PCA-SIFT (36)2.371.79Ori 2DPCA-SIFT (36)2.331.802DPCA-SIFT (36)

2.29

1.79

本文的方法以及PCA-SIFT 需要事先对本征向量空间进行求解计算, 我们对33700个特征点产生的梯度分量进行训练, 求解PCA-SIFT (36)、Ori 2DPCA-SIFT (n 1=9, n 2=4) 和2DPCA-SIFT (n 1=6, n 2=3) 的本征空间. 表3给出了三种方法的本征空间求解时间以及用本征矩阵对33700个梯度分量进行投影产生特征描述的时间. PCA-SIFT 的本征矩阵求解时间需要45分钟左右, 而本文的两种方法都在10秒之内, 而且虽然2DPCA-SIFT 由于将梯度分量拆分成两个矩阵会比Ori 2DPCA-SIFT 多进行两次奇异值分解, 但求解速度却更快.

我们认为本征空间的解算速度与对应方法的散布矩阵维数和样本散布情况直接相关. 在本测试中, PCA-SIFT 方法的散布矩阵维数为3042×3042, Ori 2DPCA-SIFT 的两个散布矩阵维数分别为78×78和39×39. 2DPCA-SIFT 需要计算4个本征矩阵, 其维数都为39×39. 在对散布矩阵进行奇异值分解时, 我们发现对Ori 2DPCA-SIFT 的

水平方向78×78维散布矩阵求解大约需要6. 8s, 而2DPCA-SIFT 水平方向39×39维散布矩阵求解只需要1. 8s. 第二次垂直方向散布矩阵求解时, 由于样本经过一次投影后相对散布比较集中, 虽然同样是求解39×39维散布矩阵, Ori 2DPCA-SIFT 和2DPCA-SIFT 的求解时间分别为0. 546s 和0. 406s. 在对33700个梯度分量进行投影时, 发现PCA-SIFT 投影速度最慢, Ori 2DPCA-SIFT 次之, 2DPCA-SIFT 最快, 虽然总体来说投影速度对特征描述生成时间影响很小, 但从表2的特征生成时间上可以看出, 三者之间存在细微的差别. 一个PCA-SIFT 的3042维初始向量向3042×36维的本征矩阵投影, 需要109512次乘法和109476次加法运算. 在Ori 2DPCA-SIFT 中, 39×78维梯度分量矩阵依次向78×9维的水平方向本征空间和39×4维的垂直方向本征空间投影得到36维特征共需要28728次乘法和28395次加法运算. 而2DPCA-SIFT 产生36维特征共需4次投影, 乘法和加法运算次数分别为19656和19152. 可见, 本文方法在求解本征空间和投影计算效率上都优于PCA-SIFT 方法, 在存储上, PCA-SIFT 方法的本征空间矩阵也明显大于本文的方法.

表3

本征矩阵生成以及投影时间

Table 3

Performance of eigenspace calculation and

projecting

特征描述方法(特征维数) 投影矩阵生成时间(s)投影时间(s)

PCA-SIFT (36)2736.73.11Ori 2DPCA-SIFT (36)8.171.762DPCA-SIFT (36)

5.16

0.74

3结论

本文将2DPCA 方法引入到局部特征描述的构建中, 提出的Ori 2DPCA-SIFT 和2DPCA-SIFT 在图像变换和图像检索测试中与PCA-SIFT 方法性能相当, 在特征描述维数、检索正确率以及低差错率下的匹配响应率等方面优于SIFT 方法. 尽管如此, 由于采用和PCA-SIFT 相同数量的梯度分量作为描述的输入, 本文方法相比与PCA-SIFT 方法特征描述的独特性没有显著的提高. 相比于PCA 降维方法, 2DPCA 方法在本征空间求解和投影计算速度有了明显的提高. 从Ori 2DPCA-SIFT 和2DPCA-SIFT 方法的计算效率分析中可以看出, 采用两个分量矩阵分别进行投影的计算效率优于高维数的单个矩阵. 这为2DPCA-SIFT 方法的进一步扩展提供了可能. 在未来的工作中, 我们希望用更多的邻域信息如灰度、对比度、色彩等对2DPCA-SIFT 方法进行扩展, 对每一类信息构造二维矩阵,

采用2DPCA 进行两个方向的降维处理产生该类信息的低维描述, 最后, 将各类信息的低维描述组合起来得到最终的局部特征描述. 采用多类信息来构成最终的特征描述有利于提高特征描述的性能, 而且2DPCA-SIFT 的计算效率也使得这种扩展成为了可能.

References

1Lowe D G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision , 2004, 60(2):91−1102Louren¸c o M, Barreto J P A, Vasconcelos F. sRD-SIFT:key-point detection and matching in images with radial distor-tion. IEEE Transactions on Robotics , 2012, 28(3):752−7603Lin Hai-Feng, Ma Yu-Feng, Song Tao. Research on object tracking algorithm based on SIFT. Acta Automatica Sinica , 2010, 36(8):1204−1208

(蔺海峰, 马宇峰, 宋涛. 基于SIFT 特征目标跟踪算法研究. 自动化学报, 2010, 36(8):1204−1208)

4Rublee E, Rabaud V, Konolige K G, Bradski J R. ORB:an eﬃcientalternative to SIFT or SURF. In:Proceedings of the 2011IEEE International Conference on Computer Vi-sion. Barcelona, Spain:IEEE, 2011. 2564−2571

5Tian Q, Zhang S L, Zhou W G, Ji R R, Ni B B, Sebe N. Building descriptive and discriminative visual codebook for large-scale image applications. Multimedia Tools and Appli-cations , 2011, 51(2):441−477

6Mikolajczyk K I, Schmid C. A performance evaluation of lo-cal descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2005, 27(10):1615−1630

7Zeng Luan, Gu Da-Long. A SIFT feature descriptor based on sector area partitioning. Acta Automatica Sinica , 2012, 38(9):1513−1519

(曾峦, 顾大龙. 一种基于扇形区域分割的SIFT 特征描述符. 自动化学报, 2012, 38(9):1513−1519)

8Zeng Hui, Mu Zhi-Chun, Wang Xiu-Qing. A robust method for local image feature region description. Acta Automatica Sinica , 2011, 37(6):658−664

(曾慧, 穆志纯, 王秀青. 一种鲁棒的图像局部特征区域的描述方法. 自动化学报, 2011, 37(6):658−664)

9Bay H, Tuytelaars T, van Gool L. SURF:speeded up robust features. In:Proceedings of the 9th European Conference on Computer Vision. Graz, Austria:Springer, 2006. 404−41710Juan L, Gwun O. A comparison of SIFT, PCA-SIFT and

SURF. International Journal of Image Processing , 2009, 3(4):143−152

11Huang C R, Chen C R, Chung P C. Contrast context his-togram:an eﬃcientdiscriminating local descriptor for ob-ject recognition and image matching. Pattern Recognition , 2008, 41(10):3071−3077

12Liu Ping-Ping, Zhao Hong-Wei, Zang Xue-Bai, Dai Jin-Bo.

A fast local feature description algorithm. Acta Automatica Sinica , 2010, 36(1):40−45

(刘萍萍, 赵宏伟, 臧雪柏, 戴金波. 一种快速局部特征描述算法. 自动化学报, 2010, 36(1):40−45)

13Yang Heng, Wang Qing. A novel local invariant feature de-tection and description algorithm. Chinese Journal of Com-puters , 2010, 33(5):935−944

(杨恒, 王庆. 一种新的局部不变特征检测和描述算法. 计算机学报, 2010, 33(5):935−944)

14Ke Y, Sukthankar R. PCA-SIFT:a more distinctive rep-resentation for local image descriptors. In:Proceedings of the 2004IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington D. C., USA:IEEE, 2004. 506−51315Winder S, Hua G, Brown, M. Picking the best DAISY. In:

Proceedings of the 2009IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Miami, USA:IEEE, 2009. 20−2516Shan H H, Cottrell G W. Looking around the backyard

helps to recognize faces and digits. In:Proceedings of the 2008IEEE Computer Society Conference on Computer Vi-sion and Pattern Recognition. Anchorage, USA:IEEE, 2008. 1−817Yang J, Zhang D Q, Frangi A F, Yang J Y. Two-dimensional

PCA:a new approach to appearance-based face representa-tion and recognition. IEEE Transactions on Pattern Analy-sis and Machine Intelligence , 2004, 26(1):131−13718Yang J, Xu Y, Yang J Y. Bi-2DPCA:A fast face coding

method for recognition. Pattern Recognition Recent Ad-vances . Vienna, Austria:InTech, 2010. 313−340

颜雪军南京理工大学计算机科学与工程学院博士研究生. 主要研究方向为局部特征描述, 机器人控制. 本文通信作者. E-mail:aimar [email protected](YAN Xue-Jun Ph. D. candidate at the School of Computer Science and Engineering, Nanjing University of Sci-ence and Technology. His research in-terest covers local descriptor and robot control. Corre-sponding author of this paper.)

赵春霞南京理工大学计算机科学与工程学院教授. 主要研究方向为智能机器人技术, 图像处理.

E-mail:[email protected](ZHAO Chun-Xia Professor at the School of Computer Science and Engi-neering, Nanjing University of Science and Technology. Her research interest

covers intelligent robotics, image processing.)

袁夏南京理工大学计算机科学与工程学院讲师. 主要研究方向为机器人导航, 复杂环境建模.

E-mail:[email protected]

(YUAN Xia Lecturer at the School of Computer Science and Engineering, Nanjing University of Science and Tech-nology. His research interest covers

robot navigation and complex environmental modeling.)