（计算机应用技术专业论文）视频数据库多维索引结构的研究与实现.pdf

北京交通大学硕 于学位论文 摘要 丫 5 8 6 2 1 1 随着信息社会的到来，多媒体技术的发展和信息高速公路计划的 实施使人们越来越多地接触到大量的多媒体信息，同时每天又有大量 的信息在不断地产生。如何对大量的多媒体信息组织、建库以及对巨 容的多媒体信息库进行快速有效的检索就成为人们迫切解决的问题。 索引是快速访问大型数据库的前提，因此视频数据库的索引就有着举 足轻重的作用，成为国内外研究的热点。在过去的三十 年里，图像检 索技术和多维索引结构的研究已经取得了巨大的成绩，然而，还存在 一些问题值得人们继续研究。 本文主要包括以下几方面的_ i = 作。 首先，本文对视频数据库的相关知识、基于内容检索的关键技术 进行了介绍;对多维索引结构的特点、分类和其性能的影响因素进行 了系统的归纳与总结，对多维索引结构的现状进行分析，最后指出了 目 前存在的问题和今后的研究方向: 其次，对 o m n i 一 顺序扫描算法，基于 n b - t r e e范围查询的索引结 构提出了改进，实验数据验证了改进后的索引方法的有效性; 最后， 在前几章的理论与实践的基础上提出了一种简单有效的索 引方法:f a c - f i l e ，详细的论述了该方法的基本思想、基本概念、过 滤原理和实现过程，并将此索引方法应用于一个简单的图像检索系统 中，取得了较好的检索性能。 关键词视频数据库，基于内容检索，多维索引结构，范围查询，相 似度度量 未经作青 , 导萨尸产 勿全文毛 卜 珠 北京交通大学硕士学位论文 ab s t r a c t wit h t h e c o m i n g o f i n f o r m a t i o n s o c i e t y ， t h e d e v e l o p m e n t o f m u l t i m e d i a t e c h n i q u e s a n d t h e im p l e m e n t a t i o n o f i n f o r m a t i o n h i g h w a y m a k e p e o p l e c o n t a c t w i t h m o r e a n d m o r e m u l t i m e d i a i n f o r m a t i o n . i n a d d i t i o n , a b u n d a n t i n f o r m a t i o n c o m e s i n t o b e i n g e v e ry d a y . i t s u r g e n t f o r p e o p l e t o s o l v e h o w t o o r g a n i z e t h i s i n f o r m a t i o n a n d h o w t o r e t r ie v a l i t q u i c k l y . i t s w i l d l y k n o w n t h a t i n d e x e s a r e p r e c o n d i t i o n s a c c e s s i n g t o l a r g e d a t a b a s e q u i c k l y . s o i n d e x e s o f v i d e o d a t a b a s e a r e v e ry i m p o r ta n t a n d h a v e b e c o m e h o t s h o t o f r e s e a r c h . i n t h e l a s t t h i r ty y e a r s , g r e a t a c h i e v e m e n t s a b o u t i m a g e r e t r i e v a l t e c h n i q u e s a n d m u lt i - d i m e n s i o n i n d e x s t r u c t u r e s h a v e m a d e . y e t , t h e r e a r e m a n y o t h e r p r o b l e m s t o b e r e s o l v e d . t h e m a i n w o r k o f t h i s p a p e r i s a s f o l l o w s . f i r s t , t h e c h a r a c t e r i s t i c s o f mu l t i - d i m e n s i o n a l i n d e x s t r u c t u r e s a n d s i m i l a r i t y m e a s u r e o f r e t r i e v a l a r e i n t r o d u c e d , t h e c l ass i f i c a t i o n s o f in d e x s t r u c t u r e s b y t h e i r i n t r in s i c f e a t u r e s a r e d i s c u s s e d . a n d t h e f a c t o r s a n d t h e e v a l u a t i o n o f t h e i n d e x s t r u c t u r e s a r e s u m m a r i z e d . i n a d d i t i o n , s o m e r e p r e s e n t a t i v e a n d n e w e s t i n d e x s t r u c t u r e s a r e i n t r o d u c e d . b a s e d o n s u r v e y , s o m e o p e n i s s u e s w h i c h n e e d t o b e s e a r c h e d f u r th e r a r e p r e s e n t e d a n d t h e f u t u r e r e s e a r c h t r e n d s a r e a l s o g i v e n . s e c o n d , t h e i m p r o v e m e n t s o f o n u n i - s e q u e n t i a l s c a n a l g o r it h m a n d n b - t r e e b a s e d o n r a n g e q u e ry a r e p ro p o s e d . t h e e x p e r im e n t a l r e s u l t s s h o w t h e e f f i c i e n c y o f t h e n e w a l g o r i t h m . a t l a s t , a s i m p l e y e t e ff i c i e n t i n d e x m e t h o d i s p r o p o s e d b as e d o n t h e f o r e g o i n g t h e o ry a n d p r a c t i c e . t h e b a s i c i d e a , b a s i c c o n c e p t s , f i l t e r i n g p r i n c i p l e s a n d p r o c e s s o f i m p l e m e n t a t i o n a r e d i s c u s s e d i n d e t a i l . i n a d d i t i o n , t h i s i n d e x m e t h o d i s i m p l e m e n t e d i n t o a s i m p le i m a g e r e t r ie v a l s y s t e m a n d g o o d r e t r i e v a l p e r f o r m a n c e i s a c h i e v e d . k e y w o r d s v i d e o d a t a b a s e , c o n t e n t - b a s e d r e t r ie v a l , m u l t i - d i m e n s i o n a l i n d e x s t r u c t u r e , r a n g e q u e ry , s i m i l a r i t y v a l u e 北京交通大学硕士学位论文 绪论 论文背景及其惫义 近年来，随着数据压缩、宽带网络、高速计算机技术的发展，人 们越来越多地接触到大量的多媒体信息。每天又有大量的信息在不断 地产生。 其中 视频数据作为存储声像信息的一类非常特殊的多媒体数 据，因为具有直观、效率高、容量大、适用范围广等优点而得到了越 来越多的应用，已经成为多媒体计算和通讯环境中的重要元素。 数字视频作为一种多媒体信息，属于一种非数值数据，与传统数 据库的字符数值数据有着很大的不同。数值字符型数据的结构简单， 常常以记录类型表示，有十分确切的含义。而视频数据是一种内涵丰 富、结构复杂的新的数据类型，有着自 身的特点，主要体现在以下几 个方面。 ( 1 )视频数据含有丰富的信息内容。视频信息作为一种表达信息 的媒体，其内容可分为两类，一类是视频中含有的声音及可视的外部 表示， 一类是视频中包含的语义内 容。由 于视频所含的信息十分丰富， 不同的人对同一幅图片或一段视频可能有不同的理解，这样就由于视 频内 容的模糊性导致了视频数据的主观性和多样性。此外，视频数据 具有较高的信息分辨率，随着观察的深入，可以从视频数据中逐渐获 得一些新的细节。 ( 2 ) 视频数据具有复杂的结构和关系。文本数据是一种纯字符数值 数据，不涉及到时间和空间属性，图像数据是一种具有空间属性而无 时间属性的数据。然而视频数据除了 具有空间属性外，还有时间属性， 有时也将其称为三维数据。空间维是指每一幅图像均是空间二维结构， 图像中所蕴含的空间信息十分复杂，很难建立一种清晰的结构;时间 维是指视频是由多个图像帧构成的沿时间轴分布的以图像帧为单位的 流结构，要把视频数据存于数据库中，就要对视频流在不同的层次上 北京交通大学硕士学位论文 分段抽象。视频数据的这种时空特性使其表达和建立数据模型更为困 难，且视频数据段之间的关系十分复杂，这就给视频数据库的建立及 操作带来许多问题。 ( 3 ) 视频数据有巨大的数据量。与字符数值类数据相比，视频数据 具有巨大的数据量。现在己经有文章指出，视频数据的数据量约比结 构记录数据大七个数量级。 这些特点表明，传统的数据库模型己不能满足对于多媒体信息库 的管理和检索要求。在此背景下，建立在媒体信息理解基础上基于内 容检索技术应运而生。如何对对巨容的多媒体信息库进行快速、有效 的检索，就成为信息时代人们迫切需要解决的问 题。我们知道，索引 是快速访问大型数据库的前提。快速的查找操作需要有效的索引结构。 在过去的三十年里，已 经涌现了大量的多维索引结构，取得了很大的 进步。现在的研究已经对多维数据和多维索引结构的特点、影响索引 结构性能的因素和高维空间的本质有了一定的了解。但也存在着很多 问题有待于进一步的研究。传统的高维访问方法的工作主要是:分割 数据空间，根据分割对子空间进行聚类，通过筛选 ( p r u n e )访问部分 子空间，完成查询工作。然而存在的问题是，这些访问方法对维数低 的数据空间的访问性能较好，随着维数的增加，性能急剧下降，以至 于大多数的高维访问方法在维数高于 1 0维的时候性能都不如顺序扫 描。除此之外，目前的索引结构只支持维数固定的数据集的访问。然 而，在一些应用领域中，特征向量的维数是变化的且最大的维数是不 可预测的。此外，许多索引结构都涉及到复杂的难于实现的算法，有 时这种复杂程度和性能的提高是不匹配的。设计一种简单有效的访问 方法一直是研究人员的主要目 标。 基于内容的检索技术主要应用于以下几个方面:将基于内容检索 引擎嵌入到常规的数据库管理系统中，以实现多媒体数据的检索:在 信息检索系统中，对专用领域的视频、图象和文档库进行检索;对 i n t e r n e t 上包含在w e b 信息网中的页面上的对媒体数据进行基于内 容 的检索等。由于基于内容的检索技术有着广阔的应用前景，所以应用 于视频数据库检索的多维索引结构的研究就有着重要的实用价值。这 北京交通大学硕士学位论文 个领域是个方兴未艾的领域，必将会引起人们更大的兴趣和投入更多 的研究。 论文的主要内容和章节安排 本文对多维索引结构进行了深入的研究， 对两种己有的索引结构进 行改进，并提出了一种新的索引方法。论文章节安排如下。 第 i 章 视频数据库对数字视频的结构、特征和视频数据库的主 要问题及应用作概要的介绍。 第2 章 视频数据基于内 容的检索技术对基于内容检索的含义、 基于内容检索系统的结构和检索中的关键技术给予介绍，最后指出目 前存在的问题和研究方向。 第3章 多维索引结构对多维数据和多维索引结构的特点， 影响 索引结构性能的因素以及索引结构的分类进行了介绍和总结。此外， 还介绍了一些经典的索引结构和具有代表性的最近的索引结构。 最后， 分析了目 前存在的问 题，指明了今后的研究方向。 第4章 n e w - o m n i 一 顺序扫描算法详细介绍了n e w - o m n i - 顺序扫 描算法的思想动机、实现原理和实现过程，实验数据验证了算法的有 效性。 第 5章 基于 n b - t r e e范围查询的一种索引结构详细论述了 n e w - n b - t r e e 的基本思想、 实现原理和实现过程。 实验数据验证了算法 的有效性。 第 6章f a c - f i l e :一种有效的多维索引方法详细论述了f a c - fi l e 索引方法的思想来源、过滤原理和实现过程，最后将此索引方法应用 于一个简单的图像检索系统中，实验数据验证了该方法的有效性。 结束语总结论文的主要工作和进一步的研究方向口 北京交通大学硕士学位论文 第 1 章视频数据库 s o年代中后期发展起来的多媒体技术，己 成为世界性技术研究和 产品开发的热点，有着广泛的应用前景。多媒体技术是把文字、图形、 图像、声音、视频等媒体信息与计算机技术集成于统一的数字环境中， 以扩展这些媒体的组合应用。在多媒体信息中，视频信息是一类较特 殊的媒体信息，属于视觉媒体信息，由于其数据量大，蕴含信息丰富， 具有时间和空间结构，其传输、存储、组织及表达有更大的难度。本 章对数字视频的结构、特征和视频数据库的主要问题作概要的介绍。 ， . ， 数字视频的结构和特征 帧序列 像 琴 / 场景 e ( x , v , t ) 1 图1 - 1数字视频结构图 数字视频的结构可以用图1 - 1 表示 1 1 。 由图可见， 数字视频是由 多幅连续的图像构成的，其中的x轴及 y轴分别表示水平和垂直方向 的空间维， 而t 轴表示时间维。 沿x 轴的扫描行上分布有像素点， 沿y 轴方向 表示垂直方向的行数。这样每一个像素点的 颜色或亮度 e可以 北京交通大学硕士学位论文 表示为x y 平面上的函数e ( x , y , t ) 。 数字视频是视频数据库的存储对象。 为了方便的从视频视频数据库里检索视频对象，数字视频应以一定的 结构存储。我们常把送入计算机的一段数字视频称为原始视频流，由 图 1 . 1可见，图像帧是组成视频的最小单位。如果视频信息仅以图像 帧和视频流这两级存储，对视频的检索十分不利，因此，常在两级结 构中引入若干中间级结构，如镜头 ( s h o t ) 、场景 ( s c e n e ) 、序列 ( s e q u e n c e ) 等。 数字视频作为一种多媒体信息，属于一种非数值数据，与传统数 据库的字符数值数据有着很大的不同。数值字符型数据的结构简单， 常常以记录类型表示，有十分确切的含义。而视频数据是一种内涵丰 富、结构复杂的新的数据类型，有着自 身的特点，主要体现在以一 f 几 个方面。 ( 1 ) 视频数据含有丰富的信息内 容。视频信息作为一种表达信息的 媒体，其内容可分为两类，一类是视频中含有的声音及可视的外部表 示，一类是视频中包含的语义内容。由于视频所含的信息十分丰富， 不同的人对同一幅图片或一段视频可能有不同的理解，这样就由于视 频内容的模糊性导致了视频数据的主观性和多样性。此外，视频数据 具有较高的信息分辨率，随着观察的深入，可以从视频数据中逐渐获 得一些新的细节。 ( 2 ) 视频数据具有复杂的结构和关系。 文本数据是一种纯字符数值 数据，不涉及到时间和空间属性，图像数据是一种具有空间属性而无 时间属性的数据。然而视频数据除了具有空间属性外，还有时间属性， 有时也将其称为三维数据。 空间维是指每一幅图像均是空间二维结构， 图像中所蕴含的空间信息十分复杂，很难建立一种清晰的结构;时间 维是指视频是由多个图像帧构成的沿时间轴分布的以图像帧为单位的 流结构，要把视频数据存于数据库中，就要对视频流在不同的层次上 分段抽象。视频数据的这种时空特性使其表达和建立数据模型更为困 难，且视频数据段之间的关系十分复杂，这就给视频数据库的建立及 操作带来许多问题。 北京交通大学硕士学位论文 ( 3 ) 视频数据有巨大的数据量。与字符数值类数据相比，视频数据 具有巨大的数据量。参考文献 2 中指出，视频数据的数据量约比结构 记录数据大七个数量级。 1 .2 视频数据库的层次结构和研究的主要问题 1 . 2 . 1 视撅致据库的层次结构 视频数据库的分层虽然没有统一的形式， 但可以粗略的把视频数 据库的层次结构归纳为图1 - 2 e l l . 用 户 用户 接 口 数 据 模 型 媒体支持 图1 - 2 视频数据库层次示意图 从图 1 - 2可以 看出，视频数据库的第一层为媒体支持层，此层主 要对视频原始信息进行分段及标识等操作。第二层称为数据模型层， 此层主要完成视频数据的逻辑存储向 物理存储的映射，数据的逻辑内 容定义、相互关联及特征均由数据模型所确定。第三层为用户接口 层， 此层完成用户对视频信息的查询描述和查询结果的表现。 1 . 2 . 2视绷致据库主要的研究问百 1 . 1 节论述了视频数据的特点， 正是由于这些特点决定了视频数据 库研究中的特殊问题。 北京交通大学硕士学位论文 ( 1 )视频数据模型的建立 传统的文本数据库系统，由于其数据类型及关系较简单，所以其 数据模型也较为简单。但是，视频数据由 于其信息内容的丰富性、多 样性、结构的复杂性，在视频数据模型的建立中必须考虑一些特殊的 问题，例如，数据模型首先考虑多级视频结构的抽象，还应支持时间 和空间属性，并可从此两个方面对视频数据库进行查询，此外，视频 数据还应考虑视频数据的共享性和独立性。 ( 2 ) 视频数据的插入 传统的数据库主要处理记录型数据，对数据的插入和删除操作十 分方便。然而，视频均是由随时间变化的图像序列构成的，要想对视 频数据进行插入操作，首先要把视频数据划分为有意义的单元，因此 景物变换探测及视频分段就成为视频数据库研究的重要内容。 ( 3 ) 视频数据的索引 在传统的字符数值数据库里，可以明确的指定关键字对数据进行 索引。在视频数据库中，由于视频数据本身信息内容的丰富性和模糊 性，人们很难指定确切的类似关键字的视频单元的描述，视频索引涉 及到对视频内 容的理解，要求直接对视频内容进行分析，抽取特征和 语义，利用这些内容特征建立索引。 ( 4 ) 视频数据的查询及检索 视频数据库管理系统的目 标之一是使用户对视频数据库进行方便 的存取。视频数据的检索和视频数据库的多个方面相关，例如视频数 据模型、查询匹配时选用的特征以 及检索时的索引结构。视频数据库 的查询及检索是视频数据库管理系统综合功能的体现。 1 . 3 视频数据库系统的应用 视频数据库自9 0 年代开始成为多媒体及数据库领域研究的热点， 至今虽然还没有象传统数据库管理系统领域那样有成熟的商业商品问 世，应用也没有传统数据库那样广泛，但是视频数据库与当今多媒体 ( 文本、图像、图形、声音及视频)及其他支持技术 ( 计算机技术、 北京交通大学硕士学位论文 操作系统等)的紧密结合已 广泛的应用于多个领域。 视频数据库在教育及培训领域，例如远程教学、电信教室、交互 培训等，有着广泛的应用前景。用视频数据库进行培训及教育可以开 创出一种完全开放的教育模式，把世界各地有用的信息呈现在用户面 前并提供交互使用。许多研究表明多媒体培训方式比传统的培训方式 要有效4 0 9 6 ，而保持率可提高3 0 06 .娱乐业是视频数据库最大的应用市 场。目前，视频数据库在娱乐业的主要应用领域有影片剪辑数据库、 视频点播、收视计费电视、交互电视以及视频定期服务等。视频数据 库在未来的商业的主要应用领域有电子商务、在线广告、在线购物、 股票视频数据库等。视频数据库在线商业应用还处于酝酿阶段，但快 捷方便的在线网上购物必将逐渐的取代传统的购物方式。此外，未来 的图书馆将是一个数字图书馆，视频数据库将是数字图书馆不可分割 的一部分。视频数据库在多媒体医疗及保健，以及广播及通信方面也 有着广阔的应用前景。 视频数据作为一种动态、直观、形象的数字媒体，越来越多的出 现在各类信息服务及应用的场合。由于视频数据是一种数据量巨大、 信息含量丰富的新型媒体，对其存储、检索、重用的问题必然提到日 程上来，视频数据库系统必然得到迅速的发展，它的发展是未可限量 的。 参考文献 1 周撞汝， 胡鸿斌等， 视频数据库管理系统导论， 科学出 版社， 2 0 0 0 第一版，3 - 1 1 2 a r u n h a m p a p u r , d e s i g n v i d e o d a t a t h e s i s , t h e u n i v e r s i t y o f mi c h i g a n , 1 9 9 5 即s t e m s , p h . d 北京交通大学硕士学位论文 第2 章 视频数据库基于内容的检索技术 随着信息社会的到来，多媒体技术的发展和信息高速公路的实施 使人们接触到越来越多的信息，同时每天又有大量的信息在不断的产 生。如何对大量的多媒体信息组织、建库以 及如何对其进行快速有效 的检索成为人们迫切需要解决的问题，相应的，检索技术成为多媒体 研究中的核心技术。本章将对基于内容检索的含义、基于内容检索系 统的结构和检索中的关键技术给予介绍，最后指出目 前存在的问题和 研究方向。 2 . 1 墓于内容检索的含义 传统的数据库在信息的检索方面采用基于关键字查找的方式，处 理结构化的文本或数值。然而，视频数据库和传统的数据库相比，其 信息量大，具有数据非结构化、数据长度不固定、具有时空特性的特 点，因而传统的数据库在处理视频数据时有着非常大的局限性。近些 年来人们采取的解决办法是这样的:视频流是由随时间变化的图像序 列构成的，因此首先将其划分为有意义的单元，然后从划分后的单元 中提取代表帧，对得到的代表帧提取信息线索，即特征，如颜色、纹 理、运动、轮廓等，这些特征就构成了单元的内容描述。在检索的时 候根据一定的相似度量度返回视频数据库中内容描述最满足要求的一 组媒体对象。这种检索方法就称为基于内容的检索。 基于内容的检索一般有下面的特点:从媒体中提取的信息线索突 破传统文件检索的局限性，利用提取的特征进行匹配，使检索的结果 更加接近媒体对象;在检索的过程中人对特征比较的敏感和计算机重 复工作的优点，检索过程是个人机交互的过程;检索的过程是个近似 n配的过程，与传统数据库的精确匹配方法有着明显的不同。 北京交通大学硕士学位论文 2 . 2 典型的基干内 容检索系统的结构图 典型的基于内容检索系统的结构图如下图所示。 输入视频 ，.f-.。1。.j r -一，一 -一 t一一一 一- - 征述 特描 i .对象标识 2 . 特征提取 3 .建立索引 4 .数据入库 图像库/ 特征 库 r 一 一 - 一 - - - - 一 ， 检索 gl/滤 索过特征 r.11-we 对识 查询 交息 监 一 . 一 一 _ _ _ _ l-一_ 一_-一_ _ _ 图2 - 1 c b 工 r 系统结构图 从上面的图可以看出， 基于内容的检索有如下三个方面需要研究。 ( 1 )特征描述 特征描述即利用媒体分割与特征提取来建立媒体对象的结构描述 1 0 . 北京交通大学硕士学位论文 和特征描述。基于内容的检索与传统检索手段的主要区别在于融合了 媒体理解技术对媒体对象的内容进行描述，因此特征描述机制是基于 内容检索系统的关键。 ( z )检索要求的表达 在对媒体对象建立内容描述后，系统还需要有一种将用户的检索 要求转化为计算机可比 较的内容的检索表达机制。由于用户通过此机 制来提出检索要求的，因此检索要求表达机制的能力在很大程度上决 定了一个检索系统的检索能力。 ( 3 )对内容描述的快速索引 由 于基于内容的索引是面向大容量的多媒体信息库的，在检索时 顺序计算库中的每个对象与查询对象之间的距离难于满足实时检索的 要求。因此建立快速的索引机制是必须的。 2 . 3 基于内容检索的关键技术 2 . 3 . 1 圈像的内容特征及提取 图 像的内 容可以 理解为三个层次: 第一层为原始数据层，即元素 的原始像素点;第二层为物理特征层，反映了图像内容的底层物理特 征，如颜色、纹理、运动、轮廓等:第三层为语义特征层，是人们对 图像概念级的反映。图像检索时用的特征大多属于第二层和第三层特 征。 色彩是物体表面的一种视觉特征，每种物体都有其特有的色彩特 征，同一类物体往往有着相似的色彩特征，很少有两个完全不同的对 象有相似的颜色特征， 因此人们可以 根据色彩特征来区分物体。由 于色 彩直方图具有简单且随图像的大小、旋转变化不敏感的特点，得到了 研究人员的广泛关注，已经成为了视频数据库检索的重要手段。颜色 特征主 要表示 方法 有【 1 : 颜色直 方图; 颜色一 致性矢 量; 颜色相关图: 颜色矩等。 颜色直方图的比 较方法是最基本的方法 2 ，但缺乏图 像的 北京交通大学硕士学位论文 空间信息。在颜色直方图中，可能有许多颜色的统计值很小，这里大 多数是噪声点。为了 消除外来的影响，可以采用一个阐值加以限制， 对不超过这个阐值的颜色不进行比较，这个闽值要根据颜色数和实验 结果进行调整。由于颜色直方图实际上是颜色分布的统计特征，因此 观察轴旋转和平移时，颜色直方图是不变的。当视角和距离尺度改变 时，颜色直方图的变换也比 较缓慢。这对算法的抗干扰能力是有利的。 为了减少这种误识别，可以采用子块划分的匹配方法。主导颜色可以 从颜色直方图中的到，而平均颜色反映了图像整体在颜色空间各轴上 的平均亮度水平。利用主导颜色和平均颜色进行图像的相似匹配是很 粗略的，但是它们可以作为检索的粗查。颜色一致性矢量的方法不仅 统计整幅图像中各颜色的像素值，还统计各颜色最大区域的像素数， 效果较好，但颜色一致性矢量并没有强调各颜色区域的形状以 及与背 景的关系。颜色相关图强调颜色在图像中空间距离的相关性，其检索 效果也较好，但计算量比较大，颜色矩算法主要是采用图像中各颜色 的均值和方差作比较，处理简单，可作为图像检索的初检。总的说来， 基于颜色的索引技术可分为两类:全局颜色特征索引和局部颜色特征 索引。目 前存在的主要问题是色彩空间的选择不统一，关于色彩之间 的量度也不统一，给各种方法的效果评价带来一定的难度。 纹理也是图像中一个重要而又难以描述的特征。纹理特征包括粗 糙 度、 方向 性和对比 度等 3 ， 这也是基于纹理 特征 索引 所要 提取的 主 要特征。目 前关于纹理分析的算法不少，大致可以分为两大类:一类 是统计分析的方法，主要从图像灰度等属性的统计分析出发;另一类 是结构分析方法，主要用纹理基元及其排列规律来描述纹理的结构及 特征 4 。 无论从历史还是当前来看， 统计方法在纹理分析中占 主导地 位。随着小波变换在图像纹理分析中的广泛应用，一些人也采用小波 变 换后的 系数 作为图 像的 索引， 如s m i t h 和c h a n g 从小 波子 波段中 提 取统计特征作为图像纹理表示， 取得了 很好的 检索效果 5 。从目 前的 发展趋势来看，大多数新技术是建立在纹理检索模型的基础上，因为 可以通过纹理模型参数对应纹理分类，从而用较少的参量表示较多的 信息，可以极大的提高检索和匹配的谏fv 北 京交通大学硕士学 位论文 在人的视觉感知、识别中，形状是一个重要参数。在二维情况下， 我们可以认为形状是定义在二维范围内一条封闭边界和其包围区域的 描述，在三维空间内可以看作是封闭曲面和所围体积空间的描述。目 前幕于形状的索引方法大多围绕着从形状的轮廓特征和形状的区域特 征建立图形索引。关于对形状的轮廓特征的描述主要有;直线段描述、 样条拟合曲线、傅里叶描述子及高斯参数曲线等。对于形状的区域特 征 主要有形 状的 无关区 域的 面积、形状的纵横比等。实际更常用的办 法是采用区域特征和边界特征结合起来的方法。 轮 廓是图 像的 又一 个特征。 轮廓图 就是图像中各 物体外形所形 成的 图，一般要经过边缘检测、细化等处理后才能得到。将检出的边缘连 接或编组成有意义的图像事件，例如直线、曲线、各种轮廓线等，这 是图像理解中的一个基本而重要的内容。由边缘组成线特征是一个大 课题，目 前已 有启 发式连接、 h o u g h变换、 相位编组 和层次 记号编组 等多种方法。实际上对图像的描述就是形状。应当指出，在基于轮廓 的检索中，用户勾画的只是整个图像目标的大体描述，如果用整个轮 廓线作为匹配特征并不合适，必须进行简化。对轮廓的检索过程是人 机交 互的。 q b i c系统 6 中 采用分块相关法 进行轮廓之间的比 较。 这种 方法不具有尺度和方向的不变性，并且边缘检测、细化等预处理直接 决定了图像轮廓的质量，对图像检索的结果具有很大的影响。 2 .3 .2相似度计算 基于内容的图像检索是一种基于相似度的检索，相似度的度量问 题是基于内 容图像检索的重要方面。 相似度反映的 是视频库中 的对象 与查询对象之间的相似程度，目前对相似度还没有统一的定义，因为 相似度的度量高度地依赖于实际应用的要求，与检索系统所采用的特 征和索引方法都有着直接的关系。 距离度量是相 似度度量中的 一种常用方法， 表达式为: 距离度量的 北京交通大学硕士学位论文 d ( x , y ) = ( 艺ix 一 y , d , 其中x , y代表视频库中的 两个对象， x , y i 代表其特征分量。当二1 时称为ma n h a tt a n 距离;当r = 2 时称为e u c l i d e a n 距离;当r - 。时称为 c h e b y s h e v 距离， 此时距离的表达式为 d ( x , y ) 一 m a x 卜 ， 一 川 1 5+ 5 月 如果对每一维特征分配以 权重w o , w l , . . , w a : ， 这时 广义的 距离定义 为: d ( x ,y )二( x - y ) t w ( x - y ) 其中w为协方差矩阵。 在图像检索中采用哪一种距离量度要视具体情况而定，但 m a n h a tt a n 距离因计算简单， 效果较好而得到广泛的应用t 7 。 相似度度量方法还有相关计算，计算两个特征矢量之间的相关性， 相关值越大说明相似性越大。 其中余弦相关计算和p e a r s o n 积矩相关计 算较为常用。此外，图像中的有些特征，如状态型特征，其相似性一 般采用关联系数的计算方法。g o w e r方法是经常使用的方法之一。实 际上图像间的相关性计算是个复杂的问题，上述计算方法与人眼视觉 系统所具有的测量性能还存在很大的差距。 2 .3 .3 检索性能评价 目 前需要一个公共的实验平台来评价c b i r 系统的性能， 这个图像 检索实验平台应该具有一个图像集、一套基准和一套评价准则。 图像集应具有代表性强、容量大、多样化、不受使用局限等特点。 目 前试验中使用最多的是美国加州水资源部的图片集 8 和c o r e l 的专 业图片集。这两类图片集是否符合试验平台的要求还需要得到更多研 究者的认可。 基准查询所涉及到的内容既要全面又要简练。目 前主要用底层特 北京交通大学硕士学位论文 征来查询，与人们所期望的在较高语义上的检索还存在着相当大的差 距。处理的方法是利用多级别的查询方法逐渐实现人们的要求。第一 步用底层的特征来查询，随着图像分析和索引技术的不断发展，基准 查询将包含更多的语义信息。这样可利用试验平台的同一图片集实现 不同级别的基准查询。下面讨论检索性能评价标准。 目 前人们通常用查全率和查准率来衡量查询的性能。 用v . e 0 , 1 1 表示第 r幅图片与查询条件的相关性 ( 0 表示不相关，1 表示相关) 。 假设执行某个基准查询时得到了k 幅图片， 则正确的检测数a k = 错 误 的 检 测 数 b k = 艺 ( 1 - v n ) . 漏 检 数c k = a n 一 正 确 淘 汰 数 d k = b n -b k - 我们还可以 进一步计算查全率 凡和查准率 p k 。其中， r k = a k / a n ， 为所 检测出的相关图片数与图片库中所有相关的图片数的比值;p k = a k l k , 为所检出的相关图片与所检出的图片总数的比值。 2 .4 基于内容检索技术的主要问题和研究方向 主要有以下几个方面。 ( 1 ) 如何提取更加有效的 特征 颜色特征索引的主要问题是人们对色彩特征的视觉感知方面的考 虑不够，色彩之间相似度的定义和视觉上人对相似度的定义仍有一定 的差距。在形状特征的检索中，形状边界的自动提取一直是困扰图像 处理领域的难题。基于纹理特征索引目前存在的主要问题是各种方法 所选择的纹理特征集依赖于具体的图像，如何进行纹理特征的自 动切 换仍然需要相当长的时间。 多媒体具有视觉、听觉、时空关系等多种特征，即使是同一种特 征也有不同的表示方法。如何有机的组织从不同角度提取的特征， 利 用特征之间的互补能力提高检索效率，并对检索效果进行融合也是值 北京交通大学硕士学位论文 得研究的问 题。 ( z ) 相 似度度量问 题 图像检索是基于相似度的计算，目 前相似度的计算基本上是基于 数字比较的，与人的视觉特性还有一定的差距，如何建立符合人眼的 相似度计算模型也是一个不可回避的研究课题。 ( 3 ) 性能的 评价标准 需要一套能够平衡表达各种场景和事物的标准的测试数据来评 价检索的效率和效果。然而，这是一项相当复杂的工作，要召集领域 专家收集大量有代表意义的图 像、视频和音频数据，以便测试各种算 法的效率。在此基础上还要定义一套标准的全面检验算法性能的性能 评价标准。 ( 4 ) 高维索引结构的研究 对于大型的图片库使用索引是非常必要的。由于图像的内容特征 非常复杂而且是高维的，常规数据库的索引方法己经不适应于视频数 据库的索引。因此，迫切需要研究新的索引结构和算法以支持大型视 频数据库的检索。 ( 5 ) 如何建立简单实用的用户查询接口 目 前q b e 被认为是一种较好的查询方式但调查发现多数用户希望 用语义查询方式。然而，这需要实现从底层物理特征到高层语义特征 的转换。这虽然是计算机视觉研究的问题，但高层的基于语义内容的 图像检索将成为今后研究的热点。 北京交通大学硕士学位论 文 参考文献 t ma w e i y i n g z h a n g h o n g j i a n g . b e n c h m a r k i n g o f i m a g e f e a t u r e s f o r c o n t e n t - b a s e d r e t r i e v a l . t h e t h i r ty - s e c o n d a s i l o m a r c o n f e r e n c e o n s ig n a ls s y s t e m s m a x n u m b e r 为一整数， 代表检索要求返回的 对象个数的最大值; d i s t t h r e s h o l d为非负实数， 代表结果集中 对象与查询对象距离的 最大值。 检索返回结果一般为对象标识及对应距离，按距离从小到大顺序 排列。 不难看出， 当d i s tt h re s h o l d 为零时， 上面检索对应于一个点查询; 当优先考虑d i s tt h r e s h o l d 限 制时， 上面检索对应于一个范围 查询; 当 优 先考虑m a x n u m b e r 限制时，上面检索对应于高维空间中的k 一 最近邻查 找问题。 3 .2多维数据和多维索引结构的特点 多 维数据具有以 下特点 2 1 . ( i ) 复杂的结构: 数据是多维空间的数据，一般不能象传统的关系 型数据库一样用固定大小的条目 来保存。 ( 2 ) 动态 特性: 在 插入和 删除的 过 程中 往往 还伴随 对数 据本身的 修 改。 ( 3 ) 数据的海量:多维数据库的存储空间比 较大。 ( 4 ) 多样化的 操作: 对多维数据而言， 没有标准的 操作，一般要根 据实际的需要而定。 北京交通大学硕士学位论文 ( 5 ) 时间 代价大; 尽管多 维数 据库的 操作所花费的 时间 各不 相同， 但一般都高于传统的关系型数据库。 ( 6 ) 不能排序:无法对空间 数据进行线性排序使得那些在多维空间 中相邻的数据仍然能够相邻。 正是由于多维数据具有以上特点，因此要求多维索引结构相应的 具有以下特点【 2 j o ( 1 ) 动态构造: 由 于数据可以 在数据库中以 任意的 顺序插入或删除， 其索引结构也应支持相应的操作。 ( 2 ) 二级/ 三级存储管理: 尽管主存容量日 益增大， 但仍不能将整个 数据库保存在主存里，因此索引结构应该充分考虑到二级及三级的存 储管理。 ( 3 ) 独立于数据的 输入和插入的 顺序:支持任意顺序。 ( 4 ) 可增长性; 索引结构应能够适应数据库大小的增长。 ( 5 ) 时间的 有效性:查找速度必须是快速的。 ( 6 ) 空间的有效性;索引结构相对于原数据应是比 较小的，而且还 要保证一定的空间利用率。 ( 7 ) 支持尽量多的操作，能够保证操作的并行性和可恢复性。 3 . 3 影晌多维索引结构性能的因素及其性能评价 影响多维索引结构的因素是多方面的，其中主要的影响因素【 3 如下。 ( 1 )磁盘的访问次数 通常说来数据集太大而不能一次性读入主存。然而，在磁盘上读 或写一个块的时间里，一台典型的机器能执行l o o 万条指令 4 1 ，因此 读写磁盘块的时间决定了查询操作所需要的总时间，可以看作检索时 间的近似值。 ( 2 )距离的计算次数 北京交通大学硕士学位论文 在检索的过程中距离计算的开销是比较大的，以至于距离的计算 次数成了影响性能的一个主要因素。 ( 3 )存储利用率 对存储利用率的考虑不是因为存储设备的花费，而是主要考虑到 当执行查询范围时，尤其是此范围内的数据点较多时由存储利用率而 影响的1 / 0 次数。 针对上面的影响性能的因素分析，主要的解决方法有:减少需要 访问对象的数目 或减小对象的表示尺寸， 以减少访问的u o次数， 如利 用三角不等式剪枝、基于过滤的方法或是降维技术;减少距离的计算 次数;提高存储的利用率。目 前，对多维访问方法的性能及花费模型 的研究己 经很多 5 1 , 6 j ，从中我们可以得到这样的结论:数据空间 中的数据随着维数的增长变得越来越稀疏。正是由于数据的稀疏性， 如果采用通常的空间分割方法，当执行查询时将导致对每个划分的访 问，这样的后果将导致大多数的多维访问方法进行检索时不仅要读整 个索引文件而且还要读整个数据文件，因此在维数多于1 0 维的时候大 多数多维数据空间中的检索性能都不如顺序扫描 7 ，这就是所谓的维 数灾难。由于顺序扫描是磁盘上的顺序访问，从而大大减少了磁盘随 机访问的定位时间，且实现简单，因此顺序扫描通常被看作多维访问 方法性能比较的标准。 3 .4多维索引结构的分类 在近三十年的多维索引结构的研究中已经提出了大量的索引结 构，文献 2 中给出了多维数据索引结构的发展历史图。下面从不同的 角度对多维索引结构进行分类。 ( 1 ) 从数据集的切分方法上来看，索引结构可以分为两类:基于空 间 分割 的 索引 结 构， 例 如g ri d - f i le 8 , k - d - b - tr e e 9 , q u a d t r e e 1 0 等; 基于数据分割的索引结构，如 r - t r e e 1 1 7 , x - t r e e 1 2 7 , 1 v 1 - t r e e 1 3 7 , 北京交通大学硕士学位论文 t v t r e e 1 4 等。 ( 2 ) 根据索引结构的组织形式可分为树形索引结构如【 1 1 , 1 2 和 非树形索引结构如【 1 5 0 ( 3 ) 根据处理的数据类型，可以分为点数据类和空间数据类。点数 据类是指那些只能处理点数据的索引结构，如 k - d 一 树:空间数据类指 既能处理点数据又能处理线、矩形等具有一定形状的数据的索引结构，