Um guia interativo para a Transformada de Fourier

Tradução de An Interactive Guide To The Fourier Transform – BetterExplained

A Transformada de Fourier é um dos mais profundos insights de todos os tempos. Infelizmente, o seu significado está enterrado nesta densa equação:

$\displaystyle X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi kn / N}$

$\displaystyle x_n = \dfrac{1}{N} \sum_{n=0}^{N-1} X_k \cdot e^{i2\pi kn / N}$

Caramba! Em vez de metermos a cara nos símbolos, vamos primeiro ter contato com a sua ideia chave. Aqui vai uma metáfora em português claro:

• O que a Transformada de Fourier faz? Dado um shake de frutas, ela encontra a sua receita.
• Como? Passando o shake em filtros para extrair cada ingrediente.
• Por quê? As receitas são mais fáceis de analisar, comparar e modificar do que o próprio shake.
• Como nós podemos obter o shake de volta? Misturando os ingredientes.

E aqui está a versão em “português matemático” da explicação acima:

A Transformada de Fourier toma um padrão variante no tempo, mede todos os ciclos possíveis que o compõe e retorna a receita do ciclo agregado (a intensidade, o ponto inicial e a velocidade de rotação para todos os ciclos encontrados).

Então já podemos resolver algumas equações? Ainda não! Vamos botar a mão na massa e experimentar como qualquer padrão pode ser construído com ciclos [círculos girantes], utilizando algumas simulações.

Se tudo correr bem, teremos um momento Aha!, e intuitivamente perceberemos porque a Transformada de Fourier funciona. Vamos deixar os detalhes da análise matemática para depois.

Não vamos fazer uma marcha-forçada através das equações, mas sim um passeio casual que eu gostaria de ter tido quando precisei aprender essa transformada.

Em frente!

Do shake para a receita

Uma transformação matemática é uma mudança de perspectiva. Mudamos nossa noção de quantidade de “itens individuais” (linhas na areia, contagem com “palitinhos”) para “grupos de 10” (decimais) dependendo do que estamos contando. Pontuações num jogo? Agrupe-as. Multiplicações? Use decimais, por favor.

A Transformada de Fourier muda nossa perspectiva de consumidor para produtor, transformando “O que eu vejo?” em “Como foi feito?”

Em outras palavras: dado um shake, vamos encontrar a sua receita.

Por quê? Bem, as receitas são excelentes descrições para as bebidas. Você não daria a ninguém uma explicação detalhe por detalhe do que acabou de beber, mas simplesmente diria “eu tomei uma vitamina de laranja e banana”. Uma receita é mais fácil de categorizar, comparar e modificar do que o próprio objeto em si.

Portanto… dado um shake, como nós achamos a sua receita?

Bem, imagine que você tenha por aí alguns filtros:

• Despeje o shake pelo filtro de banana. 30 mL de banana é extraído.
• Despeje de novo pelo filtro de laranja. Saem 60 mL de laranja.
• E despeje pelo filtro de leite. 90 mL de leite.
• Despeje o resto pelo filtro de água. Mais 90 mL de água.

Podemos fazer a engenharia-reversa na receita filtrando cada ingrediente. O segredo?

• Os filtros devem ser independentes. O filtro da banana deve capturar bananas, e nada mais. Adicionar mais laranjas não deve afetar nunca a captura da banana.
• Os filtros devem ser completos. Não teremos a receita verdadeira se deixarmos de lado um filtro (“Haviam mangas também!”). Nossa coleção de filtros deve pegar até o último ingrediente.
• Os ingredientes devem ser misturáveis. Vitaminas podem ser separadas e recombinados sem problemas (Misturar um biscoito? Nem tanto. Quem quer pedacinhos?). Os ingredientes, quando separados e combinados em qualquer ordem, devem produzir o mesmo resultado.

Ver o mundo como ciclos

A Transformada de Fourier toma um ponto de vista particular: E se qualquer sinal puder ser filtrado num monte de caminhos circulares?

Uau! Esse conceito é surpreendente, mas o pobre do José Fourier teve sua ideia rejeitada a princípio. (Tem certeza, Zé? Até um padrão de “escada” pode ser criado a partir de círculos?).

E apesar de décadas de debate na comunidade matemática, é realmente esperado que os alunos internalizem essa ideia sem dificuldades. Duh. Vamos passear pela intuição.

A Transformada de Fourier encontra a receita para um sinal, como no nosso processo para o shake:

• Comece com um sinal baseado no tempo;
• Aplique filtros para medir cada “ingrediente circular” presente;
• Junte toda a receita, listando a quantidade de cada “ingrediente circular”.

Pare. Aqui é onde a maioria dos tutoriais despejam as aplicações de engenharia na sua cara. Não se apavore; pense nesses exemplos como “Uau, finalmente vamos ver o código-fonte (DNA) por trás de ideias que, até há pouco, nos eram confusas”.

• Se as vibrações de um terremoto podem ser separadas em “ingredientes” (vibrações de diferentes velocidades e intensidades), edifícios podem ser concebidos para evitar a interação com os terremotos mais fortes.
• Se as ondas de som podem ser separadas em ingredientes (frequências graves e agudas), podemos ressaltar as partes que nos interessam e esconder as outras. O ruído de sons aleatórios pode ser removido. Talvez, “ingredientes sonoros” parecidos possam ser comparados (serviços de reconhecimento de música comparam receitas e não os trechos de áudio bruto).
• Se dados computacionais podem ser representados a partir de padrões oscilatórios, provavelmente os menos importantes podem ser ignorados. Esta “compressão com pequenas perdas” pode reduzir drasticamente o tamanho de arquivos (e por essa razão arquivos JPEG e MP3 são muito menores do que arquivos brutos BMP ou WAV).
• Se o nosso sinal é uma onda de rádio, podemos usar filtros para ouvir um canal em particular. No universo dos shakes, imagine cada pessoa prestando atenção num ingrediente diferente: Adão escolheu as maçãs; Bob, as bananas; e o Carlos ficou com a couve (desculpe, camarada).

A Transformada de Fourier é útil na engenharia, claro, mas é também uma metáfora sobre como encontrar a causa-raiz por trás de um efeito observado.

Pense em círculos, não apenas em senoides

Uma das minhas grandes confusões estava na separação da definição de “senoide” e “círculo”.

• Uma “senoide” é um padrão específico de “vai-e-volta” (uma onda seno ou cosseno), e 99% das vezes isso se refere a um movimento em uma dimensão.
• Um “círculo” é um padrão circular 2D que você provavelmente já conhece. Se você gosta de falar difícil, você pode chamar um caminho circular de uma “senoide complexa”.

Chamar um caminho circular de uma “senoide complexa” é como se referir a uma palavra como “múltiplas letras”. Você deu zoom no nível errado de detalhes. As palavras servem para representar outras coisas e não as próprias letras nas quais elas (as palavras) podem ser divididas.

A Transformada de Fourier trata de caminhos circulares (não de senoides em 1 dimensão), e a Fórmula de Euler é uma maneira inteligente de gerá-los:

Temos de usar expoentes imaginários para nos mover em círculos? Não! Mas é uma forma conveniente e compacta. E, com certeza, podemos descrever nosso caminho como um movimento coordenado em duas dimensões (real e imaginária), mas não se esqueça o quadro geral: nós estamos apenas nos movendo em um círculo.

Seguindo por trajetórias circulares

Digamos que estejamos conversando ao telefone e, como de costume, eu quero que desenhemos o mesmo círculo simultaneamente. (Você prometeu!) O que eu deveria dizer?

• Quão grande é o círculo? (A amplitude, ou seja, o tamanho do raio).
• Quão rápido nós o desenhamos? (A frequência. 1 círculo/segundo é a frequência de 1 hertz (Hz) ou radianos/segundo).
• Por onde começamos? (O ângulo de fase, em que 0 graus é o eixo x).

Eu poderia dizer “raio de 2 centímetros, começando em 45 graus, 1 círculo por segundo, vai!”. Depois de meio segundo, nós devemos estar cada um apontando para: ponto de partida mais quantidade viajada = 45 + 180 = 225 graus (no círculo de 2 centímetros).

Toda trajetória circular precisa de um tamanho, velocidade e ângulo inicial (amplitude/frequência/fase). Podemos até combinar trajetórias: imagine minúsculos automóveis se movendo em círculos com velocidades diferentes.

A posição combinada de todos os círculos é o nosso sinal, assim como o sabor combinado de todos os ingredientes é o nosso shake.

Aqui está uma simulação de uma trajetória circular básica.

Clique para abrir a animação

(Baseado nesta animação, aqui está o código-fonte. É necessário um navegador de internet atualizado para visualizá-la. Clique no gráfico para pausar/prosseguir.)

A magnitude de cada ciclo é listada em ordem, iniciando em 0 Hz. Ciclos [0 1] significa:

• Força 0 para o ciclo de 0 Hz (0 Hz = um ciclo constante, preso no eixo X em zero graus).
• Força 1 para o ciclo de 1 Hz (1 ciclo completo por intervalo de tempo).

A parte desafiadora agora:

• O gráfico azul mede a parte real do ciclo. Outra confusão matemática “adorável”: o eixo real do círculo, que normalmente é horizontal, tem sua magnitude mostrada no eixo vertical do gráfico. Você pode rodar mentalmente o círculo 90 graus se quiser.
• Os pontos de tempo são espaçados a partir da frequência mais rápida. Um sinal de 1 Hz precisa de 2 pontos de tempo para marcar o seu começo e fim (um único ponto de registro não representa nenhuma frequência). O valor no tempo [1 -1] mostra a amplitude nestes intervalos igualmente espaçados.

Está comigo? [0 1] é um ciclo de 1 Hz puro.

Agora vamos adicionar um ciclo de 2 Hz na mistura. [0 1 1] significa “nada em 0 Hz, 1 Hz de força 1, 2 Hz de força 1”:

Clique para abrir a animação

Uau! Os carrinhos estão ficando selvagens: as linhas verdes são os ciclos de 1 Hz e de 2 Hz, e a linha azul é o resultado combinado. Tente alternar a caixa de seleção verde para ver o resultado claramente. O “sabor” combinado é uma oscilação que começa no máximo e desce de uma vez para o resto do intervalo.

Os pontos amarelos são quando efetivamente medimos o sinal. Com 3 ciclos definidos (0 Hz, 1 Hz, 2 Hz), cada ponto é 1/3 da trajetória do sinal. Nesse caso, ciclos [0 1 1] gera valores no tempo [2 -1 -1], quando começa no máximo (2) e desce de uma vez (-1).

Oh! Não podemos esquecer da fase, o ângulo inicial! Use magnitude:ângulo para especificar a fase. Assim [0 1:45] é um ciclo de 1 Hz que começa em 45 graus:

Clique para abrir a animação

Essa é uma versão deslocada de [0 1]. No lado do tempo nós conseguimos [.7 -.7] em vez de [1 -1] porque nosso ciclo não está exatamente alinhado com nossos intervalos de medição, que ainda estão na metade do caminho (isso poderia ser desejado!).

A Transformada de Fourier encontra as velocidades, intensidades e fases de um conjunto de ciclos que coincidem com qualquer sinal variável no tempo.

Nosso sinal torna-se uma noção abstrata que consideramos como “observações no domínio do tempo” ou “ingredientes no domínio da frequência”.

Chega de papo: Experimente! No simulador, digite qualquer tempo ou padrão de ciclo que você gostaria de ver. Se forem pontos no tempo, você conseguirá uma coleção de ciclos (combinados numa “onda”) que corresponde aos seus pontos desejados.

Mas… a onda combinada não tem valores estranhos entre os intervalos de tempo amarelos? Com certeza. Mas quem vai dizer se um sinal viaja em linhas retas, ou curvas, ou até pula para outras dimensões quando não o medimos? Ele se comporta exatamente como precisamos naqueles momentos igualmente espaçados que definimos.

Fazendo um pico no tempo

Podemos fazer um pico no tempo, como (4 0 0 0), usando ciclos? Usarei parênteses () para uma sequência de pontos no tempo, e colchetes [] para uma sequência de ciclos.

Embora o pico pareça chato para nós, “moradores do tempo” (um só ponto de medição, é isso mesmo?), pense sobre a complexidade no universo dos ciclos. Nossos ingredientes de ciclos devem começar alinhados (no valor máximo, 4) e então “explodir para fora”, cada ciclo com padrões que, somados, se cancelam no futuro. Todo ponto remanescente é zero, que é um equilíbrio complicado quando múltiplos ciclos estão correndo ao redor do círculo (nós não podemos simplesmente “desligá-los”).

Vamos passear por cada ponto no tempo:

• No tempo 0, o primeiro instante, cada ingrediente do ciclo está no máximo. Ignorando os outros pontos no tempo, (4 ? ? ?) pode ser feito a partir 4 ciclos (0 Hz 1 Hz 2 Hz 3 Hz), cada um com uma magnitude 1 e fase 0 graus (isto é, 1 + 1 + 1 + 1 = 4).
• Em cada ponto futuro (t = 1, 2, 3), a soma de todos os ciclos deve se cancelar.

Aqui está o truque: quando dois ciclos estão em lados opostos do círculo (Norte e Sul, Leste e Oeste, etc.) a posição combinada deles é zero (3 ciclos podem se cancelar se eles estiverem espalhados uniformemente a 0, 120 e 240 graus).

Imagine uma constelação de pontos se movendo ao redor de um círculo. Aqui está a posição de cada ciclo a cada instante:

Tempo 0 1 2 3

0 Hz: 0 0 0 0 1 Hz: 0 1 2 3 2 Hz: 0 2 0 2 3 Hz: 0 3 2 1

Observe como o ciclo de 3 Hz se inicia em 0, alcança a posição 3, então a posição “6” (com apenas 4 posições, 6 módulo 4 = 2), em seguida posição “9” (9 módulo 4 = 1).

Quando nossos ciclos têm duração de 4 unidades de comprimento, um ciclo que esteja se movendo meio-ciclo a frente (2 unidades) ou estará alinhado (diferença de 0, 4, 8…) ou estará no lado oposto (diferença de 2, 6, 10…).

Ok. Vamos detalhar cada ponto de tempo:

• Tempo 0: todos os ciclos no seu máximo (total de 4).
• Tempo 1: 1 Hz e 3 Hz cancelam (posição 1 e 3 são opostas), 0 Hz e 2 Hz cancelam também. O resulto líquido é 0.
• Tempo 2: 0 Hz e 2 Hz alinhadas na posição 0, enquanto 1 Hz e 3 Hz estão alinhadas na posição 2 (o lado oposto). O total ainda é 0.
• Tempo 3: 0 Hz e 2 Hz cancelam. 1 Hz e 3 Hz cancelam.
• Tempo 4 (repete t=0): todos os ciclos alinhados.

O truque é que as velocidades individuais se cancelam (0 Hz vs. 2 Hz, 1 Hz vs. 3 Hz), assim como os pares alinhados (0 Hz + 2 Hz vs. 1 Hz + 3 Hz).

Quando cada ciclo tem magnitude iguais e fase 0 graus, começamos alinhados e cancelamos depois. (Eu não tenho uma boa prova ainda – alguma proposta? –, mas você pode ver isso contra própria. Experimente [1 1], [1 1 1], [1 1 1 1] e  observe os sinais gerados: (2 0), (3 0 0), (4 0 0 0).

Na minha cabeça, considero esses sinais “picos no tempo”: eles têm uma explosão de atividade num único instante, e são zero nos outros pontos de medição (o nome chique deles é uma função delta).

Aqui está como eu vejo o alinhamento inicial, seguido por um cancelamento líquido:

Deslocando o pico no tempo

Nem tudo acontece no t=0. Podemos mudar nosso pico para (0 4 0 0)?

Parece que os ingredientes do ciclo são parecidos com (4 0 0 0), mas os ciclos devem ser alinhados em t=1 (um segundo depois). Aqui é onde a fase entra.

Imagine uma corrida com 4 corredores. Em uma corrida normal, todo mundo está alinhado na linha inicial, o (4 0 0 0) padrão de tempo. Chato.

E se quisermos que todos terminem ao mesmo tempo? Fácil. Apenas mova as pessoas para frente ou para trás pela distância apropriada. Talvez a vovozinha possa começar a 5 metros da linha de chegada, Usain Bolt a 100 metros antes, e eles possam cruzar a fita segurando as mãos.

Mudanças de fase, o ângulo inicial, são atrasos no universo cíclico. É assim que ajustamos a posição inicial para atrasar 1 segundo em cada ciclo:

• Um ciclo de 0 Hz não se move, então já está alinhado.
• Um ciclo de 1 Hz faz uma rotação completa em 4 segundos, então 1 segundo de atraso é um quarto de volta. Uma mudança de fase 90 graus para trás (-90) e ele vai para fase=0, o valor máximo, em t=1.
• Um ciclo de 2 Hz é duas vezes mais rápido, precisando assim de duas vezes o ângulo para cobrir (-180 ou 180 de mudança de fase – é meia volta no círculo, por qualquer lado).
• Um ciclo de 3 Hz é 3 vezes mais rápido, precisando de 3 vezes a distância percorrida (-270 ou +90 de deslocamento de fase).

Se os pontos no tempo (4 0 0 0) são feitos de ciclos [1 1 1 1], então os pontos no tempo (0 4 0 0) são feitos de [1 1:-90 1:180 1:90]. (Nota: estou usando “1 Hz”, mas significa “1 ciclo sobre o período de tempo total”).

Uau – estamos resolvendo os ciclos de cabeça!

A visualização da interferência é parecida, exceto pelo alinhamento em t=1.

Teste a sua intuição: você pode fazer (0 0 4 0), isto é, um atraso de dois segundos? 0 Hz não tem fase. 1 Hz tem 180 graus, 2 Hz tem 360 (o mesmo que 0), e 3 Hz tem 540 (que é igual a 180), por isso é [1 1:180 1 1:180].

Descobrindo a transformada completa

O grande insight: nosso sinal é apenas um monte de picos no tempo! Se misturarmos as receitas para cada pico de tempo, conseguiremos a receita para o sinal completo.

A Transformada de Fourier constrói a receita frequência-por-frequência:

• Separe o sinal completo (a b c d) em “picos de tempo”: (a 0 0 0) (0 b 0 0) (0 0 c 0) (0 0 0 d);
• Para qualquer frequência (como 2 Hz), a receita experimental é “a/4 + b/4 + c/4 + d/4” (a intensidade de cada pico é dividida entre todas as frequências);
• Espere! Precisamos compensar cada pico com um atraso na fase (o ângulo para “1 segundo de atraso” depende da frequência);
• A verdadeira receita para uma frequência = a/4 (sem compensar) + b/4 (1 segundo compensado) + c/4 (2 segundos compensados) + d/4 (3 segundos compensados).

Podemos então fazer um loop através de todas as frequências para obter a transformada completa.

Aqui está a conversão do “português matemático” para matemática completa:

Algumas observações:

• $N$ = número de amostras de tempo que temos.
• $n$ = amostra atual que estamos considerando (0..N-1).
• $x_n$ = valor do sinal no tempo $n$.
• $k$ = frequência atual que estamos considerando (0 Hertz até N-1 Hertz).
• $X_k$ = quantidade da frequência k no sinal (amplitude e fase, um número complexo).
• O fator $1/N$ é geralmente movido para a transformada reversa (indo das frequências de volta para o tempo). Isso é permitido, embora eu prefira $1/N$ na transformada direta uma vez que isso dá o tamanho real para os picos de tempo. Você pode apelar e até usar $1/\sqrt{N}$ em ambas as transformadas (indo para frente e para atrás ainda com o fator $1/N$).
• $n/N$ é o percentual de tempo que passou. $2\pi k$ é nossa velocidade em radianos/segundos. $e^{-ix}$ é nosso movimento para trás num caminho circular. A combinação é o quão longe temos nos movido, para esta velocidade e tempo.
• As equações brutas para a Transformada de Fourier apenas dizem “adicione números complexos”. Muitas linguagens de programação não podem manusear números complexos diretamente, então você converte tudo para coordenadas retangulares e os adiciona.

Avante

Esse foi meu artigo mais difícil até agora. A Transformada de Fourier tem vários sabores (discreta/contínua/finita/infinita), abrange uma profunda matemática (função delta de Dirac) e é fácil se perder nos detalhes. Eu tenho esbarrado constantemente nos limites do meu conhecimento.

Mas há sempre uma analogia simples lá fora. Eu me recuso a pensar de outra forma.

Seja um shake ou Usail Bolt e a vovozinha cruzando a linha de chegada, pegue uma simples compreensão e refine-a. A analogia é falha, e isto é normal: é uma jangada para ser usada e deixada para trás uma vez que atravessamos o rio.

Eu percebi quão fraco é meu próprio entendimento quando não consegui resolver a transformada (1 0 0 1) na minha cabeça. Para mim, foi como dizer que eu sabia somar, mas, incrivelmente, não tinha certeza do que “1+1+1+1” seria. Por que não? Não devemos ter uma intuição para a mais simples das operações?

Esse desconforto me levou a rodar a internet para construir minha intuição. Além das referências no artigo, eu gostaria de agradecer:

• Scott Young, pelo pontapé inicial para essa postagem;
• Shaheen Gandhi, Roger Cheng, and Brit Cruise por discutirem ideias e refinarem a analogia;
• Steve Lehar pelos grandes exemplos da Tranformada de Forrier em imagens.
• Charan Langton pelo passo-a-passo detalhado dela;
• Julius Smith pelo fantástico passo-a-passo da Transformada Discreta de Fourier (o que cobrimos hoje);
• Bret Victor pela sua técnica em aprendizagem com visualização.

A meta de hoje foi experimentar a Transformada de Fourier. Guardaremos a analise avançada para um próximo momento.

Happy Math.

Apêndice: projetando sobre ciclos

Stuart Riffle tem uma grande interpretação da Transformada de Fourier:

Imagine girando seu sinal em uma centrífuga e checar a sua tendência. Eu tenho uma correção: devemos girar para trás (o expoente na equação acima deveria ser $e^{-i 2\pi}$ …). Você já sabe o porquê: precisamos de um atraso de fase de modo que os picos se desloquem para o futuro.

Apêndice: uma outra visualização impressionante

Lucas Vieira, autor do excelente Animaçãos da Wikipedia, foi inspirado a fazer essa animação interativa:

Fourier de Brinquedo – Clique para abrir

(Lista detalhada de opções de controle)

A Transformada de Fourier é sobre ciclos somados aos ciclos somados aos ciclos. Tente fazer um “pico de tempo” configurando uma intensidade de 1 para todo componente (aperte Enter depois de inserir cada número). Fato engraçado: com um número suficiente de termos, você pode desenhar qualquer forma, até o Homer Simpson.

Apêndice: usando o código

Todo o código e os exemplos são código aberto (MIT licensed, faça o que você preferir).

• Exemplo Interativo (ver a fonte);
• Github gist;
• Discussão no Reddit em detalhes sobre a computação; sou o pb_zeppelin.

Tradução: Paulo Mercês.

Revisão: Frederico B. Teixeira.