[Ffmpeg-cvslog] r5438 - trunk/doc/TODO

[Michael Niedermayer]

Hi

On Thu, Jun 01, 2006 at 08:40:12PM +0200, Michael Niedermayer wrote:
> Hi
> 
> On Thu, Jun 01, 2006 at 08:48:28AM -0700, Mike Melanson wrote:
> > michael wrote:
> > >+- ADPCM: viterbi/trellis based optimal encoder
> > 
> > Are we talking about simple IMA ADPCM-type algorithms here?
> 
> yes

to clarify this a little, ADPCM in general encodes differences beween
samples using a small number of possible difference values and adapts
which values are allowed depending upon past difference values
( ... we all know that)

all of our current ADPCM encoders work based on the principle that
we select the best possible difference between the last sample and
the current sample while we ignore both future and past, thats not
optimal at all

a viterbi based encoder would select the optimal sequence of differences
which minimize some distortion measure like the sum of squares

viterbi ADPCM encoder:
instead of keeping a single sequence of encoded differenes of the past
samples and then encoding the next difference 
we keep track of the optimal sequence of differences/encoded bitstream
up to the current sample for every state (0..88 step + a few sample values
around the ideal one) next we just calculate the optimal bitstreams up to
the next sample using the current sample and the optimal ones up to the last
sample
hmm, i am not happy with my explanation, i doubt thats overly easy to 
understand :(

maybe a concrete example would help ...

lets say we have some input samples:    0,2,6,4,-4
and our example encoder can encode +4,+1,-1,+4 differences

our current style encoder would output: 0,1,5,4, 0 distortion=18 
optimal would be:                       1,2,6,2,-2 distortion=9

if we would start our current encoder at 1 instead of 0 it would output:
                                        1,2,6,5, 1 distortion=27

viterbi encoder:
1. iteration
-2              distortion 4
-1              distortion 1
 0              distortion 0
 1              distortion 1
 2              distortion 4
2. iteration
 0, 0           distortion 4
 0, 1           distortion 1
 1, 2           distortion 1
-1, 3           distortion 2
 0, 4           distortion 4
3. iteration
-1, 3, 4        distortion 6
 0, 1, 5        distortion 2
 1, 2, 6        distortion 1
-1, 3, 7        distortion 3
 0, 4, 8        distortion 8
4. iteration
 1, 2, 6, 2     distortion 5
-1, 3, 7, 3     distortion 4
 0, 1, 5, 4     distortion 2
 1, 2, 6, 5     distortion 2
 1, 2, 6, 6     distortion 5
5. iteration
not possibl,-6
not possibl,-5
not possibl,-4
not possibl,-3
 1, 2, 6, 2,-2  distortion 9


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

In the past you could go to a library and read, borrow or copy any book
Today you'd get arrested for mere telling someone where the library is