C语言中的滚动中位数 - Turlach实现

Question

C语言中的滚动中位数 - Turlach实现

calgorithmmatlab

17

请问有没有C语言中Turlach滚动中位数算法的清晰实现？我在将R版本移植成一个干净的C版本时遇到了困难。关于这个算法的更多细节，请参见这里。

编辑： 正如darkcminor所指出的，MATLAB有一个medfilt2函数，该函数调用ordf，它是一个滚动序统计算法的C实现。我相信该算法比O（n^2）的算法快，但它不是开源的，我也不想购买图像处理工具箱。

- Rich C

请检查这个链接，可能是Matlab相关的：http://www.mathworks.com/matlabcentral/newsreader/view_thread/270067 - edgarmtze

3

请查看此问题：https://dev59.com/73M_5IYBdhLWcg3wmkUK - Robert Gamble

2

还有一个常数时间中值滤波算法。在scikits.image中有一个2D的实现，使用八边形滤波区域。 - user227667

2个回答

2

OpenCV有一个medianBlur函数，似乎可以实现您想要的功能。我知道它是一个滚动中位数。我不能确定它是否特别是"Turlach滚动中位数"。但是它非常快，并且在可用时支持多线程。

- Carl F.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AShelly · Accepted Answer

我在这里用C语言实现了一个滚动中位数计算器 (Gist)。它使用了一个最大-中位数-最小堆结构：中位数位于堆[0]（在一个K个元素的数组的中心）。在堆[1]处有一个最小堆，而在堆[-1]处有一个最大堆（使用负索引）。

它与R源代码中的Turlach实现不完全相同：这个实现支持实时插入值，而R版本则是对整个缓冲区进行操作。但我认为时间复杂度是相同的。并且可以很容易地用它来实现整个缓冲区的版本（可能需要添加一些代码以处理R的“endrules”）。

接口：

//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); }
   }
}