688dbd836f4e0bd4f08e16fbb7478fc3a0fcf35d
[ffmpeg.git] / doc / snow.txt
1 =============================================
2 SNOW Video Codec Specification Draft 20070103
3 =============================================
4
5 Intro:
6 ======
7 This Specification describes the snow syntax and semmantics as well as
8 how to decode snow.
9 The decoding process is precissely described and any compliant decoder
10 MUST produce the exactly same output for a spec conformant snow stream.
11 For encoding though any process which generates a stream compliant to
12 the syntactical and semmantical requirements and which is decodeable by
13 the process described in this spec shall be considered a conformant
14 snow encoder.
15
16 Definitions:
17 ============
18
19 MUST    the specific part must be done to conform to this standard
20 SHOULD  it is recommended to be done that way, but not strictly required
21
22 ilog2(x) is the rounded down logarithm of x with basis 2
23 ilog2(0) = 0
24
25 Type definitions:
26 =================
27
28 b   1-bit range coded
29 u   unsigned scalar value range coded
30 s   signed scalar value range coded
31
32
33 Bitstream syntax:
34 =================
35
36 frame:
37     header
38     prediction
39     residual
40
41 header:
42     keyframe                            b   MID_STATE
43     if(keyframe || always_reset)
44         reset_contexts
45     if(keyframe){
46         version                         u   header_state
47         always_reset                    b   header_state
48         temporal_decomposition_type     u   header_state
49         temporal_decomposition_count    u   header_state
50         spatial_decomposition_count     u   header_state
51         colorspace_type                 u   header_state
52         chroma_h_shift                  u   header_state
53         chroma_v_shift                  u   header_state
54         spatial_scalability             b   header_state
55         max_ref_frames-1                u   header_state
56         qlogs
57     }
58     if(!keyframe){
59         if(!always_reset)
60             update_mc                   b   header_state
61         if(always_reset || 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     }
75
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
81
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     }
90
91 reset_contexts
92     *_state[*]= MID_STATE
93
94 prediction:
95     for(y=0; y<block_count_vertical; y++)
96         for(x=0; x<block_count_horizontal; x++)
97             block(0)
98
99 block(level):
100     if(keyframe){
101         intra=1
102         y_diff=cb_diff=cr_diff=0
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     }
130
131
132 residual:
133     FIXME
134
135
136
137 Tag description:
138 ----------------
139
140 version
141     0
142     this MUST NOT change within a bitstream
143
144 always_reset
145     if 1 then the range coder contexts will be reset after each frame
146
147 temporal_decomposition_type
148     0
149
150 temporal_decomposition_count
151     0
152
153 spatial_decomposition_count
154     FIXME
155
156 colorspace_type
157     0
158     this MUST NOT change within a bitstream
159
160 chroma_h_shift
161     log2(luma.width / chroma.width)
162     this MUST NOT change within a bitstream
163
164 chroma_v_shift
165     log2(luma.height / chroma.height)
166     this MUST NOT change within a bitstream
167
168 spatial_scalability
169     0
170
171 max_ref_frames
172     maximum number of reference frames
173     this MUST NOT change within a bitstream
174
175 update_mc
176     indicates that motion compensation filter parameters are stored in the
177     header
178
179 diag_mc
180     flag to enable faster diagonal interpolation
181     this SHOULD be 1 unless it turns out to be covered by a valid patent
182
183 htaps
184     number of half pel interpolation filter taps, MUST be even, >0 and <10
185
186 hcoeff
187     half pel interpolation filter coefficients, hcoeff[0] are the 2 middle
188     coefficients [1] are the next outer ones and so on, resulting in a filter
189     like: ...eff[2], hcoeff[1], hcoeff[0], hcoeff[0], hcoeff[1], hcoeff[2] ...
190     the sign of the coefficients is not explicitly stored but alternates
191     after each coeff and coeff[0] is positive, so ...,+,-,+,-,+,+,-,+,-,+,...
192     hcoeff[0] is not explicitly stored but found by subtracting the sum
193     of all stored coefficients with signs from 32
194     hcoeff[0]= 32 - hcoeff[1] - hcoeff[2] - ...
195     a good choice for hcoeff and htaps is
196     htaps= 6
197     hcoeff={40,-10,2}
198     an alternative which requires more computations at both encoder and
199     decoder side and may or may not be better is
200     htaps= 8
201     hcoeff={42,-14,6,-2}
202
203
204 ref_frames
205     minimum of the number of available reference frames and max_ref_frames
206     for example the first frame after a key frame always has ref_frames=1
207
208 spatial_decomposition_type
209     wavelet type
210     0 is a 9/7 symmetric compact integer wavelet
211     1 is a 5/3 symmetric compact integer wavelet
212     others are reserved
213     stored as delta from last, last is reset to 0 if always_reset || keyframe
214
215 qlog
216     quality (logarthmic quantizer scale)
217     stored as delta from last, last is reset to 0 if always_reset || keyframe
218
219 mv_scale
220     stored as delta from last, last is reset to 0 if always_reset || keyframe
221     FIXME check that everything works fine if this changes between frames
222
223 qbias
224     dequantization bias
225     stored as delta from last, last is reset to 0 if always_reset || keyframe
226
227 block_max_depth
228     maximum depth of the block tree
229     stored as delta from last, last is reset to 0 if always_reset || keyframe
230
231 quant_table
232     quantiztation table
233
234 Range Coder:
235 ============
236 FIXME
237
238 Neighboring Blocks:
239 ===================
240 left and top are set to the respective blocks unless they are outside of
241 the image in which case they are set to the Null block
242
243 top-left is set to the top left block unless it is outside of the image in
244 which case it is set to the left block
245
246 if this block has no larger parent block or it is at the left side of its
247 parent block and the top right block is not outside of the image then the
248 top right block is used for top-right else the top-left block is used
249
250 Null block
251 y,cb,cr are 128
252 level, ref, mx and my are 0
253
254
255 Motion Vector Prediction:
256 =========================
257 1. the motion vectors of all the neighboring blocks are scaled to
258 compensate for the difference of reference frames
259
260 scaled_mv= (mv * (256 * (current_reference+1) / (mv.reference+1)) + 128)>>8
261
262 2. the median of the scaled left, top and top-right vectors is used as
263 motion vector prediction
264
265 3. the used motion vector is the sum of the predictor and
266    (mvx_diff, mvy_diff)*mv_scale
267
268
269 Intra DC Predicton:
270 ======================
271 the luma and chroma values of the left block are used as predictors
272
273 the used luma and chroma is the sum of the predictor and y_diff, cb_diff, cr_diff
274 to reverse this in the decoder apply the following:
275 block[y][x].dc[0] += block[y][x-1].dc[0];
276 block[y][x].dc[1] += block[y][x-1].dc[1];
277 block[y][x].dc[2] += block[y][x-1].dc[2];
278 block[*][-1].dc[*]= 128;
279
280
281 Motion Compensation:
282 ====================
283
284 Halfpel interpolation:
285 ----------------------
286 halfpel interpolation is done by convolution with the halfpel filter stored
287 in the header:
288
289 horizontal halfpel samples are found by
290 H1[y][x] =    hcoeff[0]*(F[y][x  ] + F[y][x+1])
291             + hcoeff[1]*(F[y][x-1] + F[y][x+2])
292             + hcoeff[2]*(F[y][x-2] + F[y][x+3])
293             + ...
294 h1[y][x] = (H1[y][x] + 32)>>6;
295
296 vertical halfpel samples are found by
297 H2[y][x] =    hcoeff[0]*(F[y  ][x] + F[y+1][x])
298             + hcoeff[1]*(F[y-1][x] + F[y+2][x])
299             + ...
300 h2[y][x] = (H2[y][x] + 32)>>6;
301
302 vertical+horizontal halfpel samples are found by
303 H3[y][x] =    hcoeff[0]*(H2[y][x  ] + H2[y][x+1])
304             + hcoeff[1]*(H2[y][x-1] + H2[y][x+2])
305             + ...
306 H3[y][x] =    hcoeff[0]*(H1[y  ][x] + H1[y+1][x])
307             + hcoeff[1]*(H1[y+1][x] + H1[y+2][x])
308             + ...
309 h3[y][x] = (H3[y][x] + 2048)>>12;
310
311
312                    F   H1  F
313                    |   |   |
314                    |   |   |
315                    |   |   |
316                    F   H1  F
317                    |   |   |
318                    |   |   |
319                    |   |   |
320    F-------F-------F-> H1<-F-------F-------F
321                    v   v   v
322                   H2   H3  H2
323                    ^   ^   ^
324    F-------F-------F-> H1<-F-------F-------F
325                    |   |   |
326                    |   |   |
327                    |   |   |
328                    F   H1  F
329                    |   |   |
330                    |   |   |
331                    |   |   |
332                    F   H1  F
333
334
335 unavailable fullpel samples (outside the picture for example) shall be equal
336 to the closest available fullpel sample
337
338
339 Smaller pel interpolation:
340 --------------------------
341 if diag_mc is set then points which lie on a line between 2 vertically,
342 horiziontally or diagonally adjacent halfpel points shall be interpolated
343 linearls with rounding to nearest and halfway values rounded up.
344 points which lie on 2 diagonals at the same time should only use the one
345 diagonal not containing the fullpel point
346
347
348
349            F-->O---q---O<--h1->O---q---O<--F
350            v \           / v \           / v
351            O   O       O   O   O       O   O
352            |         /     |     \         |
353            q       q       q       q       q
354            |     /         |         \     |
355            O   O       O   O   O       O   O
356            ^ /           \ ^ /           \ ^
357           h2-->O---q---O<--h3->O---q---O<--h2
358            v \           / v \           / v
359            O   O       O   O   O       O   O
360            |     \         |         /     |
361            q       q       q       q       q
362            |         \     |     /         |
363            O   O       O   O   O       O   O
364            ^ /           \ ^ /           \ ^
365            F-->O---q---O<--h1->O---q---O<--F
366
367
368
369 the remaining points shall be bilinearly interpolated from the
370 up to 4 surrounding halfpel and fullpel points, again rounding should be to
371 nearest and halfway values rounded up
372
373 compliant snow decoders MUST support 1-1/8 pel luma and 1/2-1/16 pel chroma
374 interpolation at least
375
376
377 Overlapped block motion compensation:
378 -------------------------------------
379 FIXME
380
381 LL band prediction:
382 ===================
383 Each sample in the LL0 subband is predicted by the median of the left, top and
384 left+top-topleft samples, samples outside the subband shall be considered to
385 be 0. To reverse this prediction in the decoder apply the following.
386 for(y=0; y<height; y++){
387     for(x=0; x<width; x++){
388         sample[y][x] += median(sample[y-1][x],
389                                sample[y][x-1],
390                                sample[y-1][x]+sample[y][x-1]-sample[y-1][x-1]);
391     }
392 }
393 sample[-1][*]=sample[*][-1]= 0;
394 width,height here are the width and height of the LL0 subband not of the final
395 video
396
397
398 Dequantizaton:
399 ==============
400 FIXME
401
402 Wavelet Transform:
403 ==================
404
405 Snow supports 2 wavelet transforms, the symmetric biorthogonal 5/3 integer
406 transform and a integer approximation of the symmetric biorthogonal 9/7
407 daubechies wavelet.
408
409 2D IDWT (inverse discrete wavelet transform)
410 --------------------------------------------
411 The 2D IDWT applies a 2D filter recursively, each time combining the
412 4 lowest frequency subbands into a single subband until only 1 subband
413 remains.
414 The 2D filter is done by first applying a 1D filter in the vertical direction
415 and then applying it in the horizontal one.
416  ---------------    ---------------    ---------------    ---------------
417 |LL0|HL0|       |  |   |   |       |  |       |       |  |       |       |
418 |---+---|  HL1  |  | L0|H0 |  HL1  |  |  LL1  |  HL1  |  |       |       |
419 |LH0|HH0|       |  |   |   |       |  |       |       |  |       |       |
420 |-------+-------|->|-------+-------|->|-------+-------|->|   L1  |  H1   |->...
421 |       |       |  |       |       |  |       |       |  |       |       |
422 |  LH1  |  HH1  |  |  LH1  |  HH1  |  |  LH1  |  HH1  |  |       |       |
423 |       |       |  |       |       |  |       |       |  |       |       |
424  ---------------    ---------------    ---------------    ---------------
425
426
427 1D Filter:
428 ----------
429 1. interleave the samples of the low and high frequency subbands like
430 s={L0, H0, L1, H1, L2, H2, L3, H3, ... }
431 note, this can end with a L or a H, the number of elements shall be w
432 s[-1] shall be considered equivalent to s[1  ]
433 s[w ] shall be considered equivalent to s[w-2]
434
435 2. perform the lifting steps in order as described below
436
437 5/3 Integer filter:
438 1. s[i] -= (s[i-1] + s[i+1] + 2)>>2; for all even i < w
439 2. s[i] += (s[i-1] + s[i+1]    )>>1; for all odd  i < w
440
441 \ | /|\ | /|\ | /|\ | /|\
442  \|/ | \|/ | \|/ | \|/ |
443   +  |  +  |  +  |  +  |   -1/4
444  /|\ | /|\ | /|\ | /|\ |
445 / | \|/ | \|/ | \|/ | \|/
446   |  +  |  +  |  +  |  +   +1/2
447
448
449 snows 9/7 Integer filter:
450 1. s[i] -= (3*(s[i-1] + s[i+1])         + 4)>>3; for all even i < w
451 2. s[i] -=     s[i-1] + s[i+1]                 ; for all odd  i < w
452 3. s[i] += (   s[i-1] + s[i+1] + 4*s[i] + 8)>>4; for all even i < w
453 4. s[i] += (3*(s[i-1] + s[i+1])            )>>1; for all odd  i < w
454
455 \ | /|\ | /|\ | /|\ | /|\
456  \|/ | \|/ | \|/ | \|/ |
457   +  |  +  |  +  |  +  |   -3/8
458  /|\ | /|\ | /|\ | /|\ |
459 / | \|/ | \|/ | \|/ | \|/
460  (|  + (|  + (|  + (|  +   -1
461 \ + /|\ + /|\ + /|\ + /|\  +1/4
462  \|/ | \|/ | \|/ | \|/ |
463   +  |  +  |  +  |  +  |   +1/16
464  /|\ | /|\ | /|\ | /|\ |
465 / | \|/ | \|/ | \|/ | \|/
466   |  +  |  +  |  +  |  +   +3/2
467
468 optimization tips:
469 following are exactly identical
470 (3a)>>1 == a + (a>>1)
471 (a + 4b + 8)>>4 == ((a>>2) + b + 2)>>2
472
473 16bit implementation note:
474 The IDWT can be implemented with 16bits, but this requires some care to
475 prevent overflows, the following list, lists the minimum number of bits needed
476 for some terms
477 1. lifting step
478 A= s[i-1] + s[i+1]                              16bit
479 3*A + 4                                         18bit
480 A + (A>>1) + 2                                  17bit
481
482 3. lifting step
483 s[i-1] + s[i+1]                                 17bit
484
485 4. lifiting step
486 3*(s[i-1] + s[i+1])                             17bit
487
488
489 TODO:
490 =====
491 Important:
492 finetune initial contexts
493 spatial_decomposition_count per frame?
494 flip wavelet?
495 try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
496 try the MV length as context for coding the residual coefficients
497 use extradata for stuff which is in the keyframes now?
498 the MV median predictor is patented IIRC
499 change MC so per picture halfpel interpolation can be done and finish the implementation of it
500 compare the 6 tap and 8 tap hpel filters (psnr/bitrate and subjective quality)
501 try different range coder state transition tables for different contexts
502
503 Not Important:
504 spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
505
506
507 Credits:
508 ========
509 Michael Niedermayer
510 Loren Merritt
511
512
513 Copyright:
514 ==========
515 GPL + GFDL + whatever is needed to make this a RFC