Reconnaissance de Forme

Reconnaissance de Forme

La reconnaissance de chiffre à l'aide de l'algorithme des K plus proche voisin est un exemple standard.

Malheureusement pour nous, cela reste un exercice difficile. Nous allons donc nous intéresser à la reconnaissance de forme géométrique.

Dans cet exercice, on va donc chercher à reconnaître des formes géométriques.

Une question de distance

Dans le cours, nous avons vu que les K-plus proche voisins fonctionnent sur la notion de proximité entre différents éléments dans notre système.

Mais lorsque l'on parle d'image et de forme géométrique, quelle peut bien être la distance que l'on sait mesurer et qui nous intéresse.

Question

Sachant que les formes sont déjà isolées, proposez des critères facilement mesurables pour définir une distance.

Exemple de fichier d'entrée
Exemple de fichier d'entréeInformations[1]

Présentation de 4 formes simples (un triangle, un carré, un rectangle, un cercle)

Chacune indépendante des autres

Chaque image est un contour noir sur un fond blanc, comme dans l'image ci-contre.

Solution

Élancement et Circularité

On va s'intéresser à deux grandeurs que l'on peut facilement mesurer.

  • L'élancement : C'est le ratio entre la largeur et la hauteur du rectangle qui encadre au plus proche notre figure.

    Par exemple :

    • Pour un carré, c'est 1, en effet le rectangle englobant le plus petit et le carré lui même et a donc ses cotés égaux

    • Pour le cercle, c'est 1 aussi, le rectangle englobant est le carré circonscrit

    • Pour le rectangle, c'est variable mais toujours inférieur à 1, sinon c'est un carré

    • Pour le triangle, c'est encore plus variable

  • La circularité : C'est le ratio entre l'aire et le carré du périmètre (multiplié par \(4\pi\), pour normaliser).

    Par exemple :

    • Pour le carré, c'est toujours \(\pi/4\) = 0.78

    • Pour le cercle, c'est toujours 1

    • Pour le rectangle, c'est proche de 0.65

    • Pour le triangle, c'est proche de 0.39

La manipulation d'image

Manipuler des images peut être compliqué et très coûteux en temps de calcul.

C'est pourquoi on vous fourni un binaire qui permet de faire le traitement d'image rapidement et un script python pour l'utiliser.

Créez un dossier et téléchargez ce fichier dedans

Module python pour l'analyse des images [py]

Téléchargez ce fichier dans le même dossier et retirez l'extension .out

Le code de ce programme peut être trouver sur la forge

Programme pour l'analyse d'image [out]

Si lors de l'import de analyse_image.py, vous avez un problème d'exécution, vérifier que vous avez bien les droits d'exécution sur le fichier binaire.

chmod u+x analyse_forme

Des données

Le module analyse_image.py fourni une fonction donnees.

Cette fonction fourni une liste de dictionnaires dont le format est donné ci-après.

1
{
2
    "fichier": "<nom du fichier>",
3
    "forme": "<la forme ou mystere>",
4
    "elancement": <l elancement>,
5
    "circularite": <la circularité>,
6
}

Les valeurs pour fichier et forme sont des strings, et pour elancement et circularite, des flottants.

Une distance

On va repérer nos images dans un plan 2D, tel que :

  • L'abscisse est l'élancement

  • L'ordonnée est la circularité

On utilisera alors la distance euclidienne naturelle dans cet espace.

Question

Implémentez, une fonction distance, telle que :

  • Entrée :

    • image1 : Un dictionnaire représentant une analyse

    • image2 : Un autre dictionnaire représentant une analyse

  • Sortie : la distance euclidienne

Indice

On rappelle la formule de la distance euclidienne : \(distance(A, B)=\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}\)

Indice

Il faut importer la fonction sqrt depuis le module math :

1
from math import sqrt
2
3
# Utilisation :
4
sqrt(4)  # 2
Indice
Nos valeurs A et B dans la formule s'appliquent de cette façon :
  • \(x_A \rightarrow\) image1['elancement']
  • \(x_B \rightarrow\) image2['elancement']
  • \(y_A \rightarrow\) image1['circularite']
  • \(y_B \rightarrow\) image2['circularite']
Question
Implémentez, une fonction plus_proche, telle que :
  • Entrée :
    • image : Un dictionnaire représentant une analyse
    • k : un entier strictement positif, qui est le paramètre de K-PPV
    • association : un liste de dictionnaire dont on connait déjà la forme
  • Sorties : Une liste contenant les k dictionnaires les plus proches de image.
On propose l'algorithme suivant :
  • Stocker, dans une liste distances, les couples (distance, indice), tels que :
    • distance est la distance entre image et association[indice]
    Cette liste va nous permettre de trouver plus efficacement les k plus proches
  • Trier la liste distances. Comment trier rapidement ?
    • Cela fonctionne car lorsqu'on trie une liste de tuples, le tri va se faire en priorité sur le premier élément du tuple (ici sur la distance). Ingénieux !
  • Parcourir les k premiers éléments de la liste distances et créer la liste des k plus proches Image
Indice
On souhaite obtenir une liste qui ressemble à cela :
1
distances = [(0.3, 0), (0.2, 4)]
Cette liste a deux éléments :
  • Le premier est l'Image en indice 0 de association, située à distance 0.3 de self
  • Le second est l'Image en indice 4 de association, située à distance 0.2 de self
Pour y parvenir, il faut :
  • parcourir toutes les adresses de association (par exemple avec for i in range(len(association)):) ;
  • calculer la distance d avec la méthode distance ;
  • l'ajouter dans la liste distances sous la forme (d, i)
Indice
Il suffit de parcourir les indices de 0 à k (exclu) en utilisant la boucle FOR et range(k).
Si on utilise i comme variant de notre boucle for, on peut ensuite récupérer l'indice du voisin avec distances[i][1].
  • Pourquoi 1 ? Parce-que distances[i] est un tuple qui contient comme premier élément la distance, et comme deuxième élément l'adresse.
On approche de la fin
Il ne nous reste plus qu'à faire le choix de la bonne forme.
Question
Implémentez, une fonction forme_kppv, telle que :
  • Entrée :
    • image : Un dictionnaire représant un analyse d'image
    • k : un entier strictement positif, qui est le paramètre de K-PPV
    • association : un liste de dictionnaire dont on connait déjà la forme
  • Sorties : La forme la plus probable pour image.
On propose l'algorithme suivant :
  • Exécuter la fonction plus_proche, pour obtenir les k plus proches voisins
  • Créer une liste (formes) des formes des plus proches voisins
  • Utiliser max(formes, key=formes.count), pour trouver la forme la plus probable.
Indice
On peut obtenir la valeur la plus fréquente dans une liste grâce à max(formes, key=formes.count). Pourquoi ?
  • La fonction max() renvoie la valeur la plus grande dans une liste (ex : max([2,5,3]) renvoie 5).
  • Le paramètre key= permet de préciser une fonction a utiliser sur chaque élément avant de le comparer aux autres.
  • La fonction formes.count renvoie le nombre d’occurrences d'un élément passé en paramètre.
    • Les parenthèses ne sont d'ailleurs pas présentes car on ne veut pas donner à max() le résultat de la fonction, mais le nom de la fonction qu'il devra utiliser.
Donc la fonction max() regarde le nombre d’occurrences de chaque élément, et pour celui dont cette valeur est la plus élevée, va renvoyer sa valeur.
Question
Évaluez la qualité de votre algorithme.
Pour cela vous pouvez utiliser la fonction mysteres fournis par analyse_image.py qui vous donne accès à une liste d'images dont on ne connait pas la forme.
Indice
On remarquera que la forme n'est pas un si grand mystère et est présente dans le nom du fichier.
Pour les plus rapides
Si vous avez tout terminé, bravo ! Le reste des exercices n'est que du bonus, et n'est pas à connaître. Il s'agit de trois questions bonus :
  • La première consiste à agrandir notre ensemble de donnée ;
  • La deuxième consiste à essayer de distinguer plus de forme ;
  • La troisième consiste à essayer de distinguer des formes manuscrites.
Plus de données
Notre ensemble de données sûres n'est que de 100 images.
Il serait sage d'utiliser plus d'images.
Question
En étudiant le code du script python, trouvez la ligne qui vous permettra d'avoir un dataset plus grand.
Modifiez la ligne de façon à avoir un dataset de 2 000 images.
Plus de forme
Pour l'instant on reconnait les triangles, carrés, cercle et rectangle.
On aimerait en reconnaître plus.
Question
En utilisant la documentation intégré à analyse_forme, générez des ovales.
Indice
Les commandes :
  • ./analyse_forme -h
  • ./analyse_forme generate -h
Permettent d'obtenir plus d'information sur le fonctionnement du programme.
Des formes manuscrites
On s’intéresse à reconnaître des images dessinées à la main.
Question
Dessinez à la règle l'équerre et le compas des formes et prenez les en photos et exécutez le programme dessus.
Question
Essayez la même chose mais avec des formes à main levée sur Gimp.