реклама на сайте
подробности

 
 
4 страниц V  < 1 2 3 4 >  
Reply to this topicStart new topic
> вычисление медианы массива (или произвольной моды), stm32f4 + STL
Xenia
сообщение Jul 30 2013, 16:35
Сообщение #16


Гуру
******

Группа: Модератор FTP
Сообщений: 4 479
Регистрация: 20-02-08
Из: Москва
Пользователь №: 35 237



Цитата(AlexandrY @ Jul 30 2013, 20:03) *
Вы будете смеяться Xenia, но ваш алгоритм в 4 раза! медленней по сравнению с применением библиотечной функции qsort на unsigned short.
А на unsigned int в 4.5 раза.


А какой длины массив использовался при проверке?
Ведь qsort там не пузырьковый, у него логарифмическая скорость. А следовательно на больших массивах эта фора обязательно скажется. Однако в сфере МК память ОЗУ обычно невелика, а потому невелики и массивы. Обычно редко кто ищет медиану в массивах, более длинных чем 1024 элемента. А при такой длине поиск медианы на основе функции qsort врядли даст заметное преимущество.
Go to the top of the page
 
+Quote Post
Axel
сообщение Jul 31 2013, 05:02
Сообщение #17


Местный
***

Группа: Свой
Сообщений: 480
Регистрация: 21-11-04
Пользователь №: 1 188



Мне тоже стало интересно... Попробовал фильтр Ekstrom'а для обработки сигналов touch screen (5 - 15 отсчетов). Понравилось (время не измерял).
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Jul 31 2013, 07:25
Сообщение #18


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Цитата(Xenia @ Jul 30 2013, 20:35) *
Обычно редко кто ищет медиану в массивах, более длинных чем 1024 элемента.

Тут я поддержу Ксению, т.к. в моих задачах (не связанных с применением DSP) средняя глубина медианной фильтрации варьируется от 5 до 31 отсчёта.
Давайте определимся с правилами игры. Предлагаю предоставлять результаты своих замеров для следующих глубин фильтра: 10, 100, 1K и 10K


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post
Tanya
сообщение Jul 31 2013, 08:41
Сообщение #19


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(demiurg_spb @ Jul 31 2013, 11:25) *
варьируется от 5 до 31 отсчёта.
Давайте определимся с правилами игры.

Вот тоже скажу... Нет никакого смысла в оцифровке скрипящего потенциометра последовательностью в 100 точек. Не более 10, если не слишком часто...
Кроме того сортировка проводится не случайным образом перемешанной последовательности, а априорно известной. Таким образом, возможно, что самым лучшим для данного случая будет не самый быстрый для общего случая алгоритм.
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Jul 31 2013, 10:07
Сообщение #20


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Цитата(Tanya @ Jul 31 2013, 12:41) *
Кроме того сортировка проводится не случайным образом перемешанной последовательности, а априорно известной. Таким образом, возможно, что самым лучшим для данного случая будет не самый быстрый для общего случая алгоритм.
Не понял эту глубокую мысль...
У нас каждый раз новая неизвестная последовательность (не важно все 10 отсчётов новых или только один из десяти (скользящее окно)).
Т.е. всегда что-то новое и неизвестное. А то что мы отсортировали на прошлом шаге для нас не представляет никакой ценности на текущем шаге, т.к. наши отсчёты после сортировки теряют привязку к своей очерёдности (то бишь ко времени).


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post
Tanya
сообщение Jul 31 2013, 10:59
Сообщение #21


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(demiurg_spb @ Jul 31 2013, 14:07) *
Не понял эту глубокую мысль...

Поясню. Последовательность не произвольная, а реальная - две полочки, а между ними выбросы. Или одна полочка без выбросов. Возможно, что со всем этим можно легко справиться с помощью одного резистора и одного конденсатора.
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Jul 31 2013, 11:06
Сообщение #22


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Цитата(Tanya @ Jul 31 2013, 14:59) *
Не всегда. У меня есть разработка - тахометр, который используют в весьма разболтанных системах (люфты страшные) + метки на колесе неоднородно размещены бывают, так для нормального функционирования приходится и медианный фильтр и фнч 2 порядка ставить. И никакие конденсаторы тут не спасают.


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post
KRS
сообщение Jul 31 2013, 11:22
Сообщение #23


Профессионал
*****

Группа: Модераторы
Сообщений: 1 951
Регистрация: 27-08-04
Из: Санкт-Петербург
Пользователь №: 555



А ведь если фильтр скользящий, на этапе добавление очередного измерения, уже есть отсортированный массив.
Но из него удаляется один элемент, при этом он остается отсортированным, надо просто вставить новый на нужное место. Ту сортировка вставками будет самой быстрой.
Go to the top of the page
 
+Quote Post
Xenia
сообщение Jul 31 2013, 11:50
Сообщение #24


Гуру
******

Группа: Модератор FTP
Сообщений: 4 479
Регистрация: 20-02-08
Из: Москва
Пользователь №: 35 237



Цитата(demiurg_spb @ Jul 31 2013, 11:25) *
Давайте определимся с правилами игры. Предлагаю предоставлять результаты своих замеров для следующих глубин фильтра: 10, 100, 1K и 10K


Да-да! И тогда я победю Клёна! sm.gif
Go to the top of the page
 
+Quote Post
Tanya
сообщение Jul 31 2013, 12:06
Сообщение #25


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(demiurg_spb @ Jul 31 2013, 15:06) *
. И никакие конденсаторы тут не спасают.

Верю. Но я же написала "возможно"... Медианный фильтр нелинейный и удаляет "неправильные" выбросы.
А откуда они берутся? Разрывается контакт (повисает в воздухе), а входное сопротивление АЦП не очень...
Есть еще вариант - сделать ограничение скорости нарастания (тоже нелинейная штука) - при рассогласовании запомненного значения с АЦПшным оно медленно увеличивается или уменьшается (на фиксированную величину). Это будет самый быстрый способ. Я так думаю.
Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле.
Go to the top of the page
 
+Quote Post
Axel
сообщение Jul 31 2013, 12:30
Сообщение #26


Местный
***

Группа: Свой
Сообщений: 480
Регистрация: 21-11-04
Пользователь №: 1 188



Цитата(Tanya @ Jul 31 2013, 15:06) *
Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле.

Иногда (часто) не в ручонках дело. Типичный пример - потенциометры на педали газа автомобилей. Пример из программы ECU привести не могу - не сохранился, но когда однажды пришлось разбираться, то обнаружился вполне серьезный фильтр (насколько удалось понять после дизассемблера).
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Jul 31 2013, 13:14
Сообщение #27


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Ну что, пришло время подвести некоторые итоги. biggrin.gif

Ниже результаты тестирования алгоритмов на платформе на основе Kinetis MK60 (Cortex-M4).
Программа выполнялась из внутренней Flash, данные во внутренней RAM. Частота ядра 120 МГц, частота шины 60 МГц, частота Flash 24 МГц.
Компилятор Keil ARMCC v5.03. Ключи компиляции: -c --cpu Cortex-M4.fp -D__MICROLIB -g -O3 -Otime --apcs=interwork

Я проводил тестирование на интересующем меня объеме выборки. Кому надо дальше может тестировать сам. Проект выложу.
Как видно абсолютный победитель - алгоритм Ekstrom .
Но надо сказать, что в нем есть нюанс. В данных не должно быть числа равного символу STOPPER.
В алгоритме STOPPER равен 0, значит в данных не должно быть 0, что я сделал формирую случайные данные.

Если такая кривизна не устраивает, то лучший алгоритм select из рецептов на C.

Код
INVCPU v1.00 PCB Test Suit.
System Core Clock = 120000000 Hz
Now. System ticks = 750055l, Sysytem time = 0.006250 s
Clock check. T1= 1440076l, T2= 1560048l, Delta(tick)= 119972l, Delta(s)= 0.0010
----------------------------------------------
Algorithm 'Qsort' (standart C library ):
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 67287, time(us)=560.73
Measured min. number of cycles = 23532, time(us)=196.10
Measured aver.number of cycles = 26937, time(us)=224.48

----------------------------------------------
Algorithm 'Select' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.341):
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 3142, time(us)=26.18
Measured min. number of cycles = 1237, time(us)=10.31
Measured aver.number of cycles = 2087, time(us)=17.39

----------------------------------------------
Algorithm 'Selip' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.343):
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 18478, time(us)=153.98
Measured min. number of cycles = 2198, time(us)=18.32
Measured aver.number of cycles = 16979, time(us)=141.49

----------------------------------------------
Algorithm 'Xenia' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180687):
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 40263, time(us)=335.53
Measured min. number of cycles = 920, time(us)=7.67
Measured aver.number of cycles = 19902, time(us)=165.85

----------------------------------------------
Algorithm 'Ekstrom' (http://embeddedgurus.com/stack-overflow/tag/median-filter/):
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 1243, time(us)=10.36
Measured min. number of cycles = 1182, time(us)=9.85
Measured aver.number of cycles = 1187, time(us)=9.89

----------------------------------------------
Algorithm 'Klen' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180679)
----------------------------------------------
Results CRC = D6EF
Number of samplles   = 65
Number of iterations = 1000
Measured max. number of cycles = 3517, time(us)=29.31
Measured min. number of cycles = 1732, time(us)=14.43
Measured aver.number of cycles = 2470, time(us)=20.58



Да, а Klen-у выкинуть свой компилятор. wink.gif
Скомпилированное Keil-ом 127 сэмплов по его алгоритму вычисляет за 53 мкс на 120 МГц ядре против 56 мкс на 168 МГц ядре скомпилированное GCC.

Если отключить опцию MICROLIB в компиляторе то алгоритм qsotr ускорится где-то в 9 раз.
Go to the top of the page
 
+Quote Post
Altemir
сообщение Jul 31 2013, 14:03
Сообщение #28


Местный
***

Группа: Свой
Сообщений: 249
Регистрация: 2-05-06
Из: Россия, Поволжье
Пользователь №: 16 686



AlexandrY
"Number of samplles" - это длина массива? Какой тип чисел был во входном массиве? signed long не пробовали с длиной 128 элементов?
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Jul 31 2013, 14:10
Сообщение #29


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Altemir @ Jul 31 2013, 17:03) *
AlexandrY
"Number of samplles" - это длина массива? Какой тип чисел был во входном массиве? signed long не пробовали с длиной 128 элементов?

Был использован тип unsigned int
Number of samplles - это длинна массива. Выбрана нечетной чтобы был элемент посередине.
Измерялось время между подачей очередного случайного сэмпла (от 1 до 10000)в массив и получением медианы как отклика.
Всего пропускалось по 1000 сэмплов.
Вначале массивы инициализировались единицами (из-за особенности алгоритма Ekstrom )
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Jul 31 2013, 14:10
Сообщение #30


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Цитата(KRS @ Jul 31 2013, 15:22) *
А ведь если фильтр скользящий, на этапе добавление очередного измерения, уже есть отсортированный массив.
Но из него удаляется один элемент, при этом он остается отсортированным, надо просто вставить новый на нужное место. Ту сортировка вставками будет самой быстрой.
Это понятно, но вы посмотрите на размер кода такого алгоритма 'Ekstrom'.
Я это тоже изобретал, но отверг по причинам невпихуемости результирующей прошивки.


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post

4 страниц V  < 1 2 3 4 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 11th July 2025 - 15:08
Рейтинг@Mail.ru


Страница сгенерированна за 0.01516 секунд с 7
ELECTRONIX ©2004-2016