content/browser/media/capture/video_capture_oracle.cc

   1 // Copyright (c) 2013 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/video_capture_oracle.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/debug/trace_event.h"
  10 #include "base/format_macros.h"
  11 #include "base/strings/stringprintf.h"
  12
  13 namespace content {
  14
  15 namespace {
  16
  17 // This value controls how many redundant, timer-base captures occur when the
  18 // content is static. Redundantly capturing the same frame allows iterative
  19 // quality enhancement, and also allows the buffer to fill in "buffered mode".
  20 //
  21 // TODO(nick): Controlling this here is a hack and a layering violation, since
  22 // it's a strategy specific to the WebRTC consumer, and probably just papers
  23 // over some frame dropping and quality bugs. It should either be controlled at
  24 // a higher level, or else redundant frame generation should be pushed down
  25 // further into the WebRTC encoding stack.
  26 const int kNumRedundantCapturesOfStaticContent = 200;
  27
  28 // These specify the minimum/maximum amount of recent event history to examine
  29 // to detect animated content.  If the values are too low, there is a greater
  30 // risk of false-positive detections and low accuracy.  If they are too high,
  31 // the the implementation will be slow to lock-in/out, and also will not react
  32 // well to mildly-variable frame rate content (e.g., 25 +/- 1 FPS).
  33 //
  34 // These values were established by experimenting with a wide variety of
  35 // scenarios, including 24/25/30 FPS videos, 60 FPS WebGL demos, and the
  36 // transitions between static and animated content.
  37 const int kMinObservationWindowMillis = 1000;
  38 const int kMaxObservationWindowMillis = 2000;
  39
  40 // The maximum amount of time that can elapse before declaring two subsequent
  41 // events as "not animating."  This is the same value found in
  42 // cc::FrameRateCounter.
  43 const int kNonAnimatingThresholdMillis = 250;  // 4 FPS
  44
  45 // The slowest that content can be animating in order for AnimatedContentSampler
  46 // to lock-in.  This is the threshold at which the "smoothness" problem is no
  47 // longer relevant.
  48 const int kMaxLockInPeriodMicros = 83333;  // 12 FPS
  49
  50 // The amount of time over which to fully correct the drift of the rewritten
  51 // frame timestamps from the presentation event timestamps.  The lower the
  52 // value, the higher the variance in frame timestamps.
  53 const int kDriftCorrectionMillis = 6000;
  54
  55 // Given the amount of time between frames, compare to the expected amount of
  56 // time between frames at |frame_rate| and return the fractional difference.
  57 double FractionFromExpectedFrameRate(base::TimeDelta delta, int frame_rate) {
  58   DCHECK_GT(frame_rate, 0);
  59   const base::TimeDelta expected_delta =
  60       base::TimeDelta::FromSeconds(1) / frame_rate;
  61   return (delta - expected_delta).InMillisecondsF() /
  62       expected_delta.InMillisecondsF();
  63 }
  64
  65 }  // anonymous namespace
  66
  67 VideoCaptureOracle::VideoCaptureOracle(base::TimeDelta min_capture_period,
  68                                        bool events_are_reliable)
  69     : frame_number_(0),
  70       last_delivered_frame_number_(-1),
  71       smoothing_sampler_(min_capture_period,
  72                          events_are_reliable,
  73                          kNumRedundantCapturesOfStaticContent),
  74       content_sampler_(min_capture_period) {
  75 }
  76
  77 VideoCaptureOracle::~VideoCaptureOracle() {}
  78
  79 bool VideoCaptureOracle::ObserveEventAndDecideCapture(
  80     Event event,
  81     const gfx::Rect& damage_rect,
  82     base::TimeTicks event_time) {
  83   DCHECK_GE(event, 0);
  84   DCHECK_LT(event, kNumEvents);
  85   if (event_time < last_event_time_[event]) {
  86     LOG(WARNING) << "Event time is not monotonically non-decreasing.  "
  87                  << "Deciding not to capture this frame.";
  88     return false;
  89   }
  90   last_event_time_[event] = event_time;
  91
  92   bool should_sample;
  93   switch (event) {
  94     case kCompositorUpdate:
  95     case kSoftwarePaint:
  96       smoothing_sampler_.ConsiderPresentationEvent(event_time);
  97       content_sampler_.ConsiderPresentationEvent(damage_rect, event_time);
  98       if (content_sampler_.HasProposal()) {
  99         should_sample = content_sampler_.ShouldSample();
 100         if (should_sample)
 101           event_time = content_sampler_.frame_timestamp();
 102       } else {
 103         should_sample = smoothing_sampler_.ShouldSample();
 104       }
 105       break;
 106     default:
 107       should_sample = smoothing_sampler_.IsOverdueForSamplingAt(event_time);
 108       break;
 109   }
 110
 111   SetFrameTimestamp(frame_number_, event_time);
 112   return should_sample;
 113 }
 114
 115 int VideoCaptureOracle::RecordCapture() {
 116   smoothing_sampler_.RecordSample();
 117   content_sampler_.RecordSample(GetFrameTimestamp(frame_number_));
 118   return frame_number_++;
 119 }
 120
 121 bool VideoCaptureOracle::CompleteCapture(int frame_number,
 122                                          base::TimeTicks* frame_timestamp) {
 123   // Drop frame if previous frame number is higher.
 124   if (last_delivered_frame_number_ > frame_number) {
 125     LOG(WARNING) << "Out of order frame delivery detected.  Dropping frame.";
 126     return false;
 127   }
 128   last_delivered_frame_number_ = frame_number;
 129
 130   *frame_timestamp = GetFrameTimestamp(frame_number);
 131
 132   // If enabled, log a measurement of how this frame timestamp has incremented
 133   // in relation to an ideal increment.
 134   if (VLOG_IS_ON(2) && frame_number > 0) {
 135     const base::TimeDelta delta =
 136         *frame_timestamp - GetFrameTimestamp(frame_number - 1);
 137     if (content_sampler_.HasProposal()) {
 138       const double estimated_frame_rate =
 139           1000000.0 / content_sampler_.detected_period().InMicroseconds();
 140       const int rounded_frame_rate =
 141           static_cast<int>(estimated_frame_rate + 0.5);
 142       VLOG(2) << base::StringPrintf(
 143           "Captured #%d: delta=%" PRId64 " usec"
 144           ", now locked into {%s}, %+0.1f%% slower than %d FPS",
 145           frame_number,
 146           delta.InMicroseconds(),
 147           content_sampler_.detected_region().ToString().c_str(),
 148           100.0 * FractionFromExpectedFrameRate(delta, rounded_frame_rate),
 149           rounded_frame_rate);
 150     } else {
 151       VLOG(2) << base::StringPrintf(
 152           "Captured #%d: delta=%" PRId64 " usec"
 153           ", d/30fps=%+0.1f%%, d/25fps=%+0.1f%%, d/24fps=%+0.1f%%",
 154           frame_number,
 155           delta.InMicroseconds(),
 156           100.0 * FractionFromExpectedFrameRate(delta, 30),
 157           100.0 * FractionFromExpectedFrameRate(delta, 25),
 158           100.0 * FractionFromExpectedFrameRate(delta, 24));
 159     }
 160   }
 161
 162   return !frame_timestamp->is_null();
 163 }
 164
 165 base::TimeTicks VideoCaptureOracle::GetFrameTimestamp(int frame_number) const {
 166   DCHECK_LE(frame_number, frame_number_);
 167   DCHECK_LT(frame_number_ - frame_number, kMaxFrameTimestamps);
 168   return frame_timestamps_[frame_number % kMaxFrameTimestamps];
 169 }
 170
 171 void VideoCaptureOracle::SetFrameTimestamp(int frame_number,
 172                                            base::TimeTicks timestamp) {
 173   frame_timestamps_[frame_number % kMaxFrameTimestamps] = timestamp;
 174 }
 175
 176 SmoothEventSampler::SmoothEventSampler(base::TimeDelta min_capture_period,
 177                                        bool events_are_reliable,
 178                                        int redundant_capture_goal)
 179     :  events_are_reliable_(events_are_reliable),
 180        min_capture_period_(min_capture_period),
 181        redundant_capture_goal_(redundant_capture_goal),
 182        token_bucket_capacity_(min_capture_period + min_capture_period / 2),
 183        overdue_sample_count_(0),
 184        token_bucket_(token_bucket_capacity_) {
 185   DCHECK_GT(min_capture_period_.InMicroseconds(), 0);
 186 }
 187
 188 void SmoothEventSampler::ConsiderPresentationEvent(base::TimeTicks event_time) {
 189   DCHECK(!event_time.is_null());
 190
 191   // Add tokens to the bucket based on advancement in time.  Then, re-bound the
 192   // number of tokens in the bucket.  Overflow occurs when there is too much
 193   // time between events (a common case), or when RecordSample() is not being
 194   // called often enough (a bug).  On the other hand, if RecordSample() is being
 195   // called too often (e.g., as a reaction to IsOverdueForSamplingAt()), the
 196   // bucket will underflow.
 197   if (!current_event_.is_null()) {
 198     if (current_event_ < event_time) {
 199       token_bucket_ += event_time - current_event_;
 200       if (token_bucket_ > token_bucket_capacity_)
 201         token_bucket_ = token_bucket_capacity_;
 202     }
 203     TRACE_COUNTER1("mirroring",
 204                    "MirroringTokenBucketUsec",
 205                    std::max<int64>(0, token_bucket_.InMicroseconds()));
 206   }
 207   current_event_ = event_time;
 208 }
 209
 210 bool SmoothEventSampler::ShouldSample() const {
 211   return token_bucket_ >= min_capture_period_;
 212 }
 213
 214 void SmoothEventSampler::RecordSample() {
 215   token_bucket_ -= min_capture_period_;
 216   if (token_bucket_ < base::TimeDelta())
 217     token_bucket_ = base::TimeDelta();
 218   TRACE_COUNTER1("mirroring",
 219                  "MirroringTokenBucketUsec",
 220                  std::max<int64>(0, token_bucket_.InMicroseconds()));
 221
 222   if (HasUnrecordedEvent()) {
 223     last_sample_ = current_event_;
 224     overdue_sample_count_ = 0;
 225   } else {
 226     ++overdue_sample_count_;
 227   }
 228 }
 229
 230 bool SmoothEventSampler::IsOverdueForSamplingAt(base::TimeTicks event_time)
 231     const {
 232   DCHECK(!event_time.is_null());
 233
 234   // If we don't get events on compositor updates on this platform, then we
 235   // don't reliably know whether we're dirty.
 236   if (events_are_reliable_) {
 237     if (!HasUnrecordedEvent() &&
 238         overdue_sample_count_ >= redundant_capture_goal_) {
 239       return false;  // Not dirty.
 240     }
 241   }
 242
 243   if (last_sample_.is_null())
 244     return true;
 245
 246   // If we're dirty but not yet old, then we've recently gotten updates, so we
 247   // won't request a sample just yet.
 248   base::TimeDelta dirty_interval = event_time - last_sample_;
 249   return dirty_interval >=
 250       base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis);
 251 }
 252
 253 bool SmoothEventSampler::HasUnrecordedEvent() const {
 254   return !current_event_.is_null() && current_event_ != last_sample_;
 255 }
 256
 257 AnimatedContentSampler::AnimatedContentSampler(
 258     base::TimeDelta min_capture_period)
 259     : min_capture_period_(min_capture_period) {}
 260
 261 AnimatedContentSampler::~AnimatedContentSampler() {}
 262
 263 void AnimatedContentSampler::ConsiderPresentationEvent(
 264     const gfx::Rect& damage_rect, base::TimeTicks event_time) {
 265   AddObservation(damage_rect, event_time);
 266
 267   if (AnalyzeObservations(event_time, &detected_region_, &detected_period_) &&
 268       detected_period_ > base::TimeDelta() &&
 269       detected_period_ <=
 270           base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) {
 271     if (damage_rect == detected_region_)
 272       UpdateFrameTimestamp(event_time);
 273     else
 274       frame_timestamp_ = base::TimeTicks();
 275   } else {
 276     detected_region_ = gfx::Rect();
 277     detected_period_ = base::TimeDelta();
 278     frame_timestamp_ = base::TimeTicks();
 279   }
 280 }
 281
 282 bool AnimatedContentSampler::HasProposal() const {
 283   return detected_period_ > base::TimeDelta();
 284 }
 285
 286 bool AnimatedContentSampler::ShouldSample() const {
 287   return !frame_timestamp_.is_null();
 288 }
 289
 290 void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
 291   recorded_frame_timestamp_ = frame_timestamp;
 292   sequence_offset_ = base::TimeDelta();
 293 }
 294
 295 void AnimatedContentSampler::AddObservation(const gfx::Rect& damage_rect,
 296                                             base::TimeTicks event_time) {
 297   if (damage_rect.IsEmpty())
 298     return;  // Useless observation.
 299
 300   // Add the observation to the FIFO queue.
 301   if (!observations_.empty() && observations_.back().event_time > event_time)
 302     return;  // The implementation assumes chronological order.
 303   observations_.push_back(Observation(damage_rect, event_time));
 304
 305   // Prune-out old observations.
 306   const base::TimeDelta threshold =
 307       base::TimeDelta::FromMilliseconds(kMaxObservationWindowMillis);
 308   while ((event_time - observations_.front().event_time) > threshold)
 309     observations_.pop_front();
 310 }
 311
 312 gfx::Rect AnimatedContentSampler::ElectMajorityDamageRect() const {
 313   // This is an derivative of the Boyer-Moore Majority Vote Algorithm where each
 314   // pixel in a candidate gets one vote, as opposed to each candidate getting
 315   // one vote.
 316   const gfx::Rect* candidate = NULL;
 317   int64 votes = 0;
 318   for (ObservationFifo::const_iterator i = observations_.begin();
 319        i != observations_.end(); ++i) {
 320     DCHECK_GT(i->damage_rect.size().GetArea(), 0);
 321     if (votes == 0) {
 322       candidate = &(i->damage_rect);
 323       votes = candidate->size().GetArea();
 324     } else if (i->damage_rect == *candidate) {
 325       votes += i->damage_rect.size().GetArea();
 326     } else {
 327       votes -= i->damage_rect.size().GetArea();
 328       if (votes < 0) {
 329         candidate = &(i->damage_rect);
 330         votes = -votes;
 331       }
 332     }
 333   }
 334   return (votes > 0) ? *candidate : gfx::Rect();
 335 }
 336
 337 bool AnimatedContentSampler::AnalyzeObservations(
 338     base::TimeTicks event_time,
 339     gfx::Rect* rect,
 340     base::TimeDelta* period) const {
 341   const gfx::Rect elected_rect = ElectMajorityDamageRect();
 342   if (elected_rect.IsEmpty())
 343     return false;  // There is no regular animation present.
 344
 345   // Scan |observations_|, gathering metrics about the ones having a damage Rect
 346   // equivalent to the |elected_rect|.  Along the way, break early whenever the
 347   // event times reveal a non-animating period.
 348   int64 num_pixels_damaged_in_all = 0;
 349   int64 num_pixels_damaged_in_chosen = 0;
 350   base::TimeDelta sum_frame_durations;
 351   size_t count_frame_durations = 0;
 352   base::TimeTicks first_event_time;
 353   base::TimeTicks last_event_time;
 354   for (ObservationFifo::const_reverse_iterator i = observations_.rbegin();
 355        i != observations_.rend(); ++i) {
 356     const int area = i->damage_rect.size().GetArea();
 357     num_pixels_damaged_in_all += area;
 358     if (i->damage_rect != elected_rect)
 359       continue;
 360     num_pixels_damaged_in_chosen += area;
 361     if (last_event_time.is_null()) {
 362       last_event_time = i->event_time;
 363       if ((event_time - last_event_time) >=
 364               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 365         return false;  // Content animation has recently ended.
 366       }
 367     } else {
 368       const base::TimeDelta frame_duration = first_event_time - i->event_time;
 369       if (frame_duration >=
 370               base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
 371         break;  // Content not animating before this point.
 372       }
 373       sum_frame_durations += frame_duration;
 374       ++count_frame_durations;
 375     }
 376     first_event_time = i->event_time;
 377   }
 378
 379   if ((last_event_time - first_event_time) <
 380           base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) {
 381     return false;  // Content has not animated for long enough for accuracy.
 382   }
 383   if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3))
 384     return false;  // Animation is not damaging a supermajority of pixels.
 385
 386   *rect = elected_rect;
 387   DCHECK_GT(count_frame_durations, 0u);
 388   *period = sum_frame_durations / count_frame_durations;
 389   return true;
 390 }
 391
 392 void AnimatedContentSampler::UpdateFrameTimestamp(base::TimeTicks event_time) {
 393   // This is how much time to advance from the last frame timestamp.  Never
 394   // advance by less than |min_capture_period_| because the downstream consumer
 395   // cannot handle the higher frame rate.  If |detected_period_| is less than
 396   // |min_capture_period_|, excess frames should be dropped.
 397   const base::TimeDelta advancement =
 398       std::max(detected_period_, min_capture_period_);
 399
 400   // Compute the |timebase| upon which to determine the |frame_timestamp_|.
 401   // Ideally, this would always equal the timestamp of the last recorded frame
 402   // sampling.  Determine how much drift from the ideal is present, then adjust
 403   // the timebase by a small amount to spread out the entire correction over
 404   // many frame timestamps.
 405   //
 406   // This accounts for two main sources of drift: 1) The clock drift of the
 407   // system clock relative to the video hardware, which affects the event times;
 408   // and 2) The small error introduced by this frame timestamp rewriting, as it
 409   // is based on averaging over recent events.
 410   base::TimeTicks timebase = event_time - sequence_offset_ - advancement;
 411   if (!recorded_frame_timestamp_.is_null()) {
 412     const base::TimeDelta drift = recorded_frame_timestamp_ - timebase;
 413     const int64 correct_over_num_frames =
 414         base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
 415             detected_period_;
 416     DCHECK_GT(correct_over_num_frames, 0);
 417     timebase = recorded_frame_timestamp_ - (drift / correct_over_num_frames);
 418   }
 419
 420   // Compute |frame_timestamp_|.  Whenever |detected_period_| is less than
 421   // |min_capture_period_|, some extra time is "borrowed" to be able to advance
 422   // by the full |min_capture_period_|.  Then, whenever the total amount of
 423   // borrowed time reaches a full |min_capture_period_|, drop a frame.  Note
 424   // that when |detected_period_| is greater or equal to |min_capture_period_|,
 425   // this logic is effectively disabled.
 426   borrowed_time_ += advancement - detected_period_;
 427   if (borrowed_time_ >= min_capture_period_) {
 428     borrowed_time_ -= min_capture_period_;
 429     frame_timestamp_ = base::TimeTicks();
 430   } else {
 431     sequence_offset_ += advancement;
 432     frame_timestamp_ = timebase + sequence_offset_;
 433   }
 434 }
 435
 436 }  // namespace content