Sudoku Vision 3.0

Bonjour!

La version 3.0 de Sudoku Vision est disponible sur le Market de Android : Sudoku Vision

Voici les principaux changements de cette version :

• Amélioration du support de Android 4.0 (Ice Cream Sandwich)
• Amélioration du taux de reconnaissance des chiffres
• Amélioration de la robustesse
• Bogues mineurs corrigés

Voici la description générale de Sudoku Vision 3.0 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Voir la réalité augmentée en action

• Montrer un Sudoku à Sudoku Vision et vous verrez la solution, pas de photo à prendre et pas de bouton à presser
• Montrer un Sudoku à Sudoku Vision pour siphonner les chiffres, pas de photo à prendre et pas de bouton à presser
• Placer le Sudoku à n'importe quel angle de 0° à 360°

3. Générer un Sudoku

• Demander un niveau de "1. Très très facile" à "7. Très très difficile"
• Plusiers stratégies supportées(*) 
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

4. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution, même pour le Sudoku le plus difficile
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution(*)

5. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

(*) Stratégies supportées (d'autres ajoutées dans la prochaine version) :

• Candidat unique isolé
• Candidat unique caché
• Intersection
• Jumeau isolé
• Jumeau caché
• Triplet isolé
• Triplet caché
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Espadon
• Méduse
• Unicité type 1 à 6
• Unicité type x
• Unicité rectangle caché
• Bogue type 1
• Boque type 2
• Boque type x

- Support plein écran des tablettes larges

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Voici les stratégies par niveau :

Niveau	Stratégie
1	Candidat unique isolé
2	Candidat unique caché
3	Intersection
4	Jumeau isolé
	Jumeau caché
5	Triplet isolé
	Triplet caché
6	Quadruplet caché
	X-Aile
	XY-Aile
	XYZ-Aile
	Bogue type 1
	Unicité type 1
7	Unicité type 2
	Unicité type 3
	Unicité type 4
	Unicité type 5
	Unicité type 6
	Unicité type x
	Unicité rectangle caché
	Quadruplet caché
	Espadon
	Méduse
	Boque type 2
	Bogue type x

Sudoku Vision 2.9

Bonjour!

La version 2.9 de Sudoku Vision est disponible sur le Market de Android : Sudoku Vision

Voici les principaux changements de cette version :

• Écrans ajustés  pour les tablettes larges
• Icônes ajustées pour les tablettes larges
• Réalité augmentée et prise de photos ajustées pour les tablettes larges

Voici la description générale de Sudoku Vision 2.9 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Voir la réalité augmentée en action

• Montrer un Sudoku à Sudoku Vision et vous verrez la solution, pas de photo à prendre et pas de bouton à presser
• Montrer un Sudoku à Sudoku Vision pour siphonner les chiffres, pas de photo à prendre et pas de bouton à presser
• Placer le Sudoku à n'importe quel angle de 0° à 360°

3. Générer un Sudoku

• Demander un niveau de "1. Très très facile" à "7. Très très difficile"
• Plusiers stratégies supportées(*) 
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

4. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution, même pour le Sudoku le plus difficile
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution(*)

5. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

(*) Stratégies supportées (d'autres ajoutées dans la prochaine version) :

• Candidat unique isolé
• Candidat unique caché
• Intersection
• Jumeau isolé
• Jumeau caché
• Triplet isolé
• Triplet caché
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Espadon
• Méduse
• Unicité type 1 à 6
• Unicité type x
• Unicité rectangle caché
• Bogue type 1
• Boque type 2
• Boque type x

- Support plein écran des tablettes larges

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Voici les stratégies par niveau :

Niveau	Stratégie
1	Candidat unique isolé
2	Candidat unique caché
3	Intersection
4	Jumeau isolé
	Jumeau caché
5	Triplet isolé
	Triplet caché
6	Quadruplet caché
	X-Aile
	XY-Aile
	XYZ-Aile
	Bogue type 1
	Unicité type 1
7	Unicité type 2
	Unicité type 3
	Unicité type 4
	Unicité type 5
	Unicité type 6
	Unicité type x
	Unicité rectangle caché
	Quadruplet caché
	Espadon
	Méduse
	Boque type 2
	Bogue type x

Sudoku Vision 2.8

Bonjour!

La version 2.8 de Sudoku Vision est disponible sur le Market de Android : Sudoku Vision

Voici les principaux changements de cette version :
 

• Réalité augmentée : montrer un Sudoku à Sudoku Vision et vous verrez la solution, pas de photo à prendre et pas de bouton à presser
• Réalité augmentée : montrer un Sudoku à Sudoku Vision pour siphonner les chiffres, pas de photo à prendre et pas de bouton à presser
• Réalité augmentée : placer le Sudoku à n'importe quel angle de 0° à 360°
• Amélioration des icônes

Voici la description générale de Sudoku Vision 2.8 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Voir la réalité augmentée en action

• Montrer un Sudoku à Sudoku Vision et vous verrez la solution, pas de photo à prendre et pas de bouton à presser
• Montrer un Sudoku à Sudoku Vision pour siphonner les chiffres, pas de photo à prendre et pas de bouton à presser
• Placer le Sudoku à n'importe quel angle de 0° à 360°

3. Générer un Sudoku

• Demander un niveau de "1. Très très facile" à "7. Très très difficile"
• Plusiers stratégies supportées(*) 
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

4. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution, même pour le Sudoku le plus difficile
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution(*)

5. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

(*) Stratégies supportées (d'autres ajoutées dans la prochaine version) :

• Candidat unique isolé
• Candidat unique caché
• Intersection
• Jumeau isolé
• Jumeau caché
• Triplet isolé
• Triplet caché
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Espadon
• Méduse
• Unicité type 1 à 6
• Unicité type x
• Unicité rectangle caché
• Bogue type 1
• Boque type 2
• Boque type x

- Support plein écran des tablettes

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Voici les stratégies par niveau :

Niveau	Stratégie
1	Candidat unique isolé
2	Candidat unique caché
3	Intersection
4	Jumeau isolé
	Jumeau caché
5	Triplet isolé
	Triplet caché
6	Quadruplet caché
	X-Aile
	XY-Aile
	XYZ-Aile
	Bogue type 1
	Unicité type 1
7	Unicité type 2
	Unicité type 3
	Unicité type 4
	Unicité type 5
	Unicité type 6
	Unicité type x
	Unicité rectangle caché
	Quadruplet caché
	Espadon
	Méduse
	Boque type 2
	Bogue type x

Sudoku Vision 2.7

Bonjour!

La version 2.7 de Sudoku Vision est disponible sur le Market de Android : Sudoku Vision

Voici les principaux changements de cette version :

• Stratégies ajoutées :
• Unicité type 5
• Unicité type 6
• Unicité type x
• Unicité rectangle caché
• Boque type 2
• Bogue type x
• Génération de Sudokus modifiée pour inclure les stratégies ajoutées
• Chaque stratégie est identifiée dans le chemin explicatif vers la solution

Voici la description générale de Sudoku Vision 2.7 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Générer un Sudoku

• Demander un niveau de "1. Très très facile" à "7. Très très difficile"
• Plusiers stratégies supportées(*) 
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

3. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution, même pour le Sudoku le plus difficile
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution(*)

4. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

(*) Stratégies supportées (plusieurs autres ajoutées dans la prochaine version) :

• Candidat unique isolé
• Candidat unique caché
• Intersection
• Jumeau isolé
• Jumeau caché
• Triplet isolé
• Triplet caché
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Espadon
• Méduse
• Unicité type 1 à 6
• Unicité type x
• Unicité rectangle caché
• Bogue type 1
• Boque type 2
• Boque type x

- Support plein écran des tablettes

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Voici les stratégies par niveau :

Niveau	Stratégie
1	Candidat unique isolé
2	Candidat unique caché
3	Intersection
4	Jumeau isolé
	Jumeau caché
5	Triplet isolé
	Triplet caché
6	Quadruplet caché
	X-Aile
	XY-Aile
	XYZ-Aile
	Bogue type 1
	Unicité type 1
7	Unicité type 2
	Unicité type 3
	Unicité type 4
	Unicité type 5
	Unicité type 6
	Unicité type x
	Unicité rectangle caché
	Quadruplet caché
	Espadon
	Méduse
	Boque type 2
	Bogue type x

Sudoku Vision 2.6

Bonjour!

La version 2.6 de Sudoku Vision est disponible sur le Market de Android : Sudoku Vision

Voici les principaux changements de cette version :

• 2 niveaux de difficulté de plus : "6. Très difficile" et "7. Très très difficile"
• Stratégies ajoutées :
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Bogue type 1
• Unicité type 1 à 4
• Espadon
• Méduse
• Chiffre sélectionné en surbrillance
• Bogues mineurs corrigés

Voici la description générale de Sudoku Vision 2.6 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Générer un Sudoku

• Demander un niveau de "1. Très très facile" à "7. Très très difficile"
• Plusiers stratégies supportées(*) 
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

3. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution, même pour le Sudoku le plus difficile
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution(*)

4. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

(*) Stratégies supportées (plusieurs autres ajoutées dans la prochaine version) :

• Candidat unique isolé
• Candidat unique caché
• Intersection
• Jumeau isolé
• Jumeau caché
• Triplet isolé
• Triplet caché
• Quadruplet isolé
• Quadruplet caché
• X-Aile
• XY-Aile
• XYZ-Aile
• Bogue type 1
• Unicité type 1 à 4
• Espadon
• Méduse

- Support plein écran des tablettes

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Voici les stratégies par niveau :

Niveau	Stratégie
1	Candidat unique isolé
2	Candidat unique caché
3	Intersection
4	Jumeau isolé
	Jumeau caché
5	Triplet isolé
	Triplet caché
6	Quadruplet caché
	X-Aile
	XY-Aile
	XYZ-Aile
	Bogue type 1
	Unicité type 1
7	Unicité type 2
	Unicité type 3
	Unicité type 4
	Quadruplet caché
	Espadon
	Méduse

Sudoku Vision 2.5

Bonjour!

La version 2.5 de Sudoku Vision est disponible sur le Market Android.

Voici les principaux changements de cette version :

• Générer un Sudoku avec un niveau de "1. Très facile" à "5. Très difficile"
• Visualiser étape par étape le chemin explicatif vers la solution
• Demander d'évaluer le niveau de difficulté d'un Sudoku
• Afficher les marques de crayon
• Accepter les Sudokus avec un minimum de 17 chiffres

Voici la description générale de Sudoku Vision 2.5 :

1. Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone

• Placer le Sudoku à n'importe quel angle de 0° à 360°
• Voir chaque étape effectuée pour trouver la grille et les chiffres sur la photo
• Demander d'évaluer le niveau de difficulté du Sudoku pris en photo

2. Générer un Sudoku

• Demander un niveau de "1. Très facile" à "5. Très difficile"
• Génération instantanée
• Nombre illimité de Sudokus
• Aucun besoin d'un accès Internet

3. Avoir de l'aide pour la solution

• Afficher les marques de crayon
• Demander un indice, pour apprendre, si vous êtes bloqués
• Demander une solution
• Demander s'il y a plus qu'une solution
• Voir étape par étape le chemin explicatif vers la solution

4. Sauvegarder et ouvrir un Sudoku

• Le Sudoku comme tel
• La photo du Sudoku

- Support plein écran des tablettes

- L'application peut être déplacée dans la mémoire auxiliaire (APP2SD)

Étape 9 : Jouer et résoudre le Sudoku

Traitement pour trouver la grille et les chiffres

C'est vraiment étonnant de constater comme il est simple d'écrire un programme pour trouver une solution ou toutes les solutions d'un Sudoku.

Voici le pseudo-code pour le faire:

Fonction Trouver_toutes_les_solutions (Le_Sudoku)

    trouver le premier carré vide dans Le_sudoku
    s'il n'y a pas de carré vide
          vous avez trouvé une solution
          vous pouvez afficher, enregistrer ou imprimer Le_Sudoku
    sinon
          pour i = 1 à 9
               si vous pouvez placer i dans le carré vide
                    placer i dans le carré vide
                    appeler Trouver_toutes_les_solutions(Le_Sudoku)
                    placer 0 dans le carré vide

Fin de Trouver_toutes_les_solutions

Vous n'avez plus qu'à traduire ce pseudo-code en Java et ça marche!

Mais, ce code n'est pas le code plus performant. Nous pouvons l'améliorer, notamment avec  Dancing Links, ou DLX, qui est une technique proposée par le célèbre Donald Knuth. Voici quelques ressources très intéressantes concernant cette technique:

Dancing links
Knuth's Algorithm X
Exact Cover Matrix

Bien sûr, nous avons implanté cette excellente technique dans notre application.

Donc, maintenant, il vous suffit de jouer avec votre Sudoku. Mais parfois, le Sudoku est très difficile. Bien sûr, notre application peut donner une solution. Et notre application peut même dire s'il existe plus qu'une solution. Mais, demander la solution ne permet pas de savoir comment résoudre un Sudoku. Alors, pourquoi ne pas demander juste un indice? Si vous le faites, notre application vous donnera le chiffre suivant qu'il jouerait. À ce moment-là, vous pouvez avoir une de ces réactions:

1. Oui, bien entendu, pourquoi n'ai-je pas trouvé ce chiffre  moi-même?
2. Pourquoi ce chiffre est-il suggéré par l'application? Vous vérifiez le Sudoku un peu plus et vous comprenez! Maintenant, vous apprenez rapidement à résoudre un Sudoku
3. Je ne sais pas pourquoi l'application propose ce chiffre, mais, au moins, je peux continuer

Voici l'écran affiché lorsque vous appuyez sur le bouton Indice. Il faut l'essayer! Vous le comprendrez très vite :

Quelle technique utilisons-nous pour proposer un chiffre pour donner un indice, pour les lignes par exemple? Très simple. . . comme d'habitude! Nous utilisons la fonction Trouver_toutes_les_solutions pas pour tous le Sudoku, mais plutôt pour la première ligne; après, pour toutes les solutions trouvées dans la première ligne, nous vérifions si un chiffre est toujours dans le même carré. Si oui, nous suggérons ce chiffre. Sinon, nous vérifions la ligne 2 jusqu'à la ligne 9. Si nous ne trouvons pas un chiffre toujours dans le même carré, nous disons que nous n'avons pas d'indice pour les lignes.

Vous voulez un conseil pour les colonnes? Il suffit d'appuyer sur le bouton Colonnes. Et ainsi de suite.

Amusez-vous bien!

Note : Vous pouvez enregistrer le Sudoku courant. Il est enregistré dans la mémoire auxiliaire dans le répertoire nommé com.rogerlebo.sudokuvision. Bien sûr, vous pouvez également récupérer un Sudoku que vous avez enregistré précédemment.

Étape 8 : Donner les chiffres

Nous retournons le chiffres du Sudoku avec le très simple code Java suivant :

Uri data = Uri.parse(sudoku_capture);

Intent result = new Intent(null, data);

setResult(RESULT_OK, result);

finish();

Display

Dans cette étape, toutes les photos donnent le même résultat. Ci-dessous, vous pouvez voir le résultat final avec 3 téléphones Android différents.

Voici quelques observations concernant les images :

• l'application peut être en anglais ou en français selon la langue dans laquelle vous définissez pour votre téléphone
• plus grande est la hauteur de l'écran du téléphone, plus vous voyez de nouveaux boutons ou des boutons plus hauts; les mêmes fonctions des boutons manquants dans les 2 premières images peuvent être obtenues avec le bouton menu

Étape 7 : Placer les chiffres sur la photo

Traitement pour trouver la grille et les chiffres

Tous les chiffres sont trouvées. Il s'agit maintenant de les afficher sur la photo.

Afficher

Donc, maintenant, nous voulons seulement  afficher les chiffres sur la photo originale. Le défi est de donner la perspective originale pour les chiffres trouvés et d'appliquer cette perspective sur la photo. Pour ce faire, nous utilisons cette fois la miraculeuse méthode  setPolyToPoly de la classe Matrix. Mais, à première vue, ce n'est pas très facile à comprendre. Il m'a fallu beaucoup de temps pour bien utiliser la classe correctement.C'est pourquoi nous présentons le code exact de notre programme Java.

Voici quelques variables déjà définies :

bitmap : la photo originale de dimension 512X512
sudoku_dim : la dimension de la grille extraite (sudoku_dim = largueur = hauteur)
(x1,y1), (x2,y2), (x3,y3), (x4,y4) : les coordonnées des 4 coins de la grille sur la photo originale
sudoku_capture : les 81 chiffres trouvés (une cellule vide est représentée par un blanc)

 Voici le code complet :

Bitmap bitmap_to_display = bitmap.copy(Bitmap.Config.RGB_565, true);

    

float orig [] = new float [] {

            0, 0,

            sudoku_dim, 0,

            sudoku_dim, sudoku_dim,

            0, sudoku_dim

            };        

float dest [] = new float [] {

            (float) x1, (float) y1,

            (float) x2, (float) y2,

            (float) x3, (float) y3,

            (float) x4, (float) y4

            };

Matrix matrice = new Matrix();

matrice.setPolyToPoly(orig, 0, dest, 0, 4);

       

Canvas canvas;                  

canvas = new Canvas(bitmap_to_display);

canvas.setMatrix(matrice);

       

int width_square, height_square;                       

width_square = sudoku_dim / 9;

height_square = width_square;

                 

Paint paint_chiffre = new Paint();

paint_chiffre.setTextSize(34);

paint_chiffre.setTypeface(Typeface.DEFAULT_BOLD);

paint_chiffre.setColor(Color.GREEN);

     

String le_nombre;

int iimage, jimage;

int deb_x_square, deb_y_square;

int idx = -1;

for (iimage = 0; iimage < 9; iimage++) {

      deb_y_square = iimage * height_square + 12 + iimage * 2 / 3 ;

      for (jimage = 0; jimage < 9 ; jimage++){

        deb_x_square = jimage * width_square + 2 + jimage / 3; 

        idx++;           

        le_nombre = sudoku_capture.substring(idx,idx + 1);

        if (!le_nombre.equals(" "))

            canvas.drawText(le_nombre,

                        deb_x_square + 8, deb_y_square + 18,
                        paint_chiffre);                         

      }

}

image.setImageBitmap(bitmap_to_display);

Et ça marche!

Pour afficher les chiffres à n'importe quel angle de 0° à 360°, il s'agit de changer les points (x,y) en conséquence.

Dans les captures d'écrans des mêmes photos, nous voyons les chiffres avec la bonne perspective :

É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 à 0°

                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 :

Étape 5 : Transformation de perspective

Traitement pour trouver la grille et les chiffres

Souvent, la grille est déformée et il est presqu'impossible de trouver des chiffres si la grille n'est pas carrée. Nous avons besoin d'un moyen pour passer d'une grille déformée à une grille carrée. La façon miraculeuse est d'utiliser la transformation de perspective aussi appelée "projective mapping"  ou  "2D mapping". Donc, nous voulons transformer la grille verte entourée à gauche vers la grille à droite :

Pour utiliser la transformation de perspective, il y a une méthode nommée setPolyToPoly dans la classe Matrix de Android. Mais, parfois, une partie des coins de la grille est perdue et, par conséquent, certains chiffres peuvent être perdus également. Donc, nous avons décidé d'écrire notre propre code Java pur pour réaliser la transformation de perspective.

Mais, où trouver toutes les informations dont nous avons besoin pour faire cela? Pour sûr, maintenant, vous connaissez la réponse. . . dans le merveilleux livre de Burger et Burge. . . bien sûr. Ceci est très clairement expliqué dans le chapitre 16 page 380. C'est appelé "projective mapping" dans le livre. Comme d'habitude, vous pouvez trouver le code Java ici:

Chapter 16 Geometric Operations

Vous pouvez voir des exemples de vraies codes Java sur le blogue anglais de la page actuelle:

Code Java sur le blogue anglais



Afficher

Dans les captures d'écran des 4 mêmes photos, on voit les transformations de perspective. Noter la quatrième où nous n'avions pas les 4 coins de la photo originale :

Code Java

Vous pouvez voir des exemples de vraies codes Java sur le blogue anglais de la page actuelle:

Code Java sur le blogue anglais

Étape 4 : Trouver la grille

Traitement pour trouver la grille et les chiffres

Maintenant, nous devons trouver les 4 coins de la grille. Il y a 2 étapes:

1. trouver toutes les lignes droites possibles dans la grille
2. trouver les 4 coins de l'intersection des 4 lignes droites les plus éloignées

Pour trouver toutes les lignes droites possibles dans la grille, nous utilisons le célèbre algorithme de la transformation de Hough.

Voici l'équation d'une ligne droite dans la forme normale de Hesse:

      r = x . cos(θ) + y . sin(θ)

Pour chaque point (x,y) dans l'image obtenue dans l'étape précédente, nous varions θ de 0 à 180 pour obtenir r. Et, (θ,r) devient les coordonnées d'un nouveau tableau nommé accumulateur.

Une explication très compréhensible de cet algorithme est donnée dans . . . le merveileux libre de Burger et Burge encore une fois, dans le chapitre 9 à la page 155.

Voulez-vous voir quelques lignes de code Java pour cet algorithme? Pourquoi pas? Vérifiez le chapitre 9 juste ici:

Chapter 9 Detecting Simple Curves

Vous pouvez également trouver quelques explications utiles, courtes et visuelles de l'algorithme ici :
Hough Transform in Wikipedia

Maintenant, essayons de trouver les 4 coins. Comment pouvons-nous faire? Premièrement, nous trouvons la ligne la plus à gauche, la ligne la plus à droite, la ligne la plus haute et la ligne la plus basse dans le tableau accumulateur. Avec l'intersection de chacune de ces 4 lignes, nous trouvons les 4 coins. N'est-ce pas que c'est simple? Dans le merveilleux livre  de Burger et Burge, il y a une section dont le titre est "Analyzing the Accumulator Array", page 163, qui décrit exactement ce que nous voulons. Quel bon livre!

Voici une brève analyse de l'algorithme de la transformation de Hough :

Avantages:

• facile à programmer
• trouver la grille  même si la forme du Sudoku n'est pas carrée
• trouver la grille même si nous n'avons aucun coin sur la photo

Désavantages:

• mauvaise performance parce qu'il y a trop de calculs et d'itérations

Pour améliorer les performances de l'algorithme, on utilise 3 techniques:

1. cos(θ) et sin(θ) sont mis dans une antémémoire car nous en avons besoin dans de nombreux calculs
2. nous faisons varier θ de 0 à 180 par 4, ce qui est suffisant pour trouver la grille
3. nous prenons (x, y) dans le tableau original à chaque 5 points, ce qui est suffisant pour trouver la grille

Avec le Nexus One roulant Android 2.2, il faut 0,08 seconde pour traiter cette étape 4. Finalement, la performance n'est pas si mal.

  

Afficher

Dans les captures d'écran des mêmes photos, nous voyons les 4 lignes droites en vert et les 4 coins en rouge . . . quand il y a un coin sur la photo :