Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Tomographie discrète – partie 1
Ce TP est la première partie d’un travail qui sera mené sur plusieurs séances et dont le but est de réaliser une application permettant de reconstituer une image à partir d’une signature représentant les nombres de pixels actifs sur les lignes et colonnes. Le principe peut être étendu aux diagonales, mais ce sera l’objet d’un prochain TP.
1. Le problème de la tomographie discrète
Bien qu’il ait des applications tout à fait sérieuses, on peut présenter ce problème sous la forme d’un petit jeu. Observez la grille ci-dessous.

Le but du jeu est de placer 14 jetons sur la grille de manière à ce que le nombre de jetons sur chaque ligne et colonne soit égal à la valeur indiquée en face.
Essayez de trouver une solution, mais sans y passer trop de temps, juste pour prendre conscience de la difficulté du problème.
Voici une solution, mais il y en a peut être d’autres. Il est facile de vérifier si une configuration de jetons est une solution, mais plus difficile en pratique de rechercher une solution.

On peut considérer que les jetons sont les pixels actifs d’une image (noirs ou blancs selon la convention utilisée). La liste des nombres de pixels actifs sur les différentes colonnes, (1,6,2,2,2,1) et celle des nombres de pixels actifs sur les différentes lignes, (2,5,2,2,2,1) constituent ce que nous appellerons la signature de l’image.
Le problème de la tomographie discrète consiste, étant donnée une signature, à produire une image en cohérence avec cette signature. Le problème se généralise à des grilles, carrée ou rectangulaires, de toutes dimensions. Toute image à une signature, mais au delà d’une certaine taille de grille, certaines signatures correspondent à plusieurs images.
Voici un exemple de signature correspondant à deux images différentes.

On peut améliorer la fiabilité de la reconstruction en ajoutant à la signature les nombres de pixels actifs dans les diagonales montantes et descendantes.

Dans un premier temps, nous nous intéresserons à la variante simple du problème basée sur des signatures lignes / colonnes.
2. Représentations des données
Représentation d’une image
Nous allons d’abord travailler sur la représentation d’une image sous la forme d’un tableau d’entiers de type char à une dimension. La figure ci-dessous illustre sur un exemple le principe utilisé.

Voici la déclaration d’un tableau représentant une image de 6 par 6 ne contenant que des pixels éteints.
int dim = 6;
char image[dim*dim] = {0};
Représentation d’une signature
La signature de l’image à reconstituer sera constituée de deux tableaux représentant respectivement les nombres de pixels actifs sur les lignes et sur les colonnes.
int dim = 6;
int sLignes[dim] = {2,5,2,2,2,1};
int sColonnes[dim] = {1,6,2,2,2,1};
3. Fonctions à réaliser
Affichage d’une image
Pour la mise au point du programme et la vérification du résultat, nous aurons besoin d’une fonction permettant d’afficher une image.
// Affiche l'image désignée par img,
// de largeur et hauteur dim.
void afficheImage(char* img, int dim);
La fonction auxiliaire suivante pourra être utilisée par la fonction afficheImage et par d’autres fonctions que vous aurez à définir.
// Retourne la valeur du pixel situé en ligne lgn et
// en colonne col dans l'image de dimension dim
// désignée par img
int litPixel(char* img, int dim, int lgn, int col);
La fonction suivante suivant permet de tester la fonction afficheImage en lui faisant afficher une image de test.
void test_AfficheImage()
{
char image[] =
{
1,0,1,1,
1,0,1,1,
1,0,1,0,
1,1,1,0
};
afficheImage(image, 4);
}
L’affichage attendu est le suivant :
XX XX XX
XX XX XX
XX XX
XX XX XX
Horizontalement, chaque pixel est représenté par le motif XX et les pixels sont séparés par des espaces.
Vérification de la signature d’une image
Fonctions à définir
La fonction suivante permet de vérifier si une image est compatible avec une signature
// Vérifie si la signature constituée des tableaux désignés
// par sLgn (pour les lignes) et sCol (pour les colonnes)
// est compatible avec l'image de dimension dim désignée
// par img. Retourne vrai si image et signature compatibles.
int verifSign(char* img, int* sLgn, int* sCol, int dim)
Cette fonction fera appel à deux fonctions auxiliaires : une pour compter le nombre de pixels actifs sur une colonne donnée et une autre pour compter le nombre de pixels actifs sur une ligne donnée.
// Retourne le nombre de pixels actifs sur la ligne lgn de
// l'image de dimension dim désignée par img
int compteLigne(char* img, int lgn, int dim);
// Retourne le nombre de pixels actifs sur la colonne col
// de l'image de dimension dim désignée par img
int compteCol(char* img, int col, int dim);
Vous devez non seulement implémenter ces fonctions, mais aussi réaliser les fonctions de test associées en suivant les instructions données dans la section suivante.
Test des fonctions
Une bonne pratique de développement consiste à tester chaque fonction après l’avoir définie et avant de commencer à implémenter d’autres fonctions. Cela suppose d’implémenter la fonction compteLigne et la fonction compteCol avant la fonction verifSign qui les utilise.
D’une manière générale, toute fonction a des données d’entrée et des données de sortie.
Les données d’entrée d’une fonction peuvent être :
- Les valeurs de ses paramètres, appelées arguments,
- Toutes les autres informations prises en compte par la fonction, qui peuvent être par exemple dans des variables globales ou dans des variables pointées par des arguments de la fonction.
Les données de sortie peuvent être :
- La valeur de retour,
- Toutes les informations modifiées par l’exécution de la fonction, qui peuvent être par exemple des données situées dans des variables globales ou dans des variables pointées par des arguments de la fonction.
- Les affichages réalisés par la fonction, si applicable.
Pour tester une fonction, il faut des données de test, c’est à dire des données d’entrée avec lesquelles on va exécuter la fonction et vérifier que les données de sortie sont correctes. Ces données de tests ne doivent pas être complaisantes. Elles doivent être conçues dans le but de provoquer une erreur si la fonction est mal programmée.
Le test d’une fonction est appelé test unitaire. Deux approches sont possibles pour réaliser un tel test :
- L’approche artisanale, dans laquelle on vérifie visuellement, par des affichages, que les données de sorties sont correctes.
- L’approche automatisée, dans laquelle une fonction de test appelle plusieurs fois la fonction à tester avec des données de tests pré-établies ou produites aléatoirement, vérifie que les résultats sont corrects, et retourne un booléen indiquant si le test a été réussi ou si une erreur a été détectée. Dans ce dernier cas, un message décrivant l’erreur et la donnée problématique peut être produit. (Dans les grosses applications développées en équipe, ce message peut être écrit dans un fichier ou même envoyé automatiquement au développeur ayant implémenté la fonction défaillante.)
Examinons ces deux approches avec la fonction compteLigne.
Test artisanal
Voici un exemple de fonction de test "artisanale" de la fonction compteLigne, qui compte le nombre de pixels actifs sur une ligne d’une image.
void test__compteLigne()
{
char image[] =
{
1,0,1,1,
1,0,0,1,
1,0,1,0,
0,0,1,0
};
printf("\nLes valeurs obtenues sont : ");
for(int i=0; i<4; i++)
{
printf("%d ", compteLigne(image,i,4));
}
printf("\nLes valeurs correctes sont : 3 2 2 1\n");
}
La donnée de test est une image pré-définie par l’initialisation d’un tableau. On appelle la fonction compteLigne pour chaque ligne de cette image et on affiche la valeur retournée. La personne qui réalise le test vérifie que les affichages produits correspondent bien aux valeurs attendues.
Test automatisé
Voici un exemple de fonction qui automatise le test de la fonction compteLigne.
int test_compteLigne()
{
char image[] =
{
1,0,1,1,
1,0,0,1,
1,0,1,0,
0,0,1,0
};
int sLgn[] = {3,2,2,1};
for(int i=0; i<4; i++)
{
if(compteLigne(image,i,4) != sLgn[i])
{
printf("Test de compteLigne : erreur ligne %d\n",i);
return 0;
}
}
return 1;
}
Non seulement cette fonction de test appelle la fonction à tester avec différentes données d’entrée (une même image, mais plusieurs numéros de lignes), mais elle vérifie si le résultat retourné est correct. Bien sûr les résultats attendus ont été produits par un autre moyen que l’appel à la fonction à tester. Ici, la personne ayant défini la fonction de test a compté les 1 dans les représentations des lignes de l’image de test.
Quel type de test implémenter ?
Dans le cadre d’un TP ponctuel, d’une durée limité, des fonctions de test artisanales sont suffisantes car le temps supplémentaire passé à réaliser des tests automatisés ne serait pas rentabilisé par une utilisation ultérieure des fonctions de tests développées.
Dans le cadre de ce TP, vous devez réaliser les fonctions de test artisanales et automatisées des fonctions compteCol et verifSign. Pour les autres fonctions, seul un test artisanal est demandé.
Recherche d’une image correspondant à une signature
Il existe différents moyens pour rechercher une image correspondant à une signature connue. Les plus faciles à programmer sont les moins efficaces et ne permettent de traiter que de petites images. Les moyens proposé ici pourront être exploités avec des images de 4 par 4.
Recherche aléatoire
Le principe est de produire une image aléatoire, puis de vérifier si elle correspond à la signature donnée, et de recommencer tant qu’une image compatible n’est pas produite. On peut donner une limite du nombre d’essais à réaliser.
Une fonction auxiliaire doit être définie et testée de manière artisanale :
// Crée une image aléatoire de dimension dim dans
// le tableau désigné par img.
void genRandImage(char* img, int dim);
Voici la déclaration de la fonction de recherche :
// Recherche une image de dimension dim compatible avec la signature
// définie par les tableaux désignés pae sLgn (pour les lignes) et
// sCol (pour les colonnes). La recherche consiste à produire au plus
// nEssais images aléatoires et s'arrête lorsqu'une image correcte
// est trouvée. La valeur de retour est -1 si aucune image correcte n'est
// trouvée, sinon c'est le nombre d'essais réalisés.
int rechercheRandom(char* img, int dim, int* sLgn, int* sCol, long nEssais)
Elle doit être testée de manière artisanale par la fonction main suivante :
int main()
{
int dim = 4;
srand(time(NULL));
int sLignes[] = {3,3,2,3};
int sColonnes[] = {4,1,4,2};
char image[dim*dim];
int n = rechercheRandom(image,dim,sLignes,sColonnes,100000);
if(n>0)
{
printf("Image trouvée en %d essais\n\n",n);
afficheImage(image, 4);
}
else
{
printf("Image non trouvée\n");
}
return 0;
}
L’initialisation du germe du générateur pseudoaléatoire basée sur le temps système permet d’obtenir des tirages différents à chaque exécution du programme.
Vous pourrez constater que non seulement le nombre d’essais réalisés avant d’obtenir une image correcte varie d’une exécution à l’autre, mais aussi que l’image trouvée n’est pas toujours la même.
Recherche par force brute
Cette approche consiste à produire de manière systématique toutes les images possibles jusqu’à en trouver une compatible avec la signature donnée. Seules les personnes les plus avancées sont invitées à traiter cette partie.
Une manière de procéder, pour des images de dimension 4, consiste à réaliser un comptage de \(0\) à \(2^{16}-1\) avec un entier de type uint16_t. Pour chaque valeur produite, les 16 bits de l’entiers sont transposés dans le tableau représentant l’image.«