====== 4 couleurs ======

===== Énoncé du problème =====

  * 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.

== Exemple ==

Cette carte

{{ .:carte.png?direct&400 |}}

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

{{ .:carte_colored.png?direct&400 |}}

===== Ingrédients nécessaires =====

  - Lire le contenu du fichier,
  - identifier les zones,
  - identifier les relations de voisinage entre les zones,
  - choisir une couleur pour chaque zone,
  - produire le nouveau fichier avec les zones coloriées


==== Bibliothèque utiles ====

<Code python>
import matplotlib.image as mpimg
import numpy as np
</Code>


==== Lecture du fichier image ====

Je propose le module suivant

<Code python>
# 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
</Code>

==== Écriture du fichier image ====
<Code python>
def saveimage(img, filename):
    '''
    img: tableau numpy contant l'image en RGB
    filename: nom du fichier à créer
    '''
    mpimg.imsave(filename, img)
</Code>

==== Manipulations de tableau numpy ====

<Code python>
# 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
</Code>

==== Détecter zone ====

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 :

<Code:none linenums>
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
</Code>

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]%%''.


==== Détecter voisinage ====

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 :

<Code:none linenums>
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
</Code>

== Avec numpy ==

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

<Code python>
zz = np.copy(z)
</Code>

Le parcours des pixels frontières aussi :

<Code python>
for line, col in np.argwhere(z == 0):
    p = z[line, col]
    ...
</Code>

==== Création du graphe et coloration ====

Utilisez le [[nsi:modules:graph|module graph]] que nous avons implémenté en cours d'année.