Data-Compression Notes | EduRev

: Data-Compression Notes | EduRev

 Page 1


1
CSEP 590 - Lecture 10 - Autumn 2007 1
CSEP 590
Data Compression
Autumn 2007
Context Based Arithmetic Coding 
for the DCT (CBACD) 
(Kyle Littlefield, 2006)
CSEP 590 - Lecture 10 - Autumn 2007 2
CBACD 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 methods
CSEP 590 - Lecture 10 - Autumn 2007 3
CBACD Overview - Results
• Performs 
significantly better 
than JPEG
• Performs slightly 
under wavelet 
based methods 
such as SPIHT and 
JPEG-2000
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 4
CBACD Overview
original
image DCT
inverse
DCT
reconstructed
image
extrapolate coefficients 
(to bit planes that were not encoded)
denormalize coefficients
add DC
average
recombine bit planes
bit planes
context
modeling
arithmetic
coding
subtract DC
average
normalize
coefficients
split into
bit planes
significance pass
refinement pass
Encoder
Decoder
bit planes
context
modeling
arithmetic
coding
refinement pass
significance pass
encoded bit stream
DC average
DC average
normalization constant
normalization constant
header data
1001111011
header data
CSEP 590 - Lecture 10 - Autumn 2007 5
Context Modeling – Significance Bits
Inter-block/intra-subband
coefficients (For which 
information from the current 
bit-plane is available.)
Coefficient of interest
Intra-block/inter-subband
coefficients
Inter-block/intra-subband
coefficients (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 6
Context Modeling – Significance Bits
• First a significance factor is computed, based 
on a linear sum of the two factors
• Details
– c
spatial
is set to 1.5, c
frequency
to 0.225, c
constant
to .375
– The distance formula is taken to be the square of the 
Euclidean distance: i
2
+j
2
constant
i
frequency
j i
spatial
c y x i isSig c
j i dist
j y i x sub isSig
c y x sub f + +
+ +
=
? ?
=
63
1 ,
) , , (
) , (
) , , (
) , , (
Page 2


1
CSEP 590 - Lecture 10 - Autumn 2007 1
CSEP 590
Data Compression
Autumn 2007
Context Based Arithmetic Coding 
for the DCT (CBACD) 
(Kyle Littlefield, 2006)
CSEP 590 - Lecture 10 - Autumn 2007 2
CBACD 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 methods
CSEP 590 - Lecture 10 - Autumn 2007 3
CBACD Overview - Results
• Performs 
significantly better 
than JPEG
• Performs slightly 
under wavelet 
based methods 
such as SPIHT and 
JPEG-2000
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 4
CBACD Overview
original
image DCT
inverse
DCT
reconstructed
image
extrapolate coefficients 
(to bit planes that were not encoded)
denormalize coefficients
add DC
average
recombine bit planes
bit planes
context
modeling
arithmetic
coding
subtract DC
average
normalize
coefficients
split into
bit planes
significance pass
refinement pass
Encoder
Decoder
bit planes
context
modeling
arithmetic
coding
refinement pass
significance pass
encoded bit stream
DC average
DC average
normalization constant
normalization constant
header data
1001111011
header data
CSEP 590 - Lecture 10 - Autumn 2007 5
Context Modeling – Significance Bits
Inter-block/intra-subband
coefficients (For which 
information from the current 
bit-plane is available.)
Coefficient of interest
Intra-block/inter-subband
coefficients
Inter-block/intra-subband
coefficients (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 6
Context Modeling – Significance Bits
• First a significance factor is computed, based 
on a linear sum of the two factors
• Details
– c
spatial
is set to 1.5, c
frequency
to 0.225, c
constant
to .375
– The distance formula is taken to be the square of the 
Euclidean distance: i
2
+j
2
constant
i
frequency
j i
spatial
c y x i isSig c
j i dist
j y i x sub isSig
c y x sub f + +
+ +
=
? ?
=
63
1 ,
) , , (
) , (
) , , (
) , , (
2
CSEP 590 - Lecture 10 - Autumn 2007 7
Context 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 8
Context 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 9
Context 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 contexts
CSEP 590 - Lecture 10 - Autumn 2007 10
Context 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 PSNR
CSEP 590 - Lecture 10 - Autumn 2007 11
Subband groupings
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Original CBACD 
(64 groups / 320 contexts)
Single group 
(1 group / 5 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 12
More subband groupings
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 4 5 5 6 7
4 4 4 5 5 6 7 8
5 5 5 5 6 7 7 8
6 6 6 6 7 7 8 9
7 7 7 7 8 8 9 9
0 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7
11 11 2 3 4 5 6 7
12 12 12 4 5 5 6 7
13 13 13 14 5 6 7 8
14 14 14 14 15 7 7 8
15 15 15 15 16 16 8 9
16 16 16 16 17 17 18 9
Circular (10 groups / 50 contexts) Circular with horizontal/vertical 
split (19 groups / 95 contexts)
Page 3


1
CSEP 590 - Lecture 10 - Autumn 2007 1
CSEP 590
Data Compression
Autumn 2007
Context Based Arithmetic Coding 
for the DCT (CBACD) 
(Kyle Littlefield, 2006)
CSEP 590 - Lecture 10 - Autumn 2007 2
CBACD 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 methods
CSEP 590 - Lecture 10 - Autumn 2007 3
CBACD Overview - Results
• Performs 
significantly better 
than JPEG
• Performs slightly 
under wavelet 
based methods 
such as SPIHT and 
JPEG-2000
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 4
CBACD Overview
original
image DCT
inverse
DCT
reconstructed
image
extrapolate coefficients 
(to bit planes that were not encoded)
denormalize coefficients
add DC
average
recombine bit planes
bit planes
context
modeling
arithmetic
coding
subtract DC
average
normalize
coefficients
split into
bit planes
significance pass
refinement pass
Encoder
Decoder
bit planes
context
modeling
arithmetic
coding
refinement pass
significance pass
encoded bit stream
DC average
DC average
normalization constant
normalization constant
header data
1001111011
header data
CSEP 590 - Lecture 10 - Autumn 2007 5
Context Modeling – Significance Bits
Inter-block/intra-subband
coefficients (For which 
information from the current 
bit-plane is available.)
Coefficient of interest
Intra-block/inter-subband
coefficients
Inter-block/intra-subband
coefficients (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 6
Context Modeling – Significance Bits
• First a significance factor is computed, based 
on a linear sum of the two factors
• Details
– c
spatial
is set to 1.5, c
frequency
to 0.225, c
constant
to .375
– The distance formula is taken to be the square of the 
Euclidean distance: i
2
+j
2
constant
i
frequency
j i
spatial
c y x i isSig c
j i dist
j y i x sub isSig
c y x sub f + +
+ +
=
? ?
=
63
1 ,
) , , (
) , (
) , , (
) , , (
2
CSEP 590 - Lecture 10 - Autumn 2007 7
Context 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 8
Context 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 9
Context 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 contexts
CSEP 590 - Lecture 10 - Autumn 2007 10
Context 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 PSNR
CSEP 590 - Lecture 10 - Autumn 2007 11
Subband groupings
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Original CBACD 
(64 groups / 320 contexts)
Single group 
(1 group / 5 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 12
More subband groupings
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 4 5 5 6 7
4 4 4 5 5 6 7 8
5 5 5 5 6 7 7 8
6 6 6 6 7 7 8 9
7 7 7 7 8 8 9 9
0 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7
11 11 2 3 4 5 6 7
12 12 12 4 5 5 6 7
13 13 13 14 5 6 7 8
14 14 14 14 15 7 7 8
15 15 15 15 16 16 8 9
16 16 16 16 17 17 18 9
Circular (10 groups / 50 contexts) Circular with horizontal/vertical 
split (19 groups / 95 contexts)
3
CSEP 590 - Lecture 10 - Autumn 2007 13
More subband groupings
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 4 4 5 6 7
5 5 5 5 5 5 6 7
6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 7
Diagonal 
(15 groups / 75 contexts)
Max frequency 
(8 groups / 40 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 14
More subband groupings
0 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7
9 9 2 3 4 5 6 7
10 10 10 3 4 5 6 7
11 11 11 11 4 5 6 7
12 12 12 12 12 5 6 7
13 13 13 13 13 13 6 7
14 14 14 14 14 14 14 7
0 1 3 3 3
2 5 5 5
4 5 5 5
4 5 5
4
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
Generic grouping by types
(7 groups / 35 contexts)
Max frequency with horizontal/vertical 
split (15 groups/75 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 15
Context 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.004
CSEP 590 - Lecture 10 - Autumn 2007 16
Context 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 architecture
CSEP 590 - Lecture 10 - Autumn 2007 17
Context 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 18
Context Modeling – Refinement Bits
• Model is based on coefficient distribution
– Coefficients are skewed towards 0, so refinement 
bits are also skewed towards 0
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
Page 4


1
CSEP 590 - Lecture 10 - Autumn 2007 1
CSEP 590
Data Compression
Autumn 2007
Context Based Arithmetic Coding 
for the DCT (CBACD) 
(Kyle Littlefield, 2006)
CSEP 590 - Lecture 10 - Autumn 2007 2
CBACD 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 methods
CSEP 590 - Lecture 10 - Autumn 2007 3
CBACD Overview - Results
• Performs 
significantly better 
than JPEG
• Performs slightly 
under wavelet 
based methods 
such as SPIHT and 
JPEG-2000
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 4
CBACD Overview
original
image DCT
inverse
DCT
reconstructed
image
extrapolate coefficients 
(to bit planes that were not encoded)
denormalize coefficients
add DC
average
recombine bit planes
bit planes
context
modeling
arithmetic
coding
subtract DC
average
normalize
coefficients
split into
bit planes
significance pass
refinement pass
Encoder
Decoder
bit planes
context
modeling
arithmetic
coding
refinement pass
significance pass
encoded bit stream
DC average
DC average
normalization constant
normalization constant
header data
1001111011
header data
CSEP 590 - Lecture 10 - Autumn 2007 5
Context Modeling – Significance Bits
Inter-block/intra-subband
coefficients (For which 
information from the current 
bit-plane is available.)
Coefficient of interest
Intra-block/inter-subband
coefficients
Inter-block/intra-subband
coefficients (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 6
Context Modeling – Significance Bits
• First a significance factor is computed, based 
on a linear sum of the two factors
• Details
– c
spatial
is set to 1.5, c
frequency
to 0.225, c
constant
to .375
– The distance formula is taken to be the square of the 
Euclidean distance: i
2
+j
2
constant
i
frequency
j i
spatial
c y x i isSig c
j i dist
j y i x sub isSig
c y x sub f + +
+ +
=
? ?
=
63
1 ,
) , , (
) , (
) , , (
) , , (
2
CSEP 590 - Lecture 10 - Autumn 2007 7
Context 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 8
Context 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 9
Context 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 contexts
CSEP 590 - Lecture 10 - Autumn 2007 10
Context 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 PSNR
CSEP 590 - Lecture 10 - Autumn 2007 11
Subband groupings
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Original CBACD 
(64 groups / 320 contexts)
Single group 
(1 group / 5 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 12
More subband groupings
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 4 5 5 6 7
4 4 4 5 5 6 7 8
5 5 5 5 6 7 7 8
6 6 6 6 7 7 8 9
7 7 7 7 8 8 9 9
0 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7
11 11 2 3 4 5 6 7
12 12 12 4 5 5 6 7
13 13 13 14 5 6 7 8
14 14 14 14 15 7 7 8
15 15 15 15 16 16 8 9
16 16 16 16 17 17 18 9
Circular (10 groups / 50 contexts) Circular with horizontal/vertical 
split (19 groups / 95 contexts)
3
CSEP 590 - Lecture 10 - Autumn 2007 13
More subband groupings
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 4 4 5 6 7
5 5 5 5 5 5 6 7
6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 7
Diagonal 
(15 groups / 75 contexts)
Max frequency 
(8 groups / 40 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 14
More subband groupings
0 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7
9 9 2 3 4 5 6 7
10 10 10 3 4 5 6 7
11 11 11 11 4 5 6 7
12 12 12 12 12 5 6 7
13 13 13 13 13 13 6 7
14 14 14 14 14 14 14 7
0 1 3 3 3
2 5 5 5
4 5 5 5
4 5 5
4
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
Generic grouping by types
(7 groups / 35 contexts)
Max frequency with horizontal/vertical 
split (15 groups/75 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 15
Context 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.004
CSEP 590 - Lecture 10 - Autumn 2007 16
Context 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 architecture
CSEP 590 - Lecture 10 - Autumn 2007 17
Context 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 18
Context Modeling – Refinement Bits
• Model is based on coefficient distribution
– Coefficients are skewed towards 0, so refinement 
bits are also skewed towards 0
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
4
CSEP 590 - Lecture 10 - Autumn 2007 19
Context Modeling – Refinement Bits
• Bits are placed into contexts based on the 
number of bit planes since the coefficient 
became significant
• Provides significant improvements over putting 
all refinement bits in 1 context
– Leads to PSNR improvements of up to .1 dB at high 
bit rates
# 0s # 1s % 0s
1 26758 14575 64.74
2 13737 9511 59.09
3 3610 5324 54.23
4 2927 2677 52.23
5 1491 1436 50.93
6 649 650 49.96
CSEP 590 - Lecture 10 - Autumn 2007 20
Coefficient Extrapolation
• The bit plane process guarantees that only 
the first few bits of each coefficient will be 
transmitted to the decoder.
– The decoder must decide how to fill in the 
untransmitted bits
.0101????????...
.010100000000…
.010111111111…
.010110000000…
.010101011001…
Transmitted coefficient
Possible extrapolations
CSEP 590 - Lecture 10 - Autumn 2007 21
Coefficient Extrapolation - Goal
• Reduce reconstructed image distortion
• Reduce distortion as measured by PSNR
• Reduce average per-pixel difference 
between original and deconstructed image
• Reduce average difference between 
original DCT coefficient and reconstructed 
DCT coefficient
• Reduce average distance across possible 
DCT coefficient distribution.
CSEP 590 - Lecture 10 - Autumn 2007 22
Coefficient Extrapolation Example
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
Best Extrapolation for .0101????????... is .010101101100…
CSEP 590 - Lecture 10 - Autumn 2007 23
Coefficient Extrapolation
• Can not calculate best extrapolation 
for every possible set of transmitted 
bits
• Instead, compute best extrapolation 
for every possible pair of 
– Bit plane that the coefficient became 
significant in
– Number of bits transmitted after the 
coefficient became significant
• Best extrapolation is computed 
separately for each subband
• The ‘standard’ coefficient distribution 
consists of the sum of the 
distributions from 250 images pulled 
from the CBIRT database 
(http://www.cs.washington.edu/rese
arch/imagedatabase/groundtruth/)
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
CSEP 590 - Lecture 10 - Autumn 2007 24
Results - Barbara
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
Page 5


1
CSEP 590 - Lecture 10 - Autumn 2007 1
CSEP 590
Data Compression
Autumn 2007
Context Based Arithmetic Coding 
for the DCT (CBACD) 
(Kyle Littlefield, 2006)
CSEP 590 - Lecture 10 - Autumn 2007 2
CBACD 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 methods
CSEP 590 - Lecture 10 - Autumn 2007 3
CBACD Overview - Results
• Performs 
significantly better 
than JPEG
• Performs slightly 
under wavelet 
based methods 
such as SPIHT and 
JPEG-2000
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 4
CBACD Overview
original
image DCT
inverse
DCT
reconstructed
image
extrapolate coefficients 
(to bit planes that were not encoded)
denormalize coefficients
add DC
average
recombine bit planes
bit planes
context
modeling
arithmetic
coding
subtract DC
average
normalize
coefficients
split into
bit planes
significance pass
refinement pass
Encoder
Decoder
bit planes
context
modeling
arithmetic
coding
refinement pass
significance pass
encoded bit stream
DC average
DC average
normalization constant
normalization constant
header data
1001111011
header data
CSEP 590 - Lecture 10 - Autumn 2007 5
Context Modeling – Significance Bits
Inter-block/intra-subband
coefficients (For which 
information from the current 
bit-plane is available.)
Coefficient of interest
Intra-block/inter-subband
coefficients
Inter-block/intra-subband
coefficients (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 6
Context Modeling – Significance Bits
• First a significance factor is computed, based 
on a linear sum of the two factors
• Details
– c
spatial
is set to 1.5, c
frequency
to 0.225, c
constant
to .375
– The distance formula is taken to be the square of the 
Euclidean distance: i
2
+j
2
constant
i
frequency
j i
spatial
c y x i isSig c
j i dist
j y i x sub isSig
c y x sub f + +
+ +
=
? ?
=
63
1 ,
) , , (
) , (
) , , (
) , , (
2
CSEP 590 - Lecture 10 - Autumn 2007 7
Context 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 8
Context 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 9
Context 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 contexts
CSEP 590 - Lecture 10 - Autumn 2007 10
Context 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 PSNR
CSEP 590 - Lecture 10 - Autumn 2007 11
Subband groupings
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Original CBACD 
(64 groups / 320 contexts)
Single group 
(1 group / 5 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 12
More subband groupings
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 4 5 5 6 7
4 4 4 5 5 6 7 8
5 5 5 5 6 7 7 8
6 6 6 6 7 7 8 9
7 7 7 7 8 8 9 9
0 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7
11 11 2 3 4 5 6 7
12 12 12 4 5 5 6 7
13 13 13 14 5 6 7 8
14 14 14 14 15 7 7 8
15 15 15 15 16 16 8 9
16 16 16 16 17 17 18 9
Circular (10 groups / 50 contexts) Circular with horizontal/vertical 
split (19 groups / 95 contexts)
3
CSEP 590 - Lecture 10 - Autumn 2007 13
More subband groupings
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 4 4 5 6 7
5 5 5 5 5 5 6 7
6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 7
Diagonal 
(15 groups / 75 contexts)
Max frequency 
(8 groups / 40 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 14
More subband groupings
0 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7
9 9 2 3 4 5 6 7
10 10 10 3 4 5 6 7
11 11 11 11 4 5 6 7
12 12 12 12 12 5 6 7
13 13 13 13 13 13 6 7
14 14 14 14 14 14 14 7
0 1 3 3 3
2 5 5 5
4 5 5 5
4 5 5
4
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
Generic grouping by types
(7 groups / 35 contexts)
Max frequency with horizontal/vertical 
split (15 groups/75 contexts)
CSEP 590 - Lecture 10 - Autumn 2007 15
Context 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.004
CSEP 590 - Lecture 10 - Autumn 2007 16
Context 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 architecture
CSEP 590 - Lecture 10 - Autumn 2007 17
Context 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 18
Context Modeling – Refinement Bits
• Model is based on coefficient distribution
– Coefficients are skewed towards 0, so refinement 
bits are also skewed towards 0
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
4
CSEP 590 - Lecture 10 - Autumn 2007 19
Context Modeling – Refinement Bits
• Bits are placed into contexts based on the 
number of bit planes since the coefficient 
became significant
• Provides significant improvements over putting 
all refinement bits in 1 context
– Leads to PSNR improvements of up to .1 dB at high 
bit rates
# 0s # 1s % 0s
1 26758 14575 64.74
2 13737 9511 59.09
3 3610 5324 54.23
4 2927 2677 52.23
5 1491 1436 50.93
6 649 650 49.96
CSEP 590 - Lecture 10 - Autumn 2007 20
Coefficient Extrapolation
• The bit plane process guarantees that only 
the first few bits of each coefficient will be 
transmitted to the decoder.
– The decoder must decide how to fill in the 
untransmitted bits
.0101????????...
.010100000000…
.010111111111…
.010110000000…
.010101011001…
Transmitted coefficient
Possible extrapolations
CSEP 590 - Lecture 10 - Autumn 2007 21
Coefficient Extrapolation - Goal
• Reduce reconstructed image distortion
• Reduce distortion as measured by PSNR
• Reduce average per-pixel difference 
between original and deconstructed image
• Reduce average difference between 
original DCT coefficient and reconstructed 
DCT coefficient
• Reduce average distance across possible 
DCT coefficient distribution.
CSEP 590 - Lecture 10 - Autumn 2007 22
Coefficient Extrapolation Example
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
Best Extrapolation for .0101????????... is .010101101100…
CSEP 590 - Lecture 10 - Autumn 2007 23
Coefficient Extrapolation
• Can not calculate best extrapolation 
for every possible set of transmitted 
bits
• Instead, compute best extrapolation 
for every possible pair of 
– Bit plane that the coefficient became 
significant in
– Number of bits transmitted after the 
coefficient became significant
• Best extrapolation is computed 
separately for each subband
• The ‘standard’ coefficient distribution 
consists of the sum of the 
distributions from 250 images pulled 
from the CBIRT database 
(http://www.cs.washington.edu/rese
arch/imagedatabase/groundtruth/)
1
10
100
1000
10000
100000
1000000
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Coefficient magnitude
Number of coefficients
CSEP 590 - Lecture 10 - Autumn 2007 24
Results - Barbara
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
5
CSEP 590 - Lecture 10 - Autumn 2007 25
Results - Boat
22
24
26
28
30
32
34
36
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 26
Results – Lena
25
27
29
31
33
35
37
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 27
Results - Mandrill
20
22
24
26
28
30
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 28
Results - Pentagon
24
26
28
30
32
34
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 29
Results - Stream
21
23
25
27
29
31
0 0.2 0.4 0.6 0.8 1
Bit Rate (bpp)
PSNR (dB)
CBACD
JPEG
JPEG-2000
SPIHT
CSEP 590 - Lecture 10 - Autumn 2007 30
Results
• For images involving a lot of high 
frequency information, such as Barbara 
and Mandrill
– CBACD performance is a fraction of a dB 
worse than wavelet methods.
• For images with fewer high-frequency 
components, such as Pentagon
– CBACD performs somewhat worse than 
wavelet methods, from .5 dB at high bit rates, 
up to 1.5 dB at very low bit rates. 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!