Easyelectronics.ru

Электроника для всех
Текущее время: 24 сен 2020, 08:01

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/5шт. два слоя. $5/5шт. четыре слоя
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 12:59 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2795
Откуда: Санкт-Петербург
arhiv_6 писал(а):
VladyMile писал(а):
А нет ли у вас готового алгоритма (идеально - кода на Сях для МК :) ) для простого (на 5 точек, например) медианного фильтра?
Мне с нуля такие вещи писать самому пока рано - надо сначала почитать и посмотреть.
А то примеры нахожу какие-то .... м-м-м... замысловатые.

Алгоритм простейший, не бойтесь написать его с нуля. Сортируете массив M из n элементов по возрастанию или убыванию (функция qsort из стандартной библиотеки) и берёте M[n/2] элемент массива если n нечётное. И всё, это и есть результат. Если n чётное - берите среднее от двух цетнральных элементов массива: (M[n/2] + M[(n/2)+1])/2

ААААА!!! медиана! через сортировку массива! qsort! Почему этого человека нельзя просто уволить нахрен?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 13:18 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
VladyMile писал(а):
А нет ли у вас готового алгоритма (идеально - кода на Сях для МК :) ) для простого (на 5 точек, например) медианного фильтра?

https://embeddedgurus.com/stack-overflo ... filtering/


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 13:23 
Старожил

Зарегистрирован: 15 янв 2018, 18:52
Сообщения: 854
http://geekmatic.in.ua/filtracia_shumov ... go_signala вот для дуины вроде понятная реализация 2х фильтров


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 13:29 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
mazahakka v2.0 писал(а):
http://geekmatic.in.ua/filtracia_shumov_analogovogo_signala вот для дуины вроде понятная реализация 2х фильтров

Сортировка пузырьком явно не способствует быстродействию.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 20:12 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2795
Откуда: Санкт-Петербург
evsi, самое смешное, что для бегущей медианы лучше уж за основу взять сортировку пузырьком (а ещё лучше - вставками), чем квиксорт: нужно не N проходов, а 1-2 (массив уже был отсортирован, один элемент убрали, один добавили), сложность O(N), а не O(N^2), как для полновесного пузырька, или O(N*log(N)), как для qsort.

Кстати, полный поиск медианы в массиве тоже делается за O(N), а не за O(N*log(N)). Один из алгоритмов - типа quicksort, только нам не надо сортировать весь массив. Для поиска i-го по порядку элемента из N делим массив на две части, как в quicksort, смотрим, в какой из частей и каким по порядку он будет, и повторяем процедуру там.

Ну и то, что полная сортировка не нужна, позволяет ещё ускорить алгоритм (я там выше постил ссылку) и находить очередное значение за O(log(N)).

VladyMile, я потом постараюсь поискать нормальную реализацию (писать из головы лень - надо ж проверять как следует), ну или погуглите сами (fast running median). Все реализации, в которых вызывается сортировка, можете сразу пропускать - это просто иллюстрации.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 22:11 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
aamonster писал(а):
evsi, самое смешное, что для бегущей медианы лучше уж за основу взять сортировку пузырьком (а ещё лучше - вставками), чем квиксорт:

Я вообще не очень люблю квиксорт из-за вырожденных случаев. Причем для уже отсортированых данных его поведение хуже всего. Но на самом деле лучше брать алгоритмы, которые вообще не используют сортировку. Алгоритм с двумя хипами легко гуглится, я нашел, по крайней мере, с полдюжины реализаций. Даже одну из них поправил под свои нужды. Если кому будет интересно, могу выложить на гитхаб. Правда, там плюсы, шаблоны и все такое.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 12 сен 2018, 23:56 
Старожил

Зарегистрирован: 15 янв 2018, 18:52
Сообщения: 854
мне кажется самый идеальный вариант - когда код доступен и он читабелен/хорошо комментирован - ну а дальше можно вести хоть какое-то обсуждение - в идеале конечно глянуть бы статейку с разными подходами реализации одного фильтра. например того же медианного и какие-нить сравнительные тесты производительности мк :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 13 сен 2018, 08:36 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
mazahakka v2.0 писал(а):
мне кажется самый идеальный вариант - когда код доступен и он читабелен/хорошо комментирован - ну а дальше можно вести хоть какое-то обсуждение - в идеале конечно глянуть бы статейку с разными подходами реализации одного фильтра. например того же медианного и какие-нить сравнительные тесты производительности мк :)

https://gist.github.com/siy/cbee8b7b2d2 ... 2eb2ce8b9f

А вообще гуглится очень много реализаций, было бы желание искать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 13 сен 2018, 08:42 
Старожил
Аватара пользователя

Зарегистрирован: 18 май 2013, 20:43
Сообщения: 4902
Откуда: Кемеровская область, Киселевск
evsi писал(а):
mazahakka v2.0 писал(а):
мне кажется самый идеальный вариант - когда код доступен и он читабелен/хорошо комментирован - ну а дальше можно вести хоть какое-то обсуждение - в идеале конечно глянуть бы статейку с разными подходами реализации одного фильтра. например того же медианного и какие-нить сравнительные тесты производительности мк :)

https://gist.github.com/siy/cbee8b7b2d2 ... 2eb2ce8b9f

А вообще гуглится очень много реализаций, было бы желание искать.

Гавно алгоритм


Есть еще один фильтр плавающий, заводиться таймер с нужной скоростью, и по приходу числа то вниз то вверх плавает.
Нужен только таймер, сложение и вычитание. Простейший. Ошибки фильтрует любые за делать нехуй. Не нагружает процессор, требует кода пару строк.
У C++ кодеров мышление другое, они не способны оптимизировать алгоритмы.

_________________
RADIOWOLF.RU


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 13 сен 2018, 09:41 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2012, 20:35
Сообщения: 2471
Oxford писал(а):
Гавно алгоритм

Да, тот "алгоритм" который предложили вы - полное говно. Вы врядли в состоянии внятно объяснить как он работает и что, собственно, он фильтрует. Тем более не в состоянии объяснить его характеристики.
Oxford писал(а):
Есть еще один фильтр плавающий, заводиться таймер с нужной скоростью, и по приходу числа то вниз то вверх плавает.
Нужен только таймер, сложение и вычитание. Простейший. Ошибки фильтрует любые за делать нехуй. Не нагружает процессор, требует кода пару строк.

Да-да, "у любой задачи есть простое, легкое для объяснения неправильное решение".
Oxford писал(а):
У C++ кодеров мышление другое, они не способны оптимизировать алгоритмы.

Вы путаете оптимизацию с профанацией.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 14 сен 2018, 19:25 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 856
Oxford, повидимому, предлагает линейную фильтрацию на апериодическом звене.

Из недостатков:
Постоянная времени не зависит от временных характеристик сигнала.
Худшая, чем у медианного фильтра, устойчивость к импульсному шуму.

Из плюсов:
Меньшая вычислительная сложность
Нет необходимости в хранении предыдущих значений.
Академичность. Возможность анализа частотных характеристик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 14 сен 2018, 21:33 
Старожил
Аватара пользователя

Зарегистрирован: 18 май 2013, 20:43
Сообщения: 4902
Откуда: Кемеровская область, Киселевск
Устойчивость к помехам зависит от таймера, инерционность. Поэтому иммунитет к помехам очень высокий.

_________________
RADIOWOLF.RU


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 15 сен 2018, 20:34 
Старожил

Зарегистрирован: 10 апр 2013, 17:41
Сообщения: 353
Пользовался таким, заготовка из этих интернетов.
Очень хорошо помогает при помехах большой амплитуды, я применял для фильтрации сбоев конверсии АЦП

Код:
extern int32_t Filter_median (int32_t datum, Filter_m_t *stg);

// размерность медианного фильтра в сэмплах
#define      MEDIAN_FILTER_SIZE    (7)


typedef struct
{
    uint8_t timePos;
    int32_t timeOrder[MEDIAN_FILTER_SIZE];
    int32_t valueOrder[MEDIAN_FILTER_SIZE];
} Filter_m_t;



/*******************************************************************************
* Фильтр медианный
      Parameter:    входной отсчет,
               структура хранения промежут. вычислений
      Return:      выходной отсчет
Note:
//Filter_m_t filt_m_ch0; // создаем структуру
codfiltrm.cn0 = Filter_median(codADC.cn0, &filt_m_ch0);
*******************************************************************************/
int32_t Filter_median (int32_t datum, Filter_m_t *stg)
{

    int32_t oldest = stg->timeOrder[stg->timePos];
    uint8_t p, i;
    int32_t res;

    for(i = 0; i < MEDIAN_FILTER_SIZE; ++i)
    {
        if(stg->valueOrder[i] == oldest)
        {
            p = i;
            break;
        }
    }

    for(--p; (p != 255) && stg->valueOrder[p] > datum; --p) stg->valueOrder[p+1] = stg->valueOrder[p];
    ++p;

    for(++p; (p != MEDIAN_FILTER_SIZE) && stg->valueOrder[p] < datum; ++p) stg->valueOrder[p-1] = stg->valueOrder[p];
    --p;

    stg->timeOrder[stg->timePos] = datum;
    stg->valueOrder[p] = datum;
    stg->timePos = (stg->timePos + 1) % MEDIAN_FILTER_SIZE;

    res = (MEDIAN_FILTER_SIZE % 2 == 1) ? stg->valueOrder[MEDIAN_FILTER_SIZE/2]
          :(stg->valueOrder[MEDIAN_FILTER_SIZE/2-1] + stg->valueOrder[MEDIAN_FILTER_SIZE/2]) / 2;

    return res;
}



_________________
Стиль: "G&P"


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 17 сен 2018, 10:52 
Старожил
Аватара пользователя

Зарегистрирован: 14 июн 2015, 17:41
Сообщения: 2722
Откуда: Русь, Новороссийск
45893569365, благодарю.

Пытаюсь понять написанное :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: алгоритм отсеивания аномальных значений
СообщениеДобавлено: 17 сен 2018, 11:44 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2795
Откуда: Санкт-Петербург
VladyMile, смысл там довольно простой:
* поддерживается отсортированный массив valueOrder и циклический буфер "по порядку прихода" timeOrder/timePos
* при приходе нового значения - надо удалить из valueOrder самое старое и добавить новое
** самое старое берём из timeOrder
** находим (первый цикл) позицию самого старого в valueOrder - это будет свободное место. Надо на него сдвигать элементы, пока не освободится место под новое.
*** вначале пробуем сдвигать элементы слева (двигаем по одному слева направо, пока можно) - второй цикл
*** потом пробуем сдвигать элементы справа - третий цикл (на самом деле либо второй, либо третий цикл закончится сразу)
** в итоге свободное место под новый элемент - p; кладём туда новый элемент
** ну и timeOrder тоже обновляем
* ну и собственно считаем медиану, что несложно при наличии отсортированного массива.

Хороший алгоритм для небольших значений MEDIAN_FILTER_SIZE: на каждый шаг пробегает пара циклов длиной не больше MEDIAN_FILTER_SIZE, т.е. сложность O(MEDIAN_FILTER_SIZE) - но при этом в циклах код очень простой, так что, вероятно, при небольших MEDIAN_FILTER_SIZE даже перегонит алгоритм с двумя кучами (и уж, во всяком случае, его куда проще понять). Плюс при желании его несложно модифицировать (простейший пример: считать не медиану, а среднее из трёх-четырёх центральных элементов массива)

P.S. Интересно, компилятор строчку stg->timePos = (stg->timePos + 1) % MEDIAN_FILTER_SIZE соптимизирует так, чтобы в ней не было деления?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 40 ]  На страницу Пред.  1, 2


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB