Algoritmos de ordenamiento - El turista impertinente

main1.png main2.png main3.png

Dos tareas comunes cuando se trabaja con arreglos de datos son buscar datos y ordenarlos de forma ascendente o descendente. Dos algoritmos de ordenamiento sencillos y bien conocidos son el ordenamiento de selección (Selection Sort) y el ordenamiento de burbuja (Bubble Sort). Los algoritmos de ordenamiento forman parte de muchos programas; por ejemplo, listas de contactos, hojas de cálculo, y motores de búsqueda. En esta experiencia de laboratorio completarás una aplicación para procesar imágenes y practicarás el uso de algoritmos de ordenamiento. También aprenderás sobre la biblioteca QImage de Qt y sobre el filtro de mediana utilizado en el procesamiento de imágenes para remover "ruido"; en este caso, un turista impertinente.

Esta experiencia de laboratorio es una adaptación del "nifty assignment" presentado por John Nicholson en [1].

Objetivos:

  1. Practicar el ordenamiento de arreglos por selección y por método de burbuja.

  2. Practicar el uso de estructuras de decisión y repetición.

  3. Utilizar métodos de la clase vector de C++.

  4. Utilizar los métodos de la clase QImage de Qt para manipular los píxeles de una imagen.

  5. Aprender sobre el filtro de mediana para el procesamiento de imágenes.

Pre-Lab:

Antes de llegar al laboratorio debes:

  1. Repasar los algoritmos de ordenamiento de selección y de burbuja.

  2. Familiarizarte con los métodos push_back(), at(i), size(), y clear() de la clase vector de C++.

  3. Familiarizarte con los métodos width(), height(), pixel(i, j), y setPixel(i,j, pixel) de la clase QImage de Qt.

  4. Estudiar los conceptos e instrucciones para la sesión de laboratorio.

  5. Tomar el quiz Pre-Lab, disponible en Moodle.

Píxeles

Al elemento más pequeño de una imagen se le llama píxel. Cada píxel contiene un color que se obtiene mediante una combinación de tonalidades de los colores primarios rojo, verde y azul. La Figura 2 ilustra como se codifica la información de color de un píxel usando los bytes de un entero sin signo. Los tres bytes menos significativos indican las intensidades de rojo, verde y azul. El byte más significativo especifica lo que se conoce como la composición alfa, la cual define la opacidad del píxel (0xff es totalmente opaco y 0x00 es totalmente transparente, e.g. invisible). A esta combinación se le llama el ARGB del color por las siglas de "Alpha-Red-Green-Blue". Por ejemplo, un píxel de color rojo puro tiene una representación RGB 0xffff0000, mientras que un píxel de color blanco tiene una representación RGB de 0xffffffff (ya que el color blanco es la combinación de los tonos rojo, verde y azul en toda su intensidad). A través de esta experiencia de laboratorio, asumiremos que el alfa de los píxeles tiene opacidad total (0xff).

figure2.png

Figura 1. Distribución de bits para la composición alpha y las tonalidades de rojo, verde y azul dentro de la representación ARGB. Cada tonalidad puede tener valores entre 0x00 (los ocho bits en 0) y 0xFF (los 8 bits en 1).

En Qt se utiliza el tipo de dato QRgb para representar valores ARGB. Utilizando ciertas funciones que describimos abajo, podemos obtener los componentes rojo, verde y azul del valor QRgb del píxel y así manipular las imágenes. En esta experiencia de laboratorio, no vamos a manipular el canal alfa de los píxeles.

La experiencia de laboratorio de hoy utilizará la clase QImage. Esta clase permite acceder a los datos de los píxeles de una imagen para poder manipularla. La documentación de la clase QImage se encuentra en http://doc.qt.io/qt-4.8/qimage.html.

Procesamiento de imágenes

El procesamiento de imágenes es usado en una amplia variedad de aplicaciones que son relevantes socialmente. En las redes sociales, prácticamente cada vez que publicas una imagen, hay un filtro de procesamiento de imágenes tomando efecto. Las redes sociales, las cámaras, y los dispositivos móviles usan el procesamiento de imágenes para reconocimiento facial. Asimismo, investigadores usan el procesamiento de imágenes para contar organismos dentro de un espacio explorado, para detectar anomalías en tomografías computarizadas ("CT scans"), y en general, para obtener mejor información acerca de objetos explorados.

El filtro de mediana es uno de los filtros más simples utilizados en el procesamiento de imágenes. Este filtro es muy útil para remover objetos no deseados de las imágenes. Digamos que encuentras el árbol más interesante del mundo y quieres fotografiarlo; colocas tu equipo fotográfico, la luz es perfecta, y los colores son hermosos. Para estar segura de obtener la foto perfecta, tomas tres de ellas. Sin embargo, en el momento preciso en que se tomaron las fotos, un turista impertinente se metió en el medio de tu creación. El filtro de mediana te ayudará a remover el turista de la foto, fusionando las tres fotos en una en la que no aparecerá el turista.

Dadas 3 o más imágenes del mismo espacio, el filtro de mediana trabaja como sigue: para el píxel en cada posición encuentra el color correspondiente a la mediana de los colores de las tres imágenes, luego usa el color correspondiente a la mediana en la imagen fusionada.

main2.png

Figura 2. Ilustración del algoritmo del filtro de mediana en un píxel dado. Se determinan los colores de los píxeles correspondientes en las tres imágenes, luego se calcula la mediana. La mediana del píxel se usa en la posición correspondiente en la imagen fusionada.

Mediana

La mediana de una lista de números es el valor que separa la mitad de los números con valor mayor, de la mitad de los números con valor menor. Para calcularla, se ordena la lista en orden ascendente. Si la cantidad de números en la lista es impar, se escoge el valor del medio. Si la cantidad de números en la lista es par, se toma el promedio de los dos valores en el medio.

Por ejemplo, la mediana de {3,5,2,7,11} es 5 pues el arreglo ordenado es {2, 3, 5, 7, 11}. La mediana de {3,9,3,2,10,11} es 6 pues el arreglo ordenado es {2, 3, 3, 9, 10, 11} y el promedio de 3 y 9 es 6.

Mediana de píxeles

El método que usaremos en esta experiencia de laboratorio para hallar la mediana de varios píxeles será el siguiente: hallaremos la mediana de sus componentes rojos, verdes, azules y luego compondremos un nuevo píxel usando esas medianas. El siguiente ejemplo ilustra el procedimiento.

Ejemplo:

Supón que debemos hallar la mediana de los tres píxeles con valores 0xff223344, 0xff112233, y 0xff001155.

  • La mediana del componente rojo es 0x11 (dado que los componentes rojos son 0x22, 0x11 y 0x00).
  • La mediana del componente verde es 0x22 (dado que los componentes verdes son 0x33, 0x22 y 0x11).
  • La mediana del componente azul es 0x44 (dado que los componentes azules son 0x44, 0x33 y 0x55).

Por lo tanto, la mediana de los píxeles sera 0xff112244, compuesto por las medianas de los componentes de colores rojo, verde y azul.

Nota que el resultado puede ser un píxel con un color que no existía entre los originales. Sin embargo, ese detalle no afecta mucho la aplicación que estamos realizando en esta experiencia de laboratorio.

¿Cuál es la mediana de los siguientes tres píxeles (según explicamos en la sección Mediana de Píxeles)?
0x00FF00 , 0x00FE01 , 0x00FD00 0x01FG00 0x00FE00 0x00FF01 0x01FD01 Para encontrar la mediana de un conjunto de valores, primero se ordenan de forma ascendente. En el caso de una lista con un largo impar, la media corresponde al valor del medio de la lista ordenada. En este caso, como estamos manejando pixeles, se computa la mediana de los valores de rojo (R), verde (G), y azul (B) individualmente. Los valores de rojo en este vector son 00, 00 y 00. Por lo tanto el valor del medio es 00. Los valores de verde en este vector son FF, FE y FD, que en orden son FD, FE, y FF. Por lo tanto, el valor del medio es FE. Los valores de azul son 00, 01 y 00, que en orden son 00, 00 y 01. Por lo tanto, el valor del medio es 00. Uniendo estos valores, construimos la mediana: 0x00FE00.

Suponga que la función sort(int A[], int size) recibe como argumentos un arreglo de enteros y el tamaño del arreglo y ordena el arreglo en orden ascendente. ¿Cuál de los siguientes pedazos de código devolverá la mediana de los enteros almacenados en el arreglo? Asuma que el número de elementos en el arreglo es impar. sort(A, size); return A[size/2]; sort(A/2, size); return A; sort(A, size/2); return A; La respuesta correcta es la primera opción, ya que primero necesitamos ordenar el arreglo y luego buscar el valor del medio para así calcular la mediana. La instrucción sort(A, size); ordena el arreglo de forma ascendente, y entonces es solo necesario encontrar el valor en el medio con return A[size/2]; ya que tenemos un número impar de elementos. La segunda opción no es válida, ya que la operación A/2 no se podrá realizar. La tercera opción solo va a ordenar la primera mitad, ya que en la función sort(), se ordena hasta la posición dada con el argumento size lo cual no permitirá calcular la mediana.

Bibliotecas

Para esta experiencia de laboratorio necesitarás saber cómo utilizar los siguientes métodos de la clase vector de C++:

  • push_back() // inserta un elemento al final de un vector
  • at(i) // obtiene el elemento en la posición i
  • size() // obtiene el número de elementos en el vector
  • clear() // vacía el vector / remueve los elementos.

Las siguientes funciones son útiles para trabajar con datos de tipo QRgb:

  • qRed(pixel) // devuelve el tono del color rojo del píxel
  • qGreen(pixel) // devuelve el tono del color verde del píxel
  • qBlue(pixel) // devuelve el tono del color azul del píxel

Los objetos de clase QImage tienen los siguiente métodos que serán útiles para manipular los píxeles de las imágenes:

  • width() // devuelve el valor entero del ancho de la imagen
  • height() // devuelve el valor entero de la altura de la imagen
  • pixel(i, j) // devuelve el QRgb del píxel en la posición (i,j)
  • setPixel(i,j, pixel) // modifica el valor del píxel en la posición (i, j) al valor píxel QRgb.
  • qRgb(int red, int green, int blue) // devuelve un píxel QRgb compuesto de los valores de rojo, verde y azul recibidos.

Ejemplos:

  1. QRgb myRgb = qRgb(0xff, 0x00, 0xff);: Asigna a myRgb el valor 0xff00ff que representa el color figure3.png

    Nota que el valor 0xff00ff representa los valores 0xff, 0x0, 0xff, que corresponden a los componentes rojo, verde y azul de myRgb.

  2. Si la siguiente imagen 4 x 4 de píxeles representa el objeto originalImage,

    main1.png

    entonces originalImage.pixel(2,1) devuelve un valor rgb que representa el color azul (0x0000ff).

    1. La siguiente instrucción asigna el color rojo al píxel en posición (2,3) en la imagen editada:

      editedImage.setPixel(2,3,qRgb(0xff,0x00,0x00));.

    2. La siguiente instrucción le asigna a greenContent el valor del tono de verde que contiene el pixel (1,1) de originalImage:

      int greenContent = qGreen(originalImage.pixel(1,1));.

    3. El siguiente código le asigna al componente rojo del píxel (1,1) de editedImage el promedio de los valores del tono de rojo que contiene el píxel (1,1) de originalImage1 y originalImage2 y lo mismo hace con los componentes verde y de azul.

#include <QImage>

using namespace std;
int main() {
    int redEdit;
    int greenEdit;
    int blueEdit;
    QImage editedImage;

   redEdit=(qRed(originalImage1.pixel(1,1)) + qRed(originalImage2.pixel(1,1)))/2;
   greenEdit=(qGreen(originalImage1.pixel(1,1)) + qGreen(originalImage2.pixel(1,1)))/2;
   blueEdit=(qBlue(originalImage1.pixel(1,1)) + qBlue(originalImage2.pixel(1,1)))/2;

   editedImage.setPixel(1,1,qRgb(redEdit,greenEdit,blueEdit));

   return 0;
}

¿Qué está almacenado en el vector exam al final del código?
0, 3, 5, 6, 10, 15 0, 3, 5, 6, 9, 10, 12 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 0 0, 3, 5 La función push_back() de los vectores inserta el elemento al final del vector. El for loop genera los enteros desde el 0 hasta el 14. Solo los valores que sean divisibles entre 3 y 5 serán añadidos al vector exam. La primera opción está incorrecta ya que faltan 9 y 12, y ambos modulo 3 dan 0. Además, el 15 no estará, ya que el for loop no permite que se ejecute el código cuando la i es 15. La segunda opción es la correcta, ya que como push_back() añade los elementos al final del vector, en este caso los va a añadir en orden ascendente. La tercera opción es incorrecta ya que tiene todos los números de 0-14, y muchos de ellos no son divisibles por 3 o 5. La cuarta y quinta opción también son incorrectas ya que faltan números. Por lo tanto la solución correcta es: 0, 3, 5, 6, 9, 10, 12.

Sesión de laboratorio:

El proyecto PeskyTourist contiene el esqueleto de una aplicación para remover el "ruido" de una imagen. En esta experiencia de laboratorio completarás la aplicación para procesar imágenes, utilizando el filtro de mediana para remover el ruido de una imagen, en este caso, un turista impertinente. Estarás trabajando en el archivo Filter.cpp.

Algoritmo general para remover ruido de una imagen

Input: VI, un vector con N imágenes
Output: una imagen sin ruido
---------------------------------------
1. Para cada posición x,y:
    * P es un vector de tamaño N
    * Asignar a los elementos de P los valores de los
      píxeles en la posicion (x,y) de las N imágenes de VI
    * M = mediana de los píxeles de P
    * Asignar el valor de M al píxel (x,y) de la imagen sin ruido

Ejercicio 1 - Implementar una función para ordenar un vector de enteros

Para hallar la mediana de los componentes de colores de los píxeles, debemos contar con una función de ordenamiento. En esta parte implementarás el ordenamiento de selección.

Instrucciones

  1. Carga a QtCreator el proyecto PeskyTourist. Hay dos maneras de hacer esto:

    • Utilizando la máquina virtual: Haz doble “click” en el archivo PeskyTourist.pro que se encuentra en el directorio /home/Documents/eip/sorting-peskytourist de la máquina virtual.
    • Descargando la carpeta del proyecto de Bitbucket: Utiliza un terminal y escribe el comando git clone http:/bitbucket.org/eip-uprrp/sorting-peskytourist para descargar la carpeta sort-peskytourist de Bitbucket. En esa carpeta, haz doble “click” en el archivo PeskyTourist.pro.

  2. Configura el proyecto y ejecuta el programa marcando la flecha verde en el menú de la izquierda de la ventana de Qt Creator. El código que te proveemos crea la interfaz de la Figura 3.

    figure3.png

    Figura 3. Interfaz del editor de imágenes.

  3. Marca el botón Load Images y busca el directorio ImagesPeskyTourist que contiene las imágenes con el turista impertinente.

  4. Tu primera tarea es completar la función Sort que recibe un vector de enteros. La función debe ordenar los enteros del vector en orden ascendente utilizando el método de selección.

  5. Crea una prueba unitaria para validar la función Sort e invócala desde la función RemoveNoise.

Ejercicio 2 - Calcular la mediana de un vector de enteros

Instrucciones

  1. Completa la función Median que recibe un vector de enteros. La función Median debe invocar la función Sort para ordenar los enteros y calcular la mediana. La función devuelve la mediana calculada.

  2. Crea una prueba unitaria para validar la función Median e invócala desde la función RemoveNoise.

Ejercicio 3 - Calcular la mediana de cada píxel

Completa la función MedianPixel que recibe un vector de píxeles (de tipo QRgb) y devuelve el píxel QRgb correspondiente a la mediana de los píxeles. La mediana de los píxeles se compone de las medianas de cada componente de color en los píxeles.

En el código proveemos una función que puedes usar para validar la función MedianPixel.

Algoritmo:

Para computar la mediana del píxel, para cada uno de los componentes de color (rojo, verde y azul), extrae el componente en un vector e invoca la función Median para calcular la mediana sobre ese vector. Por ejemplo, si recibimos un vector con los píxeles 0xff112233, 0x113344, y 0x224455, una de las primeras tareas del algoritmo sería extraer los componentes rojos y crear un vector con ellos: 0x11, 0x11 y 0x22. Luego se enviaría ese vector a la función Median para obtener la mediana (obtendremos 0x11 como resultado). Esto se realizaría también para los componentes verde y azul.

Ejercicio 4: Remover ruido

Tu última tarea es completar la función RemoveNoise que recibe un vector de imágenes con ruido y la referencia a la imagen editada que tendrá el ruido removido.

Algoritmo:

Para cada posición , forma un vector de píxeles que contendrá los valores de los píxeles en la posición de cada una de las imágenes con ruido. Invoca la función MedianPixel y asigna el valor de la mediana los píxeles en la posición de la imagen editada.

Cuando completes la función, el botón Remove Noise ejecutará tus algoritmos y desplegará la imagen final.

Entrega

Utiliza "Entrega" en Moodle para entregar el archivo Filter.cpp que contiene las funciones que implementaste en esta experiencia de laboratorio. Recuerda utilizar buenas prácticas de programación, incluye el nombre de los programadores y documenta tu programa.

Referencias

[1] John Nicholson, http://nifty.stanford.edu/2014/nicholson-the-pesky-tourist/

results matching ""

    No results matching ""