Unit 04 - Compression Flashcards

Question

What is the compression process?

Answer 1

The encoder takes strings as input and uses a codetable to decide on which codewords to produce Input Data Stream -> Encoder -> Data storage or transmission -> Decoder -> Output data stream The decoder takes codewords as input and uses the same codetable to decide on which characters to produce to recreate the string

Answer 2

Encoder and decoder pass the encoded data as a series of codewords, along with the codetable. The codetable can be passed explicitly or implicitly, by: -sending it across -agreeing on it beforehand (hard wired) -recreate it from the codewords (clever!)

Answer 3

Symmetric compression: time to encode = time to decode Asymmetric compression: time to encode < decoding Symmetric algorithms are consequently often used for live activities, like streaming media Asymmetrical algorithms are useful for backing up or exporting.

Answer 4

The measurement of the entropy of a thing tells you how much information you need to describe it. Example: You can describe hhhhhhhh with just 9*h – it has low entropy The string arghbdqwplsk!? requires more information to describe – it has higher entropy Entropy encoding is lossless & independent of the specific characteristics of the medium being compressed. Common examples of entropy encoding: ● Run-length ● Huffman ● Lempel Ziv Welch

Answer 5

Run-length encoding (RLE) is a simple early & simple compression method (used by MacPaint & fax machines) ● Leverages repeating data (called runs) ● Data are represented by a count of the run length along with the original data (e.g. AAAABB => 4A2B)

Answer 6

1. Count until there is a change in data 2. Then start the next count 3. Repeat - while moving cell-by-cell: left-right, top-bottom

Answer 7

Run-length encoding is lossless and has fixed-length codewords -Best for images with solid backgrounds (e.g. cartoons) -Less effective for natural images (e.g. photos) and English text, where runs are short Run-length encoding is almost always a part of a larger compression system, like JPEG

Answer 8

While run-length codewords are fixed length, Huffman codewords are variable length ● Length of codewords is inversely proportional to frequency ● In variable length compression one code cannot be the prefix of another ● A binary tree structure guarantees this

Answer 9

There are two major parts in Huffman Encoding 1. Build a Huffman Tree from input characters 2. Traverse the Huffman Tree and assign codes to characters

Answer 10

I’m going to encode the string: this is my example ● 18 characters ● 1 character = 8 bits ● 18 characters * 8 bits = 144 bits ● My string is 144 bits before compression ● Let’s see if we can improve on that! ● Characters include: letters, punctuation, spaces

Answer 11

1. Build a tree A. Create a leaf node for each unique character (*case sensitive) and build a min heap (a list) of all leaf nodes. ○ I’ll be attempting to encode the 18-character phrase: this is my example ○ Go through your encoding string and add a row every time you encounter a unique character ○ Add a tick mark beside it every time you encounter it (including the first) ○ Sum up the ticks for each row and write that number in a new column (Count) Char Freq Count t | 1 h | 1 i || 2 s || 2 _ ||| 3 m || 2 y | 1 e || 2 x | 1 a | 1 p | 1 l | 1

Answer 12

1. Build a tree A. ... ○ Add up ALL the counts & make sure that total = the number of characters in your string. ○ Sort the table by the count column (descending), so your table has most frequent characters at the top. Char Freq Count _ ||| 3 i || 2 s || 2 m || 2 e || 2 t | 1 h | 1 y | 1 x | 1 a | 1 p | 1 l | 1

Answer 13

1. Build a tree B. Take the bottom two characters (the ones with the minimum frequencies) out of your list. ○ In my example: ■ p (frequency: 1) ■ l (frequency: 1) Char Count _ 3 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 14

1. Build a tree C. Create a new node with a frequency equal to the sum of the two nodes frequencies. Note the order you put the nodes. If you keep them consistent, it will help you with decoding later. Add this new node back to the list (wherever it belongs in order). pl (2) p1 l1 _3 i2 s2 m2 e2 t1 h1 y1 x1 a1 Char Count _ 3 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 15

1. Build a tree D. Then repeat this process until you run out of nodes For anything other than super short strings, it can take a while _3 i2 s2 m2 e2 t1 h1 y1 pl (2) ax (2) p1 l1 a1 x1 Char Count _ 3 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 16

1. Build a tree _3 i2 s2 m2 e2 t1 pl (2) ax (2) hy (2) p1 l1 a1 x1 h1 y1 Char Count _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 17

1. Build a tree _3 i2 s2 m2 pl (2) ax (2) hy(2) et (3) p1 l1 a1 x1 h1 y1 e2 t1 Char Count et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 18

1. Build a tree _3 i2 pl (2) ax (2) hy(2) et(3) sm (4) p1 l1 a1 x1 h1 y1 e2 t1 s2 m4 Char Count sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 19

1. Build a tree pli(4) sm(4) et(3) hy(2) ax(2) pl(2) s2 m2 e2 t1 h1 y1 a1 x1 p1 l1 i2 Char Count pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1 p 1 l 1

Answer 20

1. Build a tree hyax(4) pli(4) sm (4) et(3) hy(2) ax(2) pl(2) s2 m2 e2 t1 h1 y1 a1 x1 p1 l1 i2 Char Count hyax 4 pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1 a 1

Answer 21

1. Build a tree et_(6) hyax(4) pli(4) et(3) sm(4) hy(2) ax(2) pl(2) e2 t1 _3 s2 m2 h1 y1 a1 x1 p1 l1 i2 Char Count et_ 6 hyax 4 pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1 x 1

Answer 22

1. Build a tree smpli (8) et_ (6) hyax(4) pli(4) et(3) sm(4) hy(2) ax(2) pl(2) e2 t1 _3 s2 m2 h1y1 a1x1 p1 l1 i2 Char Count smpli 8 et_ 6 hyax 4 pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1 y 1

Answer 23

1. Build a tree et_hyax (10) smpli(8) et_(6) hyax(4) pli(4) et(3) hy(2)ax(2) sm(4) pl(2) e2t1_3 h1y1 a1x1 s2m2 p1l1 i2 Char Count et_hyax 10 smpli 8 et_ 6 hyax 4 pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1

Answer 24

1. Build a tree et_hyaxsmpli (18) 0 1 et_hyax (1) smpli(8) et_(6) hyax(4) pli(4) et(3) hy(2)ax(2) sm(4)pl(2) e2t1_3 h1y1 a1x1 s2m2p1l1i2 Char Count et_hyax 10 smpli 8 et_ 6 hyax 4 pli 4 sm 4 et 3 _ 3 hy 2 ax 2 pl 2 i 2 s 2 m 2 e 2 t 1 h 1

Answer 25

2. Traverse the Huffman Tree and assign codes to characters so at the top is et_hyaxsmpli (18) to the left down would be 0 to the right down would be 1 it follows this pattern so left is 0 and to the right is 1 at the bottom you get your code so for example, if you go all the way down the left and keep going left you would get 0000 the char _ would be 001 i would be 111 because i at the bottom is all the way at the bottom right Do this for all the characters and you get Char Count Code _ 3 001 i 2 111 s 2 100 m 2 101 e 2 0000 t 1 0001 h 1 0100 y 1 0101 x 1 0111 a 1 0110 p 1 1100 l 1 1101

Answer 26

Recall that the original string was 144 bits uncompressed because there was 18 characters x 8 bits because 1 character = 8 bits 18 characters * 8 bits = 144 bits before compression To calculate the size of the compressed string: 1. Calculate the number of bits per code 2. Multiply the number of bits by the count for each character 3. Add them all up (count size) =63 bits when you add up all of the count size Char Count Code Size (bits) Count * Size _ 3 001 3 9 i 2 111 3 6 s 2 100 3 6 m 2 101 3 6 e 2 0000 4 8 t 1 0001 4 4 h 1 0100 4 4 y 1 0101 4 4 x 1 0111 4 4 a 1 0110 4 4 p 1 1100 4 4 l 1 1101 4 4 Just multiply the bits by the count to get the count size So 3 count * 3 size (bits) = 9 count size and then add up all the count sizes to get the size of the compressed string which is 63 bits

Answer 27

Compression ratio = uncompressed size/compressed size Compression Ratio = 144/63 Compression Ratio = 2.3

Answer 28

Browse the tree from root to leaves (top to bottom) until you reach an existing leaf. This is the decoded character 000101001111000011111000011010101001000001110110101110011010000 this is my example

Answer 29

Assuming the correct probabilities (or frequencies), Huffman coding is optimal for encoding single characters (Relatively) quick and easy to implement

Answer 30

Not optimal for encoding multiple characters with a single encoding Requires two passes for both encoding and decoding Avoid this by sending the tree (takes time) or using consistent frequencies (less efficient)

Answer 31

1. Calculate the number of bits per code, meaning if the code is 001 the number or size of bits is 3. If the code is 0000 then the number or size of bits is 4. 2. Multiply the number of bits by the count for each character The count just means how many times this character appears in the string. For example, i appears 2 times in the phrase: "This is my example" so that means i has a count of 2. So you multiply the number of bits, for i in this case the number of bits is 3 because the code for i is 111. You multiply 3 by the size of bits which is 3 because of the code 001. so 3 x 3 = 9 and that's your count size. You then do this to each character that appears in the string. 3. Add them all up (Count size) so 9+6+6+6+8+4+4+4+4+4+4+4 = 63 bits based on our example "This is my example"

Answer 32

You take the uncompressed size which is the number of characters times 8 bits because 1 character is 8 bits. So "This is my example" has 18 characters in it. 18 * 8 = 144 bits This is your uncompressed size You then take your compressed size which is 63 bits after adding up all the count sizes which you get by multiplying the count (how many times the character appears in the string) by their size(bits) (determined by code, so 000 = 3, 0000 = 4) You divide the uncompressed size by the compressed size so: 144/63 = 2.3

Answer 33

Lempel Ziv Welch (LZW) ● A lossless compression algorithm ● Previous methods worked only on characters, but LZW works by encoding strings ● This makes it possible to encode some longer strings with a single codeword

Answer 34

The string to codeword mappings are created dynamically by the encoder ● ... and also recreated dynamically by the decoder, so there’s no need to pass the codetable between the two

Answer 35

1. Create a dictionary with all the possible input characters 2. Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary 3. The index for the string without the last character (longest substring that is in the dictionary) is retrieved from the dictionary and sent to output 4. The new string (including the last character) is added to the dictionary with the next available code 5. The next input character in your string is then used as the starting point to scan for substrings, repeating Steps 2–5 until complete

Answer 36

Now, let's suppose our input stream we wish to compress is: banana_bandana Create a dictionary with all the possible input characters The individual characters are the first entries. Index Entry 0 a 1 b 2 d 3 n 4 _

Answer 37

Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary. The longest substring that is in the dictionary is retrieved from the dictionary and sent to output Recall that our string is: banana_bandana And b is already in the dictionary, but ba is not (yet!) Index Entry 0 a 1 b 2 d 3 n 4 _ Encoded output:

Answer 38

banana_bandana The next string that isn’t yet in the dictionary is: ba Add that to the dictionary at the next available index (just count up). Index Entry 0 a 1 b 2 d 3 n 4 _ 5 ba Encoded output: 1

Answer 39

Step 2. Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary. Recall that our string is: banana_bandana The next string that isn’t yet in the dictionary is: an Index Entry 0 a 1 b 2 d 3 n 4 _ 5 ba 6 an Encoded output: 1,0

Answer 40

Step 2. Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary. Recall that our string is: banana_bandana The next string that isn’t yet in the dictionary is: na Index Entry 0 a 1 b 2 d 3 n 4 _ 5 ba 6 an 7 na Encoded output: 1,0,3

Answer 41

Step 2. Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary. Recall that our string is: banana_bandana The next string is: an ... but that already is in the dictionary (entry 6!) No new entries. But next step, we’ll have to add 6 to the encoded output. Index Entry 0 a 1 b 2 d 3 n 4 _ 5 ba 6 an 7 na Encoded output: 1,0,3

Answer 42

Step 2. Scan through the input string for successively longer substrings until you find one that is not yet in the dictionary. Recall that our string is: banana_bandana So move to the next string that is not yet in the dictionary: ana Remember to add Index 6: an to our encoded output. Index Entry 0 a 1 b 2 d 3 n 4 _ 5 ba 6 an 7 na 8 ana Encoded output: 1,0,3,6

Answer 43

Adapts to the content ● Simple and fast ● Good compression ● Compresses in a single pass: A dynamic codetable built for each file, but the decoder recreates the codetable, so it does not need to be passed

Answer 44

Not the optimum compression ratio ● Actual compression hard to predict ● Compression doesn't typically start until a large number of bytes (> 100) are read in

Answer 45

Used in ZIP and GIF encoding and decoding applications ● Patent expired mid 2003 for the US, mid 2004 for the rest of the world ● IBM’s own variant patent expired Aug 11, 2006 ● Open source GIF encoders & decoders are now legal!

Answer 46

RLE, Huffman, and LZW are all lossless and entropy based ● Lossless methods are essential for computer data (zip, gnuzip, etc) ● Run-length encoding + Huffman encoding is a standard combined tool ● They are often used as a subroutine by other lossy methods (JPEG, MPEG)

Answer 47

Source encoding takes into account type of data (e.g. visual). It is typically lossy, but can be lossless. Common types of source encoding: ● JPEG, GIF (images) ● MPEG (video) ● MP3 (audio) Source encoding often uses entropy encoding as a sub-routine.

Answer 48

Source encoding is typically lossy, but can be lossless

Answer 49

1. Transform methods ● Used for "natural" data like audio signals or photos ● Knowledge of the application is used to choose information to discard, thereby lowering its bandwidth ● Remaining information is then compressed via various methods 2. Predictor methods ● For sequences ● Leverage temporal coherence to store only the difference between the actual value and prediction of that value ● Simplest possible prediction is just to use the previous value

Answer 50

JPEG is not a file format, it's a lossy compression method Published in 1992 Supports a maximum image size of 65,535 x 65,535 pixels, up to 4 gigapixels for an aspect ratio of 1:1

Answer 51

How to JPEG 1. Partition image into 8 by 8 picture macroblocks 2. Discrete cosine transform (DCT) each block (going from left to right) 3. Remove high-frequency data by quantizing the DCT coefficients 4. Entropy code the reduced coefficients 5. Display the image by reconstructing it through decompression

Answer 52

discrete cosine transform (DCT) a process that compresses images separates an image into its luminance and chrominance These spectral sub-bands are given differing importance, by mapping them onto cosine waves to generate DCT coefficients

Answer 53

The loss-producing (lossy) step Compresses a range of DDCT coefficients into a single value Each DCT coefficient is divided by a quantization value and rounded A standard quantization table is 8 by 8 Larger values (more loss) at higher frequencies

Answer 54

1. Take quantized DCT coefficients and store them together as a sequence of integers 2. Perform run-length encoding (ordered as a zig-zag to maximize the chance of a run) 3. Do Huffman encoding on the runs - this is a lossless step Compression ratios of 20:1 are common!

Answer 55

JPEG is lossy JPEG is better for storing photographs and realistic images. PNG is lossless Better for storing line drawings, text, and iconic graphics. Both are common choices for use on the web.

Answer 56

Short for Graphics Interchange Format Pronounced with a hard G, like guppy or good Palette of up to 256 different colours Relies on Lempel-Ziv-Welch (LZW) lossless data compression method

Answer 57

Bitrate is the number of bits per second that can be transmitted along a digital network. Higher bitrate, more data, higher quality video. But! Recall Higher compression = smaller files = more loss lower compression = bigger files = less loss

Answer 58

I-frame (Intra-coded): a full image, like a JPG or BMP image file. P-frame (Predicted): holds only the changes in the image from the previous frame. Also known as delta-frames. B-frame (Bidirectional predicted): even more efficient by predicting content, using differences between the current frame and the frames that are before and after it.

Answer 59

So many standards! The full set of MPEG standards is long and includes a lot of different types of specification. Full knowledge of them all is NOT required for this course.

Answer 60

Released in 1993 Intended for storage of synchronized audio and video signals on CD Optimized for NTSC TV, with 324 x 240 pixel resolution, same frame rate as broadcast TV (~29.97 fps) Non-interlaced (progressive scanning) Typical compression is 26:1

Answer 61

Designed for studio quality motion video Handles a resolution of 720 x 480 Both progressive and interlaced scan modes Actually emerged as a standard for HDTV (High definition television)

Answer 62

Designed to handle HDTV It became unnecessary because MPEG-2 was found able to accommodate HDTV

Answer 63

MPEG-4 absorbed and improved on many of the features of MPEG-1 and MPEG-2 and other related standards Ability to encode mixed media data (video, audio, speech) Error resilience for robust transmission Initially intended for low bit-rate video communications Expanded to be efficient across a variety of bitrates (from several kbps to tens of mbps)

Answer 64

Uses predictor method for video sequences Basically JPEG with some prediction, also called motion compensation Assuming a frame rate of 30fps: Two frames in a row do not vary a lot in 1/30th of a second unless the camera is moving very fast!

Answer 65

MPEG-4 Part 10, Advanced Video Coding (AVC) A more advanced compression method than MPEG-4 & very popular Higher compression rate (1.5-2x more efficient) than MPEG-4 ratio of about 2000:1 Better image quality More fluent playback lower bitrate required for network transmission Now part of MPEG-4 (part 10 aka AVC)

Answer 66

MPEG-4 Part 14 Introduced in 2001 A digital multimedia container format most commonly used to store video and audio Can also store other data (subtitles, images) Supports streaming Most digital platforms and devices support MP4

Unit 04 - Compression Flashcards

(90 cards)