Comprobar la aleatoriedad. Test de rachas.

Uno de los problemas de tener un generador de números que parecen aleatorios es estar seguro de si lo son. Hay que tener en cuenta que hablamos de números aleatorios justos, donde todos sean igual de probables, en este caso de números binarios que con un 50% salga 0 o 1 (existen formas de asegurarse de que una fuente aleatoria es justa). Vamos a ver el test de rachas para validar la aleatoriedad.

Test de rachas

En el caso de números binarios este test es muy fácil de entender, contamos el número de rachas que hay en los datos. ¿Qués un racha? Cada vez que un valor es distinto que el valor anterior. Por ejemplo:

00110101100111100

Si lo separamos en rachas:

00 – 11 – 0 – 1 – 0 – 11 – 00 – 1111 – 00

Ahora contamos las rachas, los ceros y los unos. En este caso hay 9 rachas, 8 ceros y 9 unos.

Si el número de rachas es R, el número de ceros es n0, el de uno es n1 y n = n0+n1.

media => u = (2*n0 *n1 / n) + 1

varianza => var = 2*n0*n1*(2*n0*n1-n) / n² * (n-1)

desviación típica => des = sqrt(var)

Z = R + c – u / des

Si R > u → c = -0,5

Si R < u → c = 0,5

El resultado es el Z score. Podemos usar tablas para saber su valor pero si queremos tener una buena aproximación con una seguridad del 95% de que es una distribución aleatoria no puede ser mayor de 1.6 ni menor de -1.6.

R = 9

n0 = 8

n1 = 9

n = 17

u = (298 / 17) +1 = 9,47

var = 298 * (298-17) / 17² * (17-1) = 18,10

des = 4,25

Z = 9 – 0,5 – 9,47 / 4,25 = -0,22

-0,22 esta entre 1.6 y -1.6 con lo cual lo consideraríamos como aleatorio.

Creatividad artificial. CLIP+GA. Pinturas minimalistas y conceptuales con CLIP y algoritmos genéticos

Tras ver lo bien que funcionaba VQGAN+CLIP para generar imágenes yo también quería hacer un programa que creara arte a partir de un texto pasado como referencia. Por supuesto el resultado ha sido un fracaso, sin embargo se puede aprender de los fracasos.

La idea

La idea es usar solo CLIP con algoritmos genéticos. CLIP permite calcular (más o menos) la diferencia entre una imagen y un texto. Si le paso el texto «pato» y una foto me dice como de parecido es el contenido de esa foto al texto, en este caso a un pato. La idea es usar CLIP como función fitness. Para ello calculamos el vector que CLIP asocia a la imagen generada por nuestro algoritmo genético (luego vemos esto) y el vector que asocia a nuestro texto de referencia y calculamos la similitud coseno . La similitud coseno devuelve un valor entre -1 y 1:

  • 1 significa que es idéntico
  • 0 significa que no tiene nada que ver (es ortogonal)
  • -1 que es opuesto

Por lo tanto nuestra función fitness seria:

fitness = 1 - simCos(vectorTexto, vectorImagen)

Vamos a ver un poco de código.

Vector de características de texto:

#vector de carateristicas de texto
text_tokenize = clip.tokenize(TEXT).to(device)
with torch.no_grad():
  text_features = model.encode_text(text_tokenize)
text_features /= text_features.norm(dim=-1, keepdim=True)

Vector de características de la imagen:

#vector de carateristicas de la imagen
image = preprocess(im).unsqueeze(0).to(device)
with torch.no_grad():
  image_features = model.encode_image(image)
image_features /= image_features.norm(dim=-1, keepdim=True)  

Similitud coseno:

#similitud coseno
sim = torch.cosine_similarity(text_features, image_features, dim=1) 

Fitness:

#fitness
return 1 - sim[0].item()

Teniendo una función fitness ya puedo usar cualquier metaheurística. En este caso se trata de optimizar una imagen para que se acerque cada vez más a lo que CLIP considera similar al texto.

Para este caso vamos a usar algoritmos genéticos. Cada individuo es una imagen. Por lo tanto la población es un conjunto de imágenes que irán evolucionando y cruzándose compitiendo por reducir el valor de la función fitness.

Individuos, cruces y mutaciones

En un primer momento intente que el genotipo fueran los pixeles de la imagen y que las mutaciones y cruces fueran cambios aleatorios en los mismos. Manejar 16 millones de colores por cada pixel me parecían un espacio de soluciones muy amplio y decidí hacerlo en escala de grises por lo que solo tendría 256 posibilidades por pixel. Sin embargo el resultado fue un desastre los pixeles sueltos eran tan «pequeños» que creaba un «ruido» que no era capaz de evolucionar. Como solución intenté crear «píxels» más gordos. Para ello use cuadrados. Tampoco funcionó. Añadir colores dio como resultado cosas que podían tener sentido pro dentro de un ruido de colorines.

Siguiente plan, separar el genotipo y el fenotipo. El genotipo serían las instrucciones para construir la imagen mientras que el fenotipo sería la propia imagen. Como pasos para construir la imagen decidí usar pinceladas. En este caso para simularlas use líneas rectas que van de un punto aleatorio a otro, con color y anchura también aleatorios.

Una vez tenemos definidos los individuos hay que definir sus operaciones de cruce, de mutación y de reemplazo.

Operadores de cruce:

  • Intercambiar un bloque de trazos
  • Mezclar todos los trazos
  • No cruzar

Operadores de mutación:

  • Mover un trazo
  • Cambiar de color un trazo
  • Cambiar de orden un trazo por otro
  • Añadir un trazo

Como operador de reemplazo se reemplaza al peor individuo de la población (fitness más alto) por aquel hijo que tenga menos fitness que él.

Como el resultado era caótico, lleno de lineas de colores que no aportaban nada a CLIP pero dificultaba que un humano reconociera el dibujo decidí minimizar el número de trazos, para ello cada cierto tiempo se ejecuta una función de optimización local que prueba a eliminar cada uno de los trazos y si no altera o reduce la función fitness lo descarta. 

Como último añadido y para dar más variedad a los trazos incluí que un trazo pueda ser una linea, un rectángulo o una elipse. Y una función mutación que cambia el tipo de trazo.

El resultado es un artista minimista que trata de trazar el menor número de líneas para dibujar un concepto.

Una Inteligencia artificial conceptual y minimalista

Hemos logrado un artista que crea con el menor número de trazos posible. Conceptual y minimalista…solo hay un problema que es un autor conceptual y minimalista desde el punto de vista de una IA. Hay imágenes en la que coincidimos, por ejemplo con las rosas:

Rosa

Otras imágenes sin embargo son incomprensibles, por ejemplo cuando le pido que me dibuje un pato le basta con dibujar una linea naranja rodeada de lineas verdosas, me lo hizo varias veces.

Pato ¿?

¿Por qué esa linea es un pato? Seguramente porque lo identifica con el pico y no necesita más para identificar un pato. Así que como nuestro autor minimalista reconoce patos por el pico (su rasgo más distintivo) es difícil que surja una mutación que mejore ese resultado.

Algo parecido me pasa con los dragones que no me pinta el cuerpo solo la cabeza, generalmente con algún tipo de «cresta» y a veces las patas, pero nada de cuerpo. Lo cual tiene sentido ya que su cuerpo se parece al de otros reptiles.

¿El dragón sin cuerpo?

Como herramienta puede ayudarnos a entender que «ve» una IA en una imagen.

Para probarlo dejo este enlace al codebook de Google donde probarlo

Creatividad artificial. Generar imágenes para microcuentos con VQGAN+CLIP

Llevo un tiempo probando VQGAN+CLIP para generar imágenes a partir de texto y quería hacer algo con él, pero no sabia el que. Hasta que recordé que hace años tenia un twitter llamado tweetcuento donde publicaba unos microcuentos que escribía. Sin entrar en detalles sobre mi calidad como cuentista me pareció que podría ser una buena idea usarlo de base para un experimento de creación de imágenes

VQGAN+CLIP es la unión de dos sistemas. VQGAN y CLIP . CLIP funciona como un puente entre las imágenes y el texto. Explicado pronto y mal, CLIP generaría el mismo valor (o al menos uno muy cercano) para una foto de una gafas que para la palabra «gafas». Ahí radica la clave de este sistema de generación de imágenes, se le pasa un texto a CLIP y luego una imagen generada por VQGAN. Y trata de que el valor del texto y la imagen se aproximen. VQGAN usa este valor para mejorar su resultado. Si queréis una explicación más exhaustiva DotCSV tiene un video estupendo sobre el tema.

Todo este proceso lo he realizado a partir de un notebook de google colab creado por Katherine Crowson . Sin embargo para usarlo con mis cuentos tenia que realizar varios pasos.

CLIP solo funciona en inglés así que toca traducir los microcuentos. Podría hacerlo yo pero me parece más interesante que lo haga un traductor automático (y es posible que lo haga mejor que yo). He recurrido al traductor de Google, pero no uso directamente sus resultados. Antes los reviso y solo los modifico si hay alguna palabra cuya traducción es errónea ya que podría influir en el resultado. En el resto delos casos dejo la traducción como esta. En las pruebas realizadas hasta ahora no he necesitado modificar la mayoría de los resultados.

Luego adapto el texto para pasarlo a CLIP. Elimino los símbolos que no sean letras o números. Cada frase separada por un punto la separo, los mismo hago con las conversaciones.

- Quiero ese globo - la niña señaló un pobre globo que apenas se elevaba del suelo
- Los hay más bonitos
- Si, pero este sé que no me dejará

Se convierte en

["Quiero ese globo", "la niña señaló un pobre globo que apenas se elevaba del suelo", "Los hay más bonitos", "Si pero este sé que no me dejará"]

En realidad el texto estaría en inglés pero el ejemplo se entiende mejor así.

Otra condición que me he autoimpuesto es que se generan solo 3 imágenes por cada cuento. Elegiré la que me parezca más adecuada, si dudo entre varias imágenes publicaré todas entre las que esté dudando.

Además esperare un par de días para evitar sesgos. He notado que cuando estas mirando como el sistema produce sus imágenes te parecen mucho mas sorprendentes unos que días después.

Las imágenes obtenidas son tal y como las genera VQGAN+CLIP . Muchas de ellas serian fácilmente mejorables con algún pequeño retoque.

Por último y puesto que no podían faltar los NFTs cada imagen es convertida en un NFT y ofrecida en una galería en Opensea. No creo que nadie vaya a comprarlas pero quería aprender el proceso.

Veamos un ejemplo de todo este proceso, partiendo del cuento:

"Las máquinas se rebelaron, ganaron la guerra y esclavizaron a la humanidad. Se convirtieron en los amos del mundo. Esta situación se prolongó durante tres años hasta que las máquinas perdieron ante su mayor enemigo, la obsolescencia programada."

La imagen obtenido ha sido:

Para ver mas ejemplos los iré publicando poco a poco en tweetcuento

Como evitar ataques de repetición en tus proyectos de IoT con OTP (Arduino)

Los ataques de repetición son un habitual en los dispositivos de IoT y muchas grandes empresas los han sufrido. Se producen cuando alguien intenta securizar las comunicaciones entre dispositivos pero no tiene muy claro como se hace.

Realmente un ataque de repetición es un ataque de inyección de comandos pero con algunas limitaciones. Vamos a plantear un escenario muy sencillo. Una casa con una bombilla inteligente conectada por WiFi (o de cualquier otra manera la capa física de la conexión da igual). Esta bombilla recibe comandos para encenderse y apagarse. Ahora conectamos un dispositivo «malvado» a esta red (o no lo era cuando lo conectamos pero un atacante se hace con el control). Este dispositivo podría enviar comandos de encendido y apagado a la bombilla. Lo que sería el equivalente a un niño jugando con el interruptor. Esto sería un ataque de inyección de comandos.

Para solucionarlo el fabricante piensa que puede cifrar los comandos con un cifrado superseguro e irrompible, cada bombilla tendrá una clave única así que aunque el atacante haga ingeniería inversa no le va servir de nada. Ahora el fabricante anuncia que su dispositivo es seguro y comprador se siente protegido.

Pero la realidad es que no basta con cifrar la comunicación. La lámpara recibe comandos de encendido y apagado cifrados. Podríamos decir que es lo mismo, un conjunto de bytes enciende la lámpara y otro la apaga, solo que esta vez ese conjunto es diferente para cada lámpara del mundo. La clave de este ataque es que si siempre se cifra el mismo comando con la misma clave el conjunto de bytes siempre es el mismo por lo que al atacante le basta con capturarlo para poder reenviarlo tantas veces como quiera.

¿Y si añade una parte del mensaje que sea aleatoria? Tampoco sirve, aunque ahora cada mensaje sea un grupo de bytes diferente, se puede reutilizar el mismo mensaje varias veces ya que el dispositivo no puede verificar su validez.

Lo mismo ocurre si el mensaje va firmado digitalmente. Nada impide al atacante copiar ese mensaje y reenviarlo.

El truco esta en usar una parte del mensaje que sea predecible y no repetible. Predecible para que el receptor del mensaje pueda saber que es correcto y no repetible para descartar los ya utilizados.

Para ello vamos a usar passwords de un solo uso (OTP) para saber más sobre el tema se puede ver en este articulo. En el articulo se emplea un contador o un timestamp dependiendo de que tipo de OTP se use, lo ideal seria usar TOTP. En nuestro caso eso da igual. No hay que olvidar que aquí estamos hablando de proyectos IoT lo cual limita técnicamente las soluciones que podemos adoptar.

Antes de ver posibles soluciones vamos a empezar explicando el concepto de «ventana de tiempo del ataque», se podría definir como «tiempo durante el cual somos vulnerables al ataque». En nuestro caso es el tiempo durante el que un mensaje capturado y reenviado por un atacante es considerado válido por nuestro dispositivo. Cuanto más pequeña sea esta ventana más seguros estaremos.

Volviendo a nuestro OTP tenemos: una función que lo calcula (OTP), un contador o timestamp (c) y un secreto compartido entre ambos dispositivos (k) y un comando o mensaje a enviar (msg). En lugar de calcular un token OTP con el contador uniremos el mensaje y el contador y calcularemos un OTP de ambos.

Token = OTP(msg+c, k)

Truco, si el mensaje es demasiado grande para procesarlo ya sea por memoria o por tiempo se puede usar cualquier función que lo resuma (una función hash o algo menos costoso), aunque hay que tener cuidado de que dos comandos distintos generen dos resúmenes diferentes.

Ahora enviamos el mensaje y el token para que el cliente pueda validarlo.

Si un tercero interceptara nuestro comando este solo le seria valido durante un breve periodo de tiempo.

Si queremos añadir un extra de seguridad podemos hacer que nuestro sistema no acepte dos veces el mismo comando durante un periodo de tiempo igualo mayor a la ventana de ataque.

En el esquema de debajo se puede ver como es el proceso, para calcular c se usa el timestamp (t) actual dividido por la ventana de tiempo (vt).

Un detalle a tener en cuanta es que nunca se ha hablado de cifrar la comunicación, este sistema es seguro aunque los mensajes se distribuyan de forma abierta.

Password de un solo uso (OTP) en Arduino (HMAC, HTOP, TOTP)

Los password de un solo uso también llamados OTP (One Time Password) son passwords que solo se pueden usar una vez o durante un periodo de tiempo breve. Es una buena medida de seguridad, aunque estas contraseñas sean robadas o interceptadas se reduce el tiempo que el atacante puede acceder al sistema. Uno de sus usos es como segundo factor de autenticación. Casi todos habremos tenido que usar alguna vez códigos que nos envían al móvil o que genera algún aplicación y cuyo tiempo de vida es breve. Eso es un OTP.

Cuando hay un canal seguro para notificar el OTP, por ejemplo un mensaje por SMS. Es sencillo crear un OTP, se genera un código aleatorio asociado a ese usuario y listo.

Pero no siempre hay un canal seguro. En ese caso la solución es algo más complicada. Necesitamos tener dos programas que generen exactamente la misma contraseña en el mismo momento. Para estos sistemas necesitaremos dos cosas.

  • Un secreto o clave, que es compartido por ambos sistemas y debe de permanecer en secreto para que sea seguro. La llamaremos k
  • Una secuencia o contador, este dato puede ser publico sin ningún problema (en teoría) sirve para que ambos programas generadores creen la misma contraseña. Lo llamaremos c

Con random

Una implementación muy sencilla y de muy baja seguridad (suficiente para proyectos caseros) es usar el generado de números pseudoaleatorios de Arduino. En este caso el secreto es la semilla con la que se inicializa el generador. En este caso la secuencia o contador no es explicito, no se le pasa es implícito al numero de veces que se ha llamado a la función random. Lo que añade la dificultad añadida de tener ambas secuencias sincronizadas.

long randNumber;
void setup() {
  randomSeed(k);
}
void calculateOTP() {
  return random(10000, 99999);//contraseña de 5 digitos
}

Otro problema es que cada vez que se reinicia perdemos el punto donde estábamos de la secuencia y esta vuelve a empezar. Seria necesario guardar en la EEPROM el número de veces que hemos generado un OTP y luego llamar a la función ese numero de veces para resincronizar el estado del generador de números pseudoaletaorios.

Con una función hash

Otra táctica parecida es usar una función de hash. Para calcular la primera contraseña se llama a la función de hash con el secreto k, luego se usa el password anteriror, añadiendole el secreto k para calcular el siguiente:

k0 = H(k)

k1 = H(k0+k)

k2 = H(k1+k)

k3 = H(k2+k)

….

kn = H(kn-1+k)

La ventaja de este sistema es que basta con guardar en la EEPROM el último password generado para mantener la sincronización.

HTOP

Estos dos sistemas nos sirven para desarrollos caseros que no requieren demasiada seguridad para hacer una implementación segura podemos usar HMAC (hash-based message authentication code). HMAC usa una función de hash, un secreto o clave y un mensaje, en este caso el mensaje será el contador. A esta implementación se le conoce como HTOP (HMAC-based one-time password).

Empecemos viendo como funciona HMAC

HTOP(k, c) = HMAC(k, c) = H( (k ^ opad) || H(k ^ ipad) || c )

  • H es la función e hash
  • k es la clave secreta
  • c es el contador
  • opad es un bloque formado por el valor 0x5c repetido
  • opad es un bloque formado por el valor 0x36 repetido
  • || es la operación OR
  • ^ es la operación XOR

En este caso no necesitamos tener el contador sincronizado. El contador se puede pasar en la petición. Supongamos que el dispositivo B intenta contactar con el dispositivo A, el proceso puede ocurrir de dos maneras:

  • B usa su contador interno y la pasa el password (TokenB ) con el contador usado para calcularlo. A calcula el password con el contador que le pasa B y verifica si coinciden
  • B le pide a A un contador y A le pasa el contador con el que B tiene que generar el password (tokenB) y se lo devuelve a A que verifica si coinciden

El segundo caso es más seguro ya que evitamos que un atacante

TOTP

Lo ideal seria que ninguno tuviera que intercambiar el contador, que ambos tuvieran un contador sincronizado. Una opción seria usar la hora actual. O un timestamp que exprese la hora actual como milisegundos transcurridos desde el 1 de enero de 1970 a las 00:00:000. Es decir que TOTP (Time-based One-time Password) es HMAC usando como mensaje el tiempo o lo que es lo mismo usar HTOP usando como contador el tiempo.

El único problema aquí es que cada milisegundo la contraseña cambia y puede ser muy poco tiempo para realizar el intercambio de password. La solución es dejar una ventana de tiempo durante la cual el password es válido. Si usamos t para indicar el tiempo en milisegundo y vt el tiempo (en milisegundos) durante el cual el password es válido.

c = Trunc(t/vt)

TOTP(k, c) = HMAC(k, c)

Así nos ahorramos la parte de tener que intercambiar el contador entre dispositivos. Ambos usan la hora actual con una ventana de tiempo vt.

El problema es que Arduino no tiene un RTC (real time clock) por lo que no tiene forma de saber directamente qué hora es, necesita un elemento externo que le informe de ello.

«TOTP» sin RTC

Hay una forma un poco tramposa de implementar TOTP sin usar un RTC. En este caso partimos de HTOP, usaremos la segunda forma de HTOP en la que A le pasa el contador a B. El funcionamiento es exactamente igual que antes solo que tras un periodo de tiempo t la variable contadorA se incrementa automáticamente dejando a B con un OTP que ya no es valido.

No es un sistema tan cómodo como tener ambos sistemas sincronizados por su reloj. Ademas de que si varios dispositivos quieren conectarse al dispositivo A puede ser complicado de gestionar y necesitarías un contador y un secreto para cada uno.

¿Cual elegir?

Las soluciones basadas en HMAC son las más seguras pero también las más exigentes en tiempo y memoria. Y aunque TOTP es la segura y cómoda implica tener un RTC y que todos los dispositivos lo tengan sincronizados. Cada uno tiene que elegir el método según el balance de seguridad y coste.

Código

Para implementar todo esto podemos usar la librería Cryptosuite para Arduino. Permite usar la funciones hash SHA-1 y SHA-256.

Una vez copiada a nuestro directorio de librerías de Arduino puede usarse añadiendo el include correspondiente

#include "sha1.h"
#include "sha256.h"

Un ejemplo de uso de HMAC es:

 uint8_t *hash;
 Sha256.initHmac(key,keyLength); //secreto y su longitud
 Sha256.print(counter); //contador
 hash = Sha256.resultHmac();

Crear un agente con creatividad artificial

La creatividad artística es una de las capacidades humanas que más nos distinguen de los demás seres vivos. Es una de nuestras capacidades mas difíciles de imitar por las inteligencias artificiales. Tanto es así que hasta los más pesimistas pronósticos sobre la destrucción del empleo por parte de las máquinas salvan los empleos creativos. Pero la inteligencias artificiales poco a poco se adentran el el campo de la creatividad construyendo lo que se conoce, con el poco creativo nombre de creatividad artificial.

Es importante señalar que la creatividad artificial se centra en el proceso creativo no en el impulso creativo. Podemos imitar los resultados del proceso creativo humano pero no la necesidad, el contexto o el mensaje de la obra. Los resultados a veces son tan sorprendentes que parecen contener un mensaje o significado mas allá de la propia obra, pero es algo accidental, codificado en los datos con los que se alimentó la obra. Realmente se busca la imitación del arte humano, no la expresión de la máquina.

Elegir el dominio artístico

No es lo mismo crear un libro, que una pintura, una escultura o un vestido. Incluso dentro de cada dominio hay casos diferentes, no es lo mismo escribir una novela que un poema. Ni sigue las mismas reglas una novela romántica que una de misterio e incluso dentro del mismo género hay estilos.

Reunir ejemplos

Necesitamos recopilar obras de arte del dominio. Las necesitamos para alimentar nuestro sistema y extraer sus características y reglas. Hay que tener en cuenta que estas obras son las que definirán las creaciones de nuestro agente hay que reunir obras como las que queremos que produzca

Convertir las obras a un modelo

El modelo es una forma de representar la obra de forma «entendible y manipulable» por nuestro software.

Reglas y algoritmo generador

La creatividad necesita seguir una reglas. Si tiramos letras al azar sobre una página el resultado será muy innovador y único pero su valor como novela es muy pobre. Las reglas nos dicen como generar una obra a partir de una entrada. Pueden estar definidas a mano, aprendidas automáticamente de nuestros ejemplos o una mezcla de ambas. Podemos darnos el lujo de romper alguna regla durante el proceso creativo pero si rompemos todas obtendremos un sin sentido.

siguiente estas reglas el algoritmo puede crear una obra a partir de los datos proporcionados como entrada.

Datos de entrada o semilla

Hace falta definir una «semilla», una entrada al modelo con la que este pueda «tirar del hilo» para generar la obra de arte. La semilla puede ser elegida por un humano, generada al azar o tomar algún valor de algún sitio. En los modelos iterativos (más adelante los vemos) la semilla incluye una obra que es la que vamos a transformar. En la primera iteración se pueden usar datos generados al azar.

Representar el modelo

La representación es la traducción de ese modelo a la obra que nosotros los humanos apreciamos. Es el paso contrario a convertir la obra en modelo

Modelos iterativos

Lo ideal seria que a la primera la obra resultante fuera valida. Pero Actualmente se aprovecha que tenemos un «juez» para convertir el proceso de creación de la obra en uno iterativo. En este proceso se toma la obra generada o mejor dicho su modelo y se usa para realimentar el algoritmo generador de forma iterativa transformando la obra intentando mejorar la puntuación del juez en cada iteración. Este proceso recuerda al de las metaheurísticas.

Juez

El juez actúa valorando la obra creada según las características deseadas. Estas características pueden ser aprendidas o definidas por nosotros. Esta parte del algoritmo se comporta como la función fitness.

Hay algoritmos generadores que en lugar de generar una obra generan varias obras que son pequeñas variaciones de la mima. El juez actúa eligiendo con cual se realimenta el proceso. Que por lo general suele ser la que mejor puntuación obtiene.

En este punto se puede introducir «ayuda» humana que actué como juez, si no en todas las iteraciones cada cierto número de ellas.

Ejemplo

En el caso del generador de textos basado cadena de Markov que vimos en esta entrada del blog tendríamos los siguientes elementos:

  • Los textos que se usan para entrenarla son los ejemplos.
  • El modelo son los tokens que se extraen del texto para entrenar a la red.
  • Los n-gramas que se aprenden son la reglas generadoras.
  • El algoritmo generador es tan sencillo como elegir al azar la palabra siguiente ponderando este azar según las probabilidades indicadas por las reglas (n-gramas)
  • En este caso no hay juez a que es un algoritmo de una única pasada

Vamos a convertir este sistema en iterativo. En lugar de una frase se generaran varias. Un humano indicará cual es la que más le gusta y a partir de esa frase se generaran nuevas frases. Para ello el algoritmo tomará un punto aleatorio de la frase, eliminará todas las palabras a partir de ese punto y continuará creando la el texto usando los n-gramas aprendidos para elegir la siguientes palabras.

Brillo y contraste. Ajuste automático.

El ajuste del brillo y del contraste se usa para mejorar la visibilidad de la imagen. El brillo añade o reduce luminosidad a la imagen y el contraste aumenta o disminuye la distancia entre los valores. No vamos a complicarnos la vida. La fórmula para ajustar el brillo y el contraste de una imagen es muy sencilla, es la unión de dos formulas. Como ya os imaginareis, la de ajuste del brillo y la de ajuste del contraste

Formula para ajustar el brillo de la imagen:

newPixelValue = pixelValue+b;

Sumando a cada pixel un valor lo hacemos más brillante, si el valor es positivo, o más oscuro, si es negativo.

Formula para ajuste del contraste:

newPixelValue = c * (pixelValue-128) + 128

Combinando ambas tenemos una formaula que nos permite ajusta ambos valores:

newPixelValue = c * (pixelValue-128) + 128 + b

Siendo el parámetro c el contraste y b el brillo. Sólo hay que tener en cuenta las diferencias entre la estructura de datos de color y de escala de grises y tenemos el código listo.

Pero como nos encanta complicarnos la vida vamos a intentar que el ajuste del brillo y el contraste sea automático. ¿Como?. Supongamos que una imagen correctamente balanceada «ocupa» todo el rango de valores de 0 a 255. Vamos a «estirar» los valores de la imagen para que el mínimo sea el 0 y el máximo el 255. Es tan «sencillo» como buscar el valor más bajo y más alto que hay en la imagen. Ahora seleccionamos los valores contraste y brillo que hacen que el mínimo valor sea 0 y el máximo 255. Suena lógico, ¿cómo lo hacemos?. ¡Resolviendo ecuaciones!. Contened vuestra emoción.

Vamos a hacer que el mínimo sea la variable low y el máximo high. Tenemos estas dos ecuaciones:

(c*(high-128))+128+b = 255

(c*(low-128))+128+b = 0

Resolvemos el valor de b en la que es igual a 0. Podríamos despejarlo de cualquier otra forma pero esta me ha parecido la más fácil.

b = 128*c - low*c - 128

Sustituimos la b en la segunda ecuación:

c = 255/(high-low)

Bueno, ¿de donde sacamos estos valores low y high? Es tan sencillo como recorrer la imagen comparando los valores de sus pixels para  encontrar el mínimo y el máximo.

Con las imágenes en escala de grises es sencillo pues solo hay un valor maximo y uno minimo. Pero con las de color hay que tomar una decisión. ¿Ajustamos los tres canales de color de forma independiente calculando los valores b y c para cada uno o usamos los mismos para todos los canales?.

Si ajustamos todos los canales con los mismos valores de b y c hay dos opciones:

  • Convertir cada pixel a escala de grises, calcular el mínimo y el máximo y luego los correspondientes b y c
  • Calcular el máximo y mínimo de cada canal y calcular el b y c de aquel que tenga mayor distancia entre el valor máximo y mínimo (high -low). Asi nos aseguramos que coger el canal que «menos hay que estirar».

¿Cual es el problema ajustar cada color por separado? Que al estirar cada canal por separado la relación entre los colores cambia cambiando el color y no sólo el contraste y la intensidad. Por ejemplo si el rango de cada canal es:

Rojo: 0-255

Verde: 10-230

Azul: 100-150

Tras aplicar nuestro ajuste todos los canales tendrán un rango de 0-255. Así que mientras que el canal rojo no ha cambiado el azul ha variado de forma desproporcionada de tal forma que un píxel RGB con valores (230, 230, 100) pasa a ser tras el ajuste (230, 255, 0). Mientras el canal R y G casi no varía el B pasa de 100 a 0. Estos cambios alteran el color. Puede dar resultados muy artísticos pero poco naturales.

Todos estos cálculos se pueden realizar usando tablas de consulta calculando el valor para cada uno de los posibles valores de cada pixel (0…255)

Evitar el ruido

Vamos a la siguiente vuelta de tuerca. ¿Qué pasa si el valor mínimo y el máximo sólo corresponden a unos pocos píxeles no representativos de la imagen? Al aplicar el ajuste de brillo y contraste podríamos hacer más mal que bien y dejar la imagen peor. ¿Pero ese caso se puede dar? Resulta que «píxeles con valores extremos no representativos de la imagen» describe muy bien cierto tipo de ruidos como el ruido de sal y pimienta. Como siempre la realidad resulta ser menos bonita que la bella teoría. Por suerte hay solución. En lugar de coger los valores mínimos y máximos vamos a descartar una porcentaje pequeño de los valores más altos y más bajos. Por ejemplos vamos a descartar el 5% de los pixeles con los valores más bajos y el 5% con los valores más altos. En caso de que la iamgen esté muy deteriorada por el ruido estos valores pueden ser mayores

Así que hemos de sumar cuantos pixeles de cada valor hay en la imagen. Un momento, eso me suena, huy si, es el histograma y ya lo tenemos hecho. Sólo hemos de ir sumando el número de píxeles de cada entrada del array del histograma hasta que el acumulado supere los valores deseados y usar esos valores como mínimo y máximo. Parece facil y lo es hasta que vemos el histograma a color, tenemos tres canales de color ¿Como elegimos los valores high y low para calcular los ajustes de brillo y contraste?. En el caso anterior hemos ignorado de forma poco elegante este punto y el resultado a veces se resiente. La solución más simple es modificar la función de ajuste de brillo y contraste para que permita modificar cada canal por separado.

Combinar cálculos de tablas de consulta e histogramas.

Ya hemos visto lo útiles que resultan las tablas de consulta para agilizar cálculos y también la utilidad del histograma que al ser una representación estadística de la imagen nos permite calcular ajustes globales de la imagen con solo 256 valores. ¿A que seria genial que ambos métodos se pudieran usar conjuntamente? La vida es bella, ya que no solo es posible sino que es realmente sencillo.

En los distintos métodos que usan el histograma (ajuste del brillo y contraste, ecualización del histograma, …) sencillo que calcular la tabla de consulta correspondiente. Pero al aplicar estas tablas la imagen cambia y por tanto el histograma también. ¿Podemos calcular el nuevo histograma sin tener que volver a recorrer toda la imagen contando pixels? Por fortuna para el interés de esta entrada la respuesta es sí. Además de una forma realmente sencilla.

  1. Creamos un nuevo histograma (newHistogram en el ejemplo) con todos sus valores a 0.
  2. Recorremos todos los posibles valores i del histograma original (por ejemplo de 0 a 255).
  3. Para cada valor i del histograma original consultamos su valor (lut[i]) en la tabla de consulta lut
  4. Se suma el valor del histogram[i] a newHistogram[lut[i]]

for(var i = 0; i < 256; ++i){
  newHistogram[lut[i]] += histogram[i];
}

Con solo recorrer 256 elementos tenemos el histograma actualizado y nos hemos ahorrado volver a recorrer la imagen.

Fenómeno de sincronización con autómatas celulares

En la naturaleza se dan lo que se conoce como fenómenos de sincronización, elementos que se sincronizan solos a partir de un pequeño intercambio de información local.

Si colocas varios metrónomos, cada uno marcando un tiempo, en una superficie que permita la transferencia de movimiento entre ellos acaban sincronizándose.

Las luciérnagas también sincronizan sus destellos hasta terminar destellando al unisono, este proceso tiene una complicación más ya que cada luciérnaga solo percibe a sus vecinas más cercanas por lo que el procesos de intercambio de información ocurre a escala local, pero acaba afectando de forma global.

Como vemos lo que tiene en común es el intercambio de información.

Vamos a simular esto mismo de una forma simple. Para ellos tendremos un autómata celular donde cada celda empieza en un estado de N posibles (4 en nuestro caso: rojo, azul, lima y amarillo) elegido al azar, cada uno de ellos con igual probabilidad. No cuesta mucho imaginar que en un autómata celular con C celdas habrá aproximadamente C/N celdas en cada estado distribuidas uniformemente.

En cada iteración cada celda mirará a sus 8 vecinos, elegirá uno al azar y copiará su estado.

El ejemplo está aquí y el código aquí.

El autómata durante su ejecución

En podríamos pensar que si dejamos funcionar este sistema durante mucho tiempo lo único que ocurrirá es que los individuos irán intercambiando sus estados en un confuso baile de colores. Sin embargo si se deja el tiempo suficiente los estados empiezan a agruparse y a crecer como si compitieran entre ellos hasta que uno a uno comienzan a desaparecer hasta que al final solo queda uno. Todas la celdas han sincronizado su color.

Resultado final con todas las celdas sincronizadas

Si el autómata es pequeño el resultado se alcanza antes, cuando es muy grande tarda mas tiempo en llegar a el, pero al final el resultado es el mismo todas se sincronizan (aunque el color final sea diferente cada vez)

¿Como es esto posible? En teoría no debería cambiar demasiado el estado global, cambiamos aleatoriamente el valor de cada celda copiando el de un vecino que a su vez es aleatorio. Fijaos que ni siquiera es un intercambio inteligente ni muy organizado. Lo que ocurre es que en el azar hay pequeñas desviaciones, pequeñas zonas locales donde un color se vuelve mayoritario esto es posible por el intercambio de información entre vecinos. Cuantos más individuos de ese color existan más probable es que ese estado sea copiado por otros. Cuando un individuo queda rodeado de vecinos en su mismo estado se ha creado un núcleo estable que será difícil de cambiar y que ira creciendo. Solo en la frontera de ese núcleo puede darse el cambio. Basta un pequeño desequilibrio para que el intercambio de información entre vecinos lo realimente y crezca. Al ser un proceso aleatorio hay vaivenes, un color que es mayoritario puede descender bruscamente y otro ocupa su lugar hasta llegado a un punto en que un color es tan mayoritario que acaba imponiéndose.

Debajo puede verse una gráfica con lo % de cada color en la ejecución del autómata.

La evolución en % de los cuatro colores hasta que uno se impone (el 2º)

Caminata aleatoria (random walk) en un autómata celular

Una caminata aleatoria, random walk en inglés, es un proceso aleatorio donde una partícula (aquí partícula es una forma elegante de decir «cosa») se mueve avanzando en direcciones aleatorias donde la elección en cada momento no está condicionada por ninguna elección anterior. Se suele ilustrar con el paseo realizado por un caminante borracho que elige aleatoriamente entre alguna de las posibles direcciones que tiene alrededor y da un paso en esa dirección. Tras ese paso repite el proceso. En nuestra simulación los pasos van a tener todos el mismo tamaño, una celda. Para evitar las diagonales (que seria avanzar 1,41 veces mas que por lo lados) se va a usar una vecindad de tipo von Neumann lo que deja solo cuatro vecinos por celda y solo cuatro direcciones en las que el caminante se puede mover (arriba, abajo, izquierda, derecha)

Los estados de las celdas son solo dos, si contiene al caminante o no. Para mejorar la visualización se suele definir un tercer estado que indica si la celda ha sido visitada alguna vez o no por el caminante. Este tercer estado es algo simplemente visual y no afecta en nada a los movimientos del caminante.

  • Negra, celda sin visitas
  • Blanca, celda visitada
  • Azul, indica la celda donde esta el caminante

Las reglas son muy simple, la celda donde este el caminante elige una de sus cuatro vecinas y se mueve ahí.

El simulador se puede ver aquí y el código aquí.