diff options
Diffstat (limited to 'webrtc/modules/video_coding/jitter_estimator.cc')
| -rw-r--r-- | webrtc/modules/video_coding/jitter_estimator.cc | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/webrtc/modules/video_coding/jitter_estimator.cc b/webrtc/modules/video_coding/jitter_estimator.cc new file mode 100644 index 0000000000..8270c60e01 --- /dev/null +++ b/webrtc/modules/video_coding/jitter_estimator.cc @@ -0,0 +1,443 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "webrtc/modules/video_coding/jitter_estimator.h" + +#include <assert.h> +#include <math.h> +#include <stdlib.h> +#include <string.h> +#include <string> + +#include "webrtc/modules/video_coding/internal_defines.h" +#include "webrtc/modules/video_coding/rtt_filter.h" +#include "webrtc/system_wrappers/include/clock.h" +#include "webrtc/system_wrappers/include/field_trial.h" + +namespace webrtc { + +enum { kStartupDelaySamples = 30 }; +enum { kFsAccuStartupSamples = 5 }; +enum { kMaxFramerateEstimate = 200 }; + +VCMJitterEstimator::VCMJitterEstimator(const Clock* clock, + int32_t vcmId, + int32_t receiverId) + : _vcmId(vcmId), + _receiverId(receiverId), + _phi(0.97), + _psi(0.9999), + _alphaCountMax(400), + _thetaLow(0.000001), + _nackLimit(3), + _numStdDevDelayOutlier(15), + _numStdDevFrameSizeOutlier(3), + _noiseStdDevs(2.33), // ~Less than 1% chance + // (look up in normal distribution table)... + _noiseStdDevOffset(30.0), // ...of getting 30 ms freezes + _rttFilter(), + fps_counter_(30), // TODO(sprang): Use an estimator with limit based on + // time, rather than number of samples. + low_rate_experiment_(kInit), + clock_(clock) { + Reset(); +} + +VCMJitterEstimator::~VCMJitterEstimator() {} + +VCMJitterEstimator& VCMJitterEstimator::operator=( + const VCMJitterEstimator& rhs) { + if (this != &rhs) { + memcpy(_thetaCov, rhs._thetaCov, sizeof(_thetaCov)); + memcpy(_Qcov, rhs._Qcov, sizeof(_Qcov)); + + _vcmId = rhs._vcmId; + _receiverId = rhs._receiverId; + _avgFrameSize = rhs._avgFrameSize; + _varFrameSize = rhs._varFrameSize; + _maxFrameSize = rhs._maxFrameSize; + _fsSum = rhs._fsSum; + _fsCount = rhs._fsCount; + _lastUpdateT = rhs._lastUpdateT; + _prevEstimate = rhs._prevEstimate; + _prevFrameSize = rhs._prevFrameSize; + _avgNoise = rhs._avgNoise; + _alphaCount = rhs._alphaCount; + _filterJitterEstimate = rhs._filterJitterEstimate; + _startupCount = rhs._startupCount; + _latestNackTimestamp = rhs._latestNackTimestamp; + _nackCount = rhs._nackCount; + _rttFilter = rhs._rttFilter; + } + return *this; +} + +// Resets the JitterEstimate +void VCMJitterEstimator::Reset() { + _theta[0] = 1 / (512e3 / 8); + _theta[1] = 0; + _varNoise = 4.0; + + _thetaCov[0][0] = 1e-4; + _thetaCov[1][1] = 1e2; + _thetaCov[0][1] = _thetaCov[1][0] = 0; + _Qcov[0][0] = 2.5e-10; + _Qcov[1][1] = 1e-10; + _Qcov[0][1] = _Qcov[1][0] = 0; + _avgFrameSize = 500; + _maxFrameSize = 500; + _varFrameSize = 100; + _lastUpdateT = -1; + _prevEstimate = -1.0; + _prevFrameSize = 0; + _avgNoise = 0.0; + _alphaCount = 1; + _filterJitterEstimate = 0.0; + _latestNackTimestamp = 0; + _nackCount = 0; + _fsSum = 0; + _fsCount = 0; + _startupCount = 0; + _rttFilter.Reset(); + fps_counter_.Reset(); +} + +void VCMJitterEstimator::ResetNackCount() { + _nackCount = 0; +} + +// Updates the estimates with the new measurements +void VCMJitterEstimator::UpdateEstimate(int64_t frameDelayMS, + uint32_t frameSizeBytes, + bool incompleteFrame /* = false */) { + if (frameSizeBytes == 0) { + return; + } + int deltaFS = frameSizeBytes - _prevFrameSize; + if (_fsCount < kFsAccuStartupSamples) { + _fsSum += frameSizeBytes; + _fsCount++; + } else if (_fsCount == kFsAccuStartupSamples) { + // Give the frame size filter + _avgFrameSize = static_cast<double>(_fsSum) / static_cast<double>(_fsCount); + _fsCount++; + } + if (!incompleteFrame || frameSizeBytes > _avgFrameSize) { + double avgFrameSize = _phi * _avgFrameSize + (1 - _phi) * frameSizeBytes; + if (frameSizeBytes < _avgFrameSize + 2 * sqrt(_varFrameSize)) { + // Only update the average frame size if this sample wasn't a + // key frame + _avgFrameSize = avgFrameSize; + } + // Update the variance anyway since we want to capture cases where we only + // get + // key frames. + _varFrameSize = VCM_MAX(_phi * _varFrameSize + + (1 - _phi) * (frameSizeBytes - avgFrameSize) * + (frameSizeBytes - avgFrameSize), + 1.0); + } + + // Update max frameSize estimate + _maxFrameSize = + VCM_MAX(_psi * _maxFrameSize, static_cast<double>(frameSizeBytes)); + + if (_prevFrameSize == 0) { + _prevFrameSize = frameSizeBytes; + return; + } + _prevFrameSize = frameSizeBytes; + + // Only update the Kalman filter if the sample is not considered + // an extreme outlier. Even if it is an extreme outlier from a + // delay point of view, if the frame size also is large the + // deviation is probably due to an incorrect line slope. + double deviation = DeviationFromExpectedDelay(frameDelayMS, deltaFS); + + if (fabs(deviation) < _numStdDevDelayOutlier * sqrt(_varNoise) || + frameSizeBytes > + _avgFrameSize + _numStdDevFrameSizeOutlier * sqrt(_varFrameSize)) { + // Update the variance of the deviation from the + // line given by the Kalman filter + EstimateRandomJitter(deviation, incompleteFrame); + // Prevent updating with frames which have been congested by a large + // frame, and therefore arrives almost at the same time as that frame. + // This can occur when we receive a large frame (key frame) which + // has been delayed. The next frame is of normal size (delta frame), + // and thus deltaFS will be << 0. This removes all frame samples + // which arrives after a key frame. + if ((!incompleteFrame || deviation >= 0.0) && + static_cast<double>(deltaFS) > -0.25 * _maxFrameSize) { + // Update the Kalman filter with the new data + KalmanEstimateChannel(frameDelayMS, deltaFS); + } + } else { + int nStdDev = + (deviation >= 0) ? _numStdDevDelayOutlier : -_numStdDevDelayOutlier; + EstimateRandomJitter(nStdDev * sqrt(_varNoise), incompleteFrame); + } + // Post process the total estimated jitter + if (_startupCount >= kStartupDelaySamples) { + PostProcessEstimate(); + } else { + _startupCount++; + } +} + +// Updates the nack/packet ratio +void VCMJitterEstimator::FrameNacked() { + // Wait until _nackLimit retransmissions has been received, + // then always add ~1 RTT delay. + // TODO(holmer): Should we ever remove the additional delay if the + // the packet losses seem to have stopped? We could for instance scale + // the number of RTTs to add with the amount of retransmissions in a given + // time interval, or similar. + if (_nackCount < _nackLimit) { + _nackCount++; + } +} + +// Updates Kalman estimate of the channel +// The caller is expected to sanity check the inputs. +void VCMJitterEstimator::KalmanEstimateChannel(int64_t frameDelayMS, + int32_t deltaFSBytes) { + double Mh[2]; + double hMh_sigma; + double kalmanGain[2]; + double measureRes; + double t00, t01; + + // Kalman filtering + + // Prediction + // M = M + Q + _thetaCov[0][0] += _Qcov[0][0]; + _thetaCov[0][1] += _Qcov[0][1]; + _thetaCov[1][0] += _Qcov[1][0]; + _thetaCov[1][1] += _Qcov[1][1]; + + // Kalman gain + // K = M*h'/(sigma2n + h*M*h') = M*h'/(1 + h*M*h') + // h = [dFS 1] + // Mh = M*h' + // hMh_sigma = h*M*h' + R + Mh[0] = _thetaCov[0][0] * deltaFSBytes + _thetaCov[0][1]; + Mh[1] = _thetaCov[1][0] * deltaFSBytes + _thetaCov[1][1]; + // sigma weights measurements with a small deltaFS as noisy and + // measurements with large deltaFS as good + if (_maxFrameSize < 1.0) { + return; + } + double sigma = (300.0 * exp(-fabs(static_cast<double>(deltaFSBytes)) / + (1e0 * _maxFrameSize)) + + 1) * + sqrt(_varNoise); + if (sigma < 1.0) { + sigma = 1.0; + } + hMh_sigma = deltaFSBytes * Mh[0] + Mh[1] + sigma; + if ((hMh_sigma < 1e-9 && hMh_sigma >= 0) || + (hMh_sigma > -1e-9 && hMh_sigma <= 0)) { + assert(false); + return; + } + kalmanGain[0] = Mh[0] / hMh_sigma; + kalmanGain[1] = Mh[1] / hMh_sigma; + + // Correction + // theta = theta + K*(dT - h*theta) + measureRes = frameDelayMS - (deltaFSBytes * _theta[0] + _theta[1]); + _theta[0] += kalmanGain[0] * measureRes; + _theta[1] += kalmanGain[1] * measureRes; + + if (_theta[0] < _thetaLow) { + _theta[0] = _thetaLow; + } + + // M = (I - K*h)*M + t00 = _thetaCov[0][0]; + t01 = _thetaCov[0][1]; + _thetaCov[0][0] = (1 - kalmanGain[0] * deltaFSBytes) * t00 - + kalmanGain[0] * _thetaCov[1][0]; + _thetaCov[0][1] = (1 - kalmanGain[0] * deltaFSBytes) * t01 - + kalmanGain[0] * _thetaCov[1][1]; + _thetaCov[1][0] = _thetaCov[1][0] * (1 - kalmanGain[1]) - + kalmanGain[1] * deltaFSBytes * t00; + _thetaCov[1][1] = _thetaCov[1][1] * (1 - kalmanGain[1]) - + kalmanGain[1] * deltaFSBytes * t01; + + // Covariance matrix, must be positive semi-definite + assert(_thetaCov[0][0] + _thetaCov[1][1] >= 0 && + _thetaCov[0][0] * _thetaCov[1][1] - + _thetaCov[0][1] * _thetaCov[1][0] >= + 0 && + _thetaCov[0][0] >= 0); +} + +// Calculate difference in delay between a sample and the +// expected delay estimated by the Kalman filter +double VCMJitterEstimator::DeviationFromExpectedDelay( + int64_t frameDelayMS, + int32_t deltaFSBytes) const { + return frameDelayMS - (_theta[0] * deltaFSBytes + _theta[1]); +} + +// Estimates the random jitter by calculating the variance of the +// sample distance from the line given by theta. +void VCMJitterEstimator::EstimateRandomJitter(double d_dT, + bool incompleteFrame) { + uint64_t now = clock_->TimeInMicroseconds(); + if (_lastUpdateT != -1) { + fps_counter_.AddSample(now - _lastUpdateT); + } + _lastUpdateT = now; + + if (_alphaCount == 0) { + assert(false); + return; + } + double alpha = + static_cast<double>(_alphaCount - 1) / static_cast<double>(_alphaCount); + _alphaCount++; + if (_alphaCount > _alphaCountMax) + _alphaCount = _alphaCountMax; + + if (LowRateExperimentEnabled()) { + // In order to avoid a low frame rate stream to react slower to changes, + // scale the alpha weight relative a 30 fps stream. + double fps = GetFrameRate(); + if (fps > 0.0) { + double rate_scale = 30.0 / fps; + // At startup, there can be a lot of noise in the fps estimate. + // Interpolate rate_scale linearly, from 1.0 at sample #1, to 30.0 / fps + // at sample #kStartupDelaySamples. + if (_alphaCount < kStartupDelaySamples) { + rate_scale = + (_alphaCount * rate_scale + (kStartupDelaySamples - _alphaCount)) / + kStartupDelaySamples; + } + alpha = pow(alpha, rate_scale); + } + } + + double avgNoise = alpha * _avgNoise + (1 - alpha) * d_dT; + double varNoise = + alpha * _varNoise + (1 - alpha) * (d_dT - _avgNoise) * (d_dT - _avgNoise); + if (!incompleteFrame || varNoise > _varNoise) { + _avgNoise = avgNoise; + _varNoise = varNoise; + } + if (_varNoise < 1.0) { + // The variance should never be zero, since we might get + // stuck and consider all samples as outliers. + _varNoise = 1.0; + } +} + +double VCMJitterEstimator::NoiseThreshold() const { + double noiseThreshold = _noiseStdDevs * sqrt(_varNoise) - _noiseStdDevOffset; + if (noiseThreshold < 1.0) { + noiseThreshold = 1.0; + } + return noiseThreshold; +} + +// Calculates the current jitter estimate from the filtered estimates +double VCMJitterEstimator::CalculateEstimate() { + double ret = _theta[0] * (_maxFrameSize - _avgFrameSize) + NoiseThreshold(); + + // A very low estimate (or negative) is neglected + if (ret < 1.0) { + if (_prevEstimate <= 0.01) { + ret = 1.0; + } else { + ret = _prevEstimate; + } + } + if (ret > 10000.0) { // Sanity + ret = 10000.0; + } + _prevEstimate = ret; + return ret; +} + +void VCMJitterEstimator::PostProcessEstimate() { + _filterJitterEstimate = CalculateEstimate(); +} + +void VCMJitterEstimator::UpdateRtt(int64_t rttMs) { + _rttFilter.Update(rttMs); +} + +void VCMJitterEstimator::UpdateMaxFrameSize(uint32_t frameSizeBytes) { + if (_maxFrameSize < frameSizeBytes) { + _maxFrameSize = frameSizeBytes; + } +} + +// Returns the current filtered estimate if available, +// otherwise tries to calculate an estimate. +int VCMJitterEstimator::GetJitterEstimate(double rttMultiplier) { + double jitterMS = CalculateEstimate() + OPERATING_SYSTEM_JITTER; + if (_filterJitterEstimate > jitterMS) + jitterMS = _filterJitterEstimate; + if (_nackCount >= _nackLimit) + jitterMS += _rttFilter.RttMs() * rttMultiplier; + + if (LowRateExperimentEnabled()) { + static const double kJitterScaleLowThreshold = 5.0; + static const double kJitterScaleHighThreshold = 10.0; + double fps = GetFrameRate(); + // Ignore jitter for very low fps streams. + if (fps < kJitterScaleLowThreshold) { + if (fps == 0.0) { + return jitterMS; + } + return 0; + } + + // Semi-low frame rate; scale by factor linearly interpolated from 0.0 at + // kJitterScaleLowThreshold to 1.0 at kJitterScaleHighThreshold. + if (fps < kJitterScaleHighThreshold) { + jitterMS = + (1.0 / (kJitterScaleHighThreshold - kJitterScaleLowThreshold)) * + (fps - kJitterScaleLowThreshold) * jitterMS; + } + } + + return static_cast<uint32_t>(jitterMS + 0.5); +} + +bool VCMJitterEstimator::LowRateExperimentEnabled() { + if (low_rate_experiment_ == kInit) { + std::string group = + webrtc::field_trial::FindFullName("WebRTC-ReducedJitterDelay"); + if (group == "Disabled") { + low_rate_experiment_ = kDisabled; + } else { + low_rate_experiment_ = kEnabled; + } + } + return low_rate_experiment_ == kEnabled ? true : false; +} + +double VCMJitterEstimator::GetFrameRate() const { + if (fps_counter_.count() == 0) + return 0; + + double fps = 1000000.0 / fps_counter_.ComputeMean(); + // Sanity check. + assert(fps >= 0.0); + if (fps > kMaxFramerateEstimate) { + fps = kMaxFramerateEstimate; + } + return fps; +} +} // namespace webrtc |