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 "media/capture/animated_content_sampler.h"
   6
   7 #include <algorithm>
   8
   9 namespace media {
  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       sampling_state_(NOT_SAMPLING) {
  46   DCHECK_GT(min_capture_period_, base::TimeDelta());
  47 }
  48
  49 AnimatedContentSampler::~AnimatedContentSampler() {}
  50
  51 void AnimatedContentSampler::SetTargetSamplingPeriod(base::TimeDelta period) {
  52   target_sampling_period_ = period;
  53 }
  54
  55 void AnimatedContentSampler::ConsiderPresentationEvent(
  56     const gfx::Rect& damage_rect, base::TimeTicks event_time) {
  57   // Analyze the current event and recent history to determine whether animating
  58   // content is detected.
  59   AddObservation(damage_rect, event_time);
  60   if (!AnalyzeObservations(event_time, &detected_region_, &detected_period_) ||
  61       detected_period_ <= base::TimeDelta() ||
  62       detected_period_ >
  63           base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) {
  64     // Animated content not detected.
  65     detected_region_ = gfx::Rect();
  66     detected_period_ = base::TimeDelta();
  67     sampling_state_ = NOT_SAMPLING;
  68     return;
  69   }
  70
  71   // At this point, animation is being detected.  Update the sampling period
  72   // since the client may call the accessor method even if the heuristics below
  73   // decide not to sample the current event.
  74   sampling_period_ = ComputeSamplingPeriod(detected_period_,
  75                                            target_sampling_period_,
  76                                            min_capture_period_);
  77
  78   // If this is the first event causing animating content to be detected,
  79   // transition to the START_SAMPLING state.
  80   if (sampling_state_ == NOT_SAMPLING)
  81     sampling_state_ = START_SAMPLING;
  82
  83   // If the current event does not represent a frame that is part of the
  84   // animation, do not sample.
  85   if (damage_rect != detected_region_) {
  86     if (sampling_state_ == SHOULD_SAMPLE)
  87       sampling_state_ = SHOULD_NOT_SAMPLE;
  88     return;
  89   }
  90
  91   // When starting sampling, determine where to sync-up for sampling and frame
  92   // timestamp rewriting.  Otherwise, just add one animation period's worth of
  93   // tokens to the token bucket.
  94   if (sampling_state_ == START_SAMPLING) {
  95     if (event_time - frame_timestamp_ > sampling_period_) {
  96       // The frame timestamp sequence should start with the current event
  97       // time.
  98       frame_timestamp_ = event_time - sampling_period_;
  99       token_bucket_ = sampling_period_;
 100     } else {
 101       // The frame timestamp sequence will continue from the last recorded
 102       // frame timestamp.
 103       token_bucket_ = event_time - frame_timestamp_;
 104     }
 105
 106     // Provide a little extra in the initial token bucket so that minor error in
 107     // the detected period won't prevent a reasonably-timed event from being
 108     // sampled.
 109     token_bucket_ += detected_period_ / 2;
 110   } else {
 111     token_bucket_ += detected_period_;
 112   }
 113
 114   // If the token bucket is full enough, take tokens from it and propose
 115   // sampling.  Otherwise, do not sample.
 116   DCHECK_LE(detected_period_, sampling_period_);
 117   if (token_bucket_ >= sampling_period_) {
 118     token_bucket_ -= sampling_period_;
 119     frame_timestamp_ = ComputeNextFrameTimestamp(event_time);
 120     sampling_state_ = SHOULD_SAMPLE;
 121   } else {
 122     sampling_state_ = SHOULD_NOT_SAMPLE;
 123   }
 124 }
 125
 126 bool AnimatedContentSampler::HasProposal() const {
 127   return sampling_state_ != NOT_SAMPLING;
 128 }
 129
 130 bool AnimatedContentSampler::ShouldSample() const {
 131   return sampling_state_ == SHOULD_SAMPLE;
 132 }
 133
 134 void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
 135   if (sampling_state_ == NOT_SAMPLING)
 136     frame_timestamp_ = frame_timestamp;
 137   else if (sampling_state_ == SHOULD_SAMPLE)
 138     sampling_state_ = SHOULD_NOT_SAMPLE;
 139 }
 140
 141 void AnimatedContentSampler::AddObservation(const gfx::Rect& damage_rect,
 142                                             base::TimeTicks event_time) {
 143   if (damage_rect.IsEmpty())
 144     return;  // Useless observation.
 145
 146   // Add the observation to the FIFO queue.
 147   if (!observations_.empty() && observations_.back().event_time > event_time)
 148     return;  // The implementation assumes chronological order.
 149   observations_.push_back(Observation(damage_rect, event_time));
 150
 151   // Prune-out old observations.
 152   const base::TimeDelta threshold =
 153       base::TimeDelta::FromMilliseconds(kMaxObservationWindowMillis);
 154   while ((event_time - observations_.front().event_time) > threshold)
 155     observations_.pop_front();
 156 }
 157
 158 gfx::Rect AnimatedContentSampler::ElectMajorityDamageRect() const {
 159   // This is an derivative of the Boyer-Moore Majority Vote Algorithm where each
 160   // pixel in a candidate gets one vote, as opposed to each candidate getting
 161   // one vote.
 162   const gfx::Rect* candidate = NULL;
 163   int64 votes = 0;
 164   for (ObservationFifo::const_iterator i = observations_.begin();
 165        i != observations_.end(); ++i) {
 166     DCHECK_GT(i->damage_rect.size().GetArea(), 0);
 167     if (votes == 0) {
 168       candidate = &(i->damage_rect);
 169       votes = candidate->size().GetArea();
 170     } else if (i->damage_rect == *candidate) {
 171       votes += i->damage_rect.size().GetArea();
 172     } else {
 173       votes -= i->damage_rect.size().GetArea();
 174       if (votes < 0) {
 175         candidate = &(i->damage_rect);
 176         votes = -votes;
 177       }
 178     }
 179   }
 180   return (votes > 0) ? *candidate : gfx::Rect();
 181 }
 182
 183 bool AnimatedContentSampler::AnalyzeObservations(
 184     base::TimeTicks event_time,
 185     gfx::Rect* rect,
 186     base::TimeDelta* period) const {
 187   const gfx::Rect elected_rect = ElectMajorityDamageRect();
 188   if (elected_rect.IsEmpty())
 189     return false;  // There is no regular animation present.
 190
 191   // Scan |observations_|, gathering metrics about the ones having a damage Rect
 192   // equivalent to the |elected_rect|.  Along the way, break early whenever the
 193   // event times reveal a non-animating period.
 194   int64 num_pixels_damaged_in_all = 0;
 195   int64 num_pixels_damaged_in_chosen = 0;
 196   base::TimeDelta sum_frame_durations;
 197   size_t count_frame_durations = 0;
 198   base::TimeTicks first_event_time;
 199   base::TimeTicks last_event_time;
 200   for (ObservationFifo::const_reverse_iterator i = observations_.rbegin();
 201        i != observations_.rend(); ++i) {
 202     const int area = i->damage_rect.size().GetArea();
 203     num_pixels_damaged_in_all += area;
 204     if (i->damage_rect != elected_rect)
 205       continue;
 206     num_pixels_damaged_in_chosen += area;
 207     if (last_event_time.is_null()) {
 208       last_event_time = i->event_time;
 209       if ((event_time - last_event_time) >=
 210               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 211         return false;  // Content animation has recently ended.
 212       }
 213     } else {
 214       const base::TimeDelta frame_duration = first_event_time - i->event_time;
 215       if (frame_duration >=
 216               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 217         break;  // Content not animating before this point.
 218       }
 219       sum_frame_durations += frame_duration;
 220       ++count_frame_durations;
 221     }
 222     first_event_time = i->event_time;
 223   }
 224
 225   if ((last_event_time - first_event_time) <
 226           base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) {
 227     return false;  // Content has not animated for long enough for accuracy.
 228   }
 229   if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3))
 230     return false;  // Animation is not damaging a supermajority of pixels.
 231
 232   *rect = elected_rect;
 233   DCHECK_GT(count_frame_durations, 0u);
 234   *period = sum_frame_durations / count_frame_durations;
 235   return true;
 236 }
 237
 238 base::TimeTicks AnimatedContentSampler::ComputeNextFrameTimestamp(
 239     base::TimeTicks event_time) const {
 240   // The ideal next frame timestamp one sampling period since the last one.
 241   const base::TimeTicks ideal_timestamp = frame_timestamp_ + sampling_period_;
 242
 243   // Account for two main sources of drift: 1) The clock drift of the system
 244   // clock relative to the video hardware, which affects the event times; and
 245   // 2) The small error introduced by this frame timestamp rewriting, as it is
 246   // based on averaging over recent events.
 247   //
 248   // TODO(miu): This is similar to the ClockSmoother in
 249   // media/base/audio_shifter.cc.  Consider refactor-and-reuse here.
 250   const base::TimeDelta drift = ideal_timestamp - event_time;
 251   const int64 correct_over_num_frames =
 252       base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
 253           sampling_period_;
 254   DCHECK_GT(correct_over_num_frames, 0);
 255
 256   return ideal_timestamp - drift / correct_over_num_frames;
 257 }
 258
 259 // static
 260 base::TimeDelta AnimatedContentSampler::ComputeSamplingPeriod(
 261       base::TimeDelta animation_period,
 262       base::TimeDelta target_sampling_period,
 263       base::TimeDelta min_capture_period) {
 264   // If the animation rate is unknown, return the ideal sampling period.
 265   if (animation_period == base::TimeDelta()) {
 266     return std::max(target_sampling_period, min_capture_period);
 267   }
 268
 269   // Determine whether subsampling is needed.  If so, compute the sampling
 270   // period corresponding to the sampling rate is the closest integer division
 271   // of the animation frame rate to the target sampling rate.
 272   //
 273   // For example, consider a target sampling rate of 30 FPS and an animation
 274   // rate of 42 FPS.  Possible sampling rates would be 42/1 = 42, 42/2 = 21,
 275   // 42/3 = 14, and so on.  Of these candidates, 21 FPS is closest to 30.
 276   base::TimeDelta sampling_period;
 277   if (animation_period < target_sampling_period) {
 278     const int64 ratio = target_sampling_period / animation_period;
 279     const double target_fps = 1.0 / target_sampling_period.InSecondsF();
 280     const double animation_fps = 1.0 / animation_period.InSecondsF();
 281     if (std::abs(animation_fps / ratio - target_fps) <
 282             std::abs(animation_fps / (ratio + 1) - target_fps)) {
 283       sampling_period = ratio * animation_period;
 284     } else {
 285       sampling_period = (ratio + 1) * animation_period;
 286     }
 287   } else {
 288     sampling_period = animation_period;
 289   }
 290   return std::max(sampling_period, min_capture_period);
 291 }
 292
 293 }  // namespace media