p2-cv
EECS 280 Project 2: Computer Vision
Due 8:00pm EST Wednesday September 27th, 2023. You may work alone or with a partner
(partnership guidelines).
Fall 2023 release.
Introduction
Build an image resizing program using a seam-carving algorithm.
The learning goals of this project include Testing, Debugging, Pointers, Arrays, Strings, Streams, IO,
and Abstract Data Types in C. You’ll gain practice with C-style pointers, arrays, and structs.
When you’re done, you’ll have a program that uses seam carving for content-aware resizing of
images. The algorithm works by finding and removing “seams” in the image that pass through the
least important pixels. For a quick introduction, check out this video.
Original Image: 479x382 Resized: 300x382 Resized: 400x250
Setup
Set up your visual debugger and version control, then submit to the autograder.
Visual debugger
During setup, name your project p2-cv . Use this starter files link:
https://eecs280staff.github.io/p2-cv/starter-files.tar.gz
VS Code Visual Studio Xcode
After setting up your visual debugger, rename main.cpp to resize.cpp . You should end up with a
folder with starter files that looks like this. You may have already renamed files like
Matrix.cpp.starter to Matrix.cpp .
Here’s a short description of each starter file.
File Description
Matrix.hpp Interface specification for the Matrix module.
Image.hpp Interface specification for the Image module.
processing.hpp
Specification of image processing functions that are
pieces of the seam carving algorithm.
Matrix.cpp.starter Starter code for the Matrix module.
Image.cpp.starter Starter code for the Image module.
$ ls
Image.cpp.starter dog.ppm
Image.hpp dog_4x5.correct.ppm
Image_public_test.cpp dog_cost_correct.txt
Image_test_helpers.cpp dog_energy_correct.txt
Image_test_helpers.hpp dog_left.correct.ppm
Image_tests.cpp.starter dog_removed.correct.ppm
Makefile dog_right.correct.ppm
Matrix.cpp.starter dog_seam_correct.txt
Matrix.hpp horses.ppm
Matrix_public_test.cpp horses_300x382.correct.ppm
Matrix_test_helpers.cpp horses_400x250.correct.ppm
Matrix_test_helpers.hpp horses_cost_correct.txt
Matrix_tests.cpp.starter horses_energy_correct.txt
crabster.ppm horses_left.correct.ppm
crabster_50x45.correct.ppm horses_removed.correct.ppm
crabster_70x35.correct.ppm horses_right.correct.ppm
crabster_cost_correct.txt horses_seam_correct.txt
crabster_energy_correct.txt processing.cpp.starter
crabster_left.correct.ppm processing.hpp
crabster_removed.correct.ppm processing_public_tests.cpp
crabster_right.correct.ppm resize.cpp
crabster_seam_correct.txt unit_test_framework.hpp
File Description
processing.cpp.starter Starter code for the processing module.
Matrix_tests.cpp.starter Starter code for unit testing the Matrix module.
Image_tests.cpp.starter Starter code for unit testing the Image module.
Matrix_public_test.cpp Public tests for the Matrix module.
Image_public_test.cpp Public tests for the Image module.
processing_public_tests.cpp
Tests for the processing module and seam carving
algorithm.
Matrix_test_helpers.hpp
Matrix_test_helpers.cpp
Image_test_helpers.hpp
Image_test_helpers.cpp
Helper functions for unit tests
unit_test_framework.hpp A simple unit-testing framework
dog.ppm , crabster.ppm ,
horses.ppm
Sample input image files.
Several _correct.txt files.
Several .correct.ppm files.
Sample (correct) output files used by the
processing_public_tests program.
Makefile Helper commands for building and submitting
Version control
Set up version control using the Version control tutorial.
After you’re done, you should have a local repository with a “clean” status and your local repository
should be connected to a remote GitHub repository.
1
2
3
4
5
6
7
8
$ git status
On branch main
Your branch is up-to-date with 'origin/main'.
nothing to commit, working tree clean
$ git remote -v
origin https://github.com/awdeorio/p2-cv.git (fetch)
origin https://githubcom/awdeorio/p2-cv.git (push)
You should have a .gitignore file (instructions).
Group registration
Register your partnership (or working alone) on the Autograder using the direct link in the
Submission and Grading section. Then, submit the code you have.
Matrix Module
Create a Matrix abstract data type (ADT). Write implementations in Matrix.cpp for the functions
declared in Matrix.hpp .
Run the public Matrix tests.
Complete the EECS 280 Unit Test Framework Tutorial.
Write tests for Matrix in Matrix_tests.cpp using the unit test framework. You’ll submit these
tests to the autograder. See the Unit Test Grading section.
Submit Matrix.cpp and Matrix_tests.cpp to the Autograder using the link in the Submission
and Grading section.
Setup
Rename these files (VS Code (macOS), VS Code (Windows), Visual Studio, Xcode, CLI):
Matrix.cpp.starter -> Matrix.cpp
Matrix_tests.cpp.starter -> Matrix_tests.cpp
The Matrix tests should compile and run. Expect them to fail at this point because the Matrix.cpp
starter code contains function stubs.
1
2
3
4
5
$ pwd
/Users/awdeorio/src/eecs280/p2-cv
$ head .gitignore
# This is a sample .gitignore file that's useful for C++ projects.
...
1
2
$ make Matrix_public_test.exe
$ ./Matrix_public_test.exe
1
2
$ make Matrix_tests.exe
$ ./Matrix_tests.exe
Configure your IDE to debug either the public tests or your own tests.
Public tests Your own tests
VS Code
(macOS)
Set program name to:
${workspaceFolder}/Matrix_public_test.exe
Set program name to:
${workspaceFolder}/Matrix_
VS Code
(Windows)
Set program name to:
${workspaceFolder}/Matrix_public_test.exe
Set program name to:
${workspaceFolder}/Matrix_
XCode
Include compile sources:
Matrix_public_test.cpp , Matrix.cpp ,
Matrix_test_helpers.cpp
Include compile sources:
Matrix_tests.cpp , Matrix.c
Matrix_test_helpers.cpp
Visual
Studio
Exclude files from the build:
Include Matrix_public_test.cpp
Exclude Matrix_tests.cpp ,
Image_public_test.cpp ,
Image_tests.cpp ,
processing_public_tests.cpp ,
resize.cpp (if present), main.cpp (if
present)
Exclude files from the build:
Include Matrix_tests.cp
Exclude Matrix_public_t
Image_public_test.cpp ,
Image_tests.cpp ,
processing_public_test
resize.cpp (if present),
(if present)
Interface
A matrix is a two-dimensional grid of elements. For this project, matrices store integer elements and
we will refer to locations by row/column. For example, here’s a 3x5 matrix.
The Matrix.hpp file defines a Matrix struct to represent matrices and specifies the interface for
functions to operate on them. The maximum size for a Matrix is given by constants in
Matrix.hpp . Dimensions of 0 are not allowed.
1
2
3
4
$ make Matrix_public_test.exe
$ ./Matrix_public_test.exe
$ make Matrix_tests.exe
$ ./Matrix_tests.exe
To create a Matrix , first allocate storage and then use an initializer function.
The new operator allocates an object in dynamic memory, giving us a pointer to the newly created
object. We will use dynamic memory to store Matrix and Image objects, since they are too large
to be created as local variables on the stack.
Once a Matrix is initialized, it is considered valid. Now we can use any of the functions declared in
Matrix.hpp to operate on it.
Access to individual elements in a Matrix is provided through a pointer to their location, which can
be retrieved through a call to Matrix_at . To read or write the element, you just dereference the
pointer.
The RMEs in Matrix.hpp give a full specification of the interface for each Matrix function.
When a Matrix object is no longer needed, its storage should be deallocated with the delete
operator.
Implementation
The Matrix struct looks like this:
Matrix stores a 2D grid of numbers in an underlying one-dimensional array.
1
2
Matrix* m = new Matrix; // allocate storage in dynamic memory
Matrix_init(m, 100, 100); // initialize it as a 100x100 matrix
1
2
3
4
5
6
7
8
Matrix_fill(m, 0); // fill with zeros
// fill first row with ones
for (int c = 0; c < Matrix_width(m); ++c) {
*Matrix_at(m, 0, c) = 1; // see description below
}
Matrix_print(m, cout); // print matrix to cout
delete m;
1
2
3
4
5
struct Matrix {
int width;
int height;
int data[MAX_MATRIX_WIDTH * MAX_MATRIX_HEIGHT];
};
Interface Implementation
Each of the functions in the Matrix module takes a pointer to the Matrix that is supposed to be
operated on. In your implementations of these functions, you should access the width , height ,
and data members of that Matrix , but this is the only place you may do so. To all other code, the
individual members are an implementation detail that should be hidden behind the provided
interfaces for the Matrix module.
Your Matrix_at functions will need to perform the appropriate arithmetic to convert from a
(row,column) pair to an index in the array, and your Matrix_row and Matrix_column functions will
need to go in the other direction. None of these functions require a loop, and you’ll find your
implementation will be very slow if you use a loop.
There are two versions of the Matrix_at function to support element access for both const and
non-const matrices. The constness of the pointer returned corresponds to the Matrix passed in.
The implementations for these will be identical.
Remember that you may call any of the functions in a module as part of the implementation of
another, and in fact you should do this if it reduces code duplication. In particular, no function
other than Matrix_row , Matrix_column , and the two versions of Matrix_at should access
the data member directly – call one of these functions instead. (However, you will not be able
to call one version of Matrix_at from the other due to the differences in constness.)
Pro-tip: Use assert() to check the conditions in the REQUIRES clause. If other code
breaks the interface, that’s a bug and you want to know right away! Here’s an example.
Some things can’t be checked, for example that a pointer points to a valid Matrix .
1
2
3
4
5
6
7
8
9
10
// REQUIRES: mat points to a valid Matrix
// 0 <= row && row < Matrix_height(mat)
// 0 <= column && column < Matrix_width(mat)
// EFFECTS: Returns a pointer to the element in
// the Matrix at the given row and column.
int* Matrix_at(Matrix* mat, int row, int column) {
assert(0 <= row && row < mat->height);
assert(0 <= column && column < mat->width);
// ...
}
Testing
Test your Matrix functions to ensure that your implementations conform to specification in the RME.
Heed the Small Scope Hypothesis. There is no need for large Matrix structs. (Other than an as
edge case for max size.) Think about what makes tests meaningfully different.
Create Matrix objects with the new operator, and then destroy them with delete when you are
done.
Do not create a Matrix on the stack. It’s too large.
Respect the interfaces for the modules you are testing. Do not access member variables of the
structs directly. Do not test inputs that break the REQUIRES clause for a function.
Sometimes you need to use one Matrix one function while testing another. For example, you need
Matrix_at to test Matrix_fill .
1
2
3
4
5
TEST(test_fill_basic) {
Matrix *mat = new Matrix;
// ...
delete mat;
}
1
2
3
TEST(bad_example) {
Matrix mat; // BAD! TOO BIG FOR STACK
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TEST(test_bad) {
Matrix *mat = new Matrix;
const int width = 3;
const int height = 5;
const int value = 42;
Matrix_init(mat, 3, 5);
Matrix_fill(mat, value);
for(int r = 0; r < height; ++r) {
for(int c = 0; c < width; ++c) {
ASSERT_EQUAL(mat.data[r][c], value); // BAD! DO NOT access member
directly
}
}
delete mat;
}
Use an ostringstream to test Matrix_print() .
In your Matrix tests, you may use the functions provided in Matrix_test_helpers.hpp . Do not
use Image_test_helpers.hpp in your Matrix tests.
Image Module
Create an Image abstract data type (ADT). Write implementations in Image.cpp for the functions
declared in Image.hpp .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TEST(test_fill_basic) {
Matrix *mat = new Matrix;
const int width = 3;
const int height = 5;
const int value = 42;
Matrix_init(mat, 3, 5);
Matrix_fill(mat, value);
for(int r = 0; r < height; ++r) {
for(int c = 0; c < width; ++c) {
ASSERT_EQUAL(*Matrix_at(mat, r, c), value);
}
}
delete mat;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include
TEST(test_matrix_print) {
Matrix *mat = new Matrix;
Matrix_init(mat, 1, 1);
*Matrix_at(mat, 0, 0) = 42;
ostringstream expected;
expected << "1 1\n"
<< "42 \n";
ostringstream actual;
Matrix_print(mat, actual);
ASSERT_EQUAL(expected.str(), actual.str());
delete mat;
}
Run the public Image tests.
Write tests for Image in Image_tests.cpp using the Unit Test Framework. You’ll submit these tests
to the autograder. See the Unit Test Grading section.
Submit Image.cpp and Image_tests.cpp to the Autograder using the link in the Submission and
Grading section.
Setup
Rename these files (VS Code (macOS), VS Code (Windows), Visual Studio, Xcode, CLI):
Image.cpp.starter -> Image.cpp
Image_tests.cpp.starter -> Image_tests.cpp
The Image tests should compile and run. Expect them to fail at this point because the Image.cpp
starter code contains function stubs.
Write tests for Image in Image_tests.cpp using the Unit Test Framework. You’ll submit these tests
to the autograder. See the Unit Test Grading section.
Configure your IDE to debug either the public tests or your own tests.
Public tests Your own tests
VS Code
(macOS)
Set program name to:
${workspaceFolder}/Image_public_test.exe
Set program name to:
${workspaceFolder}/Image_te
VS Code
(Windows)
Set program name to:
${workspaceFolder}/Image_public_test.exe
Set program name to:
${workspaceFolder}/Image_te
1
2
$ make Image_public_test.exe
$ ./Image_public_test.exe
1
2
$ make Image_tests.exe
$ ./Image_tests.exe
1
2
3
4
$ make Image_public_test.exe
$ ./Image_public_test.exe
$ make Image_tests.exe
$ ./Image_tests.exe
1
2
$ make Image_tests.exe
$ ./Image_tests.exe
Public tests Your own tests
XCode
Include compile sources:
Image_public_test.cpp , Matrix.cpp ,
Image.cpp , Matrix_test_helpers.cpp ,
Image_test_helpers.cpp
Include compile sources:
Image_tests.cpp , Matrix.cpp
Image.cpp ,
Matrix_test_helpers.cpp ,
Image_test_helpers.cpp
Visual
Studio
Exclude files from the build :
Include Image_public_test.cpp
Exclude Image_tests.cpp ,
Matrix_public_test.cpp ,
Matrix_tests.cpp ,
processing_public_tests.cpp ,
resize.cpp (if present), main.cpp (if
present)
Exclude files from the build:
Include Image_tests.cpp
Exclude Image_public_tes
Matrix_public_test.cpp ,
Matrix_tests.cpp ,
processing_public_tests
resize.cpp (if present),
main.cpp (if present)
Interface
An Image is similar to a Matrix , but contains Pixel s instead of integers. Each Pixel includes
three integers, which represent red, green, and blue (RGB) color components. Each component
takes on an intensity value between 0 and 255. The Pixel type is considered “Plain Old Data”
(POD), which means it doesn’t have a separate interface. We just use its member variables directly.
Here is the Pixel struct and some examples:
struct Pixel {
int r; // red
int g; // green
int b; // blue
}
(255,0,0) (0,255,0) (0,0,255)
(0,0,0) (255,255,255) (100,100,100)
(101,151,183) (124,63,63) (163,73,164)
Below is a 5x5 image and its conceptual representation as a grid of pixels.
The maximum size for an Image is the same as the maximum size for a Matrix . Dimensions of 0
are not allowed. To create an Image , first allocate storage and then use an initializer function.
There are several initializer functions, but for now we’ll just use the basic one.
Once an Image is initialized, it is considered valid. Now we can use any of the functions declared in
Image.hpp to operate on it.
To read and write individual Pixel s in an Image , use the Image_get_pixel and
Image_set_pixel functions, respectively.
The RMEs in Image.hpp give a full specification of the interface for each Image function.
When an Image object is no longer needed, its storage should be deallocated with the delete
operator.
PPM Format
The Image module also provides functions to read and write Image s from/to the PPM image
format. Here’s an example of an Image and its representation in PPM.
Image Image Representation in PPM
1
2
Image* img = new Image; // allocate storage in dynamic memory
Image_init(img, 5, 5); // initialize it as a 5x5 image
1
2
3
4
5
6
7
8
9
10
11
12
Pixel um_blue = { 0, 46, 98 };
Pixel um_maize = { 251, 206, 51 };
Image_fill(img, um_blue); // fill with blue
// fill every other column with maize to make stripes
for (int c = 0; c < Image_width(img); ++c) {
if (c % 2 == 0) { // only even columns
for (int r = 0; r < Image_height(img); ++r) {
Image_set_pixel(img, r, c, um_maize);
}
}
}
delete img;
P3
5 5
255
0 0 0 0 0 0 255 255 250 0 0 0 0 0 0
255 255 250 126 66 0 126 66 0 126
66 0 255 255 250
126 66 0 0 0 0 255 219 183 0 0 0
126 66 0
255 219 183 255 219 183 0 0 0 255
219 183 255 219 183
255 219 183 0 0 0 134 0 0 0 0 0 255
219 183
The PPM format begins with these elements, each separated by whitespace:
P3 (Indicates it’s a “Plain PPM file”.)
WIDTH HEIGHT (Image width and height, separated by whitespace.)
255 (Max value for RGB intensities. We’ll always use 255.)
This is followed by the pixels in the image, listed with each row on a separate line. A pixel is written
as three integers for its RGB components in that order, separated by whitespace.
To write an image to PPM format, use the Image_print function that takes in a std::ostream .
This can be used in conjunction with file I/O to write an image to a PPM file. The Image_print
function must produce a PPM using whitespace in a very specific way so that we can use
diff to compare your output PPM file against a correct PPM file. See the RME for the full details.
To create an image by reading from PPM format, use the Image_init function that takes in a
std::istream . This can be used in conjunction with file I/O to read an image from a PPM file.
Because we may be reading in images generated from programs that don’t use whitespace in the
same way that we do, the Image_init function must accommodate any kind of whitespace used to
separate elements of the PPM format (if you use C++ style I/O with >> , this should be no problem).
Other than variance in whitespace (not all PPM files put each row on its own line, for example), you
may assume any input to this function is in valid PPM format. (Some PPM files may contain
“comments”, but you do not have to account for these.)
See Working with PPM Files for more information on working with PPM files and programs that can
be used to view or create them on various platforms.
Implementation
The Image struct looks like this:
The Interface for Image makes it seem like we have a grid of Pixel s, but the Image struct
actually stores the information for the image in three separate Matrix structs, one for each of the
RGB color channels. There are no Pixel s in the underlying representation, so your
Image_get_pixel function must pack the RGB values from each color Matrix into a Pixel to be
returned. Likewise, Image_set_pixel must unpack RGB values from an input Pixel and store
them into each Matrix .
Each of the functions in the Image module takes a pointer to the Image that is supposed to be
operated on. When you are writing implementations for these functions, you may be tempted to
access members of the Matrix struct directly (e.g. img->red_channel.width , img-
>green_channel.data[x] ). Don’t do it! They aren’t part of the interface for Matrix , and you should
not use them from the outside. Instead, use the Matrix functions that are part of the interface (e.g.
Matrix_width(&img->red_channel) , Matrix_at(&img->green_channel, r, c) ).
In your implementation of the Image_init functions, space for the Matrix members will have
already been allocated as part of the Image . However, you still need to initialize these with a call to
Matrix_init to ensure they are the right size!
The Image struct contains width and height members. These are technically redundant, since
each of the Matrix members also keeps track of a width and height, but having them around
should make the implementations for your functions easier to read.
Respect the Interfaces!
Our goal is to use several modules that work together through well-defined interfaces, and to keep
the implementations separate from those interfaces. The interfaces consist of the functions we
provide in the .hpp file for the module, but NOT the member variables of the struct. The member
variables are part of the implementation, not the interface!
This means you may access member variables directly (i.e. using . or -> ) when you’re writing
code within their module, but never from the outside world! For example, let’s consider the Image
module. If I’m writing the implementation of a function inside the module, like Image_print , it’s fine
to use the member variable height directly:
1
2
3
4
5
6
7
struct Image {
int width;
int height;
Matrix red_channel;
Matrix green_channel;
Matrix blue_channel;
};
This is fine, because we assume the person who implements the module is fully aware of all the
details of how to use height correctly. However, if I’m working from the outside, then using
member variables directly is very dangerous. This code won’t work right:
The problem is that we “forgot” about initializing the width and height of the Matrix structs that
make up each color channel in the image. Instead, we should have used the Image_init function
from the outside, which takes care of everything for us.
Here’s the big idea - we don’t want the “outside world” to have to worry about the details of the
implementation, or even to know them at all. We want to support substitutability, so that the
implementation can change without breaking outside code (as long as it still conforms to the
interface). Using member variables directly from the outside messes this all up. Don’t do it! It could
break your code and this will be tested on the autograder!
An exception to this rule is the Pixel struct. It’s considered to be a “Plain Old Data” (POD) type. In
this case, the interface and the implementation are the same thing. It’s just an aggregate of three
ints to represent an RGB pixel - nothing more, nothing less.
We should note there are patterns used in C-style programming that hide away the definition of a
struct’s members and prevent us from accidentally accessing them outside the correct module.
Unfortunately, this causes complications that we don’t have all the tools to deal with yet (namely
dynamic memory management). We’ll also see that C++ adds some built-in language mechanisms
to control member accessibility. For now, you’ll just have to be careful!
1
2
3
4
5
6
7
8
void Image_print(const Image *img, std::ostream& os) {
...
// loop through all the rows
for (int r = 0; r < img->height; ++r) {
// do something
}
...
}
1
2
3
4
5
6
7
8
9
int main() {
// Make a 400x300 image (sort of)
Image* img = new Image;
img->width = 400;
img->height = 300;
// do something with img but it doesn't work :(
...
delete img;
}
Copying Large Structs
In many cases you will find it useful to copy Matrix and Image structs in your code. This is
supported by the interface, so feel free to use it wherever useful. However, try to avoid making
unnecessary copies, as this can slow down your code.
As an example, let’s say you wanted to add a border to a Matrix and print it without changing the
original. You could write this:
For posterity, we will note that the main reason it is fine to use the built-in copying behavior for the
Matrix and Image structs is that neither holds an object or resource indirectly through a pointer.
Thus, a straightforward member-by-member copy of the structs is sufficient and the built-in copy is
fine. If this doesn’t seem relevant right now, just wait until we get to the “Big Three” in lecture :).
Testing
Respect the interfaces for the modules you are testing. Do not access member variables of the
structs directly. Do not test inputs that break the REQUIRES clause for a function.
Make sure to create Image objects with the new operator, and then destroy them with delete
when you are done. Do not declare an Image on the stack, as they are too large to be placed in a
stack frame. Declaring an Image* is fine, since a pointer is small.
You may use stringstreams to simulate file input and/or output for your unit tests. You may also use
the image files dog.ppm , crabster.ppm , and horses.ppm , but no others.
In your Image tests, you may use the functions provided in Image_test_helpers.hpp . Do not use
Matrix_test_helpers.hpp in your Image tests.
Processing Module
1
2
3
4
5
6
7
8
9
10
...
// Assume we have a variable mat that points to a Matrix
// Make a copy of mat and add the border. original remains unchanged
Matrix* mat_border = new Matrix(*mat); // need to dereference mat to copy it
Matrix_fill_border(mat_border, 0);
// print the bordered version
Matrix_print(mat_border, os);
...
The processing module contains several functions that perform image processing operations.
Some of these provide an interface for content-aware resizing of images, while others correspond to
individual steps in the seam carving algorithm.
The main interface for using content-aware resizing is through the seam_carve ,
seam_carve_width and seam_carve_height functions. These functions use the seam carving
algorithm to shrink either an image’s width or height in a context-aware fashion. The seam_carve
function adjusts both width and height, but width is always done first. For this project, we only
support shrinking an image, so the requested width and height will always be less than or equal to
the original values.
Write implementations in processing.cpp for the functions declared in processing.hpp .
Run the public processing tests.
Submit processing.cpp to the Autograder using the link in the Submission and Grading section.
Setup
Rename this files (VS Code (macOS), VS Code (Windows), Visual Studio, Xcode, CLI):
processing.cpp.starter -> processing.cpp
The Processing tests should compile and run. Expect them to fail at this point because the
processing.cpp starter code contains function stubs.
Configure your IDE to debug public tests.
VS Code
(macOS)
Set program name to:
${workspaceFolder}/processing_public_tests.exe
VS Code
(Windows)
Set program name to:
${workspaceFolder}/processing_public_tests.exe
XCode Include compile sources:
processing_public_tests.cpp , Matrix.cpp , Image.cpp ,
1
2
$ make processing_public_tests.exe
$ ./processing_public_tests.exe
1
2
$ make processing_public_tests.exe
$ ./processing_public_tests.exe
processing.cpp , Matrix_test_helpers.cpp , Image_test_helpers.cpp
Visual
Studio
Exclude files from the build:
Include processing_public_tests.cpp
Exclude Matrix_public_test.cpp , Matrix_tests.cpp ,
Image_public_test.cpp , Image_tests.cpp , resize.cpp (if present),
main.cpp (if present)
Energy Matrix
compute_energy_matrix : The seam carving algorithm works by removing seams that pass through
the least important pixels in an image. We use a pixel’s energy as a measure of its importance.
To compute a pixel’s energy, we look at its neighbors. We’ll call them N (north), S (south), E (east),
and W (west) based on their direction from the pixel in question (we’ll call it X).
The energy of X is the sum of the squared differences between its N/S and E/W neighbors:
The static function squared_difference is provided as part of the starter code. Do not change the
implementation of the squared_difference function.
To construct the energy Matrix for the whole image, your function should do the following:
1. Initialize the energy Matrix with the same size as the Image and fill it with zeros.
2. Compute the energy for each non-border pixel, using the formula above.
3. Find the maximum energy so far, and use it to fill in the border pixels.
Cost Matrix
compute_vertical_cost_matrix : Once the energy matrix has been computed, the next step is to
find the path from top to bottom (i.e. a vertical seam) that passes through the pixels with the lowest
total energy (this is the seam that we would like to remove).
We will begin by answering a related question - given a particular pixel, what is the minimum energy
we must move through to get to that pixel via any possible path? We will refer to this as the cost of
energy(X) = squared_difference(N, S) + squared_difference(W, E)
that pixel. Our goal for this stage of the algorithm will be to compute a matrix whose entries
correspond to the cost of each pixel in the image.
Now, to get to any pixel we have to come from one of the three pixels above it.
Pixels above (3,2) Pixels above (2,4)
We would want to choose the least costly from those pixels, which means the minimum cost to get
to a pixel is its own energy plus the minimum cost for any pixel above it. This is a recurrence
relation. For a pixel with row r and column c , the cost is:
Use the Matrix_min_value_in_row function to help with this equation. Of course, you need to be
careful not to consider coming from pixels outside the bounds of the Matrix .
We could compute costs recursively, with pixels in the first row as our base case, but this would
involve a lot of repeated work since our subproblems will end up overlapping. Instead, let’s take the
opposite approach…
1. Initialize the cost Matrix with the same size as the energy Matrix .
2. Fill in costs for the first row (index 0). The cost for these pixels is just the energy.
3. Loop through the rest of the pixels in the Matrix , row by row, starting with the second row
(index 1). Use the recurrence above to compute each cost. Because a pixel’s cost only
depends on other costs in an earlier row, they will have already been computed and can just be
looked up in the Matrix .
Minimal Vertical Seam
find_minimal_vertical_seam : The pixels in the bottom row of the image correspond to the
possible endpoints for any seam, so we start with the one of those that is lowest in the cost matrix.
1
2
3
cost(r, c) = energy(r, c) + min(cost(r-1, c-1),
cost(r-1, c),
cost(r-1, c+1))
First, find the minimum cost pixel in the bottom row.
Now, we work our way up, considering where we would have come from in the row above. In the
pictures below, the blue box represents the “pixels above” in each step.
Then find the minimum cost pixel above. Don't look outside the bounds!
For ties, pick the leftmost. Repeat until you reach the top row.
You will find the Matrix_column_of_min_value_in_r