"Buttery Smooth" Tab Capture.

content/browser/media/capture/video_capture_oracle.cc

 // Copyright (c) 2013 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/video_capture_oracle.h"
 
+#include <algorithm>
+
 #include "base/debug/trace_event.h"
+#include "base/format_macros.h"
+#include "base/strings/stringprintf.h"
 
 namespace content {
 
 namespace {
 
 // This value controls how many redundant, timer-base captures occur when the
 // content is static. Redundantly capturing the same frame allows iterative
 // quality enhancement, and also allows the buffer to fill in "buffered mode".
 //
 // TODO(nick): Controlling this here is a hack and a layering violation, since
 // it's a strategy specific to the WebRTC consumer, and probably just papers
 // over some frame dropping and quality bugs. It should either be controlled at
 // a higher level, or else redundant frame generation should be pushed down
 // further into the WebRTC encoding stack.
 const int kNumRedundantCapturesOfStaticContent = 200;
 
+// These specify the minimum/maximum amount of recent event history to examine
+// to detect animated content.  If the values are too low, there is a greater
+// risk of false-positive detections and low accuracy.  If they are too high,
+// the the implementation will be slow to lock-in/out, and also will not react
+// well to mildly-variable frame rate content (e.g., 25 +/- 1 FPS).
+//
+// These values were established by experimenting with a wide variety of
+// scenarios, including 24/25/30 FPS videos, 60 FPS WebGL demos, and the
+// transitions between static and animated content.
+const int kMinObservationWindowMillis = 1000;
+const int kMaxObservationWindowMillis = 2000;
+
+// The maximum amount of time that can elapse before declaring two subsequent
+// events as "not animating."  This is the same value found in
+// cc::FrameRateCounter.
+const int kNonAnimatingThresholdMillis = 250;  // 4 FPS
+
+// The slowest that content can be animating in order for AnimatedContentSampler
+// to lock-in.  This is the threshold at which the "smoothness" problem is no
+// longer relevant.
+const int kMaxLockInPeriodMillis = 83333;  // 12 FPS

[ncarter (slow), 2014/07/26 00:57:58]

83333 milliseconds is 83 seconds? What does 12FPS have to do with that?

[miu, 2014/07/28 21:54:13]

Doh!  That should be microseconds.  ;-)

[miu, 2014/07/31 01:25:32]

Done.  I meant microseconds.

+
+// The amount of time over which to fully correct clock drift, when computing

[ncarter (slow), 2014/07/26 00:57:58]

Do you mean http://en.wikipedia.org/wiki/Clock_drift , or are you describing a
different phenomenon? What two time counters are drifting relative to each
other?

[miu, 2014/07/28 21:54:13]

I should update this comment/naming since there are really two things going on:

1. Clock drift: The local video hardware can/will occasionally drift w.r.t. the
system clock (TimeTicks).  My understanding is the vsync timebase/interval will
be updated in RWHV/DelegatedFrameHost to account for this.

2. "Drift" due to frame timestamp rewriting: The frame timestamps are rewritten
based on the detected animation rate.  That's based on an average over the past
1000-2000 ms which, being an estimation, can introduce significant error over
long periods of time.  "error" here refers to the frame timestamps drifting too
far off from the raw event_times from the compositor.  In other words, the logic
is designed to gently push the rewritten frame timestamps towards the
event_times.

[miu, 2014/07/31 01:25:32]

Done.  Documented this with code comments where this constant is used.

+// the timestamp of each successive frame.  The lower the value, the higher the
+// variance in frame timestamps.
+const int kDriftCorrectionMillis = 6000;
+
+// Given the amount of time between frames, compare to the expected amount of
+// time between frames at |frame_rate| and return the fractional difference.
+double FractionFromExpectedFrameRate(base::TimeDelta delta, int frame_rate) {
+  DCHECK_GT(frame_rate, 0);
+  const base::TimeDelta expected_delta =
+      base::TimeDelta::FromSeconds(1) / frame_rate;
+  return (delta - expected_delta).InMillisecondsF() /
+      expected_delta.InMillisecondsF();
+}
+
 }  // anonymous namespace
 
-VideoCaptureOracle::VideoCaptureOracle(base::TimeDelta capture_period,
+VideoCaptureOracle::VideoCaptureOracle(base::TimeDelta min_capture_period,
                                        bool events_are_reliable)
-    : capture_period_(capture_period),
+    : min_capture_period_(min_capture_period),
       frame_number_(0),
-      last_delivered_frame_number_(0),
-      sampler_(capture_period_,
-               events_are_reliable,
-               kNumRedundantCapturesOfStaticContent) {}
+      last_delivered_frame_number_(-1),
+      smoothing_sampler_(min_capture_period_,
+                         events_are_reliable,
+                         kNumRedundantCapturesOfStaticContent),
+      content_sampler_(min_capture_period_) {
+}
+
+VideoCaptureOracle::~VideoCaptureOracle() {}
 
 bool VideoCaptureOracle::ObserveEventAndDecideCapture(
     Event event,
+    const gfx::Rect& damage_rect,
     base::TimeTicks event_time) {
-  // Record |event| and decide whether it's a good time to capture.
-  const bool content_is_dirty = (event == kCompositorUpdate ||
-                                 event == kSoftwarePaint);
+  DCHECK_GE(event, 0);
+  DCHECK_LT(event, kNumEvents);
+  if (event_time < last_event_time_[event]) {
+    LOG(WARNING) << "Event time is not monotonically non-decreasing.  "
+                 << "Deciding not to capture this frame.";
+    return false;
+  }
+  last_event_time_[event] = event_time;
+
   bool should_sample;
-  if (content_is_dirty) {
-    frame_number_++;
-    should_sample = sampler_.AddEventAndConsiderSampling(event_time);
-  } else {
-    should_sample = sampler_.IsOverdueForSamplingAt(event_time);
+  switch (event) {
+    case kCompositorUpdate:
+    case kSoftwarePaint:
+      should_sample =
+          smoothing_sampler_.AddEventAndConsiderSampling(event_time);
+      if (content_sampler_.ConsiderPresentationEvent(damage_rect, event_time)) {

[ncarter (slow), 2014/07/26 00:57:58]

I got confused trying to understand how the two samplers fit together, because
the two Consider functions have pretty different semantics on the return value.

I wonder if the code would be more readable if the content sampler decision
function evaluated to a tri-state enum: DONT_SAMPLE, DO_SAMPLE,
IM_CONFUSED_ASK_SOMEBODY_ELSE?

[miu, 2014/07/31 01:25:32]

I made this clearer by using the same API for both, and I've separated out the
"consider event" from the "should sample" method calls.

+        event_time = content_sampler_.next_frame_timestamp();
+        should_sample = !event_time.is_null();
+      }
+      break;
+    default:
+      should_sample = smoothing_sampler_.IsOverdueForSamplingAt(event_time);
+      break;
   }
+
+  SetFrameTimestamp(frame_number_, event_time);
   return should_sample;
 }
 
 int VideoCaptureOracle::RecordCapture() {
-  sampler_.RecordSample();
-  return frame_number_;
+  smoothing_sampler_.RecordSample();
+  content_sampler_.RecordSample(GetFrameTimestamp(frame_number_));
+  return frame_number_++;
 }
 
 bool VideoCaptureOracle::CompleteCapture(int frame_number,
-                                         base::TimeTicks timestamp) {
-  // Drop frame if previous frame number is higher or we're trying to deliver
-  // a frame with the same timestamp.
-  if (last_delivered_frame_number_ > frame_number ||
-      last_delivered_frame_timestamp_ == timestamp) {
-    LOG(ERROR) << "Frame with same timestamp or out of order delivery. "
-               << "Dropping frame.";
+                                         base::TimeTicks* frame_timestamp) {
+  // Drop frame if previous frame number is higher.
+  if (last_delivered_frame_number_ > frame_number) {
+    LOG(WARNING) << "Out of order frame delivery detected.  Dropping frame ";
     return false;
   }
+  last_delivered_frame_number_ = frame_number;
 
-  if (last_delivered_frame_timestamp_ > timestamp) {
-    // We should not get here unless time was adjusted backwards.
-    LOG(ERROR) << "Frame with past timestamp (" << timestamp.ToInternalValue()
-               << ") was delivered";
+  *frame_timestamp = GetFrameTimestamp(frame_number);
+
+  // If enabled, log a measurement of how this frame timestamp has incremented
+  // in relation to an ideal increment.
+  if (VLOG_IS_ON(2) && frame_number > 0) {
+    const base::TimeDelta delta =
+        *frame_timestamp - GetFrameTimestamp(frame_number - 1);
+    if (content_sampler_.detected_period() > base::TimeDelta()) {
+      const double estimated_frame_rate =
+          1000000.0 / content_sampler_.detected_period().InMicroseconds();
+      const int rounded_frame_rate =
+          static_cast<int>(estimated_frame_rate + 0.5);
+      VLOG(2) << base::StringPrintf(
+          "Captured #%d: delta=%" PRId64 " usec"
+          ", now locked into {%s}, %+0.1f%% slower than %d FPS",
+          frame_number,
+          delta.InMicroseconds(),
+          content_sampler_.detected_region().ToString().c_str(),
+          100.0 * FractionFromExpectedFrameRate(delta, rounded_frame_rate),
+          rounded_frame_rate);
+    } else {
+      VLOG(2) << base::StringPrintf(
+          "Captured #%d: delta=%" PRId64 " usec"
+          ", d/30fps=%+0.1f%%, d/25fps=%+0.1f%%, d/24fps=%+0.1f%%",
+          frame_number,
+          delta.InMicroseconds(),
+          100.0 * FractionFromExpectedFrameRate(delta, 30),
+          100.0 * FractionFromExpectedFrameRate(delta, 25),
+          100.0 * FractionFromExpectedFrameRate(delta, 24));
+    }
   }
 
-  last_delivered_frame_number_ = frame_number;
-  last_delivered_frame_timestamp_ = timestamp;
+  return !frame_timestamp->is_null();
+}
 
-  return true;
+base::TimeTicks VideoCaptureOracle::GetFrameTimestamp(int frame_number) const {
+  DCHECK_LE(frame_number, frame_number_);
+  DCHECK_LT(frame_number_ - frame_number, kMaxFrameTimestamps);
+  return frame_timestamps_[frame_number % kMaxFrameTimestamps];
+}
+
+void VideoCaptureOracle::SetFrameTimestamp(int frame_number,
+                                           base::TimeTicks timestamp) {
+  frame_timestamps_[frame_number % kMaxFrameTimestamps] = timestamp;
 }
 
 SmoothEventSampler::SmoothEventSampler(base::TimeDelta capture_period,
                                        bool events_are_reliable,
                                        int redundant_capture_goal)
     :  events_are_reliable_(events_are_reliable),
        capture_period_(capture_period),
        redundant_capture_goal_(redundant_capture_goal),
        token_bucket_capacity_(capture_period + capture_period / 2),
        overdue_sample_count_(0),
@@ skipping 65 matching lines @@
       return false;  // Not dirty.
     }
   }
 
   if (last_sample_.is_null())
     return true;
 
   // If we're dirty but not yet old, then we've recently gotten updates, so we
   // won't request a sample just yet.
   base::TimeDelta dirty_interval = event_time - last_sample_;
-  if (dirty_interval < capture_period_ * 4)
-    return false;
-  else
-    return true;
+  return dirty_interval >=
+      base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis);
 }
 
 bool SmoothEventSampler::HasUnrecordedEvent() const {
   return !current_event_.is_null() && current_event_ != last_sample_;
 }
 
+AnimatedContentSampler::AnimatedContentSampler(
+    base::TimeDelta min_capture_period)
+    : min_capture_period_(min_capture_period) {}
+
+AnimatedContentSampler::~AnimatedContentSampler() {}
+
+bool AnimatedContentSampler::ConsiderPresentationEvent(
+    const gfx::Rect& damage_rect, base::TimeTicks event_time) {
+  AddObservation(damage_rect, event_time);
+
+  if (AnalyzeObservations(event_time, &detected_region_, &detected_period_) &&
+      detected_period_ > base::TimeDelta() &&
+      detected_period_ <=
+          base::TimeDelta::FromMilliseconds(kMaxLockInPeriodMillis)) {
+    if (damage_rect == detected_region_)
+      UpdateNextFrameTimestamp(event_time);
+    else
+      next_frame_timestamp_ = base::TimeTicks();
+
+    return true;
+  }
+
+  detected_region_ = gfx::Rect();
+  detected_period_ = base::TimeDelta();
+  next_frame_timestamp_ = base::TimeTicks();
+  return false;
+}
+
+void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
+  recorded_frame_timestamp_ = frame_timestamp;
+  sequence_offset_ = base::TimeDelta();
+}
+
+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().second > event_time)
+    return;  // The implementation assumes chronological order.
+  observations_.push_back(Observation(damage_rect, event_time));
+
+  // Prune-out old observations.
+  const base::TimeDelta threshold =
+      base::TimeDelta::FromMilliseconds(kMaxObservationWindowMillis);
+  while ((event_time - observations_.front().second) > threshold)
+    observations_.pop_front();
+}
+
+bool AnimatedContentSampler::AnalyzeObservations(
+    base::TimeTicks event_time,
+    gfx::Rect* rect,
+    base::TimeDelta* period) const {
+  // There must be at least three observations, or else it's possible to divide
+  // by zero at the end of this method, where |*period| is assigned the result.
+  if (observations_.size() < 3)
+    return false;
+
+  // Find the candidate damage Rect that *would* be the majority value, if a
+  // majority value exists.  This is an implementation of the Boyer-Moore
+  // Majority Vote Algorithm.

[ncarter (slow), 2014/07/26 00:57:58]

Why is majority appropriate, rather than plurality value?

When you have 24fps video but 60fps animations (IIRC you'd see this on youtube
content), will we find the video?

[miu, 2014/07/28 21:54:13]

I thought about this for a while, and I'm not sure it makes a huge difference
either way.  In typical cases, the plurality value is very likely to be the same
as the majority.  I'm inclined to use the majority because:

1. Using the majority forces the code to estimate the animation rate with more
data points, improving accuracy.  Likewise, lock-in only happens when there is
more certainty about what we really should be locking in to.

2. It's a lot simpler (both code and run-time complexity) to find a majority
than a plurality.
This is an excellent point.  I thought about this for a while as well, and I
think I should modify the heuristics to be weighted on "number of pixels
changed."  Meaning, for example:

Video: 24 FPS * 720 * 480 = 8.3 million pixels/sec
Spinner: 60 FPS * 96 * 96 = 0.55 million pixels/sec

This also jives with my intuition as well, since our human perception of
smoothness is very much related to how much of the video frames are in motion. 
Think of a spinner running at 24 FPS, which we would perceive as smooth, but a
large 24 FPS video panning over a nature scene like a canyon landscape will look
very flickery.

I'll try out this idea and get back to you...

+  const gfx::Rect* candidate = NULL;
+  size_t count = 0;
+  for (ObservationFifo::const_iterator i = observations_.begin();
+       i != observations_.end(); ++i) {
+    if (count == 0) {
+      candidate = &(i->first);
+      count = 1;
+    } else if (i->first == *candidate) {
+      ++count;
+    } else {
+      --count;
+    }
+  }

[ncarter (slow), 2014/07/26 00:57:58]

This is subtle enough that I would consider:
 - Breaking it into a private static FindMajority function
 - adding a FRIEND_TEST declaration
 - Having a unit test for just the majority detection.

[miu, 2014/07/31 01:25:32]

Done.

+
+  // Accomplish two goals by making a second pass over |observations_|.  First,
+  // confirm that |candidate| in fact points to the majority damage Rect, and
+  // didn't just win the "voting" phase.  Second, sum up the durations between
+  // the frames having the candidate damage Rect, and track the event time of
+  // the first and last of those frames.
+  count = 0;
+  base::TimeDelta sum_frame_durations;
+  base::TimeTicks first_event_time;
+  base::TimeTicks last_event_time;
+  for (ObservationFifo::const_iterator i = observations_.begin();
+       i != observations_.end(); ++i) {
+    if (i->first != *candidate)
+      continue;
+    ++count;
+
+    if (first_event_time.is_null()) {
+      first_event_time = i->second;
+    } else {
+      const base::TimeDelta frame_duration = i->second - last_event_time;
+      if (frame_duration >=
+              base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {

[ncarter (slow), 2014/07/26 00:57:58]

Seems like anytime a bubble appears, the AnimatedContentSampler is going to
faint for a second or two (and fall back to interval based capture). Is that a
little weird? Did you consider, instead of "return false", resetting count to 1
or just excluding the current interval from the tally?

[miu, 2014/07/28 21:54:12]

Good catch.  Yes, we should be locking into the most recent continuous sequence,
rather than requiring all event history to match.  That was my intention here. 
I'll fix this.

[miu, 2014/07/31 01:25:32]

Done.  Fixed this by iterating |observations_| backwards, and breaking from the
loop at the first non-animating interval.

+        return false;  // Content has not animated continuously.
+      }
+      sum_frame_durations += frame_duration;
+    }
+    last_event_time = i->second;
+  }
+
+  if (count <= observations_.size() / 2)

[ncarter (slow), 2014/07/26 00:57:58]

If you're using a 50% threshold here, what happens on an input of exactly two
rect values in strict alternation? Wouldn't the majority alternate hysterically
as the window slides along?

[miu, 2014/07/28 21:54:12]

Yes.  The harm would be in the flip-flopping between which subset of the frames
we lock in to (the estimated animation period would be the same).

The idea I have to make all this pixel-weighted should make such a situation
less likely to occur, but two identically-sized videos playing on the same
screen would still cause the problem.

The simplest solution may be to require, say, a >75% majority.  I'll have to run
some experiments...

[miu, 2014/07/31 01:25:32]

I looked at this all again.  While the resulting |detected_period_| won't change
during the flip-flop, the frame selection will.  Thus, I've imposed a 2/3
majority requirement, which seems to work well.  Also, I added some unit testing
to confirm the desired behavior.

+    return false;  // |candidate| was not a majority value.
+  if ((last_event_time - first_event_time) <
+          base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) {
+    return false;  // Content has not animated for long enough.
+  }
+  if ((event_time - last_event_time) >=
+          base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
+    return false;  // Content animation has recently ended.
+  }
+

[ncarter (slow), 2014/07/26 00:57:58]

Random thought: once a majority is established, you could avoid recomputing the
majority each time by tracking its frequency as items are added to and removed
from the container. Only when the frequency falls below 50% do you need to
retally. Though with list sizes of ~125, I'm pretty sure this isn't necessary.

[miu, 2014/07/28 21:54:12]

At one point, I tried a more "online" algorithm and, as you noted, it was a lot
more code complexity with very little run-time benefit.

+  *rect = *candidate;
+  *period = sum_frame_durations / (count - 1);
+  return true;
+}
+
+void AnimatedContentSampler::UpdateNextFrameTimestamp(
+    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_);
+
+  // Compute the |timebase| upon which to determine the |next_frame_timestamp_|.
+  // Ideally, this would always equal the timestamp of the last recorded frame
+  // sampling, but no clock is perfect.  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.
+  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);
+  }
+
+  // Compute the |next_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_;
+    next_frame_timestamp_ = base::TimeTicks();
+  } else {
+    sequence_offset_ += advancement;
+    next_frame_timestamp_ = timebase + sequence_offset_;
+  }
+}
+
 }  // namespace content