Calculating frame index based on new frame rate for video generation

Question

My .NET application as a sequential list of images representing each frame of a video recorded at 30 frames per second.

00000001.png
00000002.png
00000003.png
...
99999999.png

Now I want to reorder this list so it can generate a video based on the following parameters:

Start Frame Index: 100
Direction:         Forward
Output Speed:      100 FPS
Duration:          10 seconds

So far I have something like this:

var originalFrameRate = 30D;
var originalFrameTime = 1D / originalFrameRate;
var originalStartFrameIndex = 100; // 00000100.png.
// Assume [originalFrames] will be filled with image file names from above.
var originalFrames = new List<string>
(new string [] { "0000003.png", "0000002.png", ..., "99999999.png", });

var targetFrameRate 100; // FPS.
var targetDuration = TimeSpan.FromSeconds(10);
var targetFrameCount = speed * targetDuration.Seconds;
var targetFrames = new List<string>();

for (int i = 0; i < targetFrameCount; i++)
{
    // How to map the original list from 30 FPS to 100 FPS?
    targetFrames.Add(originalFrames [originalStartFrameIndex + ???]);
}

In the above example, the output would be targetFrames being filled with the appropriate file name based on the variables names targetXXX.

Any suggestions on how to map this would be appreciated.

EDIT: I forgot to mention that the output video will always be generated at the original frame rate. The length of the target video will of course change. If the original FPS is lower than the target, we will repeat frames. Otherwise we will be skipping them.

Answer 1

targetFrames.Add(originalFrames [originalStartFrameIndex + (int)(i * targetFrameRate / originalFrameRate) ]

should do the trick. Add some error validation (check for divide by zero and exceeding the bounds of the array) :)

Answer 2

I started to expand upon Vincent's answer to fix a problem I noticed: when scaling from 30fps to 100fps, frame 0 is repeated a fourth time (a frame pattern of 0000 111 222 3333) when I was expecting 000 111 2222. Not a big deal since it's probably just a matter of preference (whether you want the fractional "adjustment" to happen on an even or odd frame), but then I went down the rabbit hole and built an iterator class that can handle just about any scenario, including fractional framerates.

(Using a generic iterator has the added bonus of not requiring the frames to be string - if you wanted to represent each frame as a class, you could do that, too.)

public sealed class FramerateScaler<T> : IEnumerable<T>
{
    private IEnumerable<T> _source;
    private readonly double _inputRate;
    private readonly double _outputRate;
    private readonly int _startIndex;

    public double InputRate { get { return _inputRate; } }
    public double OutputRate { get { return _outputRate; } }
    public int StartIndex { get { return _startIndex; } }

    public TimeSpan InputDuration {
        get { return TimeSpan.FromSeconds((1 / _inputRate) * (_source.Count() - StartIndex)); }
    }

    public TimeSpan OutputDuration {
        get { return TimeSpan.FromSeconds((1 / _outputRate) * this.Count()); }
    }

    public FramerateScaler(
        double inputRate, double outputRate, 
        IEnumerable<T> source, int startIndex = 0)
    {
        _source = source;
        _inputRate = inputRate;
        _outputRate = outputRate;
        _startIndex = startIndex;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new ScalingFrameEnumerator<T>(_inputRate, _outputRate, _source, _startIndex);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return (IEnumerator)GetEnumerator();
    }

    private sealed class ScalingFrameEnumerator<T> : IEnumerator<T>
    {
        internal readonly double _inputRate;
        internal readonly double _outputRate;
        internal readonly int _startIndex;

        private readonly List<T> _source;

        private readonly double _rateScaleFactor;
        private readonly int _totalOutputFrames;
        private int _currentOutputFrame = 0;

        public ScalingFrameEnumerator(
            double inputRate, double outputRate, 
            IEnumerable<T> source, int startIndex)
        {
            _inputRate = inputRate;
            _outputRate = outputRate;
            _source = source.ToList();
            _startIndex = startIndex;

            _rateScaleFactor = _outputRate / _inputRate;
            // Calculate total output frames from input duration
            _totalOutputFrames = (int)Math.Round(
                (_source.Count - startIndex) * _rateScaleFactor, 0);
        }

        public T Current
        {
            get
            {
                return _source[_startIndex + 
                    (int)Math.Ceiling(_currentOutputFrame / _rateScaleFactor) - 1];
            }
        }

        public void Dispose()
        {
            // Nothing unmanaged to dispose
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            _currentOutputFrame++;
            return ((_currentOutputFrame - 1) < _totalOutputFrames);
        }

        public void Reset()
        {
            _currentOutputFrame = 0;
        }
    }
}

And a set of tests covering idempotence, scaling up, scaling down, and fractional framerates:

[TestClass]
public class Test
{
    private readonly List<string> _originalFrames = new List<string>();

    public Test()
    {
        // 30 FPS for 10 seconds
        for (int f = 0; f < 300; f++)
        {
            _originalFrames.Add(string.Format("{0:0000000}.png", f));
        }
    }

    [TestMethod]
    public void Should_set_default_values()
    {
        var scaler = new FramerateScaler<string>(30, 30, _originalFrames, 10);

        Assert.AreEqual(30, scaler.InputRate);
        Assert.AreEqual(30, scaler.OutputRate);
        Assert.AreEqual(10, scaler.StartIndex);
        Assert.AreEqual(_originalFrames.ElementAt(10), scaler.First());
    }

    [TestMethod]
    public void Scale_from_same_is_idempotent()
    {
        var scaler = new FramerateScaler<string>(30, 30, _originalFrames);

        Assert.AreEqual(scaler.InputDuration, scaler.OutputDuration);
        Assert.AreEqual(_originalFrames.Count, scaler.Count());
        Assert.IsTrue(_originalFrames.SequenceEqual(scaler));
    }

    [TestMethod]
    public void Scale_from_same_offset_by_half_is_idempotent()
    {
        var scaler = new FramerateScaler<string>(
            30, 30, _originalFrames, _originalFrames.Count / 2);

        Assert.AreEqual(150, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        Assert.IsTrue(_originalFrames
            .Skip(150)
            .SequenceEqual(scaler));
    }

    [TestMethod]
    public void Scale_from_30_to_60()
    {
        var scaler = new FramerateScaler<string>(30, 60, _originalFrames);

        Assert.AreEqual(600, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        var result = scaler.ToList();
        Assert.IsTrue(_originalFrames
            .Concat(_originalFrames)
            .OrderBy(x => x)
            .SequenceEqual(scaler));
    }

    [TestMethod]
    public void Scale_from_30_to_60_offset_by_half()
    {
        var scaler = new FramerateScaler<string>(
            30, 60, _originalFrames, _originalFrames.Count / 2);

        Assert.AreEqual(300, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        Assert.IsTrue(_originalFrames
            .Skip(150)
            .Concat(_originalFrames.Skip(150))
            .OrderBy(x => x)
            .SequenceEqual(scaler));
    }

    [TestMethod]
    public void Scale_from_30_to_100()
    {
        var scaler = new FramerateScaler<string>(30, 100, _originalFrames);

        Assert.AreEqual(1000, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        // 000 - 111 - 2222 ...
        Assert.IsTrue(scaler.PatternIs(0, 0, 0, 1, 1, 1, 2, 2, 2, 2));
    }

    [TestMethod]
    public void Scale_from_30_to_100_offset_by_half()
    {
        var scaler = new FramerateScaler<string>(
            30, 100, _originalFrames, _originalFrames.Count / 2);

        Assert.AreEqual(500, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        // 000 - 111 - 2222 ...
        Assert.IsTrue(scaler.PatternIs(0, 0, 0, 1, 1, 1, 2, 2, 2, 2));
    }

    [TestMethod]
    public void Scale_from_24p_to_ntsc()
    {
        var scaler = new FramerateScaler<string>(23.967, 29.97, _originalFrames);

        Assert.AreEqual(375, scaler.Count());
        Assert.AreEqual(
            scaler.OutputDuration.TotalMilliseconds, 
            scaler.InputDuration.TotalMilliseconds, delta: 4);
        // 0 - 1 - 2 - 33 ...
        Assert.IsTrue(scaler.PatternIs(0, 1, 2, 3, 3));
    }

    [TestMethod]
    public void Scale_from_30_to_15()
    {
        var scaler = new FramerateScaler<string>(30, 15, _originalFrames);

        Assert.AreEqual(150, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        Assert.IsTrue(_originalFrames
            .Where((item, index) => index % 2 == 1)
            .SequenceEqual(scaler));
    }

    [TestMethod]
    public void Scale_from_30_to_15_offset_by_half()
    {
        var scaler = new FramerateScaler<string>(30, 15, _originalFrames, 150);

        Assert.AreEqual(75, scaler.Count());
        Assert.AreEqual(scaler.OutputDuration, scaler.InputDuration);
        Assert.IsTrue(_originalFrames
            .Skip(150)
            .Where((item, index) => index % 2 == 1)
            .SequenceEqual(scaler));
    }
}

static class Extensions
{
    public static bool PatternIs<T>(this IEnumerable<T> source, params int[] pattern)
    {
        foreach (var chunk in source.Chunkify(pattern.Length))
        {
            for (var i = 0; i < chunk.Length; i++)
                if (!chunk.ElementAt(i).Equals(
                    chunk.Distinct().ElementAt(pattern[i])))
                    return false;
        }

        return true;
    }

    // http://stackoverflow.com/a/3210961/3191599
    public static IEnumerable<T[]> Chunkify<T>(this IEnumerable<T> source, int size)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (size < 1) throw new ArgumentOutOfRangeException("size");
        using (var iter = source.GetEnumerator())
        {
            while (iter.MoveNext())
            {
                var chunk = new T[size];
                chunk[0] = iter.Current;
                for (int i = 1; i < size && iter.MoveNext(); i++)
                {
                    chunk[i] = iter.Current;
                }
                yield return chunk;
            }
        }
    }
}