DPM 模型

计算机视觉

部分中英文参考链接

Deformable Part Model 展示网页
作者个人主页
一个DPM的专题
另一个DPM专题
凸优化和非凸优化

简介

这是一种多尺度可变形部件模型来解决此问题，此模型的判别训练过程只需要正样本的标注矩形框(意思是说只需要整个目标的标注信息，不需要各个部件的标注信息)。基于此模型实现了一个高效而精确的检测系统，可以在两秒内处理一张图片并达到明显比之前方法更高的检测精度。系统还依赖于判别训练的新方法。

作者将一种挖掘难例(Hard Negative Example)的间隔敏感方法与隐藏变量SVM(Latent variable SVM)结合在一起。隐藏SVM类似于隐藏条件随机场(Hidden CRF)问题，最终是一个非凸规划的训练问题。隐藏SVM是半凸规划(semi-convex)问题，但是一旦将隐藏信息指明给正样本，则训练问题变为凸规划问题。

发展过程

方法基于图结构(Pictorial Structures)框架 ，图结构使用一系列部件以及部件间的位置关系来表示目标。每个部件描述目标的一个局部属性，通过部件间的弹簧连接(Spring-like Connection)表示模型的可变形配置。而本系统最终使用混合模型来适应一些变换，比如视角和物体的类型

主要内容

使用一系列部件以及部件间的位置关系来表示目标。每个部件描述目标的一个局部属性，通过部件间的弹簧连接来表示各结构之间的配置。
Felzenszwalb提出的Deformable Part Model用到了三方面的主要知识：1.Hog Features 2.Part Model 3. Latent SVM。

1. 作者通过Hog特征模板来刻画每一部分Part Model，然后进行匹配。并且采用了金字塔，即在不同的分辨率上提取Hog特征
2. 利用上段提出的Part Model。在进行object detection时，detect window的得分等于 part 的匹配得分减去模型变化的花费。
3. 在训练模型时，需要训练得到每一个part的Hog模板，以及衡量part位置分布cost的参数。文章中提出了Latent SVM方法，将deformable part model的学习问题转换为一个分类问题。利用SVM学习，将part的位置分布作为latent values，模型的参数转化为SVM的分割超平面。具体实现中，作者采用了迭代计算的方法，不断地更新模型。

模型

star-structed part-based 模型：此模型由一个根滤波器(root filter)和一系列部件滤波器(part filter)以及相应的可变形模型(deformable model)构成。
星型模型在图像特定位置和尺度的得分等于根滤波器在给定位置的得分加上各个部件的得分的总和，每个部件的得分等于此部件在所有空间位置的得分的最大值，部件在某位置的得分等于部件滤波器在此位置的得分减去此位置的变形花费，位置的变形花费衡量了部件偏离其理想位置(这里说的位置是指与根滤波器的相对位置)的程度。

特征空间金字塔

通过对图像的降采样和平滑建立图像金字塔，按照每$\lambda$个level选取一个尺度，同时以这个level分辨率的二倍建立特征金字塔

( A feature pyramid and an instantiation of a person model within that pyramid. The part filters are placed at twice the spatial resolution of the placement of the root.)

得分计算方法

根滤波器和部件滤波器的得分都是由滤波器参数与特征金字塔中一个窗口的特征向量的点积(dot product)定义的。
每一个filter的得分计算方法 $F'*\phi (H,p,\omega,h)$
其中F'是各个filter对每个特征位置的权重按照行优先的方式排列，H是特征金字塔，$p(x,y,l)$表示指定位置和尺度(在特征金字塔中的level),w,h是窗口的尺度

latent SVM

在LSVM中，每个样本x使用下面形式的公式进行评分：
$f_\beta(x)=\max_{z \in Z(x)} \beta*\Phi (x,z)$
其中，β是模型参数向量，z是隐藏变量，Φ(x,z) 是特征向量。模型参数β是根滤波器、部件滤波器、变形花费权重串联起来构成的参数向量，z是目标配置参数，Φ(x, z)是特征金字塔中的一个窗口对应的HOG特征和部件变形特征串联起来构成的特征向量。
我们使用带类标的样本集D = (, ..., )，yi∈{-1, 1}来训练参数β，通过最小化下面的目标函数：
$L_{D(\beta )} =\frac{1}{2} \left \| \beta \right \| ^2 + C\sum_{i=1} ^n max(0,1-y_i f_{\beta }(x_i))$ , 这个问题其实是一个凸优化问题

凸优化问题

数学中最优化问题一般表示为 求取 $x^* \in X$ 使得 $f(x^*)=min \left [ f(x):x\in X)\right ]$，其中x是n维向量， $X$是x的可行域。
凸优化问题需要最优化问题满足两个条件
1. X是凸集,即集合中的任意两点的连线上的点都在集合内，至少在边上不能是下图的情况

2.f是X上的凸函数，即函数曲线应该是向下凸的，至少是线性的

之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决

LSVM的凸性

当LSVM的每一个正样本的隐藏变量只有一个可能的取值的时候，f函数是线性的，既是凸函数，又是凹函数。所以对于所有的样本，LSVM都是凸优化的问题,这样就可以通过求局部最优求得全局最优
LSVM的半凸性质非常重要，正是由于具有半凸性质所以问题变为容易解决的凸优化问题(即使负样本的隐藏变量值是不确定的)。还有一种相似的处理过程，在每一轮迭代时固定所有样本的隐藏变量值，但这可能无法产生最优结果。假设Z指定训练集D中所有样本的隐藏变量值。由于LD(β)遇到负样本时可能最大化，所以LD(β)可能比LD(β,Z)还大，因此不能指望通过最小化LD(β,Z)来获得一个好的模型。

难例挖掘

在训练目标检测的模型时，经常需要用到非常大量的负样本(对扫描窗口分类器来说，一张图片就可以产生大约105个负样本)，这使得同时处理所有负样本变得不可能。相反，用正样本和负样本难例(Hard Negative)来构成训练数据集变得更为常用。
只有 $y*f_\beta(x) > 1$才是正确的分类，这样的例子是容易的例子，而对于上面的，如果分类错误那么步进就要小小地，如果分类正确，就依旧按照之前的步速前进

待续