Attached files.Assignment Description Introduction A quadtree is a tree data structure in which each...

Question

Attached files.Assignment Description Introduction A quadtree is a tree data structure in which each internal node has exactly four children. In this assignment, we will be using the quadtree data structure to compress bitmap image files, and then decompress them afterwards. In this assignment, you will: ● learn about the quadtree data structure ● learn to implement recursive operations on trees ● use inheritance and good OOP design to build an interface for your compression algorithm ● gain some insight into reading binary file data (although we do most of the work for you) So then, you might be wondering how a quadtree works to compress a file. Given an image file (which is essentially a 2D matrix of pixels), we first split it into four equal quadrants. For each of those quadrants, we further split them into four quadrants until we reach a quadrant that only consists of one pixel. At this point, we can store the data of the pixel in a leaf node in the tree. When we want to retrieve pixel data from the tree, we can very easily traverse the quadtree structure to find out what the colour each pixel is. All we have to do is specify the location of the pixel, and depending on which quadrant the pixel is located in, recursively look into the children of current tree node until we reach a leaf, which we can retrieve the pixel data from. However, there is one caveat to the approach we just described: it doesn’t actually do any compression! If we store every single pixel in a tree structure, this would actually make it take up even more space, because of the extra attributes we would need to store at each node. Fret not, however, as there is a neat trick to fix this, and that is to introduce a loss level during our quadtree compression process. https://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/BMP_file_format The idea is very simple: when we are splitting up our pixel data into quadrants, we calculate the standard deviation and mean of the pixel values inside each of the four quadrants that we have just created. If the standard deviation does not exceed our loss level (an integer between 0 and 255, inclusive, and is specified by the user), then that means that the pixel values inside the quadrant is “close enough” to one another. When this happens, we get lazy and say, let’s store this entire quadrant as one colour: the mean (average) value of all the colours that were originally in the quadrant. This is where the compression happens. By storing the entire quadrant as a single colour value, we essentially save all the space that we would have originally needed to store the colour values of each pixel in the quadrant. All we have to do now is to remember the height and width of the quadrant so that we can restore the image when needed. This method of compression also does something quite neat, it preserves the parts of the image which have finer details, because quadrants with finer details results in a higher standard deviation as neighboring pixels are likely to have different colours (there is a lot of statistics and science behind this in fields like image recognition, etc). However, this also means that quadtree compression is a lossy compression algorithm. That is, once an image is compressed, it is impossible to retrieve the original image data from the compressed image file. The good part about this is that the compressed file can be quite small depending on the loss level, which you will see when you implement the assignment. Here is the recommended order of tasks to do in order to complete this assignment, all the work that you will submit will be in a2tree.py (this is the only file you’ll need to submit). Note: The tasks are marked by TODOs in the starter code. In general, you’re allowed to add new helper methods if needed; however, you should NOT modify the provided methods that don’t have a TODO in it. https://en.wikipedia.org/wiki/Standard_deviation https://en.wikipedia.org/wiki/Lossy_compression Task 1: Understand the Starter Code Below is a quick description of the files in the starter code: 1. a2tree.py: This file contains the classes that define the quadtree data structure. This is the file that you’ll be working with most of the time for this assignment. You WILL submit this file. 2. a2files.py: This file contains the classes for the input/output file formats used in this assignment, namely, BMP and QDT. You will NOT submit this file, so you need to make sure your a2tree.py works correctly with the original a2files.py in the starter code. 3. a2main.py: This is the main file for running the program. It defines the compressor and decompressor classes. You will need to add some code in the main block of this file for the user interface. However, you will NOT submit this file, so you need to make sure your a2tree.py works correctly with the class defined in the original a2main.py in the starter code. 4. a2test_student.py: This file contains a template for the test suite. You WILL be asked to submit this file with some required test cases. See Task 6 for the detail. 5. dog.bmp, toronto.bmp, and uoft.bmp: three example BMP images that you can compress. Feel free to use your own BMP images as well. Look at the overall structure of the classes and methods in all files of the starter code. You don’t need to understand exactly how everything works yet, but it’s a good idea to get a general sense of the structure beforehand. No code needs to be written in this task – it’s all about the understanding. As a verification that you have understood the code well enough, you should be able to answer the following questions. 1. BMP and QDT are the two file types involved in the input and output of this program. What do they share in common and how do they differ? What is stored in the header and body of a BMP/QDT file? 2. Note that we store a “preorder_list” as the body data of the QDT file. When reading a QDT file, we read the preorder_list from the file, and we can somehow restore the tree structure from the preorder_list. Why is this even possible? Isn’t it possible that different trees can have the same preorder traversal? How could we make sure that the tree structure we restored is unique? 3. What are the different classes of quadtree nodes? What does each type of node represent in terms of the image? Why does some class have a “value” while others don’t? 4. Why is it necessary to have a class for an “empty” node? What could go wrong if we don’t have it? 5. How many children can an internal node in a tree have? Exactly 4, no more than 4, or other? The children are also required to be in a certain order in terms of which quadrants they represent. What’s the order? 6. The Compressor class does a special thing when compressing a BMP image: it converts an RGB coloured image into a grayscale image. Where in the code does that happen? Also, the pixels list we pass to the build_quad_tree() method is different from the raw pixel info stored in the image file – it is about 1/3 of the size of raw pixels list. Can you explain how that works? 7. Why is the loss level between 0 and 255? What does a loss level 0 or 255 mean to the quality of the image after compression? 8. What are the input/output filenames used by the compressor and decompressor? What is “.bmp.qdt” and what is “.bmp.qdt.bmp”? Task 2: Compression In this task, you’ll implement the compression related methods. The main method used for compression is the build_quad_tree() method in the QuadTree class, which utilizes a helper method _build_tree_helper() that you will implement. The _build_tree_helper() should be implemented with recursion. What are the base cases? Make sure to think about this carefully! Also, somewhere while building the tree, you’ll need to compare the standard deviation of a quadrant with the loss level and decide whether to turn that quadrant into a leaf node. IMPORTANT: the condition for compressing a quadrant is the standard deviation being LESS THAN OR EQUAL TO (

Assignment Description Introduction A quadtree is a tree data structure in which each internal node has exactly four children. In this assignment, we will be using the quadtree data structure to...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment