CSEP 590Data CompressionAutumn 2007EBCOTJPEG 2000CSEP 590 - Lecture 12 - Autumn 2007 2History• Embedded Block Coding with Optimized Truncation (EBCOT)– Taubman – journal paper 2000– Algorithm goes back to 1998 or maybe earlier– Basis of JPEG 2000• Embedded– Prefixes of the encoded bit stream are legal encodings at lower fidelity, like SPIHT and GTW• Block coding– Entropy coding of blocks of bit planes, not block transform coding like JPEG.CSEP 590 - Lecture 12 - Autumn 2007 3Features at a High Level• SNR scalability (Signal to Noise Ratio)– Embedded code - The compressed bit stream can be truncated to yield a smaller compressed image at lower fidelity– Layered code – The bit stream can be partitioned into a base layer and enhancement layers. Each enhancement layer improves the fidelity of the image• Resolution scalability– The lowest subband can be transmitted first yielding a smaller image at high fidelity.– Successive subbands can be transmitted to yield larger and larger imagesCSEP 590 - Lecture 12 - Autumn 2007 4Block Diagram of EncoderwavelettransformPartition intocoding blocksimagewavelet transformedimageblocked wavelet transformedimagetruncate to achievedesired bit rate andmaximum fidelitybit-plane code each block independentlyonlyis transmittedCSEP 590 - Lecture 12 - Autumn 2007 5Extreme Case is NormalwavelettransformPartition intoone blockimagewavelet transformedimagetruncate to achievedesired bit ratebit-plane codeCSEP 590 - Lecture 12 - Autumn 2007 6Layering wavelettransformPartition intocoding blocksimagewavelet transformedimageblocked wavelet transformedimagebit-plane code each block independentlycreate layerslayer 1layer 2layer 3CSEP 590 - Lecture 12 - Autumn 2007 7Resolution Orderingwavelettransform1 2 5 63 4 7 89 10 13 1412 15 16Partition intocoding blocksimagewavelet transformedimageblocked wavelet transformedimage11resolutionpartitionbit-plane code each block independently1234...1516lowest resolutionnext lowestnext,next lowestCSEP 590 - Lecture 12 - Autumn 2007 8Block Coding• Assume we are in block k, and c(i,j) is a coefficient in block k.• Divide c(i,j) into its sign s(i,j) and m(i,j) its magnitude. • Quantize to where qkis the quantization step for block k. • Example: c(i,j) = -10, qk= 3.– s(i,j) = 0– v(i,j) = floor(-10/3 + .5) = -2.5j)/qm(i,j)v(i,k+=CSEP 590 - Lecture 12 - Autumn 2007 9Bit Planes of Normalized Quantized Coefficients0 0 0 0 10 1 0 0 01 0 1 0 00 0 0 1 1...+ - + + +block sign plane1234...Quantized coefficients are normalized between –1 and 1CSEP 590 - Lecture 12 - Autumn 2007 10Bit-Plane Coding of Blocks• Sub-block significance coding (like group testing)– Some sub-blocks are declared insignificant– Significant sub-blocks must be coded• Contexts are defined based on the previous bit-plane significance.– Zero coding (ZC) – 9 contexts– Run length coding (RLC) – 1 context– Sign coding (SC) – 5 contexts – Magnitude refinement coding (MR) – 3 contexts• Block coded in raster order using arithmetic codingCSEP 590 - Lecture 12 - Autumn 2007 11Sub-Block Significance Coding• Quad-tree organized group testing• Block divided into 16x16 sub-blocks• Identify in few bits the sub-blocks that are significantsignificantinsignificantblockCSEP 590 - Lecture 12 - Autumn 2007 12Quad-Tree Subdivision02 310 2 31CSEP 590 - Lecture 12 - Autumn 2007 13Quad-Tree Subdivision02 31CSEP 590 - Lecture 12 - Autumn 2007 14Quad-Tree Subdivision Coding02 31Depth-first code = 1 for significant 0 for insignificant111000100110000100101000110001000CSEP 590 - Lecture 12 - Autumn 2007 15Quad-Tree Subdivision Coding02 31Skip symbols that are already known:1. nodes significant in previous bit plane2. last child of significant parent of other childrenare insignificantknown significant inlast bit plane111000100110000100101000110001000CSEP 590 - Lecture 12 - Autumn 2007 16ZC – Zero Coding• LH is transposed so that it can be treated the same as HL. (LH)Thas similar characteristics to HL.• Each coefficient has its neighbors in thesamesubbandHHLHHLHHLHHLLLvertical neighborshorizontal neighborsdiagonal neighbors?CSEP 590 - Lecture 12 - Autumn 2007 17ZC Contexts• v = number of vertical neighbors significant in the previous bit-plane• h = number of horizontal neighbors significant in the previous bit-plane• d = number of diagonal neighbors significant in the previous bit-planeHL (LH)TLL HHh v d d h+v*> 2**28> 02*> 01702> 0016> 11001511*20401*103> 10> 1002101001000000label0 <h, v < 20 < d < 4higher labelsmean more likelyto be significantCSEP 590 - Lecture 12 - Autumn 2007 18ExamplesHLh = 0v = 2d = 0Context 4?HHh = 0v = 2d = 0Context 2?HLh = 2v = 0d = 0Context 8HHh = 2v = 0d = 0Context 2HLh = 0v = 0d = 2Context 2HHh = 0v = 0d = 2Context 6significant inprevious bit-plane????CSEP 590 - Lecture 12 - Autumn 2007 19RLC – Run Length Coding• Looks for runs of 4 that are likely to be insignificant• If all insignificant then code as a single symbol• Main purpose – to lighten the load on the arithmetic coder.? ???CSEP 590 - Lecture 12 - Autumn 2007 20SC – Sign Coding−=110hsif horizontal neighbors are both insignificant or of opposite signif at least one horizontal neighbor is positiveif at least one horizontal neighbor is negative−=110vsif vertical neighbors are both insignificant or of opposite signif at least one vertical neighbor is positiveif at least one vertical neighbor is negative432101234-1-1-111-1111-101-101-101-1-1-1000111hsvssign predictionlabelCSEP 590 - Lecture 12 - Autumn 2007 21MR – Magnitude Refinement• This is the refinement pass. • Define t = 0 if first refinement bit, t = 1 otherwise. *12> 001000label t h + vCSEP 590 - Lecture 12 - Autumn 2007 22Bit Allocation• How do we truncate the encoded blocks to achieve a desired bit rate and get maximum fidelitytruncate to achievedesired bit rate andmaximum fidelityCSEP 590 - Lecture 12 - Autumn 2007 23Basic Set Up• Encoded block k can be truncated to nkbits.• Total Bit Rate • Distortion attributable to block k iswhere wkis the “weight” of the basis vectors for block k and is the recovered coefficients from nkbits of block k.∑∈−=kkkBj)(i,2n2knkj))c(i,j)(i,(cwD∑kknj)(i,cknCSEP 590 - Lecture 12 - Autumn 2007 24Bit Allocation as an Optimization Problem• Input: Given m embedded codes and a bit rate
View Full Document
Unlocking...