（计算机应用技术专业论文）基于聚类的相关反馈图像检索的研究.pdf

摘要 近年来，随着信息技术的发展，数字图像的数量正在飞速增长。如何在这海 量的数字图像中找到我们所需要的图像数据越来越被人们所关注。基于内容的图 像检索成为当前的一个热门研究课题。 基于内容的图像检索技术依据图像的画面内容特征来检索图像库中与目标 图像相似的图像。经典的基于内容的图像检索算法在用户输入目标图像后，算法 首先提取目标图像的特征，并使用此特征与特征库中其他图像的相应特征进行匹 配，计算图像间的相似度，接着根据计算结果对特征库中的图像进行筛选，找出 与目标图像最相似的图像显示给用户。 在实际检索中，存在着特征匹配结果不能完全反映用户的语义要求，在海量 图像数据库中顺序查找效率过低等问题。针对上述问题本文对经典的基于内容的 图像检索系统提出了以下改进： ( 1 ) 选择更适合肉眼分辨的h s l 模型作为特征提取的颜色空间，对h s l 空 间进行了非等间隔的划分以达到降低维数和减少信息损失的目的，并结合加权欧 氏距离进行直方图的距离度量： ( 2 ) 引入相关反馈机制并对其提出改进，解决了增加反馈图像和用户视觉 疲劳的矛盾； ( 3 ) 将r p c l 算法引入c b i r 中并对其缺点提出了改进，提高了检索速度， 解决了事先无法确定聚类数目的问题； 为了验证改进的有效性，本文建立了相应的实验系统，并利用它对基于聚类 的相关反馈图像检索算法进行了实验。在实验中，就检索算法的准确率，查洵时 间等进行了计算，并在此基础上与以往的算法进行了比较。实验数据表明，本文 算法具有更优的检索性能。 关键词：图像检索，c b i r ，颜色，聚类，相关反馈 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm o d e mi n f o r r n a t i o nt e c l l r i o l o g y ，t h en u m b e ro fd i g i t a l l m a g e i sg m w i n gr 印i d l yh o wt of i n dt 1 1 ei m a g ed a t aw en e e di nt h em 船s i v ed a t ab a s ei sa m a c t e db y m o r ea 1 1 dm o r ep e o p l e n o wt h ec o n t e n t _ b a s e di m a g er e t r i e v a lt e c h n i q u eh a sb e e nai m p o r t a m r e s e a r c hs u b j e c t t h ec o n t e n t - b a s e di m a g er e 啊e v a lt e c l l n i q u es e a r c ht h ei m a g ei nt h ei m a g el i b r a r yb yt h e c o n t e n tf e a t u r e s t h er e s u l ti ss i m i l a rt ot h e t a 唱e ti m a g e t h et r a d i t i o n a ii m a g er e t r i e v a l a l g o r i t h mg e t sm ec h a r a c t e ro fi a 唱e ti m a g ea t 行r s tb yc o m p a r et h e c h a r a c t e rw i t ht h eo t h e r i m a g e sc o r r e s p o n d i n gc h a r a c t e r s ，w ec a ng e tt h ei m a g es i m i i a r 吼t h e na c c o r d i n gt ot h er e s u l t s ， w ec a nn n dt h em o s ts i m i l a ri m a g ew i t ht h et a 唱e ti m a g eb ys e l e c tt h ei m a g ei nt h ec h a r a c t e rb a s e i nf k t ，t h e r ea r et h ef o l i o wp r o b i e m s t h em a t c h i n gc h a r a c i e rr e s u i t sc a n tr e n e c tt h eu s e r s s e m a n t i cr e q u i r e m e n t sc o m p l e t e l y _ t h ea b i l 时o fs e r i a is e a r c hi s p o o ri n t h ei m a g em a s s i v e d a t a b a s el nav i e wo f m e s ep r o b l e m s ，t h et l e s i sg i v et h ef o l l o w i n gi m p r o v e m e n t s ( 1 ) t h et h e s i sc h o o s e 血em o r ep r o p e r l yh s lc 0 1 0 rs p a c e t h e ni td i v i d et h eh s ls p a c eu n e q u a y w h j c hc a nr e d u c et h ed i m e n s i o n sa n di n f o r m a t i o nl o s se f f j c t i v e l 弘a ti h es a r n et i m ei ta l s o c a r e st h eh i s t o 静a m sd i s t a n c em e a s u r el ld i s t a n c ew i t hw e i 曲ta d d e d ( 2 ) t h ec o r r e l a t em e c h a n i s mo ff e e d b a c ki sp u ta n dg i v ea n ；m p r o v e m e n tw h i c hs o l v et h e c o n t r a d i c t i o nb e n e e nt h ei n c r e a s e df e e d b a c ki m a g ea n dt h eu s e r s e y es t r a j n ( 3 ) t h er p c la l g o r i t h mi sp u ti n i ot h ec b i r w i t ht h ei m p r o v e m e n ol h ea l g o r i c h m s d e f e c t s ，i i i m p r o v et h er e t r i e v a ls p e e d 锄dt h ep r o b l e mo fh o wt od e t e 兀】血n ea u t o m a t i c a i l yg r o u p i n g n u m b e l i no r d e rt o t e s tt h ei m p r o v j n go ft h e a l g o r i t h m ，t h e t h e s i sb u i l dt h e c o r r e s p o n d i n g e x p e r i m e n t a ls y s t e m 1 nt h ee x p e r i m e n to f c o r r e l a t ef e e d b a c ko fi m a g er e t r i e v a l ，t h et h e s i s s a l g o r i t h m i s c o m p a r e d w t ho t h e ra l g o r i t h m sw h i c hb a s e do nt h e a c c u r a c y ，s e a r c h i n g c o m p l ex i t j e s b yt h ee x p e r i m e n t a ld a t a ，t h ea i g o r i t h mo ft h i st h e s i sh a sm o r es u p e r i o rr e t r i e v a i p e r f o r m a n c e ， k e y w o r d s ：i m a g er e t r i e v a l ，c b i r ，c o l o r ，c 1 u s t e r i n 岛r e l e v a t l c ef e e d b a c k 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一 同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 学位论文使用授权说明 起斌 2 0 0 6 年6 月1 日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ： 垃缝盛 2 0 0 6 年6 月1 日 第一章绪论 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 ) 是一门随着 计算机视觉、图像理解与图像处理研究的进步而逐渐发展成熟的一种图像媒体检 索技术，涉及了图像处理、模式识别、人工智能、神经网络及数据库技术等多种 学科。该领域具有真正意义的研究起步于二十世纪8 0 年代，到了9 0 年代其研究 才取得较大的突破，多种成果开始转化为应用技术，随着这些技术的不断成熟， 它已经被广泛应用到了网络搜索引擎、数字图书馆图像检索、商标检索等领域， 日益增长的应用需求反过来也推动其研究向更高的层次发展，这个时期主要以模 式识别的研究为主，随着m p e g 一7 标准的推出，图像检索将朝商业化发展。 1 2 研究背景 c b i r 作为传统数据库检索的拓展，把图像处理、图像识别、数据库3 个领 域的技术成果结合起来，并融合了图像理解技术，利用图像特征的距离度量相似 性，从数据库中查找具有指定特征或含有特定内容的图像，其应用领域涉及多媒 体数据库、地理信息系统、电子图书馆、商标管理、罪犯识别系统、卫星遥感图 像处理、医疗图像管理等多个方面h 9 50 1 。同传统的关系数据库检索系统相比，具 体主要有以下几个特点【2 j ： 1 、基于内容的图像检索是一种近似匹配，不断接近的过程 在基于内容的图像检索过程中，每次检索得到的中问结果都是一个集合。对 于图像的检索，实际上是一个不断缩小结果集范围，逐步接近目标图像的过程。 这明显有别于关系数据库中检索的精确匹配。 2 、利用多种方法从图像内容中进行特征提取以检索 从图像中提取的特征信息可以是颜色、形状、纹理、轮廓、空间关系等多种 图像视觉特征：提取的方法也可以有多种，如直方图、小波分析、模糊逻辑、区 域匹配、相关图、信息熵等等4 ，5 ，6 1 。这使得检索出来的结果更加接近图像本身。 3 、特征提取和索引建立可由计算机自动实现 计算机自动实现避免了人工描述的主观性，大大减少了：i ：作量。但相似性度 河海大学硕士学位论文 量与人的主观感受有关，因此，常需要用人机交互的方法，学习人的主观相似度 感受。 对基于内容的图像检索的研究可分为三层：下层是基于颜色、纹理、形状等 反映图像基本物理特征的检索，是最直接、最基本的层面，用到图像信息处理、 图像分析和相似性匹配技术；中间层是基于图像对象语义，如图像中实体及实体 之间的空间关系的检索，对象级检索技术建立在下层特征基础上，并引入了对象 模型库、对象识别和人工智能等图像理解技术；最上层是基于图像概念级语义的 检索，其技术建立在对象层语义特征提取的基础上，引入了对象和场景之间的逻 辑、情感等高层语义的描述及识别，需要用到知识库和更加有效的人工智能和神 经网络技术。 目前，基于内容的图像检索系统获取图像信息的方式主要有两种：一种是利 用查询语言直接操纵信息；二是在对现实世界真实描述的基础上开发查询接口。 利用查询语言直接操纵信息的方式是让查询语言作为载体，把用户要查图像 的相关信息精确的告诉计算机，计算机根据这些信息进行查询。该方式能够精确 描述要查的图像相关内容，但用户界面不够友好，可视化程度不高。 目前，大多数基于内容的图像查询系统采用第二种方式，即在对现实世界真 实描述的基础上开发查询接口。该方式对现实世界的描述不够精确，但具有较高 的可视化程度。例子图像查询( q u e r yb a s e di m a g ee x 锄p l e ，q b i e ) 方法1 就 是基于这一方式的。它采用了两步走的检索策略：在预备阶段，对图像数据库中 的每幅图像提取基本特征向量，并把它作为索引存放在图像数据库中。在实际查 询阶段，让用户提出或画出一个要检索的图像范例，系统提取出该范例图像的特 征向量，让这个特征向量与图像数据库中的索引特征向量进行比较，然后按照相 似的程度，返回给用户一个结果集。例如，i b m 开发的q b i c 系统，便支持例子 图像的查询。 由于基于内容的检索有着广泛的需要，并有着较好的市场前景，因而也引起 了国际标准化组织的关注。m p e g 专家组正在着手制定更高版本的m p e g 一7 ( 又称为 多媒体内容描述接口) ，它主要是对各种类型的多媒体数据进行规范化描述，目 的是便于快速和有效地查找用户感兴趣的材料。随着多媒体内容描述的标准化， 图像内容的描述也将随之而标准化，基于内容的图像检索将朝商业化方向迈进。 第一章绪论 国内外也已经开发出部分原型系统，比如i b ma l m a d e n 研究中心研究开发的 q b i c 系统是基于内容检索系统的典型代表。q b i c 系统允许使用例子图像、用户 构建的草图和图画、选择的颜色和纹理模式、镜头和目标运动和其他图形信息等， 对大型图像和视频数据库进行查询。 另外还有许多类似的系统，如m i t 的媒体实验室在1 9 9 4 年开发研制的 p h o t o b o o k 系统，美国哥伦比亚大学图像和高级电视实验室开发的v i s u a l s e e k 系统。但这些系统存在的一个主要问题是检索过程以计算机为中心，使得一些查 询结果并不能完全满足用户的要求。 这种方法有较大的局限性： ( 1 ) 用一种或多种视觉特征无法表达图像的语义信息； ( 2 ) 相似性距离表示的是图像特征空间中的距离，而不是真正的图像语义之 间的相似距离： ( 3 ) 人的查询目的具有很大的主观性，很难用这种客观的距离度量来适应这 种主观性。 本文在这种研究现状下，通过在传统c b i r 系统中结合聚类和相关反馈机制， 来达到改进图像检索性能的目的。 1 - 3 本文主要研究内容 本文为实现提高c b i r 的检索查全率、查准率以及查询时间，研究了相关反 馈算法、聚类算法在c b i r 中的应用并做了相应的改进，主要内容主要包括以下 几个方面： 介绍c b l r 中涉及的各种技术。迤今为止，人们在c b i r 中引入了多种算法 思想，如相关反馈、聚类、神经网络、支持向量机、小波算法等。对本文中涉及 的相关技术进行了介绍，并将现有的相关方法进行了比较。 针对原有各种算法的不足，提出本文算法，并进行了详细介绍。 通过实际例子比较各种算法。分析各算法的性能。 1 4 论文结构 第一章绪论 河海大学硕士学位论文 介绍论文的研究背景、研究目的、研究方法、研究成果和最终结论。 第二章研究中涉及的关键技术 介绍了在基于内容图像检索中涉及的关键技术，包括特征的提取方法、 相似性度量方法、相关反馈和聚类方法。 第三章基于聚类的相关反馈检索的设计 详细分析了现有算法及其不足，提出自己对现有算法的改进。对r p c l 算法和相关反馈算法进行相应的改进，提出了本文的基于聚类的相关反 馈图像检索算法。 第四章基于w e b 的c b i r 试验系统 通过相关的验证系统对本文算法和各种相关算法的查全率，查询时间等 性能进行了比较。 第五章总结与展望 对全文的工作、创新点和理论、实际意义傲了一个总结，并且对今后 的研究工作进行了展望。 第二章研究中涉及的关键技术 2 1 引言 第二章研究中涉及的关键技术 基于内容的图像检索技术依靠计算机自动提取图像特征和编制图像的特征 库，检索时依据目标图像的特征( 例如颜色、形状或纹理等) 自动比较特征库中的 对应特征信息，最后将最佳匹配结果和相关信息输出给用户“1 ，整个处理过程如 图2 1 所示： 图2 1c b i r 的处理 由图2 一l 可见，c b i r 中关键在于检索模块和查询模块。 检索模块涉及到从图像中提取相应的特征( 颜色、形状和纹理等) ，以及利 用图像特征的距离度量相似性，特征提取和距离度量方法是图像度量的基础，图 像特征的选择和度量方法的选择直接影响到检索效果和效率，此外，检索模块中 还涉及到聚类技术，对图像库采用聚类算法并按某种相似度原则进行分类，把相 河海大学硕士学位论文 似的图像聚合在一起，大大地缩小图像搜索的范围，可以达到快速、准确检索到 目标图像的目的； 查询模块负责将查询结果与用户进行交互，交互的效果，界面是否友好也将 影响到查询的结果，查询模块中涉及到相关反馈技术，在基于内容的图像检索中 采用相关反馈机制可以达到逐步求精的过程； 本文提出使用聚类思想和相关反馈机制来改进c b i r 。本章将就涉及到的特征 提取、距离度量、聚类以及相关反馈这四个方面关键技术的现状和发展动态进行 相应的介绍。 2 2 基于内容的图像检索的特征提取 尽管经过了2 0 多年的研究，较为成熟的基于内容的图像检索技术目前仍处于 对底层特征的研究。同时，由于底层研究是语义等上层研究的基础，为了给上层 建立准确、有效的图像特征提取方法，底层的研究仍在不断的发展。颜色、纹理 和形状是图像最基本的特征，现有的c b i r 系统主要是根据图像的色彩、纹理、形 状等底层图像特征，建立图像的特征矢量。 2 2 1 颜色特征 颜色特征是在图像检索中应用最为广泛的视觉特征，因为颜色和图像中的物 体或场景十分相关。而且，与其他的视觉特征相比，颜色特征对图像本身的尺寸、 方向、视角的依赖性较小，具有较高的鲁棒性。本文将主要介绍颜色直方图、颜 色矩、颜色集、颜色聚合向量以及颜色相关图等颜色特征的表示方法。 ( 1 ) 颜色直方图 颜色直方图是采用最广泛的颜色特征。s w a i n 和b a l l a r d 于1 9 9 0 年提出了颜色 直方图，先将颜色空间划分为若干个固定的子空间，然后对每幅图像统计属于各 子空间的像素数目。它所描述的是不同色彩在整幅图像中所占的比例。这种方法 具有计算简单、对平移和旋转不敏感等优点，但因为不包含色彩的空间位置信息， 就无法描述图像中的对象或物体。 颜色通常采用r g b 三色表示，但这种表示法不符合人眼视觉特性，因此一般 要把r g b 空间转换到其他颜色空间，比如h s l 空间、l u v 空间和l a b 空间，因为它们 第二章研究中涉及的关键技术 更接近于人们对颜色的主观认识。其中h s l 空间是直方图最常用的颜色空间，其 优点是可以转换回r g b 空间。它的三个分量分别代表色彩( h u e ) 、饱和度 ( s a t u r a t i o n ) 和亮度( l i g h t n e s s ) 。 ( 2 ) 颜色矩 另一种非常简单而有效的颜色特征使由s t r i c k e r 和o r e n g o 所提出的颜色矩 ( c o l o rm o m e n t s ) ”3 。其数学基础是图像中任何的颜色分布均可以用它的矩来 表示。此外，由于颜色分布信息主要集中在低阶矩中，因此仅采用颜色的一阶矩 ( m e a n ) 、二阶矩( v a r i a n c e ) 和三阶矩( s k e w n e s s ) 就足以表达图像的颜色分 布。与颜色直方图相比，该方法的另一个好处在于无需对特征进行向量化。在实 际应用中，颜色矩一般在使用其它特征前起到过滤缩小范围的作用。 ( 3 ) 颜色集 为支持大规模图像库中的快速查找，s m i t h 和c h a n g 提出了用颜色集( c o l o r s e t s ) 作为对颜色直方图的一种近似“。首先将r g b 颜色空间转化成视觉均衡的 颜色空问( 如h s l 空间) ，并将颜色空间量化成若干个b i n 。然后，用色彩自动分 割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引， 从而将图像表达一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集 之问的距离和色彩区域的空间关系( 包括区域的分离、包含、交等，每种对应于 不同得评分) 。因为颜色集表达为二进制的特征向量，可以构造二分查找树来加 快检索速度，这对于大规模的图像集合十分有利。 ( 4 ) 颜色聚合向量 针对颜色直方图和颜色矩无法表达图像色彩的空间位置的缺点，p a s s “”提出 了图像的颜色聚合向量( c o l o rc o h e r e n c ev e c t o r ) 。它是颜色直方图的一种演 变，其核心思想是将属于直方图每一个b i n 的像素进行分为两部分：如果该b i n 内的某些像素所占据的连续区域的面积大于给定的阈值，则该区域内的像素作为 聚合像素，否则作为非聚合像素。假设口- 与肛分别代表直方图的第f 个b i n 中聚 合像素和非聚合像素的数量，图像的颜色聚合向量可以表达为 ( k t ，届l 如z ，z l ，b “，风) ) 。而( d + 崩，口：+ 岛，口。+ 风就是该图像的颜色 直方图。由于包含了颜色分布的空间信息，颜色聚合向量相比颜色直方图可以达 到更好的检索效果。 河海大学硕士学位论文 ( 5 ) 颜色相关图 颜色相关图( c 0 1 0 rc o r r e l o g r a m ) 是图像颜色分布的另一种表达方式3 。 这种特征不但刻画了某一种颜色的像素数量占整个图像的比例，还反映了不同颜 色对之间的空间相关性。实验表明，颜色相关图比颜色直方图和颜色聚合向量具 有更高的检索效率，特别是检索空间关系一致的图像。 2 2 2 纹理特征 纹理特征是一种不依赖于颜色或亮度的反映图像中同质现象的视觉特征，它 是所有物体表面共有的内在特性，例如云彩、树木、砖、织物等都有各自的纹理 特征。纹理特征包含了物体表面结构组织排列的重要信息以及它们与周围环境的 联系。这里，本文简要介绍那些在基于内容的图像检索中所常用的那些纹理特征， 主要有t a m u r a 纹理特征、自回归纹理模型、方向性特征、小波变换和共生矩阵等 形式。 ( 1 ) t a m u r a 纹理特征 基于人类对纹理的视觉感知的心理学的研究，t a m u r a 等人提出了纹理特征的 表达“。t a m u r a 纹理特征的六个分量对应于心理学角度上纹理特征的六种属性， 分别是粗糙度( c o a r s e n e s s ) 、对比度( c o n t r a s t ) 、方向度( d i r e c t i o n a l i t y ) 、 线像度( 1 i n e l i k e n e s s ) 、规整度( r e g u l a r i t y ) 和粗略度( r o u g h n e s s ) 。其 中，前三个分量对于图像检索尤其重要。 ( 2 ) 自回归纹理模型 近年来，有大量的研究集中在应用随机场模型表达纹理特征，m a r k o v 随机场 ( m r f ) 模型取得了很大的成功。自回归纹理模型( s i m u l t a n e o u s a u t or e g r e s s jv e ，或s a r ) 就是m r f 模型的一种应用实例。 在s a r 模型中，每个像素的强度被描述成随机变量，可以通过与其相邻的像 素来描述。如果s 代表某个像素，则其强度值g ( s ) 可以表达为它的相邻像素强度 值的线性叠加与噪音项s ( j ) 的和。此外，s a r 的一种变种称为旋转无关的自回归 纹理特征( r o t a t i o n i n v a r i a n ts a r 或r i s a r ) ，具有与图像的旋转无关的特点。 定义合适的s a r 模型需要确定相邻像素集合的范围。然而，固定大小的相邻 像素集合范围无法很好地表达各种纹理特征。为此，有人提出过多维度的自回归 第二章研究中涉及的关键技术 纹理模型( m u l t i r e s o l u t i o ns a r 或m r s a r ) ，能够在多个不同的相邻像索集合 范围下计算纹理特征。 ( 3 ) 其它纹理特征 除了上述的t a m u r a 特征、s a r 模型纹理特征之外，还有许多其它的纹理特征。 7 0 年代，h a r a l i c k 等人提出了用共生矩阵( c o o c c u r r e n c em a t r i x ) 表示纹理特 征的方法1 。该方法对从数学角度研究了图像纹理中灰度级的空间依赖关系。它 首先建立一个基于象素之间方向性和距离的共生矩阵，然后从矩阵中提取有意义 的统计量作为纹理特征。许多其他研究人员沿着这个方向提出了扩展的方案。 g a b o r 过滤法“”能够最大程度地减少空间和频率的不确定性，同时还能够检 测出图像中不同方向和角度上的边缘和线条。此外，小波变换也是一种常用的纹 理分析和分类方法“。 2 2 3 形状特征 物体和区域的形状是图像表达和图像检索中的另一重要的特征。但不同于颜 色或纹理等特征，形状特征的表达必须以对图像中物体或区域的划分为基础。由 于当前的技术无法做到准确而鲁棒的自动图像分割，图像检索中的形状特征只能 用于某些特殊应用，在这些应用中图像包含的物体或区域可以直接获得。另一方 面，由于人们对物体形状的变换、旋转和缩放主观上不太敏感，合适的形状特征 必须满足对变换、旋转和缩放无关，这对形状相似度的计算也带来了难度。 通常来说，形状特征有两种表示方法，一种是轮廓特征的，一种是区域特征 的。前者只用到物体的外边界，而后者则关系到整个形状区域。这两类形状特征 的最典型方法分别是傅立叶描述符和形状无关矩。 ( 1 ) 傅立叶形状描述符 傅立叶形状描述符( f o u r i e rs h a p ed e s c r i p t 。r s ) 的基本思想是用物体边 界的傅立口f 变换作为其形状描述。从边界点的坐标中推导出三种形状表达，分别 是曲率函数( c u r v a t u r ef u n c t i o n ) 、质心距离( c e n t r o i dd i s t a n c e ) 和复坐 标函数( c o m p l e xc o o r d i n a t e sf u n c t i o n ) 。 ( 2 ) 形状无关矩 形状无关矩( m o m e n ti n v a r i a n t s ) 是基于区域的物体形状表示方法。文献 河海大学硕士学位论文 1 8 中，h u 提出了广泛使用的一系列具有变换、旋转和缩放无关性的7 个矩。此 外，y a n g 和a 1 b r e g t s e n 在g r e e n 定理的基础上提出了在二值图像中快速计算矩的 方法。由于许多有效的不变量都是从反复的实验中得到的，k a p u r 等开发了一系 列算法用来系统地寻找特定的几何不变性。g r o s s 和l a t e c k i 还开发出了一种方 法，能够在图像数字化的过程中保持物体边缘的定性微分几何。 ( 3 ) 基于内角的形状特征 在文献 1 9 中提出了一种基于内角的形状特征表达方法。与傅立叶描述符一 样，首先将物体近似的表达成多边形的形式。基于内角的形状描述与形状所在位 置、旋转和大小无关，因此它非常适于图像检索系统。从内角导出的形状特征定 义包括：定点数、内角平均值、内角标准方差、内角直方图。 ( 4 ) 其它形状特征 近年来在形状表示和匹配方面的工作，包括有限元法( f i n i t ee l e m e n t m e t h o d 或f e m ) 、旋转函数( t u r n i n gf u n c t i o n ) 、和小波描述符( w a v e l e t d e s c r i d t o r ) 等方法。f e m 定义了一个稳定性矩阵来描述物体上的每一个点与 其它点之问的联系。这个稳定性矩阵的特征向量被称作特征空间的模合基。所有 的形状都首先映射到这个特征空间，再在特征值的基础上计算形状相似性。类似 于傅立叶描述符的思路，a r k i n 等提出了旋转函数用来比较凹面或凸面多边形的 相似性。c h u a n g 和k u o 用小波变换来描述物体形状。它几乎包含了符合要求的所 有性质，如不变性、单一性、稳定性和空间位置等。另外，i b m 所开发的q b i c 图 像检索系统采用曲率、离心率和主轴方向等参数作为形状特征。 尽管计算上述的形状特征并不复杂，但发明一种符合人们主观判断的形状相 似性度量算法还是一个有待解决的难题。同时，要在图像检索中充分使用形状特 征，还必须有鲁棒的图像自动分割的通用算法。 2 3 相似性度量 传统的数据库系统中的检索般是基于精确的匹配，基于内容的图像检索 中，图像特征是图像的近似表示，检索也是在图像集合中查找与给定检索图例“相 似”的对象，即从候选图像集合中找出与指定的待搜索对象在视觉特征上相似度 最大的对象子集。属于“相似性检索”( s i m i l a rs e a r c h ) 。 第二章研究中涉及的关键技术 因此，定义一个合适的视觉特征相似性度量方法对检索的效果有很大的影 响。c b i r 中的视觉特征大都可以表示成向量的形式，常用的相似性度量方法都是 基于向量空间模型( v e c t o rs p a c em o d e l ) ，即将视觉特征看作是向量空间中的 点，通过计算两个点之间的接近程度来衡量图像特征间的相似度。设x 、y 为图 像特征，分量分别为。一，y - ( 1 f 尺( 三”，有厂( 三，q ) ，( 三，q ) 。故 而，尺( ) 在一定程度上反映了图像l 与q 的相似程度，可以被用来进行图像查询 精度的计算。 图像查询精度的计算，其标准主要有两个：查准率e 和查全率c 。对于对图像 数据库多次查询得到的查询集合 q l ，q z 一q n ) 中的某次查询q ，本文用 三，= ( 上：，上，耳。) 表示其得到的满足用户查询要求的唯一结果图像集合。则查 准率可以计算为 上 e ：土争复墨蚴 智 卅 ( 2 8 ) 河海大学硕士学位论文 c ：三宇咝坦壁! 三型 智 m ( 2 9 ) 查准率e 和查全率c 的计算较好的反映了系统的查询精度。 2 6 2 查询速度的计算 c b i r 系统得到结果所耗费的时间是系统查询速度的主要衡量标准，主要分为 预处理时间r t 和查询时问s t 两部分。预处理时间r t 主要是指c b i r 系统生成图像数 据库的时间，它的计算公式为 。，生成数据库总耗费时间将图像集加入到数据j 聋扣总耗费时间 代1 2 顶丽再画丽4 啊蘅砰面骊雨广( 2 1 0 ) 而查询时间s t 主要是指c b i r 系统实际进行查询所耗费的时间，它的计算公式 为 盯：竺壁查塑堡墨塞璺堑望堕塑 查询结果集图象的个数 ( 2 1 1 ) 预处理时间r t 与查询时间s t 的计算能够大致反映c b i r 系统的运行速度的基 本情况。 2 7 本章小结 本章介绍了基于内容的图像检索中的特征提取、相似性的度量方法、聚类的 分类以及图像检索中相关反馈机制的应用。 第三章基于聚类的相关反馈检索的设计 3 1 引言 第三章基于聚类的相关反馈检索的设计 基于内容的图像检索( c o n t e n t b a s e d i n l a g c r e m e v a l ，c b i r ) 依靠计算机自动 提取图像特征和编制图像的特征库，检索时依据目标图像的特征( 例如颜色、形 状或纹理等) 自动比较特征库中的对应特征信息，最后将晟佳匹配结果和相关信 息输出给用户【3 5 j 。 经典的c b i r 算法的流程如图3 一l 所示。在用户输入目标图像后，算法首先提 取目标图像的特征，并使用此特征与特征库中其他图像的相应特征进行匹配，计 算图像间的相似度，接着根据计算结果对特征库中的图像进行筛选，找出与目标 图像最相似的图像显示给用户。通常，算法首次给出的检索结果往往难以令人满 意，因此需要用户对检索结果评价和标记，指出结果中哪些与目标图像相似、哪 些不相似，然后利用这些相关反馈信息对特征匹配的策略进行修正，接着进行二 次检索，如此循环，直到用户满意为止。 目标例俾 用尸 图3 1c b i r 算法的流程 但是经典的c b i r 算法中存在着以下缺陷： ( 1 ) 人类不能像计算机显示器那样只使用r g b ( 红、绿、蓝) 成分感知颜色， 需要选择一个适合于人类视觉特征的颜色模型来改善检索效果； ( 2 1 大部分c b i r 算法在进行图像筛选时，只是按照目标图像特征的相似度对 特征库中的图像进行排序，并向用户返回相似度最大的n 幅图像【3 6 】。由于计算机 河海大学硕士学位论文 自动提取的图像特征与人所理解的语义之间存在巨大的差异，显示给用户的图像 中包含的相似图像可能会很少，造成每次检索的准确率比较低，同时用户需要检 索的次数相应增加。要想解决这个问题，可以每次向用户显示更多的图像，例如 相似度最大的锄幅图像，以增加相似图像的数量。但是，如果显示给用户的图像 太多，又会造成用户的疲劳，反而使后续检索准确率下降： ( 3 ) 对于海量的图像数据库，采用顺序查找的方法进行示例图像与图像数据 库中的图像进行匹配效率过低，现有的聚类方法都可以应用到c b 瓜中。在文献 4 5 】【4 6 】中也的确将k - m e a n s 、i s o d a ，i a 等聚类方法应用到了c b i r 中，但是现实 中需事先确定类的数目，然而在许多场合，这个数目是未知的： 针对存在问题，本文对上述问题提出了解决方法，详细介绍了本文基于聚类 的相关反馈图像检索系统中颜色特征空间的选择以及划分、聚类算法的选择以及 改进、相关反馈机制的选择以及改进。 3 2 颜色特征的提取 在图像的所有表征属性中，颜色特征是最可靠、最稳定的视觉特征。相对于 几何特征而言，颜色对图像中子对象的大小和方向的变化都不敏感，具有相当强 的鲁棒性。同时，在许多情况下，颜色又是描述一幅图像最简便而有效的特征。 人们对于一幅图像的印象，往往从图像中颜色的空间分布开始。所有这些都促使 颜色成为基于内容的图像检索所采取的主要手段之一，因此本文也基于颜色进行 特征查询。 认知科学及视觉心理学证明，人类不能像计算机显示器那样只使用r g b ( 红、 绿、蓝) 成分感知颜色，因此，选择一个适合于人类视觉特征的颜色模型可以改 善检索效果。我们知道图像的颜色有多种表示方式，其中h s l ( h u e s a t u r a t i o n l i g h t n e s s ) 颜色模型是一种适合肉眼分辨的模型。在h s l 模型 中，h 定义为颜色的波长，称为色调( o 。h 玉3 6 0 。) ；s 定义为颜色的强度 ( i n t e n s i t y ) 表示颜色的深浅程度，称为饱和度( o s 1 ) ：l 定义为掺入的 白光量，称为亮度( o 1 ) ，基于色调一饱和度一亮度的颜色模型，其色彩 表示具有同人类对色彩感知的一致性、均匀性【3 7 1 ，因此在w i n d o w s 中也用了h s l 第三章基于聚类的相关反馈检索的设计 表示法，1 6 色v g a 调色板的值就是根据h s l 设计的。h s l 定义在圆柱坐标系 上如图3 2 所示，若把s 和l 的值设置为l ，当改变h 时就是选择不同的纯颜色； 减小饱和度s 时，就可体现掺入白光的效果；降低亮度时，颜色就暗，相当于掺 入了黑色。所以人们常将h s l 作为常用的色彩表示空间。h s l 色彩模型可用 m u n s e l l 三维空间坐标系来表示，如图3 2 所示。因坐标之间的心理感知独立性， 因此，可以独立感知各颜色分量的变化；且这种颜色模型具有线性伸缩性，可感 知的颜色差是与颜色分量的相应样值上的欧几里德距离成比例的。在基于内容检 索中应用这种模型更适合用户的肉眼判断。 l ( a ) h s l 颜色模型的三维表示( b ) h s l 的颜色轮表示 图3 - 2h s l 颜色模型的表达 从图像中一般得到的都是r g b 值，由r g b 值到h s l 空间的映射过程 t ( h s l ) ：( r ，g ，b ) 一( h ，s ，1 ) 定义如下： 给定r g b 颜色空间的值( r ，g ，b ) ，r ，g ，b o ，1 ，2 5 5 设f = m a ) 【( ，g ，6 ) ，定义7 ，g ，6 为： r = 南( 3 1 )g = 南( 3 - 2 ) 6 2 再 ( 3 3 ) 厶：6 0 ( 3 4 ) s = 芈( 3 5 ) f _ z 2 5 5 ( 3 6 ) 其中： 河海大学硕士学位论文 = ( 5 + b ，) r = m a x ( r ，g ，b ) 口n dg = m i n ( r ，g ，b ) ( 1 一g ) r = m a x ( r ，g ，b ) 册dg m i n ( r ，g ，” ( 1 + r 0g = m a x ( r ，g ，”硎db = r n i n ( r ，g ，b ) ( 3 _ b ) g = m a x ( r ，g ，b ) 册db r n j n ( r ，g ，b ) ( 3 + g ) b = m a x ( r ，g ，b ) 册dr = m i n ( r ，g ，b ) f 5 - r ，) o t h e r w i s e ( 3 7 ) 这里，h o 3 6 0 】，s o l 】，l e 【o 1 】 本文用h s l 空间的颜色直方图来描述图像的整体颜色特征，从上面可以看 出，h s l 色彩空间中的三个色彩分量大部分是连续的，通过离散化可以产生大 量的离散值。因为，一幅图像的颜色一般非常多，尤其是真彩色图像，因此直方 图矢量的维数会非常多，如果对h s l 空间进行适当的量化后再计算直方图，则 计算量要少很多。如果将h 进行3 6 0 等分，s 和1 分别进行1 0 0 等分将产生3 6 + 1 0 4 种色彩。实际上人对色彩的分辩能力是有限的，在色彩空间中，当两个色彩之间 色差的距离小于一定的值时，人眼已经不能区分出他们之间的区别，认为是同一 种色彩。因此，从量化的角度考虑，将色彩空间h s l 进行适当的划分，然后再 计算直方图，其计算量要小得多。关于色彩空间的划分，目前有两种方式：均匀 色彩空间的划分和非均匀色彩空间的划分。文献 3 8 中将整个h s l 色彩空间h 进行1 8 等分，s 、1 分别进行3 等分，然后再加上四个灰度级共形成1 6 6 种色彩， 采用的方法基本上是对色彩空间进行平均划分。文献 3 9 中将h 、s 、l 三个分量 进行了非等间隔的量化，将h 空间分别8 非等间隔区间，饱和度s 和亮度l 分 为3 非等间隔，量化后的色彩空间共有7 2 种色彩。 由于人对颜色感知的敏感程度( 对色调分量h 感知较为灵敏，对亮度分量l 和饱和度分量s 感觉相对迟钝) 和光学中相关理论( 物体的颜色与光的波长和频 率有关，不同的色光在真空中的波长和频率的范围不一样) 的考虑【4 7 ，48 1 ，本文进 行非等间隔量化。研究表明，人类对亮度信息感知分辩能力要比对色彩和饱和度 要强得多，在h s l 色彩空间的划分中，l 分量不能太粗，否则，会导致色彩信 息的大量丢失。因此，本文采取的方法是：将h ，s ，l 三个分量按照人的颜色 感知进行非等间隔的量化，把色彩h 空间分成8 份，饱和度s 和亮度l 空间分 别分成3 份和5 份，并根据色彩的不同范围进行量化，量化后的结果用h s l 空 问的颜色直方图来描述图像的整体颜色特征。设色调、饱和度和亮度值分别为h ， 第三章基于聚类的相关反馈检索的设计 s ，l ，则本文所定义的划分如下 h ( ) = 0 矗“3 1 6 ，2 0 】 1 ；2 【2 1 ，4 0 2 而【4 1 ，7 5 】 3 矗 3 7 6 ，1 5 5 】 4 矗【1 5 6 ，1 9 0 5 【1 9 1 ，2 7 0 】f os 【o ，o 2 】工u ) = 6 【2 7 l ，2 9 5 】s ( j ) = lj ( 0 2 ，o 7 ) 7 矗【2 9 6 ，3 1 5 】1 25 ( o 7 ，l ，o o ，【o ，o 2 】 1 z ( o 2 ，o 4 】 2 f e ( o 4 ，o 6 】 3 ，( o 6 ，o 8 】 4f (