animated_content_sampler.cc 11 KB

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