（计算机科学与技术专业论文）聚类算法在图像索引中的应用与研究.pdf

中文摘要 摘要：随着网络技术，数字多媒体技术的高速发展，各类的信息迅速增长，人们 接触到大量的图像信息，导致人们对图像检索的要求越来越迫切。传统的基于文 本的图像检索已经不能适应环境的发展。基于内容的图像检索技术应运而7 k ，它 借助于自动提取的高维特征，对图像进行近似匹配，是融合了多种技术的图像检 索技术。 本文首先介绍了基于内容的图像检索技术的背景、发展和研究现状，总结了 一个通用的基于内容的图像检索的框架，在此基础上对基于内容的图像检索的两 个核心问题，特征提取和表示，相似性度量进行了系统的介绍。 在图像数据库中，图像的特征表示为高维的特征向量。图像特征的商维特性 使得一般的传统索引结构不再适合，高维数据空l h j 的索0 i 成为一个重要的研究领 域。基于内容的图像检索非常需要高效的索引来提高性能。本文首先介绍了聚类 分析的方法，并对小波分析的概念和典型高维索引结构进行了系统的阐述。最后 从聚类的预处理出发，结合小波分析，提出了一种新的索引结构c b b t r e e 索引结 构。该索引结构是对一种聚类树的改进，结合了b + 树的搜索性能。在这个设计思 想下，作者设计并实现了一个基于内容的图像检索实验系统，通过大量的实验结 果比较分析，证明了提出的这个新的索引结构能够提高基于内容的图像检索的效 率。 关键词：基于内容的图像检索；一聚类分析；高维索引结构 分类号：t p 3 9 1 a b s t r a c t a b s t r a c t ：w i t ht h eh i g h - s p e e dd e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dd i g i t a l m u l t i m e d i at e c h n o l o g y , a n dt h er a p i dg r o w t ho fv a r i o u st y p e so fi n f o r m a t i o n ，p e o p l e l i v ei naw o r l da r o u n dal a r g en u m b e ro fi m a g e s ，r e s u l t i n gi nm o r ea n dm o r ep r o c e s s i n g r e q u i r e m e n t so fi m a g er e t r i e v a l h o w e v e r , t r a d i t i o n a lt e x t b a s e di m a g er e t r i e v a lh a sn o t a d a p t e dt ot h ec u r r e n te n v i r o n m e n t 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 ) c a m ei n t o b e i n g c b i re x t r a c t st h eh i g h d i m e n s i o n a li m a g ef e a t u r e sa u t o m a t i c a l l y , a n dt h e nd o e s a p p r o x i m a t ei m a g em a t c h i n gt of i n dt h et a r g e ti m a g e i ti sak i n do fi m a g er e t r i e v a l t e c h n o l o g yw h i c hi n t e g r a t e sav a r i e t yo fo t h e rt e c h n o l o g y f i r s t ，t h i sp a p e ri n t r o d u c e st h eb a c k g r o u n d ，d e v e l o p m e n ta n dc u r r e n tr e s e a r c ho f c b i r ，a n ds u m m a r i z e sac o m m o nc 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 a n dt h e n t h i sp a p e rs e t sf o r t ht w oc o r ei s s u e s ：f e a t u r ee x t r a c t i o na n dr e p r e s e n t a t i o n ，s i m i l a r i t y m e a s u r e i nt h ei m a g ed a t a b a s e ，i m a g e sa r ei n d e x e dw i t hh i 曲- d i m e n s i o n a lf e a t u r ev e c t o r s m a n yr e s e a r c h e sh a v es t u d yp l e n t yo ft r e e - l i k ei n d e x i n gs t r u c t u r e ss ot h a ti tc a nm e e t t h er e q u e s to fe f f e c t i v ei m a g er e t r i e v a l b u i l d i n ga ni n d e x i n gs t r u c t u r ei ni m a g e i n f o r m a t i o nr e t r i e v a lb e c o m e sav e r yc h a l l e n g i n gi s s u e t h i sp a p e ri n t r o d u c e sk i n d so fc l u s t e r i n gm e t h o d s t h ec o n c e p to fw a v e l e ta n a l y s i s a n ds o m et y p i c a lh i g h - d i m e n s i o n a li n d e xs t r u c t u r e s a f t e ra l l ，f r o mt h ec o m b i n a t i o no fa c l u s t e r i n gm e t h o da n dw a v e l e tt r a n s f o r m a t i o n ，an e w i n d e xs t r u c t u r ec a l l e dc b b - t r e ei s p r o p o s e d i ti sa ni m p r o v e m e n to fc l u s t e rt r e ew h i c ht a k e sa d v a n t a g eo fm u l t i s c a l e s e a r c h i n gp e r f o r m a n c ec o m b i n e dw i t ht h eg o o di op e r f o r m a n c eo fb + t r e e o nt h eb a s i so ft h i sn e wc b b - t r e e ，t h ea u t h o rd e s i g n sa n dr e a l i z e sac o n t e n t - b a s e d i m a g er e t r i e v a le x p e r i m e n t a ls y s t e m al a r g en u m b e ro fc o m p a r a t i v ea n a l y s i st o e x p e r i m e n t a lr e s u l t sp r o v et h a t t h ep r o p o s e di n d e x i n gs t r u c t u r ec a ni m p r o v et h e e f f i c i e n c yo fi m a g e r e t r i e v a l k e y w o r d s ：c b i r ；c l u s t e r i n gm e t h o d ；h i 曲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 e c i a s s n o ：t p 3 9 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 杨尚 导师签名：诈癌砌 签字日期：咿。7 年舌月偿日签字日期：另卯尹年多月谚日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使j 】过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 柄嘞签字日期：们。7 年多月，扩日 致谢 本论文的工作是在我的导师许宏丽副教授的悉心指导下完成的，在此向许宏 丽老师表示衷心的谢意。 从本论文的立题、资料收集直至最后完稿的整个过程中，许老师都给予我f ! 多的指导、建议和帮助。许老师不仅让我学到了专业知识，更多的是订：我学剑了 作为一个科研工作者对研究严谨诚实的作风和对学生无私奉献的精神。她f i 断给 予我为人和治学的指导，对我严格要求、悉心关怀，在学习上和生活上都给予了 我很大的关心和帮助。再次衷心地感谢两年来许老师对我的关心和指导。 在实验室工作及撰写论文期间，逯晓鹏、谷君、朱振宇等同学对我沦文的研 究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校心究成我的学、i k 。感 谢所有帮助过我的人们! 1 绪论 1 1 课题的研究背景与意义 有研究表明，人类获取外界信息时，7 0 以上的信息来自于视觉。而图像作为 视觉信息的重要载体，由于直观、内容丰富和尤语者限制等特点，越来越受到人 们的关注和重视。近年来，随着数字技术、大容量的存储设备以及计算机网络技 术的发展和普及，可获取的图像数量呈现出爆炸式的增长速度。数字图像的应用 已经深入到科研、生产以及生活的各个方面，对军事、气象、通信、医学、新闻 媒体、文化娱乐等都产生了重大影唰1 1 。面对如此海量的数7 - 图像信息资源和广泛 的需求应用，如何合理地组织这些资源，并且如何从海量数掘i f l 快速有效地提取 有用信息，使得图像数据库的管理工作成为一个迫切的研究课题，图像检索技术 是其中的核心技术之一【2 】。国际上从上世纪7 0 年代初就开始了对图像检索技术的 研究，迄今有一大批研究性的或商用的图像检索系统已经建立。图像检索在学术 领域与实际应用方面都有重要的价值，有着广泛的应用前景。然而目前图像检索 技术还远远不能满足人们的实际需求，因此对该问题的研究具有实际意义。 1 2 技术发展与研究现状 从图像检索技术发展的过程来看，主要经历了两个阶段：基于文本的图像检 索和基于内容的图像检索。 1 2 1 基于文本的图像检索 早期图像检索使用的是文本标注方法( t e x t b a s e di m a g er e t r i e v a l ) 【3 j ，当时 流行的图像检索系统是将图像作为数据库中存储的一个对象，用关键字或自由文 本对其进行描述。其典型框架是首先用文本对图像进行注解，然后用基于文本的 数据库管理系统进行图像的检索，检索操作是使用该图像的文本描述进行精确匹 配或者概率匹配，有些系统的检索模型还有词典支持。t a m u r a 对基于人工注释的 图像检索技术给出了全面的综述【4 】。 基于文本的图像检索技术在比较小的图像数据库和图像内容比较单一时能发 挥很好的效果。目前一些著名的搜索引擎如y a h o o 和g o o g l e ，采用关键字和描述 文本进行查询图像。它们虽然取得了成功的应用，但由于该方法仅仅用到文本信 息，而没有考虑到图像的可视特性，面对着成千上力- 的海量规模图像数据时，也 存在着一些无法回避的问题【5 】： ( 1 ) 图像内容难以精确地用文本描述 文本描述是一种定性描述，而图像中往往含仃太多的定量描述信息。因此， 采用文本难以对图像进行精确描述。还有，许多图像特征难以用文本描述来表示， 如不规则形状、散布的纹理等。同时，一剐i 纠像能够传达的信息非常丰富，用人 工注释的方式很难充分地表达图像； ( 2 ) 人工标注无统一标准 人工的标注受语言限制。对于不同国家不同民族的人来说，很难用统一的语 言进行标注，导致推广性差，检索结果无法符合用户的需求； ( 3 ) 文本描述客观性差 对于图像来说，由于其内容的丰富性以及视觉的主观性，不同人在理解同一 幅图像时会产生很大的差异，甚至同一个人在不同的环境下对同一幅图像的理解 也可能不相同，从而导致内容的描述具有很大的主观性。这种主观理解的差异将 导致图像检索中的失配； ( 4 )费时费力 受限于目前的计算机视觉和人工智能技术的研究还不成熟，无法对图像进行 自动文本标注，而必须依赖人工对图像做出标注。当数据库规模很大时，耗时费 力。 1 2 2 基于内容的图像检索 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 ) j 应运而生。区别于对图像进行人工标注的做法，基于内 容的图像检索技术自动提取图像的视觉内容特征作为其描述，如色彩、纹理、形 状等。它能根据样本图像生成查询，然后从数据库中直接找到具有特定特征或含 有特定内容的图像。基于内容的图像检索不同于基于文本的检索，它基本不需要 人工参与，具有客观、节省人力、可建立复杂描述、通用性好和应用前景广阔等 许多优点，因此一经出现就受到人们的广泛关注，并得到了迅速的发展【_ 7 1 。 基于内容的图像检索是一项复杂的工作，融合了传统的模式识别技术与良好 的多媒体人机交互技术，是多种技术合成的新兴检索技术。它涉及到图像处理与 理解、模式识别、相似检索和数据库等多方面的关键技术。c b i r 与模式识别、图 2 像理解及计算机视觉等学科的重要区别在于，c b i r 是一种信息检索技术，应能从 大型数据库中，以用户可以接受的响应时间，查询到所要求的信息。 基于内容的图像检索主要具有以下特剧8 】： ( 1 ) 突破了传统的基于关键字检索的局限，直接对图像进行分析，抽取特征。 并利用这些内容特征建立索引，使得检索巫接近图像对象； ( 2 ) 基于内容的图像检索是一种近似匹配的技术。传统的数据库中，符号数据 可以用基本数据类型精确地表示，检索匹配足精确匹配。而图像数据是一段二进 制数据流，对图像进行像素和像素的精确匹配不科学。事实上，人对两个图像的 相似和不相似的判断是根据图像中所包含的内容，很难将其精确描述，因此是一 种近似匹配。在检索过程中，通过某种特i f 以性度量末匹配图像数据集中的对象， 以得到检索的结果； ( 3 ) 因为由计算机来自动实现图像特征的提取和索引的创建，提高了描述的客 观性，减少了人工的工作量。 基于内容的图像检索己成为国内外研究的热点，并成为2 1 世纪必须要攻克的 关键技术之一。其应用领域涉及到多媒体数据库、军事领域、建筑和工程设计、 时尚和室内装演设计、旅游业和广告业、地理信息系统和遥感系统、考古学、教 育和训练、家庭娱乐、电子图书馆、商标管理、医疗图像管理、公安系统以及卫 星图像管理等众多领域。 1 2 3 研究现状 自9 0 年代早期开始，基于内容的图像检索已经成为一个非常活跃的研究领域， 一大批研究机构和学者投入到c b i r 的研究上来，同时一些研究性或商用的图像检 索系统也被建立起来。但是基于内容的图像检索仍然处于极不成熟的阶段，要想 达到使用水平仍有较远的距离，还有许多关键技术需要进一步研究。下面介绍一 些典型的c b i r 系统。 1 q b i c ( q u e r yb yi m a g ec o n t e n t ) 最早的基于内容的图像查询系统是由i b ma l m a d e l lr e s e a r c hc e n t e r 的m y r o n f l i c k n e r 等推出的q b i c 9 。它主要集中于基于非语义内容的图像和视频检索。图 像内容的表示是在整幅图像或图像的一部分上进行的。图像中的对象通过与用户 交互来标识。q b i c 支持基于示例图像、用户手画草图以及选择的颜色和纹理模式 等多种查询方式。图像中的对象特征包括颜色、纹理和形状等。q b i c 中使用的颜 色特征是( r ，g b ) ，( y i ，q ) ，( l ，如) 和m t m 色坐标的平均以及k 元颜色直方图。所 使用的纹理特征是t a m u r a 纹理表示的改进版，即粗糙度、对比度和方向度的组合 b o 。形状特征有形状的面积、周长、奇异度、轴心方向和代数不变矩。在q b i c 系统中，它首先使用k l 变换对特征空间进行维数压缩，然后使用r 树对高维特 征进行索引。q b i c 的查询在索引结构上进行，它是少数几个使用高维特征索引的 系统之一。 2 m a r s ( m u l t i m e d i aa n a l y s i sa n dr e t r i e v a ls y s t e m ) m a r s 】【1 2 1 是由美国大学u r b a n a c h a m p a i g n 分校开发的，支持色彩、纹理、 形状的组合查询以及纹理查询。j 研究焦点4 i 再是找到单一的最佳特征表达，1 i l j 是根据实际的应用环境和用户需要在检索框架中动态地组合调整各种不同的图像 特征。在图像特征方面，使用h s v 空间的h s 上的颜色直方图来描述图像的颜色； 抽取图像纹理的粗糙度和方向性以及对比度等特征描述纹理；采用图像的规则分 割的方法对图像特征的空间分布进行描述；根据纹理对图像进行分割来实现图像 中的对象描述，并对分割后的对象区域按照敏感性进行分组；使用f o u r i e r 描述了 对图像中对象的形状进行描述。检索时对上述特征分别采用相应的相似度度量力 法，最终给出综合排名。m a r s 在图像检索领域正式提出了相关反馈的体系结构， 并在检索中不同层次上结合了该技术，包括查询矢量优化、自动匹配工具选择和 自动特征适应。m a r s 无论在研究角度还是应用领域都和其它的图像检索系统有 很大的差异，主要是因为m a r s 是一个多学科交叉融合的产物，包括计算机视觉、 数据库管理系统以及传统的信息检索技术。 3 s u a l s e e k 和、7 | 瞻i b s e e k v i s u a l s e e k t l 3 】和w e b s e e k t l 4 】系统是万维网图像影像检索工具，其研制者 j o h nrs m i t h 毕业于哥伦比亚大学电子信息研究中心。s u a l s e e k 是一个基于图 像视觉特性的搜索引擎，w e b s e e k 实际上是它的一种，是面向w e b 的文本和图像 搜索引擎。s u a l s e e k 系统由四部分组成：图形用户界面、服务器应用、图像检 索服务器和图像归档。s u a l s e e k 提供了基于颜色和纹理的索引方法，整幅图像 颜色的分布使用了全局颜色直方图，区域颜色的索引用二进制颜色集表达方法； 采用了基于小波变换的方法来表示图像的纹理特征。其特点是提供对图像区域的 空间关系的检索，图像的特征从图像的压缩域中获得，并且使用q u a d t r e e 和r t r e e 的索引结构提高检索速度。现己在电子图书馆等领域得到了一些应用。w e b s e e k 包括三个模块：图像视频收集、分类与索引和搜索以及浏览和检索，支持结合关 键词的检索，并使用用户相关反馈技术来改进检索效果。 相对于其它的多媒体检索系统，v i s u a l s e e k 的优点在于：高效的w e b 图像 信息检索，采用了先进的特征抽取技术，用户界面强大，操作简单，查询途径丰 富，输出画面生动且支持用户直接下载信息。w e b s e e k 本身就是一个独立的万维 网可视化编程工具，用户可以使用目录浏览和特征检索方式进行图像检索。 4 4 v i r a g e v h a g e 1 5 是由v i r a g e 公司开发的基于内容的图像搜索引擎。v i r a g e 不但支持基 于颜色、颜色布局、纹理和结构( 对象边界信息) 的可视化查询，而且支持由上 述四个原子查询的任意组合。用户可根据他们自己的侧重调整这四个原子查洵的 权丘，j e f f r e y 等人进一步提出了图像管理的一个开放式框架，将视觉特征( 称为 “原语”) 按通用型( 盘i i 颜色、形状和纹理) 和领域相关型( 如人脸识别等) 分类。 按领域的要求，不川的仃川“原语”可以被加到开放式结构中去。v i r a g ee n g i n e 主要有三方面的功能：图像分析、图像比较和图像管理。它将查询引擎作为一个 插件，既可应用到通用的图像查询中，也可对其进行扩展应用到特定的领域中。 该系统的特点是提供完善的用广丌发功能，例如，提供用于丌发用广| 界面的工乓 包：提出p r i m i t i v e 的概念，用于支持用户定义新的图像视觉特征；支持f i 种抽象 数据结构便于图像特征的捕述，并提供用户相关反馈检索机制。因此该系统比较 适合用来进行特定应用领域的图像数据库系统的二次开发。v i r a g e 己经和多种商业 数据库系统，如o r a c l e ，s y b a s e 等进行了集成。 此外，针对大容量图像库需要解决的快速索引问题，v i r a g o 先后提出了s s 树 和v a m s p l i t 树等索引结构实现对多维特征向量的索引。 1 3 本文的研究工作 本文通过对基于内容的图像检索技术的分析和研究，从聚类分析出发，并在 基于子空间的聚类的基础上建立一个改进的聚类树算法，c b b t r e e ，重点研究了该 索引结构在图像检索中的应用。并通过一个实现的基于内容的图像检索系统进行 实验，验证了该索引结构具有较好的检索效率，具有一定的应用价值。本文的研 究工作主要从以下几个方面展开： ( 1 ) 分析了基于内容的图像检索系统的特点，总结了基于内容的图像系统的 基本框图。并对图像检索的特征提取和表示从颜色、纹理、形状等方面进行了归 纳和总结，也对常用的相似度量方法进行了总结和分析。 ( 2 ) 对传统的聚类算法进行了总结和分析，并找到了一种适用于高维数据的 基于子空间的聚类的方法，为以后聚类树的聚类算法的选择提供了很好的参照。 ( 3 ) 对高维特征和高维索引结构的特点进行了总结，并对高维索引结构的典 型代表进行了分析，为提出的索引结构提供了基础。 ( 4 ) 提出了一种改进的聚类树索引结构。该结构通过对一种基于子空间的聚 类进行改进来得到一个层次的结构，通过两层索引结构来对该结构进行组织。 ( 5 ) 设计并实现了一个基于内容的图像检索实验系统。通过在该系统上进行 5 的大量实验验证算法的检索性能。实验表明，本文提出的c b b t r e e 索引结构能够 提高图像检索的效率，加快图像检索的速度。 1 4 论文的组织安排 本文共分为七章： 第一章绪论。首先介绍了课题的研究背景和意义，体现了研究图像检索技术 的必要性和重要性，然后分析了图像检索技术的发展过程、研究现状，重点讨论 了基于内容的图像检索方法，最后对本文的研究工作和内容的组织安排进行了阐 述。 第二章基于内容的图像检索关键技术。提出了基j ：内容的图像检索系统的通 用框架，详细分析了图像颜色、纹理和形状等特征的提取和表示，并对相似度量 方法做了分析和总结。 第三章聚类分析。阐述了聚类分析的概念，并对聚类方法分类进行了介绍， 总结和分析了五种聚类算法中有代表性的聚类方法的特点。接着针对高维数据的 特殊性，找到了一种适用于高维数据的子空间聚类，并对子空间聚类进行了分类 介绍。 第四章高维索引结构和小波分析。总结了高维数据的特点，并以此介绍了高 维索引结构应该具有的一些特点。接着介绍了k d b 树，r 树家族和v a - f i l e 三种 有代表性的高维索引结构。最后这一章还介绍了以后章节要用到的小波变换的基 本概念和多尺度分析的相关理论。 第五章c b b t r e e 索引结构的研究。本章是本文的核心章节。首先说明了 c b b t r e e 索引结构的设计原理，并详细说明了该算法的实现。 第六章基于内容的图像检索系统的设计与实现。设计了一套基于内容的图像 检索实验系统，主要是对c b b t r e e 索引结构的实现和对各种的检索算法的测试平 台。首先介绍了实验系统的结构，并对各个模块的功能进行了介绍，然后结合系 统的实现界面介绍了系统如何使用，最后给出了几个验证实验并对结果进行了分 析。 第七章结论。对全文进行了总结，并对进一步地研究做了展望。 6 2 基于内容的图像检索关键技术 基于内容的图像检索，简称c b i r ，建立在计算机视觉和图像理解理论基础之 上，综合了人工智能、数据挖掘、认知心理学、数据库等多学科的知识。图像内 容的描述不再依赖于人的手工标注，而是借助于从图像中自动提取的视觉特征， 检索过程也不再是关键字匹配，而足视觉特征问的相似匹配。 2 1 图像检索系统的通用框架 基于内容的图像检索系统可以看作一种信息服务系统，它介于用，f l t 和图像数 据集之问。用户通过该系统可以从图像数捌库| f i 捩取符合自己需要的图像。c b i r 的一般框架如图2 1 所示： 图2 - 1 基于内容的图像检索系统基本框图 f i g u r e2 - 1g e n e r a lf r a m ef o rc b i rs y s t e m 用户通过查询模块发出查询要求，系统的特征提取模块从要查询的图像中提 取特征，并将所提取的特征与特征数据库中存放的特征在匹配模块中进行相似性 度量，最后根据度量的结果在图像数据库中找到用户所要查找的目标图像。各模 7 块的简单介绍如下： 查询模块 图像检索的最终结果是交给用户的，因此在图像检索系统中，查询模块的用 户接口也起着重要的作用。它在用户和检索系统之间提供了一种交互式的检索机 制，为用户提供多样的查询手段以支持用户根据不同应用进行各种类型的检索。 所提供的常用检索机制有：范例图像查询、草图查询、目标图像的几何形状和图 像的背景颜色等等。 特征提取模块 从用户的查询要求中提取可以抽象表达图像内容的特征数据，并且让计算机 可以处理提取的特征。同时，在特征数据库建立时，会对图像数据库中的每一幅 图像进行特征的提取。c b i r 在不同的应用领域可以采用不同的特征或特征组合进 行检索。例如，在卫星系统中图像的纹理特征是十分晕要的，而在商标配准系统 中，商标的形状特征是最为重要的。在提取完图像的特征后，图像检索的主要任 务就变成度量图像特征间的相似度问题。 匹配模块 将检索图像的特征与特征数据库中的特征进行相似性度量，以确定它们之间 的相似程度。这个匹配的结构将用来提取目标图像。合理的相似性度量方法也是 执行有效图像检索的关键。常用的相似性度量方法主要包括：欧氏距离、城区距 离、二次式距离和直方图交等。不同的相似性度量方法有其内在的优点和缺点， 并非某一种度量方法对所有的图像检索系统均适用，它们也有各自的适用范围。 索引机制 多维索引模块是为了提高在大规模图像库中检索图像时系统的运行速度。它 是高性能图像检索系统中必不可少的部分。为了有效地完成图像检索，必须解决 图像特征的有效存储问题。对于图像的特征，它们之间可能没有内在的顺序，也 可能具有多重相关特征，因此在图像检索系统中选用合适的数据结构模型对于有 效的图像检索是十分必要的。目前常用的数据结构模型有：k d 树，r t r e e 系列以 及v a f i l e 等。在这些数据结构模型中，每一种数据结构模型都有其内在的优点和 缺点，因此在选择合适的数据结构模型时需要考虑所提取的图像特征的特性。这 个模块主要涉及计算几何、数据库管理和模式识别技术。 2 2 图像特征的提取和表示 图像特征的提取和表达是基于内容的图像检索技术的基础，特征提取在很大 程度上决定了c b i r 系统的成败。从广义上讲，图像的特征包括基于文本的特征( 如 关键字、注释等) 和视觉特征( 如颜色、纹理、形状和语义等) 两类。视觉特征 又可分为通用的视觉特征和领域相关的视觉特征。前者用于描述所有图像共有的 特征，与图像的具体类型和内容无关，主要包括颜色、纹理和形状等；后者则建 立在对所描述图像内容的某些先验知识( 或假设) 的基础上，与具体的应用领域 紧密相关，例如，人的指纹特征或面部特征等。本节只讨论通用的视觉特征。 对于某个特定的图像特征，通常又有多种不同的表达方法。由于人们主观认 识上的千差万别，对于某个特征并不存在一个所谓的最佳表达方式。事实上，罔 像特征的不同表达方式从各个不同的角度刻画了该特征的某些性质。 图像内容可以表示为一个层次模型，如图2 2 所示。第一层为原始数据层，即 图像的像素点；第二层为物理特征层，主要包括颜色、纹理和形状等。其中，颜 色、纹理特征强调物体表面的颜色、灰度变化，形状、结构特征强调物体的外形， 如弯曲、大小等；第三层为语义特征层，其特征具有相埘主观抽象的特点。目的 比较成熟的特征是颜色、纹理和一些低层的、简单的形状特征和物体间方位关系。 这些特征具有计算简单，性能稳定的特点。虽然人们偏爱语义查询，但是这种查 询方式的完全智能化目前还不可能实现。 第一层：原始数据层 ( 图像的原始像素点) 上 第二层：物理特征层 ( 图像的底层特征，如颜色、纹理和形状) 土 第三层：语义特征层 ( 人们对图像内容的概念级反映) 图2 2 图像内容的层次模型 f i g u r e2 - 2h i e r a r c h ym o d u l eo fi m a g ec o n t e n t 本文主要讨论基于内容的图像检索系统的第二层特征层。 2 2 1颜色特征 颜色是描述图像内容的最显著的特征【1 6 1 。相对于其他特征而言，颜色特征较 9 稳定，对于平移、尺度、旋转的变化不敏感，表现出较强的鲁棒性；又由于颜色 特征的提取与计算简单方便，因此，基于颜色特征的检索成为基于内容的图像检 索系统中最常用的方法。 图像颜色特征的表达涉及两个问题。首先，颜色的特征表达依赖于所用的颜 色空间。并非所有的颜色空间都与人的视觉感知一致。研究表明，人眼对j ：颜色 的感知是三维的，找到符合人眼视觉的模型是利用颜色特征进行图像枪索的火键； 其次，需要采用一定的量化方法将颜色特征表达为向量的形式。4 爿智图像颜色特 征表示为向量形式后，才能进行相似度比较。 常用的颜色空间有r g b 颜色空间和h s v 颜色空间： r g b 颜色空间 根据r g b 三基色原理，由r g b 三基色可构成一类颜色空问，各种颜色的光 均可以通过红、绿、蓝三种基色混合而成。这种由r g b 三基色构成的颜色空f h j ， 称为r g b 模型。r g b 颜色空间是图像处理中最基础、最常用的颜色空问，因为现 有的图像采集设备最初采集到的颜色信息是r g b 值，颜色显示设备最终使用的也 是r g b 值，图像处理中使用的其它颜色空间也是从r g b 颜色空问转换来的。 h s v h s v 颜色空间具有视觉一致性，h u e 表示色调、s a t u r a t i o n 表示颜色的饱和度 和v a l u e s 表示颜色的亮度。色调是与混合光谱中主要光波长相联系的，彩色的色 调反映了该彩色最接近的光谱波长。饱和度与一定色调的纯度有关，纯光谱色是 完全饱和的，随着白光的加入饱和度逐渐减少。亮度与物体的反射率呈f 比，如 果无彩色就只有亮度1 个维量的变化。对彩色来说，颜色中掺入白色越多就越明 亮，掺入黑色越多亮度就越小。 h s v 颜色空间反映了人观察彩色的方式，同时也有利于图像处n t l 门。h s v 颜 色空间有两个特点：一是亮度分量与图像的彩色信息无关；二是色调和饱和度分 量与人感受颜色的方式是紧密相连的。这些特点使得h s v 颜色空间非常适合与借 助人的视觉系统来感知彩色特性的图像处理算法【1 8 】。 颜色特征提取方法有很多种，主要包括了颜色直方图、颜色矩、颜色聚合矢 量和颜色相关图等。 颜色直方图 颜色直方图是最常用的颜色特征提取方法之一。它具有以下明显的优点：能 简单描述一幅图像中不同色彩在整幅图像中所占的比例；特别适用于描述那些难 以自动分割的图像和不需要考虑物体空间位置的图像；提取和相似度计算简便。 但其缺点在于丢失了颜色的空间分布信息，可能会出现虽然颜色直方图相似但是 图像内容很不同的情况。图像的颜色直方图可表示如下： 1 0 吃2 意i _ 磊酽怃- c j 比c ( 2 - 1 ) 其中m x n 表示图像的尺寸，乃表示像素点俐处的颜色值，c 表示图像的颜 色集。 计算颜色直方图需要将颜色空间划分成若干个小的颜色区间，每个区间成为 直方图的一个柄，这个过程称为颜色量化。然后，通过计算颜色落在每个小区问 内的像素数量可以得到颜色直方图。横坐标表示颜色色彩归一后的值，纵坐标表 示每个小的颜色区间中所对应的图像像素的总和【1 6 】。 颜色矩 s t r i c k e r 和o r e n g o 提出了颜色矩的方法【1 9 】。颜色矩是以数学方法为基础的， 它通过计算矩来描述颜色的分布。由于多数信息只与低阶矩有关，因此实际运用 中主要对每种颜色分量的一阶、二阶和三阶矩进行统计。颜色矩通常直接在r g b 空间计算。一阶( 均值) ，二阶( 方差) 和三阶( 斜度) 等颜色矩被证明可以很有 效地表示图像中的颜色分布。这三个颜色矩的数学定义如下： 1 i t ，= 厶 ( 2 - 2 ) l 、j 2 i l 吁专笔怃叫) 2 ( 2 - 3 ) _ = 专差一，) 3 ( 2 - 4 ) 其中力表示像素的颜色值为i 的概率，为图像像素点的数目。 颜色矩已经成功地应用于许多基于内容图像检索系统( 如q b i c )，特别是 对于图像中只包括一个目标的时候非常有效。由于采用9 个数值( 三个颜色坐标 轴，每个坐标轴包括三个颜色矩) ，所以相对于其他颜色特征而苦，采用颜色矩表 示颜色特征是一个非常紧凑的表示方法。然而颜色矩由于仅仅使用了少数几个矩， 因此可能出现两幅完全不同的图像有同样的矩，从而导致过多的假警。 颜色聚合矢量 颜色聚合矢量【2 0 】是p a s s 和z a b i t h 等人提出的另一种颜色特征提取与匹配方 法，旨在克服颜色直方图和颜色矩无法表达图像色彩的空间位置的缺陷。该方法 是颜色直方图的一种演变，其核心思想是将属于直方图每一个柄的像素分成两部 分，如果该柄内的某些像素所占据的连续区域的面积大于给定的阈值，则该区域 内的像素作为聚合像素，否则作为非聚合像素。假设嘶和历分别为直方图的第i 个区间中聚合像素和非聚合像素的数目，图像的颜色聚合向量可表示为， ( 2 - 5 ) 而 就是该图像的颜色直方图。由于包含了颜色 分布的空间信息，对需要比较物体空间位置的图像，颜色聚合向量能比颜色直方 图达到更好的检索效果。 颜色相关图 颜色相关图是描述图像颜色空间分布的另一种表达方式f 2 。颜色相关图利用 图像像素间的颜色关系，不但刻酾了桀+ f 颖包的像素占整个图像的比例，还反映 了不同颜色对之间的空间相关性。 对于任意的图像，假设如，表j 图像l - 颜包为c ( o 的所有像素的集合，则颜色 相关图可以表达为： 吒哆= 弓 p 2 i 。( ) i | p l p 2 i = k 】 ( 2 6 ) p j e l , ，) - p 2 e i 式中，缸，2 ，n ，k 0 , 2 ，d ，i p l - p ：i 表示像素p l 和p 2 之间的距离。此 时颜色直方图可以看作是一张用颜色对 索引的表，其中 的第k 个分量表 示图像中颜色为c 何和c 倒且距离小于k 的像素对出现的概率。如果考虑任何颜色 间的相关性，颜色相关图就会变得非常复杂和庞大。一种简化的方法是颜色自相 关图，它仅仅考虑图像空间中具有相同颜色像素间的空间关系。 2 2 2纹理特征 纹理特征是一种不依赖于颜色或亮度、反映图像同质现象的视觉特征【2 2 1 ，可 用来对图像中的空间信息进行一定的定量描述。纹理特征是一种全局特征，但它 反映的只是物体表面的特性，无法表达物体的本质，因此单单利用纹理特征是无 法描述图像内容的。 此外和颜色特征不同的是，纹理特征不是一种基于像素点的特征而是需要在 一个包含多个像素点的区域内进行统计计算，这样在相似度量的时候，不会因为 局部的些许偏差而影响检索效果。纹理特征作为一种统计特征，具有旋转不变形， 而且由于是基于一定区域的，所以对噪声有较强的抵抗能力。常用的纹理描述方 法有：模型法、统计法、结构法和频谱法四种。 ( 1 ) 模型法 模型法以图像的构造模型为基础，主要利用一些成熟的图像模型来描述纹理 特征。如基于统计学的马可夫随机场( m r f ) 、子回归模型，以及在此基础上产生 的多尺度子回归模型( m r s a ) 2 3 】等。最近2 0 多年来，应用随机场模型表达图像 纹理特征方面做了大量研究。其中，利用m r f 模型法来描述纹理特征取得了很大 的成功。这是因为，在理论上，m r f 模型可以产生任何模式的纹理。在实际应用 中，m r f 模型对于描述在微观结构上一致的图像纹理具有较好的效果，诸如草地、 1 2 沙地或动物的羽毛等，但对点状、条状或大尺度结构的纹理，则需要额外的辅助 方法加以描述。m r s a 区分不同纹理模式的能力较强，但同时计算开销也较大。 上述模型的共同特点是利用少量的参数来表示纹理。 ( 2 ) 统计法 统计法主要通过图像中灰度级分自i 的随机属性来描述纹理特征。最简单的统 计法是借助于灰度直方图的矩，仉这种方法没有利用像素相对位置的空间信息。 为了利用这些信息，h a r a l i c k 等人挺了川共生矩阵来表示纹理特征【2 4 】，他们对纹 理特征提取的研究是在模式识别的背景下展丌的。该方法首先建立一个基于像素 之间方向性和距离的共生矩阵，然后从矩阵中提取有意义的统计量作为纹理特征， 是从数学的角度研究了图像纹理中狄度级的空间依赖关系。 随着人们对纹理视觉感知的心理学研究，t a m u r a 等人从另外一个角度提h 两 个纹理特征的计算方法，其中包括机糙度、对比度、方向性、成线性、规整度和 粗略度【2 5 1 。t a m u r a 纹理特征已经被广泛的应用在图像检索系统中，如f i f 面提到的 q b i c 检索系统。 ( 3 ) 结构法 结构法分析纹理的基本思想是假定复杂的纹理可以由若干简单的纹理基元以 一定的、有规律的形式重复排列组合而成，特征提取就变为确定这些基元并定量 的分析它们的排列规则。由于纹理基元描述了局部纹理特征，因此对整幅图像中 不同纹理基元的分布统计可获得图像的全面纹理信息。比较有影响的算法有两种： v o r o n i o 棋盘格特征法和结构法。因为实际的纹理大都是无规则的，因此结构法受 到很大的限制。 ( 4 ) 频谱法 频谱法主要借助于频率特性来描述纹理特征。常用的频谱法主要包括傅立叶 功率谱法【8 1 、g a b o r 变换削和树式小波变换【2 7 1 等。 2 2 3形状特征 在计算机视觉中，相对于颜色或纹理等底层特征而言，形状特征属于图像的 中间层特征。形状常与目标对象联系在一起，有一定的语义含义。形状特征作为 刻画图像中物体和区域特点的重要特征，是描述高层视觉特征( 如目标、对象等) 的重要手段。要把图像的底层特征与高层特征有机地结合起来，必须有好的形状 特征描述与提取算法的支持。形状特征的有效表达必须以对图像中物体或区域的 分割为基础。但是，现有的形状描述方法还不成熟，至今还没有找到与人的视觉 特性一致的有关形状的确切数学描述，难以做到准确而稳健的自动图像分割和形 1 3 状特征提取与匹配，使得图像检索中的形状特征往往只能在某些特殊的应用场合 中使用，或者需要借助某些领域知识来提高形状识别的精度，如人的脸谱、虹膜 和指纹等生物特征识别。此外，在主观上，由于人们对物体形状的变换、旋转和 缩放不太敏感，合适的形状特征提取与匹配必须满足对变换、旋转和缩放无关， 这给形状特征的相似性度量带来了难度，增加了算法的复杂性。因而，对于通用 图像检索系统而言，除了用于对商标一类形状较简单的图案检索以外，利用形状 特征进行形状复杂的图像检索仍然存在。一定的困难，应用上受到一定限制，至今 未能发挥出应有的潜力。 形状表示可分为基于边界和基于区域两大类型，它们中最具代表性的方法分 别是傅立叶描述符【2 8 】和形状不变矩法【2 9 1 。傅罩叶形状描述符的基本思想足用物体 边界的傅里叶变换作为形状描述，利用i 夏域边界的封闭性和周期性，将二维问题 转化为一维问题。形状不变矩法的t 要思路足通过图像分割技术提取图像中感兴 趣的物体，依靠区域内像素的颜色分布信息提取图像特征，适合于区域能够较