Descripción del Algoritmo

El algoritmo SAI es un método de interpolación no lineal cuya principal característica distintiva frente a otros es que se estiman píxeles en grupos en lugar de hacerlo individualmente.

El algoritmo está generalizado para utilizar una ventana de cualquier forma pero en este caso se utiliza una ventana en forma octogonal. Son necesarias dos pasadas de la ventana por la imagen para completar la imagen interpolada.

Figura 1: Los puntos negros representan los pixeles de la imagen original. Los puntos grises son los píxeles estimados en la primera pasada, mientras que los blancos son los estimados en la segunda pasada.

En la primer pasada se estiman los pixeles grises mostrados en la Figura 1.

Sólo se estiman aquellos pixeles cuyos vecinos se encuentren todos dentro de la ventana. Para esto se tiene en cuenta el aporte de cada vecino ponderado por la correlación espacial de la imagen entre el pixel a estimar y el correspondiente vecino (parámetros a y b de la figura 2).

Figura 2: (a) Configuración espacial en la primera pasada.
(b)Parámetros del modelo estacionario a=(a1,a2,a3,a4) correspondientes a la correlación espacial entre el pixel estimado y sus vecinos de conectividad 8, y b análogo para conectividad 4 vecinos

Para interpolar los píxeles yi deconocidos en la primer pasada se usa un modelo PAR (Piecewise Stationary Autoregressive Model) de parámetros ai para caracterizar las correlaciones diagonales en una ventana local. Con el modelo PAR se interpolan los n píxeles con una estimación por mínimos cuadrados.

Figura 3: Estimación de pixel y^ mediante mínimos cuadrados, para una ventana W dada. El supra índice indica el tipo de conectividad (en este caso 8 vecinos).

Es en la ecuación anterior donde se ve reflejada la diferencia de este método frente a los comúnmente utilizados dado que estima un bloque de pixeles a la vez. A su vez, el segundo término de la ecuación establece una realimentación al mecanismo, exigiendo que los píxeles estimados en la imagen de alta resolución se relacionen bajo el mismo conjunto de parámetros a correspondiente, lo cual permite mitigar errores de estimación prohibiendo que los valores estimados en la imagen de alta resolución violen la relación con sus vecinos de la imagen de baja resolución.

Sin embargo, como se puede observar, todavía no se incluyó la dependencia vertical y horizontal, por lo que se introduce el vector paramétrico b definido previamente en la figura (2). También a través de un modelo PAR como se muestra en la figura 4.

Figura (4): Píxeles estimados sujetos a mantener la correlación espacial vertical y horizontal entre los pixeles de la imagen de alta resolución, y los correspondientes de la imagen de baja resolución.

Para incluir esta condición a la ecuación planteada en (3), se utiliza un mutiplicador de Lagrange, denominado lambda que cumpla:

Figura (5): Restriccion de coeficientes de Lagrange

Dicho parámetro puede calcularse para cada ventana con el objetivo de cumplir la ecuación anterior, sin embargo, se recomienda que para la mayoría de las imágenes naturales un valor de lambda=0,5 no supone cambios en el rendimiento del método y ahorra cálculos.

Finalmente el problema a resolver para estimar el bloque de pixeles corresponde a la siguiente ecuación:

Figura (6): Ecuación a minimizar para estimar los pixeles faltantes en la imagen de alta resolución.

                Hasta ahora, al resolver la ecuación anterior, tenemos una imagen conformada por pixeles originales y pixeles estimados, en la cual todavía falta estimar los píxeles blancos de la figura 1 para lograr una imagen de alta resolución. Para ello es necesaria una segunda pasada, en la cual los pixeles previamente estimados serán considerados como pixeles de la imagen original. Esta segunda pasada es parecida a la primera, diferenciándose en que los pixeles son estimados utilizando los vecinos de conectividad 4 verticales y horizontales (en lugar de conectividad 8, diagonales ). La formulación del problema es análoga a la anterior.

La clave del desempeño del algoritmo reside en parte, en estimar correctamente los parámetros a y b en base a la imagen de baja resolución.

Figura(7): Configuración espacial de muestras para estimar parámetros a y b.

Los parámetros a y b se estiman utilizando mínimos cuadrados como se muestra en la figura 8 y 9.

Figura (8): Mínimos cuadrados para estimar b

Se puede observar en la figura (7b), que la relación espacial entre la imagen de baja resolución y la de alta resolución es la misma en lo que se refiere a conexión de 4 vecinos, lo cual no sucede para el parámetro "a", estimado de la forma:

                Se asume que a no mantiene la relación espacial de distancia entre ambas imágenes, por lo que la precisión de su estimación reside en asumir que la correlación entre pixeles es invariante frente a cambios en la escala, mas información de esto se puede ver en el articulo de New Edge-Directed Interpolation. Dado que la distancia entre xi -xi8 es el doble que entre yi-yi8. Sin embargo, dada la estrategia de los coeficientes de Lagrange, este error puede ser mitigado en la mayoría de los casos, robusteciendo el método.

Dado que solo se estiman aquellos pixeles cuyos vecinos pertenezcan a la ventana, al recorrer la imagen habrá solapamiento entre ventanas consecutivas como muestra la figura 10:

Figura 10: Posible configuración para algoritmo

En la imagen anterior, los pixeles estimados son y1,y2,y3,y4, dado que el resto de los pixeles a estimar se calcularán con otra ventana. La elección del tamaño de la ventana es un tema de preferencia, cuanto mayor sea, el algoritmo será más rápido, a costo de perder las propiedades estacionarias, vitales para la estimación de parámetros tal como se estableció previamente.

Para estimar los parámetros a y b definidos previamente se trabaja en la siguiente notación:

Figura 11: Notación a y b

Donde el vector v está compuesto por todos los pixeles del a imagen de baja resolución dentro de la ventana (pixeles conocidos) y la columna i-ésima de B consiste en los cuatro vecinos con conectividad 4 de xit, con t=1,2,3,4. Análogamente la columna i-ésima de A consiste en los cuatro vecinos con conectividad 8 de xi, por lo tanto si se expresa la ecuación 6 en forma matricial se obtiene:

Figura 12: Notación matricial del problema mínimos cuadrados. Donde y es el vector que contiene los pixeles y a estimar que se encuentran dentro del a ventana, siendo x es el vector de los pixeles conocidos dentro de la misma.

Figura 13: Composición de las matrices C1 y C2

También se tiene que los elementos de D1, d1(i,j) se corresponden con el parámetro ai correspondiente si el pixel xj es vecino de conexión 8 del pixel yi.

Esto es:

Por lo tanto la solución final se puede escribir de la forma:

A pesar de las dimensiones de la matriz C 12x12, como la misma es una matriz esparza conteniendo alrededor de 1/5 de sus valores no nulos, invertirla no supone un costo tan grande como a primera impresión.

Con el objetivo de reducir el costo computacional el método plantea que la estimación detallada puede hacerse solo en las áreas de gran actividad, es decir, aquellas cuya varianza sea mayor a un umbral dado, interpolando en el resto bajo un método tradicional como puede ser interpolación bicúbica.

En cuanto a la implementación, se utilizó para la primera pasada la notación sugerida en el paper, quedando los pixeles de la ventana nombrados de la siguiente manera:

Figura 15: Distribución y notación de los pixeles de la ventana en la primera pasada

En primera instancia puede parecer que la notación es poco práctica, sin embargo, a pesar de que espacialmente resulta complicada para referirse a los pixeles, matricialmente ahorra cálculos computacionales.

Dado que para la segunda pasada, el problema tiene prácticamente la misma formulación, la configuración utilizada surge de rotar la anterior 45º, por lo tanto se tiene:

Figura 16: Distribución y notación de los pixeles de la ventana en la segunda pasada

Las matrices para la segunda pasada quedan iguales pero cambiando a por b y b por a.

Por otra parte, para la estimación del multiplicador de Lagrange se utilizó la sugerencia de elegir un valor de lamda=0,5 , que no supone una pérdida de rendimiento para la mayoría de las imágenes naturales.