看完第二节，区看后面的代码

1. 写在前面的屁话。

最近的科研任务需要对HOG算法进行魔改，很自然的就需要来看一看算法，看一看代码了。
一开始网上down了一些代码，发现效果很差。分析了一下原因，发现他们都是根据作者论文直接复现的。然后没办法，把matlab中的代码调出来看了一下，果然，事情没有那么简单。

里面分别用了高斯滤波，三线性插值这两个骚操作，简直666.

讲道理，代码我看了两天，真的是没看懂，这也是因为我没有看原始论文的原因，为了图快，也是看了网上的博客，大家都是讲了大概，文章中的一些细节都没讲明白，其中最主要的一点就是，为什么要用三线性插值，怎么用三线性插值。
下面我就把这个做笔记写下来吧。

2. 三线性插值

-----通常将某个变量范围固定划分为几个区域进行某种计算时，由于边界变量与相邻区域也有相关性，如果只对当前区域进行计算而完全忽略与相邻区域的关系，就会产生区域混叠效应。这种混叠效应会在特征向量中产生突变。在这种情况下就需要采用插值算法对计算结果进行修正。在HOG特征提取方法中，位于不同cell交界处的像素如果只对所在的cell进行投影同样会对其他区域产生混叠效应，此时需要采用三维线性插值的方法对梯度向量直方图进行修正。
------插值运算在图像放大中应用较多， 这里借用插值运算的思想对累积直方图进行修正， 即将某个像素点的梯度幅值以不同的权重累加到相应的bin上。确切地说， 这是一种权值分配， 但多数文献和博客中仍然延续 “插值” 这一说法。由于提取HOG特征时需要在两个位置坐标(x, y)和一个方向坐标( θ )共三个维度上进行插值运算， 因此称为三线性插值。
------首先以二维情况为例说明线性插值的思想。在两个维度上进行线性插值称为“双线性插值”。双线性插值在图像放大或图像旋转中应用广泛，它是利用周围4个邻点的灰度值在两个方向上作线性内插以得到待采样点的灰度值，即根据待采样点与相邻点的距离确定相应的权值计算出待采样点的灰度值。如下图所示，点P为待采样点，Q11、Q12、Q21、Q22为点P的四个相邻点，用线性插值法对P点进行插值运算的数学表达式为：

----------------------------------------------------二维线性插值原理图

2.1 在梯度方向上进行线性插值

根据上述插值思想，可在各像素的梯度方向上进行加权运算，如下图所示，将区间[0°,180°]以20°为一个区间划分，每个小区间以中心角度作为直方图的中心数值，假设要对梯度方向为15°的像素点进行处理，显然15与以10和30为中心的直方图最近，应该将该点的梯度幅值加权累加到这两个直方图上，权重分别为(30-15)/20=0.75和(15-10)/20=0.25。

---------------------------------------对待处理像素点的梯度方向进行线性加权示意图
针对这个图，我简单解释一下。在HOG算法中，根据图像梯度方向范围，将其划分为无符号型（0，180°）或者有符号行（-180，180）。我是使用（0，180°）。这样的话，因为默认将角度分为9个方向，因此就事9个bin，每个bin带宽20°，即（0，20），（20，40），…,（160，180） ，因此，在bin中，梯度的每个方向的中心分别是：10，30，50，70，…,170.。

2.2 在像素位置上进行插值

同理运用线性插值方法在各个像素的位置上进行加权运算， 如下图所示， 左图中的方框处为待处理像素点， 它位于block中的C0单元中， 利用该点与四个cell中的中心像素点 （图中4个圆点） 的距离计算权值， 将待处理像素点的梯度幅值分别加权累加到C0、C1、 C2、 C3中相应的直方图上。

----------------------对待处理像素点的位置进行线性加权

2.3 在像素位置和像素梯度方向上进行三线性插值

综合考虑，在两个位置坐标(x,y)和一个方向坐标(θ)上进行三线性插值，关键要解决的问题是应该在哪些bin上进行加权累加，累加时权值又是多少。将一个像素点处的梯度幅值加权分配到4个cell中与该点梯度方向相邻的2个bin上（这边还需要对梯度幅进行高斯滤波）。按照下面公式修正直方图向量，其中x、y轴表征像素点的空间位置，z轴表征该点的梯度方向（即θ）。对于待处理像素点(x,y)，设其梯度幅值为ω，梯度方向为z，z1和z2分别是与之最邻近的两个bin的中点坐标。梯度直方图h沿x、y、z三个维度的直方图带宽分别为b=[bx,by,bz]，bx=by=8，bz=180°/9。如图6所示为三线性插值计算梯度方向直方图向量的示意图，左图中的方框处为待处理像素点，计算block的每个cell中与该点梯度方向相邻的2个bin，共计8个直方图柱上的权值，将该点的梯度幅值进行加权累加，即形成block中的梯度方向直方图[5]。

由于线性插值法考虑了待采样点周围直接邻点对待采样点的影响， 因此能够克服区域混叠的问题。

--------------------------------------三线性插值计算梯度方向直方图向量

3. 结合代码来分析

为什么要写代码呢，这是因为我们干看上面那8行代码会很懵逼，算法的魅力就在于能推出来公式，还能用代码把公式给实现了。

4. 参考文献

特此感谢
黄冬丽, 戴健文, 冯超, et al. HOG特征提取中的三线性插值算法[J]. 电脑知识与技术, 2012(31):7548-7551.