Frequency measurement with missing data

Is there a known good algorithm for measuring a clock frequency based upon
"ticks" where some of the ticks are missing?

Specifically, I'm trying to infer the video refresh rate based upon a
sequence of timestamps, each of which is shortly after vsync (i.e. the
system time at which SwapBuffers() returns).

So if the refresh rate is 60 Hz, the interval between two successive
timestamps would be one of 1/60, 1/30, 1/20, 1/15, 1/12, ... seconds, plus
some jitter (typically around a millisecond or so).

I have something which mostly works, but I can't help feeling that there's
probably something simpler and more robust.

The awkward case is where the intervals initially all correspond to an
even number of frames, resulting in the inferred frequency being half the
actual frequency, then odd multiples start occurring.

On Thu, 17 Dec 2015 07:50:35 +0000, Nobody <nobody@nowhere.invalid>
wrote:

>
>Is there a known good algorithm for measuring a clock frequency based upon
>"ticks" where some of the ticks are missing?
>
>Specifically, I'm trying to infer the video refresh rate based upon a
>sequence of timestamps, each of which is shortly after vsync (i.e. the
>system time at which SwapBuffers() returns).
>
>So if the refresh rate is 60 Hz, the interval between two successive
>timestamps would be one of 1/60, 1/30, 1/20, 1/15, 1/12, ... seconds, plus
>some jitter (typically around a millisecond or so).
>
>I have something which mostly works, but I can't help feeling that there's
>probably something simpler and more robust.
>
>The awkward case is where the intervals initially all correspond to an
>even number of frames, resulting in the inferred frequency being half the
>actual frequency, then odd multiples start occurring.
>

For that sort of application doesn't the minimum detected period give
the frequency?


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

On Thu, 17 Dec 2015 17:04:55 +0000, Eric Jacobsen wrote:

> For that sort of application doesn't the minimum detected period give the
> frequency?

Not necessarily. E.g. if it takes roughly 2.5 times the frame period to
render each frame before requesting a buffer swap, the interval between
events (buffer swap complete) will alternate between 2 and 3 frame periods.

What I essentially want is the greatest common divisor of the intervals,
but timing jitter means I can't literally use the GCD.

At the moment, I divide the minimum observed interval Tmin by k=1,2,3,...,
finding the least k such that all observed intervals are integer multiples
of Tmin/k to within a given (and somewhat arbitrary) tolerance.

At that point, I can assign an integer frame number to each event, then
use linear least-squares regression on the frame number and timestamp to
determine the period and offset (essentially filtering out the jitter from
the timestamps).

The main complication is the desire to be able to re-synchronise quickly
if the frame rate changes (e.g. due to switching output between monitors),
but when the frame rate is stable use a large number of samples to compute
the rate accurately.

On Saturday, December 19, 2015 at 2:11:41 AM UTC-5, Nobody wrote:
> On Thu, 17 Dec 2015 17:04:55 +0000, Eric Jacobsen wrote:
> 
> > For that sort of application doesn't the minimum detected period give the
> > frequency?
> 
> Not necessarily. E.g. if it takes roughly 2.5 times the frame period to
> render each frame before requesting a buffer swap, the interval between
> events (buffer swap complete) will alternate between 2 and 3 frame periods.
> 
> What I essentially want is the greatest common divisor of the intervals,
> but timing jitter means I can't literally use the GCD.
> 
> At the moment, I divide the minimum observed interval Tmin by k=1,2,3,...,
> finding the least k such that all observed intervals are integer multiples
> of Tmin/k to within a given (and somewhat arbitrary) tolerance.
> 
> At that point, I can assign an integer frame number to each event, then
> use linear least-squares regression on the frame number and timestamp to
> determine the period and offset (essentially filtering out the jitter from
> the timestamps).
> 
> The main complication is the desire to be able to re-synchronise quickly
> if the frame rate changes (e.g. due to switching output between monitors),
> but when the frame rate is stable use a large number of samples to compute
> the rate accurately.

To get the most from this board I think some additional information will be beneficial.

The first questions that come to (my) mind are:

1. Is the set of frame rates to be detected known a priori?
2. If so are any or all rates integrally or rationally related?
3. What is the maximum processing delay you can tolerate?
4. What is the maximum gap duration between tick events?

>Not necessarily. E.g. if it takes roughly 2.5 times the frame period to
>render each frame before requesting a buffer swap, the interval between
>events (buffer swap complete) will alternate between 2 and 3 frame
periods.
>
>What I essentially want is the greatest common divisor of the intervals,
>but timing jitter means I can't literally use the GCD.
>
>At the moment, I divide the minimum observed interval Tmin by
k=1,2,3,...,
>finding the least k such that all observed intervals are integer
multiples
>of Tmin/k to within a given (and somewhat arbitrary) tolerance.
>
>At that point, I can assign an integer frame number to each event, then
>use linear least-squares regression on the frame number and timestamp to
>determine the period and offset (essentially filtering out the jitter
from
>the timestamps).
>
>The main complication is the desire to be able to re-synchronise quickly
>if the frame rate changes (e.g. due to switching output between
monitors),
>but when the frame rate is stable use a large number of samples to
compute
>the rate accurately.

It seems to me that a histogram is your best answer and you want to have
two modes.  Here is some pseudocode:

  mode = FindingRate
  histogram[100] = 0s  
  multiplier = AppropriateValue

  while not done
    time_interval = GetTimeInterval()
    switch mode
     case FindingRate
        LookForRate()
        break
     case MonitoringRate
        MonitorRate()
        break
    end switch
  end while

  return

LookForRate
  index = time_interval * multiplier
  histogram[index]++

  if IsThereAClusterAt( index ) then
     SearchForOtherClusters()
     If found then
        current_interval = 
           cluster_spacing / multiplier
        mode = MontitoringRate
     end if
  end if

MonitorRate

  frame_count = time_interval / current_interval

  if frame_count near integer then
    frame_interval = time_interval
      / ClosestInteger( frame_count )
    current_interval = w * current_interval
         + ( 1 - w ) * frame_interval
  else
    mode = LookingForRate
    ProcessRateChange()
    histogram[100] = 0s  
    LookForRate()  
  end if

If shouldn't be too difficult to fill in the missing parts, but it would
make the post too long to include them.

Hope this helps.

Ced


---------------------------------------
Posted through http://www.DSPRelated.com

[..snip..]
>The awkward case is where the intervals initially all correspond to an
>even number of frames, resulting in the inferred frequency being half
the
>actual frequency, then odd multiples start occurring.

I didn't notice this at first.  There is nothing you can do, unless you've
built a list of possible values.

In the pseudo code I provided, you can find this condition when monitoring
if the frame_count is near integer+.5 and adjust your variables
accordingly without kicking back into FindingRate mode.

Ced

---------------------------------------
Posted through http://www.DSPRelated.com

On Sat, 19 Dec 2015 05:00:04 -0800, lito844 wrote:

> 1. Is the set of frame rates to be detected known a priori?

Ideally, no. Certain rates are standard, but an approach which works with
any rate (at least within 50-120 Hz) is preferred.

> 2. If so are any or all rates integrally or rationally related?

Some are integral multiples (e.g. 60 and 120 Hz), some are small rational
multiples (e.g. 60 and 75 Hz are 4:5), others may have no relation.

> 3. What is the maximum processing delay you can tolerate?

Processing delay?

> 4. What is the maximum gap duration between tick events?

42 ms (24 fps).

On Sunday, December 20, 2015 at 6:13:02 AM UTC-5, Nobody wrote:
> On Sat, 19 Dec 2015 05:00:04 -0800, lito844 wrote:
> 
> > 1. Is the set of frame rates to be detected known a priori?
> 
> Ideally, no. Certain rates are standard, but an approach which works with
> any rate (at least within 50-120 Hz) is preferred.
> 
> > 2. If so are any or all rates integrally or rationally related?
> 
> Some are integral multiples (e.g. 60 and 120 Hz), some are small rational
> multiples (e.g. 60 and 75 Hz are 4:5), others may have no relation.
> 
> > 3. What is the maximum processing delay you can tolerate?
> 
> Processing delay?
> 
> > 4. What is the maximum gap duration between tick events?
> 
> 42 ms (24 fps).

These questions are my attempt to not ony bound the problem but to frame it in a more generic signal processing context so that DSP experts without video frame rate processing experience (like me) could contribute solutions.

Regarding question 1: Based on your answer that all rates over a limited range must be detected, I take it your estimator must reliably discriminate for example between 60 Hz and 60.001 Hz.  If this is indeed the case then the problem is much more complicated then my original assumption.

Regarding question 3: To clarify, I'm trying to understand how quickly your estimator must turn a solution.  How many tick events can the estimator accumulate before rendering a frame rate output?  Simplistically the more data the estimator has to work with the more accurate the result.  Howerver at some point (I assume) the delay will become intolerable.

Regarding question 4: In your OP you mentioned that the system is subject to "missing ticks".  This question is my attempt to ascertain the maximum number of missing ticks that can occur.  So in the parlance of this question the maximum gap duration refers to the maximum interval over which consecutive ticks are missing.  Your answer implies that at 24 fps no missing ticks will occur.  What about other frame rates?

On Sun, 20 Dec 2015 05:24:42 -0800, lito844 wrote:

> Regarding question 1: Based on your answer that all rates over a limited
> range must be detected, I take it your estimator must reliably
> discriminate for example between 60 Hz and 60.001 Hz.  If this is indeed
> the case then the problem is much more complicated then my original
> assumption.

That part isn't so hard. It doesn't matter if the measured frame interval
is off by a few percent, so long as the error doesn't accumulate between
frames.

The current approach runs a rolling least-squares regression over the
timestamps of some number of previous frames, so if the frequency of
either the video clock or system clock changes slightly, the parameters
will be updated.

This part works well enough, and should cope with significant variation in
frequency. But the regression requires being able to match each timestamp
with a frame number, which requires knowing the frame rate closely enough
that I can calculate the frame number using

    F[n] = F[n-1]+round((T[n]-T[n-1])/period)

where F[n] are frame numbers and T[n] are timestamps. I.e. the period
needs to be accurate enough that round((T[n]-T[n-1])/period) is the
correct number of frames which elapsed.

> Regarding question 3: To clarify, I'm trying to understand how quickly
> your estimator must turn a solution.  How many tick events can the
> estimator accumulate before rendering a frame rate output?  Simplistically
> the more data the estimator has to work with the more accurate the result.
>  Howerver at some point (I assume) the delay will become intolerable.

At present, it goes with whatever it's given. Starting with a few "blank"
frames ensures that the minimum observed interval is actually a single
frame. But currently it doesn't attempt to re-synchronise in the event of
a sudden, substantial change to the frame rate (rather than just "drift").

Detecting such a change probably isn't that hard (providing it's not e.g.
2:1; a change from 60 Hz to 120 Hz would never be noticed because I'd
never get to see the extra ticks), and in the worst case I can just
discard the history and start over. But this problem seems close enough to
a software PLL that I wondered if there are already established solutions.

> Regarding question 4: In your OP you mentioned that the system is subject
> to "missing ticks".  This question is my attempt to ascertain the maximum
> number of missing ticks that can occur.  So in the parlance of this
> question the maximum gap duration refers to the maximum interval over
> which consecutive ticks are missing.  Your answer implies that at 24 fps
> no missing ticks will occur.  What about other frame rates?

If we take 1/24 sec (~42ms) as the maximum rendering time, then at 60 Hz
I expect to see the interval between swaps alternating between 2 and 3
frames (1/30 and 1/20 sec), i.e. I see every second or third tick. At 120
Hz, I would see every fifth tick. At higher frequencies, aliasing with the
OS' time-slice frequency (1000 Hz on Windows) starts to become an issue.

On Sunday, December 20, 2015 at 11:49:56 PM UTC-5, Nobody wrote:
> On Sun, 20 Dec 2015 05:24:42 -0800, lito844 wrote:
> 
> > Regarding question 1: Based on your answer that all rates over a limited
> > range must be detected, I take it your estimator must reliably
> > discriminate for example between 60 Hz and 60.001 Hz.  If this is indeed
> > the case then the problem is much more complicated then my original
> > assumption.
> 
> That part isn't so hard. It doesn't matter if the measured frame interval
> is off by a few percent, so long as the error doesn't accumulate between
> frames.
> 
> The current approach runs a rolling least-squares regression over the
> timestamps of some number of previous frames, so if the frequency of
> either the video clock or system clock changes slightly, the parameters
> will be updated.
> 
> This part works well enough, and should cope with significant variation in
> frequency. But the regression requires being able to match each timestamp
> with a frame number, which requires knowing the frame rate closely enough
> that I can calculate the frame number using
> 
>     F[n] = F[n-1]+round((T[n]-T[n-1])/period)
> 
> where F[n] are frame numbers and T[n] are timestamps. I.e. the period
> needs to be accurate enough that round((T[n]-T[n-1])/period) is the
> correct number of frames which elapsed.
> 
> > Regarding question 3: To clarify, I'm trying to understand how quickly
> > your estimator must turn a solution.  How many tick events can the
> > estimator accumulate before rendering a frame rate output?  Simplistically
> > the more data the estimator has to work with the more accurate the result.
> >  Howerver at some point (I assume) the delay will become intolerable.
> 
> At present, it goes with whatever it's given. Starting with a few "blank"
> frames ensures that the minimum observed interval is actually a single
> frame. But currently it doesn't attempt to re-synchronise in the event of
> a sudden, substantial change to the frame rate (rather than just "drift").
> 
> Detecting such a change probably isn't that hard (providing it's not e.g.
> 2:1; a change from 60 Hz to 120 Hz would never be noticed because I'd
> never get to see the extra ticks), and in the worst case I can just
> discard the history and start over. But this problem seems close enough to
> a software PLL that I wondered if there are already established solutions.
> 
> > Regarding question 4: In your OP you mentioned that the system is subject
> > to "missing ticks".  This question is my attempt to ascertain the maximum
> > number of missing ticks that can occur.  So in the parlance of this
> > question the maximum gap duration refers to the maximum interval over
> > which consecutive ticks are missing.  Your answer implies that at 24 fps
> > no missing ticks will occur.  What about other frame rates?
> 
> If we take 1/24 sec (~42ms) as the maximum rendering time, then at 60 Hz
> I expect to see the interval between swaps alternating between 2 and 3
> frames (1/30 and 1/20 sec), i.e. I see every second or third tick. At 120
> Hz, I would see every fifth tick. At higher frequencies, aliasing with the
> OS' time-slice frequency (1000 Hz on Windows) starts to become an issue.

I get now that you're further down the path to a working solution than I previously thought.  So rather than suggest a new solution starting with a clean sheet of paper I'll try to offer something that may help you get to the next step.

First, I think your heuristic solution using statistics and linear regression is fine, especially in light of the fact that you've proven it to work.  It sounds like the only piece missing is detecting a change in frame rate.

Others may chime in but an established software PLL solution is not immediately evident to me, at least one which provides a clear advantage over a heuristic approach.

Since you have a proven method I'd suggest an approach where you use two instances of your method running concurrently, one utilizing long term statistics (call it the narrowband, or NB instance) and one processing short term statistics (the wideband, or WB instance).  

The NB instance is akin to what you have today and continues to provide the final output of the system.  The purpose of the WB instance is to quickly detect a change in frame rate.  Both instances are the same design, the difference being the WB instance measures frame rate using (much) fewer data points.  (The number of data points in both instances is a design parameter.)

A change in frame rate is declared when the output of the WB instance differs from the NB instance by THRESHOLD standard deviations. (THRESHOLD is a design parameter.)  At this point the state history of the NB instance can be replaced with that of the WB instance and concurrent processing continues. 

When the frame rate is not changing the WB instance is free to wander about the mean without affecting the output of the system.  But when the rate changes WB will move quickly to the new rate signaling the change.