ALGORITMO

Enfoque del problema || El algoritmo || "Relleno" de una sección de la imagen


Enfoque del problema

  Como ya dijimos, el objetivo del trabajo es sustituir una zona de la imagen que fue eliminada por algo que "disimule" su falta. El algoritmo hace esto generando pixels que tengan que ver estadísticamente con la imagen. Lo que hace es sustituir los pixels eliminados por otros que tengan la misma distribución de probabilidad que el resto de la imagen, dado el contexto del pixel a rellenar. O sea, se asume que el modelo de la imagen es un Markov Random Field (MRF). Por lo tanto se supone que el nivel de gris de un determinado pixel, dado los valores de los pixels vecinos, es independiente del resto de la imagen. En nuestro caso el contexto será una ventana cuadrada alrededor del pixel. El tamaño de dicha ventana será un parámetro que definirá el usuario y que indicará qué tan estocástica se cree que es la imagen. Cuanto más pequeña la ventana, menos estructurado será el resultado de la sustitución.

  Le llamaremos p al pixel a regenerar. Entonces, una primera idea sería generar tablas con su distribución de probabilidad de p dado cualquier contexto. Una vez determinado el contexto del pixel, restaría simplemente muestrear un valor con la distribución indicada en la tabla. Aunque parece sencillo, la dificultad que hace a esta idea inútil es que la tabla tendría un tamaño inmanejable. Supongamos una ventana de lado 3 (que es bastante pequeña) en una imagen de 256 niveles de gris. La cantidad de distintos contextos sería 25632-1 = 264, que es poco menos de 2x1019.

  Otra idea - que nos evita este problema - consiste en, dado el contexto de p, recorrer la imagen y construir la densidad de probabilidad como el histograma de todos los posibles valores que toman aquellos pixels que tienen el mismo contexto que p. En realidad, como veremos más adelante, el histograma lo construiremos no sólo con aquellos pixels que tengan el mismo contexto, sino también con aquellos que tengan uno "similar".

  Una posible crítica al algoritmo es la necesidad de recorrer toda la imagen por cada pixel que se quiere generar. Como veremos más adelante, esto será el principal culpable de que el algoritmo no sea demasiado rápido.

arriba


El algoritmo

  Como primera aproximación, supongamos que queremos rellenar solamente un pixel en una imagen infinita Iinf . Sea p el pixel a generar; w una ventana cuadrada centrada en él; y d(w1,w2) una distancia entre ventanas con distintos pixels de centro. Además, sea el conjunto:

  Por lo tanto, la distribución de probabilidad condicional de p puede estimarse mediante el histograma de todos los pixels que son centro de las ventanas pertenecientes a A.

  Ahora, nosotros contamos con una imagen finita Ifin contenida dentro de la imagen ideal infinita. Esto significa que el conjunto A así definido, pero para la imagen finita, puede llegar a ser vacío. Por lo tanto debemos encontrar un conjunto A' que nos permita hacer una aproximación razonable de la distribución de probabilidad condicional. El algoritmo fabrica ese conjunto hallando, primero que nada, la ventana wmejor contenida en Ifin que tiene la mínima distancia respecto a la ventana centrada en p. Sea esa distancia dmín. El conjunto A' resulta:

  Donde e es un valor arbitrario que los autores recomiendan sea 0.1. Es interesante observar que si se da el caso de que dmín resulta cero, A' contendrá sólo ventanas cuya distancia sea cero.

  Con el conjunto A' ya definido podemos hallar el histograma y muestrear de allí. Esto se puede hacer tomando en cuenta o no la distancia a la cual se encontraba cada ventana. En nuestra implementación no tomamos en cuenta la distancia.

  Lo único que resta hacer es definir la distancia que vamos a usar . La primera opción es considerar la suma cuadrática de las diferencias. Pero el problema que tiene es que le da el mismo peso a todas las diferencias, independientemente de la distancia al centro de la ventana. Como nosotros queremos preservar lo más posible la estructura local de la textura, esto es un inconveniente. Por lo tanto vamos a multiplicar punto a punto la matriz de las diferencias cuadráticas con un kernel gaussiano. De esta forma le damos más peso a los errores cerca del centro de la ventana, que a los que están más hacia los extremos de la misma.

arriba


"Relleno" de una sección de la imagen

  Lo que desarrollamos en la sección anterior fue para generar un solo pixel. Por ende, no nos sirve en nuestro problema, pues tal como describimos el algoritmo, todos los pixels alrededor del pixel a generar deben ser conocidos. Habría que modificar el algoritmo para que maneje la situación de tener algunos pixels desconocidos alrededor. Lo único que hay que hacer es simplemente redefinir la distancia, pero tomando en cuenta sólo los valores conocidos, y normalizándola entre la cantidad que haya de ellos.

  Claro está que los pixels deben generarse desde el borde hacia el interior del "agujero". Los pixels del borde son los que tienen la mayor cantidad de pixels conocidos dentro de su ventana y son por lo tanto los más confiables para generar primero. Es por eso que el primer paso consiste en verificar qué pixel de los que falta generar es el que tiene más pixels conocidos dentro de su ventana. Luego, ese será el pixel a generar en esa iteración. Cabe la pregunta de si se puede considerar como conocidos a los pixels ya generados. La respuesta es que sí y no: sí se pueden considerar conocidos para tener definido un entorno en el caso de los pixels más interiores al "agujero", pero no se pueden considerar conocidos en el momento de generar el histograma. Esto se hace evidente al trabajar con "agujeros" grandes, comparables con el tamaño del sector de la imagen que se conoce; en estos casos, si se incluye en el histograma a los valores regenerados, se obtienen resultados no deseados.

  Por lo tanto, en resumen, el algoritmo consiste en, primero que nada, hallar el pixel a generar que tiene más pixels conocidos dentro de su ventana. Luego, se compara su ventana con la ventana de todo el resto de los pixels de la imagen, calculando la distancia entre ellas. Se calcula el histograma de todos los pixels que están a una distancia menor que la distancia mínima multiplicada por un factor mayor o igual a uno. Se toma éste como una aproximación a la densidad de probabilidad condicional del pixel a generar y se muestrea de ella un valor. Se le asigna ese valor al pixel y se vuelve a repetir el proceso hasta que no haya más pixels a rellenar. El único parámetro a definir por el usuario es el tamaño de la ventana, que como ya dijimos está relacionado con qué tan estocástica es la textura a generar.

arriba arriba siguiente