El trabajo desarrollado en esta tesis tuvo como objetivo el diseño, implementación y evaluación de un índice distribuido para objetos en espacios métricos y su respectiva estrategia de procesamiento paralelo de consultas para máquinas de búsqueda. / Tesis doctoral de la Facultad de Ciencias Físicomatemáticas y Naturales (Universidad Nacional de San Luis). Grado alcanzado: Doctor en Ciencias de la Computación. Director de tesis: Martín Mauricio; co-director: Marcela Printista.

El filtro mediano es una de las operaciones básicas en el procesamiento de imágenes digitales, su función es la de eliminar el ruido impulsivo sin alterar la información de la imagen. A pesar de estas características, su uso se ve restringido debido al alto costo computacional del filtro. Las propuestas tradicionales de solución, consisten en disminuir la complejidad del algoritmo del filtro mediano, y en vectorizar los algoritmos existentes. Esta vectorización se realiza al utilizar las unidades SIMD (Single Instruction Multiple Data - Instrucción Única Múltiples Datos) de los procesadores modernos. Ésta les permite realizar una misma operación a un conjunto, o vector, de datos de manera simultánea, con lo que se obtiene un mejor desempeño computacional. En el presente trabajo se implementa el filtro mediano con el algoritmo vectorial propuesto por Kolte [1], el cual aprovecha las ventajas de las unidades SIMD. La eficiencia computacional de la implementación realizada se compara con el algoritmo Filtro Mediano en Tiempo Constante, propuesto recientemente por Perreault [2], el cual presenta una complejidad de O(1). La implementación realizada es 75 y 18.5 veces mas rápida que la implementación de referencia, para áreas de análisis de 3 x 3 y 5 x 5 respectivamente. Se concluye además que la vectorización de un algoritmo no necesariamente obtiene los mismos resultados que un algoritmo diseñado específicamente para ser implementado en unidades vectoriales [3]. / Tesis

No description available.

El filtro mediano es una de las operaciones básicas en el procesamiento de imágenes digitales, su función es la de eliminar el ruido impulsivo sin alterar la información de la imagen. A pesar de estas características, su uso se ve restringido debido al alto costo computacional del filtro. Las propuestas tradicionales de solución, consisten en disminuir la complejidad del algoritmo del filtro mediano, y en vectorizar los algoritmos existentes. Esta vectorización se realiza al utilizar las unidades SIMD (Single Instruction Multiple Data - Instrucción Única Múltiples Datos) de los procesadores modernos. Ésta les permite realizar una misma operación a un conjunto, o vector, de datos de manera simultánea, con lo que se obtiene un mejor desempeño computacional. En el presente trabajo se implementa el filtro mediano con el algoritmo vectorial propuesto por Kolte [1], el cual aprovecha las ventajas de las unidades SIMD. La eficiencia computacional de la implementación realizada se compara con el algoritmo Filtro Mediano en Tiempo Constante, propuesto recientemente por Perreault [2], el cual presenta una complejidad de O(1). La implementación realizada es 75 y 18.5 veces mas rápida que la implementación de referencia, para áreas de análisis de 3 x 3 y 5 x 5 respectivamente. Se concluye además que la vectorización de un algoritmo no necesariamente obtiene los mismos resultados que un algoritmo diseñado específicamente para ser implementado en unidades vectoriales [3].

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.

En esta tesis se aborda la eliminaci'on de ruido impulsivo, gaussiano y speckle en im'agenes a color y en escala de gises. Como caso particular se puede mencionar la eliminaci'on de ruido en im'agenes m'edicas. Algunos m'etodos de filtrado son costosos computacionalmente y m'as a'un, si las im'agenes son de gran tama¿no. Con el fin de reducir el coste computacional de dichos m'etodos, en esta tesis se utiliza hardware que soporta procesamiento paralelo, como lo son los cores CPU con procesadores multicore y GPUs con procesadores manycore.En las implementaciones paralelas en CUDA, se configuran algunas caracter'¿sticas con la finalidad de optimizar el procesamiento de la aplicaci'on en las GPUs. Esta tesis estudia por un lado, el rendimiento computacional obtenido en el proceso de eliminaci'on de ruido impulsivo y uniforme. Por otro lado, se eval'ua la calidad despu'es de realizar el proceso de filtrado. El rendimiento computacional se ha obtenido con la paralelizaci'on de los algoritmos en CPU y/o GPU. Para obtener buena calidad en la imagen filtrada, primero se detectan los p'¿xeles corruptos y luego son filtrados solo los p'¿xeles que se han detectado como corruptos. Por lo que respecta a la eliminaci'on de ruido gaussiano y speckle, el an'alisis del filtro difusivo no lineal ha demostrado ser eficaz para este caso. Los algoritmos que se utilizan para eliminar el ruido impulsivo y uniforme en las im'agenes, y sus implementaciones secuenciales y paralelas se han evaluado experimentalmente en tiempo de ejecuci'on (speedup) y eficiencia en tres equipos de c'omputo de altas prestaciones. Los resultados han mostrado que las implementaciones paralelas disminuyen considerablemente los tiempos de ejecuci'on secuenciales. Finalmente, en esta tesis se propone un m'etodo para reducir eficientemente el ruido en las im'agenes sin tener informaci'on inicial del tipo de ruido contenido en ellas. I / Sánchez Cervantes, MG. (2013). Algoritmos de detección y filtrado de imágenes para arquitecturas multicore y manycore [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/28854 / TESIS