Publicado originalmente no Medium em 2020. Republicado aqui na íntegra, com as imagens guardadas localmente e os créditos originais.
Estava a ver um vídeo de Grant Sanderson (também conhecido como 3Blue1Brown) sobre convoluções, processamento de imagem e a linguagem de programação Julia (uma linguagem fantástica!) quando alguém fez esta pergunta.
Vê o vídeo de Grant Sanderson sobre convoluções e Julia. Recomendo-o vivamente!
Ele respondeu (corretamente) que não achava que fosse possível, porque estaríamos a perder informação. No entanto, pensei um pouco mais na questão e percebi que seria possível se a imagem de saída tivesse o mesmo tamanho que a imagem de entrada. Dessa forma, a saída teria píxeis — e informação — suficientes para recuperar a imagem original.
A convolução como filtro
Comecemos por explicar o que é uma convolução e como pode ser usada para desfocar uma imagem. Para uma explicação aprofundada, sugiro o vídeo acima; para uma versão rápida, continua por aqui. Uma convolução é uma operação matemática que, quando aplicada a imagens, pode ser entendida como um filtro.
Imagem do GitHub: vdumoulin/conv_arithmetic.
Nesta animação vemos um exemplo da convolução de uma imagem com um filtro ou kernel. A imagem original é a matriz azul, o kernel é a matriz azul-escura que desliza sobre ela e a saída é a matriz azul-esverdeada.
A convolução obtém-se multiplicando os elementos sobrepostos do kernel e da imagem e somando os produtos. As equações seguintes podem ajudar: dada uma imagem x e um kernel k, o resultado da convolução será y,
com
Se já sabias como funcionavam as convoluções em imagens, talvez este sistema de equações não seja demasiado assustador. Se não sabias, não te preocupes: não tens de o memorizar, esse é o trabalho do programa. Uma representação útil consiste em interpretar a convolução como uma multiplicação de matrizes, que não é muito difícil de escrever a partir das equações anteriores:
equivalente à equação matricial
Com esta representação, parece que, conhecendo A e y, poderíamos calcular x resolvendo a equação acima. Contudo, como A tem mais colunas do que linhas, o sistema é indeterminado, o que significa que não conseguimos obter uma única solução.
Manter a entrada e a saída com o mesmo tamanho
Comecei por dizer que, para ser possível inverter uma convolução, a entrada e a saída teriam de ter o mesmo tamanho. Na forma matricial, isto corresponderia a A ser quadrada — ter o mesmo número de linhas e colunas —, permitindo invertê-la e calcular x como
Neste momento, a entrada é 4×4 e a saída é 2×2. Como podemos obter uma saída com o mesmo tamanho da entrada? Uma possibilidade é adicionar preenchimento (padding) à imagem de entrada — por exemplo, zero-padding,
Desta forma, a saída seria 4×4, tal como a entrada original. Em detalhe, neste caso simples de uma convolução com padding, as dimensões da saída podem ser calculadas como
Se quisermos que a entrada e a saída tenham o mesmo tamanho, então o padding tem de ser
o que impõe uma condição importante: o tamanho do kernel tem de ser ímpar, uma vez que o padding é um valor inteiro.
Esta convolução também pode ser representada como uma multiplicação de matrizes semelhante à anterior, mas poupo-te à leitura porque as dimensões seriam muito maiores. Bastaria escrever as equações da convolução associadas a cada entrada de y e organizá-las numa multiplicação matricial como a anterior.
Repara que, apesar de a entrada com padding ser 6×6, correspondendo a 36 elementos, apenas 4×4 desses elementos são variáveis únicas e desconhecidas. Assim, o x da equação pode ter apenas 16×1 elementos, em vez de 36×1.
Para calcular x e inverter a convolução, basta conhecer A e y. Para construir A, é preciso conhecer o kernel usado na convolução e o tipo de padding aplicado.
Uma experiência em Julia
Como é que isto pode ser usado?
Uma imagem pode ser desfocada através de uma convolução. Por exemplo, um desfoque gaussiano é obtido convoluindo uma imagem com um kernel ou filtro que segue uma distribuição gaussiana, com o maior valor no centro e valores cuja soma é 1. Um exemplo seria o kernel
Fiz uma implementação simples deste problema em Julia para confirmar que é, de facto, possível inverter a convolução. Podes consultar e experimentar o código na ligação abaixo.
Comecei por desfocar uma imagem com um desfoque gaussiano. Apliquei uma convolução à imagem original com um kernel gaussiano e usei replicate padding: os valores fora da imagem original são definidos como o valor mais próximo da margem, em vez de zero.
Imagem original à esquerda e imagem desfocada à direita.
Como conhecia o kernel utilizado, consegui construir a matriz A e resolver a equação em ordem a x. O resultado foi o esperado: a imagem reconstruída é exatamente igual à original.
Imagem desfocada à esquerda e imagem reconstruída à direita.
Podes consultar a implementação acima e confirmar que a imagem original não foi usada na reconstrução.
Quando o kernel ou o padding estão errados
Esta reconstrução a 100% só é possível porque conhecemos o kernel e o padding usados. O que acontece se usarmos um kernel que não é exatamente igual ao usado para desfocar a imagem original?
Imagem desfocada à esquerda e reconstruída à direita quando não se usa o kernel exato.
E se assumirmos zero-padding quando foi usado replicate padding?
Imagem desfocada à esquerda e reconstruída à direita quando não se assume o padding exato.
Como vemos, se não conhecermos o kernel e o padding usados, não conseguimos reconstruir a imagem original. Neste sentido, o processo pode quase ser visto como um problema de encriptação: se conhecermos a “chave”, conseguimos reconstruir a mensagem original sem perdas nem ruído adicional.
Reconstruir a imagem original também é uma tarefa muito dispendiosa, porque a matriz A cresce muito depressa com o tamanho da imagem. Se a imagem original tiver 4×4 píxeis, A terá 16×16 elementos — o número de elementos cresce com N².
Espero que tenhas gostado desta breve explicação e que a tenhas achado interessante. Eu achei, e foi uma excelente forma de aprender mais sobre Julia, convoluções, processamento de imagem e álgebra linear. Se tiveres alguma pergunta ou encontrares algum erro, partilha-o comigo.
Como nota de despedida, acho que ainda não precisamos de nos preocupar com alguém inverter o desfoque das nossas fotografias.
Imagem desfocada à esquerda e reconstruída à direita.
Imagem de destaque.
Nota sobre esta republicação
O texto original acima foi preservado de 2020. Uma matriz quadrada não é necessariamente invertível: a recuperação também exige um operador não singular e o condicionamento numérico é relevante. A condição de o kernel ser ímpar pressupõe padding inteiro simétrico e stride unitário. Aqui, representa o número de píxeis da imagem, pelo que uma matriz de convolução densa armazena elementos. A analogia histórica com encriptação é apenas intuitiva, não uma garantia de segurança.