To apply arithmetic coding to an image, one must order the pixels and supply 
the encoder and decoder with coding distributions to accompany the symbols 
as they are losslessly encoded and decoded.  Such distributions typically 
depend on previously encoded symbols.  This paper proposes ways to order 
pixels and supply coding distributions when the image is binary and modeled 
as a Markov random field (MRF).  One method, intended for an MRF based 
on an acyclic graph, uses belief propagation to efficiently compute the optimal 
coding distributions.  Another method, intended for an MRF with a cyclic 
graph, has a first stage that losslessly encodes a set of pixels, called a loop-
cutset, whose removal leaves an acyclic graph that can be encoded by the 
previous method in a second stage.  Several suboptimal, but efficiently 
computable, methods for encoding the loop-cutset are proposed.