視覺追蹤之meanshift

04-19

Meanshift算是單目標視覺追蹤裡面比較重要且經典的演算法，本文將從原理和編程實現細節上對這個方法梳理一下（主要內容是翻譯了一下這篇論文，對部分證明進行了省略），錯誤的地方還請指正。好，那麼我們開始吧！

在開篇之前讀者可以熟悉一下單目標追蹤的任務定義以及面臨那些困難，關於這部分內容在我這篇博文有提及，不太熟悉的童鞋可以瀏覽一下！

簡要：MeanShift 可以翻譯為「均值漂移」，它在聚類、圖像平滑、圖像分割和跟蹤方面得到了比較廣泛的應用。MeanShift 這個概念最早是由Fukunaga等人於1975年在一篇關於概率密度梯度函數的估計（The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition）中提出來的。其最初含義正如其名：就是偏移的均值向量。在這裡MeanShift是一個名詞，它指代的是一個向量。但隨著Mean Shift理論的發展，MeanShift的含義也發生了變化。如果我們說MeanShift演算法，一般是指一個迭代的步驟，即先算出當前點的偏移均值，移動該點到其偏移均值，然後以此為新的起始點繼續移動，直到滿足一定的條件結束。[1]

符號定義：

標量： $x_i$
列向量： $extbf{x}_i$

1.mean shift的數學定義：

給定一個點集： ${ extbf{x}_i}_{i=1...n}$ ,且處於 $d$ 維空間，則關於向量 $extbf{x}$ 的多變數核密度估計為：

$hat f_K( extbf{x})=frac{1}{nh^d}sum_{i=1}^nk(frac{| extbf{x}- extbf{x}_i|^2}{h})$ (1)

註：在代碼模擬中用的是高斯核密度函數

其中核函數為 $K( extbf{x})$ ,窗口半徑為 $h$ 。

同時我們令：

$g(x)=-k(x)$ (2)

同時我們定義核函數 $G$ ：

$G(x)=Cg| {x} |^2$ (3)

則函數 $hat f_K( extbf{x})$ 的一階導數是：

$hat abla {f_K}(x) = frac{2/C}{h^2}M_{h,G}hat f_G(x)$ (4)

其中：

$M_{h,G}=frac{sum olimits_{i=1}^{n} { extbf{x}_ig(|frac{ extbf{x}- extbf{x}_i}{h}|^2)} }{sum olimits_{i=1}^{n} {g(|frac{ extbf{x}- extbf{x}_i}{h}|^2)} }- extbf{x}$ (5)

$M_{h,G}+ extbf{x}$ 為mean shift向量,原因如下（注意這個向量方向與核密度函數的梯度保持一致，且梯度方向為函數值增加的方向）

==============================================

當變數按照目標方程值增大的方向更新時，其公式如下：

$extbf{x}^* = extbf{x}+lr* abla extbf{x}$

其中 $lr$ 為學習率(標量)， $extbf{x}^*$ 為自變數更新後的值

==============================================

$hat f_G( extbf{x})=frac{C}{nh^d}sum_{i=1}^n{g(|frac{ extbf{x}- extbf{x}_i}{h}|^2)}$ (6)

需要注意的是前面的函數的輸出值為標量，關於它的收斂條件請參考[2]

2.巴氏係數的定義

在確定巴氏係數之前，我們首先引入兩個概率密度方程:

$q_z$ 為目標的真實概率分布

$p_z(y)$ 為採樣樣本在以位置 $y$ 為中心的概率分布方程

其中的 $z$ 代表目標物的顏色或者紋理特徵

則巴氏係數的作用是用來度量兩個離散或者連續概率分布的相似性，其積分數學形式為：

$ho(y)= ho[p(y),q]=intsqrt{p_z(y)q_z}dz$ (7)

離散數學形式為：

$ho(y)= ho[p(y),q]=sum_{z=1}^m {sqrt{p_z(y)q_z}}$ (8)

這個離散形式可以解釋為，兩個向量的餘弦距離

3.mean shift與目標追蹤

有了前面的基礎，我們可以實現一個基於mean shift的單目標跟蹤演算法，我們的優化目標就是巴氏係數，優化手段為mean shift，優化對象為位置變數 $y$ ，不停的改變它的值就完成了對目標物在當前幀位置的估計。好了接下來我們引入一個具體的例子，來看看實際怎麼操作：

對應前面的內容，我們定義目標物基於特徵 $u$ 真實概率分布為(離散)，目標物的中心坐標為 $extbf{0}$ ， ${x_i^*}_{i=1...n}$ 為像素點的坐標值：

$hat q_u=Csum_{i=1}^nk(| extbf{x}_i^*|^2)delta[b( extbf{x}_i^*)-u]$ (9)

註：一般我們根據第一幀的先驗信息，依據顏色直方圖信息就可以定義一個目標物的無參核密度估計函數 $hat q_u$

其中的 $b( extbf{x}_i^*)$ 為圖像中對應位置的像素處於顏色直方圖的那個區間

則中心坐標在 $extbf{y}$ 的候選樣本的概率分布函數為：

$hat p_u=C_hsum_{i=1}^{n_h} k(|frac{ extbf{y}- extbf{x}_i}{h}|^2)delta[b( extbf{x}_i)-u]$ (10)

我們將前面提到的巴氏係數按照泰勒展開，可以近似為：

$ho[hat{ extbf{p}}( extbf{y}), hat{ extbf{q}}]approx frac{1}{2}sum_{u=1}^m {sqrt{hat p_u(hat{ extbf{y}}_0)hat q_u}}+frac{m}{2}sum_{u=1}^{n_h} hat p_u(hat{ extbf{y}}){sqrt frac{hat q_u}{hat p_u(hat{ extbf{y}}_0)}}$ (11)

將公式(9)帶入公式(11)得：

$ho[hat{ extbf{p}}( extbf{y}), hat{ extbf{q}}]approx frac{1}{2}sum_{u=1}^m {sqrt{p_u(hat{ extbf{y}}_0)q_u}}+frac{C_h}{2}sum_{i=1}^{n_h} w_ik(|frac{ extbf{y}- extbf{x}_i}{h}|^2)$ (12)

其中 $w_i$ 為：

$w_i=sum_{u=1}^m delta[b( extbf{x}_i-u)]{sqrt frac{hat q_u}{hat p_u(hat{ extbf{y}}_0)}}$ (13)

為了最大化巴氏係數的值，近似等價於優化公式(12)的第二項(注意第一項的值是一個常量，並不隨變數 $extbf{y}$ 的值而改變)，此時利用mean shift的定義便可以達到所要求的優化目標。

那麼完成整個追蹤過程的是：

===================================================

目標：最大化巴氏係數

已知：目標物的真實分布 ${hat q_u}_{u=1...m}$ ,目標物在上一幀的位置坐標為： $hat{ extbf{y}}_0$

----------------------------------------------------------------------------------------

1.基於前一幀的信息計算： ${hat p_u(hat{ extbf{y}}_0)}_{u=1...m}$ ,同時計算其與目標物真實分布之間的巴氏係數的值：

$ho[hat{ extbf{p}}( extbf{y}_0), hat{ extbf{q}}]= sum_{u=1}^m {sqrt{hat p_u(hat{ extbf{y}}_0)hat q_u}}$

2. 根據公式(13)求取權值 ${w_i}_{i=1...n_h}$

3. 基於mean shift的定義，得到新的位置：

$hat{{ extbf{y}}}_1=frac{sum olimits_{i=1}^{n} { extbf{x}_iw_ig(|frac{hat{ extbf{y}}_0- extbf{x}_i}{h}|^2)} }{sum olimits_{i=1}^{n}w_i {g(|frac{hat{ extbf{y}}_0- extbf{x}_i}{h}|^2)} }$