Déchiffrer un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
193
Mois de parution
mai 2016
Domaines


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.

glmfcouleurs

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

er


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


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ù donne .

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.




Articles qui pourraient vous intéresser...

Tirez parti des nouveautés de PostgreSQL 13

Magazine
Marque
GNU/Linux Magazine
Numéro
245
Mois de parution
février 2021
Domaines
Résumé

Le 24 septembre 2020 est sortie la version 13 de PostgreSQL. Elle comprend de nombreuses nouvelles fonctionnalités. Certaines ont pour cible les utilisateurs et développeurs, d’autres sont pour les administrateurs. La première version corrective de cette branche, la 13.1, est sortie le 12 novembre et cela nous semble une bonne occasion de regarder en profondeur certaines de ces nouveautés.

Gestion de projets avec Erlang/OTP

Magazine
Marque
GNU/Linux Magazine
Numéro
245
Mois de parution
février 2021
Domaines
Résumé

Un langage de programmation se doit d’être facile d’accès, que ce soit pour son apprentissage, la réalisation de concepts ou de produits finaux. La création de projets en Erlang se fait via les notions d’application et de release. Couplés à différents outils internes ou fournis par la communauté, ces principes permettent de créer un environnement de production flexible et maintenable sur le long terme, tout en facilitant la diffusion et le partage des modules conçus par les créateurs.

Encodage d'un script Python et exécution du script encodé (Acme::Buffy style)

Magazine
Marque
GNU/Linux Magazine
Numéro
245
Mois de parution
février 2021
Domaines
Résumé

Il est parfois intéressant de considérer des problèmes anodins, complètement inutiles, mais qui permettent de mettre en œuvre des éléments de programmation encore jamais employés. Je vous propose ici de réécrire en Python un module bien connu des développeurs Perl : Acme::Buffy.

Quarkus dans les nuages

Magazine
Marque
GNU/Linux Magazine
Numéro
245
Mois de parution
février 2021
Domaines
Résumé

Lancé il y a moins de deux ans, le projet Open Source Quarkus vient déjà d’être consacré « produit » par la compagnie qui l’a initié, Red Hat. Qu’est-ce que cela signifie ? Simplement que, désormais, en plus d’être Open Source, le projet dispose d’une version entièrement certifiée et supportée par le chapeau rouge. Mais c’est aussi un indicateur que Quarkus a le vent en poupe. Bref, tout ceci forme une excellente opportunité de revenir sur cet excitant cadre de développement Java !

Rendre une page présentant du code plus ergonomique avec Tampermonkey/Greasemonkey

Magazine
Marque
GNU/Linux Magazine
Numéro
245
Mois de parution
février 2021
Domaines
Résumé

Lire des articles contenant du code informatique sur le Web n’est pas nécessairement simple, ne serait-ce que de par la complexité inhérente au sujet traité. Pourquoi alors se compliquer la tâche avec une présentation des informations qui n’est pas nécessairement adaptée au contenu, alors qu’on peut l’améliorer ?