[FFmpeg-devel] [PATCH] G.722 trellis encoder

[Martin Storsjö]

On Mon, 1 Nov 2010, Michael Niedermayer wrote:

> On Fri, Sep 24, 2010 at 12:43:41AM +0300, Martin Storsj? wrote:
> > Hi,
> > 
> > As in $subj, this adds a G.722 encoder codepath that uses trellis to 
> > improve the quality.
> > 
> > For the lower sub-band, it tries a few other values around the one 
> > suggested by encode_low. Since the lowest 2 bits of the codeword for the 
> > lower subband doesn't affect the predictor, testing values that don't 
> > change the lowest 2 bits is useless, since it's less optimal for the 
> > current sample but still affect the predictor in the same way.
> > 
> > For the higher sub-band, there's only 4 different combinations, so instead 
> > of testing a range around the value suggested by encode_high, it tests all 
> > 4 of them. (This gives a much larger gain than testing more values in the 
> > lower sub-band.)
> > 
> > For one sample, using -trellis 5, the stddev is lowered from 76.49 to 
> > 62.10 and the PSNR is increased from 58.66 to 60.47.
> [...]
> > +                    for (n = 0; n < frontier; n++) {
> > +                        if (!nodes_next[n] || ssd < nodes_next[n]->ssd) {
> > +                            struct TrellisNode* node = nodes_next[frontier - 1];
> > +                            if (!node) {
> > +                                assert(pathn < FREEZE_INTERVAL * frontier);
> > +                                node = next++;
> > +                                node->path = pathn++;
> > +                            }
> > +                            node->ssd = ssd;
> > +                            node->band[0] = band[0];
> > +                            node->band[1] = band[1];
> > +                            c->paths[node->path].value = value;
> > +                            c->paths[node->path].prev = nodes[j]->path;
> > +                            memmove(&nodes_next[n+1], &nodes_next[n],
> > +                                    (frontier - n - 1)*sizeof(*nodes_next));
> > +                            nodes_next[n] = node;
> > +                            break;
> > +                        }
> > +                    }
> 
> i dont know if it would help in practice with actual frontier sizes but this
> is not optimal. its O(n) while O(log n) can be achived (for example using a
> heap like in heap sort to keep things similar) or the whole could be
> written and then sorted using a modified quick sort that skiped the right
> side where no elements of it would be needed ...

Hmm, interesting idea. This code was written as a quite straight copy of 
the trellis code in adpcm.c, so if we'd want it to use a heap, I'd 
implement and test it there first.

One feature of the data structure in this algorithm that a heap doesn't 
provide fully is being able to remove the worst one (you only know the 
best one, at the top), which we need to do once the array is full. If we 
just replace last one in the array and sift that one up as far as it goes, 
we will never touch or replace any of the elements outside of the path 
from the last one up to the top.

Do you have any suggestions on how to do this better? That is, when the 
heap uses all of the array, and we have a new item to insert, how would 
one do it? One solution would be to replace any of the leaf nodes (e.g. 
pick a different one among the leaf nodes each time) and sift that one up.

// Martin