COS 526 - Advanced Computer Graphics
Assignment 1 - Poisson Image Editing
Due Mon, Oct. 8
The goal of this assignment is to implement the "Seamless Cloning" algorithm
described in the Poisson Image Editing paper
by Pérez et al. Please read the paper and make sure you understand
equations (7) and (11), which define the linear system that you need to solve.
Here is a suggested order in which to implement things:
- Write a simple program that reads in three images. Two of the images
(call them "source" and "destination") are just regular color images.
The third is a "mask" that defines which pixels in the source are to be
inserted into the destination. This is ideally a binary image, with black
meaning "leave the destination alone" and white meaning "replace with the
source", though if you use lossy image formats such as JPG, you'll need to
threshold the image first.
There are some images here to get you started.
Note that these have been adjusted to all be the same size. You should assume
this for starters, though later on you will relax this assumption.
For your very first program, just replace the destination image pixels with
source, at locations where the mask is "white". You should get results
along the lines of the non-seamless cloning in the paper. Write the
results out to a new image.
You may use any programming language you'd like. If you're using C or C++,
you may download simple image I/O code here.
This uses the standard open-source libjpeg
and libpng libraries,
which are available for most systems. For Python, consider using
Pillow for Image I/O. For other
languages, use whatever Image I/O functionality you can find on the web,
or have used in other classes.
- The next stage is to set up for solving the linear system of equations.
There will be one equation for each pixel in the mask, so you'll need some
data structure that maps from pixel (x,y) coordinates to which variable in
your linear system corresponds to it. You'll also need to be able to identify
which pixels are on the "boundary" - they are not within the mask, but have
neighbors that are within the mask. These pixels do not have their own
equations, but are treated specially by their neighbors.
- Next, you need to set up and solve the linear system. To make things
scalable, we suggest you use a sparse solver. For C/C++, consider using the
GNU Scientific Library (GSL).
It has a sparse
matrix datatype, and can solve
sparse linear systems. For Python, the SciPy
package contains sparse matrices
and sparse solvers.
If you're using other languages, you should be able to find linear algebra
libraries, though perhaps not sparse solvers. In that case, feel free
to use the "dense" routines, though you may be memory-limited in how big a
system you can solve. Be sure to use "iterative" instead of "direct" solvers,
and solve the system separately for each of the R, G, and B color channels.
- Finally, copy the results back out of the matrix and into your output
image. You should output both "cloning" and "seamless cloning" results for
- Now, relax one of the assumptions made above - that all the inputs are
the same size. In particular, the "mask" should still be the same size as
the "destination", but the source may differ in size. You will also need to
take as input the (x,y) offset of the source relative to the target. See if
you can work with these images.
- Once you have the basic seamless cloning working, implement (at least) one
of the extensions illustrated in figures 5 through 11 of the paper. Or come
up with your own creative extension!
- Create a writeup (in HTML) briefly describing your implementation
(including which external libraries you used and how to build/run your code)
and showing off plenty of pretty results.
This assignment is due Monday, October 8.
Please submit a single .zip file containing your code and writeup.
The Dropbox link to submit the assignment is
Feel free to use external libraries for image input/output and solving linear
systems, but obviously you shouldn't use external code that implements
Poisson Image Editing itself. Please acknowledge in your writeup all outside
sources that you consulted.
smr at princeton edu