Déchiffrer un code QR

Dans cet article, on transformera l’image d’un code QR sans erreur ni joli petit dessin en un tableau de bits. Pour cela, on doit déterminer la taille d’un module, la position des cibles et éventuellement l’orientation de l’image.

Avant de lire l’image, un petit rappel s’impose. Nous allons étudier le code QR de la figure 1, le même que celui de l'article précédent. J’appelle module un petit carré blanc ou noir, cible les motifs carrés des coins, elles nous serviront pour déterminer la taille en pixels d’un module et l’orientation de l’image.

Fig. 1 : Le code QR à décoder.

Le cadre est clair, on peut commencer à lire l’image fournie en entrée.

1. Chargement et recadrage de l’image

Nous y voilà, la première méthode charge et stocke les pixels de l’image dans l’attribut image à partir de l’attribut fichier qui contient — tadaaa — le nom du fichier. Elle gère aussi les options de la ligne de commande. Je renuméroterai le code à partir de 01 à chaque section.

argparse est une bibliothèque qui permet de manipuler simplement les arguments de la ligne de commande sans réinventer la roue. Ici :

• -i spécifie l’image utilisée en entrée, de format bitmap ;
• -c (dés)active la correction des erreurs ;
• -a affiche la totalité des informations ou seulement le contenu du code QR.

Voici ce que donne l’option -h, automatiquement fournie par la bibliothèque :

Et sans option :

La suite du code :

On essaie d’ouvrir l’image, en cas d’échec on sort en se plaignant sur la sortie d’erreur.

On convertit l’image en noir et blanc à l’aide de la bibliothèque de traitement d'images PIL — sans John Lydon.

On stocke l’image dans l’attribut image qui est un tableau de tableaux puis, à la fin de la méthode chargeim, au cas où elle aurait été mal cadrée, on la recadre pour que le contour n’ait que deux pixels d’épaisseur. Python convertit automatiquement la valeur True à 1 et False à 0 en cas d’opération entre un booléen et un entier donc si un pixel est noir, la valeur de l’expression 0+(pix[j,i]==0) sera 1. On peut remarquer que les coordonnées dans l’objet pix sont écrites de manière mathématique et non de manière pythonique.

On retaille le haut puis le bas avant d’ajouter deux lignes blanches en haut puis en bas.

Et de même avec les colonnes de gauche ligne 31 où on enlève le premier élément blanc de chaque ligne (si la colonne est entièrement blanche) puis de même avec le dernier blanc ligne 40 avant d’ajouter deux colonnes blanches de chaque côté.

2. Recherche de la dimension d’un module

2.1 Méthode directe

On n’utilise pas les petits pointillés bleus d’un module d’épaisseur (voir figure 2 pour rappel), on va reconnaître le motif blanc-noir-blanc à partir du coin supérieur gauche et du coin opposé. En effet, au moins l’un des deux contient une cible. Bien entendu, si l’attribut image est vide (un démon de minuit ?), on appelle la méthode précédente.

Fig. 2 : Les quatre différentes zones d’un code QR.

On va reconnaître l’expression rationnelle 0+1+0 (au moins un 0 suivi d’au moins un 1 et d’un 0 pour finir, voir figure 3) pour laquelle une cible a une dimension minimale. Pour cela il faut détecter deux changements d’état : une fois pour passer de 0 à 1 et une fois pour revenir à 0. Par exemple pour le coin supérieur gauche, ligne 09, si la valeur courante image[i][i] est différente de la valeur précédente etat0, on stocke la coordonnée du changement dans la liste n0 et on modifie l’état courant jusqu’à avoir repéré deux changements (ie n0 ou n1 a deux éléments).

Fig. 3 : Notre petite machine qui reconnaît le motif.

Le premier entre n0 et n1 qui a une longueur de 2 a rencontré une cible, c’est donc lui qui va nous indiquer la dimension d’un module. En fait, ligne 16, on teste si la cible est en bas à droite.

Ici, un module fait 6×6 pixels.

2.2 Graphe étiqueté

On peut aussi utiliser un petit parcours de graphe étiqueté :

On reconnaît une matrice de notre graphe à quatre sommets, une ligne correspond à un sommet, la position au sommet où on va et la valeur au caractère reconnu.

Ainsi au sommet 1, [None,0,1,None] signifie que si on a un 0, on reste sur le sommet 1 mais que si on a un 1, on passe au sommet 2. Tout autre caractère fait arrêter la reconnaissance.

On envoie donc la diagonale descendante (motif) puis la montante (motif[::-1]), regraph retourne si le motif a été reconnu entièrement (aucune importance ici) et les positions des modules de chaque changement de couleur. Ligne 09, celle qui reconnaît le plus tôt le premier changement est celle qui permet d’obtenir la taille d’un module.

regraph est la fonction suivante (dans qrcodeoutils.py) :

On parcourt le motif envoyé (la liste l) et on essaie de parcourir le graphe étiqueté g selon les valeurs des éléments de l. À chaque changement d’état, c’est-à-dire de sommet, on stocke sa coordonnée dans coord. Le sommet courant est npos, le sommet précédent est pos.

3. Le tableau

3.1 Transformation en tableau

Dans cette méthode, on se contente de prendre la valeur du pixel de coordonnées 2+i*module en ordonnée et 2+j*module en abscisse pour compléter le tableau. Le début vaut 2 parce qu’on a retaillé ainsi l’image dans la méthode chargeim. Si l’image contenait des modules arrondis, il faudrait tester ligne 09 si un module contient par exemple plus de 60% de noir ou étudier les pixels en son centre pour le déclarer noir et revoir la méthode précédente.

On stocke le tableau dans l’attribut qr, il s’agit bien du dessin en noir et blanc du code QR.

3.2 Orientation du tableau

Enfin, il reste à vérifier que le coin sans grande cible est bien en bas à droite du tableau. Si ce n’est pas le cas, on le tourne autant de fois que nécessaire.

Comme d’habituuudeuh.

On a besoin du motif des carrés concentriques caractéristique des grandes cibles :

Ce code est dans qrcodestandard.py.

On teste si, dans un des coins, un segment horizontal de sept modules ne correspond pas au segment de la cible attendu. Le numéro du coin est le nombre de quarts de tour directs nécessaire pour orienter correctement le tableau. Si le travail de création de l’image est bien fait, un seul canard coin doit se plaindre et comme je collectionne des canards (vivants)… plus ils sont contents, plus je le suis.

La disposition des coins est donc la suivante : .

Cette fonction tourner90, dans qrcodeoutils.py, retourne la matrice envoyée en argument tournée d’un quart de tour direct, où  donne  .

On tourne coin fois le tableau (zéro fois éventuellement) et on signale que la matrice est bien orientée.

Conclusion

Le tableau de bits (Jamie Mc Cartney n’y est pour rien) est prêt, il reste à l’interpréter dans le dernier article de cette première partie.