🆘 🧘🏻 🚳 Les programmeurs ont besoin de mathématiques ou d'un problème que je devais résoudre 👨🏻‍⚖️ 👦 👩🏿‍🤝‍👩🏽

salut!

Je travaille sur WebRTC - un cadre pour la conférence audio-vidéo (ou les appels? En d'autres termes - la communication en temps réel). Dans cet article, je veux décrire un problème intéressant et comment il a été résolu. Dans le problème, en fait, il était nécessaire de minimiser le lcm de plusieurs nombres réels avec des restrictions supplémentaires. J'ai dû appliquer pas mal de théorie des nombres ou du moins de logique.

Si vous n'êtes intéressé que par le problème, vous pouvez passer en toute sécurité à la section «Formulation du problème». La section suivante explique d'où il vient et quelle est sa signification.

introduction

Les clients peuvent configurer WebRTC pour encoder le flux entrant dans plusieurs résolutions à la fois. Par exemple, cela peut être utile en visioconférence: chaque client envoie plusieurs flux au serveur avec différentes résolutions et débits binaires, et le serveur envoie à tous les autres uniquement le flux qui correspond à la bande passante du client.

Mais vous ne pouvez pas simplement définir les autorisations souhaitées, non - ce serait trop facile. Le fait est qu'une source (par exemple, une caméra en chrome) peut produire une vidéo de n'importe quelle résolution. Et il y a aussi un mécanisme de rétroaction, et avec une charge élevée sur le processeur, la résolution entrante diminue. En bref, l'utilisateur définit les facteurs de mise à l'échelle $S_i \ ge 1.0$ . Ensuite, la trame entrante est compressée un nombre spécifié de fois, codée et envoyée sur le réseau aux destinataires.

Le problème est que certains encodeurs ne fonctionnent pas avec des images arbitraires - ils ont certainement besoin de tailles égales. Et il y a aussi toutes sortes d'optimisations lors de l'encodage, si le rapport de résolution des différentes images est entier. Et surtout, si différents flux ont des rapports hauteur / largeur différents, lors du passage de l'un à l'autre, il y aura une secousse très perceptible. Par conséquent, il est nécessaire que la résolution entrante soit complètement divisée par tous les coefficients.

, , : 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)$

: - , , .

, - -. UNE . MaxA MaxA ( 16). - UNE , .

- , (1), . i- .

$A / (S'_i \ cdot d), A, d \ in \ mathbb {N}$ , , $S'_i \ dans \ 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) UNE :

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

UNE

$d \ vert f \ cdot D_i$

, :

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

(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)$

, 1 ( ) :

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

, (1) (5) (6), , UNE , . . (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;
}

, , . , . , .

Oui, sans maths, vous pouvez toujours vous convaincre que les coefficients émis par ce code correspondront à la condition du problème (le numérateur divise l'alignement calculé, partagez donc tout entièrement, et le dénominateur donne la divisibilité par l'alignement requis pour l'encodeur). Mais sans la chaîne de raisonnement (1) => (4), (5), on ne sait généralement pas comment ce code trouve la solution optimale.

Les programmeurs ont besoin de mathématiques ou d'un problème que je devais résoudre

introduction

More articles: