（计算机科学与技术专业论文）基于多线索融合的互联网图像搜索引擎关键技术研究.pdf

浙江大学硕士学位论文 摘要 摘要 随着计算机技术的发展和网络带宽的提高，互联网上的图像资源变得越来越 丰富，它们被大量的内嵌在h t m l 网页中，构成了一个庞大的“互联网图像库”。 信息量的庞大和纷繁复杂使互联网图像检索技术变得十分重要，而目前图像检索 的瓶颈问题是如何准确识别图像的语义。基于内容的图像检索在利用图像底层特 征逼近语义上仍存在很大的鸿沟，而使用人工标注则费时费力。需要注意的是， 与普通的图像库不同，互联网环境为图像提供了多线索的语义支持，例如图像所 处网页的网页结构、环绕文本、链接信息等。然而，目前的搜索引擎未能很好的 融合利用这些线索，从而给出较低的查准率和查全率。另外，目前的搜索引擎没 有对返回结果进行有效的归类，给用户的使用造成不便。本文对互联网图像搜索 引擎的关键技术进行了拓展性研究，重点研究了多线索融合的图像标注技术和基 于谱聚类算法的分类技术，并实现了一个互联网图像搜索系统i s e ”c h 。这些技 术对于解决互联网搜索引擎和类似信息库的分析与检索问题有一定的价值。 本文首先介绍了研究背景，简述了现有技术与不足，并概括了本文的主要工 作。 在第二章中，综述了图像检索的研究状况，包括相关技术和典型系统。 在第三章中，介绍了基于各种线索的图像标注方法，然后对融合多线索的网 页图像标注技术作出探讨。 在第四章中，讨论了利用谱聚类对网页图像进行分类的方法，介绍了谱聚类 方法涉及的网页图像向量化、降维算法和聚类算法。 在第五章中，实现了一种基丁互联网图像标注和分类的图像搜索系统 i s e a r c h ，在本章巾对其系统架构和实现技术进行了介绍，并给出实验结果。 在第六章中我们对全文作了总结，讨论了本文所述技术的应用前景和未来的 研究方向。 关键字：图像，检索，多线索，标注，分类，谱聚类 浙江人学硕h 学位论文 概述 1 1 研究背景 第1 章概述 由于计算机网络及相关技术的日渐成熟，加上数字摄像设备的普及，在网页 上使用图像变得非常普及。图像能极大的丰富网页的可观性，增强用户的对信息 的直观认识，现在已经成为当今网页不可或缺的一部分。这些网页图像成为了用 户获取感兴趣图像的一个重要来源。如何根据用户需求有效的搜集这些图像资料 成为当前学界研究的一个热点。从而也提出了新的挑战： 1 、图像需要进行语义层面上的理解 初始的图像搜索系统通过人工标注进行索引检索，缺点是不仅费时费力，而 且由于自然语言的模糊性和人工标注存在偏差，效果很不理想。由此基础上发展 的基于内容的图像搜索系统【1 ，2 ，3 ，4 ，5 】一定程度上改善了这个问题。但由于目 前技术上纯粹利用图像的底层特征去逼近高层语义仍然存在很大的困难，因此基 于内容的图像搜索系统存在较大的局限性。对于互联网的图像搜索系统，由于图 像周围的语义环境非常丰富，包括标题、图像说明、环绕文本和链接等，这些语 义环境对图像的内容进行了比较准确和详细的描述。针对互联网图像的这种特殊 性，需要一种有效的工具，对这些文本信息和链接信息进行利用，从而实现在语 义层面上理解图像。 2 、返回结果需要进行合理的分类 目前基于关键词查询的互联网图像检索系统，如g o o g l e 和b a i d u ，其图像返 回结果是无分类的，但由于用户查询关键词的多义性，造成返回结果存在多个分 类，例如在百度图像搜索引擎( h t t p ：i m a g e b a i d u c o m ) 键入“苹果”，返回结果 既有水果“苹果”，又有“节果”电脑公司的新闻图片，目前的检索系统不加区 分的呈现给用户，给用户查找和利用图像资源造成了很大的麻烦。因此，需要一 种图像分类机制，把相同语义的图像进行有效的组织。 浙江人学硕士学位论文 概述 1 2 图像检索技术历史 为了便于人们快捷准确地访问图像资源，图像检索领域的研究人员在过去的 十几年中开展了大量的研究工作。目前图像检索的主流技术主要有两种：基于关 键字的检索方法和基于内容的检索方法。 用于文本检索的信息检索技术在过去的几十年中得到了充分的研究，并已成 功运用于诸如g o 0 9 1 e ，l y c o s 等商用搜索引擎中。在7 0 年代末，这种技术首次 被用于图像检索中，这就是基于关键字的图像检索。这种方法的通用流程是首先 人工对图像用关键字进行注释，然后通过匹配用户查询( 关键字) 和图像的注释 来搜索相关图像。文献 6 中对使用这种方法的系统进行了综述。这种方法的缺 陷是显而易见的：首先，人工注释需要大量劳动力和时间，因此这种方法不适用 于大规模的数据集合；其次，由于完全依赖人工来标注图像中的对象、事件等所 有信息，它所支持的查询的复杂程度也完全取决于人工标注的详尽程度；最后， 由于不同的人对于同样的图像有不同的理解，甚至可能出现错误理解，这些理解 上的偏差和错误会导致图像注释的不精确性，从而引起检索过程中的错误匹配。 为了解决上述问题，9 ( ) 年代初期人们又提出了基于内容的图像检索技术。 这种技术从图像中自动提取底层的视觉特征，比如颜色、纹理、形状等，作为图 像的索引。在检索中，用户提交一幅能代表自己需求的“例子图像”给系统作为 查询，系统会返回与此图像在视觉特征上相似的其他图像作为检索结果。文献 4 中综述了基于内容的图像检索技术。基于内容的检索方法的问题在于，它所用来 描述图像的特征是一些底层的视觉听觉特征，而人们则爿惯于在语义层次上衡 量检索结果的相关与否。以目前的计算机视觉技术，我们还很难从图像内容的底 层特征中对应到高层语义，因此基丁内容的检索方法的准确性还不高。 另外，在多媒体检索领域中还有三个新的趋势。第一，研究人员不再像早期 那样致力于建立全自动的检索系统，而是”始利用人机交互来辅助检索。这方面 的一个典型技术就是相关反馈技术【7 ，它通过分析用户对以前检索结果的评价 来不断地优化检索结果。第二，研究人员存检索中融合不同类型的多媒体数据( 通 常是文本和图像之问) ，比如p a e k 等人尝试结合丈宁和视觉特征来进行图像分类 1 8 ，而l u 提出了基于父键字和底层特征的图像榆索和相关反馈方法 9 。第三， 研究人员采用统计学习方法或者是对象议剖技术来傲多媒体数掘的文本标注和 浙江人学硕士学位论文 概述 检索，比如j e o n 等人提出采用交叉媒体干h 关模型来进行图像的文本自动标注和 检索【1 0 】，而d u y g u l u 等采用对象识别技术做图像到文本的机器翻译【1 1 。 1 3 本文的主要工作 在回顾了图像检索的研究状况后，现有技术的一些不足之处也突现出来，主 要表现在以下两个方面： 不能有效自动支持基于语义的检索：传统的基于关键字的图像检索需要由人工对 数据关键字标注，效率十分底下而且还可能带来很多主观偏差和错误。而基于统 计学习和对象识别技术的语义获取方法还局限在特定的研究范围内，不具有通用 性。另一方面，基于内容的检索方法尽管是全自动，但是所用的多媒体底层特征 难以对应于其语义特征，普通用户需要对多媒体的底层特征有一定了解才能提出 查询需求，同时由于人们倾向于通过语义层次上的寿h 关性来判断检索结果的好 坏，所以此方法在检索的准确率上不能满足用户要求。 不能智能地进行图像分类呈现：目前的互联网图像检索系统对搜索结果以同一分 类的形式进行呈现。然而，由于用户查询关键词的多义性，造成返回结果可能在 语义和内容上大相径庭，因此，这种静态的结果显示模式不能满足用户精确查询 的要求。 本文针对上述两方面不足，对图像分析与检索技术进行了扩展性研究，使其 能够更加有效的访问互联网图像资源，更加符合用户的实际需求。 首先，针对图像手工标注的缺点，提出了个互联网图像自动标注的机制， 综合考虑了图像周围的语义环境，在选择芙键词时对其位置、全局词频和局部词 频进行全面考虑，使选出的关键字能比较好的体现图像语义。 其次，针对图像无分类呈现的缺点，提出了一种结合文本信息和链接结构的 分类方法。把返h 的图像按照语义信息进行分类，并根据每类中图像与质心( 该 类的代表性图像) 距离的远近对图像进行排序。通过这样的过程，町以把结粜以 浙江火学硕士学位论文概述 分类、有序的方式呈现给用户。 1 4 本文的组织 本文首先介绍了研究背景，简述了现有技术与不足，并概括了本文的主要工作。 第二章，回顾了图像检索的研究现状，包括技术路线、相关技术和典型系统。 第三章，介绍了有关图像标注的几种线索，然后导引出融合多线索的：t 联网图像 标注算法。 第四章，研究了基于谱聚类的图像分类技术：文本向量化、降维技术、聚类算法。 第五章，实现了一种基于互联网图像自动标注和分类的图像搜索原型系统，在本 章中对其系统架构进行了介绍，并给出实验结果和数据。 第六章，对全文作了总结，讨论了本文所述技术的应用前景和未来的研究方向。 浙江大学硕士学位沧文 图像搜索系统综述 第2 章图像搜索系统综述 图像搜索系统的研究主要是沿两条路线展开，一是基于关键字的检索方法， 一是基于内容的检索方法。目前也有很多系统【8 ，9 】尝试结合多种媒体进行检索。 在本章中，我们将分别介绍基于内容的图像检索技术，以及多模态结合的图像检 索技术，包括基于网页块分析和基于语义网络的图像检索系统。 2 1 基于内容的图像搜索系统 一系统框架 很多基于内容的图像检索系统【1 2 】都可描述为图2 1 的框架。通常我们研究图 像搜索系统关心的是用户如何形成一个查询、相关反馈是否支持以及怎样实现、 什么特征被使用了、在查询图片和数据库图片之间是如何被匹配的、检索出来的 结果怎么呈现给用户以及系统采用什么样的索引结构。用户界面通常包含了用户 查询生成器和结果显示部分。图像怎样呈现给用户可以使用多种方式。其中一种 是通过数据库一张张的浏览。另一种就是通过关键字、图像抽取出的特征来选取 图片。再一种就是提供一张图像或者描述从数据库选出的图像应该具有什么样的 特征，从而与之相匹配。相关反馈是为了提供对查询结果正面的或负面的反馈， 从而系统可以改善搜索。 浙江大学硕十学位论文 图像搜索系统综述 图2 1 图像检索系统架构 特征描述 在基于内容的图像搜索系统中通常使用如下查询：颜色、纹理、形状、图层 等。以下是对它们的简要介绍： 颜色 颜色特征在图像检索和图像处理中最为常用，足因为颜色和图像中的物体和 背景密切相关，而且不依赖图像的尺寸和方向等因素。颜色直方图是在许多图像 检索系统中被广泛采用的颜色特征。它所描述的是不同色彩在整幅图像中所占的 比例，而并不关心每种色彩所处的空问位置，即无法描述图像中的对象或物体。 颜色直方图可以是基于不同的颜色空间和坐标系。最常用的颜色空间是r g b 颜 色空间，原斟在于大部分的数字图像都是用这种颜色空间表达的。然而，r g b 空间结构并不符合人们列颜色相似性的t 观判断。因此，有人提出了基于h s v 空间、l u v 空间和l a b 空间的颜色直方图，因为它们更接近于人们对颜色的主观 浙江大学硕十学位论文 图像搜索系统综述 认识。 纹理特征 纹理特征是一种不依赖于颜色或亮度的反映图像中同质现象的视觉特征。它 是所有物体表面共有的内在特性，例如云彩、树术、砖、织物等都有各自的纹理 特征。纹理特征包含了物体表面结构组织排列的重要信息以及它们与周围环境的 联系【1 3 】。正因为如此，纹理特征在基于内容的图像检索中得到了广泛的应用， 用户可以通过提交包含有某种纹理的图像来查找含有相似纹理的其他图像。 形状特征 物体和区域的形状是图像表达和图像检索中的另一重要的特征。不同于颜色 或纹理等底层特征，形状特征的表达必须以对图像中物体或区域的划分为基础。 由于当前的技术无法做到准确而鲁棒的自动图像分割，图像检索中的形状特征只 能用于某些特殊应用，在这些应用中图像包含的物体或区域可以直接获得。另一 方面，由于人们对物体形状的变换、旋转和缩放主观上不太敏感，合适的形状特 征必须满足对变换、旋转和缩放无关，这对形状相似度的计算也带来了难度。 通常来说，形状特征有两种表示方法，一种是轮廓特征的，一种是区域特征 的。前者只用到物体的外边界，而后者则关系到整个形状区域。这两类形状特征 的最典型方法分别是傅立叶描述符和形状无关矩。 系统示例 w e b s e e r 图像搜索系统 开发者芝加哥大学计算机系 1 2 】 特征从网络上收集蚓米的图片被提交至一系列的颜色测试来区分。有些简单的 测试得出图片有几种颜色、在一个给定的阈值n 下最频繁颜色的比率、跳转颜 色( 象素和它相邻点r g b 值的l 】距离最大) 大于闽值t 的比率、饱和度( r g b 颜色最大与最小之差) 人丁阈值t 的像素比率和图像维数的比率。一个更精细 的测试是，首先使用两个大的图片集：分别是图表和照片，构造图表的平均颜色 的直方图，j h ，以及一个照片的，。定义两个标准化的r g b 直方图a 利b 浙江人学硕十学位论文 图像搜索系统综述 的关系为：c ( 爿，b ) = 彳。，t b 。，t 。一副颜色柱状图为，的图片在测试中 j - 0r = o = 0 有值s = c ( h ，h ，) ( c ( e ，) + c ( z ，日。) ) 。两个类似的测试也使用最远邻近直 方图和饱和度直方图来代替颜色直方图。当图片被认为是照片时，就会使用基于 神经网络的人脸探测。关键字从图片的文件名、标注、超链接、说明文本和h t m l 题目中提取。 查询方式用户提交所需图像的关键字，或指定某些图像的特征，例如维度、文 件大小以及时照片或图画。如果用户查找人，他必须指定人脸的数量以及人像的 大小。 匹配为了区分一张图像是照片还是图片，颜色测试结合运用了多重决策树，并 使用了人工分类的一系列训练集。它们是二分树，树= 市点包含了下一个测试，以 确定图像应该提交，通过比较测试结果和阈值来调整指引检索的阈值大小。在每 个叶节点我们找到一个该图像是否照片的概率估计。从所有的决策树以类似方式 得到结果并与阈值比较，我们就可以作出这张图片归于哪个分类的决定了。 结果显示如果查找的人脸，那么结果将以人脸尺寸由大到小进行排列。否则， 找到的图片没有明确的排序规则进行返回。用户可以通过图像小图标上的页面按 钮来访问图像所在的网页。 2 - 2 _ 基于网页分割的图像分类系统 在很多情况下，网页不同块之问语义差别很大， 1 4 提出了基于网页块分割 的文本、链接结合算法。这个系统主要考虑提取同一个网页块内的图像以及其相 关的文本和链接信息，并利用这些信息对图像进行分类。一般来说，图像搜索引 擎返回的结果包含了多个主题。把这些结果根据语义聚合成不同的分类有利于用 户的浏览。通过使用基于视觉的页面分割算法( v i p s ：v i s i o n _ b a s e dp a g e s e g m e n t a t i o na l g o r i l h m ，如图2 2 所示) ，一个网页被分割成块，斟此文本和链接 信息可以被较准确的提取。使用块层次的链接分析，可以构造图像拓扑图。然后 使用谱聚类来找剑图像结构空间的欧氏内嵌空嵋j 。因此对于每张图像，它们使用 三种表示方式：视觉特征、文本特征和拓扑结构柬构成表示向量。使用谱聚类方 浙江大学硕士学位论文 幽像搜索系统综述 法处理这些向量，可以把所对应的图像聚成不同的语义块，从而达到分类浏览的 目的。 图2 2v i p s 网页分析系统 2 3 基于语义网络的图像搜索系统 在互联网上，图像周围有丰富的语义资源可供利用。 1 5 】提出了一个相关反 馈的架构，除了图像的底层特征，还利用图像的语义内容。通过形成一个在关键 字和图像之间的语义网络( 如图2 3 ) ，可以精确的把图像语义应用到检索中去。 图2 3 语义网络 在典型的搜索系统中有两科t 不同的用户交互模式。第一种，用户键入一串代 表所需图像语义的关键词。另外一种就是用户提交图像例子，然后检索系统把相 似的图像找出来。在很多图像检索系统中，这两种方法是互斥的。而结合它们可 浙江人学硕士学位论文图像搜索系统综述 以使它们优点互补从而得到更好的准确性和易用性。 结合了相关反馈和查询扩展的基于内容的检索架构，把基_ 丁_ ； 语义的索引及相 关反馈，和基于图像底层特征的向量无缝的结合起来。图2 4 显示了这个架构， 图2 5 是这个架构下的i f i n d 图像检索系统。通过语义网络和图像索引，它支持 使用关键词的查询和图像例子的查询。除了相关反馈，它还支持跨模态查询扩展。 通过关键词检索到的图像被作为正例，这样查询就被扩展到这些图像的特征上。 换句话说，系统从关键词查询转为底层特征查询，从而扩展了搜索域。对于基于 例子的查询，可以应用同样的方法扩展的语义空间。另外，相关反馈可以修正检 索条件，更新语义网络和相关性方法中的特征权重。 t 潦粕辩# 删kn 聪瓣b 赫d 咖# 讣7 i 目e f # d b k l 秘幽”q 口科，$ 耐_ 删i b h 妇b a 酬 o n u s 廿l e h h 蛳t “划b 腻k 图2 4 相关反馈下的检索模型 图2 5i f i n d 图像检索系统 囤 圈 浙江人学硕士学1 _ 7 = 论文 融合多线索的网页图像标注 第3 章融合多线索的图像标注算法 3 1 背景 在图像检索领域，一般认为用户倾向于在语义层次上判断检索结果的好坏。 这就是说，用户所认为的好结果必然是与用户查询在语义上( 而不是在其他方面) 高度相关的。因此，语义对于图像检索系统的性能至关重要。我们可以以语义为 线索将现有的各种图像检索方法进行分类。近年来的研究热点一基于内容的图像 检索方法 1 ，2 ，3 ，4 ，5 卜一试图采用自动获得的图像底层特征( 比如颜色直方图) 来“逼近”语义特征。然而，基于内容的检索方法的最大弱点就在于图像的底层 特征很难对应到高层语义特征上。因此，这种方法只能够获得视觉上近似于查询 ( 例子图像) 的结果，而无法获得语义上相关的结果。 关键字是用来表达高层语义概念的一种常用工具，因此基于关键字的图像检 索方法【6 的性能要大大优于基于内容的检索方法。比如根据r o d d e n 【1 6 】的测试 结果，人们在管理个人数字照片时最希望拥有的功能是根据照片上的文字描述进 行查询的功能。传统图像上的描述性关键字通常都是由人手工标注上去的，不但 耗费时间和人力，还有出现主观错误的可能。对于处于丰富语义环境的互联网图 像来说，实现自动标注既可以省时省力，又准确高效地实现图像索引。下面我们 将首先介绍基于内容的图像标注算法，它将图像分割成个个“语义块”从而和 1 定的语义项( 关键字) 联系起来。然后，我们根据网页图像的特性，介绍如何 从网页文本中提取关键字的算法。 3 - 2 _ 融合多线索的互联网图像标注 3 2 1 t a g 线索 刚页文本是一个结构文本 1 7 ，t m l 语义使用t a g ( 标签) 来组织结构，理 浙江大学硕士学位论文 融台多线索的网页图像标注 解这个结构有利于揭示对网页图像有价值的语义信息。下面是儿种出现在网页不 同位置的文本，他们给出了关于图像内容的语义提示，我们以重要程度的降低列 举如表3 1 。 表3 1 网页标签 标签说明 图像文件名文件名中包含了文件内容的重要线索。在很多情况下图像的完整的 u r l ( 比如“h t q p ：、例w 2 i n t e v r y 肌h u 鲈m 硅g e s ，m “l y n m m n 锄s g i f ) 比相对u r l ( 如“m m 一打a 1 1 s g 妒) 蕴涵更多的信息。在顶层目录的文件 名对索引图片非常有帮助。遗憾的是，由于人们很多时候采用缩写或 无关的名字来命名自己的文件夹，文件名很难被破译。 图像说明( c 印r 0 ) 通常，图片都有描述性的说明。虽然h n i l 没有对说明特别的标志， 但通常说明都是位于和图片同一个块或同一段落。 a l t 在h t i l 文档里，图片通常伴随着“a l t = ”的标志，用以在图片无法 下载时显示说明文本。这些说明文本很可能简短的描述了图片的内 容。例如，一个人照片的说明文本很可能时这个人的名字。而说明文 本也可能给出该图片用意的提示，例如一副可口可乐公司的广告图片 的说明文本就可能是“买可口可乐”。 h t m l 标题h t m l 文档的标题( 通常在浏览器的标题栏) 经常提供了包含图片的信 息。 超链接超链接的文本通常给出链接内容的提示。 其他文本 除了以上文本，其他在网页出现的文本也给了页面图片一定的语义提 示。但通常比上面的文本的相关性要弱。 由于图像说明( c 印，f o ”) 的缺失，超链接和其他文本噪音较犬，这些文本将 视作统1 文本作t f j d f 关键字判断( 超链接将继续用于进行链接结果分析以及 s r 的计算) 。而对其他几个类，可考虑采用权值来进行标定。设权值分别为：图 片文件名、al ir 、h t m l 标题一丑、其他占， f 丑 占。 则文档内某单词的权值彤= l f i 丑i j ( 单词f 取它【叮能的最大权值，比如 f 既出现在文件名中，也出现在a 1 t 中，则墩文件名的权值) 。不失一般性，我 浙江大学硕十学位论文融合多线索的网页图像标注 们对t 的权值作归一化处理： 瞅两2 击 慨6 ) 其中厅为当前文档。 3 2 2 r i 1 d f 线索 在实际应用中，由于h n 江l 网页的病念性，很多h t m l 网页并非以上述方 式给出图片的语义信息，与图片相关的文本组织比较混乱，但就整个文档而言， 我们同样可以在凌乱的结构中抽取关键信息，这就涉及到文本分类中的文本空间 模型和特征提取。在文本分类中，广泛使用向量空间模型( 阮c 抽r 劬卯 如出，) 来 标引文本。即文本的特征直接采用文本中的词条t ( 而妇n ) 作为特征项，文本可 以表示为特征的向量d = ( ，r ：，f 。) ，分量f ，是词条对应的权值。特征选择实质 上就是从特征集r = “，f ：，r 。) 中选择一个真子集r = n ，f ，) ，满足 ( 一cs ) 。其中，s 为原始特征集的大小，s 为选择后的特征集大小。选择的准 则是经特征选择后能有效提高文本准确率。选择没有改变原始特征空间的性质， 只是从原始特征空间中选择了一部分重要的特征，组成一个新的低维空间 1 8 ，1 9 ，2 0 ，2 1 。文本分类中，用于特征选择的统计量大致有：特征频度( 乃堋 m g 讹 掣) ，文档频度( d d c 删p 埘m g “p h 刚，特征熵( 抬r me m 叼秒) ，互信息 ( 胍埘2 觑白r m d f f d n ) ，信息增益( 知加，m 口，0 ”g 口f 胆) ，x 2 统计量( c 俦f 2 唧“阳) ，特 征权( 殄r 固旭呼 ) ，期望交叉熵( 却p c ，耐c m s s 勘，仰y ) ，文本证据权( 肫函胁d 西胁竹卯加r 乃x f ) ，几率比( 仇& 如r d 肋) 等。这些统计量从不同的角度度量特征对 分类所起的作用。本文主要结合使用特征频度( t f ) 和文档频度( d f ) 进行特征 提取，下面对这两个参量进行介绍，再介绍常用的t fj d f 参量。 - 特征频度( 抬m 砌g “蹦，t f ) 特征频度指训练集中特征屯出现的次数。这 是最简，户的特征选择方法。直观上，特征在文本集巾出现次数越多，对文本 分类的贡献越大。由于原始特征集中绝大部分是低频特征，凼此，没定t f 】3 浙江大学硕十学位论文 融合多线索的网页酬像标注 闽值对过滤低频特征非常有效，可以获得很大的降维度。就高频特征而言， 特征的统计分布决定了文本分类的准确率。即当该高频特征均匀地分布在所 有文本中时，对分类的作用将是有限的。因此，t f 主要用在文本标引时直接 删除某些低频特征 2 2 ，2 3 ，2 4 ，2 5 。 -文档频度( d o c “m p n f 肌g “8 n 纠，d f ) 文档频度是训l 练集中含有词条“的文 本数在总文本数中出现的概率。其理论假设为稀有词条或者对分类作用不 大，或者是噪声，可以被删除。文本频度较特征频度的统计粒度更粗一些， 在实际运用中有一定的效果 2 6 。但是如果某一稀有词条主要在某类文本中 出现的情况下，可能会把该类的显著特征错误地过滤掉。文献 2 6 通过实验 表明，用t f 和i d f 的组合进行特征选择可以得到更好的降维效果。 简言之，所谓t f i d f ，其中t f ( 死r m 肌g “e n ) 表示特征( 术语) 频率， 是单词在该文档中出现的频率，如果一个词对这篇文章特别重要，它必定会反复 的出现，因而会有较高的t f 值。但具有较高的t f 值的单词则不一定是文档的 关键词，例如某些词在很多文档里出现频率都很高，就不能成为对某文档辨谚 度 高的单词，因此，我们使用文档频度d f 来表征这种特性，据此引入逆文档频率 i d f ( 如v p 船ed o c “m p m g “册纠) 。i d f 是反映了训练文本中的词频，来体现单 词对个别文档的重要性。 目前存在多种t f i d f 公式，我们在系统中采用了一种比较普遍的t f i d f 公 式： 也耻羞舞器 慨7 ) 其中，彤n 。( ，d ) 为词f 在文本d 中的权重，而r 厂( ，j ) 为词f 在文本 d 中的词频，为训练文本的总数，为训练文本集中出现t 的文本数，分 母为归一化因子。 词的权值越大，证明该词越特别，在实际应用中我们把权值最大的几个荦 词作为浚文档的关键词。 浙江人学硕士学位论文融合多线索的网页图像标注 3 2 3 s r 线索 通常一个网页与它链接的网页在语义上是相关的，因此我们可以使用链接下 的文本作为参考文本，选取关键字。这旱我们使用艘值大小来确定关键字。 艘( s e m a l l t i cr a t i o ) 【2 7 】是一个基于链接文本来衡量单词在原文本重要性 的参量。与t f i d f 不同的是它只考虑了从当前文档出发的一个一层子图，它认 为网页上链接的文本与当前文本有很强的相关性。通常来说，一个网页上的超链 接( 特别是与图像在同一块结构的超链接或邻近的超链接) 对应的网页内容与本 网页的内容有很大的相关，而s r 算法( 公式3 8 ) 就是利用这种隐含的相关性 来挖掘文本中的关键字。 黜_ ) 5 商鬻蒜( 3 s ) 矿已q “p ，z c y ( ，z 聆彤( d + l 其中e g ”e ”钞( f ，孟) 表示词项t 在本文档五中的词频，p q 钾n 钞0 ，砌( 西) ) 表 示词项t 在当前网页孑的所有子层网页( 孑上有超链接到它的子层网页) 上的词 频。 利用公式3 8 ，我们计算词t 在文档d 中的权重为： 吲厕2 器 公式3 9 中的分母为归一划因子。 3 2 4 多线索融合标注 互联网图像位于一个结构性、网络化的文档中，因此考虑单词的重要性，我 们可以从该词在网页中所处的位置、出现的频率来衡量其重要程度。关于多线索 的融合方式，有线性融合和顺序融合两种。 - 线性融合 我们提出下面计算单涮在文档中权值的多线索线性融合公式： ( ，孑) = 口彬。( ，孑) + 阡0 o 百) + 圪o ，厅)( 3 1 0 ) 浙江大学硕 ：学位论文融合多线索的网页图像标注 其中单词f 在文档d 的重要程度由三个线索下的权重构成：t a g 权重 h ，l 口g ( r ，孑) ，t f i d f 权重咿( f ，孑) ，s r 权重岷，( f ，孑) ，口、y 是三个分量的 影响度。当计算好每个词项的权值后，选取一定数量( 如四个) 词项作为图像的 标注关键字。 - 顺序融合 顺序融合是按次序使用各种线索挑选关键字，通常我们首先应用标签信息缩 小候选关键字的范围，再应用t f i d f 和s r 值在候选集中进行筛选。 舍弃 舍弃 图3 1 多线索顺序融合流程图 t f i d f 、s r 闽值限制可以根据实验选定闽值，也可以简单的把词项进行排序， 选取前j l 个词项作为关键字。 浙江大学硕士学 ： 7 论文基于谱聚类的图像分类案日 第4 章基于谱聚类的图像分类算法 4 1 背景 由于自然语义的多义性，在实际应用中，用户提交的查询可能返回不同涵义 的图像。我们在b a i d u 图像搜索引擎( h 却：i m a g e b a i d u c o m ) 输入“苹果”这个 查询语句( 如图4 1 ) ，返回的结果可能是水果的图片，也可能是“苹果”电脑公 司相关的图片，而这些图片都杂乱的放在一起呈现给用户，显然对用户的阅读造 成很大的干扰。 图4 1 在百度图片搜索引擎搜索关键字“苹果”出现不同分类结果 在本章中，我们将介绍基于谱聚类( 涉及特征根分解的降维方法，如下文介 绍的m d s 降维方法) 的互联网图像分类算法，它通过挖掘网页语义来对图像进 行分类，当这种算法运用到图像搜索引擎中时( 如第五章我们实现的i s e a r c h ) ， 用户可以通过浏览分类文件夹来定位自己的目标图像集。如用户输入“苹果”关 键字，我们分类算法的目标是把苹果公司的图片和水果相关的图片分离开柬。目 前有很多图像分类算法是通过底层特a f 来实现( 用在“苹果”这个例子上可能有 较好的效果，因为至少从颜色特征卜可以把果树分离开来) ，但是在很多情况f ， 两张图片在颜色直方图上的差异和他们在语义 ：的差异是不能等同看待的。对于 互联网图片得天独厚的语义环境( 丰富的网页义本描述) ，我们采用向量化的网 浙江大学硕士学位论文基于谱聚类的图像分类索b 页文本来表征图像语义。然后应用降维方法和聚类方法对这些向量进行分类。下 文我们将分成三个小节论述分类算法的关键步骤：向量化、降维和聚类。 4 2 基于谱聚类的互联网图像分类 基于谱聚类的互联网图像分类算法主要包含两个算法：降维算法和聚类算 法。降维算法的输入是向量化文本的距离矩阵，而聚类算法的输入则是降维后的 向量坐标，这些概念将在下文详细论述。分类的大体过程是，我们首先需要把图 像表示成向量。然后利用m d s 算法得出向量在低维空间的坐标，即降维过程。 然后，利用聚类算法把降维后的向量进行分类。算法流程如图4 2 。 4 2 1 向量表示 图片附计算得距离矩 属文本到向量阵进行 向量化 间距离 + m d s 降 矩阵 维 得到降使用k 得到向 维后向甲均聚量对应 量坐标 + 娄算法 图片的 聚类分类 图4 2 基丁- 谱聚类削像分类算法 降 维 算 法 聚 类 算 法 在进行互联网图像分类时，小文主要采用文本特征来表示图像，而文本的来 源就是图像所在h t m l 页面的文字。这早需要重复下第三章已经提及过的文本 浙江大学硕十学位论文基于谱聚类的图像分类索日 向量空间模型( 例) 。向量空问模型的基本思想是以向量来表示文本： ( 彬，e ) ，其中彬为第，个特征项的权重，那么选取什么作为特征项昵， 一一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为特征项要优于 字和词组。这些特征词的选取需要依赖一个庞大的训练词库，即选用上万个分词 作为特征项。我们事先收集了近万份网页文本，将其分词后做成特征项集合。 要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作 为向量的维数来表示文本，最初的向量表示完全是0 、l 形式，即，如果文本中 出现了该词，那么文本向量的该维为1 ，否则为0 。这种方法无法体现这个词在 文本中的作用程度，所以逐渐0 、1 被更精确的词频代替，词频分为绝对词频和 相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一 化的词频，其计算方法主要运用t f i d f 公式，目前存在多种t f i d f 公式，我 们在系统中采用了一种比较普遍的t f i d f 公式： ( ，孑) ：t 辈窒些! 些坠型苇 国k r ( 瞄) x l o g ( q + o 0 1 ) j 2 其中，形( f ，孑) 为词f 在文本孑中的权重，而矿( f 囊) 为词 在文本孑中 的词频，为训练文本的总数，”，为训练文本集中出现f 的文本数，分母为归 一化因子。 文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇，然后 统计词频，最终表示为上面描述的向量。 当我们把文档向量化后，下文的m d s 方法需要文本向量间的距离矩阵来作 为输入参数，本文使用欧式距离来定义文档问距离。 d 。= ( 彬。一，) 2 + ( 彬：一，) 2 + + ( 阡一玎0 ) 2 ( 4 1 0 ) 其中文档f 表示为( 彬，形：，) ，文档，表示为( ，形p ，矿卅) 。 文档向量之间的距离有一个重要的应用就是用来衡量查询浯旬和数据库文 档的相似程度，这个可以作为直接检索的依据( 即把待索引文本与查询语句逐 计算距离，然后进行排序选择。这样作检索效率较差，本文i s e a r c h 系统通过查 询语句与文档关键字的直接匹配来索引数据库) ，另一个比较重要的应用是作为 返回结果排序的依据，即根据查询语句与返u 【文档的相似度来划文档进行排序。 浙江大学硕士学位论文 基丁谱聚类的图像分类索b 除了文档距离，我们也使用文档相似度来衡量两个文档之间的相似性，相似度的 定义如公式4 1 l 。 s i m ( d 。，d ，) 。 ( 4 1 1 ) 其中，z 、d ，为文本向量，硝为特征向量的维数，为向量的第厅维。 现实中很难确定查询语句的权重，一般把各个分词的权重取同一值。现在比 较好的做法是使用用户相关反馈，即调整查询语句的权重值。 相关反馈( r e l e v a l l c ef c e d b a c k ) 技术最早被应用于传统的文本检索( i r ) 领 域中。它是用户和检索系统之间的一个交互过程，具体是指系统根据用户对当前 检索结果的评价来调整用户的初始查询，从而优化检索结果的过程。最具代表性 的相关反馈方法是由r o c c h i o 提出的基于向量空间的反馈模型【2 8 】。在他的模型 中，无论是文档还是用户查询都可以表达位向量空间中的点，而相关反馈的本质 是将代表初始查询q 的点移动到靠近相关文档且远离无关文档的位置上。这种 方法可以用公式表示为： d 一，嗉p h 畴p ， 2 ， 其中。【、卢和y 是常量，d r 和d 分别代表相关文档和无关文档的集合，r 和 w 则分别是d 曰和d 中文档的数量。q 代表调整后的查询所对应的点。 r u i 和h u a n g 2 9 】最早开始将相关反馈技术运用于基于内容的图像检索。这以 后出现了很多用于图像检索的相关反馈算法。这些方法大多数都是基于向量空间 模型的，并且可以大致分成两类：查询点移动法和权重调整法。 查询点移动法的本质存于试图把查询点( 即查询在特征空间中的位置) 向相 关图像所在的位置靠近，同时远离无天图像所在的位置。人们希望通过这种方 法使查询点更接近人们真实的信息需求。这里常用的技术就是公式2 ，3 2 所示的 r o c c h i o 公式针对图像检索的一个变形，也就是d 尺和d 分别代表用户指定 浙江大学硕十学位论文 基于谱聚类的图像分类索； 的相关图像和无关图像的集合，而把所有的计算都放到图像特征空间中进行。 权重调整法的中心思想也很简单直观。比如图像检索系统m a r s 中实现了一 种基于标准方差的权重调整法【3 0 。由于每张图像都是由一个维的特征矢量所 描绘的，我们可以把图像看作维特征空间中的点。因此，如果所有相关例子 ( 图像) 在某坐标轴，上的方差很大，则说明图像的第，个特征和查询的相关度 较小，我们给此特征设定一个较小的权重。在m a r s 里，人们将第，个特征的 权重设为所有相关图象的第，个特征值的标准方差的倒数。最近还有人提出了计 算上更为复杂的全局优化方法。有i s l l i k a w a 等人提出的图像检索系统m i n d r e a d e r 【3 l 】把相关反馈构造成一个参数估计问题。和其他一些图像检索系统不同的是， m i n d r e a d e r 允许距离度量函数和坐标轴不平行，这就使它不仅能够为不同的轴 ( 所对应的特征) 加权，还考虑了轴( 不同特征) 之间的相关因素。r u i 和h u a n g 【3 2 】 在这种方法的基础上进行了改进。在他们提出的系统中，除了解决最优化问题外， 还能够处理多层次的图像特征。 4 2 2 降维算法 由于自然语言中存在大量的多义词、同义词现象，特征集无法生成一个最优 的特征空间对文本内容进行描述。特征抽取是将原始特征空间进行变换，重新生 成一个维数更小、各维之问更独立的特征空间。常见的降维方法分为线性降维 ( p c a 、i c a 、l p p 等) 以及非线性降维( m d s 、i s o m a p 、l l e 等) 。线性降维由于 假设原始数据在线性空间中，因此只能发现特征在线性子空间的结构关系，如果 高维空间存在非线性拓扑分布，它得到的降维结果不够真实，但是线性降维的优 点在于可以方便的扩展到非训练集数据上；非线性降维则可以反映高维空间的非 线性拓扑分布，但这种非线性特性只能定义于训练集卜，很难应用到非训练数据 中。由于本文的应用需要，我们不需要把降维结果扩展到非训练数据，而且为了 发掘向量空间的非线性拓扑关系，本文将关注非线性降维中的m d s ( 多维标度) 方法，这种方法也将应用到第h 章的分类器中。 m d s ( m u l t i d i m e n s i o n a ls c a l i n g ) 3 3 1 通过给出实体之问的儿何表示来获得它 浙江大学硕十学位论文基丁谱聚类的图像分类索g 们之间的内在结构关系。无论一对实体之间关系如何，都可以转换成一个相似度 量( 如前几节描述的文本向量之间相似度，链接特征之间的相似度等) ，m d s 难 是在这些相似度集合上的一个应用，它给出了实体集的空间表示。 我们使用符号p 。来表示实体f 和实体，之问的相似度。如果一个物体有两种 可觉察的颜色上的差异，并存在可度量的值( 0 表示“无区别”而1 0 表示“最 大的不同”) ，那么这个值可被认为是两种颜色相似度的度量。或者在变量i 和i 之间的相似系数也可认为是两个变量的相似度描述。然后，我们在几何空间描述 相似度，例如在欧式空间。在m 维欧式空间两点之间距离使用下式计算： 鼢训2 ( 4 1 9 ) 欧氏距离与相似度p 是可转换的：d f = 厂( n ) ( 假设几何模型与数据相符) 。 如果相似度是线性转换，那么，( 岛) = 口+ 6 ( 既) ，如果相似度表示的是两者之间 的近似性，那么系数b 是负值( 距离越大近似性越小) ，否则b 为正值。 在距离函数中的坐标，以及用来把相似度转化为距离的函数，都通过最小 化以下适合函数来获取( 常在m d s 文章中被称作s t r e s s 或s 函数) 。 ( 气 d ； ( 4 2 0 ) 这个方程考虑了现实中没有一个对数据非常适合的模型。因此值5 。在s 方程 中被引入，以实现从相似度所到距离d i 的最优逼近。 在m d s 中相似度一般直接表示成距离。然而，相似度矩阵p 应该事先被处理 已实现可度量。两种属性必须被保持：非退化和= 三角不等关系。 非退化表示对所有的f ，有d ，= o 。而三角不等表示对于所有的三点组( f ，j i ) 有d ，+ d * d ”。预处理好的矩阵标记为优可被证明 浙江大学硕士学位论文 基于谱聚类的图像分类索日 窆d ；窆d ；宝宝d ； 。 d ；一一+ 等= 一2 b ( 4 2 1 ) 。 。 石 。 j 是行索引，j 是列索引，n 是对象个数，所是维数。矩阵的内积为： b = 一圭 - 一去；t 。2 一一去“7 ( 4 z z ， 2ln jl n j 其巾i 是门力单位矩阵而j 是长度为月的单位向量。这个矩阵是对称和半正定 的。使用单值分解( s v d ) ，b = v a v ，我们可以定义b = x x l ，x = v ”。 特征向量是标准化的。保留前，个特征向量( r m ) 就得到了低维空间的解。 4 2 3 聚类算法 聚类的目标是将观测分割成类 3 4 】，使分到同一类的每对观测间的相异度趋 向于要比不同类中观测的相异度小。聚类算法分为三种类型组合算法、混合 建模和众数搜索。 聚类算法分类 组合算法：直接在观测上处理，不直接涉及潜在的概率模型。k 平均聚类算 法属于这种类型： 一混合建模：假定数据来自某一个概率密度函数描述的总体的独立同分布样 本。该密度函数由带参数的模型刻画，可以看作各个密度函数的混合，每个 支密度函数描述其中一个类。这个模型通过极大似然或对应的贝叶斯方法拟 合数据： 众数搜索( 凸点搜索) ：以一种非参数的观点，尝试直接估计概率密度函数 的不同众数。距离各个众数“最近”的观测定义一个单独的类。 相异度 相异度是两个数据点问距离的一个度量。若对象问第j 各属性值之间差异度 为d ，( x ，x ，) ，我们可以定义 浙江大学硕士学位论文 基于谱聚类的图像分类索 d ( 工，x ，) = d 廖f ，x ，) ( 4 2 3 ) = 】 为对象f 和对象f 之问的差异度。最常用的选择是平方距离： 办( x ”，x 。) = ( x 一x ，) 2 ( 4 2 4 ) 当然，其他选择也是可能的，并且可能导致不同的结果。对于非定量的属性 ( 比如，分型类数据) ，平方距离可能不适用。另外，可以对属性赋予不同的权 值。 k 平均聚类 该算法使用任意定义的相异度d ( x ，x ，) ，在最常见的形式中，每个类中心限 制为所指派类中的一个观测。我们没有必要显示地计算类中心，而只需要一直记 录下标f ：。算法如下： l 、对给定的类指派c ，找出类中的观测，它到该类其他点的总距离最小： 扣鬻嬲。蒹 ( 4 2 5 ) 则= x 。：，后= 1 ，2 ，k 是类中心的当前估计。 2 、给定类中心的当前集合协1 ，m 。 ，通过将每个观测指派到( 当前) 最近的 类中心 c ( f ) = a 增m i n d