Robust and accurate background segmentation is crucial for surveillance applications and is a key element in visual tracking, layer-based compression, and silhouette-based 3D reconstruction. In this paper, we present a novel spatial-temporal model that describes the appearance and dynamics of background scenes at multiple resolutions. We propose a time-dependent Markov Random Field (MRF) to represent the state of foreground and background at each pixel in the spatial-temporal pyramid. Pixels are linked spatially and temporally across frames. The probability of adding/deleting a foreground object is calculated by online learning algorithm and is used as prior information in computing foreground label. We use Gibbs Sampling to solve the MRF in a Maximum A Posterior (MAP) framework. Experimental results show that this real-time algorithm is able to segment the foreground object accurately from videos and more resilient to distractions such as imaging noise, illumination changes, camera shakes, and random motion in the scene.