（计算机应用技术专业论文）基于聚类的分层索引结构在图像检索中的应用研究.pdf

中文摘要 摘要：伴随着信息技术特别是i n t e 釉e t 技术的不断发展，多媒体信息不断涌现，图 像数据飞速增长。如何快速、有效地检索到所需要的图片变得迫不及待。传统的 基于文本注释的图像检索已经不能适应检索的需要，这使得基于内容的图像检索 技术成为当前的研究热点。 本文对基于内容的图像检索技术的发展、关键技术以及效果评价进行了概要介 绍。图像内容特征提取是基于内容的图像检索技术的基础，本文分别从颜色特征、 形状特征、纹理特征以及图像空间关系进行了描述。 传统的基于内容的图像检索技术使用的是顺序检索，对于大容量、高维数的图 像数据来说，这种检索方法在效率上显然已经不能满足需要。对图像数据库进行 必要的预处理并且建立索引以提高检索效率显得愈发重要。本文引入了一种无参 数的、高效的、基于予空间技术的聚类算法用于图像数据的预处理。同时，对该 算法进行了改进，将小波的多尺度分析引入样本分布曲线处理，建立多层次的聚 类。在多层次聚类的基础上，建立起分层索引结构，并且提出利用数据库系统来 保存这种索引结构。 在以上提出的理论基础之上，设计了一个基于内容的图像检索实验平台，通过 实验数据，从检索效率和检索结果进行比较，有力地证明了作者提出的基于聚类 的分层索引结构在基于内容的图像检索中的高效、实用。 关键词：基于内容图像检索；聚类分析；分层索引 a b s t r a c t a b s t r a c t 刖g 谢t hm ed e v e l o p 涨m to fi n 】f o l _ m a t i o nt e c h l o g y ，e s p e c i a l l yt h e d e v e l o p m e n to fb t e m 烈t c c l l n o l o g y ，m m 咖e d i ai n f o 珊a t i o i l i n c l u d i n gi m a g ed a t a ，i s f a p i dg r 0 1 ) v i n g nb c c o m e sm o 旭a n dm o 坞n c c e s s a r yt 0 糟t r i e v i i l gi m a g e sf 如t e r 缸d e 街c i 衄廿y a s 乜a d m 伽i a lm e t h o d ，n o t e s b 豁e di m a g er e 仃i e v a lh 弱b e e n 硼a b l et om e e t 血e n d s t h 哦f 0 峨也e c o n t e n t - b a s e d i m a g e 蜘a l ( c b 哟h a s b e e nd r a w 吨m o f c 柚dm o mr e s e a r c ha t 咖m o ni i lt l l e 托c 既l ty e a 璐 倘sp 印e rp f e s 啪m cd c v e l o p m c n to fc b 取t e c h n o l o 鼢m ek c yt c c h n o l o g yo f c b 取a n de v a l m 面no fc b r h a g ef 毫抓聆e x 仃a c 在o ni s 吐呛b 勰i so fc b i a 1 1 dt l l i s p a p 盯d e s c r i b e st h ef c a t i l 埔o fi m a g e s 敝噬nt h cc o l o r ，s h a p e ，t c x t e 锄dr e l a l i o l l s l l i p b e 帆n s p e s 1 k 仃a d i t i o n a lc b 取i s d i i l a im 仃i “a 1 h o w e v e r ，f o rl a r g e - v o l 啪ea n d h i g h - d i m e n s i o ni m a g ed a 饥t h i s 托雠w a lm e 也o dd b v i o u s l yh a sb e c nu m i b l et om e e t e 伍c i e n c y ni sm o 把i m p c 瞳恤tt h a tt h ei m a g ed 毒岫l b a s h c n l l db ep r e p r o c e s d 觚d e s t a _ b l i s hi n d e xt oi m p r o v e 聆t r i 酬e 佑c i e n c y a s ，t h i sp a p 盯细d u c e sa n c 心p a m m e 缸c ，e 伍c i 眦，s i | _ b s p a c e - b 跚dc l l l s t c r i n ga l g o r i t h m f b ri m a g ed a 协b a s c p r e p r o c e s s i n g m e 锄w h i l e ，t h e 越i i t - 0 ri n i p r o v e st h ea l g o r 油m ，柚du st h em u m - s c a l e w a v e l c ta n a l y s i st e c h n o l o g yt 0p f o c e s st h ed i s 缸b i m o nc u r v eo fs a m p l e s ，a n dc r c a 土e sa m 1 1 l t i - l a y e rc l l l s t 既b 嬲e do nt h em u m l a y e fc l u s t e r ，i t c a ne s t a b l i s hl l i e r a r c h i c a l i i l 出嘶n gs 旬f i l c t i l 坞m o r e a v e f ，t h ea 删h o rp r o p o s e st o l l s et h ed a t a b 船es y s t e mt 0 p r v et h i si n d e x 蛐m l 1 1 艟t h e o r c t i c a lb 酗i so ft h ea _ b o v e ，t l 尬a 删rd e s i g 衄ac b 玎re x p c r i m e n t a l p l 加c 锄p 删b y 砸c v a le 伍c i e n c y 她dr e l d 钾a l 坨s u n ，“i sc o n v i i l c i n g l yp r o v e d t h a tl l i e 翔r c h i c a li n d e xs t n j c t l l 托b 蠲e do nc i u g t e r i i l gi se 舔c i e ma n da p p l i c a b l ei nc b 吸 k e y w o r d s ：c t e n t b 勰c di m a g er e 仃i e v a l ；c l t l s t 盯a n a j y s i s ；h i e r a r c h i c a li n d e x 致谢 本论文的工作是在我的导师许宏丽副教授的悉心指导下完成的，许老师严谨 的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心地感谢三年来 许老师对我的关心和指导。 本论文从选题、撰写、实验分析以及最终的定稿，倾注了许老师的大量的心 血。在我攻读硕士学位期间，她不断给予我为人和治学的指导，对我严格要求、 悉心关怀，使我克服了一个个的困难。她渊博的知识、严谨的治学精神和高尚的 人品将使我受益终生。 在实验室工作及撰写论文期间，我的很多同学对我论文的研究工作给予了热 情帮助，在此向他们表达我的感激之情。 另外还要感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学 业。 北京交通大学硕士学位论文引言 l 引言 1 1研究背景及国内外研究现状 近年来，随着大容量存储器以及数字化图像采集设备，如扫描仪、数码相机 的发展及普及，以及i n t e r m t 技术的蓬勃发展，图像数据大量涌现，出现了按指数 级增长的趋势。图像数据已经广泛用于h i t c n 蝣t 和企事业信息系统中，用户不仅要 存取常规的字符数据，而且越来越多的商业活动、事务交易和信息表现将包括图 像数据。在浩如烟渺的图像数据库中，如何有效地按照其特性去检索这些数据便 成为了多媒体技术研究中的热点问题。 在2 0 世纪7 0 年代人们利用常规关系数据库管理系统来管理图像数据，对图 像数据人工输入各种属性，建立图像数据的元数据库来支持查询。但是，随着2 0 世纪9 0 年代多媒体技术的飞速发展，可获取的图像和其他多媒体数据越来越多， 数据库容量不断增大，而这种用人工输入属性和注释的方法就暴露出了它的缺点。 首先，人工注释需要大量的人力，尤其是对于大型的多媒体信息库，如w e b 网络 资源、数字图书馆等。在这样的信息环境中，每天都有大量的新资料出现，需要 及时把这些资料归档。没有计算机的自动和辅助处理，资料的更新周期就不能满 足用户的需要。其次，人工注释难以解决蕴藏在图像数据中丰富的内容以及内容 感知描述的主观性。人们常说，一幅图胜过千言万语，图片上的很多内容很难用 文字来描述清楚。最后，就是对于实时广播流媒体的处理，手工处理是完全不可 行的，必须用计算机进行实时的内容分析。 解决上述问题的一个理想方案就是由计算机自动理解图像信息的内容，并绘 图像信息加上客观而且全面的概念性标注。但这是一个难题，其中涉及众多领域 的知识。特别是，就目前技术而言，当不限定图像的内容范围时，要做到任意图 像的自动理解还远远不是一件容易的事情。因此，需要从一个中间层次来研究图 像内容的表示以及检索问题，即基于内容的多媒体信息检索技术。 基于内容的检索是指根据媒体和媒体对象的内容及上下文联系在大规模多媒 体数据库中进行检索，它的研究目标是提供在没有人类参与的情况下能自动识别 或理解图像重要特征的算法。在这种方法中，首先对媒体信息进行分割使其成为 单独的可供检索的媒体对象，再对每个媒体对象采用特征提取算法提取相应的特 征。媒体对象特征的集合就构成了其内容描述。在检索时，根据检索要求，查询 并返回媒体库中内容描述最满足要求的一组媒体对象。 北京交通大学硕士学位论文引言 基于内容的图像检索( c o n t e n tb a $ e dh a g er e t r i e v a l ，简称c b i r ) ，是一门涉 及面很广的交叉学科，需要利用图像处理、模式识别、计算机视觉、图像理解等 领域的知识作为基础，还需从认知科学、人工智能、数据库管理系统、人机交互、 信息检索等领域引入新的媒体数据表示和数据模型，从而设计出可靠、有效的检 索算法、系统结构以及友好的人机界面。 目前，基于内容的图像检索，主要工作集中在识别和描述图像的颜色、纹理、 形状、空间关系上，以及图像特征匹配的相似度度量上。当图像特征提取和相似 度度量方法确定以后，检索就变成了在图像数据库中查找与给定的图像最相似的 图像的过程。因为特征向量的相似性比较的计算量非常大，顺序扫描检索的效率 非常低，为了提高检索效率，可以对图像数据库进行聚类预处理，然后在层次聚 类的基础上建立索引。这也是本文的出发点。c b 取中建立索引的主要目的是减少 检索的时间和空间开销。但是与其他类型的索引相比，有三个主要特点：首先，图 像特征都是高维向量，所以要能处理高维空间向量；其次，由于数据库的图像经 常发生变化，当新插入或者删除对象时，数据库索引应该可以动态地变化，而不 应当重新建立；最后，检索的类型、策略和标准有根本的区别。 最早的图像检索在2 0 多年前就已经提出【1 】，图像检索技术从提出到现在引起 了广泛的关注和兴趣，已经取得了非常大的成就。新的技术方法曾出不穷，检索 技术已经得到了许多非常有价值的应用，为人类日常生活带来了方便同时也带来 的巨大的社会价值。 胁n c o 在2 0 0 0 年的报告【2 l 中，介绍了3 9 种基于内容的图像检索系统。现在， 国内外已经出现了很多关于图像检索的原型系统。最为著名的是m m 的q b i c ( q u e r yb yi n l a g ec o i l t e n t ) 系统。q b i c 是第一个商品化的基于内容的图像检索系 统，它的系统框架和技术对后来的图像检索系统具有深远的影响，q b i c 支持基于 示例图像、用户构造略图、颜色、纹理等特征的查询。在它的新系统中，则是将 基于文本的关键字查询与基于内容的相似性查询结合在一起。 m g e 公司开发的、，i m g e 系统，与q b i c 相似，支持基于颜色、纹理的可视 化查询，但瑚喀e 比q b i c 更进一步，支持以上原子查询的任意组合。 除此之外，在国外还出现了很多优秀的原型系统，如哥伦比亚大学开发的 s u a l s e e k 系统、m r r 媒体实验室开发的p h o t i 出0 0 k 、u cb e r k e l c y 开发的c l l a b o t f 3 】 系统等等。 国内清华大学的徐寅、章毓晋设计和开发了一个由抽取特征来检索图像的算 法测试平台( t e s tb e df o rr e t r i e v i n gi n l a g ew i me x 吮t e df e a t i l r e ) ，简称t b r i e f 该平台是一个针对算法开发的抽取特征检索图像的算法测试平台，可以集成现有 的多个不同算法，并且便于管理，同时它还提供了诸如综合检索、渐进检索等功 2 北京交通大学硕士学位论文引言 能，可用于算法研究、性能比较等。 浙江大学计算机系完成了两个原型系统：基于图像颜色的检索系统 n 耐g a t o r ，以及基于图像形状的检索系统p h a t 0e n g m e 。前者采用颜色聚类算法， 提出了一种有效的支持颜色近似匹配的方法，后者提出了基于内角的表征方法和 狭长度计算，以及一种快速的匹配算法。在上述系统基础上，又开发了一个基于 内容的多媒体检索系统w 曲s c o p e c b r ，其总体设计思想是允许用户找到包含 特定颜色、纹理和形状的图像，它支持基于关键字、全局颜色、全局纹理、对象 形状、颜色布局、纹理布局等的查询。 目前很多著名的搜索引擎都有了自己的图像检索引擎，如： 谷歌( h t t p ：饷嗍g o o g l e c o m i m g h p ? l l l = 吐c n ) 通过关键字做检索，同时在检 索范围内可以指定图像的大小、图像的格式、图像的色调等。 雅虎( 1 1 t i p ：g a l l 哪y a j l o o c o m ) 支持基于关键字的检索，同时将图像分门别类区 分成了各种类别，用户可以按类别浏览。 百度 t i p ：i m a g e b a i d u c 锄) 通过关键字来检索图片，同时可以选定图像的大 小和格式，例如用户可提出检索要求：检索关键字为“水果”，大小为“壁纸 8 0 0 + 6 0 0 ”，格式为“j 鸺”。 1 2 本文主要研究工作 本文主要研究了基于内容的图像检索技术，侧重于论述聚类分析技术以及基于 聚类的分层索引结构在图像特征空间检索中的应用，并实现了一个图像检索实验 平台，对作者提出的基于聚类的分层索引结构进行了实验验证，有力地证明了该 算法在图像检索中较其他算法在检索效率上的优越性。 ( 1 ) 对基于内容的图像检索进行了概要的介绍。并且分析了基于内容的图像 检索及其特点和核心问题。对于图像内容的描述与特征提取，本文从颜色、纹理、 形状等几方面对其进行了归纳和总结。对于颜色，介绍了几种符合人类视觉感知 的颜色空间，给出了几种常用的且较好的颜色特征提取方法及其优缺点；对于纹 理，详细讨论了三种纹理特征；对于形状，介绍了几种常用形状的描述。 ( 2 ) 分析和比较了一些多媒体数据的相似性搜索的算法。通过分析与比较， 找出各算法的优缺点，为提出新的图像检索框架和新的算法提供理论基础。还介 绍了本论文使用到的小波分析、聚类技术以及索引结构的相关理论。 ( 3 ) 提出了基于密度和网格聚类之上的按层次索引的图像检索系统框架。现 在大部分的检索系统过程只有两个步骤，即特征提取( f e a n 鹏e x a c t i o n ) 和相似度 度量( s i m i l a r i t ym e 船w e m e n t ) 。在本文中，增加了对图像数据库中图像的特征进行 北京交通大学硕士学位论文 引言 聚类( c 1 u s t e 渤g ) 的处理步骤，即对图像数据库中的图像进行特征提取后，对它们的 特征进行分层次聚类，这样充分利用了图像数据库内图像之间的相似性的信息， 从而将被检索的大量图像根据其相似程度形成一个个的簇。同时在所聚类的过程 中，按不同的精度对类的密度分布曲线进行小波光滑化，目的是形成多个层次的 聚类，并且提出建立层次索引结构。这样的处理过程使得样本图像可以根据索引 快速地检索到相匹配的簇，然后样本图像只需要与该相似的簇内的图像进行特征 比较，就可以找到相似的图像，从而在保证了检索精度的同时，大大地加快检索 的速度。在基于聚类的图像框架中，对图像数据库中的图像的聚类过程以及建立 索引作为预处理的过程只是一次完成，并且将其存入数据库，在对图像的聚类完 成后，可以在以后的每次查询中都使用这些聚类，这也极大地提高了查询的效率。 ( 4 ) 在聚类算法中，本文引进了一个基于密度和网格的聚类算法，不需要用 户指定参数，解决了现有大部分聚类算法需要用户指定参数的缺陷。同时，作者 对该算法进行了改进，将多尺度小波变换技术引入聚类过程，可以根据需要，对 密度分布进行相应得光滑处理，调整了曲线的平滑度，从而按照不同的颗粒度进 行聚类处理。在多尺度层次聚类的基础上，建立了一个全新的高效实用的层次索 引结构，并且提出利用数据库系统来存储这个索引结构，以提高图像检索的速率 和质量。 ( 5 ) 设计并实现了一套基于内容的图像检索实验系统，是一个实验性的框架 系统。利用该系统进行实验验证，测试作者提出的基于聚类的层次索引结构在图 像检索中的高效率。实验证明，本文提出的基于聚类分析的层次索引结构算法是 高效可行的。 1 3 论文的组织结构 本文的行文和组织结构如下： 第一章，引言。 介绍了本文的研究背景、研究的出发点、国内外的研究现状和研究成果，以及 本文的主要研究工作。 第二章，基于内容图像检索概述。 概要介绍了图像检索的概念，比较了传统的图像检索和基于内容的图像检索的 区别，重点介绍了基于内容的图像检索及其特点，以及基于内容图像检索的核心 问题。最后介绍了图像检索效果的评价。 第三章，图像检索的特征描述。 主要介绍图像内容的视觉特征描述，并从颜色、纹理、形状等方面介绍了图像 4 北京交通大学硕士学位论文引言 可视信息的特征描述和提取方法以及特征归一化方法，并介绍了图像特征相似度 度量常用的几种方法。 第四章，基于内容图像检索的相关理论和研究。 这章是本文的重点。介绍了本文所要重点分析的多尺度小波分析理论以及聚类 技术和索引结构的相关理论基础。并介绍了目前主流的几种高维向量的聚类技术 和索引技术，分析了它们之间的优劣。同时给出了一种经过改进了的高维向量的 聚类算法，并且与主流的聚类算法进行了比较。同时介绍了一种作者提出并实现 的基于聚类分析的分层索引结构。 第五章，基于层次索引结构的图像检索系统的设计与实现。 介绍了作者实现的一个基于聚类技术和层次索引结构的图像检索系统，并分析 该系统上的一些实验结果。 第六章，结论与展望。 对本文的研究工作进行了总结，得出结论。并对未来的基于内容图像检索领域 作出前景展望。 北京交通大学硕士学位论文基于内容图像检索概述 2 基于内容图像检索概述 2 1 图像检索概述 传统的图像管理以文件的形式进行，当用户查询一幅图像，要通过打开文件 才能进行浏览，找到目标对象。随着应用领域的扩大，图像数据处理量剧增，并 面临数据共享的问题，文件系统已难满足实际的需求，需要用数据库系统来支撑。 由于图像数据的信息含量丰富、结构关系复杂，如何利用数据库来描述图像数据， 并提供有效的查询手段，是图像数据管理面临的新问题。 图像检索的研究基本上经历了基于关键词注释的文本标注的图像检索阶段和 基于内容的图像检索阶段。 2 1 1 基于关键字文本标注的图像检索 早在二十世纪七十年代末，基于文本的图像检索技术就已经产生，这种检索方 案常使用文字标志符，例如具体到对图像的查询是借助对图像的编号，即标签来 进行的。为实现检索，先给图像加上一个对其描述的文字或数字标签，然后在索 引时对标签进行检索。这样对图像的查询就变成了基于描述标签的查询。后来又 出现了用关键词伥e y w o r d ) 或描述性文本( 表示图像的客观属性，如图像的作者、标 题、创作时间等) 来表示一幅图像，然后实现基于关键字的索引。 采用这一技术，图像检索通过匹配查询时给出的文本信息和图像数据库中存储 的描述关键字来实现，它要求用户对文本特征的描述具有一定的准确性和规范性。 采用基于关键词注释的检索方法，一个明显的优点就是可以表达抽象概念，但 这种方法也具有如下缺点： ( 1 ) 文本描述难于充分表达图像的丰富内容。文本描述是一种定性的描述， 描述能力有限，而图像中往往含有大量需要定量描述的信息。而且，许多图像对 象的特征难于用文本描述来表示，如散布纹理和不规则形状等。 ( 2 ) 文本描述具有一定的主观性。对于一幅图像来说，由于其内容的丰富性 以及不同人理解和感兴趣方面的不同，导致内容描述的建立具有很大的主观性( 如 不同人对颜色的感知就不尽相同) 。这样，采用这种检索方法就会带来一定的歧义。 ( 3 ) 处理文本描述涉及到自然语言的理解问题。采用文本描述的检索方法， 本质就在于计算检索请求与图像文本描述之间的相似度，这就涉及到目前尚未解 决的自然语言理解问题。目前实现的系统中，通过采用同义词词典( t h e s a u m s ) 来使 6 北京交通大学硕士学位论文基于内容图像检索概述 问题得到简化，但同时也使检索的表达能力大大受到了的限制。 ( 4 ) 手工输入文本描述效率低，难以满足海量图像数据库的要求。采用这种 检索方法，图像内容的文本描述一般需要手工输入，效率低，因此不能满足海量 图像数据库的检索要求。 2 1 2 基于内容的图像检索 人工注释带来的最大问题就是不能实现图像库的自动检索，以及不能保持一 种客观性，并且图像的视觉特征难以用关键字来描述，使得这种方法往往不能满 足人们的需要。因此人们开始试图通过自动提取图像内部某种固定的信息作为索 引标签以供检索，这就是基于内容的图像检索的初衷。基于内容的检索不需要用 户的参与，而利用图像自身的特征，如颜色、纹理、形状等特征来进行检索，具 有较强的客观性。通常，可以抽取图像库中所有文件的特征，用户检索的过程一 般是提供一个样例图像，系统抽取该样例图像的特征，然后同数据库中所有的图 像特征进行比较，并将与样例特征相似的图像返回给用户。 2 2 基于内容的图像检索及其特点 基于内容的图像检索( c o n t e n tb a di m a g cr e t r i e 、，a l ，简称c b r ) ，是指直接 根据描述图像内容的各种特征进行检索，它能从数据库中查找出具有给定特征或 含有特定内容的图像，它区别于传统的基于关键字的检索手段，融合了图像理解、 模式识别等技术，具有如下特点： ( 1 ) 直接从图像内容中提取信息线索。基于内容的图像检索，突破了传统的 基于表达的检索局限，直接对图像进行分析和抽取特征，利用这些描述图像内容 的特征来建立索引。 ( 2 ) 基于内容的图像检索实质上是一种近似匹配的技术。在数据库中，需使 用模式识别的方法对图像库中的图像按不同索引特征分类。在检索的过程中，它 采用某种相似性度量，对图像库中的图像进行匹配，以获得查询结果。这一点与 常规数据检索的精确匹配方法有明显不同。 ( 3 ) 特征提取和索引建立可由计算机自动实现，避免了人工描述的主观性， 也大大减少了工作量。 2 3 基于内容图像检索的关键技术 7 北京交通大学硕士学位论文基于内容图像检索概述 基于内容图像检索主要依赖于以下几个关键技术： ( 1 ) 图像数据的描述模型，即图像内容的表示问题 它是指采用图像理解技术实现图像内容描述的方法。选择合适的图像数据模 型表示图像内容特征是进行基于内容检索的基础。图像存在多种视觉特征，如颜 色、形状、纹理、空间特征等。图像的特征集合构成了它的内容描述集。图像特 征的提取是基于内容图像检索技术中的一个必不可少的关键步骤。一个好的图像 特征应具有以下特点：特征对用户而言具有直观的含义，换句话说，特征表达 的信息和用户的需求之间存在清晰联系。用户易于指定查询，系统也可以进行 有效的检索。特征能够明确地区分相关图像和非相关图像。图像的颜色、形状、 纹理和轮廓等特征适用于各种图像内容的描述，在图像数据描述模型中具有较好 的通用性。考虑到图像数目的急剧增长，图像特征的提取最好是自动完成，也 可以在少量人工协助的情况下通过半自动的方式完成。 ( 2 ) 图像特征的匹配问题 也称为图像的相似性度量。图像经过特征提取之后，就可以抛开图像本身， 而以所获得的特征作为图像内容的表示。因此，研究图像间的相似性事实上是在 研究特征间的相似性。图像特征的匹配问题就是研究如何获得计算特征间的相似 性的有效方式。通常，特征间的相似性是通过距离来刻画的，其计算策略也可能 随外界的反馈信息而进行动态地调整。由于特征匹配计算往往需要快速的联机分 析反应能力，因此，其计算效率也是一个重要的研究内容。通常将欧氏几何距离 和集合理论作为图像的相似性度量。 ( 3 ) 特征库的预处理以及建立索引结构 一般情况下，描述图像内容的特征集合可看作是高维空间中的向量，这样， 基于内容检索( 寻找与指定特征最相近的一组对象) 就转化为高维空间点集的最近 邻搜索问题。由于c b i r 系统中往往含有海量图像，单纯的线性搜索方法难以满足 实时检索的需要，有必要对特征库进行预处理，如进行聚类处理，并且建立索引， 使用相似索引技术来建立特征索引机构，以支持对中、高维特征向量的相似性的 查询。在特征匹配时，c b 瓜系统将计算出来的向量距离按由小到大的排序来决定 返回的结果。结果的返回方式大致分成两类：k 个最近邻居查询和球形范围查询， 前者返回与查询向量的距离最小的k 个特征向量所对应的图像：后者则返回与查 询向量的距离小于一个阈值的所有图像。一般常见的特征索引结构有r 树以及r 树族索引结构。本文采用基于分层聚类的分层索引结构。 基于内容的图像检索是一个综合性的研究学科，它从图像处理、计算机视觉、 模式识剐和数据库等研究领域借鉴了很多方法。它强调的是如何从大规模的图像 库中快速检索到符合特定需求的相似图像。本文的研究工作也将主要围绕上述核 8 北京交通大学硕士学位论文基于内容图像检索概述 心问题展开。 2 4 检索效果评价 基于内容的图像检索方法很多，在具体应用中只有采用恰当的检索算法才能 得到满意的结果。因此，需要对这些算法进行评估，比较其优劣。检索算法评价 方法能够在相同的条件下找出最佳算法。但是，至今在图像检索研究领域还没有 形成一个公认的测试图像数据库。原因是：一方面，图像本身所蕴含的内容的多 样性，一幅图像所传递的信息往往不会是单一的：另一方面，对图像相似性判断 的主观性，不同的人存在不同角度的理解，而且很可能都是合理。这两个原因给 创建一个公认的而且是分类合理的测试数据库带来了困难。标准的测试数据库的 缺乏给图像检索研究的横向比较带来了困难。但是，从另外一个方面来说，这又 说明了基于内容的图像研究还是一个开放的研究课题。 检索效果的评价策略可以分成评价手段和评价指标两部分。评价手段指的是 采用何种方式来实施评价过程；评价指标则指的是对评价过程中所收集到的数据 经过分析后得到一系列用来衡量检索效果的数值指标。 评价手段一般可以分为主观评价和客观评价两种方式。主观评价需要人的参 与，即通过人对检索结果的视觉检查，主观判定结果中哪些图像与查询目标是一 致的，哪些又是不一致的，更精确地，还可以标出一致和不一致的程度。当然， 这样会大大增加评价人的负担，并因此影响评价过程，一般并不实用。一般来说， 人的视觉最有权力判断图像间的相似性，但是，又无法忽略人在判断过程中的主 观随意性对评价结果的影响。这种影响可以通过让更多人参与评价并取多数意见 得到部分解决。客观评价则完全由程序自动完成，这需要借助一个事先经过分类 的图像数据库。分类存在一个合理性的问题，但是为了客观还是规定只有属于同 一类的图像才是相似的。理想情况下，测试用的图像数据库中的分类还可以是“软 分类”，就是一幅图像可以同时分属多类，而且可以具有不同的隶属度。但要得到 这样一个合理的“软分类”的数据库是非常困难的。 相比较而言，达到一定规模的多人参与主观评价方法可以得到最好的评价效 果。但是，这非常费时费力，特别是当评价实验需要反复进行时，其可操作性太 差。而且，主观评价存在一个致命的弱点是不可重复性，因为一个人前后两次的 评价标准会随心理状态的变化而发生改变。客观评价则不存在这一问题，可操作 性也强。因此，客观评价手段应用的更为普遍，也更有说服力。 对于评价指标，一般从检索质量和检索效率两个方面来考虑。检索质量主要 有以下两种方法1 4 】； 9 北京交通大学硕士学位论文基于内容图像检索概述 ( 1 ) 以查全率和查准率为基准的方法 查全率和查准率一般定义为：查全率= 检索到的相关图像数目所有相关图像数 目；查准率= 检索到的相关图像的数目，已检索出的图像数目。 为了评价算法的优劣，用户可以选定含有特定目标的图像作为一组相关图像， 然后根据返回的结果计算查全率和查准率。查全率和查准率越高，说明该检索算 法越有效。 ( 2 ) 排序评价方法 如果图像匹配采用相似性比较，那么，根据不同的相似性尺度，返回的图像 数目可能不同，此时采用该方法。具体过程是： 选定一定数目的含有特定目标的相关图像，如水池、草坪、人与人会谈等。 固定返回图像的数目，把返回的图像按相似性大小排序。 计算有关返回图像的排序评价指标。比如计算检索到的相关图像在所有返 回图像中的序号平均值。在理想情况下，所有相关图像都排在最前面。因此，平 均值越小，表明检索算法越好。还可以计算丢失的相关图像占所有返回图像的比 例，这个值越小，表明成功率越高。 在知识不断膨胀、数据不断增加的今天，用“海量”来形容数据量已不为过， 这样，图像检索的效率越发显得不容忽视。当图像数据量不是很大的情况下，这 个问题并不是十分突出。但是在海量的图像数据库中检索出相关的图像，势必要 考虑到检索的速率。如果不优化检索的算法，检索的时间将有可能达到用户无法 容忍的地步。因此，在保证检索质量的情况下，检索的效率也是一个重要的考量 因素。 1 0 北京交通大学硕士学位论文图像内容的特征描述 3 图像内容的特征描述 图像内容的特征描述也就是如何来描述一幅图像，是图像检索特征提取的基 础。一般来说，可以从颜色、形状、纹理以及图像空间关系等特征来描述一幅图 像。本章将分别予以介绍。 3 1 图像内容的分类 f l l h _ i l il o n g 对图像内容进行了分类【5 】。在图像内容的层次上，既有视觉部分 ( v i s lc o r l i e n t ) 又有语义部分( m a n t i cc o n t e n t ) 。视觉的部分往往被一般化或有特定 的领域。一般的视觉内容( g e r a lv i s u a lc o m e m ) 包括颜色，纹理，形状，空间位置， 轮廓，时间关系、语义特性等等。而领域特定的视觉内容( d o m a i ns p e c i f i cv i s l l a l c o n t e l l i ) ，如人脸的识别，是与应用有关的并且可能包含了该领域的一些知识。语 义的内容( s e m a 确cc o n t e n t ) 是通过原文的注释或基于视觉内容复杂的推论而获得 的，是人们对图像中的内容的概念的反映。图3 1 表示了图像内容的层次分类。另 外，好的视觉内容描述应该对图像处理过程中附加的变化是不变性( i n v a r i m c e ) ，这 种不变性的描述( i n v a r i a md e s c r i 埘o n ) 在计算机视觉中有深入的研究，而在图像检索 中的研究还相对较新p 胴。 3 2 颜色特征描述 图3 1 图像内容的层次分类 颜色特征是在c b m 中应用最为广泛的视觉特征，因为颜色和图像中的物体或 北京交通大学硕士学位论文图像内容的特征描述 场景十分相关。而且，与其他的视觉特征相比，颜色特征对图像本身的尺寸、方 向、视角的依赖性较小。相对于其他特征，颜色特征非常稳定，对于旋转、平移、 尺度变化，甚至各种形变都不敏感，表现出相当强的鲁棒性，而且颜色特征计算 简单，因此成为现有检索系统中应用最广泛的特征。目前几乎所有的基于内容检 索的图像数据库系统都把颜色检索方法作为检索的一个重要手段，并提出了许多 改进方法。 3 2 1 颜色特征模型 对颜色特征的研究必须置至于颜色模型之中，常用的颜色模型有：r g b 、h s v 川、嘲、o 【9 j 、u 【埘、l a b l l ”及m u m e l l 叫模型。这些模型都各有所长， r g b 模型由红、绿、蓝三个颜色分量组成，是最常用的颜色空间，常用于硬件显 示系统；h 8 v 是一种反映人类视觉特性的颜色空间模型，更适用于图像处理，其 中h 表示色调，s 表示饱和度，v 表示亮度值，该模型被诸多算法所采用；y u v 和o 主要用于视频传输和编码，其中y 为亮度分量，u 、v 或i 、q 为色差分量； l a b 和l u v 为均匀色度模型，其中两点间的欧氏距离与人所观察到的相应颜色的 区别程度对应；m u n l l 模型是从心理学角度，根据颜色视觉特点所指定的颜色分 类和定标系统，它由以h ( 色调) 、v ( 明度) 、c ( 色度) 为基础系统排列的色卡组成。 以下主要介绍颜色直方图、颜色矩、颜色集、颜色聚合向量以及颜色相关图 等颜色特征的表示方法。 3 2 2 颜色直方图 颜色直方图( c o l o r h i s t o g r a m ) 1 2 堤用来表达颜色特征的最常用的手段。所谓颜 色直方图是颜色信息的函数，它表示图像中具有同颜色级别的象素的个数，其横 坐标是颜色级别，纵坐标是该颜色出现的频率( 象素的个数) 。从统计意义上讲， 它是指三个颜色通道强度的联合概率。 图像特征的统计直方图实际上是一个1 d 的离散函数，即 ( 后) = i ，七= o ，l ，三一l ( 3 1 ) 其中七代表图像的特征取值，三是特征可取值的个数，是图像中具有特征值 七的象素的个数，是图像象素的总数。公式表征了图像中具有特征值七的象素出 现的频率，提供了该图像外观的一个全局描述。图像的颜色特征用直方图来表示 时，图像间的距离度量问题就相应地转化为直方图间距离度量问题，常用的度量 北京交通大学硕士学位论文图像内容的特征描述 方法有以下几种： ( 1 ) 直方图相交法 令日口和珥o ) 分别代表查询图像和数据库图像的直方图分量，则两图之间 的匹配值为： m i n ( ( f ) ，日，( 功 p ( q ，) = 旦1 一 如( o l i l ( 3 2 ) ( 2 ) 直方图匹配法 直方图的距离可使用一般的欧式距离来衡量： 蚝( 9 d = 1 魄( f ) 一日力) r ( 3 3 ) 也可以使用加权距离函数来衡量： 肘，( q ，) = 1 彬慨( o 一珥( f ) ) 2 ( 3 4 ) 其中 形= 翥耄蒙蓝挲髫三。 c s s ， ”一1l ，如果片口( f ) = o 或者e ( f ) = o ” ( 3 ) 距离法 为了减少计算复杂度，可以用直方图的均值来粗略地表达颜色特征，对图像 的r 、g 、b 三个颜色通道，匹配的特征矢量为：厂= 【。，。，。】7 。这样，查询 图像q 和数据库图像i 之间的匹配值可以定义为： 尸( q ，) = ( 尼一五) 2 = 。 g ，。( 心一胁) 2 ( 3 6 ) 该方法计算简单，容易实现，但是检索效果并不精确。 ( 4 ) 参考颜色表法 距离法太粗糙，直方图相交法计算量太大，一种折衷的办法是将图像颜色用 一组参考色表示，这组参考色应能覆盖视觉上可感受到的各种颜色。参考色的数 量要比原图的颜色数少的多，这样可算得简化的直方图，相应的特征矢量是 ，= 石，以，以r 。其中z 代表第i 种颜色出现的频率，n 是颜色参考表的长度。 此时加权后的查询图像q 和数据库图像i 之间的匹配值为： 她l = 阮：娜t = 忒鬣：鬣凳q mlf - li 1 0 谚7 v h 。 北京交通大学硕士学位论文图像内容的特征描述 3 2 3 累积直方图 当图像的特征不能取遍所有可能的取值时，统计直方图中会出现一些零值。 这些零值的出现会对计算直方图相交带来很大影响，从而使得算出的匹配值不能 正确地反映两图之间的颜色差别。对此，s t r i c k 盯和帆n g o 提出了使用“累积颜色 直方图”的概念【1 3 l 。假设颜色直方图中共有l 种颜色并按一定的顺序排列，记在 第i 种颜色上的像素数目为h ( i ) ，则累积颜色直方图可以表示为： t c = 乏：日( f ) 七= o ，1 ，三一l ( 3 8 ) 面 s 仃i c k 盯和o r e n g o 的研究结果以及刘忠伟的实验结果【1 4 1 表明累积颜色直方图 的效果要好于全局颜色直方图。 3 2 4 颜色矩 颜色的空间分布是决定图像内容的一个非常重要的因素。一片连续的红色区域 和很多分散的小红点在视觉上的差异是很明显的，但对于颜色直方图来说，它们 可能就是没有差别的。于是，有很多学者开始研究与颜色的空间分布和像素的相 关关系的颜色特征提取技术。 s 砸c k 盯和o r e n g o 认为图像的信息集中在图像的像素颜色的低阶矩中，并提出 了颜色矩( c o l o r m o m e m ) 的索引方法【”】。他们对图像中的所有像素统计在每种颜 色分量上的一阶、二阶和三阶矩，从而为每幅图像定义了9 个矩特征。计算公式 如下： 1 e = 专既 ( 3 9 ) q = 砖和谢) l ，2 墨= 砖姜( 聊嘲3 ) i 鸬 ( 3 1 0 ) ( 3 1 1 ) 其中，p ，表示图像中第，个像素点的f 颜色通道颜色值，n 表示图像的像素点 数，置、吒和墨分别为一、二、三阶矩。 实验证明，该方法用于颜色匹配比直方图具有更好的鲁棒性，由于没有考虑像 素的空间位置，该方法仍存在着精确度和准确度不足的缺点。 1 4 北京交通大学硕士学位论文图像内容的特征描述 3 3 形状特征描述 图像中物体和区域的形状是图像表达和图像检索中用到的另一类重要特征，但 是不同于颜色等特征，形状特征的表达必须以对图像中物体或区域的分割为基础。 由于当前的技术无法做到准确而稳健的自动图像分割，图像检索中的形状特征只 能在某些特殊应用场合使用，在这些应用中图像包含的物体或区域可以直接获得。 另一方面，由于人们对于物体形状的变换、旋转和缩放主观上不太敏感，合适的 形状特征必须满足对变换、旋转和缩放的不变性，这对形状相似度的计算也带来 了难度。 形状特征一般由两种表示方法：一种是轮廓特征，一种是区域特征。图像的轮 廓特征用到物体的外边界，而图像的区域特征则关系到整个形状区域。这两类形 状特征的最典型方法分别是傅立叶描述符和形状无关距。 傅立叶形状描述符但o l | r i c rs h a p cd e s c r i p t o r s ) 的基本思想是用物体边界的傅立 叶变换作为形状描述。假设一个二维物体的轮廓由一系列的坐标为( x s ，y s ) 的像素组 成，其中o s s 一l ，而n 是轮廓上像素的总数。从这些边界点的坐标中可以推 导出三种形状表达，分别是曲率函数( c u r v a t 眦f i l n c d o n ) 、质心距离( c e 曲o i dd i s 协n c e ) 和复坐标函数( c o m p l e xc 0 0 r d m 【钯s 缸l c 吐o n ) 。轮廓线上某一点的曲率定义为轮廓切 向角度相对予弧长的变化率，质心距离定义为从物体的边界点到物体中心u c c ， 的距离，复坐标函数是用复数表示的像素坐标。 庄越挺中提出了一种基于内角的形状特征表示方法【1 5 】【1 6 】，与傅立叶描述符一 样，基于内角的形状特征的提取算法首先将物体近似表达成多边形。多边形的内 角能很好的表达物体的形状，而且与形状所在位置、旋转和大小无关，很适合于 图像检索系统。 其他的形状特征的表示方法还包括有限元法( f i l l i t ee l 咖e n tm e t l l o d ，f e m ) 、旋 转函数( t l m 缸n gf u n c t i o n ) 等。另外，m m 开发的q b i c 图像检索系统采用曲率、离 心率和主轴方向等参数作为形状特征。 3 4 纹理特征描述 纹理特征是一种不依赖子颜色或亮度的反映图像中同质现象的视觉特征，它是 所有物体表面共有的内在特性，例如云彩、树木、砖、织物等都有各自的纹理特 征。纹理特征包含了物体表面结构组织排列的重要信息以及它们与周围环境的联 系。它是图像中一个重要而又难于描述的特性，在计算机视觉、遥感等领域有着 非常广泛的应用前景。纹理通常定义为图像的某种局部性质，或是对局部区域中 北京交通大学硕士学位论文图像内容的特征描述 像素之间关系的一种度量，其基本单位是纹理元。纹理特征可用来对图像中的空 间信息进行一定程度的定量描述。 目前纹理分析的方法基本可以分为统计法、结构法、模型法和空间法频率域 联合分析法等四类。基于统计的方法是对图像中的颜色强度的空间分布信息进行 统计，包括共生矩阵法、l a 髑纹理能量法等；基于结构的方法将重点放在分