Les Étincelles du Palais de la découverte
La médiation scientifique
Découvrez le futur Palais
Vous êtes une amatrice ou un amateur (un peu blasé.e) de sudoku ou de nonogramme ? Cet article vous propose des jeux de grille logiques inédits, inspirés directement de la pratique de la tomographie. Au passage, il vous en révèle les difficultés et vous initie aux techniques de cette discipline, qui m’a été très utile pour ma thèse en mécanique des fluides.
Si vous voulez jouer sans lire les détails de l’article, téléchargez uniquement les grilles de jeux. Elles existent en format Excel si vous souhaitez utiliser votre ordinateur, ou en version PDF si vous êtes plutôt papier-crayon et que vous pouvez les imprimer. Vous trouverez également les solutions en PDF, en extrême recours, en fin d’article. Amusez-vous bien !
La reconstruction tomographique est l’art de pouvoir reconstruire un volume à partir d’images planes (fig. 1). Un architecte, par exemple, peut souhaiter visualiser un bâtiment en trois dimensions (3D) à partir de photographies prises sur site. Un médecin a besoin d’une vision 3D de l’intérieur du corps de son patient à partir de radiographies à rayons X. Un expert en cristallographie veut connaître la structure en 3D d’un cristal ou d’un matériau à partir des données recueillies au microscope électronique à balayage (MEB) en deux dimensions, pour en déduire ses caractéristiques physiques. Le chercheur en mécanique des fluides que je suis est intéressé, quant à lui, par la visualisation de l'écoulement de l'air autour d’une voiture. En filmant le passage de millions de petites particules, il peut reconstruire en 3D et en temps réel la position de chacune d’entre elles pour étudier l’aérodynamisme de l’ensemble.
Votre cerveau fait lui aussi régulièrement de la tomographie. Testez cette expérience simple pour vous en persuader : fermez un œil, bras demi-tendus et rapprochez doucement vos index l'un de l'autre jusqu’à ce qu'ils se touchent. Sans tricher, l'exercice devient très vite difficile. Mais si vous rouvrez l’autre œil, il est aisé de constater combien l'emploi simultané des deux yeux et l'intégration des différentes informations par le cerveau permet d'évaluer rapidement la profondeur de champ. Et de se rendre compte par la même occasion de l'air très amusé du voisin d'en face qui se demande ce que vous fabriquez !
Le super-ordinateur qu’est notre cerveau récupère en permanence les images délivrées par chacun de nos yeux, qui ont des angles de vue légèrement différents, et reconstruit ainsi une image de l’environnement qui nous entoure en trois dimensions : c’est la vision stéréoscopique.
Cette reconstruction est un art complexe, y compris pour notre cerveau. Aussi, il arrive parfois qu’il soit obligé de tricher un peu et d’interpréter cette reconstruction. Ce qui peut conduire à des illusions d’optique.
Un jeu proche de la tomographie existe depuis les années 70, nommé parfois nonogramme, picross ou encore logimage, mais dont le principe reste identique. Il s’agit de noircir autant de cases dans chaque ligne et colonne que les nombres indiqués sur les côtés de la grille de jeu. Ces derniers désignent en réalité des « paquets » séparés les uns les autres par au moins une case vide. La plupart du temps, la solution est une image en « pixel-art ». Le jeu n° 1 en montre un exemple.
Pour un ordinateur, la tâche est plus ardue. D’abord parce que l'idée même de volume n’est pas « naturelle » pour lui. Afin de pallier ce problème, les informaticiens ont recours au voxel. Comme son homologue le pixel, petit carré de base de nos photographies numériques, le voxel est un petit cube dans l’espace contenant une information de couleur (fig. 2).
La reconstruction volumique, une technique utilisée souvent en médecine, consiste à simplifier encore le problème pour l’ordinateur : travailler en coupes, comme en cuisine. Plutôt que de reconstruire le volume entièrement, celui-là est tranché en rondelles – virtuellement bien sûr – dans le sens de la longueur. Il sera plus facile ensuite de réaliser des reconstructions tomographiques plan par plan. Chaque plan sera superposé alors sur les autres pour reconstruire finalement le corps entier. Un peu comme si un légume déjà tranché était reconstitué en accolant toutes ses coupes (fig. 3).
Autre problème plus délicat : ni les ordinateurs les plus perfectionnés, ni même la fameuse intelligence artificielle (IA) ne sont pourvus à l’heure actuelle de la capacité à interpréter les reconstitutions de volumes qu’ils construisent.
Pour comprendre cette difficulté, imaginons la situation suivante : sur une table sont placés un cône et une pyramide à base triangulaire. Placez vos yeux au ras de la table, face à l’axe du cône ou une arête de la pyramide. L’un de vos yeux voit à chaque fois la même projection du volume, qu’il soit cône ou pyramide : il s’agit d’un triangle. Si vous utilisiez uniquement les images que recevaient vos yeux, vous ne seriez pas en mesure de faire la différence entre le cône et la pyramide, car ces deux objets renvoient exactement les mêmes projections. Comment le cerveau distingue-t-il donc ces deux objets ?
En fait, le réfléchissement de la lumière sur l’objet, l’état de la surface (par exemple la présence d’arêtes) ou encore les ombres sont autant d’informations supplémentaires intégrées par notre cerveau pour « sélectionner » une forme plutôt qu’une autre. Dans ce contexte, imaginez combien l’art de la reconstruction volumique peut devenir un véritable casse-tête pour les ordinateurs !
Ces trois points caractérisent un problème dit « mal posé » en mathématiques. Il est pourtant indispensable de trouver des méthodes de résolution acceptables.
Dans la suite, nous considérons un exemple de jeu qui se rapproche davantage de la résolution tomographique. Imaginons des grilles dans lesquelles les cases peuvent être blanches ou noires. Le nombre de cases noires sur chaque ligne et colonne est reporté sur les bords du tableau. Attention ! Le nombre indiqué est ici une projection, et les cases noires ne sont pas nécessairement contiguës, contrairement au nonogramme. La figure 4 propose un exemple comportant deux solutions différentes.
Dans son article de 1957 (« Combinatorial properties of matrices of zeros and ones »), le mathématicien américain H. J. Ryser donne une condition nécessaire et suffisante pour savoir si une solution à ce genre de problèmes est possible et comment la construire. Il explique comment déterminer si une solution est unique : il faut et il suffit qu’aucune bascule ne soit possible. Dans le cas de deux projections (horizontale et verticale), une bascule est une situation que les amateurs de jeux de grilles connaissent bien : elle survient lorsqu’il est possible d’échanger la position de deux cases noires avec deux cases blanches sans modifier les projections.
Regardons par exemple les quatre cases au sommet du carré de cette grille. Il s'agit d'un exemple de bascule : dans les deux grilles de la figure 5, il y a une unique case noire sur les première et dernière lignes. De même, il y a une unique case noire sur les première et dernière colonnes. En ne connaissant que les valeurs des projections horizontales et verticales, il est totalement impossible de favoriser une solution plutôt qu'une autre, les deux solutions sont possibles !
Plus généralement, si la solution n'est pas unique, c'est qu'il manque des informations ou qu’il y a, grossièrement, davantage d’inconnues que de projections. Nous pouvons passer alors à un plus grand nombre de projections : 3, 4, 5, 10, 100 ou plus encore. Mais nous nous apercevons que le problème devient très rapidement illisible et complexe. Nous laisserons donc le soin à un ordinateur de trouver la bonne solution, ou au moins la meilleure possible !
En pratique, nous tentons ici de reconstituer une image à partir de deux projections. Avec une seule, toute notion de profondeur disparaît. Mais comme il n’est pas rare de trouver deux images différentes qui renvoient les mêmes projections (fig. 6), la solution qui s’impose rapidement consiste à augmenter le nombre de projections.
Passons de deux à trois projections en considérant une troisième direction, diagonale cette fois-ci. Un peu comme un médecin qui ne se contenterait pas de deux angles de vue sur des radiographies pour repérer une lésion.
Voici donc un nouveau jeu où, comme précédemment, l’objectif est de noircir les cases pour faire en sorte que le nombre de cases noires sur chaque ligne et chaque colonne corresponde à celui reporté sur les bords de la grille. Mais cela doit être vrai aussi sur les diagonales…
Dans certains cas, comme en mécanique des fluides par exemple, la forme des objets recherchés est connue, il ne reste qu’à déterminer leur position. Cela fournit incontestablement des informations supplémentaires pouvant aider à la résolution.
Représentons cela dans un nouveau jeu : comme précédemment, les cases sont à noircir en tenant compte des nombres portés sur les lignes, les colonnes et les diagonales. De plus, nous savons que les cases noires sont regroupées nécessairement 4 par 4 pour former des « L », qui peuvent être tournés dans tous les sens comme sur la figure 7.
Maints problèmes liés à la tomographie (dont les jeux n° 1, 3 et 4) appartiennent à une grande famille de problèmes nommés NP-complets, dont font partie également les problèmes de remplissage de grilles de sudoku. La résolution de ce type de problèmes, hormis dans de rares cas construits pour l’exercice, s’avère très difficile, y compris pour un ordinateur. Dans la pratique, pour accroître la complexité, il est courant de chercher la solution sur de « petites » grilles… de plusieurs millions de cases !
Nous l’avons vu, la reconstruction tomographique intéresse de nombreux domaines des sciences. Au-delà du jeu, ce beau problème mélange plusieurs branches des mathématiques et de l’informatique : l’analyse combinatoire, la théorie des groupes, la théorie des graphes, mais aussi l’algorithmique et la programmation.
Enfin, de manière assez étonnante, la reconstruction tomographique peut concerner aussi d’autres domaines de recherche, parfois relativement éloignés du problème de départ. Ainsi, en compression d’image, il serait avantageux, pour minimiser la taille des données, de n’envoyer que les projections d’une photographie… si l’on était capable de reconstruire la photographie à partir de ce seul jeu de données !
Damien Geneste a réalisé une thèse en physique à l'université Paris-Saclay. Il a rejoint Saint-Gobain Recherche en mars 2023, où il travaille sur l'amélioration de l'impact environnemental de la fabrication de la laine de verre.
