形变目标识别DPM论文《Object Detection with Discriminatively Trained Part Based Models》阅读笔记

DPM论文阅读笔记

        DPM（Deformable Parts Model）本质上是“整体HOG+组件HOG+SVM”进行目标识别，其识别效果非常好。但是在具体如何选择合适的训练集、剪切目标区域、合理设置参数等并不是很清楚。所谓“知其然，知其所以然”，所以决定研究一下DPM算法。

        我主要以《Object Detectionwith Discriminatively Trained Part Based Models》论文为主进行研究，写的东西并不会面面俱到，主要是对研究DPM有所帮助，分为三个重点：DPM整体框架（包括如何训练、如何检测）；核心的概念和算法（比如HOG特征、图像金字塔、SVM等）；我看Felzenswalb论文的理解，及其一些思考。这些可能是相互穿插的，希望能对后来研究者有所帮助。

        论文：《Object Detection with Discriminatively Trained Part Based Models》

        论文和代码下载地址：www.rossgirshick.info/latent/

 

一、DPM的31维特征

        设图像大小为M*N，Cell大小为k*k，则将图像分成([(M-1)/k]+1)*([(N-1)/k]+1)个互不相交个Cell，每个Cell对应31维的特征。读者可自行了解HOG特征是什么，这个写得很详细http://blog.****.net/zouxy09/article/details/7929348，主要就是先计算每个像素的梯度，然后将梯度按梯度值大小加权投影到梯度方向所在区间，一般按20度为一个区间，因为不考虑正负方向，所以一共180/20=9个区间。一般每个Cell只考虑单元内的8*8个像素，这样一个8*8的Cell就产生了9维特征向量。

      接下来就来看DPM每个Cell如何产生31维特征向量。

1、利用距离和方向线性插值产生9维HOG特征

图1 产生9维HOG特征流程图

        上述是每个Cell产生9维HOG特征的流程图，因为于每个Cell的梯度特征不仅与Cell内部的像素有关，还和相邻的Cell有关，所以用线性插值分配梯度：将每个像素的梯度根据影响分配到不同的Cell。

        另外梯度对应的梯度值不是全部分配到梯度方向所在的方向区间，同样还是按照影响按权分配到不同区间。

        上述两个线性插值具体可参见：

                http://blog.****.net/u011448029/article/details/11709443

                http://www.chongchonggou.com/g_855649192.html

 

2、归一截断得到Cell对应的36维特征向量

        已知C(i, j)表示第(i, j)个Cell的9维特征向量，下面是9个相邻的Cell及其梯度特征向量：

     定义，其中；

然后根据

得到第(i, j)个Cell对应的4*9=36维的特征向量。其中

3、PCA将36维降维至13维

        下图是36个主成分，前12个横条和竖条状的特征向量占据大部分，所以分别按行和按列求和，一共得到4+9=13维特征向量。

   

图2 36个4*9维特征向量

        注：这里要解释一下特征向量是条状和按行列求和的原因，是将这些特征向量作为基向量，给定4*9维特征向量投影到这些基向量就得到同样的结果。

        另外要吐槽的是：由9维HOG特征得到的4个9维特征向量，按定义本身就很相似，这样升维再降维似乎用处不大，可以试试不这样做的效果。

 

4、取有正负方向梯度，得到31-13=18维特征向量

        上述1、2、3操作是假设梯度无方向，考虑有方向的梯度，那每个Cell就有360/20=18维HOG特征，再由第2步得到4*18维特征，然后按行求和得到18维特征向量。注意此时不再进行列求和。故无向和有向一共31维向量。

 

5、整体示意图如下：

图3 DPM的31维特征向量提取流程图

6、整幅图像

         整幅图像划分为若干个Cell，得到featuremap。

 

二、图像金字塔及其在DPM中的应用

1、图像金字塔和尺度空间金字塔

        参考：http://www.cnblogs.com/ct1104/p/4480928.html

尺度空间金字塔参考博客：http://blog.****.net/abcjennifer/article/details/7639681

        图像金字塔：传统的就是直接平滑下采样，即像素越来越少。

        尺度空间金字塔：sift中提到，每层塔由降采样得到；每层塔之间的层由不同k*sigma高斯核卷积得到。

图4 尺度空间金字塔

    由图4可知，尺度空间金字塔与传统金字塔区别在于，每层塔还有不同尺度的高斯卷积核模糊。

 

2、DPM中的应用

        DPM应用的是传统的图像金字塔，每经过λ层分辨率降为1/2，所以下采样scale为s=2^1/λ。另外还增加一组上采样，后面root filter和part filter检测会用到。论文中第三章提到训练时λ取5，检测时取10。

图5 DPM图像金字塔

3）缺陷

        运用图像金字塔可检测不同尺度的目标，若训练集框较大，则训练出的模型较大，响应的目标区域较大。而图像金字塔是下采样过程，若图像中目标较大，可以在下采样层被响应；但是若图像中目标区域较小，则始终不能被响应。所以做了实验，给定图片，汽车过小，检测不到，但是对其上采样，目标可以被检测：

图6 原图，汽车较小，无法检测到

图7 对原图插值上采样，检测到了目标

 

三、检测

        检测比较简单，主要是“rootfilter响应+part filter响应+part位置偏移量”三部分得分相加，滑动按Cell为单位进行。另外需要结合图像金字塔去看，给定image pyramid第L层得到相应的feature map，root filter和该feature map做卷积；而part filter和第层feature map做卷积，所以part filter对应的feature map分辨率是root filter分辨率的两倍；root filter再遍历各层feature map（L>=1）。

        这篇博客写得比较清楚：http://blog.****.net/masibuaa/article/details/25990309

1、训练模型介绍

1）模型可视化结果

       DPM采用多模型，模型个数自己设定，为保证视角对称，所以一共偶数个；每个模型由6个固定组件组成。下图是汽车训练出来的3个不同角度一共6个模型，左图是整体模型（root filter）；中间图是6个部件滤波器（part filter）覆盖到左图对应位置的结果，其分辨率是root filter两倍；右图表示部件滤波器和根滤波器相对位置间的关系。

图8 模型可视化结果

2）模型参数和可视化关系

         

        详细可参见：http://blog.****.net/masibuaa/article/details/25990309

 

2、下图是对图像金字塔某层进行检测。

图9 featuremap响应流程图

3、注意多模型、多层feature map

         论文中是采用mixturemodel和图像金字塔，需要理解max与其关系。

 

四、训练

        给定训练集：正样本P={(I₁, B₁), …, (I_n, B_n) }，负样本是N={ J₁…, J_m}。其中I是图像，B是框住目标的box。希望训练出m个模型（论文如此，m可能与负样本个数的m混淆）。

        训练三个关键部分：初始化多个模型（由root filter和6个part filters组成），利用latent SVM训练参数（filters），以及data-mining hard examples。直接上算法流程图：

图10 训练流程图

 

1、初始化模型

        初始化模型主要确定了各个模型的root filter的大小、part filter大小和相对位置以及各自大致轮廓。

1）初始化多个模型的root filters

        作者首先将正样本用聚类的思想按box的长宽比（aspectratio）分成m类；

        然后对于每一类的正样本，选择较小的样本的平均大小作为root filter的尺寸（这样是为了保证大多数样本的box能覆盖root filter）；

        每一类正样本随机从框内选取与rootfilter相同大小的区域作为训练集（保证提取的特征向量维数与root filter相同），利用SVM训练出m个root filters。

2）Merging Components（即m个models）

        利用训练集P和N，将m个初始后的rootfilters合在一起，利用latent SVM（此时root filter的位置、在feature map的哪一层都是latent变量）训练这m个root filters。（此时暂不考虑part filters）

3）初始化各模型的part filters

        对给一个模型，用6个互不相交的矩形框，按high-energy和对称的思想尽可能覆盖rootfilter。用双线性插值将这些矩形框内的参数超分辨率到原来的两倍，得到初始化后的各part filters，其大小和相对part filters的位置也固定了。

         初始化汽车模型如下，可以看出基本有了汽车的轮廓了。

图11 初始化模型可视化结果

2、optimize the LatentSVM

        与普通线性SVM类似，只是增加一个latent变量，输出公式如下：

，即输出还与latent变量z（当前窗口在x相对位置、所在层数等）相关。

          对于训练集，需要满足不等式约束条件，利用外点罚函数，将求参转问题换为如下优化问题：

        最后利用随机梯度求解上述优化问题，梯度公式如下：

。

注：此处latent SVM只用到最简单的线性SVM，也为用到软边缘，而是直接用罚函数方法；求解未用对偶求解，而是直接用SGD求解。

3、data-mining hardexamples

        简单来说，在训练过程中，负样本集是动态变化的，针对当前样本集训练出参数；然后去掉负样本集中分类效果好的点，从N中随机取一些分类效果不好的样本添加到负样本集。（这里的负样本集是用窗口从N中扫描图像构成。）

        论文中有SVM和LSVM版本，本质上都是根据分类结果动态增加删除一些负样本点，具体算法如下：

图12 data-mininghard example算法

 

五、SVM及其在DPM中的应用

        论文中latent SVM关于参数的目标函数与常见的SVM不太相同，这里着重理清SVM的内在逻辑，并与论文中的形式进行比较，具体SVM算法可参见推荐的教材和网站。

1、带约束条件的最值问题及其求解

1）等式约束：拉格朗日求解

    问题：min f(x)，s.t c(x)=0

    转化为无约束求解：拉格朗日乘子法。

    从等高线解释：*

    从隐函数解释：http://math.fudan.edu.cn/math_anal/jiaoan/Lagrange.pdf

2）不等式约束

    有两种求解方法：转化为KKT求解；罚函数

   参考：《数值最优化方法》（北京大学出版社）

 

2、SVM

    参考：《数据挖掘导论》，写得条理清晰，通俗易懂。

    三个主线：线性可分、线性不可分（软边缘）、高维映射解决非线性问题

    求解：转化为对偶问题

 

3、DPM中应用

1）线性模型+外点罚函数

        论文中的latentSVM和常见的SVM不同，这里直接用最简单的线性模型+外点罚函数，没有用到核函数（因为特征向量的维数本身就很高了）、也没有用到软边缘；求解最优化问题直接用SGD，并没有转化为对偶问题求解。这两点需要注意，否则会和常见的SVM的形式对不上。

2）latent SVM

        与SVM相比关键是引入latent变量。

   

 

六、DPM使用注意事项

1、多模型

        由模型训练初始化可知，不同模型主要依赖于box尺寸而定，所以在对正样本进行box时，需要根据预先需要的模型数和可能的模型，决定box的尺寸。

        另外上次东南大学某位同学想法很有意思，是否可以直接用SVM训练多个目标模型，实现多类目标识别。

2、检测

        由检测过程可知，一旦rootfilter确定，其大小和方向等就确定了，待检测feature map区域与root filter做卷积，所以区域中的目标大小和轮廓必须与root filter相似，才能产生很高的响应，故DPM对旋转和尺寸检测效果不好。

1）尺寸检测

        由检测过程可知，图像金字塔是下采样，而rootfilter是遍历各层feature map，所以当场景中目标像素远小于root filter大小时，就无法检测到。

2）旋转

        旋转效果也不好，分析同上。取同样一张含car的图像，分别旋转0度、20度、60度，检测结果如下：

图13 原图

图14 旋转20度

图15 旋转60度