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 pictureRequires uncompressed bit rate of 80 Mbits/sec2Requires 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 alphabetUsually 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 compressionDifferent 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 iil6Possible 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 )1140 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 photosLZ 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
View Full Document