Abstract: Ambiguity is the major difficulty in multi-object tracking problem due to the interactions of multiple targets (partial or complete occlusion). This ambiguity can be resolved by Markov random field (MRF) without explicit data association. However, the computational cost of general probabilistic inference algorithms of MRF is expensive. This paper presents a novel approach to this problem. Firstly, a new recursive Bayesian estimation framework, bootstrap importance sampling particle filter (BIS-PF), is devised, which has a "distributed-central-distributed" structure. The core of this framework is a suboptimal importance density which uses the observation at present time. So, it does not suffer from the curse of dimensionality. Secondly, a new Monte Carlo strategy is proposed, which uses bootstrap sampling to generate low-cost and high-quality samples, maintains multi-modality and decreases the number of likelihood computations. Thirdly, a new marginalization technology is presented, which uses an auxiliary variable sampler to obtain marginal samples and bootstrap based histogram for density estimation. The experiments show that the proposed method can track multiple targets in real-time, handle the complex interaction and maintain multi-modalities even the objects disappear.