🈯️ ❌ ⚛️ Programmierer brauchen Mathematik oder ein Problem, das ich lösen musste 🌙 🛌 ♦️

Hallo!

Ich arbeite an WebRTC - einem Framework für Audio-Video-Konferenzen (oder Anrufe? Mit anderen Worten - Echtzeit-Kommunikation). In diesem Artikel möchte ich ein interessantes Problem beschreiben und wie es gelöst wurde. Bei dem Problem war es tatsächlich erforderlich, die lcm mehrerer reeller Zahlen mit zusätzlichen Einschränkungen zu minimieren. Ich musste einiges an Zahlentheorie oder zumindest Logik anwenden.

Wenn Sie nur an dem Problem interessiert sind, können Sie sicher zum Abschnitt "Formulierung des Problems" springen. Im nächsten Abschnitt wird erklärt, woher es kommt und was es bedeutet.

Einführung

Clients können WebRTC so konfigurieren, dass der eingehende Stream in mehreren Auflösungen gleichzeitig codiert wird. Dies kann beispielsweise bei Videokonferenzen hilfreich sein: Jeder Client sendet mehrere Streams mit unterschiedlichen Auflösungen und Bitraten an den Server, und der Server sendet an alle anderen nur den Stream, der in die Bandbreite passt, an den Client.

Aber Sie können nicht einfach die gewünschten Berechtigungen festlegen, nein - das wäre zu einfach. Tatsache ist, dass eine Quelle (z. B. eine Kamera in Chrom) Videos mit beliebiger Auflösung erzeugen kann. Außerdem gibt es einen Rückkopplungsmechanismus, und bei hoher Belastung der CPU nimmt die eingehende Auflösung ab. Kurz gesagt, der Benutzer legt die Skalierungsfaktoren fest $S_i \ ge 1.0$ . Anschließend wird der eingehende Frame eine bestimmte Anzahl von Malen komprimiert, codiert und über das Netzwerk an die Empfänger gesendet.

Das Problem ist, dass einige Encoder nicht mit beliebigen Bildern arbeiten - sie benötigen definitiv gerade Größen. Und es gibt auch alle Arten von Optimierungen beim Codieren, wenn das Auflösungsverhältnis für verschiedene Bilder ganz ist. Und was am wichtigsten ist: Wenn verschiedene Streams unterschiedliche Seitenverhältnisse haben, tritt beim Umschalten zwischen ihnen ein sehr deutlicher Ruck auf. Daher ist es notwendig, dass die eingehende Auflösung vollständig durch alle Koeffizienten geteilt wird.

, , : alignment. , {1.0, 2.0, 4.0} , alignment=8. - . , . , , 8 1, 2 4 , .

, {1, 1.7, 2.3}? , "" - 391. , 782. , , 782. , VGA (640x480) . - , , , -, , -, .

, , , ? , {1, 1.6, 2.4} {1, 1.7, 2.3} 48 ( 782). , .

: $d \ in \ mathbb {N}, \ S_i \ ge 1, S_i \ in \ mathbb {R}, i = 1..n$

: $A \ in \ mathbb {N}, \ A \ le MaxA, \ S'_i \ in \ mathbb {R}, \ S'_i \ ge 1, \ i = 1..n$

$\ sum_ {i = 1} ^ n \ left (S_i -S'_i \ right) ^ 2 \ rightarrow min$ $\ frac {A} {S'_i \ cdot d} \ in \ mathbb {N}, i = 1..n \ \ \ \ \ \ \ \ \ (1)$

: - , , .

, - -. EIN . MaxA MaxA ( 16). - EIN , .

- , (1), . i- .

$A / (S'_i \ cdot d), A, d \ in \ mathbb {N}$ , , $S'_i \ in \ mathbb {Q}$ S'_i = N_i / D_i . .

, : GCD (N_i, D_i) = 1

(1) $\ frac {A \ cdot D_i} {N_i \ cdot d} \ in \ mathbb {N}$ ,

$N_i \ cdot d \ vert A \ cdot D_i \ \ \ \ \ \ \ (2)$

( : ).

. N_i D_i , . N_i $N_i \ vert A.$ ,

$A = N_i \ cdot f, \ f \ in \ mathbb {N} \ \ \ \ \ \ (3)$

, (2) :

$f \ cdot N_i \ cdot d \ vert f \ cdot A \ cdot D_i$

(3) EIN :

$A \ cdot d \ vert f \ cdot A \ cdot D_i$

EIN

$d \ vert f \ cdot D_i$

, :

$f \ cdot D_i = k \ cdot d, k \ in \ mathbb {N} \ \ \ \ \ \ \ \ \ \ (4)$

S'_i (3) (4):

$S'_i = \ frac {N_i \ cdot f} {D_i \ cdot f} = \ frac {A} {f \ cdot D_i} = \ frac {A} {k \ cdot d}, \ \ k \ in \ mathbb {N} \ \ \ \ \ \ \ \ (5)$

, S'_i 1 ( ) :

$k \ le \ frac {A} {d} \ \ \ \ \ \ \ (6)$

, (1) (5) (6), , EIN , . . (6) , .

. , , 0, $k ^ * = \ frac {A} {S_i \ cdot d}$ . , 2 $k = min \ {\ lfloor k ^ * \ rfloor, \ \ lceil k ^ * \ rceil \}$ . , - , . . , (6).

, ( ):

const int kMaxAlignment = 16;

//    scale_factor (S_i)   
//   (d)     (A).
//     error_acc.
float GetApprox(int encoder_alignment, int requested_alignment, 
                float scale_factor, float *error_acc) {
  int k = static_cast<int> ((requested_alignment + 0.0) / 
                            (encoder_alignment * scale_factor));
  float best_error = 1e90;
  float best_approx = 1.0;
  for (int i = 0; i < 2; i++, k++) {
    if (k == 0 || k * encoder_alignment > requested_alignment) continue;
    float approx = (requested_alignment +0.0) / (k * encoder_alignment);
    float error = (approx - scale_factor) * (approx - scale_factor);
    if (error < best_error) {
      best_error = error;
      best_approx = approx;
    }
  }
  *error_acc += best_error;
  return best_approx;
}

//  .    (S'_i)
//    (A)   requested_alignment.
std::vector<float> CalulateAlignmentAndScaleFactors(
    int encoder_alignment, std::vector<float> scale_factors, 
    int *requested_alignment) {
  float best_error = 1e90;
  int best_alignment = 1;
  std::vector<float> best_factors;
  std::vector<float> cur_factors;
  
  for (int a = 1; a <= kMaxAlignment; ++a) {
    float cur_error = 0;
    cur_factors.clear();
    for (float factor: scale_factors) {
      float approx = GetApprox(encoder_alignment, a, factor, &cur_error);
      cur_factors.push_back(approx);
    }
    if (cur_error < best_error) {
      best_error = cur_error;
      best_factors = cur_factors;
      best_alignment = a;
    }
  }
  *requested_alignment = best_alignment;
  return best_factors;
}

, , . , . , .

Ja, ohne Mathematik können Sie sich immer noch davon überzeugen, dass die von diesem Code ausgegebenen Koeffizienten dem Zustand des Problems entsprechen (der Zähler teilt die berechnete Ausrichtung, teilen Sie also alles vollständig, und der Nenner gibt die Teilbarkeit durch die erforderliche Ausrichtung für den Encoder). Ohne die Argumentationskette (1) => (4), (5) ist jedoch im Allgemeinen unklar, wie dieser Code die optimale Lösung findet.

Programmierer brauchen Mathematik oder ein Problem, das ich lösen musste

Einführung

More articles: