金字塔匹配核用图像特征集的判别分类

金字塔匹配核：用图像特征集的判别分类KristenGraumanandTrevorDarrell2005年摘要判别学习是具有挑战性的，当实例是特征集，且这些集合的基数是变化的并缺乏任何有意义的排序。基于内核的分类方法可以学习复杂的决策边界，但当输入是无序集时内核必须以某种方式解决对应关系——通常一个计算昂贵的任务对大型数据集来说变得不切实际。我们提出了一个新的快速核函数——将无序的特征集映射到多分辨率直方图，并在这个空间计算加权直方图交叉核。这种“金字塔匹配”的计算量与特征的数量是成线性关系的，它基于匹配首次出现的最精细分辨率的单元格隐式地找到对应关系。因为内核并没有penalize（惩罚，使处于不利地位）额外特征的存在，它对杂波具有鲁棒性。我们展示核函数是正定的，这使其在最优解决方案只能保证Mercer内核的学习算法中的应用是有效的。我们在目标识别任务中验证了我们的算法，并证明它是准确的比当前的一些方法更快。1.引言用于计算机视觉的各种表示包括无序的特征集或部分集，其中每个集合有不同的基数，并在每个集合中的特征之间的对应关系是未知的。例如，一个图像可能由一组检测到的局部仿射不变区域描述，一个形状可以由一组定义在每个边缘点的局部描述符描述，或一个人的脸可以由一组不同的面部部分块表示。在这种情况下，特征向量集代表一个特定感兴趣类别（对象，场景，形状，人脸等）的单一实例，并且人们期望特征的数目在不同的例子——由于视点变化，闭塞，或由兴趣算子的不一致检测——中是不同的。用这种表示来执行如分类或识别这样的学习任务是具有挑战性的。虽然生成方法已经取得了一些成功，但基于内核的识别方法以有效地表示复杂的决策边界和概括（generalizewell）未知数据[24，21]而著称。例如，支持向量机（SVM）是一种广泛使用的找出两类之间的最佳分离超平面的判别分类方法。核函数，衡量输入数据的相似性，向决策功能引入了非线性；内核非线性地将输入空间的两个实例映射到特征空间中的内积。然而，传统的基于核的算法被设计为固定长度的向量输入操作，其中每个输入向量对应于该实例的一个特定的全局属性；定义在的常用的通用内核（例如，高斯RBF，polynomial(多项式)）不适用于向量空间。图1.金字塔匹配核交叉直方图成金字塔状形成的局部特征，近似于特征集之间的最佳匹配。在这项工作中，我们提出了一个金字塔匹配核——定义在无序特征集合上的允许它们被有效并高效地应用在基于核的学习方法中的新的核函数。每一个特征集被映射到一个在最精细水平保留单个特征的特性的多分辨率直方图上。然后使用加权直方图相交计算来比较直方图金字塔，我们显示了在匹配对第一次出现的最精细分辨率的直方图单元里定义的隐式的对应关系（见图1）。通过金字塔匹配度量的相似性近似于不平等基数（unequalcardinality）的特征集之间的最佳对应度量的相似性（即，在较低的基数集合中的最佳匹配点的部分匹配近似于较大的基数集合中的点的一些子集，这样匹配点之间的总的相似性是最大的）。我们的核是非常有效的并且可以在与集合的基数成线性的时间内被计算。我们证明了我们的核函数是正定的，这意味着它适合于与保证只为正定核收敛到一种独特的优化（例如，支持向量机）的学习方法一起使用。因为它不penalize多余数据点的存在，我们所提出的核对杂波是鲁棒的。我们将表明，这转化为用不同背景或遮挡来处理未分割图像的能力。核还respect输入集所固有的共生关系：代替单独的集合中的匹配功能，忽略一个集合中由特征所传达的潜在的依赖关系，我们的相似性度量捕捉特征的联合统计。解决这个问题的其他方法已被提出[25，3，12，27，16，20，14]，但不幸的是，这些方法中的每一个都有以下缺点中的某一些：计算复杂度使大型特征集不可行；参数分布的限制可能无法充分描述数据；非正定（不保证对支持向量机唯一的解决方案）的内核；相同大小集合的限制；和不考虑特征集内的依赖关系。我们的方法解决了所有这些问题，产生了适用于在已经存在的任何基于核的学习范式中比较无序的，长度可变的特征集合的核。我们用目标识别任务证明了我们的算法，并显示其准确性比得上当前的方法，然而需要显著较少的计算时间。2.相关工作在本节中，我们将回顾基于特征集合的判别式分类的相关工作，采用内核和支持向量机进行识别及多分辨率图像表示。目标识别是一个具有挑战性的问题，需要来自一个分类器的强大的推广能力，以应对同一对象或对象类的图片的各种各样的光照，视角，闭塞，杂乱，类内外形和变形的发生。虽然研究者已显示出将支持向量机用于目标识别的有希望的结果，但他们通常使用全局图像特征——将图像作为一个整体的长度相等的特征，例如颜色或灰度直方图或原始像素数据的向量[5,1,17]。众所周知，这种全局表示对真实世界的成像条件，如闭塞，姿势的变化或图像的噪声是敏感的。最近的工作已经表明，局部特征不变的普通图像变换（例如，SIFT[13]）是用于识别的一个强大的表示，因为该特征可以在不同的视角，姿势，或照明条件下的同一对象或场景的实例中被可靠地检测和匹配。然而，大多数方法使用最近邻（例如，[1,8，22，2]）或基于投票分类器及随后的对准步骤（例如，[13，15]）的局部特征表示来进行识别；这两种方法可能对大型训练集来说是不切实际的，因为其分类时间随着训练实例数的增加而增加。另一方面，一个支持向量机确定训练示例的稀疏子集（支持向量）以描绘一个决策边界。基于核的学习算法，其中包括支持向量机，核PCA，或高斯处理已经成为可用于包括判别性分类，回归，密度估计，和聚类[21]的多种情况下完善的工具。最近，注意力已集中于开发专门的内核，它们可以在数据不能由欧几里得向量空间（如图，字符串或树）自然地表示时更充分地利用这些工具。一些研究人员已经设计了操作在无序特征集上的相似性度量。见表1对方法的简要比较。[25]的作者提出了在其他集合的每个特征最佳匹配特征的相似性中求平均值的核。在该核内的“最大”操作符的使用使它成为非默瑟核（即，不正定-见第3部分），因此在用于SVM时它缺乏收敛保证。[14]中给出的类似的核也考虑了所有可能的特征的匹配，但没有提出每对特征之间的相似性。[25]和[14]都有一个计算复杂性是在特征的数量二次。此外，无论是独立地匹配一组中的每个特征，忽略可能有用的同现信息。相比之下，我们的内核由它们同时匹配作为一组捕获的共现的功能的联合统计信息。表1：比较匹配无序集合的内核方法。每列展示每个方法的计算代价及是否内核可以捕获共现（C），是否正定（P），不假定一个参数模型（M），能否处理不相等基数的集合（U）。d是向量的维数，m是最大的集合基数，D是向量空间的直径。“金字塔”指的是所提出的内核。在[3]是根据给定的上找到使用贪婪启发式两组之间的次优匹配的方法;尽管这导致在非Mercer核，作者提供调整内核超参数以便限制给定的内核矩阵不是正定的概率的装置。[27]措施相似的作者在由两组'矢量元素跨越的两个线性子空间之间的主要角度而言。这个内核是仅正定为集相等的基数，并且其复杂性是在特征的数量的立方。在[20]，代数内核被用于通过基于矢量的内核给出相似性结合，与加权选择以反映功能是否在对准（订购）。当设置基数发生变化，输入被用零填充，以便形成大小相等的矩阵。在[12]，高斯拟合到每个组向量，然后两组之间的核心价值是其高斯分布之间的巴氏亲和力。正如作者指出，该方法被约束为以具有闭合形式解使用高斯模型。在实践中，在[12]的方法也限于套小基数，因为它的复杂性是在特征的数量的立方。同样的，[16]的作者适合高斯到功能设置，然后使用KL散度作为距离度量比较集。不像[12]和[16]的核，这是基于该假定的输入将适合某种形式的参数模型，我们的方法是无模型，并在表示保持不同的数据点。与无序集合数据处理时的另一种方法是，从每个类指定原型的例子，然后表示在它们的距离为每个原型的条款的示例;在欧氏空间向量处理标准算法是那么适用。[28]的作者建立手写数字这样的分类，并使用[1]作为相似的措施的形状内容的距离。面对这样一个基于原型的方法，这些问题是确定哪些例子将作为原型，选择多少应该有，并适当更新原型遇到新的数据类型时。我们的特征表示基于多分辨率直方图或“金字塔”，这是由分箱的数据点到越来越大尺寸的离散区域来计算。单级直方图已在各种视觉识别系统被使用，其中第一个是该[23]，其中，使用全球颜色直方图的相交进行比较的图像。金字塔已被证明是在各种各样的图像处理任务的有用表示-见摘要[9]。在[10]，多分辨率直方图与距离L1相比近似相等质量全局颜色直方图的对最近邻图像检索的最小代价匹配。这启发我们使用了点将台类似的表示。然而，与[10]，我们的方法生成一个判别分类器，并将其与加权相交，而不是L1比较直方图。我们的方法允许输入到具有不等基数并因此使部分的匹配，这是用于处理杂波和未分割的图像在实践中重要的。我们相信，我们的是提倡使用直方图金字塔作为形成在套明确判别功能，并且所述第一与分层加权直方图交集相似性测量使用时，以显示其为最佳局部匹配连接所述第一工作。3方法基于内核的学习算法[24，21]是建立在将数据嵌入到欧氏空间（n维空间）中的思想，然后在嵌入的数据中寻找线性关系。例如，一个SVM找到嵌入式空间（也被称为特征空间）中两个类之间的最优分类超平面。核函数K：XX用于在输入空间X中将数据点对的内积映射到嵌入空间F中，从而评估所有点之间的相似性并确定它们的相对位置。在嵌入式空间中寻求线性关系，但在输入空间中的决策边界仍然可能是非线性的，这取决于特征映射函数Φ：X→F的选择。这项工作的主要贡献是一种新的基于隐式对应的核函数，它能对无序、可变长度的向量集合判定类别。可以证明内核是正定。我们的算法的主要优点是它的效率，其使用遵守共同特征的联合统计的隐式对应关系，并对杂波或“多余的”数据点有抵抗性。我们的方法的基本思想是将特征集合映射到多分辨率直方图，然后将该直方图与加权直方图相交的措施以近似特征集合之间最佳局部匹配的相似性。我们称之为“金字塔匹配核”，因为输入集被转换为多分辨率直方图。3.1金字塔匹配核我们考虑一个包含d维特征向量集合的输入空间X，其边界是一个直径为D的球，其最小矢量间距离是2d：]},...,[],...,,...,{[|1111ffffxxmdmdxxX，（1）这里在X中的不同实例下mx是变化的。特征提取函数被定义为：)](),...,(),([)(01xHxHxHxL，（2）这里)(,,log2xHXxDLi是一个直方图向量用长度为2i的d维bins在数据x上形成的，的维度为diDrdi2。换句话说，是一个级联直方图向量，并且结果中每个分量直方图的bin是前一个的两倍。最精细直方图中的bin是足够小的使得来自集合X的每个d维数据点落入自己的bin中，然后bin的长度增加直到集合x中所有的数据点在L层落入单一的bin中。金字塔匹配核K基于隐式对应关系在多分辨率直方图空间中测量点集之间的相似性。两个输入集之间的相似性被定义为每级金字塔的特征匹配数的加权总和，匹配数由Ψ计算：LiiiNzyK0))(),((（3）)(xHi)(xH1这里表示在i层新的匹配对的数量。一个新的匹配被定义为在任何更精细分辨率水平下不匹配的一对特征。内核隐式地找到点集之间的对应关系，如果我们考虑一旦两个点落入同一bin里（从最精细的分辨率级别，其中每一点被保证有自己的bin）则认为这两个点匹配。匹配等价于一个层次化过程：在较高分辨率下不能对应的向量有可能在较低分辨率下是匹配的。例如，在图2中，在最精细分辨率下有两个点是匹配的，在中等规模分辨率下增加了两个新的匹配，在最粗略分辨率下又有一个新的匹配。K的输出值反映了匹配的整体相似性：在i层每一个新的匹配对贡献i，正比于在该层两个点的相似程度，由bin的大小确定。注意，公式（3）中的和从指数0i开始，因为Ψ的定义确保在层级1i处没有点的匹配