MP 6 Unknown

Motivation

In software development, it is rare that you build anything completely “from scratch”. Today, we rely on the work of people before us who built amazing programs that allow us to build ever increasingly complex programs. Here in CS 225, this is no exception:

• We use the lodepng library in every MP to read/write PNG files on disk into PNG obejcts that contain HSLAPixels.
• We use the “C++ Automated Test Cases in a Header” or “catch” framework for writing unit tests both for you to run to test your own code and for the autograder to grade your code.
• We use the standard template library, std::, extensively in all of our MPs and labs.

One of the best metrics to determine the robustness of a piece of software is how long it has been in use. When we updated MP5 for this semester, we knew MP5 had been used for the past seven years (around 15 semesters). With that in mind, MP5 was likely to be robust, well debugged, and suitable for updating for this semester.

With a little exploration as a class, together, we found that was not completely true. When I made my new Facebook profile picture out of my favorite picture from a trip to Disney World, I found:

• It crashed on EWS while trying to create the picture
• It also crashed on desktop PC with 32 GB of RAM
• I had to dig into the code and find out what was going on that caused 32 GB to not be enough memory to generate a single mosaic. And the problems were all in the provided code.

With Fall Break coming up in less than two weeks, this MP is a reflection on a very common real-world problem: understanding the data structures in code that functionally works and applying your knowledge about data structures to improve the runtime and memory usage of that code.

Overview

For MP6, you should take your solution from MP5 and copy it into your MP6 file (that is: maptiles.{cpp,h} and kdtree.{cpp,h}. If you did not complete MP5, you can use a course solution that I have posted here.

The end goal of MP5 was to use a kdTree to create a photo mosaic. In the process of creating that mosaic, there are a couple different inputs that we are going to quantify for MP6:

• n$n$, the number of “tile images” in the directory of images to use for the mosaic
• w$w$, the number of “tile images” that make up the width of the mosaic (eg: a mosaic may be 100 images across)
• h$h$, the number of “tile images” that make up the height of the mosaic (eg: a mosaic may be 200 images in height, this is a function of the width and the aspect ratio of the image)
• PNG$PNG$, the size of a PNG

The goal of MP6 is to explore the API you used in MP5 and improve the algorithms that you used (without even knowing you used them)!

Requirements

This MP requires that you improve the runtime and memory footprint of MP5. There are only a few technical limitations that are imposed on you for this MP:

• You can modify any of the files in the base directory
• Your code must compile using make and produce an mp6 executable
• The command line interface to create a mosaic with MP6 must be the same as MP5 (eg: you probably should not modify main.cpp unless you’re certain you know what you’re doing)
• Other than that:
  • You can change the interface to any/all of the functions
  • You can add/remove any files you want
  • you can modify your Makefile
  • You can change any data structures used
  • You can rewrite the whole thing in main.cpp, but that is crazy

You already have a working MP6, so there are no unit tests (it already works)! Instead, you must ensure your program runs in a reasonable amount of memory and time. The following command should both not crash and run in less than 10 minutes on EWS:

./mp6 source.png /class/cs225/mp5_pngs/ 400 5 mosaic.png 

It should not be necessary to test this (it takes a while) – we’ll work through some observations about this code.

You will have to commit a mosaic that you generated with your program. It should be named exactly mosaic.png and be located in your mp6 directory.

Observations

The following are some observations about the runtime of MP5 that will help you improve the runtime of this code.

Observation 1: Generating a mosaic uses far too much memory!

When generating a large mosaic (eg: by running the command above), the following occurs:

• The “tile images” are loaded, allocating n∗PNG$n\ast PNG$ memory
• The mosaic is populated with tile images… and the program is killed for using too much memory! :(

When the mosaic is being populated with tile images, w∗h∗PNG$w\ast h\ast PNG$ additional memory is allocated. For a large mosaic, this would require over 1 TB of RAM! (w=500, h=500, PNG=5MB results in 1.25 TB of memory allocated.)

Modify the MP to allocate w∗h∗C$w\ast h\ast C$ memory when the mosaic is populated, where C is a small constant (eg: C=8 bytes, if a only a single pointer is needed for each image; with C=8, our example above would require only 2 MB instead of 1,250,000 MB).

Observation 2: Generating a mosaic is far too slow!

After reducing the memory footprint of the program, the following occurs when generating a large mosaic:

• The “tile images” are loaded, running in O(n)$O(n)$ time
• The mosaic is populated with images, running in O(w∗h∗lg(n))$O(w\ast h\ast lg(n))$ time
• The mosaic is drawing… forever, and ever, and ever, running in O(w∗h∗w′∗h′)$O(w\ast h\ast w^{\prime }\ast h^{\prime })$ time, where w′$w^{\prime }$ and h′$h^{\prime }$ are the width and height of the “tile images”

When a mosaic is drawing, the running time is effectively a quartic polynomial!

Modify the MP to draw the mosaic in O(w∗h+n∗w′∗h′)$O(w\ast h+n\ast w^{\prime }\ast h^{\prime })$ time.

Make a Mosaic!

You have spent almost four weeks making an mosaic – you should show off your work! You’ll have to gather some pictures, convert them to PNGs, and generate a mosaic using your mp6 executable.

After generating your mosaic, make sure to commit it to SVN as mosaic.png.

Making a great mosaic: Gathering Pictures

A good mosaic requires a lot of tile images. A baseline for a decent mosaic is ~100 tile images if the images are all different (eg: not all daylight pictures or selfies) and ~1000 for a great mosaic. You probably already have many images:

• If you have an Android, Google Photos usually [backs up your photos to the cloud at photos.google.com][https://photos.google.com/]. You can download them as a ZIP file.
• If you have an iPhone, Apple usually [backs up your photos in iCloud][https://www.icloud.com/]. You can download them as a ZIP file.
• Using a computer and a bit of time, you can download a bunch of your photos frome Facebook, Instagram, Twitter, etc.

Making a great mosaic: Converting to PNG

The program you built requires PNG files as input. Often photos are JPEG files and must be converted.

Once you have converted all of the image into PNG, place all of the images into a single directory inside of your mp6 folder. This folder will likely be very large – you should NOT commit it to svn!

Making a great mosaic: Sharing and explaining what you’ve made

A mosaic looks like a fun Instagram “block” transformation at first glance, but becomes even more amazing when someone understands what they’re seeing – an image made entirely from other images.

If you share you image, it’s best if you describe what you’ve done! If you want to share it with your peers, post it with #cs225 so we can find it. :)

Handing in Your Code

Commit your changes in the usual way:

svn ci -m "mp6 submission" 

If you add any new files, remember to svn add them.

Please don’t commit your tile images! This could easily amount to hundreds of megabytes of files per student, and EngrIT will probably not like that :)

Grading Information

As specified in the Requirements section above, you are able to modify any/all parts of this MP that you wish. To that end, we will use all files present in your mp6 directory to grade your code. We will use the following commands to test your code:

make
./mp6 source.png /class/cs225/mp5_pngs/ 400 5 mosaic.png 

Don’t forget to commit the mosaic.png that you generate!

If running make doesn’t produce an executable called mp6 or your mp6 executable doesn’t work with the above arguments, you will receive a 0 on this MP.

Good luck!