英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
词汇树扩展模式识别
David Nistacute;er 和 Henrik Stewacute;enius
可视化与虚拟环境研究中心
肯塔基大学计算机科学系
http://www.vis.uky.edu/dnister/ http://www.vis.uky.edu/stewe/
摘要
本论文提出了一种能够有效应用到大量对象处理中的图像识别方案。经过对数据库中的40000张流行音乐CD封面的图像识别检测，本方法表现出了可信赖的效率和质量
该方案建立的基础是从本地区域中提取的索引描述量，其具有对图像背景杂波的封闭性和鲁棒性。局部区域描述量在词汇树中是按层次结构量子化。词汇树允许一个更大、更具差异性的词集被有效地利用。在我们的实验中显示，在该方案下得到的检索质量有大幅度的提高。这项方案中，最重要的属性是由树结构直接定义了词集容量。因此量化和索引技术是完全集成的，它们在本质上是相同的。
识别质量的评价通过对比标定的真实数据得到，通过在容量高达100万张的图像库中的进行检索，词汇树算法显示出其卓越的性能。
1.介绍
对象识别是计算机视觉领域的核心问题之一，这是一个被广泛研究的课题。由于图像的外观变化造成的影响，例如由非刚性变化、背景杂波、角度、方向、比例和照明条件引起的差异，因而这是很难处理的问题。
图1 具有三个分支因子、两个层次的词汇树形式图例。从图像中提取大量的椭圆区域并将之变形到的典型状态。从每个区域中计算得出一个描述向量。然后描述向量被词汇树分层量化。在第一个量化层中，描述符被分配给最近的三个绿色中心。在第二层中，它被分配给最临近的绿色中心的三个蓝色后代。词汇树的每个节点中都包含一个相关的倒排文件，它引用了包含该节点实例的图像。通过在词汇树的多个层次使用倒排文件，数据库中的图像会分层地进行评分。
对象识别中一个重要的挑战是构造方法缩放与图像数据库大小间的匹配，并保证能够在可接受的时间内对大量对象进行筛选。在本文中，我们提出了一个针对大量对象处理的方法。该方法属于目前非常流行一类对于图像局部区域描述量的方法，这些描述量是用于代表一幅图像的，从[1、 2、 8、 11、 15、 16、 18]这些局部区域中提取出来的。这类算法的优势是其封闭性和对背景杂波的天然鲁棒性。
本文最重要的贡献是提出了极其高效的索引检索机制。当前实现下的效用参考为，对 640 times; 480的视频，每帧画面的特征提取只需0.2秒，在一个容量为50000张的数据库中进行查询只需25ms。
2.方法及其与之前研究的联系
我们的工作很大程度上受到Sivic和Zisserman的鼓舞[17]。他们在一部电影中使用一种文本检索方法对一些镜头进行检索。从局部仿射不变区域中提取的描述量经过量化后成为视觉单词，是通过方法对训练图像中提取的描述符向量进行处理而得到的。使用术语频率逆文档频率 （）对视觉单词集进行评分，从而确定图像库图像与检索图像间的相关性。评分过程使用倒排文件来实现。
我们建议将视觉词汇集合构成一个词汇树的层次结构，来定义一种分层的TF-IDF得分。该方案将带来更高的视觉单词查找效率，并支持更大的词汇集。实验证明这可以让检索效果显著提升。其优点尤其在于，我们希望显示出高质量的检索结果，却不需要考虑框架内视觉单词集合的几何结构，虽然报告[17]中认为几何构造是至关重要的，但我们也发现在使用较小数量的词汇的情况下这样处理的确是无误的。我们将会集中展示在各几何构造的词集下检索的效果。为了将本方法扩展到大型数据库上，我们认为这是至关重要的。
识别质量是通过对同一对象或区域中标定的真实数据与数据库图像间的检索结果得到，但两者是在不同的视点、旋转度、范围和照明条件下进行的。这一测评显示出词汇树结构能够让我们实现明显好于先前方法的识别效果，无论是在质量和效率上都是如此。
更大词汇集的使用还显现出倒排文件方法的真正效果，这是通过减少数据库中必须被明确注意的图像数量来实现的。在[17]中，使用的是大约10000个视觉单词的词汇集。大约 每帧1000个视觉单词，这意味着在一次查询期间，约十分之一的数据库在被遍历，即使视觉单词在数据库中是均匀分布的。我们证明在词汇量较大时能获得更好的检索质量，甚至在达到1600 万叶子节点的词汇树中亦是如此。在这种容量的词汇集下，数据库中必须被明确识别的图像数量将会更少，从而可以得到较高的检索质量和效率。尤其是，我们在100万张图像的数据库中获得了次秒级的检索时间，而在[17]中，只在数千张图像的容量下进行了测试。我们使用分层的得分方式，也就是说，相比叶子结点，其他结点被认为是更重要的，但是图像附加到节点的倒排文件的数量受限于一个固定的数目，因此大的倒排文件处理代价更高，但在得分中只提供很小的熵。
通过使用方法，词汇树还提供了更有效的训练效果。在[17]中，使用了400张训练图，而在这里我们提升到了35000张，并且我们展示了当使用大型词汇集时，辨识质量的提升。
同时[17]中使用了一个脱机的爬虫过程来对视频进行索引，每帧至少需要10秒，测试报告显示，我们可以以同样的速度进行特征提取并向数据库中插入图像，即对于640 times; 480的分辨率大约有5 赫兹。这种在传输过程中将新对象插入到数据库的潜力，是将特征量化为视觉单词的结果，这种方式是一劳永逸，同时它仍然允许通常意义上的高性能检索。此功能是重要的，但却与以往的研究结果相当不同。我们计划将它用于基于影像式的位置和映射同步中，其中新位置需要在传输过程中实时添加。
几位作者已经展示了树能体现出图像当前局部索引区域的有效途径。例如Lepetit、Lagger和Fua[7]使用重新呈现的图像修补程序来训练索引要点，有点让我们想起局部性敏感哈希处理[6，3]的多重决策树。他们使用了像素强度的比率作为树的量度。与此相反的是，我们使用的是描述符向量与词汇树各个聚类中心间的相似度。他们的方法提供了非常快捷的在线操作。它侧重于对单个对象的检测，但该方案可能应用在更多的对象上。使用他们的方法，使以最佳方式对新对象进行训练需要 10-15 分钟，而他们最快的方法需要一分钟来训练一个新对象。我们使用脱机的无监督训练阶段来构建词汇树，而词汇树一旦构建完毕，新的图像即可在传输过程中插入到数据库。
Obdrzalek和Matas [14]使用决策树来索引特征点。他们使用像素量度，每个用于划分描述量的像素集大约处于各半的分布状态。他们已经用这种方法展现了大约 100 至 1000 个对象的在线识别。插入新对象需要离线训练决策树。
Lowe[9]在树上使用最优节点优先算法来寻找与查询描述符向量最接近的邻域。Lowe 展示了在图像库中包含约100000 关键点的描述量对应的结果，引用了数据库中约50幅训练图像的样本，每幅额定的稳定特征数量为2000。Lowe的方法已经被应用到了大约 5000 个对象的商业应用程序中，但我们无意以学术参考的方式来描述这些结果。
大多数情况下，上述方法在数据库中留存的数据量，是图像中图像块本身数量的多少决定的，或至少与局部描述量的数量相关。但是，对于在大型数据库中的检索效率而言，数据库的紧凑是非常重要的。用我们的词汇树方法，图像块只简单地表示为一个或两个整数，这与使用数以百计的字节数或浮点数用以表示描述向量产生了显著的对比。
紧凑也是我们的方法与Grauman和Darrell [5]使用的分层方法间最重要的区别。他们使用金字塔状直方图，每一层沿每条轴加倍容器数目，而不考虑数据的分布。通过使用与数据可能的分布相适应的词汇，我们可以使用一棵较小规模的树，同时又能够保持紧凑的表示，从而获得更好的分辨率。我们也做出估计，我们的方法在使用这个要素的条件下能够有1000倍的速度提升。
对于特征提取，我们使用我们自己实现的最大限度稳定极值区域方法() [10]。它们已经在全面的效果评测中，被证明有很好的表现 [13，4]。我们沿着每个分割区域扭曲椭圆块，使之成为一个圆形块。我们特征提取的剩余部分按照Lowe 提出的[9] 特征提取管道方法进行。我们发现规范化的方向是基于图像形成的梯度直方图。描述符的提取是与规范化的方向相联系的。在效用评定中描述符已经被发现是与众不同的[12]。然后归一化的描述符会用词汇树进行量化。最后，这个分层的评分方案将被用于从数据库中检索图像。
3.建立和使用词汇树
词汇树使用分层的聚类定义了一种分层的量化。在树的无监督训练中使用了一个大型代表性描述向量集。
并非是定义最终的群集数目或量化细胞，定义的是树的分支因子（每个节点的孩子节点数量）。首先，一个初始的过程运行于训练数据上，定义个聚类中心。然后训练数据被划分成组，其中每个组由接近特定群集中心的描述向量组成。
图2 构建词汇树的过程图例。分层量化在每一层定义个中心（在本例中=3）和它们的区域。
然后同样的过程被递归地调用于每组描述向量，通过将每个量化细胞拆分成个新的部分，从而递归地定义量化细胞。这棵树被一层一层地决定，直到层数的最大值，每次划分为个部分的过程，只由属于双亲量化单元的描述向量的分布来定义。过程如图 2 所示。
在线阶段，每个描述符向量只是简单地从树上传播下来，通过在每层将描述向量与个候选聚类中心相比较(由在树中的个孩子节点表示)，然后选择最接近的那个。这是一个简单的执行问题，在每一层执行次比较，从而总共有次比较，在不太大的情况下是非常有效的。树上从上至下的路径可以编码为一个单独的整数，然后就可以在得分中使用。
请注意树以一种集成的方式，直接定义了视觉词汇集和一种高效的搜索方式。这不同于以非层次形式定义视觉词汇集，然后制订近似的最近邻域搜索，以有效地寻找视觉单词。我们找到的无缝衔接选择更具吸引力，虽然后一种方法也定义了不同的情况，即量化细胞在原始空间中，是被连续地使用还是确定地使用。这种分层方式也给其后的评分过程以更大的灵活性。
虽然在非层次的结构方式中，增加词汇量的大小会使得计算的成本非常高，但是在分层方式中，叶子节点的数目与计算成本间是对数的关系。内存使用量与叶子节点数目是线性关系。描述向量的总数必须被表示为，对于用字符表示的-维描述符，树中的字符量大小可以近似地表示为字节。我们目前的实现，的一棵树，总共有1万个叶子节点，使用 143容量。
4.评分的定义
一旦词汇树量化完成，我们希望确定数据库图像与待查询图像间的相关性，我们可以通过确定数据库图像和查询图像的描述符对应的，它们各自在词汇树中下降路径的相似程度来得到结果。这种表示的图例已在图 3 中给出。这里还有无数种选项，我们也从经验的角度对大量变形形式进行了比较和筛选。
我们已经尝试过的大部分的方案，可以被认为是分配一个权重到词汇树中的每个节点上，这通常是基于熵，然后根据制定的权重定义查询向量集和数据库向量集，如
所示，和分别是查询图像和数据库图像的描述向量序号，即一条通过结点的路径，。然后一幅数据库图像被赋予一个相似度得分，基于查询图像和数据库图像向量集间的归一化差异︰
归一化可以以任何需要的标准进行，并用于实现数据库中有少量描述向量和多个描述向量的图像间的计分公平。我们已经发现 -标准给出了比更普遍的 -标准更好的结果。
图3 在分支因子为10的3层词汇树分布中，一张包含400个特征的图片表示。
在最简单的情况下，权重被设置为常量，但是检索的效果通过会更好，如果将熵的权重设置为：
其中是数据库中图像的数目，是图像库中有至少一个描述向量路径通过点的图像数。这产生了方案。我们也尝试了使用点的出现频率来代替，但看起来没有多大区别。
针对词汇树中不同层次的权重 可以以多种方式处理。直观地说，根据路径的上层节点来分配每个结点的熵似乎是正确的，但也许有点令人吃惊的是，我们发现根据树的根节点确定熵，而无视路径中点的相互依赖是更好的方案。这也说明，通过设置某些层次的权重为零，只使用最接近叶子结点的层次，从而屏蔽树中的某些层次是可能的。
我们发现影响检索质量最关键的要素是，一个大的词汇集（拥有大量的叶子节点），并且不要赋予词汇树中的内结点以过高的权重。原则上，词汇集的大小最终必然增长到太大，因此，描述向量中的变形和噪声会频繁地将描述向量们在不同的量化细胞间移动。在此的权衡必然是特殊性 (要求小的量化细胞和深的词汇树) 与重复性（要求大的量化细胞）之间。然而，分层评分的一个好处是，过度构造词汇集大小的风险被减弱了。而且，我们发现在词汇集大小的一个相当大的范围内 (在1和1600 万叶子节点之间的数目)，检索的性能随着叶子节点的增加而提升。这大概也解释了为何直接根据根节点分配熵值会更好。叶节结点确实比内部节点有用得多。
也可以使用禁止列表。当被设置为0号特征，作为最常见的或最不常见的特征。当时用倒排文件时，我们屏蔽长列表。这适用于特征们非常稠密地分布于列表中而不产生很多熵时。我们这样做主要是为了保持效率，但有时甚至会提升检索性能。[17]中提出了禁止列表，用以从相符的集合中移除错误匹配。然而在大多数情况下，我们不能通过使用禁止列表来提升检索质量。
5.评分的实现
为了在大型数据库中有效地评分，我们使用倒排文件。词汇树中的每个节点都与一个倒排文件关联。当一个特定的点出现时，倒排文件会存储图像的id号，以及每张图像的词频。转发文件也可以作为一种补充，来查找一幅特定图像中呈现的视觉单词。
只有叶子节点会在我们的实现中显式表示，因为内部节点的倒排
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[25440]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
