| blob | f99133971c370d3c3a7470dfe2c9d3f33a9b0bfc |
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 }
508 }
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