← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/xvidcap/jaunty-proposed

« back to all changes in this revision

Viewing changes to ffmpeg/doc/snow.txt

  • Committer: Bazaar Package Importer
  • Author(s): Lionel Le Folgoc, Andrew Starr-Bochicchio, Lionel Le Folgoc
  • Date: 2008-12-26 00:10:06 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20081226001006-2040ls9680bd1blt
Tags: 1.1.7-0.2ubuntu1
https://launchpad.net/bugs/298547
https://launchpad.net/bugs/311412
[ Andrew Starr-Bochicchio ]
* Merge from debian-multimedia (LP: #298547), Ubuntu Changes:
 - For ffmpeg-related build-deps, fix versionized dependencies
   as the ubuntu versioning is different than debian-multimedia's.

[ Lionel Le Folgoc ]
* LP: #311412 is fixed since the 1.1.7~rc1-0.1 revision.
* debian/patches/03_ffmpeg.diff: updated to fix FTBFS due to libswscale API
  change (cherry-pick from Gentoo #234383).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ffmpeg/doc/snow.txt
1
1
=============================================
2
 
SNOW Video Codec Specification Draft 20070103
 
2
Snow Video Codec Specification Draft 20080110
3
3
=============================================
4
4
 
 
5
Introduction:
 
6
=============
 
7
This specification describes the Snow bitstream syntax and semantics as
 
8
well as the formal Snow decoding process.
 
9
 
 
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.
5
16
 
6
17
Definitions:
7
18
============
45
56
        max_ref_frames-1                u   header_state
46
57
        qlogs
47
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
    }
48
75
 
49
76
    spatial_decomposition_type          s   header_state
50
77
    qlog                                s   header_state
70
97
            block(0)
71
98
 
72
99
block(level):
 
100
    mvx_diff=mvy_diff=y_diff=cb_diff=cr_diff=0
73
101
    if(keyframe){
74
102
        intra=1
75
 
        y_diff=cb_diff=cr_diff=0
76
103
    }else{
77
104
        if(level!=max_block_depth){
78
105
            s_context= 2*left->level + 2*top->level + topleft->level + topright->level
103
130
 
104
131
 
105
132
residual:
 
133
    residual2(luma)
 
134
    residual2(chroma_cr)
 
135
    residual2(chroma_cb)
 
136
 
 
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
    }
 
145
 
 
146
subband:
106
147
    FIXME
107
148
 
108
149
 
145
186
    maximum number of reference frames
146
187
    this MUST NOT change within a bitstream
147
188
 
 
189
update_mc
 
190
    indicates that motion compensation filter parameters are stored in the
 
191
    header
 
192
 
 
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
 
196
 
 
197
htaps
 
198
    number of half pel interpolation filter taps, MUST be even, >0 and <10
 
199
 
 
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}
 
216
 
 
217
 
148
218
ref_frames
149
219
    minimum of the number of available reference frames and max_ref_frames
150
220
    for example the first frame after a key frame always has ref_frames=1
175
245
quant_table
176
246
    quantiztation table
177
247
 
 
248
 
 
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
 --------------------------------------------
 
286
 
 
287
Decoding process:
 
288
=================
 
289
 
 
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
 -------------------
 
308
 
 
309
 
178
310
Range Coder:
179
311
============
180
 
FIXME
 
312
 
 
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.
 
321
 
 
322
 
 
323
bit seen | new state
 
324
---------+-----------------------------------------------
 
325
    0    | 256 - state_transition_table[256 - old_state];
 
326
    1    |       state_transition_table[      old_state];
 
327
 
 
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};
 
345
 
 
346
FIXME
 
347
 
 
348
 
 
349
Range Coding of integers:
 
350
-------------------------
 
351
FIXME
 
352
 
181
353
 
182
354
Neighboring Blocks:
183
355
===================
184
356
left and top are set to the respective blocks unless they are outside of
185
357
the image in which case they are set to the Null block
186
358
 
187
 
top-left is set to the top left block unless its outside of the image in
 
359
top-left is set to the top left block unless it is outside of the image in
188
360
which case it is set to the left block
189
361
 
190
 
if this block has no larger parent block or its at the left side of its
 
362
if this block has no larger parent block or it is at the left side of its
191
363
parent block and the top right block is not outside of the image then the
192
364
top right block is used for top-right else the top-left block is used
193
365
 
215
387
the luma and chroma values of the left block are used as predictors
216
388
 
217
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;
218
395
 
219
396
 
220
397
Motion Compensation:
221
398
====================
 
399
 
 
400
Halfpel interpolation:
 
401
----------------------
 
402
halfpel interpolation is done by convolution with the halfpel filter stored
 
403
in the header:
 
404
 
 
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;
 
411
 
 
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;
 
417
 
 
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;
 
426
 
 
427
 
 
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
 
449
 
 
450
 
 
451
unavailable fullpel samples (outside the picture for example) shall be equal
 
452
to the closest available fullpel sample
 
453
 
 
454
 
 
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
 
462
 
 
463
 
 
464
 
 
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
 
482
 
 
483
 
 
484
 
 
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
 
488
 
 
489
compliant Snow decoders MUST support 1-1/8 pel luma and 1/2-1/16 pel chroma
 
490
interpolation at least
 
491
 
 
492
 
 
493
Overlapped block motion compensation:
 
494
-------------------------------------
222
495
FIXME
223
496
 
224
497
LL band prediction:
225
498
===================
226
 
FIXME
 
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
 
512
 
227
513
 
228
514
Dequantizaton:
229
515
==============
231
517
 
232
518
Wavelet Transform:
233
519
==================
234
 
FIXME
 
520
 
 
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.
 
524
 
 
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
 ---------------    ---------------    ---------------    ---------------
 
541
 
 
542
 
 
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]
 
550
 
 
551
2. perform the lifting steps in order as described below
 
552
 
 
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
 
556
 
 
557
\ | /|\ | /|\ | /|\ | /|\
 
558
 \|/ | \|/ | \|/ | \|/ |
 
559
  +  |  +  |  +  |  +  |   -1/4
 
560
 /|\ | /|\ | /|\ | /|\ |
 
561
/ | \|/ | \|/ | \|/ | \|/
 
562
  |  +  |  +  |  +  |  +   +1/2
 
563
 
 
564
 
 
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
 
570
 
 
571
\ | /|\ | /|\ | /|\ | /|\
 
572
 \|/ | \|/ | \|/ | \|/ |
 
573
  +  |  +  |  +  |  +  |   -3/8
 
574
 /|\ | /|\ | /|\ | /|\ |
 
575
/ | \|/ | \|/ | \|/ | \|/
 
576
 (|  + (|  + (|  + (|  +   -1
 
577
\ + /|\ + /|\ + /|\ + /|\  +1/4
 
578
 \|/ | \|/ | \|/ | \|/ |
 
579
  +  |  +  |  +  |  +  |   +1/16
 
580
 /|\ | /|\ | /|\ | /|\ |
 
581
/ | \|/ | \|/ | \|/ | \|/
 
582
  |  +  |  +  |  +  |  +   +3/2
 
583
 
 
584
optimization tips:
 
585
following are exactly identical
 
586
(3a)>>1 == a + (a>>1)
 
587
(a + 4b + 8)>>4 == ((a>>2) + b + 2)>>2
 
588
 
 
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
 
597
 
 
598
3. lifting step
 
599
s[i-1] + s[i+1]                                 17bit
 
600
 
 
601
4. lifiting step
 
602
3*(s[i-1] + s[i+1])                             17bit
 
603
 
235
604
 
236
605
TODO:
237
606
=====
238
607
Important:
239
608
finetune initial contexts
240
 
spatial_decomposition_count per frame?
241
609
flip wavelet?
242
610
try to use the wavelet transformed predicted image (motion compensated image) as context for coding the residual coefficients
243
611
try the MV length as context for coding the residual coefficients
244
612
use extradata for stuff which is in the keyframes now?
245
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
246
616
 
247
617
Not Important:
 
618
compare the 6 tap and 8 tap hpel filters (psnr/bitrate and subjective quality)
248
619
spatial_scalability b vs u (!= 0 breaks syntax anyway so we can add a u later)
249
620
 
250
621