（计算机应用技术专业论文）语义判别投影在图像检索中的应用.pdf

摘要 摘要 随着数码设备的普及，互联网的兴起，每天将产生大量数字图像。为了有效 的存储、管理图像数据库，需要对图像库进行索引，按特定的需求检索图像。怎 么根据数字图像的视觉内容有效地管理图像库是当前研究的一大热点。为此，基 于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ：c b i r ) 受到广大计算机视觉、 机器学习等领域研究人员的广泛关注。经过十几年的努力，基于内容的图像检索 依然有两个基本问题有待解决。 首先，用于描述图像视觉内容的特征向量，如颜色、纹理、形状、空间关系 等等，一般维数比较高。很多情况下都是从几百到几千，一般的机器学习方法不 能在这么高维的特征空间学习。这就是所谓的“维数灾难。 其次，基于内容的图像检索中用于刻画图像视觉内容的低维特征与高层语 义概念之间不存在直接的联系，这就是所谓的“语义鸿沟”。 为了更好的揭示低维视觉特征与高层语义概念间的联系，本文提出一种基 于拉普拉斯的学习方法，学习得到的语义子空间为基于内容的图像检索提供更 强的判别表示。 本文提出的方法在构建邻接图时，不仅考虑到表示描述信息的无类别的视 觉相似性，而且包含了表示判别信息的语义相异性。充分利用这两种信息学习得 到语义子空间。通过引入一个惩罚参数7 ，本文提出建立一个差式约束优化问题。 那么最优投影就可以通过矩阵的特征值分解求得。创建的邻接图用一个关系矩 阵表示，这样，计算复杂度和计算量都比比保局投影和局部判别嵌入要小。另一 方面，学习的得到语义子空间不仅具有保持局部几何特性，而且全局相关信息也 得到很好地保持。以前相关学习方法都存在奇异性问题，而且不能确定学习后子 空间的维数。本文提出的方法解决了这两个问题。 本文侧重研究子空间学习方法在基于内容的图像检索中的应用，提出一种 新的子空间学习方法“语义判别投影”，通过学习描述信息和判别信息得到 新的语义子空间。本文用一个图描述图像间基于内容的视觉特征的相似性，用另 一个图表示图像间的语义相异性。接着，求解一个带惩罚参数的差式约束优化问 题。本文提出的语义子空间学习方法避免了奇异性问题，而且能学习得到一个最 优维。同样地，本文提出的方法也可应用于再生核希尔伯特空间，得到称为“核 广东工业大学工学硕士学位论文 语义判别投影 的学习方法。随后，本文提出另外两种扩展学习方法二维语 义判别投影和通过相关反馈增量学习的方法。实验结果表明，本文提出的方法 比当前其它学习方法具有更好的检索性能。最后，总结全文并探讨进一步研究工 作。 关键词 基于内容的图像检索；子空间学习；数据降维；语义判别投影；核方法； 张量学习；相关反馈 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fd i g i t a li m a g i n gt e c h n o l o g ya n dt h ep o p u l a r i t yo fw o r l d w i d ew e b ，g i g a b y t e so fi m a g e sa l eg e n e r a t e de v e r yd a y i ti sac h a l l e n g et oe f f e c t i v e l y m a n a g ei m a g e sv i s u a lc o n t e n t 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 ) h a sr e c e i v e d m u c hi n t e r e s tf o rt h i sp u r p o s e h o w e v e r ，t h e r ea l es t i l lm a n yo p e ni s s u e st ob es o l v e d f i r s t l y , t h ev i s u a lc o n t e n ts u c ha sc o l o r , s h a p e ，t e x t u r e ，i se x t r a c t e d f r o ma ni m a g e a sf e a t u r ev e c t o r s t h ed i m e n s i o n a l i t yo ff e a t u r es p a c ei su s u a l l yv e r yh i g h i tr a n g e s f r o mt e n st oh u n d r e d so ft h o u s a n d si nm o s tc a s e s t r a d i t i o n a lm a c h i n el e a r n i n ga p - p r o a c h e sf a i lt ol e a r ni ns u c hah i g h - d i m e n s i o n a lf e a t u r es p a c e t h i si st h ew e l l k n o w n c u r s eo fd i m e n s i o n a l i t y s e c o n d l y ，t h el o w - l e v e li m a g ef e a t u r e su s e di nc b i ra l eo f t e nv i s u a lc h a r a c t e r - i z e d ，b u ti td o e s n te x i s tt h ed i r e c t l yc o n n e c t i o nw i t hh i g h - l e v e ls e m a n t i cc o n c e p t s ，i e s o - c a l l e ds e m a n t i cg a p t ob r i d g el o w - l e v e lv i s u a lf e a t u r et ot h eh i g h - l e v e ls e m a n t i ci sag r e a tc h a l l e n g e i nc b i r w eu s el a p l a c i a nt ol e a r nt h ei m a g e ss e m a n t i cs u b s p a c ei no r d e rt oa c h i e v e m o r ed i s c r i m i n a t i v ei m a g er e p r e s e n t a t i o nf o rc b i r i no u rw o r k ，b o t hv i s u a ls i m i l a r i t ya n ds e m a n t i cd i s s i m i l a r i t ya l ea p p l i e dt oc o n - s t r u c tn e i g h b o r h o o dg r a p hs i n c en o to n l yt h e yc o n t a i nt h ed e s c r i p t i v ei n f o r m a t i o no f t h eu n l a b e l e di m a g e sb u ta l s ot h ed i s c r i m i n a t i v ei n f o r m a t i o no ft h el a b e l e di m a g e si s u t i l i z e di nl e a r n i n g w ei n t r o d u c eap e n a l t y ，yt of o r m u l a t eac o n s t r m n e do p t i m i z a t i o n p r o b l e mi nt h ed i f f e r e n c ef o r m ，s ot h a tt h eo p t i m a lp r o j e c t i o nc a nb ef o u n db ye i g e n 。 v a l u ed e c o m p o s i t i o n i n f o r m a t i o no fc o m u n c t i v eg r a p h si sr e p r e s e n t e db yaa f f i n i t y m a t r i x a n di ti sm u c hm o t ec o m p u t a t i o n a l l ye f f i c i e n ti nt i m ea n ds t o r a g et h a nl p p a n dl d e o nt h eo t h e rh a n d ，t h el e a r n ts u b s p a c ec a np r e s e r v eb o t hl o c a lg e o m e t r ya n d r e l e v a n c ei n f o r m a t i o n p r e v i o u sw o r k so f t e nn e g l e c tt h es i n g u l a r i t yp r o b l e ma n dt h e o p t i m a ld i m e n s i o n a l i t y , b u tw e w i l ld e t e r m i n et h eo p t i m a ld i m e n s i o n a l i t ya n da v o i d t h es i n g u l a r i t yp r o b l e ms i m u l t a n e o u s l y s u b s p a c el e a r n i n gh a sa t t r a c t e dm u c ha t t e n t i o ni ni m a g er e t r i e v a l i nt h i s t h e 。 i l l 广东工业大学工学硕士学位论文 s i s ，w ep r e s e n tan o v e ls u b s p a c el e a r n i n ga p p r o a c h ，r e f e r r e dt o “s e m a n t i cd i s c r i m i n a t i v ep r o j e c t i o n ”( s d p ) ，w h i c hl e a r n st h es e m a n t i cs u b s p a c et h r o u g hi n t e g r a t i n gt h e d e s c r i p t i v ei n f o r m a t i o na n dd i s c r i m i n a t i v ei n f o r m a t i o n w ef i r s tc o n s t r u c to n eg r a p h t oc h a r a c t e r i z et h es i m i l a r i t yo fc o n t e n t e d - b a s e df e a t u r e s ，a n da n o t h e rt od e s c r i b et h e s e m a n t i cd i s s i m i l a r i t y t h e nw ef o r m u l a t et h ec o n s t r a i n e do p t i m i z a t i o np r o b l e mw i t l la p e n a l i z e dd i f f e r e n c ef o r m t h e r e f o r e ，w ec a na v o i dt h es i n g u l a r i t yp r o b l e ma n dg e tt h e o p t i m a ld i m e n s i o n a l i t yw h i l el e a r n i n gas e m a n t i cs u b s p a c e f u r t h e r m o r e ，s d pm a yb e c o n d u c t e di nt h eo r i g i n a ls p a c eo ri nt h er e p r o d u c i n gk e r n e lh i l b e r ts p a c ei n t ow h i c h i m a g e sa r em a p p e d t h i sg i v e sr i s et ok e r n e ls d el e a r n i n gw i t ht e n s o rr e p r e s e n t a - t i o ni sf u r t h e ri n t r o d u c e d t oc a p t u r et h es e m a n t i cd y n a m i c a l l y , s d pc a ni n t e g r a t e r e l e v a n c ef e e d b a c ke f f i c i e n t l yt h r o u g hi n c r e m e n t a ll e a r n i n g w ei n v e s t i g a t ee x t e n s i v e e x p e r i m e n t s t ov e r i f yt h ee f f e c t i v e n e s so fo u ra p p r o a c h e x p e r i m e n t a lr e s u l t ss h o wt h a t o u ra p p r o a c ha c h i e v e sb e t t e rr e t r i e v a lp e r f o r m a n c et h a ns t a t e o f - a r tm e t h o d s f i n a l l y , w es u m m a r i z eo u r f i n d i n g sa n dd i s c u s s i o ne x t e n s i o n st ot h ec u r r e n tw o r k k e y w o r d s 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 ) ；s u b s p a c el e a r n i n g ；d i m e n s i o n r e d u c t i o n ；s e m a n t i cd i s c r i m i n a t i v ep r o j e c t i o n ( s d p ) ；k e r n e lm e t h o d ； t e n s o rl e a r n i n g ；r e l e v a n c ef e e d b a c k i v 广东工业大学工学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人 在导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加 以标注和致谢的地方外，论文中不包括其他人已经发表或撰写过的研究成果，不 包含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的声明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的， 论文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字： 论文作者签字： 日期：2 0 0 8 年5 月2 0 日 第一章绪论 1 1 研究背景 第一章绪论 自从2 0 世纪9 0 年代以来，随着数码设备的普及，每天将产生大量数字图像。 特别是互联网的兴起，大量数字图像分布在世界各地。为了有效的存储、管理、访 问、利用这些数字图像。这就要求一种能够快速而准确查找访问图像的技术，也 就是所谓的图像检索技术【1 1 。现在图像检索己成为计算机视觉、多媒体数据库、 机器学习等领域的研究热点。以往的图像检索模式是基于文本的，采用关键字等 方式对数字图像的内容进行描述，检索时，用户提交所要查找的图像的描述信 息，检索系统根据文本描述进行匹配，根据其相似度返回检索结果。如现在常用 百度图片1 、g o o g l e t mi m a g e s 2 。然而，基于文本的图像检索需要大量的人工注释， 而且注释内容也存在很大的主观差异性，往往不能反映图像的本质内容，甚至有 些图像内容是很难用文字描述的。为此，需要一种基于内容的检索技术，把图像 的视觉内容作为检索的依据，这就是本文要研究的基于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ：c b i r ) 。基于内容的图像检索克服传统方法的缺陷，直接 利用图像的内容如颜色、纹理、形状、空间关系等进行检索。检索依据的是图像 的视觉内容的相似度。这就需要两个基本步骤特征提取和相似度量。特征提 取把颜色等特征按一定的方式概括图像内容，从而获得图像的特征分布。相似度 量计算特征分布间的距离，并据此作为图像间的相似度。 1 2 研究进展 在过去的十几年，基于内容的图像检索已成为计算机视觉、多媒体数据库、 机器学习等领域的研究热点。很多学术期刊、国际会议出版了大量关于这一方 面的论文。从1 9 9 0 年到现在( 2 0 0 8 年3 月1 2 日) ，i e e ex p l o r e 3 就发表了3 ，3 5 7 篇 相关论文。最近几年，i e e ex p l o r e 每年出版t 3 0 0 + 篇有关基于内容的图像检索 的论文。在g 0 0 9 l e 聊s c h o l a r 4 中，就以标题作为检索范围也返回5 ，7 6 0 篇相关文 1 h t t p ：i m a g e b a i d u c o m 2 h t t p ：i m a g e s g o o g l e c o m 3 h t t p ：i e e e x p l o r e i e e e o r g 4 h t t p ：s c h o l a r g o o g l e c o r n 广东工业大学工学硕士学位论文 献( s e a r c ho n l yi ne n g i n e e r i n g ，c o m p u t e rs c i e n c e ，a n dm a t h e m a t i c s ) 。其中，引 用最多的论文是参考文献 2 】，已被引用1 , 5 8 8 次。早期的综述文章 3 也被引用 了7 4 4 次。近年的综述文章 4 _ 7 】也得到很多研究者的关注。有关这一方面的分析 可参看文献 7 】。 早期的综述文章 3 】和 2 】详细介绍t 2 0 0 0 年以前基于内容的图像检索的发 展，概括了理论上、技术上的进展。首先，他们讨论了基于内容的图像检索的基 本原则。接着，讨论了在特征提取上取得的进展。针对不同的特征，他们回顾了 各种距离或相似度量方法。随后，他们讨论了多维索引技术。最后，总结了基于 内容的图像检索的系统架构，并介绍了相关的图像检索系统及所用的方法。文 鼠、警甲，声 声i 厂弋 ic o 弹t 砌l n i q 硼畴 6 磊磊 乙呵 回心一二匿 蕊画刊 熙黧j k e yq t 骶r l o n s | h o w t o 触o et h es e m a n t i cg a p ? l 脚c 姐u 枷郸蹴麟k 鼬捌 w h a tp o t e n t i a l1 1 5 c $ c a nt h e yh a v e ? n e wi d e a s s u b f i e l d ss p a 姗酣? l 珏。w 毫oc o n l p a l ec 。m p e 也瞎a p p a c h e s a n ds e ti n d t l s t t 3 3 t a n d a 心? 夕罔 图1 - 1 基于内容的图像检索总览【7 】 f i g u r e1 - 1o v e r v i e wo fc o n t e n t - b a s e di m a g er e t r i e v a l ( b yc o u r t e s yo f 【7 】) 献 4 】总结了基于内容的图像检索在理论、技术和应用上取得的新进展。包括检 索模式、图像库、图像视觉特征、表示与索引和相似度量。文献 5 】回顾了最新的 图像视觉特征、相似度量和高性能索引；讨论了比较实际的问题，如浏览与搜索 范式、用户偏好、情感计算、语义查询及性能评价。文献 6 】注重讨论怎样缩小“语 义鸿沟。特别侧重介绍机器学习、相关反馈、语义模板等方面的进展。同时，也 2 西 第一章绪论 详细讨论了低维视觉特征提取、相似度量、高层语义派生的视觉特征、图像测试 集和性能评价标准。据我们所知，文献 7 】是基于内容的图像检索研究领域最全 面的综述。如图1 1 所示，文献 7 】给出图像检索的总览，包含了相关研究的方方 面面。详细讨论了核心技术、性能评价、研究分支及应用，更为重要的是给出了 一些实际应用及研究趋势。 自从基于内容的图像检索提出以来，越来越多的研究者进入这个热门的领 域。相继出现了一些图像检索系统，如q b i c 【8 1 ，v i s u a l s e e k l 9 1 ，b l o b w o r l d t l o 】等 等。文献 1 1 按字母顺序详细介绍了5 8 个图像检索系统，在众多系统基础上，作 者给出一个复杂的概念框架。现在基于w e b 的应用己成为一种趋势，所以面 向w e b 的图像检索系统是十分必要的。网上存在许多在线演示系统。中国科学 院智能科学课题组推出了一个原型化系统m i r e s l 。由高等学校中英文图书数字 化国际合作计划发起，浙江大学开发了c a d a l 图像搜索引擎2 。n e w s a m 等人【1 2 】创 建了一个演示系统3 ，他们所用的视觉特征为颜色和纹理，而且他们应用了相关 反馈技术。f i r e 4 ，c i r e s 5 也是比较好的在线演示系统。v i p e r 6 介绍了很多相关的 系统。l i 和w a n g 主持开发ta u t o m a t i cl i n g u i s t i ci n d e x i n go fp i c t u r e s - r e a lt i m e ( a l i p r t m ) 7 ，详细的介绍可参看文献 1 3 】。 基于内容的图像检索一般地概括为如图1 2 所示的框架【3 】。从中看出，特征 提取和相似度量是两个关键问题，下面我们将简要介绍这两个方向的研究进展。 1 - 2 1 特征提取 图像视觉特征提取在基于内容的图像检索中处于核心地位。传统的特征描 述有颜色、纹理、形状、空间关系等。m p e g - 7 标准相应地定义了这些特征的描 述子 1 4 - 1 8 。早期比较详细的介绍可参看文献 3 1 。d e s e l a e r s 在他的硕士学位论文 中对图像视觉特征进行了深入的研究【”】。 现在大多数图像检索系统所用的视觉特征是基于全局或局部描述。文献 2 0 】 提出一种全局描述的颜色直方图。首先，把图像分为较小的块，然后对小块 1 h t t p ：w w w i n t s c i a c c n c b i r 2 h t t p ：w w w c a d a l z j u e d u c i l ，i m ，蹦h t m 3 h t t p ：n a y a n a e c e u c s b e d u i m s e a r c h i m s e a r c h h u n l 4 h t t p ：w w w i 6 i n f o r m a t i k r w t h a a c h e n d e d e s e l a e r s f i r e h t m l h t t p ：c i r e s m a t t h e w r i l e y c o m 6 h t t p ：v i p e r u n i g e c h o t h e r s y s t e m s 7 h t t p ：w w w a l i p r c o m 广东工业大学工学硕士学位论文 图1 - 2 基于内容的图像检索框架【3 】 f i g u r e1 - 2c o n t e n t - b a s e di m a g er e t r i e v a lf r a m e w o r k ( b yc o u r t e s yo f 【3 】) 进行特征提取，最后由高斯混合向量量化( g a u s sm i x t u r ev e c t o rq u a n t i z a t i o n - g m v q ) 聚类算法得到直方图。由聚类或分割算法得到的签名( s i g n a t u r e ) 是 另一种常用的视觉特征描述。基于高斯混合模型( g a u s sm i x t u r em o d e l ：g m m ) 的e m ( e x p e c t a t i o nm a x i m u m ) 算法 2 1 雨 l l o y d 聚类算法【2 2 】是其中最为常用的 方法。我们的工作 2 3 采用的就是l l o y d 聚类算法。现在最常用的图像分割方法 是n o r m a l i z e dc u t s 2 4 并l l m e a ns h i f t l 2 5 1 。文献 2 6 】采用m e a ns h i f t 算法对自然图像 进行统计建模，能自动检测概念目标( 如图1 3 所示) 。 1 2 _ 2 相似度量 图像视觉特征被提取出来之后，要把图像库中图片的视觉特征与查询例 子的视觉特征进行相似度比较。相似度量是基于内容的图像检索的又一个重要 的问题。传统的相似度量都是一一匹配的。常用的有m i n k o w s k i 距离l 口和k - l 散 度( k u l l b a c k l e i b l e rd i v e r g e n c e ) 。文献【2 7 】和文献 2 8 1 对各种相似度量进行了详细 4 第一章绪论 ”d e t e c t i o nr e s u l t c ) s e g m e n t a t t o nr e s u l t 图1 - 3a ) 原图b ) 检测结果c ) 分割结果 f i g u r e1 - 3a ) o r i g i n a li m a g eb ) d e t e c t i o nr e s u l tc ) s e g m e n t a t i o nr e s u l t 的实验评价。详细地介绍了加权均值方差( w e i g h t e d m e a n v a r i a n c e ) ，k o l m o g o r o v s m i r n o v 距离，x 2 - s t a t i s t i c ，j e f f r e y 散度，c o s i n e 距离，马氏距离( m a h a l a n o b i sd i s t a n c e ) 和二次距离( q u a d r a t i cd i s t a n c e ) 等相似度量的优缺点。很多图像检索系统采 用的特征是基于变长表示的签名( s i g n a t u r e ) 。这样就需要多对多匹配的相似度 量，其中广为采用的是推土机距离( e a r t hm o v e r sd i s t a n c e ：e m d ) 【2 9 1 。签名由 聚类算法得到的簇及相应的权值表示，推土机距离直观表示的是一个签名( 土 堆) 搬运到另一个签名( 空穴) 的所花费的最小成本( 距离) 。推土机距离起源 于运筹学中的运输问题模型，各个签名所含簇的个数可以不同，是一种部分匹 配方法。我们的工作 2 3 提出采用两种贪婪算法得到计算复杂度更低的近似推 土机距离算法。文献【3 0 提出一种称为e m d l x 的快速计算推土机距离算法。这 个算法是以l 1 作为簇间的基本距离( g r o u n dd i s t a n c e ) ，而且算法复杂度由原始 的o ( n 31 0 9 ( 佗) ) 降为0 m 2 ) 。文献 3 1 提出一种贪婪算法以签名间的最小失真作为 相似度量。算法所用的签名由基于高斯混合模型聚类算法得到，而且以签名间单 个高斯间的失真作为基本距离。统一特征匹配( u n i f i e df e a t u r em a t c h i n g ：u f m ) 提出一种基于模糊逻辑的相似度量方法【3 2 1 。v a s c o n c e l o s 等人提出一个整合了特 征提取和相似度量的概率框架【3 3 1 ，并给出闭合解渐进似然估计算法( a s y m p t o t i c l i k e l i h o o da p p r o x i m a t i o n ：a l a ) 。 5 广东工业大学工学硕士学位论文 1 3 论文组织 本文侧重研究子空间学习方法在基于内容的图像检索中的应用，本文的部 分工作发表在文献 3 4 。第一章即本章是绪论部分，简略地介绍了基于内容的图 像检索相关研究背景及进展。后面五章是本文的主体，其中主要研究内容及组织 如下： 第二章提出一种新的子空间学习方法一语义判别投影。首先，简要介绍 了当前研究的热点及相关研究工作，随后，我们详细地讲解提出的方法及算法步 骤。最后，我们分析本文提出方法的特性。 第三章我们提出语义判别投影的扩展算法： 1 第3 1 节把语义判别投影推广到非线性情况，提出核学习版本核语 义判别投影。 2 第3 2 节基于新数据表示模型提出语义判别投影的张量化学习方 法二维语义判别投影。 3 第3 3 节提出基于增量学习的相关反馈学习方法。 第四章是实验部分，讨论实验相关的设置，并给出实验结果。 最后，总结全文并探讨进一步的研究工作。 6 第二章语义判别投影 2 1 相关工作 2 1 1 引言 第二章语义判别投影 随着数码设备的普及，互联网的兴起，每天将产生大量数字图像。为了有效 的存储、管理图像数据库，需要对图像库进行索引，按特定的需求检索图像。怎 么根据数字图像的视觉内容有效地管理图像库是当前研究的一大热点。为此，基 于内容的图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ：c b i r ) 受到广大计算机视觉、 机器学习等领域研究人员的广泛关注。经过十几年的努力，基于内容的图像检索 依然有两个基本问题有待解决。首先，用于描述图像视觉内容的特征向量，如颜 色、纹理、形状、空间关系等等，一般维数比较高。很多情况下都是从几百到几 千，一般的机器学习方法不能在这么高维的特征空间学习。这就是所谓的“维数 灾难”。其次，基于内容的图像检索中用于刻画图像视觉内容的低维特征与高层 语义概念之间不存在直接的联系，这就是所谓的“语义鸿沟”。 2 1 2 相关工作 为缓解所谓的“维数灾难”难题，越来越多的学者集中到数据降维方法的研 究。其中最著名的数据降维方法是主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ：p c a ) ) 【3 5 】和多维尺度变换( m u l t i d i m e n s i o n a ls c a l i n g - m d s ) 1 3 6 1 。主成分分析 实质上是一种线性的特征变换投影方法。它求解使得投影后的低维数据空间保 持最大方差( 即重构误差最小) 。经典的多维尺度变换利用数据点间的距离关系 求解一个低维嵌入，使之保持数据点间的距离。如果多维尺度变换采用的距离是 欧式距离，那么多维尺度变换本质上就等同于主成分分析。随着流形学习方法的 提出，数据降维方法成为一种流行的机器学习方法。等距映射( i s o m a p ) 【3 7 1 ，局 部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ：l l e ) 1 3 8 1 和拉普拉斯特征映射( l a p l a c i a n e i g e n m a p s ) 1 3 9 是最早的流形学习算法。跟随其后，越来越多的研究者在他们的 启发下提出很多学习方法。这些算法都是在某一启发下，保持数据集的局部或 全局特性，进而发掘其揭示内部结构的低维嵌入。t e n e n b a u m 等人提出用测地距 7 广东工业大学工学硕士学位论文 离( g e o d e s i cd i s t a n c e ) 代替欧氏距离计算数据点间的距离，然后采用多维尺度变 换获得其低维嵌入【3 7 1 。s a u l 等人提出基于数据局部坐标近似线性的假设，那么数 据点就可有其近邻点线性组合近似得到。这样低维嵌入可通过最小化重构误差 而保持其局部领域关系而得到【3 羽。拉普拉斯特征映射使训练数据空间的近邻数 据点在映射后的数据空间也保持其局部近邻关系【3 9 1 。等距映射、局部线性嵌入、 拉普拉斯特征映射都是非监督式、非线性学习方法，不能直接学习得到面向整个 特征空间的投影( 变换) 。除上面所述的方法外，还有很多新的方法相继提出。有 关这个一方面的综述可参看文献 4 肚4 4 】。 为了克服非线性学习方法的局限，很多线性扩展学习方法相继提出。基 于拉普拉斯特征映射的线性学习方法，保局投影( l o c a l i t yp r e s e r v i n gp r o j e e t i o n s ：l p p ) 1 4 5 1 ，局部判别嵌入( l o c a ld i s c r i m i n a n te m b e d d i n g ：l d e ) t 4 6 是其中最著 名的算法。最近提出的边缘f i s h e r 分析( m a r g i n a lf i s h e ra n a l y s i s ：m f a ) t 4 7 , 4 8 本质 上与局部判别嵌入是一样的。保局投影用一个邻接图刻画训练数据的局部保持 特性，使原空间近邻数据在投影后的特征空间也保持近邻关系【4 5 1 。局部判别嵌 入构造两个图，一个用来保持近邻关系，另一个使不同类间尽量分开【蚓。保局投 影和局部判别嵌入都是线性学习方法，能到一个面向整个特征空间线性映射。保 局投影只利用了一个图去发掘数据的内在结构，而且是一种非监督式的，没有充 分利用类别信息。局部判别嵌入在保局上与保局投影一致，其加入了类别信息， 使得同类的近邻点保持局部关系。但局部判别嵌入只考虑数据点间同时是近邻、 来自不同类时使其尽量分离，而且在求解保局投影和局部判别嵌入时都要计算 逆矩阵，存在奇异性问题。 2 1 3 基于拉普拉斯的子空间学习 本小节介绍前面所述的拉普拉斯特征映射，同时给出我们工作相关的保局 投影，局部判别嵌入。在此基础上，下一节我们再引入提出的语义判别投影。 假设图像数据集中有咒张训练图片，每张图片特征x 。表示为： x i l - 1 妒 ( 2 1 ) 其中佗是训练图像数，d 是原始特征维数。现在创建两个邻接图g s 和g y 。g s 表示 图像问的语义相似性( 通过类别) ，g y 表示图像间的视觉相似性( 通过图像几何 8 第二章语义判别投影 空间的邻接关系) 。分别用s 和y 表示g s 和建立的关系矩阵。w s 和w y 的 定义如下： ， 唠： 1 l0 r 略： 1 【0 x t ，巧属于同一语义类， ( 2 2 ) 其它情况 x j f i 勺k - n n 或者x t 的尼一n n ， ( 2 3 ) 其它情况 其中忌n n ( ) 表示尼近邻。现在合并这两种信息，定义如下关系矩阵： w 一= w s w l d e ：丽aw y w + ：w saw y 其中“a ”表示两个o 1 矩阵的“m e e t ”运算。 拉普拉斯特征映射寻找低维表示： 乳) 警1 一 其中d 为降维后的维数。拉普拉斯特征映射的目标函数表示为： m i n i l y t y 歹1 1 2 略 t ，歹 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 保局投影是拉普拉斯特征映射的线性扩展，即有y t = p t x t ，那么公 式( 2 8 ) 改写为： p = a r g r a i n l i p t 磁一p t x j l l 2 w 荔 ( 2 9 ) i , j 用迹( t r a c e ) 的形式改写公式( 2 9 ) ，那么可得到如下公式化优化问题： 9 广东工业大学工学硕士学位论文 i i p t 磁一p t 巧i ，j = t r ( p t 托一p t x j ) ( p t x i p t x j ) t ) w 孑 i , j = t r p t ( x i 一巧) ( 磁- x j ) t 尸) 略 i , j = t r p t ( x i 一巧) 略( 磁一x j ) t p ) t ，j = 2 t r p t x d y w y x t p ) = 2 t r p t x l y x t p ) ( 2 1 0 ) 其中l y = d y w y 是拉普拉斯矩阵h 5 1 ，d y 是一对角矩阵，且碟= j 略。加入 约束： 那么保局投影的特征函数为： t r p t x d y x t p ) _ l x l y x t p = a x d y x t p 局部判别嵌入的约束目标函数为1 4 6 ： m a x l i p t x i p t 巧1 1 2 唠加 i , j s t h p t x i p t 巧1 1 2 咐= 1 i , j 相似地推出局部判别嵌入特征函数为： x l l d e x t p = x x ：l + x t p ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 其中l l d e = d 加e w l d e ，d l d e 是一对角矩阵，且d 磊d e = 歹吆d e 。相似地 1 0 第二章语义判别投影 有，矿= d + 一w + ，磁= j 咐。 2 2 语义判别投影 为了更好的揭示低维视觉特征与高层语义概念问的联系，本文提出一种基 于拉普拉斯的学习方法，学习得到的语义子空间为基于内容的图像检索提供更 强的判别表示。本文提出的方法在构建邻接图时，不仅考虑到表示描述信息的无 类别的视觉相似性，而且包含了表示判别信息的语义相异性。充分利用这两种信 息学习得到语义子空间。通过引入一个惩罚参数，y ，本文提出建立一个差式约束 优化问题。那么最优投影就可以通过矩阵的特征值分解求得。创建的邻接图用一 个关系矩阵表示，这样，计算复杂度和计算量都比比保局投影和局部判别嵌入要 小。另一方面，学习的得到语义子空间不仅具有保持局部几何特性，而且全局相 关信息也得到很好地保持。以前相关学习方法都存在奇异性问题，而且不能确定 学习后子空间的维数。本文提出的方法解决了这两个问题。本节将介绍本文提出 的“语义判别投影”，并把“语义判别投影”应用到基于内容的图像检索中。提出的 学习方法保持了原图像特征空间的局部描述信息和判别信息。 本文引入一个带惩罚参数的差式约束优化问题求解最优投影p 。求解最优 投影p 的优化问题可以表述为： p _ a r g p m 脚a x i i p t x i - - p t m 忾一，y 咐) ( 2 1 5 ) t j 其中w 一，w + 分别由公式( 2 4 ) ，( 2 6 ) 定义，7 是惩罚参数，约束p t p = i 避免无 价值的解，j 是d d 的单位矩阵，d 是特征约简后的维数。 公式( 2 1 5 ) 隐含了本文启发式优化假设：来自不同语义类别的图像在投影后 的子空间尽量分开；视觉特征相似且属于同一语义类别的图像在投影后的子空 间尽量聚到一块，保持其几何内部结构。 在模式分类系统中，样本特征的多样性很重要【4 9 1 。这种多样性表现在两个 方面：类内和类间。很多情况下，类内的特征多样性都不被重视。也就是说，一 般默认的数据分布假设是单模( 每类属于一个聚类高斯分布) 。基于上述分析， 观测数据的数据分布为多模更为合理。例如，同一语义类图像可能来自不同视觉 特征的图像源( 如图4 1 所示) 。这样，有必要使只有视觉特征和语义概念同时相 同的图像聚集到一个聚类。图2 1 给出一个简单的示意图。如图示，蓝色表示的 广东工业大学工学硕士学位论文 数据类来自同一个高斯分布，而红色表示的数据类则来自两个不同的高斯分布。 基于这种假设，本文给出优化问题的数学模型公式( 2 1 5 ) 。文献 5 0 ，5 1 跟本文类 似，同样采用数据多模分布的假设。