Expliquer un code QR

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


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




Articles qui pourraient vous intéresser...

Simulation d’un ordinateur mécanique en scriptant sous FreeCAD

Magazine
Marque
Hackable
Numéro
35
Mois de parution
octobre 2020
Domaines
Résumé

L’évolution du traitement du signal est une histoire fascinante largement déroulée par David Mindell dans ses divers ouvrages [1] et citations [2]. Partant de l’ordinateur mécanique avec ses rouages, poulies, bielles et crémaillères, le passage à l’électrique au début du 20ème siècle, puis à l’électronique intégrée avec l’avènement du transistor et des circuits intégrés (VLSI) nous ont fait oublier les stades initiaux qui ont amené à notre statut actuel d’ordinateurs infiniment puissants, précis et compacts. Alors que cette histoire semble s’accompagner du passage de l’analogique au numérique – de la manipulation de grandeurs continues en grandeurs discrètes avec son gain en stabilité et reproductibilité – il n’en est en fait rien : un boulier fournit déjà les bases du calcul discrétisé mécanique, tandis que [3] introduit les concepts du calcul mécanique avec les traitements numériques avant de passer aux traitements analogiques.

Conservez l’historique de vos commandes pour chaque projet, le retour

Magazine
Marque
GNU/Linux Magazine
Numéro
241
Mois de parution
octobre 2020
Domaines
Résumé

Pouvoir conserver un historique dédié pour chaque projet, voici l’idée géniale énoncée par Tristan Colombo dans un précédent article de GLMF [1]. Cet article reprend ce concept génial (je l’ai déjà dit?) et l’étoffe en simplifiant son installation et en ajoutant quelques fonctionnalités (comme l’autodétection de projets versionnés pour proposer à l’utilisateur d’activer un historique dédié, si ce n’est pas le cas).