video_cadence_estimator.cc 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365
  1. // Copyright 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/filters/video_cadence_estimator.h"
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <iterator>
  8. #include <limits>
  9. #include <numeric>
  10. #include <string>
  11. #include "base/logging.h"
  12. #include "base/metrics/histogram_macros.h"
  13. #include "media/base/media_switches.h"
  14. namespace media {
  15. // To prevent oscillation in and out of cadence or between cadence values, we
  16. // require some time to elapse before a cadence switch is accepted.
  17. const int kMinimumCadenceDurationMs = 100;
  18. // The numbers are used to decide whether the current video is variable FPS or
  19. // constant FPS. If ratio of the sample deviation and the render length is
  20. // above |kVariableFPSFactor|, then it is recognized as a variable FPS, and if
  21. // the ratio is below |kConstantFPSFactor|, then it is recognized as a constant
  22. // FPS, and if the ratio is in between the two factors, then we do not change
  23. // previous recognition.
  24. const double kVariableFPSFactor = 0.55;
  25. const double kConstantFPSFactor = 0.45;
  26. // Records the number of cadence changes to UMA.
  27. static void HistogramCadenceChangeCount(int cadence_changes) {
  28. const int kCadenceChangeMax = 10;
  29. UMA_HISTOGRAM_CUSTOM_COUNTS("Media.VideoRenderer.CadenceChanges",
  30. cadence_changes, 1, kCadenceChangeMax,
  31. kCadenceChangeMax);
  32. }
  33. // Construct a Cadence vector, a vector of integers satisfying the following
  34. // conditions:
  35. // 1. Size is |n|.
  36. // 2. Sum of entries is |k|.
  37. // 3. Each entry is in {|k|/|n|, |k|/|n| + 1}.
  38. // 4. Distribution of |k|/|n| and |k|/|n| + 1 is as even as possible.
  39. VideoCadenceEstimator::Cadence ConstructCadence(int k, int n) {
  40. const int quotient = k / n;
  41. std::vector<int> output(n, 0);
  42. // Fill the vector entries with |quotient| or |quotient + 1|, and make sure
  43. // the two values are distributed as evenly as possible.
  44. int target_accumulate = 0;
  45. int actual_accumulate = 0;
  46. for (int i = 0; i < n; ++i) {
  47. // After each loop
  48. // target_accumulate = (i + 1) * k
  49. // actual_accumulate = \sum_{j = 0}^i {n * V[j]} where V is output vector
  50. // We want to make actual_accumulate as close to target_accumulate as
  51. // possible.
  52. // One exception is that in case k < n, we always want the vector to start
  53. // with 1 to make sure the first frame is always rendered.
  54. // (To avoid float calculation, we use scaled version of accumulated count)
  55. target_accumulate += k;
  56. const int target_current = target_accumulate - actual_accumulate;
  57. if ((i == 0 && k < n) || target_current * 2 >= n * (quotient * 2 + 1)) {
  58. output[i] = quotient + 1;
  59. } else {
  60. output[i] = quotient;
  61. }
  62. actual_accumulate += output[i] * n;
  63. }
  64. return output;
  65. }
  66. VideoCadenceEstimator::VideoCadenceEstimator(
  67. base::TimeDelta minimum_time_until_max_drift)
  68. : cadence_hysteresis_threshold_(
  69. base::Milliseconds(kMinimumCadenceDurationMs)),
  70. minimum_time_until_max_drift_(minimum_time_until_max_drift),
  71. is_variable_frame_rate_(false) {
  72. Reset();
  73. }
  74. VideoCadenceEstimator::~VideoCadenceEstimator() = default;
  75. void VideoCadenceEstimator::Reset() {
  76. cadence_.clear();
  77. pending_cadence_.clear();
  78. cadence_changes_ = render_intervals_cadence_held_ = 0;
  79. first_update_call_ = true;
  80. bm_.use_bresenham_cadence_ =
  81. base::FeatureList::IsEnabled(media::kBresenhamCadence);
  82. bm_.perfect_cadence_.reset();
  83. bm_.frame_index_shift_ = 0;
  84. }
  85. bool VideoCadenceEstimator::UpdateCadenceEstimate(
  86. base::TimeDelta render_interval,
  87. base::TimeDelta frame_duration,
  88. base::TimeDelta frame_duration_deviation,
  89. base::TimeDelta max_acceptable_drift) {
  90. DCHECK_GT(render_interval, base::TimeDelta());
  91. DCHECK_GT(frame_duration, base::TimeDelta());
  92. if (frame_duration_deviation > kVariableFPSFactor * render_interval) {
  93. is_variable_frame_rate_ = true;
  94. } else if (frame_duration_deviation < kConstantFPSFactor * render_interval) {
  95. is_variable_frame_rate_ = false;
  96. }
  97. if (bm_.use_bresenham_cadence_)
  98. return UpdateBresenhamCadenceEstimate(render_interval, frame_duration);
  99. // Variable FPS detected, turn off Cadence by force.
  100. if (is_variable_frame_rate_) {
  101. render_intervals_cadence_held_ = 0;
  102. if (!cadence_.empty()) {
  103. cadence_.clear();
  104. return true;
  105. }
  106. return false;
  107. }
  108. base::TimeDelta time_until_max_drift;
  109. // See if we can find a cadence which fits the data.
  110. Cadence new_cadence =
  111. CalculateCadence(render_interval, frame_duration, max_acceptable_drift,
  112. &time_until_max_drift);
  113. // If this is the first time UpdateCadenceEstimate() has been called,
  114. // initialize the histogram with a zero count for cadence changes; this
  115. // allows us to track the number of playbacks which have cadence at all.
  116. if (first_update_call_) {
  117. DCHECK_EQ(cadence_changes_, 0);
  118. first_update_call_ = false;
  119. HistogramCadenceChangeCount(0);
  120. }
  121. // If nothing changed, do nothing.
  122. if (new_cadence == cadence_) {
  123. // Clear cadence hold to pending values from accumulating incorrectly.
  124. render_intervals_cadence_held_ = 0;
  125. return false;
  126. }
  127. // Wait until enough render intervals have elapsed before accepting the
  128. // cadence change. Prevents oscillation of the cadence selection.
  129. bool update_pending_cadence = true;
  130. if (new_cadence == pending_cadence_ ||
  131. cadence_hysteresis_threshold_ <= render_interval) {
  132. if (++render_intervals_cadence_held_ * render_interval >=
  133. cadence_hysteresis_threshold_) {
  134. DVLOG(1) << "Cadence switch: " << CadenceToString(cadence_) << " -> "
  135. << CadenceToString(new_cadence)
  136. << " :: Time until drift exceeded: " << time_until_max_drift;
  137. cadence_.swap(new_cadence);
  138. // Note: Because this class is transitively owned by a garbage collected
  139. // object, WebMediaPlayer, we log cadence changes as they are encountered.
  140. HistogramCadenceChangeCount(++cadence_changes_);
  141. return true;
  142. }
  143. update_pending_cadence = false;
  144. }
  145. DVLOG(2) << "Hysteresis prevented cadence switch: "
  146. << CadenceToString(cadence_) << " -> "
  147. << CadenceToString(new_cadence);
  148. if (update_pending_cadence) {
  149. pending_cadence_.swap(new_cadence);
  150. render_intervals_cadence_held_ = 1;
  151. }
  152. return false;
  153. }
  154. int VideoCadenceEstimator::GetCadenceForFrame(uint64_t frame_number) const {
  155. DCHECK(has_cadence());
  156. if (bm_.use_bresenham_cadence_) {
  157. double cadence = *bm_.perfect_cadence_;
  158. auto index = frame_number + bm_.frame_index_shift_;
  159. auto result = static_cast<uint64_t>(cadence * (index + 1)) -
  160. static_cast<uint64_t>(cadence * index);
  161. DCHECK(frame_number > 0 || result > 0);
  162. return result;
  163. }
  164. return cadence_[frame_number % cadence_.size()];
  165. }
  166. /* List of tests that are expected to fail when media::kBresenhamCadence
  167. is enabled.
  168. - VideoRendererAlgorithmTest.BestFrameByCadenceOverdisplayedForDrift
  169. Reason: Bresenham cadence does not exhibit innate drift.
  170. - VideoRendererAlgorithmTest.CadenceCalculations
  171. Reason: The test inspects an internal data structures of the current alg.
  172. - VideoRendererAlgorithmTest.VariablePlaybackRateCadence
  173. Reason: The test assumes that cadence algorithm should fail for playback
  174. rate of 3.15. Bresenham alg works fine.
  175. - VideoCadenceEstimatorTest.CadenceCalculationWithLargeDeviation
  176. - VideoCadenceEstimatorTest.CadenceCalculationWithLargeDrift
  177. - VideoCadenceEstimatorTest.CadenceCalculations
  178. - VideoCadenceEstimatorTest.CadenceHystersisPreventsOscillation
  179. - VideoCadenceEstimatorTest.CadenceVariesWithAcceptableDrift
  180. - VideoCadenceEstimatorTest.CadenceVariesWithAcceptableGlitchTime
  181. Reason: These tests inspects an internal data structures of the current
  182. algorithm.
  183. */
  184. bool VideoCadenceEstimator::UpdateBresenhamCadenceEstimate(
  185. base::TimeDelta render_interval,
  186. base::TimeDelta frame_duration) {
  187. if (is_variable_frame_rate_) {
  188. if (bm_.perfect_cadence_.has_value()) {
  189. bm_.perfect_cadence_.reset();
  190. return true;
  191. }
  192. return false;
  193. }
  194. if (++render_intervals_cadence_held_ * render_interval <
  195. cadence_hysteresis_threshold_) {
  196. return false;
  197. }
  198. double current_cadence = bm_.perfect_cadence_.value_or(0.0);
  199. double new_cadence = frame_duration / render_interval;
  200. DCHECK_GE(new_cadence, 0.0);
  201. double cadence_relative_diff = std::abs(current_cadence - new_cadence) /
  202. std::max(current_cadence, new_cadence);
  203. // Ignore small changes in cadence, as they are most likely just noise,
  204. // caused by render_interval flickering on devices having difficulty to decode
  205. // and render the video in real time.
  206. // TODO(ezemtsov): Consider calculating and using avg. render_interval,
  207. // the same way avg. frame duration is used now.
  208. constexpr double kCadenceRoundingError = 0.008;
  209. if (cadence_relative_diff <= kCadenceRoundingError)
  210. return false;
  211. bm_.perfect_cadence_ = new_cadence;
  212. if (render_interval > frame_duration) {
  213. // When display refresh rate is lower than the video frame rate,
  214. // not all frames can be shown. But we want to make sure that the very
  215. // first frame is shown. That's why frame indexes are shifted by this
  216. // much to make sure that the cadence sequence always has 1 in the
  217. // beginning.
  218. bm_.frame_index_shift_ = (render_interval.InMicroseconds() - 1) /
  219. frame_duration.InMicroseconds();
  220. } else {
  221. // It can be 0 (or anything), but it makes the output look more like
  222. // an output of the current cadence algorithm.
  223. bm_.frame_index_shift_ = 1;
  224. }
  225. DVLOG(1) << "Cadence switch"
  226. << " perfect_cadence: " << new_cadence
  227. << " frame_index_shift: " << bm_.frame_index_shift_
  228. << " cadence_relative_diff: " << cadence_relative_diff
  229. << " cadence_held: " << render_intervals_cadence_held_;
  230. render_intervals_cadence_held_ = 0;
  231. return true;
  232. }
  233. VideoCadenceEstimator::Cadence VideoCadenceEstimator::CalculateCadence(
  234. base::TimeDelta render_interval,
  235. base::TimeDelta frame_duration,
  236. base::TimeDelta max_acceptable_drift,
  237. base::TimeDelta* time_until_max_drift) const {
  238. // The perfect cadence is the number of render intervals per frame.
  239. const double perfect_cadence = frame_duration / render_interval;
  240. // This case is very simple, just return a single frame cadence, because it
  241. // is impossible for us to accumulate drift as large as max_acceptable_drift
  242. // within minimum_time_until_max_drift.
  243. if (max_acceptable_drift >= minimum_time_until_max_drift_) {
  244. int cadence_value = round(perfect_cadence);
  245. if (cadence_value < 0)
  246. return Cadence();
  247. if (cadence_value == 0)
  248. cadence_value = 1;
  249. Cadence result = ConstructCadence(cadence_value, 1);
  250. const double error = std::fabs(1.0 - perfect_cadence / cadence_value);
  251. *time_until_max_drift = max_acceptable_drift / error;
  252. return result;
  253. }
  254. // We want to construct a cadence pattern to approximate the perfect cadence
  255. // while ensuring error doesn't accumulate too quickly.
  256. const double drift_ratio =
  257. max_acceptable_drift / minimum_time_until_max_drift_;
  258. const double minimum_acceptable_cadence =
  259. perfect_cadence / (1.0 + drift_ratio);
  260. const double maximum_acceptable_cadence =
  261. perfect_cadence / (1.0 - drift_ratio);
  262. // We've arbitrarily chosen the maximum allowable cadence length as 5. It's
  263. // proven sufficient to support most standard frame and render rates, while
  264. // being small enough that small frame and render timing errors don't render
  265. // it useless.
  266. const int kMaxCadenceSize = 5;
  267. double best_error = 0;
  268. int best_n = 0;
  269. int best_k = 0;
  270. for (int n = 1; n <= kMaxCadenceSize; ++n) {
  271. // A cadence pattern only exists if there exists an integer K such that K/N
  272. // is between |minimum_acceptable_cadence| and |maximum_acceptable_cadence|.
  273. // The best pattern is the one with the smallest error over time relative to
  274. // the |perfect_cadence|.
  275. if (std::floor(minimum_acceptable_cadence * n) <
  276. std::floor(maximum_acceptable_cadence * n)) {
  277. const int k = round(perfect_cadence * n);
  278. const double error = std::fabs(1.0 - perfect_cadence * n / k);
  279. // Prefer the shorter cadence pattern unless a longer one "significantly"
  280. // reduces the error.
  281. if (!best_n || error < best_error * 0.99) {
  282. best_error = error;
  283. best_k = k;
  284. best_n = n;
  285. }
  286. }
  287. }
  288. if (!best_n) return Cadence();
  289. // If we've found a solution.
  290. Cadence best_result = ConstructCadence(best_k, best_n);
  291. *time_until_max_drift = max_acceptable_drift / best_error;
  292. return best_result;
  293. }
  294. std::string VideoCadenceEstimator::CadenceToString(
  295. const Cadence& cadence) const {
  296. if (cadence.empty())
  297. return std::string("[]");
  298. std::ostringstream os;
  299. os << "[";
  300. std::copy(cadence.begin(), cadence.end() - 1,
  301. std::ostream_iterator<int>(os, ":"));
  302. os << cadence.back() << "]";
  303. return os.str();
  304. }
  305. double VideoCadenceEstimator::avg_cadence_for_testing() const {
  306. if (!has_cadence())
  307. return 0.0;
  308. if (bm_.use_bresenham_cadence_)
  309. return bm_.perfect_cadence_.value();
  310. int sum = std::accumulate(begin(cadence_), end(cadence_), 0);
  311. return static_cast<double>(sum) / cadence_.size();
  312. }
  313. } // namespace media