（计算机应用技术专业论文）高维索引技术中向量近似方法研究.pdf

摘要 摘要 基于内容的图像检索已经成为图像数据库的一项重要应用。高维数据索引是 加速图像相似性检索的关键技术之一，也是多媒体和数据库领域的研究热点和难 点。传统的多维索引技术在高维情况下会受到“维数灾难”现象的影响，在维数 足够高的情况下( 超过几十维) ，其检索性能会退化到最原始的顺序查找方法，研 究有效的高维索引机制是使面向大规模数据库的检索达到实时性要求的关键。除 了多媒体对象的相似性检索外，高维索引技术也可应用于其他相关领域，如数据 挖掘、模式识别、机器学习、数据统计和分析等。 本文在介绍维数灾难现象的基础上，系统地综述了高维索引技术的研究现状 和发展趋势。向量近似方法是一种有效的高维索引技术，在高维情况下，其检索 性能仍优于顺序查找方法，目前对高维索引技术的研究大部分都是在该方法的基 础上进行。本文主要面向大规模图像数据库上k 近邻搜索应用，在向量近似方法的 基础上，开展对高维索引技术的研究。本论文的主要创新性成果如下所述： 1 向量近似方法是一种基于压缩技术的索引方法，该方法需要顺序访问所有 的近似向量才能完成搜索过程。提出了一种基于主分量排序的新型索引方法，只 要顺序访问部分近似向量即可完成搜索过程。首先在正交变换域上建立近似向量， 选择变换域能量最大的分量作为主分量，根据主分量值对近似向量进行顺序排列， 并且用b + 树存储每个数据页面中的主分量值的范围。在k 近邻搜索过程中，采用 变换域部分失真搜索算法，从初始访问数据页面开始在升序和降序两个方向上顺 序访问近似向量。除了欧氏距离外，本文还将新的索引方法扩展到了二次式距离 和绝对值距离。对于二次式距离，使用奇异值分解技术对向量进行变换。对于绝 对值距离，提出了一种相邻元素相加的多分辨率数据结构。实验结果表明，该索 引方法能够在保持顺序访问方式的基础上，减少近似向量访问数量，提高检索性 能。 2 提出了一种用r 树组织近似向量的新型索引结构- - p c r 树。在正交变换域 上建立近似向量，选择变换域能量最大的多维分量作为主分量，采用r 树来组织 主分量上的近似向量。在k 近邻搜索过程中，采用了新的低维过滤算法来剪枝p c r 树中的目录节点。主分量维数的选取对p c r 树的索引能力影响很大，选取的主分 量维数越少，能量损失越大，过滤效率越低，f o 开销会增大；选取的主分量维数 越多，过滤效率越高，但是索引结构又会受到维数灾难现象的影响。实验结果表 明，在p c r 树中，访问很少的近似向量即可完成搜索过程，从而大幅度降低了搜 索过程中的c p u 运算开销。 西安电子科技大学博士学位论文 高维索引技术中向量近似方法研究 3 提出一种基于矢量量化技术的索引方法。从量化技术角度来看，近似向量 的生成实际上采用了标量量化方法，与标量量化相比，矢量量化能够提供更高的 压缩率，采用矢量量化技术生成近似向量，可以进一步降低近似向量的长度，从 而降低近似文件的存储容量。对特征向量进行矢量量化后，量化码字就是其近似 向量。采用超球来组织矢量量化后胞腔中的数据，根据近似向量可以计算特征向 量与查询向量之间的距离上、下界。为解决矢量量化过程中码字数目过大以及复 杂度过高的问题，采用乘积矢量量化器来生成码书。实验结果表明，该方法能够 在保证过滤效率的基础上，降低近似向量文件的长度，降低搜索过程中的i o 代价， 从而提高搜索性能。 4 探讨了向量近似方法在相关反馈技术中的应用，相关反馈技术中一个很重 要的特性就是在反馈过程中特征向量的表示和相似性度量方式都会发生变化。介 绍了二次式距离和核函数距离上的向量近似方法，并且提出了改进的近邻搜索算 法。反馈过程中相邻两次查询结果具有一定的相关性，改进算法在查询过程中利 用了反馈信息和上轮次的查询结果，可以提高向量近似方法的过滤性能，从而提 高搜索速度。 5 在基于低层特征的图像检索应用中，精确检索得到的结果并不具有精确含 义，最近几年人们提出了近似检索的概念。从索引技术角度来看，近似检索技术 是克服维数灾难现象的一种有效手段。针对本文提出的多种精确索引结构，分别 提出相应的近似近邻搜索算法。( 1 ) 对于顺序访问方式的向量近似方法，采用访问 部分数据集的近似查询方法。( 2 ) 对于基于矢量量化的近似索引方法，提出了用倒 排文件组织近似向量的索引结构和搜索算法，新算法能够大幅度降低c p u 运算开 销，并且只用一次i o 即可完成最近邻查询过程，但是改进算法不能用于多级乘积 矢量量化。( 3 ) 对于p c r 树索引结构，改变了索引结构的构建方法，提出了相应 的近似近邻搜索算法。实验表明，近似检索方法可以在不显著降低检索结果的准 确率的情况下，大幅度提高搜索效率。 关键词：高维索引，基于内容的图像检索，维数灾难，近似检索，相关反馈，向 量近似方法，主分量排序，主分量r 树，矢量量化 西安电子科技大学博士学位论文 a b s t r a c t - 。，_ 。- _ _ 。- _ 。_ 。- - _ _ _ _ _ _ - _ _ _ _ _ _ 。_ 。- _ 。- _ _ _ 。- 1 。 a b s t r a c t a ni m p o r t a n tr e s e a r c hi s s u ei nt h ef i e l do fi m a g ed a t a b a s e si st h ec o n t e n t - b a s e d i m a g er e t r i e v a l h i 曲- d i m e n s i o n a li n d e x i n gh a sb e e nc o n s i d e r e da l li m p o r t a n tm e a n st o i m p r o v et h ep e r f o r m a n c ei nq u e r y i n gl a r g ei m a g ed a t a b a s e s ，a n di t h a sb e e nav e r y a c t i v er e s e a r c ha r e ai nm u l t i m e d i aa n dd a t a b a s ea p p l i c a t i o n so v e rt h el a s tf e wy e a r s i t h a sb e e no b s e r v e dt h a tt h ep e r f o r m a n c eo ft r a d i t i o n a li n d e x i n gm e t h o d sd e t e r i o r a t e r a p i d l ya sd i m e n s i o n a l i t yi n c r e a s e s - - ap h e n o m e n o nw h i c hh a sb e c o m ek n o w na st h e c u r s eo fd i m e n s i o n a l i t y e f f i c i e n ti n d e x i n gs c h e m e sf o rh i g h - d i m e n s i o n a ld a t aa r e r e q u i r e df o rr e a l - t i m eq u e r y i n gi nl a r g e s c a l ei m a g ed a t a b a s e h i 曲一d i m e n s i o n a l i n d e x i n g a l s oc a nb e u s e di no t h e rr e s e a r c ha r e a ，s u c ha sd a t am i n i n g ，p a t t e r n r e c o g n i t i o n ，m a c h i n el e a r n i n ga n dd a t aa n a l y s i s 珏。p h e n o m e n o no f ；c u r s eo fd i m e n s i o n a l i t y i si n 仃o d u c e di n t h i sd i s s e r t a t i o n f i r s t l y , a n dt h ec u r r e n ts t a t u sa n df u t u r ed e v e l o p m e n tt r e n do fh i 【g h - d i m e n s i o n a l i n d e x i n g a r es u m m a r i z e d t h ev e c t o r a p p r o x i m a t i o na p p r o a c h i s 8 , 1 1 e f f i c i e n t h i g h d i m e n s i o n a li n d e x i n gm e t h o d w h i c hc a r l r e d u c et h e d i f f i c u l t yo f c u r s eo f d i m e n s i o n a l i t y m o s to ft h er e s e a r c h e so nh i g h d i m e n s i o n a li n d e x i n ga r eb a s e do n v e c t o ra p p r o x i m a t i o na p p r o a c h t l l i sd i s s e r t a t i o nf o c u s e sr e s e a r c ho nt h ek n e a r e s t n e i g h b o rs e a r c hi nl a r g e - s c a l ei m a g ed a t a b a s e s s o m en e wm o d i f i e dm e t h o d sb a s e do n v e c t o ra p p r o x i m a t i o na p p r o a c ha r ep r e s e n t e d m a i ni n n o v a t i v ec o n t r i b u t i o n sa r ea s f o l l o w s 1 t h ev e c t o ra p p r o x i m a t i o na p p r o a c h e ss u g g e s ta c c e l e r a t i n gt h es e q u e n t i a ls c a n b yb s eo fd a t ac o m p r e s s i o n ，a n dt h e yn e e dt or c c e s sa l lo ft h ea p p r o x i m a t ev e c t o r s a n e wh i g h d i m e n s i o n a l i n d e x i n gs t r u c t u r eb a s e dv e c t o ra p p r o x i m a t i o nm e t h o dw a s i n t r o d u c e d t h ea p p r o x i m a t ev e c t o ri sb u i l ta tt h ed i s c r e t ew a v e l e tt r a n s f o r md o m a i n ， a n dt h ef i r s tc o m p o n e n ti sc h o s e na sp r i n c i p a lc o m p o n e n t as e q u e n c ei n d e xi sb u i l t a c c o r d i n gt ot h ep r i n c i p a lc o m p o n e n t ，w h i c hu s e sb + t r e et om a n a g et h ea p p r o x i m a t e v e c t o r s w h e np e r f o r m i n gk n e a r e s tn e i g h b o rs e a r c h ，t h ep a r t i a ld i s t o r t i o n s e a r c h i n g a l g o r i t h mi s u s e dt or e j e c tt h ei m p m p e ra p p r o x i m a t ev e c t o r s o n l yas m a l ls e to f a p p r o x i m a t ev e c t o r sa r ea c c e s s e dd u r i n gt h es e a r o h ，w h i c hc a nr e d u c et h ec o m p u t a t i o n a l c o m p l e x i t ya n di oc o s t t h en e wm e t h o da l s oc a ns u p p o r tq u a d r a t i cf o r md i s t a n c ea n d 厶d i s t a n c e f o rq u a d r a t i cf o r md i s t a n c e ，s i n g u l a rv a l u ed e c o m p o s i t i o nt e c h n i q u ei s u s e dt og e tt h ep r i n c i p a lc o m p o n e n t f o r l ld i s t a n c e ，an e wm u l t i r e s o l u t i o nd a t a 西安电子科技大学博士学位论文 高维索引技术中向量近似方法研究 s 缸u c t l l r ei sb u i l ta c c o r d i n gt ot h es u mo fa d j a c e n te l e m e n t s t h ee x p e r i m e n tr e s u l t so n l a r g ei m a g ed a t a b a s e ss h o wt h a tt h en e w m e t h o dc a ni m p r o v et h ep e r f o r m a n c eo f v e c t o r a p p r o x i m a t i o na p p r o a c h 2 an e wh i g h - d i m e n s i o n a li n d e x i n gs t r u c t u r ec a l l e dp c r t r e e0 r i n c i p a l c o m p o n e n t srt r e e ) w a sp r e s e n t e d ，w h i c he m p l o y sl o w d i m e n s i o n a lr t r e et om a n a g e t h ea p p r o x i m a t ev e c t o r sa tp r i n c i p a lc o m p o n e n t s t h ep r i n c i p a lc o m p o n e n t si nt h e p c r t r e ea r em u l t i d i m e n s i o n a l ，a n dt h el o wd i m e n s i o n a lm b r s ( m i n i m u mb o u n d i n g r e c t a n g l e s ) c a nb eb u i l to na p p r o x i m a t ev e c t o r s a t p r i n c i p a lc o m p o n e n t s w h e n p e r f o r m i n gk - n e a r e s tn e i g h b o rs e a r c h ，an e wl o w e r - b o u n df i l t e r i n ga l g o r i t h mi su s e dt o r e j e c tt h ei m p r o p e rn o d e so fp c r t r e e i t sv e r yi m p o r t a n tt os e l e c tt h ed i m e n s i o no f p r i n c i p a lc o m p o n e n t s w h e nt h ed i m e n s i o no fp r i n c i p a lc o m p o n e n t si sl o w , t h e r ei s m o r ei n f o r m a t i o nl o s tl e a d i n gm o r en o d e st ob ee x a m i n e d w h e ni ti sh i g h ，t h en o d e s a c c e s sc o s ta l s ob e c o m e sh i g hd u et od i m e n s i o n a l i t yc u r s e t h ee x p e r i m e n tr e s u l t so n l a r g ei m a g ed a t a b a s e ss h o wt h a tt h en e wa p p r o a c hp r o v i d e saf a s t e rs e a r c hs p e e dt h a n o t h e rt r e e s t r u c t u r e dv e c t o ra p p r o x i m a t i o na p p r o a c h e s 3 t h ea p p r o x i m a t ev e c t o r sa r eb u i l ta c c o r d i n gt os c a l a rq u a n t i z a t i o ns c h e m e a n e wh i g h - d i m e n s i o n a li n d e x i n gs 仃u c n 雌b a s e dv e c t o rq u a n t i z a t i o ni si n t r o d u c e d t h e v c t o rq u a n t i z a t i o ni st h eb e s tq u a n t i z a t i o ns c h e m e , w h i c ha c h i e v e sag o o db a l a n c e b e t w e e nq u a l i t yo fv e c t o rr e c o n s t r u c t i o na n dt h en u m b e ro fb i t su s e dt od e s c r i b et h e v e c t o r s av e c t o rc a nb ed e s c r i b e du s i n gt h ec e l li nw h i c ht h ev e c t o rl i e s i nt h en e w s t r u c t u r e ，a p p r o x i m a t ev e c t o ri st h ei n d e xo fc o d e b o o k t h es p h e r ei su s e dt om a n a g e t h ed a t ai nt h es a m ec e l l a c c o r d i n gt ot h es p h e r e t h el o w e ra n du p p e rb o u n do f d i s t a n c eb e t w e e nq u e r ya n dv e c t o rc a nb ec a l c u l a t e d w h e np e r f o r m i n gk n e a r e s t n e i g h b o rs e a r c h ，t h er e p r o d u c t i o nv e c t o ra n dt h es p h e r ec a nb eu s e dt of i l t e rt h e a p p r o x i m a t ev e c t o r s i n o r d e rt or e d u c et h es i z eo fc o d e b o o k ，t h e s p l i t v e c t o r q u a n t i z a t i o ns m l c t l l r ci sa d a p t e d t h ee x p e r i m e n tr e s u l t so nh i g h - d i m e n s i o n a li m a g e f e a t u r ed a t a b a s e ss h o wt h a tt h en e wa p p r o a c hc a nr e d u c et h ei oc o s td r a m a t i c a l l yt h a n v e c t o ra p p r o x i m a t i o na p p r o a c h 4 r e l e v a n c ef e e d b a c k t e c h n i q u e sa r ei m p o r t a n ta p p r o a c h e sc l o s i n gu pt h e s e m a n t i cg a pb e t w e e nh i g h - l e v e lc o n c e p t sa n dl o w - l e v e lf e a t u r e si ni m a g er e t r i e v a l a n e wk - n e a r e s tn e i g h b o rs e a r c ha l g o r i t h mb a s e do nv e c t o ra p p r o x i m a t i o na p p r o a c hf o r r e l e v a n c ef e e d b a c ki m a g er e t r i e v a li si n t r o d u c e d b a s e do nt h e f e e d b a c k ，t h e c o r r e l a t i o n so ft h eu n d e r l y i n gs i m i l a r i t ym e t r i cb e t w e e nt w oc o n s e c u t i v es e a r c h e si s 西安电子科技大学博士学位论文 a b s t r a c t e x p l o i t e d ，t h e nt h es e a r c hr e s u l ta n df e e d b a c k sa r eu s e dt of i l t e r i n gt h ea p p r o x i m a t e v e c t o r si nt h en e x ts e a r c hr o u n d e x p e r i m e n t ss h o war e m a r k a b l er e d u c t i o no fv e c t o r s a c c e s s e d ，a n dt h e ya l s os h o wa ni m p r o v e m e n to nt h ei n d e x i n gp e r f o r m a n c ec o m p a r e d w i t ht h ee x i s t i n gs e a r c ha l g o r i t h m s 5 i nt h ei m a g er e t r i e v a lb a s e do nl o w l e v e lf e a t u r e ，t h ee x t r a c t i o no ff e a t u r e v e c t o r si sah e u r i s t i c p r o c e s s t h a t a t t e m p t s t o a p p r o x i m a t e l yc a p t u r er e l e v a n t i n f o r m a t i o n a p p r o x i m a t es i m i l a r i t ys e a r c hi sa ne f f i c i e n tw a y t or e d u c et h ed i f f i c u l t yo f c u r s eo fd i m e n s i o n a l i t y f o ra l lo ft h ei n d e x i n gs t r u c t u r e sp r e s e n t e di nt h i sd i s s e r t a t i o n ， t h ea p p r o x i m a t es i m i l a r i t ys e a r c ha l g o r i t h m sa r ea l s oi n t r o d u c e d ( 1 ) f o rt h el i n e a rs c a n s t r u c t u r e ，e a r l yt e r m i n a t i o ns t r a t e g i e sa r eu s e d ，i nw h i c hs e a r c ha l g o r i t h m sa r e p r e m a t u r e l ys t o p p e dw h e nc u r r e n tr e s u l ti sj u d g e dt ob es a t i s f y i n gt h ea p p r o x i m a t i o n r e q u i r e m e n t s ( 2 ) f o rp c r - t r e e ，t h ei n d e x i n gs t r u c t u r ei sm o d i f i e dt os a t i s f yt h e a p p r o x i m a t es e a r c h ( 3 ) f o rt h ea p p r o x i m a t es e a r c ha l g o r i t h mb a s e do nv e c t o r q u a n t i z a t i o n ，an e ws t r u c t u r ei sp r e s e n t e dw h i c hs t o r et h ea p p r o x i m a t ev e c t o r sb y i n v e r t e df i l ea n do r g a n i z et h ei n v e r t e df i l eu s i n gh a s ht a b l e e x p e r i m e n t sr e s u l t ss h o w ar e m a r k a b l es p e e d u po fp e r f o r m a n c ei nk - n e a r e s tn e i g h b o rs e a r c ha l l o w i n gas m a l l r e d u c t i o no f r e s u l tq u a l i t y k e yw o r d s ：h i 曲一d i m e n s i o n a li n d e x i n g ，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 u r s eo f d i m e n s i o n a l i t y , a p p r o x i m a t es i m i l a r i t ys e a r c h ，r e l e v a n c ef e e d b a c k ，v e c t o r a p p r o x i m a t i o na p p r o a c h , p r i n c i p a lc o m p o n e n ts o r t i n g ，p r i n c i p a lc o m p o n e n t sr t r e e ，v e c t o rq u a n t i z a t i o n 西安电子科技大学博士学位论文 创新性( 或独创性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名日期竺三：2 三：1 7 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于机密，在一年解密后适用本授权书。 本人签名 导师签名 日期鲨! 坐! 心 第一章绪论 第一章绪论 1 1 课题的目的和意义 随着多媒体技术和网络技术的飞速发展，多媒体信息的应用日益广泛，对规 模越来越大的多媒体数据库进行有效的管理成为迫切需要解决的问题。高效、准 确的多媒体检索策略是解决这一问题的关键技术之一。图像是最为广泛和基本的 多媒体信息，因而图像检索已成为计算机和多媒体领域的研究热点 1 0 川1 。 1 1 1 基于内容的图像检索 图像检索技术提供了通过图像描述信息从海量图像数据库中检索感兴趣目标 的有效手段，从2 0 世纪7 0 年代开始成为一个活跃的领域。早期的图像检索技术 普遍采用文本或关键词的方式，即首先对图像进行文本注释，然后通过基于文本 的数据库管理技术( d b m s ) 实现图像检索，被称为基于文本的图像检索( t e x t - b a s e d i m a g er e t r i e v a l ) 。然而，基于文本的图像检索存在一些明显的不足之处，主要包 括： ( 1 ) 随着图像数量的增多，手工注释文本信息的工作量太大。 ( 2 ) 许多存在于图像中的丰富的与人类感觉主观性相关的可视化信息不能够 通过文字进行完整、全面、准确的描述，并且不同的人对于相同的图像可能会有 不同的认知，将所有不同的认知或理解都转化为关键词( 文本或数字) 的形式几 乎是不可能的。 ( 3 ) 如果图像的信息描述有歧义性，则在检索时不会返回或者返回不准确或 者错误的结果。 由此可见，单纯的基于文本的图像检索技术已经不能满足人们的需要。解决 上述问题的一个理想方案是由计算机自动理解图像的内容，并给图像加上客观而 且全面的概念性标注。但是，由于在图像理解和模式识别研究中有许多尚未解决 的难题，就目前的技术而言，当不限定图像内容的范围时，要做到任意图像的自 动理解还远远不是一件可能的事情。因此，需要从一个中间层次来研究图像内容 的表示以及检索问题，即基于内容的图像检索技术的研究。 到2 0 世纪9 0 年代初，人们提出了基于内容的图像检索( c o n t e n t b a s e di m a g e r e t r i e v a l ，简称c b i r ) 的概念，试图从理解图像本身特征的角度实现图像检索。 与传统的基于文本或者关键词的图像检索技术不同，c b i r 技术试图通过图像内 西安电子科技大学博士学位论史 高维索引技术中向量近似方法研究 容( 人对图像的理解和认知) 来表示图像，通过图像内容来检索图像。c b i r 技 术是一门包括数据库技术、计算机视觉、图像处理和模式识别等在内的众多学科 相互交融和相互促进的新兴边缘学科。实现基于特征的图像检索的基本思路( 过 程) 是：从图像中分析并提取低层视觉特征，构成特征向量，通过特定的距离定 义方式计算特征向量之间的距离获取图像之间的相似程度，从而实现基于内容的 检索。 目前，国内外很多机构都开展了相关的研究计划和项目，取得了很多令人瞩 目的成就，并开发出很多商用和研究用的系统。其中有代表性的有q b i c t l _ 5 、 v i r a g e 6 1 、v i s u a l s e e k 和w e b s e e k 7 ，8 1 、p h o t o b o o k 2 1 以及m a r s 9 等。基于内容的 图像检索的研究和应用主要集中在三个方面：特征提取( f e a t u r ee x t r a c t i o n ) ，有 效检索( e f f i c i e n ti n d e x i n g ) 及用户接口( u s e r i n t e r f a c e ) 。 1 特征提取 图像的特征主要包括低层特征( p r i m i t i v ef e a t u r e s ) 和语义特征( s e m a n t i c f e a t u r e s ) 。低层特征主要包括图像的颜色、形状、纹理和空间关系等一些定量的特 征，这些特征可以通过计算机自动或人机交互的方法来提取。图像的语义特征是 一种定性特征，是对图像内容的抽象描述。目前，语义特征主要通过人工或人机 交互的方式提取。在不同的应用领域c b i r 系统将采用不同的特征或特征组合进 行检索。 2 有效检索 为了有效的完成图像检索，必须解决图像特征的有效存储问题以及选取合适 的相似性度量准则问题。图像特征通常由高维向量表示，在大容量图像库情况下 提高搜索效率成为突出的问题。因此，面向大容量图像库的检索系统需要有效的 数据索引机制来加速检索过程，以达到实时性的要求。同时，合理的相似性度量 方法也是执行有效图像检索的关键，常用的相似性度量方法主要包括：欧氏距离、 绝对值距离、二次式距离等。不同的相似性度量方法也有其内在的优点和缺点， 并非某一种度量方法对所有的图像检索系统均适用，它们也有各自的适用范围。 3 用户接口 图像检索的最终结果是交给用户的，因此在图像检索系统中，用户接口也起 着重要的作用，它在用户和检索系统之间提供了一种交互式的检索机制用户可 以通过该接口选取合适的查询机制以及浏览图像检索结果。用户接口所提供的常 用检索机制主要包括：关键词查询( q u e r yb yk e y w o r d ) 、草图查询( q u e r yb y s k e t c h i n g ) 、例子查询( q u e r yb ye x m a p l e ) 、类别浏览( b r o w s i n gb yc a t e g o r i e s ) 、图像 特征和权值选取( f e a t u r es e l e c t i o na n dw e i g h t i n g ) 及相关反馈( r e l e v a n c ef e e d b a c k l 西安电子科技大学博士学位论文 第一章绪论 等。 m p e g ( m o v i n g p i c t u r ee x p e r tg r o u p 运动图像专家组) 在上述研究的基础上， 致力于制定和完善通用的“多媒体内容描述接口”( m u l t i m e d i ac o n t e n td e s c r i p t i o n i n t e r f a c e , m p e g 7 ) 标准 1 0 , 1 1 ，目标就是要制定一个标准化的多媒体内容描述的 框架，以便于多媒体内容的有效表示和检索。m p e g 7 标准也试图实现集高层语 义特征和低层视觉特征的多特征综合检索。 1 1 2 图像检索面临的主要问题 目前，基于内容的图像检索方法主要面临两个问题： 1 语义特征提取 基于语义的检索( s e m a n t i c - b a s e dr e t r i e v a l ) 是图像检索的理想方案 1 2 , 1 3 , 1 4 】， 是计算机发展的智能表现，由于目前计算机视觉、图像理解和模式识别的发展水 平所限，这些领域有许多尚未解决的难题，目前基于语义的检索还没有很好的解 决方案，使得c b i r 系统还无法真正支持基于语义的图像检索。由于图像语义的 丰富性和用户需求判断的主观性，基于低层视觉特征的c b i r 系统往往不能满足 以高层语义为特征的检索需求。为了解决这一问题，近期c b i r 系统大都采用了 基于相关反馈( r e l e v a n c ef e e d b a c k ) 的交互机制 1 5 , 1 6 , 1 7 , 1 8 , 1 9 , 2 0 , 2 1 ，将用户模型嵌入 到图像检索系统。基于内容的相关反馈是一个逐步求精的交互过程。 2 高维索引 c b i r 系统通常提取图像基本可视特征组成特征向量。通过某种距离度量方 式计算特征向量之间的距离可以衡量图像之间的相似性，这种相似性查询可以看 成是向量空间中的近邻搜索问题。由于表示图像特征的向量维数较高，传统的 多维索引技术在特征维数足够高的情况下( 超过几十维) ，近邻搜索性能会低于原 始的顺序查找算法，这种现象被称为“维数灾难”( c u i s eo f d i m e n s i o n a l i t y ) 2 2 2 3 , 2 4 。 采用相关反馈的图像检索是一种多轮次的交互查询过程，要保证在大规模图像数 据库检索时达到实时性要求，必须采用有效的高维数据索引机制来加速检索过程。 随着图像库容量的迅速增大，图像检索的实时性要求也日益突出。在传统多维索 引技术的基础上探索更加有效的高维索引技术就成为一个急需解决的问题【3 1 。 1 2 多维索引技术 索引技术是加速图像相似性检索的关键技术之一，也是多媒体和数据库领域 的研究热点和难点。由于内存储器( 内存) 的容量限制，大规模的多媒体数据库 西安电了科技大学博士学位论文 高维索引技术中向量近似方法研究 中数据对象存储在外部存储设备( 外存) 中。对外存中的数据建立索引结构可以 在查询时迅速定位所需数据，提高查询效率。研究者提出了许多有效的针对多维 数据底检索结构 2 5 , 2 6 。著名杂志a c mc o m p u t i n gs u r v e y s 在最近几年就刊登了多 篇有关多维数据索引技术的综述文章 2 7 , 2 8 , 2 9 , 3 0 】。国内也有类似的综述文章阻3 2 ”】。 在这些索引结构中，每种结构都有自己性能比较突出的适用范围。适用所有场合， 所有数据分布情况的索引结构是不存在的。许多因素，包括数据的类型，分布的 情况，维数的大小等，都会对一种索引结构的性能产生很大的影响。 在多维索引结构中，树型索引结构是最常用的索引结构，它的构建方法实际 上是基于数据空间的层次化聚类原则。从结构上来讲，多维树型索引结构类似于 一维数据索引结构一b 树【3 4 1 。它的节点也分为叶子( 数据) 节点和目录节点，向 量存储在数据节点中，空间位置临近的向量尽可能存储在同一节点。一般说来， 同一个数据节点中的数据存储在同一个数据页面中。节点之间以层次化目录结构 来组织，每一个目录节点都指向下一级的一个子树。通常，数据节点的数据结构 与目录节点的结构完全不同。比较而言，目录节点在各个索引级上具有更好的一 致性。在这种层次化组织结构中，一般存在一个被称之为根节点的单独目录节点， 它是进行查询和更新处理的开始节点。目前的索引结构大都采用平衡树的构建方 法，即对任何一个目录节点，其所有子树的高度( 深度) 差不超过1 。树型索引 结构的查询性能主要与树型结构的高度有关。 按照节点的建立方式不同，树型多维索引结构可以进一步划分为数据点划分 和空间划分两大类。基于数据点划分的索引结构包括r 树、r + 树、r + 树唧、 x 树渊、s s 树【3 9 】、s r 4 川树等。在这些索引结构中，r 树，r + 树，r + 树，x 树的 目录节点采用i v l b r ( m i n i m u m b o u n d i n gr e c t a n g l e ，最小外接矩形) 表示，s s 树的 目录节点采用超球( s p h e r e ) 表示，s r 树则将这两种目录节点的表示方法相结合。 在搜索过程时，根据m b r 或外接超球可