content/browser/media/capture/animated_content_sampler.cc

   1 // Copyright (c) 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "content/browser/media/capture/animated_content_sampler.h"
   6
   7 #include <algorithm>
   8
   9 namespace content {
  10
  11 namespace {
  12
  13 // These specify the minimum/maximum amount of recent event history to examine
  14 // to detect animated content.  If the values are too low, there is a greater
  15 // risk of false-positive detections and low accuracy.  If they are too high,
  16 // the the implementation will be slow to lock-in/out, and also will not react
  17 // well to mildly-variable frame rate content (e.g., 25 +/- 1 FPS).
  18 //
  19 // These values were established by experimenting with a wide variety of
  20 // scenarios, including 24/25/30 FPS videos, 60 FPS WebGL demos, and the
  21 // transitions between static and animated content.
  22 const int kMinObservationWindowMillis = 1000;
  23 const int kMaxObservationWindowMillis = 2000;
  24
  25 // The maximum amount of time that can elapse before declaring two subsequent
  26 // events as "not animating."  This is the same value found in
  27 // cc::FrameRateCounter.
  28 const int kNonAnimatingThresholdMillis = 250;  // 4 FPS
  29
  30 // The slowest that content can be animating in order for AnimatedContentSampler
  31 // to lock-in.  This is the threshold at which the "smoothness" problem is no
  32 // longer relevant.
  33 const int kMaxLockInPeriodMicros = 83333;  // 12 FPS
  34
  35 // The amount of time over which to fully correct the drift of the rewritten
  36 // frame timestamps from the presentation event timestamps.  The lower the
  37 // value, the higher the variance in frame timestamps.
  38 const int kDriftCorrectionMillis = 2000;
  39
  40 }  // anonymous namespace
  41
  42 AnimatedContentSampler::AnimatedContentSampler(
  43     base::TimeDelta min_capture_period)
  44     : min_capture_period_(min_capture_period) {}
  45
  46 AnimatedContentSampler::~AnimatedContentSampler() {}
  47
  48 void AnimatedContentSampler::ConsiderPresentationEvent(
  49     const gfx::Rect& damage_rect, base::TimeTicks event_time) {
  50   AddObservation(damage_rect, event_time);
  51
  52   if (AnalyzeObservations(event_time, &detected_region_, &detected_period_) &&
  53       detected_period_ > base::TimeDelta() &&
  54       detected_period_ <=
  55           base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) {
  56     if (damage_rect == detected_region_)
  57       UpdateFrameTimestamp(event_time);
  58     else
  59       frame_timestamp_ = base::TimeTicks();
  60   } else {
  61     detected_region_ = gfx::Rect();
  62     detected_period_ = base::TimeDelta();
  63     frame_timestamp_ = base::TimeTicks();
  64   }
  65 }
  66
  67 bool AnimatedContentSampler::HasProposal() const {
  68   return detected_period_ > base::TimeDelta();
  69 }
  70
  71 bool AnimatedContentSampler::ShouldSample() const {
  72   return !frame_timestamp_.is_null();
  73 }
  74
  75 void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
  76   recorded_frame_timestamp_ =
  77       HasProposal() ? frame_timestamp : base::TimeTicks();
  78   sequence_offset_ = base::TimeDelta();
  79 }
  80
  81 void AnimatedContentSampler::AddObservation(const gfx::Rect& damage_rect,
  82                                             base::TimeTicks event_time) {
  83   if (damage_rect.IsEmpty())
  84     return;  // Useless observation.
  85
  86   // Add the observation to the FIFO queue.
  87   if (!observations_.empty() && observations_.back().event_time > event_time)
  88     return;  // The implementation assumes chronological order.
  89   observations_.push_back(Observation(damage_rect, event_time));
  90
  91   // Prune-out old observations.
  92   const base::TimeDelta threshold =
  93       base::TimeDelta::FromMilliseconds(kMaxObservationWindowMillis);
  94   while ((event_time - observations_.front().event_time) > threshold)
  95     observations_.pop_front();
  96 }
  97
  98 gfx::Rect AnimatedContentSampler::ElectMajorityDamageRect() const {
  99   // This is an derivative of the Boyer-Moore Majority Vote Algorithm where each
 100   // pixel in a candidate gets one vote, as opposed to each candidate getting
 101   // one vote.
 102   const gfx::Rect* candidate = NULL;
 103   int64 votes = 0;
 104   for (ObservationFifo::const_iterator i = observations_.begin();
 105        i != observations_.end(); ++i) {
 106     DCHECK_GT(i->damage_rect.size().GetArea(), 0);
 107     if (votes == 0) {
 108       candidate = &(i->damage_rect);
 109       votes = candidate->size().GetArea();
 110     } else if (i->damage_rect == *candidate) {
 111       votes += i->damage_rect.size().GetArea();
 112     } else {
 113       votes -= i->damage_rect.size().GetArea();
 114       if (votes < 0) {
 115         candidate = &(i->damage_rect);
 116         votes = -votes;
 117       }
 118     }
 119   }
 120   return (votes > 0) ? *candidate : gfx::Rect();
 121 }
 122
 123 bool AnimatedContentSampler::AnalyzeObservations(
 124     base::TimeTicks event_time,
 125     gfx::Rect* rect,
 126     base::TimeDelta* period) const {
 127   const gfx::Rect elected_rect = ElectMajorityDamageRect();
 128   if (elected_rect.IsEmpty())
 129     return false;  // There is no regular animation present.
 130
 131   // Scan |observations_|, gathering metrics about the ones having a damage Rect
 132   // equivalent to the |elected_rect|.  Along the way, break early whenever the
 133   // event times reveal a non-animating period.
 134   int64 num_pixels_damaged_in_all = 0;
 135   int64 num_pixels_damaged_in_chosen = 0;
 136   base::TimeDelta sum_frame_durations;
 137   size_t count_frame_durations = 0;
 138   base::TimeTicks first_event_time;
 139   base::TimeTicks last_event_time;
 140   for (ObservationFifo::const_reverse_iterator i = observations_.rbegin();
 141        i != observations_.rend(); ++i) {
 142     const int area = i->damage_rect.size().GetArea();
 143     num_pixels_damaged_in_all += area;
 144     if (i->damage_rect != elected_rect)
 145       continue;
 146     num_pixels_damaged_in_chosen += area;
 147     if (last_event_time.is_null()) {
 148       last_event_time = i->event_time;
 149       if ((event_time - last_event_time) >=
 150               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 151         return false;  // Content animation has recently ended.
 152       }
 153     } else {
 154       const base::TimeDelta frame_duration = first_event_time - i->event_time;
 155       if (frame_duration >=
 156               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 157         break;  // Content not animating before this point.
 158       }
 159       sum_frame_durations += frame_duration;
 160       ++count_frame_durations;
 161     }
 162     first_event_time = i->event_time;
 163   }
 164
 165   if ((last_event_time - first_event_time) <
 166           base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) {
 167     return false;  // Content has not animated for long enough for accuracy.
 168   }
 169   if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3))
 170     return false;  // Animation is not damaging a supermajority of pixels.
 171
 172   *rect = elected_rect;
 173   DCHECK_GT(count_frame_durations, 0u);
 174   *period = sum_frame_durations / count_frame_durations;
 175   return true;
 176 }
 177
 178 void AnimatedContentSampler::UpdateFrameTimestamp(base::TimeTicks event_time) {
 179   // This is how much time to advance from the last frame timestamp.  Never
 180   // advance by less than |min_capture_period_| because the downstream consumer
 181   // cannot handle the higher frame rate.  If |detected_period_| is less than
 182   // |min_capture_period_|, excess frames should be dropped.
 183   const base::TimeDelta advancement =
 184       std::max(detected_period_, min_capture_period_);
 185
 186   // Compute the |timebase| upon which to determine the |frame_timestamp_|.
 187   // Ideally, this would always equal the timestamp of the last recorded frame
 188   // sampling.  Determine how much drift from the ideal is present, then adjust
 189   // the timebase by a small amount to spread out the entire correction over
 190   // many frame timestamps.
 191   //
 192   // This accounts for two main sources of drift: 1) The clock drift of the
 193   // system clock relative to the video hardware, which affects the event times;
 194   // and 2) The small error introduced by this frame timestamp rewriting, as it
 195   // is based on averaging over recent events.
 196   base::TimeTicks timebase = event_time - sequence_offset_ - advancement;
 197   if (!recorded_frame_timestamp_.is_null()) {
 198     const base::TimeDelta drift = recorded_frame_timestamp_ - timebase;
 199     const int64 correct_over_num_frames =
 200         base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
 201             detected_period_;
 202     DCHECK_GT(correct_over_num_frames, 0);
 203     timebase = recorded_frame_timestamp_ - (drift / correct_over_num_frames);
 204   }
 205
 206   // Compute |frame_timestamp_|.  Whenever |detected_period_| is less than
 207   // |min_capture_period_|, some extra time is "borrowed" to be able to advance
 208   // by the full |min_capture_period_|.  Then, whenever the total amount of
 209   // borrowed time reaches a full |min_capture_period_|, drop a frame.  Note
 210   // that when |detected_period_| is greater or equal to |min_capture_period_|,
 211   // this logic is effectively disabled.
 212   borrowed_time_ += advancement - detected_period_;
 213   if (borrowed_time_ >= min_capture_period_) {
 214     borrowed_time_ -= min_capture_period_;
 215     frame_timestamp_ = base::TimeTicks();
 216   } else {
 217     sequence_offset_ += advancement;
 218     frame_timestamp_ = timebase + sequence_offset_;
 219   }
 220 }
 221
 222 }  // namespace content