有效图像块描述子分析范文

本站小编为你精心准备了有效图像块描述子分析参考范文，愿这些范文能点燃您思维的火花，激发您的写作灵感。欢迎深入阅读并收藏。

《软件学报》2015年第十一期

1图像特征表示方法概述

设计图像的特征表示是计算机视觉中一项非常基本的研究内容,图像的分类、检索、标注等工作都是以提取图像特征为初始步骤,好的特征表示可以在相关图像分析中取得更佳的效果.因此,图像特征的设计与构造,直接影响算法的性能.而如何定义一个好的图像特征却是非常困难的:一方面,设计的图像特征对于同一类别下图像之间的变化(比如尺度、光照变化、对象位置变化等)要有足够的鲁棒性;另一方面,设计的图像特征要具备足够的判别性来处理不同类别间图像的变化.近年来,研究者提出了大量的底层特征用于各种图像分析任务,其中最具有代表性的是基于梯度朝向直方图的SIFT(scale-invariantfeaturetransform)[1]和HOG(histogramoforientedgradient)[2].尽管这类特征取得了一定意义的成功,但研究者发现,这类单一的底层特征并不足以在某些应用上达到更好的效果,因此提出了一类中间层的图像特征表示方法.其中,BoW(bagofwords)[3]是这类图像特征表示方法的典型代表,该方法在场景分类中获得了较好的性能.BoW算法生成图像特征表示分为3个过程:图像底层特征的获取、学习过完备字典和计算图像的码字直方图表示.然而,BoW方式并没有考虑特征向量在图像空间上的位置关系,使得其特征描述能力并没有达到最大化.为了弥补这一缺陷,空间金字塔匹配(spatialpyramidmatching,简称SPM)[4]方法通过在一幅图像的不同层次上计算码字直方图,形成了一个BoW多层特征,将BoW模型与图像空间进行合理融合.然而,由于SPM方法利用直方图交核函数来度量两幅图像间的相似度,导致无法产生低维度的图像特征表示,而且需要完整计算训练集图像间相似度的Gram矩阵,因此,其算法复杂度为O(n2)(其中,n为训练集中图像的个数).为了解决这一问题,有效匹配核算法(efficientmatchkernel,简称EMK)[5]在码字间相似性的基础上构造了一个低维特征映射空间,整个图像的特征可以表示为码字映射在这个低维特征空间后的平均,且可以采用线性SVM方法训练分类器,在图像分类应用中获得了非常不错的效果.然而,有效匹配核算法仍然依赖于人为定义的图像局部特征(如SIFT或HOG),只不过是通过计算有限维空间的局部线性特征表示来推出整体图像的线性特征.

Bo等人扩展了有效匹配核算法并提出了核描述子(kerneldescriptor,简称KD)[6]方法.这种方法只需定义任意两个局部图像块之间的相似性,且该相似性函数满足核函数定义.由于每个核函数都隐性定义了一个映射,它将图像块映射为再生核希尔伯特空间(reproducingkernelHilbertspace,简称RKHS)中一个非常高维的向量,这样,核函数可以表示为RKHS中两个高维向量的内积,通过核主成分分析(kernelprincipalcomponentanalysis,简称KPCA)[7]算法,可以由核函数推出图像块特征的有限维线性表示.这种低维空间中的表示就称为核描述子,并且采用EMK算法将其推广到整个图像的特征表示.尽管核描述子方法的设计思想较为新颖,但仍然存在计算复杂度过高这一缺陷,限制了其在大规模图像数据库上的应用.事实上,在KPCA方法的离线阶段,所有联合基向量对之间的相似性都需要计算,这是非常耗时的.更重要的是:在线阶段计算一个新图像块的特征映射时,该图像块与所有联合基向量之间的相似性也是需要计算的,而这实际上是不需要的.Xie等人[8]通过使用不完整Cholesky分解替代KPCA算法,成功地解决了这个问题,并且通过迭代,应用不完整Cholesky分解算法表示整个图像特征[9].但文献[8,9]中,通过不完整Cholesky分解得到的标志联合基向量并没有对应实际的图像块,因此,其产生的特征判别能力并没有最大化地得到利用.

Wang等人提出了有监督的核描述子方法[10],该方法利用训练集中的图像类标来辅助设计底层图像块特征.尽管他们利用该特征取得了不错的分类效果,但这个算法运行过程中需要大量有类标的图像,并且对象优化函数求解过程复杂,时间复杂度过高.除了上述生成图像底层特征表示的方法以外,另外一类构成图像特征的方法基于深度学习理论.2006年,Hinton等人[11,12]提出了用于深度信任网络(deepbeliefnetwork,简称DBN)的无监督学习算法,DBN的多层结构,使得它能够学习得到层次化的特征表示,实现自动特征抽象,文献[12]将DBN模型成功用于手写数字识别应用上.Bengio等人在文献[13]中提出了基于自编码器(auto-encoder)[14]的深度学习网络,在手写数字识别图像数据库上得到了类似的实验结果.另外,文献[1517]提出了一系列基于稀疏编码的深层学习网络,在图像应用中取得了一定的成功.LeCun等人用误差梯度设计并训练卷积神经网络(convolutionalneuralnetwork,简称CNN),其在图像分类,特别是手写体字符识别应用中得到优越的性能.在此基础上,Krizhevsky等人[21]将CNN模型应用到分类大规模ImageNet图像数据库,更加充分地显示了深度学习模型的表达能力.尽管在深度学习模型下获得的图像特征有很强的判别表示能力,但其要求计算机硬件条件较高,单机环境下很难实现.除此之外,更加详细地介绍图像特征描述子领域的综述可以参考文献[23].本文在大数据时代背景下,为了能够快速得到图像块的线性特征表示,提出了有效图像块描述子(efficientpatch-leveldescriptor,简称EPLd)方法.该方法在不完整Cholesky分解基础上,可以自动地进行图像块筛选,对于求解新图像块的线性特征表示,只需计算它和一小部分基图像块的相似性就足够了.有了图像块的特征表示之后,一幅图像就对应着一个图像块特征的集合,该集合可以看作是特征空间中基于某个分布的样本集,这样,两幅图像之间的差异可以看作两个分布的距离.本文采用基于高维概率分布的MMD距离[24]进行估算,进而计算两幅图像间的相似性.本文首先介绍核描述子方法,然后给出有效图像块描述子算法的具体实现过程以及如何利用MMD距离计算两幅图像的相似性,并在几个著名的图像分类数据库上进行实验,最后给出工作的结论和展望.

2核描述子方法简介

核描述子方法是对图像像素点属性(梯度/形状/颜色+位置)基础上生成的联合基向量应用KPCA方法,从而计算新图像块的有限维特征表示.为了方便叙述,本文采用像素点的梯度属性来介绍核描述子方法.通过公式(2)可以看到,核描述子方法的主要缺陷有以下3点:(1)算法计算复杂度高,因为需要对dodp维的联合基向量形成的Gram矩阵计算特征值分解,如果联合基向量的维度过高或者个数过多,KPCA算法甚至无法实施;(2)对联合基向量进行KPCA获得的tij并不是稀疏的,这也就意味着在计算新图像块的特征表示时,需要和所有的联合基向量进行在线计算,所以算法需要存储全部的联合基向量;(3)算法无法进行特征选择,即,并不知道联合基向量中哪些样本最具代表性.

3有效图像块描述子算法

针对核描述子方法的3点不足之处,文献[8]解决了其主要缺陷的第一、第二两点,但是文献[8]在本质上仍然使用联合基向量,所以没有明确地进行特征选择,即,找出哪些图像块是最具代表性的,使得其特征表示能力并没有达到最大化.为了更加完善地解决核描述子方法的缺陷,本文提出了一种新的图像块特征表示方法,称为有效图像块描述子.该方法基于对图像块相似度矩阵执行不完整Cholesky分解。总体上来说,有效图像块描述子算法由两部分构成:1)首先从训练图像集中均匀抽取足够的图像块,然后在这些图像块形成的Gram矩阵上执行不完整Cholesky分解算法.如果设定N代表图像块的个数,M代表分解后矩阵的秩,通常情况下,M<<N.这样做的好处有两点:首先,在分解过程中只需要按需计算O(MN)个Gram矩阵元素的值;其次,对Gram矩阵执行Cholesky分解的时间复杂度为O(M2N),远远低于KPCA算法的O(N3).2)经过第1步分解步骤之后,选择出了M个最具代表性的基图像块,新图像块的特征表示仅仅通过O(M)次计算就可以得到.算法的具体步骤将在以下部分详细介绍.

3.1Gram矩阵的低秩近似半正定的Gram矩阵K可以分解为GGT,所以不完整Cholesky分解的目标就是找到一个矩阵G,其大小为NM,使得TGG在M足够小的情况下近似K.在执行不完整Cholesky分解算法的过程中,选择出M个最具代表性的基图像块,利用所有图像块和这M个基图像块之间的相似性,可以近似恢复Gram矩阵K.这里,M的值是可以通过算法在线确定的,由算法中提前给定的近似精度参数来控制.关于不完整Cholesky分解的详细执行过程可以参考文献[26],其中,作为输入参数的Gram矩阵K实际上是按需计算的,即,算法执行过程中需要用到哪两个训练图像块间的相似度,就按照公式(1)计算得到.算法执行后,就得到了一些具有代表性的基图像块,用向量P保存基图像块的索引序号,同时得到了矩阵G,使得.TGGK

3.2构造图像块特征映射算法一旦获得了NM的矩阵G,新图像块的特征(有效图像块描述子)就可以由G构造.其中,新图像块特征维度大小由M确定,每一维度i的值可由新图像块与P(i)所指示的基图像块间相似性K(newpatch,P(i))恢复得到。通过算法1可以看到:选择出的M个最具代表性的基图像块可以看成是一系列局部图像块的非线性滤波器,将每个新图像块和这些基图像块进行相似性度量的过程,也可看成是对这个新图像块进行特征提取的过程.另外,针对图像块相似度矩阵执行不完整Cholesky分解往往可以保证获得精度非常高的低秩近似,且分解过程中只与某些训练样本(图像块)有关.也就是说,利用这些训练样本就可以很好地近似恢复相似度矩阵,所以训练集中的图像块具有不同程度的重要性.因此,我们称重要性最高的前M个图像块为“最具代表性”的基图像块.为了更加形象地展示这些重要的基图像块,我们在Scene-15图像库上提取了最重要的前16个基图像块,如图1所示(每个图像块由其像素点的梯度幅值来表示).可以看到,每个图像块都包含了丰富的边缘和纹理信息.本文提出的有效图像块描述子算法不只继承了文献[8]的有效性,而且很好地解决了核描述子算法中的第3点缺陷,最大限度地发挥了图像块特征的判别能力.

4利用MMD距离计算图像间的相似性

基于算法1,每一个图像块都可以用有效图像块描述子来表示.一幅图像通过稠密采样确定很多关键点,每一个关键点都对应着一个局部的图像块,因此,一幅图像就对应着一个局部特征的集合.假定图像I1包含m个图像块,则其特征集合可以表示为Fp(patchp1,patchp2,…,patchpm),图像I2包含n个图像块,其特征集合表示为Fq(patchq1,patchq2,…,patchqn).Fp可以看作特征空间中来自分布p的一个样本集,同样,Fq也可以看作是来自分布q的样本集.这样,图像I1与I2之间的差异性就可以由p和q两个分布的距离表示.当然,这两个概率分布之间的距离只能通过这两个样本集进行估算.为此,本文采用基于高维概率分布的MaximumMeanDiscrepancy(MMD)距离[24]进行估算.MMD距离可以看作是将两个概率分布,通过非线性核函数映射到再生核希尔伯特空间(RKHS)后均值的距离.对于上述分布p和q的MMD距离估计可由公式(3)计算。单纯地利用公式(3),并没有考虑局部特征在整幅图像上的空间分布信息.为了解决这个问题,本文首先采用空间金字塔方法将整幅图像进行逐层划分;然后,在两幅图像每个层次对应的小图像上计算它们之间的MMD距离;最终,将所有层次的MMD距离按照其对应层次的权重进行汇总求和,然后度量两幅图像I1与I2之间的差异性.

5实验

本文使用像素点的梯度、形状和颜色属性分别构造基于梯度的有效图像块描述子(EPLd-G)、基于形状的有效图像块描述子(EPLd-S)和基于颜色的有效图像块描述子(EPLd-C).为了测试有效图像块描述子算法的性能,分别在3个著名的图像分类数据库(Scene-15,Caltech-101[28]和UIUC-8[29])上做了实验.在接下来的实验中,计算3个不同类型的有效图像块描述子都是首先将图像按照固定比率缩放到不超过300300像素点;特别地,在计算EPLd-G和EPLd-S时,将缩放后的图像中的像素点的灰度值标准化为[0,1]范围.图像块通过每隔8个像素点的稠密采样方式从训练集图像中进行抽取,大小为1616像素点.EPLd-All是将EPLd-G,EPLd-S和EPLd-C这3个描述子串接起来形成的.训练线性SVM分类器使用LIBLINEAR[30],其中,图像间的相似性利用MMD距离来定义.在计算MMD时,将图像按照11,22和33分为3个层次来汇总求和,尺度参数在不同的数据库上利用交叉验证方法确定.所有的实验均重复10次,每次的训练集和测试集都随机抽取确定,将10次分类准确率的平均值和方差记录下来.实验中的其他参数从公平比较的角度考虑,与文献[6,8]设置相同.

5.1Scene-15Scene-15场景数据库包含4485张图片,这些图片分属15个类别,有室内场景和室外场景,每一个类别包含200张~400张图片不等.按照惯例,从每个类别中随机抽取100张图片作为训练,剩余图片作为测试.在算法中设置Pivots的个数为200,即,利用不完整Cholesky分解选出200个最具代表性的基图像块来构造维度为200的有效图像块描述子.实验结果列在表1中(其中,KD代表核描述子方法[6],EKD代表有效核描述子方法[8],EPLd代表本文提出的有效图像块描述子方法),EPLd方法获得在这个数据库上的最佳分类准确率(87.0%).另外,EPLd方法在所有4种不同情况(梯度、形状、颜色和上述3种属性的汇总)下的性能均超过了文献[6,8].在实验中,除了测试分类准确率来体现EPLd的判别能力,还通过不同维度下测试分类准确率来体现EPLd的有效性.我们发现,在特征维度只有50维的情况下也获得了接近最优分类准确率的性能,这充分体现出EPLd算法的有效性和健壮性.事实上,通过表2可以看到:特征维度从50维增加到300维,分类准确率并没有得到明显的提升.造成这一现象的原因是,不完整Cholesky分解容易获得高质量的低秩近似.表2中的数据表明:即使是50维的低秩近似也足以体现Gram矩阵中的关键信息,而这些关键信息直接决定了分类的性能.在后面的实验中,从算法效率的角度考虑都使用了100维的特征表示.

5.2Caltech-101Caltech-101图像数据库包含9144张图片.这9144张图片隶属于101个对象类别外加一个背景类别,每个类别中的图片在31张~800张不等.表3中,将EPLd与其他有代表性的描述子算法进行了对比.同样根据惯例,每个类别随机挑出30张图片进行训练,从剩余图片中挑选不超过50张进行测试.可以看到:EPLd算法达到了最佳的分类准确率(77.1%),甚至在仅仅使用梯度属性的情况下(EPLd-G)也达到了非常不错的分类效果(73.7%).

5.3UIUC-8UIUC-8图像数据库包含1579张图片,这1579张图片隶属于8个运动类别,每个类别下包含图片137张~250张不等.按照惯例,随机从每个类别中抽取70张图片进行训练,从剩余图片中挑选60张进行测试.分类准确率结果列于表4中.通过表4可以看到,EPLd-All非常接近最佳分类准确率(87.2%vs.87.23%).在实验部分的最后,本文对比了构造3种不同描述子(EPLdvs.KDvs.EKD)的计算效率.其中,最耗时的是形状特征,一幅标准图像(最大300300分辨率,图像块大小为1616像素点,图像块间隔8个像素点)上的EPLd-S与EKD-S描述子在Matlab环境下计算需要耗时2s,而KD-S需要耗时2.5s.对于梯度特征,EPLd-G与EKD-G描述子耗时0.9s,KD-G耗时1s.以上对比结果列在表5中.表5中的对比结果是在生成100维特征情况下得到的,如果提高特征的维度,EPLd与EKD的计算效率提升相对于KD会表现得更加明显.另外一点需要指出的是:EPLd与EKD的计算耗时虽然基本相同,但EPLd描述子的特征判别能力相对于EKD描述子要强很多,这一点通过在3个图像数据库上的实验对比结果可以得到印证.所以,综合考虑,EPLd描述子无论在计算效率还是在判别能力上都要优于EKD和KD描述子.

6结束语

本文提出了有效图像块描述子算法.该算法的主要思想是:通过不完整Cholesky分解对图像块的相似性进行逆向学习,选出具有代表性的基图像块.这些基图像块可以看成是一系列的非线性滤波器,将每个新图像块和这些基图像块进行相似性度量的过程,就是对这个新图像块进行特征提取的过程.另外,本文还设计了更为优秀的基于局部特征的整体图像相似性度量,也就是利用MMD距离计算两幅图像之间的相似性,该相似性度量方式不仅能够反映局部图像特征之间的相似性,而且能够有效地利用特征的空间分布信息,从而最大限度地提高整体图像相似性度量的精确度和敏感度.实验结果显示:EPLd方法相对于KD方法和其他一些代表性的方法,在3个著名图像分类数据库上都获得了非常不错的性能.

作者：谢博鋆 朱杰 于剑 单位：交通数据分析与挖掘北京市重点实验室 河北省机器学习与计算智能重点实验室 中央司法警官学院 信息管理系