Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Talleres/Taller 2 del 2007

Consigna

Dado el filtro que le toque implementar:

• Acote lo mejor posible la complejidad computacional del algoritmo que utiliza la aplicación Imago.
• Compruebe con ejemplos si su conclusión es correcta, utilizando el tiempo que toman las operaciones, que será mostrado por consola. Obtenga además, una aproximación de la constante $k$ que multiplicada por la función de orden de la complejidad, acote el tiempo aproximado de respuesta.
• Idee un algoritmo que realice el mismo trabajo más eficientemente. Acote la complejidad del problema para el peor caso, y compare con la complejidad del algoritmo que implementa la aplicación Imago.
• Implemente y pruebe sobre los mismos ejemplos. Compruebe sus conclusiones y obtenga una aproximación de la constante $k$ para el nuevo algoritmo.

Filtros a implementar

Mediana

Descripción

Cada píxel de la imagen filtrada se calcula obteniendo la media de los nueve píxeles de la imagen original que forman el cuadrado de $3\times 3$ con la posición del píxel calculado como centro.

Algoritmo que implementa la aplicación

Por cada píxel se toman los 9 píxeles correspondientes, se ordenan por su valor y se toma el píxel central.

Moda

Descripción

Cada píxel de la imagen filtrada se calcula obteniendo la moda de los nueve píxeles de la imagen original que forman el cuadrado de $3\times 3$ con la posición del píxel calculado como centro.

Algoritmo que implementa la aplicación

Por cada píxel se toman los diferentes colores que aparecen entre los 9 píxeles correspondientes, se ordenan con los siguientes criterios, en el siguiente orden:

1. El que aparece más veces.
2. El que tiene valor más cercano al del píxel central.

Finalmente se toma el que queda en el primer lugar.

Suavizado selectivo (+)

Descripción

Cada píxel de la imagen filtrada se calcula obteniendo el promedio de los siete píxeles de la imagen original que quedan de los nueve que forman el cuadrado de $3\times 3$ con la posición del píxel calculado como centro, luego de eliminarse los dos que quedan en los extremos una vez ordenados por su valor.

Algoritmo que implementa la aplicación

Por cada píxel se toman los 9 píxeles correspondientes, se ordenan por su valor, se toman los siete centrales y se calcula su promedio.

Suavizado selectivo (-)

Descripción

Cada píxel de la imagen filtrada se calcula obteniendo el promedio de los ocho píxeles de la imagen original que quedan de los nueve que forman el cuadrado de $3\times 3$ con la posición del píxel calculado como centro, luego de eliminarse el que menos aparece.

Algoritmo que implementa la aplicación

Por cada píxel se toman los diferentes colores que aparecen entre los 9 píxeles correspondientes, se ordenan con los siguientes criterios, en el siguiente orden:

1. El que aparece menos veces.
2. El que tiene valor más lejano al del píxel central.

Finalmente se elimina el que queda en el primer lugar, y se calcula el promedio de los que quedan.

Información complementaria

Introducción a los filtros lineales de imágenes

Los filtros lineales se basan en cambiar el nivel de gris de un punto en función de los puntos de su entorno mediante la aplicación de una mascara del tipo:

$w_{1}$	$w_{2}$	$w_{3}$
$w_{4}$	$w_{5}$	$w_{6}$
$w_{7}$	$w_{8}$	$w_{9}$

Donde el nivel de gris del punto central viene dado por:

$R={\frac {\sum _{i=1}^{9}(w_{i}p_{i})}{\sum _{i=1}^{9}(w_{i})}}$

siendo $p_{i}$ el nivel de gris de los puntos de la imagen a filtrar.

Máscaras

Ejemplos de máscaras

Media

$1$	$1$	$1$
$1$	$1$	$1$
$1$	$1$	$1$

Gaussiano

$1$	$2$	$1$
$2$	$4$	$2$
$1$	$2$	$1$

Filtro de mediana

En este caso el nivel de gris también depende de los niveles de gris de los puntos del entrono pero en este caso no es función lineal de estos, sino que es la mediana de los niveles de gris del entorno.