2D Convolution in Image Processing

Este artigo fornece uma visão da convolução bidimensional e zero-padding com respeito ao processamento digital de imagens.

No meu artigo anterior “Better Insight into DSP: Learning about Convolution”, eu discuti convolução e suas duas importantes aplicações no campo de processamento de sinais. Lá, os sinais foram presumivelmente considerados como sendo unidimensionais no domínio espacial. Entretanto, o processo de convolução também pode ser levado em sinais multidimensionais.

Neste artigo, vamos tentar entender melhor o processo e as consequências da convolução bidimensional, usada extensivamente no campo de processamento de imagens.

A definição de Convolução 2D

Convolução envolvendo sinais unidimensionais é referida como convolução 1D ou apenas convolução. Caso contrário, se a convolução for realizada entre dois sinais que se estendem ao longo de duas dimensões mutuamente perpendiculares (isto é, se os sinais são bidimensionais por natureza), então ela será referida como convolução 2D. Este conceito pode ser estendido para envolver sinais multidimensionais devido aos quais podemos ter convolução multidimensional.

No domínio digital, a convolução é realizada multiplicando e acumulando os valores instantâneos das amostras sobrepostas correspondentes a dois sinais de entrada, um dos quais é invertido. Esta definição de convolução 1D é aplicável mesmo para a convolução 2D, exceto que, neste último caso, uma das entradas é invertida duas vezes.

Este tipo de operação é extensivamente utilizada no campo de processamento de imagem digital onde a matriz 2D que representa a imagem será envolvida com uma matriz comparativamente menor chamada kernel 2D.

Um Exemplo de Convolução 2D

Tentemos calcular o valor de pixel da imagem de saída resultante da convolução da matriz x de imagem de tamanho 5×5 com o kernel h de tamanho 3×3, mostrado abaixo na Figura 1.

Figure 1: Matrizes de entrada, onde x representa a imagem original e h representa o kernel. Imagem criada por Sneha H.L.

Para realizar isto, o procedimento passo-a-passo a ser seguido é descrito abaixo.

Passo 1: Inversão de matriz

Este passo envolve a inversão do kernel ao longo, digamos, de linhas seguidas por uma inversão ao longo de suas colunas, como mostrado na Figura 2.

Figure 2: Representação pictórica da inversão de matriz. Imagem criada por Sneha H.L.

Como resultado, cada (i,j)elemento do kernel original torna-se o (j,i)elemento da nova matriz.

Passo 2: Deslize o kernel sobre a imagem e execute a operação MAC a cada instante

Passe o kernel invertido sobre a imagem, avançando pixel por pixel.

Para cada caso, calcule o produto dos pixels sobrepostos mutuamente e calcule sua soma. O resultado será o valor do pixel de saída naquele local em particular. Para este exemplo, assume-se que os pixels não sobrepostos terão o valor ‘0’. Discutiremos isso com mais detalhes na próxima seção em “Zero Padding”.

No presente exemplo, começaremos a deslizar a coluna do kernel primeiro e depois avançar ao longo das linhas.

Pixels linha por linha

Primeiro, vamos percorrer completamente a primeira linha e depois avançar para a segunda, e assim por diante e assim por diante.

Durante este processo, a primeira sobreposição entre o kernel e os pixels da imagem resultaria quando o pixel na parte inferior direita do kernel caísse no valor do primeiro pixel na parte superior esquerda da matriz da imagem. Ambos os valores de pixel são realçados e mostrados na cor vermelha escura na Figura 3a. Então, o primeiro valor de pixel da imagem de saída será 25 × 1 = 25.

Next, vamos avançar o kernel ao longo da mesma linha por um único pixel. Neste estágio, dois valores da matriz do kernel (0, 1 – mostrado em fonte vermelha escura) se sobrepõem com dois pixels da imagem (25 e 100 representados em fonte vermelha escura) como mostrado na Figura 3b. Assim, o valor do pixel de saída resultante será 25 × 0 + 100 × 1 = 100.

Figura 3a, 3b. Resultados de convolução obtidos para os pixels de saída no local (1,1) e (1,2). Imagem criada por Sneha H.L.

Figure 3c, 3d: Resultados de convolução obtidos para os pixels de saída no local (1,4) e (1,7). Imagem criada por Sneha H.L.

Advancing similarmente, todos os valores dos pixels da primeira linha da imagem de saída podem ser computados. Dois desses exemplos correspondentes ao quarto e sétimo pixels de output da matriz de output são mostrados nas figuras 3c e 3d, respectivamente.

Se continuarmos a deslizar o kernel pela mesma linha, nenhum dos pixels do kernel se sobrepõe aos da imagem. Isto indica que estamos fazendo ao longo da linha atual.

Move Down Vertically, Advance Horizontally

O próximo passo seria avançar verticalmente para baixo por um único pixel antes de reiniciar para mover horizontalmente. A primeira sobreposição que então ocorreria é como mostrado na Figura 4a e executando a operação MAC sobre eles; obtemos o resultado como 25 × 0 + 50 × 1 = 50.

Seguir isto, podemos deslizar o kernel na direcção horizontal até não haver mais valores que se sobreponham entre o kernel e as matrizes da imagem. Um desses casos correspondente ao sexto valor de pixel da matriz de saída (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) é mostrado na Figura 4b.

Figure 4a, 4b. Resultados de convolução obtidos para os pixels de saída no local (2,1) e (2,6). Imagem criada por Sneha H.L.

Este processo de mover um passo para baixo seguido de digitalização horizontal tem que continuar até a última linha da matriz da imagem. Três exemplos aleatórios relacionados com as saídas dos pixels nos locais (4,3), (6,5) e (8,6) são mostrados nas Figuras 5a-c.

Figure 5a. Resultados de convolução obtidos para os pixels de saída em (4,3). Imagem criada por Sneha H.L.

Figure 5b. Resultados da convolução obtidos para os pixels de saída em (6,5). Imagem criada por Sneha H.L.

Figure 5c. Resultados da convolução obtidos para os pixels de saída em (8,6). Imagem criada por Sneha H.L.

Passo

Hence a matriz resultante será:

Figure 6. A matriz de saída resultante do nosso exemplo. Imagem criada por Sneha H.L. x representa a matriz da imagem de entrada a ser envolvida com a matriz h do kernel para resultar em uma nova matriz y, representando a imagem de saída. Aqui, os índices i e j estão preocupados com as matrizes de imagem enquanto as de m e n lidam com a do kernel. Se o tamanho do kernel envolvido na convolução é 3 × 3, então os índices m e n variam de -1 a 1. Para este caso, uma expansão da fórmula apresentada resulta em

$$¥¥¥esquerda=\sum_{m=-\esquerda esquerda esquerda x esquerda + esquerda x esquerda + esquerda x esquerda + esquerda x esquerda + esquerda x esquerda x esquerda x esquerda tem que haver 9 multiplicações a serem realizadas cujos fatores são os elementos de pixels sobrepostos da imagem e do núcleo. No entanto, enquanto calculamos o valor do nosso primeiro pixel de saída, realizamos apenas uma única multiplicação (Figura 3a replicada como Figura 7a). O que isso significa? Implica uma inconsistência com a forma de equação de convolução 2-D?

Não, não realmente. Porque, o resultado obtido pela soma de nove termos do produto pode ser igual ao produto de um único termo se o efeito coletivo dos outros oito termos do produto se igualar a zero. Uma dessas formas é o caso em que cada produto dos outros oito termos se avalia a si mesmo como sendo zero. No contexto do nosso exemplo, isto significa que todos os termos de produto correspondentes aos pixels não sobrepostos (entre a imagem e o kernel) devem tornar-se zero para que os resultados da fórmula-computação sejam iguais aos da computação gráfica.

Dos nossos conhecimentos elementares de matemática, sabemos que se pelo menos um dos fatores envolvidos na multiplicação é zero, então o produto resultante também é zero. Por esta analogia, podemos afirmar que, em nosso exemplo, precisamos ter um pixel de imagem com valor zero correspondente a cada pixel não sobreposto da matriz do kernel. A representação pictórica disto seria a que é mostrada na Figura 7b. Uma coisa importante a ser notada aqui é que tal adição de zeros à imagem não altera a imagem em nenhum sentido exceto seu tamanho.

Figure 7: Zero-padding mostrado para o primeiro pixel da imagem (Drawn by me)

Este processo de adição de zeros extras é conhecido como padding zero e é necessário ser feito em cada caso onde não há pixels da imagem para sobrepor os pixels do kernel. Para o nosso exemplo, o preenchimento zero requer ser feito para cada pixel que se encontra ao longo das duas primeiras linhas e colunas, assim como aqueles que aparecem ao longo das duas últimas linhas e colunas (estes pixels são mostrados em fonte azul na Figura 8). Em geral, o número de linhas ou colunas a serem zero-padded em cada lado da imagem de entrada é dado por (número de linhas ou colunas no kernel – 1).

Figure 8

Uma coisa importante a ser mencionada é o fato de que zero padding não é a única maneira de lidar com os efeitos de borda trazidos pela convolução. Outras técnicas de acolchoamento incluem acolchoamento replicado, extensão periódica, espelhamento, etc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Sumário

Este artigo visa explicar o método gráfico da convolução em 2-D e o conceito de acolchoamento zero com respeito ao processamento digital de imagens.