🚧 🚀 🦂 程序员需要数学，或者我必须解决的问题 👩🏿‍🤝‍👨🏾 🍌 🎬

你好！

我正在研究WebRTC-音频视频会议（或呼叫？换句话说-实时通信）的框架。在本文中，我想描述一个有趣的问题及其解决方法。实际上，在该问题中，需要通过附加限制来最小化几个实数的lcm。我不得不运用大量的数论或至少是逻辑。

如果您仅对问题感兴趣，则可以安全地跳到“问题的形成”部分。下一节将说明它的来源和含义。

介绍

客户端可以配置WebRTC一次对输入流进行多种分辨率的编码。例如，这在视频会议中很有用：每个客户端以不同的分辨率和比特率将多个流发送到服务器，而服务器仅将适合客户端带宽的流发送给其他所有人。

但是您不能只设置所需的权限，不，那太容易了。事实是，信号源（例如镀铬的相机）可以产生任何分辨率的视频。还有一种反馈机制，在CPU上负载较高时，传入的分辨率会降低。简而言之，用户设置比例因子 $S_i \ ge 1.0$ 。然后，将传入帧压缩指定的次数，进行编码并通过网络发送给接收者。

问题是某些编码器无法处理任意图像-它们肯定需要均匀大小。如果不同图像的分辨率比较完整，则编码时还会进行各种优化。最重要的是，如果不同的流具有不同的宽高比，则在它们之间切换时会产生非常明显的混响。因此，有必要将输入分辨率完全除以所有系数。

实现此目的的最有效方法是要求将源许可划分为指定数量：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$

: $\ Mathbb {N}中的一个\ \ MaxA，\ A \ le MaxA中的\ S'_i \ \ Mathbb {R}中的一个\ S'_i \ ge 1，\ i = 1..n$

$\ sum_ {i = 1} ^ n \左（S_i -S'_i \右）^ 2 \ rightarrow分钟$ $\ frac {A} {S'_i \ cdot d} \ in \ mathbb {N}，i = 1..n \ \ \ \ \ \ \ \ \（1）$

: - , , .

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

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

( : ).

. D_i , . $N_i \版本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）$

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), , , . . (6) , .

. , , 0, $k ^ * = \ frac {A} {S_i \ cdot d}$ . , 2 $k =最小值\ {\ 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;
}

, , . , . , .

是的，如果没有数学知识，您仍然可以说服自己自己，该代码发出的系数将适合问题的情况（分子将计算出的对齐方式相除，因此可以完全共享所有内容，分母可以通过编码器所需的对齐方式进行除数分解）。但是如果没有推理链（1）=>（4），（5），通常不清楚该代码如何找到最佳解决方案。

程序员需要数学，或者我必须解决的问题

介绍

More articles: