Why Compress?CompressionRedundancyHuman Perception FactorsClassificationEntropyHuffman CodingRun-length CodingLempel-Ziv-Welch (LZW) CodingArithmetic CodingSummaryImage and Video CompressionJPEG EncoderImage/block PreparationDCT ComputationQuantizationQuantization TableEntropy CodingDifferential EncodingRun-length EncodingHuffman EncodingFrame BuildingVideo CompressionFrame/Picture TypesPicture SequenceMPEG-video EncodingWhy Compress?•To reduce the volume of data to be transmitted (text, fax, images)•To reduce the bandwidth required for transmission and to reduce storage requirements (speech, audio, video)Compression•How is compression possible?–Redundancy in digital audio, image, and video data–Properties of human perception•Digital audio is a series of sample values; image is a rectangular array of pixel values; video is a sequence of images played out at a certain rate•Neighboring sample values are correlatedRedundancy•Adjacent audio samples are similar (predictive encoding); samples corresponding to silence (silence removal)•In digital image, neighboring samples on a scanning line are normally similar (spatial redundancy)•In digital video, in addition to spatial redundancy, neighboring images in a video sequence may be similar (temporal redundancy)Human Perception Factors•Compressed version of digital audio, image, video need not represent the original information exactly•Perception sensitivities are different for different signal patterns•Human eye is less sensitive to the higher spatial frequency components than the lower frequencies (transform coding)Classification •Lossless compression–lossless compression for legal and medical documents, computer programs–exploit only data redundancy•Lossy compression–digital audio, image, video where some errors or loss can be tolerated–exploit both data redundancy and human perception properties•Constant bit rate versus variable bit rate codingEntropy•Amount of information I in a symbol of occurring probability p : I = log2(1/p)•Symbols that occur rarely convey a large amount of information•Average information per symbol is called entropy HH = pix log2(1/pi) bits per codeword•Average number of bits per codeword = Nipi where Ni is the number of bits for the symbol generated by the encoding algorithmHuffman Coding•Assigns fewer bits to symbols that appear more often and more bits to the symbols that appear less often•Efficient when occurrence probabilities vary widely•Huffman codebook from the set of symbols and their occurring probabilities•Two properties:–generate compact codes–prefix propertyRun-length Coding•Repeated occurrence of the same character is called a run•Number of repetition is called the length of the run•Run of any length is represented by three characters–eeeeeee7tnnnnnnnn–@e7t@n8Lempel-Ziv-Welch (LZW) Coding•Works by building a dictionary of phrases from the input stream•A token or an index is used to identify each distinct phrase•Number of entries in the dictionary determines the number of bits required for the index -- a dictionary with 25,000 words requires 15 bits to encode the indexArithmetic Coding•String of characters with occurrence probabilities make up a message•A complete message may be fragmented into multiple smaller strings•A codeword corresponding to each string is found separatelySummary•Statistical encoding exploits the fact that not all symbols in the source information occur with equal probability•Variable length codewords are used with the shortest ones used to encode symbols that occur most frequently•Static coding -- text type is pre-defined and codewords are derived once and used for all subsequent transfers •Dynamic coding -- type of text may vary from one transfer to another and same set of codewords are generated at the transmitter and the receiver as the transfer takes placeImage and Video Compression•Two dimensional array of pixel values•Spatial redundancy and temporal redundancy•Human eye is less sensitive to chrominance signal than to luminance signal (U and V can be coarsely coded)•Human eye is less sensitive to the higher spatial frequency components•Human eye is less sensitive to quantizing distortion at high luminance levelsJPEG Encoder•International standards body -- Joint Photographic Experts Group•JPEG encoder schematic•Image/block preparation•DCT computation•Quantization•Entropy coding -- vectoring, differential encoding, run-length encoding, Huffman encoding•Frame buildingImage/block Preparation•Source image as 2-D matrix of pixel values•R, G, B format requires three matrices, one each for R, G, B quantized values•In Y, U, V representation, the U and V matrices can be half as small as the Y matrix•Source image matrix is divided into blocks of 8X8 submatrices•Smaller block size helps DCT computation and individual blocks are sequentially fed to the DCT which transforms each block separatelyDCT Computation•Each pixel value in the 2-D matrix is quantized using 8 bits which produces a value in the range of 0 to 255 for the intensity/luminance values and the range of -128 to + 127 for the chrominance values. All values are shifted to the range of -128 to + 127 before computing DCT•All 64 values in the input matrix contribute to each entry in the transformed matrix•The value in the location F[0,0] of the transformed matrix is called the DC coefficient and is the average of all 64 values in the matrix•The other 63 values are called the AC coefficients and have a frequency coefficient associated with them•Spatial frequency coefficients increase as we move from left to right (horizontally) or from top to bottom (vertically). Low spatial frequencies are clustered in the left top corner.Quantization•The human eye responds to the DC coefficient and the lower spatial frequency coefficients•If the magnitude of a higher frequency coefficient is below a certain threshold, the eye will not detect it•Set the frequency coefficients in the transformed matrix whose amplitudes are less than a defined threshold to zero (these coefficients cannot be recovered during decoding)•During quantization, the size of the DC and AC coefficients are reduced •A division operation is performed using the predefined threshold value as the divisorQuantization Table•Threshold values vary for each of the 64 DCT coefficients and are held in a 2-D matrix•Trade off between
View Full Document
Unlocking...