ASCII by Biased Potts Markov field

  • interactive
  • ascii
  • docs
  • markov

Abstract

Cómo hacer emerger una imagen desde el ruido: Potts-Markov en tiempo real mediante un muestreo de Gibbs en local.

Laboratorio

1.60
2.80
0.60
0.020
0.35
0.025

Ajusta los parámetros en tiempo real para ver cómo emerge la figura.

La animación de este ASCII de Hypnos está calculada en tiempo real con JS, aplicando la propiedad de Markov local sesgada sobre ruido totalmente aleatorio.

Modificando algunos parámetros ponderantes podemos alterar y moldear el comportamiento del ruido, alterando la velocidad y la forma del mismo.

Planteamiento del espacio ASCII

Para operar en un espacio ruidoso, podemos entender una imagen ASCII como una matriz bidimensional discreta:

Ω={1,…,W}×{1,…,H}\Omega = \{1,\dots,W\} \times \{1,\dots,H\}

Donde celda i∈Ω i \in \Omega representa una posición de carácter y puede tomar un valor de un alfabeto finito ordenado de menor a mayor densidad:

A={a0,a1,…,aK−1}A = \{a_0, a_1, \dots, a_{K-1}\}

Por ejemplo:

A = [" ", ".", ":", "-", "=", "+", "*", "#", …]

En base a esta densidad, podemos transformar la imagen en un espacio escalar continuo:

T:Ω→[0,1]T : \Omega \rightarrow [0,1]

donde 0 correspondería a la ausencia de caracteres " " y 1 sería lo más cercano a una celda en negro “@”.

Campos aleatorios de Markov (MRF)

Teniendo un conjunto de variables aleatorias

X={Xi}i∈Ω,X = \{X_i\}_{i \in \Omega},

asociadas a la matriz bidimensional, donde cada XiX_i toma valores en el alfabeto AA, una imagen ASCII completa no es más que una asignación:

x:Ω→A,xi∈A.x : \Omega \rightarrow A, \qquad x_i \in A.

Para formalizar esto junto las dependencias espaciales (vecinos de las celdas), definimos un grafo no dirigido:

G=(Ω,E),G = (\Omega, \mathcal{E}),

donde:

  • Ω\Omega son los nodos (las celdas),
  • E\mathcal{E} conecta celdas vecinas en la rejilla.

Asumimos vecindad de 4, por lo que el vecindario de una celda ii es:

N(i)={ j∈Ω:(i,j)∈E }.\mathcal{N}(i) = \{\, j \in \Omega : (i,j) \in \mathcal{E} \,\}.

Es decir, el conjunto de todas las celdas directamente adyacentes a la celda ii (arriba, abajo, izquierda y derecha).

Ejemplos de vecindad en una matriz 3×33\times3:

[i] x  o                       o  x  o
 x  o  o                       x [i] x
 o  o  o                       o  x  o

Propiedad de Markov local

Habiendo ya definido el espacio donde estas variables aleatorias, este ruido, operará y se transformará en una imagen, debemos definir cómo se comportará cada celda con sus vecinos

La hipótesis fundamental del MRF antes descrito es la propiedad de Markov local, que exige:

P(Xi=a∣XΩ∖{i})=P(Xi=a∣XN(i)),∀i∈Ω, ∀a∈A.P(X_i = a \mid X_{\Omega \setminus \{i\}}) = P(X_i = a \mid X_{\mathcal{N}(i)}), \quad \forall i \in \Omega,\ \forall a \in A.

Esto significa que la probabilidad de que la celda ii tome el carácter de densidad aa, es idéntica a su probabilidad condicionada al estado de sus vecindario inmediato. Es decir, el valor final de una celda solo dependerá de sus vecinos (por ahora).

Para el modelo, nos basamos meramente en interacciones locales.

Distribución de Gibbs

Para que el MRF sea totalmente usable recurrimos a la distribución de Gibbs, que asigna una probabilidad a cada configuración global (a nivel imagen completa) xx:

P(X=x)=1Z exp⁡(−E(x)).P(X = x) = \frac{1}{Z}\,\exp\big(-E(x)\big).

Donde:

  • E(x)E(x) [Energía] es una función que asigna un “coste” a una configuración completa,
  • ZZ es la constante de normalización o constante de partición:
Z=∑x∈A∣Ω∣exp⁡(−E(x)).Z = \sum_{x \in A^{|\Omega|}} \exp\big(-E(x)\big).

El número total de configuraciones posibles es ∣A∣∣Ω∣|A|^{|\Omega|}, por lo que ZZ es intratable para matrices donde la imagen sea mínimamente distinguible.

Para comprobarlo, solo tenemos que calcular el número total de configuraciones a evaluar por ZZ:

∣A∣∣Ω∣=KW⋅H.|A|^{|\Omega|} = K^{W \cdot H}.

Partiendo de que podemos evaluar RR configuraciones por segundo, pongamos de forma muy optimista R=108R = 10^8 y con un alfabeto de solo 10 caracteres, en una celda 4×44 \times 4 tenemos 101610^{16} configuraciones; lo que nos llevaría aproximadamente unos 3.17 años.

Puesto que al final solo tratamos probabilidades condicionales locales, ZZ se cancela fácilmente.

Formalmente, la probabilidad condicional de un valor concreto en una celda se escribe como:

P(Xi=a∣XΩ∖{i})=exp⁡(−E(x(i=a)))∑b∈Aexp⁡(−E(x(i=b))).P(X_i = a \mid X_{\Omega \setminus \{i\}}) = \frac{\exp\big(-E(x^{(i=a)})\big)} {\sum\limits_{b \in A} \exp\big(-E(x^{(i=b)})\big)}.

Si estás familiarizado con las redes neuronales habrás notado que esto es similar a un Softmax!

Energía

Definimos la función de la energía como la suma de dos términos: un término de interacción (Potts) y un término de sesgo externo inducido por la imagen objetivo TT:

E(x)=Epair(x)+Eunary(x).E(x) = E_{\text{pair}}(x) + E_{\text{unary}}(x).

1) Potts (Coherencia Espacial)

Utilizamos el modelo de Potts, pues favorece que celdas vecinas compartan el mismo carácter (misma densidad), generando coherencia espacial y evitando ruido “sal y pimienta”. Para cada par de vecinos ⟨i,j⟩\langle i,j\rangle:

Epair(x)=−β∑⟨i,j⟩1[xi=xj].E_{\text{pair}}(x) = -\beta \sum_{\langle i,j\rangle} \mathbf{1}[x_i = x_j].

El parámetro β≥0\beta \ge 0 controla la fuerza de la coherencia espacial: cuanto mayor es β\beta, mayor es la tendencia a formar grandes masas homogéneas de densidad.

En la actualización local (Gibbs), este término aporta un “voto” de los vecinos; cuantos más vecinos tengan el carácter candidato aa, mayor será su probabilidad.

2) Sesgo hacia Objetivo TT

A partir del campo escalar T(i)T(i), se define un carácter preferido por celda. Sea

π:A→{0,…,K−1}\pi : A \rightarrow \{0,\dots,K-1\}

el índice del carácter en la escala de caracteres ordenada por densidad, y definimos:

π∗(i)=⌊T(i) (K−1)+12⌋,a∗(i)=aπ∗(i).\pi^*(i) = \left\lfloor T(i)\,(K-1) + \tfrac{1}{2} \right\rfloor, \qquad a^*(i) = a_{\pi^*(i)}.

Decaimiento α

Para que el sesgo sea suave, y con ello la transición del ruido hacia el objetivo, se introduce una distancia adicional:

d(au,av)=∣π(au)−π(av)∣,d(a_u,a_v) = \lvert \pi(a_u) - \pi(a_v) \rvert,

y el término unario se define como:

Eunary(x)=−λ∑i∈Ωexp⁡ ⁣(−α d(xi,a∗(i))2).E_{\text{unary}}(x) = -\lambda \sum_{i \in \Omega} \exp\!\big(-\alpha\, d(x_i, a^*(i))^2\big).

Donde:

  • λ≥0\lambda \ge 0 controla la fidelidad al objetivo TT,
  • α>0\alpha > 0 regula el decaimiento con la distancia en la rampa (cuánto penalizamos en la función desviarse del carácter preferido).

En la demo, la fidelidad no es constante: λ\lambda se incrementa linealmente desde λmin\lambda_{min} hasta λmax\lambda_{max} y se recorta al llegar al máximo. El control de Velocidad fija el incremento Δλ\Delta\lambda por frame, mientras que Fidelidad ajusta λmax\lambda_{max} (con λmin\lambda_{min} fijo en 0.03).

Formulación final de la probabilidad local

Combinando ambos términos de la energía y sustituyendo en la fórmula de Gibbs, la probabilidad condicional de asignar el carácter aa a la celda ii quedaría como:

P(Xi=a∣XN(i)=xN(i))=exp⁡ ⁣(β∑j∈N(i)1[a=xj]+λexp⁡ ⁣(−α d(a,a∗(i))2))∑b∈Aexp⁡ ⁣(β∑j∈N(i)1[b=xj]+λexp⁡ ⁣(−α d(b,a∗(i))2)).P(X_i = a \mid X_{\mathcal{N}(i)} = x_{\mathcal{N}(i)}) = \frac{ \exp\!\left( \beta \sum\limits_{j \in \mathcal{N}(i)} \mathbf{1}[a = x_j] + \lambda \exp\!\big(-\alpha\, d(a,a^*(i))^2\big) \right) }{ \sum\limits_{b \in A} \exp\!\left( \beta \sum\limits_{j \in \mathcal{N}(i)} \mathbf{1}[b = x_j] + \lambda \exp\!\big(-\alpha\, d(b,a^*(i))^2\big) \right) }.

Es decir, calculamos la probabilidad de la densidad teniendo:

  • el término de interacción, que premia la coincidencia con los vecinos (regularización),
  • el término de sesgo, que premia la proximidad al carácter objetivo inducido por TT (datos),
  • el denominador Z que simplemente normaliza la distribución hacia una probabilidad.

En la implementación interactiva, además tenemos la opción de controlar el presupuesto, este entendido como la fracción de celdas actualizadas en cada frame. A mayor presupuesto, más actualizaciones por paso y mayor coste computacional.

También se expone el ruido, la amplitud del término estocástico local. Subirlo aumenta la exploración y reduce necesariamente la coherencia global.