LOT：《Locally Orderless Tracking》 蒙特卡洛方法、 粒子滤波 、Earth Mover's Distance

1.先验概率、后验概率和似然

2.蒙特卡洛方法（Monte Carlo method）和粒子滤波（particle filtering）

蒙特卡洛采样：根据待估计的量X的概率分布（后验概率）进行采样

蒙特卡洛方法：在采集了N个样本之后，如果要求X的均值，那么可以直接对采集的N个样本 求平均计算出的值来代替样本的均值，当N足够大的时候，平均值的与均值的近似度越高，误差越小。

  

粒子滤波：把蒙特卡洛采样的样本点当做一个粒子，按照蒙特卡洛方法对粒子进行平均，获得粒子滤波后的结果

但是这样的方法存在一个缺点：不知道X的分布，即不知道后验概率的分布，那么要进行如何采样呢

粒子滤波还可以进行加入噪声，使得结果更加的趋于稳健

重要性采样：根据一个已知的分布去采样，就有期望为：

重要的是引入了权重的概念，上面Wk(Xk)就是采样点的权重，引入权重之后，根据蒙特卡洛方法求均值就变为如下：

所以引入重要性采样之后，权重经过了归一化处理（权重的和为1），根据权重最终求出了该随机量X的均值

应用的实例：目标追踪

追踪的目的是在当前帧内计算出目标中心所在的位置，把目标的位置看做是一个随机变量，那么在当前帧内的每个位置会有一个概率，由此就构成了一个后验概率分布，因为这个概率必须根据前一帧的位置，或者是根据初始帧的位置确定。 利用粒子滤波的方法在理论上可以求出当前帧目标的位置，因为位置的分布服从一个概率分布，其均值就是当前帧目标最有可能的位置处。

但是在实际当中，并不知道位置的概率分布具体是什么，所以就很难去根据分布采样，所以就进行的是重要性采样（一般是进行均匀的采样），所以难点就放在计算每个采样（粒子）的权重计算上，在实际的应用问题中，计算采样的权重是进行迁移了的，在追踪中，每个采样点可以根据其周围的像素点分布情况进行采样，即比较模板与候选的位置的相似程度，然后再确定权重。最后就能计算出位置。   

3.Earth Mover's Distance-地面移动距离

EMD是由 2000年YOSSI RUBNER在《The Earth Mover's Distance as a Metric for Image Retrival》论文中提出的

在计算上诉粒子滤波的采样点权重时，可以迁移为计算模板的Signsture与候选位置的Signature，在此处利用EMD来计算。

EMD的定义：

其中这个问题可以规约到一个线性规划问题的求解，如下

在这上面中，尤其重要的是dij，代表的是在Signature中与之相应的两个elements的distance的多少，在每个EMD中是必须存在的，但这个distance的计算方式也是多种多样的。在求出的最优解后，即计算出了fij后，此时的EMD可表示为：

                    

fij表示的是取得最优解时的值。

在实际的应用中，比如image/patch的像素直方图，把直方图当做一个Signature，把0-255个值划分为多个bin，然后求出直方图，那么EMD代表的就是使得两个直方图变为一样时，需要总的代价是多少，在计算代价中，一定需要一个distance，即不同的bin之间移动的代价，这个移动就表示像素值的改变，最终使得两个图像的直方图一样所需要的最小代价就是EMD，这是一个线性优化的过程。

另外一个实际的EMD的例子如下：

在比较两个目标Signature时的EMD，是经过迁移之后的EMD，要套用在这个情形下，必须进行一定的转化才能应用。

论文中的算法：《Locally Orderless Tracking》

参考的博文：

https://blog.****.net/piaoxuezhong/article/details/78619150

https://blog.****.net/zhangping1987/article/details/25368183