Expliquer un code QR

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


Résumé

Vous en avez assez de voir des codes QR sans comprendre leur fonctionnement ? Voici comment lire leur contenu, qu’il soit entaché d’erreurs ou non et comment en créer.


Body

Cette série de huit articles présente une étude presque complète des codes QR et pour commencer, une présentation du projet suivie d’une description du format et des premières méthodes de notre classe. Les deux articles suivants déchiffreront l’image en un tableau de bits puis en liront toutes les informations nécessaires à son décodage, c’est-à-dire écrire le message caché dans le magma de carrés noirs et blancs. Toutes les informations de format pourront également être affichées. Les codes QR entachés d’erreurs ou munis d’un petit dessin verront leur contenu corrigé à l’aide de codes de Reed-Solomon (et une brève étude d’un corps fini ainsi que son codage en Python seront nécessaires). Enfin, tout ceci nous servira pour créer un code QR fonctionnel.

On voit de plus en plus de carrés pourvus de petites cibles dans les coins, remplis de carrés noirs et blancs disposés presque aléatoirement. Il ne s’agit pas d’œuvres d’artistes de rue qui veulent remplacer les populaires petits space invaders en céramique mais, et c’est moins joli, de codes QR, destinés à remplacer les codes à barres. Ils contiennent une vraie correction d’erreur contrairement à ces derniers et permettent de stocker des données plus variées et en plus grande quantité. Ils sont protégés par des brevets [1] donc cet article est à usage non professionnel, seulement pour geeker entre amis. Ces codes se limitent à traduire une image carrée faite de carrés, pas à reconnaître un code QR vu en perspective.

1. Préliminaires

1.1 Présentation du projet

Huit articles sont prévus en trois parties, trois articles sur la lecture, trois sur la correction et deux sur la création :

  • le premier présente le projet, le format du code QR et l’affichage en console ;
  • le deuxième déchiffre l’image de la figure 1 qui ne contient pas d’erreur en vue ;
  • le troisième interprète le contenu binaire pour afficher le message ;
  • le quatrième présente les mathématiques des corps finis ;
  • le cinquième construit la classe mathématique utilisée dans la correction de Reed-Solomon ;
  • le sixième détaille le mécanisme de correction des erreurs ;
  • le septième prépare les données à remplir ;
  • le dernier présente comment écrire un code QR.

Nous ne nous intéresserons qu’aux codes QR de modèle 2 dits standards, pas au micro QR ni au modèle 1, plus ancien et abandonné.

Ce premier article commence par présenter brièvement le format.

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

1.2 Organisation du code

Le code décortiqué dans cet article est organisé en cinq fichiers non nettoyés en Python 3 : vous bénéficierez de code mort et de tonnes de codes ratés en commentaires, avec les images et exemples sur le github du magazine [2] :

  • qrdecode.py, le code principal qui affiche le contenu de l’image du code QR, éventuellement décoré ou avec des erreurs ;
  • qrencode.py, le code principal qui crée une image du code QR dont le contenu est un fichier ;
  • qrcodeoutils.py, une petite bibliothèque d’utilitaires communs aux autres mais non spécifique aux codes QR ;
  • qrcodestandard.py, une bibliothèque qui contient les fonctions et constantes spécifiques aux codes QR ;
  • qrcorps.py, une bibliothèque qui permet de manipuler le corps fini formule_1 et les polynômes à coefficients dans ce corps.

L’organigramme est présenté en figure 2.

bibliotheques

 

Fig. 2 : L’organigramme des bibliothèques utilisées.

Par exemple, qrcorps.py nécessite seulement qrcodeoutils.py et est utilisé par qrdecode.py.

Enfin, qrdecode.py et qrencode.py ont besoin de la bibliothèque d’images PIL [3], d’argparse pour le traitement des options de la ligne de commande et de sys pour exit et sdterr.

PIL s’installe avec le paquet python3-pil de Debian, argparse avec python-argparse (plutôt pour Python 2 mais fonctionne très bien ici) et sys est fourni d’office.

Je me suis principalement servi des deux articles parus sur wikiversity [4], parfois corrigés silencieusement ici, les autres sources sont données dans le texte.

2. Description du format

La description en détail du format se fera pendant l’explication du code en Python, il est cependant utile d’avoir un aperçu du vocabulaire employé et de voir globalement où sont les données utiles au décodage.

2.1 Vocabulaire

Un code QR est un carré formé d’un contour blanc de quatre modules d’épaisseur et d’un grand carré central qui contient les données codées sous forme de petits carrés noirs et blancs — les modules — plus quelques zones vierges de données pour calibrer la reconnaissance de l’image, les cibles et deux segments pointillés.

La version d’un code QR est, en gros, sa taille : un code de version 1 a 21 modules de côté (sans le contour) et 4 modules supplémentaires augmentent la version d’une unité.

Le format contient le niveau de correction des erreurs (on peut corriger plus ou moins d’erreurs) et le masque qui sert à éviter des motifs trompeurs dans l’image (par exemple des carrés concentriques où il ne faudrait pas ou des zones monochromes trop grandes). On en détaillera le principe lors de la création d’un code QR.

Enfin, le type désigne le type de données que le code contient parmi les quatre suivants :

  • un format numérique ;
  • un format alphanumérique qui contient 45 symboles ;
  • un format binaire qui peut contenir du texte ASCII ou non mais aussi, soyons fous, un exécutable (s’il est bref sinon sur plusieurs codes QR consécutifs, chose possible) ;
  • un format de texte kanji (non codé dans cet article) puisqu’il vient du Japon.

Les formats sont compressés sauf le format binaire.

2.2 Différentes zones

Les différentes zones d’un code QR de version 3 (donc de 29×29 modules) sont illustrées dans la figure 3.

glmfcouleurs

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

Un module noir vaut 1 et sera représenté par une couleur pure ; un module blanc vaut 0 et sera représenté par une couleur pastel. Les couleurs d’une même teinte sont de la même zone.

En rouge vif et rose, les cibles pour la reconnaissance et le placement correct de l’image plus un module nécessairement noir au-dessus de la barre verticale verte inférieure. Seul un code QR de version 1 n’a pas la petite cible en bas à droite, en revanche, un code QR de version 7 ou plus a des petites cibles complémentaires, réparties régulièrement dans l’image plus deux zones de vérification de la version de 3×6 modules chacune.

En bleu, les deux zones pointillées qui servent aussi au calibrage, par exemple à la détermination des dimensions des modules.

En vert pomme, les deux zones de format concaténées avec leur correction d’erreur : elle est présente d’une part autour de la cible en haut à gauche en tournant dans le sens trigonométrique, d’autre part en partant du bas et en remontant sur la cible à droite en tournant dans le sens horaire. Regardez bien et observez les deux endroits distincts où est écrite la suite de bits 111110110101010 (et comment). Si vous restez perché comme un guitariste psychédélique après l’avoir lue de tête, vous êtes mûr pour la partie grisée sans les articles suivants.

Enfin, en gris et blanc, la zone de données proprement dite qui contient un court en-tête (dont sa longueur exacte et le type de données), le message et sa correction. Ces données se lisent à partir du coin en bas à droite en suivant un petit serpent qui zigzague que nous repréciserons deux articles plus loin.

3. Construction du tableau de bits

Mon premier code était un pur code impératif qui nécessitait un suivi minutieux des données d’une fonction à la suivante. Bref, c’était laid et peu pratique. Allez, je me lance, j’essaie la programmation orientée objet à l’acronyme si amusant en anglais [5].

J’ai finalement utilisé une unique classe qrdecode dont un membre de la classe — une instance — essai, contient tous les éléments — ses attributs — du nom du fichier au contenu textuel du message. Chaque fonction — ou méthode — est une étape dans le décodage, de la lecture du fichier à la production du message. Elles s’appellent les unes les autres, à la manière de poupées russes si un attribut (ou donnée) de l’instance n’est pas défini (c’est-à-dire s’il vaut None) au début de l’exécution de la méthode qui en a besoin. Bien entendu, à des fins de jeu ou de débogage, on peut toujours remplir soi-même ces attributs au sein du code.

Après l’initialisation de l’instance et son affichage, les méthodes transforment progressivement l’image brute en un tableau de bits : chargement et en passant recadrage si nécessaire, puis recherche des dimensions d’un module. Enfin, l’image est tournée si elle est mal orientée. Ce paragraphe détaille le contenu de l’article suivant.

3.1. Initialisation

Le code sera expliqué méthode par méthode en commençant par l’initialisation. Par ailleurs, il sera renuméroté à partir de 01 à chaque section.

01: #!/usr/bin/python3


03: from PIL import Image
04: from sys import exit,stderr
05: from argparse import *

06: from qrcorps import *

07: from qrcodestandard import *

08: from qrcodeoutils import *

 

10: class qrdecode:
11:  def __init__(self):
12:  [self.fichier,self.corrige,self.tout,self.image,self.module,self.qr,

13:  self.esttourne,self.form,self.formatok,self.nivcor,self.masque,self.dim,

14:  self.version,self.gris,self.code,self.clair,self.redondant,self.messageok,

15:  self.mode,self.longueur,self.longclair,self.message] = [None]*22

Il s’agit du constructeur d’une instance de la classe qrdecode.py et pour le moment, chaque attribut vaut None. Les noms des attributs sont presque tous parlants par eux-mêmes, ils sont présentés dans l’ordre d’apparition dans le code. Pour des commentaires plus lisibles, j’omettrai systématiquement le préfixe self. dans les noms des attributs et des méthodes.

3.2 Affichage

Avant de s’intéresser aux méthodes particulières à la classe (voir article suivant), commençons par la sortie de notre programme et la méthode __str__.

01:  def __str__(self):

Si on décide d’afficher toutes les informations du code :

02:  if self.tout:

03:  ch=""
04:  if self.fichier is not None:
05:  ch=ch+"Fichier : "+self.fichier+"\n"
06:  if self.formatok is not None and self.formatok is not True:

07:  ch=ch+"Il y a eu besoin de corriger la zone de format.\n"

08:  if self.nivcor is not None:
09:  ch=ch+"Niveau de correction : "+nomnivcor[self.nivcor]+"\n"

nomnivcor (dans qrcodestandard.py) contient les noms longs des niveaux de correction :

nomnivcor={"L":"Low","M":"Medium","Q":"Quality","H":"High"}

On dessine le masque utilisé :

10:  if self.masque is not None:
11:  ch=ch+"Masque :\n"
12:  ch=ch+dessine([[self.masque(i,j) for j in range(6)] for i in range(6)])

La fonction dessine est dans qrcodeoutils.py (voir à la fin de cette section).

Le petit bout de code suivant permet d’afficher les huit masques :

for m in sorted(masques):

print(m)

print(dessine([[masques[m](j,i) for i in range(6)] for j in range(6)]))

 

tableau

Par exemple, le masque (0,0,1) inverse les lignes de rang (pythonique) pair alors que (0,1,1) inverse une diagonale sur trois.

13:  if self.dim is not None:
14:  ch=ch+"Dimensions : "+str(self.dim)+"×"+str(self.dim)+"\n"
15:  if self.version is not None:
16:  ch=ch+"Version : "+str(self.version)+"\n"
17:  if self.messageok is not None and self.messageok is not True:

18:  ch=ch+"Il y a eu besoin de corriger %d erreur(s) dans la zone de données.\n"%self.messageok

19:  if self.mode is not None:
20:  ch=ch+"Mode : "+modes[self.mode]+"\n"

modes est dans qrcodestandard.py avec la définition suivante :

modes={0:"Numeric",1:"Alphanumeric",2:"Byte",3:"Kanji"}

Et enfin :

21:  if self.longclair is not None:
22:  ch=ch+"Longueur du message : "+str(self.longclair)+"\n"
23:  if self.message is not None:
24:  ch=ch+"Message :\n"+self.message+"\n"
26:  return ch[:-1]

Si on choisit de tout afficher avec l’option -a 1, tout ce qui est utile et défini (donc distinct de None) est ajouté à la queue leu leu (tout le monde s’amuse) dans la chaîne de caractères ch, qui est retournée ligne 26 privée du dernier retour à la ligne. Eh oui, sinon il y a un retour à la ligne en trop et c’est laid.

Si on choisit de n’afficher que le contenu :

28:  else:

29:  return self.message

Cette méthode doit retourner une chaîne et non l’afficher.

Il peut être utile de taper dir(2), dir([2]) ou dir({2}) dans une console Python pour regarder différentes méthodes entourées de doubles _. Ainsi, __str__ sert par exemple aux fonctions print et str. __add__ (qui n’est pas utile ici) sert à ajouter une instance à gauche de quelque chose (à gérer dans le code de la méthode) en utilisant tout simplement l’opérateur +. Ceci nous servira plus loin quand nous créerons de toutes pièces les opérations dans le corps fini formule_1, en clair pour prolonger 2*3-4 avec nos futurs nombres bizarres.

Voici le détail de la fonction dessine :

def dessine(tableau):

dic={0:"·",1:"█",False:"·",True:"█"}

c=""
 for l in tableau:
 c=c+"".join(dic[i] for i in l)+"\n"

return c

Elle sert à afficher le masque de décodage (voir le troisième article de cette série) en noir et blanc dans la console (True ou 1 par un rectangle noir █ et False ou 0 par le petit point ·) et pourrait aussi servir à dessiner le code QR. La méthode join du type str permet de concaténer directement les éléments d’un type itérable (liste, ensemble…) si ce sont des chaînes. Le séparateur est ici vide mais il peut être n’importe quelle autre chaîne comme une espace ou un tiret.

31:  def __repr__(self):

32:  if self.message is not None:

33:  return self.message

34:  return "Rien n’est défini."

La méthode __repr__, au cas où, ne retourne que le message.

Conclusion

Le décor est planté, l’article suivant va transformer l’image de notre code QR en un tableau de bits dans le but de finalement lire effectivement son contenu.

Références

[1] Les codes QR sont protégés par neuf brevets au Japon et au États-Unis : http://www.qrcode.com/en/patent.html.

[2] Le code et les exemples sont présents ici https://github.com/GLMF.

[3] La bibliothèque PIL est ici : http://effbot.org/imagingbook/.

[4] Reed–Solomon codes for coders : https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders et le complément plus précis : https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders/Additional_information. Le code QR utilisé dans cet article a été créé sur le site https://www.the-qrcode-generator.com/.

[5] Also sprach Winnie the POO



Article rédigé par

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

Les derniers articles Premiums

Les derniers articles Premium

Du graphisme dans un terminal ? Oui, avec sixel

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

On le voit de plus en plus, les outils en ligne de commandes s'étoffent peu à peu d'éléments graphiques sous la forme d'émojis UTF8. Plus qu'une simple décoration, cette pointe de « graphisme » dans un monde de texte apporte réellement un plus en termes d'expérience utilisateur et véhicule, de façon condensée, des informations utiles. Pour autant, cette façon de sortir du cadre purement textuel d'un terminal n'est en rien une nouveauté. Pour preuve, fin des années 80 DEC introduisait le VT340 supportant des graphismes en couleurs, et cette compatibilité existe toujours...

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.

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