【毕业学位论文】（Word原稿）基于文本的Web图片搜索引擎的研究-计算机系网络与分布式系统

北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 硕士研究生学位论文 题目： 基于文本的 片搜索引擎的研究 姓 名： 学 号： 10108093 系 别： 计算机科学技术系 专 业： 计算机应用 研究方向： 网络与通讯 导 师： 宋再生 教授 二零零四年五月 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - I - 版 权 声 明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不 得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 摘 要 本文研究工作是针对 片搜索引擎 的 应用背景，以构建 大型 片搜索引擎为目标， 提出基于文本检索方式的 片搜索引擎设计方案。 文中介绍和研究了一系列与 片搜索引擎相关的技术，包括网页抓取、相关性排序（ 信息提取、信息索引等，这些技术将被应用到文中提出的系统设计方案中。 本文重点 地研究如何从 档中提取图片相关信息，保证高效和准确的实现图片检索 。 在 对 真实数据 进行 实 验和分析的基础上 ， 提出了若干关键技术，用于系统的设计 ， 现归纳如下： 1) 本文提出的方法通过 细致地 分析 件的 标记、 标记、网页标题、网页的超链接文本、图片 标记、关联的 和结构、 结构、图片周围文本等部分的结构特点，并利用真实数据进行实验 验证 ，总结了 9 条提取模式，用于从这些结构中提取 与图片相关的信息 ，以保证提取到的信息相关性程度较高。研究了三种具体的提取方法：基于 方法、基于字符串的方法和基于 2) 提出了过滤无用图片的方法， 提高 了系统中 图片的 可用度。该方法将图片文件大小小于某一阈值，图片的长或宽小于某一阈值，图片的长宽比例超过某一阈值以及同一网页内通过 引用次数超过某一阈值的图片作为无用图片剔除。 3) 通过统计 分析 总结 出 件 中表现出的一些潜在规律 ，比如 区别、 和 标记的不同意义以及图片引用次数的不同意义。得到如下结论： 要性大于 标记来源图片的重要性大于 标记的图片； 引用次数越高的图片重要性越高，而 引用次数高的图片需要经过过滤才能保证重要性较高。 4) 粗略地探讨了将 法应用于图片搜索引擎来整合文字和内容信息的方法，并通过简单实验进行了效果验证 。 5) 设计 并实现 了一个 基于文本的 片搜索引擎 ，给出了系统的总体结构图，并对获取网页、提取信息、图片抓取和死链检查、生成缩略图、建立索引和提供查询这 6 个工作流程进行了详细的描述，最后对系统的使用效果和性能进行了简单评测 。 关键词： 片搜索引擎 图像检索 基于文本 基于内容 信息提取 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - n we a to a eb We a of eb as be in We on to to to on we as 1) We of of of up to to We 2) We to to of of 3) of We as PG of 4) SI to of 5) We a eb of of of in a is 京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 目 录 第 1 章 引言 . 1 景 . 1 片检索系统概述 . 3 统应用领域 . 3 户检索方式 . 3 统评价 . 4 究现状 . 5 有图片检索系统简介 . 5 文的主要工作 . 8 第 2 章 相关技术 . 10 页抓取技术 . 10 本原理 . 10 型 问题 . 10 关性排序技术 . 11 . 12 改良： . 13 息提取技术 . 15 于内容的提取技术 . 15 于文本的提取技术 . 17 息索引技术 . 17 引方式 . 18 高索引的性能 . 19 它相关技术 . 20 章小结 . 21 第 3 章 的图片信息提取 . 22 介 . 22 片信息提取模式 . 23 息提取方法 . 27 档的规范化 . 27 于 提取方法 . 27 于字符串的提取方法 . 28 于 提取方法 . 28 用图片过滤 . 30 掘 潜在规律 . 31 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - V - 区别 . 31 的 不同意义 . 32 片引用次数的分析 . 32 于文本和基于内容的整合模式 . 34 章小结 . 37 第 4 章 片搜索引擎的设计和实现 . 38 统简介 . 38 统详细工作流程 . 40 取网页 . 40 取信息 . 40 片抓取和死链检查 . 42 成缩略图 . 42 立索引 . 43 供查询 . 47 统评测 . 50 章小结 . 51 第 5 章 总结和展望 . 52 要工作总结 . 52 术发展方向 . 52 参 考 文 献 . 54 致 谢 . 58 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 图 表 图表 1 网页数及网页字节数情况 . 2 图表 2 近三年中国网页数对比 . 2 图表 3 网页的内容分类情况（按多媒体形式） . 2 图表 4 关于 重要性调查 . 31 图表 5 不同来源标记的图片统计 . 32 图表 6 不同来源标记的引用统计 . 33 图表 7 不同来源标记的统计折线图 . 33 图表 8 系统总体结构图 . 38 图表 9 系统工作过程 . 39 图表 10 网页库访 问模式 . 40 图表 11 图片内容重复百分比统计 . 43 图表 12 建索引流程图 . 46 图表 13 内容相同图片的拉链结构 . 47 图表 14 查询过程 . 47 图表 15 查询线程流程图 . 49 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 1 - 第 1章 引言 景 目前的 用已经取得了长足的发展，随着网络带宽和终端计算能力的不断增强，图片被越来越多的应用于内容的表达和信息的承载，特别是在 经成为一个巨大的、分布的、动态的、快速增长的资源库。然而， 身是一个极度分散的系统，数以亿计的图片分布在各个角落，人工寻找并获取需要的图片已经变得越来越困难，因此，如何通过自动化的手段有效的获取和再利用这些图片资源成为信息共享的一个重要课题。 图片的再利用问题涉及到图片信息的收集和检索问题。图片的信息是指图片的内容所表征的意义，这种的信息承载方式与传统的文本的信息是不一样的。由于文本的直观性和简单性，文本的信息即包含于本身；而图片的信息可以通 过图片本身的内容传达出来，也可以通过相关文字的描述传达出来，于是图片便有了双重的信息载体。因而，图片在信息的获取上便有了不同于文本的技术。 按照图片信息来源的载体的不同，图片信息的获取技术被分为两大类：基于内容和基于文本。基于内容的技术是对图片的内容本身（像素）进行分析和检索，而基于文本的技术利用图片的相关文字信息作为分析对象，并提供类似于传统文本检索的工作方式。 边缘化特点使得信息组织非常自由化，大量的图片文件被按照不同的方式，不同的风格组织到不同的地方。文字和图片之间几乎是可以按照完全随意的方式自由安置。但是统计的结果显示，大量的组织方式具有某些共同的特点，这些特点符合人类获取信息的习惯。这就为提供一个通用的信息提取框架提供了可能。在 ，通常图片和文本被有机的组织在一起，最常见的组织形式就是 页，于是通过 掘可以获取到大量的关于图片的信息。 页是 应用最广泛的信息组织方式，是搜索引擎获取信息的最主要来源。 页数量及其所包含的多媒体资源相当丰富。 根据 2003 中国互联网络信息资源数量调查报告 1显示（截至到 2003 年 12 月 31 日）： 网页数 全国网页总数 311,864,590 个 其中：静态网页数 226,725,557 个 动态网页数 85,139,033 个 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 2 - 静动态网页数比例 平均每个网站的网页数 网页字节数 全国网页总 字节数 6,059,431,526个网页平均 字节数 均每个网站的网页 字节数 10,表 1 网页数及网页 字节数 情况 近三年中国网页数对比159460056 1570912203118645905 %9 8 0500000001000000001500000002000000002500000003000000003500000002001 年 2002 年 2003 年 %10%40%70%100%130%网页数 增长比率图表 2 近三年 中国网页数对比 图像 音频 视频 图表 3 网页的内容分类情况 （按 多媒体 形式） 从以上统计数字可以看到，目前国内的 息资源数量已经相当可观，并且随着 在 2003 年的逐渐复苏，网页数量比 2002 年增长了一倍。网络上的多媒体内容绝大部分以图像的形式存在，这对于图片搜索引擎的资源获取无疑具有相当的价值。 索引擎技术已经被广泛的引用到 ，每天要抓取海量的页，这是一个宝贵的资源库，但目前 索基本上只利用到其中的文本信息。如果充分的挖掘资 源库中的潜在价值，可以建构出很多增值的搜索系统，比如图片搜索， 索， 索等等。因此，本文的切入点就是如何有效的利用这些 页来构建 片搜索引擎。 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 3 - 片检索系统概述 统应用领域 随着图片使用的日趋广泛和图片搜索技术的不断发展，图片检索系统的应用范围变得越来越广。目前使用最广泛的是通用 片搜索引擎，比如 面向通用领域的用户提供服务。除此之外，有大量的专用领域使用到了图片检索，比较常见的领域有： 医药领域。许多的医学和健康相关的专业需要使用例如 X 光、扫描 影像之类的一些可视信息资料，用于诊断和检测疾病。图片检索技术能够有效的用于这类信息的表示、存储、传输和分析，针对该领域的研究主要集中在图像处理上，例如边界或者特征检测，可用于跟踪肿瘤的生长等。该领域已经有成功的系统使用案例。 图形设计领域。对于已有的设计的重用，可以为该领域的工作者提供大量的素材和灵感，图片检索系统可以为这些工作提供大量帮助，同时，对于用户寻找特定要求的作品也提供了很大的便利。 出版领域。出版社、报社、杂志社等机构对于图片的需求是相当多的，基本上都有自己的图片库，传统方式利用多种归类方式来进 行存储和查找。该领域的工作者需要花费大量的时间来查找和挑选合适的图片，利用图片检索系统能够提供有效的帮助。 其它的一些领域还包括建筑设计、天文学、地理学、历史研究、犯罪取证等。 户检索方式 在检索方式上，图片检索相对于网页检索来说，有很大的不同。目前的网页检索系统几乎仅有关键字查询一种，因为当前考虑范围内用于网页内容的唯一描述只有文字。而图片可以有相关的文字描述，同时图片本身还具有自描述性（内容本身提供了语义信息）。因此，图片通常具有多种检索方式，从用户检索的角度看，可以分为如下几类： 目录式检索： 图片搜索集成了其网页搜索的特点，将图片进行分类，用户按照分类结构逐渐细化查询范围。目录式检索方式经常需要人工来进行大部分的分类工作，因此代价是相当高的。 关键字查询： 目前使用中的大型图片搜索引擎使用的方式。用户给出与所需的图片相关的文字，系统根据之前建立的文字到图片的匹配来查找包含有查询词的文本对应的北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 4 - 图片。关键字检索方式最显著的优点是其检索速度非常快，并且基于文本的索引技术已经很成熟。信息和文字的匹配上有两种方法，一种是人工标引，一种是自动提取。 人工标引对于信息的准确度方面是效果比较好的。但是也 面临几个主要的缺点：一是人工标引工作量太大，在海量系统中几乎是不现实的。二是人工标引的信息主观性比较强，有时候不能恰当的反映图片的真实信息或者反映的信息不完全（后者几乎总是存在）。 自动提取方法的难点在于如何为图片提取正确的文字信息。由于信息组织的多样化以及难于判定具体的组织方式，很难确定哪些信息是与图片相关的。这种方法通常采用启发式规则来进行信息提取，使用比较常用的模式来获取信息，并通过无用信息过滤等技术来尽可能的提高信息的准确性。 实例式检索： 目前的基于内容的图片搜索引擎大多是这一类。方法是提供一张图 片实例或者由用户绘制一个大概的形状，系统根据某些可视特征去寻找在该特征上相似的图片。这种检索方式的优势在于发现相似图片的效果比较好，缺点在于需要用户提供图片实例，这一点通常使系统变得很不友好。虽然基于内容的检索系统可以提供一些分类信息，但也仅限于户内或者户外，风景或者人物等粒度比较大的分类。 属性式检索： 这种检索方式多用于小规模的专门的图片数据库，比如摄影图片库，用户可以根据作者，拍摄日期等一些图片的外在特征来进行检索。该类数据库具有集中式管理的特点，信息往往比较规范，建立索引和检索过程都相对简单，可以使 用现有的关系数据库来实现。 统评价 检索系统中很重要的系统评价指标是查准率（ 查全率（ 查准率表示查询结果中相关的文档数所占结果文档总数的比例；查全率表示查询到的相关文档数占整个文档集合中所有相关文档数的比例。假设对于特定的查询， D+为整个文档集合中相关文档的数量， R 为查询结果文档集合， R+为结果文档中相关文档集合，则查准率和查全率可以形式化的定义为： 查准率： 系统中，对于这两项指标的度量比较困难，因为对于图片与文本的相关性评价是相当主观的，基本上只能得到一个很粗略的统计结果。 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 5 - 除了以上两项指标以外，还有一个评价指标是性能，即系统提供服务的能力度量，可以包含系统的吞吐量，响应时间等。 系统的可扩展性也是需要考虑的，当查询数量和频率增加以后，可以通过增加服务的主机数来满足性能的要求。比较好的期望是系统能够接近线性可扩展性。 究现状 基于文本的图片检索最早可以追溯到 20 世纪 70 年代早期，当时的检索系统使用人工对图片的内容进行文字信息标引，利用 储文字信息， 并利用文本检索技术提供查询。当时的研究多集中在数据建模、多维索引、查询评估等数据库技术上。当图片库的规模急剧增大以后，人工标引需要耗费大量的人力，依然使用这种方法变得不切实际，需要提供一种自动的技术来完成信息的索引，另一方面，人工标引提供的信息相当主观，而且往往只反映了图片某一方面的内容。 为了克服这些缺点，在 20 世纪 90 年代早期，提出了基于内容的图片检索技术。该技术不需要进行文字标引，而是通过图片本身的可视化内容来进行索引，例如颜色、纹理、形状等。自此，很多的学者针对基于内容的技术进行了大量的研究，提出了 很多的算法，并开发了很多的实验系统。当前大量研究热点集中在基于内容的检索上。但是目前基于内容的检索在实际使用中不尽人意，单纯的使用误识率较高，主要的原因在于这类技术仅仅使用图片的相似关系来进行检索，并不符合人们检索信息的习惯，而且目前的相似性度量方法还比较粗浅，效果并不太好。 鉴于此，有学者提出了基于语义的图像检索 43，该技术试图建立一种高层次的语义到低层次的可视特征之间的映射关系，实际上是试图将可视特征识别为语义概念，使之类似于人类识别事物的方式 。例如当分析出上半部分为白色，下半部分为蓝色的图景时，能够理解为“海平面”。该技术需要使用到知识库，用于存储语义网络和映射关系。关于可视特征的识别需要深入的理解人类的视觉机制，这方面的进展还不太大。 在所有的图像检索技术中，无疑基于文本的检索是效率最高的一种，很多的图片搜索引擎都全部或部分的运用了基于文本的检索机制。目前 档得到，从而克服了人工标引的不足。因此，这一类的系统在实际应用中取得了不错的效果。 有图片检索系统简介 目前，许多大 型的搜索引擎公司和研究机构都先后推出了图片搜索功能。其北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 6 - 中比较重要的几个商业图片搜索引擎包括国外的 ，国内的有。同时，还有很多研究性的图片搜索引擎，具有代表意义几个是： 像搜索 像搜索 7是 页搜索的一个增值系统，提供目前全球最大的图片库，拥有 张 图片可供检索。 过对网页的分析，提取与图片相关的文字信息，提供基于关键字的检索，支持复杂的布尔查询表达式。采用一定的基于内容的分析手段，提供基于色彩类型（黑白，灰阶和全彩）的过滤。针对英文可以提供敏感图片过滤功能。利用复杂算法实现图片的消重，并利用在排序技术方面的优势提供较好的图片排序输出。 是波士顿大学（ 算机系开发的一个图片搜索引擎。其 采用了图片内容和文本信息结合的方式进行处理，分别计算出两种特征向量，结合起来提供查询。 过 法来计算图片与文字之间的相关性，生成文字特征向量。文字从图片所在的 档中提取，权值的大小由几个因素决定：文本在 档中的出现频率，文本与图片的距离和文本的形式（比如 ）。 通过对图片内容的分析来生成内容特征向量。特征的提取包括颜色柱状图（ 主方向柱状图（ 及纹理（ 并利用了 尽可能少丢失信息的情况下降低向量的维数。 系统提供两种方式的查询：关键词查询和相似查询，并提供逐渐提纯查询结果的功能。 由芝加哥大学（ 算机系开发。采用图片内容与文本信息结合的方式进行处理。 不对整个网页的信息建立索引，而是从多个可能的来源提取文 数字 北京大学硕士研究生学位论文 基于文本的 片搜索引擎的研究 - 7 - 字，同时对 不同的来源确定不同的权值。系统同时对图片内容进行比较简单的分析，能够辨别出照片和其他图像。系统还对图片的一些属性（例如图片维数，灰度级，文件类型等）进行了索引。用户通过提供关键字以及指定图片属性值进行查询。 0由哥伦比亚大学（ 发。系统可以提供图片和视频的查询。 含一个 理（ ，通过遍历一系列 表并发现其中的图片和视频，获取并储存到本地用于下一阶段的分析。 对图片和视频的分析过程包括： 提取可视化特征（颜色柱状图）； 提取附带属性，比如文件类型，图片的长宽，视频的帧数等等； 对图片和视频进行压缩，生成缩略图或代表帧； 从 提取相关的文字信息，比如文件名等 供了一个分类的目录，提供层次结构，用于按目录方式检索图片。系统提供关键字检索方式，输入关键字得到一个初始的结果集，之后可以通过文字或者内容的提纯。 提供了相关反馈机制，用户可以通过对结果 图片按照相关度排序来提纯进一步的检索结果。 1由荷兰的莱顿大学（ 算机系开发，可以查询可视化的多媒体文件，可以通过关键字、图例或者用户手绘草图来查询。 系统从 获取文本，图片和视频，并利用模式识别算法来分析图片内容，例如识别人脸等。并将这些可视化特征利用 来索引，可以达到近似 n)级的检索性能。相似度利用基于