TP25 : tableaux bidimensionnels en `C` et détection de contours

Rappel: compilez avec le plus d’options possibles, par exemple -Wall -Wno-unused -pedantic -Werror -Wextra.

Révisions sur les tableaux et les pointeurs

On sait qu’en C les tableaux statiques et les pointeurs alloués par malloc ne se trouvent pas dans la même zone mémoire. Ainsi l’exécution du programme dim1a.c suivant:

int main(void){
  int *t0 = (int *)malloc(3*sizeof(int));
  int t1[] = {1,2,3};
  int t2[3];
  int *t3 = (int *)malloc(3*sizeof(int));

  t0[0] = 4;
  t1[0] = 5;
  t2[0] = 6;
  t3[0] = 7;

  printf("t0 : %p\nt1 : %p\nt2 : %p\nt3 : %p\n", (void *)t0, (void *)t1, (void *)t2, (void *)t3);
  
  return 0;
}

permet de constater ce phénomène. Vous pouvez aussi exécuter le programme sur C tutor.

On a vu que les en-têtes suivantes de fonctions sont complètement équivalentes:

void fp(int *t);
void ft(int t[]);

et qu’on peut donner t0, t1, t2 ou t3 en argument à ces deux fonctions sans problème.

On a aussi évoqué le fait que les adresses des cases d’un tableau (statique ou alloué avec malloc) sont consécutives (en laissant la place pour les données bien sûr), ce qu’on peut constater avec le programme dim1b.c:

/* dans la vraie vie il faudrait faire un tableau avec toutes les
adresses et une fonction intermédiaire, mais le but de ce TP étant
de mieux comprendre les tableaux 2D, je m'abstiens.
*/
int main(void){
  int *t0 = (int *)malloc(3*sizeof(int));
  int t1[] = {1,2,3};
  int t2[3];
  int *t3 = (int *)malloc(3*sizeof(int));

  printf("t0 :  ");
  for(int i=0; i<3; i=i+1){
    printf("%p  ", (void *)&t0[i]);
  }
  printf("\n\n");

  printf("t1 :  ");
  for(int i=0; i<3; i=i+1){
    printf("%p  ", (void *)&t1[i]);
  }
  printf("\n\n");

  printf("t2 :  ");
  for(int i=0; i<3; i=i+1){
    printf("%p  ", (void *)&t2[i]);
  }
  printf("\n\n");

  printf("t3 :  ");
  for(int i=0; i<3; i=i+1){
    printf("%p  ", (void *)&t3[i]);
  }
  printf("\n\n");

  return 0;
}

Que se passe-t-il en dimension 2 ? Les effets en mémoire des déclarations suivantes sont-elles fondamentatement différentes ?

  int **tt0 = (int **)malloc(3*sizeof(int *));
  int *tt1[3];
  int tt2[3][2];
  int tt3[][2] = { {1,2},{3,4},{5,6} };

  for(int i=0; i<3; i=i+1){
    tt0[i] = (int *)malloc(2*sizeof(int));
    tt1[i] = (int *)malloc(2*sizeof(int));
  }

En adaptant dim1a.c, affichez les adresses de tt0, tt1, tt2, puis les adresses des trois sous-tableaux de chacun.

Exécutez votre programme sur C tutor pour comprendre comment sont réparties les données.

Affichez les adresses des deux cases de chacun des trois sous-tableaux de tt0, puis de ceux de tt1, puis de ceux de tt2.

Regardez de plus près les adresses de t[0][1] et t[1][0] (pour t prenant les valeurs tt0, tt1, tt2et tt3). Que remarquez-vous ? Que pouvez-vous conclure sur la façon dont les tableaux tt2 et tt3 sont rangés en mémoire ?

Regardons maintenant ce qui se passe avec les fonctions.

On considère les quatre fonctions suivantes disponibles dans le fichier dim2b.c:

void fpp(int **t){
  printf("fpp\n");
}

void fpt(int *t[]){
  printf("fpt\n");
}

void ftt1(int t[3][2]){
  printf("ftt1\n");
}

void ftt2(int t[][2]){
  printf("ftt2\n");
}

Essayez d’invoquer ces fonctions avec tt0, tt1, tt2 et tt3 comme argument. Faites le bilan de ce qui est possible et de ce qui ne l’est pas.

Bien sûr, il faut garder en tête qu’une fonction ne ne peut pas renvoyer une adresse dans sa pile d’appel, puisqu’ à la sortie de l’appel cet adresse n’a plus de sens. En revanche, rien n’interdit de transmettre à un appel de fonction une adresse locale, l’appel ayant alors la possibilité de modifier le contenu à cette adresse.

Contour d’image

Dans ce qui suit, je vais utiliser des variables déclarées const comme longueurs de tableaux statiques au lieu de macro définies avec #define. En fait ce sont du coup des VLA - variable length array, qui sont donc explicitement hors programme. Mais un des concours a utilisé ça dans un énoncé. Au moins vous l’aurez vu une fois.

Par dérivée

Le but ici est de partir d’une image au format pgm ascii de taille 400x600 (cette image) et d’en extraire le contour (sous forme d’une image de même dimension et au même format, ne contenant que du noir et du blanc).

Par exemple l’image

permet d’obtenir le contour

Le principe pour trouver le contour d’une image, est de repérer les points dont la couleur varie particulièrement par rapport aux couleurs des voisins.

Pour cela, on regarde la variation par rapport au voisin du dessous et au voisin de droite (en fait par rapport au voisin obtenu en décrémentant l’abscisse et au voisin obtenu en décrémentant l’ordonnée, peu importe l’orientation de l’image).

Le but est d’écrire les fonctions derive et seuil déclarées dans le fichier contours.h de façon à pouvoir exécuter la fonction principale contenue dans main.c.

Pour derive: la valeur obtenue pour le pixel $(x,y)$ est $\sqrt{\bigl(I(x,y)-I(x-1,y)\bigr)^2+\bigl(I(x,y)-I(x,y-1)\bigr)^2}$ (quand cela a un sens).

La fonction seuil permet ensuite de modifier l’image transmise en mettant 0 pour les valeurs inférieures au seuil et 1 pour les autres (dans l’exemple j’ai pris un seuil de 4000).

Par filtres plus perfectionnés

Il existe des opérateurs permettant de détecter les contours de façon un peu plus fine, en variant les directions considérées. Ils s’écrivent tous sous forme de matrice 3x3 noté $f$ et s’appliquent sous forme de produit de convolution:

$\sum_{u=-1}^{1} \sum_{v=-1}^{1} f(u,v)\times I\bigl(x-u,y-v\bigr)$

(Il faut bien entendu faire attention aux bords.)

Écrire une fonction qui prend pour paramètre une image source sous la forme d’un tableau d’entiers de taille hautxlarg, un filtre de taille 3x3, et une image destination sous la forme d’un tableau d’entiers de taille hautxlarg et remplit l’image destination avec le produit de convolution.

Vous pouvez faire des tentatives avec les filtres suivants: