# Seam Carving

Suppose that we are given an image and wish to shrink its width by a given number of pixels without changing its height. The simplest strategy is simply to scale the image, but this may introduce undesirable distortions. Another option is to crop the edges of the image, but this is unacceptable if the edges contain important information.

In this assignment, you will implement a more advanced algorithm — seam carving — to intelligently decide what parts of the image to remove.

## Energy

Given an image, we first compute the "energy" of each pixel, which measures how much that pixel stands out from its surroundings and gives us a rough idea of its importance.

To compute the energy of a pixel E surrounded by pixels A through I,

```        A B C
D E F
G H I
```

use the formula

```        energy(E) = sqrt(xenergy2 + yenergy2)
```

where

```        xenergy = a + 2d + g - c - 2f - i
yenergy = a + 2b + c - g - 2h - i
```

and each lowercase letter represents the brightness (sum of the red, blue, and green values) of the corresponding pixel.

To compute the energy of edge pixels, you should pretend that the image is surrounded by a 1 pixel wide border of black pixels (with 0 brightness).

You are welcome to experiment with different energy functions, but the solution you hand in must use the formula above.

## Seams

We will shrink the width of the image by removing vertical seams from the picture. A vertical seam is a set of pixels, one on each row of the image, which are connected vertically. That is, any two pixels on adjacent rows are either orthogonally or diagonally adjacent. The energy of a seam is the sum of the energies of the pixels in the seam.

Seam carving is the process of repeatedly finding the lowest-energy vertical seam and removing it from the image. Sometimes mutliple seams may tie for the lowest energy. If this happens, remove the leftmost of those seams. Note that once a seam has been removed, the image has changed, so energies must be recomputed.

Think about why we remove lowest-energy seams rather than simply removing the lowest-energy pixel from each row. Better still, try it out, and you'll see the difference for yourself!

## Part 1

Implement the following function:

• `seam-carve : (Image\$ Integer\$ -> Image\$)`
Given an image, shrink the image's width by removing the number of vertical seams specified by the second argument.

Your solution should be reasonably efficient (do not use an exponential-time algorithm). If you cannot carve 10 seams in a few minutes from the test images we provide, you should rethink your implementation. Bear in mind that our fastest implementation carves seams at a rate of roughly one per second from those images. You do not need to be this fast to receive full credit, but it is a good benchmark.

You should be able to do this assignment with minimal use of mutation. In particular, can you do it with no more mutation than memoization offers?

You will need to require `seam-carving-support-v2.rkt` for this assignment. By doing so, you will be able to use:

• `(define-struct: color ([red : Integer\$] [green : Integer\$] [blue : Integer\$]))`
describes color in terms of their red, green, and blue values from 0 to 255.

• `image->2d-color-list : (Image\$ -> (Listof: (Listof: Color\$)))`
Given an image, returns a list of lists containing the color corresponding to each pixel in the image. The output is in row-major order, so the first sublist corresponds to the top row of the image.

• `2d-color-list->image : ((Listof: (Listof: Color\$)) -> Image\$)`
Consumes a two-dimensional list of colors in row-major order (as the output of `image->2d-color-list`) and returns an image where each pixel's color corresponds to that location in the two-dimensional list.

• `time : (Expr\$ -> Any\$)`
Returns the result of evaluating the expression, and prints information on how much time was spent on the evaluation:

• Milliseconds of CPU time needed to evaluate expr
• Milliseconds of real time needed to evaluate expr
• Milliseconds of CPU time spent on garbage collection during evaluation

You will also gain access to a `check-image` function, which behaves as `check-expect` but is usable for comparing images. Note that `check-expect` cannot compare images, so you will need to use `check-image` in your testing.

We provide several images to test on (see below), but you should also use some of your own images. The bigger the image the slower your tests will run, but you should definitely run at least a couple larger tests.

## Part 2

Give a big-O analysis of your solution. Also give a big-O bound for the number of different vertical seams in an image in terms of its width and height. Use this bound to find the time complexity of the naive solution which computes the energy for every possible seam.

## Part 3 – Extra Credit

If you finish seam carving early, and you feel up for an extra challenge, implement a second different solution of reasonable efficiency, then use one as an oracle for testing the other.

Choosing not to do the extra credit will not adversely affect your grade, but if you haven't done as well as you'd have liked in the course and want to make up some ground, here's a good way to accomplish it.

## What to turn in:

• A Racket file, `seam-carving.rkt`, containing your first solution.
• (optional) A Racket file, `oracle.rkt`, containing a second different solution to the problem (as described by the extra credit section) and your oracle for testing.
• A file, `readme.[txt,pdf,doc]`, containing short descriptions of your seam carving algorithm and the optimizations you used. Give a brief example of each optimization showing how it helped. If you choose to do the extra credit, you should also include a brief description of your second algorithm and a short explanation of your oracle.
• A file, `analysis.[txt,pdf,doc`] with your answers for Part 2.

As always, these files must be in plain text, pdf, or, if you really must, Word format. If you use Word, we will accept only Word 2003 (`.doc`) files. If you are using Word 2007, you should export to a pdf. We will not accept Word 2007 (`.docx`) files because we cannot read them.