typo
[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
229
230 Motion Compensation:
231 ====================
232 FIXME
233
234 LL band prediction:
235 ===================
236 FIXME
237
238 Dequantizaton:
239 ==============
240 FIXME
241
242 Wavelet Transform:
243 ==================
244
245 Snow supports 2 wavelet transforms, the symmetric biorthogonal 5/3 integer
246 transform and a integer approximation of the symmetric biorthogonal 9/7
247 daubechies wavelet.
248
249 2D IDWT (inverse discrete wavelet transform)
250 --------------------------------------------
251 The 2D IDWT applies a 2D filter recursively, each time combining the
252 4 lowest frequency subbands into a single subband until only 1 subband
253 remains.
254 The 2D filter is done by first applying a 1D filter in the vertical direction
255 and then applying it in the horizontal one.
256  ---------------    ---------------    ---------------    ---------------
257 |LL0|HL0|       |  |   |   |       |  |       |       |  |       |       |
258 |---+---|  HL1  |  | L0|H0 |  HL1  |  |  LL1  |  HL1  |  |       |       |
259 |LH0|HH0|       |  |   |   |       |  |       |       |  |       |       |
260 |-------+-------|->|-------+-------|->|-------+-------|->|   L1  |  H1   |->...
261 |       |       |  |       |       |  |       |       |  |       |       |
262 |  LH1  |  HH1  |  |  LH1  |  HH1  |  |  LH1  |  HH1  |  |       |       |
263 |       |       |  |       |       |  |       |       |  |       |       |
264  ---------------    ---------------    ---------------    ---------------
265
266
267 1D Filter:
268 ----------
269 1. interleave the samples of the low and high frequency subbands like
270 s={L0, H0, L1, H1, L2, H2, L3, H3, ... }
271 note, this can end with a L or a H, the number of elements shall be w
272 s[-1] shall be considered equivalent to s[1  ]
273 s[w ] shall be considered equivalent to s[w-2]
274
275 2. perform the lifting steps in order as described below
276
277 5/3 Integer filter:
278 1. s[i] -= (s[i-1] + s[i+1] + 2)>>2; for all even i < w
279 2. s[i] += (s[i-1] + s[i+1]    )>>1; for all odd  i < w
280
281 \ | /|\ | /|\ | /|\ | /|\
282  \|/ | \|/ | \|/ | \|/ |
283   +  |  +  |  +  |  +  |   -1/4
284  /|\ | /|\ | /|\ | /|\ |
285 / | \|/ | \|/ | \|/ | \|/
286   |  +  |  +  |  +  |  +   +1/2
287
288
289 snows 9/7 Integer filter:
290 1. s[i] -= (3*(s[i-1] + s[i+1])         + 4)>>3; for all even i < w
291 2. s[i] -=     s[i-1] + s[i+1]                 ; for all odd  i < w
292 3. s[i] += (   s[i-1] + s[i+1] + 4*s[i] + 8)>>4; for all even i < w
293 4. s[i] += (3*(s[i-1] + s[i+1])            )>>1; for all odd  i < w
294
295 \ | /|\ | /|\ | /|\ | /|\
296  \|/ | \|/ | \|/ | \|/ |
297   +  |  +  |  +  |  +  |   -3/8
298  /|\ | /|\ | /|\ | /|\ |
299 / | \|/ | \|/ | \|/ | \|/
300  (|  + (|  + (|  + (|  +   -1
301 \ + /|\ + /|\ + /|\ + /|\  +1/4
302  \|/ | \|/ | \|/ | \|/ |
303   +  |  +  |  +  |  +  |   +1/16
304  /|\ | /|\ | /|\ | /|\ |
305 / | \|/ | \|/ | \|/ | \|/
306   |  +  |  +  |  +  |  +   +3/2
307
308
309 TODO:
310 =====
311 Important:
312 finetune initial contexts
313 spatial_decomposition_count per frame?
314 flip wavelet?
315 try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
316 try the MV length as context for coding the residual coefficients
317 use extradata for stuff which is in the keyframes now?
318 the MV median predictor is patented IIRC
319
320 Not Important:
321 spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
322
323
324 Credits:
325 ========
326 Michael Niedermayer
327 Loren Merritt
328
329
330 Copyright:
331 ==========
332 GPL + GFDL + whatever is needed to make this a RFC