====== Labyrinthe sur une image ======

===== Présentation =====

Dans cet exercice, on souhaite trouver une solution pour un labyrinthe fourni sous forme d'un fichier image. Voici un exemple :

{{ laby.png?direct |}}

Sur cette image,
  * le fond est en blanc,
  * les murs en noir bien contrasté, 
  * la tache bleue est le départ,
  * la tache verte est l'arrivée

On souhaite produire une nouvelle image avec la solution tracée en rouge, par exemple :

{{ laby_sol.png?nolink |}}

===== Manipulation du fichier image =====

==== Bibliothèques ====

Pour résoudre ce problème nous devrons ouvrir le fichier image et le manipuler.
Nous allons pour cela utiliser des modules, notamment le fameux ''%%numpy%%'', l'une des plus importantes de python.

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

> Dans les deux lignes, le mot-clé ''%%as%%'' permet de donner un //alias//. Par exemple en ligne 2, ''%%as np%%'' permettra d'écrire seulement ''%%np%%'' dans la suite au lieu de ''%%numpy%%''.

==== Ouverture ====

<Code python linenums>
# récupérer le fichier image
def read_image_file(filename):
    '''
    filename: nom du fichier
    renvoie un tableau numpy contenant l'image.
    img[line, col, :] représente un pixel.
      ce pixel est codé sur 3 octets de couleur RGB
    '''
    img = mpimg.imread(filename)
    if img.dtype == np.float32:
        # il peut arriver que chaque canal pour chaque pixel
        # soit codé par un flottant entre 0 et 1
        # au lieu d'un entier entre 0 et 255
        # Ce if est là pour tenir compte de cette éventualité
        img = (img * 255).astype(np.uint8)
    # Suite à cela, img contient un tableau numpy
    # ou chaque pixel contient un tableau de 3 canaux de couleurs
    return img
</Code>

==== Coordonnées des départs et arrivée ====

Numpy est une bibliothèque très puissante qui est de plus codé en [[:langages:C|C]] ce qui lui permet d'être performante. On a donc intérêt à utiliser les fonctions intégrées de numpy. Mais le but ici n'est pas de maîtriser l'utilisation de numpy, je vous donne donc quelques fonctions.

<Code python>
def coords_centre(img, rgb):
    '''
    img: le tableau numpy représentant l'image
    rgb: une couleur sous forme d'un triplet (R,G,B)
    renvoie les coordonnées du centre de gravité de
      l'ensemble des pixels ayant la couleur demandée
    '''
    pixels_color = np.all(img == rgb, axis=2)
    # pixels_color est un tableaux au mêmes dimensions
    # que img et ou pour chaque pixel on a True ou False
    # True si le pixel a la bonne couleur dans img
    coords = np.where(pixels_color)
    # coords est le tableau des paires de coordonnées
    # pour lesquelles pixels_color est True
    # donc les coordonnées des points ayant la bonne couleur
    centre = np.mean(coords, axis=1).astype(int)
    # moyenne des coordonnées donc centre de gravité
    # arrondi en entiers
    return centre
</Code>

Cette fonction étant définie, on pourra écrire :

<Code python>
depart = coords_centre(img, (0,0,255))
arrivee = coords_centre(img, (0,255,0))
</Code>
    
==== Carte des murs ====

Les pixels noirs ou presque noirs correspondent aux murs. On va produire un tableau dans lequel les pixels prennent la valeur True ou False, True s'il s'agit d'un mur.

<Code python>
def get_walls(img):
    '''
    img: le tableau numpy représentant l'image
    renvoie tableau numpy de même taille que l'image d'origine
      pour lequel les pixels correspondant à un mur sont à True
      et les autres à False
    '''
    # calcule de la somme des 3 canaux
    S = np.sum(img, axis=2)
    # on retient comme suffisamment noirs pour être des murs
    # les pixels dont la somme des canaux est < 60
    return S < 60
</Code>

Suite à la définition de cette fonction,

<Code python>
>>> walls = get_walls(img)
>>> walls[45,36]
False
# signifie qu'il n'y a pas un mur en ligne 45, col 36
>>> walls[59,36]
True
# en revanche, il y a un mur en ligne 59, col 36
</Code>

==== Produire le fichier image ====

Supposons que vous ayez pu produire le tableau ''%%path%%'' qui serait un tableau de paires de coordonnées ''%%(ligne, colonne)%%'' et que vous vouliez mettre les pixels correspondant en rouge puis sauvegarder. Voici la fonction :

<Code python>
def save_path(img, path, filename):
    '''
    img: tableau numpy de l'image originale
    path: tableau de paires de coordonnées
    filename: nom du fichier image à créer
    '''
    r, g, b = 255, 0, 0 # couleur rouge
    for ligne, colonne in path:
        img[ligne, colonne, 0] = r
        img[ligne, colonne, 1] = g
        img[ligne, colonne, 2] = b
    mpimg.imsave(filename, img)
</Code>

===== Algorithme proposé =====

Nous avons défini ci-dessus

  * de quoi charger le fichier image,
  * de quoi savoir si tel pixel est un mur,
  * de quoi obtenir les coordonnées du départ et de l'arrivée
  * de quoi sauvegarder le chemin trouvé dans une image

Il nous reste à trouver ce chemin.

Je propose d'explorer une solution type marcheur ivre :
  - initiez votre chemin par le point de départ,
  - à chaque nouveau pas, depuis le pixel où vous êtes, faites un pas au hasard vers un pixel voisin qui n'est pas un mur,
  - ajoutez ce pixel au chemin.

Dans un labyrinthe de petite taille, cette technique aléatoire fonctionne bien. La solution brute est cependant peu probante : Note homme ivre rempli tous les couloirs par son parcours aléatoire et on ne distingue plus son chemin.

Une amélioration consiste à, quand l'homme ivre passe une 2e fois dans son chemin en un point P, de supprimer toute la portion du chemin allant de P à P.

===== Autre fichier image disponible =====

Cous pourrez également tester ce labyrinthe.

{{ groslaby.png?direct&400 |}}