Générer un QR code étape par étape

 (nayuki.io)
5 points par GN⁺ 2024-11-19 | 1 commentaires | Partager sur WhatsApp
  • Il est possible de suivre le processus interne qui transforme un texte en QR code grâce à une visualisation des étapes 0 à 9, et de comprendre le fonctionnement de la bibliothèque Nayuki QR Code generator
  • L’entrée d’exemple Hello, world! 123 est analysée comme 17 points de code Unicode et encodée en mode Byte, puisqu’elle ne relève ni du mode Numeric, ni Alphanumeric, ni Kanji
  • La concaténation des bits de mode, du nombre de caractères, des données de segment et des bits de terminaison produit 19 mots de code de données, ce qui correspond à la capacité du niveau ECC L de la Version 1
  • Un QR code Version 1 place 19 mots de code de données et 7 mots de code ECC Reed–Solomon dans un seul bloc, puis dispose les motifs fixes et les modules de données
  • Après comparaison des pénalités des 8 masques, le Mask pattern 3, au score total le plus faible, est choisi ; le résultat final ne dépend donc pas d’un simple encodage, mais aussi d’une évaluation de qualité

Objectif de la démo et traitement de l’entrée

  • Cette application web visualise étape par étape le processus par lequel une chaîne de texte est encodée en QR code
  • La page décompose le processus d’encodage afin d’aider à comprendre le fonctionnement interne de la QR Code generator library
  • Les champs de saisie utilisateur comprennent la chaîne de texte, le niveau de correction d’erreurs, la Version minimale imposée et le motif de masque imposé

Étape 0 : analyse des caractères Unicode

  • La chaîne d’exemple est Hello, world! 123, et le texte saisi compte 17 points de code
  • Chaque caractère est testé pour vérifier s’il peut être encodé en mode Numeric, Alphanumeric, Byte ou Kanji
  • La possibilité d’encoder toute la chaîne selon chaque mode est la suivante
    • Numeric : impossible
    • Alphanumeric : impossible
    • Byte : possible
    • Kanji : impossible
  • Le mode de segment choisi pour contenir tous les caractères est Byte

Étape 1 : création du segment de données

  • Chaque caractère est converti en chaîne de bits
  • En modes Numeric et Alphanumeric, les caractères consécutifs sont regroupés pour l’encodage
  • En mode Byte, un caractère produit 8, 16, 24 ou 32 bits
  • Dans l’exemple, la valeur hexadécimale de chaque caractère est convertie en 8 bits
    • H : 48 → 01001000
    • e : 65 → 01100101
    • 1 : 31 → 00110001
    • 2 : 32 → 00110010
    • 3 : 33 → 00110011
  • Pour simplifier, le programme de démonstration crée toujours un seul segment
  • La stratégie de découpage optimale qui réduit la longueur totale en bits est traitée séparément dans optimal text segmentation for QR codes

Étape 2 : ajustement du numéro de Version

  • La longueur totale en bits nécessaire pour représenter la liste de segments dépend de la plage de Versions
    • Versions 1 à 9 : 148 bits, 19 mots de code
    • Versions 10 à 26 : 156 bits, 20 mots de code
    • Versions 27 à 40 : 156 bits, 20 mots de code
  • Un mot de code est défini comme 8 bits, soit 1 octet
  • La capacité en mots de code de données d’un QR code dépend de la Version et du niveau de correction d’erreurs
  • L’entrée d’exemple tient dans la Version 1 avec le niveau de correction d’erreurs sélectionné
  • Le numéro de Version finalement choisi est 1

Étape 3 : concaténation des segments, padding et génération des mots de code

  • Plusieurs chaînes de bits sont concaténées pour former le flux de bits de données
    • Mode du segment 0 : 0100, 4 bits
    • Nombre du segment 0 : 00010001, 8 bits
    • Données du segment 0 : 136 bits
    • Terminator : 0000, 4 bits
  • Le nombre cumulé de bits est de 152 bits
  • Dans l’exemple, le Bit padding et le Byte padding font tous deux 0 bit
  • Les octets de mots de code de données complets sont découpés par groupes de 8 bits et affichés en hexadécimal
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

Étape 4 : division en blocs, ajout de l’ECC et entrelacement

  • Les statistiques des blocs de l’exemple sont les suivantes
    • Nombre de mots de code de données : 19
    • Nombre de blocs : 1
    • Mots de code de données par bloc court : 19
    • Mots de code de données par bloc long : sans objet
    • Mots de code ECC par bloc : 7
    • Nombre de blocs courts : 1
    • Nombre de blocs longs : 0
  • La séquence de mots de code de données est divisée en blocs courts et longs, puis les mots de code ECC sont calculés et ajoutés à la fin de chaque bloc
  • Le processus mathématique de calcul du code de correction d’erreurs Reed–Solomon est omis au motif qu’il est long, fastidieux et peu intéressant
  • La séquence finale de mots de code est composée en entrelaçant les mots de code de données et ECC
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
  • Le flux de bits final à dessiner selon le scan en zigzag est également généré à partir de cette séquence de mots de code

Étapes 5 à 6 : placement des motifs fixes et des mots de code

  • À l’étape des motifs fixes, un timing pattern est dessiné sur la ligne 6 et la colonne 6
  • Dans les trois coins, un finder pattern 8×8 est placé, separator inclus
  • Des dummy format bits temporaires sont insérés autour des finder patterns
  • À l’étape du placement des mots de code, un scan en zigzag démarrant dans le coin inférieur droit est calculé
  • Le scan en zigzag saute les modules fonctionnels (function modules) et parcourt les modules qui n’ont pas encore été remplis
  • Les modules de données, d’ECC et de remainder sont dessinés selon les valeurs de bits des mots de code finaux et l’ordre du zigzag
  • Par exemple, le mot de code hexadécimal C5 correspond au binaire 11000101 et produit la séquence de modules [dark, dark, light, light, light, dark, light, dark]

Étapes 7 à 9 : application des masques et calcul des pénalités

  • Chaque motif de masque n’affecte que les modules non fonctionnels (non-function modules)
  • Le masque est appliqué par XOR aux modules de données, d’ECC et de remainder
  • Les véritables format bits sont dessinés autour des finder patterns
  • La recherche de pénalités examine les éléments suivants
    • Les runs horizontaux d’au moins 5 modules de même couleur
    • Les runs verticaux d’au moins 5 modules de même couleur
    • Les carrés 2×2 de même couleur
    • Les motifs horizontaux ressemblant à un finder pattern
    • Les motifs verticaux ressemblant à un finder pattern
    • L’équilibre entre modules sombres et modules clairs
  • La taille et le ratio de couleurs du QR code d’exemple sont les suivants
    • Longueur d’un côté : 21
    • Total des modules : 441
    • Modules clairs : 221
    • Modules sombres : 220
    • Proportion de modules sombres : 49,887 %
    • Écart par rapport à la moitié : −0,113 %
  • Les pénalités totales des 8 masques sont les suivantes
    • Mask 0 : 1204
    • Mask 1 : 1134
    • Mask 2 : 1084
    • Mask 3 : 1081
    • Mask 4 : 1121
    • Mask 5 : 1100
    • Mask 6 : 1189
    • Mask 7 : 1137
  • Le masque ayant obtenu la pénalité totale la plus faible est le Mask pattern 3

Code source

À lire aussi

1 commentaires

 
GN⁺ 2024-11-19
Avis sur Hacker News
  • C’est dommage que les explications sur les QR codes, où qu’on les cherche en ligne, semblent toujours faire l’impasse sur le calcul de correction d’erreurs Reed-Solomon.
    Ici aussi, l’auteur dit que c’est « long, fastidieux et pas très intéressant », mais comme tout le monde semble penser ainsi, c’est devenu assez difficile à trouver.
    • J’ai suivi un cours de théorie des codes en école doctorale ; c’était le cours le plus rigoureux que j’aie suivi, difficile pour nous cinq, mais je suis content de l’avoir pris.
      Reed-Solomon a été abordé un peu après le milieu du semestre, et l’idée centrale est que cela repose sur les polynômes. Avec suffisamment de points, un polynôme est déterminé exactement ; donc si l’on ajoute des points redondants, on peut le reconstruire même si certains disparaissent.
      Le reste consiste à appliquer cela aux données binaires, c’est-à-dire à utiliser des corps finis ; c’est mathématiquement élégant, mais ça devient assez complexe.
    • Ces deux tutoriels expliquent le calcul de correction d’erreurs :
      https://www.thonky.com/qr-code-tutorial/error-correction-cod...
      https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
    • https://www.quaxio.com/an_artisanal_qr_code.html et PagedOut! Issue #2 expliquent comment créer un QR code à partir de zéro, correction d’erreurs incluse avec une division longue.
    • C’est long et fastidieux, mais c’est en réalité la partie la plus intéressante de tout le sujet.
    • Il existe un article Wikipédia à ce sujet.
  • La récente vidéo de Veritasium, I used to hate QR codes. But they're actually genius, traite aussi de ce thème.
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • La compilation des retours reçus par l’auteur est assez amusante : https://www.nayuki.io/page/poor-feedback-from-readers
    • Se moquer de gens qui maîtrisent mal l’anglais, et faire des commentaires dénigrants sur tout un pays comme si les personnes ayant envoyé ces e-mails en étaient un échantillon représentatif, en dit plus sur le propriétaire du blog que sur les expéditeurs.
      Les commentaires dégagent une forte impression d’élitisme. En parcourant rapidement le blog, on voit qu’il demande des dons en Bitcoin en suggérant 3 $, mais il ne semble pas tenir compte du fait qu’une bonne partie pourrait disparaître en frais.
    • Même si l’on reçoit des messages déplaisants, il vaut mieux éviter de mêler à ses plaintes un racisme léger et des critiques du niveau d’anglais de l’auteur.
    • Se moquer d’un anglais maladroit est toujours un signe de bêtise. Les gens intelligents peuvent aussi se comporter comme des idiots.
    • Désolé, mais l’auteur du blog donne l’impression d’être quelqu’un d’assez antipathique.
      Ça ressemble à : « Non, tu ne peux pas utiliser le code de mon dépôt GitHub pour ton chatbot de projet universitaire. Tes standards de codage ne sont pas à la hauteur des miens. Et ton anglais est nul. »
    • Je comprends à quel point tenir un blog personnel peut être pénible. Il faut gérer toutes sortes de gens.
      Heureusement, il partage aussi séparément les bons retours : https://www.nayuki.io/page/decent-feedback-from-readers
  • C’est plutôt excellent. J’aimerais voir un décodeur conçu de la même manière.
    • Vous pourriez aussi aimer le guide de Piko et blinry sur la façon de lire un QR code sans ordinateur : https://qr.blinry.org/
    • Je suis d’accord. Je suis toujours étonné de voir à quelle vitesse un téléphone peut décoder un QR code sombre, flou et dont environ un quart sort de l’écran.
    • Je cherche toujours un guide pour implémenter un lecteur de QR codes à partir de zéro.
      Je ne veux pas d’un truc du genre « branchez simplement cette bibliothèque de vision par ordinateur et donnez-lui l’image, elle renverra le résultat », comme on en voit sur Google.
      Je cherche un guide qui parte du principe qu’on dispose déjà des données brutes de l’image décodée, puis qui implémente tous les algorithmes nécessaires.
  • J’apprécie qu’il y ait une explication. Personnellement, je voulais juste en générer un rapidement, mais les recherches me donnaient des sites bourrés de pubs ou des sites « inscription obligatoire ».
    J’en ai aussi trouvé quelques-uns sur GitHub, mais ils avaient d’autres problèmes ; j’ai donc rapidement fait le mien avec une bibliothèque bien conçue que j’avais déjà utilisée, et ça m’a pris environ 15 minutes.
    https://greggman.github.io/qr-code/
    On pourrait ajouter davantage d’options, mais en réalité la plupart des utilisateurs n’en ont probablement pas besoin.
    • Ravi que ça ait été utile. Moi aussi, je voulais depuis un moment essayer d’écrire ma propre implémentation, mais tout ce que j’avais pu trouver, c’étaient des packages complets pour Python ou Golang.
      Si quelqu’un connaît de bonnes ressources pour comprendre la partie correction d’erreurs liée aux QR codes, je suis preneur.
  • J’avais fait une implémentation en Rust il y a quelque temps.
    https://github.com/aabiji/qr
  • Quand un article n’est pas de l’année en cours, c’est une bonne pratique d’ajouter l’année de l’article dans le titre, ici 2018.
    • D’accord. Le lien original ne comportait pas de date à mes yeux, et je ne peux plus le modifier maintenant.
  • Très bien. Comprendre le fonctionnement des QR codes était sur ma liste de choses à faire depuis longtemps, et c’était un bon article d’introduction.
  • Maintenant que vous savez comment ça marche, vous pouvez aussi l’utiliser dans des requêtes SQL : https://github.com/Florents-Tselai/pgQR