Visual Tracking with Online Multiple Instance Learning (MIL)目标跟蹤論文筆記

1. 論文資訊

• 論文标題 ：Visual Tracking with Online Multiple Instance Learning
• 論文作者：
  1. Boris Babenko，University of California, San Diego
  2. Ming-Hsuan Yang，University of California, Merced
  3. Serge Belongie，University of California, San Diego
• 發表會議：CVPR，2009

2. 基礎知識

• 目标跟蹤的三大要素：圖像表示（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個用于進行判别。

• 該論文在更新判别分類器時，核心算法如下所示：
  1. for k = 1 to K do
  2.     for m = 1 to M do
  3.          pmij=σ(Hij+hm(xij))
  4.          pmi=1−∏j(1−pmij)
  5.          Lm=∑i(yilog(pmi)+(1−yi)log(1−pmi))
  6.     end for
  7.      m∗=argmaxmLm
  8.      hk(x)←hm∗(x)
  9. Hij=Hij+hk(x)

  10. 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;
p = exp((x - mu).^.*e0).*n0;
p1 = exp((x - mu1).^.*e1).*n1;

r = log(eps + p1) - log(eps + p);
           

7. 源碼分析

• 源碼中幾個重要的步驟有：采樣、為每個樣本計算Haar特征、更新弱分類器和選擇分類器，其中更新弱分類器有三個相關函數（weakClassifierUpdate、weakClassifier、MilBoostClassifierUpdate）。
• 函數weakClassifierUpdate、weakClassifier、MilBoostClassifierUpdate之間的差別在于，weakClassifierUpdate 主要用于更新 μ 和 σ ，weakClassifier。 主要用于存放各個弱分類器對各個樣本的分類結果， MilBoostClassifierUpdate主要用于選出50個分類器。
• 算法的主要結構如下圖所示：