Kernel Descriptor in Depth

Reading time ~1 minute

Title Kernel Descriptors for Visual Recognition
Conference NIPS 2010
Author Liefeng Bo and Xiaofeng Ren and Dieter Fox

这是一篇2010年的老文章,从读博士开始,我就在follow他的工作,最近有朋友问题kernel descriptor的问题,并且由于最近想基于kernel descriptor做一点改进的工作,把他的论文和代码重读了一遍,主要是论文,在这里总结一下。

What is kernel?


简单来说,kernel就是一种内积的高级说法,而内积其实就是一种linear kernel,而常见的kernel还有polynomial kernel以及Gaussian kernel,显示如下:

  • polynomial kernel: \[ \mathbf{k}(x, z) = (<x, z>+1)^{\gamma}, \gamma\in Z^{+} \]
  • gaussian kernel: \[ \mathbf{k}(x, z) = \exp\left(-\dfrac{||x-z||^{2}}{2\sigma^{2}}\right), \sigma\in R-{0} \]
  • laplacian kernel: \[ \mathbf{k}(x, z) = \exp\left(-\dfrac{||x-z||}{\sigma}\right), \sigma \in R-{0} \]

首先回到最简单分类问题的开始,如果有两个sample point,label分别为\( (+1, -1) \),给定一个测试样本\( x^{t} \),如何确定它的标签。最简单的想法就是比较测试样本\( x^{t} \)和两个训练样本 \( x^{+}, x^{-} \)的相似性,赋予的标签和跟近似的训练样本一直。于是乎,相似性的问题浮出了水面,最传统的相似性度量包括或者。与其相关的研究被成为distance learning。但是,简单的度量方式往往只适合线性可分的情况,如下图右侧所示。那么kernel trick 完成的工作就是把低维的特征投影到高维。在下图中,投影的方程为:

Feature mapping
Feature mapping from low dimension to high dimension

经过这样的变换,本来一个线性不可分的问题变成了线性可分,而相似性的度量也更加准确。这里我们给出的是特征投影方程\( \phi: R^{2} \rightarrow R^{3} \),但是很多情况下,找出这样的特征投影方法是比较困难的。我们再次看一下通过观察投影过后特征的内积(相似性度量):

我们发现,可以控制内积的变换,在不知道的情况下,完成相似性的度量,而内积的变换方法就是核函数,又被称为kernel trick。简单总结一下kernel的几个特点:

  • 利用变换将特征空间投影到高维空间,又被称为Hilbert空间;
  • 尽量使得在内,问题线性可分,这也就是kernel SVM的基础知识;
  • 高维空间内的内积可以通过低维空间内的内积进行核函数操作求得,计算更快捷;
  • kernel function必须是有限半正定

 

Back to Kernel Descriptor


通过上面的总结,我们可以知道kernel在描述相似性方面的一些优点。现在我们需要回到计算机视觉里面传统的基于histogram的描述子(以及任何描述方法):SIFT, HoG以及BoVW(Bag of Visual Words)。在这三者之间,SIFT和HoG与Kernel Descriptor相关,而BoVW则与Liefeng Bo的另一篇文章Efficient Matching Kernel相关。其实这两个工作的思想方法是很相似的,简单总结就是传统的度量相似性的方法由于离散化的原因过于粗糙,而通过gaussian kernel可以更细致的描述相似性,但是与此同时带来了投影的特征空间无穷大的问题,于是用高维空间来近似无限维空间,而特征和高维空间基的相似性作为最终的kernel descriptor。

从基于histogram的描述方法说起,其实初衷就是为了更有效的描述不规则的离散分布的数值,将数值空间分为个histogram,统计每个histogram中的数值个数,而最终对这堆离散数据的表达则化为histogram。这就带来了第一个误差,也就是数据的近似。而当需要匹配两个特征描述子的时候,通常的做法也就是比较两个归一化histogram的距离。而论文中提出了从Kernel的视角看这个老问题的新方法,以gradient为例:

而误差就是出在上面公式的函数。举一个简答的例子,一个指向为和一个指向为的向量,经过histogram化之后,被分配到了两个不同的histogram,他们之间的相似性就消失了,但是简单的几何知识可以告诉我们,这两个角度其实是很接近的,而他们的相似性应该考虑其中。文章引入了来更细致的描述:

通过将简单的角度通过上式进行变化,我们可以更好的描述角度。而的相似性可以通过gaussian kernel来表达:

作者同样考虑了像素点在邻域内的位置,引入了另一个kernel:

最终的相似性比较用kernel表示为:

但是,kernel只能用来描述两个特征点之间的相似性,如何获得单个描述子就成为了另外一个问题。传统的做法是通过kernel function求得我们之前讨论的投影方程。然而这里的问题是,由于使用了高斯核,特征空间的分解将是无限维的,我们需要将无限维空间投影到有限维空间的基上。可以简单的理解为,将特征空间内的表述与有限空间内的基做内积。再将这个无限维的特征投影到又个基张成的空间内,完成了又无限维至有限维的转换。然而作者为了进一步压缩特征的维数,再一次使用了kernel PCA达到特征降维的目的,这一步应该是比较好理解的。

Kernel Descriptor给出了一个lower-level的特征描述,如何得到middle-level或者是higher-level的描述,常用的方法是BoVW以及Spatial Pyramid Matching。而在这篇论文中,作者使用了自己提出了EMK,思想方法也比较好理解,如果将来有机会再介绍一下。

Amazon Picking Challenge -- Perception Module

When we first designed the framework of perception module for Amazon Picking Challenge(APC), we tried to continue using our existing RGB-...… Continue reading