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

[Michael Niedermayer]

On Tue, Nov 02, 2010 at 11:14:49AM +0200, Martin Storsj? wrote:
> 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),

you flip up and down then you know the worst and can remove it


> 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.

finding the best is O(n), sorting all by completing the heap sort is O(n log n)
(radix sort would be faster but i dont think there are enough elements for this
 to be fast in parctice)
the current code does O(m*n) and the heap based insertion would do O(m log n)
with m>=n
so this doesnt look like it would be limiting

there are also balanced binary trees that allow faster finding of the biggest
element and faster spliting the tree in 2 but i think they would have more
overhead and end up slower but see libavutil/tree* if you want

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

I do not agree with what you have to say, but I'll defend to the death your
right to say it. -- Voltaire
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101102/161813e3/attachment.pgp>