（信号与信息处理专业论文）最大间隔方法及其在图像检索中的应用.pdf

摘要 摘要 随着图像获取、传输、存储等技术的进步，各种数字图像资源变得越来越丰 富。为了对图像资源进行有效的利用，首先要求能够快速准确地从规模日益庞 大的图像数据库中查找到需要的图像。图像检索是一个综合性的问题，为建立 一个成功的图像检索系统，需要首先解决许多相关的基本问题，如图像相似性 的度量、图像相关排序、图像分类以及聚类等。 近年来，机器学习理论与算法的长足发展为各种实际问题的解决提供了有 力的工具。在众多的机器学习算法中，支持向量机模型因在理论上具有坚实的 基础并在实践中表现出优异的性能而受到广泛的关注。本文在支持向量机模型 和间隔最大化准则的基础上，提卜b 了一系列最大间隔算法，对图像检索中相关 的问题展开了研究。 本论文首先研究了当用局部特征表示图像时，如何通过局部特征的匹配，度 量图像之间的相似度，并在此基础上用支持向量机实现图像分类。文中提出了 一种新颖的双空间金字塔匹配算法，能够快速地计算两个特征集合间的隐式匹 配关系。该算法首先对特征空问和幽像空问分别进行多分辨率的划分，然后将 一幅图像对应的局部特征的集合映射成建立在双空间中的多分辨率直方图，最 后通过直方图的加权相交实现两个特征集合的快速匹配。由于充分利用了局部 特征在两个空间中的分布特点，因此相比于只在单空间中进行匹配的算法，双空 间金字塔匹配能够更准确地反映局部特征集合之间的关系。同时，基于双空间 金字塔匹配的相似性度量满足半正定条件，因此能够作为支持向量机的核函数， 用于对图像进行分类。在i m a g e c l e f 医学图像分类任务上，基于双空间金字塔 匹配的支持向量机取得了比2 0 0 5 年公布的最佳参赛结果更小的分类错误率。 本论文然后研究了在基于关键词的图像检索中，如何有效地将图像按照与 关键词的相关程度的大小进行排序。与传统工作将检索问题建模成二分类问题 并优化分类性能不同，本文将问题建模成一个排序学习问题，并直接优化与排 序性能相关的目标函数。本文基于支持向量机模型和间隔最大化准则提出了一 种新颖的多示例排序学习框架。该框架采用基于区域的图像表示，并利用一组 具有优先关系的图像对学习图像排序模型。利用学到的排序模型，能够计算新 i 摘要 图像的排序分数，并按排序分数的大小对图像进行排序。在这个框架下，基于对 区域和图像排序分数关系的不同假设，本文分别提出了三种具体的多示例排序 学习算法。对从f 1 i c k r 上搜集的图像进行的实验表明，多示例排序学习算法能够 极大地提高图像的排序质量。这项工作是最早将排序学习与多示例学习结合进 行考虑的工作。 本论文还研究了基于支持向量机模型和间隔最大化原理的聚类算法，由此 可以对图像进行聚类。这剩最大间隔聚类算法通过寻找使类问间隔最大的分类 面，实现对数据集的划分。与传统的聚类算法相比，最大间隔聚类具有良好的推 广性能，因此在大规模的聚类问题中能够发挥重要的作用。木文在分析现有最 大间隔聚类算法不足的基础上，提出了基于成对约束的半监督最大间隔聚类算 法。该算法通过在最大间隔聚类的目标函数中添加针对成对约束的损失项，使 得求得的聚类分界面尽量满足给定的约束条件，从而提高最大间隔聚类的性能。 本文不仅在标准支持向量机模型的基础上讨论了两类情况下的聚类，还从多类 支持向量机出发，详细讨论了多类情况下基于成对约束的最大间隔聚类。对于 聚类问题所对应的非凸优化问题，本文提出了基于c c c p 过程的迭代解法来进 行高效地求解。存多类情况下为了保证聚类速度，还为c c c p 迭代中子问题的 求解提出了基于割平面法的快速算法。对标准的图像数据集进行聚类的结果表 明，成对约束的引入，能有效地弥补现有最大问隔聚类算法的不足，并极大地提 高其聚类准确性。 关键词：图像检索支持向量机最大间隔方法相似性度量分类排序学 习聚类 a b s t r a c t a b s t r a c t w i t ht h ea d v a n c e si nt e c h n i q u e sf 6 ri m a g ec a p t u r e ，t r a n s m i s s i o na n ds t o r a g e ，t h e r e s o u r c e so fd i g i t a li m a g e sh a v eb e e ng r e a t l ye n r i c h e d i no r d e rf b re f f e c t i v eu t i l i z a t i o n o ft h i si m a g er e s o u r c e s ，w es h o u l d 丘r s tb ea b l et o 丘n dd e s i r a b l ei m a g e sq u i c k l ya n d a c c u r a t e l y 士r o ml a r g es c a l ei m a g ed a t as e t i m a g er e t r i e v a li sac o m p r e h e n s ep r o b - l e m t bs u c c e s s f u l l yb u i l da ni m a g er e t r i e v a ls y s t e m ，w en e e dt os 0 1 v es o m er e l e v a n t p r o b l e m si na d v a n c e ，s u c ha sm e a s u r i n gi m a g es i m i l a r i t i e s ，r a n k i n gi m a g e sa c c o r d i n g t or e l e v a n c e ，i m a g ec l a s s i f i c a t i o na n dc l u s t e r i n g i nr e c e n ty e a r s ，t h ea d v a n c e si nm a c h i n el e a m i n ga r e ah a sp r o v i d e dp o w e r f u lt o o l s 士o rs o l v i n gd i f k r e n ta p p l i c a t i o np r o b l e m s a m o n gt h en u m e r o u sm a c h i n el e a r n i n g a l g o r i t h m s ，s u p p o r tv e c t o rm a c h i n e ( s v m ) h a sa t t r a c t e dm u c ha t t e n t i o nd u et oh a v i n g s o l i dt h e o r e t i c a lf b u n d a t i o na n dp e r f b r m i n gw e l li np r a c t i c e t h i st h e s i ss t u d i e ss e v e r a l r e s e a r c hp r o b l e m si ni m a g er e t r i e v a lu s i n gm a x i m u mm a r g i nm e t h o d s ，w h i c ha r eb a s e d o nt h es v mm o d e la n dt h ep r i n c i p l eo fm a x i m i z i n gt h em a r g i n t h et h e s i sf i r s ts t u d i e sw h e nu s i n gl o c a lt e a t u r eb a s e di m a g er e p r e s e n t a t i o n ，h o w t om a t c ht h el o c a lf e a t u r e sf r o md i f 俺r e n ti m a g e ss oa st om e a s u r et h es i m i l a r i t yb e t w e e nt h e m ，w h i c hi sa l s oc r i t i c a lf o ri m a g ec l a s s m c a t i o nu s i n gs u p p o r tv e c t o rm a c h i n e s 。an o v e ld u a l s p a c ep y r a m i dm a t c h i n ga l g o r i t h mi sp r o p o s e d ，w h i c hc a ne 币。 c i e n t l yc o m p u t et h ei m p l i c i tm a t c h i n gr e l a t i o nb e t w e e nt w of e a c u r es e t s t h ep r 。p o s e d m a t c h i n ga l g o r i t h mf i r s tp e r f o r m sm u l t i r e s o l u t i o ns p a c ep a r t i t i o ni nb o t hf e a t u r es p a c e a n di m a g es p a c e t h e nt h ef e a t u r es e to fa ni m a g ei sm a p p e dt oam u l t i r e s o l u t i o nh i s t o g r a mt h a ts p a n st h et w os p a c e s f i n a l l y ，t h em a t c h i n gb e t w e e nt w of e a t u r es e t s i s o b t a i n e dt h r o u g hw e i g h t e dh i s t o g r a mi n t e r s e c t i o n b ye x p l o r i n gt h ed i s t r i b u t i o nc h a r - a c t e r i s t i c so fl o c a lf e a t u r e si nb o t hf e a t u r es p a c ea n di i n a g es p a c e ，d u a l - s p a c ep y r a m i d m a t c h i n gc a ng e tm o r ea c c u r a t es i m i l a r i t ym e a s u r et h a nt h es i n g l e s p a c em a t c h i n ga l _ g o f i t h m s m o r e o v e r ，t h es i m i l a r i t ym e a s u r eo b t a i n e db yd u a l - s p a c ep y r a m i dm a t c h i n g s a t i s f i e st h es e m i d e f i n i t ec o n d i t i o n t h e r e f o r e ，i tc a nb eu s e da sak e r n e l 士u n c t i o nf o r s v mb a s e di m a g ec l a s s i 疗c a t i o n t h ep e r f b r m a n c eo fs u c hac l a s s i 厅e rh a sb e e ne v a l u l t i a b s l k a c l 。 a t e do nt h ed a t a s e tf o rt h ea u t o m a t i cm e d i c a li m a g ec l a s s i f i c a t i o nt a s ko fi m a g e c l e f 2 0 0 5 i to u c p e r f b r m st h eb e s tr e s u l ta n n o u n c e di nt h ec a m p a i g no ft h a ty e a r t h et h e s i st h e ns t u d i e st h ep r o b l e mo fh o wt oe f 琵c t i v e l yr a n ki m a g e sa c c o r d i n g t ot h e i rr e l e v a n c et ot h eq u e r yi nk e y w o r db a s e di m a g er e t r i e v a l u n l i k et r a d i t i o n a l w o r k s ，w h i c hu s u a l l ym o d e lt h er e t r i e v a lp r o b l e ma sab i n a r yc l a s s i 6 c a t i o np r o b l e m a n do p t i m i z ec l a s s i f i c a t i o np e r f o r m a n c ed u r i n g1 e a m i n g ，t h i sw o r km o d e l si ta sar a n k i e a m i n gp r o b l e ma n dd i r e c t l yo p t i m i z e sa no b j e c t i v ef u n c t i o nt h a ti sr e l e v a n tt ot h e r a n k i n gp e r f o r m a n c e an o v e lm u l t i p l e i n s t a n c er a n ki e a m i n gf r a m e w o r kb a s e do n s v mm o d e la n dm a x i m u mm a 唱i np r i n c i p l ei sp r o p o s e di n t h i sw o r k i ta s s u m e s t h a tt h ei m a g e sa r er e p r e s e n t e db ys e t so fi m a g er e g i o n s as e to fi m a g ep a i r sw i t h p r e f e r e n c er e l a t i o n sa r eu s e dt ol e a mt h ei m a g er a n k i n gm o d e l t h e1 e a m e dm o d e l c a n b eu s e dt oc o m p u t et h er a n k i n gs c o r e so fn e wi m a g e sa n dt h ei m a g e sc a nt h e nb er a n k e d a c c o r d i n gt ot h e i rs c o r e s w i t h i nt h ep r o p o s e df r a m e w o r k ，m r e ed i f f e r e n tm u l t i p l e - i n s t a n c er a n k i n ga l g o r i t h m sa r ep r o p o s e da c c o r d i n gt od i f f e r e n ta s s u m p t i o n sa b o u tt h e r e l a t i o n sb e t w e e nt h er a n k i n gs c o r eo fa ni m a g ea n dl h o s eo fi t sc o n s t i t u e n tr e g i o n s t h ep e r f o r m a n c eo ft h e s ea l g o n t h m sa r ee v a l u a t e do nr e a l w o r l di m a g e sc o l l e c t e df r o m f l i c k r t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h em u l t i p l e i n s f a n c er a n k i n ga l g o r i t h m s c a ng r e a t l yi m p r o v et h er a n k i n gq u a l i t yo ft h ei m a g e s t h i si sm e6 r s tw o r kt h a tj o i n t l y c o n s i d e r st h er a n kl e a r n i n gp r o b l e ma n dt h em u l t i p l e i n s t a n c e1 e a r n i n gp r o b l e m t h et h e s i sa l s os t u d i e st h ec l u s t e r i n ga l g o r i t h mw h i c h e x p l o i t st h em a x i m u mm a r g i np r i n c i p l eo fs u p p o r tv e c t o rm a c h i n e t h ea l g o r i t h mc a nb eu s e dt oc l u s t e ri m a g e s t h i sm a x i m u mm a r g i nc l u s t e r i n g ( m m c ) a l g o r i t h mp e r f o r m sd a t ap a r t i t i o nt h r o u g h 6 n d i n gt h em a x i m u mm a r g i ns e p a r a t i n gh y p e r p l a n e si nm ed a t a c o m p a r e dw i t ht r a d i c i o n a lc l u s t e r i n ga l g o r i t h m s ，i th a sg o o dg e n e r a l i z a t i o np e r f o r m a n c ea n dc a np l a ya n i m p o r t a n tr o l ei n1 a 玛es c a l ec l u s t e r i n gp r o b l e m s b a s e do nt h ea n a l y s i so ft h el i m i t a t i o n so fe x i s t i n gm m cm e t h o d s ，t h i sw o r kp r o p o s e sap a i r w i s ec o n s t r a i n e ds e m i s u p e r v i s e dm a x i m u mm a r g i nc l u s t e r i n ga l g o r i t h m as e to fp a i r w i s el o s sf u n c 七i o n sa r e i n t r o d u c e di n t ot h ec l u s t e r i n go b j e c t i v ef u n c t i o n st om a k es u r et h a tt h es e p a r a t i n gh y p e r p l a n e ss a t i s 母t h eg i v e np a i r w i s ec o n s t r a i n t sa sm u c ha sp o s s i b l e t h i si ss u p p o s e d t oi m p r o v et h ep e r f b r m a n c eo fm m c b e s i d e ss t u d y i n gb i n a r yc l u s t e r i n gb a s e do nt h e s t a n d a r ds v mm o d e l ，t h i sw o r ka l s oe x p l o r e st h ep a i r w i s ec o n s t r a i n e dm m c a l g o i v a b s t r a c t r i t h mf o rm u i t i p i ec l a s sc l u s t e r i n gb a s e do nm u i t i - c l a s ss v m m o d e i i ti sp r o p o s e dt o u s ec d ，l s f ，- 口协g dc d n c a v e c d n v i 曼xp ，d c p d “，訾( c c c p ) t oe f 葡c i e n t l ys o l v et h en o n c o n v e x 0 p t i m i z a t i o np r o b l e m sc o n e s p o n d i n gt om m c m o r e o v e r f o rc o n s t r a i n e dm u l t i c l a s s m m c ，a ne 硒c i e n tc u c i n g p l a n ea l g o r i t h mi sp r e s e n c e dt os 0 1 v et h es u b p r o b l e mi n e a c hi t e r a t i o no fc c c ps oa st oe n s u r ei t se f f i c i e n c y c l u s t e “n ge x p e r i m e n t so ns t a n d a r di m a g ed a t a s e t si n d i c a t et h a tt h ei n t r o d u c t i o no fp a i r w i s ec o n s t r a i n t sc a ne f l e c t i v e l y m a k eu pt h es h o r t c o m i n g so fp r e s e n tm m ca l g o r i t h m sa n dg r e a t l yi m p r o v et h ea c c u r a c yo ft h ec l u s t e r i n gr e s u l t s k e y w o r d s ： i m a g er e t r i e v a l ，s u p p o r tv e c t o rm a c h i n e s ，m a x i m u mm a 唱i nm e t h o d s ， s i m i l a r i t ym e a s u r e ，c l a s s i 6 c a t i o n ，r a n kl e a m i n g ，c l u s t e r i n g v 表格 3 1 3 2 3 3 表格 图3 6 中各类别的文字描述举例【4 1 。 基于金字塔匹配对医学图像进行分类的性能比较 i m a g e c l e f2 0 0 5 医学图像分类错误率比较1 6 7 1 3 5 3 7 3 9 4 14 种方法对每个查询词的a p 值。4 种方法对所有查询词的平均 a p 值分别为o 4 8 3 ，o 6 5 5 ，o 6 4 2 和o 6 9 9 。 6 1 5 1 实验数据集概况 9 6 x i 插图 插图 1 1 两类分类问题及分类间隔示意图5 2 1 分类间隔和最优分类面示意图【1 1 2 2 松弛项示意图i 1 1 。 3 1 局部特征表示的例子【2 1 3 2 g r a u m a n 和d a r r e u 的特征空间金字塔匹配示意图【2 1 3 3 二维特征空间的两种划分方式示意图 3 4 在图像空间中构造3 层金子塔的示意图【3 1 。假设图像中的局部特 征被分成3 类，分别用星号、加号和井号表示。在箭头左边，同一 幅图像被划分成大小不同的子区域。在箭头右边，对相应子区域 中各种特征的数目进行统计，并用直方图进行表示。图下的分数 表示经过直方图匹配后对结果进行加权求和所用的权值。 3 5 双空间金字塔示意图。 3 6 i m a g e c l e f2 0 0 5 医学图像分类任务所用的数据集的示意图【4 1 4 1f l i c k f 上，三幅标签中均含有“大象”的图像。 4 2 利用线性排序函数进行排序的例子 4 3 f l i c k r 图像的例子。三幅图像为一组，第l 列和第4 列为第一类最 相关的图像，第2 列和第5 列为第二类中等程度相关的图像，第 3 列和第6 列为第三类不相关的图像。 。 4 4四种方法在第5 、l o 、2 0 幅图像处的n d c g 值比较 4 5 利用多示例排序学习算法预测图像区域相关性的例子( 以s o f t m a x 算法为例) 。第1 列和第4 列为原图像，第2 列和第5 列为图像分 割的结果，第3 列和第6 列显示了图像区域的相关性，区域越亮 相关性越大。 5 1i t e r s v r 的聚类准确性受类平衡约束参数f 影响的例子。 5 2 i t e r s v r 的聚类准确性受初始化影响的例子 x i i i 1 0 1 l 2 2 2 4 2 8 3 3 2 4 0 4 2 4 9 5 8 6 3 6 4 6 9 7 0 插图 5 3 m n i s t 数据集的手写数字图像的示例 8 8 5 4 初始化敏感性比较 8 9 5 5 两类情况下的聚类错误率比较9 l 5 6 多类情况下的聚类错误率比较 9 2 5 7 对新样本聚类的错误率 9 3 x i v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：_ 二哗 签字日期：皇噶l l 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 留公开口保密( 年) 作者签名： 签字日期： 型卜 珥五l 导师签名：祖觅 签字日期：鼍兰【笪：兰一 第l 章绪论 第1 章绪论 1 1研究背景 1 1 1图像检索及相关问题 随着海量的数字图像在日常生活的各个领域被广泛地采集和存储，如何实 现从大规模的图像数据库中快速准确地查找到需要的信息，成为非常重要的问 题。为此，研究人员针对相关的问题开展了大量的研究工作。目前广泛采用的图 像检索方式主要有两种：基于关键词的图像检索( q u e r yb yk e y w o r d ) 和基于样例 的图像检索( q u e r yb ye x a m p l e ) 。在基于关键词的检索中，用户通过输入文本形 式的关键词，查找包含相关内容的图像。这是现有的商业图像搜索引擎普遍采 用的检索方式。基于样例的检索又称为基于内容的图像检索( c b i r ，c o n t e n tb a s e d i m a g er e t r i e v a l ) ，在这种方式中，用户提交图像作为检索的目标，系统自动查找图 像数据库中与目标相似的图像。这种检索方式对于特定领域内的图像检索，如 商品检索、医学图像检索、卫星云图的检索等，具有重要的意义。 图像检索是一个综合性的问题，包含许多相关的子问题。下面对一些主要 的问题进行简要的介绍与分析。 1 1 1 1 图像内容的表示 为实现图像检索，首先面临着如何对图像内容进行表示的问题。传统的工 作主要采用全局特征对图像进行描述。每幅图像通过一个长度固定的特征向量， 如颜色直方图进行刻画。在这种表达方式下，可以赢接采用各种标准的机器学 习和距离度量算法完成图像分析和检索的任务。它的局限性在于缺乏对图像子 区域以及图像中的物体的直接描述能力，因此对不同图像的区分能力有限。比 用一个全局特征稍细致的表示方式是将图像分割成多个子区域，然后对每个子 区域分别进行特征提取。在这种方式下能够实现在区域层次上的图像分析。此 外，为了更充分和准确地把握图像的具体内容，近年来，越来越多的工作采用大 量的局部特征对图像进行表示。尽管具有了更强的描述能力，然而在这种新的 表达方式下，如何度量图像之间的相似性，以及女何与已有的机器学习算法有 机地结合以实现对图像内容的分析，则是急需解决的新问题。 1 第1 章绪论 1 1 1 2 图像分类 图像分类对图像检索具有重要的意义。通过分类能够对图像进行更加有效 的组织和管理。对大规模的图像数据集，首先对图像进行分类，然后在属于同一 类的图像中寻找相似的图像，是缩小查找范围，提高检索速度的有效方法。在分 类的基础上，检索系统也可以对不同类别的图像提取不同特征，或在检索时采 用不同的模型或模型参数，从而提高检索的准确性。此外，为了实现基于关键词 的图像检索，需要首先建立关于图像内容的文本描述。现有的商业图像搜索引 擎主要从图像的文件名、u r l 、a l t 标签以及网页上位于图像周围的文字等文 本信息中提取关键词。然而由于这些文本信息含有很多噪声，采用这种方式获 得的文本描述，准确性往往较低。因此通过分析图像的内容，实现图像的自动标 注成为一个重要的研究课题。图像标注从本质上讲是一个分类问题，因而图像 分类也是实现图像自动标注的重要手段。 1 1 1 3 图像聚类 为了实现图像分类，需要首先定义各图像类别，对于人规模的开放的数据 集，这通常存在一定的困难。定义了图像类别之后，还需要通过人工标注，为每 个类别获取足够的训练图像，以进行分类器的训练，这通常需要耗费相当多的 时间和人力。当无法事先进行图像类别定义或获取足够的人工标注时，根据图 像特征在特征空间中的分布特点，利用无监督的聚类算法实现对图像数据集的 自动划分是一种有效的替代策略。对图像进行聚类除了能够在进行图像检索前 发挥与图像分类相似的作用，如通过对数据集进行预划分缩小查找范围等，在 得到检索结果后，还可以通过对图像进行聚类，方便用户对检索结果进行浏览。 对大规模的数据库，针对每个查询项返回的相关图像的数目往往很大，而用户 的时间和精力是有限的，因此只能浏览一小部分图像。通过对搜索结果进行聚 类，能够帮助用户更快地找到感兴趣的图像； 1 1 1 4 相似性度量 图像之间相似性的度量是实现图像检索的另一个基本问题。对于基于内容 的图像检索，其基本操作即是将目标图像与数据库中的图像依次进行相似性度 量，然后将数据库中的图像按照与目标图像相似性的大小进行排序。图像之间 相似性的度量也是对图像进行分类和聚类的基础。例如，在训练支持向量机时， 2 第1 章绪论 需要首先建立反映训练图像之间相似性关系的核矩阵。而图像聚类的基本准则 是将彼此相似的图像聚为一类。当用一个全局特征表示图像时，图像之间的相 似性通常可以通过传统的方式，如欧式距离等进行度量。而当用局部特征的集 合表示图像时，如何度量相似性却是一个新的需要考虑的问题。 1 1 1 5 相关排序 基于内容的图像检索关注图像与图像之间相似性的大小，而基于关键词的 图像检索则主要关注图像与文本关键词之间相关性的大小。传统的工作通常将 后一类图像检索问题建模成一个两类分类问题。对一个检索词，首先构造一个 包含相关与不相关两类图像的训练集合，然后由此学习一个分类器，检索的时 候则将数据库中的图像按照被分为相关图像的置信度的大小进行排列。从对图 像进行自动标注的角度看，则是将图像按照被标注上相应关键词的置信度的大 小进行排列。这种方法的不足在于，首先，将图像划分为相关与不相关两类是一 个太粗略的划分，图像内容的丰富与多样性决定了不同的图像存在多种不同程 度的相关。其次，训练分类器时通常关注分类的准确性，而检索时则应关注图像 排列的先后次序是否正确。因此训练时优化的目标与对检索结果进行评价时采 用的准则是不一致的。近年来，在机器学习和文本检索领域，研究人员开始关注 排序学习问题，在学习时即直接考虑样本之间的排列关系。排序学习的有效性 在文本检索领域已得到了证明，但在图像检索中，相关的研究工作还非常有限。 可以看到，为了成功地实现图像检索，需要对许多相关的子问题进行研究 和探讨。本文将用一系列基于支持向量机模型的最大间隔方法对这些问题展开 研究。在下一节中，首先对支持向量机及由此所引中出来的最大间隔方法进行 简要的介绍。 1 1 2 支持向量机与最大间隔方法 支持向量机是在统计学习理论基础上发展起来的一种机器学习方法，它采 用结构风险最小化准则进行模型的训练，与传统的神经网络等学习算法相比，在 推广能力上具有明显的优势。近年来，围绕支持向量机的相关研究一直是机器 学习领域的热点。下面，我们从学习问题的定义出发，对支持向量机的基本思想 做简要的介绍。 假设样本( x ，秒) 服从联合概率分布p ( x ，可) ，其中x l 疋为样本输入，犰y 为相应的样本输出，一个学习问题可表述为从给定的函数集合尸= ( ，( x ，q ) i q 3 第l 章绪论 a 中选择一个函数，( x ，o ) ，使得期望风险( 也称为实际风险) ， 冗( a ) = l ( 可，( x ，a ) ) d 尸( x ，可) ( 1 1 ) 最小。其中，( x ，0 f ) 为预测函数( 或称为“学习机器”) ，0 f 为函数的广义参数，厂 可以表示任何函数集合，l ( 秒，( x ，口) ) 是由于，( x ，口) 与秒的误差而造成的在损 失函数l ( ，) 下的损失。 由于p ( x ，秒) 未知，( 1 1 ) 所示的期望风险通常无法计算。因此，传统的学习 方法，如最小二乘法、极大似然法、早期的神经网络方法等，都采用了经验风险 最小化准则进行替代，即假设( x l ，耖1 ) ，( x z ，犰) 为2 个训练样本，则用由训练 样本定义的经验风险 1 z 冗。m p ( a ) = 亭l ( 玑，( 磁，q ) ) ， ( 1 2 ) 。 = 1 作为对期望风险的估计。然而，在实践中，研究人员发现，经验风险的降低并非 总带来实际风险的降低。在一些情况下，可以采用复杂的函数使经验误差降低 至o ，但学习机的推广能力，即在新样本上的预测准确性，却反而降低了。 v a p n i k 等人从2 0 世纪6 0 年代开始致力于小样本情犹下机器学习基本规律 的研究，并逐步建立起一套新的被称为统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o 叻 的理论体系【5 1 。统计学习理论的研究发现，经验风险r 。m 。( 0 ) 和期望风险r ( 0 ) 至少以1 一叩( o 叩o ) 的概率满足以下不等式关系： 冗( 8 ) r 。m ，( q ) + 、鱼坚墼篓翌丛堕! 上蝴， ( 1 3 ) 其中而为函数集合丁的v c 维。v c 维是个反应函数集合学习性能( c a p a c i t y ，容 量) 的指标。v c 维越大，则学习机器越复杂，学习容量越大。尽管还没有通用的 关于任意函数集v c 维计算的理论，但由( 1 3 ) 可知，期望风险的大小不仅跟经 验风险有关，还依赖于一个关于函数集v c 维 的增函数( 称为置信范围) 。在样 本有限的情况下，学习机器的v c 维越高，其复杂性越高，则期望风险与经验风 险的差别可能越大。对同一类学习机，不仅应使经验风险最小，还应使v c 维尽 量小，从而缩小置信范围，使实际风险最小。这种准则又被称为结构风险最小化 准则。统计学习理论最重要和最实用的成果之一即是支持向量机理论。它采用 结构风险最小化准则进行学习机的训练，相比传统的机器学习算法，有许多特 有的优势。 4 第1 章绪论 图1 1 两类分类问题及分类间隔示意图 考虑如图1 1 所示的两类分类问题。我们希望寻找一个分类超平面，能够将 图1 1 中用不同颜色表示的两类样本点分开。可以看到，可以用不同的超平面 ( 红色虚线所示) 实现对训练样本的f 确划分。假设训练样本到分类面的最小距 离称为分类间隔，则支持向量机通过选择使分类间隔最大的分类面( 红色实线所 示) ，实现使结构风险最小的目标。v a p n i k 等从理论上证明了，分类间隔越大，则 分类超平面集合的v c 维越小。因此，使分类间隔最大的分类面即是推广性能最 好的分类面。 直观地看，按照分类间隔最大化的准则得到的分类面，对样本和分类面参 数的微小变化最不敏感，即鲁棒性( r o b u s t n e s s ) 最好。首先，当分类间隔较大时， 即使离分类面最近的样本发生微小的移动，也不会立刻使其从位于分类面的一 侧变成位于另一侧，即不会对其分类结果造成影响。其次，当分类间隔较大时， 分类面的微小变动( 对应学习机参数的微小扰动) ，也不会改变其对训练样本的 分类结果，即原米位于分界面一侧的样本不会因为分界面的微小变动而变成位 于另侧。 间隔最大化准则既具有良好的理论依据，在实践中也表现出期望的性能优 势，同时，在描述上又非常的简洁和直观。因此，问隔最大化的概念甚至不再局 限于支持向量机模型，而成为分析许多不同的分类算法，如b o o s t i n g 、神经网络 等的一个统一原理【6 l 。同时，支持向量机模型及间隔最大化准则也成为解决分类 以外的其他机器学习问题的重要工具。例如，为解决回归问题，人们提出了支持 向量回归算法：为解决样本输入包含多个示例的多示例问题，研究人员提出了 基于支持向量机的多示例学习算法【7 j 面对样本输出具有复杂结构的预测问题， 结构支持向量机应运而生【8 ，9 l 。此外，支持向量机模型还被用于解决距离函数学 5 第l 章绪论 习f l o 】、矩阵分解【1 2 】等不同的问题。这些方法可以通称为最大间隔方法。 针对图像检索这一实际问题，本文一方面着力于如何通过核函数的设计， 使基本的支持向量机分类模型更好地与特定的数据表达形式相结合，从而提升 其分类性能；另一方面，本文将沿着上述基于支持向量机的最大间隔方法的足 迹，研究支持向量机模型和最大间隔准则在排序和聚类等新问题中的应用，从 而进一步拓展其在解决不同的学习问题中的作用和影响力。 1 2 论文的主要工作 由于支持向量机模型和间隔最大化准则在理论和实践上均表现出特有的优 势，因此本文以它们作为基本的理论框架和工具，对图像检索中面临的几个基 本问题分别进行研究，主要包括相似性的度量与图像分类，图像的相关排序，以 及聚类问题。 首先，本文研究采用局部特征表示图像时，如何通过局部特征的匹配，度量 图像之间的相似度，这是进行图像检索以及用支持向量机进行图像分类的基础。 当采用局部特征表示图像时，每幅图像提取的特征的数目是不同的，并且特征 之间没有特定的顺序，因此不能直接使用传统的方法进行相似性度量。为此，一 些方法通过穷举搜索，为每个特征寻找另一个集合中最匹配的特征，并在此基 础上计算特征集合的相似度。这种方法的运算量通常很大，并且由此得到的相 似性度量一般不满足半正定条件，不能直接作为支持向量机的核函数。本文提 出一种双空间金字塔匹配算法，能够快速地计算两个特征集合间的隐式匹配关 系。在进行特征匹配时，同时考虑特征在特征空间中的相似度，以及特征在图像 上的位置之间的对应关系。双空间金子塔匹配首先对特征空间和图像分别进行 多分辨率的划分，然后将每个局部特征的集合映射成建立在双空间中的多分辨 率直方图。特征集合的匹配则通过直方图的加权相交实现。与