Recursión - Revolvedor de Imágenes

La recursión es una técnica muy utilizada en programación. Con esta técnica se resuelven problemas resolviendo un problema similar, pero para casos más pequeños. Podemos construir conjuntos de objetos o procesos utilizando reglas recursivas y valores iniciales. Las funciones recursivas son funciones que se auto-invocan, utilizando cada vez conjuntos o elementos más pequeños, hasta llegar a un punto en donde se utiliza la condición inicial en lugar de auto-invocarse. En esta experiencia de laboratorio practicarás la definición e implementación de funciones recursivas para revolver una imagen y hacerla incomprensible.

Objetivos:

Definir e implementar funciones recursivas.
Practicar el procesamiento de imágenes.
Practicar el uso de estructuras de control y repetición.

Pre-Lab:

Antes de llegar al laboratorio debes:

Haber repasado los conceptos relacionados a funciones recursivas.
Haber estudiado los conceptos e instrucciones para la sesión de laboratorio.
Haber tomado el quiz Pre-Lab disponible en Moodle.

Revolver imágenes digitalmente

Al revolver las imágenes digitalmente reordenamos los píxeles de las imágenes para romper la relación entre píxeles adyacentes y así hacer que la imagen original sea incomprensible. Esta técnica se usa mucho para cifrar imágenes y esconder datos. [1]

Figura 1. La imagen de la izquierda fue cifrada utilizando la técnica de revolver la imagen y se obtuvo la imagen de la derecha. Tomada de [2].

Existen muchos métodos que han sido propuestos para revolver imágenes. En esta experiencia de laboratorio utilizarás un método muy simple que tiene una implementación natural usando funciones recursivas.

¡Revuélvela!

El método que utilizarás para revolver las imágenes funciona intercambiando rectángulos de una imagen un cierto número de veces, según lo establezca el nivel. La Figura 2 ilustra un revoltillo de nivel 1 de una imagen: se intercambian los cuadrantes diagonales. Observa también la Figura 6.

Figura 2. Revoltillo de nivel 1: (a) es la imagen original dividida en cuadrantes, (b) es la imagen luego de revolverla con el primer nivel intercambiando cuadrantes diagonales.

El revoltillo del siguiente nivel, nivel 2, primero intercambia las mitades izquierda y derecha de la imagen. Luego le aplica un revoltillo de nivel 1 a cada cuadrante. Observa que el revoltillo de nivel 1 es aplicado a cada uno de los cuatro cuadrantes de la imagen original.

Figura 3. Revoltillo de nivel 2: (a) es la imagen original, (b) es la imagen luego de intercambiar las mitades izquierda y derecha, (c) es la imagen luego de aplicar revoltillo de nivel 1 a cada cuadrante.

Pregunta: ¿Cuál de las figuras (a), (b), (c), (d) (en la Figura 5) representa el resultado de hacerle un revoltillo de nivel 2 al dibujo de el pingüino en la Figura 4?

Figura 4.

Figura 5.

Si continuamos el patrón, un revoltillo de nivel 3 comienza intercambiando los cuadrantes diagonales. Luego le aplica un revoltillo de nivel 2 a cada cuadrante: intercambia las mitades izquierda y derecha, y aplica el revoltillo de nivel 1 a cada nuevo cuadrante. La Figura 8 muestra el proceso de hacer un revoltillo de nivel 3.

Para revolver una imagen hacemos este proceso para un cierto nivel N. ¿Cuál es el patrón? ¿Cómo comenzaría el revoltillo de nivel 4? ¿En cuántos cuadrantes habremos dividido la figura original al completar el revoltillo?

El algoritmo para revolver que se acaba de describir es su propio inverso. Esto es, si le aplicas el mismo algoritmo a la imagen revuelta, debes obtener la imagen original.

Las siguientes figuras ilustran los intercambios que hacen los revoltillos de nivel 1, 2 y 3.

Figura 6. Revoltillo de nivel 1: se intercambian los cuadrantes diagonales.

Figura 7. Revoltillo de nivel 2: (a) se intercambian las mitades izquierda y derecha, (b) se aplica un revoltillo de nivel 1 a cada cuadrante.

Figura 8. Revoltillo de nivel 3: (a) se intercambian los cuadrantes diagonales para luego aplicar revoltillo de nivel 2 a cada cuadrante, (b) se intercambian mitades izquierda y derecha en cada cuadrante, (c) se aplica un revoltillo de nivel 1 a cada nuevo cuadrante.

¿Cuál de los siguientes sería el resultado de un “scramble” de nivel 2 en la imagen del pingüino?

Un “scramble” de nivel 1 representa mover diagonalmente los cuadrantes de la imagen, y uno de nivel 2 representa invertir las mitades de la imagen, y luego aplicar un “scramble” de nivel 1. Si invertimos las mitades del pingüino, su lado izquierdo ahora estará a la derecha, y su lado derecho ahora estará a la izquierda, como se puede apreciar en la segunda opción. Si tomamos los cuadrantes de la imagen cuyas mitadas han sido intercambiadas, y e intercambiamos diagonalmente el resultado será la primera imagen.

¿Cuál es el output del siguiente programa?

"01234567" ”45670123” ”67452301” ”76543210” Cada invocación de la función recursiva revoltillo intercambia la primera y segunda mitad del string que es pasado como argumento. El árbol de recursión para la invocación revoltillo(“01234567”,2) es el siguiente y produce como resultado el string ”67452301”. Por lo tanto, la tercera opción es la correcta.

Funciones adicionales provistas en el proyecto

El proyecto en el que trabajarás hoy contiene la función cropSwap que implementa la funcionalidad de intercambiar los píxeles contenidos en dos rectángulos congruentes dentro de una imagen. Su prototipo es:

void ImageScrambler::cropSwap(QImage &img, int x0, int y0, int x1, int y1, int width, int height );

Sus parámetros son:

img: referencia a la imagen que se desea modificar (un objeto de clase QImage)
x0, y0,x1, y1: coordenadas de las esquinas superior izquierda de los rectángulos.
width, height: ancho y altura (en píxeles) de los rectángulos.

Por ejemplo, si deseamos intercambiar los píxeles de la mitad superior e inferior de una imagen P de ancho 100 y alto 150, invocamos la función así:

cropSwap(P, 0, 0, 0, 75, 100, 75 );

Sesión de laboratorio:

El proyecto ImageScrambler contiene el esqueleto de una aplicación para revolver y "des-revolver" imágenes. En la experiencia de laboratorio de hoy trabajarás con el archivo Filter.cpp para completar la aplicación.

Ejercicio 1 - Pseudocódigo de la función para revolver

Escribe el pseudocódigo para expresar el algoritmo de revolver descrito arriba como una función recursiva.

Ejercicio 2 - Función recursiva para revolver la imagen

Instrucciones

Carga a QtCreator el proyecto ImageScrambler. Hay dos maneras de hacer esto:
- Utilizando la máquina virtual: Haz doble “click” en el archivo ImageScrambler.pro que se encuentra en el directorio /home/eip/labs/recursion-imagescrambler 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/recursion-imagescrambler para descargar la carpeta recursion-imagescrambler de Bitbucket. En esa carpeta, haz doble “click” en el archivo ImageScrambler.pro.
El código que te proveemos crea la interfaz de la Figura 9.
Figura 9. Interfaz del proyecto Image Scrambler.
El botón que dice Scramble Image se programó para que invoque una función llamada ScrambleFilter.
Completa la función ScrambleFilter contenida en el archivo Filter.cpp de modo que implemente el algoritmo recursivo de revolver imágenes. La función tiene el siguiente formato: QImage ImageScrambler::ScrambleFilter(QImage image, int N, int sx, int sy, int width, int height);
Usa esta imagen para validar la función que implementaste.

Entregas

Utiliza "Entrega 1" en Moodle para entregar el archivo con el pseudocódigo de la función para revolver.
Utiliza "Entrega 2" 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] F. Maleki et al., ‘‘An Image Encryption System by Cellular Automata with Memory,’’ Proc. 3rd Int’l Conf. Availability, Reliability, and Security, IEEE CS Press, 2008, pp. 12661271.

[2] Dalhoum, Abdel Latif Abu, et al. "Digital Image Scrambling Using 2 D Cellular Automata." IEEE MultiMedia 19.4 (2012): 28-36.

[3] http://www.instructables.com/id/Python-Programming-recursion/

recursion-revolvedordeimagenes