|
|
  |
вычисление медианы массива (или произвольной моды), stm32f4 + STL |
|
|
|
Jul 31 2013, 16:04
|
Гуру
     
Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883

|
Цитата(KRS @ Jul 31 2013, 18:19)  Но как видно минимально возможное время все таки у алгоритма Xenia! И во многих случаях для реальных измерений с АЦП он будет давать лучшее время! "Мой" алгоритм еще быстрее. Вот только имеет ли тут смысл говорить о скорости... Цитата(KRS @ Jul 31 2013, 18:19)  А физический смысл для рандомного массива применять медианный фильтр не очень понятный! Вот по этой самой причине. Тем более, что массив вполне себе не массив, а последовательность с вполне понятными особенностями.
|
|
|
|
|
Aug 1 2013, 07:45
|

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

|
Цитата(Tanya @ Jul 31 2013, 19:04)  "Мой" алгоритм еще быстрее. Вот только имеет ли тут смысл говорить о скорости...
Вот по этой самой причине. Тем более, что массив вполне себе не массив, а последовательность с вполне понятными особенностями. Говорить не надо, надо только измерить.  Если имеете исходник, то выкладывайте. Хотя меня в этой теме больше привлекает возможность помериться оценить компиляторы, но медиана сама по себе применяется именно на зашумленных произвольных сигналах. И что там за понятные особенности никак не пойму. Медиану с успехом применял для декодеров частотно модулированных сигналов. Вот ниже график сигналов с которыми я имею дело при проектировании силовой электроники. Вверху исходный сигнал. посередине зашумленный, внизу сравнение 3-х фильтров: желтый - скользящее среднее (31 отсчет), голубой - ФНЧ (Fpass=80Hz, Fstop=1000Hz, Astop=60dB ), розовый - медиана (31 отсчет) Как видно медиана ближе всех повторяет исходный вид сигнала. [attachment=78573:Median_vs_Average.png]
|
|
|
|
|
Aug 1 2013, 08:13
|
Гуру
     
Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883

|
Цитата(AlexandrY @ Aug 1 2013, 11:45)  Говорить не надо, надо только измерить. Если имеете исходник, то выкладывайте. Хотя меня в этой теме больше привлекает возможность помериться оценить компиляторы, но медиана сама по себе применяется именно на зашумленных произвольных сигналах. И что там за понятные особенности никак не пойму. Как видно медиана ближе всех повторяет исходный вид сигнала. Какой исходник? Одно сравнение и один же инкремент или декремент. Медиана у Вас разве не задерживает сигнал?
|
|
|
|
|
Aug 1 2013, 09:09
|

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

|
Цитата(Tanya @ Aug 1 2013, 11:13)  Какой исходник? Одно сравнение и один же инкремент или декремент. Медиана у Вас разве не задерживает сигнал? Мы наверно о разном. Еще раз повторил тесты уже с нормальной библиотекой C-и и с сигналом повторяющим характер зашумленного сигнала АЦП как на графике выше. Добавил итераций для более надежной статистики. Алгоритм Xenia оказался самым чувствительным к виду данных. Алгоритм Ekstrom почти не чувствует изменения характера данных, а главное имеет очень маленькую дисперсию. Однако какая сила эти списки! А с виду кажутся такими громоздкими. Где там Klen? Пора переводить на STL! Код INVCPU v1.00 PCB Test Suit. System Core Clock = 120000000 Hz Now. System ticks = 750131l, Sysytem time = 0.006251 s Clock check. T1= 1440087l, T2= 1560069l, Delta(tick)= 119982l, Delta(s)= 0.0010 ---------------------------------------------- Algorithm 'Qsort' (standart C library ): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 15054, time(us)=125.45 Measured min. number of cycles = 9369, time(us)=78.08 Measured aver.number of cycles = 12036, time(us)=100.30
---------------------------------------------- Algorithm 'Shell' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1181687): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 6370, time(us)=53.08 Measured min. number of cycles = 3640, time(us)=30.33 Measured aver.number of cycles = 5454, time(us)=45.45
---------------------------------------------- Algorithm 'Select' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.341): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 3129, time(us)=26.07 Measured min. number of cycles = 834, time(us)=6.95 Measured aver.number of cycles = 1621, time(us)=13.51
---------------------------------------------- Algorithm 'Selip' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.343): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 15714, time(us)=130.95 Measured min. number of cycles = 2224, time(us)=18.53 Measured aver.number of cycles = 14548, time(us)=121.23
---------------------------------------------- Algorithm 'Xenia' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180687): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 21885, time(us)=182.38 Measured min. number of cycles = 930, time(us)=7.75 Measured aver.number of cycles = 10514, time(us)=87.62
---------------------------------------------- Algorithm 'Neiver' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180944): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 8009, time(us)=66.74 Measured min. number of cycles = 1512, time(us)=12.60 Measured aver.number of cycles = 1535, time(us)=12.79
---------------------------------------------- Algorithm 'Ekstrom' (http://embeddedgurus.com/stack-overflow/tag/median-filter/): ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 1325, time(us)=11.04 Measured min. number of cycles = 1256, time(us)=10.47 Measured aver.number of cycles = 1265, time(us)=10.54
---------------------------------------------- Algorithm 'Klen' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180679) ---------------------------------------------- Results CRC = 7EC7 Number of samplles = 65 Number of iterations = 6000 Measured max. number of cycles = 4405, time(us)=36.71 Measured min. number of cycles = 1595, time(us)=13.29 Measured aver.number of cycles = 2403, time(us)=20.02
|
|
|
|
|
Aug 1 2013, 09:44
|
Гуру
     
Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883

|
Цитата(AlexandrY @ Aug 1 2013, 13:09)  Мы наверно о разном.  Может... Я про то, что 1. Человек не может крутить ручку с бесконечно большой скоростью. 2. Скрип возникает только в процессе верчения. 3. Выбросы поэтому будут только на фронтах и всегда в одну сторону (к нулю?). 4. Не имеет смысла часто и много все это измерять. 5. Выбросы нужно просто выбрасывать. Ваш медианный алгоритм может давать очень большую ошибку, если более половины выборки придется на фронт с большими выбросами.
|
|
|
|
|
Aug 1 2013, 10:20
|
Местный
  
Группа: Участник
Сообщений: 214
Регистрация: 22-03-10
Из: Саратов
Пользователь №: 56 123

|
Цитата(AlexandrY @ Aug 1 2013, 13:09)  Алгоритм Neiver-а не прошел верификацию, там получается явно не медиана. Кстати да, там у меня ошибочка была, при не четном колчестве элементов. Сейчас поправил и чуть оптимизировал. Код int Median(const int *data, size_t size) { int min, max, newMax, newMin; size_t middle = (size+1) / 2; min = max = data[0]; for(size_t i = 0; i < size; i++) { max = std::max(data[i], max); min = std::min(data[i], min); }
int medianCandidate; size_t less, more; do { medianCandidate = (min + max) / 2; more = less = 0; newMax = min; newMin = max;
for(size_t i = 0; i < size; i++) { if(data[i] > medianCandidate) { more ++; if (data[i] < newMin) newMin = data[i]; }else if(data[i] < medianCandidate) { less ++; if (data[i] > newMax) newMax = data[i]; } }
if (less <= middle && more <= middle) break; else if(less > middle) { max = newMax; } else { min = newMin; } } while(max - min > 1); size_t equal = size - more - less; if (less >= middle) return newMax; else if (less + equal >= middle) return medianCandidate; else return newMin; }
|
|
|
|
|
Aug 1 2013, 10:36
|
Местный
  
Группа: Свой
Сообщений: 249
Регистрация: 2-05-06
Из: Россия, Поволжье
Пользователь №: 16 686

|
AlexandrYМогу скромно попросить на той же платформе проверить медианку на основе сортировки Шелла?  Заранее благодарю. CODE #define compGT(a, B ) (a > B )
//------------------------------------------------------------------------------ //! Медианный фильтр с сортировкой Шелла //------------------------------------------------------------------------------ int Med_Shell_Sort(int *a, int ub){ int n, h, i, j; int t; // compute largest increment n = ub + 1; h = 1; if (n < 14) h = 1; else if (sizeof(tblIndex) == 2 && n > 29524) h = 3280; else { while (h < n) h = 3*h + 1; h /= 3; h /= 3; } while (h > 0) { // sort-by-insertion in increments of h for (i = h; i < ub; i++) { t = a[i]; for (j = i-h; (j >= 0) && compGT(a[j], t); j -= h) a[j+h] = a[j]; a[j+h] = t; } // compute next increment h /= 3; }
return ((ub+1)/2); }
|
|
|
|
|
Aug 1 2013, 10:54
|

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

|
Цитата(neiver @ Aug 1 2013, 13:20)  Кстати да, там у меня ошибочка была, при не четном колчестве элементов. Сейчас поправил и чуть оптимизировал. Да теперь правильно. Обновил в таблице результатов в предыдущем посте. Ого! Уже и алгоритм Neiver обошел (по некоторым параметрам) алгоритмы из Рецептов . Значит рецепты пора выбрасывать в утиль.  Цитата(Altemir @ Aug 1 2013, 13:36)  Могу скромно попросить на той же платформе проверить медианку на основе сортировки Шелла?  Заранее благодарю. Да, мог бы если скажете где взять sizeof(tblIndex) и что там за магические числа типа 29524 и 3280
|
|
|
|
|
Aug 1 2013, 11:09
|
Местный
  
Группа: Свой
Сообщений: 249
Регистрация: 2-05-06
Из: Россия, Поволжье
Пользователь №: 16 686

|
Цитата(AlexandrY @ Aug 1 2013, 14:54)  Да, мог бы если скажете где взять sizeof(tblIndex) и что там за магические числа типа 29524 и 3280 Код typedef int tblIndex; Упс. Прошу прощения. sizeof(tblIndex) - это я не всё заменил, чтобы выложить сюда. В моём примере следует использовать 4 - размерность элемента входного массива, байт. 29524 и 3280 - это действительно, магические числа. Брал пример очень давно из какого-то учебника, не вспомнить. Если правильно понимаю, сии числа ограничивают элементарный блок сортировки и шаг при работе с очень большими массивами, чтобы оптимизировать эффективность. Вроде, в книжке был целый ряд магических чисел для ещё бОльших длин, но я не использую у себя массивы, превышающие 1000 элементов, так что указанная часть кода неактуальна. Если найду источник этого примера, скину ссылку. Ага. Нашёл: http://www.info-system.ru/library/algo/sortsearch.pdfИ отдельные файлы реализации, откуда выдирал: http://www.cs.auckland.ac.nz/~jmor159/PLDS...emann/s_shl.txthttp://epaperpress.com/sortsearch/txt/shl.txtВидно, что h может быть получен разными способами.
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|