Ein Algorithmus zum Aufteilen einer Sequenz in gleichmäßig verteilte, nicht kollidierende Teilsequenzen

Question

Ich habe dieses Problem, das ich nicht einfach algorithmisch lösen kann.

Nehmen wir an, ich habe eine Videoaufnahme, die immer Videobilder mit einer festen Rate F (sagen wir 30 Bilder pro Sekunde) aufnimmt.

Ich möchte diese Bildsequenz in n (sagen wir vier) Teilsequenzen „aufteilen“.Jede Teilsequenz hat ihre Framerate fn, die offensichtlich < F ist.Frames in einer Teilsequenz haben den gleichen zeitlichen Abstand, sodass beispielsweise eine gültige 10-fps-Sequenz f1 für F = 30 fps und Zeit = 1 Sekunde wie folgt aufgebaut wird:

(0en sind Frames, die nicht zur Teilsequenz gehören, 1en sind Frames, die dazu gehören):

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

oder

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

oder für F = 30 und f = 8:

100000001

(und es würde MCD (30,8) = 120 Frames dauern, bevor eine Sekunde mit einer „1“ neu startet).

Das Problem besteht darin, dass Teilsequenzen nicht kollidieren können. Wenn also F=30, f1 = 10 fps (alle drei Bilder) und f2 = 5 fps (alle sechs Bilder), ist diese Sequenz in Ordnung:

102100 (again, in a second: 102100102100102100102100102100)

Aber wenn wir f3 = 6 fps hinzufügen

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

oder

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

Die dritte Teilsequenz würde mit der ersten kollidieren.

Die Frage ist:

• Gibt es eine Möglichkeit, es zu finden? jeden Kombination der Frameraten der n (mit n <= 4) Teilsequenzen, die nicht kollidieren und den gleichen Abstand haben würden?

(Ich brauche den allgemeinen Fall, aber in diesem speziellen Fall bräuchte ich alle gültigen Kombinationen nur für eine Sequenz (trivial), alle gültigen Kombinationen für zwei Sequenzen, alle gültigen Kombinationen von drei Sequenzen und alle für vier Sequenzen.) .

Ich hoffe, jemand könnte mich aufklären.Danke schön!

Answer 1

Wenn Sie sich Ihre Tarife ansehen, werden Sie Folgendes bemerken:

• Es gibt k in N (Ganzzahlen >= 0), so dass f1 = k * f2
• Es gibt kein k in N, sodass f1 = k * f3

Genauer gesagt sind f1 und f2 insofern etwas Besonderes, als f2 Ihnen eine Teilfolge dessen liefert, was f1 ab demselben Punkt liefern würde.Da sich dann zwei f1-Sequenzen niemals kreuzen würden, wenn sie nicht am selben Punkt beginnen (denken Sie parallel), dann wird f2 natürlich auch f1 nicht kreuzen!

Sie können auch sehen, dass das Gegenteil gilt, da f3 keine Teilfolge von f1 ist (dh f3 ist kein Teiler von f1), dann gibt es i,j in Z (Ganzzahlen), so dass if1 + jf3 = 1, obwohl ich mich nicht erinnern kann, aus welchem ​​Satz dieser stammt.Das bedeutet, dass ich tatsächlich eine Kollision finden kann, unabhängig von der Position, von der aus beide Teilsequenzen beginnen.

Es bedeutet auch, dass Sie mit f1 = 29 und f3 = 27 durchkommen könnten, wenn Sie nur ein paar Frames hätten, aber letztendlich werden sie kollidieren, wenn Sie lange genug weitermachen (obwohl es mir im Moment schwer fällt, das vorherzusagen und nicht zu berechnen). .

---

Zusamenfassend:Wählen Sie eine „Master“-Frequenz (die schnellste aller gewünschten) und nehmen Sie dann nur Teiler dieser Frequenz auf, und Sie werden in Ordnung sein, unabhängig von der Länge Ihres Videos.

Answer 2

Ich glaube, dies würde es für den 4 -Stream -Fall tun, und es sollte offensichtlich sein, was für die weniger Stream -Fälle zu tun sind.

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

Grundsätzlich, welche Frequenzen, die Sie in Betracht ziehen, 1) Sie können nicht mehr als den gesamten Stream 2) Wenn ihr größter gemeinsamer Nenner <4 ist, können Sie keine Anordnung von ihnen finden, die nicht konflikt. (Betrachten Sie beispielsweise den Fall von zwei Primzahlen; GCD (P1, P2) ist immer 1, und sie werden immer in <= p1*p2 -Frames konflikt, unabhängig davon, wie Sie sie ausgleichen)