Novelty detection or background subtraction methods for surveillance with a fixed camera typically model each pixel independently of its neighbours. More recently [11], a Markov Random Field (MRF) prior has been used to model consistencies among neighbouring foreground/background labels. Graph Cut methods have been used to find the maximum of the resulting posterior distribution for the labels for each frame. However, for increased efficiency and accuracy, we propose the use of loopy belief propagation. A major reason for increased efficiency is the fact that the output labels from the previous frame can be used as initialisation for the current frame in belief propagation. The Graph Cuts approach is empirically compared with both the "sumproduct" as well as "max-product" rules of belief propagation on real video sequences. Significantly, while the "max-product" rule has similar peak precision-recall performance as graph-cuts, the "sum-product" rule gives even better peak performance. This can be attributed to the fact that latter rule finds the marginals over the entire posterior distribution for the labels rather than just the maximum of the posterior which is more prone to noise.