Compreendendo a Transformada de Fourier
04/12/2012
Esta é a tradução para: Understanding the Fourier transform
Sim, eu sei que depois de ler o título do post 99% dos leitores em potencial só manteve a rolagem. Então, para os poucos de vocês que clicaram sobre ele, bem-vindo! Não se preocupe, isso não vai demorar muito.
Há muito tempo atrás eu estava curioso como detectar a força dos graves e agudos na música, a fim de sincronizar alguns efeitos gráficos. Eu não tinha idéia de como fazer tal coisa, então eu tentei descobrir, mas não fui muito longe. Eventualmente, eu aprendi que eu precisava de algo chamado detransformada de Fourier, então eu fiz uma viagem para biblioteca e mergulhei em cima (que é o que tinha pra fazer naqueles dias).
O que eu encontrei foi a Transformada Discreta de Fourier (TDF), que se parece com isso:
Esta fórmula, como todos podem ver, não faz sentido. Eu decidi que Fourier deve ter falado para extraterrestres, porque com todo tempo e papel do mundo eu não teria sido capaz de chegar a isso.
Eventualmente eu era capaz de visualizar como ela funciona, o que foi um pouco como uma lâmpada para mim. É sobre isso que eu quero escrever hoje: uma maneira intuitiva de imaginar a transformada de Fourier. Isso pode ser óbvio para você, mas não foi para mim, por isso, se você trabalha com áudio ou rendering espero que você ache algo útil aqui.
Aviso: minhas habilidades matemáticas são improvisos, na melhor das hipóteses, e isso tem a intenção de ser apenas um artigo informal, por isso não espere um tratamento rigoroso. No entanto vou fazer meu melhor para não enganar de cara, e eu tenho certeza que as pessoas me corrigirão se eu fizer alguma coisa errada.
Sendo profundamente rápido - o que é que a transformada de Fourier faz? Ela traduz entre duas formas diferentes de representar um sinal:
- A representação do domínio do tempo (uma série de amostras uniformemente espaçadas ao longo do tempo)
- A representação do domínio de frequência (a força e fase das ondas, as frequências diferentes que podem ser utilizadas para reconstruir o sinal)
A imagem da esquerda mostra três ciclos de uma onda senoidal, e a imagem da direita mostra a transformada de Fourier das amostras. As barras mostram a saída de energia em três ciclos (e confusamente suficiente, 3 ciclos negativos... mais sobre isso abaixo).
As entradas e saídas são na verdade números complexos, de modo a alimentar um sinal real (como algumas músicas) para a transformada de Fourier, nós apenas definiremos todos os componentes imaginários à zero. E para verificar a intensidade da informação de freqüência, basta olhar para a magnitude das saídas, e ignorar a fase. Mas vamos esquecer isso por enquanto.
O que estamos tentando fazer? Temos um sinal amostrado, e queremos extrair informações de frequência à partir dele. A transformada de Fourier trabalha em um sinal periódico, ou looping. Isso parece ser um problema, já que na verdade não tem nenhum sinal como esse. Na prática, você pega apenas uma pequena fatia de um longo sinal, tira ambas as extremidades para zero, de modo que elas possam ser unidas (que é um tópico inteiro sobre) e finge que é um loop.
Vamos deixar as coisas simples e dizer que o nosso ciclo se repete uma vez por segundo.
Imagine-o como um cordão, deslizando para cima e para baixo ao longo de uma haste fina, rastreando o sinal. Então, como esta pérola está subindo e descendo olha o que acontece se girar a haste a uma taxa de, digamos, dez rotações por segundo:
Ficamos com um rabisco, como era de esperar. E é mais ou menos centrado na origem.
Agora, vamos supor que nós sabemos que há um pouco de energia no sinal em 3Hz, e queremos medir. O que quer dizer é que acima de tudo está fazendo com que o sinal oscile ao redor, nós adicionamos uma onda que oscila três vezes por segundo. Tem um ponto alto a cada 1/3 de segundo, e correspondente aos pontos baixos intermediários, igualmente espaçados entre 1/3 parte do segundo. Você provavelmente pode ver agora como podemos ser capazes de detectá-lo ... Vamos tentar girar o nosso sinal a uma taxa de correspondente de 3 rotações por segundo.
Uma vez que o sinal complete uma rotação a cada 1/3 de segundo, todos os pontos elevados na nossa onda de 3Hz traçam na mesma parte da rotação, e isto puxa tudo para rabiscar fora do centro. Como podemos quantificar isso? A maneira mais fácil seria marcar um monte de pontos e gira-los, mediando-os para encontrar o seu ponto médio:
Faz sentido que a distância deste ponto médio a partir da origem seja proporcional à intensidade do sinal, porque como os pontos altos no nosso sinal ficam mais altos eles vão mover o rabisco mais longe. Mas e se o sinal não contiver energia em 3Hz? Vamos remover a onda 3Hz e veja:
Agora não existe nada para puxar o rabisco fora do centro, e de todas as outras oscilações tendem a equilibrar-se (aproximadamente) mutuamente.
Isto parece uma maneira promissora para se detectar a energia a uma dada frequência. Hora de traduzi-la para matemática! Para um sinal de looping de N amostras:
(Aumentando e com poder da imaginação produz-se uma rotação em torno de um círculo unitário no plano complexo, de acordo com a fórmula de Euler. Como? Mágica, tanto quanto eu posso dizer. Mas, aparentemente verdade).
Portanto, esta equação é um pouco diferente do que começou. Eu adicionei um fator de normalização de 1/N, e mudei o sinal do expoente. Eu também reorganizei os termos de uma forma um pouco mais clara. Esta forma é normalmente chamada de TDF inversa, que é confusa, mas aparentemente a diferença entre a TDF e TDFI é uma questão de convenção, e pode depender da aplicação. Então, vamos chamar isso de perto o suficiente.
De qualquer forma, uma vez que você possa "ver" o que está acontecendo em sua cabeça, um monte das peculiaridades do trabalho com TDF torna-se muito menos misterioso. Se você já teve que trabalhar antes com saídas TDF você pode ter se perguntado:
- Por que o primeiro elemento no resultado (k = 0) contém DC offset (sinal contínuo de baixa freq.)? Porque nesse caso nossas amostras não giram completamente, então tudo o que estamos fazendo é a média entre elas.
- Por que o DC offset não afeta a informação da frequência? Como adicionar um valor constante para todas as amostras só faz o rabisco ficar maior, não afeta o ponto médio.
- Por que a segunda metade da matriz de saída contém uma imagem de espelho do primeiro semestre? É apenas o nosso velho amigo atalho. Ao calcular o último elemento (k = N-1), que está girando por (N-1)/N em cada etapa, o que é quase toda a volta. Isto é o mesmo que pequenos passos (1/N) na direção errada. É por isso que o resultado em (k = N-1) tem a mesma magnitude (k = 1). É equivalente ao processar uma frequência negativa de (k = -1).
- Por que uma onda senoidal com amplitude 1,0 sai da TDF como 0,5? Quando giramos a onda senoidal temos um círculo de diâmetro 1,0, mas é o ponto médio, é apenas metade da distância a partir da origem.
- Onde está a outra metade da energia, então? Ela está se escondendo na parte negativa da freqüência!
Esperemos que tenha sido mais útil do que confuso.
