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

[Michael Niedermayer]

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


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

I have never wished to cater to the crowd; for what I know they do not
approve, and what they approve I do not know. -- Epicurus
-------------- 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/20101101/b8e8ac53/attachment.pgp>