Este artículo proporciona una visión de la convolución bidimensional y el relleno de cero con respecto al procesamiento digital de imágenes.
En mi artículo anterior «Una mejor visión de la DSP: aprendiendo sobre la convolución», discutí la convolución y sus dos importantes aplicaciones en el campo del procesamiento de señales. Allí, las señales se consideraban presumiblemente unidimensionales en el dominio espacial. Sin embargo, el proceso de convolución también puede llevarse a cabo en señales multidimensionales.
En este artículo, intentaremos comprender mejor el proceso y las consecuencias de la convolución bidimensional, muy utilizada en el campo del procesamiento de imágenes.
- La definición de convolución 2D
- Un ejemplo de convolución 2D
- Figura 1: Matrices de entrada, donde x representa la imagen original y h representa el núcleo. Imagen creada por Sneha H.L.
- Paso 1: Inversión de la matriz
- Figura 2: Representación pictórica de la inversión de la matriz. Imagen creada por Sneha H.L.
- Paso 2: Deslizar el kernel sobre la imagen y realizar la operación MAC en cada instante
- Figura 3a, 3b. Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (1,1) y (1,2). Imagen creada por Sneha H.L.
- Figura 3c, 3d: Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (1,4) y (1,7). Imagen creada por Sneha H.L.
- Figura 4a, 4b. Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (2,1) y (2,6). Imagen creada por Sneha H.L.
- Figura 5a. Resultados de la convolución obtenidos para los píxeles de salida en (4,3). Imagen creada por Sneha H.L.
- Figura 5b. Resultados de la convolución obtenidos para los píxeles de salida en (6,5). Imagen creada por Sneha H.L.
- Figura 5c. Resultados de la convolución obtenidos para los píxeles de salida en (8,6). Imagen creada por Sneha H.L.
- Paso
- Figura 6. La matriz de salida resultante de nuestro ejemplo. Imagen creada por Sneha H.L.
- Almohadilla Cero
- Figura 7: Relleno cero mostrado para el primer píxel de la imagen (dibujado por mí)
- Figura 8
- Resumen
La definición de convolución 2D
La convolución que implica señales unidimensionales se denomina convolución 1D o simplemente convolución. En cambio, si la convolución se realiza entre dos señales que se extienden a lo largo de dos dimensiones mutuamente perpendiculares (es decir, si las señales son de naturaleza bidimensional), entonces se denominará convolución 2D. Este concepto puede ampliarse para incluir señales multidimensionales, por lo que podemos tener una convolución multidimensional.
En el dominio digital, la convolución se realiza multiplicando y acumulando los valores instantáneos de las muestras superpuestas correspondientes a dos señales de entrada, una de las cuales está invertida. Esta definición de convolución 1D es aplicable incluso para la convolución 2D, excepto que, en este último caso, una de las entradas se voltea dos veces.
Este tipo de operación se utiliza ampliamente en el campo del procesamiento digital de imágenes en el que la matriz 2D que representa la imagen será convolucionada con una matriz comparativamente más pequeña llamada núcleo 2D.
Un ejemplo de convolución 2D
Intentemos calcular el valor del píxel de la imagen de salida resultante de la convolución de la matriz de imagen x de tamaño 5×5 con el núcleo h de tamaño 3×3, que se muestra a continuación en la Figura 1.
Figura 1: Matrices de entrada, donde x representa la imagen original y h representa el núcleo. Imagen creada por Sneha H.L.
Para lograrlo, a continuación se describe el procedimiento paso a paso a seguir.
Paso 1: Inversión de la matriz
Este paso implica el volteo del núcleo a lo largo de, digamos, las filas, seguido de un volteo a lo largo de sus columnas, como se muestra en la Figura 2.
Figura 2: Representación pictórica de la inversión de la matriz. Imagen creada por Sneha H.L.
Como resultado, cada (i,j)º elemento del núcleo original se convierte en el (j,i)º elemento de la nueva matriz.
Paso 2: Deslizar el kernel sobre la imagen y realizar la operación MAC en cada instante
Superponer el kernel invertido sobre la imagen, avanzando píxel a píxel.
Para cada caso, calcular el producto de los píxeles que se superponen mutuamente y calcular su suma. El resultado será el valor del píxel de salida en ese lugar concreto. Para este ejemplo, se asumirá que los píxeles no superpuestos tienen un valor de ‘0’. Discutiremos esto con más detalle en la siguiente sección sobre «Relleno Cero».
En el presente ejemplo, empezaremos a deslizar el núcleo por columnas primero y luego avanzaremos por las filas.
Píxeles Fila por Fila
Primero, abarquemos la primera fila por completo y luego avancemos a la segunda, y así sucesivamente.
Durante este proceso, el primer solapamiento entre el núcleo y los píxeles de la imagen se produce cuando el píxel de la parte inferior derecha del núcleo cae sobre el valor del primer píxel de la parte superior izquierda de la matriz de la imagen. Ambos valores de píxel están resaltados y se muestran en color rojo oscuro en la Figura 3a. Así, el valor del primer píxel de la imagen de salida será 25 × 1 = 25.
A continuación, avancemos el núcleo a lo largo de la misma fila un solo píxel. En esta etapa, dos valores de la matriz del kernel (0, 1 – mostrados en letra roja oscura) se solapan con dos píxeles de la imagen (25 y 100 representados en letra roja oscura) como se muestra en la Figura 3b. Así, el valor del píxel de salida resultante será 25 × 0 + 100 × 1 = 100.
Figura 3a, 3b. Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (1,1) y (1,2). Imagen creada por Sneha H.L.
Figura 3c, 3d: Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (1,4) y (1,7). Imagen creada por Sneha H.L.
Avanzando de forma similar, se pueden calcular todos los valores de los píxeles de la primera fila de la imagen de salida. Dos ejemplos de este tipo correspondientes a los píxeles cuarto y séptimo de la matriz de salida se muestran en las figuras 3c y 3d, respectivamente.
Si seguimos deslizando el núcleo a lo largo de la misma fila, ninguno de los píxeles del núcleo se solapa con los de la imagen. Esto indica que hemos terminado a lo largo de la fila actual.
Mover verticalmente hacia abajo, avanzar horizontalmente
El siguiente paso sería avanzar verticalmente hacia abajo un solo píxel antes de reiniciar el movimiento horizontal. El primer solapamiento que se produciría entonces es el que se muestra en la Figura 4a y al realizar la operación MAC sobre ellos; obtenemos el resultado como 25 × 0 + 50 × 1 = 50.
Siguiendo esto, podemos deslizar el núcleo en dirección horizontal hasta que no haya más valores que se solapen entre el núcleo y las matrices de la imagen. Uno de estos casos, correspondiente al valor del sexto píxel de la matriz de salida (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) se muestra en la Figura 4b.
Figura 4a, 4b. Resultados de la convolución obtenidos para los píxeles de salida en la ubicación (2,1) y (2,6). Imagen creada por Sneha H.L.
Este proceso de desplazamiento de un paso hacia abajo seguido de un barrido horizontal debe continuarse hasta la última fila de la matriz de la imagen. En las figuras 5a-c se muestran tres ejemplos aleatorios relacionados con los píxeles de salida en las ubicaciones (4,3), (6,5) y (8,6).
Figura 5a. Resultados de la convolución obtenidos para los píxeles de salida en (4,3). Imagen creada por Sneha H.L.
Figura 5b. Resultados de la convolución obtenidos para los píxeles de salida en (6,5). Imagen creada por Sneha H.L.
Figura 5c. Resultados de la convolución obtenidos para los píxeles de salida en (8,6). Imagen creada por Sneha H.L.
Paso
Por tanto, la matriz de salida resultante será:
Figura 6. La matriz de salida resultante de nuestro ejemplo. Imagen creada por Sneha H.L.
Almohadilla Cero
La formulación matemática de la convolución bidimensional viene dada por
$$ y\left=\suma_{m=-\infty}^\infty\suma_{n=-\infty}^\infty h\left \cdot x\left $$
donde, x representa la matriz de la imagen de entrada que se va a convolucionar con la matriz del núcleo h para dar lugar a una nueva matriz y, que representa la imagen de salida. Aquí, los índices i y j se refieren a las matrices de la imagen, mientras que los de m y n se ocupan de la del núcleo. Si el tamaño del núcleo implicado en la convolución es de 3 × 3, los índices m y n van de -1 a 1. Para este caso una expansión de la fórmula presentada da como resultado
$$ y\left=\sum_{m=-\infty}^\infty h\left \cdot x\left + h\left \cdot x\left \\cdot x\left + h\left \cdot x\left $$
$$ y\left= h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \cdot x\left $$
Esto indica que para obtener cada pixel de salida, hay que realizar 9 multiplicaciones cuyos factores son los elementos de los píxeles superpuestos de la imagen y del núcleo. Sin embargo, mientras calculamos el valor de nuestro primer píxel de salida, sólo realizamos una única multiplicación (Figura 3a replicada como Figura 7a). ¿Qué significa esto? ¿Implica una incoherencia con la forma de ecuación de la convolución bidimensional?
No, en realidad no. Porque, el resultado obtenido por la suma de nueve términos producto puede ser igual al producto de un solo término si el efecto colectivo de los otros ocho términos producto se iguala a cero. Una de estas formas es el caso en el que cada producto de los otros ocho términos se evalúa a sí mismo como cero. En el contexto de nuestro ejemplo, esto significa que todos los términos del producto correspondientes a los píxeles no superpuestos (entre la imagen y el núcleo) deben ser cero para que los resultados de la fórmula-computación sean iguales a los de la gráfica-computación.
Desde nuestro conocimiento elemental de las matemáticas, sabemos que si al menos uno de los factores implicados en la multiplicación es cero, entonces el producto resultante también es cero. Por esta analogía, podemos afirmar que, en nuestro ejemplo, necesitamos tener una imagen-píxel de valor cero correspondiente a cada píxel no solapado de la matriz del núcleo. La representación pictórica de esto sería la que se muestra en la Figura 7b. Una cosa importante a tener en cuenta aquí es que la adición de ceros a la imagen no altera la imagen en ningún sentido, excepto en su tamaño.
Figura 7: Relleno cero mostrado para el primer píxel de la imagen (dibujado por mí)
Este proceso de adición de ceros adicionales se conoce como relleno cero y se requiere que se haga en cada caso en el que no haya píxeles de la imagen que se superpongan a los píxeles del núcleo. En nuestro ejemplo, el relleno cero debe realizarse para todos y cada uno de los píxeles que se encuentran a lo largo de las dos primeras filas y columnas, así como los que aparecen a lo largo de las dos últimas filas y columnas (estos píxeles se muestran en azul en la Figura 8). En general, el número de filas o columnas que hay que rellenar de cero en cada lado de la imagen de entrada viene dado por (número de filas o columnas en el núcleo – 1).
Figura 8
Una cosa importante que hay que mencionar es el hecho de que el relleno de cero no es la única forma de tratar los efectos de borde provocados por la convolución. Otras técnicas de relleno incluyen el relleno de réplica, la extensión periódica, el reflejo, etc. (Digital Image Processing Using Matlab 2E, González, Tata McGraw-Hill Education, 2009).
Resumen
Este artículo tiene como objetivo explicar el método gráfico de la convolución bidimensional y el concepto de relleno cero con respecto al procesamiento digital de imágenes.