Математика нужна программистам, или задача, которую мне пришлось решать19.09.2020 01:03

Всем привет!

Я работаю над WebRTC — фреймворком для аудио-видео конференций (или звонков? проще говоря — real time communication). В этой статье я хочу описать интересную задачу и как она была решена. В задаче, по сути, потребовалось минимизировать 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 (640×480) видео уже не послать вообще никак. На практике — максимально допустимое выравнивание, которое мы можем попросить должно быть ограничено, чтобы, во-первых, допускать маленькие разрешения и, во-вторых, не очень сильно искажать соотношение сторон.

Но, раз уж мы уже немного искажаем настройки пользователя, округляя входящее разрешение, то почему бы и не округлить чуть чуть коэффициенты масштабирования? Например, можно было бы взять коэффициенты {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 . Потому что только рациональные числа можно домножить и поделить на целое и получить в итоге целое.

Можно потребовать, чтобы дробь была неприводимая: 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) для выше:

$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=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 ((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 CalulateAlignmentAndScaleFactors(
    int encoder_alignment, std::vector scale_factors, 
    int *requested_alignment) {
  float best_error = 1e90;
  int best_alignment = 1;
  std::vector best_factors;
  std::vector 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) вообще неясно, как этот код находит оптимальное решение.