An output image formed from at least a portion of one or more input images may be automatically synthesized as a tapestry image. To determine which portion or region of each input image will be used in the image tapestry, the regions of each image may be labeled by one of a plurality of labels. The multi-class labeling problem of creating the tapestry may be resolved such that each region in the tapestry is constructed from one or more salient input image regions that are selected and placed such that neighboring blocks in the tapestry satisfy spatial compatibility. This solution may be formulated using a Markov Random Field and the resulting tapestry energy function may be optimized in any suitable manner. To optimize the tapestry energy function, an expansion move algorithm for energy functions may be generated to apply to non-metric hard and/or soft constraints.