Tab Capture: AnimatedContentSampler subsampling and phase fixes in tests

content/browser/media/capture/animated_content_sampler.cc

 // Copyright (c) 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "content/browser/media/capture/animated_content_sampler.h"
 
 #include <algorithm>
 
 namespace content {
 
@@ skipping 23 matching lines @@
 
 // The amount of time over which to fully correct the drift of the rewritten
 // frame timestamps from the presentation event timestamps.  The lower the
 // value, the higher the variance in frame timestamps.
 const int kDriftCorrectionMillis = 2000;
 
 }  // anonymous namespace
 
 AnimatedContentSampler::AnimatedContentSampler(
     base::TimeDelta min_capture_period)
-    : min_capture_period_(min_capture_period) {}
+    : min_capture_period_(min_capture_period),
+      sampling_state_(NOT_SAMPLING) {
+  DCHECK_GT(min_capture_period_, base::TimeDelta());
+}
 
 AnimatedContentSampler::~AnimatedContentSampler() {}
 
+void AnimatedContentSampler::SetTargetSamplingPeriod(base::TimeDelta period) {
+  target_sampling_period_ = period;
+}
+
 void AnimatedContentSampler::ConsiderPresentationEvent(
     const gfx::Rect& damage_rect, base::TimeTicks event_time) {
+  // Analyze the current event and recent history to determine whether animating
+  // content is detected.
   AddObservation(damage_rect, event_time);
-
-  if (AnalyzeObservations(event_time, &detected_region_, &detected_period_) &&
-      detected_period_ > base::TimeDelta() &&
-      detected_period_ <=
+  if (!AnalyzeObservations(event_time, &detected_region_, &detected_period_) ||
+      detected_period_ <= base::TimeDelta() ||
+      detected_period_ >
           base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) {
-    if (damage_rect == detected_region_)
-      UpdateFrameTimestamp(event_time);
-    else
-      frame_timestamp_ = base::TimeTicks();
-  } else {
+    // Animated content not detected.
     detected_region_ = gfx::Rect();
     detected_period_ = base::TimeDelta();
-    frame_timestamp_ = base::TimeTicks();
+    sampling_state_ = NOT_SAMPLING;
+    return;
+  }
+
+  sampling_period_ = ComputeSamplingPeriod(detected_period_,

[hubbe, 2015/05/06 19:53:18]

Do we need to do this here?
Can we do it after the two ifs below?
If not, perhaps add a comment as to why.

[miu, 2015/05/09 20:57:38]

Added a comment explaining this.  It could be moved one, but not two "ifs" down,
but no need to do that.

+                                           target_sampling_period_,
+                                           min_capture_period_);
+
+  // If this is the first event causing animating content to be detected,
+  // transition to the START_SAMPLING state.
+  if (sampling_state_ == NOT_SAMPLING)
+    sampling_state_ = START_SAMPLING;
+
+  // If the current event does not represent a frame that is part of the
+  // animation, do not sample.
+  if (damage_rect != detected_region_) {
+    if (sampling_state_ == SHOULD_SAMPLE)
+      sampling_state_ = SHOULD_NOT_SAMPLE;
+    return;
+  }
+
+  // When starting sampling, determine where to sync-up for sampling and frame
+  // timestamp rewriting.  Otherwise, just add one animation period's worth of
+  // tokens to the token bucket.
+  if (sampling_state_ == START_SAMPLING) {
+    if (event_time - frame_timestamp_ > sampling_period_) {
+      // The frame timestamp sequence should start with the current event
+      // time.
+      frame_timestamp_ = event_time - sampling_period_;
+      token_bucket_ = sampling_period_;
+    } else {
+      // The frame timestamp sequence will continue from the last recorded
+      // frame timestamp.
+      token_bucket_ = event_time - frame_timestamp_;
+    }
+  } else {
+    token_bucket_ += detected_period_;
+  }
+
+  // If the token bucket is full enough, take tokens from it and propose
+  // sampling.  Otherwise, do not sample.
+  DCHECK_LE(detected_period_, sampling_period_);
+  if (token_bucket_ >= sampling_period_) {

[hubbe, 2015/05/06 19:53:18]

Correct me if I'm wrong, but it seems like this token bucket is normally going
to be right on the edge of being full when we get a frame that we want to
sample. That would could lead to instability in the sampling.
It seems like we want to try to make sure that in normal operation, the
token_bucket is more than full when we should sample and less than full when we
shouldn't.

[miu, 2015/05/09 20:57:38]

It doesn't.  Both real-world testing and the unit tests show this isn't a
problem.  The specific cases:

1. Perfect, unchanging |detected_period_|: For all but the first frame, the
token bucket is incremented by one |detected_period_| for each animation event. 
|sampling_period_| has to be an integer multiple of |detection_period_| so the
instability is never realized.  (In other words, instead of a token bucket, we
could have kept a "num_animation_events" counter and just sampled whenever
num_animation_events % N == 0.)

2. Typical case, where |detected_period_| is fuzzy: |detected_period_| will
fluctuate up or down randomly, by up to a few dozen microseconds.  If this
causes us to be short of a tiny amount of tokens for an event we really do want
to sample, then that's just tough: We *will* drop that frame.  However, the
token bucket will now have almost a full sampling period's worth of "buffer
tokens" that hang around, preventing the noise from causing any future frame
drops.

If you're still not convinced, consider:

1. This is exactly the heuristic used by the SmoothEventSampler, and we have
years of evidence that this works well.  ;-)

2. This is a dual of the "borrowed time" scheme the AnimatedContentSampler was
using prior to this change.

[hubbe, 2015/05/12 19:29:03]

I think you're right. I was thinking that the problem would persist after a
frame drop in (2).  I think we can still improve a little bit by initializing
the token bucket to sampling_period_ + animation_period_/2 (or should it be
minus instead of plus?), thus hopefully avoiding having to ever drop any frames
in the (2) case.

[miu, 2015/05/13 00:01:01]

Ah, yes.  I little extra shouldn't hurt and should help prevent any initial
dropping of one frame.  Done.

+    token_bucket_ -= sampling_period_;
+    frame_timestamp_ = ComputeNextFrameTimestamp(event_time);
+    sampling_state_ = SHOULD_SAMPLE;
+  } else {
+    sampling_state_ = SHOULD_NOT_SAMPLE;
   }
 }
 
 bool AnimatedContentSampler::HasProposal() const {
-  return detected_period_ > base::TimeDelta();
+  return sampling_state_ != NOT_SAMPLING;
 }
 
 bool AnimatedContentSampler::ShouldSample() const {
-  return !frame_timestamp_.is_null();
+  return sampling_state_ == SHOULD_SAMPLE;
 }
 
 void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
-  recorded_frame_timestamp_ =
-      HasProposal() ? frame_timestamp : base::TimeTicks();
-  sequence_offset_ = base::TimeDelta();
+  if (sampling_state_ == NOT_SAMPLING)
+    frame_timestamp_ = frame_timestamp;
+  else if (sampling_state_ == SHOULD_SAMPLE)
+    sampling_state_ = SHOULD_NOT_SAMPLE;
 }
 
 void AnimatedContentSampler::AddObservation(const gfx::Rect& damage_rect,
                                             base::TimeTicks event_time) {
   if (damage_rect.IsEmpty())
     return;  // Useless observation.
 
   // Add the observation to the FIFO queue.
   if (!observations_.empty() && observations_.back().event_time > event_time)
     return;  // The implementation assumes chronological order.
@@ skipping 79 matching lines @@
   }
   if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3))
     return false;  // Animation is not damaging a supermajority of pixels.
 
   *rect = elected_rect;
   DCHECK_GT(count_frame_durations, 0u);
   *period = sum_frame_durations / count_frame_durations;
   return true;
 }
 
-void AnimatedContentSampler::UpdateFrameTimestamp(base::TimeTicks event_time) {
-  // This is how much time to advance from the last frame timestamp.  Never
-  // advance by less than |min_capture_period_| because the downstream consumer
-  // cannot handle the higher frame rate.  If |detected_period_| is less than
-  // |min_capture_period_|, excess frames should be dropped.
-  const base::TimeDelta advancement =
-      std::max(detected_period_, min_capture_period_);
+base::TimeTicks AnimatedContentSampler::ComputeNextFrameTimestamp(
+    base::TimeTicks event_time) const {
+  // The ideal next frame timestamp one sampling period since the last one.
+  const base::TimeTicks ideal_timestamp = frame_timestamp_ + sampling_period_;
 
-  // Compute the |timebase| upon which to determine the |frame_timestamp_|.
-  // Ideally, this would always equal the timestamp of the last recorded frame
-  // sampling.  Determine how much drift from the ideal is present, then adjust
-  // the timebase by a small amount to spread out the entire correction over
-  // many frame timestamps.
-  //
-  // This accounts for two main sources of drift: 1) The clock drift of the
-  // system clock relative to the video hardware, which affects the event times;
-  // and 2) The small error introduced by this frame timestamp rewriting, as it
-  // is based on averaging over recent events.
-  base::TimeTicks timebase = event_time - sequence_offset_ - advancement;
-  if (!recorded_frame_timestamp_.is_null()) {
-    const base::TimeDelta drift = recorded_frame_timestamp_ - timebase;
-    const int64 correct_over_num_frames =
-        base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
-            detected_period_;
-    DCHECK_GT(correct_over_num_frames, 0);
-    timebase = recorded_frame_timestamp_ - (drift / correct_over_num_frames);
+  // Account for two main sources of drift: 1) The clock drift of the system
+  // clock relative to the video hardware, which affects the event times; and
+  // 2) The small error introduced by this frame timestamp rewriting, as it is
+  // based on averaging over recent events.
+  const base::TimeDelta drift = ideal_timestamp - event_time;
+  const int64 correct_over_num_frames =
+      base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
+          sampling_period_;
+  DCHECK_GT(correct_over_num_frames, 0);
+
+  return ideal_timestamp - drift / correct_over_num_frames;

[hubbe, 2015/05/06 19:53:18]

Wonder if it would make sense to break out ClockSmoother from
base/media/audio_shifter.cc and use here?

[miu, 2015/05/09 20:57:38]

As discussed face-to-face, I'll consider this for future clean-up work.

[hubbe, 2015/05/12 19:29:03]

Optional: Add a TODO?

[miu, 2015/05/13 00:01:01]

Done.

+}
+
+// static
+base::TimeDelta AnimatedContentSampler::ComputeSamplingPeriod(
+      base::TimeDelta animation_period,
+      base::TimeDelta target_sampling_period,
+      base::TimeDelta min_capture_period) {
+  // If the animation rate is unknown, return the ideal sampling period.
+  if (animation_period == base::TimeDelta()) {
+    return std::max(target_sampling_period, min_capture_period);
   }
 
-  // Compute |frame_timestamp_|.  Whenever |detected_period_| is less than
-  // |min_capture_period_|, some extra time is "borrowed" to be able to advance
-  // by the full |min_capture_period_|.  Then, whenever the total amount of
-  // borrowed time reaches a full |min_capture_period_|, drop a frame.  Note
-  // that when |detected_period_| is greater or equal to |min_capture_period_|,
-  // this logic is effectively disabled.
-  borrowed_time_ += advancement - detected_period_;
-  if (borrowed_time_ >= min_capture_period_) {
-    borrowed_time_ -= min_capture_period_;
-    frame_timestamp_ = base::TimeTicks();
+  // Determine whether subsampling is needed to achieve the target sampling
+  // period.  If so, compute the sampling period such that the sampling rate is
+  // the closest integer multiple of the animation frame rate.
+  base::TimeDelta sampling_period;
+  if (animation_period < target_sampling_period) {
+    const double target_fps = 1.0 / target_sampling_period.InSecondsF();
+    const double animation_fps = 1.0 / animation_period.InSecondsF();
+    const int64 ratio = target_sampling_period / animation_period;
+    if (std::abs(animation_fps / ratio - target_fps) <

[hubbe, 2015/05/06 19:53:18]

I don't think you need this if statement.
I think ratio is already correct. (It kind of looks like you meant to do a
floor() call when you calculated ratio.)

Without the floor call, ratio should already be the correct value and ratio+1 is
not.

[miu, 2015/05/09 20:57:38]

|ratio| is an int64, so there's an implicit floor'ing happening there.  I moved
the statement to the top of this code block to help avoid confusion.
Consider target_fps=30, animation_fps=42.  Then:

  ratio = floor(42/30) = floor(1.4) = 1

and then we find out we want to use ratio+1 because this is false:

  std::abs(42 / 1 - 30) < std::abs(42 / 2 - 30)

In other words, we want to use ratio+1 because a sampling rate of 21 FPS is
closer to the target of 30 than 42.  This is the desired result.

[hubbe, 2015/05/12 19:29:03]

Ok, I'm officially an idiot, now I've read up on float rounding again....

Anywho, you should still be able to remove the if statement by doing:

  ratio = target_sampling_period / animation_period + 0.5;

(or by using round())

[miu, 2015/05/13 00:01:01]

As discussed, our mad algebra and spreadsheet skills determined the existing
solution is the better one.

+            std::abs(animation_fps / (ratio + 1) - target_fps)) {
+      sampling_period = ratio * animation_period;
+    } else {
+      sampling_period = (ratio + 1) * animation_period;
+    }
   } else {
-    sequence_offset_ += advancement;
-    frame_timestamp_ = timebase + sequence_offset_;
+    sampling_period = animation_period;
   }
+  return std::max(sampling_period, min_capture_period);
 }
 
 }  // namespace content