Data Compression

An Introduction to Data Compression : 

Sam Janisko EMGT 520 - Information Systems Engineering Final Presentation April 4th, 2011 An Introduction to Data Compression

An Introduction to Data Compression : 

Introduction Compression is a way to deliver the same information with less data. Why compress data? Data expands with hardware improvements Goal is to reduce the volume of data Reduce bandwidth and time required for transmission Reduce costs associated with storing data Time and energy savings = $ savings An Introduction to Data Compression

An Introduction to Data Compression : 

Example Downloading digital color photograph given a 33.6 kbps modem: Uncompressed image (TIFF file) = 600 kbytes, 142 seconds Lossless compression (GIF file) = 300 kbytes, 71 seconds Lossy compression (JPEG file) = 50 kbytes, 12 seconds An Introduction to Data Compression

An Introduction to Data Compression : 

Compression Usage Uncompressed file types: TIFF, BMP, WAV, AIFF, etc. Generic file compression: ZIP, gzip, 7-zip, BOA, RAR, NTFS, etc. Multimedia : GIF, JPEG, PNG, MP3, MPEG, DivX, some HDTV, etc. Communication: ITU-T T4 Group 3 Fax, modems, etc. Databases: MDBC, specialized libraries and algorithms Other compression systems: zlib – software library used by Linux, Mac OS X, PS 3, Wii, iPhone and thousands of other applications An Introduction to Data Compression

An Introduction to Data Compression : 

Philosophy An Introduction to Data Compression Compression is possible by exploiting redundancies in the data and properties of human perception.

An Introduction to Data Compression : 

Redundancies An Introduction to Data Compression Text files Frequently used characters or groups of characters Image files Adjacent pixels in an image (spatial redundancy) Audio Files Silence (silence removal) Neighboring samples (predictive encoding) Video Files Similar neighboring images (temporal redundancy)

An Introduction to Data Compression : 

Properties of Human Perception An Introduction to Data Compression Human perception sensitivities can allow loss of data in some cases. - Losses are either imperceptible or, at worst tolerable.

An Introduction to Data Compression : 

Process and definitions An Introduction to Data Compression So = original file Sc = compressed file Su = decompressed file Compression ratio = Sc [bits] / So [bits] Codec – Encoder/Decoder (specific compression algorithms) bit = binary data 0 or 1 byte = 8 bits Encoder Decoder So Sc Su

An Introduction to Data Compression : 

Forms of data compression – Lossy vs. Lossless An Introduction to Data Compression Lossless Compression (So = Su) - Decompressed (decoded) data is identical to the source - executable code, word processing files, etc. Lossy Compression (So ~ Su) - Decompressed (decoded) data is not identical to the source - audio, video, images Encoder Decoder So Sc Su

Slide 10: 

Lossless compression: Basic techniques

Lossless Compression : 

Run Length Encoding (RLE) Lossless Compression Some files have same data repeated many times in a row. For example: Image of night sky (many black pixels in sequence) Silence between words or songs in audio files. White pixels in character spaces (70-80% white) Machine code files (long runs of binary sequences)

Lossless Compression : 

Run Length Encoding (RLE) Lossless Compression Suppose we had the following characters in a text file: HHHEEEELLLLLOOOOWWWWWWWWOOOOOORRLLLDDD [38 bytes] We could encode this sequence as: 3H 4E 5L 4O 8W 6O 2R 3L 3D [18 bytes] However, what about: HELLOWORLD [10 bytes] 1H 1E 2L 1O 1W 1O 1R 1L 1D [18 bytes] File inflation! Solution: HE@L2OWORLD [11 bytes, still inflating in this case, but better]

Lossless Compression : 

Lossless Compression A form of frequency dependent coding - Not all data appears with the same frequency. - Data can be coded based on the frequency distribution. More frequently appearing data or data groups can be assigned shorter bits than less frequent ones (variable output). Mathematically optimal when number of bits used to represent data is proportional to the logarithm of the data’s probability of occurrence. Huffman Encoding

Lossless Compression : 

Lossless Compression Huffman Encoding http://en.wikipedia.org/wiki/Huffman_coding “this is an example of a huffman tree” 0 1 1 0 0 1 1 0

Lossless Compression : 

Lossless Compression Huffman Encoding The encoder and decoder algorithms must use the same “dictionary”! Can use a single, predefined encoding table for all files, regardless of information. Can attach a file specific encoding table within the compressed file. Both methods are common.

Lossless Compression (sometimes) : 

Lossless Compression (sometimes) Delta Encoding Store the difference between successive data points rather than the points themselves. Useful for digital waveforms. Say you have a 10-bit digital audio signal with the following ADC values in the 0-1024 range: [100] [105] [107] [109] [111] [112] [103] [100] [97] Delta encoded signal: [100] [5] [2] [2] [2] [2] [-9] [-3] [-3] Since data is more redundant, follow delta encoding with run-length or Huffman encoding to get lossless compression. Or, store data in 5-bits (+/- 15) instead of 10! (Could be lossy)

Lossless Compression (sometimes) : 

Linear Predictive Coding LPC is similar to delta encoding Increase the redundancy of stored values Do this by predicting the next value, and storing the difference between the actual and predicted values. Actual signal: [100] [103] [107] [110] [113] [116] [120] [123] [129] Predicted signal: [NA] [100] [106] [111] [113] [116] [119] [124] [126] Difference between actual and predicted: [NA] [3] [1] [-1] [0] [0] [1] [-1] [3] More accurate prediction = more 0’s, +1’s and -1’s = redundancy! -Follow LPC with run-length/Huffman encoding Store values in fewer bits Lossless Compression (sometimes)

Lossless Compression : 

Lossless Compression Lempel Ziv (and Welch) Compression (LZ77,LZ78,LZW) LZW Most common algorithm for general purpose data compression English text, executable code, GIF, many other data files LZ Compressor family looks for patterns in the data, regardless of length, and creates a dictionary for redundant sequences. LZW can reduce long lengths of English text by 50%. Longer message = higher compression ratio

Lossless Compression : 

Lossless Compression LZ77 Compression A sliding window example: waitressing is a fun job. however, I don’t like waiting on rude customers, dressing up or waiting for my tips. Compressed: waitressing is a fun job. however, I don’t like [4][48]ing on rude customers or d[7][64] up or [4][44]ting for my tips.

Lossless Compression : 

Lossless Compression LZW Compression A fixed dictionary example: TOBEORNOTTOBEORTOBEORNOT# http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch How can this be efficient? Extended dictionary does not have to be sent! - Decoder just needs to know initial dictionary, can figure the rest out as it decodes.

Slide 21: 

Lossy compression: Basic techniques

Lossy Compression : 

Lossy Compression Important points Decompression results in an approximation of the original data - Preserve perceptible information, not exact digital information. “Lossy” = loss of information, not loss of quality. Usage? - Mostly in multimedia (image data, movie data, audio data) - This data is intended for human interpretation - An ABX test can validate the imperceptibility of lossy compression

Lossy Compression : 

Lossy Compression Basic types of codecs 1. Lossy predictive codecs Linear predictive coding presented earlier. The delta between the predicted data and the real data is encoded. Losses will occur when delta is larger than bit-storage capacity. ie. 1 byte only allows for errors within +/- 128. 2. Lossy transform codecs Look at small groups of data (a complex waveform) Use mathematical transform functions to represent the group in as sine or cosine waves (simple waveforms) Fourier Transform Discrete Cosine Transform

Lossy Compression : 

Lossy Compression Lossy transform codecs – Audio example Image Source: http://dvd-hq.info/data_compression_2.php In this example, all you need is: Amplitude x3 (16 bits) Frequency x3 (16 bits) Phase x3 (16 bits) Total storage = 18 bytes Express entire signal as sums of waveforms.

Lossy Compression : 

Lossy Compression Other important concepts Perceptual coding - psychovisual and psychoacoustic Use known characteristics of human perception to guide compressor There is no point in storing information that cannot be perceived by humans. Example: Human hearing ranges from 20 Hz to 20 KHz - Other frequencies can be omitted Human hearing prioritizes certain sounds ahead of others (Masking) Less important data can be stored in fewer bits

Lossy Compression : 

Lossy Compression Other important concepts Bit allocation Reduce the number of bits for storage of data samples. For example GIF file format uses single byte encoding per pixel (8 bits or 256 possible colors) http://dvd-hq.info/data_compression_2.php

Lossy Compression : 

Lossy Compression MP3 Compression So, how do you compress digital audio into an MP3 file? Separate the uncompressed audio file into sections or blocks Approximate the waveform in each section with transform coding Store frequency and amplitude data 3) Analyze frequency and amplitude data against psychoacoustic model Remove unnecessary data Identify the priority of the data Determine where masking can occur 4) Perform bit allocation on each block Allocate less storage bits for blocks with higher masking

Lossy Compression : 

Lossy Compression JPEG Compression - Lossy image compression Image Source: http://www.eetimes.com/design/signal-processing-dsp/4017500/Data-compression-tutorial-Part-3?pageNumber=0 8x8 pixel block Discrete Cosine Transform Quantization (losses) Run Length, Huffman Encoding to .jpg file

An Introduction to Data Compression : 

An Introduction to Data Compression REFERENCES: Smith, Steven W. (2010). “Data Compression Tutorial: Part 1”. Retrieved April 2nd, 2011, from: http://www.eetimes.com/design/signal-processing-dsp/4017497/Data-compression-tutorial-Part-1. Smith, Steven W. (2010). “Data Compression Tutorial: Part 2”. Retrieved April 2nd, 2011, from: http://www.eetimes.com/design/signal-processing-dsp/4017497/Data-compression-tutorial-Part-2. Smith, Steven W. (2010). “Data Compression Tutorial: Part 3”. Retrieved April 2nd, 2011, from: http://www.eetimes.com/design/signal-processing-dsp/4017497/Data-compression-tutorial-Part-3. Sayood, Khalid. Introduction to Data Compression 2nd Ed. Morgan Kaufman, San Francisco, CA: 2000. Del-Negro, Rui (2010). “Data Compression Basics: Part 1 - Lossless data compression”. Retrieved April 1st, 2011, from: http://dvd-hq.info/data_compression_1.php Del-Negro, Rui (2010). “Data Compression Basics: Part 2 - Lossless data compression”. Retrieved April 1st, 2011, from: http://dvd-hq.info/data_compression_2.php Wikipedia (2010a). “Lossy Compression”. Retrieved April 2nd, 2011 from: http://en.wikipedia.org/wiki/Lossy_compression Wikipedia (2010b). “MP3”. Retrieved April 2nd, 2011 from: http://en.wikipedia.org/wiki/MP3#Encoding_audio Wikipedia (2010a). “Huffman Coding”. Retrieved April 2nd, 2011 from: http://en.wikipedia.org/wiki/Huffman_coding

An Introduction to Data Compression : 

An Introduction to Data Compression REFERENCES: Wikipedia (2010b). “Lempel Ziv Welch”. Retrieved April 2nd, 2011 from: http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch Blelloch, Guy E. (2010). “Introduction to Data Compression”. Retrieved March 15th, 2011, from: http://www.cs.cmu.edu/~guyb/realworld/compression.pdf Hacker, Scot (2010). “Inside the MP3 Codec”. Retrieved April 3rd, 2011, from http://www.mp3-converter.com/mp3codec/ Sound on Sound (2010). “Perceptual Coding: How Mp3 Compression Works”. Retrieved April 3rd, 2011, from http://www.soundonsound.com/sos/may00/articles/mp3.htm Wolfgang, Ray (2010). “JPEG Tutorial”. Retrieved April 3rd, 2011, from: http://cobweb.ecn.purdue.edu/~ace/jpeg-tut/jpegtut1.html Shaaban (2010). “Data Compression Basics” . Retrieved April 1st, 2011, from: http://meseec.ce.rit.edu/eecc694-spring2000/694-5-9-2000.pdf Diamond, Jim (2010). “A Very Introduction to Data Compression”. Retrieved April 1st, 2011, from: http://cs.acadiau.ca/~solid/presentations/xmlcompr-seminar05.pdf Princeton (2010). “Data Compression”. Retrieved April 1st, 2011, from: http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/compress.4up.pdf