• Soit une carte donnée sous forme d'une image *.png représentant, sur un fond blanc, des zones fermées délimitées par une frontière noire. Frontière et fond sont bien contrastés.
• On se donne 4 couleurs.
• On souhaite colorier les zones fermées en utilisant ces couleurs en n'utilisant jamais la même couleur pour deux zones ayant une frontière en commun.
• En fin de processus, notre programme doit fournir une copie du *.png original avec les zones coloriées.

Cette carte

pourrait aboutir, par exemple, à ce résultat :

1. Lire le contenu du fichier,
2. identifier les zones,
3. identifier les relations de voisinage entre les zones,
4. choisir une couleur pour chaque zone,
5. produire le nouveau fichier avec les zones coloriées

import matplotlib.image as mpimg
import numpy as np

Je propose le module suivant

# récupérer le fichier image
def readFile(filename):
    '''
    filename: nom du fichier
    renvoie un tableau numpy contenant l'image.
    img[line,col,c] représente l'octet pour le pixel définit par sa position et canal
      de couleur c (0 pour R, 1 pour G et 2 pour B)
    '''
    img = mpimg.imread(filename)
    if img.dtype == np.float32:
        # Rectifie au cas où le résultat n'aurait pas le
        # type voulu
        img = (img * 255).astype(np.uint8)
    # l'image est une grille constituée
    # de nombres entiers codés sur 8 bits
    return img

def saveImage(img, filename):
    '''
    img: tableau numpy contant l'image en RGB
    filename: nom du fichier à créer
    '''
    mpimg.imsave(filename, img)

# avec img image chargée
>>> img.shape
(200,300,3)
# tuple représentant les dimensions du tableau
>>> img.mean(axis=2)
# produit une copie de img, avec un seul canal égal à la moyenne des 3
# on peut faire de même avec min, max...
>>> img.mean(axis=2).astype(int)
# même chose mais avec les résultats transformé en int
>>> A = np.zeros((2,3))
# crée un tableau numpy A de taille 2 x 3 rempli de 0
>>> A[A>2] = 10
# toutes les cellules du tableau A respectant la condition sont modifiées
>>> np.argwhere(A>2)
# renvoie un tableau des coordonnées [line,col] respectant la condition
>>> B = np.copy(A)
# B est une copie de A

Il existe de nombreuses possibilités. Je propose de produire un tableau au même dimensions que l'image d'origine et qui pour chaque position (ligne, colonne) donne un numéro identifiant la zone. L'identifant zéro sera réservé aux pixels sans zone (les frontières).

Je propose l'algorithme suivant :

FONCTION zones:
  Entrée: tableau image
  sortie: tableau des zones, tableau des ids utilisés
  
  créer tableau z plein de 0 aux dimensions de image
  créer tableau ids vide
  marquer qu'une nouvelle zone commence
  POUR chaque ligne:
      POUR chaque colonne
          lire p, le pixel de image en ligne et colonne
          SI p est pixel frontière:
              marquer qu'une nouvelle zone commence
              passer tout de suite au pixel suivant
          S'il est marqué qu'une nouvelle zone commence:
              choisir un nouvel identifiant de zone
              ajouter cet identifiant à ids
              marqué que l'on ne commence plus une nouvelle zone
          affecter l'identifiant de zone en cours dans z à la ligne et colonne en cours
          SI la ligne courante n'est pas la première,
              soit i l'identifiant du pixel courant,
              soit j l'identifiant du pixel du dessus,
              Si j != 0 et j!= i:
                  remplacer dans z toutes les occurrences de i par j
                  identifiant courant devient j
                  supprimer i des identifiants de ids
        Fin de la ligne donc marquer qu'une nouvelle zone commence
    RENVOYER z et ids

Notez que de nouveaux identifiants sont créés à chaque passage de frontière ou à chaque nouvelle ligne et des identifiants sont abandonnés quand on réalise que deux identifiants couvrent des zones identiques. Il s'en suit que les identifiant ne seront pas forcément consécutifs. Par exemple, selon la carte, on pourrait obtenir ids = [1, 2, 5, 9, 11].

Il s'agit de créer un graphe dont les nœuds sont les zones et où les arêtes représentent un voisinage entre deux zones. Je propose l'algorithme suivant qui consiste à faire se dilater les zones jusqu'à ce qu'elles se touchent :

FONCTIONS voisinages:
  Entrée: tableau z des zones, identifiants des zones de z
  sortie: graphe des voisinages
  
  Créer un graphe ayant pour sommets les identifiants des zones de z
  Créer zz un clone de z,
  TANT QUE il existe des pixels frontière dans z:
      POUR chaque pixel de frontière de z:
          notons p ce pixel,
          SI p a plusieurs pixels adjacents dans z qui ne sont pas des frontières:
             ajouter des relations de voisinage selon les cas
             (nécessite un peu de réflexion:
                il faut chercher 2 pixel adjacents, situés à 90°, par ex au-dessus
                et à gauche, et d'identifiants > 0 et différents)
          SI p a au moins un pixel adjacent q dans z qui a n'est pas une frontière:
              attribuer à la position ligne,colonne dans zz l'identifiant de q
              choisir le premier trouver s'il yen a plusieurs
              (ce choix peut se faire de différentes manières :
                - avec un ordre de priorité, toujours le même,
                - au hasard
                - chercher le majoritaire
              )
      fin d'un parcours de l'image. Pour préparer le suivant,
      on place zz dans z et on crée un nouveau clone zz de z
  RENVOYER le graphe

La création de copie est très simple :

zz = np.copy(z)

Le parcours des pixels frontières aussi :

for line, col in np.argwhere(z == 0):
    p = z[line, col]
    ...

Utilisez le module graph que nous avons implémenté en cours d'année.