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

Et si on déchiffrait la machine Enigma...

Magazine
Marque
GNU/Linux Magazine
Numéro
235
Mois de parution
mars 2020
Domaines
Résumé

La machine Enigma fut utilisée par les Allemands, pendant la Seconde Guerre mondiale, pour chiffrer des messages secrets. Alan Turing est connu pour avoir fortement contribué à la compréhension du fonctionnement du chiffrement de cette machine. Dans cet article, je vais présenter le modèle M3 de la machine Enigma et proposer une simulation de cette machine utilisant le langage Python.

Informatique quantique : l’empire des chats morts-vivants

Magazine
Marque
GNU/Linux Magazine
Numéro
233
Mois de parution
janvier 2020
Domaines
Résumé

Le célèbre paradoxe du chat, à la fois vivant et mort, expérience de pensée due à Erwin Schrödinger en 1935 [1], est très certainement la « bizarrerie » la plus connue, mais aussi la plus perturbante de la mécanique quantique. Elle avait pour but d’illustrer simplement les paradoxes de la mécanique quantique, à une époque où elle n’était pas encore acceptée par les scientifiques. Pour comprendre le passage du monde quantique (la boîte n’est pas ouverte et contient un chat mort-vivant) au monde classique (la boîte est ouverte et le chat est soit mort soit vivant), nous allons présenter les problèmes de cohérence et de mesure. Partons donc à la chasse aux chats morts-vivants.

Les filtres de Bloom : un peu de bruit pour beaucoup [1] !

Magazine
Marque
GNU/Linux Magazine
Numéro
231
Mois de parution
novembre 2019
Domaines
Résumé

Avec l’explosion des données (un fichier de logs, par exemple), chercher une information particulière déjà connue devient une tâche complexe. Or depuis 1970, il existe une technique particulièrement puissante qui permet de résoudre très efficacement ce problème : les filtres de Bloom. Cet article propose de les explorer et de montrer comment les implémenter.

Graphes géants creux : comment définir le centre du Web

Magazine
Marque
MISC
HS n°
Numéro
18
Mois de parution
novembre 2018
Domaines
Résumé

Les graphes, composés de sommets et d’arêtes sont des objets communs en mathématiques (et indispensables) en informatique. Lorsqu’on veut manipuler des graphes de plusieurs centaines de millions de sommets, voire de plusieurs milliards de sommets, comme le graphe du web (ou un sous-ensemble) ou le graphe de certains réseaux sociaux, les choses se compliquent singulièrement : la plupart des algorithmes « académiques » se heurtent au « mur » de la complexité en temps (voire en espace), que nous appellerons le mur du « Big Data ». Tout algorithme dont la complexité est de l’ordre de O(n³) ou même de l’ordre de O(n²) est en fait inutilisable en pratique (ou très coûteux) dès lors que n, le nombre de sommets, dépasse (disons) le milliard. Il faut alors suivre d’autres stratégies. Il faut par exemple accepter de ne pouvoir calculer qu’une approximation même si dans certains cas, cette approximation peut en fait être la valeur exacte.

Quelques applications des Arbres Binaires à Commande Équilibrée

Magazine
Marque
GNU/Linux Magazine
Numéro
218
Mois de parution
septembre 2018
Domaines
Résumé

Les Arbres Binaires à Commande Équilibrée, ou ABCE, ont été présentés dans GLMF n°215 [1] au moyen d'une métaphore ferroviaire. Cependant, ils sont surtout utiles dans certains circuits numériques, dont ils améliorent la vitesse et la consommation, pour la plupart des technologies. Par rapport à un arbre binaire classique, le gain de performance augmente avec la taille, ce qui est un atout précieux pour concevoir des circuits intégrés par exemple.