（计算机应用技术专业论文）基于berkeley+db的图像信息索引机制的设计与实现.pdf

n a n ji n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y d e s i g n a n d i m p l e m e n t a t i o no fi n d e x i n g m e c h a n i s mf o ri m a g ei n f o r m a t i o nb a s e do n t h e b e r k e l e y d b a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g y s h u a n gs o n g a d v i s e db y v i c e p r o f e s s o rl i - s o n gw a n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g d e c e m b e r , 2 0 0 9 j _ 一 j p 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日期： 扉双 一 ， r 南京航空航天大学硕士学位论文 摘要 在互联网环境下，产生了大量的图像文件数据，为了提供这些图像文件信息的检索和分析， 首先要解决检索过程中索引存储问题，而目前已有的图像文件信息检索引擎的检索效率和精确 度都不高，已成为应用系统的瓶颈。本文在分析了基于文本的图像信息检索技术之后，重点对 检索过程中的索引机制进行研究。 基于文本的图像信息检索的索引机制的建立主要分为三个部分：索引关键字的提取、索引 数据库的存储和检索结果排序。本文主要研究了这三个方面的内容，重点对前两个过程中相关 数据结构和算法进行了研究和设计。 关于关键字提取过程，研究了三种经典的分词词典机制，针对现有的分词词典机制中的结 构构造复杂、分词效率不高的问题，提出一种改进的分词词典机制；在分析了开源的b e r k e l e yd b 基础上，为进一步提高索引数据的存储和检索效率，对b e r k e l e yd b 的索引机制进行了改进， 设计出一种不分裂的桶分配机制，以减少分裂过程产生的昂贵开销。本文将数据库索引技术与 图像信息检索技术进行融合，设计并实现了一个高效的索引机制，实验结果表明新索引机制提 高了在大数据量存储情况下的图像信息检索效率。 关键字：基于文本的图像检索，b e r k e l e yd b ，h a s h 索引，分词词典，桶 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 a b s t r a c t al a r g en u m b e ro fi m a g ef i l ed a t ac o m e sa b o u ti nt h ei n t e r a c te n v i r o n m e n t 。i no r d e rt op r o v i d e t h ei m a g ef i l ei n f o r m a t i o nr e t r i e v a la n da n a l y s i s ，f i r s to fa l lw es h o u l ds o l v et h ei m a g ef i l e i n f o r m a t i o nr e t r i e v a l si n d e xs t o r a g ep r o b l e m ，t h ee x i s t i n gp i c t u r es e a r c he n g i n e ss e a r c h i n ga r e i n e f f i c i e n c ya n di n a c c u r a c yc a l l ts a t i s f i e dt h eu s e r sn e e d t h i sp a p e rb a s e do nt h et e x t - b a s e di m a g e i n f o r m a t i o nr e t r i e v a l ，r e s e a r c h e dt h ei n d e xm e c h a n i s mo ft h er e t r i e v a lp r o c e s s t h ei n d e x i n gm e c h a n i s m so ft e x t - b a s e di m a g ei n f o r m a t i o nr e t r i e v a lp r o c e s sc a nb ed i v i d e di n t o t h r e ep a r t s ：i n d e xk e y w o r de x t r a c t i o n ，i n d e x i n gd a t a b a s es t o r a g e ，a n ds e a r c hr e s u l t ss o r t i n g t h i s p a p e rp r i m a r i l yf o c u s e do ni n t r o d u c i n gt h ec o n t e n to ft h e s et h r e ea r e a s ，a n de m p h a s i z e do nt h e k e y w o r de x t r a c t i o na n di n d e x i n gd a t as t o r et h e s et w op r o c e s s e s t h i sp a p e ra n a l y z e ds e v e r a lc l a s s i c a ld i c t i o n a r ym e c h a n i s m si nt h ek e y w o r de x t r a c t i o np r o c e s s ， f o rt h ec u r r e n td i c t i o n a r ym e c h a n i s ms t r u c t u r ei sc o m p l i c a t e da n di n e f f i c i e n t , i tp r o p o s e da l li m p r o v e d d i c t i o n a r ym e c h a n i s m a n a l y s i sb a s e do nt h eo p e ns o u r c eb e r k e l e yd b ，i no r d e rt of u r t h e ri m p r o v e t h ei n d e x i n go fd a t as t o r a g ea n dr e t r i e v a le f f i c i e n c ya n da m e l i o r a t et h eh a s ha c c e s sm e t h o do f b e r k e l e yd b ，t h i sp a p e rp r o p o s e dan o - s p l i tb u c k e ta l l o c a t i o nm e c h a n i s m ，r e d u c i n gt h ee x p e n s i v e o v e r h e a dr e s u l t i n gf r o mt h es p l i tp r o c e s s i n t e g r a t e dt h ed a t a b a s ei n d e x i n gt e c h n i q u e sa n di m a g e i n f o r m a t i o nr e t r i e v a lt e c h n i q u e s ，t h i sp a p e rd e s i g n e da n di m p l e m e n t e da ne f f i c i e n ti n d e x i n g m e c h a n i s m ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wi n d e xm e c h a n i s mh a sp r o m o t e di m a g e i n f o r m a t i o nr e t r i e v a le f f i c i e n c yf o rt h el a r g ea m o u n to fd a t as t o r e d k 呵w o r d s ：t h et e x t - b a s e di m a g ei n f o r m a t i o nr e t r i e v a l ，b e r k e l e yd b ，h a s hi n d e x , w o r d s e g m e n t a t i o nd i c t i o n a r y , b u c k e t 第一章绪论l 1 1 课题研究的背景和意义。l 1 1 1 弓i 言1 1 1 2 课题研究的意义1 1 2 课题研究的现状和前景：。2 1 2 1 图像检索技术2 1 2 1 1 基于内容的图像检索技术3 1 2 1 2 基于文本的图像检索技术4 1 2 2 索引数据库。5 1 3 论文研究的内容5 1 4 论文结构6 第二章基于文本的图像信息索引技术概述。7 2 1 图像信息索引总架构7 2 2 基于文本图像索引机制8 2 2 1 索引机制架构。8 2 2 2 增量索引10 2 3 索引存储数据库的选择1 0 2 4 本章小结1 4 第三章图像信息索引机制的设计l5 3 1 分词词典设计1 5 3 1 1 基于整词二分的分词词典机制1 6 3 1 2 基于t r i e 索引树的分词词典机制1 6 3 1 3 基于逐字二分的分词词典机制1 8 3 1 4 一种改进的分词词典建立18 3 2 索引数据库的建立2 0 3 3 索引结果排序2 1 3 3 1 关键字赋权分析2 2 3 3 2 基于频率的关键字赋权方法2 3 3 3 3 索引聚类模型2 4 。l ii 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 3 4 本章小结2 7 第四章基于b e r k e l e yd b 索引存储机制详细设计一2 8 4 1b d bh a s h 索引概述一2 8 4 2b d bh a s h 存储访问方法原理。2 9 4 3 改进的h a s h 索引机制3 2 4 4 本章小结3 5 第五章系统实现与实验结果分析3 6 5 1 改进词典机制的实现3 6 5 2 改进的b d bh a s h 机制的实现3 8 5 3 结果分析4 l 5 4 本章小结4 6 第六章结束语4 7 6 1 论文工作的总结4 7 6 2 下一步工作4 7 致谢4 8 参考文献。4 9 攻读硕士学位期间参加的科研项目和发表的论文5 3 南京航空航天大学硕士学位论文 图表目录 图2 1 基于文本图像搜索过程8 图2 2 倒排文件结构9 图2 3 基于b d b 索引机制接口模型l3 图3 1 基于整词二分的分词词典机制。1 6 图3 2 基于t r i e 索引树的分词词典机制1 7 图3 3 基于逐字二分的分词词典机制1 8 图3 4 改进后分词词典机制1 9 图3 5 关键字到图像信息的映射机制。2 1 图3 6 数据挖掘过程模型2 5 图4 1h a s h 索引2 9 图4 2b d b 中h a s h 存储访问桶分裂模型3 0 图4 3 改进后b d bh a s h 存储访问第一代桶分裂模型3 3 图4 4 改进后b d bh a s h 存储访问第一代桶分裂模型3 4 图5 1b d b 函数调用流程图3 9 图5 2 桶号与代号映射函数修改。4 0 图5 3 桶号与页号映射函数修改4 0 图5 4 词典分词运行结果4l 图5 5 改进b e r k e l e yd bh a s h 存储访问运行结果4 2 图5 6 三种经典分词词典机制测试结果。4 3 图5 7 改进后词典机制在改进前与改进后h a s h 索引机制下的效率测试4 4 表5 1b d b 中桶分裂有关主要函数一3 8 表5 2 改进前各词典机制空间、时间比较实验结果4 4 。卜ll 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 ( 1 ) b d b ( 2 ) m m 注释表 b e r k e l e yd b 简写 m a x i m u mm a t c h i n gm e t h o d最大匹配算法 南京航空航天大学硕士学位论文 第一章绪论 1 1 课题研究的背景和意义 1 1 1 引言 随着计算机技术的日渐发展，计算机互联网应用日渐广泛，伴随着网络相册平台，数字动 画，网络图书馆，电子地图等技术的发展，图像在网络中数据的所占比例越来越型1 1 【2 1 。在c n n i c 的报告中i ，国内用户对w e b 非文本信息的访问频率已经高达2 2 1 ，并且有逐年增长的趋势， 尤其以静态图片的发展最为快速。 各种数字化设备的普及，使得现代社会中多媒体信息的数量迅猛增长，导致了多媒体信息 管理的研究得到越来越多的关注。图像数据库系统在多媒体信息管理的研究中占有特别重要的 地位，图像不仅是视频的基础，而且图像数据库技术也可以直接应用于数字图书馆、数字博物 馆，医学、地理图像数据库，公共安全和国防等多个领域。 随着网络应用方面的深入，和图像有关的信息搜索引擎快速发展起来，从而使图像搜索引 擎的效率与准确度成为搜索引擎中发展的重点。起初，应用程序开发者直接采用文件系统方式 存放数据，在程序中直接对数据文件进行操作，但在存储的数据量愈来愈大时，一个随之产生 的问题是如何更高效的管理这些数据。尤其当人们试图在分布式环境下进行图像数据的操作时， 检索过程中索引机制的建立与索引数据库的存储的索引效率问题变得更为重要，是目前所有闺 像多媒体产品和解决方案提供商面临的最大挑战。 1 1 2 课题研究的意义 目前，网络对人们生活的影响越来越巨大，以图像技术为核心内容的多媒体产业，以数字 化媒介为载体，内容涵盖信息、传播、广告、通讯、电子娱乐产品、网络教育、娱乐、出版等 多个领域，涉及计算机、影视、传媒、教育等多行业的产业集合，被称为是2 l 世纪知识经济的 核心产业，是继i t 产业后又一个经济增长点。由多媒体产业带动的信息、通信、数字家电、软 件及其他相关产业的国际市场规模将达到2 万亿美元，比现在任何一个单一产业，乃至于能源 产业的产值都要庞大1 3 1 。各大电子商务平台的建立，改变了人们面对面的购物买卖等商业活动， 而其中代替实物供买卖双方谈判的基础就是以图片为主的多媒体数据。 丰厚的经济收益，极低的能源损耗，使得许多国家都投巨资对图像技术进行研发。而随之 带来的问题就是图像信息检索技术的研究。 尽管目前已有很多搜索功能比较强大的搜索引擎能提供图像检索的功能，但总的来说，目 _ 基于b e r k e l e yd b 的图像信息索弓 前图片检索状况并不那么乐观：每天都有上千万张图片 擎所检索到；图片搜索引擎索引到得结果的满意度一般 作者，每周在w e b 上查找图片平均都要消耗到2 0 小时l 基于目前图像应用的广泛性和图像检索效率不高的情况，研究一款高效可靠的图像检索引 擎索引机制既是i t 行业的基本发展方向，也可以创造巨大的经济效益，更是人们社会生活发展 脚步前进的方向。 1 2 课题研究的现状和前景 1 2 1 图像检索技术 图像数据类型与传统数据类型在数据模型上是有很多不同方面的，图像数据模型要求不但 包括能够有效的抽象描述多媒体数据库的静态特征的各种数据信息，如图像数据的构成，属性 ( 名字，大小，类型等) 以及约束关系等，还包括根据各个图像数据自身特征抽取出的颜色等 方面的属性值。 传统数据类型与图像数据类型区别【4 j ： ( 1 ) 传统数据类型，包括字符数值型数据、文本数据等。字符数值型数据记录对象的简单 属性，包括人数，文件大小，或者高度抽象的数据类型( 如事物所属类型，人物性别等) 。文本 是最常见的多媒体格式，包括各种书籍、资料文献、档案等无不都是由文本数据媒体数据为主 构成。传统数据库主要存储检索格式主要针对这种类型数据格式，但是在多媒体数据库中，到 目前为止这仍是众多场合中仍然需要选择这种数据进行管理。 ( 2 ) 图像数据类型，其在应用中具有很大的实用价值，目前提出的图像数据的检索包括属 性描述法( 文本描述) 、特征提取、分割、文理识别、颜色检索等等。图像数据属性既包括传统 的数据类型，又包括自身固有的属性特点。 由于数据模型不同，图像数据类型不同于传统数据类型的数据模型，则其数据定义必然不 同于传统的数据类型。由于数据定义与操作的不同，图像数据检索要采用独特的查询优化算法。 图像数据的关键字检索区别于一般数据类型的关键字检索，图像数据的关键字与传统数据类型 相比分为文本型和内容型【卯。由于图片的信息可以通过图片本身的内容传达出来，也可以通过 相关文字的描述传达出来，于是图片便有了双重的信息载体。图像数据检索区别于传统数据的 检索又分为基于内容图像信息检索和基于文本的信息检索。 图像的检索技术主要包括以下环节： ( 1 ) 对图像的特征进行选择提取和索引 图像特征的提取与表达，其主要内容包括基于文本的检索( 如关键字、注释) 和基于视觉 ( 内容) 的检索( 如色彩、纹理、形状等) 两类。而在现代网络应用中，不管是网络相册还是 2 ， 索方法。 效率。 ( 3 ) 处理历史检索结果的相关反馈，改善检索结果 根据用户以往的搜索结果，例如根据网络中数据的点击率等特征来进行反馈分析，将分析 结果直接作用域检索结果。 下面主要介绍基于文本的和基于内容的两种图像检索技术特点与发展应用范围。 1 2 1 1 基于内容的图像检索技术 自上个世纪9 0 年代，基于内容的图像数据库检索开始成为新的研究热点，出现了许多研究 或商用的图像数据检索系统： v i r ，由v i r a g e 公司开发的基于内容的检索系统。其特点是提供完善的用户开发功能， 如：提供用于开发用户界面的工具包；提出p r i m i t i v e 的概念，用于支持用户定义新的图像视觉 特征( 包括该特征的类型，计算和相似性度量方法) ；支持五种抽象数据结构便于图像特征的描 述，并提供用户相关反馈检索机制。因此该系统比较适合用来进行特定应用领域的图像数据库 系统的二次开发。r 己经和多种商业数据库系统如o r a c l e 、s y b a s e 等进行了集成1 6 1 。 v i s u a l s e e k 和w e b s e e k ，它们都是哥伦比亚大学开发的，v i s u a l s e e k 是一个基于图像视觉特 征的搜索引擎，w e b s e e k 是面向w e b 的文本和图像搜索引擎。其特点是提供对图像区域的空间 关系的检索，图像的特征从图像的压缩域中获得。图像视觉特征主要为颜色和基于小波变换的 纹理特征，并且使用基于r - t r e e 的索引结构提高检索速度。支持基于视觉特征及其相互之间空 间关系的检索。w e b s e e k 是一个面向w e b 的搜索引擎，包括3 个模块，图像视频收集，分类与 索引和搜索，浏览和检索。支持结合关键词检索，并使用用户相关反馈技术来改进检索效果【7 1 0 m a r s 是由u i u c 开发的支持图像底层特征的复合检索的图像检索系统。其特点是使用比 较全面的图像底层特征，提供基于树结构的多特征的组合检索。在图像特征方面：使用h s v 空 间的h s 上的色彩直方图来描述图像的颜色；抽取图像纹理的粗糙度和方向性以及对比度等特 征描述纹理：采用图像的规则分割( 5 x 5 ) 的方法对图像特征的空间分布进行描述( 颜色直方图和小 波交换系数) ；根据纹理对图像进行分割来实现图像中的对象描述，并对分割后的对象区域按照 敏感性进行分组。m a r s 在科研方面的主要特点还包括它是数据库管理系统和信息检索极端的 结合，索引和检索技术的融合。检索时对上述特征分别采用相应的相似性度量方法，最终给出 综合排名。由于采用多方面的图像特征描述与相似性度量方法，该系统提供较复杂的检索功能， 如可以通过布尔表达式进行组合检索。m a r s 是较早进行用户相关反馈研究的图像检索系统。 3 基于b e r k e l e yd b 的图 媒体相关的各种处理，包括描述，检索，过滤等等。随着这些标准的制定完成，图像内容的描 述也将随之标准化，基于图像内容和语义表达的图像检索将得到更大的促进，多媒体信息检索 技术的发展也将取得更大的突破。 基于内容的图像检索技术近年来已经成为图像检索技术发展的一个方向，其在人脸识别， 指纹识别等特殊场合发挥了自己独特的优势，基于内容的图像信息检索技术由于需要事先提供 图像样本并且其还有很多地方例如动态识别不同图像中对同一实物不同角度不同颜色的识别等 方面发展不完善，所以该种索引方式在普通网络应用场合中仍没有普及f 6 】【引，应用范围不广泛。 1 2 1 2 基于文本的图像检索技术 基于文本的图像检索技术亦即基于关键字的图像检索技术。在基于文本的图像检索技术中 各种文本描述作为图像数据的代理，在w e b 网页检索过程中作为图像数据检索的关键字，从而 达到快速、高效的检索出与其描述相对应的图像，其检索对象不是图像本身而是描述该图像的 文本数据。 现有的基于文本的图片搜索引擎： g o o g l e 图片搜索是g o o g l e 网页搜索的一个增值子系统，提供目前全球最大的图片库。其 主要技术是通过对网页分析，利用全文搜索技术提供基于关键字的检索，提取与图片相关的文 字信息。该技术支持复杂的布尔查询表达式，根据提供的相关信息进行图像的检索查询。由于 网络中图片数据量非常巨大，图片信息存在于网络中的各个角落。因此，搜索工程巨大，搜索 过程非常复杂。然而利用完全自动的搜索技术搜索出来的结果不甚满意，搜索精度不是很高。 y a h o o 图片搜索是y a h o o 网页搜索的一个增值子系统，其基本搜索特点是人工对图片进行 分类，而不是采用类似g o o g l e 的全文搜索；然后根据分类后的关键字进行图片搜索，其搜索到 的图片比g o o g l e 技术搜索到的图片精确度要高很多。但是由于基于人工分类进行图片存储，其 图片量相比较g o o g l e 图片搜索量要少的很多。 由于早期信息检索处理的对象只有文本，所以基于文本的多媒体信息检索技术便应运而生。 虽然目前基于图像内容和语义表达的图像检索技术发展已经出现了很大的成果，但是由于其搜 索需要提供样式图片，且技术发展不够成熟、应用范围相对比较狭隘的原因，目前只适合精确 图像匹配。所以基于内容的图像信息检索技术的应用只局限在一些特殊的图像检索场合，例如 瞳孔识别、指纹识别等需要图片精确匹配并已提供参照图片的场合。因此，基于文本的图像信 息检索仍然是当前最基本、最常用的一种多媒体信息检索方式。大型网站，包括g o o g l e 搜索引 4 w e b 图片检索，这也是本课题 1 2 2 索引数据库 在目前存在的大型图像信息检索系统中，g o o s e 等大型搜索引擎采用b e r k e l e yd b 作为服 务器端索引数据库，对十几万台甚至几十万台的服务器中存放的数据生成索引供用户快速高效 的查询数据。 b e r k e l e yd b 数据库，其最大的特点就是快速高效可靠的轻量级嵌入式( 可嵌入到应用程序) 数据库，它几乎可以应用在所有的操作系统环境以及硬件平台中，具有高度可移植性。例如它 被应用在大型数据库o r a c l e 、m y s p a c e 中作为后台数据库；m e m c a c h e d b 缓存服务器系统将其作 为后台数据库；开源的群件平台c i t a d e l ，包括信息库在内的全部数据利用b e r k e l e yd b 进行存 储。这些软件系统选择b e r k e l e yd b 作为其底层数据库系统，主要原因就是其高效性。 b e r k e l e y d b 是一个开源的数据库引擎，其环境可以根据具体应用进行配置，其代码可以由 具体应用软件开发的程序员进行个性化修改，以更适应其自己的应用场合。 本文中，我们也采用b e r k e l e yd b 作为图像信息索引数据的底层数据库，并对其索引机制 进行分析。在图像信息检索过程中，总是希望能够对用户的查询请求进行实时回应。为了提高 查询速度，对b e r k e l e yd b 索引机制进行改进以用于存储图像信息检索索引是十分必要的。 1 3 论文研究的内容 在图像数据的检索应用中，关键字提取过程包括对检索到的图像数据进行关键字提取和对 用户提供查询文本的关键字提取、索引数据存储、检索结果的排序。这些技术都影响图像搜索 的效率与结果的准确性。本论文重点是基于文本的图像索引机制的设计，把图像索引的数据存 储到改进后的b e r k e l e yd b 中，实现索引数据库中数据地快速存储以及检索查询。本文研究的 内容主要有以下几个方面： ( 1 ) 本论文研究内容基础以基于文本图像信息检索技术为背景，分析目前基于文本的图像 检索技术的主要特点，介绍文本检索中词典构造的几种重要方式，并且提出一种改进的词典构 造方法。 ( 2 ) 建立索引数据库，采用快速高效的b e r k e l e yd b 作为存储索引的底层数据库，并改进 b e r k e l e yd b 的底层h a s h 存储访问机制，以提高图像文件数据检索的整体检索效率。 ( 3 ) 对检索结果进行排序，给抽取的关键字赋权，通过建立关键字向量采用数据挖掘的方 法建立图像与关键字之间的相似度联系；最后将索引结果进行相关性排序，并传递给用户。 5 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 1 4 论文结构 本论文共分六章，各章节内容如下： 第一章绪论。概述课题背景、研究意义及国内外研究现状，介绍论文的主要研究内容。 第二章基于文本的图像信息索引技术概述。简述图像信息检索引擎总体架构，对基于文本 的图像信息索引机制进行概述，并且对b e r k e l e yd b 存储子系统进行描述，介绍选择其做索引 数据底层存储数据库的原因。 第三章图像信息索引机制的设计。首先介绍几种经典的分词词典机制，并且提出一种改进 的分词词典机制。然后根据提出的分词词典机制和b e r k e l e yd b 存储特点建立索引数据库，最 后对介绍检索结果排序方法进行详细介绍。 第四章基于b e r k e l e yd b 索引存储机制详细设计。对b e r k e l e yd bh a s h 存储访问机制进行 具体分析，指出其不足之处，加以改进，提高索引数据存储效率。 第五章系统实现与实验结果分析。对前面提出的改进的分词词典机制与改进的b e r k e l e y d bh a s h 存储访问机制进行设计实现，并通过测试对实验结果进行分析。 第六章结束语。 6 南京航空航天大学硕士学位论文 章基于文本的图像信息索引技术概述 搜索引擎的内容涉及到相当多的技术问题，包括网页数据的快速采集、海量数据的索引和 存储、搜索结果的相关性排序、搜索效率的毫秒级要求、分布式处理和负载均衡、自然语言的 理解技术等等，是一个复合型技术领域。而基于文本的图片搜索本身也是一种搜索引擎的增值 应用，是一个复杂的系统，需要多个工作部件之间的协调工作，比如纯文本网页和二进制图片 的抓取，图片的文字信息提取，对文字信息建立索引，提供高性能的查询手段等。因此，整个 系统设计需要考虑诸多的技术问题f 9 1 。 2 1 图像信息索引总架构 图像信息搜索引擎的工作主要分为以下几个部分： ( 1 ) 信息规范化与搜集( 数据分析层) 【8 】 在这一步中，在搜索范围内，该模块负责搜集有用的图像信息n , q l i 务器中，对图像的特征 进行选择分类。这个过程即我们由知识发现者查找有用的图像所在文件的过程，此步骤是整个 过程中不可缺少的部分，此步骤的主要作用是清除后续步骤中不会用到的图像资料，或者是错 误的资料，例如在网页搜索中我们需要把广告条、图标、背景等无语义信息的图像与用户真正 需要的图像区别开。对提取信息模块输出的图片信息文件进行简单的排序，将相同的u i u 的图 片排列到一起，方便建索引。 ( 2 ) 数据库层 建立数据词典，对搜集的图像信息分析的过程即抽取出图像中的所有关键字的过程，以使 该图像可以表示成由这些关键字及其出现的频率组成的关键字向量。根据一定的相关度模型算 法进行计算，得到每个关键词的重要性。然后用关键字详细信息和其他有关图像信息建立索引 数据库。 用户数据关键字搜索时，同样也是首先对用户提供文本进行关键字提取，然后由搜索系统 通过索引数据库查询出符合要求的图像数据的具体位置。 ( 3 ) 对搜索的结果进行处理排序 用户提供关键字在索引数据库中进行搜索，根据图像关键字索引机制检索出来的图像结果 一般情况下都会有很多张。这时我们希望搜索出来的图像数据能够按照用户比较希望的排序法 则一一呈现出来。 所有相关网页针对该关键词的相关信息在索引库中都有记录，根据关键词的权值高低对图 像数据进行排序。在数据量特别少的情况下，可以根据相关度进行排序，按照相关度算法综合 7 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 相关信息和网页级别形成相关度数值，然后进行排序。相关度越高，排名越靠前。 生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户n 们n 。 图像信息搜索引擎的工作流程如图2 1 所示。 图2 1 基于文本图像搜索过程 2 2 基于文本图像索引机制 2 2 1 索引机制架构 图像索引机制的建立是指利用网页爬虫等工具抓取各个网页信息并且提取选择了有意义的 图像数据之后的工作，包括：图像关键字的抽取，索引文件建立，索引结果排序。 建立索引即是利用提取的信息模块生成信息倒排文件，因为在w e b 中网页搜索的时候数据 会非常庞大，在这里我们采用建立分一总索引技术，即首先将一定量的数据信息，分别建立 索引，最后将为这些索引建立一个总索引表，其过程分析如下i 坨1 ： ( 1 ) 对提取信息模块输出的图片信息分析，通过一定的聚类方法，使具有较大相似度的图 像的地址排放在一起； ( 2 ) 读取图像文件的关键字信息，建立数据词典。该步循环进行，当达到一定的图片数量 后，转( 3 ) ： ( 3 ) 将词典中的数据按照词的签名排序，并输出一组分组索引数据到磁盘上，包括字典， 索引项，显示信息。然后清空内存中的数据，开始转到( 2 ) ，执行下一组索引的生成过程。如 8 r ，则合并可以通过多 以后写入新的索引文 件中。 在图像信息检索系统中，图像文件都存储在专门的图像服务器中，而只在数据库中存储索 引文件，用来检索查询图像数据。 对于大数据量的数据索引，查询过程不能简单的采用类似s q l 语言中的字符串匹配来对文 档进行处理，这对于大数据量的查找来说效率是非常低的。这种情况下需要索引查询的方法， 先对文档进行预处理，在文档之间建立一种便于搜索的数据结构。当文档信息库非常庞大而且 这些信息相对稳定的时候，建立一定的数据结构将会显著提高搜索的速度。用于海量文本数据 库建立索引的方式中最常用的主要就是倒排文件的方式1 1 3 】【1 4 1 。 用记录的非主属性值来查找记录而组织的文件叫倒排文件。倒排文件中包括了所有副键值， 并列出了与之有关的所有记录主键值，主要用于复杂查询。它包含一个查询项到查询主体的映 射结构，其优势在于映射结构可以预先建立并存储，而在查询时可以通过映射结构直接获得查 询项对应的查询主体，并作为查询结果，避免了整个文档集的扫描。在图像信息检索索引机制 中，图像检索信息文件中，每一个记录项的主键是图像i d ，图像信息中的关键词条为非主键， 在我们构造倒排文件的时候用图像检索信息记录的关键词条作为查询项，图像信息作为查询主 体。倒排文件格式如下图2 2 所示： i 金毛 ；金毛犬 j 幼崽 ：蒙古 ：草原 ：蒙古包 图像l i 图像l i 图像l i 图像2 ，3 i 图像2 i 图像3 ； f 一。- 。一一一一一一一。一一- 一- - - 。1 ：图像文档： 图2 2 倒排文件结构 对应索引中的每一个记录，关键词条为k e y ，所有包含该特征词的图像信息结构体作为该 记录的d a t a ，构成倒排文件索引。对每一个k e y 建立一个对应的列表，存放包含有该词项的图 片的信息。一个简单的倒排索引结构就是由第三章介绍的一个字典和记录项构成，字典是一个 9 基于b e r k e l e yd b 的图像信息索引机制的设计与实现 h a s h 映射结构，每一个词经过一次或者多次h a s h 后的值为对应的记录项的信息。 应的查询主题的一个列表结构，用户存储和实际记录相关的信息。 我们建立的索引存储的是图像数据有关的信息，因为图片数据的信息量比网页 很多，更重要的一点是图片的更新往往比网页要慢得多。基于以上原因，可以对普通的图片索 引定期的进行索引重建，将更新的信息建入到新的索引中，同时去除掉无用的信息( 比如图片 删除后出现的图片死链接) 。 在某些网络应用场合，例如网络相册，新闻图片等应用场合，实时性比较高，图片的更新 比较频繁，为了提高图像检索系统的准确性，这种情况下，每天的甚至每小时抓取到的图片都 需要及时的在用户的检索结果总体现出来。同时，对于一些用户已经删除的或者过期时间较长 的图片，应该在用户的检索结果中删除，但是如果这些所有的操作都在一个索引中操作的话对 于大数据量的索引数据库这种操作也是非常费时，并且会降低索引检索的速度。短时间频繁重 建索引代价太高，而定期的索引更新又不能满足需求，这时就需要增加一个增量索引技术。 2 2 2 增量索引 增量索引技术主要是在主索引之外建立一个辅助索引( s t o p p r e s si n d e x ) ，用于对图片信息 的更新操作进行记载。辅助索引和主索引的工作方式类似，只是在每条信息加一个标志位，标 志该项记录属于新增还是删除。更新的数据量所建的索引相对于主索引，其数据量是非常小的， 这时我们可以设置一个比较短的时间对增量索引进行实时的更新1 1 5 】【16 1 。 用户检索时，检索程序同时向主索引和辅助索引提交查询请求，将两者返回的结果合并以 后返回给用户。 在一段时间以后，当辅助索引增加到一定的大小以后，可以将辅助索引和主索引合并。此 时的合并可能需要涉及到整个索引的重建，但是由于合并的频率比较低，并不需要经常的进行， 所以代价相对直接修改主索引要小的多。 2 3 索引存储数据库的选择 在众多数据库中，选用b e r k e l e yd b 作为多媒体数据的底层索引数据库存储系统是因为其 相比较其他数据库有更大的优势，下面我们简述b e r k e l e yd b 相比较其他主流关系型数据库在 存储索引数据库方面的优势。 b e r k e l e yd b ( 简称b d b ) 是一个开放源代码的嵌入式数据库的函数库，它为应用程序提 供弹性的、高性能的、事物保护型的数据库管理服务，b d b 为数据的访问和管理提供了简单的 应用程序接1 ：3a p i 。 b d b 不仅提供简单数据类型数据的存储等操作，还支持复杂数据类型的存储。访问数据库 的程序自主决定数据如何储存在记录里，b e r k e l e yd b 不对记录里的数据进行任何包装，记录和 1 0 程序员自己规定数据类型 不同应用场合构造不同数 据库引擎，一旦b d b 被 b d b 在许多方面都是弹性的。函数库本身非常紧凑( 在常见的机器体系上大约只占用不到 3 0 0 k 的空间) ，但是它可以操作多达2 5 6 t b 的数据。它也支持高强度的并发操作，可以同时允 许数以千计的用户在同一个数据库进行操作。在高端服务器领域，b d b 是足够小的，它可以在 高度受限的嵌入式系统上运行，但却可以利用高达g b 量级的内存空间和高达t b 量级的磁盘 空间。其高度并发性是符合网络应用环境中的多用户同时提供查询服务的要求的。 b d b 性能比关系型数据库和面向对象的数据库优越的原因是多方面的。首先，b d b 不是 一个独立的数据库服务器。它是一个函数库，和调用它的应用程序是运行在同一地址空间中的。 因为函数库和应用是运行在同一地址空间中的，省掉了数据库操作时的进程间通信。而众所周 知，不管是在单机上还是在分布式系统上，进程间通信所花的时间要远多于函数调用所要花的 时间，b d b 相比较其他关系型数据库在这一方面是高效的。其次，相比较大多数主流关系型数 据库需要对结构化