MP 5 PhotoMosaic

Goals and Overview

In this MP, you will:

• learn about k-d trees
• implement and use a nearest neighbor search (NNS) algorithm
• practice using templates
• practice const-correctness
• use your knowledge to make a useful application

Videos

• k-d tree : 2-D example
• (partition based) Quick Select
• findNearestNeighbor - Part 1: Explanation
• findNearestNeighbor - Part 2: Walkthrough

Checking Out Your Code

As usual, check out the code by running

svn up 

from your cs225 directory. This will create a new folder in your working directory called mp5.

Background: PhotoMosaics

A PhotoMosaic is a picture created by taking some source picture, dividing it up into rectangular sections, and replacing each section with a small thumbnail image whose color closely approximates the color of the section it replaces. Viewing the PhotoMosaic at low magnification, the individual pixels appear as the source image, while a closer examination reveals that the image is made up of many smaller tile images.

For this project you will be implementing parts of a PhotoMosaic generator. Specifically your code will be responsible for deciding how to map tile images to the rectangular sections of pixels in the source image. Selecting the appropriate tile image is supported by a data structure called a k$k$-d tree which we will describe in the next section. The pool of tile images are specified by a local directory of images. We provide the code to create the TileImage pool and the code to create the mosaic picture from a tiled source image.

Background: K-d trees

Binary Search Trees are linear data structures that support the Dictionary ADT operations (insert, find, remove). They also support nearest neighbor search: If you have a binary search tree, given a key that may or may not be in the tree, you can find the closest key that is in the tree. To do so, you just recursively walk down the tree, as in find, keeping track of the closest node found:

K BST::findNearestNeighbor(Node * croot, K target)
{ // Look in the left or right subtree depending on whether target is smaller or larger than our current root  if (target < croot->key)
    { // if we have no child in the correct direction, our root must be the closest  if (croot->left == NULL) return croot->key;
        childResult = findNearestNeighbor(croot->left);
    } else { if (croot->right == NULL) return croot->key;
        childResult = findNearestNeighbor(croot->right);
    } // Calculate closest descendent node's distance to the target  childDistance = distance(childResult, target); // Find the distance of this node to the target  currDistance = distance(croot->key, target); // If the root node is closer, return it, otherwise return the closer child  if (currDistance < childDistance) return croot->key; else return childResult;
} 

A k$k$-d tree is a generalization of a Binary Search Tree that supports nearest neighbor search in higher numbers of dimensions — for example, with 2-D or 3-D points, instead of only 1-D keys. A 1-D-tree (a k$k$-d tree with k=1$k=1$) is simply a binary search tree. For this MP, you will be creating a photomosaic, which requires that given a region on our original image, we can determine which of our available images best fills that region. If we use the average color of regions and tile-images, this can be determined by finding the nearest colored tile image to a given region. If we treat colors as (R,G,B)$(R,G,B)$ points in 3-D space, we can solve this problem with a 3-D tree.

More formally, a k$k$-d tree is special purpose data structure used to organize elements that can be described by locations in k$k$-dimensional space. It is considered a space-partitioning data structure because it recursively subdivides a space into two convex sets. These sets are rectangular regions of the space called hyperrectangles. k$k$-d trees are particularly useful for implementing nearest neighbor search, which is an optimization problem for finding the closest element in k$k$-dimensional space.

A k$k$-d tree is a rooted binary tree. Each node in the tree represents a point in k$k$-d-space, as well as a line (hyperplane) defined by one dimension of this point, which divides this space into two regions (hyperrectangles). At each level in the tree, a different dimension is used to decide the direction of the splitting line (hyperplane). An element is selected to define the splitting line by its coordinate value for the current dimension. This element should be the median of all the points in this part of the tree, taken over the current dimension. A node is then created for this element in the tree and its children are created recursively using the same process, which repeats until no elements remain in the region (hyperrectangle). The splitting dimension at any level of the tree can be selected to find the best partition of the data. For our purposes, we will change dimension cyclically, in order (for k=3$k=3$, we will use dimensions 0,1,2,0,1,2,0,…$0,1,2,0,1,2,0,\dots$).

k$k$-d trees are particularly useful for searching points in Euclidean space. Perhaps the most common use of a k$k$-d tree is to allow for fast search for the nearest neighbor of a query point, among the points in the tree. That is, given an arbitrary point in k$k$-dimensional space, find the point in the tree which is nearest to this point. The search algorithm is defined in detail below.

For this MP, we will be using a 3-D tree (a 3-dimensional k$k$-d tree) to find the closest average color of TileImages to the average color of pixel sections in the source image. With the pool of average colors organized in a k$k$-d tree, we can search for the best tile to match the average color of every region in the input image, and use it to create a PhotoMosaic!

Requirements

These are strict requirements that apply to both parts of the MP. Failure to follow these requirements may result in a failing grade on the MP.

• You are required to comment the MP as per the commenting standard described by the Coding Style Policy.
• You must name all files, public functions, public member variables (if any exist), and executables exactly as we specify in this document.
• Your code must produce the exact output that we specify: nothing more, nothing less. Output includes standard and error output and files such as images.
• Your code must compile on the EWS machines using clang++. Being able to compile on a different machine is notsufficient.
• Your code must be submitted correctly by the due date and time. Late work is not accepted.
• Your code must not have any memory errors or leaks for full credit. Valgrind tests will be performed separately from the functionality tests.
• Your public function signatures must match ours exactly for full credit. If using different signatures prevents compilation, you will receive a zero. Tests for const-correctness may be performed separately from the other tests (if applicable).

Assignment Description

We have provided the bulk of the code to support the generation of PhotoMosaics. There is one critical component that is missing: the KDTileMapper. This class is responsible for deciding which TileImages to use for each region of the original image. In order to make this decision it must be able to figure out which TileImage has the closest average color to the average color of that region. A data structure called a k$k$-d tree is used to find the nearest neighbor of a point in k$k$-dimensional space.

This assignment is broken up into the following two parts:

• MP 5.1 — the KDTree class.
• MP 5.2 — the mapTiles function.

As usual, we recommend implementing, compiling, and testing the functions in MP 5.1 before starting MP 5.2.

MP 5.1

For the first part of MP 5, you will implement a generic KDTree class that can be used to organize points in k$k$-dimensional space, for any integer k>0$k>0$.

The KDTree class

Although we will only be using a 3-D tree, we want you to create a more general data structure that will work with any positive non-zero number of dimensions. Therefore, you will be creating a templated class where the template parameter is an integer, specifying the number of dimensions. We have provided the skeleton of this class, but it is your assignment to implement the member functions and any helper functions you need.

A k$k$-d tree is constructed with Points in k$k$-dimensional space. To support this, we have provided a templated Point class, which takes the same integer template parameter as the k$k$-d tree.

In this part of assignment we ask you to implement all of the following member functions.

Implementing smallerDimVal

Please see the Doxygen for smallerDimVal.

This function should take in two templatized Points and a dimension and return a boolean value representing whether or not the first Point has a smaller value than the second in the dimension specified. That is, if the dimension passed in is k$k$, then this should be true if the coordinate of the first point at k$k$ is less than the coordinate of the second point at k$k$. If there is a tie, break it using Point’s operator<. For example:

Point<3> a(1, 2, 3);
Point<3> b(3, 2, 1);
cout << smallerDimVal(a, b, 0) << endl; // should print true,  //    since 1 < 3 cout << smallerDimVal(a, b, 2) << endl; // should print false,  //    since 3 > 1 cout << smallerDimVal(a, b, 1) << endl; // should print true,  //    since a < b according to operator<, 

Implementing shouldReplace

Please see the Doxygen for shouldReplace.

This function should take three templated Points: target, currentBest, and potential. This should return true if potential is closer (i.e., has a smaller distance) to target than currentBest (with a tie being broken by the operator< in the Point class: potential < currentBest). The Euclidean distance between two k$k$-dimensional points, P(p1,p2,…,pk)$P(p_1,p_2,\dots ,p_k)$ and Q(q1,q2,…,qk)$Q(q_1,q_2,\dots ,q_k)$, is the square root of the sum of squares of the differences in each dimension:

Note that minimizing the distance is the same as minimizing squared-distance, so you can avoid invoking the square root, and just compare squared distances throughout your code:

Point<3> target        (1, 3, 5);
Point<3> currentBest1  (1, 3, 2);
Point<3> possibleBest1 (2, 4, 4);
Point<3> currentBest2  (1, 3, 6);
Point<3> possibleBest2 (2, 4, 4);
Point<3> currentBest3  (0, 2, 4);
Point<3> possibleBest3 (2, 4, 6);
cout << shouldReplace(target, currentBest1, possibleBest1) << endl; // should print true cout << shouldReplace(target, currentBest2, possibleBest2) << endl; // should print false cout << shouldReplace(target, currentBest3, possibleBest3) << endl; // based on operator<, this should be false!!! 

Implementing the KDTree Constructor

Please see the Doxygen for the KDTree constructor.

This takes a single parameter, a reference to a constant std::vector of Points. The constructor should build the tree using recursive helper function(s).

Just like there is a way to represent a balanced binary search tree using a specially sorted vector of numbers (how?), we can specially sort a vector of points in such a way that it represents a k$k$-d tree. More specifically, in the KDTreeconstructor, we are interested in copying the input list of points into a points vector, and sorting this vector such that it represents a k$k$-d tree.