CPSC 554X Assignment 2: Compression
2021 Winter Term 1.
cs assignment代写 This assignment is to be done individually. Prepare a typed report with your answers to each question and how you arrived at them.
In this assignment, you will leverage your understanding of signal processing and combine it with machine learning techniques to implement efficient compression of audio data.
This assignment is to be done individually. Prepare a typed report with your answers to each question and how you arrived at them. You may consult external resources, such as Internet resources, provided they do not contain solutions to any of the questions. If you do so, mention these resources in a references section (you can simply provide web URLs – no formal citation is required). You may use any programming language or environment that you are comfortable with, although we recommend Python (3.6 or above) if you are not sure what to use.
For assignment submission, include your code, supplementary data and report in a single.zip file. Submit this package to the appropriate assignment on Canvas (https://canvas.ubc.ca).
Entropy Encoding (25%) cs assignment代写
As a warm-up to implementing a compression algorithm, you will first explore entropy en- coding for a short piece of text. In q1huff.json, you will find a dictionary which describes a mapping from ASCII characters to Huffman bit strings. The corresponding file q1.bin represents a text file that has been encoded using this mapping. Every character of the text file was replaced with the corresponding bit string, then the bit strings were packed into a binary file (8 bits per byte), starting with the most significant bit in each byte.
For example, two consecutive bytes in the .bin file with values 41 and 233 would represent the bitstring 0010100111101001. In the mapping file, the special symbol EOF does not repre- sent a character, but rather the end of the file; once you see this symbol appear, you should stop decoding. This is necessary because we may need to add padding bits to the final byte, which the decoder must ignore.
1a. Decode the file q1.bin using the provided mapping, and extract the ”magical words” from the text. Submit the words in your report, along with your decompressor and output.
1b. The encoding is not optimal, as it was computed using a frequency distribution that does not match the text file. Using the Huffman algorithm shown in class, compute an optimal Huffman tree (specifically for this text file) and re-compress the file. Submit your compressor, new Huffman tree (in the same format as q1huff.json, and your new compressed file. In your report, note the new size of your compressed file. Don’t forget to include an EOF symbol.
This gets us halfway to popular lossless encoding schemes like Zip and Deflate (used by gzip, zlib, and widely on the Web for serving compressed data). The other half, which we won’t implement here, is a “dictionary” compressor which can compress repeated sequences of characters (such as the name of the main character in this text file) more efficiently than a character-by-character encoder.
Musical Compression (75%) cs assignment代写
The main part of this assignment will be implementing various lossy compression algorithms for a piece of music.You have been provided with two files: a long flute piece in .wav format, and a script which compares two .wav files for similarity. Your goal is to write a compressor and decompressor pair which can compress the given file into the smallest possible space, and successfully decompress it with minimal loss.
The size of the compressed data is defined as the size of the compressed file plus the size of the decompressor. Note that your compressor size is not counted. You can hard- code anything you want into the decompressor, and make it as specific to the given flute file as you like. The decompressor size is the size of your script or program, including any non-standard dependencies or libraries. Standard dependencies, which are defined as any package installable via a standard package manager like Homebrew, apt, pip, rpm, etc., are excluded; be sure to specify these in your submission so I can test your code. cs assignment代写
Most compression techniques involve entropy coding as a final step. In order to simplify this part of the assignment, we will offload the entropy coding to the Zip algorithm. The script size.py takes your decompressor (file or directory) and a compressed audio file, then Zips it all together and spits out the resulting Zip size. Use this to test your file sizes.
Compression must be balanced with quality for any lossy algorithm. As such, you are provided the script score.py which will compare the original file against your decompressed output for similarity using the RMS signal-to-noise ratio.
Parts 1-3 are worth 25% each. In each part, you will have a target score and a target size. Submit your compressor, decompressor, and compressed file. In the report, provide a brief description of your technique and the outputs of score.py and size.py.
7.5% is all-or-nothing based on your submission’s score (as determined by score.py) – you get these marks if and only if your score is at least as high as the target.
7.5% is a sliding scale based on your submission’s size s (as determined by size.py). If your submission is above the target size t, your grade on this part will be t/s. For example, if your submission is 2x as large as the target, you will get half the marks. If your submission is below the target size, your grade will be 120% 20%(s/t), that is, you will receive bonus marks.
10% will be based on your report and code.
Testing Your Code
You’ve been given a dumb compressor/decompressor pair which “compresses” the input by simply dropping the least-significant bit of each sample. This is provided to demonstrate the desired interface and give you a skeleton to get started. Here are the commands to run and test this provided code:
# Compress the music using the dumb compressor and check the size
$ python3 dumbcomp.py flute.wav flute.cmp
$ python3 size.py dumbdecomp.py flute.cmp Zipped size: 46997050 bytes cs assignment代写
# Decompress the file and check how accurate it is
$ python3 dumbdecomp.py flute.cmp flute.cmp.wav
$ python3 score.py flute.wav flute.cmp.wav Your score: 0.99978
Part 0. Quantization
To get started, modify the given compressor/decompressor to increase the quantization factor (the “2” in the scripts). Observe that the size as reported by size.py decreases, even though the compressed file itself does not get smaller, and that the score also decreases. Explain these observations in your report.
Part 1. DCT Compression (25%)
As a first step, you will implement a DCT compression scheme. Start by implementing a compressor which transforms blocks of audio using the Discrete Cosine Transformation, then writes the resulting coefficients out in some format. Then, implement a decompressor which takes the compressed file and spits out a reconstructed .wav file (in 16-bit format). Note that depending on your block size, the final block might not fit nicely. If so, zero-pad the final block and remove the padding during decompression. cs assignment代写
Merely transforming the data via the DCT will not produce appreciable compression. Thus, you will want to apply some quantization to the data to shrink the coefficients. Im- plement a quantization scheme in the compressor and decompressor. You may hard-code the quantization table in your decompressor.
In this part, your score target is 0.99, and your size target is 5.0 MiB (5242880 bytes).
Part 2. Predictive Compression (25%) cs assignment代写
As we saw from question 3 from assignment 1, you can accurately classify the notes in the file using a variety of techniques on the audio spectrogram. In this part, build a classifier or regressor which analyzes the input and generates a sequence of labels (e.g. notes). In your decompressor, convert these labels back into blocks of audio (e.g. using trained spectrograms, precomputed audio blocks, or other ML means).
You may use any ML algorithm you’re comfortable with for the prediction, such as regression, PCA, classification, recurrent NNs, etc., and you may adapt your A1 solution if you want. Explain how your predictive compressor works in your assignment report.
In this part, your score target is 0.95, and your size target is 4.0 MiB (4194304 bytes). Note the reduced score target compared to part 1 – your prediction-based approach might only be able to roughly approximate the original signal.
Part 3. Combining Prediction and DCT (25%) cs assignment代写
One challenge with a purely predictive compressor is that the predictions (labels) might bewrong, resulting in an error at the decompressor. Or, the decompressor might not be able to reconstruct the original signal accurately even from a correct label. To mitigate this, real systems also encode an error alongside the predictive data.
In this part, you will combine a predictive compressor with DCT encoding of an error term. In brief, your compressor willalso run the predictive decompressor, comparing the output to the original input. You will then encode the difference between these signals using DCT-based compression, and include that in the final compressed data stream. Because the error term is expected to have much smaller magnitude than the original signal, you can employ a lossier quantization matrix and thereby get higher compression ratios.
In this part, your score target is 0.99, and your size target is 3.0 MiB (3145728 bytes).
Hints
This is a complex assignment, but keep in mind that you can make optimizations for the given dataset. This is not uncommon in real-world compression tasks; for example, the Hutter Prize is awarded for the best compressor on a very specific 100MB chunk of Wikipedia. cs assignment代写
In Python, you may save a set of arrays as a binary file using the numpy.savez function.This format is relatively efficient, as long as you choose your datatypes carefully.
One particular fact that may come in handy: the input file actually consists of four separate pieces of music, separated by short gaps of silence. Each piece has a different tempo (notes per minute) and style, so you might consider compressing them separately.
更多代写：代码代写 Gmat代考 英国Econ代上网课 博士Essay代写 伯明翰大学酒店管理学论文代写 代写JAVA设计编程价格
