Transformada de Fourier em Visão Computacional
A mais importante transformada do século XIX
Texto Escrito por: Rodrigo Fill Rangel. Agradecimentos a Rodrigo Estevam pela ajuda de pesquisa.
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 conhece um pouco do tema você deve estar pensando: “como transformada de Fourier pode se relacionar com visão computacional?”. Bem é para isso que este texto vai servir, mostrar as mais diversas aplicações desta que é uma das mais importantes transformações matemáticas de todos os tempos. Mas este texto é também uma introdução necessária para o entendimento do tema de um próximo texto, que abordará as transformadas Wavelets. Então sem mais delongas, vamos ao texto.
Transformada de Fourier
A transformada de Fourier é um importante recurso de análise de sinais que consiste na decomposição de um sinal temporal em seus vários componentes espectrais de frequência, facilitando, e muito, por exemplo a análise de sinais ruidosos, ou muito confusos. O sinal pode ser analógico, como um pulso elétrico, ou digital, como uma sequência de dados acerca de uma observação, como preços de fechamento de um ativo na bolsa de valores. Para tal a transformada tenta decompor um sinal em uma somatória de senoides, estas senoides podem ser de qualquer frequência, isto o algoritmo irá buscar, cada senoide sendo representativa de apenas uma frequência. Estas senoides são chamadas de harmônicas. Observe a fórmula abaixo:
Entretanto tentar entender o funcionamento apenas pela matemática do problema pode ser consideravelmente complexo, portanto vamos partir para uma exploração mais simples, utilizando representações visuais. O que tentamos fazer é representar um sinal qualquer como a soma de senos e cossenos dentro de uma transformada de Fourier. Esses senos e cossenos então são representados por sua frequência, em um novo domínio, chamado domínio da frequência, assim passamos de um sinal temporal para a somatória de senos e cossenos que representa aquele sinal no tempo, e representamos esses senos e cossenos por suas frequências, como mostra a imagem abaixo:
Na figura temos um sinal em azul escuro que pode ser representados pelas duas senoides no meio da imagem, uma de frequência menor mas de amplitude maior, e outra de frequência maior e amplitude menor, que são representadas em um novo plano agora em função de suas frequências e potências, que é ligada à amplitude do sinal. Assim funciona a transformada de Fourier, levando do domínio temporal para o domínio espectral (frequência).
Mas aí você, caro leitor, me pergunta para que isso serve? Qual utilidade de tamanha complexidade de transformação? Bem, temos várias aplicações da transformada de Fourier em diversas áreas do conhecimento, é fato que esta é uma transformação tão importante que o texto poderia ter uma hora de leitura sem que eu conseguisse cobrir todas as aplicações. Por isso vamos nos ater ao mais simples, mas que já é suficiente para que seja compreendido a grande relevância do tema.
Para tal então vou fazer uma abordagem prática, utilizando o python. Todos códigos foram adaptados do material dos professores Steven. L. Brunton & J. Nathan Kutz, que é uma excelente referência para o tema. Primeiramente vamos considerar o seguinte código:
O output deste código é:
Acima nós simplesmente fabricamos um dataset, com um sinal limpo em preto, proveniente da soma de duas senoides, e juntamente a estas senoides somamos um sinal ruidoso, de grande amplitude. Vamos fazer um exercício de faz de conta, fingindo que o sinal preto não existe, não sabemos que ele está presente no sinal vermelho, e apenas temos acesso ao sinal ruidoso, mas sabemos que o sinal vermelho possuí diversos artefatos que estão complicando nossa análise. Assim vamos buscar encontrar as frequências significativas e filtrar as outras. Para tal vamos utilizar o fast fourier transform, que é uma implementação da transformada de Fourier, mas com algumas modificações que não vem ao caso neste texto. Temos:
No domínio da frequência fica bastante evidente a influência de potência dominante por duas frequências no sinal, todo o resto podendo ser considerado como ruído. Portanto vamos agora filtrar estes sinais, de forma bastante simples, basta escolher um valor de threshold para a potência, se o valor for inferior ao limite, aquele espectro é zerado, caso contrário não. Pela análise do gráfico basta escolher algo como 200:
Por fim podemos agora realizar a transformada inversa rápida de Fourier para conseguirmos o sinal original:
Desta forma podemos compreender de forma prática apenas um pouco da importância desta ferramenta para análise de séries temporais, mas a transformada de Fourier também pode ser aplicada a imagens. É possível definir a transformada de Fourier em 2 dimensões , no próprio numpy a impĺementação é dada por np.fft.fft2
. Vale dizer que não estaríamos realizando nada muito novo, apenas aplicando a transformação em todas colunas, depois em todas linhas, ou vice e versa (não importa em nada qual direção você escolher transformar primeiro). Vejamos o código a seguir:
A imagem da direita acima nada mais é que uma representação dos diversos coeficientes da transformada rápida de Fourier, ou seja, em cada ponto daquela imagem temos a informação da magnitude de uma multiplicação de senos e cossenos, bem como suas fases, e o que estamos tentando fazer nada mais é que para cada pixel na imagem original encontrar uma soma de senos e cossenos de diferentes frequências que resultem no mesmo padrão observado pela imagem original, criado por suas intensidades. Agora eu sei que isso não faz o menor sentido simplesmente falando assim para vocês, até porque como a imagem da direita poderia ser uma representação da imagem na esquerda se elas não tem absolutamente nenhuma ligação visual, mas eu devo lembrar que a imagem à direita trata apenas de coeficientes, não de valores de pixels em sí, e para ficar mais claro eu quero mostrar a seguinte representação da imagem à esquerda:
Perceba como é possível representar uma imagem como se ela fosse na verdade uma sequência de valores de uma serie temporal, então os vários coeficientes da transformada rápida de Fourier 2d está tentando somar senos e cossenos em cada ponto da imagem para recriar o padrão descrito pelo plot de superfície acima. Na imagem à direita temos o mesmo plot da esquerda mas em perspectiva superior, mostrando a foto da gatinha. Mas este processo por si só não é extremamente relevante, é importante entender que a partir disto podemos realizar diversas transformações na nossa imagem, sendo as mais comuns a compressão e a filtragem de ruído, mas ambas eu vou descrever somente quando passarmos por wavelets, uma vez que já me estendi demais neste texto :).
Entretanto, após falar tanto, a transformada de Fourier não é perfeita, ela apresenta um grande problema que é apenas apresentar informações sobre as frequências do sinal, mas não quando esta frequência aparece no tempo. Uma forma de pensar essas transformações é em termos de resolução espectral, mas isso é tão importante que vou dedicar uma subseção apenas para isso.
Resolução Temporal e Espectral
A resolução de uma transformada mostra o quão bem representado está o sinal em termos de algum eixo que buscamos representar. No eixo do tempo, em que nossa função estava originalmente, temos uma grande resolução temporal, mas a resolução de frequências é muito baixa, a informação de frequências naquela representação não é relevante. Ao fazer a transformação de Fourier passamos a ter uma alta resolução de frequência do sinal, mas a resolução temporal fica excessivamente baixa. Veja a imagem a seguir:
Esta imagem denota como o tempo na base temporal está bem caracterizado em várias divisões, qualquer evento temporal pode ser bem posicionado em termos do tempo. Já em relação à frequência a base temporal tem baixa resolução, ou seja, não temos nenhuma informação sobre a frequência nesta base. O oposto ocorre no domínio da frequência, onde a resolução espectral é alta, assim sabemos quais faixas de frequência aparecem no sinal em análise, mas não temos informações sobre o tempo em que tais frequências ocorrem, visto que a resolução temporal é nula.
Este configura um problema grave da transformada de Fourier em aplicações que necessitam tanto do conhecimento das frequências como do tempo em que cada frequência ocorre. Para tal surgiram modificações na transformada de Fourier, vou citar uma neste texto, mas a outra será explorada muito a fundo em outro texto que deve sair nas próximas semanas.
Transformada de Fourier de tempo curto (STFT)
A STFT nada mais é que um método de reintroduzir o tempo na análise, tentando romper com a barreira citada no final da seção anterior. Mas isso não é nada fácil, considerando que o a única forma de fazer isso implica em um trade-off entre resolução temporal e de frequências. Para ficar mais claro a STFT funciona com janelamento, considerando que o sinal analisado é composto, em cada instante, por algumas frequências dominantes, então em cada instante de tempo de janelamento, aplica-se a transformada de Fourier no sinal da janela, o que estiver fora da janela é automaticamente zerado, assim temos:
A imagem acima representa bem o resultado de uma STFT, trata-se de um plot 3D com um eixo representando a mudança de frequências, outro eixo representando as mudanças temporais e o terceiro tem a magnitude ou potência dos sinais. O problema deste método é justamente seu trade-off de resoluções, neste caso quanto maior for o janelamento melhor a resolução de frequências, visto que mais mais frequências estão na janela, porém menor é a resolução temporal, ao passo que a quanto menor o janelamento melhor seria a resolução temporal, porém pior é a resolução espectral. Neste algoritmo é normal usar o janelamento igualmente dividido, como na figura abaixo:
Perceba então que nem a resolução temporal nem a espectral são altas, mas ambas existem, nenhuma é nula, permitindo a análise do sinal tanto no tempo quanto na frequência. Uma aplicação interessante deste recurso pode ser visto no próprio youtube, esse método é comumente utilizado para fazer análises de músicas, identificando quais notas são tocadas em quais momentos, veja este vídeo:
Assim enceramos nosso texto sobre Transformada de Fourier, 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! Lembrando que em breve teremos outro texto sobre a transformada Wavelet.
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!