利用分层语义索引进行大型图像检索 秋.docx

利用分层语义索引进行大型图像检索谭伟（21021096）July 31，2011概述本文解决相似的图像检索的问题，尤其是对于数以百万计至数十亿的大型图像数据集。核心的贡献是一种可以事先利用语义层次的知识的方法。当训练时语义的标签和有关它们的层次结构可用时，可的显着改善相似的艺术图像检索的实现。这样做的好处一方面能够使用更多的信息，经过实验一种特殊情况，没有提供额外的数据，当前状态的相似性学习的艺术中，表明新的方法仍然可以胜过OASIS6。利用分层的关系处理较大规模的问题是很重要的，因为可扩展性变得至关重要。我们建议的学习方法是底层并行化的，因此比以前的工作更容易扩展的。另外的一个贡献，是一种新型的hash方案（双线性概率向量的相似性，可以考虑层次），就是经Caltech256和更大的ImageNet数据集上进行实验能够降低检索的计算成本。简介如上图所示,结果表明，利用图像的层次关系，可以大大提高检索的准确性。随着数据集变得更大，层次化关系是变得越来越重要。获得最大的潜在利益要求对类采样时“密集”，必须细粒度的区分。为了处理如此大规模的数据，计算效率和可扩展性对有效地利用检索层次是一个关键方面。我们的方法演示了如何有效利用一个层次结构的形式图像的语义属性定义与人类先验知识结合。对于给定的语义属性，如马，狗，或风车，一个预定义的层次结构，可以让我们知道，一个含有马的图片与一个包含狗的比一个包含一个风车的会更类似。指定一个语义属性的层次结构是可行的，但直接利用低层次的特征点可能是相当困难的。目前的图像检索的过程中，我们的目标是学习一个函数，计算直接由低层次图像特征向量的相似性，并且不允许变量的相似性形成可编码的层次结构。我们的方法学习图像的语义属性，然后使用一个预先定义的比较函数 （从已知的层次结构的基础上产生 ）来获得相似性得分进行检索。学习识别语义属性可以很容易地进行并行化，使这种方法可伸缩性很好。这种方法需要语义属性标记的数据可能会有限，但在实践中，几乎每一个单一的实验数据上的相似性学习的相关工作带有标签，如在Caltech256的类别，或查询产生的图像，在OASIS 6 。此外，非覆盖的类别，它可以直接利用OASIS6，LMNN 33，MCML 15，和其他技术重建所使用的训练数据的类别标签。我们表明，在标签和一个层次结构是已知或标签可以推断出，但层次不提供时结果得到显着改善。然而，当标签是真的不可用，并不能推断，提出的技术不会是适当的或最优的。一旦确定了一个相似度函数，有效的利用检索层次结构的相似性查询最相似的数据库图像是下一个挑战。本文介绍的一种新的散列策略，提供了一个用于检索次线性时间解决方案，并形成了自身的普遍可用的组件。当与线性的输入数据和固有的并行化的语义分类的培训相结合，整个系统是非常的可扩展性。为了使这方面的具体，我们的语义索引结构建60万张图像在一个单一的CPU上消耗14天，或因为容易可并行性， 使用1000的CPU耗时20分钟以内。使用散列，检索生成的索引类似图像每次查询耗时3毫秒，同时准确性接近蛮力搜索的90，同时计算成本与蛮力搜索相比小于0.001倍。3利用层次信息来检索图像为了利用层次知识来检索，我们认为评估两幅图像之间的相似性的核心子程序Sim。大型数据库检索发现与查询图像相似性最大的图像组成。在以往的工作中，在检索系统建设的努力学习，从图像计算相似度值映射的低级图像特征的相似性功能。对于图像a，b，c，d，设f（）表示低级别的特征，然后再训练，可以考虑上成对的约束，例如，a和b是以上类似的c和d使Sim（f（ a），f（b） Sim（f（d），f（d）+1。OASIS6图像分为三份，a与b应该是更为相似，而不是到c到b，所以应有约束的Sim（f（a），f（b）项）Sim（f（a） ，f（C）+1。这些制约因素是用于学习矩阵L，使Sim（f（a），f（b）= f（a）L f（B）。正如图2所示，我们的方法计算图像相似性首先语义属性的估计概率S（f（a）。然后，我们使用语义的层次关系的先验知识的确定性计算分层相似矩阵S，和相似的特征是Sim（a，b）= s（f（a）T S s（f（b）。这不仅允许利用层次的知识，但只需要学习，建立语义属性模型一个过程，是比以前相似学习的方法更容易并行。3.1 利用语义相似性来编码层次性我们的方法的核心是使用语义属性的层次结构的先验知识，用于计算检索相似性。我们开始讨论这样一个相似的非概率的版本，并描述了一套二进制语义属性1K。属性可以对象类别（“是一只狗”），部分关系（“有一条腿”），可视化的描述（“是黑色”）或事实上任何有关图像的判定。我们将主要侧重于对象类的类属性的属性，因为它们是目前使用的和已被广泛研究的属性主导型，但是这种方法可扩展到任意的属性。两幅图像之间的相似性的属性，a和b可以再进行测量好自己的属性匹配。具体来说，让i（a）0，1的指标函数的图像有属性一我们定义的相似性为Sim *（A，B）= i,j（a）Sijj（b），这里SRK K并且SIJ之间的属性是一个i和J “匹配得分”，即语义事先人类知识为基础的相似性。我们这里S称为先验矩阵。这是一个非常一般的形式，并包含大量语义相似性的类型。对于对象类的属性，一个占主导地位的关系“是一个”关系，自然他们组织成一个语义层次结构。在这种情况下，S可以得到通过测量相对的层次类别。例如，让S（I，J）=（I，J），（I，J）是i和j最低的共同祖先类，（）：1KR是一些实值函数来非递减下降遍历层次结构，即最低的共同祖先的层次越低，类别i和j更相似。例如，“驴”是更类似于“马”而不是“键盘”，因为“驴”和“马”有一个较低的水平的共同祖先，相对于“马”与 “键盘”。可根据具体（）的节点的高度。因此，不是使用二进制的指标，我们描述一个图像是使用向量s（f（a）= xRK其中xi= Pr（i（a）=1|a ），即图像x含有属性i的概率。对于给定图像a，b和他们的概率向量x，y，我们重新定义了相似性，定义为非概率部分的期望，即Sim(a，b)= E Sim*(a,b)=i,jxiSijyj，或者干脆Sim（a，b）= xT Sy。这里假设图像a和b是独立绘制，这一般是对大多检索正确的。我们将把形式为xTSy相似性为双线性相似性。在学习层次结构时使用SVM来学习二类分类器为每个语义单独分类。然后将分类输出转化为概率。4.高效的散列只考虑对象类作为属性检索时，效率是一个大型检索重大挑战，可能会导致在一个几万尺寸的概率向量3。计算查询和每个数据库图像之间的相似性，因而变得代价很大。我们引进一种新技术，根据局部敏感哈希（LSH）实现次线性检索的时间来查找双线性相似性。关键是要构建一系列哈希函数H满足Pr hH（h（x）= h（y）= Sim（x，y）或Pr（h1（X）= h2（Y ）= Sim（x，y），h1和h2独立抽取的特征。对于一个查询点的y，检索数据库点，从h（Y）的箱子，并重新排名产生的最终结果。在实践中，人们可以连接多个哈希函数，以减少虚假的投票，并使用多个哈希表增加正确返回。对于我们的双线性相似函数Sim（x，y）= xT Sy其中x和y是概率向量，我们提供足够的条件，S和相应的生成函数，非正式的表示为：（1）如果S是每个元素非负，对称，对角占优，则存在一个构建函数（2）如果S是从一个层次结构从满足共享较低的共同祖先的类有较高的相似性派生，则存在一个构建函数（引理A.7） 。一个密切相关的现有技术是随机的超平面LSH 逼近余弦相似Sim（x，y）= (xT y)/(x y)来计算x和y之间的角度，与