Алгоритм скользящего среднего

EatApples

Здравствуйте, начал читать одну книжку для "детей" можно сказать по ЦОС.
Но дураку сложно понять даже такую книгу)

В общем есть там пример одного из самого распространенного алгоритма фильтрации - скользящее среднее.

Вроде понятно в общем идею, но так как нет примера простого, немного не понятно, какие значения берутся именно и как потом записываются обратно, нужно ли это все делать в отдельном буфере, какой буфер отображать в итоге, если берем программную реализацию и подобные вопросы.

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

Буду премного благодарен за любую помощь.

Спасибо

Реклама

mickbell

Самый простой случай фильтрации методом скользящего среднего выполняется так.
Имеется поток данных, поступающих периодически. Имеется также буфер (массив), хранящий несколько, например, десять значений.
Каждый раз при поступлении нового значения самое древнее херится, и таким образом в буфере всегда содержатся десять последних полученных значений. Далее берётся их среднеарифметическое значение и используется.

Реклама

Ivanoff-iv

Да тут ничего сложного запоминается n последних измерений (нужен массив размера n), для нахождения среднего все элементы массива суммируем и делим на n всё.
остаётся правильно заполнить массив: либо сдвигаем значения (последнее значение пропадает) чтобы освободить первую ячейку (в неё запишется свежепоступившее значение), но это долго (все значения приходится перекладывать), быстрее просто вписывать свежее значение в массив "по кругу" когда круг завершится, свежее значение будет затирать самое старое. (остается запомнить номер последней записанной ячейки, чтобы знать куда писать следующее значение)

Добавлено after 53 seconds:
опять опередили...

Добавлено after 3 minutes 8 seconds:
есть ещё Метод экспоненциального сглаживания (его чаще применяют т.к. там массив не нужен) если интересно распишу

El-Eng

Ivanoff-iv писал(а):... быстрее просто вписывать свежее значение в массив "по кругу" когда круг завершится, свежее значение будет затирать самое старое.

Если сделать число элементов n равным степени 2 (n=2^m) то операция добавления нового значения сводится к записи его по адресу указателя, инкременту указателя и операции побитового "и" значения указателя с маской из m единиц (не нужно следить за переполнением). Операция деления на n сводится к операции сдвига вправо на m. Иногда можно просто учесть, что результат умножен на 2^m.

Реклама

Siarzhuk

[uquote="mickbell",url="/forum/viewtopic.php?p=3229487#p3229487"]Далее берётся их среднеарифметическое значение и используется.[/uquote]
Для больших окон усреднения сумму можно считать в отдельной переменной [достаточного размера] - вычитаем из неё выбрасываемое из буффера значение, прибавляем добавляемое значение, делим сумму на размер окна, не забываем про переходный процесс при запуске фильтра.

Реклама

Муркиз

Да зачем так сложно.

Берется один массив, в котором пишутся значения со сдвигом по счетчику. А при расчете делаем выборку нужного количества элементов назад от текущего значения счетчика. На границе массива делаем переход на начало и выборку делаем с учетом перехода.

Ну а для расчета используются либо вспомогательный массив, либо просто набор переменных.

Реализация у меня есть - но только на Паскале. Собственно - даже я тогда просто библиотечную функцию сделал кругового массива для простоты использования.

Реклама

Siarzhuk

[uquote="Муркиз",url="/forum/viewtopic.php?p=3229920#p3229920"]Да зачем так сложно.

Берется один массив, в котором пишутся значения со сдвигом по счетчику. А при расчете делаем выборку нужного количества элементов назад от текущего значения счетчика. На границе массива делаем переход на начало и выборку делаем с учетом перехода.[/uquote]
В жизни, конечно, всегда есть место подвигу, но если взять ваш вариант за основу, сделать ширину массива равной ширине окна усреднения N, то во-первых, обычное деление индекса по модулю избавит нас от необходимости следить за границами массива, во-вторых снимет необходимость морочиться с "обратным заворотом" на начале массива - результат получается суммированием всех элементов массива и делением на их количество - т.е. тот самый уже озвученные в этой теме "сложный" вариант. А поскольку чем шире N -тем больше нас будут неудовлетворять затраты на арифметику (N сложений + 1 деление на точку) - добавление переменной с текущей суммой снизит затраты к (1 вычитание + 1 сложение + 1 деление на точку) которые от N не зависят.

Муркиз

У меня длина выборки минимально требовалось 512 отсчётов.
А заказ предписывал аж до 4к иметь... По ТЗ.

EatApples

Спасибо огромное за ответы.
Наверное немного неправильно задал вопрос, главный вопрос что выдается на выход после этого фильтра и куда мы записываем среднее значение посчитанное на определенной итерации, в массив который мы использовали для счета этого же среднего ?

Вот к примеру читаем данные флоками определенного размера, обычно размер буфера для чтения больше чем окно для скользящего фильтра и блокирующий вызов.

Код: Выделить всё

short* readBuffer = new short[SIZE_OF_READ_BUFFER];
short* avgBuffer = new short[AVARAGE_FILTER_WINDOW_SIZE];
// Блокирующий вызов, зависаем до поступления новых данных
while(isRunning) {
     int result = source.read(readBuffer,0,SIZE_OF_READ_BUFFER);
     // Что делать дальше ?)
}

Ivanoff-iv

[uquote="Муркиз",url="/forum/viewtopic.php?p=3230252#p3230252"]У меня длина выборки... аж до 4к иметь... По ТЗ.[/uquote] можно в несколько этапов делать,исначала, допустим усреднение 16и, а потом усреднение 256 тех усреднённых...

Муркиз

Нет, там была другая задача - выделение сигнала из шума. Для обсчета расфокусированных реперов. Дробить выборки нельзя.