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

Stubby : protection de votre vie privée via le chiffrement des requêtes DNS

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

Depuis les révélations d’Edward Snowden sur l’espionnage de masse des communications sur Internet par la NSA, un effort massif a été fait pour protéger la vie en ligne des internautes. Cet effort s’est principalement concentré sur les outils de communication avec la généralisation de l’usage du chiffrement sur le web (désormais, plus de 90 % des échanges se font en HTTPS) et l’adoption en masse des messageries utilisant des protocoles de chiffrement de bout en bout. Cependant, toutes ces communications, bien que chiffrées, utilisent un protocole qui, lui, n’est pas chiffré par défaut, loin de là : le DNS. Voyons ensemble quels sont les risques que cela induit pour les internautes et comment nous pouvons améliorer la situation.

Surveillez la consommation énergétique de votre code

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

Être en mesure de surveiller la consommation énergétique de nos applications est une idée attrayante, qui n'est que trop souvent mise à la marge aujourd'hui. C'est d'ailleurs paradoxal, quand on pense que de plus en plus de voitures permettent de connaître la consommation instantanée et la consommation moyenne du véhicule, mais que nos chers ordinateurs, fleurons de la technologie, ne le permettent pas pour nos applications... Mais c'est aussi une tendance qui s'affirme petit à petit et à laquelle à terme, il devrait être difficile d'échapper. Car même si ce n'est qu'un effet de bord, elle nous amène à créer des programmes plus efficaces, qui sont également moins chers à exécuter.

Donnez une autre dimension à vos logs avec Vector

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

Avoir des informations précises et détaillées sur ce qu’il se passe dans une infrastructure, et sur les applications qu'elle héberge est un enjeu critique pour votre business. Cependant, ça demande du temps, temps qu'on préfère parfois se réserver pour d'autres tâches jugées plus prioritaires. Mais qu'un système plante, qu'une application perde les pédales ou qu'une faille de sécurité soit découverte et c'est la panique à bord ! Alors je vous le demande, qui voudrait rester aveugle quand l'observabilité a tout à vous offrir ?

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 62 listes de lecture

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous