Description

1 Goals
Implement Poisson Editing for image cloning on the GPUs. Go fancy and implement faster algorithms to gain the bonus points.
2 Description
2.1 Image Cloning
Obviously there are rooms for improvement from this naive algorithm. In this assignment, we ask you to implement Poisson Editing, a computationally intensive but effective algorithm that is designed to seamlessly blend the background and target images by means of differential domain operations. The algorithm is described in more details later in this document, and we encourage you to read the original paper “Poisson Image Editing” from SIGGRAPH 2003 by P. Perez et al.
2.2 Function Signature
The function signature for this assignment is Listing 1. background and output are interlaced RGB images of size Wb ×Hb and range from 0 to 255. target is the same except that its size is Wt ×Ht. mask is the mask that contains only one color channel and we use 0.0f/255.0f to represent false/true.

1 void PoissonImageCloning(
2 const float *background,
3 const float *target,
4 const float *mask,
5 float *output,
6 const int wb, const int hb, const int wt, const int ht,
7 const int oy, const int ox
8 );

Listing 1: Function signature

(a) The background image Wb ×Hb.

(b) The target image which will be (c) The mask Wt ×Ht. pasted to the background, Wt ×Ht.
Figure 1: The input images of this assignment.
We will also assign the offset Oy,Ox, which means the offset of the target image in the background image (from the top-left corner). To generate the image shown in Figure 2 with the sample code, run the program according to Listing 2.

1 ./a.out img_background.ppm img_target.ppm img_mask.pgm 130 600 output.ppm

Listing 2: Execute your code
We use the very popular PGM/PPM image format, which can be edited by many image processing softwares. You can generate new test cases if you wish.
2.3 Poisson Editing
4Cb − (Sb + Eb) = 4Ct − (Nt + Wt + St + Et) + (Nb + Wb). (1)
2

Figure 2: A very naive and ineffective image cloning output.

(a) The values to be solved. (b) The corresponding target im-
age.
Figure 3: The gray nodes are the boundary (the black pixels in the mask). of Cb but only depends on it’s neighbors.
(2)
It is your job to generalize and figure out the equation for (1) when the locations of gray points change, and (2) when the point has less than four neighbors.
2.4 Acceleration
A cheaper solution is to use a hierarchical method. Start by solving the problem at a lower resolution, upsample, and then solve it at a higher resolution. You could do this at 1/8x, 1/4x, 1/2x and 1x scales with the nearest-neighbor upsampling algorithm, for example. Note that the number of iterations after each scale promotion would be less than solving the complete problem, because your lower-resolution solutions would look reasonably similar to the higher resolution ones already.
Cb,SOR′ = ωCb′ + (1 − ω)Cb. (3)
SOR is just a interpolation/extrapolation between current values and the values of the next iteration. Usually, we use ω < 1 to ensure the convergence while ω > 1 to accelerate the convergence. Also note that when ω = 1, this algorithm reduces to the original unoptimized algorithm. You could choose larger ω (e.g., 2) initially, and decrease it to 1 later after a few iterations.
3 Grading
1. 100 points, when you finish the baseline implementation (Jacobi, no acceleration).
2. Up to 10 bonus points, if you submit other interesting examples and results.
3. Up to 90 bonus points, if you accelerate and analyze your algorithm (write a report when you submit).
4 Submission
• Please submit the result in loseless PNG format lab3/results/***.png.
4

(a) 2 iterations (b) 20 iterations

(c) 200 iterations (d) 2000 iterations

(e) 6000 iterations (f) 20000 iterations
Figure 4: The convergence with Jacobi Iteration.

• Submit your source code lab3/lab3.cu. Again, you should only modify this file in the homework.
• We will test your code with the command listed in Listing 2. • If you implement hierarchical, SOR, or any other speed-up algorithm, you need to submit a report lab3/report.pdf to be considered for the bonus.
5 Hint

1 void PoissonImageCloning(
2 const float *background,
3 const float *target,
4 const float *mask,
5 float *output,
6 const int wb, const int hb, const int wt, const int ht,
7 const int oy, const int ox
8 ) {
9 // set up
10 float *fixed, *buf1, *buf2;
11 cudaMalloc(&fixed, 3*wt*ht*sizeof(float));
12 cudaMalloc(&buf1, 3*wt*ht*sizeof(float)); 13 cudaMalloc(&buf2, 3*wt*ht*sizeof(float));
14
15 // initialize the iteration
16 dim3 gdim(CeilDiv(wt,32), CeilDiv(ht,16)), bdim(32,16);
17 CalculateFixed<<<gdim, bdim>>>(
18 background, target, mask, fixed,
19 wb, hb, wt, ht, oy, ox
20 );
21 cudaMemcpy(buf1, target, sizeof(float)*3*wt*ht, cudaMemcpyDeviceToDevice);
22
23 // iterate
24 for (int i = 0; i < 10000; ++i) {
25 PoissonImageCloningIteration<<<gdim, bdim>>>(
26 fixed, mask, buf1, buf2, wt, ht
27 );
28 PoissonImageCloningIteration<<<gdim, bdim>>>(
29 fixed, mask, buf2, buf1, wt, ht
30 );
31 }
32
33 // copy the image back
34 cudaMemcpy(output, background, wb*hb*sizeof(float)*3, cudaMemcpyDeviceToDevice);
35 SimpleClone<<<gdim, bdim>>>(
36 background, buf1, mask, output,
37 wb, hb, wt, ht, oy, ox
38 );
39
40 // clean up
41 cudaFree(fixed);
42 cudaFree(buf1);
43 cudaFree(buf2);
44 }

Listing 3: Hint