Boris Babenko,的论文（MIL）Robust Object Tracking with Online Muliple instance Learning中基本思想和算法想要解决的问题的梳理笔记：

一、一般的目标跟踪的主要分为以下几步：

    1、特征提取（Feature Extraction）：即能对跟踪目标进行较好描述的描述子称为特征。跟踪算法要求提取的特征既能较好地描述跟踪目标又能快速计算．常见的图像特征有灰度特征、颜色特征、纹理特征、Haar-like 矩形特征、兴趣点特征、超像素特征等；

    2、外观模型（Appearance Model）：在当前帧中判决候选图像区域是被跟踪目标的可能性。在目标跟踪算法中，外观模型的设计处于一个核心地位，如何设计一个具有鲁棒性的外观模型是目标跟踪算法的关键；

    3、运动模型（Motion Model）：运动模型旨在描述帧与帧目标运动状态之间的关系，显式或隐式地在视频帧中预测目标图像区域，并给出一组可能的候选区域，即将目标位置和时间关联起来。当前比较经典的运动模型有有卡尔曼滤波( Kalman Filtering)、粒子滤波( Particle Filtering)等；

    4、更新机制（搜索策略：Search Strategy）:在当前帧找到目标最可能的位置.常见的外观模型更新方式有模板更新、增量子空间学习算法及在线分类器等；

    正如前面说到的外观模型是跟踪算法的关键，Boris的这篇论文主要的也是对于外观模型的研究设计，目的是为了能够跟踪部分遮挡和各式各样外观变化的目标，而在外观模型更新过程中不会出现明显的漂移，且只有较少的参数。

二、基本思想

2.1 外观模型设计

外观模型一般具有两种表示方式：

    1、静态外观模型（Stastic Apperance Models）（人为定义或者通过第一帧训练得到（先验知识）

缺点：无法处理外观剧烈变化的情况，如变形、平面外旋转、场景光照变化； 

    2、自适应外观模型（Adaptive Apperance Models）（在跟踪过程中，随着目标变化，外观模型不断迭代更新）缺点：有很多参数要调节、局部遮挡时会出现漂移 ；

Boris采用的是自适应外观模型，想达到的目标是能够跟踪到部分遮挡的物体而不出现明显的漂移，并且只有较少的参数。

自适应外观模型的建模方式一般会有两种思路： 

    1、只对目标建模：建模后在后续帧进行模板匹配（产生式方法） 

    2、同时对目标和背景建模：把跟踪当成二分类问题，用目标和背景训练分类器，然后用分类器寻找目标（判别式方法）同时对目标和背景建模，并使用判别式分类器区分前后背景，跟踪效果更好。因此同时对目标和背景进行建模具备一定的优势，也常被采用。

Boris采用的便是同时对目标和背景建模，在外观模型更新时如何选择正负样本（目标是正样本、背景是负样本）是一大难题，选择正负样本的方式有： 

    1、把当前跟踪位置作为单个正样本，在其周围采样得到若干负样本 这样做，如果跟踪器确定的位置不精确，会导致误差积累，出现漂移。Grabner et al.提出的半监督（semi-supervised）的方法，将tracker得到的目标都认为是无标签的样本，而只有第一帧中的样本是有标签的。然后通过聚类的方法给定这些无标签样本一个伪标签，在继续使用有标签的方法进行跟踪。这个方法没有充分的利用到视频中有用信息，比如说相邻的帧之间的变化非常的小等。

     2、从当前跟踪位置附近采样得到多个正样本，在其周围采样得到若干负样本 ，这样做目标模型会变得混乱(有多个正样本，不知道具体选哪个做下一帧目标位置)，其判别能力会减弱，同时也会出现样本不精确导致的跟踪漂移 

    3、把跟踪位置的确定看作一个多示例问题（即知道目标的大概位置，但是具体位置不知道），用多示例学习解决 。

    3就是Boris的MIL的基本思想：在训练过程中，样本不再是单个图像块（Image Patch），而是将多个图像块放在一个包（Bag）里，整个包有一个标签。如果包里至少有一个正实例（positive instance），则标记为正。否则，标记为负。 即从当前跟踪位置附近采样得到多个样本，放在一个包里，标记为正（至少有一个正样本），在其周围采样得到若干负样本，每个负样本都单独放在一个负包里（也可以把所有负样本都放在一个负包里，结果一样。因为负包里的样本都是负样本）。

2.2 MIL跟踪算法

MIL跟踪算法： 
    1、由前一帧目标位置得到当前帧目标可能位置的集合，并计算相应的特征向量（使用Haar-like特征）表示图像块x的位置，包括坐标(x,y)和尺度； 表示第（t-1）帧（前一帧）的目标位置； s为参数，度量图像块与前一帧目标位置的最大距离。 
    2、使用MIL分类器计算集合中所有图像块的概率（图像块x中包含目标的概率） 

    3、更新跟踪器目标位置，选出概率最大的图像块作为当前帧的目标位置 

    4、得到目标位置以后，扩展样本： 扩展为正样本，放在一个包里面，并标签为正；

， 扩展负样本，每个负样本单独放在一个包里面，并标签为负；   

    5、用扩展后的正包和负包对MIL外观模型 进行更新； 

    同时论文还考虑了引入尺度变换参数，好处是结果可以更加的准确；坏处是增加了参数的空间维度，因此可根据需求决定是否采用。

2.3 多示例学习（Multiple Instance Learning）

 MIL分类器的在线训练过程 

 多示例学习MIL 

    1、用传统算法训练分类器： 

训练样本：， 

为单个示例(样本)，为示例标签， 

用训练样本训练得到分类器H，用分类器对新样本进行分类，p(y|x)  

    2、用多示例学习训练分类器： 

训练样本：， 其中

为包，里面是若干个示例，为包的标签，为示例标签 

正包：包中至少有一个正例 

负包：包中所有示例都是反例 

包的标签与示例标签的关系：

 在实际训练过程中，示例标签是未知的。MIL分类器在线训练开始阶段，更新弱分类器要用到示例标签(弱分类器是示例分类器，即是对示例进行分类的)，是直接将包的标签复制给示例 。

2.4 在线多示例提升（Online Multiple Instance Boosting）

在线提升Online Boosting 

    Boosting是改善学习算法准确度的一般方法，即把较弱的学习算法变成较强的学习算法。也即将多个弱分类器h加权线性组合，得到一个强分类器H，

Online MILBoost(OMB) 

Online MILBoost实质是通过多示例学习(MIL)在线(Online)挑选弱分类器，然后将弱分类器加权线性组合(Boost)成强分类器的过程（弱分类器的挑选是个迭代的过程，前一步的结果会影响后一步）

 如何挑选弱分类器 ：

挑选弱分类器的标准：最优化目标函数J，即(1) 

（其中，是前面k-1个弱分类器合成的强分类器，是所有弱分类器的集合。 是得到的第k个弱分类器，是对应的权重；

本论文里，目标函数J是计算所有包都是正包的概率（然后取对数），即  （2）

所以本论文的弱分类器挑选标准是：(3)（结合(1)(2)），即挑选使所有包都最可能是正包（概率最大）的弱分类器h；

K次迭代挑选出来的弱分类器h加权线性组合成一个强分类器H，即

在本论文里，权重被融进了弱分类器，所以组合方式变为

备注： 1、目标函数
里的表示一个包是正包的可能性，用NOR模型计算得到，即 

2、为简化问题，权重被融进了弱分类器，这样分类器的返回值不再是0或1，而是实数 

3、NOR模型里的是单个示例的概率，计算方式为，(sigmoid函数，能够把输入的连续实值压缩到0到1之间)，H(x)表示用强分类器对示例x分类之后输出的结果，是实数，不是二进制0、1 

4、弱分类器h总共有M个，在这M个里挑选K个，组合成一个强分类器H 

5、弱分类器是用示例更新的，示例标签是直接从包的标签复制过来的。负包里的示例都是负示例，正包里的示例可能有负示例，直接复制标签会有误差。所以用所有包都是正包的概率作为目标函数，找出使目标函数最大的弱分类器。

训练MIL分类器的主要步骤： 
从弱分类器池(M个)中挑选出K个弱分类器，进行K次循环，每次循环挑选一个弱分类器，每次循环都执行以下步骤： 
1、用(sigmoid函数)计算每个示例的概率 
2、用NOR模型计算每个包是正包的概率 
3、计算所有包都是正包的可能性 

然后找出使所有包都是正包的可能性最大的弱分类器，作为当前循环的输出。 最后将挑选出来的K个弱分类器加权线性组合成一个强分类器，即（权重被融进了弱分类器）

训练MIL分类器的完整步骤：

注释： 
输入：训练集，包含N个包（1个正包，N-1个负包） 
    1、用带标签的示例更新弱分类器池中的全部弱分类器（M个） 
因为弱分类器是示例分类器，所以更新时需要用到示例信息，即{xij,yi} 训练集中，只有包的标签已知，示例标签不知道 论文里的做法是，将包的标签直接复制给示例  
    2、对所有的示例xij（第i个包中的第j个示例），初始化时Hij=0 
Hij保存的是要对示例xij进行分类的分类器，实际等于前k趟挑出的弱分类器的加权线性组合（由11可以看出） 

    3、进行K趟循环，每趟从弱分类器池中选出一个弱分类器hk 

    4、每个弱分类器的选择都是从弱分类器池（M个）中挑选的 挑选标准是：挑选使包的可能损失函数最大的弱分类器hm 

    5、计算示例的概率， Hij保存的是前一趟得到的强分类器，用Hij和第m个弱分类器hm叠加以后，共同对示例xij进行分类，返回结果是示例的概率，为一个实数 

    6、计算第i个包是正包的可能性（每个弱分类器都会对应一个值）

    7、计算所有包都是正包的可能性（每个弱分类器都会对应一个值） 

    9、挑选使所有包都是正包的可能性最大的弱分类器hm* 

    10、把hm*作为这一趟挑选的弱分类器hk 

    11、Hij表示对示例xij进行分类的分类器，这里是对每趟挑选出的弱分类器进行加权线性组合，这样Hij在每趟循环过后，保存的都是当前的强分类器（前面k趟挑选的弱分类器的加权线性组合） 

输出：一个强分类器（所有弱分类器的加权线性组合）。

三、总结

   Boris针对分类器更新过程中产生的漂移问题。做法是既然得到样本标签的准确率有问题，那么对得到的样本进行扩展，作为一个事件集选出里面错误率最低的时间来更新目标的位置，也由此来更新分类器。准确率和速度都会好很多。

参考资料：https://blog.csdn.net/ikerpeng/article/details/19235391

          https://wenku.baidu.com/view/37e63c7e86c24028915f804d2b160b4e767f81f9.html