Signaux: soudain, votre silhouette est transformée...

... Une Promenade Fouriériste! (Partie 4.2)


Résumé des épisodes précédents: la transformée de Fourier (qu'on peut considérer comme le jeu de coefficients de la série, dans le cas d'une fonction périodique), peut se calculer rapidement, dans sa variante discrétisée FFT, ce qui est bien utile, avons nous dit... mais il serait temps de savoir à quoi!

cas d'une fonction périodique (série) cas d'une image cas d'une erreur...
Dans tous les cas, l'original est à gauche, sa FFT à droite; sauf dans le dernier, où l'original semble perdu...

Les exposés (plus ou moins) techniques pouvant être trouvés en abondance sur la toile, nous nous limitons ici à des principes généraux et des présentations schématiques: le but est d'embrasser d'un coup d'œil ce que Stéphane Mallat appelle respectueusement le Royaume de Fourier.

Parole, parole et... en avant la Zizique!

< à venir>

Qui n'a jamais fait une photo au format JPEG?

Pas grand monde, à l'évidence, depuis que la photo s'est faite numérique. Et encore moins depuis que l'appareil photo a eu l'idée de se déguiser en téléphone... Les images stockées ont des noms du type IMG001.jpg, et cette extension ".jpg" désigne le format de fichier le plus courant. Il y en a certes d'autres, à commencer par le format brut, dans lequel une image en noir et blanc (pour simplifier) est un tableau de valeurs de gris, codées entre 0 et 255, une par pixel de l'image. JPEG permet de compresser spectaculairement ce volume de donnés., grâce à la tranformation de Fourier et au prix d'une légère dégradation, qu'on peut rendre imperceptible, 

1. Avant de transformer l''image, on la découpe en blocs de 8x8 pixels. Une image 512x512 (c'était beaucoup, au temps des débuts héroïques...) sera donc partitionnée en 64x64 = 4096 petits carrés de cette taille, chacun à 64 pixels. Vérifiez, le compte y est: 512x512 = 4096x64 !

2. C'est à chacun de ces petits carrés qu'on va appliquer une variante de la transformée de Fourier. Bidimensionnelle d'abord (Fourier avait lui même généralisé à 2 ou 3 dimensions), discrète toujours (évidemment), et limitée à l'emploi des cosinus, d'où son nom de Discrete Cosine Transform (DCT).
Les formules peuvent paraître un peu rugueuses; n'en retenons que l'essentiel (au pire, sautons les...):
  • N vaut 8 (ou plus généralement, le nombre de pisels par côté du carré à transformer);
  • Le coefficient C(u) vaut presque toujours 1 (sauf si u=0, et c'est alors ): on peut l'oublier le temps de comprendre!
  • Le coefficientdevant est normalisé pour que les deux formules soient le plus similaires possible. Attention, d'un ouvrage à l'autre, ces normalisations peuvent varier!
 

Après cet effeuillage, il ne reste qu'une somme (double, pour aller dans les deux sens dimmensionnels) des produits de la fonction pix (qui donne le niveau de gris), et de cos [...] qui prennent la place des exp[i...]. Une transformée de Fourier, quoi!

Et la merveilleuse propriété reste: la formule inverse est la même, à quelques broutilles près!

source de l'image

3. À ce stade, on peut légitimement penser qu'on n'a fait que compliquer...
D'autant que la notion de fréquence est bien plus abstraite dans le cas des images que dans le cas du son. Il se passe toutefois quelque chose d'analogue; commençons par un exemple (emprunté au livre de Mark Nelson, La Compression des Données, Dunod); les valeurs sont bien sûr arrondies aux entiers:

140 144 147 140 140 155 179 175
144 152 140 147 140 148 167 179
152 155 136 167 163 162 152 172
168 145 156 160 152 155 136 160
162 148 156 148 140 136 147 162
147 167 140 155 155 140 136 162
136 156 123 167 162 144 140 147
148 155 136 155 152 147 147 136

186 -18  15 -9 23 -9 -14  19
21 -34  26 9 -11 11 14 7
-10 -24 -2 6 -18 3 -20 -1
-8 5  15 -15 -8 3 -3 8
-3 10 8 1 -11 18 18 15
4 -2 -18 8 8 -4 1 -7
9 1 -3 4 -1 -7 -1 -2
0 -8 -2 2 1 4 -6 0
tableau d'origine (fonction pix)
après DCT

La majorité des coefficients à valeur élevée se situent vers le haut et la gauche. Pourquoi? parce que les basses fréquences de l'image encodent l'essentiel des contours, les fréquences plus hautes ajoutant de la précision. Un peu comme pour une voix: les fréquences les plus basses suffisent à la comprendre, et c'était exploité par le téléphone avant l'ère numérique: en coupant les fréquences au delà de 2000Hz, le discours était net, mais si l'on faisait écouter de la musique à son interlocuteur, elle souffrait beaucoup -tout en laissant le morceau reconnaissable. Cela se reproduit avec l'image; la première somme calculée est, à un coefficient près, la moyenne des valeurs du tableau; les autres coefficients encodent des variations plus fines de l'image. De plus en plus fines en s'éloignant vers le sommet opposé du carré.
À ce niveau, la DCT Inverse restituerait exactement la portion d'image; et on na clairement rien gagné en espace, puisquon remplace par un tableau de la même taille.


4. Une fois constaté le phénomène, on l'accentue en divisant par un facteur de quantification, qui traduit cet éloignement: en général: comme p et q croissent à partir du coin en haut et à gauche, p+q est constant sur une diagonale montant de gauche à droite, et cellte valeur est d'autant plus élevée que l'on va vers le coin en bas , à droite. On prend en général, 1+a*(p+q+1); a est réglable, par ex a=2, etn arrondit à l'entier le plus proche.

62 -4  2 -1 2 -1 -1  1
4 -5  3 1 -1 1 1 0
-1 -3 0 0 -1 0 1 -1
-1 0  1 -1 0 0 -3 0
0 1 1 0 -1 1 1 1
0 0 -1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
 
après DCT et quantification
parcours zig-zag

Le procédé est clairement irréversible; il y aura donc perte (modérée avec un a bien réglé, mais la compression consistera à éviter de répéter tous ces zéros: un procédé classique, le Run Length Encoding, qu'on ne détaillera pas ici mais facile à imaginer, ne retient de ce tableau que les coefficientts non nuls et la longueur des chaînes de 0 intermédiaires, grâce à un parcours en zig-zag particulièrement bien adapté à l'effet de la quantification!

5.  On accède de nouveau à l'image par "déquantification" (produit par l'inverse) et DCT inverse.

En résumé, la transformation de Fourier est intervenue:

Qu'est ce qui rend un scanner médical performant?

Les stars aussi passent au scanner! Les nouvelles techniques d'imagerie médicale, après avoir fourni une aide au diagnostic sans précédent, et ainsi contribué à sauver des milliers de vies, ont naturellement étendu leur champ de compétence... à l'archéologie. L'avantage est évident: ce sont des techniques non invasives, qui permettent de voir à l'intérieur d'un objet, d'une sculpture, sans y toucher!
En l'honneur de "Fourier l'Égyptien", commençons avec un des bustes les plus célèbres de l'Histoire de l'Art... et comme vous l'avez vu et revu, le Mathouriste, qui n'aime rien tant qu'un regard décalé, vous le fait voir de façon un peu moins attendue... d'abord, avec une toile qu'il aime particulièrement, car elle confronte deux de ses artistes préférés, l'un auteur, l'autre sujet: le peintre Bernard Rancillac, figure de proue de la Figuration Narrative, et, vous l'aurez reconnu, Alberto Giacometti dans son atelier. Rancillac conçoit ses toiles à partir de photos, découpées, réassemblées, projetées à l'épiscope sur la toile qu'il colore à son gré... et voilà comment une charmante curieuse s'invite chez Alberto! Á droite, cette beauté va faire savoir ce qu'elle a dans la tête, grâce à un passage au scanner (2006, mais une première séance s'était déroulée en 1992, 20 ans après l'invention du scanner médical). Les experts ont notamment pu découvrir le modèle brut en pierre, savoir comment il avait été "stuqué" avant d'être peint (voir cet article),  et accessoirement de désamorcer une argumentation fantaisiste prétendant que la statue n'était qu'un faux, âgé d'une centaine d'années seulement.


 
Bernard Rancillac, "chez Alberto" (1966)
vu à  la rétrospective 2017,
Espace Niemeyer (Paris)
photographie originale l'ayant inspirée:
par Sabine Weiss (1954)
voir ce site  (Musée de la Photographie)
Néfertiti passe son examen
(voir ici l'article)

Prenez le temps, avant de plonger vos yeux dans le cambouis mathématique, de contempler la reine en écoutant le mythique Nefertiti du Miles Davis Quintet (Wayne Shorter, Herbie Hancock, Ron Carter et Tony Williams aux côtés du maître).

Un petit coup d'œil au matériel des premiers temps (1972) et... aux images obtenues dit mieux que des mots, le formidable progrès technique qui a accompagné une innovation presque immédiatement récompensée par un prix Nobel de médecine (1979, Allan M. Cormack, Godfrey N. Hounsfield [plus détaillé en Anglais])


 

première image d'un cerveau machine ayant réalisé l'image de droite.
Elle permet seulment le passage d'une tête...aujourd'hui le corps entier!
première image  d'une tumeur cérébrale
Source des images: discours de réception du prix Nobel, rédigé  par Hounsfield.

Au départ, le principe ne diffère pas d'une radiographie ordinaire. Celle-ci permet de bien distinguer un os dans un environnement de muscle et de graisse, parce qu'avec une capacité d'absroption supérieure des rayons X, il apparait comme une tâche plus sombre. On vise bien le même but pour voir une tumeur dans un cerveau atteint, mais les différences de niveau de gris sont moindres.
Mais l'essentiel du problème est ailleurs: une projection d'un objet de l'espace sur un plan perd l'information spatiale en écrabouillant tout! Sur toute sa trajectoire linéaire, un rayon X "somme les atténuations" en chacun des points et délivre un résultat global, sans qu'on puisse revenir en arrière pour séparer les contributions.


 
Sur toute sa trajectoire linéaire, un rayon X "somme les atténuations" en chacun des points et délivre un résultat global, sans qu'on puisse revenir en arrière pour séparer les contributions.

Sur la figure de gauche (image "historique" modifiée pour les besoins de notre démonstration), les sommes présentées sur la droite bleue, au point A par le rayon rouge, au point B par le rayon jaune, peuvent fort bien être égales, donc n'apporter aucune information au médecin, alors que ces sommes ont été obtenues de façons radicalement différentes: l'une (rayon rouge) par une grosse contribution (70% à 80%) dans la partie sombre suspecte et le complément dans les zones assez claires restantes; l'autre (rayon jaune) de manière plutôt uniforme. Dans ces conditions, comment le médecin pourrait-il savoir que l'un traverse une zone tumorale, l'autre une zone saine?

 À droite, une analogie numérique: donnons nous 4 nombres: a, b, c,d, dont nous connaissons les sommes par colonne: pouvons nous les déterminer, inversement? Bien sûr que non!
a + c = b + d = 40
Nous n'avons que deux équations pour quatre inconnues, il y a des tas de manières de réaliser cela.
a b  ?
c d  ?
40 40




À droite, restons-y, une information sur les sommes en ligne élimine une partie de l'indétermination.
Par exemple, = 15, b = 17, c = = 25, d = 23, n'est plus envisageable.
Mais le système
a + c = b + d = 40
a + b = 56,  c + d = 24
 en conserve une certaine part, car l'équation a + c + b + d = 80, qui résulte des sommes de colonnes, détermine c + d = 24  dés qu'on connait a + b = 56. Autrement dit, la dernière équation n'apporte aucune information supplémentaire. Le  système se réduit en fait à  3 équations, par exemple:
a + c = b + d = 40
a + b = 56

Mais avec une somme de ligne et une diagonale, par exemple:
a + c = b + d = 40
a + b = 56
a  + d = 52
on trouve facilement tous les éléments du tableau de manière unique, à savoir

a = 34, b = 22, c = 6 , d = 18

a b  56
c d  24
40 40

pas tout à fait assez...

a b  56
c d  ?
40 40 52
gagné!

Repassons à l'image de gauche: pour avoir quelque espoir de reconstituer les valeurs des niveaux de gris en tout point de cette coupe, il vient l'idée qu'il faut connaître les sommes dans plusieurs directions, beaucoup de directions... en fait tous les angles possibles. Et voilà pourquoi le scanner a une forme d'anneau!

Ce n'est pas gagné pour autant, car les choses sont, bien sûr, plus compliquées. Il faut trouver une fonction inconnue d(x, y) qui représente la densité de gris au point (x, y) de l'image précédente en connaissant les fameuses sommes dans toutes les directions, qui s'écrivent maintenant avec des intégrales
où (X, Y) sont les coordonnées dans le repère ayant tourné de l'angle θ, traduisant d dans ce système de coordonnées. La chose s'annonce ardue!

Mais ce qui est impossible dans les coordonnées "naturelles" d'espace devient possible dans l'espace des fréquences, c'est à dire après transformation de Fourier!
Un théorème, dit théorème de rétroprojection, vient opportunément relier les deux transformées, celle, unidimensionnelle, de P
θ pour toute les valeurs de θ et celle, bimensionnelle, de d.
Il se démontre en quelques lignes sans difficulté... que l'on réservera à quelques curieux! L'affaire n'excède pas le niveau Bac +1/+2.

 explication détaillée

<à venir>



On reviendra à d par la formule de réciprocité de la transformée de Fourier bidimensionnelle; c'est à dire

En résumé, il n'y a qu'à faire effectuer par la partie calculateur du scannner quelques transformations de Fourier --rapides... cela vaut mieux! - pour retrouver, point par point, la fonction d et la traduire sur un écran en niveaux de gris.

En effectuant des coupes successives, grâce à l'avancée par échelons du "lit" à l'intérieur de l'anneau, on obtient une reconstituion tridimensionnelle, qui peut donner lieu à des images en perspective
de l'objet etudié, qu'on peut même animer par rotations successives!

Revenons  à l'histoire de l'art:

"Jusqu'à cet examen, nous ne connaissions pas l'épaisseur du stuc, ni ne savions s'il y avait un deuxième visage sculpté dans la pierre. L'hypothèse courante était que celle-ci ne constituait qu'une simple armature."

A. HUPPERT, directeur del'Institut d'Imageire Scientifique
Hôpital de la Charité, Berlin

"Notre technologie a pour but, avant tout, d'améliorer le suivi médical des patients dans le monde entier. Cependant, nous sommes heureux de contribuer aux efforts de ceux qui cherchent à percer les mystères de l'archéologie. Voilà deux ans que nous avons scanné la momie de Toutankhamon, et maintenant, nous apportons notre aide à l'étude d'un autre trésor de l'ancienne Égypte."

B. MONTAG, président de Siemens Medical Solutions

scanner du crâne de Toutankhamon, reconstruction 3D.
Source de l'image: cet aticle

Les techniques d'imageire se sont diversifiées, notamment avec l'arrivée de l'IRMN. Avec celle-ci, qu'on ne détaillera pas dans cette page, les détecteurs reçoivent des signaux, dont il faut démêler les fréquences... grâce à la FFT, et c'est une nouvelle fois par transformée de Fourier inverse que l'on reconstruit l'image compréhensible par les médecins... et le reste des humains!

Et puis, ces techniques se démocratisent et se répandent, et c'est tant mieux: de nos jours, sur le territoire français, on n'est jamais très loin d'un scanner, ce qui est crucial pour qu'il n'y ait pas une médecine des riches et une des pauvres, une des villes et une des champs... En voici une preuve archéologique, si l'on ose dire: même au fin fond de l'Auvergne natale du Mathouriste, là où les christs sont noirs... comme les charbonniers du pays, ces bougnats aux curieuses enseignes dans le Paris de jadis: Vins et Charbon, le scanner est aussi devenu un outil d'aide aux historiens de l'Art!


 
Images illustrant cet article du quotidien La Montagne (16/06/2016 ) : "Le Christ noir de la cathédrale de Saint-Flour est passé au scanner"

Tout ce que vous voulez savoir sur les étoiles... sans y avoir jamais mis le pied!


< à venir>

Des cristaux aux quasi-cristaux


< à venir>


(à suivre...)

Références

  • E. BRIGHAM, The Fast Fourier Transform and its Applications (Prentice Hall)
  • H; GOLDSTINE, A History of Numerical Analysis from the 16th through the 19th Century (Spinger)

Poursuivre...


Aller à la Page:     Analyse Harmonique... mais Pourquoi ce Nom?          (Prélude à la Théorie Analytique, #0.1)
Aller à la Page:     Analyse Harmonique... en tambours et clarinettes      (Prélude à la Théorie Analytique, #0.2) 
 
Revenir à la Page:      Naissance des Séries de Fourier                          (Promenade dans la Théorie Analytique, #1)
Revenir à la Page:      l'Armille, la Sphère, le Cylindre et les Autres...  (Promenade dans la Théorie Analytique, #2)
Revenir à la Page:      Naissance de la Transformation de Fourier         (Promenade dans la Théorie Analytique, #3)

Revenir à la Page:      Naissance de la FFT: Fast and Fourier !             (Promenade dans... la suite de l'histoire, #4.1)
Aller à la Page:           De Gabor aux Ondelettes                                      (Promenade dans... la suite de l'histoire, #5)

Aller à la Page:      Kelvin, l'Analyse de Fourier et les Marées     (En bord de mer...avec de Belles Mécaniques!)
Aller à la Page:      Séries et Modes Propres, Applications Modernes     (Pré/postlude à la Théorie Analytique, #0.3)


Revenir à la Page Biographique



Revenir à la Home Page du Mathouriste









Revenir à la Home Page du Mathouriste