🔶 🕳️ 🔪 Os programadores precisam de matemática, ou um problema que eu tive que resolver 🧚🏾 🕴🏻 🔰

Olá!

Estou trabalhando no WebRTC - uma estrutura para áudio-videoconferência (ou chamadas? Em outras palavras - comunicação em tempo real). Neste artigo, quero descrever um problema interessante e como ele foi resolvido. No problema, de fato, era necessário minimizar o lcm de vários números reais com restrições adicionais. Tive de aplicar um pouco da teoria dos números ou, pelo menos, da lógica.

Se você está interessado apenas no problema, pode pular com segurança para a seção "Formulação do problema". A próxima seção explica de onde veio e qual é seu significado.

Introdução

Os clientes podem configurar o WebRTC para codificar o fluxo de entrada em várias resoluções ao mesmo tempo. Por exemplo, isso pode ser útil em videoconferência: cada cliente envia vários fluxos para o servidor com diferentes resoluções e taxas de bits, e o servidor envia para todos os outros apenas o fluxo que se encaixa na largura de banda do cliente.

Mas você não pode simplesmente definir as permissões desejadas, não - isso seria muito fácil. O fato é que uma fonte (por exemplo, uma câmera cromada) pode produzir vídeo de qualquer resolução. E também há um mecanismo de feedback, e com uma alta carga na CPU, a resolução de entrada diminui. Resumindo, o usuário define os fatores de escala $S_i \ ge 1.0$ . Em seguida, o quadro de entrada é compactado um número especificado de vezes, codificado e enviado pela rede aos destinatários.

O problema é que alguns codificadores não funcionam com imagens arbitrárias - eles definitivamente precisam de tamanhos uniformes. E também há todos os tipos de otimizações durante a codificação, se a proporção de resolução para imagens diferentes for total. E o mais importante, se diferentes streams têm diferentes proporções de aspecto, ao alternar entre eles haverá um solavanco muito perceptível. Portanto, é necessário que a resolução de entrada seja completamente dividida por todos os 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)$

: - , , .

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

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

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

UMA

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

, , . , . , .

Sim, sem matemática, você ainda pode se convencer de que os coeficientes emitidos por este código se encaixam na condição do problema (o numerador divide o alinhamento calculado, então compartilhe tudo inteiramente, e o denominador dá divisibilidade pelo alinhamento necessário para o codificador). Mas sem a cadeia de raciocínio (1) => (4), (5) geralmente não está claro como esse código encontra a solução ótima.

Os programadores precisam de matemática, ou um problema que eu tive que resolver

Introdução

More articles: