Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Tomographie discrète – partie 2
Pour aborder cette partie, il faut maîtriser la partie précédente à l’exception de la recherche par force brute, soit en ayant vous-même trouvé les solutions, soit en ayant étudié et compris la solution qui vous a été fournie.
1. Rappels sur les briques logicielles disponibles
Tous les éléments repris ici sont fournis dans le corrigé du TP3 disponible sur le padlet de l’unité d’enseignement.
Structures de données
Images
Une image, c’est à dire une grille carrée peuplée de pixels allumés et de pixels éteints, est représentée concrètement par un tableau à une dimension comme indiqué sur un exemple par la figure ci-dessous.

On appelle dimension d’une image le nombre de cases, ou pixels, d’une ligne ou d’une colonne. L’image ci-dessus a pour dimension 3.
Le tableau représentant une image de dimension 3 dont tous les pixels sont éteints peut se déclarer de la manière suivante :
int dim = 3;
char image[dim*dim] = {0};
Signatures
La signature d’une image de dimension dim est constituée de deux listes de dim entiers représentées par des tableaux de int.
- La première liste donne les nombres de pixels allumés sur les lignes de l’image. Dans l’exemple de l’image de dimension 3 de la figure précédente, ces nombres sont 1, 2, 0.
- La deuxième liste donne les nombres de pixels éteints sur les colonnes de l’image. Dans l’exemple de la figure précédente, ces nombres sont 1, 1, 1.
Les tableaux représentant la signature de l’image de la figure précédente peuvent se déclarer de la manière suivante (on suppose que la variable dim a été précédemment déclarée et initialisée à 3) :
int sL[dim] = {1,2,0}; // Signature lignes
int sC[dim] = {1,1,1}; // Signature colonnes
Fonctions disponibles
Les fonctions suivantes sont déjà implémentées (voir corrigé du TP3).
Lecture d’un pixel
int litPixel(char* img, int dim, int lgn, int col);
Paramètres :
img: Image dans laquelle se trouve le pixel à lire.dim: Dimension de l’image.lgn: Numéro de la ligne du pixel (entre 0 etdim-1).col: Numéro de la colonne du pixel (entre 0 etdim-1).
Valeur de retour : 0 si le pixel est éteint, 1 s’il est allumé.
Affichage d’une image
void afficheImage(char* img, int dim);
Paramètres :
img: Image à afficher.dim: Dimension de l’image.
Nombre de pixels allumés sur une ligne
int compteLigne(char* img, int lgn, int dim);
Paramètres :
img: Image à analyser.dim: Dimension de l’image.lgn: Numéro de la ligne (entre 0 etdim-1).
Valeur de retour : Nombre de pixels allumés sur la ligne lgn.
Nombre de pixels allumés sur une colonne
int compteCol(char* img, int col, int dim)
Paramètres :
img: Image à analyser.dim: Dimension de l’image.col: Numéro de la colonne (entre 0 etdim-1).
Valeur de retour : Nombre de pixels allumés sur la colonne col.
Vérification de la cohérence entre signature et image
int verifSign(char* img, int* sLgn, int* sCol, int dim);
Paramètres :
img: Image à analyser.dim: Dimension de l’image.sLgn: Signature des lignes de l’image.sCol: Signature des colonnes de l’image.
Valeur de retour : vrai (1) si la signature correspond à l’image, faux (0) sinon.
Génération d’une image aléatoire
void genRandImage(char* img, int dim);
Paramètres :
img: Tableau de destination de l’image à produiredim: Dimension de l’image à produire.
Recherche d’une image compatible avec une signature
int rechercheRandom(char* img, int dim, int* sLgn, int* sCol, long nEssais);
Paramètres :
img: Tableau de destination de l’image à produire.dim: Dimension de l’image.sLgn: Signature des lignes de l’image.sCol: Signature des colonnes de l’image.nEssais: nombre maximum d’essais autorisé.
Valeur de retour : -1 si aucune image compatible avec la signature n’a été trouvée, sinon le nombre d’essais réalisés pour trouver une image compatible.
Dans le cas où la valeur de retour est positive, l’image trouvée est placée dans le tableau désigné par le paramètre img.
Exemple d’utilisation
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;
}
2. Création d’une image à partir d’une chaîne
Vous devez définir la fonction…
void str2img(char* str, char* img);
…qui convertit une chaîne de caractère en image.
La chaîne doit comporter autant de caractères qu’il y a de pixels dans l’image à produire. Les espaces de la chaînes représentent les pixels éteints. Tout autre caractère représente un pixel allumé. Voici un exemple d’utilisation.
int dim = 8;
char* str =
" ###### "
"## ##"
"## ##"
" #######"
" ##"
"## ##"
" ###### "
" ";
char img[dim*dim];
str2img(str,img);
afficheImage(img,dim);
Le résultat attendu est :
XX XX XX XX XX XX
XX XX XX XX
XX XX XX XX
XX XX XX XX XX XX XX
XX XX
XX XX XX XX
XX XX XX XX XX XX
Les fragments de chaînes placés les uns sous les autres dans le code source sont interprétés par le compilateur C comme une unique chaîne.
3. Création de la signature d’une image
Les deux fonctions à implémenter permettent de produire la signature d’une image connue. Cette signature pourra servir à tester une fonction de recherche d’une image compatible avec une signature.
Affichage d’une signature ligne ou colonne
Vous devez définir une fonction d’affichage d’une signature ligne ou d’une signature colonne qui affiche simplement les valeurs de cette signature. Cette fonction servira uniquement lors des tests des deux fonction suivantes. Elle ne fait rien d’autre que d’afficher les valeurs d’un tableau d’entier.
void afficheSign(int* sign, int dim);
Paramètres :
sign: Une signature ligne ou colonne.dim: La dimension de l’image dontsignest la signature.
Création d’une signature ligne
Vous devez définir la fonction suivante qui permet de produire la signature des lignes d’une image. Vous devez également tester cette fonction, par exemple avec l’image représentant le chiffre 9 ayant servi à tester la fonction de conversion de chaîne en image.
void creeSignL(char* img, int dim, int* signL);
Paramètres :
img: Une image.dim: La dimension de l’image.signL: Le tableau dans lequel la signature des lignes doit être placée.
Création d’une signature colonne
Vous devez définir la fonction suivante qui permet de produire la signature des colonnes d’une image. Vous devez également tester cette fonction, par exemple avec l’image représentant le chiffre 9 ayant servi à tester la fonction de conversion de chaîne en image.
void creeSignC(char* img, int dim, int* signC);
Paramètres :
img: Une image.dim: La dimension de l’image.signC: Le tableau dans lequel la signature des colonnes doit être placée.
4. Recherche efficace d’une image
Si vous produisez la signature d’une image de 8 x 8 telle que celle donnée précédemment en exemple et si vous utilisez la fonction de reconstruction d’image (recherche d’une image compatible avec une signature) du TP précédent (voir solution du TP3), vous constaterez que la recherche échoue systématiquement, même avec 10 millions ou 100 millions d’essais. En effet, le nombre d’images différentes de 8 x 8 pixels est \(2^{64}\), soit de l’ordre de 20 milliards de milliards. Plusieurs images sont compatibles avec une même signature, mais pas suffisamment pour permettre à une recherche au hasard ou par force brute de trouver une image compatible avec un temps d’exécution raisonnable.
Pour rechercher plus rapidement une image compatible avec une signature de référence donnée, nous allons utiliser la recherche locale stochastique. Nous implémenterons un algorithme qui exploite une fonction attribuant un score à toute image.
Un exemple d’algorithme de recherche locale stochastique
Le score d’une image \(I\) de dimension \(n\) sera calculé de la manière suivante.
On note \(R = (R^L_1,…,R^L_n,R^C_1,…,R^C_n)\) la signature de référence, dans laquelle les valeurs \(R^L_1,…,R^L_n\) sont les nombres de pixels allumés sur les lignes et les valeurs \(R^C_1,…,R^C_n\) sont les nombres de pixels allumés sur le colonnes.
On note \(S = (S^L_1,…,S^L_n,S^C_1,…,S^C_n)\) la signature de l’image \(I\).
Le score de \(I\) est : $\sum_{i=1}^n|S^L_i – R^L_i| + \sum_{i=1}^n|S^C_i – R^C_i|$
Le score \(I\) est donc la somme des valeurs absolues des différences entre les valeurs des signatures lignes et colonnes de \(I\) et les valeurs des signatures lignes et colonnes de référence. Plus la signature de \(I\) "ressemble" à la signature de référence, plus le score est petit. Le score de \(I\) vaut 0 si et seulement si sa signature est identique à la signature de référence.
La recherche en elle même se déroule de la manière suivante :
- Une image aléatoire initiale
imgest produite. Le score de cette image est calculé et placé dans une variablescore. La valeur de cette variable est appelée score courant. - Une succession de transitions est réalisée jusqu’à ce que la variable score ait la valeur 0 ou qu’un nombre maximum de transitions, fixé à l’avance, soit atteint.
Voici en quoi consiste chaque transition :
- Une petite modification aléatoire est réalisée. Par exemple, l’état d’un pixel tiré au hasard est modifié. S’il était allumé on l’éteint, sinon on l’allume.
- Le nouveau score de l’image modifiée est calculé.
- Si le nouveau score est supérieur au score courant, la modification de l’image est annulée, sinon la variable
scoreest mise à jour avec le nouveau score.
Les fonctions à implémenter
Calcul du score
int getScore(char* img, int dim, int* sL, int* sC);
Paramètres :
img: Image dont on veut calculer le score.dim: Dimension de l’image.sL: Signature de référence pour les lignes.sC: Signature de référence pour les colonnes.
Valeur de retour : Le score de l’image.
Modification de l’image
Les deux fonctions suivantes utilisent une variable globale qui contient la position du pixel modifié dans le tableau à une dimension représentant l’image. Cette information est utilisée pour annuler la modification en cas de besoin. Tester ces fonctions avant de passer à l’étape d’implémentation de la fonction de recherche locale stochastique est une très bonne idée pour éviter un cumul d’erreurs qui rendrait la mise au point du programme très difficile.
int PosModif;
La fonction suivante permet de modifier un pixel de l’image choisi au aléatoirement.
void modifImage(char* img, int dim);
Paramètres :
img: Image à modifier.dim: Dimension de l’image.
La fonction suivante permet d’annuler la dernière modification faite par le dernier appel à la fonction modifImage.
void annuleModif(char* img)
Paramètre :
img: Image à modifier.
La dimension de l’image n’est pas utile car la variable globale PosModif contient l’indice du pixel à modifier dans le tableau désigné par le paramètre img.
Recherche d’une image compatible avec une signature donnée
int rechercheLoc(char* img, int dim, int* sL, int* sC, long nEssais);
Paramètres :
img: Tableau dans lequel l’image trouvée (si applicable) sera placée.dim: Dimension de l’image recherchée.sL: Signature de référence pour les lignes.sC: Signature de référence pour les colonnes.nEssais: Nombre maximum de transitions autorisé.
Valeur de retour : 1 si une image compatible a été trouvée, sinon 0.
Si la valeur de retour est 1, on récupère l’image trouvée dans le tableau img.
Vous devez tester cette fonction. Pour la mise au point, vous pouvez ajouter des affichages du score, réalisé par exemple à chaque diminution de sa valeur.
Approfondissement
Cette partie s’adresse uniquement aux personnes qui souhaitent approfondir le sujet et qui ont le temps de le faire.
Vous avez dû constater que les images obtenues dans la partie précédente sont décevantes parce qu’elles ne ressemblent pas à l’image utilisée pour produire la signature de référence. L’origine de ce problème est qu’une signature ligne / colonne ne contient pas suffisamment d’information pour reconstituer une image ayant une certaine ressemblance avec celle utilisée pour produire la signature de référence.
Pour avoir des résultats plus intéressants, il faut utiliser une signature prenant en compte les lignes, les colonnes, mais aussi les diagonales de l’image à reconstituer. Voici un exemple avec une image de 3 x 3, qui se généralise à n’importe quelle dimension.

Le challenge est de développer une application permettant de produire des signatures avec diagonales et de rechercher des images compatibles.
Pour éviter de manipuler 4 tableaux pour une signature complète, il serait judicieux de revoir le format des signatures de manière à placer les valeurs relatives aux lignes, colonnes et diagonales dans un même tableau.