An algorithm for splitting a sequence in equally spaced, non colliding subsequences.

Question

Hi to all, I got this problem that I can't just solve algorithmically.

Let's say i have a video capture that always captures video frames at a fixed rate F (let's say 30 frames per second).

What I want is to "split" this frame sequence in n (say four) subsequences. Each subsequence has its framerate fn, that's obviously < F. Frames in a subsequence are equally spaced in time, so for example some valid 10 fps sequence f1 will be contructed like that for F = 30 fps and time = 1 second:

(0s are frames that don't belogn to the subsequence, 1s are frames that do):

100 (in 1 second it will repeated like: 100100100100100100100100100100)

or

010 (again, in 1 sec it will go like: 010010010010010010010010010010)

or, for F = 30 and f = 8:

100000001

(and it would take MCD (30,8) = 120 frames before a second restarts with an "1").

The problem is that subsequences can't collide, so if F=30, f1 = 10 fps (every three frames) and f2 = 5 fps (every six frames), this sequence is ok:

102100 (again, in a second: 102100102100102100102100102100)

But if we add f3 = 6 fps

132100 (1 AND 3) <--- collides! 02100102100102100102100

or

102103102130102 (1 AND 3) <--- collides! 00102100102100

The third subsequence would collide with the first.

The question is:

• Is there a way to find every combination of the framerates of the n (with n <= 4) subsequences that won't collide and would be equally spaced?

(I need the general case, but in this particular case, I would need all the valid combinations for one sequence only (trivial), all the valid combinations for two sequences, all the valid combinations of three sequences, and all for four sequences).

Hope someone could enlighten my mind. Thank you!

Answer 1

If you have a look at you rates, you are going to remark that:

• There is k in N (integers >= 0) such that f1 = k * f2
• There is no k in N such that f1 = k * f3

More to the point, f1 and f2 are specials in that f2 gives you a subsequence of what f1 would give starting at the same point. Then since two f1 sequences would never cross if they don't begin at the same point (think parallel), then naturally f2 is not going to cross f1 either!

You can also see that the contrary holds, since f3 is not a subsequence of f1 (ie, f3 is not a divisor of f1), then there exist i,j in Z (integers) such that i*f1 + j*f3 = 1, though I can't remember which theorem this is from. This means that I can actually find a collision whatever the position both subsequences start from.

It alos means that you could get away with f1 = 29 and f3 = 27 if you could only had a few frames, but ultimately they will collide if you keep going long enough (though predicting and not computing it is beyond me at the moment).

---

In short: elect one 'master' frequence (the fastest of all those you want) and then only pick up divisors of this frequence and you will be okay whatever the length of your video.

Answer 2

I believe this would do it for the 4 stream case, and it should be obvious what to do for the fewer stream cases.

for a in range(1,31):
    for b in range(a,31):
        for c in range(b,31):
            for d in range(c,31):
                if (1.0/a+1.0/b+1.0/c+1.0/d)<=1.0 and gcd(a,b,c,d)>=4:
                    print a,b,c,d

Basically, whatever frequencies you're considering, 1) they can't take up more than all of the stream 2) if their greatest common denominator is <4, you can't find an arrangement of them that won't conflict. (For example, consider the case of two prime numbers; gcd(p1,p2) is always 1, and they'll always conflict in <=p1*p2 frames regardless of how you offset them)