DOC PREVIEW
UW CSEP 590 - Data Compression

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSEP 590 - Lecture 10 - Autumn 2007 1CSEP 590Data CompressionAutumn 2007Context Based Arithmetic Coding for the DCT (CBACD) (Kyle Littlefield, 2006)CSEP 590 - Lecture 10 - Autumn 2007 2CBACD overview• Evolved out of PACW– A simple wavelet based coder developed at UW by Dane Barney and Amanda Askew• Goals:– Replace wavelet transform with the DCT– Replace context model with one suitable for the DCT– Compare performance to• Existing DCT-based methods, primarily JPEG• State of the art wavelet methodsCSEP 590 - Lecture 10 - Autumn 2007 3CBACD Overview - Results• Performs significantly better than JPEG• Performs slightly under wavelet based methods such as SPIHT and JPEG-200022242628303234360 0.2 0.4 0.6 0.8 1Bit Rate (bpp)PSNR (dB)CBACDJPEGJPEG-2000SPIHTCSEP 590 - Lecture 10 - Autumn 2007 4CBACD OvervieworiginalimageDCTinverseDCTreconstructedimageextrapolate coefficients (to bit planes that were not encoded)denormalize coefficientsadd DCaveragerecombine bit planesbit planescontextmodelingarithmeticcodingsubtract DCaveragenormalizecoefficientssplit intobit planessignificance passrefinement passEncoderDecoderbit planescontextmodelingarithmeticcodingrefinement passsignificance passencoded bit streamDC averageDC averagenormalization constantnormalization constantheader data1001111011header dataCSEP 590 - Lecture 10 - Autumn 2007 5Context Modeling – Significance BitsInter-block/intra-subbandcoefficients (For which information from the current bit-plane is available.)Coefficient of interestIntra-block/inter-subbandcoefficientsInter-block/intra-subbandcoefficients (For which only information from the previous bit-plane is available.)• Based on two factors– Intra-block correlation: Relationships between subbands within a block.– Inter-block correlation: Relationships to neighboring blocks, within the same subband.CSEP 590 - Lecture 10 - Autumn 2007 6Context Modeling – Significance Bits• First a significance factor is computed, based on a linear sum of the two factors• Details– cspatialis set to 1.5, cfrequencyto 0.225, cconstantto .375– The distance formula is taken to be the square of the Euclidean distance: i2+j2constantifrequencyjispatialcyxiisSigcjidistjyixsubisSigcyxsubf ++++=∑∑=631,),,(),(),,(),,(CSEP 590 - Lecture 10 - Autumn 2007 7Context Modeling – Significance Bits• Interblock correlation sum is taken over 24 surrounding blocks. Closer blocks have more influence.• Blue denotes blocks for which information is available for the current bit plane.• Red denotes blocks for which information is only available for the previous bit-plane.CSEP 590 - Lecture 10 - Autumn 2007 8Context Modeling – Significance Bits• A context is determined from the significance factor by truncating to an integer which is used to look up the context.• A maximum of five contexts are used per subband (each subband is treated separately).– All significance factors larger than 4 are truncated to 4.CSEP 590 - Lecture 10 - Autumn 2007 9Context Dilution Concerns• Context dilution occurs when only a few bits are encoded in each context– Results in decreased arithmetic coding performance, as contexts do not have enough bits encoded to meaningfully update statistics• Most context-based coders use many fewer contexts than CBACD– EBCOT – 27– PACW – 30-56 (variable)– JPEG-2000 – 27• CBACD uses 340 contextsCSEP 590 - Lecture 10 - Autumn 2007 10Context Dilution Experiments• Context dilution concerns were approached by trying various grouping of subbands.• If context dilution was occuring, grouping subbands should result in large improvements in PSNRCSEP 590 - Lecture 10 - Autumn 2007 11Subband groupings0 1 2 3 4 5 6 78 9 10 11 12 13 14 1516 17 18 19 20 21 22 2324 25 26 27 28 29 30 3132 33 34 35 36 37 38 3940 41 42 43 44 45 46 4748 49 50 51 52 53 54 5556 57 58 59 60 61 62 630 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0Original CBACD (64 groups / 320 contexts)Single group (1 group / 5 contexts)CSEP 590 - Lecture 10 - Autumn 2007 12More subband groupings0 1 2 3 4 5 6 71 1 2 3 4 5 6 72 2 2 3 4 5 6 73 3 3 4 5 5 6 74 4 4 5 5 6 7 85 5 5 5 6 7 7 86 6 6 6 7 7 8 97 7 7 7 8 8 9 90 1 2 3 4 5 6 710 1 2 3 4 5 6 711 11 2 3 4 5 6 712 12 12 4 5 5 6 713 13 13 14 5 6 7 814 14 14 14 15 7 7 815 15 15 15 16 16 8 916 16 16 16 17 17 18 9Circular (10 groups / 50 contexts)Circular with horizontal/vertical split (19 groups / 95 contexts)CSEP 590 - Lecture 10 - Autumn 2007 13More subband groupings0 1 2 3 4 5 6 71 2 3 4 5 6 7 82 3 4 5 6 7 8 93 4 5 6 7 8 9 104 5 6 7 8 9 10 115 6 7 8 9 10 11 126 7 8 9 10 11 12 137 8 9 10 11 12 13 140 1 2 3 4 5 6 71 1 2 3 4 5 6 72 2 2 3 4 5 6 73 3 3 3 4 5 6 74 4 4 4 4 5 6 75 5 5 5 5 5 6 76 6 6 6 6 6 6 77 7 7 7 7 7 7 7Diagonal (15 groups / 75 contexts)Max frequency (8 groups / 40 contexts)CSEP 590 - Lecture 10 - Autumn 2007 14More subband groupings0 1 2 3 4 5 6 78 1 2 3 4 5 6 79 9 2 3 4 5 6 710 10 10 3 4 5 6 711 11 11 11 4 5 6 712 12 12 12 12 5 6 713 13 13 13 13 13 6 714 14 14 14 14 14 14 70 1 3 3 32 5 5 54 5 5 54 5 5466666666666666666666666666666666666666666666666Generic grouping by types(7 groups / 35 contexts)Max frequency with horizontal/vertical split (15 groups/75 contexts)CSEP 590 - Lecture 10 - Autumn 2007 15Context Dilution Results• Over a set of six images encoded at 0.25 bits per pixel (changes in PSNR dB)– Single grouping: -0.128– Circular: +0.006 – Circular with horizontal/vertical split: +0.008– Diagonal: +0.016– Max Frequency: +0.002– Max Frequency with horizontal/vertical split: +0.006 – Grouping by type: -0.004CSEP 590 - Lecture 10 - Autumn 2007 16Context Dilution - Conclusions• The single grouping (not surprisingly) does significantly worse than any other• The other groupings perform about the same– The original CBACD is among the worst of these• Context dilution is only a very slight concern within the CBACD architectureCSEP 590 - Lecture 10 - Autumn 2007 17Context Modeling – Sign Bits• Modeled similar to refinement bits, except:– No intra-block correlation– Smaller area over which sum is taken– All subbands use a single set of contexts– 9 contexts used (instead of 5)CSEP 590 - Lecture 10 - Autumn 2007 18Context Modeling – Refinement Bits• Model is based on coefficient distribution– Coefficients are skewed towards 0, so refinement bits are also skewed towards 011010010001000010000010000000 0.1 0.2 0.3 0.4 0.5


View Full Document

UW CSEP 590 - Data Compression

Documents in this Course
Sequitur

Sequitur

56 pages

Sequitur

Sequitur

56 pages

Protocols

Protocols

106 pages

Spyware

Spyware

31 pages

Sequitur

Sequitur

10 pages

Load more
Download Data Compression
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Data Compression and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Data Compression 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?