1 =============================================
2 SNOW Video Codec Specification Draft 20070103
3 =============================================
7 This Specification describes the snow syntax and semmantics as well as
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
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
22 ilog2(x) is the rounded down logarithm of x with basis 2
29 u unsigned scalar value range coded
30 s signed scalar value range coded
43 if(keyframe || always_reset)
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
59 update_mc b header_state
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
68 update_qlogs b header_state
70 spatial_decomposition_count u header_state
75 spatial_decomposition_type s header_state
77 mv_scale s header_state
79 block_max_depth s header_state
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
94 for(y=0; y<block_count_vertical; y++)
95 for(x=0; x<block_count_horizontal; x++)
99 mvx_diff=mvy_diff=y_diff=cb_diff=cr_diff=0
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]
107 if(level==max_block_depth || leaf){
108 intra b block_state[1 + left->intra + top->intra]
110 y_diff s block_state[32]
111 cb_diff s block_state[64]
112 cr_diff s block_state[96]
114 ref_context= ilog2(2*left->ref) + ilog2(2*top->ref)
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)]
141 this MUST NOT change within a bitstream
144 if 1 then the range coder contexts will be reset after each frame
146 temporal_decomposition_type
149 temporal_decomposition_count
152 spatial_decomposition_count
157 this MUST NOT change within a bitstream
160 log2(luma.width / chroma.width)
161 this MUST NOT change within a bitstream
164 log2(luma.height / chroma.height)
165 this MUST NOT change within a bitstream
171 maximum number of reference frames
172 this MUST NOT change within a bitstream
175 indicates that motion compensation filter parameters are stored in the
179 flag to enable faster diagonal interpolation
180 this SHOULD be 1 unless it turns out to be covered by a valid patent
183 number of half pel interpolation filter taps, MUST be even, >0 and <10
186 half pel interpolation filter coefficients, hcoeff[0] are the 2 middle
187 coefficients [1] are the next outer ones and so on, resulting in a filter
188 like: ...eff[2], hcoeff[1], hcoeff[0], hcoeff[0], hcoeff[1], hcoeff[2] ...
189 the sign of the coefficients is not explicitly stored but alternates
190 after each coeff and coeff[0] is positive, so ...,+,-,+,-,+,+,-,+,-,+,...
191 hcoeff[0] is not explicitly stored but found by subtracting the sum
192 of all stored coefficients with signs from 32
193 hcoeff[0]= 32 - hcoeff[1] - hcoeff[2] - ...
194 a good choice for hcoeff and htaps is
197 an alternative which requires more computations at both encoder and
198 decoder side and may or may not be better is
204 minimum of the number of available reference frames and max_ref_frames
205 for example the first frame after a key frame always has ref_frames=1
207 spatial_decomposition_type
209 0 is a 9/7 symmetric compact integer wavelet
210 1 is a 5/3 symmetric compact integer wavelet
212 stored as delta from last, last is reset to 0 if always_reset || keyframe
215 quality (logarthmic quantizer scale)
216 stored as delta from last, last is reset to 0 if always_reset || keyframe
219 stored as delta from last, last is reset to 0 if always_reset || keyframe
220 FIXME check that everything works fine if this changes between frames
224 stored as delta from last, last is reset to 0 if always_reset || keyframe
227 maximum depth of the block tree
228 stored as delta from last, last is reset to 0 if always_reset || keyframe
234 Highlevel bitstream structure:
235 =============================
236 --------------------------------------------
238 --------------------------------------------
239 | ------------------------------------ |
243 | | ......... intra? | |
244 | | : Block01 : yes no | |
245 | | : Block02 : ....... .......... | |
246 | | : Block03 : : y DC : : ref index: | |
247 | | : Block04 : : cb DC : : motion x : | |
248 | | ......... : cr DC : : motion y : | |
249 | | ....... .......... | |
250 | ------------------------------------ |
251 | ------------------------------------ |
254 --------------------------------------------
255 | ------------ ------------ ------------ |
256 || Y subbands | | Cb subbands| | Cr subbands||
257 || --- --- | | --- --- | | --- --- ||
258 || |LL0||HL0| | | |LL0||HL0| | | |LL0||HL0| ||
259 || --- --- | | --- --- | | --- --- ||
260 || --- --- | | --- --- | | --- --- ||
261 || |LH0||HH0| | | |LH0||HH0| | | |LH0||HH0| ||
262 || --- --- | | --- --- | | --- --- ||
263 || --- --- | | --- --- | | --- --- ||
264 || |HL1||LH1| | | |HL1||LH1| | | |HL1||LH1| ||
265 || --- --- | | --- --- | | --- --- ||
266 || --- --- | | --- --- | | --- --- ||
267 || |HH1||HL2| | | |HH1||HL2| | | |HH1||HL2| ||
268 || ... | | ... | | ... ||
269 | ------------ ------------ ------------ |
270 --------------------------------------------
281 | | LL0 subband prediction
284 ------------------- \ |
285 | Reference frames | \ IDWT
286 | ------- ------- | Motion \ |
287 ||Frame 0| |Frame 1|| Compensation . OBMC v -------
288 | ------- ------- | --------------. \------> + --->|Frame n|-->output
289 | ------- ------- | -------
290 ||Frame 2| |Frame 3||<----------------------------------/
301 left and top are set to the respective blocks unless they are outside of
302 the image in which case they are set to the Null block
304 top-left is set to the top left block unless it is outside of the image in
305 which case it is set to the left block
307 if this block has no larger parent block or it is at the left side of its
308 parent block and the top right block is not outside of the image then the
309 top right block is used for top-right else the top-left block is used
313 level, ref, mx and my are 0
316 Motion Vector Prediction:
317 =========================
318 1. the motion vectors of all the neighboring blocks are scaled to
319 compensate for the difference of reference frames
321 scaled_mv= (mv * (256 * (current_reference+1) / (mv.reference+1)) + 128)>>8
323 2. the median of the scaled left, top and top-right vectors is used as
324 motion vector prediction
326 3. the used motion vector is the sum of the predictor and
327 (mvx_diff, mvy_diff)*mv_scale
331 ======================
332 the luma and chroma values of the left block are used as predictors
334 the used luma and chroma is the sum of the predictor and y_diff, cb_diff, cr_diff
335 to reverse this in the decoder apply the following:
336 block[y][x].dc[0] = block[y][x-1].dc[0] + y_diff;
337 block[y][x].dc[1] = block[y][x-1].dc[1] + cb_diff;
338 block[y][x].dc[2] = block[y][x-1].dc[2] + cr_diff;
339 block[*][-1].dc[*]= 128;
345 Halfpel interpolation:
346 ----------------------
347 halfpel interpolation is done by convolution with the halfpel filter stored
350 horizontal halfpel samples are found by
351 H1[y][x] = hcoeff[0]*(F[y][x ] + F[y][x+1])
352 + hcoeff[1]*(F[y][x-1] + F[y][x+2])
353 + hcoeff[2]*(F[y][x-2] + F[y][x+3])
355 h1[y][x] = (H1[y][x] + 32)>>6;
357 vertical halfpel samples are found by
358 H2[y][x] = hcoeff[0]*(F[y ][x] + F[y+1][x])
359 + hcoeff[1]*(F[y-1][x] + F[y+2][x])
361 h2[y][x] = (H2[y][x] + 32)>>6;
363 vertical+horizontal halfpel samples are found by
364 H3[y][x] = hcoeff[0]*(H2[y][x ] + H2[y][x+1])
365 + hcoeff[1]*(H2[y][x-1] + H2[y][x+2])
367 H3[y][x] = hcoeff[0]*(H1[y ][x] + H1[y+1][x])
368 + hcoeff[1]*(H1[y+1][x] + H1[y+2][x])
370 h3[y][x] = (H3[y][x] + 2048)>>12;
381 F-------F-------F-> H1<-F-------F-------F
385 F-------F-------F-> H1<-F-------F-------F
396 unavailable fullpel samples (outside the picture for example) shall be equal
397 to the closest available fullpel sample
400 Smaller pel interpolation:
401 --------------------------
402 if diag_mc is set then points which lie on a line between 2 vertically,
403 horiziontally or diagonally adjacent halfpel points shall be interpolated
404 linearls with rounding to nearest and halfway values rounded up.
405 points which lie on 2 diagonals at the same time should only use the one
406 diagonal not containing the fullpel point
410 F-->O---q---O<--h1->O---q---O<--F
418 h2-->O---q---O<--h3->O---q---O<--h2
426 F-->O---q---O<--h1->O---q---O<--F
430 the remaining points shall be bilinearly interpolated from the
431 up to 4 surrounding halfpel and fullpel points, again rounding should be to
432 nearest and halfway values rounded up
434 compliant snow decoders MUST support 1-1/8 pel luma and 1/2-1/16 pel chroma
435 interpolation at least
438 Overlapped block motion compensation:
439 -------------------------------------
444 Each sample in the LL0 subband is predicted by the median of the left, top and
445 left+top-topleft samples, samples outside the subband shall be considered to
446 be 0. To reverse this prediction in the decoder apply the following.
447 for(y=0; y<height; y++){
448 for(x=0; x<width; x++){
449 sample[y][x] += median(sample[y-1][x],
451 sample[y-1][x]+sample[y][x-1]-sample[y-1][x-1]);
454 sample[-1][*]=sample[*][-1]= 0;
455 width,height here are the width and height of the LL0 subband not of the final
466 Snow supports 2 wavelet transforms, the symmetric biorthogonal 5/3 integer
467 transform and a integer approximation of the symmetric biorthogonal 9/7
470 2D IDWT (inverse discrete wavelet transform)
471 --------------------------------------------
472 The 2D IDWT applies a 2D filter recursively, each time combining the
473 4 lowest frequency subbands into a single subband until only 1 subband
475 The 2D filter is done by first applying a 1D filter in the vertical direction
476 and then applying it in the horizontal one.
477 --------------- --------------- --------------- ---------------
478 |LL0|HL0| | | | | | | | | | | |
479 |---+---| HL1 | | L0|H0 | HL1 | | LL1 | HL1 | | | |
480 |LH0|HH0| | | | | | | | | | | |
481 |-------+-------|->|-------+-------|->|-------+-------|->| L1 | H1 |->...
482 | | | | | | | | | | | |
483 | LH1 | HH1 | | LH1 | HH1 | | LH1 | HH1 | | | |
484 | | | | | | | | | | | |
485 --------------- --------------- --------------- ---------------
490 1. interleave the samples of the low and high frequency subbands like
491 s={L0, H0, L1, H1, L2, H2, L3, H3, ... }
492 note, this can end with a L or a H, the number of elements shall be w
493 s[-1] shall be considered equivalent to s[1 ]
494 s[w ] shall be considered equivalent to s[w-2]
496 2. perform the lifting steps in order as described below
499 1. s[i] -= (s[i-1] + s[i+1] + 2)>>2; for all even i < w
500 2. s[i] += (s[i-1] + s[i+1] )>>1; for all odd i < w
502 \ | /|\ | /|\ | /|\ | /|\
503 \|/ | \|/ | \|/ | \|/ |
505 /|\ | /|\ | /|\ | /|\ |
506 / | \|/ | \|/ | \|/ | \|/
510 snows 9/7 Integer filter:
511 1. s[i] -= (3*(s[i-1] + s[i+1]) + 4)>>3; for all even i < w
512 2. s[i] -= s[i-1] + s[i+1] ; for all odd i < w
513 3. s[i] += ( s[i-1] + s[i+1] + 4*s[i] + 8)>>4; for all even i < w
514 4. s[i] += (3*(s[i-1] + s[i+1]) )>>1; for all odd i < w
516 \ | /|\ | /|\ | /|\ | /|\
517 \|/ | \|/ | \|/ | \|/ |
519 /|\ | /|\ | /|\ | /|\ |
520 / | \|/ | \|/ | \|/ | \|/
521 (| + (| + (| + (| + -1
522 \ + /|\ + /|\ + /|\ + /|\ +1/4
523 \|/ | \|/ | \|/ | \|/ |
524 + | + | + | + | +1/16
525 /|\ | /|\ | /|\ | /|\ |
526 / | \|/ | \|/ | \|/ | \|/
530 following are exactly identical
531 (3a)>>1 == a + (a>>1)
532 (a + 4b + 8)>>4 == ((a>>2) + b + 2)>>2
534 16bit implementation note:
535 The IDWT can be implemented with 16bits, but this requires some care to
536 prevent overflows, the following list, lists the minimum number of bits needed
539 A= s[i-1] + s[i+1] 16bit
544 s[i-1] + s[i+1] 17bit
547 3*(s[i-1] + s[i+1]) 17bit
553 finetune initial contexts
555 try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
556 try the MV length as context for coding the residual coefficients
557 use extradata for stuff which is in the keyframes now?
558 the MV median predictor is patented IIRC
559 implement per picture halfpel interpolation
560 try different range coder state transition tables for different contexts
563 compare the 6 tap and 8 tap hpel filters (psnr/bitrate and subjective quality)
564 spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
575 GPL + GFDL + whatever is needed to make this a RFC