Your assignment is to implement the

A naive cloning result is shown in Figure 3 of the paper (two foregrounds have been pasted, one after the other):

Your goal is to compute the gradient domain cloning result shown at right. This is done by solving a differential equation that tries to match the gradients of the result

You can implement gradient domain cloning by following the paper's derivation. The paper uses a quadratic energy (6) which is differentiated to give a linear system of equations (7). This system is defined over the unknowns which are colors at the matted pixels.

Our background

Here the neighborhood

Your program should first count the number of unknowns

`sparse`

or Python `scipy.sparse.lil_matrix`

. The entries of the matrices Notes:

- We suggest to first create arrays to map between unknown variables in Equation (7) and pixel coordinates. For the forward map, you can use an 1D array that maps from the index
*i*of an unknown variable in**u**to an (*x*,*y*) coordinate. For the reverse map, you can use an image that stores at each (*x*,*y*) pixel the index*i*of its corresponding unknown variable in**u**. - A next implementation step is to build the (sparse) matrix
**A**and vector**b**. You can do this by looping over all matted pixels*p*which are the equations of (7), that is the matrix and vector row number. - Your matrix
**A**should be symmetric, with 4s on the main diagonal and -1s or 0s off the main diagonal. - For very small masks (having only a few pixels of 1s in the mask) you can check that your matrix
**A**is correct by converting back to a dense matrix (Python:`A.todense()`

,`MATLAB: full(A)`

). Do not do this for large masks or you will run out of memory. - Example images: background, foreground, matte. For debugging you may wish to crop out a small region to reduce the number of variables.
- As a sanity test, you can run your program on the same image for both foreground and background. This should give back the unaltered input image.

`yourname_project2.zip`

. In the root directory place a `README.txt`

file that is your writeup, which should include:
- Your name
- UVA computing ID
- Operating system
- Note any unfinished parts of the assignment, and any extra credit you did

`part1`

in your zip containing:- Source for your gradient domain compositing implementation.
- Add to your README writeup a brief description of how to run the program.
- Include the result of your gradient-domain compositing (
`result.png`

) with the provided background, foreground, and matte images. You can additionally include results on other images.