Dessiner un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
199
|
Mois de parution
décembre 2016
|
Domaines


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


Sur le même sujet

Exporter une application Godot dans différents formats

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
109
|
Mois de parution
juillet 2020
|
Domaines
Résumé

Vous avez terminé votre application et vous souhaitez maintenant la distribuer ? Il faut donc que vous convertissiez - ou exportiez - votre programme, pour qu'il puisse être exécuté sur les plateformes cibles. Nous verrons dans cet article les exports vers le Web, Windows et Android.

Machine Learning sur des objets connectés avec TensorFlow Lite pour l’agriculture verticale

Magazine
Marque
GNU/Linux Magazine
Numéro
239
|
Mois de parution
juillet 2020
|
Domaines
Résumé

Tout au long de cet article, nous verrons comment déployer des algorithmes de Deep Learning sur des objets connectés grâce à TensorFlow Lite. Nous verrons comment l’utiliser pour concevoir une « ferme verticale » capable de prédire et optimiser la production de légumes, aussi bien chez soi que dans des pays en voie de développement où la connexion internet est intermittente.

À la découverte de Godot

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
109
|
Mois de parution
juillet 2020
|
Domaines
Résumé
  • Godot ? D'habitude on l'attend, on ne le découvre pas, comme dans la pièce de théâtre de Samuel Beckett...
  • Je parle du moteur 3D.
  • Un moteur 3D ? Non, je connais Unity, Unreal Engine, mais pas celui-là.
  • Alors, découvrons dans cet article Godot, « The game engine you waited for ».

Émulation d’un circuit comportant un processeur Atmel avec simavr

Magazine
Marque
Hackable
Numéro
34
|
Mois de parution
juillet 2020
|
Domaines
Résumé

Il existe de nombreux cas où le matériel n’est pas disponible pour développer un système embarqué, que ce soit parce que la carte commandée n’a pas encore été livrée, parce que le collègue chargé de la conception du circuit imprimé a fait une erreur ou est en retard, ou parce qu’un virus interdit l’accès aux salles de travaux pratiques de l’Université (Fig. 1). Pour toutes ces raisons, nous désirons appréhender le développement d’un système embarqué sur un émulateur, c’est-à-dire un logiciel capable de fournir une représentation fidèle du comportement du dispositif réel, incluant ses latences et temporisations.

Utilisez GitLab pour la gestion globale de vos projets en équipe

Magazine
Marque
Linux Pratique
Numéro
120
|
Mois de parution
juillet 2020
|
Domaines
Résumé

D’après Wikipédia, GitLab est un « logiciel libre de forge basé sur Git [1] proposant les fonctionnalités de wiki, un système de suivi des bugs, l’intégration continue et la livraison continue » [6]. Il est développé par la société GitLab Inc. et est très utilisé par les entreprises informatiques, mais aussi les centres de recherche et les équipes produisant des logiciels libres. Sa première version date d’octobre 2011 et il n’a pas cessé d’évoluer depuis. GitLab est donc une plateforme permettant d’héberger et de gérer des projets dans leur ensemble. Elle offre la possibilité de gérer ses dépôts Git et permet une gestion de tout le processus de développement de l’idée à la production. Elle propose ainsi une collaboration simple et efficace entre les différents participants d’un même projet.

Les namespaces ou l’art de se démultiplier

Magazine
Marque
GNU/Linux Magazine
Numéro
239
|
Mois de parution
juillet 2020
|
Domaines
Résumé

Notions indispensables aux mécanismes d’isolation, mais plutôt méconnus du grand public, les namespaces sont devenus incontournables dans l’environnement Linux. Ils sont, le plus souvent, utilisés de manière implicite à travers les gestionnaires de conteneurs tels que LXC.

Par le même auteur

Dessiner un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
199
|
Mois de parution
décembre 2016
|
Domaines
Résumé
Et voilà le dernier article de cette longue série sur les codes QR. À son issue, nous saurons les dessiner.

Préparer un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
199
|
Mois de parution
décembre 2016
|
Domaines
Résumé
Les articles précédents [1-6] vous ont donné envie de créer vos propres codes QR ? Ce sera chose faite ici même, pour le moment on prépare les données binaires.

Réparer un code QR

Magazine
Marque
GNU/Linux Magazine
Numéro
198
|
Mois de parution
novembre 2016
|
Domaines
Résumé
Nous terminons cette première série sur la lecture des codes QR par la réparation automatique de sa zone de format et de sa zone de données.

Fabriquer un corps fini

Magazine
Marque
GNU/Linux Magazine
Numéro
196
|
Mois de parution
septembre 2016
|
Domaines
Résumé
Pour corriger un code QR avec erreur ou rature, nous avons besoin de construire le corps fini F256 et son anneau de polynômes.