Revisando cosas en mundocripto me encontré con este post bastante entretenido, aquí un copy/paste:

Lugar: sede de la ACMS (Agencia Castellana de Máxima Seguridad). Despacho del Gran Jefe. Alguien llama a la puerta y pasa.

Bienvenido X28, tengo aquí los detalles de su nueva misión. En primer lugar, usted y el agente Y6 tienen que reunirse con su contacto en Quintanamartingalindez que les dará más instrucciones.

Me temo que no sé dónde queda Quintanamartingalindez, jefe.

No me haga perder el tiempo X28, mírelo en el mapa. Aquí tiene la imagen que le permitirá identificar a la persona que buscan…

Je, je, me parece que esta foto no ha salido demasiado bien, va a tener que repetirla si quiere que lo reconozca.

Déjeme acabar de hablar. Esta es sólo una sombra de la fotografía original, su compañero Y6 tiene la otra, Cuando se reúnan unirán sus fotos obteniendo una copia casi exacta de la original aunque menos contrastada.

Con el debido respeto jefe, esto es sólo un fondo gris plano, si lo uno con otro igual no obtendré más que gris.

Sólo aparentemente X28, el ojo humano no es suficiente para distinguir matices de gris tan similares. Fíjese en un volcado hexadecimal de los primeros bytes de su imagen:

  00000000 50360a323030203232310a3235350a80 |P6.200 221.255..|
  00000010 80808080807f7f7f8080807f7f7f7f7f |................|
  00000020 7f7f7f7f8080807f7f7f7f7f7f7f7f7f |................|
  00000030 7f7f7f80808080808080808080808080 |................|
  00000040 80808080807f7f7f7f7f7f7f7f7f7f7f |................|
  ...

Vea, después de la cabecera siguen una serie de grupos de bytes (pixels) que son o bien (80, 80, 80) o bien (7f, 7f, 7f) y ya que 80h=128 y 7Fh=127 tenemos dos grises muy similares. Además observe que en binario 80h=10000000b y 7Fh=01111111b luego los bits que están a cero en uno, en el otro están a uno y viceversa.

Sigo sin entender…

Bueno. La imagen original estaba formada sólo por pixels blancos (FF,FF,FF) o negros (00,00,00). Lo que nuestro laboratorio supersecreto hizo fue arrojar una moneda por cada uno de los pixels (tienen mucha paciencia estos chicos) y decidir de acuerdo con la siguiente tabla.

De esta manera si la imagen original era un pixel blanco su sombra podría tener por ejemplo un valor 80h que unido (operación lógica OR) con el 7Fh de su compañero daría lugar a FFh=1111 1111 es decir el blanco original.

Hum. Pero jefe, cuando mi sombra tenga un valor 80h y la de mi compañero también, la unión será de nuevo 80h y no 00h que era el negro original.

Veo que presta atención X28, tanto en este caso como en el otro (7Fh con 7Fh) se obtiene un gris oscuro en lugar del negro original, por eso dije que la imagen saldría menos contrastada. Aun así es perfectamente reconocible.

Pero si una agencia rival obtiene mi imagen o la de mi compañero,¿ no serán capaces de ver la original?

No, fíjese que por depender los resultados del azar, un byte 80h puede con igual probabilidad provenir de un byte negro como de uno blanco, todos los bitmaps en blanco y negro son igualmente posibles y su imagen podría ser perfectamente una foto del acueducto de Segovia.

Bueno jefe, ahora estoy más tranquilo, voy a buscar un mapa y salgo inmediatamente.

Buen viaje X28.

El jefe se reclina en su sillón pensativo. Luego levanta la pantalla de su portátil y mira satisfecho

Aquí termina el copy/paste…

Personalmente me gustó bastante este método, ya que es muy sencillo de implementar, pero lamentablemente es muy básico ya que si tienes las dos imágenes es muy fácil deducir que hay una operación OR, AND o XOR en la criptografía. Propondría una mejora más matemática, quizás aplicar algoritmos de convolución y dar soporte a colores para permitir una mayor complejidad de decriptación, de tal forma que al tener las dos imágenes además sea indispensable el algoritmo para poder descubrir la imagen real, permitiendo una funcionalidad similar a un public-key (criptografía asimétrica). Aún así, aparte de ser entretenido, no le encuentro alguna utilidad jajaja.

Antes habia puesto una imagen de lo que hice un rato de ocio en verano, ahora explicaré un poco mas los pasos que tuve que realizar para un caso de ejemplo en el primer informe para el ramo optimización combinatoria.

• Puntos Característicos: El primer paso es encontrar features similares en ambas imágenes, lo mas sencillo es utilizar un algoritmo que encuentre esquinas como el método de Harris. En las siguientes imágenes restringí la zona a buscar puntos, y el máximo (solo hasta 7 puntos) ya que mi versión de LINGO sólo me permite hasta 50 variables

• Normalized Cross-Correlation: Con los puntos encontrados, obtenemos la correlación con cada punto de la otra imagen en una ventana de píxeles, yo elegí una ventana de 9×9, el resultado de la correlación nos da un valor entre -1 y 1 que nos dice qué tan parecidas son las ventanas (mientras más cercano a 1 es más similar)
• Matching: Aquí va la parte principal de mi proyecto, donde usé la asignación de tipo Stable Marriage Problem para elegir la correspondencia de puntos según los valores de las correlaciones. El resultado fue el siguiente (las lineas verdes muestran el matching correcto, la roja es un matching equivocado y eliminado):

• Transformación Espacial: Con las relaciones encontradas, calculamos la homografía y transformamos una de las dos imágenes, ahora saqué el promedio de los píxeles en las zonas comunes. El resultado final es el siguiente:

Y eso es todo, como ven bastante sencillo porque obviamente el resultado no fue muy profesional, pero hasta aquí lo considero suficiente, no me quiero especializar en registro de imágenes.

Había mencionado anteriormente que agregaría este algoritmo iterativo a uno de los mas importantes del siglo pasado, lamentablemente no se ha usado mucho, pero para mi al menos los resultados han sido sorprendentes.

Básicamente, lo que logra es refinar parámetros usando el hessiano, aproximado por un jacobiano de las variables involucradas. Es una variante de la optimización iterativa Gauss-Newton. No explicaré por ahora como funciona el algoritmo porque no tengo tiempo (tengo clases en unos minutos mas), pero mostraré en qué me ha servido.

Como algunos saben, mi principal trabajo está relacionado con visión computacional y estimación geométrica para aplicaciones con realidad aumentada. El siguiente ejemplo es una estimación directa (usando un truco con la homografía) pero con exceso de ruido y algunos parametros mal estimados a propósito:

Como ven el resultado no es preciso, los cubos deberían posicionarse exactamente sobre los 4 puntos negros (la linea roja indica el lado “base” del cubo, es el lado inferior de la imagen reconocida). Ahora con esa estimación inicial, tratamos de refinar los parámetros de pose (posición y rotación) con Levenberg-Marquardt. Con sólo 2 iteraciones llegamos al siguiente resultado:

La primera vez quedé impresionado, no tiene un costo computacional muy alto, y el resultado fue muy preciso (en todas las pruebas que realicé se llegó a una convergencia). Su dificultad de implementación es lo que probablemente lo hace ser poco usado, pero últimamente he pensado en muchos problemas que se podrían llegar a resolver con un refinamiento de parámetros tan óptimo, quizás intente algo para problemas de clasificación en Support Vector Machines, ya que en mi clase de ayer de Machine Learning vimos un problema que se resuelve con el lagrangiano, y quizás pueda llegar a ser mas útil mi amigo iterativo Levenberg-Marquardt si logro hacer un buen diseño del problema.

En el verano hice esto de puro ocio:

+ =

Debería haber sacado un promedio de los píxeles comunes entre las imágenes para que no se notara la diferencia de luminocidad… pero bueno, era solo para probar. Ese cuadrado blanco fue puesto a propósito para poder estimar con mejor facilidad la correspondencia de puntos entre las imágenes, y su respectiva relación espacial (u homografía como había escrito anteriormente).