Change detection is one of the most important problems in video segmentation. In conventional methods, predetermined thresholds are utilized to test the variation between frames. Although certain reasonings about the thresholds are provided, appropriate determination of these parameters is still problematic. We present a new approach to change detection from an optimization point of view. We model the video frames and the change detection map (CDM) as Markov random fields (MRFs), and formulate change detection into a problem of seeking the optimal configuration of the CDM. Under the MRF assumption, the optimal solution, in the sense of maximum a posteriori (MAP), is obtained by minimizing the energy function associated with the MRF which is designed by utilizing the prior knowledge of noise and contextual constraints on the video frames. An algorithm that computes the potentials and optimizes the solution is constructed by applying the mean field theory (MFT). The experimental results show that the new method detects changes accurately and is robust to noise.