1

我遇到了无法仅通过算法解决的问题。

假设我有一个视频捕获，它总是以固定速率 F（假设每秒 30 帧）捕获视频帧。

我想要的是将此帧序列“拆分”为 n 个（比如说四个）子序列。每个子序列都有其帧速率 fn，这显然 < F。子序列中的帧在时间上是等距的，因此例如一些有效的 10 fps 序列 f1 将像 F = 30 fps 和时间 = 1 秒那样构造：

（0 是不属于子序列的帧，1 是属于的帧）：

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

或者

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

或者，对于 F = 30 和 f = 8：

100000001

（并且在以“1”重新开始之前需要 MCD (30,8) = 120 帧）。

问题是子序列不能碰撞，所以如果 F=30，f1 = 10 fps（每三帧）和 f2 = 5 fps（每六帧），这个序列是可以的：

102100 (again, in a second: 102100102100102100102100102100)

但是如果我们加上 f3 = 6 fps

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

或者

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

第三个子序列将与第一个子序列发生冲突。

问题是：

  • 有没有办法找到n个（n <= 4）子序列的帧速率的每个组合，它们不会发生冲突并且会等距？

（我需要一般情况，但在这种特殊情况下，我只需要一个序列的所有有效组合（平凡），两个序列的所有有效组合，三个序列的所有有效组合，以及四个序列的所有有效组合） .

希望有人能启发我的想法。谢谢！

4

2 回答 2

2

我相信这对于 4 流的情况会做到这一点，对于较少的流情况应该做什么应该是显而易见的。

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

基本上，无论您考虑什么频率，1) 它们不能占用超过所有流 2) 如果它们的最大公分母 <4，则您找不到不会冲突的它们的排列。（例如，考虑两个素数的情况；gcd(p1,p2) 始终为 1，并且无论您如何偏移它们，它们都会在 <=p1*p2 帧中发生冲突）

于 2009-10-07T00:40:21.703 回答
1

如果你看一下你的费率，你会说：

  • N 中有 k (整数 >= 0) 使得 f1 = k * f2
  • N 中没有 k 使得 f1 = k * f3

更重要的是，f1 和 f2 是特殊的，因为 f2 为您提供了 f1 从同一点开始给出的子序列。那么由于两个 f1 序列如果不在同一点开始（认为是平行的）就永远不会交叉，那么自然 f2 也不会交叉 f1！

您还可以看到相反的情况，因为 f3 不是 f1 的子序列（即 f3 不是 f1 的除数），那么在 Z（整数）中存在 i,j 使得 i f1 + j f3 = 1，虽然我不记得这是来自哪个定理。这意味着无论两个子序列从哪个位置开始，我实际上都可以找到碰撞。

这也意味着如果你只能有几帧，你可以逃脱 f1 = 29 和 f3 = 27，但如果你继续走足够长的时间，最终它们会发生冲突（尽管目前预测而不是计算它超出了我的能力） .

简而言之：选择一个“主”频率（您想要的所有频率中最快的），然后只选择该频率的除数，无论视频的长度如何，您都可以。

于 2009-10-06T17:31:01.927 回答