DPM(Deformable Parts Model)

目标检测方法

（1）基于cascade的目标检测

cascade的级联思想可以快速抛弃没有目标的平滑窗（sliding window）,因而大大提高了检测效率，但也不是没缺点，缺点就是它仅仅使用了很弱的特征，用它做分类的检测器也是弱分类器，仅仅比随机猜的要好一些，它的精度靠的是多个弱分类器来实行一票否决式推举（就是大家都检测是对的）来提高命中率，确定分类器的个数也是经验问题。这节就来说说改进的特征，尽量使得改进的特征可以检测任何物体，当然Deep Learning学习特征很有效，但今天还是按论文发表顺序来说下其他方法，（服务器还没配置好，现在还不能大批跑Deep Learning ）,。

（2）基于形变部件的目标检测

形变部件模型检测方法是现在除了深度学习之外的还相对不错的目标检测方法，先来看下为什么要使用形变部件，在下图1中，同一个人的不同姿态，试问用前面几节中的什么方法可以检测到这些不同姿态的人？阈值不行，广义霍夫变换行吗？人的姿态是变换无穷的，需要太多的模板。霍夫森林投票？貌似可以，但是霍夫森立的特征是图像块，只适用于一些形变不大的物体，当图像块内的形变很大时同样不太适用。那么ASM可以吗？想想也是和广义霍夫变换一样，需要太多的均值模板。归根结底就是我们没有很好的形状描述方法，没有好的特征。而Pedro几乎每发表一篇论文就改进一下形状描述的方法，最终由简单的表示方法到语法形式的表示方法，其演化过程可以在参考文献[4]中看出，参考文献[4]是Pedro的博士论文。

图1

1 思路

DPM是一个非常成功的目标检测算法，连续获得VOC（Visual Object Class）07,08,09年的检测冠军。目前已成为众多分类器、分割、人体姿态和行为分类的重要部分。DPM可以看做是HOG（Histogrrams of Oriented Gradients）的扩展，大体思路与HOG一致。先计算梯度方向直方图，然后用SVM（Surpport Vector Machine ）训练得到物体的梯度模型（Model）。有了这样的模板就可以直接用来分类了，简单理解就是模型和目标匹配。DPM只是在模型上做了很多改进工作。

上图是HOG论文中训练出来的人形模型。它是单模型，对直立的正面和背面人检测效果很好，较以前取得了重大的突破。也是目前为止最好的的特征（最近被CVPR20 13年的一篇论文 《Histograms of Sparse Codes for Object Detection》 超过了）。但是， 如果是侧面呢？所以自然我们会想到用多模型来做。DPM就使用了2个模型，主页上最新版本Versio5的程序使用了12个模型。

上图就是自行车的模型，左图为侧面看，右图为从正前方看。训练的时候只是给了一堆自行车的照片，没有标注是属于component 1，还是component 2.直接按照边界的长宽比，分为2半训练。这样肯定会有很多很多分错了的情况，训练出来的自然就失真了。不过没关系，论文里面只是把这两个Model当做初始值。重点就是作者用了多模型。

上图右边的两个模型各使用了6个子模型，白色矩形框出来的区域就是一个子模型。基本上见过自行车的人都知道这是自行车。之所以会比左边好辨识，是因为分错component类别的问题基本上解决了，还有就是图像分辨率是左边的两倍，这个就不细说，看论文。

有了多模型就能解决视角的问题了，还有个严重的问题，动物是动的，就算是没有生命的车也有很多款式，单单用一个Model，如果动物动一下，比如美女搔首弄姿，那模型和这个美女的匹配程度就低了很多。也就是说，我们的模型太死板了，不能适应物体的运动,特别是非刚性物体的运动。自然我们又能想到添加子模型，比如给手一个子模型，当手移动时，子模型能够检测到手的位置。把子模型和主模型的匹配程度综合起来，最简单的就是相加，那模型匹配程度不就提高了吗？还有个小细节，子模型肯定不能离主模型太远了，试想下假如手到身体的位置有两倍身高那么远，那这还是人吗？也许这是个检测是不是鬼的好主意。所以我们加入子模型与主模型的位置偏移作为Cost,也就是说综合得分要减去偏移Cost.本质上就是使用子模型和主模型的空间先验知识。

来一张合影。最右边就是我们的偏移Cost,圆圈中心自然就是子模型的理性位置，如果检测出来的子模型的位置恰好在此，那Cost就为0，在周边那就要减掉一定的值，偏离的越远减掉的值越大。

参考文献[1]、[2]、[3]分别讲述了如何利用形变模型描述物体（特征阶段）、如何利用形变部件来做检测（特征处理+分类阶段）、如何加速检测。文献[1]的形变部件。在Deformable Part Model中，通过描述每一部分和部分间的位置关系来表示物体（part+deformable configuration）。其实早在1973年，Part Model就已经在 “Therepresentation and matching of pictorial structures” 这篇文章中被提出了。

图2

         Part Model中，我们通过描述a collection of parts以及connection between parts来表示物体。图2表示经典的弹簧模型，物体的每一部分通过弹簧连接。我们定义一个energy function，该函数度量了两部分之和：每一部分的匹配程度，部分间连接的变化程度（可以想象为弹簧的形变量），与模型匹配最好的图像就是能使这个energy function最小的图片。

形式化表示中，我们可以用一无向图 G=(V,E) 来表示物体的模型，V={v1,…,vn} 代表n个部分，边 (vi,vj)∈E 代表两部分间的连接。物体的某个实例的configuration可以表示为 L=(l1,…,ln)，li 表示为 vi 的位置（可以简单的将图片的configuration理解为各部分的位置布局，实际configuration可以包含part的其他属性）。

给定一幅图像，用 mi(li) 来度量vi 被放置图片中的 li 位置时，与模板的不匹配程度；用 dij(li,lj) 度量 vi,vj 被分别放置在图片中的 li,lj位置时，模型的变化程度。因此，一副图像相对于模型的最优configuration，就是既能使每一部分匹配的好，又能使部分间的相对关系与模型尽可能的相符的那一个。同样的，模型也自然要描述这两部分。可以通过下面的（公式一）描述最优configuration：

公式1 

        优化公式1其实就是马尔科夫随机场中的经典问题求解，可以用上面说的BP算法求解。说的理论些就是最大化后验概率（MAP），因为从随机场中很容易转换到概率测度中（gibbs measure）,相关理论可以学习概率图模型（probabilistic graphical model）。识别的时候采用就是采用部件匹配，并且使得能量最小，这有点类似于ASM,但是ASM没有使用部件之间的关系，只是单纯的让各匹配点之间的代价和最小。匹配结果如图3所示：

图3

       上面的方法没有用到机器学习，另外部件的寻找也不是一件容易的事情，因为首先要大概预估部件的位置，因此这个方法也有缺点，但这个形变部件的思想可以用来作为特征，接着就来看下Pedro的第二篇文献[2]如何用它来做目标检测。

Pedro在文献[2]中基于形变模型的目标检测用到了三方面的知识：1.Hog Features 2.Part Model 3. Latent SVM。

1.      作者通过Hog特征模板来刻画每一部分，然后进行匹配。并且采用了金字塔，即在不同的分辨率上提取Hog特征。

2.      利用上段提出的Part Model。在进行object detection时，detect window的得分等于part的匹配得分减去模型变化的花费。

3.      在训练模型时，需要训练得到每一个part的Hog模板，以及衡量part位置分布cost的参数。文章中提出了Latent SVM方法，将deformable part model的学习问题转换为一个分类问题。利用SVM学习，将part的位置分布作为latent values，模型的参数转化为SVM的分割超平面。具体实现中，作者采用了迭代计算的方法，不断地更新模型。

针对上面三条，发现难题如下：

1）部件从何而来？

2）如何用部件做检测？

在基于部件做目标检测之前，PASCAL VOC 2006年Dalal-Triggs的方法是直接用HOG作为特征，然后直接基于不同尺度的滑动窗口做判别，像一个滤波器，靠这个滤波器赢得短时的荣誉，但不能抗大形变的目标。

Pedro改进了Dalal-Triggs的方法，他计算作为一个得分，其中beta是滤波器，phi(x)是特征向量。通过滤波器找到一个根（root）部件p0，根部件有专门的滤波器，另外还有一系列非根部件（parts）p1…pn,然后把他们组成一个星形结构（此时回顾图1的形变模型思想）。

每个部件用

来表示，其中X,Y是坐标，L表示金字塔级别。当这个星形结构的匹配得分减去模型变化的代价得到最终分最高时，就完成了匹配，如公式2所示：

公式2

        其中F’表示滤波器的向量化表示,b是偏移项，H表示特征金字塔。

现在假设滤波器解决了部件，完成了匹配，解答了第二个疑问，但是滤波器从何而来，简单的说就是这个滤波器的权重beta是多少？

现在不知道部件，也不知道滤波器，没有滤波器就没有部件，没有部件也求不出滤波器的参数，这就是典型的EM算法要解决的事情，但是作者没有使用EM算法，而是使用隐SVM（Latent SVM）的方法，隐变量其实就是类似统计中的因子分析，在这里就是找到潜在部件。

在训练的时候对部分部件进行打标签，用他们求beta,然后用beta再来找潜在部件，因此使用coordinatedescent迭代求解，再一次遇到这个求解方法。有了部件和打分，就是寻找根部件和其他部件的结合匹配最优问题，可以使用动态规划，但很慢，具体请参考文献[2]。

2.检测

检测过程比较简单：

综合得分：

是rootfilter (我前面称之为主模型)的得分，或者说是匹配程度，本质就是

和

的卷积，后面的partfilter也是如此。中间是n个partfilter（前面称之为子模型）的得分。

是为了component之间对齐而设的rootoffset.

 为rootfilter的left-top位置在root feature map中的坐标，

为第

个partfilter映射到part feature map中的坐标。

是因为part feature map的分辨率是root feature map的两倍，

为相对于rootfilter left-top 的偏移。

 的得分如下：

上式是在patfilter理想位置

,即anchor position的一定范围内，寻找一个综合匹配和形变最优的位置。

为偏移向量，

为偏移向量

，

为偏移的Cost权值。比如

则

即为最普遍的欧氏距离。这一步称为距离变换，即下图中的transformed response。这部分的主要程序有train.m、featpyramid.m、dt.cc.

       在文献[2]中虽然使用了金字塔来加速搜寻速度，但是对星形结构组合的搜索匹配计算量也很大，检测速度稍慢。

因此接着来看第三篇文献[3],文献[3]就是加速检测过程，对于星形结构模型采用cascade来判断，来快速抛去没有有效信息的part，其实实际中根部件的位置对匹配起着很大作用，然后依次对其他部件（n+1）,有了这种关系，取一些部件子集后我们可以采用cascade来修剪、抛去一些不是好配置的部件组合（官方用语叫配置），这样一些在弱分类器中评分高的组合进入更一步的判断，类似于cascade的级联思想，但是要注意形变模型的每个部件应该是相关的，而不应该像上节那样harr-like特征之间独立,依次判断在这里行不通，这里其实是个子序列匹配问题,文献[7]提出过一种解决方法，pedro又改进了此方法，在原来n+1个部件的基础上增加n+1可以快速计算的简单部件，这样打乱之后，子序列匹配的代价就小了一些。

下面正式进入检测流程，看看怎么来加速的，大概流程如图4所示：

图4

3.训练

3.1多示例学习（Multiple-instance learning）

3.1.1 MI-SVM

一般机器学习算法，每一个训练样本都需要类别标号（对于二分类：1/-1）。实际上那样的数据其实已经经过了抽象，实际的数据要获得这样的标号还是很难，图像就是个典型。还有就是数据标记的工作量太大，我们想偷懒了，所以多只是给了正负样本集。负样本集里面的样本都是负的，但是正样本里面的样本不一定都是正的，但是至少有一个样本是正的。比如检测人的问题，一张天空的照片就可以是一个负样本集；一张某某自拍照就是一个正样本集（你可以在N个区域取N个样本，但是只有部分是有人的正样本）。这样正样本的类别就很不明确，传统的方法就没法训练。

疑问来了，图像的不是有标注吗？有标注就应该有类别标号啊?这是因为图片是人标的，数据量特大，难免会有些标的不够好,这就是所谓的弱监督集（weakly supervised set）。所以如果算法能够自动找出最优的位置，那分类器不就更精确吗？ 标注位置不是很准确，这个例子不是很明显，还记得前面讲过的子模型的位置吗？比如自行车的车轮的位置，是完全没有位置标注的，只知道在bounding box区域附件有一个车轮。不知道精确位置，就没法提取样本。这种情况下，车轮会有很多个可能的位置，也就会形成一个正样本集，但里面只有部分是包含轮子的。

针对上述问题《Support Vector Machines for Multiple-Instance Learning》提出了MI-SVM。本质思想是将标准SVM的最大化样本间距扩展为最大化样本集间距。具体来说是选取正样本集中最像正样本的样本用作训练，正样本集内其它的样本就等候发落。同样取负样本中离分界面最近的负样本作为负样本。因为我们的目的是要保证正样本中有正，负样本不能为正。就基本上化为了标准SVM。取最大正样本（离分界面最远），最小负样本（离分界面最近）：

对于正样本：

 为正样本集中选中的最像大正样本的样本。

对于负样本：可以将max展开，因为最小的负样本满足的话，其余负样本就都能满足，所以任意负样本有：

目标函数：

也就是说选取正样本集中最大的正样本，负样本集中的所有样本。与标准SVM的唯一不同之处在于拉格朗日系数的界限。

而标准SVM的约束是：

最终化为一个迭代优化问题:

思想很简单:第一步是在正样本集中优化；第二步是优化SVM模型。与K-Means这类聚类算法一样都只是简单的两步，却爆发了无穷的力量。

这里可以参考一篇博客Multiple-instance learning。

3.1.2 Latent SVM

1）我觉得MI-SVM可以看成 Latent-SVM的一种特殊情况。首先解释下Latent变量，MI-SVM决定正样本集中哪一个样本作为正样本的

就是一个latent变量。不过这个变量是单一的，比较简单，取值只是正样本集中的序号而已。而LSVM 的latent变量就特别多，比如bounding box的实际位置x,y，在HOG特征金字塔中的某level中，样本component ID。也就是说我们有了一张正样本的图片，标注了bounding box，我们要在某一位置，某一尺度，提取出一个区域作为某一component 的正样本。

直接看Latent-SVM的训练过程：

这一部分还牵扯到了Data-minig。先不管，先只看循环中的3-6,12.

3-6就对于MI-SVM的第一步。12就对应了MI-SVM的第二步。作者这里直接用了梯度下降法，求解最优模型β。

2）现在说下Data-minig。作者为什么不直接优化，还搞个Data-minig干嘛呢？因为，负样本数目巨大，Version3中用到的总样本数为2^28，其中Pos样本数目占的比例特别低，负样本太多，直接导致优化过程很慢，因为很多负样本远离分界面对于优化几乎没有帮助。Data-minig的作用就是去掉那些对优化作用很小的Easy-examples保留靠近分界面的Hard-examples。分别对应13和10。这样做的的理论支撑证明如下：

3）再简单说下随机梯度下降法（Stochastic Gradient Decent）：

首先梯度表达式：

梯度近似：

优化流程：

这部分的主要程序：pascal_train.m->train.m->detect.m->learn.cc

3.2 训练初始化

LSVM对初始值很敏感，因此初始化也是个重头戏。分为三个阶段。英语方面我就不班门弄斧了，直接上截图。

下面稍稍提下各阶段的工作，主要是论文中没有的Latent 变量分析：

Phase1:是传统的SVM训练过程，与HOG算法一致。作者是随机将正样本按照aspect ration（长宽比）排序，然后很粗糙的均分为两半训练两个component的rootfilte。这两个rootfilter的size也就直接由分到的pos examples决定了。后续取正样本时，直接将正样本缩放成rootfilter的大小。

Phase2:是LSVM训练。Latent variables 有图像中正样本的实际位置包括空间位置（x,y）,尺度位置level，以及component的类别c，即属于component1 还是属于 component 2。要训练的参数为两个 rootfilter，offset（b）

Phase3:也是LSVM过程。

先提下子模型的添加。作者固定了每个component有6个partfilter，但实际上还会根据实际情况减少。为了减少参数，partfilter都是对称的。partfilter在rootfilter中的锚点（anchor location）在按最大energy选取partfilter的时候就已经固定下来了。

这阶段的Latent variables是最多的有：rootfilter（x,y,scale）,partfilters(x,y,scale)。要训练的参数为 rootfilters, rootoffset, partfilters, defs(

的偏移Cost)。

这部分的主要程序：pascal_train.m

4.细节

4.1轮廓预测（Bounding Box Prediction）

仔细看下自行车的左轮，如果我们只用rootfilter检测出来的区域，即红色区域，那么前轮会被切掉一部分，但是如果能综合partfilter检测出来的bounding box就能得到更加准确的bounding box如右图。

这部分很简单就是用最小二乘（Least Squres）回归，程序中trainbox.m中直接左除搞定。

4.2 HOG

作者对HOG进行了很大的改动。作者没有用4*9=36维向量，而是对每个8x8的cell提取18+9+4=31维特征向量。作者还讨论了依据PCA（Principle Component Analysis）可视化的结果选9+4维特征，能达到HOG 4*9维特征的效果。

这里很多就不细说了。开题一个字都还没写，要赶着开题……主要是features.cc。

源码分析：

DPM(Defomable Parts Model) 源码分析-检测

DPM(Defomable Parts Model) 源码分析-训练

参考文献：

[1] Pictorial Structures for Object Recognition. Pedro F.Felzenszwalb

[2]Object Detection with Discriminatively Trained Part Based Models.Pedro F. Felzenszwalb

[3]Cascade Object Detection with Deformable Part Models. Pedro F.Felzenszwalb

[4]From RigidTemplates To Grammars: Object Detection With Structured Models. Pedro F.Felzenszwalb

[5]Histogramsof oriented gradients for human detection. N. Dalal and B. Triggs

[6] http://bubblexc.com/y2011/422/

[7]A computational model for visual selection.Y. Amit and D.Geman

参考：http://blog.csdn.net/ttransposition/article/details/12966521

更多，请关注http://blog.csdn.net/tiandijun/，欢迎交流！