Optimal vicinity 2D median filter for fixed-point or floating-point values

dc.contributor.advisorCarranza De La Cruz, Cesar Alberto
dc.contributor.authorChang Fu, Javier
dc.date.accessioned2024-06-19T20:49:03Z
dc.date.available2024-06-19T20:49:03Z
dc.date.created2024
dc.date.issued2024-06-19
dc.description.abstractLos 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.es_ES
dc.description.abstractMedian 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.es_ES
dc.identifier.urihttp://hdl.handle.net/20.500.12404/28069
dc.language.isoenges_ES
dc.publisherPontificia Universidad Católica del Perúes_ES
dc.publisher.countryPEes_ES
dc.rightsinfo:eu-repo/semantics/openAccesses_ES
dc.rights.urihttp://creativecommons.org/licenses/by/2.5/pe/*
dc.subjectProcesamiento paralelo (Computadoras electrónicas)es_ES
dc.subjectProcesamiento de imágenes digitaleses_ES
dc.subjectAlgoritmoses_ES
dc.subject.ocdehttps://purl.org/pe-repo/ocde/ford#2.00.00es_ES
dc.titleOptimal vicinity 2D median filter for fixed-point or floating-point valueses_ES
dc.typeinfo:eu-repo/semantics/masterThesises_ES
renati.advisor.dni09641576
renati.advisor.orcidhttps://orcid.org/0000-0003-1222-0118es_ES
renati.author.dni09337793
renati.discipline613077es_ES
renati.jurorCastañeda Aphan, Benjamines_ES
renati.jurorCarranza De La Cruz, Cesar Albertoes_ES
renati.jurorCataño Sanchez, Miguel Angeles_ES
renati.levelhttps://purl.org/pe-repo/renati/level#maestroes_ES
renati.typehttps://purl.org/pe-repo/renati/type#tesises_ES
thesis.degree.disciplineProcesamiento de Señales e Imágenes Digitaleses_ES
thesis.degree.grantorPontificia Universidad Católica del Perú. Escuela de Posgradoes_ES
thesis.degree.levelMaestríaes_ES
thesis.degree.nameMaestro en Procesamiento de Señales e Imágenes Digitales.es_ES

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
CHANG_FU_JAVIER_OPTIMAL_VICINITY_2D.pdf
Size:
694.12 KB
Format:
Adobe Portable Document Format
Description:
Texto completo
No Thumbnail Available
Name:
CHANG_FU_JAVIER_T.pdf
Size:
3.85 MB
Format:
Adobe Portable Document Format
Description:
Reporte de originalidad

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: