（计算机应用技术专业论文）基于形状的植物叶子图像检索与聚类研究.pdf

内容摘要 随着互联网的快速发展和计算机应用范围的不断扩展，越来越多的图像数据 需要被分析和处理，但是，传统的检索方式已经不能满足实际的需求。为了便于 图像检索和识别，出现了一种称之为基于内容图像检索( c b m ) 的技术，该方 法利用颜色，纹理，形状或者是这些特征的结合来对图像进行检索。其中，形状 是一个重要的低层特征，它考虑的是物体的全局信息，其应用包括生物或医学图 像分析，形态测量学，数据库检索，军事目标识别和计算机视觉等等。本文对基 于形状的植物叶子图像检索和聚类方法进行了探讨，并通过实验对其效果进行验 证和评价。 本文的目标之一是对植物叶子形状的视觉特征进行描述。首先回顾了许多形 状表示及描述技术，包括基于轮廓的方法以及基于区域的方法。在众多的方法中， 本文集中于基于傅立叶变换的形状表示方法，对一系列的傅立叶描述方法进行了 研究，包括收敛性分析，检索性能以及对比研究，并得出一些有意义的结论。接 下来，本文提出一种基于质心距离直方图的形状描述方法，形状之间的相似度通 过对比相应范围内的半径数量进行计算。实验结果表明，两种特征的融合能够获 得更高的检索性能。 本文另一贡献是提出基于形状特征的图像聚类算法，目的是为了改善查询时 的效率。首先，回顾了基于欧拉空间的经典聚类算法，这些算法主要分为两种类 型：基于分划的聚类和基于层次的聚类。接下来，本文提出了一种基于随机模拟 退火算法的聚类算法。基本的思想是以随机的k 个聚类为开始，通过在聚类之间 进行重排来最小化评分函数，重排基于随机选择两种不同的移动方法，最后在这 个基础上提出了一种利用形状均值对形状数据库进行层次化组织的方法。 关键词：基于内容图像检索；形状检索；形状聚类 a b s t r a o t r e c e n ty e a r sh a v ew i t n e s s e dt h er a p i dg r o w t ho fd i g i t a li m a g e sd u et ot h e i n c r e a s i n gp o w e ro fc o m p u t i n ga n dt h ef a s td e v e l o p m e n to fi n t e r n e t t h e d e v e l o p m e n to fp o w e r f u lr e t r i e v a lt o o l sh a sb e c o m eac e n t r e lp r o b l e mi n v a r i o u sm a c h i n ev i s i o na p p l i c a t i o n s an e wm u l t i m e d i aa p p l i c a t i o n ，c a l l e d c o n t e n tb a s e di m a g er e t r i e v a l ( c b i r ) h a sc o m ei n t ob e i n gt oa d d r e s st h i s u r g e n ti s s u e i nc b i r ，i m a g ei sd e s c r i b e db ys e v e r a ll o wl e v e li m a g ef e a t u r e s s u c ha sc o l o r ，t e x t u r e ，s h a p eo rt h ec o m b i n a t i o no ft h e s ef e a t u r e s s h a p ei sa n i m p o r t a n tf e a t u r et h a tc o n s i d e mt h eg l o b a lf e a t u r eo fo b j e c t a p p l i c a t i o n so f s h a p ea n a l y s i si n c l u d eb i o m e d i c a li m a g ea n a l y s i s ，m o r p h o m e t r y ，d a t a b a s e r e t r i e v a l ，m i l i t a r yt a r g e tr e c o g n i t i o na n dc o m p u t e rv i s i o n t h ef o c u so ft h i s t h e s i si so nt h ef i e l do fs h a p eb a s e dl e a fi m a g e sr e t r i e v a la n dc l u s t e r i n g ，t h e i r e f f e c t i v e n e s sa r ee v a l u a t e da n dv a l i d a t e dv i as o m ee x p e r i m e n t s o n eg o a lo ft h i st h e s i si st op r e s e n tv i s u a ld e s c r i p t o r st h a tc h a r a c t e r i z et h e l e a fs h a p e s n u m e r o u ss h a p er e p r e s e n t a t i o na n dd e s c r i p t i o nt e c h n i q u e sh a v e b e e nr e v i e w e di nt h et h e s i s t h em a j o r i t yo ft h em e t h o d sp r e s e n t e dc o n s i d e r t h es h a p eu s i n gf o u r i e rd e s c r i p t i o no ft h eb o u n d a r yl i n eo ft h eo b j e c t f o rt h i s k i n do fs h a p ed e s c r i p t i o n ，an u m b e ro fc o n t o u r - b a s e ds h a p er e p r e s e n t a t i o n a n dd e s c r i p t i o nt e c h n i q u e sa r es t u d i e du s i n gas t a n d a r dm e t h o d o l o g y i n c l u d i n gc o n v e r g e n c es t u d y ，r e t r i e v a le f f e c t i v e n e s sa n dc o m p a r i s o n a f t e rt h a t ， ac e n t r o i dd i s t a n c eh i s t o g r a m sm e t h o di sp r o p o s e dt or e p r e s e n tt h es h a p e t h i ss i m i l a r i t yo ft w os h a p e sa r ej u d g e db yc o m p a r i n gt h en u m b e ro fd i s t a n c e s nc o r r e s p o n d i n gr a n g e s r e t r i e v a lr e s u l t ss h o wt h a tu s i n gc o m b i n e df e a t u r e s o u t p e r f o r m st h a nas i n g l ef e a t u r e a n o t h e rg o a li st op r e s e n tt o o l st h a tc l u s t e ri m a g e sa c c o r d i n gt ot h e s h a p e so ft h e i rb o u n d a r i e s ，t h ep u r p o s ei st oi m p r o v ed a t a b a s es e a r c h e si n s y s t e m sw i t hs h a p e b a s e dq u e r i e s f i r s t ，c l a s s i c a lc l u s t e r i n ga l g o r i t h m so n e u c l i d e a ns p a c e sa r er e v i e w e d ；t h e ya r ew e l l - r e s e a r c h e da n dg e n e r a l l yf a l l i n t ot w om a i nc a t e g o r i e s ：p a r t i t i o n a la n dh i e r a r c h i c a l a n dt h e n ，as t o c h a s t i c s i m u l a t e da n n e a l i n gb a s e dc l u s t e r i n ga p p r o a c hi s p r o p o s e d t h em e t h o d m i n i m i z e st h ec l u s t e r i n gc o s tu s i n gam a r k o vc h a i ns e a r c hp r o c e s so l lt h e c o n f i g u r a t i o ns p a c e t h eb a s i ci d e ai st os t a r tw i t hac o n f i g u r a t i o no fkc l u s t e r s a n dt or e d u c et h ev a l u eo fc o s tf u n c t i o nb yr e a r r a n g i n gs h a p e sa m o n g s tt h e c l u s t e r s t h er e a r r a n g e m e n ti sp e r f o r m e di nas t o c h a s t i cf a s h i o nu s i n gt w o k i n d so fm o v e s f i n a l l y ，ah i e r a r c h i c a lo r g a n i z a t i o nm e t h o di sp r o p o s e dt o o r g a n i z ed a t a b a s e so fs h a p e st h a ta l l o w sf o re f f i c i e n ts e a r c h e s k e y w o r d s ：c b i r ；s h a p er e t r i e v a l ；s h a p ec l u s t e r i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：弓勿9 厨移硪 劲p 6 年6 月曰 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( 乃 ( 请在以上相应括号内打“”) 作者签名：动髓磙 导师签名：1 日期：年g 月争日 日期：僻钿垆日 f 第一章引言 第一章引言 随着数字信息技术的快速发展以及互联网的不断膨胀，人们面对的数字多媒 体信息与同俱增。各类数字图书馆收集了大量的不同种类的数字信息，不仅包含 文本的信息，还包含了大量的多媒体信息( 图像、视频、音频等) 。因此，为了 更好地利用这些信息，就必须开发从大量信息中检索的技术，以满足用户不断增 长的需求，特别是从互联网进行检索的技术。 一般来说，数字图书馆由一个或多个数据库组成。数据库以及数据库的信息 在目前的信息技术领域中具有极高的重要性。不同种类的数据库包含了与人们生 活密切相关的各种信息，另一方面，人们也创建包含多媒体信息个人数据库，例 如照片、音乐或是视频。 信息的检索包括存储、组织、检索和表现四个部分 1 】。一次成功的检索就是 用户用特定的方式表示出其需求，然后被检索系统所“理解”。因此，一个实质 的问题就是如何定义用户的需求并且对它做出反应。一个传统的方法是利用关键 词( k e y w o r d ) 检索所需的信息或文档。这种方法仍然被利用在文本检索，例如学 术文献这种能够用一组关键词来表示的信息。另一方面，利用有限的关键词进行 检索常常会造成结果信息的缺失。这个例子说明了检索系统的最本质的问题：如 何发现所有用户感兴趣的信息。另外一个与之相同重要的问题是：如何保证检索 的结果都是用户感兴趣的。 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 ) 。 k a t o 2 最早提出了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 的范围主要包 括视觉特征提取，图像数据库索引，相似度计算，语义分析和系统设计等。从 1 9 9 0 年代起，许多研究者致力于这个课题的工作，出现了大量的研究系统和商 业应用【3 】 4 】 5 6 】【7 】【8 】。 最著名的商业c b i r 系统是i b m 开发的q b i c 9 1 0 。它提供了基于颜色， 纹理或是形状的检索。查询通过选择一张示例图片或者是绘制草图来进行。特征 通过用r + 树来改进检索效率。其它著名的商业系统诸如v i r a g e 1 1 和雅虎的 e x c a l i b u r 1 2 1 3 。p h o t o b o o k 1 4 是m i t 开发的具有代表性的c b i r 研究系统。 与q b i c 相同的是，数据库中的图像通过颜色，形状，纹理或是其它特征进行表 示。并且，通过这些特征能够重建图像的重要部分。这个系统提供了纹理，形状 和人脸的查询。另外著名的研究系统有m a r s 1 5 。这个系统由i l l i n o i s 大学的 h u a n g 等人开发。它把每一幅图像中的对象用一系列特征表示，使用不同的相似 度度量方法来比较查询，并且通过用户的反馈用来调整特征的权重。 目前，c b i r 的研究主要集中在三个主题：特征提取，高效的索引以及用户 界面三个方面。 1 特征提取。图像的特征主要包括简单特征和语义特征。简单特征主要包 括颜色，纹理，形状和空间关系等等，它们能够被自动地或半自动地提 取。而语义特征提供了图像在不同层次的抽象表示。但是，语义特征很 难自动提取，只能通过人工或者是半自动地提取。在特定的应用中可以 第一章引言 利用一种或多种特征。一旦特征被提取，检索过程就能转化为在特征之 间计算相似度。 2 有效率的索引。为了保证查询和搜索过程的高效性，图像数据库必须组 织成高效的数据结构。常用的数据结构有k - d - t r e e ，r - t r e e 族，r * - t r e e ， q u a d t r e e 和g r i d f i l e 等等，每一种结构都有其优缺点。 3 用户界面。在视觉信息系统中，用户的交互常常扮演着一个重要的角色。 用户界面包括了查询处理器和浏览器，用来提供交互式的图像工具和机 制，以便查询和浏览数据库。一般的用户界面提供的查询机制有：通过 关键词查询，通过草图查询，通过示例查询，通过属性浏览，特征选择 及权值设定，检索反馈。 在c b i r 系统中，主要目标是从图像数据库中提取出与用户提供的图像最相 似的那部分，也就是尽可能精确地对用户的要求做出反应。为了实现这些要求， 检索出的结果必须和查询图像在内容上相关，而只有在提取出的特征能够反映图 像内容的时候，这才成为可能，所以，特征的选取对于图像检索至关重要。另外， 图像特征的计算复杂度要尽可能低，特别是对于在线检索系统和大型图像数据 库。与c b i r 相关的研究领域还有图像分析和模式识别。 最后，应用于图像检索的特征选择和图像分类非常相似，这就意味着可以通 过对图像进行分类的实验来测试特征的性能。 1 2 本文的目标 目前的基于内容的图像检索系统应用在了许多不同领域，例如医疗图像，卫 星照片，以及新闻图片等等。本文的研究主要集中在植物叶片图像检索，植物叶 片图像检索对于医疗、教育、环保等领域均有重要意义。就目前而言，拿着一副 未知的植物图片在互连网上进行检索时，会发现现有的检索引擎均要输入名称才 可以查询，这时只能望着照片兴叹。 一个成功的例子足e t l 美术馆所用的a r t m u s e u m ，不需输入图片，可以 通过手绘物体大致外形来检索画像，因为如此，建立一个基于内容的植物叶子检 索系统是可行的。但是，植物图像的自动识别仍然有许多困难，例如，缺少合适 基于形状的植物叶子图像检索与聚类研究 的表示模型，植物图像的多样性，图像预处理等等，这些都会造成特征的缺失。 由于植物叶子大多偏绿色，所以用颜色信息来检索是不大适合的。从视觉上来说， 形状是区别不同植物叶子的最显著特征，形状的形态变化是最为丰富，所以本文 采用叶子形状来作为检索特征。本文中主要研究和对比基于傅立叶变换的形状描 述方法以及基于形状的图像特征聚类方法，并把这些方法应用到植物叶子形状检 索系统中。 1 3 本文的贡献 本文的主要贡献总结如下 1 3 1 基于傅立叶变换的形状描述研究 基于物体轮廓的形状描述子是一个重要的形状表示技术。本文回顾了基于傅 立叶变换的形状表示方法，对一系列的傅立叶描述方法进行了研究，包括收敛性 分析，检索性能以及对比研究。 1 3 2 基于彤状直方图的形状表示 本文提出了用形状直方图方法结合质心距离傅立叶方法来提高检索性能，实 验结果表明，使用两种特征的结合能获得更好的检索性能。 1 3 3 基于形状特征的聚类方法 本文提出了一种新的基于图像轮廓的层次聚类算法。该方法是结合模拟退火 算法把形状按照特征进行聚类以降低检索开销，在此基础上提出了一种利用形状 均值对形状数据库进行层次化组织的方法 1 3 4 检索系统的实现 本文实现了一个基于n e t 和m i c r o s o f ts q ls e r v e r 2 0 0 5 的图像检索系统。该 系统可用于特征提取，图像检索以及聚类的分析。 4 第一章弓i 言 1 4 本文的内容 第一章主要介绍了本文研究的背景、目标以及本文的主要贡献。 第二章开始部分介绍了基于图像检索的基本原理以及工具。包括图像数据库 的概念，特征提取，相似度计算，图像数据库索引以及检索性能的分析方法。接 下来回顾了描述图像形状的一般方法，总结了形状描述方法的分类，介绍了基于 轮廓和基于区域的两种方法，并进行了对比。 第三章研究了基于傅立叶变换的形状描述。首先，对不同的傅立叶描述子进 行了对比分析，包括对比不同傅立叶特征的收敛性、检索性能以及傅立叶描述子 维度的确定。最后，提出了一种基于直方图的方法与傅立叶描述方法进行多特征 结合，并取得了较好的实验结果。 第四章研究了基于形状特征的聚类算法，该研究的主要目的是改进检索效 率。这一章节首先回顾了聚类分析的背景，接下来提出了一种基于模拟退火的形 状聚类方法以及对形状图像数据库进行层次化组织的方法。 第五章是对本文的总结以及对该研究方向的展望。 第二章基于形状的图像检索基本原理 第二章基于形状的图像检索基本原理 研究基于内容的图像数据库索引，主要目的是能够通过自动描述图像来对比 图像的视觉内容，并且定义图像之间的相似度，这就使得对整个图像数据库按照 视觉特征分割成为可能。然而，更有应用价值的是从数据库中检索出与需求相关 的内容，也就是基于内容的图像检索。这一部分主要介绍基于内容图像检索的基 本原理。 2 1 图像数据库索引和组织 早在1 9 7 0 年代，图像数据库的索引就被作为一个研究的课题 5 】。在早期的 解决方案中，图像数据库完全由关键词( k e y w o r d ) 进行索引。【1 6 使用关键词来描 述卫星图片。另外，有两篇文章对比了基于关键词的索引方法。【1 7 对比了早期 的技术，而 1 8 对更近期的索引技术进行了总结。但是，基于关键词的方法有 许多严重的缺陷：大量的手工标注和标注人的主观性。然而，随着计算资源的增 加和数字图像数据库的不断增长，从1 9 9 0 年代开始手工标注的方法开始逐步被 自动的方法所取代，自从那时起，基于内容的图像索引和检索开始被大量研究。 在1 9 9 0 年代中期，最早的商业应用开始出现，包括q b i c 9 1 0 和p h o t o b o o k 1 4 ， 其它著名的基于内容图像索引和检索系统包括p i c t o s e e k 1 9 ，v i s u a l s e e k 2 0 ， v i r a g e 11 ，n e t r a 2 1 ，m a r s 2 2 ，p i e s o m 2 3 茅t m u v i s 2 4 1 。另外， 5 6 1 1 7 1 z r j 各 种c b i r 系统进行了对比研究。 在基于内容图像索引和检索领域，手工标注图像内容描述的方法被自动提取 图像视觉特征的方法所取代。图像数据库索引的目的是利用一个特征向量f 来表 达图像i 的内容。视觉特征p 从图像中提取。在数据库索引中，图像i j 的特征向量 f i 表示为： z 。= p l ，p 2 ，p 。) 其中，n 是向量的长度。这个n 维特征向量可以被认为是n 维特征空间中的 一个的点。 基于形状的植物叶了- 图像检索与聚类研究 2 2 基于内容图像检索关键技术 2 2 1 图像特征的提取 图像特征的提取与表达是基于内容的图像检索技术的基础。从广义上讲，图 像的特征包括基于文本的特征( 如关键字、注释等) 和视觉特征( 如色彩、纹理、 形状、对象表面等) 两类。由于基于文本的图像特征提取在数据库系统和信息检 索等领域中已有深入的研究，接下来主要介绍图像视觉特征的提取和表达。视 觉特征又可分为通用的视觉特征和领域相关的视觉特征。前者用于描述所有图像 共有的特征，与图像的具体类型或内容无关，主要包括色彩、纹理和形状；后 者则建立在对所描述图像内容的某些先验知识( 或假设) 的基础上，与具体的应 用紧密有关，例如人的面部特征或指纹特征等。由于领域相关的图像特征主要属 于模式识别的研究范围，并涉及许多专业的领域知识，所以在此只考虑通用的视 觉特征。对于某个特定的图像特征，通常又有多种不同的表达方法。由于人们主 观认识上的千差万别，对于某个特征并不存在一个所谓的最佳的表达方式。事 实上，图像特征的不同表达方式从各个不同的角度刻画了该特征的某些性质。 2 2 1 1 颜色特征 颜色特征是在图像检索中应用最为广泛的视觉特征，主要原因在于颜色往往 和图像中所包含的物体或场景十分相关。此外，与其他的视觉特征相比，颜色特 征对图像本身的尺寸、方向、视角的依赖性较小，从而具有较高的鲁棒性。 面向图像检索的颜色特征的表达涉及到若干问题。首先，需要选择合适的颜 色空间来描述颜色特征；其次，要采用一定的量化方法将颜色特征表达为向量的 形式；最后，还要定义一种相似度( 距离) 标准用来衡量图像之间在颜色上的相 似性。 颜色直方图是在许多图像检索系统中被广泛采用的颜色特征。它所描述的是 不同色彩在整幅图像中所占的比例，而并不关心每种色彩所处的空间位置，即无 法描述图像中的对象或物体。颜色直方图特别适于描述那些难以进行自动分割的 图像。 7 第二章基于形状的图像检索基本原理 当然，颜色直方图可以是基于不同的颜色空间和坐标系。最常用的颜色空间 是r g b 颜色空间，原因在于大部分的数字图像都是用这种颜色空间表达的。然 而，r g b 空间结构并不符合人们对颜色相似性的主观判断。因此，有人提出了 基于h s v 空间、l u v 空间和l a b 空间的颜色直方图，因为它们更接近于人们 对颜色的主观认识。其中h s v 空间是直方图最常用的颜色空间。它的三个分量 分别代表色彩( h u e ) 、饱和度( s a t u r a t i o n ) 和值( v a l u e ) 。 2 2 1 2 纹理特征 纹理特征是图像的一个重要属性，是物体表面的结构模式。关于纹理的定义 和纹理的量化方法有很多，目前纹理分析的方法基本可以分为统计法、结构法、 模型法和空间，频率域联合分析法等四类。基于统计的方法是对图像中的颜色强 度的空间分布信息进行统计，包括共生矩阵法、l a w s 纹理能量法等；基于结构 的方法将重点放在分析纹理元之间的相互关系和排列规则上；基于模型的方法假 设纹理按某种类型分布，例如m a r k o v 随机场模型、分形模型等；基于空间频率 域联合分析法主要包括g a b o r 变换法和小波变换法。 由于纹理特征对模式识别和计算机视觉等领域的重要意义，下文介绍两种在 基于内容的图像检索中所常用的纹理特征模型。 1 t a m u r a 纹理 基于人类对纹理的视觉感知的心理学的研究，t a m u r a 等人提出了纹理特征 的表达【2 6 】。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 7 。 2 小波纹理模型 小波变换( w a v e l e tt r a n s f o r m ) 也是一种常用的纹理分析和分类方法【2 8 】【2 9 】。小 波变换值的是将信号分解为一系列的基本函数y ，。( 功。这些基本函数都是通过对 母函数杪f 的变形得到，如下所示： 。( x ) = 2 - , 2 y ( 2 一“一h ) ( 2 1 ) 其中m 和1 3 是整数。这样，信号厂( x ) 可以被表达为： 基于形状的植物叶子图像榆索与聚类研究 ，( x ) = c 。矿。( x ) ( 2 2 ) 小波变换表示的纹理特征可以用每个波段的每个分解层次上能量分布的均 值和标准方差。根据文献【3 0 】中所作的性能对比，不同的小波变换在对纹理分析方 面没有很显著的差别。 2 2 1 3 形状特征 形状特征将在2 4 节重点介绍。 2 2 3 相似度度量 为了在图像数据库中进行检索或分类的操作，就必须在图像与图像之间定义 相似度和相异度。这个问题就能转化为评估两个特征向量之间的距离。一般来说， 基于形状的图像检索就是计算形状特征之间的相似度( s i m i l a r i t y ) 。因此，基于形 状的图像检索主要分为两步，特征提取以及计算特征之间的相似度。【3 l 】提出了 针对不同视觉描述子的相似度计算公式。3 2 回顾了基于形状描述子的相似度度 量方法。 设a ，b 为两个向量，它们之间的距离可以定义为： d 。= 厶( 4 ，曰) ( 2 3 ) 其中，丘为距离函数。 对于基于形状的图像检索来说，图像的特征通常是一个n 维向量，或者可以 看成n 维空间中的一个点。一旦通过特征向量对数据库中的图像进行索引，图 像的检索结果就是由查询图像和数据库中的图像的相似度所决定，也就是由特征 向量之间的距离所决定。而且，距离的计算应当表现出人类的感知，也就是说， 相似的图像之间距离较小而不同的图像之间距离较大。因此，对于一种形状特征 来说，检索精度越高就意昧着距离计算方法越好。当然，对于在线检索系统来说， 距离计算方法的计算复杂度应当越低越好。过去的研究者提出了许多计算相似度 的方法，包括c i t y c l o c k 距离 3 3 3 4 】，z2 统计距离 3 5 】，二次距离【3 6 】【3 7 和 m a h a l a n o b i s 距离 3 4 3 8 1 。在这一节中，我们讨论和评价不同的距离计算方法， 目的是发现合适的相似度计算方法来用于不同形状描述子的对比研究。 相似度计算方法通常被定义成一个度量距离。接下来主要讨论主要的几种常 9 笙三兰苎翌坚盟鬯堡丝窒兰查堕堡 一 用的相似度计算方法。 2 2 3 1 距离度量空间 基于向量空间模型，采用几何距离作为相似度度量的函数通常需要满足距离 公理的非负性，自反性，对称性和三角不等性等条件 3 9 。 非负性：d ( a ，鳓20 自反性：d ( a ，b ) = 0 当且仅当a 2 b 对称性：d ( a ，b ) = d ( b ，4 ) 三角不等性：d ( 0 ，b ) + d ( a ，c ) d ( b ，c ) 2 2 3 2m l n k o w s k i 距离 许多相似度计算方法都是基于两个向量之间的工，距离。工，距离，也就是 m i n k o w s k i 距离，定义为。 n - 1 l v ( a ，6 ) = ( 1 4 ，一玩1 9 ) “ ( 2 t i = 0 当p = l 时，就得到了t 距离，也q 做m a n h a t t a n 或者是c i t y - b l o c k 距离。 当p = 2 时，就得到了上：距离，也就是通称的欧拉距离： 三2 ( 口，6 ) =1 ( a 。一6 ；) 2 vj = o 欧拉距离是最著名的距离公式， 度量中 4 0 】 4 1 】 4 2 】。 当p _ ，得到： 三。( 口，= m 。a 。x 。 l a r 一6 f 1 ) 2 2 3 3 余弦距离 并且被普遍用于傅立叶形状描述子的相似度 ( 2 6 ) 余弦距离计算向量在方向上的差异，而不考虑向量的长度，余弦距离由两个 向量之间的夹角决定。 d 。( 岛= 1 - e o s o = 1 - 丽a b 图2 1 举例说明了在二维空间余弦距离和两种m i n k o w s k i 距离。可以看出， 欧拉距离同时考虑了向量之间的角度和向量长度的差异，而余弦距离只计算角度 的差异。而l l 距离计算了每一个维度上的距离。 基于形状的植物叶了图像检索与聚类研究 图2 t ( a ) 欧拉距离；( b ) 余弦距离；( e ) c i t y b l o c k 距离 2 2 3 4 直方图相交 假设q 和d 是两个含有n 个b i n 的直方图，则它们之间的相交距离表示为： e m i n ( q j ，d ) h ( q ，d ) = 旦f 一 ( 2 8 ) y d 。 j = l 2 2 3 5 二次式距离 对于基于颜色直方图的图像检索来说，二次式( q u a d r a t i c f o r m ) 距离已经被 证明比使用欧拉距离或直方图相交距离更为有效。原因在于这种距离考虑到了不 同颜色之间存在的相似度。两个颜色直方图a 和b 之间的二次式距离可以表示为： d q o a ( 日，b ) = ( a 一6 ) a ( a 一6 ) 这种方法通过引入颜色相似性矩阵a ，使其能够考虑到相似但不相同的颜色 间的相似性因素。其中，a = 【】，c 。表示直方图中下标为i 和j 的两个颜色b i n 之间的相似度。颜色相似性矩阵a 可阻通过对色彩心理学的研究 4 3 】中获得。与 此等价的另一种做法是先对颜色直方图进行求闭包操作，使每个颜色b i n 的值都 受到来自它相邻颜色b i n 的影响。这样，颜色直方图本身就包含了不同颜色之间 的相似度因素，因此可以直接地使用欧拉距离或直方图相交距离。这种对直方图 预处理的方法的好处在于在检索过程中相似度的代价较小。 2 2 3 6g a h a i a n o b is 距离 如果特征向量的各个分量间具有相关性或者具有不同的权重，可以采用 m a h a l a n o b i s 距离来计算特征之问的相似度。m a h a l a n o b i s 距离的数学表达式为： d 。咖j = ( 口一6 ) c 。1 ( d 一 ( 2 9 ) 第二章基于形状的图像检索基本原理 其中c 是特征向量的协方差矩阵。 当特征向量的各分量问没有相关性，m a h a l a n o b i s 距离还可以进一步简化， 因为这时只需要计算每个分量的方差c ；。简化后的m a h a l a n o b i s 距离如下所示： 氐一，：杰垃兰 ( 2 1 0 ) 对某个图像特征选择一种合适的相似度衡量方法是获取满意的检索效率的 重要保证。然而，更为重要和困难的是确定不同特征之间或是同一特征的不同分 量之间的权重。 2 2 4 多维图像特征的索弓 为了使基于内容的图像检索技术能够扩展到应用于大规模的图像库，我们必 须采用有效的多维索引技术，存在的难题有两个方面： 1 高维数：通常情况下，图像特征向量的维数的数量级是l o 。 2 非欧拉的相似度度量：由于欧拉度量方法可能无法有效地模仿人类对视 觉内容的所有感知，经常需要采用其它的相似性度量方法，例如直方图的交、余 弦、相关性等非欧拉的相似度衡量方法。 要解决上述这些问题，可行的途径是首先采用维数缩减技术降低特征向量的 维数，然后使用适当的多维索引技术( 通常能够支持非欧拉的相似度衡量方法) 。 2 2 4 1 维数缩减技术 虽然图像特征向量的维数非常高，但内在必需的维数并不高 4 6 3 。因此我们 在使用任何索引技术以前，最好首先进行维数缩减。常用的两种缩减方法是 k a r h u n e n l o e v e 变换( k l t ) 和按列聚类。 k l 变换和它的变种在面部识别、特征图像、信息分析和主成分分析等领 域内的应用已经得到了深入的研究。n g 和s e d i g h i a n 4 7 曾采用特征图像的方 法来实现维数缩减，f a l o u t s o s 和l i n 在 4 8 】中提出了用于维数缩减的k l t 快 速逼近算法。研究结果表明，大多数的实数集合( 视觉特征向量) 可以大量的缩 减维数，并且对检索效果不会产生明显的影响。c h a n d r a s e k a r a n 4 9 】等开发了低 秩奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 更新算法，它能够被高效而稳定 1 2 基于形状的植物叶子图像检索与聚类研究 地应用k l 变换。由于图像检索系统是一个的动态系统，不断会有新的图像加入 到系统中，索引结构也需要相应地进行动态更新。奇异值分解算法就提供了这 样一种动态更新索引结构的工具。 除了k l 变换，聚类是另一种实现维数缩减的有力工具。聚类技术被广泛 地应用于模式识别、语音分析、信息检索等领域。通常的聚类方法是将相似的对 象( 如模式、信号和文档等) 聚合在一起，以实现识别或分组等功能，即所谓的 按行聚类。同样，聚类也可以按列进行，从而缩减特征空闻的维数【5 0 】。实验表 明这种方法非常简单有效。 值得一提的是，盲目的缩减维数是非常危险的，匿舞细暴维数被缩减到必要 的维数以下，图像特征的信息就有可能丢失。为了避免塞嚣豹维数缩减，事后的 验证阶段是十分必要的。在众多的验证方法中，f 妯积渤懑斌【5 i 】可以提供有效 的监督。 2 2 4 2 多维索引技术 尽管经过了维数缩减，图像特征向量的缝赛僻然竣藏t 西此我们需要选择一 个合适的多维索引算法来为特征向量建立索引。有至个研究矮域对多维索引技术 做出过贡献，它们分别是计算几何、数据库管理系统和模式识别。现在较流行的 多维索引技术包括b u c k e t i n g 成组算法、k - d 树、优先级k - d 树、四叉树、k - d b 树、h b 树、r 树以及它的变种r + 树和r 串树等等。除了以上几种方法，在模式 识别领域有广泛应用的聚类和神经网络技术也是可能的索引技术。多维索引技术 的历史可以追溯到2 0 世纪7 0 年代中期。就在那个时候，诸如c e l l 算法、四 叉树和k d 树等各种索引技术纷纷问世，但它们的效果都不尽人意。在g i s 和 c a d 系统对空间索引技术的需求推动下，g u t t m a i l 于1 9 8 4 年提出了r 树索引 结构【5 2 】。在他的工作的基础上，许多r 树的变种被开发出来，例如s e l l i s 等 提出了r + 树【5 3 】，g r e e n e 也提出了他的r 树的变种【5 4 】。在1 9 9 0 年，b e c k m a n 和k r i e g e l 提出了最佳动态r 树的变种一r + 树【5 5 】。然而，即便是甜树也无法 处理维数高于2 0 的情况。 文献【4 6 【4 7 】中给出了对各种索引算法的综述和对比。其中w h i t e 和j a i n 【4 6 】 的研究目标是提供通用的或者领域相关的索引算法。受到k - d 树和r 树的启 发，他们提出了v a mk - d 树和v a m s p l i tr 树。实验表明v a m s p l i tr 树具有 第二章基于形状的图像检索基本原理 最优的算法效率，但失去了r 树所具有的动态特点。在 4 7 q b ，n g 和s e d i 曲i a n 提出了一种用于图像检索的三阶段检索技术，即维数缩减、现有索引算法的评估 和选择、对所选索引算法的优化。 考虑到几乎所有的树状结构索引技术都是为传统的数据库查询( 点查询和范 围查询) 所设计，而并非为了图像检索所设计，因此有必要探讨能够符合图像 检索要求和特点的新的索引结构。t a g a r e 在 5 6 中研究了这样的技术，他提出了 一种树结构的调整方法，能够通过删减妨碍相似度查询效率的树节点来优化树结 构。 上述的方法仅仅讨论了如何对图像检索中的高维数据进行索引，而没有涉及 到非欧拉的相似度度量问题。图像检索中的许多相似度计算方法都不是基于欧拉 距离的，比如颜色直方图的求交。在这个方面上有两种很有希望的技术，分别是 聚类技术和神经网c h a r i k a r 等提出了适用于动态信息检索增加的聚类技术【5 7 】。 这种技术具有动态的结构，能够处理高维数据，同时支持非欧拉的相似度度量。 在 5 8 1 中，r u i 和c h a k r a b a r t i 等在速度、精确性和对非欧拉相似度度量的支持等 方面进一步扩展了这种技术。在【5 9 】中，z h a n g 和z h o n g 提出了用自组织 ( s e l g o r g a n i z a t i o nm a p ，或s o m ) 神经网构造树状索引结构的方法。s o m 的 好处在于具有无人监督的记忆能力、动态聚类功能和支持任意的相似度度量。通 过在纹理集上进行的实验表明，s o m 是一种很有希望的索引技术。 2 3 性能分析 为了在图像检索和分类时评价不同的视觉特征，就必须在它们之间进行性能 的比较。而性能好坏基于图像数据库的检索和分类实验。 2 3 1 检索的性能 当评价基于内容图像检索的性能时，可以利用一般数据库检索的验证方法， 最经常使用到的方法是计算其召回率( r e c a l l ) 1 。信息检索的过程能通过以下方法 建模。设数掘库中用户所感兴趣的集合r ，如图2 2 ，集合r 中对象的个数为恻。 1 4 基于形状的植物叶子躅像检索与聚类研究 当用户进行一次检索操作时，返回的结果集合a 包含h 个对象。集合a 和r 的 交集定义为r a ，其中对象的个数为i r a l 。集合r a 包含了返回的结果中用户感兴 趣的部分。以这些