SSVM:Object Tracking via Dual Linear Structured SVM and Explicit Feature Map。

结构化SVM方法用于跟踪，带来了速度和效果的提升。结构化SVM和传统SVM方法相比，有着强大的判别能力，这篇博客将带大家一探结构化SVM在tracking上的应用。

同样是结构化SVM方法，Struck在2015年Pami中进一步加入尺度估计和GPU加速，使得Struck也具有相当的实用性。SSVM与Struck都是结构化预测框架，主要不同在于Struck采用SMO优化迭代求解，而SSVM采用DCD方法求闭式解，使得SSVM在速度上体现优势。

本文参考 博客http://www.p-chao.com/2017-03-27/图像跟踪（八）结构化svm：struck与ssvm/#i-11

结构化预测

首先介绍下，什么是结构化预测，这篇博客有详细介绍。本文摘录一部分：

1.二元分类（binary classification），目标变量取值只有两种可能性，简单地说就是做判断题，在现实生活
中应用非常广泛。银行根据客户资料，判断信用好坏以决定是否发放信用卡/贷款（german credit data)；
根据邮件内容，判断是否垃圾邮件(spam email)；根据病人资料，判断病人是否患癌症(breast cancer)等等。
2.二元分类是机器学习中最基本最核心的问题，许多其他演算法的基础都来自他。
3.多元分类（Multiclass Classification），简单地说就是做选择题，目标变量是level>1的factor。比如判
断某种植物所属科目（iris)，评估汽车价值高低(car evaluation)等等。
4.回归分析（regression analysis)的目标变量是Numeric类型的，取值无限多个点。典型的回归分析问题包括
用历史数据做出历年GDP的回归线，用相关变量估计房屋价格(Housing Data Set)等等。

结构化预测通过修改SVM的约束条件以及目标和核函数，将SVM从二分类问题拓展到可以预测结构化问题。结构化预测的参数学习方法有一下几种：

• structured perceptron(Collins, 2002)
• stochastic subgradient(Ratliff, 2007)
• extra-gradient(Taskar, 2006)
• cutting-plane algorithms(Joachims, 2009)
• Dual decomposition(Meshi, 2010)

结构化预测虽然提出较早，但是结构化预测用于跟踪才是近几年的事情，接下来的内容主要介绍结构化SVM用于图像跟踪。

正文来了

Struck

Struck拥有很快的速度和很好的效果，如果不是KCF横空出世，Struck可能会多流行几年，KCF174fps的速度和效果已经吊打全场了，不过Struck的优秀也是遮挡不住的。

核心思想

使用结构化SVM来处理跟踪问题

结构化SVM

结构化SVM训练的目标是学习得到预测函数f，下式中g就是评分函数，评分函数输出的是连续值而非传统的[+1,-1]，，y是搜索空间内的一个矩形，t是当前帧，时间空间，函数f作用是将时间空间映射到坐标空间，也就是预测位置过程的函数

$$\max \frac{1}{\Vert w\Vert }s.t.,y_i(w^T{x}_i+b)\ge 1,i=1,\dots ,n$$

用一系列样本训练求解以下问题，就是基本SVM的Loss函数了，是属于最大间隔框架，最小化w，附带一个软间隔项：

其中的△符号代表了我们定义的间隔，这个间隔的实际意义和重叠率是相关联的，重叠率为1时，该值为0，相当于训练时，中心处的样本，间隔设定为0

后面就是优化过程，推一边拉格朗日对偶条件，然后使用SMO优化

关于拉格朗日对偶原理的推导，建议参考《统计学习方法》（李航）

SMO优化，一次需要输入一对向量模型，一正一负，并且尽量使差异足够大，然后迭代更新支持向量

上面伪代码中，有一个符号的定义如下

使用核函数时，g的核函数形式推导如下

到这里，已经差不多结束结构化SVM的理论推导了，下面是介绍文章中跟踪的细节，第一个细节：算法使用的特征：Haar特征集

第二个细节：就是可以同时使用多个核函数进行组合，组合的方式也比较容易，就是在核映射之后取平均，如下式

以下就是该算法中SVM维护数据的可视化表达了，这部分主要是为后面GPU实现做铺垫，数据规整才适合GPU加速嘛

细节三：GPU加速，这是2015年Paper里面新加的

实现细节

采样方法：对目标周围进行密集采样，超出采样框的将舍弃
预测位置：使用SVM对每个位置输出分数，预测当前帧位置
模型更新：根据预测，更新正负支持向量，更新过程采用的是SMO方法，每回使用一对向量，如下所示

上面的伪代码可以和Struck的C++源代码一起看，因为这份源码和上面伪代码的结构是一样的，代码和Paper结合的非常好，另外其中有些细节，如代价维护等等，都在Paper里面详细说明了，这里不过多赘述

参考文献
[1]. Hare, S., A. Saffari and P.H. Torr. Struck: Structured output tracking with kernels. in 2011 International Conference on Computer Vision. 2011: IEEE.

[2]. Hare, S., et al., Struck: Structured output tracking with kernels. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015. 38(10): p. 2096-2109.

SSVM

SSVM算法就是Structure SVM的缩写，其本身和Struck极为相似，那么它和Struck有哪些不同呢？

与Struck的不同
从下面这张图应该就可以看出来了吧，SSVM与Struck的不同支取在于，Struck训练时采用SMO，需要一对支持向量来进行训练，而这对支持向量又需要通过十次（代码中的参数）迭代来选取，而SSVM训练时，采取闭式解来优化参数，DCD（Dual Coordinate Descent），Paper中的Title为 Optimization with closed form solution。

搞数学的都知道（虽然我不是搞数学的），闭式解比数值解不知道高到哪里去了，那么感受一下闭式解的求解方程吧，对于一个样本k，DCD方法首先选择一个剧烈变化的最大误差

为了估计alpha，我们首先分离变量（将输出误差设置为0），alpha就被表示为下面的公式

带入W取得近似解

再定义一个因子

然后w的更新模型就可以表示为下士

在更新完w后，问题就简单了，下面就是结构化预测的输出公式

特征选取

没用采用Haar、Hog之类的特征，直接裸数据+LRT，对于彩色图像就是RGB+LRT四通道，对于灰度图像就是Gray+LRT三通道。LRT就是Local Rank Transform，局部秩变换是一种非参数变换，对光照变化不敏感，以增加光照适应性。

算法实现
这个确实没什么好说的，典型的track-by-detection思路，一样的地方之前在Struck都讲过了，不一样的地方就是闭式解优化。

参考文献
[1]. Ning, J., et al. Object tracking via dual linear structured SVM and explicit feature map. in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.