1

アルゴリズムだけでは解決できないこの問題を抱えています。

ビデオ フレームを常に固定レート F (1 秒あたり 30 フレームとしましょう) でキャプチャするビデオ キャプチャがあるとします。

私が望むのは、このフレーム シーケンスを n 個 (たとえば 4 個) のサブシーケンスに「分割」することです。各サブシーケンスにはフレームレート 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」で 1 秒が再開するまでに MCD (30,8) = 120 フレームかかります)。

問題は、サブシーケンスが衝突できないことです。したがって、F=30、f1 = 10 fps (3 フレームごと)、f2 = 5 fps (6 フレームごと) の場合、このシーケンスは問題ありません。

102100 (again, in a second: 102100102100102100102100102100)

しかし、f3 = 6 fps を追加すると

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

また

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

3 番目のサブシーケンスは最初のサブシーケンスと衝突します。

質問は：

  • 衝突せず、等間隔になる n (n <= 4) サブシーケンスのフレームレートのすべての組み合わせを見つける方法はありますか?

（一般的なケースが必要ですが、この特定のケースでは、1つのシーケンスのみ（自明）のすべての有効な組み合わせ、2つのシーケンスのすべての有効な組み合わせ、3つのシーケンスのすべての有効な組み合わせ、および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 の場合、競合しないそれらの配置を見つけることはできません。(たとえば、2 つの素数の場合を考えてみましょう。gcd(p1,p2) は常に 1 であり、オフセット方法に関係なく <=p1*p2 フレームで常に競合します)

于 2009-10-07T00:40:21.703 に答える
1

料金を確認すると、次のようにコメントすることになります。

  • f1 = k * f2 となるような k が N (整数 >= 0) に存在する
  • f1 = k * f3 となるような k は N にありません

さらに言えば、f1 と f2 は特殊であり、f2 は f1 が同じポイントから始まる部分シーケンスを提供します。次に、2 つの f1 シーケンスが同じポイントで始まらない場合 (平行と考えてください)、交差することはないため、当然、f2 も f1 を交差することはありません!

f3 は f1 のサブシーケンスではない (つまり、f3 は f1 の約数ではない) ため、逆が成立することもわかります。その場合、i f1 + j f3 = 1 となるような i,j が Z (整数) に存在します。これがどの定理からのものか思い出せませんが。これは、両方のサブシーケンスの開始位置に関係なく、実際に衝突を見つけることができることを意味します。

また、フレームが数個しかない場合は f1 = 29 と f3 = 27 で済むことも意味しますが、十分に長く続けると、最終的には衝突します (ただし、予測して計算しないことは、現時点では私を超えています)。 .

要するに、1 つの「マスター」周波数 (必要なすべての周波数の中で最も速い周波数) を選択し、この周波数の除数のみを選択すれば、ビデオの長さに関係なく問題ありません。

于 2009-10-06T17:31:01.927 に答える