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 完成的工作就是把低维的特征投影到高维。在下图中，投影的方程为:

经过这样的变换，本来一个线性不可分的问题变成了线性可分，而相似性的度量也更加准确。这里我们给出的是特征投影方程\( \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，思想方法也比较好理解，如果将来有机会再介绍一下。