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