Media móvil en C – Implementación de Turlach

4 minutos de lectura

avatar de usuario
rica c

¿Alguien sabe si hay una implementación limpia del algoritmo de mediana móvil de Turlach en C? Tengo problemas para migrar la versión R a una versión C limpia. Vea aquí para más detalles sobre el algoritmo.

EDITAR:
Como señaló darkcminor, matlab tiene una función medfilt2 que llama ordf que es una implementación ac de un algoritmo estadístico de orden variable. Creo que el algoritmo es más rápido que O(n^2), pero no es de código abierto y no quiero comprar la caja de herramientas de procesamiento de imágenes.

  • mira esto tal vez matlab mathworks.com/matlabcentral/newsreader/view_thread/270067

    – Edgarmtze

    3 de abril de 2011 a las 4:26


  • Consulte esta pregunta: stackoverflow.com/questions/1309263/…

    – Roberto Gamble

    4 de abril de 2011 a las 18:23

  • También existe el algoritmo de filtrado de mediana de tiempo constante. Hay una implementación para 2D en scikits.image, con un área de filtro octogonal.

    usuario227667

    15 de abril de 2011 a las 9:50

avatar de usuario
AShelly

he implementado un calculadora de mediana móvil en C aquí (Esencia). Utiliza una estructura de montón max-median-min: La mediana está en el montón[0] (que está en el centro de una matriz de elementos K). Hay un minheap que comienza en heap[ 1]y un maxheap (usando indexación negativa) en el montón[-1].
No es exactamente lo mismo que el Implementación de Turlach desde la fuente R: esta admite valores que se insertan sobre la marcha, mientras que la versión R actúa en un búfer completo a la vez. Pero creo que la complejidad del tiempo es la misma. Y podría usarse fácilmente para implementar una versión de búfer completa (posiblemente con la adición de algún código para manejar las “reglas finales” de R).

Interfaz:

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

  • Puedo confirmar que esto funciona y es rápido. Sería bueno tener la capacidad de hacer estallar elementos sin insertarlos (para acomodar los valores faltantes) y especificar un percentil arbitrario. Sin embargo, estos son probablemente ajustes fáciles. ¡Buen trabajo!

    – Rico C

    15 mayo 2011 a las 18:14

  • Implementar PopOldest() sería fácil: la posición del elemento más antiguo en el montón es p=pos[(idx-ct+N)%N]. Si está en el minheap, cámbialo hasta el final, luego ordena hacia abajo para asegurarte de que el elemento intercambiado esté en el lugar correcto: if (p>0) {exchange(p,minCt); m->ct--; minSortDown(p*2);. De lo contrario, haga lo mismo con maxheap, excepto que para manejar el caso especial de p == 0, debe hacer un maxSortDown( p*2||-1).

    – A Shelly

    16 de mayo de 2011 a las 6:57

  • La implementación de “KthPercentile” sería un poco más complicada pero no tan mala. Para un K entre 0,0 y 1,0, heap apuntaría al elemento KNORTE. maxCt sería ctk, minCt sería ct-1-maxCt. La parte complicada sería inicializar la matriz pos para que los elementos iniciales se distribuyan correctamente. Sería algo así como: para cada i: punto pos[i] al siguiente elemento en el maxheap hasta que contenga más del K por ciento de los elementos hasta el momento, luego cambie al minheap.

    – A Shelly

    16 de mayo de 2011 a las 7:43

  • Aquí hay algunos puntos de referencia: github.com/suomela/median-filter — en resumen, este enfoque parece funcionar muy bien en general, pero para algunas distribuciones de datos es posible hacerlo mejor con un algoritmo basado en clasificación.

    – Jukka Suomela

    21 de abril de 2014 a las 11:24

  • Aviso para cualquier persona interesada, este código también se puede encontrar en movstat/medacc.c de la Biblioteca Científica GNU (GSL; gnu.org/software/gsl) y es accesible a través del gsl_movstat_median() interfaz.

    – sircolinton

    5 de julio de 2019 a las 15:57

OpenCV tiene un MedianBlur función que parece hacer lo que quieres. Sé que es una mediana rodante. No puedo decir si es la “mediana rodante de Turlach” específicamente. Sin embargo, es bastante rápido y admite subprocesos múltiples cuando está disponible.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad