（计算机科学与技术专业论文）基于文本的图片搜索引擎的研究.pdf

摘要 随着w e b 上图片资源的日益丰富，人们对w e b 图片检索的需求也日趋强烈。 基于文本的w e b 图片检索技术，是人们当前检索w e b 图片的主要手段。尽管 已有若干使用该技术的w e b 图片搜索引擎产品投入实用，但目前的基于文本的 图片检索技术还有待完善，主要体现为：对w e b 的复杂性理解不够，使用固定的 模式提取文本，常常以偏概全，提取效果不佳；对影响词条权重的因素考虑不够， 权重模式较粗糙；围绕词条组织索引，通过字匹配实现查询，导致了较严重的同 义词和多义词问题。 对此，本文做了有针对性的研究：针对w e b 图片搜索引擎的应用背景，以 构建大型w e b 图片搜索引擎为目标，提出基于文本检索方式的w e b 图片搜索引 擎设计方案。文中介绍和研究了一系列与w e b 图片搜索引擎相关的技术，包括 网页抓取、相关性排序( v s m 和l s i ) 、信息提取、信息索引等，这些技术将被 应用到文中提出的系统设计方案中。 本文重点地研究如何从h t m l 文档中提取图片相关信息，保证高效和准 确的实现图片检索。在对真实数据进行实验和分析的基础上，提出了若干关键 技术，设计并实现了一个基于文本的w e b 图片搜索引擎，给出了系统的总体结 构图，并对获取网页、提取信息、图片抓取和死链检查、生成缩略图、建立索 引和提供查询这6 个工作流程进行了详细的描述，最后对系统的使用效果和性 能进行了简单评测。 关键词：w e b 图片搜索引擎图像检索基于文本基于内容信息提取 a b s t r a c t a b s t r a c t a st h e r es o u r c e so fi m a g e sg r o w d a yb yd a yo nt h ew r e b ，t h ed e m a n do fi m a g e r e t r i e v a lb e c o m e ss t r o n g e ra n ds t r o n g e r a tp r e s e n t ，t h ew r e bi m a g e sr e t r i e v a lb a s e d o nt e x ti st h ep r i m a r ym e a l l sf o rt l st or e s o l v et h ed i f f i c u l tp r o b l e mo fl o o k i n gf o rt h e i m a g e so nt h ew 曲a l t h o u g ht h e r eh a v eb e e ns o m ew e bi m a g e ss e a r c he n 百n e s a p p l d n g t h i st e c h n o l o g yw o r k i n gi nt h ew o r l dt o d a y , t h et e c h n o l o g yh a ss t i l lb e e nn o t p e r f e c te n o u g h f i r s t l y , f o rl a c ko fe n o u g hu n d e r s t a n d i n gt ot h ec o m p l e x i t yo ft h e w e b a c c o r d i n gt oac h a n g e l e s sm o d et h er e l e v a n tt e x t so fi m a g e sa r et a k e nf r o m h t m lp a g e s b e c a u s eo n l yas m a l lp a r to fi m a g e so nt h ew e ba c c o r dw i t ht h e c h a n g e l e s sm o d e ，t h ee f f e c to fa c q u i r i n gt h er e l e v a n tt e x t sf r o mh ，r m lp a g e s i sn o t g o o de n o u g h s e c o n d l y , t os o m ee x t e n tt h ew e i g h ts c h e m ei sq u i t ec o a r s et os o m e e x t e n tb e c a u s es o m ef a c t o r si n f l u e n c i n gt h ew e i g h to ft e r ma r en o tb r o u g h ti n t ot h e s c h e m e t h i r d l y , i n d e x i n gb a s e do nt e r m sa n dq u e r yt h r o u g hw o r dm a t c h i n gr e s u l ti n t h er a t h e rs e v e r ep r o b l e m so fs y n o n y m ya n dp o l y s e m y as e r i e so ft e c h n i q u e sr e l a t e dt o 协i m a g es e a r c he n g i n e ，s u c ha sc r a w l i n g ， r e l e v a n c er a n k i n g ( v s ma n dl s i ) ，i n f o r m a t i o ne x t r a c t i o na n di n d e x i n ga r ed i c u s s e d i nt h i sp a p e r t h o s et e c h n i q u e sw i l lb eu s e di no u rs y s t e md e s i g n i tc o n c e n t r a t e so n h o wt oe x t r a c ti n f o r m a t i o nr e l e v a n tt oi m a g e sf r o mh t m ld o c u m e n t sm o r e e f f e c t i v e l ya n dp r e c i s e l y a c c o r d i n gt oe x p e r i m e n t sa n da n a l y s i so nr e a ld a t a ，s e v e r a l k e yt e c h n i q u e sa r ep r o p o s e da sw e l la sat e x t - b a s e d 幻i m a g es e a r c he n g i n e 劢p g l o b a ls t r u c t u r eo fo u rs y s t e ma n dr e l a t i o n so ft h ec o m p o n e n t so fs y s t e ma r ea l s o d e s c r i b e d s o m ec o m p o n e n t sa r ed e t a i l e di nf u n c t i o na n di m p l e m e n t a t i o n f i n a l l ya s i m p l ee v a l u a t i o na b o u ts e a r c h i n ge f f e c ta n dp e r f o r m a n c ei sg i v e n k e y w o r d s ：w e bi m a g e s e a r c he n g i n e ，t e x t - b a s e d ，c o n t e n t - b a s e d ，i n f o r m a t i o n e x t r a c t i o n 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：悄东哥 a 铲1 月翦日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月 日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：锕乐彳 a o o o 眸1 月以日 第1 章引言 第1 章引言 1 1 研究动机 目前的i n t e r n e t 应用已经取得了长足的发展，随着网络带宽和终端计算能 力的不断增强，图片被越来越多的应用于内容的表达和信息的承载，特别是在 w e b 的应用上更是不可或缺。w e b 已经成为一个巨大的、分布的、动态的、快速 增长的资源库。然而，i n t e r n e t 本身是一个极度分散的系统，数以亿计的图片 分布在i n t e r n e t 的各个角落，人工寻找并获取需要的图片已经变得越来越困难， 因此，如何通过自动化的手段有效的获取和再利用这些图片资源成为信息共享 的一个重要课题。 图片的再利用问题涉及到图片信息的收集和检索问题。图片的信息是指图 片的内容所表征的意义，这种的信息承载方式与传统的文本的信息是不一样的。 由于文本的直观性和简单性，文本的信息即包含于本身：而图片的信息可以通 过图片本身的内容传达出来，也可以通过相关文字的描述传达出来，于是图片 便有了双重的信息载体。因而，图片在信息的获取上便有了不同于文本的技术。 按照图片信息来源的载体的不同，图片信息的获取技术被分为两大类：基 于内容和基于文本。基于内容的技术是对图片的内容本身( 像素) 进行分析和 检索，而基于文本的技术利用图片的相关文字信息作为分析对象，并提供类似 于传统文本检索的工作方式。 i n t e r n e t 的边缘化特点使得信息组织非常自由化，大量的图片文件被按照 不同的方式，不同的风格组织到不同的地方。文字和图片之间几乎是可以按照 完全随意的方式自由安置。但是统计的结果显示，大量的组织方式具有某些共 同的特点，这些特点符合人类获取信息的习惯。这就为提供一个通用的信息提 取框架提供了可能。在i n t e r n e t 上，通常图片和文本被有机的组织在一起，最 常见的组织形式就是h t m l 网页，于是通过h t m l 挖掘可以获取到大量的关于图 片的信息。 h t m l 网页是w e b 上应用最广泛的信息组织方式，是搜索引擎获取信息的最 主要来源。i n t e r n e t 上h t m l 网页数量及其所包含的多媒体资源相当丰富。 根据c n n i c 的2 0 0 5 中国互联网络信息资源数量调查报告显示： 第1 章引言 表卜1 网页数及网页字节数情况 2 ，6 0 1 ，9 0 1 ，3 7 8 个1 全国网页总数去掉重复后为： 2 ，4 0 2 ，0 7 5 ，3 5 2 个 网页数其中：静态网页数9 4 7 ，8 7 2 ，6 7 2 个 动态网页数1 ，6 5 4 ，0 2 8 ，7 0 6 个 静、动态网页数比例 0 5 7 ：1 平均每个网站的网页数3 ，7 4 8 个 全国网页总字节数6 7 ，3 0 0 ，1 0 6 ，0 0 0 k b 网页字节数每个网页平均字节数2 5 9 k b ( k b ) 平均每个网站的网页字节 数 9 6 ，9 4 6 k b 团静态网页数日动态网页数卜年增长率 图卜l 历年网页数及发展情况 奉次统计4 i 先行剔除j ，州站引叫站之间的完伞晕复等人量重复后网负总数为2 , 6 0 1 ，9 0 1 ，3 7 8 个，w 去j ! l ：i 刚 页。i 网页的重复后的嘲贝总数为2 , 4 0 2 ，0 7 5 ，3 5 2 个。 2 3 0 0 2 5 0 2 0 0 1 5 0 9 6 1 0 0 5 0 o 一5 0 第l 章引言 表卜2 网页的内容分类情况( 按多媒体形式) 图像音频视频 9 8 7 5 1 1 3 0 1 1 从以上统计数字可以看到，目前国内的w e b 信息资源数量已经相当可观， 并且随着i t 业在2 0 0 3 年的逐渐复苏，网页数量比2 0 0 4 年增长了一倍。网络上 的多媒体内容绝大部分以图像的形式存在，这对于图片搜索引擎的资源获取无 疑具有相当的价值。 w e b 搜索引擎技术已经被广泛的引用到i n t e r n e t 上，每天要抓取海量的 h t m l 网页，这是一个宝贵的资源库，但目前w e b 搜索基本上只利用到其中的文 本信息。如果充分的挖掘资源库中的潜在价值，可以建构出很多增值的搜索系 统，比如图片搜索，m p 3 搜索，f l a s h 搜索等等。因此，本文的切入点就是如何 有效的利用这些h t m l 网页来构建w e b 图片搜索引擎。 1 2 研究目标 1 2 1 应用领域 随着图片使用的同趋广泛和图片搜索技术的不断发展，图片检索系统的应 用范围变得越来越广。目前使用最广泛的是通用w e b 图片搜索引擎，比如g o o g l e 图片搜索，它面向通用领域的用户提供服务。除此之外，有大量的专用领域使 用到了图片检索，比较常见的领域有： 医药领域。许多的医学和健康相关的专业需要使用例如x 光、扫描影像之 类的一些可视信息资料，用于诊断和检测疾病。图片检索技术能够有效的用于 这类信息的表示、存储、传输和分析，针对该领域的研究主要集中在图像处理 上，例如边界或者特征检测，可用于跟踪肿瘤的生长等。该领域已经有成功的 系统使用案例。 图形设计领域。对于已有的设计的重用，可以为该领域的工作者提供大量 的素材和灵感，图片检索系统可以为这些工作提供大量帮助，同时，对于用户 寻找特定要求的作品也提供了很大的便利。 出版领域。出版社、报社、杂志社等机构对于图片的需求是相当多的，基 本上都有自己的图片库，传统方式利用多种归类方式来进行存储和查找。该领 域的工作者需要花费大量的时问来查找和挑选合适的图片，利用图片检索系统 第1 章引言 能够提供有效的帮助。 其它的一些领域还包括建筑设计、天文学、地理学、历史研究、犯罪取证 等。 1 2 2 用户检索方式 在检索方式上，图片检索相对于网页检索来说，有很大的不同。目前的网 页检索系统几乎仅有关键字查询一种，因为当前考虑范围内用于网页内容的唯 一描述只有文字。而图片可以有相关的文字描述，同时图片本身还具有自描述 性( 内容本身提供了语义信息) 。因此，图片通常具有多种检索方式，从用户检 索的角度看，可以分为如下几类： 目录式检索： y a h o o 的图片搜索【2 】集成了其网页搜索的特点，将图片进行分类，用户按照 分类结构逐渐细化查询范围。目录式检索方式经常需要人工来进行大部分的分 类工作，因此代价是相当高的。 关键字查询： 目前使用中的大型图片搜索引擎使用的方式【3 】。用户给出与所需的图片相关 的文字，系统根据之前建立的文字到图片的匹配来查找包含有查询词的文本对 应的图片。关键字检索方式最显著的优点是其检索速度非常快，并且基于文本 的索引技术已经很成熟。信息和文字的匹配上有两种方法，一种是人工标引， 一种是自动提取。 人工标引对于信息的准确度方面是效果比较好的。但是也面临几个主要的 缺点：一是人工标引工作量太大，在海量系统中几乎是不现实的。二是人工标 引的信息主观性比较强，有时候不能恰当的反映图片的真实信息或者反映的信 息不完全( 后者几乎总是存在) 。 自动提取方法的难点在于如何为图片提取j 下确的文字信息。由于信息组织 的多样化以及难于判定具体的组织方式，很难确定哪些信息是与图片相关的。 这种方法通常采用启发式规则来进行信息提取，使用比较常用的模式来获取信 息，并通过无用信息过滤等技术来尽可能的提高信息的准确性。 实例式检索： 目前的基于内容的图片搜索引擎大多是这一类。方法是提供一张图片实例 或者由用户绘制一个大概的形状，系统根据某些可视特征去寻找在该特征上相 4 第l 章引言 似的图片。这种检索方式的优势在于发现相似图片的效果比较好，缺点在于需 要用户提供图片实例，这一点通常使系统变得很不友好。虽然基于内容的检索 系统可以提供一些分类信息，但也仅限于户内或者户外，风景或者人物等粒度 比较大的分类。 属性式检索： 这种检索方式多用于小规模的专门的图片数据库，比如摄影图片库，用户 可以根据作者，拍摄日期等一些图片的外在特征来进行检索。该类数据库具有 集中式管理的特点，信息往往比较规范，建立索引和检索过程都相对简单，可 以使用现有的关系数据库来实现。 1 2 3 系统评价 检索系统中很重要的系统评价指标是查准率( p r e c i s i o n ) 和查全率( r e c a l l ) h 】。查准率表示查询结果中相关的文档数所占结果文档总数的比例；查全率表示 查询到的相关文档数占整个文档集合中所有相关文档数的比例。假设对于特定 的查询，d + 为整个文档集合中相关文档的数量，r 为查询结果文档集合，r + 为 结果文档中相关文档集合，则查准率和查全率可以形式化的定义为： 查准率：p re c i s i o n = i r + i t r i 查全率：r e c a l l = l r + i i d + i 在图片检索系统中，对于这两项指标的度量比较困难，因为对于图片与文 本的相关性评价是相当主观的，基本上只能得到一个很粗略的统计结果。 除了以上两项指标以外，还有一个评价指标是性能，即系统提供服务的能 力度量，可以包含系统的吞吐量，响应时问等。 系统的可扩展性也是需要考虑的，当查询数量和频率增加以后，可以通过 增加服务的主机数来满足性能的要求。比较好的期望是系统能够接近线性可扩 展性。 1 3 研究现状 基于文本的图片检索【5 1 最早可以追溯到2 0 世纪7 0 年代早期，当时的检索系 统使用人工对图片的内容进行文字信息标引，利用d b m s 存储文字信息，并利 用文本检索技术提供查询。当时的研究多集中在数据建模、多维索引、查询评 第1 章引言 估等数据库技术上。当图片库的规模急剧增大以后，人工标引需要耗费大量的 人力，依然使用这种方法变得不切实际，需要提供一种自动的技术来完成信息 的索引，另一方面，人工标引提供的信息相当主观，而且往往只反映了图片某 一方面的内容。 为了克服这些缺点，在2 0 世纪9 0 年代早期，提出了基于内容的图片检索 技术。该技术不需要进行文字标引，而是通过图片本身的可视化内容来进行索 引，例如颜色、纹理、形状等。自此，很多的学者针对基于内容的技术进行了 大量的研究，提出了很多的算法，并开发了很多的实验系统。当前大量研究热 点集中在基于内容的检索上。但是目前基于内容的检索在实际使用中不尽人意， 单纯的使用误识率较高，主要的原因在于这类技术仅仅使用图片的相似关系来 进行检索，并不符合人们检索信息的习惯，而且目前的相似性度量方法还比较 粗浅，效果并不太好。 鉴于此，有学者提出了基于语义的图像检索【3 4 1 ，该技术试图建立一种高层 次的语义到低层次的可视特征之问的映射关系，实际上是试图将可视特征识别 为语义概念，使之类似于人类识别事物的方式。例如当分析出上半部分为白色， 下半部分为蓝色的图景时，能够理解为“海平面”。该技术需要使用到知识库， 用于存储语义网络和映射关系。关于可视特征的识别需要深入的理解人类的视 觉机制，这方面的进展还不太大。， 在所有的图像检索技术中，无疑基于文本的检索是效率最高的一种，很多 的图片搜索引擎都全部或部分的运用了基于文本的检索机制。目前w e b 上 h t m l 文档的大量出现使得图片的文字信息可以借助于分析h t m l 文档得到， 从而克服了人工标引的不足。因此，这一类的系统在实际应用中取得了不错的 效果。 1 4 研究目标 1 提高图片检索的质量。 基于文本的图片检索技术，脱胎于现己较成熟的文本检索技术，因此，借 鉴文本检索技术，促进基于文本的图片检索技术的发展，是比较省力和有效的 方法。 但目前，许多图片检索系统，常常照搬文本检索中某些不适合用于图片检 索的技术，给w e b 图片检索性能带来许多负面影响。此外，现有的相关文本提 取和权重模式的研究还有待加强和深化。针对上述技术现状，以相关文本提取、 权重模式、图片信息的索引和查询三个子领域的问题作为研究重点，对提高图 6 第l 章引言 片检索质量，有一定的实际意义。 2 促进图片检索技术的研究。 w e b 在迅速增长的同时，也变的越来越商业化。特别是w e b 图片搜索站点， 在提供图片信息检索服务的同时，附带了许多与图片相关的商业行为。毫无疑 问，商业操作的过多介入，除了影响查询结果的有效性，更直接导致各搜索站 点相对地减少了对技术研发的投入，并进一步使各个搜索站点画地为牢，限制 彼此的沟通和交流，从而在更大的范围内影响该技术的发展。 1 5 研究成果 对于现存的图片搜索引擎的分析可以发现，目前的商用搜索引擎基本上使 用基于文本检索的方法，主要原因是为了提高系统的性能，以支持庞大的用户 群，处理大量密集的查询请求，并且保持亚秒级的响应时间。而研究性的图片 搜索引擎大多使用到基于内容检索的方法，或者是两种方法的结合，主要是为 了提高检索的精度。 已经有大量的研究集中在基于内容的图片检索上，并提出了大量的模型和 算法。而针对如何尽可能的提高基于文本检索方法的精度的研究比较少，而这 方面的研究也是很有价值的。通过分析w e b 的结构特点，h t m l 的信息组织形 式，采用适当的提取算法，应用有效的信息索引方法，可以获得很好的系统效 能。鉴于此，本文将主要工作放在基于文本的检索方式上。 1 6 论文结构 在第2 章中，介绍了一系列与w e b 图片搜索引擎相关的技术。 在第3 章中，对如何得到与图片相关的文字进行了集中的阐述，着重分析 h t m l 的结构，w e b 的组织方式和一些潜在信息，通过启发式模式提取图片的 相关文字信息。为了提高图片的质量和信息的准确性，统计分析了w e b 上的图 片表现出来的一些规律，并将这些规律应用于无用图片过滤和图片权重确定等 规则中，从而改进图片和信息的质量。 本文也简单的介绍了主要的基于内容的信息提取方法，并在第4 章中提出 与基于文本的方法结合的手段，并通过l s i 方法来提高图片的高低层语义之间 的相关性，并演示分析了效果。 本文在第5 章中介绍了我们初步实现的一个系统，提出一个w e b 图片搜索 引擎的实现框架，并分析其中各个模块的工作和相互关系，并对系统的运行结 7 第1 章引言 果进行一定的效果和性能分析。笔者在其中主要负责信息提取、建索引和提供 检索相关的模块的工作。 本文最后针对现有的技术进行总结，并提出改进建议和今后的发展方向。 第2 章相关技术 第2 章相关技术 基于文本的w e b 图片搜索引擎是一个复杂的系统，需要多个工作部件之间 的协调工作，比如纯文本网页和二进制图片的抓取，图片的文字信息提取，对 文字信息建立索引，提供高性能的查询手段等。因此，整个系统设计需要考虑 诸多的技术问题，本章下面的部分，对影响系统设计的主要相关技术进行了介 绍和分析，包括网页抓取技术、相关排序技术、信息提取技术、信息索引技术 和其他相关技术，为第4 章中w e b 图片搜索引擎的设计和实现过程作技术准备。 2 1 信息检索技术 上文提到， w e b 图片搜索引擎中图片的信息提取有两种主要方式：基于内 容的提取和基于文本的提取。 基于内容的提取通过分析图片本身的二进制内容( 像素) ，提取出其中的一 些可视化特征，并对这些特征建立索引，在提供检索开寸，通过与检索示例图片 的同类特征进行比较来度量图片之间的相似性，并返回相似度最高的图片。 基于文本的信息提取并不试图分析图片本身的内容，而是尽力提取与图片 相关的文字信息，以这些文字作为图片内容的表征。获得文字信息之后，可以 利用传统的文本信息检索的相关技术来提供信息的组织和查询。 下面简要介绍一些基于内容和基于文本的信息提取技术，并进行简要的分 析。 2 1 1 基于内容的检索技术 基于内容的图片检索技术分析的对象是图片本身的二进制数据，该技术试 图通过分析数据，从中发现可视化信息，并利用匹配技术得到相似的图片。 和文本检索一样，基于效率上的考虑，不可能在检索的时候才去分析图片 的内容，而必须对待检索的图片集进行预处理，主要是提取其中的可视化信息， 利用多维索引技术建立索引，从而使得检索的时候只需要利用某种匹配算法在 索引中查找即可。 可视化特征提取是基于内容的图片检索的基础，按照应用范围可以分为特 定领域的特征提取和通用特征提取。前者是应用相关的，涉及到知识库，比如 对于人脸的识别，这方面的技术在模式识别领域中讨论的比较多；后者是独立 9 第2 章相关技术 于应用的，所以适用范围要广得多，他仅仅提取一些很基本但重要的可视特征， 并不要求对这些特征进行识别，这一点对于基于内容相似匹配的图片检索已经 足够了。这里重点介绍通用特征提取方式。 由于人们对于图片的观察是很主观的过程，往往存在不同的视角，并没有 一个唯一的标准来定义什么是最佳( 最精确) 的可视化特征。所以，在进行特 征提取的时候，通常也是从多个不同的角度去考虑，从而形成了多种可视化特 征对象。经常被用于分析的特征有颜色( c o l o r ) 、纹理( t e x t u r e ) 和形状( s h a p e ) 。 颜色 颜色是最常被用于基于内容的图片检索的可视化特征之一。颜色提取的优 点在于对图片的大小和方向不敏感，并且对于处理各种背景复杂的图片时效果 比较稳定，同时，颜色是也描述图片的最简单的特征。 颜色直方图是最常被用于颜色特征表达的方法，它从统计意义上表示了三 种颜色通道的强度的关联概率。s w a i n 等人提出了颜色索引方法，利用颜色直方 图的交和反投影来度量图片之间的相似性( 1 5 】【3 2 1 。 在进行颜色直方图生成时，颜色系统的选取是一个很重要的问题。r g b 是 使用最广泛的颜色系统，它表现了本原的颜色属性，但是没有考虑人眼视觉观 察的一些特点( 比如人眼对于不同颜色差别的敏感程度是不一样的) ，对于某些 应用并不是最佳选择。另外的一些颜色系统，比如u 水v 木w 、l * a * b 、l * u * v 等， 充分考虑了人眼对于颜色感知上的特点，因此适合用于图片检索这类需要满足 人眼视觉要求的系统中【2 0 1 。为了克服颜色空间信息丢失的缺点，之后的很多改 进模型被提出来。 形状 形状也是图片中的一个重要的可视化特征，是人类认知自然对象的最基本 特征。形状特征的描述通常有两种常用的方式：基于边界的描述和基于区域的 描述。 基于边界的描述方式中使用最多的是傅立叶描述子( f o u r i e rd e s c r i p t o r ) 。该 方法只考虑图片中对象的外层边界，并对边界进行傅立叶变换，作为对象的形 状特征。为了消除数字化噪音的影响，r u i 提出了改进的傅立叶描述子方法 1 引， 该方法同时对于形状的几何变换具有很好的鲁棒性。基于区域的描述方法中常 用的方法是不变矩( m o m e n ti n v a r i a n t ) ，其对于形状的变换来说是恒定的。h u 提出了7 种不同的矩 1 5 】，后来有人提出来改进的计算方法【15 1 ，有效的提高了计 1 0 第2 章相关技术 算的效率。 在实际应用中需要考虑时间和空间效率的因素，往往采用更简单的形状描 述和检索方法，比如形状参数( s h a p ef a c t o r ) t 3 2 1 ，考察面积，周长等参数，在 实际中得到较好的应用。 纹理 纹理也是图像的一个重要特征，其描述了对象表面的像素分布规律。描述 纹理的主要的方法有结构方法，统计方法和频谱分析方法【3 5 1 。结构方法主要针 对有规律的纹理结构，利用句法分析方法来进行识别。统计方法通过对像素的 分布进行统计，发现其中的分布规律。频谱分析方法主要是利用小波变换来生 成纹理特征，实践证明是效果比较好的纹理识别方法【3 引。 基于内容的图片分析中还有一种比较特殊的应用，用于发现图片中包含的 文本。目前有很多的图片，文字被嵌入到了其中，通过图片的像素表现出来。 这种信息对于人们理解来说轻而易举，但是由于其丢失了文字本身的信息，对 于机器理解还有很大的难度。 目自寸在模式识别领域有很多的关于识别图片中文本的研究。z h o u t 2 7 j 等提出 了一种文本识别算法，利用c o l o rc l u s t e r i n g 和c o n n e c t e dc o m p o n e n ta n a l y s i s 方法 将输入图片的颜色空间经过预处理量化为一系列的颜色类，然后标示出每一个 颜色类中类似文本的连接成分，最后将这些连接成分通过后继处理转化为文本。 该方法的难度在于图片中的文字可以是任意的颜色，并且有些图片的文字背景 图案由各种不同颜色的对象构成，难于将其识别为独立的成分。 基于内容的检索技术有基于文本所不具有的特点，其一大优势在于它分析 图片文件本身包含的信息，可以不依赖于图片的来源。这样带来的一个非常显 著的好处是，我们收集的可用于检索的图片的领域将会变得广阔得多。我们不 仅可以利用w e b 中无法提取文字信息的图片，还可以到邱等其他形式的并不包 含有充分的文字信息的网络资源中去获取图片。 另一个潜在的优势是，分析图片内容本身来探究其包含的意义符合固有的 人类理解图片的方式，随着计算机视觉和人工智能等技术的不断发展，图片分 析技术将会不断接近于人类的视觉认知水平。 2 1 2 基于文本的检索技术 基于文本的提取技术【1 0 1 通过分析w e b 上的资源，来获取图片的相关文字信 息。h t m l 文档能够将文字和图片组织在一起，提供了非常丰富的信息，因此 第2 章相关技术 成为我们提取信息的主要资源。通过分析h t m l 中的标记，可以利用一系列启 发式规则来获得相关的图片和文字。在这里，启发式规则的选择是相当重要的， 它将直接影响到系统的查准率，同时也在很大程度上影响着系统的查全率。 其它类型的资源，比如f t p ，从中基本上只能得到路径和文件名信息，而且 这些信息常常是无关的，因此基本上无法用于图片的文字信息提取。 本文中，我们提出了利用h t m l 来获得图片信息的一些方法以及对于 h t m l 的一些潜在意义的分析，详细的内容在第3 章阐述。 2 1 3 两种不同检索技术的比较 表2 - 1 两种图片检索技术的比较 比较项目基于文本的图片检索技术基丁内容的图片检索技术 信息提取图片提取相关文本，并通过提取并分析图片的视觉特征，一 与分析分词，获取词条集合，并赋般包括颜色，纹理和形状等 予词条以权重 建立索引根据赋有权重的词条集合，根据图片视觉特征，生成图片的 生成能代表相关文本意义的视觉特征索引，该索引同时也被 索 - 3 i ，该索引同时也是图片 认为能代表图片的信息 信息的索引 索引反映图片的语义信息，主题和文 图片的视觉特征，更多反映图片 档作者所赋予图片的意义，的客观特征 更多反映图片的主观和概念 特征 查询方式语义与概念查询：视觉柏似查询： 用户用文字，提出“我要搜用户用一张示例图片，提出“我 索什么样的图片” 要搜索这样的图片” 优点可充分利用文本索 - 3 i 技术，小必借助语言，直接考察图片： 加快研发：实现代价柏对较 4 i 受语种6 艮韦4 ： 小，效率相对较高；便于使用搜索过程寅观，方便 相对抽象的语义和概念进行 查询，符合人们习惯 代表与示 g o o g l ei b m 开发的q b i c 例 由表2 1 可知，这两种技术各有所长。但从实际使用情况来看，目前，基于 1 2 第2 章相关技术 文本的w 曲的图片检索技术优于基于内容的图片检索技术。以g u o j u nl u l 3 6 研 发的w e b 图片检索系统为例：在这个实验系统中，包含两个子系统，一个子系统 使用基于文本的图片检索技术，而另一个使用基于内容的图片检索技术。我们 对这个系统的进行了测试，据不完全统计，基于文本的子系统和基于内容的子 系统查询结果相关率为：6 0 v s 2 0 。尽管这个结果不能完全准确地反映目前两 种技术的性能对比，但对找们理解它们的研究现状和发展前景，还是有参考价 值的。 2 2 相关性排序技术 检索结果相关性排序是所有的检索系统中必须考虑的问题，特别是对于搜 索引擎这样的海量数据检索系统。随着图片数量的急剧增长，用户每次查询返 回的结果数也相应的迅速增大。如果将所得到的结果不分主次的呈现给用户， 必然会导致很糟糕的效果。为了尽可能的更好的满足用户的需求，系统需要按 照某种原则将用户最关心和最想得到的信息最早呈现，以此来提高系统的搜索 效果。 传统的关系数据库是利用s q l 语言来描述查询要求的，查询得到的结果是 无序的( 相对于相关性来说) ，因为s q l 描述的是一种精确的查询模式，不能在 其中加入启发式的规则，无从对结果的重要性进行描述。 下面介绍两种比较常用的相关性排序技术：v s m 和l s i 。 2 2 1 v s m 介绍 目前的i r 系统中普遍使用的一种相关性排序技术是v s m 4 1 ( v e c t o rs p a c e g v l o d e l ，向量空间模型) ，该项技术的发展已经相对比较成熟在大量的系统中 取得了比较好的应用效果。v s m 是一种基于词频统计来度量文档的相关性的经 验模型。 按照v s m 的方法，文档( 包含某一组信息的集合，某个图片的信息也可看 作一个文档) 被表示为向量的形式。形式化的定义为： d = 其中，d 代表文档，其 是一个n 维的向量。t 1 t n 为词项( t e r m ) ，n 是所有的文档集中出现的词项的 总数，w t i 为词项t i 在文档d 中所表现出来的重要度( 权值) ，其值由下面的公 式给出： = t f ：l i d f 第2 章相关技术 t f 2 1 】【2 2 】( t e r mf r e q u e n c y ，词频) ：表示为t f ( d ，t ) ，最简单的形式是n ( d ，t ) ， 即词项t 在文档d 中出现的次数。为了防止出现某些奇异词项对w 计算结果的 干扰，通常进行正规化，可以采用这种形式： t f ( d ，丁) ：辈2 旧 i d f 2 1 】( i n v e r s ed o c u m e n tf r e q u e n c y ，倒排文档频率) ：表示为i d f ( t ) ， 通常指包含有t 文档数的倒数。利用d 。1 1 表示所有的文档集合，d t 表示包含有t 的文档，同样为了防止干扰，可以表示为如下形式： 脚( 丁) ：l o g 掣掣 一 l 珥l v s m 基于以下考虑：某个词项在文档中出现越多，则该词项对于文档的信 息表达的相关度越高；而包含该词项的文档所占总文档数比例越小，则该文档 的区分度越高。 文档被形式化的表示成向量以后，我们可以通过将查询也表示成向量形式， 而通过计算两个向量在向量空间中的夹角来评估文档与查询之间的相似度。 1 3 n 研，2 肠力纱d ，q = c 。文d ，q 2 币葡i 渤 v s m 具有表示直观，计算方便的优点，但是也有很多不足之处。对于词项 重要性仅仅利用词频来计算是比较武断的做法，往往并不能j 下确的反映实际的 情况。另外，当文档集中大多数文档包含的词项都较少时( 图片信息恰好有这 样的特点) ，词频统计将失去意义，这时使用该模型往往不能取得好的效果。 但是v s m 的重要意义在于，它提供了一种通用的方法来比较特征之间的相 似性。对于具体的应用而言，可以利用待检索对象的其他特征作为该对象的向 量，比如图片，可以使用可视化特征或者其他相关特征来建立图片的向量空问， 从而，可以针对这些特征来进行相似度计算。 2 2 2v s m 的改良：l si v s m 技术是一种精确的索引技术，只有包含有查询词的文档才会被检索到。 但是语言本身所固有的多义性和同义性是普遍存在的，这会导致两种形式的查 询结果无效，从而影响到查准率和查全率。一方面，同一个词表达的意思在不 同的上下文中是不一样的，这种情况下，查到的结果往往并不是想要的，影响 查准率；另一方面，相同的意思可以使用多种不同的词来表达，这种情况下， 只有包含查询词的文档爿会被检索到，而其他的相关的文档将不能查到，影响 1 4 第2 章相关技术 查全率。第一种情况下，用户可以通过观察将不相关的文档滤掉，相比之下， 第二种情况可能更糟，因为用户根本无法获取到想要的信息。 目前的双系统中普遍存在这样的问题，究其原因，在于查询本体与形式之 间的映射偏差。用户想要查询的信息是在头脑当中的某种意识或目的，但必须 通过映射到词语才能在瓜系统中进行查询。图片检索系统中，这个问题更加严 重，多了一次映射，即从图片到词语。所以有些系统中提供了基于内容相似的 查询( 用户提供一张图片，查询类似的图片) ，这样免除了一次映射，对于查询 某些无法或很难利用词语来描述的图片来说，提供了一种较好的检索方式，但 目前的效果还不理想。 除了以上提到的多义性和同义性问题之外，还普遍存在的一个问题是信息 不充分。我们不可能得到用于描述某图片的很全面的文字信息( 即使是人工标 引方法也不可能) ，而往往只能获得某个方面的描述，这将导致系统的查全率降 低。 传统的检索系统中通常是引入一个知识库来试图解决上述问题。当用户提 出检索时，利用知识库中的同义词表做检索词扩展，这在一定程度上可以解决 同义性问题，但多义性问题依然无法得到较好的解决。更糟糕的是，对于通用 搜索引擎这样的领域无关系统，根本无法建立知识库。 针对以上问题，d e e r w e s t e r 等人提出了l s i 模型( l a t e n ts e m a n t i ci n d e x i n g ， 潜在语义索引) 【8 】【9 1 。该模型不试图利用任何外部知识，而是从挖掘文档集本身 的潜在信息入手，利用统计分析方法来构造语义空间结构，自动发现文档之间 的潜在语义关系。l s i 模型是对于v s m 模型的一种改良，已经被证明在很多应 用中具有显著的改进效果，能够在很大程度上弥补v s m 的不足。 l s i 模型基于一点假设：在文档集中协同出现( c o o c c u r r e n c e ) 的词之间具 有相关性，协同出现的频率越高则相关性越强。例如，如果在大量的文档中同 时出现“l i n u x ”和“g n u ”，则可以认为这两个词之间具有较强的相关性。 l s i 通过统计方法，对大规模的文档集合构造对应的矩阵，并通过s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ，奇异值分解) 和降维处理，来将文档和词的关 系映射到相似的低维的语义空间中。此时的语义空间揭示了词与词之间，文档 与文档之间，文档与词之间的潜在相似度关系，提供相当丰富的信息。 下面简要的介绍l s i 模型的计算方法。 首先需要建立矩阵x = t d ，矩阵的行代表词，列代表文档，矩阵的单元代 表词在文档中的权值。该权值的计算有很多种方法，最简单的就是词在文档中 出现的频率。另外的一些计算方法有绝对词频加权法、平均词频加权法、相对 1 5 第2 章相关技术 频率加权法、逆文档频率加权法以及多种加权法的综合运用。 然后是对词频矩阵x 进行奇异值分解( s v d ) ，得到如下形式的三个矩阵的 乘积： x = t o s o d ： 其中， s 。= d i a g ( c r ，仃：，仃。) 为奇异值的对角矩阵， 并且有 g r l 仃2 仃。，t o 和d o7 是正交矩阵，即：瓦巧= d o d ；= e 数学上可以证明，任意的矩阵总是能够进行这样的分解。 接下来是对s o 矩阵进行降维。选定一个k 值，保留s o 矩阵的对角线上的前 k 个最大的o ，而将其余的替换为0 。 用降维以后的s o7 代替原来的s o ，重新计算得到新的x7 矩阵的值。 此时的x7 矩阵是原来的x 的一个近似，重要的是语义结构已经被映射到 低维空间中，并且消除了语义上的细微差别而保留了重要的潜在语义关系。此 时文档和词之间的相关性度量被直观的表示为x7 矩阵中文档与词对应的单元 上的值。 k 值的选取是很重要的，太大会导致结果趋近于原始矩阵而失去挖掘潜在语 义的能力，太小则会使得语义信息丢失太多，以至于对于文档和词的分辨能力 不足。 实际上，l s i 的应用远不止于相关性排序。在不同的应用环境当中，对矩阵 的构造方法进行一些变化，能够衍生出很多l s i 的用途。由于能够通过统计来 挖掘大量的相关性这一特点，l s i 被广泛的应用到了包括文本检索、文本分类、 信息过滤、文本摘要、双语交叉过滤、垃圾邮件过滤、个性化服务、智能检索 等在内的广阔的领域中。 在图片搜索引擎中，图片本身能够提取到的信息是有限的，主要是由于两 点原因：1 ) 本身可供提取的信息比较少；2 ) 即使是可以提取大量的信息，考 虑到相关性低的问题，往往也只保留很少的一部分。 因为词对于文档的权值是反映词对于文档的重要性，对于不同的应用，应 该判断哪些词对于文档意义的贡献更大，从而赋予更高的权值。所以，在图片 搜索中构造l s i 初始矩阵的方法也需要一些变化，不应该单纯使用词频方法作 为词在文档中权值的计算准则，可以通过综合考