[FFmpeg-devel] [PATCH] Make ff_lpc_calc_coefs order estimation?flexible by passing parameters
Justin Ruggles
justinruggles
Sun Aug 17 17:43:05 CEST 2008
Michael Niedermayer wrote:
> On Sat, Aug 16, 2008 at 08:29:34PM -0400, Justin Ruggles wrote:
>> Justin Ruggles wrote:
>>> Michael Niedermayer wrote:
>>>> On Sun, Aug 17, 2008 at 02:10:28AM +0530, Jai Menon wrote:
>>>>> Hi,
>>>>>
>>>>> On Sunday 17 Aug 2008 1:38:51 am Michael Niedermayer wrote:
>>>>>> On Sun, Aug 17, 2008 at 01:21:52AM +0530, Jai Menon wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> On Sunday 17 Aug 2008 12:42:33 am Jai Menon wrote:
>>>>>>>> Hi,
>>>>>>>>
>>>>>>>> On Sunday 17 Aug 2008 12:36:54 am Jai Menon wrote:
>>>>>>>>> Hi,
>>>>>>>>>
>>>>>>>>> Attached patch allows for order estimation to be varied based on
>>>>>>>>> external parameters.
>>>>>>>> This will allow for order estimation between a specific range or
>>>>>>>> interval, particularly useful for the alac encoder.
>>>>>>> Again, based on Ramiro's advice, a more detailed incremental patchset.
>>>>>> [...]
>>>>>>
>>>>>>> @@ -195,10 +195,20 @@ int ff_lpc_calc_coefs(DSPContext *s,
>>>>>>> i = opt_order-1;
>>>>>>> quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i], &shift[i],
>>>>>>> max_shift, zero_shift); } else {
>>>>>>> + if(omethod == ORDER_METHOD_RANGE) {
>>>>>>> + int i = opt_order = param_list[0];
>>>>>>> + while(i < param_list[1]) {
>>>>>>> + if(ref[i] > ref[opt_order-1])
>>>>>>> + opt_order = i + 1;
>>>>>>> + i++;
>>>>>>> + }
>>>>>>> + quantize_lpc_coefs(lpc[opt_order-1], opt_order, precision,
>>>>>>> coefs[opt_order-1], &shift[opt_order-1], max_shift, zero_shift); +
>>>>>>> } else {
>>>>>>> for(i=0; i<max_order; i++) {
>>>>>>> quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i],
>>>>>>> &shift[i], max_shift, zero_shift); }
>>>>>>> }
>>>>>>> + }
>>>>>>>
>>>>>>> return opt_order;
>>>>>>> }
>>>>>> As the current omethods (If i understand the code correctly) are not
>>>>>> limiting their search range. This is a bug, and it can either be fixed or
>>>>>> left but i will not accept the addition of a new omethod because the
>>>>>> existing ones are buggy.
>>>>>>
>>>>>> Besides max_order is passed as parameter already and we do not need a
>>>>>> opaque parameter list, that is the addition of such list is rejected.
>>>>>>
>>>>> So should I just hardcode the selection among 4th and 6th orders (based on
>>>>> reflection coeffs) in a new order method solely for alac?
>>>> First please explain me again what exactly in lpc_calc_coefs is slowing your
>>>> code down when you use omethod != ORDER_METHOD_EST?
>>>>
>>>> is it quantize_lpc_coefs() ?
>>>>
>>>> if yes (and you really checked this instead of guessing) then
>>>> you can add a min_order and use ORDER_METHOD_2LEVEL with appropriate changes
>>>> to lpc_calc_coefs()
>>>> I just cannot belive that quantize_lpc_coefs() really makes a big difference ...
>>> ORDER_METHOD_EST was tuned for FLAC, so it may not be good for other codecs.
>>>
>>> I think it might be cleaner to share quantize_lpc_coefs() separately.
>>>
>>> ff_lpc_calc_coefs() would do either levinson-durbin or cholesky
>>> depending on avctx->use_lpc, and it would output lpc and reflection
>>> coeffs as doubles.
>>>
>>> ff_lpc_quantize_coefs() could be a function which quantizes coeffs for a
>>> range of orders.
>>>
>>> estimate_best_order() could be shared separately as well if it proves
>>> useful for other codecs.
>>>
>>> This way codecs which just want the coeffs could do their own
>>> quantization or order decision. MP4-ALS, for example, quantizes the
>>> reflection coeffs and has a bit-exact transformation in the spec to
>>> convert to integer lpc coeffs.
>> patch attached implementing the above.
>>
>> Although there is not an "all-in-one" function, I think this is a
>> cleaner and more flexible solution.
>>
>> -Justin
>>
>
>> Index: libavcodec/lpc.c
>> ===================================================================
>> --- libavcodec/lpc.c (revision 14797)
>> +++ libavcodec/lpc.c (working copy)
>> @@ -117,10 +117,13 @@
>> *shift = sh;
>> }
>>
>> -static int estimate_best_order(double *ref, int min_order, int max_order)
>> +int ff_lpc_estimate_best_order(double *ref, int min_order, int max_order)
>> {
>> int i, est;
>>
>
>> + assert(min_order >= MIN_LPC_ORDER && min_order <= MAX_LPC_ORDER);
>> + assert(max_order >= MIN_LPC_ORDER && max_order <= MAX_LPC_ORDER);
>
> assert(min_order <= max_order);
> assert(min_order >= MIN_LPC_ORDER && max_order <= MAX_LPC_ORDER);
yes, that is better.
>> +
>> est = min_order;
>> for(i=max_order-1; i>=min_order-1; i--) {
>> if(ref[i] > 0.10) {
>
>> @@ -134,18 +137,15 @@
>> /**
>> * Calculate LPC coefficients for multiple orders
>> */
>> -int ff_lpc_calc_coefs(DSPContext *s,
>> +void ff_lpc_calc_coefs(DSPContext *s,
>> const int32_t *samples, int blocksize, int min_order,
>> - int max_order, int precision,
>> - int32_t coefs[][MAX_LPC_ORDER], int *shift, int use_lpc,
>> - int omethod, int max_shift, int zero_shift)
>> + int max_order, int use_lpc, double lpc[][MAX_LPC_ORDER],
>> + double ref[MAX_LPC_ORDER])
>> {
>> double autoc[MAX_LPC_ORDER+1];
>> - double ref[MAX_LPC_ORDER];
>> - double lpc[MAX_LPC_ORDER][MAX_LPC_ORDER];
>> int i, j, pass;
>> - int opt_order;
>>
>> + assert(min_order >= MIN_LPC_ORDER && min_order <= MAX_LPC_ORDER);
>> assert(max_order >= MIN_LPC_ORDER && max_order <= MAX_LPC_ORDER);
>>
>> if(use_lpc == 1){
>> @@ -189,17 +189,19 @@
>> for(i=max_order-1; i>0; i--)
>> ref[i] = ref[i-1] - ref[i];
>> }
>> - opt_order = max_order;
>> +}
>
> ok
>
>>
>> - if(omethod == ORDER_METHOD_EST) {
>> - opt_order = estimate_best_order(ref, min_order, max_order);
>> - i = opt_order-1;
>> - quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i], &shift[i], max_shift, zero_shift);
>> - } else {
>
>> +void ff_lpc_quantize_coefs(double lpc[][MAX_LPC_ORDER], int min_order,
>> + int max_order, int precision, int max_shift,
>> + int zero_shift, int32_t coefs[][MAX_LPC_ORDER],
>> + int *shift)
>> +{
>> + int i;
>> +
>> + assert(min_order >= MIN_LPC_ORDER && min_order <= MAX_LPC_ORDER);
>> + assert(max_order >= MIN_LPC_ORDER && max_order <= MAX_LPC_ORDER);
>> +
>> for(i=min_order-1; i<max_order; i++) {
>> quantize_lpc_coefs(lpc[i], i+1, precision, coefs[i], &shift[i], max_shift, zero_shift);
>> }
>> - }
>> -
>> - return opt_order;
>> }
>
> looks like a silly wraper function over a for loop
It is. I can share the function inside the loop instead.
>
>> Index: libavcodec/lpc.h
>> ===================================================================
>> --- libavcodec/lpc.h (revision 14797)
>> +++ libavcodec/lpc.h (working copy)
>> @@ -36,12 +36,50 @@
>>
>>
>> /**
>> - * Calculate LPC coefficients for multiple orders
>> + * Calculate LPC coefficients for multiple orders.
>> + *
>
>> + * @param[in] s DSPContext used for autocorrelation with welch window.
>
> only true for some use_lpc values ...
yes. i'll document that.
>
>> + * @param[in] samples input audio samples for a single channel.
>> + * @param[in] blocksize number of input samples.
>> + * @param[in] min_order lowest LPC order to generate coefficients for.
>> + * @param[in] max_order highest LPC order to generate coefficients for.
>
>> + * @param[in] use_lpc determines which LPC algorithm to use.
>
> it should be a enum (or well documented what is what)
enum {
...
USE_LPC_CHOLESKY_1_PASS
...
USE_LPC_CHOLESKY_2147483646_PASS
}
I'll document it instead... :) Even if we cap the value it doesn't seem
like a good use of enum.
>
>> + * @param[out] lpc LPC coefficients for multiple orders.
>> + * @param[out] ref reflection coefficients up to \p max_order.
>> */
>> -int ff_lpc_calc_coefs(DSPContext *s,
>> +void ff_lpc_calc_coefs(DSPContext *s,
>> const int32_t *samples, int blocksize, int min_order,
>> - int max_order, int precision,
>> - int32_t coefs[][MAX_LPC_ORDER], int *shift, int use_lpc,
>> - int omethod, int max_shift, int zero_shift);
>> + int max_order, int use_lpc, double lpc[][MAX_LPC_ORDER],
>> + double ref[MAX_LPC_ORDER]);
>>
>
>> +/**
>> + * Estimate the best LPC order based on the reflection coefficients.
>> + * This does a reverse iteration through the coeffs and compares against a
>> + * fixed threshold to estimate a good order.
>> + *
>> + * @param ref reflection coefficients from 0 to \p max_order.
>> + * @param min_order lowest LPC order to choose from.
>> + * @param max_order highest LPC order to choose from.
>> + * @return estimated best LPC order.
>> + */
>> +int ff_lpc_estimate_best_order(double *ref, int min_order, int max_order);
>
> why not estimate the bits needed to store LPC coeffs & prediction residual?
If you mean by using the error value during Levinson-Durbin, that is
what the reference FLAC encoder does. I tried it and it doesn't seem to
give as good results (and is slower).
Other than that, estimating the residual bits would be about the same as
actually calculating the residual bits, which is what the other search
methods do. I was going for something better than just using the max
order, but significantly faster than the search methods.
>
>> +
>> +/**
>> + * Quantize the LPC coefficients.
>> + *
>> + * @param[in] lpc floating-point LPC coefficients for multiple orders.
>> + * @param[in] min_order lowest LPC order to quantize.
>> + * @param[in] max_order highest LPC order to quantize.
>> + * @param[in] precision largest number of bits in the quantized coefficients.
>> + * @param[in] max_shift largest left-shift value to apply when quantizing coefficients.
>> + * @param[in] zero_shift value to set \p shift to when all coefficients
>> + * quantize to zero when using \p max_shift.
>> + * @param[out] coefs quantized coefficients for multiple orders.
>> + * @param[out] shift left-shift which was applied to coefficients during quantization.
>> + */
>> +void ff_lpc_quantize_coefs(double lpc[][MAX_LPC_ORDER], int min_order,
>> + int max_order, int precision, int max_shift,
>> + int zero_shift, int32_t coefs[][MAX_LPC_ORDER],
>> + int *shift);
>> +
>
> scalar quantization of LPC coeffs is not good, some more sane variant should
> be tried, like all that are within a small distance from the correct but not
> representable vector.
My goal here was to move and document what we have now. I agree that we
can come up with a better quantization than what we have currently.
That said, I think there should be a choice between whatever we come up
with and the current method unless it is faster or only slightly slower
but much better.
On that topic, I got a suggestion and some code from someone yesterday
which reportedly does better quantized LPC coeff generation. The math
is above my head at first look, so I'll have to go through it for a
while to understand it better. If you want to check it out, I put it here:
http://justin.ruggles.googlepages.com/ilpc-0.10-src.tar.bz2
-Justin
More information about the ffmpeg-devel
mailing list