In this paper, we present a probabilistic framework for automatic detection and tracking of objects. We address the data association problem by formulating the visual tracking as finding the best partition of a measurement graph containing all detected moving regions. In order to incorporate model information in tracking procedure, the posterior distribution is augmented with Adaboost image likelihood. We adopt a MRF-based interaction to model the inter-track exclusion. To avoid the exponential complexity, we apply Markov Chain Monte Carlo (MCMC) method to sample the solution space efficiently. We take data-oriented sampling driven by an informed proposal scheme controlled by a joint probability model combining motion, appearance and interaction among detected regions. Proposed data association method is robust and efficient, capable of handling extreme conditions with very noisy detection.