This paper addresses the novel problem of automatically synthesizing an output
image from a large collection of different input images. The
synthesized image, called a digital tapestry, can be viewed as a
visual summary or a virtual 'thumbnail' of all the images in the input
collection. The problem of creating the tapestry is cast as a
multi-class labeling problem such that each region in the tapestry is
constructed from input image blocks that are salient and such that
neighboring blocks satisfy spatial compatibility.
This is formulated using a Markov Random Field and optimized via the
graph cut based expansion move algorithm. The standard expansion move algorithm can only
handle energies with metric terms,
while our energy contains non-metric (soft and hard) constraints.
Therefore we propose two novel contributions.
First, we extend the expansion move algorithm for energy functions
with non-metric hard constraints. Secondly, we modify it for
functions with ``almost'' metric soft terms, and show that it gives
good results in practice. The proposed framework was tested on several
consumer photograph collections, and the results are presented.