Homework 3: Seam carving

Examination:

You should write down answers to all questions, make an archive of that and your resulting source files and mail to me.

Deadline:

No strict deadline. My recommendation is to finish before lecture 8, so you can focus on the project part.

In this lab it is time to move to a pure Computational Photography problem: Seam carving. The task is to implement an algorithm for expanding or shrinking an image using seam carving. This task was selected since it is relatively simple and straight-forward, suitable for a homework, while still using methods similar to many other Computational Photography algorithms.

Lab files

This time there are no mandatory lab files. Homework 1 and 2 have provided you with some tools, and you are welcome to use whatever you prefer. However, the final result should be executed on the GPU. You may consider making a CPU version first. If you do, please take the chance to compare CPU and GPU performance. If you go straight to GPU, just measure the running time.

For simplicity, the default I ask you to try is to take a picture and narrow it to 75% of its width, taking away every 4th column.

Here is an image that can be suitable to work on, a test image from a seam carving paper (also available as png). Sorry about the odd size, but we are not going to do FFT or wavelets on it so it shouldn't matter. You are welcome to try other images but this is given as a default.

1. Calculate cost function

First, you need to calculate the cost function for each pixel. My suggestion is that you calculate this as a separate step and store it in an array as large as the image. The task is easily implemented in parallel.

What is your cost function? Well, you are welcome to experiment, but the standard cost function is the gradient magnitude.

2. Find cheapest paths

Then you need to search for the cheapest path. This is readily made in parallel by using one thread per column (since we look for vertical seams). Propagate suitable data downwards. Every thread loops row by row, and should examine the three neighbors in the previous row and select the cheapest.

3. Remove cheapest paths

Find the cheapest path by examining the data in the last row. (This can be made in parallel but the problem is very small so the gain is marginal if any.) Then you need to backtrack it to mark each pixel for removal. Finally, you remove the pixels by shifting all data sideways. This last step will affect much data and is suitable for parallel implementation.

Repeat this process until the desired number of columns have been removed.

Question: Which part of the algorithm takes most time?

 Question: Did you remove one column at a time, or mark many and remove all at once?

Question: What extra data did you need beyond the image and the cost function?

---

That's all for this homework. Submit your results to me.