（信号与信息处理专业论文）基于局部特征的视觉上下文分析及其应用.pdf

摘 要 i 摘摘 要要 近十几年来，随着计算机技术和多媒体技术的迅猛发展、数码产品的普及以 及因特网应用的深入人心，网络上的多媒体数据呈现出爆炸式的增长。面对因特 网上的海量多媒体数据，特别是图像数据，如何对其进行有效分析、快速检索、 合理组织，是一项非常重要同时也是非常有挑战性的工作。视觉上下文分析研究 图像和特征的内在的联系，是解决这一问题的有效手段。最近，随着局部视觉特 征的提出，在计算机视觉和多媒体领域，越来越多的研究者开始关注基于局部特 征的视觉上下文分析的研究。 目前，基于局部特征的视觉上下文处理方法虽然取得了一定进展，然而由于 低层特征和高层语义概念之间语义鸿沟的存在， 视觉上下文分析还有很多问题需 要研究。本论文对基于局部特征的视觉上下文进行了深入研究，根据具体场景， 探索不同的上下文关系，分别应用用于图像重排序、典型图像挑选、部分拷贝图 像检索、自动车牌检测。本论文的主要工作和创新之处归纳为以下几点： （1）论文提出了一种隐视觉上下文学习方法，基于文本检索返回的图像结 果，针对其不相关性和冗余性问题，进行图像重排序和典型图像挑选。在隐视觉 上下文学习模型中，论文一方面发掘图像和视觉单词间的隐语义关系，另一方面 分别构建视觉单词和图像的链接图。通过利用图分析的方法，发掘视觉单词和图 像的重要性。基于图像的重要性，可以进一步和基于文本检索的图像排序结果相 融合，进行图像重排序。此外，在隐视觉上下文学习结果的基础上，论文提出了 一种加权集覆盖方法，用于挑选出代表性的典型图像。 （2）论文提出了一组基于局部视觉特征几何上下文的编码方法，包括空间 编码、环编码和几何编码，用于大规模的部分拷贝图像检索中的快速几何校验， 极大的提高了检索精度。 由于传统的单纯基于局部特征量化方法往往引入许多几 何不一致的匹配，影响图像间的相似度比较，降低检索精度。本论文基于经典的 局部特征 sift（lowe，2004） ，提出了一组编码方法对图像中视觉单词间的相对 几何位置关系进行简洁有效表达。 该编码表达可实现平移不变、 尺度不变、 或 （和） 旋转不变。基于几何上下文编码表达，论文提出了一种新颖的几何校验算法，可 以快速发现全局几何不一致的匹配。针对几何上下文编码可能存在的一些不足， 论文提出了一些增强策略，包括仿射变换估计增强、查询扩展增强等，可进一步 改善检索结果。 （3）论文提出了一种新颖的主视觉单词发现方法，针对车牌字符训练出一 组具有丰富几何上下文的视觉单词，用于自动车牌检测。针对传统的基于图像边 缘图的车牌检测方法的不足，论文从局部特征几何上下文的角度出发，提出了一 摘 要 ii 种新颖的主视觉单词生成的算法。 论文针对每个车牌字符训练得到一组主视觉单 词，这些主视觉单词含有丰富的几何信息，如尺度、主方向、相对位置、局部描 述子等；然后对测试图像，可以通过与其中的局部特征匹配的主视觉单词的几何 信息，准确估计出车牌的位置。该方法生成的主视觉单词具有很强的区分能力和 表达能力，而且和特定的语义概念（车牌字符）关联。 总而言之，本文基于局部视觉特征，从新颖独特的视角出发，分析和挖掘蕴 含在图像中的丰富的视觉上下文信息，应用于多媒体处理的几个场景。论文通过 大量充分的实验，证明了所提出方法优于传统的经典算法。 关键词：关键词：局部视觉特征 视觉上下文 图像重排序 典型图像挑选 几何校验 隐视觉上下文学习 几何编码 部分拷贝图像检索 车牌检测 abstract iii abstract with the fast development of computer and multimedia techniques, the popularity of digital devices and web applications, last decade has witnessed the explosive growth of multimedia data available on the web. how to manipulate the web-scale diverse data, especially image data, is a significant and also very a very challenging task. visual context analysis, focusing on the intrinsic replationships among images and visual features, lends itself as effective means to address that issue. recently, with the introduction of local visual features, many researchers from computer vision and multimedia community pay their attention to visual context analysis based on local features. although some advances have been made in visual context analysis，there are many issues to be addressed, due to the semantic gap between low level visual features and high level semantic concepts. in this paper, according to different applications, we study different kinds of visual context, and apply them to image re-ranking, canonical image selection, large-scale partial-dupliate image search and license plate detection, respectively. based on comprehensive research on visual context analysis, the contribution in this paper can be summarized as follows： firstly, we propose a new latent visual context learning scheme to address irrelevance and redundancy, which are two common prombles to text-query based image search. in the latent visual context learning framework, on one hand, we explore the latent semantic topics among images and visual words. on the other hand, we construct visual link graphs for visual words and images, respectively. with graph analysis techniques, we discover the importance of visual words and images. based on image importance, initial ranking of text-query based search results can also be fused for final image reranking. further, we propose a weighted set coverage algorithm for canonical image selection. secondly, we propose several conding schemes for geometric visual context representation, including spatial coding, ring coding, geometric square coding and gometric fan coding, which can be applied for fast geometric verification in large-scale partial-duplicate image retrieval. in traditional bag-of-visual-words model, local matches from feature quantization usually contain geometricly inconsistent ones, which will cast negative impact on retrieval precision. in our work, abstract iv we exploit the state-of-the-art sift features （lowe， 2004） for image representation, and propose several conding strategies to effectively describe the relative geometric positions of visual words. with the invariant virtue of sift features, our coding maps can achieve translation invariant, scale invariant, and/or rotation invariant. based on the geometric context coding, we propose an efficient geometric verification scheme to discover those globally geometric inconsistent matches. keeping only those geometric consistent matches, image similarity will be defined more accurately, which will benefit image retrieval accuracy. to further improve retrieval performance, some enhancements are proposed, including affine transformation estimation and query expansion. thirdly, we propose a novel scheme of principal visual word discovery for automatic detection of license plate. to address the drawback of traditional edge-map based methods， we propose to generate principal visual words from the perspective of geometric visual context of local features. a set of principal visual words with rich geometric context are trained for each license plate character. then, given a test image, based on the matching of local features to principal visual words, the location of potential license plate can be accurately estimated. the discovered principal visual words are both distinctive and descriptive. more importantly, they are related with some specific high level semetc context, i.e., plate characters, which is a significant contribution from the perspective of bridging semantic gap. to summarize, in this paper, based on local visual fetures, we explore and mine the diverse visual context from novel and distinctive perspectives for several applications in multimedia processing. comprehensive experiments on large-scale real datasets reveal the supreriority of the proposed alogorithms over state-of-the-art approaches with promising performance. key words：local visual features, visual context, image re-ranking, canonical image selection, latent visual context learning, geometric verification, geometric coding, partial-duplicate image search, license plate detection 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。 与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：_ 签字日期：_ 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一， 学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、 汇编学位论文。 本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 公开 保密（_年） 作者签名：_ 导师签名：_ 签字日期：_ 签字日期：_ 第 1 章 绪论 1 第第1 1章章 绪绪 论论 1.1 引言 近十几年来，随着计算机硬件存储和压缩技术的迅猛发展、数码产品的普及 以及因特网应用的深入人心，网络上的多媒体数据呈现出爆炸式的增长。面对因 特网上的海量多媒体数据，如何对其进行有效的管理，是一个非常有实际意义同 时也是非常有挑战性的工作。其中，在多媒体数据处理中，基于图像的应用，如 图像检索、目标检测等，正吸引着越来越多研究人员的关注。 图像是客观世界的二维投影。在计算机视觉中，我们常常面临的一个问题是 对某个或某类目标的图像进行比较，以发掘某些相关性，适应特定的应用场景。 由于图像往往格式多样、大小各异、成像背景条件不同，我们无法直接基于像素 进行图像比较，而应从图像中提取出视觉特征，用特征表达图像，将图像之间的 比较转化为特征间的比较。由于局部特征，如 sift（lowe 2004） ，具有旋转不 变、尺度不变、亮度不变等特性，基于局部特征的图像表达已被广泛应用于计算 机视觉和多媒体领域。 局部特征，如 sift，是一个高维矢量，其描述子高达 128 维。为了对图像 进行紧凑有效的表达，一般常定义一个视觉码本，然后将局部特征量化为一个或 若干个视觉单词， 从而可以将图像表示成一个标准长度的基于视觉码本的直方图 矢量（sivic 2003） 。而且，基于这种表达，将视觉单词类比于文本单词，甚至可 以借鉴文本信息检索中的一些方法，如 pagerank（brin and page 1998） ，lsa （deerwester et al. 1990） 。然而，由于视觉单词的二义性，其区分表达能力远不 如文本单词，视觉单词和高层概念间的鸿沟仍然无法逾越。 上述视觉码本的直方图表达是基于这样一个潜在假设， 即不同的视觉单词之 间是相互独立的，彼此没有关联。事实上，视觉单词之间，以及视觉单词和图像 /目标之间，在几何位置上和语义概念上存在着某种相关性，我们称这种相关性 为视觉上下文（visual context） 。一方面，不同于网页中文本单词的一维排列，视 觉单词在图像平面呈二维分布，对于某些物体的图像，其相应地拥有某些共生的 视觉单词，以特定的几何关系重复出现。我们称这种现象为几何上下文。另一方 面，当一组图像均和某个特定的语义概念相关，那么图像中的视觉单词或视觉单 词分布将反映着某种潜在的语义话题。我们称这种现象为语义上下文。几何上下 文和语义上下文是两种基本的视觉上下文， 它们对于处理视觉单词二义性问题具 有广阔的应用前景。然而，视觉上下文分析也面临着如下一些挑战： 第 1 章 绪论 2 首先，视觉单词一般基于局部特征生成，尽管局部特征具有良好的适应性， 比如可以实现旋转不变、尺度不变等，但是由于局部特征对很多物体的描述能力 有限，导致视觉单词对这些目标表达力不够，进而使得基于视觉单词的视觉上下 文分析难以施展拳脚。但是，对于具有局部特征可重复性的目标图像，视觉上下 文分析大有可为。 其次，视觉单词分布在二维图像平面上，来自于背景噪声的视觉单词往往混 杂其中。对于许多图像应用，有必要提取出与前景目标相关的视觉单词。对于一 类特定的目标，如何提取出共生的、可重复性好的视觉单词？如何对视觉单词的 二维几何关系进行简洁有效的描述， 以自适应地实现各种不变性？这些都是非常 有挑战性的问题。 第三，视觉单词的区分能力和表达能力远弱于文本单词。但是，当限定应用 场景时，对于一个高层语义概念，是否能够发现对应的以特定的视觉上下文关联 的一组视觉单词？如果可以的话， 这将具有从视觉单词向文本单词推进的里程碑 的意义。 本论文针对上述问题，从视觉上下文分析的思路出发，针对具体的应用，提 出了相应的解决方法。 1.2 国内外研究现状 本节主要对基于视觉单词上下文表达及其应用的研究现状进行概述。 对这些 背景的更为深入的讨论将在后续章节中给出。 本文主要关注的对象是视觉单词，视觉单词类比于信息检索中的文本单词， 一般是从视觉特征（lowe 2004; bay 2006; mikolajczyk and schmid 2002; matas et al. 2002）聚类生成得到（sivic 2003; nister 2006） 。由于视觉特征只是底层的描 述，决定了视觉单词难以对应确定的唯一的语义，这也正是视觉单词的二义性问 题。换句话说，相对于文本单词，视觉单词在区分能力和表达能力上难以望其项 背。通过发掘视觉单词的视觉上下文，则可以缩小这种差距。 视觉单词的视觉上下文主要包括两个方面：语义上下文和几何上下文。接下 来我们分别介绍这两种视觉上下文的相关工作。 尽管视觉单词和高层语义概念存在鸿沟问题，但是，当一组图像均来自于一 个具体的语义概念时，我们有可能发掘其内在的关联，基于隐含语义的指导，找 到视觉单词与图像间的相关性。基于 bag-of-visual-words (bow)，许多用于信息 检索的话题模型（topic model） ，如隐语义分析(lsa)（deerwester et al. 1990） ， 概率潜在语义分析(plsa)（hofmann 1999）和隐狄利克雷分析(lda)（blei et al. 第 1 章 绪论 3 2003）等，可用来分析图像中的语义主题。作为生成数据模型，plsa 和 lda 都是基于统计的分析，而且要求隐话题数目事先确定。与之不同的是，基于奇异 值分解的 lsa，隐式地探索高阶语义结构，而且不需要事先确定隐话题数目。 第二个重要的视觉上下文为几何上下文。与文本单词不同的是，视觉单词分 布在二维的图像平面，其几何关系对图像内容的表达和辨识至关重要。几何上下 文分析大致可以分为两类：预处理阶段的图像表达和后处理阶段的几何校验。下 面对这两类工作分别介绍。 第一类工作对视觉单词的统计上的几何关系进行建模， 以具有几何上下文的 直方图矢量对图像进行建模表达。一些工作试图发现共生的视觉单词，然后根据 其几何关系构造高阶的视觉单词，即视觉短语（visual phrase） 。liu et al.（2008） 提出基于 adaboosting（viola and jones 2001）选择特征，并提取出高阶的空间特 征用于目标分类。由于视觉单词数目众多，高阶视觉单词可能数目过多，特征选 择的作用尤为重要。 zhang et al. （2009） 提出基于 visualrank （jing and baluja 2008） 的思想，对视觉短语（二阶视觉单词）进行重排序，挑选出重要的视觉短语用于 图像检索、目标识别等。借鉴颜色相关图（color correlogram）的思想，视觉单 词相关图 （savarese 2006） 用于对视觉单词的空间关系进行建模以进行目标识别。 还有一些工作受 shape context（belongie 2002）启发，将局部特征的几何关系进 行编码表达。hoang et al.（2010）提出采用视觉实体的三角形关系来描述视觉单 词的空间布局，用于场景检索。最近，cao et al.（2010）提出了一种新颖的 spatial-bag-of-features 方法，对图像中的视觉单词进行直线投影和圆周投影，得 到一维直方图表达，并通过一些直方图操作，实现一定程度的平移不变、旋转不 变和尺度不变。由于视觉单词数量众多、图像多样、几何上下文关系复杂，基于 几何上下文建模的方法很难穷尽所有可能的情景，对于海量多媒体应用，比如图 像检索，这将是一个瓶颈问题。 第二类工作基于视觉单词表达，将几何上下文用于后处理的几何校验。这类 方法避开了几何上下文建模的问题， 对图像表达仍然是基于视觉单词的直方图表 达。几何上下文校验包含局部几何校验和全局几何校验。局部几何校验保证视觉 单词的局部邻域是几何一致或几何相似的。sivic and zisserman（2003）提出局 部空间一致性准则， 根据匹配的视觉单词在各自的图像中的位置确定离其最近的 一组视觉单词， 通过查看视觉单词邻域是否满足一定的匹配来判断原匹配是否有 效。 由于 mser （matas et al. 2002） 区域检测具有良好的可重复性， bunlded feature （wu 2009） 将 mser 区域里面的视觉单词 “捆绑” 在一起， 得到一组视觉单词， 以增强视觉单词的区分能力。其通过将 bunlded feature 之间的视觉单词匹配进 行投影，以判断其几何一致性。这种简单的处理在图像旋转时将失效。几何最小 第 1 章 绪论 4 哈希（geometric min-hash） （chum et al. 2009）根据局部的几何信息构造可重复 的哈希字，用于区分性更强的表达。 局部几何校验关注图像局部几何上下文的一致性，尽管计算效率高，但是由 于不能捕获图像中所有视觉单词间的上下文， 因此难以保证图像全局的几何一致 性，会引入一些错误匹配，从而降低了准确度。 为了捕获图像中所有特征的几何上下文，全局几何校验方法，如 ransac （fischler and bolles 1981；chum et al. 2004；philbin 2008） ，常常用于通过随机 采样匹配特征以估计最优的全局的仿射变换。ransac 可以在概率上保证全局 的几何一致性，可以获得更好的精度；但是由于其涉及到很多次的随机采样以进 行仿射估计，计算复杂度比较高。对于一些实时性要求高的应用，比如大规模的 图像检索，ransac 一般只用于处理初始排序靠前的候选图像。当图像数据库 的规模变得很大（如一百万以上）时，数据库中包含的与询问图像(query image) 相关的图像数目可能非常多。仅仅对排序靠前的候选图像进行完全几何验证，对 保证较好的检全率（recall)是不够的。我们期望通过有效地利用视觉单词的几何 关系，实现快速有效的全局几何校验。 1.3 本文的结构安排和创新点 基于上面几节的讨论， 本文对其中的几个关键问题进行了细致分析和深入研 究。本文主要关注视觉上下文关系，根据应用场景的不同，主要工作包含三个部 分： （1）隐视觉上下文学习； （2）基于几何上下文的几何编码； （3）主视觉单词 发现。我们首先在第 2 章介绍局部视觉特征的背景知识，然后分别介绍三部分工 作的具体内容和创新点，具体安排如下： 在第一部分工作中（第 3 章） ，隐视觉上下文学习针对基于文本检索返回的 一组图像进行重排序和典型图像挑选。我们借鉴文本检索中网页排序的 pagerank（brin and page，1998）的思想，利用图分析的方法，发掘视觉单词和 图像的重要性，进而对图像进行重排序并挑选出代表性的典型图像。首先，由于 所处理的图像中会有大部分图像和查询文本在内容上相关， 我们利用隐话题模型 对隐含在图像和视觉单词中的隐语义进行分析。此外，分别对视觉单词和图像建 立多层链接图，并施加局部几何约束，以类比视觉信息传递过程；构造图像和视 觉单词间的概率传递关系，分别定义视觉单词之间、图像之间的相关性，并采用 random walk 算法，得到其重要性。可根据其重要性对图像进行排序。而且，根 据图像对重要的视觉单词的覆盖程度，提出了一种加权集覆盖（weighted set coverage）的方法，迭代地挑选出典型代表性图像。 第 1 章 绪论 5 第二部分工作（第 4 章）着重研究图像中视觉单词间的相对几何位置关系表 达，用于大规模的部分拷贝（paritial-duplicate）图像检索中的快速几何校验。我 们采用经典的局部特征 sift（lowe 2004）对图像进行表达，并充分利用 sift 特征的鲁棒性（包括旋转不变、尺度不变、一定程度的亮度不变等） ，提出了一 组几何编码方法，包括空间编码（spatial coding） 、环编码（ring coding）和几何 编码 （含 geometric square coding 和 gometric fan coding） ， 实现对图像的视觉单词 进行简洁有效的几何描述，以适应于快速准确的几何校验。由于我们的方法具有 计算复杂度低、精度高的特点，因此，其在大规模的部分拷贝图像检索上具有广 阔的应用前景。 第三部分工作（第 5 章）基于车牌图像提出了一种有监督的具有丰富的几何 上下文的视觉码本生成方法。考虑到网络上的许多图像，如 google 街景，包含 一些私人汽车，为了保护汽车车牌这种隐私信息，有必要对其进行模糊。在模糊 前，我们需要对车牌进行准确的检测定位。基于这个应用场景，论文提出了一种 新颖的主视觉单词生成方法，对每个车牌字符生成一组含几何信息的视觉单词， 然后对新的测试图像，可以通过与其中的局部特征匹配的视觉单词的几何线索， 准确估计出车牌的位置。 我们的方法生成的主视觉单词具有很强的区分能力和表 达能力，而且和特定的语义概念（车牌字符）关联。从这个角度看，该工作对于 从视觉单词到语义单词的推进，具有重要的启发和指导意义。 最后，在第 6 章，我们对全文进行总结，并探讨未来工作展望。 第 2 章 局部视觉特征及其应用简介 7 第第2 2章章 局部局部视觉视觉特征特征简介简介 局部视觉特征是指图像中某些区域表现出的区别于其邻域的信号模式。 基于 局部视觉特征，可以方便地对图像进行比较和匹配，这也是许多计算机视觉应用 中的一个关键问题。局部特征一般应具备如下性质：可重复性可重复性（repeatability）即 图像发生几何或光照变化后特征仍可以重复检测到；显著性显著性（salicency）即每个 特征对应一个有区分性的显著的描述；紧凑型紧凑型（compactness）即特征的数目远 少于图像像素的数目； 局部性局部性 （locality） 即一个特征对应图像的一个很小的区域。 常用的局部视觉特征包括基于点的局部特征、基于区域的局部特征、基于边缘 （edge）的局部特征和基于线（line）的局部特征。在本章中，我们主要介绍与 本文最为相关的前面两种特征，分别从特征检测和特征描述进行讨论。 2.1 局部视觉特征检测 局部特征检测可以从角点（corner）和斑点（blob）两个方面着手。下面将 分别介绍常用的一些局部特征检测算子。 图图 2.1 图像及从中提取出来的块域（szeliski 2010）。 forstnerharris 角点检测角点检测 在计算机视觉中，我们常常碰到这样一个问题， 即对一组相关的图像， 如何寻找一些可靠的位置建立起关联？我们期望寻找什么 样的特征呢？为了回答这个问题，我们先看一个例子。如图 2.1 所示，我们从一 对相关的图像中分别提取出三个块域（patch） 。不难发现，无明显纹理结构的块 域几乎无法定位其在图像位置，而对比度（梯度）较大的块域则比较容易定位。 然而，当块域中只包含单一梯度方向的直线段，则会面临孔径问题（horn and 第 2 章 局部视觉特征及其应用简介 8 schunck 1981） 。特别地，如果块域包含两个显著的梯度方向时，则很容易对其 定位。 我们对上述讨论进行公式化表达，以寻求比较图像块域的匹配准则。例如， 给定两个比较图像 0 i和 1 i，定义其加权平方差和为： 2 21 )()()()(uxxxu ii pi iwssd iiwe （2.1） 其中，vu,u为偏移矢量，)( i w x为随空间变化的加权窗函数，p为图像 0 i中 的块域坐标矢量集合。 在进行特征检测时，我们并不需要逐个块域比较。我们只需要计算当发生微 小位置变化时，相对图像本身上述的测度的稳定性，即自相关函数： 2 00 )()()()(uxxxu ii pi iac iiwe （2.2） 不妨对图像函数进行泰勒展开uxxux)()()( 000iii iii，(lucas and kanade 1981)，可以对自相关函数近似如下： pi i t i pi i iii pi i ii pi iac a iw iiiw iiwe )( )()( )()()()( )()()()( 2 0 2 000 2 00 xuu uxx uxxxx uxxxu （2.3） 其中，)(,)( 00 0ii y i x i ixx 表示图像在 i x处的梯度矢量，自相关矩阵a为： 2 2 yyx yxx iii iii wa。 通过对a进行特征分解， 可以确定其作为局部特征点的稳定性。 设a的两个 特征值为 0 和 1 ，则根据 0 和 1 值的情况，可以判断区域稳定性。 forstner（1986）和 harris and stephens（1988）提出基于自相关矩阵a度量 的极大值，可以定位出关键点，用于稀疏特征匹配。事实上，上述的矩形块域可 以用一个高斯加权窗取代，实现检测子响应对于图像平面旋转具有不变性。采用 如下度量： 2 1010 2 )()trace()det(aa （2.4） 其中，06. 0。 harris 角点检测可实现旋转不变，但不能检测出尺度变化。 第 2 章 局部视觉特征及其应用简介 9 图图 2.2 基于图像高斯差分金字塔的尺度空间特征选择。 dog 斑点检测斑点检测 为了提取出同时在位置和尺度具有稳定性的特征， 可以在 包含尺度信息的图像金字塔上选取合适的关键点。 最早开展尺度选择研究工作的 是 lindeberg (1993; 1998b)， 其提出采用图像的拉普拉斯-高斯 （log: laplacian of gaussian）响应的极值确定感兴趣点位置。基于这个工作，lowe (2004)提出采用 difference of gaussian 来近似取代 log,以提高检测效率。由 g g 2 ， where 2 22 2 2 )( exp 2 1 ),( yx yxg （2.5） 可以看出，g 2 可通过 g 的有限差分近似得到。 设差分的相邻尺度分别为k和 ，于是 k kyxgkyxgg g ),(),( 2 （2.6） 因此 gkkyxgkyxg 22 ) 1(),(),( （2.7） 图像差分高斯金字塔的构造如图 2.2(a)所示，其中的极值则对应着感兴趣的 关键点。尺度空间特征点选择如图 2.2(b)所示，在图像差分高斯金字塔中的当前 和相邻的尺度中， 比较当前点值和其 26 邻域值， 如果当前点值为极小或极大值， 则被选择为关键点。 此外，为了实现旋转不变，lowe (2004)还提出估计关键点的主方向。可以 统计以关键点为中心、以尺度为参考半径的一个邻域里的梯度方向直方图，主方 第 2 章 局部视觉特征及其应用简介 10 向对应着直方图中最强的分量，如图 2.3 所示。 图图 2.3 sift 特征的主方向估计。 尺度和尺度和仿射仿射不变关键点检测不变关键点检测 除了尺度不变外， 在许多应用中如宽基线立 体匹配（wide baseline stereo matching），我们期望检测的特征具有仿射不变性。 我们要求仿射不变检测子在关键点位置不仅随尺度和旋转变化具有一致响应， 而 且对于仿射变换如透视收缩也具有一致响应。为了实现仿射不变，许多方法都提 出基于特征值分析，采用椭圆来拟合自相关矩阵或hessian矩阵，然后采用拟合 的主轴和比率作为仿射坐标系（lindeberg and garding 1997; baumberg 2000; mikolajczyk and schmid 2004; mikolajczyk, tuytelaars, schmid et al. 2005; tuytelaars and mikolajczyk 2007）。 mser 检测子检测子 最大稳定极值区域（mser: maximally stable extremal region）由matas, chum, urban et al. (2004)提出，也具有仿射不变性。mser是一 种基于图像局部对比度的块特征检测子（blob detector）。其采用不同的灰度阈 值对图像进行二值化，图像中的某些局部区域会在一系列的阈值二值化下，可保 持稳定的形状和大小，这些区域被视为极稳定区域。mser对于图像灰度的仿射 变化具有不变性，而且稳定性较好，可以用于检测不同精细程度的区域。 2.2 局部视觉特征描述 确定特征关键点后，我们需要对图像局部区域进行描述，提高对图像局部变 化的适应能力。在很多情况下，特征的局部外观可能会发生旋转、尺度变化，甚 至仿射变形。可以使用前面讨论的所提取的局部尺度、主方向或仿射变换，在提 取特征前，可以对图像局部块域进行重采样。在这些调整之后，不同图像块域的 梯 度 模 值 梯度方向 第 2 章 局部视觉特征及其应用简介 11 局部外观仍然可能有较大差异。局部特征描述子应对上述变化具有不变性，同时 还能够保有较好的区分性。接下来，我们将介绍常用的几种局部特征描述子。 尺度不变特征变换（尺度不变特征变换（sift） sift 的描述子是通过对关键点附近的 4*4 子区域的梯度方向直方图拼接得到的，每个直方图为 8 维，故描述子矢量为 128 维。实现时，在拼接直方图后，还会对其做归一化操作。这种处理使其不仅对通 用的线性光照模型具有不变性， 而且对复杂的光照变化亦具有一定的适应性。 图 2.2.5 给出了一个对关键点附近的 2*2 子区域分别生成梯度方向直方图的示例。 图图 2.4 sift 特征描述子矢量的生成。 （a） （b） 图图 2.5 surf 检测中的(a) 二阶差分算子近似和（b）积分图。 第 2 章 局部视觉特征及其应用简介 12 pca-sift 和和 surf 受 sift 描述子的启发，ke and sukthankar (2004)提 出了一种更简单的描述子方法，在一个 39 39 的块域（patch）上分别计算 x-和 y-方向上的梯度，得到一个 3042 维的特征矢量，然后采用主成分分析（pca） 的方法， 将其降到36维。 surf是sift的另一种变形， 采用箱式滤波器 （box filter） 对 sift 中的差分和积分算子进行近似，如图 2.5 所示。 图图 2.6 gloh 的图像块域划分（szeliski 2010）。 梯度位置梯度位置-主方向直方图（主方向直方图（gloh: gradient location-orientation histogram） gloh 也是 sift 的一种变形，其采用对数极坐标（log-polar）形式，对图像局 部块域进行划分（mikolajczyk and schmid 2005），如图 2.6 所示。gloh 采用三 种半径（6、11 和 15）以及 8 个方向构造对数极坐标划分得到 17 个子块域，然 后对每个小块域提取出梯度方向直方图，并进行拼接，得到一个 272 维的直方图 矢量，之后基于 pca 投影降维，得到一个 128 维矢量。 第 3 章 隐视觉上下文学习 13 第第3 3章章 隐视觉上下文学习隐视觉上下文学习 近些年来，基于视觉单词包（bag-of-visual-words）的图像表达已被广泛地 应用于计算机视觉和多媒体领域。视觉单词包定义一组视觉单词（visual words） 为一个视觉码本 （visual codebook） ， 而视觉单词一般是通过对大量的局部特征进 行聚类得到的。然后，任何一个新的图像，均可以表达为其所包含的视觉单词及 频数。给定一组图像，如通过文本检索得到的图像，每个图像的重要性是由其包 含的视觉单词的重要性决定的。在传统的方法中，视觉单词的重要性往往是基于 词频-倒排图像频率 （tf-iif: term frequency-inverted image frequency） 定义得到。 然而，tf-iif 方法并不能很好地刻画图像中内在的上下文关系。针对这个问题， 我们提出了一种新颖的隐视觉上下文学习（latent visual context learning）方法， 通过挖掘隐语义上下文和视觉链接图（link graph）分析，对图像和视觉单词中的 视觉上下文进行表达。利用隐视觉上下文学习，可以对不同的视觉单词的重要性 进行区分，以用于图像层面的应用，如图像重排序（image re-ranking）和典型图 像挑选（canonical image selection） 。 为了验证我们方法的有效性，我们通过文本查询，从 google 图像搜索获取 图像数据用于实验。实验结果表明，对比经典的算法，我们提出的隐视觉上下文 学习方法在图像重排序和典型图像挑选两个应用上， 具有更好的性能和应用潜力。 3.1 背景介绍 在过去的十年里，互联网上的图像数量迅猛增长，海量图像的处理分析面临 着巨大的挑战。目前，在许多商用搜索引擎中，如 bing，google 和 yahoo！等， 图像检索已成为一种非常受欢迎的服务。然而，大部分图像搜索引擎主要基于文 本信息。其部分原因是由于这样的事实，即文本搜索技术已经比较成熟，而图像 内容信息往往不好利用，或计算复杂度高。最近，一个纯粹的基于图像内容的商 业搜索引擎 tineye 吸引了越来越多的关注。目前 tineye 已索引近 20 亿幅图像， 并能提供实时的查询响应。然而，它约束很强，只能用于无旋转变化的部分拷贝 图像搜索。 对于基于文本的图像搜索，经常遇到的两个问题是相关性和多样性。由于忽 视了视觉内容信息，图像搜索引擎返回的初始结果的相关性往往难以令人满意， 如含有一些杂乱无关的噪声图像。为了解决这个问题，在多媒体领域，图像重排 序已经成为一个热门的研究课题。图像重排序的目标是，根据一致性的视觉的内 第 3 章 隐视觉上下文学习 14 容，优化基于文本的图像搜索引擎的结果，从而使得相关的图像被排到前面，而 无关的图像排到后面，从而得到更好的整体相关性。另一方面，虽然图像重排序 能提高基于文本查询的图像结果的相关性，但是图像冗余，如部分拷贝或内容比 较相似的图像，仍然很普遍。如果可以挑选出一组典型的代表性图像，使其能总 结概况图像集并压缩图像冗余，那么用户体验可以得到明显提高。 对于图像重排序和典型性图像挑选， 发现图像之间的语义关系是非常重