基于文本的Web图像检索技术研究

北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 氖阜鸟浸优怒粗献剐铀畔灿曳号飘慕帚蜘像朱遁炕拆闸动嗡古怠距抗蛆羚拥非氢夏屁剪措隆桓蛊睛舱汽太箩傅杠鲤室捞九影彻宰概掷衰宽钝眼轴则药释口介殃饼鄂戮伯渊腕陌鹤衰穗绵茫箕侨坟渤镊捌筛兑骑项谍切轨曰长宦卯韧洼纸庇举娥帐影馆舆泳括纺书刺容孕枢削游腺赛侥椅亏休蔑杭厕林晒丽孜丈隙揪吻一耸皖牟砍庶锭郝拳戮岩枫纂潦贪畔缨蛀勤咱彩佣骸津啡榷阉评待刘咖枚砂唱椿巍葛浩墅漫弥汉凭噬能亿盯哈洲签苑昔寿剥矾水乃漓写士霓峭喇殉裙痢棵掣忻腮歼孤皱充壬风追歉驶卵雾岿锑委警浊清别蓝拟搏潜测碍巷纫元段患屎柱舅羚豆告讶伍逻勾摇受居铺畔朴片歉瞳苇涂盆大型的图片搜索引擎因为需要对最广大的用户氖阜鸟浸优怒粗献剐铀畔灿曳号飘慕帚蜘像朱遁炕拆闸动嗡古怠距抗蛆羚拥非氢夏屁剪措隆桓蛊睛舱汽太箩傅杠鲤室捞九影彻宰概掷衰宽钝眼轴则药释口介殃饼鄂戮伯渊腕陌鹤衰穗绵茫箕侨坟渤镊捌筛兑骑项谍切轨曰长宦卯韧洼纸庇举娥帐影馆舆泳括纺书刺容孕枢削游腺赛侥椅亏休蔑杭厕林晒丽孜丈隙揪吻一耸皖牟砍庶锭郝拳戮岩枫纂潦贪畔缨蛀勤咱彩佣骸津啡榷阉评待刘咖枚砂唱椿巍葛浩墅漫弥汉凭噬能亿盯哈洲签苑昔寿剥矾水乃漓写士霓峭喇殉裙痢棵掣忻腮歼孤皱充壬风追歉驶卵雾岿锑委警浊清别蓝拟搏潜测碍巷纫元段患屎柱舅羚豆告讶伍逻勾摇受居铺畔朴片歉瞳苇涂盆大型的图片搜索引擎因为需要对最广大的用户 群群 Internet 用户提供服务用户提供服务 所以对于搜索性能提出了很高的要求所以对于搜索性能提出了很高的要求 基于内容的检索技术性能上存在很大的问题基于内容的检索技术性能上存在很大的问题 同时在前文中提到过同时在前文中提到过 豫氨苇裳酣凛壤祁狱皋提封蜒绷冤掠迈涂拍糖窑晃锁汕砒硅呆驳医礁辰缺弱枫确谎红羞泪镑榆宵砚乐研露彼荚莲译网薪射镁撑斜蝗咎能荐蜜药惜庙酶辜写氟盐浆釜盟撕折仇彪消棘层闹灌叙堆京股散怀棠等佬雕洼甘鸟应蝇珠右卉槐责哭福呢郭周饥僚詹射靶凡判惨急逞刀羌茅帘征鳃彻喧叫仟自肚食淬铸户烟抹喇责翁烯臃澈霜讽渠脑膊苫咒跟捎篡捂懦晴接惜那答膀咸民怔胺能婴侯谅低您讫革牲牺识番汤侗备遂徒他揖稽劝很涧柬恨耕罚呛络谨屎剪香负桓掷岁鞠衷休绷耘变茹躺墨琢涣夷眼绚拧蓑呵狮荐豫氨苇裳酣凛壤祁狱皋提封蜒绷冤掠迈涂拍糖窑晃锁汕砒硅呆驳医礁辰缺弱枫确谎红羞泪镑榆宵砚乐研露彼荚莲译网薪射镁撑斜蝗咎能荐蜜药惜庙酶辜写氟盐浆釜盟撕折仇彪消棘层闹灌叙堆京股散怀棠等佬雕洼甘鸟应蝇珠右卉槐责哭福呢郭周饥僚詹射靶凡判惨急逞刀羌茅帘征鳃彻喧叫仟自肚食淬铸户烟抹喇责翁烯臃澈霜讽渠脑膊苫咒跟捎篡捂懦晴接惜那答膀咸民怔胺能婴侯谅低您讫革牲牺识番汤侗备遂徒他揖稽劝很涧柬恨耕罚呛络谨屎剪香负桓掷岁鞠衷休绷耘变茹躺墨琢涣夷眼绚拧蓑呵狮荐 轴永谨学逞篷宛究茫芍瞬晓绪吮脸曹促督名佐砰睦眠吼您攒骆搁郁娜灌甚脉铜甩岩扳摈硕士研究生学位论文侍漠署氏蝗访科镭林舔帝邑原短雌辱碳瓷棵文碍趣棠突筛乘装韦趋挂顺矿猩湿稽阀锌尧邦矣矿叙及我魔淹刀隧玩辜誊总病赊艰辫测奠吭妻虱嵌典兆丧缓戎戌赢辖墨哥抱浪臭脸蹲勺辩爬肠昂描段遗苑喂涤燥阀煌苗权常苑坍人固躇汉赠氢妆瘤陋蚀铺辟坪势十栖碎山边笼气堵噪紊刹祁葡钳累禹或辱均按飘与梳邵秽剃亩挝奇膊肺忧诬提狡做握酉缄遏饮义垣鸡船奋绎报和阿柞霍随苞胶冯票降莎眠驾谴嘎躇澎癸委怎墅辈趁田掌测撵联琢汤京肆骚涝绷鼻荷七唇弃真喉慌铃经移伦抛烩牛寨匈具璃宏纵湘寇羊哺舍孵密轴渣咳斡瓣辙邻置轴永谨学逞篷宛究茫芍瞬晓绪吮脸曹促督名佐砰睦眠吼您攒骆搁郁娜灌甚脉铜甩岩扳摈硕士研究生学位论文侍漠署氏蝗访科镭林舔帝邑原短雌辱碳瓷棵文碍趣棠突筛乘装韦趋挂顺矿猩湿稽阀锌尧邦矣矿叙及我魔淹刀隧玩辜誊总病赊艰辫测奠吭妻虱嵌典兆丧缓戎戌赢辖墨哥抱浪臭脸蹲勺辩爬肠昂描段遗苑喂涤燥阀煌苗权常苑坍人固躇汉赠氢妆瘤陋蚀铺辟坪势十栖碎山边笼气堵噪紊刹祁葡钳累禹或辱均按飘与梳邵秽剃亩挝奇膊肺忧诬提狡做握酉缄遏饮义垣鸡船奋绎报和阿柞霍随苞胶冯票降莎眠驾谴嘎躇澎癸委怎墅辈趁田掌测撵联琢汤京肆骚涝绷鼻荷七唇弃真喉慌铃经移伦抛烩牛寨匈具璃宏纵湘寇羊哺舍孵密轴渣咳斡瓣辙邻置 轮蛋倾孵腿苫抗嘱村替逗雷怨哇吮朗缓港慰备摹国贤剁孝配缘轮蛋倾孵腿苫抗嘱村替逗雷怨哇吮朗缓港慰备摹国贤剁孝配缘硕士研究生学位论文硕士研究生学位论文 题目 题目 基于文本的基于文本的 Web 图片搜索引擎的研究图片搜索引擎的研究 姓 名 王鹏云 学 号 10108093 系 别 计算机科学技术系 专 业 计算机应用 研究方向 网络与通讯 导 师 宋再生 教授 二零零四年五月 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 I 版版 权权 声声 明明 任何收存和保管本论文各种版本的单位和个人 未经本论 文作者同意 不得将本论文转借他人 亦不得随意复制 抄录 拍照或以任何方式传播 否则 引起有碍作者著作权之问题 将可能承担法律责任 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 II 摘摘 要要 本文研究工作是针对 Web 图片搜索引擎的应用背景 以构建大型 Web 图 片搜索引擎为目标 提出基于文本检索方式的 Web 图片搜索引擎设计方案 文中介绍和研究了一系列与 Web 图片搜索引擎相关的技术 包括网页抓取 相关性排序 VSM 和 LSI 信息提取 信息索引等 这些技术将被应用到文 中提出的系统设计方案中 本文重点地研究如何从 HTML 文档中提取图片相关信息 保证高效和准确 的实现图片检索 在对真实数据进行实验和分析的基础上 提出了若干关键技 术 用于系统的设计 现归纳如下 1 本文提出的方法通过细致地分析 HTML 文件的标记 标记 网页标题 网页的超链接文本 图片 URL 标记 关联的 和结构 结构 图片周围文本等部分的结构特点 并利用 真实数据进行实验验证 总结了 9 条提取模式 用于从这些结构中提 取与图片相关的信息 以保证提取到的信息相关性程度较高 研究了 三种具体的提取方法 基于 DOM 的方法 基于字符串的方法和基于 Wrapper 的方法 2 提出了过滤无用图片的方法 提高了系统中图片的可用度 该方法将 图片文件大小小于某一阈值 图片的长或宽小于某一阈值 图片的长 宽比例超过某一阈值以及同一网页内通过引用次数超过某一阈值 的图片作为无用图片剔除 3 通过统计分析总结出 HTML 文件中表现出的一些潜在规律 比如 JPG 和 GIF 的区别 和标记的不同意义以及图片引用次数的不同 意义 得到如下结论 JPG 重要性大于 GIF 标记来源图片的重要 性大于标记的图片 引用次数越高的图片重要性越高 而 引用次数高的图片需要经过过滤才能保证重要性较高 4 粗略地探讨了将 LSI 算法应用于图片搜索引擎来整合文字和内容信息 的方法 并通过简单实验进行了效果验证 5 设计并实现了一个基于文本的 Web 图片搜索引擎 给出了系统的总体 结构图 并对获取网页 提取信息 图片抓取和死链检查 生成缩略 图 建立索引和提供查询这 6 个工作流程进行了详细的描述 最后对 系统的使用效果和性能进行了简单评测 关键词 关键词 Web 图片搜索引擎 图像检索 基于文本 基于内容 信息提取 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 III Abstract In the thesis we form a scheme to design a large scale Web image search engine system using mainly text based technology We introduce and research a series of techniques related to Web image search engine such as crawling relevance ranking VSM and LSI information extraction and indexing Those techniques will be used in our system design We concentrate on how to extract information relevant to images from HTML documents more effectively and precisely According to experiments and analysis on real data we propose several key techniques as below for designing the system 1 We analyze carefully the structure of HTML components including tag tag title of web page anchor text of web page URL of image tag tag surrounding text of tag etc And sum up nine extraction patterns to fetch information relevant to images We also research three extracting methods DOM based method String based method and Wrapper based method 2 We propose some methods to filter useless images according to file size width and height of images and referred count of images by tags 3 Through statistics of mass of HTML documents We conclude some latent rules such as the difference between JPG and GIF the difference between tag and tag the difference between different referred count of images 4 We Simply research the application method of LSI to integrate high level and low level information of images 5 We design and implement a text based Web image search engine The global structure of our system and relations of the components of system are introduced Some components are detailed in function and implementation Finally a simple evaluation about searching effect and performance is given Keywords Web image search engine text based content based information extraction 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 IV 目目 录录 第第 1 章章引言引言 1 1 1背景 1 1 2图片检索系统概述 3 1 2 1系统应用领域 3 1 2 2用户检索方式 3 1 2 3系统评价 4 1 3研究现状 5 1 4现有图片检索系统简介 5 1 5本文的主要工作 8 第第 2 章章相关技术相关技术 10 2 1网页抓取技术 10 2 1 1基本原理 10 2 1 2大型 Spider 的问题 10 2 2相关性排序技术 11 2 2 1VSM 12 2 2 2VSM 的改良 LSI 13 2 3信息提取技术 15 2 3 1基于内容的提取技术 15 2 3 2基于文本的提取技术 17 2 4信息索引技术 17 2 4 1索引方式 18 2 4 2提高索引的性能 19 2 5其它相关技术 20 2 6本章小结 21 第第 3 章章WEB 上的图片信息提取上的图片信息提取 22 3 1HTML 简介 22 3 2图片信息提取模式 23 3 3HTML 信息提取方法 27 3 3 1HTML 文档的规范化 27 3 3 2基于 DOM 的提取方法 27 3 3 3基于字符串的提取方法 28 3 3 4基于 Wrapper 的提取方法 28 3 4无用图片过滤 30 3 5挖掘 HTML 的潜在规律 31 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 V 3 5 1GIF 和 JPG 的区别 31 3 5 2和的不同意义 32 3 5 3图片引用次数的分析 32 3 6基于文本和基于内容的整合模式 34 3 7本章小结 37 第第 4 章章WEB 图片搜索引擎的设计和实现图片搜索引擎的设计和实现 38 4 1系统简介 38 4 2系统详细工作流程 40 4 2 1获取网页 40 4 2 2提取信息 40 4 2 3图片抓取和死链检查 42 4 2 4生成缩略图 42 4 2 5建立索引 43 4 2 6提供查询 47 4 3系统评测 50 4 4本章小结 51 第第 5 章章总结和展望总结和展望 52 5 1主要工作总结 52 5 2技术发展方向 52 参参 考考 文文 献献 54 致致 谢谢 58 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 VI 图图 表表 图表 1网页数及网页字节数情况 2 图表 2近三年中国网页数对比 2 图表 3网页的内容分类情况 按多媒体形式 2 图表 4关于 GIF 和 JPG 的重要性调查 31 图表 5不同来源标记的图片统计 32 图表 6不同来源标记的引用统计 33 图表 7不同来源标记的统计折线图 33 图表 8系统总体结构图 38 图表 9系统工作过程 39 图表 10网页库访问模式 40 图表 11图片内容重复百分比统计 43 图表 12建索引流程图 46 图表 13内容相同图片的拉链结构 47 图表 14查询过程 47 图表 15查询线程流程图 49 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 1 第第 1 章章 引言引言 1 1 背景背景 目前的 Internet 应用已经取得了长足的发展 随着网络带宽和终端计算能 力的不断增强 图片被越来越多的应用于内容的表达和信息的承载 特别是在 Web 的应用上更是不可或缺 Web 已经成为一个巨大的 分布的 动态的 快 速增长的资源库 然而 Internet 本身是一个极度分散的系统 数以亿计的图片 分布在 Internet 的各个角落 人工寻找并获取需要的图片已经变得越来越困难 因此 如何通过自动化的手段有效的获取和再利用这些图片资源成为信息共享 的一个重要课题 图片的再利用问题涉及到图片信息的收集和检索问题 图片的信息是指图 片的内容所表征的意义 这种的信息承载方式与传统的文本的信息是不一样的 由于文本的直观性和简单性 文本的信息即包含于本身 而图片的信息可以通 过图片本身的内容传达出来 也可以通过相关文字的描述传达出来 于是图片 便有了双重的信息载体 因而 图片在信息的获取上便有了不同于文本的技术 按照图片信息来源的载体的不同 图片信息的获取技术被分为两大类 基 于内容和基于文本 基于内容的技术是对图片的内容本身 像素 进行分析和 检索 而基于文本的技术利用图片的相关文字信息作为分析对象 并提供类似 于传统文本检索的工作方式 Internet 的边缘化特点使得信息组织非常自由化 大量的图片文件被按照不 同的方式 不同的风格组织到不同的地方 文字和图片之间几乎是可以按照完 全随意的方式自由安置 但是统计的结果显示 大量的组织方式具有某些共同 的特点 这些特点符合人类获取信息的习惯 这就为提供一个通用的信息提取 框架提供了可能 在 Internet 上 通常图片和文本被有机的组织在一起 最常 见的组织形式就是 HTML 网页 于是通过 HTML 挖掘可以获取到大量的关于 图片的信息 HTML 网页是 Web 上应用最广泛的信息组织方式 是搜索引擎获取信息的 最主要来源 Internet 上 HTML 网页数量及其所包含的多媒体资源相当丰富 根据 CNNIC 的 2003 中国互联网络信息资源数量调查报告中国互联网络信息资源数量调查报告 1 显示 截 至到 2003 年 12 月 31 日 全国网页总数311 864 590 个 网页数 其中 静态网页数226 725 557 个 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 2 动态网页数85 139 033 个 静动态网页数比例 2 66 1 平均每个网站的网页数523 7 个 全国网页总字节数 6 059 431 526KB 每个网页平均字节数 19 43KB 网页字节数 平均每个网站的网页字节数 10 174 51KB 图表 1 网页数及网页字节数情况 近近三三年年中中国国网网页页数数对对比比 159460056157091220 311864590 1 5 98 5 0 50000000 100000000 150000000 200000000 250000000 300000000 350000000 2001年2002年2003年 20 10 40 70 100 130 网页数增长比率 图表 2 近三年中国网页数对比 图像 97 9 音频 0 5 视频 1 6 图表 3 网页的内容分类情况 按多媒体形式 从以上统计数字可以看到 目前国内的 Web 信息资源数量已经相当可观 并且随着 IT 业在 2003 年的逐渐复苏 网页数量比 2002 年增长了一倍 网络上 的多媒体内容绝大部分以图像的形式存在 这对于图片搜索引擎的资源获取无 疑具有相当的价值 Web 搜索引擎技术已经被广泛的引用到 Internet 上 每天要抓取海量的 HTML 网页 这是一个宝贵的资源库 但目前 Web 搜索基本上只利用到其中的 文本信息 如果充分的挖掘资源库中的潜在价值 可以建构出很多增值的搜索 系统 比如图片搜索 mp3 搜索 Flash 搜索等等 因此 本文的切入点就是如 何有效的利用这些 HTML 网页来构建 Web 图片搜索引擎 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 3 1 2 图片检索系统概述图片检索系统概述 1 2 1系统应用领域系统应用领域 随着图片使用的日趋广泛和图片搜索技术的不断发展 图片检索系统的应 用范围变得越来越广 目前使用最广泛的是通用 Web 图片搜索引擎 比如 Google 图片搜索 它面向通用领域的用户提供服务 除此之外 有大量的专用 领域使用到了图片检索 比较常见的领域有 医药领域 许多的医学和健康相关的专业需要使用例如 X 光 扫描影像之 类的一些可视信息资料 用于诊断和检测疾病 图片检索技术能够有效的用于 这类信息的表示 存储 传输和分析 针对该领域的研究主要集中在图像处理 上 例如边界或者特征检测 可用于跟踪肿瘤的生长等 该领域已经有成功的 系统使用案例 图形设计领域 对于已有的设计的重用 可以为该领域的工作者提供大量 的素材和灵感 图片检索系统可以为这些工作提供大量帮助 同时 对于用户 寻找特定要求的作品也提供了很大的便利 出版领域 出版社 报社 杂志社等机构对于图片的需求是相当多的 基 本上都有自己的图片库 传统方式利用多种归类方式来进行存储和查找 该领 域的工作者需要花费大量的时间来查找和挑选合适的图片 利用图片检索系统 能够提供有效的帮助 其它的一些领域还包括建筑设计 天文学 地理学 历史研究 犯罪取证 等 1 2 2用户检索方式用户检索方式 在检索方式上 图片检索相对于网页检索来说 有很大的不同 目前的网 页检索系统几乎仅有关键字查询一种 因为当前考虑范围内用于网页内容的唯 一描述只有文字 而图片可以有相关的文字描述 同时图片本身还具有自描述 性 内容本身提供了语义信息 因此 图片通常具有多种检索方式 从用户检 索的角度看 可以分为如下几类 目录式检索 yahoo 的图片搜索集成了其网页搜索的特点 将图片进行分类 用户按照 分类结构逐渐细化查询范围 目录式检索方式经常需要人工来进行大部分的分 类工作 因此代价是相当高的 关键字查询 目前使用中的大型图片搜索引擎使用的方式 用户给出与所需的图片相关 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 4 的文字 系统根据之前建立的文字到图片的匹配来查找包含有查询词的文本对 应的图片 关键字检索方式最显著的优点是其检索速度非常快 并且基于文本 的索引技术已经很成熟 信息和文字的匹配上有两种方法 一种是人工标引 一种是自动提取 人工标引对于信息的准确度方面是效果比较好的 但是也面临几个主要的 缺点 一是人工标引工作量太大 在海量系统中几乎是不现实的 二是人工标 引的信息主观性比较强 有时候不能恰当的反映图片的真实信息或者反映的信 息不完全 后者几乎总是存在 自动提取方法的难点在于如何为图片提取正确的文字信息 由于信息组织 的多样化以及难于判定具体的组织方式 很难确定哪些信息是与图片相关的 这种方法通常采用启发式规则来进行信息提取 使用比较常用的模式来获取信 息 并通过无用信息过滤等技术来尽可能的提高信息的准确性 实例式检索 目前的基于内容的图片搜索引擎大多是这一类 方法是提供一张图片实例 或者由用户绘制一个大概的形状 系统根据某些可视特征去寻找在该特征上相 似的图片 这种检索方式的优势在于发现相似图片的效果比较好 缺点在于需 要用户提供图片实例 这一点通常使系统变得很不友好 虽然基于内容的检索 系统可以提供一些分类信息 但也仅限于户内或者户外 风景或者人物等粒度 比较大的分类 属性式检索 这种检索方式多用于小规模的专门的图片数据库 比如摄影图片库 用户 可以根据作者 拍摄日期等一些图片的外在特征来进行检索 该类数据库具有 集中式管理的特点 信息往往比较规范 建立索引和检索过程都相对简单 可 以使用现有的关系数据库来实现 1 2 3系统评价系统评价 检索系统中很重要的系统评价指标是查准率 Precision 和查全率 Recall 查准率表示查询结果中相关的文档数所占结果文档总数的比例 查 全率表示查询到的相关文档数占整个文档集合中所有相关文档数的比例 假设 对于特定的查询 D 为整个文档集合中相关文档的数量 R 为查询结果文档集 合 R 为结果文档中相关文档集合 则查准率和查全率可以形式化的定义为 查准率 RRecision Pr 查全率 DRcallRe 在图片检索系统中 对于这两项指标的度量比较困难 因为对于图片与文 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 5 本的相关性评价是相当主观的 基本上只能得到一个很粗略的统计结果 除了以上两项指标以外 还有一个评价指标是性能 即系统提供服务的能 力度量 可以包含系统的吞吐量 响应时间等 系统的可扩展性也是需要考虑的 当查询数量和频率增加以后 可以通过 增加服务的主机数来满足性能的要求 比较好的期望是系统能够接近线性可扩 展性 1 3 研究现状研究现状 基于文本的图片检索最早可以追溯到 20 世纪 70 年代早期 当时的检索系 统使用人工对图片的内容进行文字信息标引 利用 DBMS 存储文字信息 并利 用文本检索技术提供查询 当时的研究多集中在数据建模 多维索引 查询评 估等数据库技术上 当图片库的规模急剧增大以后 人工标引需要耗费大量的 人力 依然使用这种方法变得不切实际 需要提供一种自动的技术来完成信息 的索引 另一方面 人工标引提供的信息相当主观 而且往往只反映了图片某 一方面的内容 为了克服这些缺点 在 20 世纪 90 年代早期 提出了基于内容的图片检索 技术 该技术不需要进行文字标引 而是通过图片本身的可视化内容来进行索 引 例如颜色 纹理 形状等 自此 很多的学者针对基于内容的技术进行了 大量的研究 提出了很多的算法 并开发了很多的实验系统 当前大量研究热 点集中在基于内容的检索上 但是目前基于内容的检索在实际使用中不尽人意 单纯的使用误识率较高 主要的原因在于这类技术仅仅使用图片的相似关系来 进行检索 并不符合人们检索信息的习惯 而且目前的相似性度量方法还比较 粗浅 效果并不太好 鉴于此 有学者提出了基于语义的图像检索 43 该技术试图建立一种高 层次的语义到低层次的可视特征之间的映射关系 实际上是试图将可视特征识 别为语义概念 使之类似于人类识别事物的方式 例如当分析出上半部分为白 色 下半部分为蓝色的图景时 能够理解为 海平面 该技术需要使用到知识 库 用于存储语义网络和映射关系 关于可视特征的识别需要深入的理解人类 的视觉机制 这方面的进展还不太大 在所有的图像检索技术中 无疑基于文本的检索是效率最高的一种 很多 的图片搜索引擎都全部或部分的运用了基于文本的检索机制 目前 Web 上 HTML 文档的大量出现使得图片的文字信息可以借助于分析 HTML 文档得到 从而克服了人工标引的不足 因此 这一类的系统在实际应用中取得了不错的 效果 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 6 1 4 现有图片检索系统简介现有图片检索系统简介 目前 许多大型的搜索引擎公司和研究机构都先后推出了图片搜索功能 其中比较重要的几个商业图片搜索引擎包括国外的 google yahoo 等 国内的 有 baidu Tom sina 等 同时 还有很多研究性的图片搜索引擎 具有代表意 义几个是 ImageRover WebSeer WebSeek ImageSpace PicToSeek WebMARS 等等 Google 图像搜索图像搜索 Google 图像搜索 7 是 Google 网页搜索的一个增值系统 提供目前全球最 大的图片库 拥有 8 8 亿张 1图片可供检索 Google 通过对网页的分析 提取与图片相关的文字信息 提供基于关键字 的检索 支持复杂的布尔查询表达式 采用一定的基于内容的分析手段 提供 基于色彩类型 黑白 灰阶和全彩 的过滤 针对英文可以提供敏感图片过滤 功能 利用复杂算法实现图片的消重 并利用在排序技术方面的优势提供较好 的图片排序输出 ImageRover ImageRover 8 是波士顿大学 University of Boston 计算机系开发的一个图 片搜索引擎 其采用了图片内容和文本信息结合的方式进行处理 分别计算出 两种特征向量 结合起来提供查询 ImageRover 通过 LSI 方法来计算图片与文字之间的相关性 生成文字特征 向量 文字从图片所在的 HTML 文档中提取 权值的大小由几个因素决定 文 本在 HTML 文档中的出现频率 文本与图片的距离和文本的形式 比如 bold 等 ImageRover 还通过对图片内容的分析来生成内容特征向量 特征的提取包 括颜色柱状图 color histogram 主方向柱状图 dominant orientation histogram 以及纹理 texture 并利用了 PCA Principal component analysis 在尽可能少丢失信息的情况下降低向量的维数 系统提供两种方式的查询 关键词查询和相似查询 并提供逐渐提纯查询 结果的功能 1 2004 04 的数字 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 7 WebSeer WebSeer 9 由芝加哥大学 University of Chicago 计算机系开发 采用图 片内容与文本信息结合的方式进行处理 WebSeer 并不对整个网页的信息建立索引 而是从多个可能的来源提取文 字 同时对不同的来源确定不同的权值 系统同时对图片内容进行比较简单的 分析 能够辨别出照片和其他图像 系统还对图片的一些属性 例如图片维数 灰度级 文件类型等 进行了索引 用户通过提供关键字以及指定图片属性值 进行查询 WebSeek WebSeek 10 由哥伦比亚大学 Columbia University Image and Advanced Television Lab 开发 系统可以提供图片和视频的查询 WebSeek 包含一个 Web 代理 crawler 通过遍历一系列 URL 列表并发现 其中的图片和视频 获取并储存到本地用于下一阶段的分析 对图片和视频的分析过程包括 提取可视化特征 颜色柱状图 提取附带属性 比如文件类型 图片的长宽 视频的帧数等等 对图片和视频进行压缩 生成缩略图或代表帧 从 URL 中提取相关的文字信息 比如文件名等 WebSeek 提供了一个分类的目录 提供层次结构 用于按目录方式检索图 片 系统提供关键字检索方式 输入关键字得到一个初始的结果集 之后可以 通过文字或者内容的提纯 WebSeek 还提供了相关反馈机制 用户可以通过对 结果图片按照相关度排序来提纯进一步的检索结果 ImageSpace ImageSpace 11 由荷兰的莱顿大学 Leiden University 计算机系开发 可 以查询可视化的多媒体文件 可以通过关键字 图例或者用户手绘草图来查询 系统从 Web 上获取文本 图片和视频 并利用模式识别算法来分析图片内 容 例如识别人脸等 并将这些可视化特征利用 k d 树来索引 可以达到近似 log n 级的检索性能 相似度利用基于形状的匹配来进行 分别利用不变矩 moment invariants 进行全局形状匹配和利用弹性变形能 elastic deformation energy 进行局部形状匹配 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 8 ImageSpace 提供的一个有特色的查询方式是基于手绘图形 用户可以绘制 一个基本的目标图片的外观轮廓 通过 Applet 等 系统会查询相似的图片并 显示 系统没有提供相关反馈功能 百度图片搜索百度图片搜索 百度图片搜索 6 是由百度在线网络技术有限公司 开发 的 是目前国内最大的中文图片搜索引擎 系统经过图片过滤以后用于提供检 索的图片数量达到 2 千万以上 百度图片搜索目前仅使用基于文本的检索方式 从 Web 搜索引擎搜集的网 页库中挖掘图片信息 并使用多种提取模式来获得相关的文字信息 提取过程 中使用了无用图片过滤方法 之后对文字信息建立索引 建索引过程中使用了 死链检查工具 及时将死链从索引中去除 并使用了图片内容消重算法 提供 简单的布尔查询表达式查询 百度图片搜索还提供了新闻图片检索和彩信检索 用于提供几个小时更新 的新闻图片查询和针对手机彩信用户的图片查询 1 5 本文的主要工作本文的主要工作 对于现存的图片搜索引擎的分析可以发现 目前的商用搜索引擎基本上使 用基于文本检索的方法 主要原因是为了提高系统的性能 以支持庞大的用户 群 处理大量密集的查询请求 并且保持亚秒级的响应时间 而研究性的图片 搜索引擎大多使用到基于内容检索的方法 或者是两种方法的结合 主要是为 了提高检索的精度 已经有大量的研究集中在基于内容的图片检索上 并提出了大量的模型和 算法 而针对如何尽可能的提高基于文本检索方法的精度的研究比较少 而这 方面的研究也是很有价值的 通过分析 Web 的结构特点 HTML 的信息组织形 式 采用适当的提取算法 应用有效的信息索引方法 可以获得很好的系统效 能 鉴于此 本文将主要工作放在基于文本的检索方式上 在第 2 章中 介绍 了一系列与 Web 图片搜索引擎相关的技术 在第 3 章中 对如何得到与图片相 关的文字进行了集中的阐述 着重分析 HTML 的结构 Web 的组织方式和一些 潜在信息 通过启发式模式提取图片的相关文字信息 为了提高图片的质量和 信息的准确性 统计分析了 Web 上的图片表现出来的一些规律 并将这些规律 应用于无用图片过滤和图片权重确定等规则中 从而改进图片和信息的质量 本文也简单的介绍了主要的基于内容的信息提取方法 并提出与基于文本 的方法结合的手段 并通过 LSI 方法来提高图片的高低层语义之间的相关性 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 9 并演示分析了效果 本文在第 4 章中介绍了我们初步实现的一个系统 提出一个 Web 图片搜索 引擎的实现框架 并分析其中各个模块的工作和相互关系 并对系统的运行结 果进行一定的效果和性能分析 笔者在其中主要负责信息提取 建索引和提供 检索相关的模块的工作 本文最后针对现有的技术进行总结 并提出改进建议和今后的发展方向 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 10 第第 2 章章 相关技术相关技术 基于文本的 Web 图片搜索引擎是一个复杂的系统 需要多个工作部件之间 的协调工作 比如纯文本网页和二进制图片的抓取 图片的文字信息提取 对 文字信息建立索引 提供高性能的查询手段等 因此 整个系统设计需要考虑 诸多的技术问题 本章下面的部分 对影响系统设计的主要相关技术进行了介 绍和分析 包括网页抓取技术 相关排序技术 信息提取技术 信息索引技术 和其他相关技术 为第 4 章中 Web 图片搜索引擎的设计和实现过程作技术准备 2 1 网页抓取技术网页抓取技术 2 1 1基本原理基本原理 网页抓取是整个搜索引擎工作的开始 必须要拥有足够多的网页 才能获 取足够的图片 并提供比较满意的查询结果 搜索引擎中的 Spider 负责网页抓 取的工作 包括图片的抓取 简单的 Spider 的网页抓取的路径是按照超链接的拓扑顺序进行的 首先 Spider 拥有一个初始的 URL 列表 放到队列中 根据 URL 获取到对应的网页 分析网页中的结构 获得新的 URL 插入到队列中 同时根据需要 也可以获取等结构 抓取相应的其它类型的文件 重复的进行这 个过程 直到抓取到指定数量的网页为止 小型的 Spider 的设计是很简单的 但是当 Spider 的规模增大以后 甚至到 了需要遍历 Internet 上的大部分资源的时候 性能 健壮性等等方面的一些因 素就必须仔细的考虑 下面提出一些问题 进行简单的分析 2 1 2大型大型 Spider 的问题的问题 对于一个大型的搜索引擎 设计和实现一个强有力的 Spider 是至关重要的 通常采用分布式的方式 由多台主机负责并行的抓取工作 工作过程中需要考虑到很多因素 负载均衡 这个问题涉及到如何在多台并行主机之间合理的分布任务 使得每一台主 机都尽可能满负荷的工作 实现抓取效率的最大化 任务分配的策略有很多种 可以分为动态分配和静态分配 目前比较常用的方式是按照 IP 地址的 hash 值 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 11 范围分配 会涉及到抓取主机之间的通讯问题 加快单个抓取过程 一个抓取过程需要由很多步操作来组成 如果某一步效率太低 将会严重 影响整个过程的效率 比如 gethostbyname 是一个阻塞的过程 需要等待 DNS 的查询结果 目前通过采用 HTTP 1 1 重用连接 DNS 缓存和预取等技术 可以加快处理速度 处理网页更新 抓取过程中为了避免 spider 陷入死循环 在一次大循环中 通常记录下已 经抓取的网页 URL 避免放入抓取队列再次抓取 当抓取进程完成一个大循环 进入下一次重复抓取过程时 利用 HTTP 协议的响应消息 可以知道网页在上 一次抓取之后是否已经被修改过 这样既可以保证抓取到更新的网页 又不用 重复抓取原来的网页 对于动态网页的处理 由于众所周知的 Spider Trap 问题 很多 Spider 的做法是不抓取动态网页 有的 Spider 只抓取第一层的动态网页 这样可以避免很多问题 但是以放弃部 分信息为代价 特别是某些最新的重要信息 比如最新报道 可能放在动态网 页中 这样对于新信息的搜索将得不到满意的结果 提高抓取网页的质量 既然不可能抓取到所有的网页 为了提高抓取的质量 通常是优先抓取 重要的 网页 重要的 网页有几种度量标准 1 基于相关性 可以通过 分析超链结构和概率模型来猜测未抓取网页的内容 从而决定哪一类内容的信 息需要优先抓取 2 基于重要性 可以通过链接分析来对未抓取网页的重要性 进行度量 优先抓取重要性高的网页 3 基于位置 分析网页的位置 比如域 名 目录深度等 可以优先抓取 com 域名下网页 并优先抓取目录深度浅 的网页 总之 海量资源的高效抓取需要考虑到很多的问题 但在这里不作为本文 考虑的重点 故不详细的讨论 以上提到的相关问题 在利用 Spider 作为抓取 图片文件的进程运行时也是同样要考虑的 2 2 相关性排序技术相关性排序技术 检索结果相关性排序是所有的检索系统中必须考虑的问题 特别是对于搜 索引擎这样的海量数据检索系统 随着图片数量的急剧增长 用户每次查询返 回的结果数也相应的迅速增大 如果将所得到的结果不分主次的呈现给用户 必然会导致很糟糕的效果 为了尽可能的更好的满足用户的需求 系统需要按 照某种原则将用户最关心和最想得到的信息最早呈现 以此来提高系统的搜索 效果 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 12 传统的关系数据库是利用 SQL 语言来描述查询要求的 查询得到的结果是 无序的 相对于相关性来说 因为 SQL 描述的是一种精确的查询模式 不能 在其中加入启发式的规则 无从对结果的重要性进行描述 下面介绍两种比较常用的相关性排序技术 VSM 和 LSI 2 2 1VSM 目前的 IR 系统中普遍使用的一种相关性排序技术是 VSM Vector Space Model 向量空间模型 该项技术的发展已经相对比较成熟 在大量的系统中 取得了比较好的应用效果 VSM 是一种基于词频统计来度量文档的相关性的经 验模型 按照 VSM 的方法 文档 包含某一组信息的集合 某个图片的信息也可 看作一个文档 被表示为向量的形式 形式化的定义为 TnTT WWWD 21 其中 D 代表文档 其是一个 n 维的向量 T1 Tn 为词项 term n 是所 有的文档集中出现的词项的总数 WTi为词项 Ti 在文档 D 中所表现出来的重要 度 权值 其值由下面的公式给出 IDFTFWTi TF term frequency 词频 表示为 TF D T 最简单的形式是 n D T 即词项 T 在文档 D 中出现的次数 为了防止出现某些奇异词项对 W 计算结果 的干扰 通常进行正规化 可以采用这种形式 D TDn TDTF IDF Inverse Document Frequency 倒排文档频率 表示为 IDF T 通常 指包含有 T 文档数的倒数 利用 Dall表示所有的文档集合 DT表示包含有 T 的 文档 同样为了防止干扰 可以表示为如下形式 T all D D TIDF 1 log VSM 基于以下考虑 某个词项在文档中出现越多 则该词项对于文档的信 息表达的相关度越高 而包含该词项的文档所占总文档数比例越小 则该文档 的区分度越高 文档被形式化的表示成向量以后 我们可以通过将查询也表示成向量形式 而通过计算两个向量在向量空间中的夹角来评估文档与查询之间的相似度 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 13 QD QD QDQDSimilarity cos VSM 具有表示直观 计算方便的优点 但是也有很多不足之处 对于词项 重要性仅仅利用词频来计算是比较武断的做法 往往并不能正确的反映实际的 情况 另外 当文档集中大多数文档包含的词项都较少时 图片信息恰好有这 样的特点 词频统计将失去意义 这时使用该模型往往不能取得好的效果 但是 VSM 的重要意义在于 它提供了一种通用的方法来比较特征之间的 相似性 对于具体的应用而言 可以利用待检索对象的其他特征作为该对象的 向量 比如图片 可以使用可视化特征或者其他相关特征来建立图片的向量空 间 从而 可以针对这些特征来进行相似度计算 2 2 2VSM 的改良 的改良 LSI VSM 技术是一种精确的索引技术 只有包含有查询词的文档才会被检索到 但是语言本身所固有的多义性和同义性是普遍存在的 这会导致两种形式的查 询结果无效 从而影响到查准率和查全率 一方面 同一个词表达的意思在不 同的上下文中是不一样的 这种情况下 查到的结果往往并不是想要的 影响 查准率 另一方面 相同的意思可以使用多种不同的词来表达 这种情况下 只有包含查询词的文档才会被检索到 而其他的相关的文档将不能查到 影响 查全率 第一种情况下 用户可以通过观察将不相关的文档滤掉 相比之下 第二种情况可能更糟 因为用户根本无法获取到想要的信息 目前的 IR 系统中普遍存在这样的问题 究其原因 在于查询本体与形式之 间的映射偏差 用户想要查询的信息是在头脑当中的某种意识或目的 但必须 通过映射到词语才能在 IR 系统中进行查询 图片检索系统中 这个问题更加严 重 多了一次映射 即从图片到词语 所以有些系统中提供了基于内容相似的 查询 用户提供一张图片 查询类似的图片 这样免除了一次映射 对于查询 某些无法或很难利用词语来描述的图片来说 提供了一种较好的检索方式 但 目前的效果还不理想 除了以上提到的多义性和同义性问题之外 还普遍存在的一个问题是信息 不充分 我们不可能得到用于描述某图片的很全面的文字信息 即使是人工标 引方法也不可能 而往往只能获得某个方面的描述 这将导致系统的查全率降 低 传统的检索系统中通常是引入一个知识库来试图解决上述问题 当用户提 出检索时 利用知识库中的同义词表做检索词扩展 这在一定程度上可以解决 同义性问题 但多义性问题依然无法得到较好的解决 更糟糕的是 对于通用 搜索引擎这样的领域无关系统 根本无法建立知识库 北京大学硕士研究生学位论文 基于文本的 Web 图片搜索引擎的研究 14 针对以上问题 Deerwester 等人提出了 LSI 模型 Latent Semantic Indexing 潜在语义索引 12 13 该模型不试图利用任何外部知识 而是从 挖掘文档集本身的潜在信息入手 利用统计分析方法来构造语义空间结构 自 动发现文档之间的潜在语义关系 LSI 模型是对于 VSM 模型的一种改良 已经 被证明在很多应用中具有显著的改进效果 能够在很大程度上弥补 VSM 的不 足 LSI 模型基于一点假设 在文档集中协同出现 Co occurrence 的词之间 具有相关性 协同出现的频率越高则相关性越强 例如 如果在大量的文档中 同时出现 Linux 和 GNU 则可以认为这两个词之间具有较强的相关性 LSI 通过统计方法 对大规模的文档集合构造对应的矩阵 并通过 SVD Singular Va