计算机视觉论文笔记三：核描述子在计算机视觉上的应用Kernel Descriptors for Visual Recognition

分手后的思念是犯贱 2022-05-27 12:59 164阅读 0赞

#  #

*  2010，nips

#  #

*  摘要

*  方向直方图的核观点等价于对image patchs计算特定种类的match kernel
 *  把像素的特征，团起来给patch
 *  这个特定种类有三种
 *  再把这个match kernel 用kernel principle component analysis(KPCA)压缩下维度，别那么大，成为我们的主角，核描述子
 *  优点就是核描述子易于设计，并且任何类型的像素级特征都能转化成核描述子

# Introduction #

要得到核描述子，分为如下三步：

1.  用像素特征设计match kernels
2.  通过kernel principle component analysis(KPCA)学习到压缩基础向量(compact basis vector)
3.  把无穷维度的特征向量映射到刚才提到的基础向量(basis vector)

手工特征不好提取因为图片的空间扰动，比方说正面侧面，有很强的结构性，并且完美的传说中的特征向量维度很高。

*  之前说的三种特征，本片论文是：梯度，颜色，形状的像素特征。
 *  最相关的工作是efficient match kernels，如果对于手工特征很感兴趣，可以看下论文

# 梯度直方图的核观点（要是着急可跳过 You jump, I jump,实际是skip） #

不讲故事，直接来。

*  什么是梯度直方图

像素z和他周围的像素颜色可能相同，可能不同，找个差别最大的连起来，这个向量，当作该像素点对于颜色的梯度（注意有大小有方向）。现在我取比方说3\*3块内的像素的颜色梯度，每个像素都去投票，比如说我把360度分成4块(orientation binning)，你的梯度在哪块，那个块就加一，这样把九个像素投好票，我就有一个直方图，横坐标是四，纵坐标加起来是九。简单粗暴，但是科学研究变量很多，比如说你可以把360度分成9块，比如说你可以取1600个像素，比如说你可以和离你4步远的像素计算梯度。所以我就是举个例子说明什么是梯度直方图。

*  再说说我们论文具体怎么表示

![70][]

*  **1 ** d维向量还有公式（1）怎么用呢，比方说你分成了四块，落在第一块(1,0,0,0)，落在第二块(0,1,0,0)，以此类推。
 *  **2**  公式（2）做了一个向量长度，模，magnitude二范数规格化。问题是所有的加起来不等于1，为什么不直接用sum(m\[z\])+constant，也就是一范数。Fh(P)举个例子(0.2,0.3,0.1,0.1).

这些是hard binning（360度分成四块四个bin），理解下，真正用的是soft binning。公式（3）开始

*  一种距离就是一种空间，比方说三维线性空间的二范数距离（二次方直线距离）也可以说是和空间的线性距离。
 *  **3**  现在衡量两个patch之间距离的公式就是公式（3），虽然是核函数，这个公式是可算的，就是实数乘法和向量内积，别害怕。
 *  从hard到soft只差一个公式一的距离

![70 1][]

ai是bin的中心

*  **4 ** 公式(4)怎么看:我们知道只有cos(-pi/2,pi/2)>0，所以梯度在bin中心左右直角范围内，都有值，越近越大，不过有个9次方，限制了方差。换句话说，对于一个梯度向量，只有他左右90度以内的bin有数值。

![70 2][]

现在，梳理下：

1.  像素梯度delta是二维的，长度是m
2.  patch向量是d维的，d大小等于bin的个数，改向量的模和像素梯度的模有关，不过被二范数规格化了，于是patch向量模为1
3.  两个patch的相似度用它们两个像素的核函数来计算，核函数计算方式就是公式(3)
4.  hard binning不如soft binning光滑，但是soft仍旧是离散的只改变了像素梯度向量，实际上还是90度以内的bin才有值。公式(3)求内积，hard会导致只要不在一个bin，数值就是0.soft好一些。

# 3  核描述子（别跳 You jump, I stay） #

##  ##

## 3.1  Gradient , color, and shape match kernels ##

在某个空间里，有特征的完美表达形式，它具有区分度，能让我们的识别率达到近似百分之百，可惜，找不着。但我们曲线救国。通过核。

简单说下核的概念：想算两个像素高维特征（传说中的）之间相似性，但是完美映射到高维空间这个映射函数（看图），我找不着，那我就不能提取这个高维特征。后来我发现，直接用低维空间特征比方说，像素颜色三维，整吧整吧，就得到高维空间的特征距离了。φ不好写。所以用f来表示高斯核函数。K(color(z),color(z'))=f(z)f(z').

![70 3][]

不过其实我想要的是单纯的f(z).但是得不到，所以只能退而求其次拉上个小伙伴。想知道更多可以看[这里][Link 1]。

###  ###

*  梯度match kernel

![70 4][]

###  ###

####  ####

*  位置核

衡量两个像素离得远近

> ![70 5][]  
> 
> 
> z是patch中规格化的位置，二维向量,ie (0.3,0.6)

###  ###

####  ####

*  梯度核

衡量两个像素的方向梯度相似度

![70 6][]

不知道theta(z)怎么求？看下图：

![70 7][]

这个方括号，是向量的意思，这也是个二维向量。先看(6)，我们用图说话：

![70 8][]

左图高中数学知识，你看，把theta加个z，表示是对z这个像素的数值，是不是就和我们的公式(6)一毛一样。公式(6)衡量了一个像素的方向orientation，那么两个像素之间的距离（蓝色向量长度）可以计算核函数了。

右图是local binary pattern.

注意到theta的模都被规格化成1了，向量规格化后，45度就不再是pi/4，(1,1), (2,2), 而是(sqrt(2),sqrt(2))了。所以务必规格化。

###  ###

####  ####

*  规格化梯度模核normalized linear kernel

衡量像素对patch的贡献，和之前的一样一样的。数值大，说明这两个像素的差异对于两个patch差异影响大。

###  ###

####  ####

*  颜色match kernel

![70 9][]

![70 10][]

以上这些都是可算的，没有上升到核函数的概念。下面将讨论核函数。但是本质上来讲只是为了说明合理性，或者是尽量具有说服力。所以领会精神就好。别害怕。

###  ###

*  local binary pattern match kernel（shape 形状）

反映了以像素z为中心，3\*3这块区域的形状，和像素z'为中心，3\*3这块区域形状的差异。常数s(z)提取自z周围的偏差，我觉得是方差。向量b(z)是一个八维向量(1,1,0,1,0,0,1,1).

![70 11][]

![70 12][]

![70 13][]

## 3.2  learning compact features ##

虽然我们已经表达出来两个patch相似性的度量方法：match kernel。但素鱿鱼计算代价昂贵，必须压缩下向量维度。公式(5)里面的展开成这样：

![70 14][]

不要害怕，这个公式是内积，就是不能算而已，领会精神，投影到传说中的高斯特征向量空间里的内积。

![70 15][]

公式(9)是拆出来的。从下面这个式子里，把patch P的部分单独拿出来，由于用了高斯核函数phi，fi，fai映射函数：

![70 16][]，

所以Fgrad(P)在无限维空间里。

![70 17][]左边是含有高斯核函数的向量内积，右边是常数，是我们熟悉的K（3.1）。

我们还是在和match kernel玩耍。只不过引入了核函数的概念。核函数要被我们表达成K，match kernel.

### 用有限维近似 ###

空间坐标基底这个线代知识没忘吧？把Fgrad(P)向坐标基底分解就好啦((3,3)=3\*(1,0)+3\*(0,1))。基用像素特征找。

![70 18][]

![70 19][]

这个basis vector是x的高斯核函数投影高维向量，不过我们用采样到的，规格化的梯度向量去拟合它。

虽然x是二维的，但我们不要这个二维的，我们要d维的。也就是用d个二维向量x去生成d维的向量k0，然后去拟合无限维度的高斯核函数。公式(10)就是这个从二维到d维的过程。

为什么不从无限维到d维，因为具体数据在二维，而无限维只是一个概念，为了说明合理性的模型。

### 把有限维的近似在进行压缩 ###

即使我们得到了大F，match kernel依旧是维度太高。

比方说，我们有256个shape(local binary pattern)的基向量(0,1,0,0,0,0,0,0)，假设一个grid是5\*5的，那么就是256\*5\*5=6400的维度，25指的是位置向量，25个格子，就有25种(0.4,0.4)(0.08,0.08)这样。密集的采样使我们得到了更全面更准确的无限维度近似，但不保证向量正交，也就是正交基，没有冗余。所以为了效率必须压缩。

![70 20][]

我们采用KPCA（kernel principal component analysis）核主成份分析。一句话概括就是：

向量alpha的所有元素利用线性组合a1得到一个常数作为新向量beta的一个元素，再利用线性组合a2得到一个元素，想要多少个元素，就用多少线性组合。线性组合系数的选取包含了你的目的，比如说pca是使数据散布的最开，差异最大，方差最大。

推荐一个讲得比较好的pca，kpca视频，只需要高中知识：需要科学上网，但是**中文讲解**

https://www.youtube.com/watch?v=G2NRnh7W4NQ&t=1s

![70 21][]

压缩好的向量中第t个数值，是之前其他向量元素的线性组合。

![70 22][]

所以我们的最终形式就是：

![70 23][]

[70]: /images/20220527/cc746ecba0014c8cbf4b0bf142d8bae1.png
[70 1]: /images/20220527/794ff5e0e99947869e235e5d63ab246c.png
[70 2]: /images/20220527/a6860cd0df72433ca8c250685c876520.png
[70 3]: /images/20220527/e1d52503bcd84243970e9ed6e882feb8.png
[Link 1]: https://blog.csdn.net/shijing_0214/article/details/51000845
[70 4]: /images/20220527/e0a29e38796149b0b68b6211516e06fa.png
[70 5]: /images/20220527/b449b397ad314d21b30a120a8db4e37c.png
[70 6]: /images/20220527/e39bb8f9b0e7464bb4e90ce318403263.png
[70 7]: /images/20220527/6a10cb4d8da74c9e832eb6ecc6be7e8f.png
[70 8]: /images/20220527/507d1579fe6b440d9ad1200c21239328.png
[70 9]: /images/20220527/e71aa12d84ed4512b3dd5d5bd68c5482.png
[70 10]: /images/20220527/a222cad1d48041f7aee15a9803c747d6.png
[70 11]: /images/20220527/1c6e3307ae604d53a4577dcd1b19cb31.png
[70 12]: /images/20220527/57bc45497b994be4af929c5c870a5422.png
[70 13]: /images/20220527/99360ab6ce664aa8a6d5b04f93fe6bf3.png
[70 14]: /images/20220527/78070e72e1f544998ade1571849a1d15.png
[70 15]: /images/20220527/08818c13c6b04267b2ee129ce3571e35.png
[70 16]: /images/20220527/49053d4a4f30495ab7339b0c97d1205c.png
[70 17]: /images/20220527/820edd5a10334017a9a6580c3065c02c.png
[70 18]: /images/20220527/bf2a5f10147642aab8e27a338ff64494.png
[70 19]: /images/20220527/d11838f775994f2cba5676327e74a420.png
[70 20]: /images/20220527/45713f61cfa44077a58e91ddc34da7a2.png
[70 21]: /images/20220527/4d22b96c2ff94c7081b610434cf77c11.png
[70 22]: /images/20220527/930a732887c2484ea445542d47b931c6.png
[70 23]: /images/20220527/1ee584c156bc4a0ea1bb94ddbf86799a.png