Los filtros medianos son una técnica digital no lineal normalmente usada para remover
ruido blanco, ’sal y pimienta’ de imágenes digitales. Consiste en reemplazar el valor de
cada pixel por la mediana de los valores circundantes.
Las implementaciones en punto flotante usan ordenamientos con técnicas de comparación
para encontrar la mediana. Un método trivial de ordenar n elementos tiene una
complejidad de O(n2), y los ordenamientos más rápidos tienen complejidad de O(n log n)
al calcular la mediana de n elementos. Sin embargo, éstos algoritmos suelen tener fuerte
divergencia en su ejecución.
Otras implementaciones usan algoritmos basados en histogramas, y obtienen sus mejores
desempeños cuando operan con filtros de ventanas grandes. Estos algoritmos pueden
alcanzar tiempo constante al evaluar filtros medianos, es decir, presenta una complejidad
de O(1).
El presente trabajo propone un algoritmo de filtro mediano rápido y altamente paralelizable.
Se basa en ordenamientos sin divergencia con ejecución O(n log2 n) y mezclas O(n)
con los cuales se puede calcular grupos de pixeles en paralelo. Este método se beneficia de
la redundancia de valores en pixeles próximos y encuentra la vecindad de procesamiento
óptima que minimiza el número de operaciones promedio por pixel. El presente trabajo
(i) puede procesar indiferentemente imágenes en punto fijo o flotante, (ii) aprovecha al
máximo el paralelismo de múltiples arquitecturas, (iii) ha sido implementado en CPU y
GPU, (iv) se logra una aceleración respecto al estado del arte. / Median filter is a non-linear digital technique often used to remove additive white, salt
and pepper noise from images. It replaces each pixel value by the median of the surrounding
pixels.
Floating point implementations use sorting and comparing techniques to find median.
A common method for sorting n elements has complexity O(n2), and the fastest sorting
ones have complexity O(n log n) when computing the median of n elements. However,
such fastest algorithms have strong divergence in their execution.
Other implementations use histogram based algorithms and have their best performance
for large size windows. These histogram based achieve constant time median
filtering, exhibiting O(1) complexity.
A fast and highly parallelizable median filter algorithm is proposed. It is based on
sorting without divergence execution O(n log2 n) and merge O(n) that computes groups
of pixels in parallel. The method benefits from redundancy values in neighboring pixels
and finds the optimal vicinity that minimize the average operations per pixel. The
present work (i) can process either fixed or floating point images, (ii) take full advantage
of parallelism of multiple architectures, (iii) have been implemented on CPU and GPU,
(iv) the results speed up state of the art implementations.
| Identifer | oai:union.ndltd.org:PUCP/oai:tesis.pucp.edu.pe:20.500.12404/28069 |
| Date | 19 June 2024 |
| Creators | Chang Fu, Javier |
| Contributors | Carranza De La Cruz, Cesar Alberto |
| Publisher | Pontificia Universidad Católica del Perú, PE |
| Source Sets | Pontificia Universidad Católica del Perú |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/masterThesis |
| Format | application/pdf, application/pdf |
| Rights | info:eu-repo/semantics/openAccess, http://creativecommons.org/licenses/by/2.5/pe/ |
Page generated in 0.002 seconds