Region-based tracking in a temporal image sequence is described as a segmentation of current frame into a set of non-overlapping regions: the tracking regions and the non-tracking region. The segmentation is viewed to be a Markov labeling process. Based on the key idea of using a doubly stochastic prior model, the optimal estimation for the label field is found by the minimization of a differentiable function. We exploit the feature-spatial probabilistic representation of a region as the conditional distribution in the Bayesian framework, which makes our tracker robust to local deformation and partial occlusion. The continuity of the objective function leads to a much faster numerical implementation. Very promising experimental results on some real-world sequences are presented to illustrate the performance of the presented algorithm.