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