Перейти к содержанию
Поиск
    

вычисление медианы массива (или произвольной моды)

Ответить

AltemirX    0

AltemirX
Опубликовано · Жалоба

AlexandrY

Огромное спасибо! Как и ожидал - у меня стабильный середнячок :) Буду теперь смотреть альтернативу. Благо, они есть в этой ветке

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

VAI    0

VAI
Опубликовано · Жалоба

Я опоздал, все результаты посчитаны, да и алгоритм медианного фильтра у меня поддерживает размер буфера от 3 до 31. 65 никак.

Когда-то выкладывал на сахаре и здесь, но здесь не нашел, вот ссылки на сахару.

http://caxapa.ru/15518.html

http://caxapa.ru/170626.html

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

AlexandrY Вы обещали выложить проект, хочу скомпилить с буфером размером 31 и сравнить скорость моего алгоритма с другими.

Или Вы добавьте мой алгоритм и выложите результат. :-)

 

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

AlexandrY    3

AlexandrY
Опубликовано (изменено) · Жалоба
... и выложите результат. :-)

 

Да, вот результат.

Уменьшил массив до 31 отсчета, под алгоритм VAI. Количество итераций довел до 10000.

И сделал сравнение для двух компиляторов Keil (ARM compiler) и IAR.

Чтобы еще было больше доверия к тесту и виднее различие компиляторов вначале идет тест CoreMark. 

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 как видно с шаблонами тоже жутко затормозил быстродействие.

Вообщем шаблоны не наш путь. ;)

 

Проекты для микроконтроллера MK60FN1M0VLQ12 здесь:

 

 

Изменено пользователем IgorKossak
[codebox] для длинного кода, [code] - для короткого!

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

p_v    0

p_v
Опубликовано (изменено) · Жалоба

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

 

Решил пойти немного другим путем - вместо median считать truncated mean (как в школе на лабораторках). То есть:

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

 

#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
[codebox] для длинного кода, [code] - для короткого!

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

p_v    0

p_v
Опубликовано · Жалоба
https://pastebin.com/xpLbyWN6 - двухпроходный вариант, ~ на 20% быстрее предыдущего, + настраиваемый порог срабатывания. 2*sigma многовато оказалось. 1.1*sigma поправдоподобнее.

Поделиться сообщением

Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
×
  • Создать...