🆎 🙏🏼 🛒 Programmer membutuhkan matematika, atau masalah yang harus saya selesaikan 🙎🏽 👨‍⚕️ 👩🏾‍🤝‍👨🏿

Halo!

Saya sedang mengerjakan WebRTC - kerangka kerja untuk konferensi audio-video (atau panggilan? Dengan kata lain - komunikasi waktu nyata). Dalam artikel ini saya ingin menjelaskan masalah yang menarik dan bagaimana pemecahannya. Dalam soal, sebenarnya, diperlukan untuk meminimalkan lcm dari beberapa bilangan real dengan pembatasan tambahan. Saya harus menerapkan cukup banyak teori bilangan atau setidaknya logika.

Jika Anda hanya tertarik pada masalahnya, maka Anda dapat melompat ke bagian "Perumusan masalah" dengan aman. Bagian selanjutnya menjelaskan dari mana asalnya dan apa artinya.

pengantar

Klien dapat mengonfigurasi WebRTC untuk mengenkode aliran masuk dalam beberapa resolusi sekaligus. Misalnya, ini dapat berguna dalam konferensi video: setiap klien mengirimkan beberapa aliran ke server dengan resolusi dan kecepatan bit yang berbeda, dan server hanya mengirimkan aliran yang sesuai dengan bandwidth ke klien kepada semua orang.

Tetapi Anda tidak bisa begitu saja mengatur izin yang diinginkan, tidak - itu akan terlalu mudah. Faktanya adalah bahwa sebuah sumber (misalnya, kamera dengan krom) dapat menghasilkan video dengan resolusi berapa pun. Dan ada juga mekanisme umpan balik, dan dengan beban tinggi pada CPU, resolusi yang masuk menurun. Singkatnya, pengguna menetapkan faktor penskalaan $S_i \ ge 1.0$ . Kemudian frame yang masuk dikompresi beberapa kali, dikodekan dan dikirim melalui jaringan ke penerima.

Masalahnya adalah beberapa pembuat enkode tidak bekerja dengan gambar sembarangan - mereka pasti membutuhkan ukuran yang sama. Dan ada juga semua jenis pengoptimalan saat encoding, jika rasio resolusi untuk gambar yang berbeda utuh. Dan yang terpenting, jika aliran yang berbeda memiliki rasio aspek yang berbeda, maka saat beralih di antara aliran tersebut akan ada sentakan yang sangat mencolok. Oleh karena itu, resolusi yang masuk harus benar-benar dibagi dengan semua koefisien.

, , : 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 \ kiri (S_i -S'_i \ right) ^ 2 \ rightarrow menit$ $\ frac {A} {S'_i \ cdot d} \ in \ mathbb {N}, i = 1..n \ \ \ \ \ \ \ \ \ \ (1)$

: - , , .

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

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

( : ).

. T_i D_i , . T_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) SEBUAH :

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

SEBUAH

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

, , . , . , .

Ya, tanpa matematika, Anda masih bisa meyakinkan diri sendiri bahwa koefisien yang dikeluarkan oleh kode ini akan sesuai dengan kondisi soal (pembilang membagi perataan yang dihitung, jadi bagikan semuanya seluruhnya, dan penyebut memberikan pembagian dengan perataan yang diperlukan untuk pembuat enkode). Tetapi tanpa rantai penalaran (1) => (4), (5) umumnya tidak jelas bagaimana kode ini menemukan solusi optimal.

Programmer membutuhkan matematika, atau masalah yang harus saya selesaikan

pengantar

More articles: