（计算机应用技术专业论文）二维形状分析及其在图像检索中的应用.pdf

二维形状分析及其在图像检索中的应用摘要随着多媒体技术、互联网业以及数字成像技术的飞速发展，在人们的日常生活中、在教育、军事、科研、工业等许多行业中都产生了大量的数字图像，对图像的使用越来越多、范围越来越广。在这种情况下，迫切需要一种对数字图像进行有效的管理和检索的手段。基于内容的图像检索就是这为解决这一问题而出现的一个研究领域。在许多机器视觉系统中，图像是一种必不可少的输入信息，对图像进行处理和分析就成了机器视觉中的关键问题。针对这样的背景，本文研究了图像中目标形状的分析技术，并对利用形状特征进行图像检索进行了探讨。二维形状的傅立时描述符是形状分析中的一个代表性的方法，有许多不同的边界标记函数可以用来提取傅立叶描述符。本文对这种方法进行了深入的比较研究，分析了基于不同标记函数的傅立叶描述符的检索性能。针对皮革c a m 系统中的实际需要选择了一种适合于鞋样匹配的描述方法。提出了一种基于链码的傅立叶描述符，研究了这种描述符的归一化处理方法，并通过实验分析了它的性能。这种描述符具有很好的数据保持性，即能够很好的恢复形状。但是对于形状识别还有一定的缺陷。设计开发了一个基于内容的图像检索系统，该系统提供例子图像查询，可以根据图像的颜色、纹理和形状特征进行检索。该系统对图像检索系统的构建是一次有益的尝试。采用设计模式使得系统具有很好的扩展性和复用性。关键词：形状分析、链码、傅立叶描述符、形状索引、基于内容、图像检索二维形状分析及其在图像检索中的应用a sar e s u l to fa d v a n c e si nt h ei n t e m e t ，m u l t i m e d i at e c h n o l o g ya n dd i g i t a li m a g es e n s o rt e c h n o l o g y , t h ev o l u m eo fd i g i t a li m a g e sp r o d u c e di ne v e r y d a yl i f ea n db ye d u c a t i o n a l ，s c i e n t i f i c ，m a r t i a l ，i n d u s t r i a la p p l i c a t i o n si n c r e a s e dd r a m a t i c a l l yi nr e c e n ty e a r s t h ee f f i c i e n tm a n a g e m e n to ft h er a p i d l ye x p a n d i n gi m a g e sb e c a m ea nu r g e n tp r o b l e m c o n t e n t - b a s e di m a g er e t r i e v a l at e c h n i q u ew h i c hu s c sv i s u a lc o n t e n t st os e a r c hi m a g e sf r o ml a r g es c a t l ei m a g ed a t a b a s e sa c c o r d i n gt ou s e r si n t e r e s t s ，t h e nc a m et ob e i n ga n db e c a m ea na c t i v ea n df a s ta d v a n c i n gr e s e a r c ha r e a i m a g e sa r et h em o s ti m p o r t a n ti n p u ti nm a n ym a c h i n ev i s i o ns y s t e m s ，s ot h ea n a l y s i so fi m a g e si sak e yt e c h n o l o g yi nt h e s es y s t e m s t h ea b o v ei s s u e sf o r mt h eb a c k g r o u n do ft h i sp a p e gt h et h e s i sf o c u s e so n2 ds h a p ea n a l y s i st e c h n o l o g ya n di t sa p p l i c a t i o ni nc o n t e n t b a s e di m a g er e t r i e v a l m a n ys h a p er e p r e s e n t a t i o nm e t h o d se x i s t a m o n gt h e m ，m e t h o d sb a s e do nf o u r i e rd e s c r i p t o r s ( 1 7 1 3 ) a c h i e v ew e l lr e p r e s e n t a t i o n d i f f e r e n ts h a p es i g n a t u r e sh a v eb e e ne x p l o i t e dt od e r i v ef d s ，h o w e v e r , f d sd e r i v e df r o md i f f e r e n ts i g n a t u r e sc a nh a v es i g n i f i c a n td i f f e r e n te f f e c to nt h er e s u l to fr e t r i e v a l t h et h e s i sm a k e sac o m p a r a t i v es t u d yo nf o u r i e rd e s c r i p t o r sw i t hd i f f e r e n ts h a p es i g n a t u r e s s i n c ef r e e m a nc h a i nc o d ei sav e r yp o p u l a ra n di m p o r t a n tm e t h o di ns h a p ed e s c r i p t i o u t h et h e s i sc o m b i n e sc h a i nc o d ew i t hf o u r i e rs e r i e st h e o r ya n dp r o p o s e san e wf o u r i e rd e s c r i p t o rb a s e do nc h a i nc o d e s e x p e r i m e n t ss h o wt h a tt h i sm e t h o di sn o ts u i t a b l ef o ri m a g er e t r i e v a lb u th a sg o o dp e r f o r m a n c ei ns h a p er e c o n s t r u c t i o n t h et h e s i sd e v e l o p e dac b i rp r o t o t y p es y s t e mn a m e di s e a r c h t h es y s t e mp r o v i d e ss a m p l eb a s e dr e t r i e v a l u s e r sa r ef r e e l yt os e l e c tc o l o r , t e x t u r e ，s h a p ef e a t u r e s ，o rt h e i rc o m b i n a t i o ni nr e t r i e v a ls e s s i o n s s o m ed e s i g np a t t e r n sa r ed e p l o y e di nt h es y s t e md e s i g na n dd e v e l o p m e n tt om a k ei te x p a n s i b l ea n dr e u s a b l e s e v e r a lr e t r i e v a le x p e r i m e n t sa r ec o n d u c t e do ni s e a r c ha n dr e s u l t sa r eg i v e ni nt h et h e s i s k e y w o r d s ：s h a p ea n a l y s i s 、c h a i nc o d e 、f o u r i e rd e s c r i p t o r 、s h a p ei n d e x 、c o n t e n t b a s e d 、i m a g er e t r i e v a ll l声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果，也不包括为获得首都师范大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。1 引言1 1二维形状分析介绍1 引言形状作为图像的一个重要属性，在图像理解、图像识别、图像检索等领域中有着很重要的作用。二维形状分析就是分析图像中二维目标形状的技术。典型的形状分析应用有指纹分析、农产品检测等。在二维情况下，可以认为形状是定义在二维范围内的一条简单连接曲线位置和方向的函数【1 1 。“简单连接”是指曲线上任何一点至多有两个也属于该曲线的邻点。形状描述涉及到对一条封闭边界的描述或者对这条边界包围区域的描述。在图像中，一个目标可以由边界或者边界包围的区域来代表，则形状就是对这个目标的描述。形状描述的前提是从图像中把要分析的目标对象提取出来，这主要是图像分割的任务。目标提取出来之后，根据应用的需要来选择不同的描述途径。王润生教授在f 1 】中把形状描述任务分为两类：识别和寄存。在识别应用情况下，形状描述符只要包含足以区分类似形状的信息就可以，不必由这些参数复原出原来的目标，在这种应用情况中，当目标尺寸、位置和方向发生变化时，描述目标形状的参数应当保持不变。在寄存应用情况下，常要求数据压缩、并且能从简化的形状描述符恢复出初始形状，这类描述称为数据保持描述。根据描述的对象是目标边界还是目标区域可以把形状描述算法分为两大类：基于轮廓的描述方法和基于区域的描述方法。这两类算法将在第三章介绍。上面介绍的形状分析都是针对单个目标的形状进行分析，然而在图像检索等应用中，由于图像内容很复杂，从中提取出目标比较困难，而且不同的人对图像内容的理解具有主观性，因此很难对复杂的图像进行目标分割与提取。这时候，只针对单个目标的描述算法并不太适合于复杂图像的检索。这时候就需要一种能够从整个图像直接提取形状特征的方法，即全局形状描述方法。由于边缘是图像形状的一种反映，因此，很多学者提出了通过边缘来描述图像全局形状特征的方法( 2 】。其中的代表性方法有小波模极大值和尺度矩方法【2 】、多尺度趋率与相位直方图方法f 3 】等。1 2基于内容的图像检索随着信息技术的发展、i n t e r a c t 的迅速普及，人们在日常生活中产生了大量的数字图像，也越来越多的使用图像来进行交流。同时，在科学研究、教育、工二维形状分析及其在图像检索中的应用业等许多领域里也涌现出了大量的数字图像。高速的处理器、大容量的存储设备为这些图像的存储提供了基本的保障，而怎样对这些数量庞大的图像进行有效的管理和检索就成为一个亟待解决的问题。图像检索( i m a g er e t r i e v a l ) 就是在这种情况下产生的一种技术。所谓图像检索就是从大量的图像中检索出用户所需要的图像。图像检索是近年来海量信息处理已经面临的瓶颈【4 】，它已经成为信息科学领域里的一个热点问题，引起了国内外许多研究机构以及一些大的信息企业的关注。图像检索经过3 0 多年的发展，已经从传统的图像检索发展到了“基于内容的图像检索”阶段。国际上很多学者提出了许多检索技术，也开发很多的检索系统。图像检索是一个多学科交叉的研究领域，它涉及到数字图像处理、机器视觉、模式识别、信息理论、人工智能、数据库以及视知觉等许多的学科，它的进一步发展需要这些领域的学者们的大力合作以及政府、企业的大力支持。本小节将介绍图像检索的发展历史、基本原理、应用领域，并介绍典型的基于内容的图像检索系统的构成和一些著名的基于内容的图像检索系统。分析基于内容的图像检索目前存在的主要问题。1 2 1 图像检索的发展概况图像检索的发展大致可以分为三个阶段：第一个阶段：基于文本方式的检索【4 】【5 】。早在7 0 年代，数据库专家就开始研究如何对图像数据库进行有效的管理，这时候主要采用关系数据库中的检索技术，并利用操作系统提供的文件系统支持，对图像文件进行管理与检索。其主要方法是对图像文件建立文本描述，形成关键词，然后在图像文件和图像关键词之间建立联系，在检索时由用户提交关键词，数据库管理系统根据关键词查找相应的图像文件返回给用户。后来数据库技术取得了很大的发展，许多数据库系统都开始支持二进制大对象( b l o b ) 这为非文件方式的图像存储提供了一种手段。这时候对图像的管理仍然是在b l o b 与图像关键词之间建立联系，而且由于直接在数据库中访问图像的操作比较复杂，因此在数据库中以b l o b 来管理图像的方法并没有真正应用起来。这一阶段的检索方式面临的问题有两个方面：一是人工对图像进行文本标注费时费力使得建造图像库的成本非常高，而且不利于系统的扩充。第二个问题是一幅图像的内容很难用几个关键词来表达，不同人对同一幅图像的理解也可能千差万别，这就导致检索的效果非常差。由于存在着这样一些问题，许多学者开始探讨直接利用图像的视觉内容来进行检索，这就发展到了第二个阶段。1 引言第二个阶段：基予内容的图像检索( c o n t e n tb a s e di m a g er c t r i e , c a lc b i r ) 。9 0 年代初【5 1 【q 【7 】，随着i n t c r n e t 的普及和数字成像技术的发展，在科学研究、教育、医疗、工业等许多领域里都产生了大量的数字图像，传统的图像管理与检索技术的问题越来越来严重，这就催生了基于内容的图像检索技术。基于内容的图像检索，就是从图像库中查找含有特定物体的图像 8 】。它主要通过图像处理与分析技术，分析图像的视觉特征比如颜色、纹理、形状以及空间布局，根据这些特征来检索图像c b 瓜主要包括以下几个方面的技术：特征提取、特征描述、特征索引、相似性度量。特征提取采用图像处理技术分析图像的内容，提取出反映视觉信息的特征用来代表图像。特征描述是采用某种合适的方式来描述图像的特征，通常采用特征向量来描述，由于图像分析的结果会产生大量的特征数据，因此特征向量通常维数很高。特征索引对高维特征向量进行降维并进行高效的索引，以提高检索的效率。相似性度量通过对图像特征之间的某种度量来衡量图像之间的视觉相似性。这些过程都可以由计算机自动完成，这与基于文本方式的检索相比是一个非常大的优势。这一阶段早期研究人员主要关注的问题是用什么样的特征可以提高检索效果，随着研究的深入，人们发现仅仅研究图像特征是不够的，因为图像的特征都是底层的特征，它与人对图像的理解之间存在着很大的鸿沟【4 】【9 】。计算机认为相似的图像对于人来说却有可能是完全不同的。为了解决这一问题，研究人员引入了在文本检索中使用的相关反馈技术。这一技术的主要思想是让用户对图像的理解也反映到检索系统中，让用户能够向检索系统反馈自己对图像的理解，检索系统内部根据这些反馈进行参数调整，从而改善检索效果f 2 】【9 】 1 0 】。相关反馈采用的参数调整方法般分为查询调整( q u e r yr e f m e m e n t ) 和相似性度量调整( s i m i l a r i t ym e a s l l r e m e n tr e f i n e m e n t ) 9 1 。用户在一次查询中，把查询到的图像分成相似的和不相似的两类，这两类结果分别作为正反馈和负反馈提交给系统，系统根据这些反馈修改查询向量( 查询调整) 或者调整特征向量的权值，使得再次查询的结果更接近于正反馈，丽远离负反馈，从而改善检索效果。这一阶段的c b i r 技术吸引了国际上许多研究机构、政府组织、公司的关注，研究人员发表了大量的研究论文，一些大学研究机构和公司也开发出了许多c b i r 系统。这一阶段的主要闯题是：图像的底层特征与图像的高层语义特征之间存在着巨大的鸿沟，现在还没有找到一种能够在这两者之问建立对应关系的方法。而且没有一种对任何类型的图像( 比如自然风景图像与商标图像) 都能达到很好的检3二维形状分析及其在图像检索中的应用索效果的图像特征和检索方法。第三个阶段：基于语义特征的图像检索【2 】【9 】【1 1 1 【1 2 】。第二阶段的图像检索系统主要是采用传统的底层图像特征对图像内容进行描述，而这种描述与人对图像内容的理解存在着很大的差异。这种差异表现在三个方面【2 】：首先是人对图像的理解是一个学习的过程，而图像的底层特征主要是以一种统计数据的形式出现的，这并不能完全反映人的理解过程；其次，图像内容具有“模糊”的特性，无法用简单的特征向量来描述；最后，人对图像内容的理解是建立在人类已有知识的基础上的，底层特征无法反映这些先验知识。为了解决这个问题，研究人员开始探索通过图像的语义特征( 包括场景、行为、情感等语义特征) 来实现图像检索。主要思想就是建立图像语义模型，从图像中提取一些视觉特征并提取语义，然后借助推理和领域知识来建立对图像语义内容的描述。这一研究方向已经得到了越来越多的关注。目前这一领域仍然是个新兴的领域，还没有一种完整的基于语义的图像内容描述方案【2 】。1 2 2 基于内容的图像检索系统一个典型的c b i r 系统结构图如下所示【9 】：图1 - 1 基于内容的图像检索系统框图在这个系统结构中，图像库中的图像经过“内容特征提取与描述”模块分析之后得到每幅图像的特征向量，这些特征向量经过索引组织之后生成一个特征库。用户提交的查询( 通常是一幅图像或者草图) 也经过“内容特征提取与描述”模块分析，得到查询的特征向量圪。屹与特征库中的特征向量k 进行相似性计算，计算的结果往往是一个反映圪与k 之间的距离的数值，这个数值的大小反映了查询图像与被检索图像之间的相似程度。系统根据相似性计算的结果把检索出来的图像返回给用户。用户对检索结果进行评价，并把评价反馈给系统，系统41 引言通过相关反馈杌铷调整参数，使得系统得检索性能不断改善。近十几年来，许多研究机构和公司开发了很多基于内容的图像检索系统。下面介绍几个著名的系统。1 2 2 1q b i c这是最早出现的c b i r 系统【5 】【1 3 】，由i b m a l m a d e nr e s e a r c hc e n t e r 开发。它支持例子图像、草图、用户选择颜色、纹理等多种查询方式，对图像的特征描述采用了颜色、纹理、形状等多种特征。q b i c 是少数考虑高维特征索引的系统之一。其演示系统在h t t p ：w w w q b i c a l m a d e n i b m c o m w e b s e e k 是由c o l u m b i a 大学开发设计的一个面向w w w 的文本图像搜索工具它支持基于关键字和视觉内容的查询。它所采用的视觉特征是颜色集和基于小波变换的纹理特征，可以按照图像内容的空间关系查询。采用了二叉树的索引算法。系统演示网址：h t t p ：w w w e e c o l u m b i a e d u s f c h a n g d e m o s e h t m 1 。2 2 3m a r sm 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 ) 1 4 是美国i i h n o i s 大学u r b a n a c h a m p a i g n 分校开发的。它是计算机视觉、数据库管理系统合信息检索多个领域交叉的结果。它的研究焦点不在于找到单一的最佳特征表达，而是如何把不同的视觉特性组织成一个可以动态适应于不同应用和不同用户的有意义的检索机制。它采用了相关反馈机制。系统演示：h t t p ：j a d z i a i f p u i u c c d u ：8 0 0 0 1 。2 。3 。4n e r r an c w a 1 5 j 邑u c s ba l e x a n d r i ad i g i t a li j b m r y ( a d l ) 开发的图像检索原型系统。它使用了颜色、纹理、形状以及区域位置等特征来进行检索。它主要的特点在于使用一种自动图像分割算法使系统可以提供基于目标或者区域的检索。演示系统在：h t t p ：v i v a m i e c e u c s b e d u n e t r a 二维形状分析及其在图像检索中的应用1 2 3 基于内容的图像检索面临的问题c b i r 面临的最大的问题就是语义鸿沟问题，即底层的图像特征与高层的语义特征之间存在着巨大的差异。现在还没有一个很好的解决方案。目前的c b i r系统都是抽取图像的视觉特征比如颜色、纹理等，而不是分析图像中所表达的场景、情感等语义特征。用户实际上需要的是根据图像的语义特征来检索图像，而现在的c b i r 系统都是试图通过计算机对图像的理解来近似表达人对图像的理解，由于计算机对图像的理解与人的理解之间存在客观上的区别，因此导致现有的检索系统都不能取得令人满意的效果，还没有达到实用的阶段。c b i r 还面临的一个问题是现在还没有一个真正意义上的图像数据库模型。由于图像数据量大、不同图像之间有很大差别、图像内容的描述方法各不相同且不统一、缺乏对图像的语义进行描述的方法等等这些原因，使得传统的关系数据库不能适用于图像的存储与基于内容的检索。现在的解决方案主要是图像的存储由文件系统来实现、图像的特征存储与管理仍然由关系数据库来完成。这种解决方案是低效的，它套用关系数据库中基于文本方式的查询方式来进行检索。c b i r的进一步发展迫切需要一个真正意义上的图像数据库管理系统。这不仅仅是c b m 的研究范畴，也是数据库领域的个重要课题。1 3基于形状的图像检索形状特征是图像最主要的视觉特征之一，人们对一幅图像的理解很大程度上有赖于对图像中目标形状的区别和感知。因此基于形状特征的图像检索也是c b i r 中的重要研究内容。基于形状的图像检索通过提取两类形状特征来描述图像，一类是局部的特征，另一类是全局的特征。局部特征即针对图像中的目标进行描述，这类特征提取方法一般需要首先对图像进行分割，然后对分割出的目标进行分析。因此这类方法对图像分割算法有很大的依赖性，图像分割效果的好坏直接影响到后续的分析工作。对目标的形状进行分析有很多的方法，主要分两类：基于轮廓的方法和基于区域的方法。比较常用的方法有矩不变量、傅立叶描述符等，见第三章。全局特征提取是直接对整个图像进行分析，由于边缘对于形状的识别很重要，因此可以分析整个图像的边缘特征来间接的描述形状特征，也有的工作是基于分裂合并方法，采用一种树形结构来表述图像中形状特征( 主要市目标分布特征) 。基于形状的图像检索的一个典型的应用是商标图像检索【1 6 】【1 7 】【1 8 】。基于内61 引言容的商标图像检索在商标注册中可以大太提高商标比对的效率，因此有很多的研究机构都在探索c b i r 技术在商标检索中的应用。羡国的汉王公司也开发了一个基于内容的商标检索系统 z 6 1 。由于商标图像比对时只使用灰度图，因此不适合用颜色特征来进行检索，而且商标图像般是某种标记、符号、图标甚至文字，它的纹理特征也很不突出。因此在商标检索中采用最多的特征就是形状特征。1 4本文的主要工作本文完成的主要工作有以下几个：通过实验对基于不同边界标记函数的傅立叶描述符算法进行了分析，比较了这些算法的优缺点。提出了一种新的形状描述算法：基于链码的傅立叶描述符。该算法的主要优点在于它能很好的恢复形状。运用设计模式思想设计并实现了一个基于内容的图像检索系统i s e a r c h 。该系统提供例子图像检索方式，组合了颜色、纹理、形状特征来检索图像。通过实验测试了该系统的检索性能。1 5本文的组织结构本文第一章简要的介绍二维形状分析技术、c b i r 的概念和基本原理。第二章和第三章分别介绍c b i r 技术和形状分析技术。第四章通过实验分析比较了凡种不同的傅立叶描述符，并给出一种对二维形状的基于链码的傅立叶描述算法，通过试验分析该算法的优缺点。第五章设计开发了一个基于内容的检索系统i s e a r e h 。全文由第六章给出总结。72 c b i r 基本技术2c b i r 基本技术c b l r 系统的关键技术可以分为以下几个：特征的提取与描述、特征索引组织与高维特征向量的降维处理、图像相似性度量方法。本章介绍这几个方面的技术。如前所述，为了提高图像检索的效果，引入了相关反馈技术，因此本章也介绍了相关反馈的一些基本技术。2 1特征提取与描述特征提取是c b i r 的基础。从广义上讲，图像特征包括基于文本的特征( 关键词、文本标注等) 、视觉特征( 颜色、纹理、形状等) 以及语义特征。基于文本的特征主要是第一代检索系统的技术，现在的第二代检索方法中主要使用的特征是第二种而语义特征的提取现在还是一个很困难的问题，没有一个成熟的解决方案。视觉特征也可以分为两类：一类是通用的视觉特征，包括颜色、纹理、形状、空间关系等，这类特征是所有数字图像中都客观存在的。另一类是面向领域的视觉特征，比如人脸、指纹等等，这类特征往往与具体的应用有关，需要一定的领域知识。图像视觉特征提取出来之后，需要用某种方式来描述它，这就是特征描述，特征描述在c b i r 中是一个必不可少的环节。通常特征描述采用向量模型，对图像特征进行分析得到一个特征向量，然后用这个特征向量来表示爵像内容。在图像相似性度量中往往就是直接对这些向量的距离进行度量，特征向量之间的距离就反映了图像之间的相似性程度：距离越大，相似性越低；距离越小，相似性越高。需要说明的是，虽然从图像中可以提取很多的视觉特征，但是由于人类视觉的主观性，并不存在一种最佳的特征描述方法适用于任何应用。实际上，每种视觉特征都存在着许多不同的描述方法，这些方法从不同的角度表达了特征信息。一般来讲，一个好的描述方法应该能够具有足够的鲁棒性，即对图像噪声、图像处理过程中产生的一些图像质量的变化等具有一定的不变性。同时，好的描述方法应该具有好的区分性能，即对不同的图像应该能正确的区分开。这两个方面往往会有一些冲突，因此需要在这两者中做一个折中。特征描述可以分为两类：全局描述和局部描述。前者对图像的整体的特征进行描述，而后者只是针对图像中的部分区域或目标进行描述。最常用的视觉特征及其主要描述方法主要有：9二维形状分析及其在图像检索中的应甩黼 6 1 1 1 9 1 1 2 0 1 , 颜色直方图、颜色聚合向量、颜色相关图、颜色矩。纹理特征：灰度共生矩阵【1 】、边缘方向直方图、基于小波变换的纹理描述符 2 1 、t a m u r a 纹理 1 9 1 。形状特征：包括全局特征和局部特征。参见第三章。空间关系特征【4 】：像元、二维符号串、空间四叉树、符号图等a2 2特征索引与降维特征索引与高维特征的降维是c b i r 系统的又一个关键性的技术，对于高效和快速的检索至关重要。图像特征提取的结果往往是高维的特征向量，它不适合于传统的索引结构，因此在构造索引之前，往往要对这些高维的特征向量进行降维( d i m e n s i o nr e d u c t i o n ) 。降维的方法有很多种，比较常见的有主成分分析法，现在已经有人提出基于人工神经网络的降维方法、聚类的方法等等【6 】。在特征向量降维之后，需要对这些多维的特征向量进行索引。有许多索引方法，包括r 树以及它的变种r + 树和r + 树、k d 树、k - d b 树、h b 树、线性四叉树等。除以上几种方法之外，聚类和神经网络技术也可以用来对高维特征向量进行索引。文献【2 1 】对各种索引算法进行了综述和对比。以上这些方法主要都是为传统的数据库查询设计的，并不是针对图像检索而设计的。这些方法在维数比较低的情况下有很好的性能，但是当维数比较高的时候表现比较差，而且，这些索引方法都是假定特征向量的比较是采用欧氏距离，然而实际情况并非如此，很多情况下图像特征之间的比较即相似度的计算不是基于欧氏距离的( 比如颜色直方图的求交运算) 。为了解决这个问题，z h a n g 和z h o n g 提出了用自组织映射( s e l f - o r g a n i z a t i o nm a p ，s o m ) 的方法【2 2 】，它具有无人监督的记忆能力、动态聚类功能和支持任意相似度度量。还有一种解决办法是聚类技术。c h a r i k a r 等人提出了适用于动态信息检索的增加聚类技术 2 3 1 ，这种技术具有动态的结构，能够处理高维数据，支持非欧拉的相似度量。2 3相似性度量图像检索一般不是精确匹配，而是检索与例子图像最相似的一些图像。检索过程主要就是计算查询图像的特征向量与数据库中的图像的特征向量之间的距离，用这种距离来衡量图像之间的相似程度。常用的相似性度量方法有( 6 】【1 4 】【1 5 】【1 9 】：阂可夫斯基距离、二次式距离、马氏距离。2 c b l r 基本技术2 4相关反馈基于内容的图像检索通过图像的颜色、纹理、形状等特征来表示图像内容，根据这些特征进行检索。虽然这些视觉特征能在一定的程度上反映图像的内容，但是它还远远不能保证图像检索的效果。其主要问题就是底层图像特征与高层语义特征之间的鸿沟。因为，视觉特征向量比如颜色鱼方图等的相似性度量与图像的语义和人类视觉的主观性并不相符。人对图像的感知和认识是很主观的、并且受人所在的环境的影响。不同的人对同一幅图像有不同的认识、同一个人在不同的场合下对同一幅图像的认识也很可能不相同。而任何视觉特征向量都只是对图像视觉内容的某个方面的一个简单反映，它不能描述图像的所有视觉特征、更不可能反映人类视觉的主观性。所以通过图像底层特征进行检索的结果往往不太准确，计算机认为相似的图像人可能并不认为相似，相反，人认为相似的图像反而可能没有被检索到。相关反馈技术正是为了解决这个问题而被提出的。它的关键的思想就是让人的感知主动性参与到检索的过程中，让用户能够根据自己的检索要求对检索结果进行评价，并把这种评价反馈给检索系统，系统根据用户的反馈修改系统的参数，从而改善检索的效果。相关反馈技术最早是在文档检索中应用的一种技术【9 】，它是一种有监督的主动学习技术，用来提高检索系统的效果。在图像检索系统中，它通过由用户提供的正、负图像来改善系统的性能。其工作过程如下：用户提交个查询，系统返回检索到的一系列图像，用户对这些图像进行评判，标记出哪些是符合要求的( 正图像) ，哪些是不符合的( 负图像) 。然后系统根据这个评判修改一些参数，使得下次查询的结果更加符合用户的要求。因此，相关反馈需要解决的一个关键问题就是怎样根据正负反馈来修正系数。最早的相关反馈算法是基于向量模型的，可以分为两类：查询向量优化( q u e r yr e f i n e m e n t ) 和相似性度量优化( s i m i l a r i t ym e a s u r er e f i n e m e n t ) 。除了这两大类算法之外，还有很多其它的算法，比较常见的有基于贝叶斯的反馈算法【1 9 】等。下面介绍查询向量优化算法和相似性度量优化算法。查询向量优化算法根据用户反馈信息来调整查询点，使之更加接近理想的查询点，然后用调整后的查询点去重新计算检索结果。常用r o c c h i o 的计算公式来调整查询向量【9 】设磷和d j 分别表示用户反馈的正相关和负相关图像，则优化之后的查询向量q 可以通过下式计算：二雏形状分析及其在图像检索中的应用q i 啦邶1 丕吖寿荟d i ) d 其中，口，p ，y 是常数，n n 。分别是d ：和d j 中的图像数日。相似性度量优化通过动态的调整图像特征的权重来改进检索结果，它不需要将图像的特征向量转变为权重向量，而是首先由归一化操作来统一不同特征的权重，然后根据相关反馈动态的调整它们的权重以改善检索结果 1 9 1 。设权重矩阵定义为【9 】：d 。荟，帽i ，1 引沼2 当一幅图像是正相关时，它的权重按下式调整：q - q ( ，+ 6 - 6 t ) ，6 一i ，( q ) 一，口一( 2 - 3 )其中6 是6 的平均值。如果一幅图像是负相关时，它的特征权重按下式调整：q 一帮f ( j 一6 + 6 j )( 2 4 )有关相关反馈算法的深入介绍参见【1 9 】。2 5检索性能的评价常用的图像检索性能评价指标有两个，它们最早是用于传统数据库检索评价，这两个标准是查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 。给定一个查询q ，图像库中与其相似的图像的集合记为r ( q ) ，检索到的图像的集合记为q ( q ) ，检索出的图像中正确相关图像的集合记为s ( q 1 ，查准率就定义为一次查询过程中，系统返回的查询结果中正确图像数目在所有返回图像数目中的比例。显然查准率越高则检索效果越好。查全率是指系统返回的结果中正确图像的数目占图像库中所有正确图像数目的比例。查全率越高则系统检索效果越好。这两个指标的定义式为：查准率i 蹦c z s ，查全率i 黜沼s ，2 c b i r 基本技术实际系统中往往要在这两个指标之间傲一个折中，因为提高一个指标往往会降低另一个指标。而且，如果图像库中相似图像比检索出来的图像数目还要多，那么查全率就没什么意义了。2 6小结本章对基于内容的图像检索中的几个关键技术做了一个简单的介绍，这些技术包括视觉特征提取与描述、索引与降维技术、相似性度量、系统性能评价。c b i r 系统中广泛使用的视觉特征是颜色、纹理、形状、空间关系。每种特征有许多不同的描述方法，不同的方法适用于不同的应用。没有一种对任何图像都适合的特征描述方法。高效的索引对于图像检索系统是至关重要的，高维的特征向量需要降维。比较常用降维方法的是k - l 变换( 比如p c a 方法就是其中一种) 、聚类方法，有人提出了人工神经网络等其它新的方法。在特征向量降维之后，需要对他们进行索引，传统数据库的许多索引技术被用于图像检索系统，但是它们都不是针对图像检索来设计的，因此出现了一些新的适合予图像检索的索引技术。相似性度量也是图像检索的一个重要步骤，传统的基于向量模型的相似性度量方法已经被证明不适合于人眼的视觉特征。因此有一些新的相似性度量方法( 比如特征对比模型) 被提出。但是由于新的度量方法还只是理论性的模型，不太易于实现，因此实际系统中基本上还是采用向量模型来衡量相似性。相关反馈是图像检索中的一种用户交互技术，它试图通过让用户的主观感知参与到检索过程中来提高检索的效果。许多实验和实际系统也证明了相关反馈是一种行之有效的方法。相关反馈的算法除了传统的查询优化和相似性度量优化之外还有一些新的算法比如基于贝叶斯理论的算法等等。检索系统的性能评价也是所有检索系统应该关注的问题之一。用的最广泛的评价指标就是查全率和查准率，也有些其它的评价方法，比如m p e g 7 中推荐的a n m r ( a v e r a g en o r m a l i z e dm o d i f i e dr e t r i e v a lr a n k ) 等。基于内容的图像检索目前主要还是采用图像的底层视觉特征来进行检索，由于语义鸿沟的存在，使得现有的系统的检索效果还不令人满意。基于语义的图像检索仍然处在探索阶段，还没有一个真正意义上的语义图像检索系统。尽管有相关反馈技术可以提高图像检索的效果，但是并不能从根本上解决这个问题。因此图像检索到目前还没有达到可以实用的阶段，仍然需要更深入的研究和探索、需要很多相关领域的合作和有关部门和企业的大力支持。3 二维形状分析概连3 二维形状分析概述二维形状分析技术可以分为三类：一类是根据形状的轮廓进行描述，称为基于轮廓的形状分析，另一类是根据形状所占的整个区域来描述，称为基于区域的形状分析。还有一类方法不是针对图像中的目标来进行分析，而是根据图像中的边缘信息获得对整个图像的形状特征的描述。本章首先介绍形状分析方法的评价标准，然后介绍这三类方法中的主要算法。3 1形状描述方法的评价标准在形状描述研究中一个很重要的闯题就是怎样评价一个描述算法的好坏。对于形状描述算法的评价还没有一个统一的标准【2 4 】。m p e g 7 标准中已经提出了几个形状描述符的评价准贝t j 2 5 2 6 ，这些准则是：检索精确( g o o dr e t r i e v a la c c u r a c y ) 、特征压缩( c o m p a c tf e a t u r e s ) 、通用性( g e n e r a la p p l c a t i o n ) 、低复杂度( 1 0 wc o m p u t a t i o nc o m p l e x i t y ) 、鲁捧的检索性能( r o b u s tr e t r i e v a lp e r f o r m a n c e ) 以及由粗到精的描述( h i e r a r c h i c a lc o r r s ct of m er e p r e s e n t a t i o n ) 。文献中一般都使用不变性( 旋转不变性、平移不变性、尺度变换不变性) 作为形状描述的一个基本的评价标准，另一个评价标准是识别率( 查准率) ，即用某种描述符对形状进行识别的效果。在本文中将使用检索系统中的查准率来分析和比较形状描述符的性能。3 2基于轮廓的形状分析方法3 2 1f r e e m a n 链码链码通过一个具有单位长度和方向的线段序列来表示边界。典型的链码有4 方向链码和8 方向链码，通过给每个方向一个数字编码，就可以对线段序列中的每个线段进行编码，从目标边界上某个点( 起始点) 开始，按顺时针( 逆时针)方向遍历整个边界，就可以得到对该目标区域的链码描述【2 4 】【2 5 】 2 8 】。边界的链码与所选择的起始点有关。通常需要对链码进行规格化。在某些场合，还采用链码的一阶微分来表示一个边界。只要简单的算出链码序列中相邻两个数字所表示的方向之间的相差的方向数( 按逆时针计算) 即可。= 维形状分析及其在图像检索中的应用使用这种链码的好处是它与边界的旋转无关。j u k k ai i v a r i n e n 等人研究利用链码直方图以及归一化直方图的方法来识别目标 2 9 1 。归一化的链码直方图是旋转无关的。3 2 2 ( 曲) 线段序列复杂的边界可以用一组线段来近似的表示【2 7 1 f 3 0 】。一个区域可以用一个多边形来表示，这些多边形的顶点就形成了对该区域的描述，这可以通过边界的分割来获得。根据不同的精度要求，可以增加或者减少多边形的边数。用一系列的线段来表示边界，主要的问题在于怎样有效的确定这些线段的端点。主要方法有边界生长法【4 】、容许区间法【2 7 】等。还可以通过计算轮廓上的一些关键点来提取近似多边形顶点。这类方法主要是利用边界曲率局部极大值，比如余弦法【3 1 】和弦长比法【3 2 】。刘玉兰等i 3 3 】提出了一种间接提取轮廓关键点的算法，该算法把数字曲线分解为两条一维离散曲线，分别找出这两条曲线上的尖点，然后进行综合得到原始曲线上的尖点的集合，这些尖点可以作为边界近似多边形的顶点。另一种边界描述方法是用曲线段来描述，称之为“常曲率”( c o n s t a n tc u r v a t u r e ) 方法【4 】，边界通常被分割成二次曲线，比如椭圆曲线、抛物线等。如果这些衄线段类型是已知的，则可以对每一种曲线段赋予一个编码，这样就可以得到整个边界的一个编码串( 类似于链码) 。3 2 3 傅立叶描述符当一个区域边界上的点被确定时，利用这些点就可以用来鉴别不同区域的形状。设x v 平面上有一条由n 个点组成的数字化边界，其中每一个边界点用其坐标o 。，y 。) 表示。从任意点o 。，y 。) 开始，沿着逆时针方向遍历整个边界，依次经过坐标“，y 。) ，0 ：，y ：) 0 ，。y 。) 。可以把这个区域看作是在复平面上，沿边界跟踪一周就可以得到一个复数序列协。+ f y 。) 。这个复数序列的傅立叶变换称为傅立叶描述子f d ( f o u r i e rd e s c r i p t i o n ) 【1 2 2 5 3 6 1 。通常取前肘个傅立叶系数来描述轮廓。高频傅立叶分量描述的是图像的细节部分，而低频分量描述的是全局的形状，因此，j l l f 越小，在边界中所丢失的细节也就越多。王涛等人提出了一种利用轮廓的近似多边形进行傅立叶描述的算法，并针对傅立叶描述子对起始点的敏感性提出了一种解决办法【3 6 】。3 二维形状分析概述广义上的傅立叶描述符可以通过对边界函数进行傅立叶变换得到。边界函数可以是上文说的边界复坐标，也可以是边界曲率函数、边界近似多变形、质心距离等，本文第四章将对几种不同边界函数的傅立叶描述符进行深入的研究。3 2 4 小波描述符设给定的轮廓函数为，( 力，则f ( x ) 的小波变换系数矸，( 口，6 ) 就n - - i 以用来作为轮廓的描述【2 】。有关小波变换请参考文献【3 7 】【3 8 】。与傅立叶轮廓描述符相比，小波轮廓描述符能通过较少的点数以较高的精度来描述轮廓信息，而且对小波描述符进行平移与尺度归一化之后不受轮廓的平移与尺度变化的影响【2 】【3 9 】。同时，相对于傅立叶描述符，小波描述符受轮廓局部畸变i 拘影响j 2 1 1 3 9 1 。杨翔英等 3 9 1 给出了小波轮廓描述符的平移归一化、尺度归一化算法，讨论了小波系数的截断问题。3 2 5 边界矩特征一个区域的边界是一条闭合曲线，曲线上从某点开始逆时针遍历一周得到一个点的序列，用复数表示为s ( k ) 一x ( k ) + 妒让) k - 0 , 1 一1 。则边界的r 阶矩为【2 5 4 0 ：m r 。专荟【s 非) 】