1 /*
2 * Copyright (c) 2013 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 "webrtc/modules/remote_bitrate_estimator/overuse_estimator.h"
12
13 #include <assert.h>
14 #include <math.h>
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include <algorithm>
19
20 #include "webrtc/base/logging.h"
21 #include "webrtc/modules/remote_bitrate_estimator/include/bwe_defines.h"
22
23 namespace webrtc {
24
25 enum { kMinFramePeriodHistoryLength = 60 };
26 enum { kDeltaCounterMax = 1000 };
27
OveruseEstimator(const OverUseDetectorOptions & options)28 OveruseEstimator::OveruseEstimator(const OverUseDetectorOptions& options)
29 : options_(options),
30 num_of_deltas_(0),
31 slope_(options_.initial_slope),
32 offset_(options_.initial_offset),
33 prev_offset_(options_.initial_offset),
34 E_(),
35 process_noise_(),
36 avg_noise_(options_.initial_avg_noise),
37 var_noise_(options_.initial_var_noise),
38 ts_delta_hist_() {
39 memcpy(E_, options_.initial_e, sizeof(E_));
40 memcpy(process_noise_, options_.initial_process_noise,
41 sizeof(process_noise_));
42 }
43
~OveruseEstimator()44 OveruseEstimator::~OveruseEstimator() {
45 ts_delta_hist_.clear();
46 }
47
Update(int64_t t_delta,double ts_delta,int size_delta,BandwidthUsage current_hypothesis)48 void OveruseEstimator::Update(int64_t t_delta,
49 double ts_delta,
50 int size_delta,
51 BandwidthUsage current_hypothesis) {
52 const double min_frame_period = UpdateMinFramePeriod(ts_delta);
53 const double t_ts_delta = t_delta - ts_delta;
54 double fs_delta = size_delta;
55
56 ++num_of_deltas_;
57 if (num_of_deltas_ > kDeltaCounterMax) {
58 num_of_deltas_ = kDeltaCounterMax;
59 }
60
61 // Update the Kalman filter.
62 E_[0][0] += process_noise_[0];
63 E_[1][1] += process_noise_[1];
64
65 if ((current_hypothesis == kBwOverusing && offset_ < prev_offset_) ||
66 (current_hypothesis == kBwUnderusing && offset_ > prev_offset_)) {
67 E_[1][1] += 10 * process_noise_[1];
68 }
69
70 const double h[2] = {fs_delta, 1.0};
71 const double Eh[2] = {E_[0][0]*h[0] + E_[0][1]*h[1],
72 E_[1][0]*h[0] + E_[1][1]*h[1]};
73
74 const double residual = t_ts_delta - slope_*h[0] - offset_;
75
76 const bool in_stable_state = (current_hypothesis == kBwNormal);
77 const double max_residual = 3.0 * sqrt(var_noise_);
78 // We try to filter out very late frames. For instance periodic key
79 // frames doesn't fit the Gaussian model well.
80 if (fabs(residual) < max_residual) {
81 UpdateNoiseEstimate(residual, min_frame_period, in_stable_state);
82 } else {
83 UpdateNoiseEstimate(residual < 0 ? -max_residual : max_residual,
84 min_frame_period, in_stable_state);
85 }
86
87 const double denom = var_noise_ + h[0]*Eh[0] + h[1]*Eh[1];
88
89 const double K[2] = {Eh[0] / denom,
90 Eh[1] / denom};
91
92 const double IKh[2][2] = {{1.0 - K[0]*h[0], -K[0]*h[1]},
93 {-K[1]*h[0], 1.0 - K[1]*h[1]}};
94 const double e00 = E_[0][0];
95 const double e01 = E_[0][1];
96
97 // Update state.
98 E_[0][0] = e00 * IKh[0][0] + E_[1][0] * IKh[0][1];
99 E_[0][1] = e01 * IKh[0][0] + E_[1][1] * IKh[0][1];
100 E_[1][0] = e00 * IKh[1][0] + E_[1][0] * IKh[1][1];
101 E_[1][1] = e01 * IKh[1][0] + E_[1][1] * IKh[1][1];
102
103 // The covariance matrix must be positive semi-definite.
104 bool positive_semi_definite = E_[0][0] + E_[1][1] >= 0 &&
105 E_[0][0] * E_[1][1] - E_[0][1] * E_[1][0] >= 0 && E_[0][0] >= 0;
106 assert(positive_semi_definite);
107 if (!positive_semi_definite) {
108 LOG(LS_ERROR) << "The over-use estimator's covariance matrix is no longer "
109 "semi-definite.";
110 }
111
112 slope_ = slope_ + K[0] * residual;
113 prev_offset_ = offset_;
114 offset_ = offset_ + K[1] * residual;
115 }
116
UpdateMinFramePeriod(double ts_delta)117 double OveruseEstimator::UpdateMinFramePeriod(double ts_delta) {
118 double min_frame_period = ts_delta;
119 if (ts_delta_hist_.size() >= kMinFramePeriodHistoryLength) {
120 ts_delta_hist_.pop_front();
121 }
122 std::list<double>::iterator it = ts_delta_hist_.begin();
123 for (; it != ts_delta_hist_.end(); it++) {
124 min_frame_period = std::min(*it, min_frame_period);
125 }
126 ts_delta_hist_.push_back(ts_delta);
127 return min_frame_period;
128 }
129
UpdateNoiseEstimate(double residual,double ts_delta,bool stable_state)130 void OveruseEstimator::UpdateNoiseEstimate(double residual,
131 double ts_delta,
132 bool stable_state) {
133 if (!stable_state) {
134 return;
135 }
136 // Faster filter during startup to faster adapt to the jitter level
137 // of the network. |alpha| is tuned for 30 frames per second, but is scaled
138 // according to |ts_delta|.
139 double alpha = 0.01;
140 if (num_of_deltas_ > 10*30) {
141 alpha = 0.002;
142 }
143 // Only update the noise estimate if we're not over-using. |beta| is a
144 // function of alpha and the time delta since the previous update.
145 const double beta = pow(1 - alpha, ts_delta * 30.0 / 1000.0);
146 avg_noise_ = beta * avg_noise_
147 + (1 - beta) * residual;
148 var_noise_ = beta * var_noise_
149 + (1 - beta) * (avg_noise_ - residual) * (avg_noise_ - residual);
150 if (var_noise_ < 1) {
151 var_noise_ = 1;
152 }
153 }
154 } // namespace webrtc
155