COS 526 - Advanced Computer Graphics	Fall 2018

Assignment 1 - Poisson Image Editing

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:

1. 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.

2. 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.
3. 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.
4. Finally, copy the results back out of the matrix and into your output image. You should output both "cloning" and "seamless cloning" results for each input.
5. 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.
6. 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!
7. 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.

Submitting

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 here.

Note: 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.