Este artículo proporciona información sobre la convolución bidimensional y el relleno cero con respecto al procesamiento de imágenes digitales.
En mi artículo anterior "Mejor información sobre DSP: aprendiendo sobre la convolución", hablé sobre la convolución y sus dos aplicaciones importantes en el campo del procesamiento de señales. Allí, las señales probablemente se consideraron 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, trataremos de comprender mejor el proceso y las consecuencias de la convolución bidimensional, utilizada ampliamente en el campo del procesamiento de imágenes.
La definición de convolución 2D
La convolución que involucra señales unidimensionales se conoce como convolución 1D o simplemente convolución. De lo contrario, 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), se la denominará convolución 2D. Este concepto se puede ampliar para incluir señales multidimensionales, debido a las cuales podemos tener 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 se invierte. Esta definición de convolución 1D es aplicable incluso para convolución 2D, excepto que, en este último caso, una de las entradas se invierte dos veces.
Este tipo de operación se usa ampliamente en el campo del procesamiento de imágenes digitales en el que la matriz 2D que representa la imagen se convendrá con una matriz comparativamente más pequeña llamada kernel 2D.
Un ejemplo de convolución 2D
Intentemos calcular el valor de píxel de la imagen de salida resultante de la convolución de una matriz de imagen de tamaño 5 × 5 X 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 lograr esto, el procedimiento paso a paso que debe seguirse se describe a continuación.
Paso 1: Inversión matricial
Este paso consiste en voltear el kernel a lo largo de, por ejemplo, filas seguidas de un giro a lo largo de sus columnas, como se muestra en la Figura 2.
Figura 2: Representación pictórica de la inversión matricial. Imagen creada por Sneha H.L.
Como resultado, cada (i, j) th elemento del kernel original se convierte en el (j, i) th elemento en la nueva matriz.
Paso 2: deslice el kernel sobre la imagen y realice la operación de MAC en cada instante
Superponga el kernel invertido sobre la imagen, avanzando píxel por píxel.
Para cada caso, calcule el producto de los píxeles que se superponen mutuamente y calcule su suma. El resultado será el valor del píxel de salida en esa ubicación en particular. Para este ejemplo, se supondrá 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, comenzaremos a deslizar el kernel por columnas primero y luego avanzaremos a lo largo de las filas.
Píxeles fila por fila
Primero, abarcaremos completamente la primera fila y luego avanzaremos a la segunda, y así sucesivamente.
Durante este proceso, la primera superposición entre el kernel y los píxeles de la imagen resultaría cuando el píxel en la parte inferior derecha del kernel caiga en el valor del primer píxel en la parte superior izquierda de la matriz de la imagen. Ambos valores de píxeles se resaltan y se muestran en color rojo oscuro en la Figura 3a. Por lo tanto, el primer valor de 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 en un solo píxel. En esta etapa, dos valores de la matriz del núcleo (0, 1 – mostrados en fuente de color rojo oscuro) se superponen con dos píxeles de la imagen (25 y 100 representados en fuente de color rojo oscuro) como se muestra en la Figura 3b. Por lo tanto, el valor de píxel de salida resultante será 25 × 0 + 100 × 1 = 100.
Figura 3a, 3b. Resultados de 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 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 manera similar, se pueden calcular todos los valores de píxeles de la primera fila en la imagen de salida. Dos ejemplos de este tipo correspondientes a los píxeles de salida cuarto y séptimo de la matriz de salida se muestran en las figuras 3c y 3d, respectivamente.
Si seguimos deslizando el kernel a lo largo de la misma fila, ninguno de los píxeles en el kernel se superpondrá con los de la imagen. Esto indica que hemos terminado a lo largo de la fila actual.
Bajar verticalmente, avanzar horizontalmente
El siguiente paso sería avanzar verticalmente hacia abajo en un solo píxel antes de reiniciar para moverse horizontalmente. La primera superposición que luego se produciría es como se muestra en la Figura 4a y al realizar la operación MAC sobre ellos; obtenemos el resultado como 25 × 0 + 50 × 1 = 50.
Después de esto, podemos deslizar el núcleo en dirección horizontal hasta que no haya más valores que se superpongan entre el núcleo y las matrices de imagen. En la Figura 4b se muestra un caso de este tipo correspondiente al valor del sexto píxel de la matriz de salida (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200).
Figura 4a, 4b. Resultados de 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 mover un paso hacia abajo seguido de un escaneo horizontal debe continuar hasta la última fila de la matriz de la imagen. En las figuras 5a-c se muestran tres ejemplos aleatorios relacionados con las salidas de píxeles en las ubicaciones (4,3), (6,5) y (8,6).
Figura 5a. Resultados de convolución obtenidos para los píxeles de salida en (4,3). Imagen creada por Sneha H.L.
Figura 5b. Resultados de convolución obtenidos para los píxeles de salida en (6,5). Imagen creada por Sneha H.L.
Figura 5c. Resultados de convolución obtenidos para los píxeles de salida en (8,6). Imagen creada por Sneha H.L.
Paso
Por lo tanto la matriz de salida resultante será:
Figura 6. La matriz de salida resultante de nuestro ejemplo. Imagen creada por Sneha H.L.
Zero Padding
La formulación matemática de la convolución 2-D está dada por
$$ y left[i,jright]= sum_ {m = – infty} ^ infty sum_ {n = – infty} ^ infty h left[m,nright] cdot x left[i-m,j-nright] $$
dónde, X Representa la matriz de imagen de entrada que se debe convertir con la matriz del kernel. h para dar lugar a una nueva matriz y, representando la imagen de salida. Aquí, los índices. yo y j están relacionados con las matrices de imágenes mientras que las de metro y norte lidiar con eso del kernel. Si el tamaño del kernel involucrado en la convolución es 3 × 3, entonces los índices metro y norte rango de -1 a 1. Para este caso, una expansión de la fórmula presentada resulta en
$$ y left[i,jright]= sum_ {m = – infty} ^ infty h left[m,-1right] cdot x left[i-m,j+1right] + h izquierda[m,0right] cdot x left[i-m,j-0right] + h left[m,1right] cdot x left[i-m,j-1right] $$
$$ y left[i,jright]= h left[-1,-1right] cdot x left[i+1,j+1right] + h izquierda[-1,0right] cdot x left[i+1,jright] + h izquierda[-1,1right] cdot x left[i+1,j-1right] + h left[0,-1right] cdot x left[i,j+1right] + h izquierda[0,0right] cdot x left[i,jright] + h izquierda[0,1right] cdot x left[i,j-1right] + h left[1,-1right] cdot x left[i-1,j+1right] + h izquierda[1,0right] cdot x left[i-1,jright] + h izquierda[1,1right] cdot x left[i-1,j-1right] $$
Esto indica que para obtener cada píxel de salida, deben realizarse 9 multiplicaciones cuyos factores son los elementos de píxel superpuestos de la imagen y el núcleo. Sin embargo, mientras calculamos el valor de nuestro primer píxel de salida, solo realizamos una sola multiplicación (la Figura 3a se replica como la Figura 7a). ¿Qué significa esto? ¿Implica una inconsistencia con la forma de ecuación de convolución 2-D?
No en realidad no. Porque, el resultado obtenido por la suma de nueve términos de producto puede ser igual al producto de un solo término si el efecto colectivo de los otros ocho términos de producto se iguala a cero. Una de esas 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 convertirse en cero para que los resultados de la fórmula-cálculo sean iguales a los de la gráfica-computación.
Por nuestro conocimiento elemental de las matemáticas, sabemos que si al menos uno de los factores involucrados en la multiplicación es cero, entonces el producto resultante también es cero. Por esta analogía, podemos afirmar que, en nuestro ejemplo, debemos tener un píxel de imagen de valor cero correspondiente a cada uno de los píxeles no superpuestos de la matriz del kernel. La representación pictórica de esto sería la que se muestra en la Figura 7b. Una cosa importante que se debe tener en cuenta aquí es que tal adición de ceros a la imagen no altera la imagen en ningún sentido, excepto en su tamaño.
Figura 7: Se muestra cero relleno para el primer píxel de la imagen (Dibujado por mí)
Este proceso de agregar ceros adicionales se conoce como relleno cero y se debe realizar en cada caso en el que no haya píxeles de imagen que se superpongan con los píxeles del kernel. En nuestro ejemplo, el relleno cero debe llevarse a cabo 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 color azul en la fuente de la Figura 8) . En general, el número de filas o columnas a rellenar con cero en cada lado de la imagen de entrada viene dado por (número de filas o columnas en el kernel – 1).
Figura 8
Una cosa importante que debe mencionarse es el hecho de que el relleno cero no es la única manera de lidiar con los efectos de borde provocados por la convolución. Otras técnicas de relleno incluyen el relleno duplicado, la extensión periódica, la creación de reflejos, etc. (Procesamiento de imágenes digitales con 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 en 2-D y el concepto de relleno cero con respecto al procesamiento de imágenes digitales.