{"id":221,"date":"2022-02-11T20:31:30","date_gmt":"2022-02-11T20:31:30","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=221"},"modified":"2022-02-11T20:31:36","modified_gmt":"2022-02-11T20:31:36","slug":"c-et-c-tp4","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/c-et-c-tp4\/","title":{"rendered":"C et C++ TP4"},"content":{"rendered":"<p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1><a id=\"tomographie-discr%C3%A8te-partie-2\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Tomographie discr\u00e8te &#8211; partie 2<\/h1>\n<p>Pour aborder cette partie, il faut ma\u00eetriser la partie pr\u00e9c\u00e9dente \u00e0 l&rsquo;exception de la recherche par force brute, soit en ayant vous-m\u00eame trouv\u00e9 les solutions, soit en ayant \u00e9tudi\u00e9 et compris la solution qui vous a \u00e9t\u00e9 fournie.<\/p>\n<h2><a id=\"1-rappels-sur-les-briques-logicielles-disponibles\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>1. Rappels sur les briques logicielles disponibles<\/h2>\n<p>Tous les \u00e9l\u00e9ments repris ici sont fournis dans le corrig\u00e9 du TP3 disponible sur <a href=\"https:\/\/padlet.com\/olivier_bailleux\/info4A\">le padlet<\/a> de l&rsquo;unit\u00e9 d&rsquo;enseignement.<\/p>\n<h3><a id=\"structures-de-donn%C3%A9es\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Structures de donn\u00e9es<\/h3>\n<h4><a id=\"images\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Images<\/h4>\n<p>Une image, c&rsquo;est \u00e0 dire une grille carr\u00e9e peupl\u00e9e de pixels allum\u00e9s et de pixels \u00e9teints, est repr\u00e9sent\u00e9e concr\u00e8tement par un tableau \u00e0 une dimension comme indiqu\u00e9 sur un exemple par la figure ci-dessous.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/1-3.png\" alt=\"1\" \/><\/p>\n<p>On appelle dimension d&rsquo;une image le nombre de cases, ou pixels, d&rsquo;une ligne ou d&rsquo;une colonne. L&rsquo;image ci-dessus a pour dimension 3.<\/p>\n<p>Le tableau repr\u00e9sentant une image de dimension 3 dont tous les pixels sont \u00e9teints peut se d\u00e9clarer de la mani\u00e8re suivante :<\/p>\n<pre><code class=\"language-C\">int dim = 3;\nchar image[dim*dim] = {0};\n<\/code><\/pre>\n<h4><a id=\"signatures\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Signatures<\/h4>\n<p>La signature d&rsquo;une image de dimension <code>dim<\/code> est constitu\u00e9e de deux listes de <code>dim<\/code> entiers repr\u00e9sent\u00e9es par des tableaux de <code>int<\/code>.<\/p>\n<ul>\n<li>La premi\u00e8re liste donne les nombres de pixels allum\u00e9s sur les lignes de l&rsquo;image. Dans l&rsquo;exemple de l&rsquo;image de dimension 3 de la figure pr\u00e9c\u00e9dente, ces nombres sont 1, 2, 0.<\/li>\n<li>La deuxi\u00e8me liste donne les nombres de pixels \u00e9teints sur les colonnes de l&rsquo;image. Dans l&rsquo;exemple de la figure pr\u00e9c\u00e9dente, ces nombres sont 1, 1, 1.<\/li>\n<\/ul>\n<p>Les tableaux repr\u00e9sentant la signature de l&rsquo;image de la figure pr\u00e9c\u00e9dente peuvent se d\u00e9clarer de la mani\u00e8re suivante (on suppose que la variable <code>dim<\/code> a \u00e9t\u00e9 pr\u00e9c\u00e9demment d\u00e9clar\u00e9e et initialis\u00e9e \u00e0 3) :<\/p>\n<pre><code class=\"language-C\">int sL[dim] = {1,2,0}; \/\/ Signature lignes\nint sC[dim] = {1,1,1}; \/\/ Signature colonnes\n<\/code><\/pre>\n<h3><a id=\"fonctions-disponibles\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Fonctions disponibles<\/h3>\n<p>Les fonctions suivantes sont d\u00e9j\u00e0 impl\u00e9ment\u00e9es (voir corrig\u00e9 du TP3).<\/p>\n<h4><a id=\"lecture-d-un-pixel\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Lecture d&rsquo;un pixel<\/h4>\n<pre><code class=\"language-C\">int litPixel(char* img, int dim, int lgn, int col);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image dans laquelle se trouve le pixel \u00e0 lire.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>lgn<\/code> : Num\u00e9ro de la ligne du pixel (entre 0 et <code>dim-1<\/code>).<\/li>\n<li><code>col<\/code> : Num\u00e9ro de la colonne du pixel (entre 0 et <code>dim-1<\/code>).<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> 0 si le pixel est \u00e9teint, 1 s&rsquo;il est allum\u00e9.<\/p>\n<h4><a id=\"affichage-d-une-image\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Affichage d&rsquo;une image<\/h4>\n<pre><code class=\"language-C\">void afficheImage(char* img, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 afficher.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<\/ul>\n<h4><a id=\"nombre-de-pixels-allum%C3%A9s-sur-une-ligne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Nombre de pixels allum\u00e9s sur une ligne<\/h4>\n<pre><code class=\"language-C\">int compteLigne(char* img, int lgn, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 analyser.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>lgn<\/code> : Num\u00e9ro de la ligne (entre 0 et <code>dim-1<\/code>).<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> Nombre de pixels allum\u00e9s sur la ligne <code>lgn<\/code>.<\/p>\n<h4><a id=\"nombre-de-pixels-allum%C3%A9s-sur-une-colonne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Nombre de pixels allum\u00e9s sur une colonne<\/h4>\n<pre><code class=\"language-C\">int compteCol(char* img, int col, int dim)\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 analyser.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>col<\/code> : Num\u00e9ro de la colonne (entre 0 et <code>dim-1<\/code>).<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> Nombre de pixels allum\u00e9s sur la colonne <code>col<\/code>.<\/p>\n<h4><a id=\"v%C3%A9rification-de-la-coh%C3%A9rence-entre-signature-et-image\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>V\u00e9rification de la coh\u00e9rence entre signature et image<\/h4>\n<pre><code class=\"language-C\">int verifSign(char* img, int* sLgn, int* sCol, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 analyser.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>sLgn<\/code> : Signature des lignes de l&rsquo;image.<\/li>\n<li><code>sCol<\/code> : Signature des colonnes de l&rsquo;image.<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> vrai (1) si la signature correspond \u00e0 l&rsquo;image, faux (0) sinon.<\/p>\n<h4><a id=\"g%C3%A9n%C3%A9ration-d-une-image-al%C3%A9atoire\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>G\u00e9n\u00e9ration d&rsquo;une image al\u00e9atoire<\/h4>\n<pre><code class=\"language-C\">void genRandImage(char* img, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Tableau de destination de l&rsquo;image \u00e0 produire<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image \u00e0 produire.<\/li>\n<\/ul>\n<h4><a id=\"recherche-d-une-image-compatible-avec-une-signature\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Recherche d&rsquo;une image compatible avec une signature<\/h4>\n<pre><code class=\"language-C\">int rechercheRandom(char* img, int dim, int* sLgn, int* sCol, long nEssais);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Tableau de destination de l&rsquo;image \u00e0 produire.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>sLgn<\/code> : Signature des lignes de l&rsquo;image.<\/li>\n<li><code>sCol<\/code> : Signature des colonnes de l&rsquo;image.<\/li>\n<li><code>nEssais<\/code> : nombre maximum d&rsquo;essais autoris\u00e9.<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> -1 si aucune image compatible avec la signature n&rsquo;a \u00e9t\u00e9 trouv\u00e9e, sinon le nombre d&rsquo;essais r\u00e9alis\u00e9s pour trouver une image compatible.<\/p>\n<p>Dans le cas o\u00f9 la valeur de retour est positive, l&rsquo;image trouv\u00e9e est plac\u00e9e dans le tableau d\u00e9sign\u00e9 par le param\u00e8tre <code>img<\/code>.<\/p>\n<h3><a id=\"exemple-d-utilisation\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Exemple d&rsquo;utilisation<\/h3>\n<pre><code class=\"language-C\">int main()\n{\n    int dim = 4;\n    srand(time(NULL));\n    int sLignes[] = {3,3,2,3};\n    int sColonnes[] = {4,1,4,2}; \n    char image[dim*dim];\n    int n = rechercheRandom(image,dim,sLignes,sColonnes,100000);\n    if(n&gt;0)\n    {\n        printf(&quot;Image trouv\u00e9e en %d essais\\n\\n&quot;,n);\n        afficheImage(image, 4);\n    }\n    else\n    {\n        printf(&quot;Image non trouv\u00e9e\\n&quot;);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2><a id=\"2-cr%C3%A9ation-d-une-image%C3%A0-partir-d-une-cha%C3%AEne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>2. Cr\u00e9ation d&rsquo;une image \u00e0 partir d&rsquo;une cha\u00eene<\/h2>\n<p>Vous devez d\u00e9finir la fonction&#8230;<\/p>\n<pre><code class=\"language-C\">void str2img(char* str, char* img);\n<\/code><\/pre>\n<p>&#8230;qui convertit une cha\u00eene de caract\u00e8re en image.<\/p>\n<p>La cha\u00eene doit comporter autant de caract\u00e8res qu&rsquo;il y a de pixels dans l&rsquo;image \u00e0 produire. Les espaces de la cha\u00eenes repr\u00e9sentent les pixels \u00e9teints. Tout autre caract\u00e8re repr\u00e9sente un pixel allum\u00e9. Voici un exemple d&rsquo;utilisation.<\/p>\n<pre><code class=\"language-C\">    int dim = 8;\n    char* str =\n    &quot; ###### &quot;\n    &quot;##    ##&quot;\n    &quot;##    ##&quot;\n    &quot; #######&quot;\n    &quot;      ##&quot;\n    &quot;##    ##&quot;\n    &quot; ###### &quot;\n    &quot;        &quot;;\n    char img[dim*dim]; \n    str2img(str,img);\n    afficheImage(img,dim);\n<\/code><\/pre>\n<p>Le r\u00e9sultat attendu est :<\/p>\n<pre><code class=\"language-plain_text\">    XX XX XX XX XX XX   \n XX XX             XX XX\n XX XX             XX XX\n    XX XX XX XX XX XX XX\n                   XX XX\n XX XX             XX XX\n    XX XX XX XX XX XX  \n<\/code><\/pre>\n<p>Les fragments de cha\u00eenes plac\u00e9s les uns sous les autres dans le code source sont interpr\u00e9t\u00e9s par le compilateur C comme une unique cha\u00eene.<\/p>\n<h2><a id=\"3-cr%C3%A9ation-de-la-signature-d-une-image\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>3. Cr\u00e9ation de la signature d&rsquo;une image<\/h2>\n<p>Les deux fonctions \u00e0 impl\u00e9menter permettent de produire la signature d&rsquo;une image connue. Cette signature pourra servir \u00e0 tester une fonction de recherche d&rsquo;une image compatible avec une signature.<\/p>\n<h3><a id=\"affichage-d-une-signature-ligne-ou-colonne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Affichage d&rsquo;une signature ligne ou colonne<\/h3>\n<p>Vous devez d\u00e9finir une fonction d&rsquo;affichage d&rsquo;une signature ligne ou d&rsquo;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&rsquo;autre que d&rsquo;afficher les valeurs d&rsquo;un tableau d&rsquo;entier.<\/p>\n<pre><code class=\"language-C\">void afficheSign(int* sign, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>sign<\/code> : Une signature ligne ou colonne.<\/li>\n<li><code>dim<\/code> : La dimension de l&rsquo;image dont <code>sign<\/code> est la signature.<\/li>\n<\/ul>\n<h3><a id=\"cr%C3%A9ation-d-une-signature-ligne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Cr\u00e9ation d&rsquo;une signature ligne<\/h3>\n<p>Vous devez d\u00e9finir la fonction suivante qui permet de produire la signature des lignes d&rsquo;une image. Vous devez \u00e9galement tester cette fonction, par exemple avec l&rsquo;image repr\u00e9sentant le chiffre 9 ayant servi \u00e0 tester la fonction de conversion de cha\u00eene en image.<\/p>\n<pre><code class=\"language-C\">void creeSignL(char* img, int dim, int* signL);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Une image.<\/li>\n<li><code>dim<\/code> : La dimension de l&rsquo;image.<\/li>\n<li><code>signL<\/code> : Le tableau dans lequel la signature des lignes doit \u00eatre plac\u00e9e.<\/li>\n<\/ul>\n<h3><a id=\"cr%C3%A9ation-d-une-signature-colonne\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Cr\u00e9ation d&rsquo;une signature colonne<\/h3>\n<p>Vous devez d\u00e9finir la fonction suivante qui permet de produire la signature des colonnes d&rsquo;une image. Vous devez \u00e9galement tester cette fonction, par exemple avec l&rsquo;image repr\u00e9sentant le chiffre 9 ayant servi \u00e0 tester la fonction de conversion de cha\u00eene en image.<\/p>\n<pre><code class=\"language-C\">void creeSignC(char* img, int dim, int* signC);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Une image.<\/li>\n<li><code>dim<\/code> : La dimension de l&rsquo;image.<\/li>\n<li><code>signC<\/code> : Le tableau dans lequel la signature des colonnes doit \u00eatre plac\u00e9e.<\/li>\n<\/ul>\n<h2><a id=\"4-recherche-efficace-d-une-image\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>4. Recherche efficace d&rsquo;une image<\/h2>\n<p>Si vous produisez la signature d&rsquo;une image de 8 x 8 telle que celle donn\u00e9e pr\u00e9c\u00e9demment en exemple et si vous utilisez la fonction de reconstruction d&rsquo;image (recherche d&rsquo;une image compatible avec une signature) du TP pr\u00e9c\u00e9dent (voir solution du TP3), vous constaterez que la recherche \u00e9choue syst\u00e9matiquement, m\u00eame avec 10 millions ou 100 millions d&rsquo;essais. En effet, le nombre d&rsquo;images diff\u00e9rentes de 8 x 8 pixels est \\(2^{64}\\), soit de l&rsquo;ordre de 20 milliards de milliards. Plusieurs images sont compatibles avec une m\u00eame signature, mais pas suffisamment pour permettre \u00e0 une recherche au hasard ou par force brute de trouver  une image compatible avec un temps d&rsquo;ex\u00e9cution raisonnable.<\/p>\n<p>Pour rechercher plus rapidement une image compatible avec une signature de r\u00e9f\u00e9rence donn\u00e9e, nous allons utiliser la <strong>recherche locale stochastique<\/strong>. Nous impl\u00e9menterons un algorithme qui exploite une fonction attribuant un <strong>score<\/strong> \u00e0 toute image.<\/p>\n<h3><a id=\"un-exemple-d-algorithme-de-recherche-locale-stochastique\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Un exemple d&rsquo;algorithme de recherche locale stochastique<\/h3>\n<p>Le score d&rsquo;une image \\(I\\) de dimension \\(n\\) sera calcul\u00e9 de la mani\u00e8re suivante.<\/p>\n<p>On note \\(R = (R^L_1,&#8230;,R^L_n,R^C_1,&#8230;,R^C_n)\\) la signature de r\u00e9f\u00e9rence, dans laquelle les valeurs \\(R^L_1,&#8230;,R^L_n\\) sont les nombres de pixels allum\u00e9s sur les lignes et les valeurs \\(R^C_1,&#8230;,R^C_n\\) sont les nombres de pixels allum\u00e9s sur le colonnes.<\/p>\n<p>On note \\(S = (S^L_1,&#8230;,S^L_n,S^C_1,&#8230;,S^C_n)\\) la signature de l&rsquo;image \\(I\\).<\/p>\n<p>Le score de \\(I\\) est : $\\sum_{i=1}^n|S^L_i &#8211; R^L_i| + \\sum_{i=1}^n|S^C_i &#8211; R^C_i|$<\/p>\n<p>Le score \\(I\\) est donc la somme des valeurs absolues des diff\u00e9rences entre les valeurs des signatures lignes et colonnes de \\(I\\) et les valeurs des signatures lignes et colonnes de r\u00e9f\u00e9rence. Plus la signature de \\(I\\) &quot;ressemble&quot; \u00e0 la signature de r\u00e9f\u00e9rence, plus le score est petit. Le score de \\(I\\) vaut 0 si et seulement si sa signature est identique \u00e0 la signature de r\u00e9f\u00e9rence.<\/p>\n<p>La recherche en elle m\u00eame se d\u00e9roule de la mani\u00e8re suivante :<\/p>\n<ol>\n<li>Une image al\u00e9atoire initiale <code>img<\/code> est produite. Le score de cette image est calcul\u00e9 et plac\u00e9 dans une variable <code>score<\/code>. La valeur de cette variable est appel\u00e9e <strong>score courant<\/strong>.<\/li>\n<li>Une succession de <strong>transitions<\/strong> est r\u00e9alis\u00e9e jusqu&rsquo;\u00e0 ce que la variable score ait la valeur 0 ou qu&rsquo;un nombre maximum de transitions, fix\u00e9 \u00e0 l&rsquo;avance, soit atteint.<\/li>\n<\/ol>\n<p>Voici en quoi consiste chaque <strong>transition<\/strong> :<\/p>\n<ol>\n<li>Une petite modification al\u00e9atoire est r\u00e9alis\u00e9e. Par exemple, l&rsquo;\u00e9tat d&rsquo;un pixel tir\u00e9 au hasard est modifi\u00e9. S&rsquo;il \u00e9tait allum\u00e9 on l&rsquo;\u00e9teint, sinon on l&rsquo;allume.<\/li>\n<li>Le nouveau score de l&rsquo;image modifi\u00e9e est calcul\u00e9.<\/li>\n<li>Si le nouveau score est sup\u00e9rieur au score courant, la modification de l&rsquo;image est annul\u00e9e, sinon la variable <code>score<\/code> est mise \u00e0 jour avec le nouveau score.<\/li>\n<\/ol>\n<h3><a id=\"les-fonctions%C3%A0-impl%C3%A9menter\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Les fonctions \u00e0 impl\u00e9menter<\/h3>\n<h4><a id=\"calcul-du-score\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Calcul du score<\/h4>\n<pre><code class=\"language-C\">int getScore(char* img, int dim, int* sL, int* sC);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image dont on veut calculer le score.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<li><code>sL<\/code> : Signature de r\u00e9f\u00e9rence pour les lignes.<\/li>\n<li><code>sC<\/code> : Signature de r\u00e9f\u00e9rence pour les colonnes.<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> Le score de l&rsquo;image.<\/p>\n<h4><a id=\"modification-de-l-image\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Modification de l&rsquo;image<\/h4>\n<p>Les deux fonctions suivantes utilisent une variable globale qui contient la position du pixel modifi\u00e9 dans le tableau \u00e0 une dimension repr\u00e9sentant l&rsquo;image. Cette information est utilis\u00e9e pour annuler la modification en cas de besoin. Tester ces fonctions avant de passer \u00e0 l&rsquo;\u00e9tape d&rsquo;impl\u00e9mentation de la fonction de recherche locale stochastique est une tr\u00e8s bonne id\u00e9e pour \u00e9viter un cumul d&rsquo;erreurs qui rendrait la mise au point du programme tr\u00e8s difficile.<\/p>\n<pre><code class=\"language-C\">int PosModif;\n<\/code><\/pre>\n<p>La fonction suivante permet de modifier un pixel de l&rsquo;image choisi au al\u00e9atoirement.<\/p>\n<pre><code class=\"language-C\">void modifImage(char* img, int dim);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 modifier.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image.<\/li>\n<\/ul>\n<p>La fonction suivante permet d&rsquo;annuler la derni\u00e8re modification faite par le dernier appel \u00e0 la fonction <code>modifImage<\/code>.<\/p>\n<pre><code class=\"language-C\">void annuleModif(char* img)\n<\/code><\/pre>\n<p><strong>Param\u00e8tre :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Image \u00e0 modifier.<\/li>\n<\/ul>\n<p>La dimension de l&rsquo;image n&rsquo;est pas utile car la variable globale <code>PosModif<\/code> contient l&rsquo;indice du pixel \u00e0 modifier dans le tableau d\u00e9sign\u00e9 par le param\u00e8tre <code>img<\/code>.<\/p>\n<h4><a id=\"recherche-d-une-image-compatible-avec-une-signature-donn%C3%A9e\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Recherche d&rsquo;une image compatible avec une signature donn\u00e9e<\/h4>\n<pre><code class=\"language-C\">int rechercheLoc(char* img, int dim, int* sL, int* sC, long nEssais);\n<\/code><\/pre>\n<p><strong>Param\u00e8tres :<\/strong><\/p>\n<ul>\n<li><code>img<\/code> : Tableau dans lequel l&rsquo;image trouv\u00e9e (si applicable) sera plac\u00e9e.<\/li>\n<li><code>dim<\/code> : Dimension de l&rsquo;image recherch\u00e9e.<\/li>\n<li><code>sL<\/code> : Signature de r\u00e9f\u00e9rence pour les lignes.<\/li>\n<li><code>sC<\/code> : Signature de r\u00e9f\u00e9rence pour les colonnes.<\/li>\n<li><code>nEssais<\/code> : Nombre maximum de transitions autoris\u00e9.<\/li>\n<\/ul>\n<p><strong>Valeur de retour :<\/strong> 1 si une image compatible a \u00e9t\u00e9 trouv\u00e9e, sinon 0.<\/p>\n<p>Si la valeur de retour est 1, on r\u00e9cup\u00e8re l&rsquo;image trouv\u00e9e dans le tableau <code>img<\/code>.<\/p>\n<p>Vous devez tester cette fonction. Pour la mise au point, vous pouvez ajouter des affichages du score, r\u00e9alis\u00e9 par exemple \u00e0 chaque diminution de sa valeur.<\/p>\n<h2><a id=\"approfondissement\" class=\"anchor\" aria-hidden=\"true\"><span class=\"octicon octicon-link\"><\/span><\/a>Approfondissement<\/h2>\n<p>Cette partie s&rsquo;adresse uniquement aux personnes qui souhaitent approfondir le sujet et qui ont le temps de le faire.<\/p>\n<p>Vous avez d\u00fb constater que les images obtenues dans la partie pr\u00e9c\u00e9dente sont d\u00e9cevantes parce qu&rsquo;elles ne ressemblent pas \u00e0 l&rsquo;image utilis\u00e9e pour produire la signature de r\u00e9f\u00e9rence. L&rsquo;origine de ce probl\u00e8me est qu&rsquo;une signature ligne \/ colonne ne contient pas suffisamment d&rsquo;information pour reconstituer une image ayant une certaine ressemblance avec celle utilis\u00e9e pour produire la signature de r\u00e9f\u00e9rence.<\/p>\n<p>Pour avoir des r\u00e9sultats plus int\u00e9ressants, il faut utiliser une signature prenant en compte les lignes, les colonnes, mais aussi les diagonales de l&rsquo;image \u00e0 reconstituer. Voici un exemple avec une image de 3 x 3, qui se g\u00e9n\u00e9ralise \u00e0 n&rsquo;importe quelle dimension.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/02\/2-2.png\" alt=\"2\" \/><\/p>\n<p>Le challenge est de d\u00e9velopper une application permettant de produire des signatures avec diagonales et de rechercher des images compatibles.<\/p>\n<p>Pour \u00e9viter de manipuler 4 tableaux pour une signature compl\u00e8te, il serait judicieux de revoir le format des signatures de mani\u00e8re \u00e0 placer les valeurs relatives aux lignes, colonnes et diagonales dans un m\u00eame tableau.<\/p>\n<hr \/>\n","protected":false},"excerpt":{"rendered":"<p>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l&rsquo;universit\u00e9 de Bourgogne. Tomographie discr\u00e8te &#8211; partie 2 Pour aborder cette partie, il faut ma\u00eetriser la partie pr\u00e9c\u00e9dente \u00e0 l&rsquo;exception de la recherche par force brute, soit en ayant vous-m\u00eame trouv\u00e9 les solutions, soit en ayant \u00e9tudi\u00e9 et compris la solution qui vous a \u00e9t\u00e9 fournie. 1. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-221","post","type-post","status-publish","format-standard","hentry","category-c-et-cpp","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/221","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=221"}],"version-history":[{"count":1,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/221\/revisions"}],"predecessor-version":[{"id":222,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/221\/revisions\/222"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=221"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=221"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=221"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}