more todo
[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
59     spatial_decomposition_type          s   header_state
60     qlog                                s   header_state
61     mv_scale                            s   header_state
62     qbias                               s   header_state
63     block_max_depth                     s   header_state
64
65 qlogs:
66     for(plane=0; plane<2; plane++){
67         quant_table[plane][0][0]        s   header_state
68         for(level=0; level < spatial_decomposition_count; level++){
69             quant_table[plane][level][1]s   header_state
70             quant_table[plane][level][3]s   header_state
71         }
72     }
73
74 reset_contexts
75     *_state[*]= MID_STATE
76
77 prediction:
78     for(y=0; y<block_count_vertical; y++)
79         for(x=0; x<block_count_horizontal; x++)
80             block(0)
81
82 block(level):
83     if(keyframe){
84         intra=1
85         y_diff=cb_diff=cr_diff=0
86     }else{
87         if(level!=max_block_depth){
88             s_context= 2*left->level + 2*top->level + topleft->level + topright->level
89             leaf                        b   block_state[4 + s_context]
90         }
91         if(level==max_block_depth || leaf){
92             intra                       b   block_state[1 + left->intra + top->intra]
93             if(intra){
94                 y_diff                  s   block_state[32]
95                 cb_diff                 s   block_state[64]
96                 cr_diff                 s   block_state[96]
97             }else{
98                 ref_context= ilog2(2*left->ref) + ilog2(2*top->ref)
99                 if(ref_frames > 1)
100                     ref                 u   block_state[128 + 1024 + 32*ref_context]
101                 mx_context= ilog2(2*abs(left->mx - top->mx))
102                 my_context= ilog2(2*abs(left->my - top->my))
103                 mvx_diff                s   block_state[128 + 32*(mx_context + 16*!!ref)]
104                 mvy_diff                s   block_state[128 + 32*(my_context + 16*!!ref)]
105             }
106         }else{
107             block(level+1)
108             block(level+1)
109             block(level+1)
110             block(level+1)
111         }
112     }
113
114
115 residual:
116     FIXME
117
118
119
120 Tag description:
121 ----------------
122
123 version
124     0
125     this MUST NOT change within a bitstream
126
127 always_reset
128     if 1 then the range coder contexts will be reset after each frame
129
130 temporal_decomposition_type
131     0
132
133 temporal_decomposition_count
134     0
135
136 spatial_decomposition_count
137     FIXME
138
139 colorspace_type
140     0
141     this MUST NOT change within a bitstream
142
143 chroma_h_shift
144     log2(luma.width / chroma.width)
145     this MUST NOT change within a bitstream
146
147 chroma_v_shift
148     log2(luma.height / chroma.height)
149     this MUST NOT change within a bitstream
150
151 spatial_scalability
152     0
153
154 max_ref_frames
155     maximum number of reference frames
156     this MUST NOT change within a bitstream
157
158 ref_frames
159     minimum of the number of available reference frames and max_ref_frames
160     for example the first frame after a key frame always has ref_frames=1
161
162 spatial_decomposition_type
163     wavelet type
164     0 is a 9/7 symmetric compact integer wavelet
165     1 is a 5/3 symmetric compact integer wavelet
166     others are reserved
167     stored as delta from last, last is reset to 0 if always_reset || keyframe
168
169 qlog
170     quality (logarthmic quantizer scale)
171     stored as delta from last, last is reset to 0 if always_reset || keyframe
172
173 mv_scale
174     stored as delta from last, last is reset to 0 if always_reset || keyframe
175     FIXME check that everything works fine if this changes between frames
176
177 qbias
178     dequantization bias
179     stored as delta from last, last is reset to 0 if always_reset || keyframe
180
181 block_max_depth
182     maximum depth of the block tree
183     stored as delta from last, last is reset to 0 if always_reset || keyframe
184
185 quant_table
186     quantiztation table
187
188 Range Coder:
189 ============
190 FIXME
191
192 Neighboring Blocks:
193 ===================
194 left and top are set to the respective blocks unless they are outside of
195 the image in which case they are set to the Null block
196
197 top-left is set to the top left block unless it is outside of the image in
198 which case it is set to the left block
199
200 if this block has no larger parent block or it is at the left side of its
201 parent block and the top right block is not outside of the image then the
202 top right block is used for top-right else the top-left block is used
203
204 Null block
205 y,cb,cr are 128
206 level, ref, mx and my are 0
207
208
209 Motion Vector Prediction:
210 =========================
211 1. the motion vectors of all the neighboring blocks are scaled to
212 compensate for the difference of reference frames
213
214 scaled_mv= (mv * (256 * (current_reference+1) / (mv.reference+1)) + 128)>>8
215
216 2. the median of the scaled left, top and top-right vectors is used as
217 motion vector prediction
218
219 3. the used motion vector is the sum of the predictor and
220    (mvx_diff, mvy_diff)*mv_scale
221
222
223 Intra DC Predicton:
224 ======================
225 the luma and chroma values of the left block are used as predictors
226
227 the used luma and chroma is the sum of the predictor and y_diff, cb_diff, cr_diff
228 to reverse this in the decoder apply the following:
229 block[y][x].dc[0] += block[y][x-1].dc[0];
230 block[y][x].dc[1] += block[y][x-1].dc[1];
231 block[y][x].dc[2] += block[y][x-1].dc[2];
232 block[*][-1].dc[*]= 128;
233
234
235 Motion Compensation:
236 ====================
237 FIXME
238
239 LL band prediction:
240 ===================
241 Each sample in the LL0 subband is predicted by the median of the left, top and
242 left+top-topleft samples, samples outside the subband shall be considered to
243 be 0. To reverse this prediction in the decoder apply the following.
244 for(y=0; y<height; y++){
245     for(x=0; x<width; x++){
246         sample[y][x] += median(sample[y-1][x],
247                                sample[y][x-1],
248                                sample[y-1][x]+sample[y][x-1]-sample[y-1][x-1]);
249     }
250 }
251 sample[-1][*]=sample[*][-1]= 0;
252 width,height here are the width and height of the LL0 subband not of the final
253 video
254
255
256 Dequantizaton:
257 ==============
258 FIXME
259
260 Wavelet Transform:
261 ==================
262
263 Snow supports 2 wavelet transforms, the symmetric biorthogonal 5/3 integer
264 transform and a integer approximation of the symmetric biorthogonal 9/7
265 daubechies wavelet.
266
267 2D IDWT (inverse discrete wavelet transform)
268 --------------------------------------------
269 The 2D IDWT applies a 2D filter recursively, each time combining the
270 4 lowest frequency subbands into a single subband until only 1 subband
271 remains.
272 The 2D filter is done by first applying a 1D filter in the vertical direction
273 and then applying it in the horizontal one.
274  ---------------    ---------------    ---------------    ---------------
275 |LL0|HL0|       |  |   |   |       |  |       |       |  |       |       |
276 |---+---|  HL1  |  | L0|H0 |  HL1  |  |  LL1  |  HL1  |  |       |       |
277 |LH0|HH0|       |  |   |   |       |  |       |       |  |       |       |
278 |-------+-------|->|-------+-------|->|-------+-------|->|   L1  |  H1   |->...
279 |       |       |  |       |       |  |       |       |  |       |       |
280 |  LH1  |  HH1  |  |  LH1  |  HH1  |  |  LH1  |  HH1  |  |       |       |
281 |       |       |  |       |       |  |       |       |  |       |       |
282  ---------------    ---------------    ---------------    ---------------
283
284
285 1D Filter:
286 ----------
287 1. interleave the samples of the low and high frequency subbands like
288 s={L0, H0, L1, H1, L2, H2, L3, H3, ... }
289 note, this can end with a L or a H, the number of elements shall be w
290 s[-1] shall be considered equivalent to s[1  ]
291 s[w ] shall be considered equivalent to s[w-2]
292
293 2. perform the lifting steps in order as described below
294
295 5/3 Integer filter:
296 1. s[i] -= (s[i-1] + s[i+1] + 2)>>2; for all even i < w
297 2. s[i] += (s[i-1] + s[i+1]    )>>1; for all odd  i < w
298
299 \ | /|\ | /|\ | /|\ | /|\
300  \|/ | \|/ | \|/ | \|/ |
301   +  |  +  |  +  |  +  |   -1/4
302  /|\ | /|\ | /|\ | /|\ |
303 / | \|/ | \|/ | \|/ | \|/
304   |  +  |  +  |  +  |  +   +1/2
305
306
307 snows 9/7 Integer filter:
308 1. s[i] -= (3*(s[i-1] + s[i+1])         + 4)>>3; for all even i < w
309 2. s[i] -=     s[i-1] + s[i+1]                 ; for all odd  i < w
310 3. s[i] += (   s[i-1] + s[i+1] + 4*s[i] + 8)>>4; for all even i < w
311 4. s[i] += (3*(s[i-1] + s[i+1])            )>>1; for all odd  i < w
312
313 \ | /|\ | /|\ | /|\ | /|\
314  \|/ | \|/ | \|/ | \|/ |
315   +  |  +  |  +  |  +  |   -3/8
316  /|\ | /|\ | /|\ | /|\ |
317 / | \|/ | \|/ | \|/ | \|/
318  (|  + (|  + (|  + (|  +   -1
319 \ + /|\ + /|\ + /|\ + /|\  +1/4
320  \|/ | \|/ | \|/ | \|/ |
321   +  |  +  |  +  |  +  |   +1/16
322  /|\ | /|\ | /|\ | /|\ |
323 / | \|/ | \|/ | \|/ | \|/
324   |  +  |  +  |  +  |  +   +3/2
325
326 optimization tips:
327 following are exactly identical
328 (3a)>>1 == a + (a>>1)
329 (a + 4b + 8)>>4 == ((a>>2) + b + 2)>>2
330
331 TODO:
332 =====
333 Important:
334 finetune initial contexts
335 spatial_decomposition_count per frame?
336 flip wavelet?
337 try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
338 try the MV length as context for coding the residual coefficients
339 use extradata for stuff which is in the keyframes now?
340 the MV median predictor is patented IIRC
341 change MC so per picture halfpel interpolation can be done and finish the implementation of it
342 compare the 6 tap and 8 tap hpel filters (psnr/bitrate and subjective quality)
343 try different range coder state transition tables for different contexts
344
345 Not Important:
346 spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
347
348
349 Credits:
350 ========
351 Michael Niedermayer
352 Loren Merritt
353
354
355 Copyright:
356 ==========
357 GPL + GFDL + whatever is needed to make this a RFC