MM-lec 9.pdf

Data compression Compression: the process of coding that will effectively reduce the total number of bits needed to represent certain information, while is retaining necessary information The compression is performed by an encoder and decompression is performed by a de...

Data compression Compression: the process of coding that will effectively reduce the total number of bits needed to represent certain information, while is retaining necessary information The compression is performed by an encoder and decompression is performed by a decoder. 1  The reduction in file size is necessary to meet 1. The storage requirements in computer data base. 2. The bandwidth ) ‫(كمية البيانات‬requirements for many transmission systems. Compression ratio 2  Saving percentage: – This shows the shrinkage as a percentage. The reduction in size relative to the uncompressing size Example: – A source image file (pixels 256 × 256) with 65,536 bytes is compressed into a file with 16,384 bytes. – The compression ratio is 4. The saving percentage is: 75% 3  Question 1 An audio CD can store about 15 uncompressed songs. How many similar songs can be stored if they are Compress CD audio by a factor of 12. The number of song that can be stored is ----- 15 × 12 = 180  Question 2 An image has a size of 1920x1080 pixels with true color, which means that 3 Bytes per pixel are used for the color information. – How long does it take to transmit the uncompressed image via a 56 kbps Modem connection? – assume the image is compressed with a compression algorithm that reduces the image size by 85%. How long does it take to transmit the image via a 56 kbps Modem connection? 5 Data compression implies sending or storing a smaller number of bits. 15.6  Run length Encoding This is most efficient on data that contains many such runs. For files that do not have many runs, RLE could increase the file size. 1. Calculate the image size 2. Encode using Run length by encoding each line separately 3. Calculate the compression ratio  B- Huffman coding Huffman coding assigns shorter codes to symbols that occur more frequently and longer codes to those that occur less frequently. 15.11  Question 4 1. Construct the Huffman tree for the following data:{A,B,C,D,E} with frequency {0.17,0.11,0.24,0.33 and 0.15} respectively ,then decoded this string 2. Use the following string 100 00 011011 to show that your Huffman code is uniquely decodable  Question reconstructed using the decompressing algorithm 0110010010 decompression is done using Huffman decoding. Match the code words with code dictionary to get the reconstructed data. 13 2- lossy Compressed 14 15 16  How JPEG Compression Works JPEG is actually the name of the entity behind the file name. Joint Photographic Experts Group created the standard and published the first JPEG standard draft in 1992. JPEG uses lossy compression. Which means that information is lost in the compression process. 17 18  Color Space Transform and Subsampling Human eyes are more sensitive to brightness than color. For this reason, JPEG allocates more space for brightness information than color information. But to do so, we first have to separate these two components, known as luminance ‫األنارة‬and chrominance ‫التلوين‬. 19 Image 20 21  Color Space Transform and Subsampling JPEG uses the YCbCr color space. It consists of three components: – luma (Y), – blue-difference chroma (Cb), and – red-difference chroma (Cr). – The luma component represents brightness while the other two components (Cb and Cr) represent the color information. 22 23 24  JPEG After transforming RGB values into YCbCr values, Cb and Cr are downsampled by a factor of 2 (or 4). That means every 4 pixels (or 16 pixels) are averaged into one pixel. This downsampling is almost unnoticeable to the human eye. 25 26 27 28  This results in color bands with only 25% the size of the original ones. Since color bands make up two-thirds of the original raw data (YCbCr data), we will be reducing the size of the image by 50%. 29 Discrete Cosine Transformation (DCT) JPEG also compresses the brightness information by discarding small detail that is almost unnoticeable to the human eye. This is done by the Discrete Cosine Transformation. The Discrete Cosine Transformation separates the input into elements of different frequencies. In the case of an image, into elements of different detail levels. This is important if we want to discard small detail (high frequencies). 30 31  Quantization Now that we separated these values into different detail levels, we need to “discard” some of these detail. This is where quanti\ation comes into play. which intervals of data are grouped or binned into a single value (or quantum) 32 33  JPEG compression does this for both the luminance and chrominance channels. Now that we removed some detail in the high frequencies, how can this reflect on the file size of the image and thus compressing it? 34  Zigzag Scan After quantization, there is a big chance that most of the high-frequency coefficients are zero. If we order the coefficients from lowest frequencies to highest frequencies, we will get, with great probability, a lot of consecutive zeros. Instead of storing, for example, “0 0 0 0 0 0 0 0”, we can store 8×”0”. So how can we sort the coefficients from low to high frequencies? We do this using a zigzag scan. 35 36  Run Length Encoding (RLE) Run length encoding groups consecutive values together to save space. Instead of storing a value repeating n time, we store (n, value). 37 Exercise 39