Home | History | Annotate | Download | only in capture 
      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
    437