Advanced Topics in Computer Graphics
Exercise 1
Poisson Image Editing



The exercise consists of two parts:

  1. Implementation of smooth image completion
  2. Implementation of Poisson seamless cloning

See also:

The presentation given in class advgraphics-ex1.ppt (1.9MB)

  The "Poisson Image Editing/SIGGRAPH 2003" paper


Check out the Q&A section below.


Online exercise solution (with source-code)

Zip, win32 binary (478KB)

 Zip, win32 source  for Visual Studio 2003/2005/2008/2010 (3.3MB)


Note: To use my pre-compiled version of TAUCS with Visual Studio 2003/2005/2008, you must set the following in all your dependent projects:

Part1: Smooth image completion

Write a program that reads a color image with missing areas (denoted by a special color C). The program should fill the missing areas smoothly as described in class.

The usage should be as following:

ex1 -complete <input image> Cr Cg Cb <output file>

Where:    <input image>    the input image filename

             Cr Cg Cb            the special unknown color value

          <output file>    the output image filename

Your program should be able to read at least one of the following common formats: bmp, jpeg, png. If the program file is run without parameters, please print the usage explanation and which formats your program handles. The result should be written to the specified output file in any of the above formats.

Include at least three non-trivial examples in your results section. Nice and original images are preferred (see General Guidelines below).

1.1 Example results

(a) line sampled image
(b) completed/estimated image from (a)
(c) the ground truth

Part 2: Poisson seamless cloning

Write a program that performs Poisson seamless cloning as explained in class.
Its usage should be as follows:

ex1 -clone <source image> <source mask> <target image> x y <output file>

Where:    <input image>    is the input image filename

          <source mask>    a black and white image, encoding the area to clone (white)

          <target image>   the target image filename

          x y              the offset of clone area in the target image

          <output file>    the output filename

Again, your program should be able to read at least one of the common image formats. If run without parameters, the program should print a "usage" message and which image formats it can recognize. Your program should clone the area of interest from the source image (denoted by the mask image) onto the target image at the specified offset, saving the result at the specified output filename.

In the documentation (see below) please discuss the quality of the algorithm by answering the following questions: when do you think it should perform well, when not, and why? Include examples (good and bad) that back up your conclusions. Try to suggest a solution to the problems you see with the current algorithm.

2.1 Example results



(a) fighter jet source image and source mask(b) landscape target image
(c) fighter jet composite



(a) bear source image and source mask(b) pool target image(c) bear Poisson composite result

Libraries and useful links

You are welcome to use any open-source image library and sparse linear algebra solver library.
We recommend the following libraries:


#include "taucs/taucsaddon.h"  // available from the above zip-file
// Create the matrix, specifying the expected (maximum) number of non-zero elements per column
taucs_ccs_matrix *pA = taucs_ccs_create(N,N,5*N,TAUCS_DOUBLE);
double* b = new double[N]; // the right hand side of the equation Ax=b
// Fill the non-zero elements of A (CCS order, check TAUCS documentation)
// Allocate the result unknown vector
double* x = new double[N];
// Run the solver, "LU" means no symmetry is required
char* options[] = { "taucs.factor.LU=true", NULL };
if (taucs_linsolve(pA, NULL, 1, x, b, options, NULL) != TAUCS_SUCCESS) {
    printf("Solver failed\n");

General guidelines

What to submit

  1. The code, in electronic form, as described below.
  2. At least 3 working examples, for each part of the project. Submit them together with the code. Note: a bonus of 5 points will be given for especially nice examples. Visual quality is important in graphics!
  3. Hardcopy of the documentation (do not print the code) or a softcopy (.rtf or .pdf please). Explain what you have implemented, describe in short the main parts of your programs and the modules, if any. Also, please mention any nuances of usage, such as the file formats accepted by your program. In addition, include the answers to the questions posed in Part 2 (Poisson seamless cloning).

Electronic submission guidelines
You may implement the exercise in C or C++ under Windows or Linux or using Matlab. Submit a diskette/CD or a zip file with:


Q: How did I get the equation (1) xi-w+xi-1-4xi+xi+1=-f(x,y+1) on slide 14
A: For a rectangular hole with width w and height h, a missing pixel at (x,y) is represented by the unknown variable xi (i=y*w+x). Let i be the index of the current pixel (x,y), so our basic equation (2) fx,y-1+fx-1,y-4fx,y+fx+1,y+fx,y+1=0 transforms into xi-w+xi-1-4xi+xi+1+xi+w=0, since the pixel on top (x,y-1) is indexed via i-w. Assuming that the pixel below (x,y+1) is known (outside of the missing region) then equation (2) transforms into (3) xi-w+xi-1-4xi+xi+1+fx,y+1=0 (no variable is allocated for known pixels), by moving sides we get the expected equation (1).

Q: If the hole is not rectangular , and xi is the unknown variable at pixel (x,y) in the image how can you know the xi-w and xi+w?
A: Any one-to-one mapping from pixel (x,y) to the variable index i will do. Maintaining regularity will accelerate the sparse solver but it is not a must. The simplest mapping is via building a hashtable.

Q: Links for CCS (Compressed Column Storage) format for sparse matrices.
A: Check out link1 and link2

Important Updates:

15-05-05    One week extension to the deadline. Submission is due on the 24/05/2005.

09-05-05    Corrected the example equation on slide 14: xi-w+xi-1-4xi+xi+1=-f(x,y+1), the minus sign on the right hand side was missing.

03-05-05    I strongly suggest that you use the pre-compiled version of taucs. The pre-compiled version is based on a newer version of taucs.

21-04-05    Updated the program parameters for both exercises, adding -complete/-clone to comply with description in presentation


Good luck!

Back to my homepage