Broadcasting audio/video/audio & video. FFmpeg + FFserver

FFmpeg - достаточно мощная утилита, кроссплатформенная, поддерживает множество кодеков.
В сети достаточно много различных инструкций по использованию, я постараюсь расписать всё простым языком, с пошаговыми действиями, и своими заметками и опытом. :)

Официальный сайт проекта FFmpeg
Про то как кодировать аудио/видео можно почитать тут: http://nix-sa.blogspot.com/2012/02/ffmpeg.html

Если вкратце, то FFmpeg - берёт входные данные (как самые обычные файлы, так и удалённый поток), и отправляет в другом формате (если это надо) или в файл, или в поток.
FFserver - исходя из названия уже понятно, что это сервер на котором будет происходить получение данных с FFmpeg источников, буферизировать данные, перенаправлять поток,  и давать возможность получать данные устройствам через плеер (я использовал FFplay, а так же VLC).
Что касается плеера: искать нужно под свой формат и кодек. Я использовал G722. VLC отказался проигрывать этот формат, но на счастье, "родной" FFplay его подхватил (если в параметрах FFplay явно не указать g722, он работать не будет, о запуске - ниже).
G722 формат честно говоря, достаточно не плох. Качество звука хорошее, и не сильно забивает сеть.

В интернете видел вопросы людей о том что при трансляции аудио в g722 звук в два раза медленней: сам столкнулся с этим, решение заключается в том, чтобы просто правильно указать битрейт и сэмплрейт. :)


Чтобы не разбивать статью на много небольших, соберу всё здесь:

Начнём про связку FFmpeg + FFserver.

Сперва почитаем https://trac.ffmpeg.org/wiki/Streaming%20media%20with%20ffserver

Скачаем и установим пакет FFmpeg (apt-get install ffmpeg или opkg install ffmpeg или ...)
(How install ffmpeg)

Далее заходим в /etc/ и редактируем/создаём файл ffserver.conf
Пример конфигурационного файла http://ffmpeg.org/sample.html

Запускаем ffmpeg, который будет перенаправлять поток с микрофона в feed ffserver-а (возможно перекодирование).

Начинает работать ffmpeg, если вы не установили флаг запуска daemon-а в фоновом режиме, и вы работаете через терминал, то запустите вторую сессию и запустите ffserver (если конфигурационный файл лежит не в /etc/ffserver.conf, то ffserver -f *ваш путь*)

Подробней можно почитать на официальном сайте.

FFmpeg и сразу в сеть

Мой скрипт для запуска:

#!/bin/bash
############### Uni/Multu cast stream
#ffmpeg -d -f oss -i /dev/dsp -f g722 -ac 1 -ab 8 -ar 16000 \

#-acodec g722 rtp://192.168.80.4:1234

ffmpeg -d -f oss -i /dev/dsp -f g722 -ac 1 -ab 8 -ar 16000 \

-acodec g722 rtp://224.1.1.1:1234 /usb_flash/out.g722

Скрипт для прослушивания:

ffplay.exe -f rtp -acodec g722 -ar 8000 -ab 8k rtp://127.0.0.1:1234

Knapsack problem

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. (Wikipedia)

1. Когда каждый тип предмета можно брать неограниченное количество раз:

Рассмотрим следующую функцию. Пусть F(s, n) есть максимальная стоимости предметов, которые можно уложить в рюкзак максимальной вместимости n, если можно использовать только первые s предметов из заданных k.

Зададим краевые значения функции F(s, n).

Если s = 0, то F(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0).

Если n = 0, то F(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).

Теперь составим рекуррентное соотношение в общем случае. Необходимо из предметов с номерами 1, ..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак.

Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1, ..., s - 1, следовательно, F(s, n) = F(s - 1, n).

Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - ws, а от добавления предмета s общая стоимость рюкзака увеличивается на ps. Значит, F(s, n) = F(s - 1, n - ws) + ps. Теперь из двух возможных вариантов составить рюкзак массы, не превосходящей n, из предметов 1, ..., s нужно выбрать наилучший:

F(s, n) = max ( F(s - 1, n), F(s - 1, n - ws) + ps ).

Теперь составим программу. Будем считать, что веса предметов хранятся в массиве w[1], ..., w[k], а их стоимости в массиве p[1], ..., p[k]. Значения функции F(s, n), где 0<=s<=k, 0<=n<=W, будем хранить в массиве F[k+1][W+1].

int F[k+1][W+1];
for(n=0;n<=W;++n)       // Заполняем нулевую строчку
    F[0][n]=0;
for(s=1;s<=k;++s)       // s - максимальный номер предмета, 
{                       // который можно использовать
    for(n=0;n<=W;++n)   // n - вместимости рюкзака
    {
        F[s][n]=F[s-1][n]; 
        if ( n>=w[s] && ( F[s-1][n-w[s]]+p[s] > F[s][n]) )
            F[s][n] = F[s-1][n-w[s]]+p[s];
    }
}

В результате исполнения такого алгоритма в элементе массива F[k][W] будет записан ответ на поставленную задачу. Легко видеть, что сложность этого алгоритма, равно как и объем используемой им памяти, являются величиной O(kW).

Рассмотрим пример работы этого алгоритма. Пусть максимальная вместимость рюкзака W = 15, количество предметов k = 5, их стоимости и массы таковы:
w1 = 6, p1 = 5, w2 = 4, p2 = 3, w3 = 3, p3 = 1,
w4 = 2, p4 = 3, w5 = 5, p5 = 6.

В приведенной ниже таблице указаны значения заполненного массива F[k+1][W+1].

2. Когда надо получить не только стоимость, но и сам набор:

Сравним значение F[k][W] со значением F[k-1][W]. Если они равны, то максимальный рюкзак можно составить без использования предмета с номером k. Если не равны, то предмет c номером k обязательно входит в максимальный рюкзак. В любом случае, задача печати рюкзака сводится к задаче печати рюкзака для меньшего числа предметов. Напишем это в виде рекурсивной функции Print(int s, int n), которая по параметрам s и n печатает номера предметов, входящих в максимальный рюкзак массой не более n и составленный из предметов 1, ..., s:

void Print(int s, int n) {
  if (F[s][n]==0) // максимальный рюкзак для параметров (s,n)
    return;        // имеет нулевую ценность, 
                   // поэтому ничего не выводим
  else if (F[s-1][n] == F[s][n]) 
    Print(s-1,n);  // можно составить рюкзак без предмета s
  else
  {                               
    Print(s-1,n-w[s]); // Предмет s должен обязательно 
    cout<<s<<endl;     // войти в рюкзак
  }
}

3. Когда каждую вещь можно брать только один раз:

Тут всё ещё проще: надо просто в каждой итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[n-w[s]], там всё ещё будет записано, набор какой максимальной стоимости веса n — w[s] можно получить, используя только вещи 0..s-1. Следовательно, если получится, что в оптимальном наборе надо использовать s-тую вещь, то она будет использована только один раз.

4. Выбор значения, как можно более близкого к данному:

Если нет стоимости, то данный алгоритм, очевидно, помогает как можно сильнее набить рюкзак. Или же, если речь идёт не о рюкзаке, и неважно, что общий объём вещей не больше объёма рюкзака, можно из нескольких чисел с помощью сложения получить число, как можно более близкое к данному.

В всех случаях ассимптотика времени работы и используемой памяти та же.

5. Когда каждую вещь можно брать определённое количество раз:

Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.

Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)

Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.

Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.