1Video TransmissionVID4: Digital Video EncodingBy Prof. Gregory D. Durgincopyright 2009 – all rights reservedExample: Digitizing Analog Video Baseband signal has 5 MHz maximum frequency Remember: starting point is a lousy analog signal/ Nyquist sampling rate is 10 Msamples/sec Let’s assume 8-level quantization Requires 8 bits/sample Visible SNR of 48 dB – pretty good pictureRequires uncompressed bit rate of 80 Mbits/sec2Requires uncompressed bit rate of 80 Mbits/sec Way too fast for many wired connections Signal is still poor analog video plus quantization noise2Lossless Data Compression Representing a common and/or recurring combination of bits with reduced alphabetUsually reduces a digital data set to a smallerUsually reduces a digital data set to a smaller number of bits No loss of real data (perfect reconstruction) Likely combinations of bits get short bit sequences Unlikely combinations get long bit sequences3 Examples of lossless image compression include Huffman encoding, Lempel-Ziv  PCX, GIF, LZW, ZIP, PNGExample of Lossless Compression Test Sentence (101 characters) I am really excited that the Georgia Tech Yellow Jackets have a chance to beat the dogs inJackets have a chance to beat the dogs in November. Swap the following representations “zz” = “z”; “za” = “the_”; “zb” = “that_” “zc” = “ed_”; “zd” = “_in_”; “ze” = “have_”; 4 “zf” = “I_am_”; “zg” = “ed.”; “zh” = “er.”;  New Sentence (82 characters) zfreally excitzczbzaGeorgia Tech Yellow Jackets zea chance to beat zadogszdNovembzh3Challenge of Lossless Data Compression Most video and images have patterns that can be exploited for lossless data compressionDifferent images have different“pattern sets”Different images have different pattern sets How do we identify the patterns Option 1: Assume a priori pattern structure Option 2: Ad-hoc patterns, build-as-you-go5Run Length Encoding Compression used in PCX, Fax transmissions Works well on “cartoonish” images Basic Idea: Assign repetitive data sequences with low-bit gp qpossibilities in the alphabet PCX Image Simple form of Run-Length Encoding Repetitive colors (3 or more) are recorded as “[2 flag bits + 6 repetition bits] [color value]”Piblth “ d”fill th iil6Possible to have “compressed” file larger than original Easy to compute; early adoption in computer image use4Huffman CodingChar Freq Codespace 7 111a 4 010e 4 000f 3 1101h 2 1010i 2 1000m 2 0111n 2 0010s 2 1011t 2 0110l1110017l111001o 1 00110p 1 10011r 1 11000u 1 00111x 1 10010Lempel-Ziv Algorithm (LZ77 and LZ78) Build a pattern alphabet as you go Basic adaptive algorithm Very easy to implement with minimal memory Incorporated into types of image & video data Used in famous DEFLATE compression algorithm (i.e. ZIP and other archival tools) Lossless algorithm8g Near-optimum for very long data streams5Lempel-Ziv Algorithm Starting data sequence “those lame dogs lose the games” Parse data into the smallest non-repeatable chunks (1) t, (2) h, (3) o, (4) s, (5) e, (6) _, (7) l, (8) a, (9) m, (10) e_, (11) d, (12) og, (13) s_, (14) lo, (15) se, (16) _t, (17) he, (18) _g, (19) am, (20) es  Final coding: each chunk is written as previous portion reference # plus its last character:9portion reference # plus its last character: [0t][0h][0o][0s][0e][0_][0l][0a][0m][5_][0d][3g][4_][7o][4e][6t][2e][6g][8m][5s]Lempel-Ziv Algorithm Starting data sequence (73 bits) 01010101010101010101010101010101010101010101010101010101010101010101010101010101010 Parse data into the smallest non-repeatable chunks (1) 0, (2) 1, (3) 01, (4) 010, (5) 10, (6) 101, (7) 0101, (8) 01010, (9) 1010, (10) 10101, (11) 010101, (12) 0101010, (13) 101010, (14) 1010101, (15) 01010101,(16) 010101010 Final bit sequence (64 bits)10 [00][01][11][110][100][1101][1001][1110][01100][10011][01111][10110][10100][11011][11001][11110]6Final Comment Sampling, Quantization, and Compression are not independent designs in communication links Optimum solution is to do these together Example: Vocoder on cell phone Compression & quantization optimized together for speech Sounds terrible if you try to listen to a musical song Audio signal requires 40 kS l / li (20 kH f )1140 kSample/sec sampling (20 kHz max frequency) 60 dB of SNR for fidelity (10 bits/sample for uniform quant.) Total of 400 kbit/sec for high-quality, uncompressed voice Typical cellular vocoder works at 8 kbit/secJPEG -- Lossy Image Compression Joint Photographic Experts Group (1992) Loses original image information without the possibility of reconstructionpossibility of reconstruction Converts image from RGB to YCbCr. Chrominance is downsampled Each channel is converted to 2D freq domain Only keep the most significant freq components12yp g q p Add run length encoding (RLE) to reduce size JPEG 2000 Standard uses wavelet-based compression instead of discrete cosine transform7Image Discrete Cosine Transform Each block of 64 pixels is expressed as linear combination of the 64 tiles shown on the right Compression level is based on which coefficients are thrown away (from lower-right tl ft)13to upper-left) Explains JPEG/MPEG errors result in “blockish” errors in image framesVariable-Rate JPEG Compression42 kB23 kB149 kB13 kBall pics4:2:28Example Compression of Two PicturesSimpsons Kauai15Comparison of Compression SizesStorage Compression Simpsons Kauai BMP None 341 KB 3,073 KB PCXRLE171 KB2,732 KBPCX RLE 171 KB2,732 KBGIF RLE + LZ 142 KB 374 KB JPG Lossy 75 KB 142 KB  RLE works well on “cartoonish” figures, not on photosLZ algorithms dramatically improve photos16LZ algorithms dramatically improve photos JPG is always best (but lossy) Interesting that both photos reduce to similar order-of-magnitude sizes in JPG (they start off vastly different)9Digital Video Compression Redundancy in moving pictures from frame to frame Best video compression algorithms are“3D” taking advantage ofare 3D”, taking advantage of Patterns in single images Frame-to-frame patterns “Motion Vectors” within a scene Trade-off: the more redundancy you remove, the more catastrophic bit 17,perrors becomeSo Let’s Turn Analog Video To Digital MPEG1 – Moving