（计算数学专业论文）基于内容的图像和视频检索技术研究及其系统实现.pdf

摘要随着多媒体和计算机网络技术的飞速发展，数字图像和视频的容量正以惊人的速度增长。如何有效的组织、管理和利用这些图像和视频数据具有重要的意义，这使得基于内容的图像和视频检索成为现在多媒体领域最活跃的研究热点。但是到目前为止，基于内容的图像和视频检索还存在很多问题有待解决。针对基于内容的图像和视频检索中的检索准确度和检索的时间复杂度，本文开发了两个原型系统：一是基于内容的图像检索系统；一是基于语义的新闻视频检索系统。在基于内容的图像检索原型系统中引入了相关反馈和支持向量机，并将d t w + g s v m 算法与u f m + g s v m 算法比较，验证了该算法的有效性。在基于语义的新闻视频检索中通过一次镜头分割和二次镜头分割实现了镜头的准确分割，在镜头准确分割的基础上，引入人工交互的方式，实现了场景的准确生成。通过引入元数据的标注完成对场景的标注，实现用户的语义查询。本文分为5 个部分。第一部分论述了基于内容的图像、视频检索的研究现状和本课题所做的主要工作。第二部分介绍了统计模式和支持向量机相关的知识。第三部分主要介绍了本文开发的一个基于区域的图像检索原型系统的设计和实现。第四部分主要介绍了本文开发的一个基于语义的新闻视频检索系统的设计与实现。最后总结了本文的研究成果和对下一步工作的展望。关键宇：基于内容的图像检索，基于内容的视频检索，支持向量机，d t wa b s t r ac tw i t ht h ed e v e l o p m e n to fm u l t i m e d i aa n dc o m p u t e rn e t w o r kt e c h n i q u e ，t h ev o l u m eo fd i g i t a li m a g ea n dv i d e oi sg o i n gu pf a b u l o u s l y i th a sag o o ds e n s et oo r g a n i z e ，m a n a g ea n du t i l i z et h ed a t ao ft h ei m a g ea n dv i d e oe f f i c i e n t l yw h i c hm a k e st h ec o n t e n t - b a s e di m a g ea n dv i d e or e t r i e v a lb eo nt h et o pr e s e a r c ho ft h em u l t i m e d i aa r e a b u tt h e r es t i l la r eal o to fp r o b l e m sn e e d e dt ob er e s o l v e di nt h ec o n t e n t b a s e di m a g ea n dv i d e or e t r i e v a la tp r e s e n t i nt h i sp a p e r ，w ed e v e l o pt w op r o t o t y p es y s t e m ss t a r t e dw i t ht h ea c c u r a c ya n dt i m eo ft h ec o n t e n t b a s e di m a g ea n dv i d e or e t r i e v a l o n eo ft h e mi sac o n t e n t - b a s e di m a g er e t r i e v a l ，t h eo t h e ri sas e m a n t i c b a s e dn e w sv i d e or e t r i e v a ls y s t e m r e l e v a n c ef e e d b a c ka n ds u p p o r tv e c t o rm a c h i n el e a r n i n ga r ei n t r o d u c e di n t ot h ec o n t e n d - b a s e di m a g er e t r i e v a ls y s t e m w ea l s oc o m p a r ed t w & g s v mr e s u l t st ou f m & g s v m sw h i c hp r o v e st h a tt h ea l g o r i t h mo fd t w & g s v mi se f f e c t i v e t h ef i r s ts h o ts e g m e n t a t i o na n dt h es e c o n ds h o ts e g m e n t a t i o nu s e di nt h es e m a n t i c b a s e dn e w sv i d e or e t r i e v a ls y s t e mm a k et h es h o t ss e g m e n t a t i o na c c u r a t e ；t h e n ，b a s e do nt h i s ，w ei n t r o d u c ei n t e r a c t i v eo fn e w sv i d e os c e n es e g m e n t a t i o n t h es e m a n t i cr e t r i e v a lo fn e w sv i d e oi si m p l e m e n t e db yt h ea n n o t a t i o no fs c e n et h r o u g hm e t a d a t aa n n o t a t i o n t h e r ea r e5s e c t i o n si nt h i sp a p e r i ns e c t i o n1 , b o t ht h ejo bw eh a v ed o n ea n dt h er e s e a r c hs t a t eo fc o n t e n t - b a s e di m a g ea n dv i d e or e t r i e v a la r ed e s c r i b e d s e c t i o n2i n t r o d u c e st h ek n o w l e d g eo fp a a e mr e c o g n i t i o na n ds u p p o r tv e c t o rm a c h i n e t h ed e s i g na n dr e a l i z a t i o no far e g i o n - b a s e di m a g er e t r i e v a lp r o t o t y p es y s t e mi sp r o v i d e di ns e c t i o n3 s e c t i o n 4d e s c r i b e st h ed e s i g na n dr e a l i z a t i o no fas e m a n t i c - b a s e dn e w sv i d e or e t r i e v a ls y s t e m a n df i n a l l y ，w ec o n c l u d ei ns e c t i o n5 , t o g e t h e rw i t had i s c u s s i o no ff u t u r ew o r k k e yw o r d ：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 o n t e n t - b a s e dv i d e or e t r i e v a l ，s u p p o r tv e c t o rm a c h i n e ，d y n a m i ct i m ew a r p i n gi i基于内容的图像和视频检索技术研究及其系统实现第一章绪论随着多媒体和计算机网络技术的飞速发展，数字图像的容量正以惊人的速度增长。为有效利用和管理图像、视频中包含的大量有用信息，必须对图像和视频进行自动及有效的描述，建立基于图像和视频内容自动或半自动描述的图像、视频数据库。近年来，在数据库和计算机视觉两大研究领域的共同推动下，基于内容的图像和视频检索已成为一个非常活跃的研究领域，同时它也成为数字图书馆、未来信息高速公路等重大项目的关键技术。尽管图像和视频各有特点，但对他们基于内容的检索都有比较一致的基本工作框架，因为都要完成对视觉信息的处理、分析和理解。基于内容的视觉信息检索可看作是介于用户和数据库之间的一种信息服务系统。用户通过它可按自然的方式从库中提取满足所需要内容的媒体数据( 本文主要是指图像和视频) 。其通用框架如图：图1 1 基于内容的视觉信息检索系统基本框架1 1 基于内容的图像与视频检索技术1 1 1 基于内容的图像检索( c b i r ) 体系基于内容的图像检索( c b i r ，c o n t e n tb a s e di m a g er e t r i e v a l ) i l l 是指直接采用图像内容进行图像信息查询的检索，在建立图像库时，对输入的图像先进行图像分析，提取图像或目标的特征向量，并在将输入图像存入图像库的同时将其对应的特征向量也存入与图像库相应的特征库。在进行图像检索时，对每一幅给定的查询图，进行图像分析并提取该图的特征向量。通过将该图像特征向量与特征库中的特征向硕士学位论文量进行匹配并根据匹配结果到图像库中搜索就可提取出所需要的检索图来。其主要思想是根据图像所包含的颜色、纹理、形状以及对象的空间关系等底层图像特征来分析图像信息，建立图像的特征矢量作为其索引进行检索，检索方法目前主要是根据图像的多维特征向量进行相似查询。随着图像特征理论的逐渐完善，人们认识到图像检索系统的用户主观性及底层视觉特征与高层语义特征难以匹配的问题，开始把用户看作检索系统的一部分，将文本检索中的相关反馈技术引入到基于内容的图像检索中【2 】。相关反馈是近年来图像检索中的一个热点问题，研究重点从最初的启发式反馈到完整反馈系统的建立，再到各种机器学习方法【34 】的引入，越来越多的相关反馈被引入查询系统来改善检索的结果。机器学习方法和相关反馈相结合，大大提高了图像检索的性能。1 1 2 基于内容的视频检索( c b v r ) 体系视频检索就是要从大量的视频数据中找到所需的视频片断。传统的视频检索只能通过快进和快退等顺序的方法人工查找，因而是一件非常繁琐耗时的工作，显然己无法满足多媒体数据库的要求。用户往往希望可以直接检索到一段包含特定信息的视频片断，例如篮球比赛中的投篮镜头、含有日出景色的片段等，由系统自动的找到所需的片段点【5 1 。视频数据难以用符号化的方法来描述其内容，比如帧图像中的颜色、灰度、目标分布和视频中的运动、时间、语音中的音调等。当用户希望利用这些信息线索对视频数据进行检索时，很难用传统的基于关键词的数据库检索技术来达到目的。因为一方面，在许多情况下很难用一个或多个关键词来充分描述其特征，而且这种特征的描述也有很大的主观性，不同的用户可能有不同的关键词描述；另一方面，用户很难将这些信息线索化为某种符号形式。因此就要求能够对视频数据进行基于内容语义的分析，以达到基于内容语义的深层次检索，这就是基于内容的视频检索技术c b v r ( c o n t e n t b a s e dv i d e or e t r i e v a l ) t 6 ，7 1 。基于内容的视频检索是一门涉及面很广的交叉学科，需要利用图基于内容的图像和视频检索技术研究及其系统实现像处理、模式识别、计算机视觉、图形理解等领域的知识作为基础，还需从认知科学、人工智能、数据库管理系统、人机交互、信息检索等领域引入新的媒体数据表示和数据模型，从而设计出可靠、有效的检索算法、系统结构以及友好的人机界面。1 2 国内外研究的现状基于内容的视觉信息检索自1 9 9 2 年正式“冠名 以来，得到了国内外信息领域科技人员的广泛重视和研究，迅速成为多媒体，特别是图像、视频和数据库技术中的研究热点之一。目前国内外已经开发出多种图像、视频数据检索系统，如q i b c t 引、w e b s e e k t 9 1 、v i s u a l s e e k 1 0 1 、m a r s e l 、j a c o b t l2 1 、n e t r a 1 3 1 、p h o t o b o o k 14 1 、v i r a g e t l 5 】、v i d e o s t a r l l 6 等等。这些系统虽然大多没有成为商用化系统，但也反映了图像、视频数据检索系统研究的主要成果。其中q i b c 是由i b m 公司推出的第一个商用的基于内容的检索系统，此系统提供了对静止图像及视频信息基于内容的检索方法，其中包括镜头探测、运动估计、层描述、关键帧生成等多种视频处理方法；j a c o b是由意大利p a l e r m o 大学开发的基于内容的视频查询系统，该系统可进行视频自动分段并从中抽取关键帧，并可按彩色及纹理特征以关键帧描述基于内容的检索；v i d e o s t a r 是一种视频存储及检索系统，此系统是一个基于通用视频数据框架模型的通用视频数据库系统，系统支持视频数据的共享与各种商用数据库的连接使用。国内的清华大学、国防科技大学、微软亚洲研究院、中科院等机构也进行了一定研究，并取得了一定成果，实现了一些改进算法和实验系统【1 71 81 9 】。但要真正做到视频结构化的分析，实现基于内容的视频检索，为用户提供更方便的使用环境，还需要做很多理论和实践工作。硕士学位论文1 3 主要研究内容及结构安排1 3 1 主要研究内容本文在前人的基础上，根据c b i r 和c b v r 的基本原理，实现了一个图像检索原型系统和一个视频检索原型系统。图像检索原型系统以数字图像为研究对象，对数字图像进行特征提取，包括颜色、纹理、形状等特征。在检索时引入了相关反馈和支持向量机，进一步改善检索的性能。该原型系统主要是用来检验本文提出的算法的有效性。视频检索原型系统主要完成了人工交互的新闻视频场景标注和检索部分。具体研究任务如下：选择一个合适的匹配算法。色彩、纹理和形状等图像特征被提取出来后，形成特征向量，就可以用这个特征向量来表征对应的图像。在图像检索中，判断图像之间是否相似是通过比较这些特征向量是否相似来进行的。也就是说，把图像特征向量之间的比较就看成图像相似度比较。显然，一个好的特征向量比较算法对图像检索结果影响很大。本文将u f m 和d t w 相结合，形成一种改进的匹配算法。将广义支持向量机( g s v m ) 应用到基于内容的图像检索。现在我们提取的图像特征主要是底层视觉特征，这样与人们的高层语义之间便存在差距。为了缩小这一差距，常会用到一些学习机制。本文将g s v m 结合上述所讲到的匹配算法，形成了本原型系统所使用的支持向量机。在原有镜头分割的基础上，提出了二次镜头分割，针对新闻视频特有的特征，在进行二次分割时又采用了不同的分割方法，为后续新闻场景的正确生成打下了基础。针对新闻视频中同一个新闻故事中视频内容变化很大，很难用聚类的方法将属于同一个新闻故事的镜头聚类，本文引入了人工交互的方式，通过确定同一新闻故事单元的首尾镜头号，完成场景的正确生成。基于内容的图像和视频检索技术研究及其系统实现针对新闻故事单元存在的语义歧义比较小，引入了人工交互的方式完成新闻场景的标注，实现后面新闻故事的语义查询。1 3 2 论文结构安排论文的结构安排如下：第一章是绪论，介绍了选题背景和意义，总结了图像检索和视频检索的研究现状及现有的图像视频检索系统，本文的主要研究内容，并对论文结构进行了安排。第二章是模式识别和支持向量机。主要介绍了模式识别中的一种新的学习方法支持向量机。其中广义支持向量机和非线性支持向量机是本文基于内容的图像检索和视频检索中将要用到的两种重要的分类器。第三章是基于内容的图像检索系统的研究。主要分析了本文开发的一个原型系统。包括特征的提取，相似性度量及广义支持向量机在图像检索中的应用，最后是实验结果。特征提取包括颜色特征、纹理特征和形状特征；相似性度量部分主要分析了d t w 算法，及d t w和g s v m 相结合在图像检索中的应用。第四章是基于语义的新闻视频检索的研究。首先分析了基于内容的视频检索中的一些关键技术，然后分析了本文开发的一个基于语义的新闻视频检索系统。包括一次镜头分割、二次镜头分割及语义场景的标注等。第五章是结束语，对本文所做的工作进行了总结，同时，对进一步的研究工作进行了展望。硕士学位论文第二章统计模式识别与支持向量机模式识别诞生于2 0 世纪2 0 年代，随着4 0 年代计算机的出现及5 0 年代人工智能的兴起，模式识别在2 0 世纪6 0 年代迅速发展成为一门新学科。它所研究的理论和方法在很多科学和技术领域中得到了广泛的重视，推动了人工智能系统的发展，扩大了计算机应用的可能性。2 1 统计模式识别的原理和方法2 1 1 模式识别什么是模式和模式识别? 广义地说，存在于时间和空间中可观察的事物，如果可以区别它们是否相同或相似，都可以称之为模式；狭义地说，模式是通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息；把模式所属的类别或同一类中模式的总体称为模式类( 或简称为类) 2 0 1 。而“模式识别”则是在某些一定量度或观测基础上把待识模式划分到各自的模式类中去。模式识别的研究主要集中在两方面，即研究生物体( 包括人) 是如何感知对象的，以及在给定的任务下，如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家、神经生理学家的研究内容，属于认知科学的范畴；后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力，已经取得了系统的研究成果。一个计算机模式识别系统基本上是由三个相互关联而又有明显区别的过程组成的，即模式采集、模式分析和模式分类。模式生成是将输入模式的原始信息转换为向量，成为计算机易于处理的形式。模式分析是对数据进行加工，包括特征选择、特征提取、数据维数压缩和决定可能存在的类别等。模式分类则是利用模式分析所获得的信息，对计算机进行训练，从而制定判别标准，以期对待识模式进行分类。有两种基本的模式识别方法，即统计模式识别方法和结构( 句法)基于内容的图像和视频检索技术研究及其系统实现模式识别方法2 0 1 。统计模式识别是对模式的统计分类方法，即结合统计概率论的贝叶斯决策系统进行模式识别的技术，又称为决策理论识别方法。利用模式与子模式分层结构的树状信息所完成的模式识别工作，就是结构模式识别或句法模式识别。2 1 2 统计模式识别统计模式识别的基本原理是：有相似性的样本在模式空间中互相接近，并形成“集团”，即“物以类聚 。其分析方法是根据模式所测得的特征向量x i = ( x i l ，x i 2 ，x i d ) t ( i = l ，2 ，n ) ，将一个给定的模式归入c 个类1 ，2 ，( o c 中，然后根据模式之间的距离函数来判别分类。其中，t 表示转置；n 为样本点数；d 为样本特征数。统计模式识别的主要方法有：判别函数法，k 近邻分类法，非线性映射法，特征分析法，主因子分析法等。在统计模式识别中，贝叶斯决策规则从理论上解决了最优分类器的设计问题，但其实施却必须首先解决更困难的概率密度估计问题。b p 神经网络直接从观测数据( 训练样本) 学习，是更简便有效的方法，因而获得了广泛的应用，但它是一种启发式技术，缺乏指定工程实践的坚实理论基础。统计推断理论研究所取得的突破性成果导致现代统计学习理论_ v c 理论的建立，该理论不仅在严格的数学基础上圆满地回答了人工神经网络中出现的理论问题，而且导出了一种新的学习方法支持向量机【3 】。2 2 支持向量机s v m支持向量机的简称是s v m ( s u p p o r tv e c t o rm a c h i n e ) ，它是一种基于统计学理论的模式识别方法，是统计学习理论中最年轻的内容，也是最实用的部分，其核心内容在1 9 9 2 1 9 9 5 年间提出2 1 1 ，目前仍处在不断发展阶段。支持向量机可用于模式识别、回归分析、主成分分析竺寸o硕士学位论文2 2 1 支持向量机的分类s v m 的目标就是找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。s v m 的解决方法是构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题( c o n s t r a i n e dq u a d r a t i cp r o g r a m i n g ) ，求解该问题，得到分类器。按照支持向量是否线性可分可以分为线性可分支持向量机、线性不可分支持向量和非线性支持向量机三类。线性可分支持向量机这是最简单的情况，对可分的训练样本训练出线性支持向量机。现有如下训练样本：扛，yf 土i = 1 ，y f - - 1 , 1 j ，x f r 假设有一个超平面可以把如上样本分成两类，那么所有在这个超平面上的点x 满足w o x + b = 0 ，w 是超平面的法向量，是点积运算，h 州叫i 是原点到超平面的垂直距离，州f = z w , 木w 。假设4 和以分别是类一和类二样本中到超平面的最近距离。定义实现如上分类的超平面的分类间隔( m a r g i n ) 为以+ 以。在线性可分情况中，支持向量机算法就是寻找使分类间隔最大的超平面。假设所有的训练样本满足如下约束：x i w + 6 1 、魄= 1x w + b - 1v y , = - 1￥吖夕也就是要找到一个判别函数厂也嵋6 ) = s i g n ( w x + 功。等式可以用一个不等式来表示：m ( 薯w + 6 ) 一1 0 ( v f )如上的两个不( 2 2 )基于内容的图像和视频检索技术研究及其系统实现口口一口口口oo图2 一l 线性司分支持向量机考虑两类中使不等式等号成立的样本点位于的超平面日。：x ，w + b = 1 和超平面h ：x ，w + b = 一1 。两个超平面h ，和h ：到原点的距离分别是1 1 6 w l 降口i 一1 6 w | | o 从而d + , dd 一的值都是1 州w i i ，分类间隔的值为2 1 1 叫i 。要注意的是超平面q 和h ：相互平行( 两者的法向量相等) ，并且没有任何训练样本位于这两个平面之间( 图2 i ) 。满足条件y i ( x ，w + 6 ) 一1 0 ( v f ) 且使| | w | 1 2 最小的分类面就叫做最优分类面，位于超平面h 和日：上的训练样本点就称作支持向量。这样，寻找最优平面的问题可以表示如下：m i n w 6 i m i z e( w ) 2 割w( 2 - 3 )w d”。i - 满足y j ( t w + 6 ) - 1 o ( v f )在解这个问题之前，我们先看一下约束条件下拉格朗日最佳求解公式。假定有如下的约束最优化问题p ：m l n ( 2 - 4 )满足g ，( x ) ( f - 1 ，p )则约束最优化问题尸的拉格朗日函数为l p = ( x ) 一“，g ，( x ) ，其中“，( “，o ) 是拉格朗日乘子。也就是说，用目标函数减去芷的拉格朗日乘子与约束方程乘积就是拉格朗日函数。那么上述寻找最优平面的问题，为每个y ，( x ，w + 6 ) 一1 0 ( v f ) 引入拉格朗日正数乘子( 相当于为每个样本引入正数乘子) a i ( 1 i f ) ，则有拉格朗日函数方程：硕士学位论文l p ：iw u 2 一i 刚融，w + 6 ) + 圭口，( 2 - 5 )由于函数极值( 不论极大值还是极小值) 处的倒数都为零。这意味着从上面也可以同时求出。的极大值，这叫做“w o l f 双向问题”。为了求三。关于w 和b 的最小值，在方程中对w 和6 进行微分，得到：w = aiy ，b 1( 2 - 6 )，、，aiy ，= 0把w ：圭q m _ 和iq y ，：o 代入三p ，同样可以求得三p 的最大值三。= 口，一砉a ，a j y ，y x ，x = 口，一寺a ；a y ，y x ，x ，( 2 7 )ini|j这样从最初的判别函数f ( x ，w ，6 ) = s i g n ( w x + b ) 变为，f ( x ，w ，6 ) = , i g 力( e e f 口f x j x + 6 ) 。i = 1线性不可分支持向量机上面的算法是应用于线性可分的样本，当把这个算法应用到线性不可分样本时，将发现没有可行解。因此，现考虑如何使上面的算法能够应用到线性不可分的样本中去。一个直接的想法是在线性不可分的情况下，在上面的条件中增加一个松弛项( s l a c k ) 专o ( 1 z 勿，为：x f w + b + 1 一参v y f = 1x 。w + b - 1 + 参v y j = - 1( 2 - 8 )六0v i如果存在线性不可分的样本( _ ，y f ) ，那么其对应的茧存在，所以，彭是训练错误的上界。为了使训练错误最小，一个最直接的方法是基于内容的图像和视频检索技术研究及其系统实现把求解的目标从最小化i | w | 1 2 变成最小化| 1 w l l 2 + c ( ，鲁) ，其中c 是参数，c 越大表示对训练错误的惩罚越大。当七为正整数时1 1 w l | 2 + c ( 。鲁) 仍然是一个凸规划问题，k = 域七= 2 时为二次规划问题。按照线性可分的原理，同样可以得到在约束条件下的拉格朗日方程：三p = 去w l l 2 + c 六一z a 。，( z ，w + 6 ) 一l + 茧) 一“，茧( 2 - 9 )厶fff其中c 是用户指派的参数，“，是用来强化鼻正性的参数。非线性支持向量机如果训练样本是用线性可分和线性不可分支持向量机均不能有效识别分类，那么必须将上面的算法推广开来，去求解非线性判断函数。求解非线性可分函数需要两个步骤：( 1 )把训练样本中的数据映射到高维特征空间( 2 ) 在高维特征空间构造一个最佳分类平面进行第一个步骤的原因来自于c o v e r 定理：一个复杂的模式识别分类问题，在高维空间比低维空间更容易线性可分。假设通过函数矽把样本中的数据映射到了高维空间h ：巾：r njh观察到在线性可分和不可分情况下都只用到了原空间的点积运算，那么非线性训练算法中的数据就是( _ ) ，( x ，) ，如果存在核函数( k e r n e l ) k 使k ( x 。，x ，) = ( 一) 矽( x ，) ，那么在训练中只需考虑核函数k ，不必明确知道映射矽。在第二步骤中，可以按照前面描述的方法构造最佳分类面，只不过支持向量不是直接来自于输入样本，而是映射后的高维特征空间。则在高维特征空间中所构造的判别函数为：n 。n 。厂( x ) = s 咖( 口，y ，地) 矽( x ) + 6 ) = s 咖( 口，y ，k ( s ，x ) + 6 )( 2 - 1 0 )硕士学位论文其中，m 是高维特征空间的维数，s ，是支持向量以下是一些常用的内积核函数：k ( x ，y ) ：p i i * - y i l 2 ，2 口2径向基神经网络内积核函数k ( x ，y ) = ( 1 + 砂) p多项式学习机内积核函数k ( x ，j ，) = t a n h ( x y 一万)多层s i g m o i d a l 神经网络内积核函数2 2 2 支持向量机的输出支持向量机本质上解决的是两类识别问题，其输出也是类别标志( 如上述的1 和一1 ) 。在 2 2 中，j o h ncp l a t t 提出了将类别标志转换成概率输出。2 3 广义支持向量机g s v m基于支持向量机的相关反馈应用到基于内容的图像检索，大大改善了其检索性能。在2 2 节介绍了支持向量机的三种类型，这三种支持向量机都要求数据点是等维的，而我们在对图像进行特征提取时，往往会出现提取的特征不等维的情况，这样就需要一种新的方法来解决数据不等维的问题。广义支持向量机g s v m ( g e n e r a l i z e ds u p p o r tv e c t o rm a c h i n e s ) t 2 3 】彳艮好的解决了这个问题。+ 假设x r ”，b r “7 ，核函数k ( x ，b ) 将将r “r “，映射到r “。的空间。如果x ，b r ”，则七 t ，x r ) r ”，k ( x r , 6 ) r ，k ( x ，x7 ) r ”m 。给定训练样本 ( t ，y m ? ，x ，r ”，y ， 1 ，一1 ) ，用矩阵可表示为x r ”及y r m ，其中y r ”为对角矩阵，值为1 或1 。假设我们有一个可分超平面定义如下：k ( x r , x r ) 】，u = b( 2 - 11 )其中u r m , b r 。在特殊情况下k 是满足条件的内积核，那么式( 2 11 ) 可表示为：( x ) 7 矽) 7 1 y u = b( 2 - 1 2 )其中：r ”jr 2 ，z 胛。式( 2 11 ) 中的参数甜和6 可以通过解如下的优化问题得到：基于内容的图像和视频检索技术研究及其系统实现a r gm i n 蛐，fc e 。孝+ o ( u )s f r ( k ( x ，x7 ) r u e 6 ) + 孝e孝0( 2 1 3 )其中e r ”是单位1 的列向量，秒是凸函数，c 是一个正参数，和分离表面参数u 的控制相对，它是对训练错误惩罚的系数。“的控制可以理解为用正的拉格朗日乘子极小化式( 2 - 1 3 ) 1 拘约束数( 如支持向量的个数) 。特别，当秒是由一个正定核推出的二次函数，则可以得到一个极大距离超平面的标准阐释【2 3 1 。式( 2 1 3 ) 的解及相应的决策函数被定义为广义支持向量机g s v m 。一当式( 2 - 1 3 ) 中的目是一个凸二次函数( 如：秒( “) = i 1 “h u ，其中h r ”，是一个对称正定矩阵) ，得到式( 2 1 3 ) 的w 0 1 f 双向问题2 4 】：m i n 舢，i 1 r k ( x ，x7 ) y h 一1 豫( x ，x7 ) ry a - e a ( 2 - 1 4 )s f p y a ：00 口c e 且u = h r k ( x ，x7 ) 7 y a 。如果k ( x ，x7 ) 是对称正定矩阵，h = y k ( x ，x7 ) 】，则“= a ，上述问题就变成了2 2 节所讲的支持向量机。 2 3 】中的基本思想是矩阵h 取不同的值，仍然可以控制z ，。最简单的例子，当h ：，“= r k ( x ，x7 ) r 口，会有如下的双向问题：m i n a 。r m2 a y a y a p 口( 2 - 1 5 )cfp y a = f 1其中a = k ( x ，x7 ) 尼( x ，x7 ) 7 1 是一个半正定矩阵，所以这是一个对任硕士学位论文意核函数都可解的凸二次问题2 3 1 。2 4 本章小结本章主要介绍了统计模式识别中支持向量机。其中广义支持向量机和非线性支持向量机是本文基于内容的图像检索和视频检索中将要用到的两种重要的分类器。将在后续章节介绍我们是如何将其应用到本文开发的原型系统中的。基于内容的图像和视频检索技术研究及其系统实现3 1 系统框架第三章基于内容的图像检索系统本文开发的基于内容的图像检索系统如图3 - 1 所示。首先对源图像库进行特征提取，生成与源图像库对应的图像特征库。根据用户输入的查询图，提取特征，进行匹配，并对返回的结果进行评价，满意则退出并显示最终的查询结果，否则继续进行检索，直到结果满意为止。本文所建的图像检索原型系统主要是用来验证所给的算法是否有效，同时也结合其它算法进行比较。图3 一l 基于区域的图像检索系统硕士学位论文下面分别从特征提取，特征匹配及广义支持向量机这几个方面来讲述本系统是如何实现的。最后给出了本文提出的算法与其他算法进行比较的结果，证明了本文提出的匹配算法的有效性。3 2 特征提取基于内容的图像检索首先要解决的问题就是图像内容的分析和表示。图像内容的分析和表示指的是通过对图像像素的颜色属性以及像素间的相互关系进行分析，从而得到一系列数字或者描述特征，这些特征可以在一定程度上描述图像本身的内容。然后，利用这些特征可以对图像建立索引，从而达到图像检索的目的。因此，图像内容的表示问题本质上是一个图像特征的提取问题。从广义上来讲，图像的特征包括基于文本的特征( 如关键字、注释等) 和视觉特征。视觉特征又可分为通用的视觉特征和领域相关的视觉特征。前者用于描述所有图像共有的特征，与图像的具体类型或内容无关，主要包括色彩、纹理、形状；后者则建立在对所描述图像内容的某些先验知识( 或假设) 的基础上，与具体的应用紧密有关，例如，人的面部特征或指纹特征等。本文主要讨论的是基于通用的视觉特征的图像内容的分析方法。3 2 1 颜色特征颜色特征是在图像检索中应用最为广泛的视觉特征，主要原因在于颜色往往和图像中所包含的物体或场景十分相关。此外，与其他的视觉特征相比，颜色特征对图像本身的尺寸、方向、视角的依赖性较小，从而具有较高的稳健性。图像颜色特征的表达涉及如下三个方面的问题：一是选择一个合适的颜色空间；二是将颜色特征量化为向量形式；三是定义一种相似度( 距离) 标准用来度量不同图像之间在颜色上的相似性。颜色空间的表示有很多种模型，如三原色法( r g b ) 、亮度色差法( c i e ) 、色度饱和度强度法( h s i ) 和色度饱和度亮度( h s v ) 2 5 等。但是，最完备的颜色分辨率应包括色品分辨率和光亮度分辨率两部分，也就是对明度、饱和度、色调这三个特性的综合分辨能力。r g b 颜色空基于内容的图像和视频检索技术研究及其系统实现间中的颜色不能与感知上的颜色模型相联系。实验证明，h s v 颜色模型比h s i 颜色模型更与人类对颜色的感知接近，可以更好的的反映人对色彩的感知和鉴别能力，非常适合基于颜色的图像相似性的比较。本文仅用到了r g b 和h s v 这两种颜色模型，下面介绍这两种颜色模型，及它们之间的转换公式。r g b 颜色模型国际照明委员会( c i e ) 所制定的r g b 颜色表示红、绿、蓝三种单色光作为彩色系统的三基色，任何颜色都可以通过这三种基色表示得到。r g b 颜色空间是三维直角坐标系颜色系统中的一个单位正方体，在此系统中计算的任何颜色都落在该正方体内，如图3 2 ，从立方体的原点( 黑) 到白色顶点的主对角线称为灰度线，线上所有点具有相等的红、绿、蓝三分量。蓝图3 - 2 r b g 颜色分量图r g b 空间的优点是比较简单、直观，但是r g b 空间也有其不足之处。首先，r g b 空间是颜色显示空间，不能直观的反映人的视觉感知；其次，r g b 空间中两点的欧氏距离与实际颜色的距离不是线性关系，从而极易造成颜色分离中的误分离，漏掉有用信息或夹杂无用信息。h s v 颜色模型h s v 颜色空间是孟塞尔彩色空间的简化形式，以色彩的色调( m 、饱和度( s ) 和亮度( v ) 为三要素来表示颜色空间，属于非线性色彩表示系统，如图3 3 ，h s v 颜色表示方法同人对色彩的感知相一致，是较为适合人的视觉特性的色彩空间。硕士学位论文j 、hjnj力刚u cir ij汰形、s图3 - 3h s v 模型的坐标系统依据t e k t r o n i x 彩色标准，色调h 的值域为 0 。, 3 6 0 。】，其中，0 。为蓝色，1 2 0 。为红色，2 4 0 。为绿色；亮度的范围为【o ，1 0 0 】，依次表现为从黑到白的变化；饱和度的范围为 o ，1 】，颜色依次加浓。r g b 空间到h s v 空间的转换【2 6 】：给定r g b 颜色空间的值( ，g ，6 ) ，( ，g ，6 ) o ，2 5 5 ，则变化到h s v空间的( 办，s ，v ) 值计算如下：当m a x ( r ，g ，6 ) m i n ( r ，g ，6 ) 时j2v m i n ( r ，g ，b )v1 ，= m a x ( r ，g ，b )h =5 + 6 ，f ( ，= m a x ( r ，g ，6 ) & g = m i n ( r ，g ，6 ) )1 一g 。，f ( r = m a x ( r ，g ，6 ) & g m i n ( r ，g ，6 ) )1 + r 。，矿( g = m a x ( r ，g ，b ) & b = m i n ( r ，g ，白) )3 一b ，f ( g = m a x ( r ，g ，6 ) & b m i n ( r ，g ，6 ) )3 + g ，f ( 6 = m a x ( r ，g ，6 ) & ，= m i n ( r ，g ，6 ) )5 一，o t h e r w i s e上瓦甲：r 一 v r 】一7 【v - m i n ( r ，g ，6 ) 】g = v - m i n 咖)6 。= 卜_ m i n g ，6 )则h = h * 6 0 ，s = s ，v = v 2 5 5当m a x ( r 2 ，b 、r a i n ( ，2 6 、，巳口r ：2 ：b 日寸，h ：s ：0 ，v ：，2 5 5 ；1 8基于内容的图像和视频检索技术研究及其系统实现其中，g ，b o ，2 5 5 ，h 0 。, 3 6 0 。】，s 【o ，1 ，v o ，l 】本文中提取的颜色特征在介绍了r g b 和h s v 两种颜色模型后，下面将介绍本文是如何提取颜色特征的。本文用到的图像数据库中的图像大小是2 5 6 x3 8 4 或者3 8 4 2 5 6 像素，在提取图像特征时将图像分成了m n 个4 4 像素块，然后对每个块提取颜色特征( 后面讲到的纹理的提取也是基于此块的) 。图像的颜色特征有颜色直方图、颜色矩、颜色集、颜色聚合向量和颜色相关图等。本文中因为每个块比较小，这些颜色特征在这里并不适用，本文提取的颜色特征仅仅是基于像素的各个颜色分量的平均值( 在h s v 颜色模型中) 。每个小块提取颜色特征的公式如下：砝去善荟砸棚j 2 去善酽棚( 3 - 1 )。去善驴3 2 2 纹理特征纹理也是描述图像内容的一个重要特征，特别是对灰度呈梯度变化的图像。它是一种不依赖于颜色或亮度的反应图像中同质现象的可视化特征【2 7 】，它能反映宏观意义上灰度变换的一些规律。从人类的感知经验出发，纹理特征主要有粗糙性、方向性和对比度，这也是用于检索的主要特征。基于纹理特征的图像检索技术与纹理分类技术密切相关。纹理分类就是通过图像处理技术提取纹理特征，研究这些纹理在图像中反复出现的局部模式和它们的排列规则，获得对纹理的定量描述，进而对图像或物体进行正确分类。对纹理图像的描述常借助纹理统计特性或结构特性进行，对基于空间域的性质也常可转换变换到频率域进行研究，所以常用的三种硕士学位论文纹理描述方法是：统计法。统计法是根据像素灰度的统计特性确定纹理特征的，如直方图统计特征法、自相关函数法等；这种方法被用于分析像木纹、沙地及草地等纹理细而又不规则物体。频谱法。频谱法是将图像变换到频域，从频谱导出其纹理特征的。如基于傅立叶变换的纹理描述、基于小波变换的纹理描述等。结构法。结构法是将复杂的纹理图像通过特征提取和分割得到局部基元和它们的属性及其相互关系，对纹理基元及其排列规则进行描述、分析和解释。这种方法适用于分析布料图案或砖的花样等一类由规则基元组成的纹理。结构法纹理描述在实际运用中没有统计法和频谱法那样广泛。这些方法的共同点是：提取了特定纹理描述中最重要的特征，突出了纹理的不同方面。下面主要介绍统计法纹理描述和频谱法纹理描述。( 1 ) 统计法纹理描述统计法纹理描述方法利用适合于统计模式识别的形式来描述纹理。在每个纹理描述结果中，每个纹理属性用一个特征向量来描述，它代表了多维特征空间中的一个点。它的目标是寻找一个确定性的或者概率型的决策规则给纹理赋予特定的类别【2 8 1 。统计法纹理描述方法主要有基于共生矩阵的模型、基于自相关函数的模型、分形模型和数学形态学的方法等。以下主要介绍基于共生矩阵的模型和基于自相关函数的模型。基于共生矩阵的模型【2 9 】共生矩阵是用来描述纹理中灰度基元之间的空间联系的基础。基于共生矩阵的模型充分利用了纹理中灰度分布的性质。假设在纹理图像的某个部分是一个n xn 的窗口，间距为d 的两个灰度级像素同时出现的联合概率分布可以用灰度共生矩阵局。( f ，) 来表示。它描述了具有灰度级i ，的两个像素，在方向p 上间隔距离为d的条件下，它在该窗口出现的最大频率。对粗纹理的区域，其灰度共生矩阵中的值相对集中于主对角线附近，因为对于粗纹理，像素对趋于具有相同的灰度。而对于细纹理的区域，其灰度共生矩阵中的一值则散布在各处。各个共生矩阵可以通过对距离和方向的各个组合来定义。对矩阵有贡献的像素对总数m ，比物体内部像素的个数少，而且这个数目随基于内容的图像和视频检索技术研究及其系统实现着距离的增加逐渐减少。因此，小物体的矩阵会相当稀疏。鉴于上述原因，常常减少划分灰度级数目，以便于共生矩阵的计算。基于共生矩阵的纹理特征：熵：h = p ( f ，j ) l o g p ( i ，)熵值是图像所具有的信息量的度量，纹理信息也属于图像的信息。若图像没有任何纹理，其灰度共生矩阵几乎为零阵，则熵值接近为零。若图像充满着纹理，那么( f ，) 的数值近似相等，则该图像的熵值最大。若图像中分布着较少的纹理，那么( f ，) 的数值差别较大，则该图像的熵值较小。对比度：，= ( f 一1 ) 2 p ( f ，)亦称对角线的惯性矩。图像的对比度可以理解为图像的清晰度，即纹理清晰程度。在图像中，纹理的沟纹越深，则其对比度越大，图像的视觉效果越是清晰。能量：e = 【p ( f ，朋2能量是图像灰度分布均匀性的度量。当灰度共生矩阵中的元素分布较集中于主对角线时，说明从局部区域观察图像的灰度分布是较均匀的；而从图像整体来观察，纹理较粗，此时能量值较大，反之则能量值较小。粗纹理的能量值较大，可以理解为粗纹理含有较多的能量。细纹理能量值较小。也即它含有较少的能量。相关性：r ：芝n 7 n i j p ( i , j ) _ u x u y i百f - ：- 1 a盯r 盯v式中“，“，是均值，吒，仃。是标准差：虬= f p d 口( f ，)甜y = p 枷( f ，)q = ( i - u ，