Remove useless intermediate var
[FFMpeg-mirror/DVCPRO-HD.git] / doc / snow.txt
blobf99133971c370d3c3a7470dfe2c9d3f33a9b0bfc
1 =============================================
2 Snow Video Codec Specification Draft 20080110
3 =============================================
5 Introduction:
6 =============
7 This specification describes the Snow bitstream syntax and semantics as
8 well as the formal Snow decoding process.
10 The decoding process is described precisely and any compliant decoder
11 MUST produce the exact same output for a spec-conformant Snow stream.
12 For encoding, though, any process which generates a stream compliant to
13 the syntactical and semantic requirements and which is decodable by
14 the process described in this spec shall be considered a conformant
15 Snow encoder.
17 Definitions:
18 ============
20 MUST    the specific part must be done to conform to this standard
21 SHOULD  it is recommended to be done that way, but not strictly required
23 ilog2(x) is the rounded down logarithm of x with basis 2
24 ilog2(0) = 0
26 Type definitions:
27 =================
29 b   1-bit range coded
30 u   unsigned scalar value range coded
31 s   signed scalar value range coded
34 Bitstream syntax:
35 =================
37 frame:
38     header
39     prediction
40     residual
42 header:
43     keyframe                            b   MID_STATE
44     if(keyframe || always_reset)
45         reset_contexts
46     if(keyframe){
47         version                         u   header_state
48         always_reset                    b   header_state
49         temporal_decomposition_type     u   header_state
50         temporal_decomposition_count    u   header_state
51         spatial_decomposition_count     u   header_state
52         colorspace_type                 u   header_state
53         chroma_h_shift                  u   header_state
54         chroma_v_shift                  u   header_state
55         spatial_scalability             b   header_state
56         max_ref_frames-1                u   header_state
57         qlogs
58     }
59     if(!keyframe){
60         update_mc                       b   header_state
61         if(update_mc){
62             for(plane=0; plane<2; plane++){
63                 diag_mc                 b   header_state
64                 htaps/2-1               u   header_state
65                 for(i= p->htaps/2; i; i--)
66                     |hcoeff[i]|         u   header_state
67             }
68         }
69         update_qlogs                    b   header_state
70         if(update_qlogs){
71             spatial_decomposition_count u   header_state
72             qlogs
73         }
74     }
76     spatial_decomposition_type          s   header_state
77     qlog                                s   header_state
78     mv_scale                            s   header_state
79     qbias                               s   header_state
80     block_max_depth                     s   header_state
82 qlogs:
83     for(plane=0; plane<2; plane++){
84         quant_table[plane][0][0]        s   header_state
85         for(level=0; level < spatial_decomposition_count; level++){
86             quant_table[plane][level][1]s   header_state
87             quant_table[plane][level][3]s   header_state
88         }
89     }
91 reset_contexts
92     *_state[*]= MID_STATE
94 prediction:
95     for(y=0; y<block_count_vertical; y++)
96         for(x=0; x<block_count_horizontal; x++)
97             block(0)
99 block(level):
100     mvx_diff=mvy_diff=y_diff=cb_diff=cr_diff=0
101     if(keyframe){
102         intra=1
103     }else{
104         if(level!=max_block_depth){
105             s_context= 2*left->level + 2*top->level + topleft->level + topright->level
106             leaf                        b   block_state[4 + s_context]
107         }
108         if(level==max_block_depth || leaf){
109             intra                       b   block_state[1 + left->intra + top->intra]
110             if(intra){
111                 y_diff                  s   block_state[32]
112                 cb_diff                 s   block_state[64]
113                 cr_diff                 s   block_state[96]
114             }else{
115                 ref_context= ilog2(2*left->ref) + ilog2(2*top->ref)
116                 if(ref_frames > 1)
117                     ref                 u   block_state[128 + 1024 + 32*ref_context]
118                 mx_context= ilog2(2*abs(left->mx - top->mx))
119                 my_context= ilog2(2*abs(left->my - top->my))
120                 mvx_diff                s   block_state[128 + 32*(mx_context + 16*!!ref)]
121                 mvy_diff                s   block_state[128 + 32*(my_context + 16*!!ref)]
122             }
123         }else{
124             block(level+1)
125             block(level+1)
126             block(level+1)
127             block(level+1)
128         }
129     }
132 residual:
133     residual2(luma)
134     residual2(chroma_cr)
135     residual2(chroma_cb)
137 residual2:
138     for(level=0; level<spatial_decomposition_count; level++){
139         if(level==0)
140             subband(LL, 0)
141         subband(HL, level)
142         subband(LH, level)
143         subband(HH, level)
144     }
146 subband:
147     FIXME
151 Tag description:
152 ----------------
154 version
155     0
156     this MUST NOT change within a bitstream
158 always_reset
159     if 1 then the range coder contexts will be reset after each frame
161 temporal_decomposition_type
162     0
164 temporal_decomposition_count
165     0
167 spatial_decomposition_count
168     FIXME
170 colorspace_type
171     0
172     this MUST NOT change within a bitstream
174 chroma_h_shift
175     log2(luma.width / chroma.width)
176     this MUST NOT change within a bitstream
178 chroma_v_shift
179     log2(luma.height / chroma.height)
180     this MUST NOT change within a bitstream
182 spatial_scalability
183     0
185 max_ref_frames
186     maximum number of reference frames
187     this MUST NOT change within a bitstream
189 update_mc
190     indicates that motion compensation filter parameters are stored in the
191     header
193 diag_mc
194     flag to enable faster diagonal interpolation
195     this SHOULD be 1 unless it turns out to be covered by a valid patent
197 htaps
198     number of half pel interpolation filter taps, MUST be even, >0 and <10
200 hcoeff
201     half pel interpolation filter coefficients, hcoeff[0] are the 2 middle
202     coefficients [1] are the next outer ones and so on, resulting in a filter
203     like: ...eff[2], hcoeff[1], hcoeff[0], hcoeff[0], hcoeff[1], hcoeff[2] ...
204     the sign of the coefficients is not explicitly stored but alternates
205     after each coeff and coeff[0] is positive, so ...,+,-,+,-,+,+,-,+,-,+,...
206     hcoeff[0] is not explicitly stored but found by subtracting the sum
207     of all stored coefficients with signs from 32
208     hcoeff[0]= 32 - hcoeff[1] - hcoeff[2] - ...
209     a good choice for hcoeff and htaps is
210     htaps= 6
211     hcoeff={40,-10,2}
212     an alternative which requires more computations at both encoder and
213     decoder side and may or may not be better is
214     htaps= 8
215     hcoeff={42,-14,6,-2}
218 ref_frames
219     minimum of the number of available reference frames and max_ref_frames
220     for example the first frame after a key frame always has ref_frames=1
222 spatial_decomposition_type
223     wavelet type
224     0 is a 9/7 symmetric compact integer wavelet
225     1 is a 5/3 symmetric compact integer wavelet
226     others are reserved
227     stored as delta from last, last is reset to 0 if always_reset || keyframe
229 qlog
230     quality (logarthmic quantizer scale)
231     stored as delta from last, last is reset to 0 if always_reset || keyframe
233 mv_scale
234     stored as delta from last, last is reset to 0 if always_reset || keyframe
235     FIXME check that everything works fine if this changes between frames
237 qbias
238     dequantization bias
239     stored as delta from last, last is reset to 0 if always_reset || keyframe
241 block_max_depth
242     maximum depth of the block tree
243     stored as delta from last, last is reset to 0 if always_reset || keyframe
245 quant_table
246     quantiztation table
249 Highlevel bitstream structure:
250 =============================
251  --------------------------------------------
252 |                   Header                   |
253  --------------------------------------------
254 |    ------------------------------------    |
255 |   |               Block0               |   |
256 |   |             split?                 |   |
257 |   |     yes              no            |   |
258 |   |  .........         intra?          |   |
259 |   | : Block01 :    yes         no      |   |
260 |   | : Block02 :  .......   ..........  |   |
261 |   | : Block03 : :  y DC : : ref index: |   |
262 |   | : Block04 : : cb DC : : motion x : |   |
263 |   |  .........  : cr DC : : motion y : |   |
264 |   |              .......   ..........  |   |
265 |    ------------------------------------    |
266 |    ------------------------------------    |
267 |   |               Block1               |   |
268 |                    ...                     |
269  --------------------------------------------
270 | ------------   ------------   ------------ |
271 || Y subbands | | Cb subbands| | Cr subbands||
272 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
273 || |LL0||HL0| | | |LL0||HL0| | | |LL0||HL0| ||
274 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
275 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
276 || |LH0||HH0| | | |LH0||HH0| | | |LH0||HH0| ||
277 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
278 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
279 || |HL1||LH1| | | |HL1||LH1| | | |HL1||LH1| ||
280 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
281 ||  ---  ---  | |  ---  ---  | |  ---  ---  ||
282 || |HH1||HL2| | | |HH1||HL2| | | |HH1||HL2| ||
283 ||    ...     | |    ...     | |    ...     ||
284 | ------------   ------------   ------------ |
285  --------------------------------------------
287 Decoding process:
288 =================
290                                          ------------
291                                         |            |
292                                         |  Subbands  |
293                    ------------         |            |
294                   |            |         ------------
295                   |  Intra DC  |               |
296                   |            |    LL0 subband prediction
297                    ------------                |
298                                 \        Dequantizaton
299  -------------------             \             |
300 |  Reference frames |             \           IDWT
301 | -------   ------- |    Motion    \           |
302 ||Frame 0| |Frame 1|| Compensation  .   OBMC   v      -------
303 | -------   ------- | --------------. \------> + --->|Frame n|-->output
304 | -------   ------- |                                 -------
305 ||Frame 2| |Frame 3||<----------------------------------/
306 |        ...        |
307  -------------------
310 Range Coder:
311 ============
313 Binary Range Coder:
314 -------------------
315 The implemented range coder is an adapted version based upon "Range encoding:
316 an algorithm for removing redundancy from a digitised message." by G. N. N.
317 Martin.
318 The symbols encoded by the Snow range coder are bits (0|1). The
319 associated probabilities are not fix but change depending on the symbol mix
320 seen so far.
323 bit seen | new state
324 ---------+-----------------------------------------------
325     0    | 256 - state_transition_table[256 - old_state];
326     1    |       state_transition_table[      old_state];
328 state_transition_table = {
329   0,   0,   0,   0,   0,   0,   0,   0,  20,  21,  22,  23,  24,  25,  26,  27,
330  28,  29,  30,  31,  32,  33,  34,  35,  36,  37,  37,  38,  39,  40,  41,  42,
331  43,  44,  45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,  56,  56,  57,
332  58,  59,  60,  61,  62,  63,  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,
333  74,  75,  75,  76,  77,  78,  79,  80,  81,  82,  83,  84,  85,  86,  87,  88,
334  89,  90,  91,  92,  93,  94,  94,  95,  96,  97,  98,  99, 100, 101, 102, 103,
335 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 114, 115, 116, 117, 118,
336 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 133,
337 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
338 150, 151, 152, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164,
339 165, 166, 167, 168, 169, 170, 171, 171, 172, 173, 174, 175, 176, 177, 178, 179,
340 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 190, 191, 192, 194, 194,
341 195, 196, 197, 198, 199, 200, 201, 202, 202, 204, 205, 206, 207, 208, 209, 209,
342 210, 211, 212, 213, 215, 215, 216, 217, 218, 219, 220, 220, 222, 223, 224, 225,
343 226, 227, 227, 229, 229, 230, 231, 232, 234, 234, 235, 236, 237, 238, 239, 240,
344 241, 242, 243, 244, 245, 246, 247, 248, 248,   0,   0,   0,   0,   0,   0,   0};
346 FIXME
349 Range Coding of integers:
350 -------------------------
351 FIXME
354 Neighboring Blocks:
355 ===================
356 left and top are set to the respective blocks unless they are outside of
357 the image in which case they are set to the Null block
359 top-left is set to the top left block unless it is outside of the image in
360 which case it is set to the left block
362 if this block has no larger parent block or it is at the left side of its
363 parent block and the top right block is not outside of the image then the
364 top right block is used for top-right else the top-left block is used
366 Null block
367 y,cb,cr are 128
368 level, ref, mx and my are 0
371 Motion Vector Prediction:
372 =========================
373 1. the motion vectors of all the neighboring blocks are scaled to
374 compensate for the difference of reference frames
376 scaled_mv= (mv * (256 * (current_reference+1) / (mv.reference+1)) + 128)>>8
378 2. the median of the scaled left, top and top-right vectors is used as
379 motion vector prediction
381 3. the used motion vector is the sum of the predictor and
382    (mvx_diff, mvy_diff)*mv_scale
385 Intra DC Predicton:
386 ======================
387 the luma and chroma values of the left block are used as predictors
389 the used luma and chroma is the sum of the predictor and y_diff, cb_diff, cr_diff
390 to reverse this in the decoder apply the following:
391 block[y][x].dc[0] = block[y][x-1].dc[0] +  y_diff;
392 block[y][x].dc[1] = block[y][x-1].dc[1] + cb_diff;
393 block[y][x].dc[2] = block[y][x-1].dc[2] + cr_diff;
394 block[*][-1].dc[*]= 128;
397 Motion Compensation:
398 ====================
400 Halfpel interpolation:
401 ----------------------
402 halfpel interpolation is done by convolution with the halfpel filter stored
403 in the header:
405 horizontal halfpel samples are found by
406 H1[y][x] =    hcoeff[0]*(F[y][x  ] + F[y][x+1])
407             + hcoeff[1]*(F[y][x-1] + F[y][x+2])
408             + hcoeff[2]*(F[y][x-2] + F[y][x+3])
409             + ...
410 h1[y][x] = (H1[y][x] + 32)>>6;
412 vertical halfpel samples are found by
413 H2[y][x] =    hcoeff[0]*(F[y  ][x] + F[y+1][x])
414             + hcoeff[1]*(F[y-1][x] + F[y+2][x])
415             + ...
416 h2[y][x] = (H2[y][x] + 32)>>6;
418 vertical+horizontal halfpel samples are found by
419 H3[y][x] =    hcoeff[0]*(H2[y][x  ] + H2[y][x+1])
420             + hcoeff[1]*(H2[y][x-1] + H2[y][x+2])
421             + ...
422 H3[y][x] =    hcoeff[0]*(H1[y  ][x] + H1[y+1][x])
423             + hcoeff[1]*(H1[y+1][x] + H1[y+2][x])
424             + ...
425 h3[y][x] = (H3[y][x] + 2048)>>12;
428                    F   H1  F
429                    |   |   |
430                    |   |   |
431                    |   |   |
432                    F   H1  F
433                    |   |   |
434                    |   |   |
435                    |   |   |
436    F-------F-------F-> H1<-F-------F-------F
437                    v   v   v
438                   H2   H3  H2
439                    ^   ^   ^
440    F-------F-------F-> H1<-F-------F-------F
441                    |   |   |
442                    |   |   |
443                    |   |   |
444                    F   H1  F
445                    |   |   |
446                    |   |   |
447                    |   |   |
448                    F   H1  F
451 unavailable fullpel samples (outside the picture for example) shall be equal
452 to the closest available fullpel sample
455 Smaller pel interpolation:
456 --------------------------
457 if diag_mc is set then points which lie on a line between 2 vertically,
458 horiziontally or diagonally adjacent halfpel points shall be interpolated
459 linearls with rounding to nearest and halfway values rounded up.
460 points which lie on 2 diagonals at the same time should only use the one
461 diagonal not containing the fullpel point
465            F-->O---q---O<--h1->O---q---O<--F
466            v \           / v \           / v
467            O   O       O   O   O       O   O
468            |         /     |     \         |
469            q       q       q       q       q
470            |     /         |         \     |
471            O   O       O   O   O       O   O
472            ^ /           \ ^ /           \ ^
473           h2-->O---q---O<--h3->O---q---O<--h2
474            v \           / v \           / v
475            O   O       O   O   O       O   O
476            |     \         |         /     |
477            q       q       q       q       q
478            |         \     |     /         |
479            O   O       O   O   O       O   O
480            ^ /           \ ^ /           \ ^
481            F-->O---q---O<--h1->O---q---O<--F
485 the remaining points shall be bilinearly interpolated from the
486 up to 4 surrounding halfpel and fullpel points, again rounding should be to
487 nearest and halfway values rounded up
489 compliant Snow decoders MUST support 1-1/8 pel luma and 1/2-1/16 pel chroma
490 interpolation at least
493 Overlapped block motion compensation:
494 -------------------------------------
495 FIXME
497 LL band prediction:
498 ===================
499 Each sample in the LL0 subband is predicted by the median of the left, top and
500 left+top-topleft samples, samples outside the subband shall be considered to
501 be 0. To reverse this prediction in the decoder apply the following.
502 for(y=0; y<height; y++){
503     for(x=0; x<width; x++){
504         sample[y][x] += median(sample[y-1][x],
505                                sample[y][x-1],
506                                sample[y-1][x]+sample[y][x-1]-sample[y-1][x-1]);
507     }
509 sample[-1][*]=sample[*][-1]= 0;
510 width,height here are the width and height of the LL0 subband not of the final
511 video
514 Dequantizaton:
515 ==============
516 FIXME
518 Wavelet Transform:
519 ==================
521 Snow supports 2 wavelet transforms, the symmetric biorthogonal 5/3 integer
522 transform and a integer approximation of the symmetric biorthogonal 9/7
523 daubechies wavelet.
525 2D IDWT (inverse discrete wavelet transform)
526 --------------------------------------------
527 The 2D IDWT applies a 2D filter recursively, each time combining the
528 4 lowest frequency subbands into a single subband until only 1 subband
529 remains.
530 The 2D filter is done by first applying a 1D filter in the vertical direction
531 and then applying it in the horizontal one.
532  ---------------    ---------------    ---------------    ---------------
533 |LL0|HL0|       |  |   |   |       |  |       |       |  |       |       |
534 |---+---|  HL1  |  | L0|H0 |  HL1  |  |  LL1  |  HL1  |  |       |       |
535 |LH0|HH0|       |  |   |   |       |  |       |       |  |       |       |
536 |-------+-------|->|-------+-------|->|-------+-------|->|   L1  |  H1   |->...
537 |       |       |  |       |       |  |       |       |  |       |       |
538 |  LH1  |  HH1  |  |  LH1  |  HH1  |  |  LH1  |  HH1  |  |       |       |
539 |       |       |  |       |       |  |       |       |  |       |       |
540  ---------------    ---------------    ---------------    ---------------
543 1D Filter:
544 ----------
545 1. interleave the samples of the low and high frequency subbands like
546 s={L0, H0, L1, H1, L2, H2, L3, H3, ... }
547 note, this can end with a L or a H, the number of elements shall be w
548 s[-1] shall be considered equivalent to s[1  ]
549 s[w ] shall be considered equivalent to s[w-2]
551 2. perform the lifting steps in order as described below
553 5/3 Integer filter:
554 1. s[i] -= (s[i-1] + s[i+1] + 2)>>2; for all even i < w
555 2. s[i] += (s[i-1] + s[i+1]    )>>1; for all odd  i < w
557 \ | /|\ | /|\ | /|\ | /|\
558  \|/ | \|/ | \|/ | \|/ |
559   +  |  +  |  +  |  +  |   -1/4
560  /|\ | /|\ | /|\ | /|\ |
561 / | \|/ | \|/ | \|/ | \|/
562   |  +  |  +  |  +  |  +   +1/2
565 Snow's 9/7 Integer filter:
566 1. s[i] -= (3*(s[i-1] + s[i+1])         + 4)>>3; for all even i < w
567 2. s[i] -=     s[i-1] + s[i+1]                 ; for all odd  i < w
568 3. s[i] += (   s[i-1] + s[i+1] + 4*s[i] + 8)>>4; for all even i < w
569 4. s[i] += (3*(s[i-1] + s[i+1])            )>>1; for all odd  i < w
571 \ | /|\ | /|\ | /|\ | /|\
572  \|/ | \|/ | \|/ | \|/ |
573   +  |  +  |  +  |  +  |   -3/8
574  /|\ | /|\ | /|\ | /|\ |
575 / | \|/ | \|/ | \|/ | \|/
576  (|  + (|  + (|  + (|  +   -1
577 \ + /|\ + /|\ + /|\ + /|\  +1/4
578  \|/ | \|/ | \|/ | \|/ |
579   +  |  +  |  +  |  +  |   +1/16
580  /|\ | /|\ | /|\ | /|\ |
581 / | \|/ | \|/ | \|/ | \|/
582   |  +  |  +  |  +  |  +   +3/2
584 optimization tips:
585 following are exactly identical
586 (3a)>>1 == a + (a>>1)
587 (a + 4b + 8)>>4 == ((a>>2) + b + 2)>>2
589 16bit implementation note:
590 The IDWT can be implemented with 16bits, but this requires some care to
591 prevent overflows, the following list, lists the minimum number of bits needed
592 for some terms
593 1. lifting step
594 A= s[i-1] + s[i+1]                              16bit
595 3*A + 4                                         18bit
596 A + (A>>1) + 2                                  17bit
598 3. lifting step
599 s[i-1] + s[i+1]                                 17bit
601 4. lifiting step
602 3*(s[i-1] + s[i+1])                             17bit
605 TODO:
606 =====
607 Important:
608 finetune initial contexts
609 flip wavelet?
610 try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
611 try the MV length as context for coding the residual coefficients
612 use extradata for stuff which is in the keyframes now?
613 the MV median predictor is patented IIRC
614 implement per picture halfpel interpolation
615 try different range coder state transition tables for different contexts
617 Not Important:
618 compare the 6 tap and 8 tap hpel filters (psnr/bitrate and subjective quality)
619 spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
622 Credits:
623 ========
624 Michael Niedermayer
625 Loren Merritt
628 Copyright:
629 ==========
630 GPL + GFDL + whatever is needed to make this a RFC