（信号与信息处理专业论文）局部特征相关性及其在量化中的应用.pdf

u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a ad i s s e r t a t i o nf o rm a s t e r d e g r e e l oc a lf e a t u r er e l a t i o n s h i pa n di t s a p p l i c a t i o ni nf e a t u r eq u a n t i z a t i o n a u t h o r ：h a o y u a ng a o s p e c i a l i t y ：s i g n a la n di n f o r m a t i o np r o c e s s i n g s u p e r v i s o r ：p r o f n , g h a iy urofne na1 ： d r l i a n s h e n gz h u a n g f i n i s h e dt i m e ： m a y , 2 0 1 2 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：酗 签字吼垄! 兰：绰 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 d 公开口保密( 年) 作者签名： 签字日期： 觯 导师签 签字日 摘要 摘要 图像表示问题是图像检索、物体识别等图像分类任务首要解决的基本问题， 图像表示模型的性能对图像分类算法的性能有着决定性影响。词袋模型( b a g o fw o r d s ) 是目前广泛使用的一个图像表示模型，对平移、旋转、缩放等几何 变换具有良好的鲁棒性，在图像检索、物体识别等图像分类应用中取得了巨大 的成功。特征量化是词袋模型的一个核心步骤，对词袋模型的性能有着关键性 影响。但是，现有特征量化方法假设局部特征之间是相互独立的，忽略了局部 特征之间的相互联系，从而降低了词袋模型的性能。 针对该问题，本文尝试利用先进的高维数据分析技术( 稀疏表示和矩阵低 秩恢复) 来挖掘局部特征相互联系( 用图来表示) ，并将其引入到特征量化过 程，旨在提高词袋模型的表达能力，进而提高图像分类算法的性能。 论文的主要研究内容和创新之处包括： 1 提出了一种新的结构性稀疏图构建算法。该算法将图中单个数据对应的 权重系数设定为一组，通过组内使用2 范式约束( 增加表示准确度) ，组 间使用1 范式约束( 获取自适应稀疏图) 的方式，构建结构性稀疏图已2 1 图。该图继承了宅1 图能够自适应的获取稀疏图的优点，并且通过添加数 据之间的相互约束，克服了现有算法只是针对单个数据进行孤立表示的情 况。实验结果表明，所构建的结构性稀疏图能够更加全面地反映数据之间 的信息，特别是在样本标注率低、样本信息相对较少的情况下，该图所反 映出的数据信息能够有效地提升数据降维和分类的效果。 2 提出了一个全新的非负低秩稀疏图( n o n - n e g a t i v el o w r a n ka n ds p a r s e g r a p h ，n n l r s g r a p h ) 构建算法。利用低秩和稀疏的约束能够有效把握 数据的整体和局部信息的性质，通过对图构建的权重同时进行低秩和稀疏 约束，构建更能反映数据关系的非负权重图。因此，获得的n n l r s 图能 摘要 够同时反映子空间结构和局部的线性结构，同时具有了生成性和区分性。 在半监督学习框架之下，分别针对半监督分类和半监督判别分析的方法进 行了构建图的比较，实验结果也证实了基于本文构建算法的构建图的有效 性。 3 提出了一种非负稀疏局部线性编码方法。针对b o w 模型中的特征量化问 题，利用非负稀疏表示技术选择与待编码局部特征处于同一线性空间中的 近邻点，然后以这些近邻点作为局部坐标系对当前局部特征进行线性编 码。实验结果表明，通过考虑局部特征的空间结构，该局部特征编码方法 显著优于现有的特征编码方法，有效地提高了图像非线性特征的区分能 力，更有利于图像分类。 关键词：图模型构建，半监督学习，图像分类，特征量化，词典学习 i i a b s t r a c t i m a g er e p r e s e n t a t i o ni s af u n d a m e n t a lr e s e a r c hs p o ti ni m a g ec l a s s i f i c a t l o n r e g i o n ，s u c ha si m a g er e t r i e v a l ，o b j e c tr e c o g n i t i o n t h er e p r e s e n t a t i o nm o d e l p l a y sad e c i s i v er o l ei nt h ep e r f o r m a n c e o fi m a g ec l a s s i f i c a t i o n a saw i d e l yu s e d m o d e l ，b o w ( b a go fw o r d s ) h a sb e e ns u c c e s s f u l l ya p p l i e dt oi m a g e r e t r i e v a la n d o b j e c tr e c o g n i t i o nw i t hr o b u s t n e s st og e o m e t r i ct r a n s f o r m a t i o n ，l i k et r a n s l a t l o n ， r o t a t i o na n ds c a l i n g t h ev e c t o rq u a n t i z a t i o ni so n eo fi t sk e ys t e p s ，w h i c h h a s as i g n i f i c a n ti n f l u e n c eo nb o wm o d e l 。h o w e v e r ，w i t h o u tc o n s i d e r i n gt h em u t u a l c o n n e c t i o nb e t w e e ne a c hl o c a lf e a t u r e ，t h ec u r r e n tm e t h o d so fv e c t o rq u a n t i z a t l o n o n l yc o p ew i t ht h o s el o c a lf e a t u r e si n d e p e n d e n t l y , w h i c hi sap r i m a r y l i m i t a t l o n o ft h i sm o d e lt oa c h i e v eb e t t e rp e r f o r m a n c e b a s e do na f o r e m e n t i o n e dl i m i t a t i o n ，t h i st h e s i si n t r o d u c e st h el a t e s th l g h d i m e n s i o n a la n a l y s i st e c h n i q u e ，t h a ti ss p a r s er e p r e s e n t a t i o na n d l o w - r a n km a t n x r e c o v e r y ，t oe x p l o i tt h ed e e pr e l a t i o n s h i pb e t w e e ne a c hl o c a lf e a t u r er e p r e s e n t e d b yg r a p h c o m b i n i n gs u c hag r a p hw i t hv e c t o rq u a n t i z a t i o ns t e p ，w e w a n tt o e n h a n c et h er 印r e s e n t a t i o nc 宣p a b i l i t yo fb o wm o d e la n da c h i e v em u c hh l g n e r i m a g ec l a s s i f i c a t i o np e r f o r m a n c e t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r e a sf o l l o w s ： 1 p r o d o s ean a v e ls t r u c t u r a ls p a r s eg r a p hc o n s t r u c t i o na l g o r i t h m b yc o n s l d - e r i n gt h eg r a p hw e i g h t so fe a c hd a t aa so n e g r o u p ，w ei n t r o d u c e 掣2n o 咖a s t h ei n n e rc o n s t r a i n ti nt h eg r o u p ( t oe n h a n c et h ea c c u r a c y ) a n da d o p t 1 n o r ma st h ec o n s t r a i n tb e t w e e ng r o u p s ( t oa c q u i r e a na d a p t i v es p a r s eg r a p h ) i no r d e rt oc o n s t r u c tz 2 1g r a p h t h eg r a p hs i m p l yi n h e r i t st h ea d v a n t a g e o f 宅】g r a p ht h a tc a np r o d u c es p a r s eg r a p ha d a p t i v e l y , a n de x p l o r e s t h er e 。 l a t i o n s h i pb e t w e e ng r o u p so fd a t ab ya d d i n gt h ec o n s t r a i n t b e t w e e ne a c n i i i d a t a , t h u s ，o v e r c o m i n gt h ed r a w b a c ko fc h r r e n tm e t h o 如w h 记虮叩洲n 鼍 d a t ai n d e p e n d e n t l y t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t e t h a ts t r u c t u r a l s p a r s eg r a p hc a ni n 0 r m a t i v e l yr e f t e c tt h ei n f o r m a t i o n b e t w e e n e a c h d a t a w h e ni tc o m e 8t ot h e1 0 wl a b e lr a t ep r o b l e m ，s u c hc o n s 缸似甜g 唧，狃 e s p e c i a l l ye n h a n c e t h ep e r f o r m a n c e 。fd e d u c t i o n o fd a t ad i m e l l s i o na n d d a t a r l a 2 p r 。p 。s ean o v e ln 。n - n e g a t i v e1 0 w r a n ka n ds p a r s e ( n n l r s ) g r a p h i 、h e w e i 曲t so f e d g e s i nt h eg r a p ha r e o b t a i n e db ys e a r c h m g f o r 帅眦导，叭e l 。w r a n ka n ds p a r s em a t r i xt h a tr e p r e s e n t se a c h d a t as a m p l ea sa1 7 e ： c o m b i n a t i 。n 。f o t h e r s t h es 0 - o b t a i n e dn n l r s 锄g rp h 叭a p t 哪e 黑h t h eg l o b a lm i x t u r e 。fs u b s p a c e ss t r u c t u r e ( b yt h e l o w r a n k n e s s ) a n d t h e 1 。c a i i yl i n e a rs t r u c t u r e ( b yt h es p a r s e n e s s ) 。f t h e d a t a h e n c e 也e g r a p h i sb o t hg e n e r a t i v ea n d d i s c r i m i n a t i v e t h ee x p e r i m e n t a lr e s u l t s f o rs e m 卜 s u d e r 、，i s e dc l a s s i 矗c a t i o na n d d i s c r i m i n a t i v ea n a l y s i ss h o wt h ee 胁e n e s s a n ds u p e r i o r i t yo fn n l r s g r a p h 一 3 p r o p o s ean o v e lm e t h 。dc a l l e d n 6 n n e g a t i v es p a r s e1 0 c a l l y h n e a r c o d i n 薯 f n 矗l c l b a s e d 。n t h ev e c t 。rq u a n t i z a t i 。np r o b l e m i nb o wm o d e l , w en d i h en e i g h b 。r i n gf e a t u r e si nt h es a m e1 i n e a rs u b s p a c e f r o m t h e 出饥i o n ，a r y ， a n dt h e nu s et h e s ef e a t u r e sa san e wd i c t i o n a ；r y t oc o n d u c tal i n e a rc o d l n g e x p e r i m e n t a lr e s u l t si n d i c a t et h a tb yc o n s i d e r i n g t h e1 0 c a l 8 u b 8 p a c e 8 翼一 t u 二n s l l ch a so u t p e r f o r m e ds t a t e 一。f - t h e - a r t l o c a lf e a t u r 甜协g 眦也叫s a n ( i sm u c hm 。r ep o w e r f u li ni m a g ec l a s s i f i c a t i o np r o b l e m k e y w o r d s ：g r a p hc o n s t r u c t i 。n ，s e 郦u p e r v i s e d l e a r n i n g , i m a g ec l 础c a t i o n v e c t o rq u a n t i z a t i o n ，d i c t i o n a r yl e a r n i n g i v 目录 目录 摘要i a b s t r a c t i i i 目录v 表格v i i 插图 算法x i 主要符号对照表x i i i 第一章绪论 1 1 1 研究背景 1 1 2 相关工作2 1 3 研究内容一5 1 4 论文安排，6 第二章理论基础 9 2 1 基本算法表示 9 2 2 优化算法实例1 0 2 2 1a l m 对r p c a 的优化算法- 1 1 2 2 2a l m 算法计算l r r 问题1 3 2 3 本章小结1 5 v 目录 第三章图的构建算法1 7 3 1 相关工作1 7 3 2 结构性稀疏图构建算法2 0 3 2 1 研究动机2 0 3 2 2 算法细节2 1 3 2 3 实验和分析2 3 3 3 非负低秩稀疏图构建算法2 7 3 3 1 研究动机2 7 3 3 2 算法细节2 8 3 3 3 实验和分析3 1 3 4 本章小结3 8 第四章特征量化3 9 4 1 相关工作3 9 4 2 非负稀疏局部编码4 1 4 2 1 研究动机4 1 4 2 2 算法细节4 2 4 2 3 实验与分析4 6 4 3 拉普拉斯稀疏编码改进算法4 7 4 3 1 算法细节一4 8 4 3 2 实验和分析5 0 4 4 本章小结5 1 第五章总结与展望5 3 5 1 工作总结5 3 5 2 未来展望5 4 参考文献5 7 致谢一6 5 在读期间发表的学术论文与取得的研究成果6 7 v i 表格 表格 3 1 在不同条件下使用g h f 传播算法的分类的错误率( ) ，其中黑 体部分表示最小的错误率，数据名称之后表示的是样本标记率。 3 6 3 2 在不同条件下使用l g c 传播算法的分类的错误率( ) ，其中黑 体部分表示最小错误率，数据名称之后表示的是样本标记率。 3 7 3 3 不同图在半监督判别分析下的识别错误率比较( ) ，其中黑体部 分为最小错误率的表示，数据名称之后表示的是样本标记率 3 7 3 4 a 固定为1 0 情况之下在p i e 数据上的半监督降维错误率( ) 3 8 4 1 c a l t e c h l 0 1 实验结果4 7 4 2 c a l t e c h l 0 1 下1 5 类实验结果 5 0 v i i 原书为空白页，不缺内容 插图 插图 1 1 论文内容组织。 7 3 1 p i e 数据库中不同构建图的分类错误率 2 6 3 2 重构系数的图 2 6 3 3 实验中使用的数据 3 3 3 4 y a l e b 数据集不同算法的可视化权重矩阵 3 5 4 1 k 近邻算法计算结果 4 1 4 2 实验样本示意图 4 6 4 3 非负约束条件对稀疏表示系数求解结果的影响。 4 7 4 4 c a l t e c h l 0 1 实验数据集 5 0 i x 原书为空白页，不缺内容 算法 算法 增广拉格朗日算法1 0 a d m 算法1 1 矩阵恢复a l m 算法1 2 a l m 求解l r r 问题1 4 使用a l m 算法求解2 1 范式限定问题2 3 使用l a d m a p 的n n s l r r 构建算法 3 0 非负低秩稀疏图构建算法3 2 基于a l m 的非负稀疏编码算法流程4 4 x i 原书为空白页，不缺内容 主要符号对照表 1 范式( 表示所有元素绝对值之和) 0 范式( 表示所有非0 元素的个数) p 范式 核范式( 奇异值之和) 矩阵的秩 矩阵的迹( 矩阵对角线元素之和) 拉格朗日乘数法( a u g m e n t e dl a g r a n g em u l t i p l i e r ) 矩阵对应元素的乘积 低秩表示( l o w r a n kr e p r e s e n t a t i o n ) 向量内积算子 n忆肌呔m r， a r v l 曳 i i i i r 打川o u “ 第一章绪论 1 1 研究背景 第一章绪论弟一旱硒化 随着互联网及多媒体技术的迅猛发展，特别是数码产品和w e b2 0 应用的 普及，互联网中多媒体数据呈爆炸式增长。如何从海量网络多媒体数据中快速 准确搜索感兴趣信息是摆在人们面前的一个巨大挑战。图像因其生动直观、信 息量丰富，受到人们的青睐，成为互联网上一类非常重要的信息载体。图像检 索自然而然成为信息检索中的一个重要研究方向，得到工业界和学术界的极大 重视。目前，各主要搜索网站( 如g o o g l e 、百度等) 都提供基于内容的图像检 索( c o n t e n tb a s e di m a g er e t r i e v a l ，c b i r ) f 1 1 2 1 ，诸多针对特定领域的垂直搜 索( 例如淘淘搜、淘宝图像等) 更是广泛使用了基于内容的图像检索技术。基 于内容的图像检索技术已经成为各主要i t 公司、互联网企业的一个竞争焦点。 特别是，随着移动终端( 如手机) 拍照功能的增强，图像将会成为移动多媒体 搜索的一个主要输入形式，基于内容的图像检索也必将成为诸多移动应用的核 心( 如地标识别、海报搜索等) 。因此，基于内容的图像检索研究就具有非常重 要的学术意义和经济价值。 图像表示是基于内容图像检索系统的基础，对整个系统的检索性能起着至 关重要的作用。在现有各种表示模型中，词袋模型( b a go fw o r d ，b o w ) f 3 1 是目前使用最为广泛的一个图像表示模型。它通过提取图像局部特征f 如s i f t 特征 1 】) ，把局部特征量化为视觉词汇( v i s u a lw o r d s ) ，最后统计各视觉词汇出 现的频率直方图来表示整张图像。通过结合图像的金字塔分解，l a z e b n i k 等人 4 】对经典的词袋模型进行了扩展，使得其在一定程度上保存了局部特征的位置 信息，进一步提高了词袋模型的表达性能。由于对平移、旋转等几何变换较为 鲁棒，词袋模型在场景分类f 4 1 、物体识别f 5 1 等图像分类任务中取得了巨大成 功，并成为了图像检索研究中一个标准图像表示模型。 特征量化作为词袋模型的关键步骤，直接决定了词袋模型的表达性能。其 第一章绪论 目标则是寻找一种局部特征编码方法，实现局部特征从原始特征空间到新特征 空间的映射。长期以来，研究人员将量化后的分类性能主要归结于所选取的词 典，忽视了特征量化方法的重要性，经常采用最简单的最近邻方法实现局部特 征映射。但是，近期研究结果表明，当词典达到一定规模之后，不同词典学习 方法对最终分类结果的影响非常有限。而且在实际应用( 如图像检索) 中，词典 规模一般都比较大，往往在几十万，数百万数量级之上，此时使用简单的随机采 样也可以得到一个令人满意的词典。相反，特征量化方法则会对最终图像分类 结果产生显著影响【6 1 。因此，高效的特征量化算法对于提高词袋模型的表达性 能具有至关重要的作用，并得到了研究者的广泛重视 7 】 8 】【9 1 0 】【1 1 】。但是，现 有特征量化方法存在着一个重要缺陷：现有特征量化方法几乎都是单独对局部 特征进行量化编码，没有考虑局部特征所在空间的结构。事实上，局部特征所 在的空间结构定义了不同局部特征之间的相关性，而这种相关性对于图像表示 极为重要f 1 2 1 。对局部特征相互关系的忽略造成了现有特征量化算法性能的下 降。 基于上述分析，本论文主要研究目标为：围绕着特征量化问题，利用高维 数据分析工具( 稀疏表示和低秩矩阵恢复) 挖掘局部特征所在的低维流形结构， 通过把局部特征相关性引入到特征量化过程，旨在提高特征量化算法的性能， 进而提高词袋模型表达性能。本课题研究成果可以广泛地应用于图像检索、图 像标注、物体识别等领域，有助于提高现有图像检索系统的检索性能。 1 2 相关工作 基于内容的图像检索( c o n t e n tb a s e di m a g er e t r i e v a l ，c b i r ) ，是指直接 采用图像内容进行图像信息查询的检索，即直接输入图像，从图像数据库中检 索与之在内容上一致或相似的图像集合的过程【1 3 】。通常通过对图像底层特征 的比较来实现检索，不同于传统的基于文本的检索方式，输入的不再是文本的 关键词，而是直接针对图像进行检索。已经有大量基于c b i r 的应用服务于我 们周边，例如最早的t i n y e y e + ，作为较早的被广泛应用的图像搜索引擎，能够 通过输入的图片发现图片的来源信息，研究其在互联网中的传播，并且如果输 2 t i n e y er e v e r s ei m a g es e a r c h ：h t t p ：t i n e y e c o m 第一章绪论 入一幅分辨率比较低的图像，能够找出分辨率较高的图片。而相应的大型的互 联网公司也开发了自己的图像搜索引擎，例如g o o g l e 于去年在自己的图像搜索 引擎添加了基于输入图片的搜索。它在其原有的基于关键词的检索窗口之后， 增加了针对网络链接图片和本地图片进行检索的功能，同样能够检索得到高分 辨率的图像，分析匹配同样图片的页面推荐给用户，并获取近似的图像：同样 的，百度之前也给出了自己的以图搜图的搜索引擎识图t ，而微软的搜索引擎 b i n 手中很早的就加入了相似图形检索的功能。而针对特殊的场景，淘宝提出了 c b i r 在电子商务中的应用淘淘搜、淘宝图像i ，针对其服务的产品，进行衣 服、鞋? 箱包等的纵向检索服务，用户可以通过输入拍摄的衣服和鞋子等的照 片在产品库中直接检索。由于这些c b i r 的检索方式，不同于传统图像搜索的 图像到文字，文字再到图像的基于标定的检索，从而大大的减少了语义鸿沟的 影响，而随着计算机技术、以及图像表示识别技术的发展，这些c b i r 在现实 生活中的应用将会更大地影响我们的生活，在将来必定给我们的生活提供更大 的便利。但是，由于现在的应用还处在开始阶段，还有很多性能提升空间，比 如检索的准确率和响应速度等等。 而当输入一幅非常简单的图像，比如大小为1 8 0 x 2 0 0 的图像，虽然在的 视觉上看起来并非如此的大，但是如果将其表示成一个简单的向量，其维度为 3 6 0 0 0 ，现有的分类方法在如此的高维度下的分类效果会大打折扣。而且简单 的像素拉伸方法将原有的二维图像结构强行换成了一维向量的结构，破坏原有 图像的很多内在的联系，没有办法反映出足够多的特征。因此现有的特征提取 算法会使用大量的结构学习的手段对原有的图片进行表示，通过不同的算子表 示不同的结构，从而反映更加全面的特征。可以采用最基本的全局特征进行表 述( 如g i s t 1 4 1 ) ，或者采用局部特征表述的方法，如基本的s i f t 特征f 1 5 、 h o g 特征1 6 1 等等。其中最常用的局部特征莫过于s i f t 特征，由于其具有 尺度和旋转不变性，并且在一定程度上具有光照不变性，被广泛的应用在了图 像物体识别、分类、检索等场景之下。s i f t 特征描述子大小为1 2 8 维，而针 g o o g l ei m a g e s ：h t t p ：i m a g e g o o g l e c o r n 百度识图相同图片搜索：h t t p ：h s h i t u b a i d u c o m 必应b i n g ：h t t p ：i m a g e b i n g c o m 淘淘搜，基于图片搜索的购物网站：h t t p ：t w w w t a o t a o s o u c o r n 图想：h t t p ：i m a g i n e t a o b a o c o r n 3 第一章绪论 对每一幅输入的图像，如果获取的特征点数目过少，无法准确反映出图像的特 征，如果获取的过多又会带来信息表示上的巨大变化。通常只从中选择一部分 进行特征的表述【1 7 】，但是即便如此，如果采用简单的全部表示的方法( f u l l r e p r e s e n t ，f r ) 1 8 1 进行表示的话，保存全部的特征，会极大地增加存储开 销，而过多的匹配过程，也会使得检索效率大幅下降。针对这个问题，一种基 于词袋( b a go fw o r d s ，b o w ) 1 9 1 模型的检索被提出并应用到这个过程中。 词袋模型起初用在文本检索之中，是一种文本检索领域非常重要的检索方 法。它通过选择一个对应的词典，将原有文档中的单词表示为词典中词汇出现 的频率，从而反映出整个文档的特征，并使用此特征进行检索。受此启发，视 觉词袋模型( b a go fv i s u a lw o r d s ) 将图像对应为一篇文章，并将原始局部特 征作为词汇，通过量化操作提取表示出图像的高语义特征，从而很大程度之上 减少对于一幅图像表示的维度，加大检索的速度。这种方法的核心在于寻找合 适词典空间的量化方法，将一幅图片看成是文本中的一篇文章，对该幅图像的 局部特征在词典上进行映射，寻求一组合适的编码表示，从而反映出图像的特 征。这个特征量化的性能对整个系统的性能有着重要的影响。 最初的b o w 模型完全借鉴文本模型，针对局部特征，采用基于特征最近 邻f 3 1 的方法进行特征量化：给定一个固定长度的词典，采用一定的距离判断准 则( 如欧式距离) 获取与最近的距离特征点。并将其对应位置量化系数标记为 1 ，其余标记为0 ，最后针对所有的量化系数进行直方图统计。图像最终使用直 方图向量进行表示。对于这种模型性能提升一般采用更新量化距离的方法。对 这种特征直方图的方式进行细致的分析就会发现，其实质是使用词典中一个视 觉词汇对原始特征进行近似。这种硬判决的操作，仅仅是寻找单一词汇进行近 似，从而使得词典无法准确描述对应特征，带来很大的量化误差。 j i a n c h a oy a n g 9 1 采用稀疏表示的方法，使用特征在词典中的稀疏表示作 为量化系数，力求使用字典中最少的词汇进行有效地表示，并结合金字塔模型 对局部特征位置约束，尽量消除b o w 模型对于图像空间位置信息的丢失，以 获得更好的图像分类效果；之后，利用局部线性嵌入( l l e ) 方法对编码特征 进行优化，j i n j u nw a n g 通过选择稀疏子词典空间进行局部线性编码( l l c ) 1 0 】 的方式进行编码。由于人为选择了更小的特征空间进行表示，虽然在一定程 度上无法取到全局的最优，但是使用稀疏低维空间约束很大程度上确实提升 4 第一章绪论 了识别的性能：f e i f e il i 2 0 1 基于t o p i cm o d e l 的降维方式，采用l d a 2 1 1 或 p l s a 2 2 1 等的概率模型，利用原有的基于文本的表示方法，使特征能够在一个 低维空问更加合适地表示出来，并通过概率模型，更准确地使用词典进行量化， 从而提升系统性能。 上述的特征量化方法主要将量化集中在对单一特征使用词典进行表示的过 程中，忽略了特征之间的相互关系。这些方法虽然能够一定程度提升量化的准 确性，尽可能减少量化误差，但是忽略图像特征之间的相互关系，导致原本比 较相似的特征，在量化之后却可能具有很大差异f 2 3 1 。假设数据分布在同一个 低维流形空间中。基于这种假设，相同的或者相近似的特征应该能够准确的映 射到同一个流形空间中，采用这种假设进行特征量化能够有效反映数据之间的 关系。而单纯使用稀疏表示的方法，无法有效地实现这个目的。 高维数据分析技术，假设数据分布在一个低维的流形空间中，能够有效地 进行图像特征之间的关系度量。这种关系常常通过构建一个无向图进行数据关 系的表征。基于此s h e n g h u ao a o 2 3 1 使用构建的l a p l a c i a n 图，针对特征之间 的原始关系与量化后的关系建立约束，力求使近似特征的量化结果同样相似， 从而使得相似的特征落入同一个流形空间中。由于图模型能够有效地反映数据 之间的内在关系，这种采用l a p l a c i a n 图进行约束的方法，能够将数据之间的 相互关系有效地运用于图像的特征量化之中，从而提升特征量化的性能。 本文针对图模型在表示数据之间关系中的重要作用，试图利用高维数据的 分析方法更加有效地构建数据相互关系，也就是构建新的图模型，并将其引入 到特征量化过程中，从而提高词袋模型的表达能力，进而提升分类性能。 1 3 研究内容 围绕着上述研究目标，本论文研究内容主要包括两个方面：1 ) 局部特征相 互关系图模型构建；2 ) 局部特征相关性在特征量化中的应用。在实际研究中， 高维数据的低维流形空间通常通过构建一个无向图来近似，此时局部特征低维 流形结构挖掘就转换为图构建算法的研究。具体而言，本论文主要研究工作包 括： 针对图构建问题，提出一种新的结构性稀疏图构建算法。其核心思想是， 5 第一章绪论 将每个数据的距离度量函数作为一个组，通过对组内添加2 范式约束，组 间使用1 范式约束，构建一个准确描述并且自适应的稀疏图。与现有图构 建算法相比，该算法添加了数据关系之间的约束，将传统独立的图权重度 量，改变为针对多个数据点的同时度量。实验表明，结构性稀疏图比现有 算法更有效地揭示了数据相关性。 针对图构建问题，提出一种新的非负低秩稀疏图构建算法。其核心思想是 利用高维数据的稀疏性和低秩结构来构建图。稀疏性保证图构建算法可以 较好地捕获数据的局部线性关系；低秩结构则保证图构建算法可以较好地 捕获了数据的全局结构信息( 如类别信息) ，并且对数据噪声更加的鲁棒。 与现有算法相比，非负低秩稀疏图同时利用了数据的局部结构信息和全局 结构信息，从而更好地捕获数据的相关性。实验结果也证明了非负低秩稀 疏图优于现有图构建算法。 针对特征量化问题，提出一种非负稀疏局部线性编码算法。其核心思想 是，利用非负稀疏表示技术选择与待编码局部特征处于同一线性空间中的 近邻点，然后以这些近邻点作为局部坐标系对当前局部特征进行线性编码。 实验结果表明，通过考虑局部特征的空间结构，该局部特征编码方法显著 优于现有的特征编码方法，有效地提高了图像非线性特征的区分能力，更 有利于图像分类任务。 针对特征量化问题，提出了一种改进的拉普拉斯稀疏编码算法。其核心思 想是通过把拉普拉斯图作为一个正则化惩罚项引入稀疏编码过程，从而使 得局部特征之间的相关性在编码后得以保持，以此提高稀疏编码算法性 能。与原始拉普拉斯编码算法2 3 1 不同的是，本论文利用稀疏表示技术来 构建图，从而更准确地揭示了局部特征的相关性。实验结果表明，改进后 的拉普拉斯算法具有更好的编码性能，更有利于分类。 1 4 论文安排 论文共包含五个章节，图1 1 给出了本文的主要研究内容的安排以及对应的 立h 覃印 6 第一章绪论 图1 1 论文内容组织 第二章理论基础 针对本文后续研究所需要的求解稀疏和低秩约束下的优化问题，采用合理 的凸函数进行近似，并使用凸函数优化算法进行优化，是一个行之有效地求解 低秩和稀疏约束的手段。本章主要介绍文章后续章节所使用的基本的凸优化增 广拉格朗日算法，并针对后面的问题所面临的具体优化问题以对应的优化求解 表达式，给出对应的实现手段，为后面不同模型约束下的算法求解提供了有效 的技术支持。 第三章图的构建算法 本章首先回顾了目前图构建算法的相关内容，针对现有构建图中存在的不 7 第一章绪论 足，从不同的角度讨论并提出了两种新的图构建算法。通过图构建过程使用2 - 1 范式进行约束，将每一个数据的图表示系数作为一个组，并且组组之间保持稀 疏的关系，使用这种方法构建的z 2 。图能够反映更多的数据之间的相互关系； 通过对构建图采取低秩和稀疏的约束，利用用稀疏性质表示局部线性空间而低 秩属性约束全局结构的性质，构建出的n n l r s 图能够更好的反映数据的全局 线性结构，并提供更多的数据之间的相互信息。在半监督学习框架下，使用上 述两种的图相对于其他的构建算法具有更好的性能表现，从而验证了上述两种 图构建方式的有效性。 第四章特征量化 在这一章通过利用图构建的算法，将所构建的图应用在视觉词袋模型中的 特征量化部分。针对特征量化中两个非常重要的量化算法l l c 和稀疏表示算 法，利用图模型能够有效地解释特征之间的相似关系，并且表征相应特征空间 的性质，将构建的图引入到特征量化的过程之中，从而提升量化的性能。首先， 利用稀疏性质对于寻找局部特征空间的性能，结合基本的l l c 编码方法，针对 寻找到的子空间进行特定的特征量化，从而提升了分类的性能；后面利用稀疏 表示对于数据之间相互关系的反映，并将构建的稀疏图引入拉普拉斯量化算法， 力求量化前后的相似特征能够对应到同一个特征空间。在b o w 模型下的图像 分类实验也证实了上述结合构建图的算法能够有效地提升特征量化编码的性能。 第五章总结与展望 对本文的工作进行了总结，指出了论文的主要贡献。并且展望了下一步的 工作目标和方向。 8 第二章理论基础 第二章理论基础 弟一早埋比垂们函 本文主要利用高维数据分析技术( 低秩矩阵恢复、稀疏表示) 来挖掘数据 之间的相互联系，涉及到高维凸优化问题求解。为了方便后面算法阅读，本章 对论文用到的主要高维凸优化问题求解算法进行简单介绍，并给出利用这些算 法求解相关高维凸优化问题的实例。 2 1 基本算法表示 传统的稀疏和低秩表示，使用矩阵的秩和0 范式进行约束。由于上述两 个函数非凸，无法使用凸优化方法进行求解。通过t a o 2 4 1 等人的努力，发现 这种约束在一定条件之下能够转化为核范式和1 范式这种凸函数形式进行求 解，由此基于凸优化的一些求解算法便被广泛使用起来。增广拉格朗日算法 ( a u g m e n t e dl a g r a n g i a nm e t h o d ，a l m ) 是一系列进行限定优化问题的求解算 法。它通过将限定问题替换为一系列的非限定问题从而进行求解。z h o u c h e n l i n 等人通过使用a l m 算法，将其用于低秩和稀疏矩阵的求解，取得了非常好 的效果，这种算法较之前常规算法a p g ( a c c e l e r a t e dp r o x i m a lg r a d i e n t ) 在速 率上有了很大的提升，