关于算法:EECS-280-计算视觉算法

EECS 280 Project 2: Computer Vision

1.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 seamcarving for content-aware resizing ofimages. The algorithm works by findingand removing“seams”in the image that pass throughtheleastimportant pixels. For a quick introduction, check out thisvideo.Original Image: 479×382 Resized: 300×382 Resized: 400x250SetupSet up your visual debugger and version control, thensubmit to the autograder.Visual debuggerDuring setup, name your project p2-cv . Use this starter files link:https://eecs280staff.github.io/p2-cv/starter-files.tar.gzVS Code Visual Studio XcodeAfter setting up your visual debugger, renamemain.cpp to resize.cpp . You should end up with afolder with starter files that looks like this. You may have already renamedfiles likeMatrix.cpp.starter to Matrix.cpp .Here’s a short description ofeach starter file.File DescriptionMatrix.hpp Interface specification for the Matrix module.Image.hpp Interface specificationfor the Image module.processing.hppSpecification of image processing functions that arepieces of the seam carvingalgorithm.Matrix.cpp.starter Starter code for the Matrixmodule.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 submittingVersion controlSet 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 repositoryshould be connected to a remote GitHub repository.Submission and Grading section. Then, submit the code you have.Matrix ModuleCreate a Matrix abstract data type (ADT). Write implementations in Matrix.cpp for the functionsdeclared in Matrix.hpp .Run the public Matrix tests.Complete the EECS 280 Unit Test Framework Tutorial.Write tests for Matrix inMatrix_tests.cppusing the unit test framework. You’ll submitthesetests to the autograder. See the Unit Test Gradingsection.
Submit Matrix.cpp and Matrix_tests.cpp to the Autograder using thelink in the Submissionand Grading section.SetupRename these files (VS Code (macOS), VS Code (Windows), VisualStudio, Xcode, CLI):Matrix.cpp.starter -> Matrix.cppMatrix_tests.cpp.starter -> Matrix_tests.cppThe Matrix tests should compile and run. Expect themto fail at this point because the Matrix.cppstarter code contains function stubs.

$ 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),

2. Interface Implementation

Each of the functions in the Matrix module takes a pointer to theMatrix that is supposed to beoperated on. In your implementationsof these functions, you should access the width height ,and data members of that Matrix , but this is the only place you maydo so. To all other code, theindividual members are animplementation detail that should be hidden behind the providedinterfaces for the Matrix module.Your Matrix_at functionswill need to perform the appropriate arithmetic to convert from a(row,column) pair to an index in the array, and your Matrix_row andMatrix_column functions willneed to go in the other direction.Noneof these functions require a loop, and you’ll find yourimplementation will be very slow if you use a loop.There are two versions of the Matrix_at function to support element access for bothconst andnon-const matrices. The constness of the pointerreturned 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 ofanother, and in fact you should do this if it reduces code duplication. In particular, nofunctionother than Matrix_row , Matrix_column , and the twoversions of Matrix_at should accessthe data member directly – call one of these functions instead. (However, you will not be ableto call one version of Matrix_at from the other due to the differences inconstness.) Pro-tip: Use assert() to check the conditions in theREQUIRES clause. If other codebreaks the interface, that’s a bugand you want to know right away! Here’s an example.Some thingscan’t be checked, for example that a pointer points to a valid Matrix .

// 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);
// ...
}

3.Testing

Test your Matrix functions to ensure that your implementationsconform to specification in the RME.Heed the Small Scope Hypothesis. There is no need for large Matrix structs. (Other than an asedge case for max size.) Think about what makes tests meaningfully different.Create Matrix objects with the new operator, and then destroy themwithdelete when you aredone.Do not create a Matrix on the stack. It’s too large.
Respect the interfaces for the modules you are testing. Do not accessmember variables of thestructs 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, youneed

#include <sstream>
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 teststo theautograder. See the Unit Test Grading section.Submit Image.cpp and Image_tests.cpp to the Autograder using the link in the SubmissionandGrading section.SetupRename these files (VS Code(macOS), VS Code (Windows), Visual Studio, Xcode, CLI):Image.cpp.starter -> Image.cppImage_tests.cpp.starter -> Image_tests.cppThe Image tests should compile and run. Expect them to fail at thispoint because the Image.cppstarter code contains function stubs.Write tests for Image in Image_tests.cpp using the Unit Test Framework. You’ll submit theseteststo the autograder. See the Unit TestGradingsection.Configure your IDE to debug either the public tests oryourown tests.Public tests Your own testsBelow is a 5×5 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 0are not allowed. To create an Image , first allocate storage and then use an initializer function.There are severalinitializer functions, but for now we’ll just use thebasicone.Once an Image is initialized, it is considered valid.Nowwecan use any of the functions declared inImage.hpp to operate on it.To read and write individual Pixel s in an Image , use theImage_get_pixel andImage_set_pixel functions, respectively.
The RMEs in Image.hpp give a full specification of the interface foreach Image function.When an Image object is no longer needed, itsstorage should be deallocated with the deleteoperator.PPM Format
The Image module also provides functions to read and write Image sfrom/to the PPM imageformat. Here’s an example of an Image and itsrepresentation in PPM.Image Image Representation in PPM

4.Cost Matrix

compute_vertical_cost_matrix : Once the energy matrix has beencomputed, the next step is tofind the path from top to bottom (i.e. a vertical seam) that passes through the pixels with the lowesttotal energy (this is the seam that we would like to remove).We will begin by answering a related question – given a particularpixel, what is the minimum energywe must move through to get to that pixelvia any possible path? We will refer to this as the costofenergy(X) = squared_difference(N, S) + squared_difference(W, E)that pixel. Our goal for this stage of the algorithm will be tocompute a matrix whose entriescorrespond 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 theminimum cost to getto a pixel is its own energy plus the minimumcost for any pixel above it. This is a recurrencerelation. For a pixel with row r and column c , the cost is:Use theMatrix_min_value_in_row function to help with this equation. Ofcourse, you need to becareful 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 wouldinvolve 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

Diagnosing Slow CodeIf your code runs too slowly (especially on larger images like the“horses”example), a tool calledperf can analyze which parts of your code take the most time. See the PerfTutorial for details.Undefined Behavior and Memory LeaksIf your code produces different results on different machine (e.g. yourcomputer vs. the autograder),the likely source isundefinedbehavior. Refer to the ASAN Tutorial for how to use the AddressSanitizer (ASAN) to check for undefined behavior. You can alsouse ASAN to detect memory leaks,which occur when your codecreates an object using new but never frees the memory for thatobject with the delete operator.Reach GoalsOptionally check out the project reach goals. Reach goals are entirely optional.AcknowledgmentsThis project was written by James Juett,Winter 2016 at the University of Michigan. It was inspiredby