1COMP 249 Advanced Distributed SystemsMultimedia Networkinghttp://www.cs.unc.edu/~jeffay/courses/comp249f99The Video Data TypeCoding & Compression BasicsKevin JeffayDepartment of Computer ScienceUniversity of North Carolina at Chapel [email protected] 7, 19992The Video Data TypeOutline! What is video?» Video components» Representations of video signals» Color spaces! Digital Video» Coding! Compression basics» Simple compression» Interpolation-based techniques» Predictive techniques» Transforms» Statistical techniques3Video BasicsThe components of video! Video deals with absorbed and projected light» Cameras absorb light and monitors project light! The primary colors in this domain are:» red, green, and blueR-valueG-valueB-value4Video BasicsThe components of video transmission! Video is a multi-dimensional signalR-component G-component B-componentxytime5Video BasicsVideo as a 1-dimensional signal! Representation of a 2-dimensional image(R, G, B)11, (R, G, B)12, (R, G, B)13, ..., (R, G, B)row, col ! Representation of motion (3-dimensional images)Frame i Frame i+133 ms NTSC (30 fps)40 ms PAL (25 fps)6Video BasicsResolution! Television broadcaststandards» NTSC — 525 lines» PAL — 625 lines! Computer graphicsstandards» VGA — 640x480» SVGA — 1024x768! Multimedia standards» CIF — 352x288» QCIF — 176x144! Digital video standards» CCIR 601 — 720x480» HDTV — 1440x1152NTSC (440x480)H.261 CIF (352x288)Image sizes (in picture elements)DVI (256x240)QCIF (176x144)Videophone (128x112)7Video BasicsColor spaces! RGB is not widely used for transmitting a signal betweencapture and display devices» It’s difficult to manage 3 separate inputs & outputs(and requires too much bandwidth)! Composite formats are used instead» Luminance (“Y”) — the brightness of the monochrome signal» Chrominance — the coloring information» Chrominance is typically represented by two “color difference”signals:❖ “U” and “V” (“hue and tint”) or❖ “I” and “Q” (“saturation” and “color”)8Video BasicsColor spaces! NTSC video» Y = 0.30R + 0.59G + 0.11B» I = 0.60R – 0.28G – 0.32B» Q = 0.21R – 0.52G + 0.31B! PAL video/Digital recorders» Y = 0.3R + 0.6G + 0.1B» U = (B – Y) x 0.493» V = (R – Y) x 0.877RBGWhiteR=G=B(gray values)RBGU = 0 PlaneV = 0PlaneY = 19Video BasicsDigital video! Sample an analog representation of video (RGB orYUV) & quantize» Two dimensions of video are already discretized» Sample in the horizontal direction according to theresolution of the media! 8-bits per component per sample is common» 24 bits per picture element (pixel)! Storage/transmission requirements» NTSC — 440 x 480 x 30 x 24 = 152x106 bits/sec (19 MB/s or 24 bits/pixel (bpp))10The Video Data TypeOutline! What is video?» Video components» Representations of video signals» Color spaces! Digital Video» Coding! Compression basics» Simple compression» Interpolation-based techniques» Predictive techniques» Transforms» Statistical techniques11! Do we really need every “bit” of a video stream?» Not if redundancy exists» Not if we can’t perceive the effect of eliminating the bitDigital VideoCompression Techniques! Eliminating imperceptible detail» Coding» Domain transformation! Eliminating redundancy» Spatial redundancy» Temporal redundancy12Digital VideoCompression TechniquesTruncationCLUTRun-lengthTruncationCLUTRun-lengthSub-samplingSub-samplingDPCMMotionCompensationDPCMMotionCompensationDiscreteCosineTransformDiscreteCosineTransformHuffman &ArithmeticcodingHuffman &ArithmeticcodingVideoCompressionAlgorithmVideoCompressionAlgorithmAdapted from Buford p.147Fixed AdaptiveColorComponentsColorComponentsBitAssignmentBitAssignmentVideoInputCompressedBit-StreamSimpleInterpolativePredictiveTransformStatistical(PCM Signals)13Video CompressionIssues! Bandwidth requirements of resulting stream» Bits per pixel (bpp)! Image quality! Compression/decompression speed» Latency» Cost» Symmetry! Robustness» Tolerance of errors and loss! Application requirements» Live video» Stored video14Simple Image CompressionTruncation! Reducing the number of bits per pixel» Throw away the least significant bits of each sample value! Example» Go from RGB at 8 bits/component sample (8:8:8) to 5 bits(5:5:5)❖ Go from 24 bpp to 15 bpp❖ This gives “acceptable results”» Go from YUV at 8 bits/component sample 6:5:5 (16 bpp)! Advantage — simple!15Simple Compression SchemesColor-table lookup (CLUT)! Quantize coarser in the colordomain» Pixel values represent indicesinto a color table» Tables can be optimized forindividual images! Entries in color table stored at“full resolution” (e.g. 24 bits)! Example:» 8-bit indices (256 colors) gives(440 x 480) x 8 + (24 x 256) = 1.7x106 bits/sec0 1 2 3 4 5 6 7 ...01234567...16Simple Compression SchemesRun-length encoding! Replace sequences of pixel components with identicalvalues with a pair (value, count)! Works well for computer-generated images, cartoons.works less well for natural video! Also works well with CLUT encoded images(i.e., multiple techniques may be effectively combined)17 23 54 54 54 54 54 54 54 22 1117 23 (54, 7) 22 11RLE17Interpolative Compression SchemesColor sub-sampling! Do not acquire chrominance component values at allsampling points» Humans have poor acuity for color changes» UV and IQ components were defined with this in mind! Example: Color representation in digital tape recorders» Subsampling by a factor of 4 horizontally is performedY component U component V component18Interpolative Compression SchemesColor sub-sampling! Subsampling by a factor of 4 horizontally & vertically! Interpolating between samples provides “excellent” results» Chrominance still sampled at 8 bppY component U component V component19Interpolative Compression SchemesColor sub-sampling! Intermediate pixels either take on the value of nearestsampling point or their value is computed by interpolation! Bi-linear interpolation:Sub-sampledU or V component............(0,0) (1,0)(0,1) (1,1)U(1, 1) = U(0,0)x0.75 + U(1,0)x0.25 + U(0,1)x0.75 + U(1,1)x0.25 U(1, 1) = U(0,0)x0.75 + U(1,0)x0.25 + U(0,1)x0.75 + U(1,1)x0.25 20Interpolative Compression SchemesColor sub-sampling! Storage/transmission requirements reduction:» Within a 4x4 pixel block: bpp = (8 bpp luminance)x16 samples + (8 bpp chrominance)x216 = 9» A 62.5% reduction overallY component U component V