lundi 10 janvier 2011

Étape 3 : Inonder

Traitement pour trouver la grille et les chiffres

Nous devons trouver la grille dans l'image binaire (image en noir et blanc). Un moyen très simple de le faire est d'utiliser un algorithme pour le marquage de région c'est-à-dire en remplissant une région, ce que nous appelons inonder une région. Il est étonnant de voir comment ça prend peu de lignes de code Java pour trouver la plus grande région de l'image qui est, soit dit en passant, la grille

Vous pouvez voir le code Java à partir du chapitre 11 à la page 199 du merveilleux livre de Burger et Burge. Il existe 3 versions de code Java pur dans le livre :
  • Version récursive (recursive version)
  • Version en profondeur d'abord (depth-first version) : c'est celle utilisée ici
  • Version en largeur d'abord (breadth-first version)

Vous pouvez voir le code Java dans le chapitre 11 ici :
Java code of chapter 11 to find regions in binary images

Vraiment, un grand livre!

Nous exécutons le même algorithme pour trouver les chiffres plus tard.

Vous pouvez voir des exemples du pseudo-code sur le blogue anglais de la page actuelle:

Pseudo-code sur le blogue anglais

Afficher

Voici les captures d'écran des photos que nous obtenons après l'inondation des régions :





Étape 2 : Noir et blanc

Traitement pour trouver la grille et les chiffres

Comme nous n'avons pas besoin de l'information concernant la couleur, nous convertissons l'image en gris avec ce code :
 
Bitmap bmwork = Bitmap.createBitmap(512, 512, Bitmap.Config.RGB_565);
ColorMatrix colorMatrix = new ColorMatrix();
colorMatrix.setSaturation(0);
Paint paint = new Paint();
ColorMatrixColorFilter cmcf = new ColorMatrixColorFilter(colorMatrix);
paint.setColorFilter(cmcf);
Canvas drawingCanvas = new Canvas(bmwork);
drawingCanvas.drawBitmap(bitmap, 0, 0, paint);

Nous devons maintenant convertir le gris en noir et blanc, noir devient l'arrière-plan (0) et le blanc devient la foregound (1). Ce faisant, la grille et les nombres seront convertis à 1. Pour ce faire, nous avons besoin d'un seuil. Beaucoup  d'informations sont données à ce sujet dans les références indiquées dans le deuxième message. Donc, nous ne répéterons pas cette information ici.

Premièrement, pour améliorer la performance, nous convertissons l'image  à un tableau comme ceci :

int imaget [][] = new int [512][512];    
for (i = 0; i < 512; i++)
       bmwork.getPixels(imaget [i], 0, 512, 0, i, 512, 1);  

Nous utilisons un algorithme avec une région de 12x12 pour trouver la grille et les chiffres. Pour chaque région, nous calculons le niveau de gris moyen, et nous utilisons un seuil de 1,08. Donc, pour le seuil, nous avons ce code:

if (imaget[i][j] < 1.08 * somme_pixels / 144)
    image1[i][j] = 1;
else
    image1[i][j] = 0;

Notes :
  1. Les trois petits boutons passent du noir au magenta lorsque l'unité de traitement est terminée, ce qui signifie que la grille et les chiffres ont tous été trouvés et sont prêts.
  2. Quand une photo est prise, nous enregistrons la photo dans le fichier nommé photo.jpg dans la mémoire auxiliaire du téléphone Android. Vous pouvez appuyer sur le bouton menu pour enregistrer la photo avec un autre nom ou pour ouvrir une ancienne photo. La photo que vous enregistrez ou récupérez est placée dans la mémoire auxiliaire dans le répertoire nommé com.rogerlebo.sudokuvision. Si vous souhaitez récupérer la dernière photo prise, appuyez simplement sur le bouton de retour sur l'écran pour prendre une photo 
Afficher 

Voici les captures d'écran des photos présentées plus tôt :





Étape 1 : Prendre une photo du Sudoku


Traitement pour trouver la grille et les chiffres

Dans l'étape 1, il y a 2 principales difficultés :
  • créer l'image avec la bonne taille
  • gérer la caméra
Pour obtenir une image avec la bonne taille,vous devez tenir compte de la dimension de la mémoire virtuelle du téléphone Android. Généralement, cette dimension est de 16 mégaoctets; certains téléphones Android avec un appareil photo de 8 mégapixels peuvent avoir 24 mégaoctets de mémoire virtuelle. Supposons que nous prenons une photo avec la taille 2048X1536 (largeur x hauteur) qui est souvent la taille par défaut définie par le téléphone Android lorsque vous ne spécifiez pas vous-même la taille requise. La mémoire occupée est 2048 X 1536 X 4 = 12 mégaoctets. Rapidement, votre programme est à court de mémoire.

Alors, quelle est la bonne taille pour l'image? Si cette taille est trop haute, il n'y a pas assez de mémoire et cela prend trop de temps pour extraire la grille et les chiffres. Si cette taille est trop petite, le programme ne prend pas beaucoup de mémoire, prend moins de temps, mais la taille n'est souvent pas assez grande pour capturer tous les chiffres. Après de nombreux essais, nous avons choisi 512 pour la largeur et la hauteur du de l'image.

Maintenant, la caméra. Nous pouvons modifier le comportement de la caméra avec la classe Parameters comme ceci :

camera = Camera.open();
Camera.Parameters parameters = camera.getParameters();
//  . . . modifier rotation, orientation, preview size, picture size, . . .
camera.setParameters(parameters);

Certains paramètres peuvent être définis de différentes manières lorsque le programme s'exécute sur les différentes versions de Android. Notre objectif est que notre programme doit s'exécuter sur la version Android 1.5 ou plus. Donc, nous ne voulons pas utiliser une méthode spécifique à une version. En outre, certains paramètres ne sont pas pris en charge par certains téléphones Android. Donc, nous avons décidé de ne pas définir de paramètres pour la caméra.

Le programme pourrait recevoir une photo avec la dimension 2048X1536, ce qui est trop élevée. Donc, avant de convertir une photo en une image, il faut interroger la dimension de la photo afin de diminuer la taille de l'image. Voici le code pour interroger la dimension de la photo et pour créer l'image en tenant compte de la largeur et de la hauteur de 512 pour l'image résultante :

BitmapFactory.Options options = new BitmapFactory.Options();
options.inJustDecodeBounds = true;
bitmap = BitmapFactory.decodeByteArray(data, 0, data.length, options);
options.inJustDecodeBounds = false;
options.inSampleSize = options.outHeight / 512;
bitmap = BitmapFactory.decodeByteArray(data, 0, data.length, options);

La dimension de l'image est maintenant de 1024X768  ce qui prend beaucoup moins de mémoire qui est maintenant dans l'ordre de 3 mégaoctets.

Voici 2 points concernant "options.outHeight / 512" :
  • nous utilisons options.outHeight au lieu de options.outWidth parce que la photo est encore en mode paysage; la photo sur le téléphone Android est toujours prise en mode paysage; nous devons donc faire pivoter l'image (voir plus loin)
  • le résultat de options.outHeight / 512 est 3 et la hauteur obtenue est 768; ça aurait du être 512; mais, Android choisit toujours un nombre immédiatement inférieur à une puissance de 2 qui est 2 dans notre cas

Ensuite, nous devons réduire l'image de 1024X768 à 512X512. Nous allons recadrer l'image  de 1024X768 à 768X768 et la redimensionner de 768X768 à 512X512. Voici le code pour ce faire :

int destWidth = 512;
int destHeight = 512;
int origWidth = bitmap.getHeight(); // pour recadrer
int origHeight = bitmap.getHeight();
Bitmap bmwork = Bitmap.createBitmap(destWidth, destHeight, Bitmap.Config.RGB_565);
Rect destRect = new Rect(0, 0, destWidth, destHeight);
Rect origRect = new Rect(0, 0, origWidth, origHeight);
Canvas canvas = new Canvas(bmwork);
canvas.drawBitmap(bitmap, origRect, destRect, null); // pour redimensionner

La dernière transformation est de pivoter l'image comme ceci :
Matrix matrix = new Matrix();
matrix.setRotate(90);
bitmap = Bitmap.createBitmap(bmwork, 0, 0, 512, 512, matrix, true);
L'image est maintenant prête. Nous démarrons une unité de traitement pour trouver la grille et les chiffres.

Afficher

Pendant ce temps, nous affichons l'image résultante donnant ainsi le temps à l'utilisateur de vérifier si la photo est à sa satisfaction

Voici les captures d'écran de quelques photos :




9 étapes

Bonjour!
 
Dans l'application Sudoku Vision, il y a 9 étapes :

Étape 1 : Prendre une photo du Sudoku
Étape 2 : Noir et blanc
Étape 3 : Inonder
Étape 4 : Trouver la grille
Étape 5 : Transformation de perspective
Étape 6 : Trouver les chiffres et les placer sur la grille
Étape 7 : Placer les chiffres sur la photo
Étape 8 : Donner les chiffres
Étape 9 : Jouer et résoudre le Sudoku

C'est aussi simple que ça!

Dans les prochains messages, nous donnerons quelques commentaires pour chaque étape. Et pour chacune,  les commentaires seront séparées en 2 parties :

  • Traitement pour trouver la grille et les chiffres
  • Afficher

Amusez-vous bien!

dimanche 9 janvier 2011

Ressources

Bonjour!

Pour écrire un programme de traitement de l'images permettant de trouver la grille et les chiffres de la photo d'un Sudoku, vous avez besoin de ce merveilleux livre :

Digital Image Processing : An Algorithmic Introduction Using Java
Wilhelm Burger, Mark J. Burge
Springer 2008

http://www.imagingbook.com/

C'est basé sur ImageJ, qui est un traitement et une analyse de l'images en Java :

http://rsb.info.nih.gov/ij

Dans ce livre, il y a plusieurs lignes de code Java pur qui sont très utiles.

Voulez-vous voir quelques lignes de code Java? Pourquoi pas? Allez voir ici :
Java code from the marvellous book!

Vraiment un merveilleux livre!
 
Et beaucoup d'informations pertinentes concernant la constructionre d'un programme Sudoku sont présentes ici :

Bonne journée!

vendredi 7 janvier 2011

Sudoku Vision


Bonjour!






Avec l'application Sudoku Vision, vous pouvez :
   
  • Prendre une photo d'un Sudoku en utilisant la caméra de votre téléphone Android
  • 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
  • Jouer avec le Sudoku obtenu
  • Demander un indice pour apprendre si vous êtes bloqués
  • Demander une solution
  • Demander s'il y a plus qu'une solution
  • Ouvrir et sauvegarder un Sudoku

30 Sudokus sont disponibles; pour en obtenir un, appuyez sur le bouton Ouvrir sur l'écran principal ou appuyez sur le bouton Menu puis sur le bouton Ouvrir.
Pour obtenir plus de Sudokus, appuyez sur le bouton Siphonner de l'écran principal ou appuyez sur le bouton Menu puis sur le bouton Siphonner.

Amusez-vous bien!

P.S. Un gros merci à mon gendre qui m'a prêté ses anciens téléphones Android pour tester mon programme. Ça m'a beaucoup aidé à améliorer mon application, en particulier en gérant adéquatement la caméra pour la prise de photo.

Pour voir les prochains messages, appuyer sur  "Message plus récent" en bas.