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