tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

compute_interpolated_gain_curve.cc (9354B)

      1 /*
      2 *  Copyright (c) 2018 The WebRTC project authors. All Rights Reserved.
      3 *
      4 *  Use of this source code is governed by a BSD-style license
      5 *  that can be found in the LICENSE file in the root of the source
      6 *  tree. An additional intellectual property rights grant can be found
      7 *  in the file PATENTS.  All contributing project authors may
      8 *  be found in the AUTHORS file in the root of the source tree.
      9 */
     10 
     11 #include "modules/audio_processing/agc2/compute_interpolated_gain_curve.h"
     12 
     13 #include <algorithm>
     14 #include <cstddef>
     15 #include <queue>
     16 #include <tuple>
     17 #include <utility>
     18 #include <vector>
     19 
     20 #include "modules/audio_processing/agc2/agc2_common.h"
     21 #include "modules/audio_processing/agc2/agc2_testing_common.h"
     22 #include "modules/audio_processing/agc2/limiter_db_gain_curve.h"
     23 #include "rtc_base/checks.h"
     24 
     25 namespace webrtc {
     26 namespace {
     27 
     28 std::pair<double, double> ComputeLinearApproximationParams(
     29    const LimiterDbGainCurve* limiter,
     30    const double x) {
     31  const double m = limiter->GetGainFirstDerivativeLinear(x);
     32  const double q = limiter->GetGainLinear(x) - m * x;
     33  return {m, q};
     34 }
     35 
     36 double ComputeAreaUnderPiecewiseLinearApproximation(
     37    const LimiterDbGainCurve* limiter,
     38    const double x0,
     39    const double x1) {
     40  RTC_CHECK_LT(x0, x1);
     41 
     42  // Linear approximation in x0 and x1.
     43  double m0, q0, m1, q1;
     44  std::tie(m0, q0) = ComputeLinearApproximationParams(limiter, x0);
     45  std::tie(m1, q1) = ComputeLinearApproximationParams(limiter, x1);
     46 
     47  // Intersection point between two adjacent linear pieces.
     48  RTC_CHECK_NE(m1, m0);
     49  const double x_split = (q0 - q1) / (m1 - m0);
     50  RTC_CHECK_LT(x0, x_split);
     51  RTC_CHECK_LT(x_split, x1);
     52 
     53  auto area_under_linear_piece = [](double x_l, double x_r, double m,
     54                                    double q) {
     55    return x_r * (m * x_r / 2.0 + q) - x_l * (m * x_l / 2.0 + q);
     56  };
     57  return area_under_linear_piece(x0, x_split, m0, q0) +
     58         area_under_linear_piece(x_split, x1, m1, q1);
     59 }
     60 
     61 // Computes the approximation error in the limiter region for a given interval.
     62 // The error is computed as the difference between the areas beneath the limiter
     63 // curve to approximate and its linear under-approximation.
     64 double LimiterUnderApproximationNegativeError(const LimiterDbGainCurve* limiter,
     65                                              const double x0,
     66                                              const double x1) {
     67  const double area_limiter = limiter->GetGainIntegralLinear(x0, x1);
     68  const double area_interpolated_curve =
     69      ComputeAreaUnderPiecewiseLinearApproximation(limiter, x0, x1);
     70  RTC_CHECK_GE(area_limiter, area_interpolated_curve);
     71  return area_limiter - area_interpolated_curve;
     72 }
     73 
     74 // Automatically finds where to sample the beyond-knee region of a limiter using
     75 // a greedy optimization algorithm that iteratively decreases the approximation
     76 // error.
     77 // The solution is sub-optimal because the algorithm is greedy and the points
     78 // are assigned by halving intervals (starting with the whole beyond-knee region
     79 // as a single interval). However, even if sub-optimal, this algorithm works
     80 // well in practice and it is efficiently implemented using priority queues.
     81 std::vector<double> SampleLimiterRegion(const LimiterDbGainCurve* limiter) {
     82  static_assert(kInterpolatedGainCurveBeyondKneePoints > 2, "");
     83 
     84  struct Interval {
     85    Interval() = default;  // Ctor required by std::priority_queue.
     86    Interval(double l, double r, double e) : x0(l), x1(r), error(e) {
     87      RTC_CHECK(x0 < x1);
     88    }
     89    bool operator<(const Interval& other) const { return error < other.error; }
     90 
     91    double x0;
     92    double x1;
     93    double error;
     94  };
     95 
     96  std::priority_queue<Interval, std::vector<Interval>> q;
     97  q.emplace(limiter->limiter_start_linear(), limiter->max_input_level_linear(),
     98            LimiterUnderApproximationNegativeError(
     99                limiter, limiter->limiter_start_linear(),
    100                limiter->max_input_level_linear()));
    101 
    102  // Iteratively find points by halving the interval with greatest error.
    103  while (q.size() < kInterpolatedGainCurveBeyondKneePoints) {
    104    // Get the interval with highest error.
    105    const auto interval = q.top();
    106    q.pop();
    107 
    108    // Split `interval` and enqueue.
    109    double x_split = (interval.x0 + interval.x1) / 2.0;
    110    q.emplace(interval.x0, x_split,
    111              LimiterUnderApproximationNegativeError(limiter, interval.x0,
    112                                                     x_split));  // Left.
    113    q.emplace(x_split, interval.x1,
    114              LimiterUnderApproximationNegativeError(limiter, x_split,
    115                                                     interval.x1));  // Right.
    116  }
    117 
    118  // Copy x1 values and sort them.
    119  RTC_CHECK_EQ(q.size(), kInterpolatedGainCurveBeyondKneePoints);
    120  std::vector<double> samples(kInterpolatedGainCurveBeyondKneePoints);
    121  for (size_t i = 0; i < kInterpolatedGainCurveBeyondKneePoints; ++i) {
    122    const auto interval = q.top();
    123    q.pop();
    124    samples[i] = interval.x1;
    125  }
    126  RTC_CHECK(q.empty());
    127  std::sort(samples.begin(), samples.end());
    128 
    129  return samples;
    130 }
    131 
    132 // Compute the parameters to over-approximate the knee region via linear
    133 // interpolation. Over-approximating is saturation-safe since the knee region is
    134 // convex.
    135 void PrecomputeKneeApproxParams(const LimiterDbGainCurve* limiter,
    136                                test::InterpolatedParameters* parameters) {
    137  static_assert(kInterpolatedGainCurveKneePoints > 2, "");
    138  // Get `kInterpolatedGainCurveKneePoints` - 1 equally spaced points.
    139  const std::vector<double> points = test::LinSpace(
    140      limiter->knee_start_linear(), limiter->limiter_start_linear(),
    141      kInterpolatedGainCurveKneePoints - 1);
    142 
    143  // Set the first two points. The second is computed to help with the beginning
    144  // of the knee region, which has high curvature.
    145  parameters->computed_approximation_params_x[0] = points[0];
    146  parameters->computed_approximation_params_x[1] =
    147      (points[0] + points[1]) / 2.0;
    148  // Copy the remaining points.
    149  std::copy(std::begin(points) + 1, std::end(points),
    150            std::begin(parameters->computed_approximation_params_x) + 2);
    151 
    152  // Compute (m, q) pairs for each linear piece y = mx + q.
    153  for (size_t i = 0; i < kInterpolatedGainCurveKneePoints - 1; ++i) {
    154    const double x0 = parameters->computed_approximation_params_x[i];
    155    const double x1 = parameters->computed_approximation_params_x[i + 1];
    156    const double y0 = limiter->GetGainLinear(x0);
    157    const double y1 = limiter->GetGainLinear(x1);
    158    RTC_CHECK_NE(x1, x0);
    159    parameters->computed_approximation_params_m[i] = (y1 - y0) / (x1 - x0);
    160    parameters->computed_approximation_params_q[i] =
    161        y0 - parameters->computed_approximation_params_m[i] * x0;
    162  }
    163 }
    164 
    165 // Compute the parameters to under-approximate the beyond-knee region via linear
    166 // interpolation and greedy sampling. Under-approximating is saturation-safe
    167 // since the beyond-knee region is concave.
    168 void PrecomputeBeyondKneeApproxParams(
    169    const LimiterDbGainCurve* limiter,
    170    test::InterpolatedParameters* parameters) {
    171  // Find points on which the linear pieces are tangent to the gain curve.
    172  const auto samples = SampleLimiterRegion(limiter);
    173 
    174  // Parametrize each linear piece.
    175  double m, q;
    176  std::tie(m, q) = ComputeLinearApproximationParams(
    177      limiter,
    178      parameters
    179          ->computed_approximation_params_x[kInterpolatedGainCurveKneePoints -
    180                                            1]);
    181  parameters
    182      ->computed_approximation_params_m[kInterpolatedGainCurveKneePoints - 1] =
    183      m;
    184  parameters
    185      ->computed_approximation_params_q[kInterpolatedGainCurveKneePoints - 1] =
    186      q;
    187  for (size_t i = 0; i < samples.size(); ++i) {
    188    std::tie(m, q) = ComputeLinearApproximationParams(limiter, samples[i]);
    189    parameters
    190        ->computed_approximation_params_m[i +
    191                                          kInterpolatedGainCurveKneePoints] = m;
    192    parameters
    193        ->computed_approximation_params_q[i +
    194                                          kInterpolatedGainCurveKneePoints] = q;
    195  }
    196 
    197  // Find the point of intersection between adjacent linear pieces. They will be
    198  // used as boundaries between adjacent linear pieces.
    199  for (size_t i = kInterpolatedGainCurveKneePoints;
    200       i < kInterpolatedGainCurveKneePoints +
    201               kInterpolatedGainCurveBeyondKneePoints;
    202       ++i) {
    203    RTC_CHECK_NE(parameters->computed_approximation_params_m[i],
    204                 parameters->computed_approximation_params_m[i - 1]);
    205    parameters->computed_approximation_params_x[i] =
    206        (  // Formula: (q0 - q1) / (m1 - m0).
    207            parameters->computed_approximation_params_q[i - 1] -
    208            parameters->computed_approximation_params_q[i]) /
    209        (parameters->computed_approximation_params_m[i] -
    210         parameters->computed_approximation_params_m[i - 1]);
    211  }
    212 }
    213 
    214 }  // namespace
    215 
    216 namespace test {
    217 
    218 InterpolatedParameters ComputeInterpolatedGainCurveApproximationParams() {
    219  InterpolatedParameters parameters;
    220  LimiterDbGainCurve limiter;
    221  parameters.computed_approximation_params_x.fill(0.0f);
    222  parameters.computed_approximation_params_m.fill(0.0f);
    223  parameters.computed_approximation_params_q.fill(0.0f);
    224  PrecomputeKneeApproxParams(&limiter, &parameters);
    225  PrecomputeBeyondKneeApproxParams(&limiter, &parameters);
    226  return parameters;
    227 }
    228 }  // namespace test
    229 }  // namespace webrtc