Dossier de Nico présenté dans l’épisode #134.

Il y a 470 jours, pour mes premières bafouilles dans PodcastScience, je vous présentais le plus simplement du monde l’infini… ou plutôt devrais-je dire LES infinis! A cette occasion la plupart d’entre vous ont en effet sans doute découvert qu’il existe un sacré paquet d’infinis, tous plus “grands” que les uns que les autres. Par exemple, nous vîmes que même avec une infinité d’épisodes de ce doux podcast, il serait bien impossible de parler de tout.

Sans vouloir entrer dans l’autobiographie, mon second dossier présenta le nombre Pi, ce nombre terriblement banal. Bien plus en tout cas que ces chiffres qui vous paraissent tant communs : 1, 2, 3 sont en fait des éléments tellement rares qu’on devrait les encadrer! Pi est très commun et comme la plupart des nombres (“presque tous” dirait-on en termes mathématiques), il est incalculable. C’est justement ce que je vous présentais dans mon troisième dossier.

Ce dossier sur les algorithmes présentait un morceau de l’histoire de l’algorithmique, cette théorie derrière les ordinateurs. Ce monde où le nombre d’opérations possibles est un infini dénombrable. Alors que le monde dans lequel on évolue est continu, nos armes pour le comprendre sont discrètes. Représenter le monde analogique/continu avec le numérique/discret, c’est comme essayer de jouer au pianola un morceau écrit pour un violon, une idée qui n’est même pas passé dans l’esprit fou de George Antheil!

C’est justement ce pari impossible qui nous intéresse aujourd’hui! Comment peut-on avec des outils discrets, dénombrables, représenter le monde continu? En d’autres termes, est-il possible de finalement jouer avec un piano toute la variété des sons que nous offre un violon. Cette problématique est la clé du monde numérique qui nous envahit aujourd’hui. Sans cela, les ordinateurs, le téléphone ou tous ces objets numériques qui nous entourent n’auraient pas connus l’essor qu’ils ont actuellement.

De pourquoi il y a un problème

Au delà de ces divagations autobio-schyzophréno-psycholo-graphiques, le problème qui s’est posé à Shannon et à d’autres avant lui, est de réussir à capter toute la variété d’un signal continu en ne prenant que quelques échantillons. Une image numérique par exemple est constituée de pixels. Dans chacun de ces pixels, on a représenté l’intensité lumineuse captée dans un petit carré. En première approximation, on peut considérer que c’est l’intensité lumineuse en un point de l’espace. Or le signal lumineux qui arrive sur le capteur est lui défini dans tout l’espace. En somme, votre appareil photo numérique est en train de regarder le monde à travers une rape à fromage et pourtant il arrive à reconstituer sans trop de problèmes le monde qui l’entoure!

En mathématiques, ce type de problèmes est à caser dans la catégorie des problèmes “mal posés”. Il n’y a en gros que deux possibilités :

• Soit un problème est bien posé et alors il a une unique solution.
• Soit on a pas de réponse à un problème et alors le plus souvent il est “mal posé”.Reprenons le cas de la rape à gruyère. Si vous regardez à travers une rape à gruyère, certaines parties de votre environnement sont cachées par celles-ci. Imaginons alors que nous cachions derrière la rape vos clés (on perd toujours ses clés). Alors vous serez bien incapable de différencier une scène avec vos clés d’une scène sans.

Deux scènes différentes donnent le même jeu d’échantillons (on voit la même chose dans les trous de la râpe), il est donc bien impossible de déterminer quelle était vraiment la bonne scène, savoir si vous clés étaient là ou pas. Conclusion (ce n’est pas le théorème de Shannon), ne mettez pas une rape de gruyère devant votre visage pour chercher vos clés.

Ce qu’a VRAIMENT montré Shannon

Alors c’est bien beau de ne prendre que quelques échantillons par ici par là, mais cela ne suffit pas à reconstruire comme il faut le monde qui nous entoure. Il faut dire que cacher les clés justement là où on notre vision est cachée par une râpe jusdicieusement posée devant nos yeux est un peu pervers et nécessite surtout des petites clés. Arrivent alors des grands esprits comme on en rencontre régulièrement dans PoscastScience : Shannon et avant lui Nyquist. Ceux-ci ont déterminé, pour une râpe à fromage donnée, la taille de clés minimale détectable!

Ce problème d’échantillonnage est des plus intéressant, car le plus complexe était de choisir des hypothèses à la fois simples et générales et non de démontrer le résultat. En effet il y a une bonne infinité possible de choix (je vous laisse déterminer si elle est dénombrable ou indénombrable) :

• Si la rape n’a qu’un énorme trou de taille infini, on voit tout (OK dans ce cas la râpe n’existe pas trop…)

• Si les clés sont de taille infinie dans toutes les directions (une sorte de plateau de taille infinie), tant que la rape a au moins un trou, on les voit (certes les clés ne sont pas très transportables dans ce cas…)

• Si les clés sont d’une longueur infinie (dans une seule direction, sorte de javelot infini des deux cotés…) et si les trous de la râpe sont en fait des lignes non parallèles, on verra bien les clés (réalisme, quand tu nous tiens…)

• Si la rape n’a qu’un seul trou qui pointe vers le centre des clés, il verra les clés (il faut être précis…)
• etc.Tous ces résultats sont vrais, mais ils sont soit trop restreints, soit irréalistes, soit un peu des deux, autant dire inutilisables!

Shannon et Nyquist ont tous les deux utilisé une notion à la fois plus simple et universelle : la notion de fréquence. Depuis le dossier sur la Transformée de Fourier (damned, tout est lié!), vous savez qu’on peut écrire n’importe quel son, n’importe quelle image ou plus généralement n’importe quel signal dans l’espace des fréquences comme on traduirait n’importe quel texte d’une langue à l’autre. La langue fréquentielle est faite de sinusoïdes, ces mêmes fonctions trigonométriques aux propriétés remarquables qui nous ont tous traumatisées dans notre jeunesse.

Une sinusoïde sert à représenter l’évolution d’un morceau de gruyère resté coincé sur notre rape circulaire (comment ça votre rape n’est pas circulaire?). Ainsi pour repérer le bout de gruyère sur la râpe, on utilise le cosinus représente son écart par rapport au centre sur l’horizontale (le sens de la table) alors que le sinus son écart par rapport au centre sur la verticale (de haut en bas).

Après une séance intensive de rape, alors que la jolie vous laisse le soin de nettoyer l’objet, positionnez votre rape circulaire telle que le morceau de gruyère vienne délicatement caresser la table et faites tourner! Au bout d’un quart de tour, le morceau de gruyère fera face à la fenêtre (si vous avez une fenêtre dans sa direction), en tout cas, le centre de la rape et le morceau seront parallèles à la table. Le sinus vaut alors zéro. Quand la rape aura fait un demi-tour, le morceau de gruyère vous fera face en pointant vers le haut (ne prenez pas cela comme une provocation et laissez le en place, on va encore en avoir besoin). C’est maintenant le cosinus qui vaut zéro comme au début de cette périlleuse expérience. Enfin, transpirant, quand vous avez enfin fait faire un tour à la rape, le morceau de gruyère sera revenu à sa place initiale, carressant de nouveau avec tendresse la table.

Votre chère et tendre, qui vous avait laissé au début de l’expérience, le morceau de gruyère contre la table, fait alors son grand retour pour vérifier si vous avez fini de nettoyer cette foutue rape! Elle vous trouve dans la position où elle vous avait laissé et il vous est bien impossible de prouver que la rape a tourné, les deux positions étant identiques! Ne prendre qu’un échantillon par période, comme l’a fait votre amie ne permet absolument pas de retrouver l’intégralité de la sinusoïde, de la rotation de la râpe. De même, si celle-ci avait tenté d’entrer alors que le gruyère vous faisait face au sommet de la rape, elle aurait été bien en mal de savoir dans quel sens avait tourné l’ustensile de cuisine.

En fait, le théorème de Shannon-Nyquist, montre que pour un signal dont la décomposition fréquentielle ne comporte pas de fréquences de plus de N hertz, il faut prendre au moins 2N échantillons par seconde pour parvenir à reconstruire exactement le signal. Mais le plus fou de ce théorème n’est pas tant qu’il faille prendre 2N ou même plus d’échantillons, c’est qu’avec cette méprisable infinité dénombrable d’échantillons, on reconstruit exactement l’infinité continue des signaux à bande limitée! Donc si un signal ne dépasse pas certaines fréquences, on pourra, avec un taux d’échantillonnage bien choisi, l’échantillonner sans pertes.

Une oreille humaine justement n’entend que les sons compris entre 20 et 20 000 Hz, ainsi, selon le théorème de Shannon-Nyquist, si on mesure l’intensité sonore 40 000 fois par seconde, on pourra reconstruire exactement (c’est à dire sans pertes, sans aucune erreur) le signal audible de départ! Vous venez de comprendre pourquoi un WAV prend 44100 échantillons par seconde!

Hors la loi

Un théorème mathématique est vrai sous certaines règles, et quand on a des règles, il n’y a rien de plus jouissif que de s’amuser à les transgresser, pour voir! Que se passe-t-il donc si l’on échantillonne trop lentement?

Reprenons notre rape, si votre “petit lapin en aspartame” était rentré après un tour et quart, elle aurait vu le morceau de gruyère dans la même position que si la rape avait seulement fait un quart de tour. En fait, toutes les fréquences qui dépassent la demi-fréquence d’échantillonnage (appelée aussi fréquence de Shannon-Nyquist), sont tout simplement soustraites par cette même fréquence de Shannon-Nyquist un nombre de fois suffisant pour entrer dans cet intervalle. C’est-à-dire que si la fréquence de rotation de la rape est d’un tour par minute (1/60 Hz, vous êtes très concentrés) et que, comme dans le premier exemple, vous regardez la position du morceau de gruyère aussi une fois par minute (1/60 Hz), la fréquence “perçue” est de :

1/60 – (1/60)/2-(1/60)/2 = 0 Hz! On a l’impression que la rape ne bouge pas.

C’est cet effet que l’on observe sur les roues des voitures lors des courses poursuites. Une caméra prend 25 images par seconde. Si la roue de la voiture fait 25 tours par seconde (en gros 230km/h), la caméra verra toujours la roue dans la même position : on aura l’impression que la roue ne bouge pas. Si par contre, elle va un peu moins vite, la roue paraitra aller en sens inverse et si elle va plus vite, elle paraitre avancer très lentement!

En d’autres termes, l’échantillonnage se traduit dans l’espace des fréquences par une translation. Alors quand il y a des fréquences hors du domaine admissible par Shannon-Nyquist, elles sont “repliées” sur les fréquences acceptables. Cela provoque des effets basse fréquence indésirables. Ces effets sont très régulièrement présents dans les vidéos. Comme on a vu dans l’épisode sur la transformée de Fourier, les sinusoïdes dans les images sont assimilables à des rayures. Ainsi, une haute fréquence repliée dans les basses fréquences sera une rayure plus élargie. C’est exactement l’effet que vous pouvez constater dans certaines images où vidéo : un effet de marche d’escalier sur les contours ou des rayures parasites apparaissant sur des zones de l’image où il y a justement de rayures. On appelle cet effet “aliasing” ou “repliement de spectre”.

Dans les images comme dans les sons, l’échantillonnage se traduit dans l’espace des fréquences comme une translation. Le théorème de Shannon-Nyquist se transpose alors en demandant à l’image d’avoir un spectre qui ne se replie pas sur lui même. Le spectre des images, comme les images elles-mêmes sont définies sur un plan. La fréquence de Shannon deviens alors un “domaine de Shannon” c’est a dire un domaine du plan spectral acceptable. Le problème de l’échantillonnage correspond alors en somme de trouver une bonne façon de carreler le sol! Quel que soit la forme du domaine spectral répété sur le carrelage, l’important est qu’il ne se superpose pas sur lui même lorsque l’on effectue une periodisation infinie! On arrive alors comme cela à acquérir des rayures bien plus fines que ce que permettrait Shannon pour les signaux à une dimension grâce à une analyse géométrique!

Depuis Shannon

Cette quête pour “dépasser Shannon” ne cesse d’occuper les mathématiciens. En particulier, le choix des hypothèses sur la rape et les clés sont particulièrement discutées. En particulier, j’ai commencé mon propos en parlant de jouer du violon avec un piano, regardons justement de plus près ce piano!

Comme tout son audible, les fréquences émises par un piano sont bien limitées comme le demande le théorème de Shannon-Nyquist. Mais est-ce que considérer que les fréquences qu’il produit peuvent être continument étalées le long des fréquences est bien réaliste? Un piano n’est finalement qu’un ensemble bien déterminé de notes, un petit ensemble discret de fréquences. En poésie mathématicienne, on parle de parcimonie. Alors, lorsque l’on échantillonne l’intensité sonore, on peut justement chercher quelles notes de piano ont pu produire ces échantillons au lieu de plus généralement chercher quel son a produit ces échantillons.

Ce problème est mieux posé, il demande en fait moins d’échantillons grâce à la redondance! On vit en permanence avec de la redondance. Les langues par exemple, sont très redondantes, Shannon a même calculé en son temps que l’anglais était à 50%. Une information redondante est une information qui vient forcément avec une autre comme pour un pléonasme : “monter en haut” ne contient pas plus d’information que “monter” alors il est inutile d’entendre tous les mots pour comprendre.

Des techniques récentes d’échantillonnage visent à utiliser ces redondances dans les signaux à mesurer pour utiliser beaucoup moins d’échantillons que ce que préconiserait le théorème de Shannon-Nyquist. Il s’agit en particulier d’acquérir le signal dans le langage le plus différent du langage dans lequel le signal est parcimonieux. Alors que le message à retrouver n’utilisera que peu de mots dans sa langue la plus efficace, il utilisera tellement de mots dans la langue d’acquisition qu’avec peu d’échantillons on aura suffisamment d’informations pour le retrouver!

Bref, on a pas fini d’entendre parler d’échantillonnage mais on détaillera une autre fois ces méthodes d’échantillonnages plus récentes!

Bibliographie et pour aller plus loin :

• L’article de Shanon qui a tout lancé : Pas forcément compréhensible dans ses détails par tout le monde mais à la lecture de ce dossier vous devriez comprendre les grandes idées.
• 50 years after Shanon : pareil que le précédent pour la compréhension mais vaut la lecture pour réaliser tout ce qui s’est fait depuis ce théorème et comment la science et en particulier les mathématiques appliqués évoluent.
• “The Information : A history, a theory, a flood” de James Gleick : je ne l’ai pas encore tout à fait fini mais c’est une vraie balade autour de l’histoire de l’information et de sa théorisation. Finalement il a très peu servi pour ce dossier mais j’en conseille malgré tout la lecture.