media/filters/video_cadence_estimator.h

   1 // Copyright 2015 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_
   6 #define MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10
  11 #include <string>
  12 #include <vector>
  13
  14 #include "base/time/time.h"
  15 #include "media/base/media_export.h"
  16 #include "third_party/abseil-cpp/absl/types/optional.h"
  17
  18 namespace media {
  19
  20 // Estimates whether a given frame duration and render interval length have a
  21 // render cadence which would allow for optimal uniformity of displayed frame
  22 // durations over time.
  23 //
  24 // Cadence is the ideal repeating frame pattern for a group of frames; currently
  25 // VideoCadenceEstimator supports N-frame ([a1:a2:..:aN]) cadences where N <= 5.
  26 // Details on what this means are below.
  27 //
  28 // The perfect cadence of a set of frames is the ratio of the frame duration to
  29 // render interval length.  I.e. for 30fps in 60Hz the cadence would be (1/30) /
  30 // (1/60) = 60 / 30 = 2.  It's common that this is not an exact integer, e.g.,
  31 // 29.974fps in 60Hz which would have a cadence of (1/29.974) / (1/60) =
  32 // ~2.0029.
  33 //
  34 // The perfect cadence is always a real number.  All N-cadences [a1:a2:..:aN]
  35 // where aK is an integer are an approximation of the perfect cadence; i.e. the
  36 // average of [a1:..:aN] will approximately equal the perfect cadence.  When N=1
  37 // we have a 1-frame cadence, when N=2, we have a 2-frame cadence, etc.
  38 //
  39 // For single frame cadence we just round the perfect cadence (~2.0029 in the
  40 // previous example) to the nearest integer value (2 in this case; which is
  41 // denoted as a cadence of [2]).  If the delta between those values is small we
  42 // can choose to render frames for the integer number of render intervals;
  43 // shortening or lengthening the actual rendered frame duration.  Doing so
  44 // ensures each frame gets an optimal amount of display time.
  45 //
  46 // For N-frame cadence, the idea is similar, we just round the perfect cadence
  47 // to some K/N, where K is an integer, and distribute [floor(K/N), floor(K/N)+1]
  48 // into the cadence vector as evenly as possible.  For example, 23.97fps in
  49 // 60Hz, the perfect cadence is 2.50313, we can round it to 2.5 = 5/2, and we
  50 // can then construct the cadence vector as [2:3].
  51 //
  52 // The delta between the perfect cadence and the rounded cadence leads to drift
  53 // over time of the actual VideoFrame timestamp relative to its rendered time,
  54 // so we perform some calculations to ensure we only use a cadence when it will
  55 // take some time to drift an undesirable amount; see CalculateCadence() for
  56 // details on how this calculation is made.
  57 //
  58 // In practice this works out to the following for common setups if we use
  59 // cadence based selection:
  60 //
  61 //    29.5fps in 60Hz,    ~17ms max drift => exhausted in ~1 second.
  62 //    29.9fps in 60Hz,    ~17ms max drift => exhausted in ~16.4 seconds.
  63 //    24fps   in 59.9Hz,  ~21ms max drift => exhausted in ~12.6 seconds.
  64 //    24.9fps in 60Hz,    ~20ms max drift => exhausted in ~4.0 seconds.
  65 //    59.9fps in 60Hz,    ~8.3ms max drift => exhausted in ~8.2 seconds.
  66 //    24.9fps in 50Hz,    ~20ms max drift => exhausted in ~20.5 seconds.
  67 //    120fps  in 59.9Hz,  ~8.3ms max drift => exhausted in ~8.2 seconds.
  68 //
  69 class MEDIA_EXPORT VideoCadenceEstimator {
  70  public:
  71   using Cadence = std::vector<int>;
  72
  73   // As mentioned in the introduction, the determination of whether to clamp to
  74   // a given cadence is based on how long it takes before a frame would have to
  75   // be dropped or repeated to compensate for reaching the maximum acceptable
  76   // drift; this time length is controlled by |minimum_time_until_max_drift|.
  77   explicit VideoCadenceEstimator(base::TimeDelta minimum_time_until_max_drift);
  78
  79   VideoCadenceEstimator(const VideoCadenceEstimator&) = delete;
  80   VideoCadenceEstimator& operator=(const VideoCadenceEstimator&) = delete;
  81
  82   ~VideoCadenceEstimator();
  83
  84   // Clears stored cadence information.
  85   void Reset();
  86
  87   // Updates the estimates for |cadence_| based on the given values as described
  88   // in the introduction above.
  89   //
  90   // Clients should call this and then update the cadence for all frames via the
  91   // GetCadenceForFrame() method if the cadence changes.
  92   //
  93   // Cadence changes will not take affect until enough render intervals have
  94   // elapsed.  For the purposes of hysteresis, each UpdateCadenceEstimate() call
  95   // is assumed to elapse one |render_interval| worth of time.
  96   //
  97   // Returns true if the cadence has changed since the last call.
  98   bool UpdateCadenceEstimate(base::TimeDelta render_interval,
  99                              base::TimeDelta frame_duration,
 100                              base::TimeDelta frame_duration_deviation,
 101                              base::TimeDelta max_acceptable_drift);
 102
 103   // Returns true if a useful cadence was found.
 104   bool has_cadence() const { return !cadence_.empty(); }
 105
 106   // Given a |frame_number|, where zero is the most recently rendered frame,
 107   // returns the ideal cadence for that frame.
 108   //
 109   // Note: Callers must track the base |frame_number| relative to all frames
 110   // rendered or removed after the first frame for which cadence is detected.
 111   // The first frame after cadence is detected has a |frame_number| of 0.
 112   //
 113   // Frames which come in before the last rendered frame should be ignored in
 114   // terms of impact to the base |frame_number|.
 115   int GetCadenceForFrame(uint64_t frame_number) const;
 116
 117   void set_cadence_hysteresis_threshold_for_testing(base::TimeDelta threshold) {
 118     cadence_hysteresis_threshold_ = threshold;
 119   }
 120
 121   double avg_cadence_for_testing() const;
 122   size_t cadence_size_for_testing() const { return cadence_.size(); }
 123   std::string GetCadenceForTesting() const { return CadenceToString(cadence_); }
 124
 125   // Determines whether a simple (single-valued) integer cadence exists for
 126   // |render_interval| and |frame_duration| that won't drift more than
 127   // |render_interval| within |minimum_time_until_max_drift|.
 128   static bool HasSimpleCadence(
 129       base::TimeDelta render_interval,
 130       base::TimeDelta frame_duration,
 131       base::TimeDelta minimum_time_until_max_drift = base::Seconds(8));
 132
 133  private:
 134   // Attempts to find an N-frame cadence.  Returns the cadence vector if cadence
 135   // is found and sets |time_until_max_drift| for the computed cadence. If
 136   // multiple cadences satisfying the max drift constraint exist, we are going
 137   // to return the one with largest |time_until_max_drift|.
 138   // For details on the math and algorithm, see https://goo.gl/QK0vbz
 139   Cadence CalculateCadence(base::TimeDelta render_interval,
 140                            base::TimeDelta frame_duration,
 141                            base::TimeDelta max_acceptable_drift,
 142                            base::TimeDelta* time_until_max_drift) const;
 143
 144   // Converts a cadence vector into a human readable string of the form
 145   // "[a: b: ...: z]".
 146   std::string CadenceToString(const Cadence& cadence) const;
 147
 148   bool UpdateBresenhamCadenceEstimate(base::TimeDelta render_interval,
 149                                       base::TimeDelta frame_duration);
 150
 151   // The approximate best N-frame cadence for all frames seen thus far; updated
 152   // by UpdateCadenceEstimate().  Empty when no cadence has been detected.
 153   Cadence cadence_;
 154
 155   // Used as hysteresis to prevent oscillation between cadence approximations
 156   // for spurious blips in the render interval or frame duration.
 157   //
 158   // Once a new cadence is detected, |render_intervals_cadence_held_| is
 159   // incremented for each UpdateCadenceEstimate() call where |cadence_| matches
 160   // |pending_cadence_|.  |render_intervals_cadence_held_| is cleared when a
 161   // "new" cadence matches |cadence_| or |pending_cadence_|.
 162   //
 163   // Once |kMinimumCadenceDurationMs| is exceeded in render intervals, the
 164   // detected cadence is set in |cadence_|.
 165   Cadence pending_cadence_;
 166   int render_intervals_cadence_held_;
 167   base::TimeDelta cadence_hysteresis_threshold_;
 168
 169   // Tracks how many times cadence has switched during a given playback, used to
 170   // histogram the number of cadence changes in a playback.
 171   bool first_update_call_;
 172   int cadence_changes_;
 173
 174   // The minimum amount of time allowed before a glitch occurs before confirming
 175   // cadence for a given render interval and frame duration.
 176   const base::TimeDelta minimum_time_until_max_drift_;
 177
 178   bool is_variable_frame_rate_;
 179 };
 180
 181 }  // namespace media
 182
 183 #endif  // MEDIA_FILTERS_VIDEO_CADENCE_ESTIMATOR_H_