1、1WEB 中图像的检索技 术研究第一章 前言1.1 引言伴随网络技术的迅猛发展，图片的来源不断在扩大，容量超大的高速存储系统给图片的海量存储给予了基本保障，各行业对图像的趋于增多，图像资源管理和搜索也愈发重要。但由于网络本身架构、管理的种种问题，想在网络精准、高效地找到所需的图像，却变成了件非常不易之事。由于网络现在的问题：内容没有良好的架构；网络海量信息不断的增多。由此，便出现了搜索引擎。虽然搜索引擎的出现给用户提供了不少的便捷，但是离精准、快速、全面的检索到自己所想要的图像还是有一段距离，所以对图像搜索的研究还要下大力气研究。依照现有的搜索引擎和国内外有关研究人员的种种资料表明，现在的网络
2、资源和搜索引擎的特点如下：(1)搜索的数据种类多样，如视频、图片、文字等。存取协议也是种类繁多，如HTTP、FTP、News 等等；(2)索引数据量巨大，从而导致不可能有某一个数据库可以包括整个网络的索引，当下最大的搜索引擎，其索引也仅仅覆盖了网络的一小部分而已；(3)资源消耗过大，系统需将 HTML 文档传送到本地之后再进行分析，占用昂贵的网络和 CPU 资源，从而增加被搜索结点的压力。此外由于搜索引擎大多是集中式的，所以搜索引擎服务器对硬件配置的要求也极高，这样才能处理巨大的数据量以及及时响应用户的检索请求；(4)不能有效解决搜索失效的问题，大多时候，搜索引擎会返回无用的查询结果；(5)各
3、种检索工具各行其事，无法相互协作，共享资源，也是一种资源的浪费。1.2 现今的图像检索技术近些年伴随着用户对图像搜索需求不断的增长，各类图像搜索引擎由此诞生，它们以不同的搜索方式为用户提供各类检索途径，使得网上图像地检索变得简单，虽然还不太完善，但已经可以满足大多数用户的要求。1.2.1 搜索引擎的工作原理最初的搜索引擎结构，是让 Spider 不停的从 Web 收集数据，存储在搜索引擎数据库当中。用户靠搜索引擎服务器的 Web 接口，发出搜索请求，让 Web Server 通过 CGI或者其它技术访问数据库，并且将用户搜索请求变成相对应的数据存取语句，发送给引擎处理，然后把结果通过网页显示反
4、馈给用户。2网络检索的基本原理其实就是通过 Spider 定期在 web 上运行，发现新的数据，把其取回到本地数据库中，让用户查询的请求可通过查询本地的数据库得到。常用的网络信息检索实现机制可分为两种，通过手工方式对网页进行索引是一种方法，但它的缺陷是 Web 覆盖率低，且不能保证是最新的息。查询匹配就是对用户写入的关键字和网页描述、标题来匹配，并非是通过对全文匹配进行的。对网页进行自动的索引是第二种，这类方法能自动实现文档分类，这种方法是采用信息提取技术。可是在分类精准性上也许不如手工进行的分类。对当下所有运行中的搜索工具来讲，基本上都会有一个机器人定期的访问一些站点，以检查这些站点最近变化
5、，同时找到新的站点。一般站点都会有个 robot.txt 文件来标注服务器不希望机器人访问的区域，机器人都必须遵守这规定。假如是自动索引，机器人在得到一个页面以后，需根据该页面的内容进行索引，依据它的关键字把它归到一个类中。页面信息是通过元数据这类形式来保存的，经典的元数据有标题、IP 地址、该页面简要的介绍、关键字抑或是索引短语、文件大小和最后更新的日期等等。虽然元数据有一定的标准，但是很多站点都是使用自己的模板。文档提取的机制、索引策略这些对搜索引擎（web）的有效性有巨大的联系。高级搜索选项包括：布尔方法、短语匹配、自然语言的处理。一个检索所产生的结果按照提取机制的不同被分成不同等级提交
6、给用户，以关联度的大小排序。每个提取出来的文档元数据会显示给用户。也会包括该文档所在的 URL 地址。此外有些关于某个主题专门的搜索引擎，只针对某个主题的内容来进行检索和处理，如此一来信息的取全率、精准度也相对会较高。当前，图片搜索引擎大多通过以下两类方法来识别图像： (1)自动查找图像档。通过 IMGSRC 和 HREF（HTML 标签）来检查是否有可显示的图片文件，IMGSRC 表达的是“显示下面的图像文件” ，导向嵌入式的图片；HREF 则是用来表示“下面是一个链接” ，导向被链接的图片。引擎通过检查扩展名来判断这个导向是否是图片文件，假若文件扩展名是.png、.jpg、.gif 等，则
7、说明是一个可显示的图片文件。 (2)人工干预找出图片。进行归类，靠人工对网上的图像及站点进行筛选。这类方法可产生精准的查询体系，可是劳动强度过大，因此处理图像的数量有限。由于图像与文本不同，要人们按照自身的理解来说明其蕴含的意义，比文字更趋于感性。因此对于计算机，图像检索的难度比文本的查询的难度要高出很多。1.2.2 图像搜索引擎检索途径1.关键词检索传统图像检索技术是靠关键字精确的匹配来检索，即输入关键字，输出图片。它3包括两种途径：(1)基于图片外部信息进行搜索。即依据图片的文件名、目录名、路径名、以及图像周围文本的信息等等外部信息来进行检索，这是当前图片搜索引擎使用最多的方法。当找到图像
8、文件后，搜索引擎通过查看文件名或者路径名来确定文件内容，当然也可以通过查看图片标题来匹配检索关键词。(2)基于手工标注的检索。通过手工对图像的内容（如颜色对比、反差、景深等）进行描述和分类，将图像标注为一系列关键字，并且建立索引。检索时，将主要在这些关键词中搜索用户输入的关键字。这种查询方法是比较准确的，大都可以获得蛮好的查准率，但是需人工参加，劳动强度高，因此限制了可处理图像的数量。此外，由于图片所包含的信息量很庞大，不同类型用户对同一张图片的看法又不尽相同，就像一万个读者有一万个哈姆雷特一般，从而导致了对图像标注缺乏统一标准。2. 图像可视属性检索基于图像内容的搜索主要是由图片分析软件自动
9、提取图片的颜色、类型等特征，从而建立特征数据库，其输入的弱国为用户要查找图片的大致特征或示例，则通过一定相似匹配规则，输出为与该图片具有相近特征的图片，按相似的程度来排列，以供用户选择，从而解决了在传统图像检索技术中一般用户难以完成的图像特征描述、提取与识别等难题。这是基于图片本身特征的检索，适用于检索明确目标的查询要求，可是目前这种较为成熟的检索技术主要是应用于图片数据库检索。在图片搜索引擎中应用这类检索技术还有困难，但是有部分图像搜索引擎开始尝试使用这种检索方法。1.2.3 对几个基本引擎的简单分析(1)InfoSeek 是一个简单而又功能强大的索引，它的优点是有面向主题搜索而且可扩展的分
10、类。可以把搜索关键字和相似的分类目录主题短语互相作为参照，而且那些主题短语会自动加入到你的查询中。使你的检索有更好的主题相关性。以此同时它也支持对图片的查询。能够漫游 Web、Usenet、Usenet FAQs 等等。不过不支持布尔操作，但可以使用“+“和“-“。 (2)AltaVista 是个大容量的，基于机器人索引的搜索引擎。能够帮你在万维网上搜索你所需的网页，文本，图像，视频音频。AltaVista 支持多种语言和简单的自然语言搜索查询。AltaVista 覆盖面约为万维网上可索引的网页之 30%(3)Scour 自称是第一个基于 web 的多媒体搜索引擎。严格讲，它并非是个图像搜索引
11、擎，但是可以将检索局限在图像搜索上。Scour 工作原理是在文件名、路径名、ALT 标签中搜索关键词。主要使用关键词搜索，可以用符号“或“来增加、排除关键词，使用较少关键词会更有效。在高级4模式中，可以将检索结果图像锁定在 GIF、PNG、JPEG 等格式中。检索结果显示简图、图像类型（如 GIF、JPG） 、大小、最后查找日期、检索词匹配数量、标引使用关键词、成功下载可靠程度等，并且同时给出图像文件的 URL 和源站点 URL。主要缺点是标引的深度太浅，查准率比较低，但查全率比较好。(4) Amazing Picture Machine 是由 NCRTEC 开发的一个“真人工建立完全关键词式
12、索引“。最大特点就是人工干预，关键词检索是其主要的检索手段。Amazing Picture Machine 搜索的结果显示一个简短标题、有关图像说明、文件大小、文件类型以及象素多少等，但是不显示简图。单击标题可以得到原图像，但需由该 URL 回溯才可找出源站点。由于是人工干预检索过程，查准率极好，但事物的作用是相对的，人工干预也限制了它的查全率。它检索范围很有限，只包括 web 上人工选择的部分站点。(5)Lycos 对所收录图像进行了非常详尽的内容描述，并且支持短语检索，从而使得其查准率获得很大提高。它根据文件的扩展名识别图像，在描述词、文件名、目录名、ALT 字段中查询到检索词。结果显示信
13、息非常丰富，包括简图、图像大小、最后检索的日期、图像文件名、图像内容的描述词、图像所在页面等。点击简图可以得到原图以及更多的信息，如著作权人和版权信息的相关图像。比较而言其检索效果很好，速度也快。1.2.4 搜索引擎基本要点(1)索引文档容量：当今最大的搜索引擎有可能包含超 100,000,000 个的链接，但是这个也只是整个 Web 网上很小的一部分。因为收集资料的机器人，只可以从已知的链接开始收集网页数据，只有小部分 Web 网页和这些已知的网页有链接；现在为止还没有一个搜索引擎可以随网页内容的更新而比较及时地更新索引；(2)覆盖面：地理上的覆盖面和主题的覆盖面；(3)索引更新频率：不同类
14、型的搜索引擎，索引更新频率相差非常大，有的是几月，有的是一年。索引更新频率一般有两种定义，一种用的比较少的定义是新的网页能被收进索引数据库中，另外一种是同一页多长时间才会被检查一次，有必要时会更新索引。有的搜索引擎会对时常更新的网页和访问人数多的网页进行更加频繁的重建索引；(4)采集过程：采集可分为宽度优先、深度优先两种算法；一般认为宽度优先对扩大内容覆盖面有帮助，深度优先算法可以提供更多细节资料；(5)索引算法：有的搜索引擎只会处理元标记和一小部分文档内容，而另外有一些搜索引擎则是会对全文进行索引；(6)结果显示：有的搜索引擎只会显示网页标题，有些的话则有更详细的一些信息，5比如说网页的内容
15、，更新日期等；(7)查询算法：一个优秀的查询算法是非常重要的，最基本的布尔查询，短语查询，有些搜索引擎还会提供指定属性的查询，比如说可以指定对网页作者、主题进行查询。另外有些搜索引擎还采用了相关度的反馈、概念查询等算法；(8)用户界面：大多数搜索引擎都提供了简单和高级查询两个界面。并有必要的帮助和示范。1.3 图像检索的发展方向图像检索技术给了用户一个在互联网上搜索感兴趣图片资源的有效手段，依靠文本和依靠内容是图像检索发展的两个分支，不过从当前图像检索研究的趋势来看，尤其是结合网络环境下图片的特征嵌入在具有文本内容的 Web 文档中，出现了三个不同的研究着重点。(1)基于文本的检索研究依靠文本
16、，对图像进行检索。试图把传统的文本检索技术用于对多媒体信息的检索上，因为基于文本的检索技术发展已经很成熟。如网页排名方法、位置方法、概率方法、摘要方法、词性标注法、分类或聚类方法等，不仅技术发展比较成熟，同时分析和实现的难度比较小小。但是由于受控词汇本身的局限，容易产生歧义，更新慢，所以不太好应对网络上日新月异的各类图像。(2)基于内容的检索研究依靠于图像内容，对图片进行分析和检索。相对而言，尽管图像检索已经出现了诸如直方图、颜色矩等多种表征图像特点的方法，但是如果要突破对低层次特征的分析，实现更加高语义上的检索，实现难度比较大，进展缓慢。但是，基于内容的图像检索建立在多媒体信息内容语义上，可
17、以更为客观地反映媒体本质的特征。(3)基于文本内容结合的检索研究融合文本和内容，二者虽然侧重不同但却互相补充。假如能将二者结合起来取长补短，则网络图像检索技术必然有新的进展。现有的图像搜索引擎在信息的自动加工和标引方面都有提高空间，需要开发出计算机自动识别、标引图像的算法和技术，用以完善现有的检索功能，并与已有成熟的图像库检索技术相融合，这是今后需要研究的一个课题。并且，图像库检索技术也应当面向网络，利用网络技术进行改造，提供新的万维网访问界面以代替原来的应用系统界面。同时把巨大的图像库资源利用网络实现共享(4)对基于内容编码技术的研究可以这么说，三个方向都是相互影响相互促进的，任何一个方向的
18、进展都能够促进图像检索技术向前精进一步。6当今，国际上还没有通用基于内容的编码标准。20 世纪 90 年代初，国际上就已经开始对基于内容的图像信息检索这一方面的研究。从最基本的颜色检索，到综合利用多种图像特征进行检索，很多原型系统已经推出，其中，有部分已投入到实际应用中以检验其有效性。与此同时，MPEG-7 标准作为基于内容的多媒体编码标准也正在规划制定当中，将要成为国际标准中的一员。所以，应尽快对 MPEG-7 标准进行研究，分析其编码的性质，在此基础上进一步研究基于内容检索的系统，使我国基于内容的图像检索能够尽快走向实际应用的阶段。(5)对用户查询接口的研究 这涉及到用户对图像内容感知表达
19、、交互方式设计、用户要如何形成并提交查询等方面。现代多媒体信息系统一个重要的特征就是信息获取过程中的可交互性，人在系统中是主导地位。除开提供示例和描绘查询基本接口以外，用户的查询接口应当提供丰富的交互能力，使用户在主动的交互过程中表达对图像语义的感知，调整查询参数及其组合，最终能够获得满意的查询结果。用户的查询接口应该是简单直观易用的，底层特征选择对用户是透明的。这里会涉及到如何把用户的查询表达转换成可以执行检索的特征矢量，如何从交互过程中获取用户的内容感知，方便选择合适的检索特征等问题。一个优秀的搜索引擎必须能够处理以下几个问题：(1)网页分类(2)自然语言处理(3)搜索策略调度和协作 (4
20、)面向特定用户搜索。所以，现在有很多的网络检索工具，就是说搜索引擎使用了智能的检索手段用来增强它的检索能力，而图片检索正是其中的一大块内容。随着网上多媒体的越来越广泛应用，对图像的检索需求将会越迫切。未来的图像检索技术将是网络技术和基于内容的图像库检索技术的融合。随着多媒体信息处理技术的日趋发展和深化，图像信息加工、处理和检索标准的陆续出台，网上的图像检索技术也会日趋完善，而图像搜索引擎也将成为网络新宠。第二章 基于 Web 的图像搜索在网络技术和计算机技术迅猛发展、多媒体应用愈发普及的现在，图像检索和图像应用已成了当今网页中不可缺少的一个重要部分。在能够实现对网页中文本信息提取的同时，如何再
21、为用户抽取所需的图片资料是信息检索中一个值得研究的问题。现7有的检索技术基于关键词匹配进行检索，往往存在查不全、查不准、检索质量不高的现象，特别是在网络信息时代，利用关键词匹配很难满足人们检索的要求。当然现在的人们也可以利用图像的内容特征去搜索所需的图片信息，但现在这项技术就是到现在也还不够成熟，其搜索效率还是不能令人满意。如今在 Web 中处理图像检索有很多成熟的技术，如基于 Web 的数据仓库、Web 数据挖掘、Web 数据源集成技术等。为此，必须为 Web 建立适当的数据模型，利用数据模型有效地从 Web 中获取信息。为了处理 Web 的中文数据，还必须使用一系列中文自然语言处理技术。比
22、较基础的技术有自动分词、人名和机构名的自动识别、自动标引等，其他像信息抽取、自动文摘、文档自动分类、中文概念词的自动发现以及概念词之间的语义关系的确定等技术都必不可少。实现上述技术需要扎实的积累和自然语言处理功底。而如何利用现有成熟的传统的图片检索手段，研究出快捷方便而且能迅速提高检索效率的方法，本文将依据现有的搜索引擎和检索手段的研究找到网页中文本与图像之间的内在特点和联系，改进原有的文本搜索使用的模式和方法，提出新的文本相似的匹配算法，并引入检索的反馈技术，把这些技术引入到图像检索中，使得搜索手段更易于实现和提高检索效率。2.1 文本与图像之间的关系在文本检索中，搜索引擎主要考虑 Web
23、页中相关文字信息以及它的语义，这些文本信息反映出网页的内容，但不完全与网页中图片的内容一致。在 HTML 网页中，根据HTML 语言的格式，捕获反映图片信息的文字信息，分析这些文本的语义具有重要的意义。如在 HTML 文档中标记以及其周围的文字信息，与网页中的插图的内容有着密切的联系。2.1.1 表示图像内容的文本标记为了能识别嵌入网页中图片的内容，必须仔细检索 HTML 文档中能反映出图像内容的标记与其中的文本。经过对 HTML 网页格式的分析与对大量实际网页的研究，可知以下几个方面的标记与文本和图像内容有着最为密切的联系。(1)图像的说明，这些文本出现在图像的周围，用一句过多句话表示出图像
24、的内容，当图像被置于表格中时，同一单元或相邻单元格内的文字也常用与表示图像的含义。(2)图像的标题，通常用一个关键词表示图像信息。(3)图像的标签，使用一段短语说明图片的摘要信息，图片无法显示时用标签的文本取代图片，显示摘要信息。(4)网页的标题，该标题反映出网页的中心内容，作为表现网页内容的图片与网页的标题之间也有着一定的联系。8以上讨论的是 HTML 中文档和嵌入网页中图像文本信息的关系，当然还存在其他的文本与多媒体信息和图像有关。但是作为搜索引擎要考虑的方面，既要保证抽取信息的准确性，也要兼顾程序执行中时间、空间的复杂度。过多地引入与图像关系不是十分紧密的内容作为检索的依据，会引入检索时
25、的躁声干扰，降低搜索效率。2.1.2 文本的权值比较以上讨论了网页中对图像信息的描述，在图像的检索中，首先是要建立描述图片内容特征的查询语句，然后比较、区分描述信息与查询语句之间的异同，获取需要检索的图像。但以上信息在对图像描述时侧重于不同角度，同时与图像信息的联系程度也不一样。图像标题和网页标题是简单的词条，两者中相对来说图像标题更接近图像的主题内容。图像的标签和图像的说明是文本信息对图像内容的描述，后者相对来说更为详细。所以在比较、区分各类文本信息以决定是否符合检索要求时，它们所占的权值应该是有所不同的。根据信息的重要程度，他们所占的权值大小按次序如下：Image CaptionImage
26、 TitleImage AlternatePage Title2.2 图像信息检索Web 搜索引擎使用何种检索模型，它所提供检索质量将会直接影响到检索效果。现在使用较多的为布尔检索模型、概率检索模型、概率推理网络模型和向量空间模型。这里采用的为近年来使用较多且效果较好的一种信息检索模型：向量空间模型。2.2.1 检索模型与相似度在用向量空间模型进行检索的时候，首先会把描述网页中的图片的文字信息看作是有序的词条序列，这样把以上归纳的信息分别称为：ICW，ITW，IAW，PTW。在应用模型时，我首先要将这些信息向量化，把文档映射为一个特征向量 V(d)=(t1, 1(d)；t n, n(d)，其中
27、 ti(i=1,2, ,n)为一列互不雷同的词条项， i(d)为 ti在 d中的权值, 一般被定义为 ti在 d 中出现频率 tfi(d)的函数，即)()(dtfii在信息检索中常用的词条权值计算方法为 TF-IDF 函数 )log()(ii nNtf其中 N 为所有文档的数目，n i为含有词条 ti的文档数目。TF-IDF 公式有很多变种，下面是一个常用的 TF-IDF 公式：9ni iiiii nNdtfd12)1.0(log)(.)(根据公式，文档集中包含某一词条的文档越多，说明它区分文档类别属性的能力越低，其权值越小；另一方面，某一文档中某一词条出现的频率越高，说明它区分文档内容属性的
28、能力越强，其权值越大。两文档之间的相似度可以用其对应的向量之间的夹角余弦来表示，即文档 di，d j的相似度可以表示为 nkjnkikjkiji ddSm1212)()(cos),( 进行查询的过程中，先将查询条件 Q 进行向量化，主要依据布尔模型:当 ti在查询条件 Q 中时，将对应的第 i 坐标置为 1，否则置为 0，即tqii01也就是说当两词条完全相同时， ，这一项为 1，其余情况为 0。可以看出文档含有完全相同的词条时，相似度=1；而其中无相同时的词条时，相似度=0。从而文档 d 与查询 Q 的相似度为niiniii iiqdSim1212)(),(根据文档之间的相似度，结合机器学习
29、的一些算法如神经网络算法，K-近邻算法和贝叶斯分类算法等，可以将文档集分类划分为一些小的文档子集。在查询过程中，可以计算出每个文档与查询的相似度，进而可以根据相似度的大小，将查询的结果进行排序。向量空间模型能够实现文档自动的分类和对查询结果的相似度排列，可以有效提高检索效率；但它的缺点是相似度的计算量大，每当有新文档加入时，就必须重新计算词的权值。2.2.2 分词技术和匹配方法1. 常用的切词算法如下：10(1)最大正向匹配法基本思想是：设 D 为词典，MAX 表示 D 中的最大词长，str 为待切分的字串。它是每次从 str 中取长度为 MAX 的子串与 D 中的词进行匹配。若成功，则该子串
30、为词，指针后移 MAX 个汉字后继续匹配，否则子串逐次减一进行匹配。(2)逆向最大匹配法 它的基本原理与前面的相同，不同的是分词的扫描方向，它是从右至左取子串进行匹配。统计结果表明，单纯使用正向最大匹配的错误率为 1/169，单纯使用逆向最大匹配的错误率为 1/245，它切分的准确率上比正向匹配法有很大提高。(3)基于词频的统计方法统计方法一般不依赖于词典，而是将原文中任意前后紧邻的两个字作为一个词进行出现频率的统计，出现的次数越高，成为一个词的可能性也就越大。在频率超过某个预先设定得阈值时，就将其作为一个词进行索引。这种方法能够有效地提取出未登录词。2. 匹配方法：(1)词典存储格式：首先对
31、存储形式进行建模，结构是 3 层树形结构，如下A1321B(f,n1)1C(t,3)2AnDn4F1G2H1RT一层存储所有单字。第二层保存所有的双字词和多字词的前两个字（因为，也许会出现 ABC 为词，但 AB 不是词的情况） ，并对两者做不同标记(t/f)。每一个可成词的单字对应一系列第二层结点，用来存储所有以该字为词首的双字（包括上述两种情况） 。并且，在这里，针对每一个双字，需要记录以该双字为词首的所有词的最大长度，实际中，可以保存除去该双字部分的最大长度(记为 n)。第三层存储以某一双字为首的所有词。为了减少存储空间，只存储除去该双字以外的部分（如上图所示） 。每一层各结点需按某种次序排列，可使用 hash、二分查找等方法进行查询。采用这种层次的存储结构，可以很快把查询词的工作缩小到一个很小的范围内，有利于分词效率的提高。(2)匹配方法由于词库中的最大词长通常大于所切分出的词长，为了提高切分的效率，不采用逐次减一个字的方法，而是使用正向逐一增长的方法。
