Abstract: The DEMD（Differential Earth Mover’s Distance） tracking algorithm adopts normalized EMD model as the similarity function，and computes the derivative of EMD on the irrational assumption that when the weight of one bin changes，the weights of other bins change in equal proportion.In addition，the DEMD tracking algorithm has slow convergence rate because it iterates by one pixel along the gradient.In addressing the two problems，an improved EMD object tracking method is proposed.It employs original EMD model to measure the similarity of two color distributions without normalization，computes using the two phase method in linear programming and then derives the mean shift iteration equations by maximizing the similarity function.Experimental results show that the proposed algorithm has better tracking performance and is more efficient than the DEMD algorithm.

Key words: object tracking, Differential Earth Mover’s Distance（DEMD）, simplex method, Mean Shift

摘要： DEMD（Differential Earth Mover’s Distance）跟踪算法采用归一化的EMD模型作为相似性函数，在推导相似性函数梯度时，假定颜色模型中某一区间权重发生改变时其他区间的权重等比例变化，这种假定在很多情况下并不合理。另外，DEMD算法沿着梯度方向以一个像素为步长进行迭代，收敛速度较慢。为了解决上述问题，提出了一种改进的EMD目标跟踪算法。该方法使用未归一化的EMD模型作为相似性函数，通过线性规划中的两阶段法求解EMD距离并推导出相应的均值漂移算法。实验表明，改进算法具有更好的跟踪性能而且收敛速度更快。

关键词: 目标跟踪, 差分推土机距离（DEMD）, 单纯型法, 均值漂移