Déchiffrer un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
193
Mois de parution
mai 2016
Spécialité(s)


Résumé

Après les présentations de l’article précédent, on continue notre voyage en lisant l’image du code QR pour la traduire en un tableau de 0 et de 1.


Body

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.

glmf3
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.

01:  def chargeim(self):
02:     parser=ArgumentParser(description="Lit et corrige un code QR.")
03:     parser.add_argument("-i",required=True,metavar="image",help="Image d’entrée.")
04:     parser.add_argument("-c",choices=["1","0"],default="1",help="Corrige ou non les erreurs.")
05:     parser.add_argument("-a",choices=["1","0"],default="0",help="On affiche tout ou seulement le message.")
06:     arguments=parser.parse_args()
07:     self.fichier=arguments.i
08:     self.corrige=int(arguments.c)
09:     self.tout=int(arguments.a)

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 :

> ./qrdecode.py -h

usage: qrdecode.py [-h] -i image [-c {1,0}] [-a {1,0}]

 

Lit et corrige un code QR.

 

optional arguments:

-h, --help show this help message and exit

-i image Image d’entrée.

-c {1,0} Corrige ou non les erreurs (peut planter si non).

-a {1,0} On affiche tout ou seulement le message.

Et sans option :

> ./qrdecode.py

usage: qrdecode.py [-h] -i image [-c {1,0}] [-a {1,0}]

qrdecode.py: error: the following arguments are required: -i

La suite du code :

11:  try:
12:     im=Image.open(self.fichier)
13:  except IOError:
14:     print("Fichier "+self.fichier+" inexistant.",file=stderr)
15:     exit(1)

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

17:  im=im.convert('1')
18:  pix=im.load()
19:  self.image=[]

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

17:  for i in range(im.height):
18:     self.image.append([0+(pix[j,i]==0) for j in range(im.width)])

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.

20:  while sum(self.image[0])==0:
21:     self.image=self.image[1:]
22:  while sum(self.image[-1])==0:
23:     self.image=self.image[:-1]
24:  self.image=[[0]*len(self.image[0])]*2+self.image+[[0]*len(self.image[0])]*2

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

25:  while True:
26:     s=0
27:     for l in self.image:
28:        s+=l[0]
29:     if s==0:
30:        for i in range(len(self.image)):
31:           self.image[i]=self.image[i][1:]
32:     else:
33:        break
34:  while True:
35:     s=0
36:     for l in self.image:
37:        s+=l[-1]
38:     if s==0:
39:        for i in range(len(self.image)):
40:        self.image[i]=self.image[i][:-1]
41:     else:
42:        break
43:  for i in range(len(self.image)):
44:     self.image[i]=[0,0]+self.image[i]+[0,0]

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.

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

01:  def dims(self):
02:     if self.image is None:
03:        self.chargeim()
04:     i=0
05:     etat0,etat1=0,0

06:     no0,no1=[],[]

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).

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

08:  while not(len(no0)==2 or len(no1)==2):
09:     if self.image[i][i]!=etat0:
10:        etat0=self.image[i][i]
11:        no0.append(i)
12:     if self.image[-i-1][-i-1]!=etat1:
13:        etat1=self.image[-i-1][-i-1]
14:        no1.append(i)
14:     i+=1
16:     if len(no0)<len(no1):
17:        self.module=no1[0]-no1[1]
18:     else:
19:        self.module=no0[1]-no0[0]

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

01:  def dims(self):
02:     if self.image is None:
03:        self.chargeim()


05:     graphe=[[None,0,None,None],[None,0,1,None],[None,None,1,0],[None]*4]
06:     motif=[self.image[i][i] for i in range(len(self.image))]
07:     _,coord1=regraph(graphe,motif,0,3)
08:     _,coord2=regraph(graphe,motif[::-1],0,3)
09:     coord=min(coord1,coord2)
10:     self.module=coord[2]-coord[1]

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

def regraph(g,l,deb,fin):

   pos=deb

   coord=[]

   for i in range(len(l)):

      if l[i] in g[pos]:

         npos=g[pos].index(l[i])

         if npos!=pos:

            coord.append(i)

            pos=npos

         elif i!=len(l)-1:

            return False,coord

   return pos==fin,coord

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.

01:  def stockeim(self):
02:     if self.module is None:
03:        self.dims()
04:     debut,taille=2,self.module
05:     self.qr=[]
06:     for i in range(debut,len(self.image)-debut,taille):
07:        self.qr.append([])
08:     for j in range(debut,len(self.image[0])-debut,taille):
09:        self.qr[-1].append(self.image[i][j])

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.

01:  def placeim(self):
02:     if self.qr is None:
03:        self.stockeim()

Comme d’habituuudeuh.

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

cible=[[1,0,1,1,1,0,1] for _ in range(7)]

cible[1][2:5]=[0]*3
cible[5][2:5]=[0]*3
cible[0]=[1]*7
cible[6]=[1]*7

Ce code est dans qrcodestandard.py.

11:  for i in range(7):
12:     if self.qr[i][:7]!=cible[i]:
13:        coin=2
14:     break
15:     if self.qr[-i-1][:7]!=cible[i]:
16:        coin=1
17:     break
18:     if self.qr[i][-7:]!=cible[i]:
19:        coin=3
20:     break
21:     if self.qr[-i-1][-7:]!=cible[i]:
22:        coin=0

23:     break

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 : m1.

def tourner90(matrice):

nl=len(matrice)
 nc=len(matrice[0])
 m=[[0 for _ in range(nl)] for _ in range(nc)]
 for i in range(nl):
 for j in range(nc):
 m[j][i]=matrice[i][-j-1]

return m

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

25:  for _ in range(coin):
26:     self.qr=tourner90(self.qr)

27:     self.esttourne=True

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.



Article rédigé par

Par le(s) même(s) auteur(s)

Les derniers articles Premiums

Les derniers articles Premium

Game & Watch : utilisons judicieusement la mémoire

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Au terme de l'article précédent [1] concernant la transformation de la console Nintendo Game & Watch en plateforme de développement, nous nous sommes heurtés à un problème : les 128 Ko de flash intégrés au microcontrôleur STM32 sont une ressource précieuse, car en quantité réduite. Mais heureusement pour nous, le STM32H7B0 dispose d'une mémoire vive de taille conséquente (~ 1,2 Mo) et se trouve être connecté à une flash externe QSPI offrant autant d'espace. Pour pouvoir développer des codes plus étoffés, nous devons apprendre à utiliser ces deux ressources.

Raspberry Pi Pico : PIO, DMA et mémoire flash

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Le microcontrôleur RP2040 équipant la Pico est une petite merveille et malgré l'absence de connectivité wifi ou Bluetooth, l'étendue des fonctionnalités intégrées reste très impressionnante. Nous avons abordé le sujet du sous-système PIO dans un précédent article [1], mais celui-ci n'était qu'une découverte de la fonctionnalité. Il est temps à présent de pousser plus loin nos expérimentations en mêlant plusieurs ressources à notre disposition : PIO, DMA et accès à la flash QSPI.

Programmation des PIO de la Raspberry Pi Pico

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

La carte Pico de Raspberry Pi est appréciable à bien des égards. Ses ressources, son prix, ses deux cœurs ARM... Mais ce morceau de silicium qu'est le RP2040 renferme une fonctionnalité unique : des blocs PIO permettant de créer librement des périphériques supplémentaires qu'il s'agisse d'éléments standardisés comme SPI, UART ou i2c, ou des choses totalement exotiques et très spécifiques à un projet ou un environnement donné. Voyons ensemble comment prendre en main cette ressource et explorer le monde fantastique des huit machines à états de la Pico !

Les listes de lecture

9 article(s) - ajoutée le 01/07/2020
Vous désirez apprendre le langage Python, mais ne savez pas trop par où commencer ? Cette liste de lecture vous permettra de faire vos premiers pas en découvrant l'écosystème de Python et en écrivant de petits scripts.
11 article(s) - ajoutée le 01/07/2020
La base de tout programme effectuant une tâche un tant soit peu complexe est un algorithme, une méthode permettant de manipuler des données pour obtenir un résultat attendu. Dans cette liste, vous pourrez découvrir quelques spécimens d'algorithmes.
10 article(s) - ajoutée le 01/07/2020
À quoi bon se targuer de posséder des pétaoctets de données si l'on est incapable d'analyser ces dernières ? Cette liste vous aidera à "faire parler" vos données.
Voir les 53 listes de lecture

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous