blob: d53fad8cf94f5ff5a3970fde430eef8e47f9b4a9 [file] [log] [blame]
// Copyright (c) 2015 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 "media/capture/content/animated_content_sampler.h"
#include <stddef.h>
#include <stdint.h>
#include <algorithm>
namespace media {
namespace {
// 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 kMaxLockInPeriodMicros = 83333; // 12 FPS
// The amount of time over which to fully correct the drift of the rewritten
// frame timestamps from the presentation event timestamps. The lower the
// value, the higher the variance in frame timestamps.
const int kDriftCorrectionMillis = 2000;
} // anonymous namespace
AnimatedContentSampler::AnimatedContentSampler(
base::TimeDelta min_capture_period)
: min_capture_period_(min_capture_period), sampling_state_(NOT_SAMPLING) {
DCHECK_GT(min_capture_period_, base::TimeDelta());
}
AnimatedContentSampler::~AnimatedContentSampler() {
}
void AnimatedContentSampler::SetMinCapturePeriod(base::TimeDelta period) {
DCHECK_GT(period, base::TimeDelta());
min_capture_period_ = period;
}
void AnimatedContentSampler::SetTargetSamplingPeriod(base::TimeDelta period) {
target_sampling_period_ = period;
}
void AnimatedContentSampler::ConsiderPresentationEvent(
const gfx::Rect& damage_rect,
base::TimeTicks event_time) {
// Analyze the current event and recent history to determine whether animating
// content is detected.
AddObservation(damage_rect, event_time);
if (!AnalyzeObservations(event_time, &detected_region_, &detected_period_) ||
detected_period_ <= base::TimeDelta() ||
detected_period_ >
base::TimeDelta::FromMicroseconds(kMaxLockInPeriodMicros)) {
// Animated content not detected.
detected_region_ = gfx::Rect();
detected_period_ = base::TimeDelta();
sampling_state_ = NOT_SAMPLING;
return;
}
// At this point, animation is being detected. Update the sampling period
// since the client may call the accessor method even if the heuristics below
// decide not to sample the current event.
sampling_period_ = ComputeSamplingPeriod(
detected_period_, target_sampling_period_, min_capture_period_);
// If this is the first event causing animating content to be detected,
// transition to the START_SAMPLING state.
if (sampling_state_ == NOT_SAMPLING)
sampling_state_ = START_SAMPLING;
// If the current event does not represent a frame that is part of the
// animation, do not sample.
if (damage_rect != detected_region_) {
if (sampling_state_ == SHOULD_SAMPLE)
sampling_state_ = SHOULD_NOT_SAMPLE;
return;
}
// When starting sampling, determine where to sync-up for sampling and frame
// timestamp rewriting. Otherwise, just add one animation period's worth of
// tokens to the token bucket.
if (sampling_state_ == START_SAMPLING) {
if (event_time - frame_timestamp_ > sampling_period_) {
// The frame timestamp sequence should start with the current event
// time.
frame_timestamp_ = event_time - sampling_period_;
token_bucket_ = sampling_period_;
} else {
// The frame timestamp sequence will continue from the last recorded
// frame timestamp.
token_bucket_ = event_time - frame_timestamp_;
}
// Provide a little extra in the initial token bucket so that minor error in
// the detected period won't prevent a reasonably-timed event from being
// sampled.
token_bucket_ += detected_period_ / 2;
} else {
token_bucket_ += detected_period_;
}
// If the token bucket is full enough, take tokens from it and propose
// sampling. Otherwise, do not sample.
DCHECK_LE(detected_period_, sampling_period_);
if (token_bucket_ >= sampling_period_) {
token_bucket_ -= sampling_period_;
frame_timestamp_ = ComputeNextFrameTimestamp(event_time);
sampling_state_ = SHOULD_SAMPLE;
} else {
sampling_state_ = SHOULD_NOT_SAMPLE;
}
}
bool AnimatedContentSampler::HasProposal() const {
return sampling_state_ != NOT_SAMPLING;
}
bool AnimatedContentSampler::ShouldSample() const {
return sampling_state_ == SHOULD_SAMPLE;
}
void AnimatedContentSampler::RecordSample(base::TimeTicks frame_timestamp) {
if (sampling_state_ == NOT_SAMPLING)
frame_timestamp_ = frame_timestamp;
else if (sampling_state_ == SHOULD_SAMPLE)
sampling_state_ = SHOULD_NOT_SAMPLE;
}
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().event_time > 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().event_time) > threshold)
observations_.pop_front();
}
gfx::Rect AnimatedContentSampler::ElectMajorityDamageRect() const {
// This is an derivative of the Boyer-Moore Majority Vote Algorithm where each
// pixel in a candidate gets one vote, as opposed to each candidate getting
// one vote.
const gfx::Rect* candidate = NULL;
int64_t votes = 0;
for (ObservationFifo::const_iterator i = observations_.begin();
i != observations_.end(); ++i) {
DCHECK_GT(i->damage_rect.size().GetArea(), 0);
if (votes == 0) {
candidate = &(i->damage_rect);
votes = candidate->size().GetArea();
} else if (i->damage_rect == *candidate) {
votes += i->damage_rect.size().GetArea();
} else {
votes -= i->damage_rect.size().GetArea();
if (votes < 0) {
candidate = &(i->damage_rect);
votes = -votes;
}
}
}
return (votes > 0) ? *candidate : gfx::Rect();
}
bool AnimatedContentSampler::AnalyzeObservations(
base::TimeTicks event_time,
gfx::Rect* rect,
base::TimeDelta* period) const {
const gfx::Rect elected_rect = ElectMajorityDamageRect();
if (elected_rect.IsEmpty())
return false; // There is no regular animation present.
// Scan |observations_|, gathering metrics about the ones having a damage Rect
// equivalent to the |elected_rect|. Along the way, break early whenever the
// event times reveal a non-animating period.
int64_t num_pixels_damaged_in_all = 0;
int64_t num_pixels_damaged_in_chosen = 0;
base::TimeDelta sum_frame_durations;
size_t count_frame_durations = 0;
base::TimeTicks first_event_time;
base::TimeTicks last_event_time;
for (ObservationFifo::const_reverse_iterator i = observations_.rbegin();
i != observations_.rend(); ++i) {
const int area = i->damage_rect.size().GetArea();
num_pixels_damaged_in_all += area;
if (i->damage_rect != elected_rect)
continue;
num_pixels_damaged_in_chosen += area;
if (last_event_time.is_null()) {
last_event_time = i->event_time;
if ((event_time - last_event_time) >=
base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
return false; // Content animation has recently ended.
}
} else {
const base::TimeDelta frame_duration = first_event_time - i->event_time;
if (frame_duration >=
base::TimeDelta::FromMilliseconds(kNonAnimatingThresholdMillis)) {
break; // Content not animating before this point.
}
sum_frame_durations += frame_duration;
++count_frame_durations;
}
first_event_time = i->event_time;
}
if ((last_event_time - first_event_time) <
base::TimeDelta::FromMilliseconds(kMinObservationWindowMillis)) {
return false; // Content has not animated for long enough for accuracy.
}
if (num_pixels_damaged_in_chosen <= (num_pixels_damaged_in_all * 2 / 3))
return false; // Animation is not damaging a supermajority of pixels.
*rect = elected_rect;
DCHECK_GT(count_frame_durations, 0u);
*period = sum_frame_durations / count_frame_durations;
return true;
}
base::TimeTicks AnimatedContentSampler::ComputeNextFrameTimestamp(
base::TimeTicks event_time) const {
// The ideal next frame timestamp one sampling period since the last one.
const base::TimeTicks ideal_timestamp = frame_timestamp_ + sampling_period_;
// Account for two main sources of drift: 1) The clock drift of the system
// clock relative to the video hardware, which affects the event times; and
// 2) The small error introduced by this frame timestamp rewriting, as it is
// based on averaging over recent events.
//
// TODO(miu): This is similar to the ClockSmoother in
// media/base/audio_shifter.cc. Consider refactor-and-reuse here.
const base::TimeDelta drift = ideal_timestamp - event_time;
const int64_t correct_over_num_frames =
base::TimeDelta::FromMilliseconds(kDriftCorrectionMillis) /
sampling_period_;
DCHECK_GT(correct_over_num_frames, 0);
return ideal_timestamp - drift / correct_over_num_frames;
}
// static
base::TimeDelta AnimatedContentSampler::ComputeSamplingPeriod(
base::TimeDelta animation_period,
base::TimeDelta target_sampling_period,
base::TimeDelta min_capture_period) {
// If the animation rate is unknown, return the ideal sampling period.
if (animation_period.is_zero()) {
return std::max(target_sampling_period, min_capture_period);
}
// Determine whether subsampling is needed. If so, compute the sampling
// period corresponding to the sampling rate is the closest integer division
// of the animation frame rate to the target sampling rate.
//
// For example, consider a target sampling rate of 30 FPS and an animation
// rate of 42 FPS. Possible sampling rates would be 42/1 = 42, 42/2 = 21,
// 42/3 = 14, and so on. Of these candidates, 21 FPS is closest to 30.
base::TimeDelta sampling_period;
if (animation_period < target_sampling_period) {
const int64_t ratio = target_sampling_period / animation_period;
const double target_fps = 1.0 / target_sampling_period.InSecondsF();
const double animation_fps = 1.0 / animation_period.InSecondsF();
if (std::abs(animation_fps / ratio - target_fps) <
std::abs(animation_fps / (ratio + 1) - target_fps)) {
sampling_period = ratio * animation_period;
} else {
sampling_period = (ratio + 1) * animation_period;
}
} else {
sampling_period = animation_period;
}
return std::max(sampling_period, min_capture_period);
}
} // namespace media