[FFmpeg-devel] [PATCH] G.722 trellis encoder
Michael Niedermayer
michaelni
Tue Nov 2 13:19:22 CET 2010
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>
More information about the ffmpeg-devel
mailing list