在C – Turlach实施中滚动中位数
有谁知道在C中是否有一个干净的Turlach滚动中值算法实现？ 我在将R版本移植到干净的C版本时遇到了麻烦。 有关算法的更多详细信息，请参见此处 。
编辑：正如darkcminor所指出的，matlab有一个函数medfilt2 ，它调用ordf ，这是一个滚动顺序统计算法的交流实现。 我相信算法比O（n ^ 2）快，但它不是开源的，我不想购买图像处理工具箱。
我在这里用C实现了滚动中值计算器 （Gist） 。 它使用max-median-min堆结构：中位数在堆[0]（位于K项数组的中心）。 从堆[1]开始有一个minheap，在堆[-1]有一个maxheap（使用负索引）。
它与来自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); } } }
OpenCV有一个medianBlur函数，似乎可以做你想要的。 我知道这是一个滚动的中位数。 我不能说具体是否是“Turlach滚动中位数”。 它虽然速度很快，但在可用时支持multithreading。
您可以在C ++中查看std :: nth_element的源代码，并将其重写为C. nth_element可以在O（N）时间内平均找到中值（或排序数组的任何其他单个元素）。
float values[N]; ... std::nth_element( values, values+N/2, values+N ); return values[N/2];