[FFmpeg-devel] [PATCH] Make ff_lpc_calc_coefs order estimation?flexible by passing parameters

[Michael Niedermayer]

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);



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


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


> + * @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)


> + * @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?


> +
> +/**
> + * 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.



>  #endif /* FFMPEG_LPC_H */
> Index: libavcodec/flacenc.c
> ===================================================================
> --- libavcodec/flacenc.c	(revision 14797)
> +++ libavcodec/flacenc.c	(working copy)
> @@ -795,6 +795,8 @@
>      int min_porder, max_porder;
>      FlacFrame *frame;
>      FlacSubframe *sub;
> +    double lpc[MAX_LPC_ORDER][MAX_LPC_ORDER];
> +    double ref[MAX_LPC_ORDER];
>      int32_t coefs[MAX_LPC_ORDER][MAX_LPC_ORDER];
>      int shift[MAX_LPC_ORDER];
>      int32_t *res, *smp;
> @@ -855,10 +857,17 @@
>      }
>  
>      /* LPC */
> -    opt_order = ff_lpc_calc_coefs(&ctx->dsp, smp, n, min_order, max_order,
> -                                  precision, coefs, shift, ctx->options.use_lpc,
> -                                  omethod, MAX_LPC_SHIFT, 0);
> +    ff_lpc_calc_coefs(&ctx->dsp, smp, n, min_order, max_order,
> +                      ctx->options.use_lpc, lpc, ref);
>  
> +    if(omethod == ORDER_METHOD_EST) {
> +        min_order = max_order = ff_lpc_estimate_best_order(ref, min_order, max_order);
> +    }
> +
> +    ff_lpc_quantize_coefs(lpc, min_order, max_order, precision, MAX_LPC_SHIFT,
> +                          0, coefs, shift);
> +
> +    opt_order = max_order;
>      if(omethod == ORDER_METHOD_2LEVEL ||
>         omethod == ORDER_METHOD_4LEVEL ||
>         omethod == ORDER_METHOD_8LEVEL) {

ok

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

Dictatorship naturally arises out of democracy, and the most aggravated
form of tyranny and slavery out of the most extreme liberty. -- Plato
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20080817/474eb62e/attachment.pgp>