Fluid Images

1 Introduction

Suppose that you 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 to intelligently decide what parts of the image to remove.

2 Energy

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

use the formula

\[energy(E) = \sqrt{xenergy^2 + yenergy^2}\]

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.

3 Seams

A vertical seam is a set of pixels, one on each row of the image, that are “connected” vertically. That is, any two pixels on adjacent rows are either vertically or diagonally adjacent. The energy of a seam is the sum of the energies of the pixels in the seam.

We will shrink the width of the image by removing vertical seams from the picture. Our algorithm consists of repeatedly finding the lowest-energy vertical seam and removing it from the image. Sometimes multiple seams may tie for the lowest energy. If this happens, remove the leftmost of those seams. The leftmost seam refers to the seam with the leftmost pixel in the top row. 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!

4 Support Code

You will be able to access the following types and functions:

• data Image

  An image object. Has the properties width and height, which specify the dimensions of the image in pixels, and the property img, which returns the underlying image itself. The image object preserves only the red, green, and blue channels, ignoring the alpha channel (corresponding to transparency).

• data Color:

  | color(red :: Number, green :: Number, blue :: Number)

  end

  Images can be thought of as 2-dimensional lists of colors. The representation of color that you will be using for this assignment is defined above.

• fun image-from-url(url :: String) -> Image

  Given a string indicating a URL, produces the image at that url.

• fun image-to-2d-color-list(image :: Image) -> List<List<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.

• fun image-from-2d-color-list(image :: List<List<Color>>) -> Image

  Consumes a two-dimensional list of colors in row-major order (as the output of image-to-2d-color-list) and returns an image object where each pixel’s color corresponds to that location in the two-dimensional list. Note that when testing and using this function in the REPL, it is best to bind the results to an identifier and access the fields individually. The image object will unfortunately not print properly in the REPL (sorry!).

5 The Assignment

For this assignment, implement the following function:

fun liquify(image-object :: Image, n :: Number)

that carves n seams from the given image.

Your solution should be reasonably efficient: it should not take exponential time! If you cannot liquify 10 seams in a few minutes from the test images we provide, you should rethink your implementation. 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 or no use of mutation. In particular, can you do it with no more mutation than memoization offers?

6 Test Images

• Dancers, Bangalore, India

• Carving, Belur, India

• Roof, British Museum, London, UK

• Grave, Edinburgh, UK

• Fallas, Valencia, Spain

• Chagall Window, Mainz, Germany

• Trafalgar Square, London, UK

• Tower, Üetliberg, Switzerland

• Uluru, Australia

• Ciudad de las Artes y las Ciencias, Valencia, Spain

All images © Shriram.

7 Analysis

Give a big-O analysis of your solution. Find an upper bound on the total number of possible vertical seams for 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, and of your chosen solution.

8 Template Files

Final Tests

Implementation Code

9 Handing In

Remember that this assignment requires you to hand in sweeps.

Like the last assignment, you will be submitting a separate test file.

To submit, return to the Captain Teach assignments page:

https://www.captain-teach.org/brown-cs019/assignments/

and click “Next Step” again. Upload a zip file containing your implementation, named fluid-images.arr, and your final-tests.arr. Then on the next step upload your analysis.