¿Alguien sabe un algoritmo de filtro de mediana rápida para arreglos de 16 bits (corto sin signo) en C++?Filtro de mediana rápida en C++
Ésta parece bastante prometedora, pero sólo parece trabajar con matrices de bytes. ¿Alguien sabe ya sea cómo modificarlo para trabajar con pantalones cortos o un algoritmo alternativo?
Here (PDF) es algo para C, es un documento con el título "Búsqueda mediana rápida: una implementación ANSI C". El autor dice que es O (log (n)), también proporciona algún código, tal vez te ayude. No es mejor que el código sugerido, pero tal vez una apariencia vale la pena.
El documento vinculado en la pregunta es O (1) que es mejor que O (log n). –
Sí, pero este quizás da más impulsos, pero definitivamente tienes razón. He hecho una pequeña edición, aclarando mi intención. –
@MarkRansom: O (1) no significa automáticamente mejor que O (log (n)) ya que siempre hay una constante que oculta la notación O. En este caso, el algoritmo O (1) es mucho más lento que el algoritmo O (log (n)) (para valores de canal que no sean de 2 bits o quizás de 4 bits). El papel O (1) funciona con histogramas, lo que hace que el tiempo de ejecución por píxel sea proporcional a 2^b, donde b es el número de bits por canal, que para 8 bits es 256 y para 16 bits es 65536 (aunque estos números son constantes, por lo tanto O (1)). Esto rápidamente hace que el algoritmo O (1) sea extremadamente lento, cuantos más bits agregue a los valores del canal. – HelloGoodbye
La técnica en el artículo se basa en crear un histograma con 256 bins para un canal de 8 bits de píxeles. La conversión a 16 bits por canal requeriría un histograma con 65536 bins, y se requiere un histograma para cada columna de la imagen. Inflar los requisitos de memoria en 256 hace que este sea un algoritmo menos eficiente en general, pero probablemente sea factible con el hardware actual.
Usar su optimización propuesta de romper el histograma en secciones gruesas y finas debería reducir aún más el tiempo de ejecución a solo 16x.
Para valores de radio pequeño, creo que encontrará que los métodos tradicionales de filtrado medio serán más efectivos.
Ver ecuaciones 4 y 5 en el siguiente documento. La complejidad es O (N * W) donde W es el ancho del filtro y N es el número de muestras.
Sé que esta pregunta es un poco viejo pero también se interesó en la mediana de filtrado. Si uno está trabajando con señales o imágenes, habrá una gran superposición de datos para la ventana de procesamiento. Esto puede ser aprovechado.
He publicado un código de referencia aquí: 1D moving median filtering in C++
Se basa plantilla así que debería funcionar con la mayoría de tipos de datos POD.
De acuerdo con mis resultados std::nth_element tiene bajo rendimiento para una mediana móvil, ya que debe ordenar la ventana de valores cada vez.
Sin embargo, utilizando un conjunto de valores que se mantienen ordenados, se puede realizar la mediana con 3 operaciones.
La mediana ahora es el valor medio en el grupo.
¡Espero que alguien encuentre esto interesante y contribuya con sus ideas!
Este artículo describe un método para el filtrado de mediana de imágenes que se ejecuta en O (log r) tiempo por píxel, donde r es el radio del filtro, y funciona para cualquier tipo de datos (ya sea 8 bits enteros o dobles):
¿usted intentó std :: nth_element? Es O (n) comparado con O (n log n) para un quicksort. – smocking
No desea modificar este algoritmo para hacer que funcione en corto, ya que el tiempo de ejecución por píxel es proporcional a 2^n, donde n es el número de bits en el tipo de datos que se utiliza. 256 para matrices de 8 bits ya es lo suficientemente doloroso, no desea ir a 65536 para matrices de 16 bits. Vea mi respuesta para un algoritmo más rápido, aunque sea O (log r) por píxel en lugar de O (1). – HelloGoodbye
Si no desea hacer un filtrado mediano, que es lo que hace, por ejemplo, en el procesamiento de imágenes donde encuentra una mediana para cada píxel, pero solo quiere encontrar una mediana, el comentario de @ smocking es relevante. – HelloGoodbye