プログラマーには数学、または私が解決しなければならなかった問題が必要です

こんにちは！

私はWebRTCに取り組んでいます。これは、オーディオビデオ会議（または通話？つまり、リアルタイム通信）のフレームワークです。この記事では、興味深い問題とそれがどのように解決されたかについて説明したいと思います。実際、この問題では、いくつかの実数のlcmを最小化する必要がありましたが、追加の制限がありました。私はかなりの数の理論または少なくとも論理を適用しなければなりませんでした。

問題のみに関心がある場合は、「問題の定式化」のセクションに安全にスキップできます。次のセクションでは、それがどこから来たのか、そしてその意味は何であるかを説明します。

前書き

クライアントは、着信ストリームを複数の解像度で一度にエンコードするようにWebRTCを構成できます。たとえば、これはビデオ会議で役立ちます。各クライアントは、異なる解像度とビットレートで複数のストリームをサーバーに送信し、サーバーは、クライアントの帯域幅に適合するストリームのみを他のすべてのユーザーに送信します。

ただし、必要な権限を設定するだけでは不十分です。簡単すぎるでしょう。事実、ソース（たとえば、クロムのカメラ）は任意の解像度のビデオを生成できます。また、フィードバックメカニズムもあり、CPUの負荷が高いと、着信分解能が低下します。つまり、ユーザーがスケーリング係数を設定します。 次に、着信フレームが指定された回数圧縮され、エンコードされてネットワーク経由で受信者に送信されます。

問題は、一部のエンコーダーが任意の画像で機能しないことです-それらは間違いなく均一なサイズを必要とします。また、さまざまな画像の解像度比が全体である場合、エンコード時にあらゆる種類の最適化が行われます。そして最も重要なことは、異なるストリームのアスペクト比が異なる場合、それらを切り替えるときに非常に目立つジャークが発生することです。したがって、入力解像度をすべての係数で完全に除算する必要があります。

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

:

:

:

: - , , .

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

- , (1), . i- .

, , . .

, :

(1) ,

( : ).

. , . ,

, (2) :

(3) :

, :

(3) (4):

, 1 ( ) :

, (1) (5) (6), , , . . (6) , .

. , , 0, . , 2 . , - , . . , (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）、このコードがどのように最適な解決策を見つけるかは一般に不明確です。