Transformation de Fourier

Après avoir regardé les magnifiques animations de 3blues1brown, je me suis dit que ce serait un exercice sympa à faire pour mieux appréhender cet outil génial que je ne connaissais pas. Pas d’approche théorique ici, on va se contenter de « tourner les boutons » à l’instar du singe savant et regarder le résultat.

Prenons un exemple simple, un dessin censé représenter un éléphant. La liste des coordonnées de l’ensemble des points constitue nos données initiales. Pour calculer la liste des coefficients de la série de Fourier correspondante, on peut utiliser numpy en Python. Ci-dessous n est la liste des tuples correspondant aux coordonnées des points de la courbe, exemple : n = [ (0,0), (10,10), …, (42,1337)]

import numpy as np
a_m = np.fft.fft(np.array( [ np.complex( i[0], i[1] ) for i in n] ))

C’est tout ? Oui c’est presque fini. Pour avoir les coordonnées du point à dessiner, il suffit de faire la somme des coefficients multipliés par le nombre complexe associé à sa fréquence :

Petit piège ici, la liste a[m] renvoyée par la fonction fft() précédemment utilisée, liste d’abord tous les coefficients positifs dans l’ordre croissant, puis tous les coefficients négatifs : a[ 0, 1, 2, 3, -3, -2, -1 ]. Si on se trompe d’ordre, on s’en rendra vite compte puisque cela dessinera n’importe quoi.

La fonction r_fft() ci-dessous fait le calcul :

def euler_to_complex( rho, theta ) :
    return np.complex(rho * math.cos(theta), rho * math.sin(theta) )
    
def r_fft( f, t, limit_n ):
    len_f = len(f)
    r = f[0]
    l = [r]
    if limit_n == 0:
        return r,  l
    if limit_n is None or limit_n > len_f:
        limit_n = len_f
    k = 1
    while len(l) <= limit_n:
        r += f[k] * euler_to_complex( 1, 2*PI*k*t )
        l.append(r)
        if len(l) > limit_n:
            break
        r += f[-k] * euler_to_complex( 1, -k*2*PI*t )
        l.append(r)
        k += 1
    return r, l 

C’est quoi ces paramètres f, t et limit_n ? Et bien f correspond à la liste a_m calculée précédemment, t permet de « faire tourner » les cercles, ainsi en faisant varier t de 0 à 1, on fera un tour complet et notre courbe sera entièrement dessinée. limit_n est le nombre de cercles que l’on souhaite utiliser.

Voilà, on a tout ce qu’il faut pour notre animation :

On peut aussi faire varier le nombre de cercles utilisés :

Que se passe-t-il maintenant si nous modifions uniquement un seul coefficient ? Modifions son argument par exemple et faisons lui faire un tour complet. Pour le premier (k=0) c’est trivial : on déplace simplement le point de départ de notre dessin, pour les suivants c’est beaucoup moins intuitif :

Et si nous faisons tourner les deux coefficient k et -k en même temps ?

En fait, pour effectuer une rotation de la figure il faut faire « tourner » tous les coefficients en même temps.

Un autre paramètre sur lequel on peut jouer est le module, faisons-le varier de 0 à 200% pour différents coefficients k:

Après avoir fait varier les coefficients pour voir l’impact sur l’image finale, on peut se demander quelle est l’influence du choix du point de départ sur le calcul des coefficients et donc sur l’image finale. En effet l’image de départ est constituée d’une liste de points dont l’ordre est important certes, mais on peut partir de n’importe quel point pour faire la boucle : commencer par la trompe ou la queue ne change rien à nos données de départ.

On constate ici que le module des coefficients ne change pas mais leur argument change. Mais alors, quelle est l’invariant qui caractérise notre éléphant ? On voit bien que tous les vecteurs « tournent », et si on regarde attentivement, ils « tournent » d’une certaine manière les uns par rapport aux autres : en additionnant les arguments des coefficients k et -k, le résultat lui reste constant.

Voilà, on comprend mieux maintenant les paramètres à prendre en compte pour caractériser le contour de notre éléphant.

<