🌯 🖱️ 🐌 Los programadores necesitan matemáticas o un problema que tuve que resolver 🧓🏻 🥂 🤢

¡Hola!

Estoy trabajando en WebRTC , un marco para conferencias de audio y video (¿o llamadas? En otras palabras, comunicación en tiempo real). En este artículo quiero describir un problema interesante y cómo se resolvió. En el problema, de hecho, se requería minimizar el mcm de varios números reales con restricciones adicionales. Tuve que aplicar bastante teoría de números o al menos lógica.

Si solo está interesado en el problema, puede pasar de forma segura a la sección "Formulación del problema". La siguiente sección explica de dónde vino y cuál es su significado.

Introducción

Los clientes pueden configurar WebRTC para codificar la transmisión entrante en varias resoluciones a la vez. Por ejemplo, esto puede ser útil en videoconferencias: cada cliente envía varios flujos al servidor con diferentes resoluciones y velocidades de bits, y el servidor envía a todos los demás solo el flujo que se ajusta al ancho de banda del cliente.

Pero no puede simplemente establecer los permisos deseados, no, eso sería demasiado fácil. El hecho es que una fuente (por ejemplo, una cámara en cromo) puede producir video de cualquier resolución. Y también hay un mecanismo de retroalimentación, y con una alta carga en la CPU, la resolución entrante disminuye. En resumen, el usuario establece los factores de escala $S_i \ ge 1.0$ . Luego, la trama entrante se comprime un número específico de veces, se codifica y se envía a través de la red a los destinatarios.

El problema es que algunos codificadores no funcionan con imágenes arbitrarias; definitivamente necesitan tamaños iguales. Y también hay todo tipo de optimizaciones al codificar, si la relación de resolución para diferentes imágenes es completa. Y lo más importante, si diferentes transmisiones tienen diferentes relaciones de aspecto, al cambiar entre ellas habrá una sacudida muy notable. Por lo tanto, es necesario que la resolución entrante esté completamente dividida por todos los coeficientes.

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

: - , , .

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

- , (1), . i- .

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

, : MCD (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) :

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

$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), , , . . (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;
}

, , . , . , .

Sí, sin matemáticas, aún puede convencerse de que los coeficientes emitidos por este código se ajustarán a la condición del problema (el numerador divide la alineación calculada, así que comparta todo por completo, y el denominador da divisibilidad por la alineación requerida para el codificador). Pero sin la cadena de razonamiento (1) => (4), (5) generalmente no está claro cómo este código encuentra la solución óptima.

Los programadores necesitan matemáticas o un problema que tuve que resolver

Introducción

More articles: