Et voilà le dernier article de cette longue série sur les codes QR. À son issue, nous saurons les dessiner.
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
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/.