lundi 10 janvier 2011

Étape 6 : Trouver les chiffres et les placer sur la grille

Traitement pour trouver la grille et les chiffres

Nous avons trouvé la grille et cette grille est maintenant carrée. L'objectif de l'étape 6 est de trouver les chiffres. Il y a 3 étapes pour pour ce faire:
  1. trouver les 81 carrés
  2. trouver et isoler le chiffre dans un carré 
  3. reconnaître le chiffre dans un carré
Comme nous avons les coordonnées des 4 coins, il est maintenant très simple de calculer les coordonnées des 81 carrés du Sudoku. Il suffit de diviser la largeur par 9 et la hauteur de 9.

Pour trouver et isoler le chiffre dans un carré, nous utilisons 2 techniques:
  1. supprimer les 1 isolés (c'est ce que nous appelons la transformation Pac-Man)
  2. inonder les régions
La transformation de Pac-Man vient de l'ancien jeu Pac-Man. Sur un carré, nous supprimons d'abord tous les 1 isolés collés à une région. Et avec la technique de l'inondation, on trouve la plus grande région qui est, soit dit en passant, le chiffre. Voici maintenant un exemple pour le chiffre 8:


Afin de reconnaître le chiffre, il y a un nombre très important de techniques. Nous avons testé beaucoup d'entre elles. Celle que nous n'avons pas encore testé est le réseau de neurones. Nous allons probablement l'utiliser dans une prochaine version de notre application. Pour l'instant, nous utilisons notre propre technique qui est en fonction de la forme du chiffre. Et la technique est basée sur le fameux algorithme de l'inondation.

Donc, pour reconnaître le chiffre, nous appliquons la très utile technique de l'inondation comme suit:
  • inonder la région supérieure gauche avec 2
  • inonder la région inférieure gauche avec 3
  • inonder la région supérieure droite avec 4
  • inonder la région inférieure droite avec 5
  • inonder toutes les régions autres (trous) avec 6 et plus
  • ne pas inonder la première ligne, la dernière ligne, la première colonne et la dernière colonne

Nous obtenons ceci pour le chiffre 8:



Ensuite, nous définissons un seuil qui dépend de la hauteur du chiffre. Quand :
  • la plus grande région en haut à gauche < seuil
  • la plus grande région en bas à gauche < seuil
  • la plus grande région en haut à droite < seuil
  • la plus grande région en bas à droite < seuil
  • la prochaine plus grande région dans la partie supérieure du chiffre >= seuil
  • la prochaine plus grande région dans la partie inférieure du chiffre >= seuil
nous reconnaissons le chiffre 8.

Voici un autre exemple. Quand:
  • la plus grande région en haut à gauche < seuil
  • la plus grande région en bas à gauche >= seuil
  • la plus grande région en haut à droite >= seuil
  • la plus grande région en bas à droite < seuil
nous reconnaissons le numéro 5.

Voici quelques caractéristiques de notre technique:
  • c'est très facile à comprendre
  • c'est  très simple à programmer
  • c'est  très rapide
  • c'est presque complètement indépendant des polices généralement utilisées dans une grille de Sudoku (nous avons choisi une police différente pour chaque photo présentée ci-dessous)
  • le taux de reconnaissance est très bon
Mais, nous pensons que le taux de reconnaissance de l'algorithme de réseau neuronal est probablement meilleur. Nous allons le tester dans une prochaine version.

Maintenant, que faisons-nous pour trouver les chiffres à n'importe quel angle de 0° à 360°? Voici le pseudo-code:

Trouver les chiffres
S’il y a 0 chiffre
                Pivoter 90°
                Trouver les chiffres
                S’il y a des chiffres en double dans les lignes,  les colonnes ou les grilles 3X3
                               Pivoter 270°
                               Trouver les chiffres
                               Si nombre de chiffres en double à 90° < nombre de chiffres en double à 270°
                                               Donner chiffres à 90°
                               Sinon
                                               Donner chiffres à 270°
                Sinon
                               Donner chiffres à 90°
Sinon
S’il y a des chiffres en double dans les lignes,  les colonnes ou les grilles 3X3
                Pivoter 180°
                Trouver les chiffres
                Si nombre de chiffres en double à 0° < nombre de chiffres en double à 180°
                               Donner chiffres à
                Sinon
                               Donner chiffres à 180°
                Sinon
                               Donner chiffres à 0°

Voilà!

Soit dit en passant, tous les chiffres et les lettres ont normalement une hauteur supérieure à la largeur. Lorsque nous trouvons un chiffre dont la largeur est supérieure à la hauteur, nous considérons que ce n'est pas un chiffre. C'est pourquoi nous pouvons avoir cette condition "S'il y a 0 chiffre".

Afficher

Comme vous vous en souvenez certainement, nous avons démarré une unité de traitement à l'étape 1 pour trouver la grille et les chiffres. Donc, avant d'afficher l'écran suivant, il ne faut pas oublier d'attendre que l'unité de traitement soit terminée.

Dans les captures d'écran des mêmes photos, nous voyons maintenant les chiffres :



Il y a 2 étapes pour demo 5:


Il y a 3 étapes pour demo 6; dans l'étape 1, nous trouvons 0 chiffre :







Aucun commentaire:

Enregistrer un commentaire