Comment fonctionne techniquement le scan d'un code QR

Votre téléphone décode un code QR en moins de 100 millisecondes. Pendant ce temps, il capture une image vidéo, convertit une photographie à gradient en grille binaire, localise trois cibles dans les coins à l'aide d'un ratio invariant quel que soit l'angle, corrige la distorsion de perspective, échantillonne de 441 à 31 329 cellules individuelles, exécute de l'arithmétique polynomiale sur un corps fini pour récupérer des octets corrompus, et délivre une URL ou une chaîne de texte. Tout cela avant que vous n'ayez consciemment réalisé que vous avez pointé l'appareil photo. La plupart des explications s'arrêtent à « votre téléphone lit le motif ». Celle-ci parcourt chaque étape du fonctionnement technique du scan de code QR, des photons bruts au payload décodé, en suivant le pipeline défini dans ISO/IEC 18004.

Étape 1 : capture d'image et binarisation

L'appareil photo d'un téléphone ne voit pas des modules noirs et blancs. Il capture un gradient de luminance continu : des données JPEG ou brutes où chaque pixel a une valeur de 0 à 255. Le premier travail du décodeur est de convertir cette image en niveaux de gris en une image véritablement binaire. Chaque pixel devient soit 0 (module sombre) soit 1 (module clair). Pas d'entre-deux.

L'approche naïve consiste à choisir un seuil global de 128 et à considérer tout ce qui est plus sombre comme « noir ». Cela échoue dès qu'un code QR est imprimé sur une surface légèrement réfléchissante, scanné sous un éclairage inégal ou placé près d'une fenêtre lumineuse. La partie du code dans l'ombre peut avoir une moyenne autour de 60 tandis que la partie éclairée tourne autour de 180 ; un seuil global unique mal classifie l'une des deux.

Les décodeurs de production utilisent un seuillage adaptatif (local). L'image est divisée en une grille de petites tuiles (ZXing utilise une taille de bloc d'environ 1/8 de la largeur de l'image). Pour chaque tuile, un seuil local est calculé à partir de l'histogramme de luminance de cette seule région. Un pixel est considéré comme sombre si sa valeur tombe suffisamment en dessous de la moyenne locale, typiquement d'un delta de 5 à 10. Ainsi une ombre sur le coin supérieur gauche du code n'affecte pas le seuil appliqué au coin inférieur droit.

Ce qui en sort est une image binaire (bitmap) où chaque cellule du code QR est représentée en noir pur ou blanc pur, à condition que le contraste original soit suffisant. C'est pourquoi le contraste n'est pas une préoccupation cosmétique. Un faible contraste produit des valeurs de pixels ambiguës que le seuillage adaptatif ne peut pas classifier de manière fiable. Un code QR bleu marine sur fond gris foncé ? Mort à l'étape 1, avant que toute autre étape ne s'exécute.

Étape 2 : trouver les motifs de recherche

Avec une image binaire prête, le décodeur doit localiser le code QR à l'intérieur. Les ancres sont les trois motifs de recherche : les grands carrés concentriques situés dans les coins supérieur gauche, supérieur droit et inférieur gauche de chaque code QR.

Chaque motif de recherche a une structure spécifique : un carré central sombre de 3x3, entouré d'une bordure claire d'un module, entourée d'une bordure sombre d'un module. Balayez n'importe quelle ligne horizontale ou verticale passant par le centre et la séquence de longueurs de plages de pixels sombres et clairs produit le ratio 1:1:3:1:1. Un sombre, un clair, trois sombres, un clair, un sombre.

Le décodeur exploite cela en balayant chaque ligne de l'image binaire de gauche à droite, comptant les plages de pixels de même couleur. Chaque fois que cinq plages consécutives apparaissent, il vérifie si leurs longueurs satisfont le ratio 1:1:3:1:1 (avec une tolérance d'environ 0,5x). Les points centraux candidats sont enregistrés. Puis le même balayage est effectué verticalement à travers la colonne de chaque candidat, confirmant que le ratio tient dans les deux directions. Là où les confirmations horizontales et verticales se croisent, vous avez un centre de motif de recherche à haute confiance.

Ce qui rend cela astucieux : le ratio est invariant par rapport à l'échelle et à la rotation. Que le code QR fasse 50 pixels ou 500 de large, qu'il soit tourné de 45 degrés, le ratio tient. La géométrie du motif de recherche encode l'orientation, pas les modules de données. Localisez-en trois, et vous connaissez immédiatement la position, l'échelle et la rotation du code dans l'image.

La zone de silence (la bordure blanche obligatoire de 4 modules autour du code) existe pour servir cette étape. Sans elle, le balayage 1:1:3:1:1 génère des faux positifs à partir d'éléments sombres du fond adjacents au motif de recherche, ou le calcul de la boîte englobante de l'étendue du code est faussé. Les zones de silence manquantes sont l'une des sources les plus courantes d'échecs de scan intermittents sur des codes qui semblent parfaitement corrects à l'œil nu.

Étape 3 : correction de perspective

Les appareils photo font rarement face à un code QR de front. Le code est incliné, déformé ou photographié sous un angle qui fait apparaître un motif carré comme un trapèze. Lire les positions des modules à partir d'une image déformée produit des valeurs erronées, donc le décodeur inverse d'abord la déformation.

Avec les centres des trois motifs de recherche connus, plus le motif d'alignement (présent dans les versions 2+) ou le quatrième coin déduit, le décodeur dispose de quatre points connus dans l'image déformée qui correspondent à quatre positions connues dans une grille idéale, de face. Problème d'homographie classique : trouver la matrice de transformation perspective 3x3 qui fait correspondre les coordonnées déformées à la grille canonique.

L'homographie est calculée par transformation linéaire directe (DLT) ou un solveur similaire. Une fois connue, la position canonique de chaque centre de module se projette sur une coordonnée pixel dans l'image originale, indiquant au décodeur exactement quel pixel échantillonner pour chaque cellule de la grille. La plupart des implémentations font cela de manière paresseuse : calculer la transformation une fois, puis échantillonner chaque module à la demande plutôt que de déformer l'image entière.

Pour les codes QR de version supérieure (version 7 et au-delà, qui peuvent avoir des zones de données denses couvrant une grande surface physique), la dérive de perspective locale à travers la zone du code devient significative. Les motifs d'alignement, de petits carrés concentriques intégrés dans la zone de données à intervalles réguliers, servent de points de calibration supplémentaires. Le décodeur échantillonne les centres des motifs d'alignement et les utilise pour affiner le modèle de perspective localement, divisant le code en régions plus petites, chacune avec sa propre grille d'échantillonnage corrigée.

Étape 4 : échantillonnage de la grille

Après la correction de perspective, le décodeur sait où se situe chaque centre de module dans l'image originale. L'échantillonnage est direct : pour chaque cellule de la grille du code QR, lire la valeur du pixel à la coordonnée projetée et la seuiller en noir ou blanc.

Un point à comprendre : cet échantillonnage réutilise le seuil adaptatif déjà calculé pour cette région de l'image, pas un nouveau seuil global. Le décodeur travaille en espace binaire depuis la première étape. Il récupère simplement maintenant les valeurs à des coordonnées spécifiques.

Le résultat est une grille booléenne 2D, une matrice NxN de valeurs sombres et claires où N va de 21 (version 1) à 177 (version 40). La majeure partie est constituée de données, mais certaines régions ont des significations fixes : les motifs de recherche eux-mêmes, les motifs de synchronisation (des bandes alternant noir et blanc qui calibrent l'espacement de la grille), le module sombre (toujours sombre à une position fixe), et les motifs d'alignement. Le décodeur masque ces zones structurelles et se concentre sur tout le reste.

Étape 5 : lecture des informations de format et de version

Avant d'extraire les données, le décodeur a besoin de deux éléments de métadonnées structurelles : les informations de format et, pour les codes version 7+, les informations de version.

Les informations de format se trouvent en deux copies identiques à des positions fixes adjacentes aux motifs de recherche. Elles encodent 15 bits : 2 pour le niveau de correction d'erreurs (L, M, Q ou H), 3 pour le motif de masque de données, et 10 bits de correction d'erreurs BCH qui protègent les informations de format elles-mêmes contre jusqu'à 3 erreurs de bits. Ces bits sont XORés avec un motif de masque fixe (101010000010010) avant stockage pour qu'ils ne soient jamais tous nuls, même pour les combinaisons défavorables.

Le motif de masque est critique. Les données QR brutes ont souvent de longues séries de modules de même couleur, et l'étape de binarisation interprète mal ces séries comme des artéfacts de frontière. Lors de l'encodage, l'un des huit motifs de masque XOR prédéfinis est appliqué aux modules de données pour casser ces séries. L'encodeur évalue les huit masques et choisit celui qui produit le motif le plus équilibré, à haut contraste, selon un score de pénalité. Sans savoir quel masque a été appliqué, le décodeur ne peut pas l'inverser, et les bits de données sont du charabia.

Se tromper sur les informations de format est fatal. Les deux copies corrompues au-delà de la capacité de correction BCH ? Le décodeur ne peut pas déterminer le motif de masque et ne peut rien déchiffrer. Un autocollant ou une rayure couvrant le coin adjacent à un motif de recherche est bien plus dommageable qu'une destruction équivalente n'importe où ailleurs sur le code.

Étape 6 : extraction des mots de code de données

Le masque connu, le décodeur le XOR à nouveau sur la zone de données, restaurant les bits originaux encodés. Les données sont lues dans un ordre zigzag spécifique : en partant du coin inférieur droit, deux colonnes à la fois, remontant puis descendant en un chemin serpentin alterné, sautant les régions structurelles fixes. Chaque module de données est visité exactement une fois.

Le flux de bits est groupé en mots de code de 8 bits. Les premiers bits spécifient le mode d'encodage : numérique (10 bits pour trois chiffres), alphanumérique (11 bits pour deux caractères), octet (8 bits par caractère), ou Kanji (13 bits par caractère). Un champ de comptage de caractères suit, puis les données encodées, une séquence de terminaison, et du remplissage pour compléter la capacité restante.

Après les mots de code de données viennent les mots de code de correction d'erreurs, calculés lors de l'encodage par Reed-Solomon et ajoutés dans des blocs définis. L'étape suivante les utilise pour vérifier et réparer les données.

Étape 7 : correction d'erreurs reed-solomon

C'est l'étape qui permet aux codes QR de survivre aux dommages physiques. Elle nécessite un peu d'arithmétique sur les corps finis, mais le concept est accessible sans preuves complètes.

Le fondement du corps fini

Reed-Solomon opère sur GF(256), un corps de Galois à 256 éléments. Pensez-y comme un système numérique où chaque valeur est un octet (0-255), mais les règles arithmétiques diffèrent des mathématiques entières ordinaires. L'addition est simplement un XOR. Pas de retenue, totalement réversible. La multiplication est définie par un polynôme primitif ; dans les codes QR, le corps utilise x^8 + x^4 + x^3 + x^2 + 1. Chaque élément non nul de GF(256) peut être exprimé comme une puissance d'une racine primitive alpha, ce qui simplifie la multiplication en addition d'exposants modulo 255.

Pourquoi utiliser un corps fini ? En arithmétique ordinaire, la division polynomiale produit des fractions. Sur un corps fini, chaque élément non nul a un inverse multiplicatif, donc la division polynomiale produit toujours des quotients et restes exacts à l'intérieur du corps. C'est cette propriété qui fait fonctionner l'ensemble du schéma de correction d'erreurs.

Encodage : ajout des octets de contrôle

Lors de la création du code QR, les octets de données sont traités comme coefficients d'un polynôme D(x). On multiplie par x^r (décalage à gauche de r positions, où r est le nombre de mots de code de correction), puis on divise par un polynôme générateur G(x) en utilisant la division polynomiale longue sur GF(256). Le reste de cette division, r octets, est ajouté aux données comme mots de code de correction d'erreurs.

Le polynôme générateur pour r octets de contrôle est le produit de r facteurs linéaires : G(x) = (x - alpha^0)(x - alpha^1)...(x - alpha^(r-1)) où alpha est l'élément primitif de GF(256). Pour le niveau H du QR avec 28 mots de code de correction par bloc, G(x) a 28 racines.

Décodage : calcul des syndromes

Sur votre téléphone, le décodeur traite la séquence de mots de code reçue (données plus octets de correction) comme un polynôme R(x). Si tout va bien, R(x) se divise exactement par G(x) et le reste est zéro. Si des erreurs se sont glissées, R(x) = C(x) + E(x) où C(x) est le polynôme de mots de code correct et E(x) est un polynôme d'erreur avec des coefficients non nuls aux positions corrompues.

Le décodeur évalue R(x) à chacune des r racines du générateur : S_i = R(alpha^i) pour i de 0 à r-1. Ces r valeurs sont les syndromes. Tous nuls signifie un message propre. Tout syndrome non nul signifie que des erreurs sont présentes.

Localisation et correction des erreurs

À partir des valeurs de syndrome, le décodeur exécute l'algorithme de Berlekamp-Massey pour trouver le polynôme localisateur d'erreurs, dont les racines correspondent aux positions des octets corrompus. Trouver ces racines (en évaluant le polynôme pour les 255 éléments non nuls du corps, un processus appelé recherche de Chien) donne les positions des erreurs. Puis l'algorithme de Forney calcule les magnitudes d'erreur à chaque position : combien XOR-er chaque octet corrompu pour restaurer la valeur correcte.

Pour les effacements (positions où le décodeur sait qu'un octet n'est pas fiable, comme un module tombé en dessous d'un seuil de confiance lors de l'échantillonnage), la capacité de correction double. Un code avec r octets de contrôle corrige t erreurs où t = r/2. Si k positions d'effacement sont déjà connues, il gère jusqu'à r - k erreurs inconnues supplémentaires en plus. Le niveau H du QR avec 28 octets de contrôle par bloc corrige 14 erreurs inconnues ou 28 effacements connus par bloc, ou toute combinaison intermédiaire.

Ce que cela signifie concrètement

Un code QR version 1-Q a 13 mots de code de données et 13 mots de code de correction par bloc. Détruisez 6 de ces mots de code de données complètement (une rayure qui oblitère environ 46 % de la zone de données) et les 13 octets originaux sont toujours récupérables. C'est pourquoi les logos intégrés dans les codes QR fonctionnent : les modules centraux sont intentionnellement corrompus, et la correction d'erreurs absorbe la perte.

La limite est réelle cependant. Dépassez la capacité de correction et le décodeur soit produit silencieusement une sortie erronée (rare, car la vérification finale attrape la plupart des échecs) soit ne retourne rien. Les décodeurs de production gèrent les cas limites en vérifiant les deux copies des informations de format et en réessayant avec des seuils de binarisation légèrement variés. ZXing, par exemple, réessaie avec des paramètres de binarisation progressivement plus grossiers avant d'abandonner.

Étape 8 : réassemblage du message

Après Reed-Solomon, le décodeur dispose d'une séquence d'octets vérifiée. La dernière étape la décompresse selon les champs de mode et de comptage de caractères lus à l'étape 6.

Pour le mode octet (le plus courant pour les URL), chaque mot de code de 8 bits correspond directement à un octet Latin-1 ou UTF-8. Lire le comptage de caractères, prendre autant d'octets du payload, produire la chaîne finale. Le mode numérique fait correspondre des groupes de 10 bits à des nombres décimaux de trois chiffres ; le mode alphanumérique fait correspondre des groupes de 11 bits à des paires de caractères d'un alphabet de 45 caractères. Vous pouvez même concaténer plusieurs segments avec différents modes dans un seul code QR. Une URL avec uniquement des caractères alphanumériques suivie d'un payload binaire est parfaitement valide.

La chaîne de sortie est ce que votre téléphone vous montre : une URL, un numéro de téléphone, un message texte, un bloc d'identifiants Wi-Fi. À ce stade, le travail du scanner est terminé et le système d'exploitation prend le relais. Suivre l'URL, composer le numéro, proposer la connexion Wi-Fi.

Pourquoi la conception du pipeline compte pour la qualité du code

Connaître le pipeline change la façon dont vous devriez penser la conception des codes QR. Chaque étape a des conséquences pratiques.

• La binarisation signifie que le ratio de contraste n'est pas optionnel. Vous avez besoin d'au moins 40 % de différence de luminance entre le module et le fond pour un scan fiable sur tous les appareils. Les codes sombre-sur-sombre ou clair-sur-clair échouent à l'étape 1 quel que soit le niveau de correction d'erreurs.
• La détection des motifs de recherche signifie que les zones de silence sont structurelles, pas cosmétiques. Les codes qui débordent jusqu'au bord d'une zone imprimée sans marge échouent à l'étape 2.
• La sensibilité des informations de format signifie que les coins adjacents aux motifs de recherche doivent être protégés contre les dommages et les obstructions. Même la correction d'erreurs niveau H ne peut pas aider ici, car les informations de format sont décodées avant que le niveau de correction d'erreurs ne soit connu.
• La capacité Reed-Solomon signifie que la tolérance aux dommages est prévisible et quantifiable. Pour un code affiché en extérieur ou imprimé dans un environnement à forte usure, choisir le niveau Q ou H et dimensionner généreusement offre une vraie résilience, pas une vague promesse que « les codes QR gèrent les dommages ».

Le générateur de QR Nova vous permet de définir le niveau de correction d'erreurs avant de créer un code, car le bon choix dépend entièrement de l'endroit où le code vivra. Un code affiché sur écran dans un environnement contrôlé convient au niveau M. Un autocollant vinyle censé durer trois ans sur du matériel extérieur justifie le niveau H, même au prix d'un code plus dense et de version supérieure.

La décomposition réelle de la vitesse

Sur le matériel smartphone actuel (testé sur les flagships iOS et Android 2024-2025), voici comment le pipeline de décodage se décompose par image vidéo :

• Conversion en niveaux de gris et binarisation : 2-5 ms (optimisé SIMD dans les bibliothèques natives)
• Balayage des motifs de recherche : 3-8 ms (linéaire en hauteur d'image)
• Correction de perspective et échantillonnage de grille : 1-3 ms
• Décodage du format + Reed-Solomon : moins de 1 ms pour les codes version 1-10

Pipeline total : bien en dessous de 30 ms sur une seule image. À 30 fps le décodeur dispose de 33 ms par image ; à 60 fps, 16 ms. Dans les deux cas, le calcul n'est pas le goulot d'étranglement. Ces 0,5 à 2 secondes que vous ressentez en scannant sont presque entièrement optiques : la mise au point automatique qui se stabilise, le flou de mouvement d'une main instable, et le temps que le code passe partiellement hors du cadre avant que vous ne le centrez.

Cela explique aussi quelque chose qui agace les gens : scanner un code QR sur un écran est parfois plus difficile que scanner un code imprimé. Les écrans à haute luminosité introduisent des reflets que l'étape de binarisation traite comme un halo clair autour des modules sombres, réduisant la taille effective du module en dessous de ce que l'échantillonneur de grille attend. Réduire légèrement la luminosité de l'écran quand vous affichez un code QR n'est pas de la superstition. Cela supprime un véritable artéfact de binarisation.

Conclusion

Ce décodage en cent millisecondes représente huit étapes de calcul distinctes fonctionnant en séquence, chacune dépendant de la précédente. La binarisation convertit l'optique en données. Les motifs de recherche fournissent l'invariance d'orientation. La correction de perspective projette une capture réelle déformée sur une grille canonique. Les informations de format déverrouillent le masque. L'arithmétique Reed-Solomon sur GF(256) récupère les octets corrompus avec une certitude mathématique, jusqu'à une limite définie.

Une fois que vous comprenez le pipeline, les échecs de codes QR cessent d'être mystérieux. Un code qui scanne de manière incohérente n'est presque jamais « cassé ». Il bute contre une frontière d'étape spécifique : contraste trop faible pour la binarisation, zone de silence trop étroite pour la détection des motifs de recherche, zone de format endommagée avant que la correction d'erreurs ne puisse intervenir. Diagnostiquez l'étape et vous diagnostiquez la solution.

Si vous générez des codes pour un usage en production, faites correspondre le niveau de correction d'erreurs à l'endroit où le code vivra, gardez la zone de silence intacte, et vérifiez le contraste par programme, pas juste à l'œil. Les mathématiques s'occupent du reste.