Dessiner un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
199
Mois de parution
décembre 2016
Spécialité(s)


Résumé

Et voilà le dernier article de cette longue série sur les codes QR. À son issue, nous saurons les dessiner.


Body

Dans l’article précédent, nous avons préparé les données binaires, il reste à créer la matrice, le masquage et l’image. Nous reprendrons à l’envers la lecture des premiers articles.

Les données sont créées et prêtes à être rangées dans la matrice. Le code et les fichiers sont sur le GitHub du magazine.

1. Création du tableau

1.1. Les invariants

On commence par placer les zones obligatoires : les grandes cibles, les petites si nécessaire, les pointillés et le module toujours noir.

01:  def matrice(self):
02:     if self.entrelac is None:
03:        self.entrelacement()
05:     self.dim=17+4*self.version
06:     self.tabmat=[[0 for _ in range(self.dim)] for _ in range(self.dim)]

On crée d’abord la matrice carrée de dimensions 17+4×version.

07:  for i in range(self.dim):
08:     self.tabmat[6][i]=1-i%2

09:     self.tabmat[i][6]=1-i%2

On place les échelles (les lignes noires et blanches en haut et à gauche).

10:  for i in range(7):
11:     self.tabmat[i][:7]=cible[i]
12:     self.tabmat[-i-1][:7]=cible[i]
13:     self.tabmat[i][-7:]=cible[i]

On place les trois grandes cibles dans tous les coins sauf celui en bas à droite.

14:  self.tabmat[-8][8]=1

On place le module toujours noir en haut de la cible inférieure.

15:  liste=minicibles[self.version]
16:     for ci in liste:
17:        for cj in liste:
18:           if (ci,cj) not in {(6,6),(6,max(liste)),(max(liste),6)}:
19:              for i in range(ci-2,ci+3):
20:                 self.tabmat[i][cj-2:cj+3]=minicible[i+2-ci]

Et on place les mini-cibles sauf si elles chevauchent les grandes.

1.2. Remplissage du tableau

On a encore besoin de préparer la zone où le petit serpent dépose ses données.

01:  def remplissage(self):
02:     if None in [self.dim,self.tabmat]:
03:        self.matrice()
05:     self.gris=griser(self.dim,self.version)
06:     i,j=self.dim-1,self.dim-1
07:     dire=-1
08:     k=0
10:     while k<len(self.entrelac):
11:        if self.gris[i][j]:
12:        self.tabmat[i][j]=self.entrelac[k]
13:        k+=1
14:     i,j,dire=suivant(i,j,dire,self.dim)

C’est à peu près le même code que pour la lecture, mais on écrit au lieu de lire. Je rappelle qu’on parcourt les modules disponibles (ceux pour lesquels gris[i][j] vaut True) en serpentant dans des colonnes de deux modules de largeur en partant du bas de la grille.

1.3. Calcul du code de contrôle de la version

Il s’agit ici de placer les deux rectangles de 3×6 modules présents uniquement si la version est supérieure ou égale à 7. L’un est placé au-dessus de la cible inférieure entre l’échelle et le bord, l’autre est placé verticalement à gauche de la cible de droite.

01:  def codecontrolev7(self):
02:     if None in [self.dim,self.tabmat]:
03:        self.remplissage()


05:     if self.version>=7:
06:        pol=[int(i) for i in "1111100100101"]

07:        liste=dec2bin(self.version,6)
08:        liste+=[0]*12
09:        while liste[0]==0:
10:           del(liste[0])
11:        while len(pol)<len(liste):
12:           pol.append(0)
13:        while len(liste)>12:
14:           liste=[i^j for (i,j) in zip(liste[:len(pol)],pol)]+liste[len(pol):]
15:        while liste[0]==0:
16:           del(liste[0])
17:     liste=[0]*(12-len(liste))+liste
18:     liste=dec2bin(self.version,6)+liste

19:     liste.reverse()

Vous avez reconnu une division euclidienne dans 𝔽2 similaire à celle de la zone de formats, mais par le polynôme X12+X11+X10+X9+X8+X5+X2+1 des lignes 13 à 16. Ensuite, on bourre avec des 0 pour obtenir exactement douze bits : six bits de version (40⩽26=64) plus douze bits de correction font bien dix-huit bits au total.

21:  for i in range(3):
22:     self.tabmat[-11+i][:6]=liste[i::3]
23:  for i in range(6):

24:     self.tabmat[i][-11:-8]=liste[3*i:3*i+3]

On place la zone inférieure puis la zone supérieure.

1.4. Calcul du meilleur masque et placement des zones de formats

1.4.1. Choix du masque

Il reste à choisir le meilleur masque parmi les huit possibles pour éviter des cibles mal placées, un déséquilibre trop criant entre le blanc et le noir ou des zones monochromes trop grandes.

01:  def choixmasque(self):
02:     if None in [self.dim,self.tabmat]:
03:        self.codecontrolev7()

05:     cor=correctionniveau[self.nivcor]
06:     dmin=None
08:     for m in range(8):
09:        if self.masque is not None and self.masque!=m:

10:           continue

Si le masque est imposé par l’option m, on ne calcule que pour ce masque. Sinon, on teste les huit masques un par un et on choisit le meilleur en tenant compte des zones de formats.

11:  tab=[list(l) for l in self.tabmat]
12:  ma=tuple(dec2bin(m,3))
13:  forma=cor+ma
14:  forma=forma+tuple(dec2bin(resteformat(bin2dec(forma)),10))
15:  forma=[i^j for (i,j) in zip(forma,masquef)]
16:  tab[8][:6]=forma[:6]
17:  tab[8][7:9]=forma[6:8]
18:  tab[7][8]=forma[8]
19:  for i in range(6):
20:     tab[i][8]=forma[-1-i]
21:     tab[8][-8:]=forma[-8:]
22:  for i in range(7):
23:     tab[-i-1][8]=forma[i]

Pour chaque masque m, on place les zones de formats correspondantes dans tab, une copie de la matrice tabmat.

24:  masquet=masques[ma]
25:  for i in range(self.dim):
26:     for j in range(self.dim):
27:        if self.gris[i][j]:
28:           tab[i][j]^=masquet(i,j)

On effectue le masque binaire sur tab.

29:  mal=malus(tab)

30:  if dmin is None or mal<dmin:
31:     dmin=mal

32:     self.bontab=tab

On calcule le malus avec la fonction idoine. Si on trouve mieux ou si le malus n’est pas encore défini, on stocke le plus petit malus dans dmin et la meilleure matrice dans bontab.

1.4.2. Calcul du malus

Détaillons le calcul du malus pour une matrice. Il existe quatre malus différents qui s’accumulent. On peut remarquer qu’une matrice de code QR ne peut pas avoir de malus nul.

def malus(table):

   m=0

 

   def m1(ligne):

      ch="".join(map(str,ligne))

      c=0

      for cinq in ["11111","00000"]:

         i=-1

         while i<len(ch):

            i+=1

            if cinq in ch[i:]:

               i+=ch[i:].index(cinq)

               c-=2

               while ch[i]==cinq[0]:

                  i+=1

                  c+=1

                  if i==len(ch):

                     break

   return c

Le malus des suites constantes trop longues : une suite de cinq modules ou plus de la même couleur est pénalisée de sa longueur moins 2, autrement dit, 1111111 (sept 1) est pénalisé de 5 points et 0000000000 (dix 0) est pénalisé de 8 points. La fonction le calcule pour une seule ligne.

Le pointeur i se place à la première position où on a repéré le motif, mais seulement à partir de i dans le but de ne pas compter plusieurs fois le même motif. À partir de cette position, on compte le nombre de bits successifs identiques qu’on ajoute au malus c.

for l in table:

   m+=m1(l)

for i in range(len(table)):

   m+=m1([l[i] for l in table])

On additionne le malus pour chaque ligne puis pour chaque colonne.

def m2(table):

   c=0

   for i in range(len(table)-1):

      for j in range(len(table)-1):

         c+=3*(table[i][j]==table[i+1][j]==table[i][j+1]==table[i+1][j+1])

   return c

 

m+=m2(table)

Chaque carré monochrome de 2×2 est pénalisé de 3 points, un carré monochrome de 3×3 contient donc quatre carrés de 2×2 et est pénalisé de 3×4=12 points.

def m3(ligne):

   ch="".join(map(str,ligne))

   return 40*(ch.count("10111010000")+ch.count("00001011101"))

 

   for l in table:

      m+=m3(l)

   for i in range(len(table)):

      m+=m3([l[i] for l in table])

La présence du motif central des cibles suivi ou précédé de quatre 0 est pénalisé de 40 points, horizontalement comme verticalement, vers la droite comme vers la gauche.

def m4(table):

   m4n=sum(sum(l) for l in table)

   m4t=len(table)**2

   pourcent=100*m4n//m4t//5*5

   return min(abs(50-pourcent),abs(50-pourcent+5))//5*10

 

m+=m4(table)

m4n compte le nombre de 1 dans la matrice, m4t le nombre de modules au total. On calcule le pourcentage de 1 arrondi par défaut et par excès à 5 près. Le malus est l’écart entre le pourcentage arrondi le plus près de 50 multiplié par 2.

return m

Et on retourne le malus total.

2. Création de l’image

La matrice est prête, il reste à déverser son contenu dans une image.

2.1. Création et sauvegarde

01:  def creation(self):
02:  if self.bontab is None:
03:     self.choixmasque()
05:  self.taille=(8+self.dim)*self.arguments.t
06:  im=Image.new("RGB",(self.taille,self.taille),"white")
07:  blanc=(255,255,255)

08:  self.image=[blanc]*self.taille*4*int(self.arguments.t)

On crée image, la matrice des pixels qui doit avoir quatre modules blancs supplémentaires tout autour, d’où le 8+dim ligne 05. Pour le moment, elle ne contient que la première ligne blanche de quatre modules de haut. On crée aussi im, l’image qui sera gérée par PIL, c’est un carré de fond blanc.

09:  for i in range(self.dim):
10:     for _ in range(self.arguments.t):
11:        self.image.extend([blanc]*4*self.arguments.t)
12:        for j in range(self.dim):
13:           couleur=255-255*self.bontab[i][j]
14:           self.image.extend([(couleur,couleur,couleur)]*self.arguments.t)
15:        self.image.extend([blanc]*4*self.arguments.t)
16:     self.image.extend([blanc]*self.taille*4*self.arguments.t)

On ajoute quatre modules blancs au début de chaque ligne, on crée les modules de largeur arguments.t et on termine par quatre modules blancs. On crée arguments.t lignes identiques pour que les modules soient bien carrés et on termine par les quatre lignes de modules blancs.

17:  im.putdata(self.image)

Et on déverse l’image dans im, c’est plus rapide ainsi. PIL s’occupe lui-même de gérer les dimensions réelles de l’image, car image est en fait une seule liste et non une liste de listes comme bontab.

18:  try:
19:     logo=Image.open(self.arguments.c)
20:     m=max(logo.width,logo.height)
21:     logo=logo.resize((self.taille//4*logo.width//m,self.taille//4*logo.height//m),\

Image.ANTIALIAS)
22:     im.paste(logo,(self.taille//2-logo.width//2,self.taille//2-logo.height//2),logo)
23:  except AttributeError:
24:     pass
25:  except IOError:
26:     print("Fichier %s inaccessible."%self.arguments.c)

27:     exit(1)

Si l’imagette est donnée en ligne de commandes, on la colle, réduite, lissée et avec transparence, au milieu du code QR. Elle prend, dans sa plus grande dimension, le quart du code QR pour ne pas le rendre illisible. Si l’imagette n’est pas définie, on passe et si son fichier n’est pas lisible (inexistant, ou droits insuffisants), on s’arrête.

29:  if self.arguments.a=="1":
30:     im.show()

31:  im.save(self.arguments.o)

Si on a demandé à afficher le code QR, on le fait via xv sous Unix selon la documentation ou paint sous Windows. Enfin, on sauvegarde l’image.

2.2. Résultat

Testons notre beau code.

01: if __name__=="__main__":
02:    code=qrencode()
03:    code.creation()

Et voilà, la figure 1 est le résultat de la commande suivante où linus.txt est le message de Linus décodé précédemment et Tux.svg.png notre manchot préféré :

> ./qrencode.py -i linus.txt -o linux2.png -t 2 -c Tux.svg.png

imagePIL

Fig. 1 : Le code QR obtenu.

Un œil exercé verra une petite différence entre cette image et celle lue dans l’article sur la correction, tout en bas à gauche, à la fin des blocs de correction. J’ai un léger bogue, mais comme les codes QR sont auto-correcteurs...

> ./qrdecode.py -i linux2.png -a1

Fichier : linux2.png

Niveau de correction : Low

Masque :

█··█··

█··█··

█··█··

█··█··

█··█··

█··█··

Dimensions : 105×105

Version : 22

Il y a eu besoin de corriger 44 erreur(s) dans la zone de données.

Mode : Byte

Longueur du message : 949

Message :

Hello everybody out there using minix -

 

I'm doing a (free) operating system (just a hobby, won't be big and

Attention aussi au tout dernier caractère du fichier en entrée, si vous voulez obtenir la même chose que [1], vous devez veiller à supprimer le dernier retour à la ligne (ouvrez votre fichier avec un éditeur hexadécimal comme ghex pour comprendre) ou à l’ajouter dans le texte copié sur le site.

Conclusion

La création de cette image prend sept secondes, c’est beaucoup trop. Une étude sérieuse du code permettrait de trouver où l’améliorer et quelles parties du code sont lentes.

Pour aller plus loin

Par ailleurs, il reste à coder le dernier mode (kanji) ainsi que les autres codages de texte et les codes QR à long contenu partagé. La lecture pourrait aussi s’accommoder de codes QR dont les modules ne sont plus carrés ainsi que de codes QR photographiés ou filmés (donc pas exactement vus de face).

Enfin, on peut s’attaquer aux autres versions des codes QR (micro QR et version 1) comme aux autres codes à barres comme le code Aztec, le MaxiCode ou le DataMatrix.

Référence

[1] Générateur de code QR : https://www.the-qrcode-generator.com/.



Article rédigé par

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

Les derniers articles Premiums

Les derniers articles Premium

Cryptographie : débuter par la pratique grâce à picoCTF

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

L’apprentissage de la cryptographie n’est pas toujours évident lorsqu’on souhaite le faire par la pratique. Lorsque l’on débute, il existe cependant des challenges accessibles qui permettent de découvrir ce monde passionnant sans avoir de connaissances mathématiques approfondies en la matière. C’est le cas de picoCTF, qui propose une série d’épreuves en cryptographie avec une difficulté progressive et à destination des débutants !

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