1. 论文信息 论文标题 ：Visual Tracking with Online Multip le Instance Learning论文作者： Boris Babenko，University of California, San DiegoMing-Hsuan Yang，University of California, MercedSerge Belongie，University of California, San Diego发表会议：CVPR ，20092. 基础知识 目标跟踪的三大要素：图像表示（Image Representation）、外观模型（Appearance Model） 和运动模型（Motion Model）。本文中的图像表示为Haar-like特征，外观模型由一个判别分类器组成，运动模型就是在上一帧目标周围取一系列的patches（要求：距离 < s ），看哪一个patch的概率最高就将新的目标框给它（贪心算法）。本文的重点是外观模型 。本文没有考虑旋转和尺度变化。3. 整体思路 只要能够在每一帧中都能应用上述贪心算法，理论上就能实现目标跟踪，那么，程序如何计算各个patches（要求：距离 < s ）的概率呢？只要每一帧确定了当前的目标位置，程序就会对外观模型进行更新，实质上是更新判别分类器，新的分类器会对各个patches（要求：距离 < s ）的概率重新进行计算，将概率最大的patch作为新的目标位置。
4. 判别分类器如何更新 一旦确定了当前的目标位置，就选取一组patches（要求：γ < 距离 < β ），把这些patch放到一个包里面，标记为positive，即假设这个包里面的所有patch中，至少有一个是正样本。同时也另选取一组patches（要求：γ < 距离 < β ），对于这些patch，每个都作为一个独立的包（有多少个patch，就有多少个包），标记为negative，即假设这个包里面的patch是负样本。注意：这里用的判别分类器并不是一个单独的分类器，实际上它由许多独立的基于Haar-like特征的弱分类器构成，将这些弱分类器用线性的方式加起来，就形成了一个Haar级联分类器：H(x)=∑k=1Kαkhk(x)(1)
上述公式(1)中的K 表示候选分类器，αk 是权值，最终目的是从M 个Haar-like特征分类器中选出K 个用于进行判别。
该论文在更新判别分类器时，核心算法如下所示：
for k = 1 to K do for m = 1 to M do pmij=σ(Hij+hm(xij)) pmi=1−∏j(1−pmij) Lm=∑i(yilog(pmi)+(1−yi)log(1−pmi)) end for m∗=argmaxml m hk(x)←hm∗(x) Hij=Hij+hk(x) end for 在上述算法中，第三行中求的是样本的概率，第四行求的是包的概率。
从上面的算法可以看出，本文MIL算法主要依赖对数似然函数进行求解，每处理一帧图像，算法就会采集一些训练样本{(X1,y1),(X2,y2)⋯} ，其中Xi={Xi1,Xi2⋯} ，这时，算法会通过估计p(y|x) 的值来使对数似然函数最大化，如下所示：
logL=∑ilog(p(yi|Xi))(2)
其中，
p(y|x)=σ(H(x))(3)
而
σ(x)=11+e−x(4)
σ(x) 是Sigmoid函数，其中x 为H(x) ，表示分类器的结果。
5. 一些不足及相应的修补方法 对于positive包，一个包中有多个实例，文章在计算时假定这些实例全部为正样本，这种假设离真实情况存在差异，其补救办法是：基于似然损失函数来选择弱分类器h 。在选择弱分类器时，没有采用系数，文章没有对此问题加以补救，文章认为这并没有影响性能。似然函数在计算时，仅仅依据当前的样本，可能导致对当前样本的过拟合，文章通过保留历史数据的做法进行修补（前面的算法有没有体现这种思想？）6. 实现细节 在文章中，每一个弱分类器hk 由一个Haar-like特征fk 以及对应的4个参数构成，弱分类器返回一个对数概率，如下所示：
hk(x)=log[pt(y=1|fk(x))pt(y=0|fk(x))](5)
其中， pt(ft(x)|y=1)∼N(μ1,σ1)pt(ft(x)|y=0)∼N(μ2,σ2)(6) 文章令p(y=1)=p(y=0) ，采用贝叶斯来计算hk(x) 。当这个弱分类器接收了一组新数据{(x1,y1),(x2,y2),...,(xn,yn))} 时，更新的原则如下所示： μ1←γμ1+(1−γ)1n∑i|yi=1fk(xi)σ1←γσ1+(1−γ)1n∑i|yi=1(fk(xi)−μ1)2−−−−−−−−−−−−−−−−−√(7) 其中，γ 被称为学习率参数。
对μ0 和σ0 的更新原则也是一样的。
上述弱分类器函数hk(x) 的计算在配套代码中有所体现，比如：
x = samples.feature;p0 = exp((x - mu0).^2.*e0).*n0;p1 = exp((x - mu1).^2.*e1).*n1;r = log(eps + p1) - log(eps + p0);7. 源码 分析 源码中几个重要的步骤有：采样、为每个样本计算Haar特征、更新弱分类器和选择分类器，其中更新弱分类器有三个相关函数（weakClassifierUpdate、weakClassifier、MilBoostClassifierUpdate）。函数weakClassifierUpdate、weakClassifier、MilBoostClassifierUpdate之间的区别在于，weakClassifierUpdate 主要用于更新μ 和σ ，weakClassifier。 主要用于存放各个弱分类器对各个样本的分类结果， MilBoostClassifierUpdate主要用于选出50个分类器。算法的主要结构如下图所示：Created with Raphaël 2.1.0 新的一帧开始 采集样本detectx（这一组样本不分正负，就是用来定位的） 利用上一轮选择好的 50 个弱分类器，计算每个 detectx 样本的 Haar 特征 计算各个弱分类器对所有detectx样本的分类结果（每个结果都是一个数值） 对每个detectx样本，将各个分类器的分类结果进行求和 Sum 找出一个数值最大的Sum，将它对应的detectx样本作为当前这一帧的目标 采集正样本和负样本 分别对正样本和负样本计算特征 分别为正样本和负样本更新mu和sigma 各个弱分类器对各个样本进行分类，打分 选出50个最好的分类器，用于下一帧 新的一帧结束
