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

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


Местный
***

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



AlexandrY
Огромное спасибо! Как и ожидал - у меня стабильный середнячок sm.gif Буду теперь смотреть альтернативу. Благо, они есть в этой ветке
Go to the top of the page
 
+Quote Post
VAI
сообщение Aug 1 2013, 18:45
Сообщение #47


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

Группа: Модераторы
Сообщений: 1 120
Регистрация: 17-06-04
Пользователь №: 37



Я опоздал, все результаты посчитаны, да и алгоритм медианного фильтра у меня поддерживает размер буфера от 3 до 31. 65 никак.
Когда-то выкладывал на сахаре и здесь, но здесь не нашел, вот ссылки на сахару.
http://caxapa.ru/15518.html
http://caxapa.ru/170626.html
В обоих вариантах алгоритм получения медианы одинаков, только способ работы с буфером разный.
AlexandrY Вы обещали выложить проект, хочу скомпилить с буфером размером 31 и сравнить скорость моего алгоритма с другими.
Или Вы добавьте мой алгоритм и выложите результат. :-)


--------------------
Если зайца бить, его можно и спички научить зажигать
Сколько дурака не бей - умнее не будет. Зато опытнее
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 5 2013, 08:18
Сообщение #48


Ally
******

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



Цитата(VAI @ Aug 1 2013, 21:45) *
... и выложите результат. :-)


Да, вот результат.
Уменьшил массив до 31 отсчета, под алгоритм VAI. Количество итераций довел до 10000.
И сделал сравнение для двух компиляторов Keil (ARM compiler) и IAR.
Чтобы еще было больше доверия к тесту и виднее различие компиляторов вначале идет тест CoreMark.
CODE
INVCPU v1.00 PCB Test Suit. INVCPU v1.00 PCB Test Suit.
System Core Clock = 120000000 Hz System Core Clock = 120000000 Hz
Now. System ticks = 750122l, Sysytem time = 0.006251 s Now. System ticks = 707843l, Sysytem time = 0.005899 s
---------------------------------------------- ----------------------------------------------
Coremark test Coremark test
---------------------------------------------- ----------------------------------------------
2K performance run parameters for coremark. 2K performance run parameters for coremark
CoreMark Size : 666 CoreMark Size : 666
Total ticks : 2090014320 Total ticks : 1619555180
Total time (secs): 17.416786 Total time (secs): 13.496293
Iterations/Sec : 287.079373 Iterations/Sec : 370.472095
Iterations : 5000 Iterations : 5000
Compiler version : ARM CC 5030069 Compiler version : IAR CC 6050006
Compiler flags : -o3 Compiler flags : -o3
Memory location : STACK Memory location : STACK
seedcrc : 0xe9f5 seedcrc : 0xe9f5
[0]crclist : 0xe714 [0]crclist : 0xe714
[0]crcmatrix : 0x1fd7 [0]crcmatrix : 0x1fd7
[0]crcstate : 0x8e3a [0]crcstate : 0x8e3a
[0]crcfinal : 0xbd59 [0]crcfinal : 0xbd59
Correct operation validated. Correct operation validated.
CoreMark 1.0 : 287.079373 / ARM CC 5030069 -o3 / STACK CoreMark 1.0 : 370.472095 / IAR CC 6050006 -o3 / STACK
---------------------------------------------- ----------------------------------------------
Algorithm 'Qsort' (standart C library ): Algorithm 'Qsort' (standart C library ):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 6452, time(us)=53.77 Measured max. number of cycles = 12865, time(us)=107.21
Measured min. number of cycles = 3722, time(us)=31.02 Measured min. number of cycles = 6340, time(us)=52.83
Measured aver.number of cycles = 4788, time(us)=39.90 Measured aver.number of cycles = 8508, time(us)=70.90

---------------------------------------------- ----------------------------------------------
Algorithm 'Shell' Algorithm 'Shell' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1181687):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 2372, time(us)=19.77 Measured max. number of cycles = 2610, time(us)=21.75
Measured min. number of cycles = 1355, time(us)=11.29 Measured min. number of cycles = 1565, time(us)=13.04
Measured aver.number of cycles = 1949, time(us)=16.24 Measured aver.number of cycles = 2098, time(us)=17.48

---------------------------------------------- ----------------------------------------------
Algorithm 'Select' Algorithm 'Select' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.341):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 1453, time(us)=12.11 Measured max. number of cycles = 1530, time(us)=12.75
Measured min. number of cycles = 472, time(us)=3.93 Measured min. number of cycles = 495, time(us)=4.13
Measured aver.number of cycles = 825, time(us)=6.88 Measured aver.number of cycles = 858, time(us)=7.15

---------------------------------------------- ----------------------------------------------
Algorithm 'Selip' Algorithm 'Selip' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.343):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 3325, time(us)=27.71 Measured max. number of cycles = 3590, time(us)=29.92
Measured min. number of cycles = 1090, time(us)=9.08 Measured min. number of cycles = 1170, time(us)=9.75
Measured aver.number of cycles = 2957, time(us)=24.64 Measured aver.number of cycles = 3266, time(us)=27.22

---------------------------------------------- ----------------------------------------------
Algorithm 'Xenia' Algorithm 'Xenia' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180687):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 5375, time(us)=44.79 Measured max. number of cycles = 5340, time(us)=44.50
Measured min. number of cycles = 469, time(us)=3.91 Measured min. number of cycles = 474, time(us)=3.95
Measured aver.number of cycles = 2947, time(us)=24.56 Measured aver.number of cycles = 2766, time(us)=23.05

---------------------------------------------- ----------------------------------------------
Algorithm 'Neiver' Algorithm 'Neiver' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180944):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 3014, time(us)=25.12 Measured max. number of cycles = 2540, time(us)=21.17
Measured min. number of cycles = 754, time(us)=6.28 Measured min. number of cycles = 681, time(us)=5.68
Measured aver.number of cycles = 761, time(us)=6.34 Measured aver.number of cycles = 695, time(us)=5.79

---------------------------------------------- ----------------------------------------------
Algorithm 'Ekstrom' Algorithm 'Ekstrom' (http://embeddedgurus.com/stack-overflow/tag/median-filter/):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 694, time(us)=5.78 Measured max. number of cycles = 637, time(us)=5.31
Measured min. number of cycles = 632, time(us)=5.27 Measured min. number of cycles = 563, time(us)=4.69
Measured aver.number of cycles = 637, time(us)=5.31 Measured aver.number of cycles = 574, time(us)=4.78

---------------------------------------------- ----------------------------------------------
Algorithm 'Klen' Algorithm 'Klen' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180679)
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 1967, time(us)=16.39 Measured max. number of cycles = 7120, time(us)=59.33
Measured min. number of cycles = 822, time(us)=6.85 Measured min. number of cycles = 2580, time(us)=21.50
Measured aver.number of cycles = 1169, time(us)=9.74 Measured aver.number of cycles = 4260, time(us)=35.50

---------------------------------------------- ----------------------------------------------
Algorithm 'VAI' (http://caxapa.ru/170626.html): Algorithm 'VAI' (http://caxapa.ru/170626.html):
---------------------------------------------- ----------------------------------------------
Results CRC = 81AD Results CRC = 7CBB
Number of samplles = 31 Number of samplles = 31
Number of iterations = 10000 Number of iterations = 10000
Measured max. number of cycles = 5707, time(us)=47.56 Measured max. number of cycles = 4627, time(us)=38.56
Measured min. number of cycles = 5650, time(us)=47.08 Measured min. number of cycles = 4549, time(us)=37.91
Measured aver.number of cycles = 5652, time(us)=47.10 Measured aver.number of cycles = 4562, time(us)=38.02


С шаблонами на C++ в обоих компиляторах наблюдаются проблемы.
Keil при наличии шаблонов отказывается делать кроссмодульную оптимизацию. IAR как видно с шаблонами тоже жутко затормозил быстродействие.
Вообщем шаблоны не наш путь. wink.gif

Проекты для микроконтроллера MK60FN1M0VLQ12 здесь:
[attachment=78643:Test_Suite_IAR.zip]
[attachment=78644:Test_Suite_Keil.zip]

Сообщение отредактировал IgorKossak - Aug 1 2018, 17:18
Причина редактирования: [codebox] для длинного кода, [code] - для короткого!
Go to the top of the page
 
+Quote Post
VAI
сообщение Aug 5 2013, 11:59
Сообщение #49


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

Группа: Модераторы
Сообщений: 1 120
Регистрация: 17-06-04
Пользователь №: 37



Херовый у меня алгоритм.. :-(


--------------------
Если зайца бить, его можно и спички научить зажигать
Сколько дурака не бей - умнее не будет. Зато опытнее
Go to the top of the page
 
+Quote Post
p_v
сообщение Aug 1 2018, 16:07
Сообщение #50


Участник
*

Группа: Участник
Сообщений: 68
Регистрация: 16-06-18
Из: СПб
Пользователь №: 105 099



Тема старая, но очень годная. Спасибо за тесты, очень удобно, когда есть на что ориентироваться.

Решил пойти немного другим путем - вместо median считать truncated mean (как в школе на лабораторках). То есть:
  1. Считаем среднее.
  2. Считаем дисперсию.
  3. Считаем среднее только по тем элементам, которые укладываются в заданную дисперсию относительно среднего.
Каких-то особых целей не преследовал, просто захотелось посмотреть как еще можно покоцать резкие отклонения.

CODE
#define ADC_BUFFER_SIZE 32
#define ADC_BUFFER_MASK 0x1F

uint32_t truncated_mean(uint16_t *src, int head, int count)
{
int i = 0;
int idx = 0;

// Collect mean
i = count;
idx = head;
int s_mean = 0;
while (i)
{
i--;
idx--;
idx &= ADC_BUFFER_MASK;
s_mean += src[idx];
}

// add (count >> 1) for better rounding
int mean = (s_mean + (count >> 1)) / count;

// Collect sigma
i = count;
idx = head;
int s_sigma = 0;
while (i)
{
i--;
idx--;
idx &= ADC_BUFFER_MASK;
int val = src[idx];
s_sigma += (mean - val) * (mean - val);
}

int sigma_square_4 = s_sigma * 4 / count;

// Drop big deviations and count mean for the rest
i = count;
idx = head;
int s_mean_filtered = 0;
int s_mean_filtered_cnt = 0;

while (i)
{
i--;
idx--;
idx &= ADC_BUFFER_MASK;
int val = src[idx];

if ((mean - val) * (mean - val) < sigma_square_4)
{
s_mean_filtered += val;
s_mean_filtered_cnt++;
}
}

// Protection from zero div. Should never happen
if (!s_mean_filtered_cnt) return mean;

return (s_mean_filtered + (s_mean_filtered_cnt >> 1)) / s_mean_filtered_cnt;
<div> }


На M3 31 отсчет 1460 циклов по дебагеру. Не знаю на сколько врет, он вообще странный немного.
  • Это медленнее Ekstrom, но зато тут есть встроенный усреднятор (теоретически должен дрожать меньше медианы).
  • Можно переписать вычисление дисперсии и среднего на 1 проход вместо 2, но тогда целочисленная арифметика потянет только 15 12-битных отсчетов
  • Тут еще дополнительные накладные расходы, чтобы читать из кольцевого буфера, лень было вырезать.
  • Кольцевой буфер делался чтобы не возиться с локами и т.п. - размер сделан с запасом, поэтому пока мы обрабатываем данные из одной части, АЦП пишет дальше.


Сообщение отредактировал IgorKossak - Aug 1 2018, 17:07
Причина редактирования: [codebox] для длинного кода, [code] - для короткого!
Go to the top of the page
 
+Quote Post
p_v
сообщение Aug 3 2018, 15:16
Сообщение #51


Участник
*

Группа: Участник
Сообщений: 68
Регистрация: 16-06-18
Из: СПб
Пользователь №: 105 099



https://pastebin.com/xpLbyWN6 - двухпроходный вариант, ~ на 20% быстрее предыдущего, + настраиваемый порог срабатывания. 2*sigma многовато оказалось. 1.1*sigma поправдоподобнее.
Go to the top of the page
 
+Quote Post

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

 


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


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