Transformadas Wavelet em Visão Computacional
A transformada que revolucionou a Pixar e o mundo
Texto Escrito por: Rodrigo Fill Rangel e Rodrigo Estevam
Olá, caro leitor de Turing Talks, seja muito bem vindo a mais um texto da nossa querida série de textos de visão computacional. Se você leu nosso texto de algumas semanas atrás sobre Transformada de Fourier deve estar esperando ansiosamente por este aqui, que é uma continuação espiritual daquele, da mesma forma que a transformada wavelet é uma sucessora da transformada de Fourier de alguma maneira. Pra entender tudo que eu vou falar aqui é importante que você tenha acompanhado o texto passado, que está bem aqui: Transformada de Fourier em Visão Computacional. Vai lá, da uma lida, deixa os claps e depois volta aqui pra aproveitar tudinho.
Resolução espectral da transformada wavelet
Eu terminei o texto passado falando sobre as resoluções, tanto da transformada de Fourier quanto da transformada de Fourier de tempo curto. Agora vamos direto falar sobre a resolução espectral da transformada wavelet, já pra mostrar para vocês como ela apresenta uma melhoria em relação às propostas anteriores. O grid de resolução da transformada wavelet é genericamente assim:
Numa primeira olhada ele parece devidamente estranho, né? Mas existem ótimas justificativas para esta divisão. Vejamos, primeiramente, que em baixas frequências a resolução temporal é baixa, correto? Sim, ela é baixa pois uma onda de baixa frequência muda lentamente no tempo, ou seja, não precisamos ter uma grande resolução para medir coisas que mudam de forma lenta, mas conforme a frequência aumenta é necessário aumentar a resolução temporal, visto que agora as coisas mudam mais rapidamente no tempo, o período de oscilação é menor, assim para obter mais informação, temos de aumentar a resolução temporal e reduzir a resolução espectral do sinal, já que geralmente as frequências altas são menos significativas no sistema. E assim temos a estrutura em grid mostrada. Vale dizer que esta estrutura pode ser definida por você para satisfazer as suas necessidades.
Para conseguir este padrão a transformada wavelet vai funcionar de forma similar à transformada de Fourier, ela toma a função de análise e projeta a mesma sobre uma base ortogonal, a grande diferença neste caso é que a base ortogonal utilizada neste caso não será meramente uma junção de senos e cossenos, mas uma hierarquia de funções ortogonais, que vão modificadas, ajustadas, para justamente se encaixarem nestes menores retângulos de resolução na imagem acima. Essas funções descritas são chamadas de wavelets, elas devem ser funções ortogonais, ou seja, integral nula no tempo, e podem ter diferentes formatos, por isso que existem diversas transformadas wavelets, porque a função wavelet utilizada pode variar, alguns tipos são:
Todas estas funções serão então descritas como sendo uma Ψ(𝑡). Esta função será a “wavelet mãe” que dará origem a outras variações de wavelets usadas para serem adaptadas a cada uma das resoluções. A função genérica de uma “wavelet filha” em função da wavelet mãe é:
É possível notar que os fatores a e b definem deslocamento e o escalonamento da função, então o valor de b desloca a função no tempo, escolhendo para qual retângulo da esquerda para a direita aquela variação de wavelet corresponde, enquanto que o parâmetro a aumenta ou encolhe a função no tempo, e isso essencialmente corresponde à aumentar ou diminuir a frequência da onda, escolhendo verticalmente qual seria o retângulo correspondente. Para entender melhor veja a imagem abaixo:
A curva em azul em todos os casos mostra a wavelet mãe, enquanto que para cada quadro temos uma variação possível em termos dos parâmetros a e b. Veja agora como cada wavelet “filha” preenche o retângulo de resolução:
Em se tratando de Wavelets já cobrimos quase tudo que tinha para cobrir, resta apenas agora definir a fórmula da transformada em si, mas não é nada muito obscuro, segue a mesma estrutura da definição em Fourier:
Que consiste simplesmente no produto interno entre a wavelet em questão e a função a ser transformada, lembrando que no espaço de funções contínuas o produto interno corresponde àquela integral mencionada no texto anterior, mas não precisamos nos focar nos aspectos matemáticos neste momento. Agora que já cobrimos quase tudo do básico da teoria de wavelets, vamos tentar aplicar esta transformação em uma imagem, claro, bem como a FFT, a transformada wavelet pode ser definida espacialmente em uma versão 2d. Vejamos um exemplo de implementação.
Wavelets aplicadas espacialmente
Assim como em Fourier, a transformada espacial da wavelet é bastante diferente da temporal e tentar entender o processo espacial pode ser mais eficiente se feito de forma mais visual. Vamos usar uma biblioteca em python que já cuida de toda aplicação espacial, e temporal se essa for a aplicação. Essa biblioteca é chamada PyWavelets e pode ser encontrada aqui. Os códigos aqui apresentados são baseados no material dos professores Steven. L. Brunton & J. Nathan Kutz, que é uma excelente referência para o tema.
A princípio vamos apenas escolher uma imagem e aplicar a transformada para ver o resultado direto:
O primeiro passo está abaixo, em que definimos o nível de decomposição, no caso n = 1 mesmo, e o tipo de wavelet, no caso a daubacchies 1 como mostrada na imagem de wavelets acima. Com um pré-processamento podemos chegar no resultado abaixo:
O resultado é curioso, temos uma imagem com a metade do tamanho da original, além de outras 3 imagens que são uma espécie de detalhes da imagem original. Para explicar exatamente o que está acontecendo na imagem acima eu vou necessitar da ajuda de uma das maiores pesquisadoras da área hoje, Ingrid Daubechies, com base nos slides desta aula.
O que está acontecendo neste slide acima é o seguinte: Temos uma imagem na parte superior e ampliamos a imagem até vermos os pixels dela, bem como seus valores. Estes pixels estão na primeira linha de números. Repare como os números são valores muito próximos, eles tem uma diferença brusca em um ponto mas em sua grande parte os valores são próximos, então vamos fazer o seguinte, vamos tentar unir eles., tirando a média entre dois pixels adjacentes. O resultado é a segunda linha. Ao fazer isso perdemos informação sobre os pixels anteriores, correto? Eram dois agora temos um só que tenta condensar a informação contida nos dois anteriores. Não queremos perder totalmente esta informação então vamos fazer o seguinte, vamos guardar a diferença entre o segundo pixel e o primeiro. Assim podemos reconstruir a primeira linha a partir da segunda. A terceira linha, primeira em vermelho, contem a informação da diferença.
Podemos repetir o processo, o número de vezes que fazemos isso corresponde ao nível de decomposição da wavelet, o parâmetro n naquele código acima. Repare em uma coisa, quase todas diferenças registram valores pequenos, indicando que os pixels eram praticamente idênticos e que perdemos pouca informação ao fazer a média entre os dois. Há, entretanto, os casos destacados por um circulo verde que ressalta que naquele ponto houve uma grande perda de informação ao realizar a média. Entender isso é vital então releia e observe a imagem se tiver alguma dúvida.
Isso cobre a wavelet espacial em uma dimensão, mas e em duas? Bem temos que fazer o mesmo processo mas nas duas dimensões, assim, temos:
A imagem acima tem uma parte de uma imagem, representada pela matriz 4x4, vamos aplicar o procedimento que vimos primeiro horizontalmente, chegando nas imagens matrizes 4x2. A imagem em preto representa as médias e a em vermelho as diferenças. Agora vamos realizar o procedimento verticalmente sobre essas imagens resultastes da operação horizontal, média e diferenças da imagem preta e média e diferenças da imagem vermelha, gerando 4 imagens ao total, todas 2x2. A primeira sofreu um processo de médias horizontais e verticais, representando uma suavização, redução de detalhes em relação à imagem original. Esta imagem é a apresentada como a imagem superior esquerda na figura resultante do código, mostrando a gatinha acima. A segunda matriz 2x2 passou por um processo de médias verticais e diferenças horizontais, portanto ela contem informação dos detalhes horizontais da imagem, que foram perdidos na suavização. Já a terceira matriz 2x2 passou por um processo de diferenças verticais e médias horizontais, armazenando os detalhes verticais da imagem original. Por fim a ultima matriz passou por diferenças horizontais e verticais, armazenando informações de detalhes inclinados.
Com toda essa informação agora, volte à imagem da gatinha acima e analise como as outras três figuras estranhas armazenam majoritariamente detalhes em algum sentido como falado agora. Por que quase toda imagem é cinza? Isso ocorre porque essas imagens passaram por algum processo de diferenças então seus pixels tem valores não de 0 a 255 mas de -255 a 255, sendo o zero o cinza. Veja então que grande parte das imagens de detalhes são praticamente zero, quase tudo na imagem é cinza. Esse é o pulo do gato para entender melhor grande parte das aplicações de wavelets em imagens, vamos falar mais sobre elas.
Aplicações de wavelets espaciais em processamento de imagens
Compressão de imagens:
Uma das principais aplicações, tanto da tansformada de Fourier quanto das Wavelets, é a compressão de sinais e imagens, descantando-se a segunda. A relevância da compressão de imagens se dá em diversos contextos, quase todas imagens disponíveis para nosso acesso são comprimidas por fatores grandes, para serem acessíveis pela internet, não ocuparem espaços proibitivos nas unidades de armazenamento, entre outros fatos. Por exemplo na compressão antiga JPEG, que utilizava a FFT para compressão, o arquivo armazena uma série de módulos e fases de senos e cossenos que serão inversamente transformados quando houver a necessidade de exibir a imagem da forma convensional que estamos acostumados. Neste processo o Fast da FFT se torna muito importante, para não tornar proibitivo a conversão e exibição das imagens.
Como visto na explicação acima, grande parte das imagens é referente apenas à pequenas variações entre os seus píxels, a parte realmente interessante das imagens, notoriamente as bordas, ou features, não aparecem com tanta frequência na imagem, consequentemente podemos filtrar essa grande parte de informação “pouco relevante”, mantendo ainda a grande parte das features na imagem e ao mesmo tempo reduzindo expressivamente seus tamanhos, veja a aplicação em código abaixo:
No código acima transformamos a imagem, aplicamos uma máscara para considerar apenas as diferenças mais importantes, com valores maiores, e reconstruirmos a imagem, o resultado é o seguinte:
Grande parte da imagem é composta por informações pouco relevantes, então a perda de qualidade só se torna visível para altos níveis de compressão.
Algo importante de ser notado neste tipo de compressão é que elementos de alta frequência, texturas, grama, pelo, qualquer feature que oscile muito, são mais difíceis de serem comprimidas consequentemente apresentam maior dificuldade de aplicação dos métodos de compressão. Outro fator de alta importância para a eficiência da compressão de arquivos é a resolução inicial da imagem, quanto menor a imagem mais complicado é de ser comprimida. Para entender a questão das features de alta frequência, veja a imagem abaixo, note que ambas imagens utilizadas tem o mesmo tamanho, justamente para que isto não seja um fator de influência no resultado:
Essa grande dificuldade de compressão de features de alta frequência, como pelos de animais ou grama e vegetação, é um dos motivos da Pixar, em 1997, quando lançaram sua primeira animação, Toy Story, terem feito a pele dos brinquedos todos de plástico, para evitar justamente altas frequências, que tornariam proibitivas as compressões para o cinema. Entretanto em 2004 eles lançaram o Monstros S.A que trazia em tela o Sullivan, ostentando seus pelos, e desde então esse tipo de modelagem não seria mais um problema para a Pixar e outras animadoras. Entre Toy Story e Monstros S.A o que ocorreu? O desenvolvimento das tecnicas de compressão utilizando wavelets. Claro que eu não sei exatamente o que a Pixar usa, é uma empresa fechada, mas é no mínimo curioso. Neste mesmo período a compressão dos formatos JPEG passou a ser atualizada para compressão via wavelets e não Fourier. Para ter uma ideia de como era proibitivo, aqui está a compressão do Sullivan com Fourier:
Fourier tem uma perda grande de informação por não conseguir lidar bem com as features de alta frequência.
Filtragem de ruído
Outra aplicação bastante comum tanto da transformada wavelet como de Fourier é a filtragem de ruídos, tanto em sinais 1D quanto em imagens. Veja o exemplo abaixo:
Assim enceramos nosso texto sobre Transformadas Wavelet, espero que tenha gostado e que este texto seja útil para a compreensão da mesma. Obrigado por ter lido até aqui! Contamos com sua presença no próximo Turing Talks!
Lembre-se de nos acompanhar em nossas redes sociais! No Facebook, no Linkedin, Instagram, nossas postagens anteriores no Medium e em nosso servidor no Discord!
