É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 :