mp_traversals

Image and Image Traversal

Mathematically, an image can be considered as a function of two variables, f(x, y), where x and y are spatial coordinates and the value of the function at given pair of coordinates (x, y) is called the intensity value.

In the figure below - Values in the grid represent the grayscale intensity of the image on the right. A) Intensity values shown in a grid of same dimension as image. B) Image as seen on monitor

One way to traverse the image is in row first order. Figure below describes this Note that rows are being accessed one after the other. This is known as ‘Row First Traversal’. The graphic suggests that in the current iteration, x = 4 and y = 3 both starting from 0.

Checking Out the Code

You can find the code for all our released assignments at the following public git repo.

release-f22

You can either clone this or pull a zip file of the repo to your local computer. All the files for this MP are in the mp_traversals directory. You should copy that directory into the directory you setup for your docker container.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the mp_traversals directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

You will need to do the above once for each assignment. You will need to run make every time you change source code and want to compile it again.

Part 1 : Image Traversals

As you learned in lecture, there are many ways to traverse a data structure. In this MP, you will use object-oriented programming techniques to develop classes that traverse an image in a generic way.

Background – Understanding an ImageTraversal

The goal of an ImageTraversal is to create a traversal that starts at some start point and visits every point within some tolerance in a specific order.

For example, consider a “Block I” image that is exactly 6 pixels wide and 7 pixels tall:

One possible traversal of this image is a Row First Traversal, where every pixel in a single row (within a tolerance) is visited before a pixel in any other row is visited. Starting at (2, 3), such a traversal visits every pixel in Row 2 before moving to Row 3 and visited everying pixel in Ro 3 before moving to Row 4:

Two things to note:

1. The blue pixels are not visited, because they are outside of a tolerance
2. The traversal requires only that all pixels in a row are visited before visiting the next row. Therefore, the order may vary depending on the implementation.

Below are few traversals with iterators (only the pixels within the shape are within the ‘tolerance’ ):

Entire Image	Rectangle	Circle	Line	Polygon
Ellipse	Spiral

Components of an ImageTraversal

ImageTraversal is an abstract class that provides the setup to build a generic traversal library. ImageTraversal contains six pure virtual functions:

• ImageTraversal::begin() and ImageTraversal::end(), used to return iterators
• ImageTraversal::add(const Point &)Add new point to the traversal Virtual function.
• ImageTraversal::pop() Remove and return the next point of the traversal Virtual function.
• ImageTraversal::peek() Return but not remove the next point of the traversal Virtual function.
• ImageTraversal::empty() To see if the traversal has no points left

Developing an ImageTraversal

Consider a simple image of 16 pixels:

Every ImageTraversal will start at a provided Point. In this image above, suppose we start in the bottom-left corner (0, 3). The first pixel a traversal will “visit” will almost always be that starting point (0, 3).

As part of “visiting” a point, a traversal must add all of the neighbors that will be visited at some time in the future. Every point has up to four neighbors (and the neighbors MUST be added in the following order):

• The pixel to the right, (x + 1),
• The pixel below, (y + 1), and
• The pixel to the left, (x - 1).
• The pixel above, (y - 1),

As our starting point (0, 3) is a corner, it has only two neighbors (1, 3) and (0, 2):

After visiting the first point (the starting point), the next point visited is determined by our ImageTraversal. The logic in add and pop determines the order the nodes are visited. For example, if we visit the point that was most recently added, we create the following traversal:

Finally, in the image above, only orange pixels were visited. A point must NOT be visited in a traversal if either of the following statements are true:

1. The point has already been visited (a traversal never visits the same point twice), OR
2. The pixel at the point is greater than or equal to a given tolerance away from the pixel at the starting point. The function ImageTraversal::calculateDelta is provided for you to calculate the difference between two pixels.

Part 1a: Create a DFS ImageTraversal

Implement the traversal described above in imageTraversal/DFS.{cpp,h}. It is not necessary to implement the begin and end functions yet.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 1b: Create a BFS ImageTraversal

Implement the second ImageTraversal, BFS, by visiting the first earliest point that was added that has not yet been visited. It is not necessary to implement the begin and end functions yet.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 1c: Create the ImageTraversal::Iterator

Finally, create an iterator that uses the ImageTraversals that you have built. You can read about iterators here. You need only to create the simplest of all the iterators – a forward iterator – which requires three operations:

• operator*, to access the current Point in the image traversal
• operator++, to advance to the next Point in our image traversal
• operator!=, to check if two iterators are different

A call to DFS::begin() or BFS::begin() must return an ImageTraversal::Iterator that starts at the starting point (eg: *(dfs.begin()) == startingPoint) and must move through the traversal you created in parts 1a and 1b.

As you work through this:

• You may assume the PNG image will not change after your object is created.
• Iterators must be independent (moving one iterator forward does not change other instances of an iterator).
• There are at least four very different ways to build your iterator. You may need to create a copy of your entire BFS or DFS object within your iterator, this is okay.
• Remember that begin() returns an iterator at the starting point, but end() returns an iterator one past the end.
• It is common for end() to be a sentinel value (eg: a NULL pointer, etc). It should not be necessary to run through the full traversal to get to one past the end.

Finally, simple test cases for this part can be run with the following command:

make test
./test [part=1]

Extra Credit Submission

For extra credit, you can submit the code you have implemented and tested for mp_traversals, Part 1. You must submit your work before the extra credit deadline as listed at the top of this page. The extra credit submission will appear as a separate submission on PrairieLearn.

Part 2 (Curated): Flood Fill

In this MP, you will be flood-filling an image using a ColorPicker and an ImageTraversal. You built ImageTraversal classes in Part 1 and we have provided some ColorPicker classes for you (including RainbowColorPicker, SolidColorPicker, and others).

The FloodFilledImage class outlines the three member functions you must implement for this part.

• Feel free to use a std::vector, std::list, std::stack, or std::queue if they would be helpful.

Part 3 (Creative): Your Flood Fill!

Finally, time to be creative with what you built! Two separate things are required:

1. Create a new color picker called MyColorPicker, found in the colorPicker folder. This picker may be anything, but must be different than the color pickers we provided.

2. Modify main.cpp to create a FloodFilledImage using at least two flood fill operations (two calls to addFloodFill). Your main.cpp must save the last frame as myFloodFill.png.

To test and create your artwork,

make
./main

Testing

The following warning is only if you are not developing in the container. The container has ImageMagick.

convert

To run all of the tests for this MP:

make test
./test

Grading Information

The following files are used to grade mp_traversals:

• imageTraversal/BFS.cpp (Part 1)
• imageTraversal/BFS.h (Part 1)
• imageTraversal/DFS.cpp (Part 1)
• imageTraversal/DFS.h (Part 1)
• imageTraversal/ImageTraversal.cpp (Part 1)
• imageTraversal/ImageTraversal.h (Part 1)
• FloodFilledImage.cpp (Part 2)
• FloodFilledImage.h (Part 2)
• colorPicker/MyColorPicker.cpp (Part 3)
• colorPicker/MyColorPicker.h (Part 3)
• main.cpp (Part 3)
• myFloodFill.png (Part 3)

All other files including any testing files you have added will not be used for grading.

Good Luck!