Скользящая медиана в реализации C - Turlach - PullRequest
15 голосов
/ 03 апреля 2011

Кто-нибудь знает, есть ли чистая реализация алгоритма скользящего медиана Турлаха в C?У меня проблемы с переносом версии R на чистую версию C.См. здесь для более подробной информации об алгоритме.

EDIT: Как указал darkcminor, в matlab есть функция medfilt2, которая вызывает ordf, которая является реализацией переменногоалгоритма статистики скользящего порядка.Я считаю, что алгоритм работает быстрее, чем O (n ^ 2), но он не с открытым исходным кодом, и я не хочу покупать набор инструментов для обработки изображений.

Ответы [ 2 ]

17 голосов
/ 12 мая 2011

Я реализовал скользящий медианный калькулятор в C здесь (Gist) .Он использует структуру кучи max-median-min: медиана находится в куче [0] (которая находится в центре массива элементов K).Существует minheap, начинающийся с heap [1], и maxheap (использующий отрицательное индексирование) в куче [-1].
Это не совсем то же самое, что реализация Turlach из источника R один поддерживает значения, вставляемые на лету, в то время как версия R действует сразу на весь буфер.Но я считаю, что сложность времени одинакова.И его можно легко использовать для реализации целой версии буфера (возможно, с добавлением некоторого кода для обработки "endrules" R) .

Интерфейс:

//Customize for your data Item type
typedef int Item;
#define ItemLess(a,b)  ((a)<(b))
#define ItemMean(a,b)  (((a)+(b))/2)

typedef struct Mediator_t Mediator;

//creates new Mediator: to calculate `nItems` running median. 
//mallocs single block of memory, caller must free.
Mediator* MediatorNew(int nItems);

//returns median item (or average of 2 when item count is even)
Item MediatorMedian(Mediator* m);

//Inserts item, maintains median in O(lg nItems)
void MediatorInsert(Mediator* m, Item v)
{
   int isNew = (m->ct < m->N);
   int p = m->pos[m->idx];
   Item old = m->data[m->idx];
   m->data[m->idx] = v;
   m->idx = (m->idx+1) % m->N;
   m->ct += isNew;
   if (p > 0)         //new item is in minHeap
   {  if (!isNew && ItemLess(old, v)) { minSortDown(m, p*2);  }
      else if (minSortUp(m, p)) { maxSortDown(m,-1); }
   }
   else if (p < 0)   //new item is in maxheap
   {  if (!isNew && ItemLess(v, old)) { maxSortDown(m, p*2); }
      else if (maxSortUp(m, p)) { minSortDown(m, 1); }
   }
   else            //new item is at median
   {  if (maxCt(m)) { maxSortDown(m,-1); }
      if (minCt(m)) { minSortDown(m, 1); }
   }
}
2 голосов
/ 26 апреля 2011

OpenCV имеет функцию medianBlur , которая, кажется, выполняет то, что вы хотите.Я знаю, что это скользящая медиана.Я не могу сказать, является ли это «медиана Турлаха прокатки» конкретно.Хотя это довольно быстро и поддерживает многопоточность, когда доступно.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...