Bit-plane coding
Gray coding:
Binary and Gray codes (4 bits):
Example (8 bits):
Value =127 Binary representation = 01111111
Value = 128 Binary representation = 10000000
Binary and Gray code bit planes:
/ 7 /
/ 6 /
/ 5 /
/ 4 /
/ 3 /
/ 2 /
/ 1 /
/ 0 /
Pedictive coding in lossless JPEG
ALTERNATIVE PREDICTORS:
Mode: / Predictor: / Mode: / Predictor:0 / Null / 4 / N + W - NW
1 / W / 5 / W + (N - NW)/2
2 / N / 6 / N + (W - NW)/2
3 / NW / 7 / (N + W)/2
RESIDUAL CODING:
DECODER:
ENTROPY CODING:
· HUFFMAN CODING
· ARITHMETIC CODING (QM-CODER)
Huffman coding
0 / 00 / 0 / -
1 / 010 / -1, 1 / 0, 1
2 / 011 / -3, -2, 2, 3 / 00, 01, 10, 11
3 / 100 / -7,..-4, 4..7 / 000,...011, 100...111
4 / 101 / -15,..-8, 8..15 / 0000,...0111, 1000...1111
5 / 110 / -31,..-16, 16..31 / :
6 / 1110 / -63,..-32, 32..63 / :
7 / 11110 / -127,..-64, 64..127 / :
8 / 111110 / -255,..-128, 128..255 / :
Binary arithmetic coding
Lossless JPEG: example
Pixel sequence: 10, 12, 10, 7, 8, 8, 12.
Prediction mode: 1 (previous pixel value)
Pixel: / 10 / 12 / 10 / 7 / 8 / 8 / 12e / +10 / +2 / -2 / -3 / +1 / 0 / +4
Category: / 4 / 2 / 2 / 2 / 1 / 0 / 3
Bits: / 1011010 / 01110 / 01101 / 01100 / 0101 / 00 / 100100
FELICS
PREDICTION MODEL:
L = The smaller of the two neighbor pixel value
H = The larger of the two neighbor pixel value
Assumption of distribution:
CODING THE PIXEL VALUE:
IF P Î [L, H] THEN
Output(0);
Encode P-L by adjusted binary coding;
ELSE IF P < L THEN
Output(1);
Output(0);
Encode (L-1)-P by Golomb-Rice coding;
ELSE
Output(1);
Output(1);
Encode P-(H+1) by Golomb-Rice coding;
CODe table:
Pixel position: / Codeword:Below range / 10 + Rice(L-P-1)
In range / 0 + Adj.Binary(P-L)
Above range / 11 + Rice(P-H-1)
Adjusted binary coding:
· Let D=H-L. There are D+1 possible values in the range.
· If D+1 is a power of two, a binary code with log2(D+1) bits is used.
· Otherwise are used for middle values and bits for the “outer values”.
· For example, if D=4 there are five values (0, 1, 2, 3, 4) and their corresponding adjusted binary codewords are (111, 10, 00, 01, 110).
Rice coding:
· For determining the Rice coding parameter k, the D is used as a context.
· For each context D, acumulative total bit rate is maintained for each reasonable Rice parameter value k, of the code length that would have resulted if the parameter k were used to encode all values encoutered so far in the context.
· The parameter with the smallest cumulative code length is used to encode the next value encountered in the context.
· The allowed parameter values are k=0, 1, 2, and 3.
Model structure of JPEG-LS
JPEG-LS predictor
Components of the model:
a. Prediction
b. Determination of context.
c. Probability model for the prediction errors.
Predictor:
RESIDUAL CODING:
JPEG-LS context model
GRADIENT DETERMINATION:
g1=d - b
g2=b - c
g1=c - a
CONTEXT QUANTIZATION:
gi ® qi
{0}
±{1,2}
±{3,4,5,6}
±{7,8,...,20}
±{e³20}
NUMBER OF MODELS:
JPEG-LS coding
VALUE MAPPING:
0,-1,+1,-2,+2, -3, +3, -4, +5, ...
MODEL PARAMETER DETERMINATION:
CODING:
Golomb coding with parameter 2k (aka Rice)
QUANTIZATION IN NEAR-LOSSLESS MODE:
Prediction examples of JPEG-LS
10 10 10
10 10 10
10 10 10 / 10 / g1= 0
g2= 0
g3= 0
0 10 20
0 10 20
0 10 20 / 10 / g1=10
g2=10
g3= 0
0 0 0
10 10 10
20 20 20 / 10 / g1= 0
g2= 0
g3= -10
0 5 10
5 10 15
10 15 20 / 5 / g1= 5
g2= 5
g3= -5
0 10 10
0 10 10
0 10 10 / 10 / g1= 0
g2= 10
g3= 0
0 0 0
10 10 10
10 10 10 / 10 / g1= 0
g2= 0
g3= -10
Real example of JPEG-LS
ORIGINAL
184 / 189 / 193 / 185 / 143 / 81192 / 192 / 179 / 133 / 75 / 77
195 / 175 / 108 / 67 / 61 / 74
169 / 93 / 53 / 69 / 57 / 70
74 / 52 / 53 / 59 / 65 / 61
46 / 47 / 43 / 59 / 52 / 41
PREDICTORS:
Left / Up / Plane3 / -14 / -52 / -68 / 0 / -13 / -46 / -58 / -5 / -17 / -38 / -16
-17 / -71 / -66 / -14 / -20 / -67 / -41 / -6 / -20 / -54 / 5 / 52
-82 / -55 / 2 / -4 / -76 / -40 / 16 / -12 / -56 / 27 / 57 / -6
-41 / 0 / -10 / 8 / -22 / 1 / 6 / 6 / 54 / 41 / -10 / 18
507 / 430 / 476
CHOSEN: RESIDUAL:
192 / 193 / 179 / 133 / 0 / -14 / -46 / -58195 / 175 / 108 / 67 / -20 / -67 / -41 / -6
169 / 93 / 53 / 63 / -76 / -40 / 16 / -6
74 / 52 / 69 / 57 / -22 / 1 / -10 / 8
Comparison of lossless methods
Source: http://www.hpl.hp.com/research/itc/csl/vcd/infotheory/loco.html