Implement timestamp translation/filter in VideoCapturer.

webrtc/media/base/videocapturer_unittest.cc

 /*
  *  Copyright (c) 2008 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 <stdio.h>
 
 #include <memory>
 #include <vector>
 
 #include "webrtc/base/gunit.h"
 #include "webrtc/base/logging.h"
+#include "webrtc/base/random.h"
 #include "webrtc/base/thread.h"
 #include "webrtc/media/base/fakevideocapturer.h"
 #include "webrtc/media/base/fakevideorenderer.h"
 #include "webrtc/media/base/testutils.h"
 #include "webrtc/media/base/videocapturer.h"
 
 using cricket::FakeVideoCapturer;
 
 namespace {
 
@@ skipping 746 matching lines @@
   capturer_->set_enable_camera_list(true);
   capturer_->ConstrainSupportedFormats(vga_format);
   EXPECT_EQ(2u, capturer_->GetSupportedFormats()->size());
   // To make sure it's not just the camera list being broken, add in VGA and
   // try again. This time, only the VGA format should be there.
   supported_formats.push_back(vga_format);
   capturer_->ResetSupportedFormats(supported_formats);
   ASSERT_EQ(1u, capturer_->GetSupportedFormats()->size());
   EXPECT_EQ(vga_format.height, capturer_->GetSupportedFormats()->at(0).height);
 }
+
+namespace {
+// Computes the difference x_k - mean(x), when x_k is the linear sequence x_k =
+// k, and the "mean" is plain mean for the first |window_size| samples, followed
+// by exponential averaging with weight 1/|window_size| for each new sample.
+// This is needed to predict the effect of camera clock drift on the timestamp
+// translation. See the comment on VideoCapturer::UpdateOffset for more context.
+double MeanTimeDifference(int nsamples, int window_size) {
+  if (nsamples <= window_size) {
+    // Plain averaging.
+    return nsamples / 2.0;
+  } else {
+    // Exponential convergence towards
+    // interval_error * (window_size - 1)
+    double alpha = 1.0 - 1.0 / window_size;
+
+    return ((window_size - 1) -
+            (window_size / 2.0 - 1) * pow(alpha, nsamples - window_size));
+  }
+}
+
+}  // Anonymous namespace
+
+TEST_F(VideoCapturerTest, AttenuateTimestampJitterPosDrift) {
+  const int kWidth = 800;
+  const int kHeight = 400;
+
+  const double rel_freq_error = 0.003;
+  const int64_t epoch = 10000;
+  const int64_t jitter_us = 5000;
+  const int64_t interval_us = 33333;  // 30 FPS
+  const int64_t interval_error_us = interval_us * rel_freq_error;
+  const int window_size = 100;
+  const int nframes = 2 * window_size;

[sprang_webrtc, 2016/06/17 13:10:52]

Think also these should have kConstantVariable formatting.
And preferreably kNumFrames instead of nFrames

[nisse-webrtc, 2016/06/17 13:43:01]

CamelCaseEvenForLocalVariables? Sure, I can do that, even if I find it ugly. No
new patchset at the moment, though.

[sprang_webrtc, 2016/06/17 14:35:38]

Makes it clear which ones are just named constant and which are actual
variables. And I for one like the kConstantValue better than chromes
CONSTANT_VALUE, if I can add some fuel to the flame war :P

[nisse-webrtc, 2016/06/20 11:47:49]

Done.

+
+  const int64_t system_start_us = rtc::TimeMicros();
+  webrtc::Random random(17);
+
+  int64_t prev_translated_time_us = system_start_us;
+
+  for (int i = 0; i < nframes; i++) {
+    // Camera time subject to drift.
+    int64_t camera_time_us = epoch + i * (interval_us + interval_error_us);
+    int64_t system_time_us = system_start_us + i * interval_us;
+    // And system time readings are subject to jitter.
+    int64_t system_measured_us = system_time_us + random.Rand(jitter_us);
+
+    int out_width;
+    int out_height;
+    int crop_width;
+    int crop_height;
+    int crop_x;
+    int crop_y;
+    int64_t translated_time_us;
+
+    EXPECT_TRUE(capturer_->AdaptFrame(kWidth, kHeight,
+                                      camera_time_us, system_measured_us,
+                                      &out_width, &out_height,
+                                      &crop_width, &crop_height,
+                                      &crop_x, &crop_y, &translated_time_us));
+
+    EXPECT_LE(translated_time_us, system_measured_us);
+    EXPECT_GE(translated_time_us, prev_translated_time_us);
+
+    // The relative frequency error contributes to the expected error
+    // by a factor which is the difference between the current time
+    // and the average of earlier sample times.
+    int64_t expected_error_us =
+        jitter_us / 2 +
+        rel_freq_error * interval_us * MeanTimeDifference(i, window_size);
+
+    int64_t bias_us = capturer_->clip_bias_us();
+    EXPECT_GE(bias_us, 0);
+
+    if (i == 0) {
+      EXPECT_EQ(translated_time_us, system_measured_us);
+    } else {
+      EXPECT_NEAR(translated_time_us + bias_us,
+                  system_time_us + expected_error_us,
+                  2.0 * jitter_us / sqrt(std::max(i, window_size)));
+    }
+    // Initially, the bias applied by the capturer depends mainly on
+    // the measurement noise. It is is expected to roughly cancel the
+    // expected error from the clock drift, as this grows. The numbers
+    // for this test were selected after some trial and error.
+    if (i < 10) {
+      EXPECT_LE(bias_us, jitter_us / 2);
+    } else {
+      EXPECT_NEAR(bias_us, expected_error_us, 1500);
+    }
+    prev_translated_time_us = translated_time_us;
+  }
+}
+
+TEST_F(VideoCapturerTest, AttenuateTimestampJitterNegDrift) {

[sprang_webrtc, 2016/06/17 13:10:52]

A lot of code duplication here. Could you extract most of this logic to a helper
class that takes rel_freq_error as a parameter and condition the bias_us checks
on rel_freq_error > 0 (if that is what's going on?)

The you could also easily have test cases for large and small negative and
positive drift, plus a zero drift just for the sake of it. wdyt?

[nisse-webrtc, 2016/06/17 13:43:01]

Makes some sense, I can give it a try.

In general, I'm a lot more tolerant to code duplication in test code than in
other code. E.g, there might be a need to do something special for one
particular test, and that gets more difficult if it's down in some shared
helper. 

[sprang_webrtc, 2016/06/17 14:35:38]

Agree, some code duplication in tests are fine. In this case it's not trivial
code though, and especially if makes it easy to add more test varieties I think
it's worth a refactoring.

[nisse-webrtc, 2016/06/20 11:47:49]

Done.

+  const int kWidth = 800;
+  const int kHeight = 400;
+
+  const double rel_freq_error = -0.003;
+  const int64_t epoch = 10000;
+  const int64_t jitter_us = 5000;
+  const int64_t interval_us = 33333;  // 30 FPS
+  const int64_t interval_error_us = interval_us * rel_freq_error;
+  const int window_size = 100;
+  const int nframes = 2 * window_size;
+
+  const int64_t system_start_us = rtc::TimeMicros();
+  webrtc::Random random(17);
+
+  int64_t prev_translated_time_us = system_start_us;
+
+  for (int i = 0; i < nframes; i++) {
+    // Camera time subject to drift.
+    int64_t camera_time_us = epoch + i * (interval_us + interval_error_us);
+    int64_t system_time_us = system_start_us + i * interval_us;
+    // And system time readings are subject to jitter.
+    int64_t system_measured_us = system_time_us + random.Rand(jitter_us);
+
+    int out_width;
+    int out_height;
+    int crop_width;
+    int crop_height;
+    int crop_x;
+    int crop_y;
+    int64_t translated_time_us;
+
+    EXPECT_TRUE(capturer_->AdaptFrame(kWidth, kHeight,
+                                      camera_time_us, system_measured_us,
+                                      &out_width, &out_height,
+                                      &crop_width, &crop_height,
+                                      &crop_x, &crop_y, &translated_time_us));
+
+    EXPECT_LE(translated_time_us, system_measured_us);
+    EXPECT_GE(translated_time_us, prev_translated_time_us);
+
+    // The relative frequency error contributes to the expected error
+    // by a factor which is the difference between the current time
+    // and the average of earlier sample times.
+    int64_t expected_error_us =
+        jitter_us / 2 +
+        rel_freq_error * interval_us * MeanTimeDifference(i, window_size);
+
+    int64_t bias_us = capturer_->clip_bias_us();
+    EXPECT_GE(bias_us, 0);
+
+    if (i == 0) {
+      EXPECT_EQ(translated_time_us, system_measured_us);
+    } else {
+      EXPECT_NEAR(translated_time_us + bias_us,
+                  system_time_us + expected_error_us,
+                  2.0 * jitter_us / sqrt(std::max(i, window_size)));
+    }
+    EXPECT_LE(bias_us, jitter_us / 2);
+    prev_translated_time_us = translated_time_us;
+  }
+}