Comment un téléphone décode un QR code : Reed-Solomon expliqué

Tenez votre téléphone au-dessus d'un ticket dans un restaurant mal éclairé, de travers, avec une ombre sur la moitié du code : le lien s'affiche quand même en une seconde. Pourtant, l'appareil photo n'a jamais vu une belle grille noire et blanche. Il a vu un trapèze grisâtre, un dégradé de lumière et beaucoup de bruit.

Entre cette image et l'URL sur votre écran se succèdent plusieurs étapes distinctes, dont chacune peut échouer en silence. La plupart des applications appareil photo relancent la tentative de décodage complète sur chaque image à la cadence vidéo et jettent celles qui n'aboutissent pas, ce qui explique qu'un code limite semble réfléchir un instant avant d'accrocher. Il ne réfléchit pas. Il échoue en boucle et réessaie jusqu'à ce qu'une image soit par hasard assez bonne.

Cela veut dire aussi que tout ce qui dégrade l'image dégrade tout ce qui suit : flou de bougé, objectif taché, autofocus qui pompe. Un code flou n'échoue pas à la fin du processus. Il échoue avant que le processus commence.

Binarisation : décider quels pixels comptent comme sombres

Le décodeur doit trier chaque pixel dans l'un de deux paniers. L'approche naïve choisit une seule valeur de luminosité pour toute l'image et coupe là, ce qui marche en laboratoire et s'effondre sur une vraie table où une lampe à gauche rend le côté gauche du code plus clair que le papier blanc à droite.

Les décodeurs seuillent donc en général localement. L'image est découpée en petites régions et chaque région reçoit son propre seuil, dérivé de la luminosité alentour. Une ombre en travers du symbole cesse alors d'avoir de l'importance, car les modules dans l'ombre restent plus sombres que leurs voisins immédiats.

C'est aussi à cette étape que se produisent les échecs de couleur. La teinte est jetée ici. Ce qui survit, c'est la clarté relative, et c'est pourquoi deux couleurs qui paraissent nettement différentes à un humain peuvent tomber dans le même panier et produire un code qui ne se scanne jamais.

Trois coins donnent ses repères au décodeur

Vient ensuite la chasse aux motifs de repérage, les trois carrés emboîtés dans les coins. Ils sont repérables parce qu'une ligne tracée à travers l'un d'eux, dans n'importe quelle direction, traverse des plages sombres et claires dans un rapport 1:1:3:1:1. Le décodeur peut balayer des lignes de l'image binarisée à la recherche de cette signature sans savoir où est le code, quelle est sa taille, ni comment il est tourné.

Trois coins, pas quatre. Le quatrième coin vide est ce qui indique au décodeur où est le haut. Les symboles plus grands portent aussi de petits carrés d'alignement répartis dans la grille, qui servent de points de référence supplémentaires quand la surface est courbe ou la photo très biaisée. Le versant structurel de tout cela est traité dans comment fonctionnent les QR codes.

Retransformer une photographie en grille carrée

Presque personne ne scanne un code bien en face. Les motifs de repérage fournissent des points de référence connus, et à partir d'eux le décodeur calcule une transformation perspective : l'application qui ramènerait le quadrilatère photographié à un carré. Appliquez-la et le biais disparaît.

Le décodeur a ensuite besoin du nombre de modules. Les motifs de synchronisation, alternance de plages sombres et claires tendue entre les motifs de repérage, lui permettent de compter. La grille résolue, il échantillonne le centre de chaque cellule et tient enfin ce que tout le monde imaginait qu'il avait depuis le début : une matrice de uns et de zéros.

Les bits de format décrivent comment lire le reste

À côté des motifs de repérage se trouve un petit bloc d'information de format. Il porte deux choses sans lesquelles le décodeur ne peut pas avancer : le niveau de correction d'erreurs employé (L, M, Q ou H) et le motif de masque appliqué lors de la génération du code.

Perdre ce bloc rendrait le symbole entier illisible, il est donc écrit deux fois à des emplacements distincts et porte sa propre correction d'erreurs. C'est la zone la plus défendue du code.

Démasquer et remettre les mots de code dans l'ordre

Les encodeurs n'écrivent pas les données directement dans la grille. Un motif de masque est d'abord appliqué par XOR sur la zone de données, choisi pour casser les grands aplats et pour éviter de produire par accident quelque chose qui ressemble à un motif de repérage. Des mélanges équilibrés de sombre et de clair se seuillent plus fiablement : le masquage est donc une fonctionnalité de lisibilité, pas une obfuscation. Le décodeur retire le même motif par XOR.

Il parcourt ensuite les modules dans l'ordre en zigzag prescrit, groupe les bits en mots de code de huit bits, et les désentrelace. L'entrelacement compte plus qu'il n'y paraît. Dans les symboles plus grands, les données sont réparties en blocs et ces blocs sont tissés à travers la grille, de sorte qu'une auréole de café qui efface une zone physique prélève quelques mots de code dans chaque bloc au lieu d'anéantir complètement un bloc. Les dégâts sont dilués exprès.

Reed-Solomon, sans l'algèbre

Vient la réparation elle-même. À côté des mots de code portant vos données, l'encodeur en a stocké d'autres, calculés à partir d'eux, et l'image mentale utile est un système d'équations simultanées. Vous avez plus d'équations que d'inconnues, vous pouvez donc en perdre plusieurs et résoudre quand même chaque valeur, y compris celles qui ne sont jamais arrivées.

C'est proche de ce que fait le décodeur. Il vérifie si les mots de code reçus sont cohérents avec la redondance. S'ils le sont, c'est terminé. Sinon, il détermine où siège la corruption et quelles valeurs d'origine permettraient à tout de s'équilibrer à nouveau. Deux formes de dégâts existent et elles coûtent différemment : un mot de code dont le décodeur sait déjà qu'il manque est bon marché à réparer, alors qu'un mot de code présent mais faux coûte environ le double, parce qu'il faut aussi résoudre sa position.

Les quatre niveaux fixent la quantité de redondance disponible, approximativement sept, quinze, vingt-cinq et trente pour cent des mots de code récupérables en L, M, Q et H. Ce sont des plafonds pour le symbole entier, partagés avec toutes les autres sources de dégâts : défauts d'impression, éraflures, reflets, un pouce, un logo. Rien n'est mis de côté.

Au-delà de la limite de correction, il n'y a pas de dégradation progressive. Le décodeur reconstruit exactement les données ou signale un échec. Un code qui se scanne est correct bit pour bit, et c'est pourquoi un autocollant à moitié usé fonctionne parfaitement jusqu'au moment où il ne fonctionne plus du tout. La plupart des raisons pour lesquelles un code cesse de se scanner remontent aux étapes antérieures plutôt qu'à celle-ci, puisque la binarisation et la détection des repères n'ont aucune correction d'erreurs derrière elles.

Et en France ?

La correction Reed-Solomon n'est pas propre aux QR codes, et vous l'utilisez sans le savoir tous les jours. Elle protège les données des CD et des DVD, et elle fait partie de la chaîne de codage de la télévision numérique terrestre, la TNT : c'est elle qui permet à votre téléviseur d'afficher une image propre malgré un signal un peu dégradé.

Le principe est le même que pour un QR code : ajouter des données de contrôle calculées pour que le récepteur puisse reconstruire ce qui a été perdu en route. Sur un QR code, la perte vient d'une tache ou d'un reflet ; sur la TNT, d'un orage ou d'une antenne mal orientée.

Tout cela se passe sur l'appareil

Toutes ces étapes sont des calculs faits sur place, sur des pixels que le téléphone a déjà. Pas de recherche, pas de serveur, pas d'aller-retour. Un scanner décode même en mode avion, parce qu'il n'y a rien à télécharger : le texte est dans le motif, et le calcul qui le retrouve prend quelques millisecondes sur l'appareil que vous tenez en main.

Ce que le code contient et ce que le code déclenche ensuite sont deux questions distinctes, et la seconde est traitée dans ce qui se passe quand vous scannez.