Abb. 1: Schematischer Aufbau eines QR Code Version 7 (vgl. [ISO] S. 6)
Der schematische Aufbau eines QR Codes ist in Abbildung 1 dargestellt. Ein Symbol besteht demnach aus Funktionsmustern (Function Patterns) und einem Encoding Bereich (Encoding Region), letzterer enthält die eigentlichen Daten.
Die Quiet Zone umgibt das gesamte Symbol mit einer weißen Fläche und stellt sicher, dass der QR Code auch auf schwarzem Hintergrund erkannt wird. Ohne die Quiet Zone würden die Finder Patterns (Position Detection Patterns) mit dem Hintergrund verschmelzen.
Das Timing Pattern ist eine Folge von weißen und schwarzen Feldern, die einem Zebramuster ähnelt. Es hilft die einzelnen Zeilen und Spalten besser voneinander abzugrenzen und ist erst im Decodierungsprozess wichtig.
Alle anderen Elemente eines QR Code werden im Folgenden in eigenen Unterkapiteln genauer erklärt.
Abb. 1: Schematischer Aufbau eines QR Code Version 7 (vgl. [ISO] S. 6)
Ein Modul ist die kleinste Einheit in einem QR Code. Es besteht aus einer quadratischen Fläche einheitlicher Größe, welche genau 2 Ausprägungen hat: hell und dunkel. Dabei muss zwischen Modulen von Funktionsmustern (Finder Pattern, Alignement Pattern und Timing Pattern) und Datenmodulen unterschieden werden. Letztere repräsentieren Bits, wobei die dunklen Module der binären 1 und die hellen Module der binären 0 entsprechen.
Abb. 2: Helles und dunkles Modul
Üblicherweise werden die Module zu Codewörtern zusammengefasst, wobei ein Codewort aus genau 8 Modulen besteht.
Sobald die Codewörter in ein Symbol (Matrix) überführt werden, hat jedes Modul eine eindeutige Position in dieser Matrix, die durch seine X und Y Koordinate bestimmt ist. Dies ist später für das Masking wichtig.
Ein Codewort (CW) besteht wie schon erwähnt aus 8 Modulen, die in einer bestimmten Reihenfolge angeordnet sind. Die Anordnung hängt von der Richtung des Codewortes ab. Es werden zwei fundamentalen Richtungen unterschieden: Hoch (Upwards) und Runter (Downwards), diese sind in Abbildung 3 zu sehen. Das höchstwertigste Modul (Bit) ist das mit der Position 7 gekennzeichnete.
Abb. 3: Fundamentale Richtungen: Upwards und Downwards (vgl. [ISO] S. 47)
Abb. 4: Fließrichtungen bei Grenzen (vgl. [ISO] S. 47)
Es kann passieren, dass die jeweilige Richtung durch eine Grenze unterbrochen wird, dann muss die Richtung umgekehrt werden (siehe Abbildung 4). Alle über die Grenze hinausragenden Module werden in die nächsten zwei linken Spalten übertragen.
Wenn ein Funktionsmuster (z.B. einem Alignment Pattern) im Weg steht, gibt es zwei Regeln um es zu umgehen.
Abb. 5: Schematische Darstellung der Codewörter und ihrer Richtungen (vgl. [ISO] S. 48)
Das erste Codewort befindet sich in einem QR Code immer unten rechts und hat die Richtung Hoch, so wie D1 in Abbildung 5. Sobald ein Codewort gegen die obere Grenze stößt wird die Richtung umgekehrt und das nächste Codewort hat die Richtung Runter. Dies wird serpentinenartig so fortgeführt, bis alle Codewörter abgebildet sind.
In der Grafik wird das Codewort D15 in einer Spalte behindert und umfließt das Alignment Pattern. D13 dagegen trifft mit beiden Spalten gegen das Muster und wird deswegen in einen oberen und einen unteren Teil zerlegt.
Wenn einige Module keinem Codewort zugeordnet werden können, weil es zu wenige sind (< 8), werden sie Remainder Bits genannt und bleiben leer, das heißt hell.
Wie in der Abbildung zu sehen ist, gibt es die Konvention immer zunächst alle Daten Codewörter und dann erst die Fehlerkorrektur Codewörter abzulegen. Wie viele Daten- bzw. Fehlerkorrektur Codewörter es in einem Symbol gibt steht im Standard und ist von der Version und dem Fehlerkorrektur Niveau abhängig. (siehe [Informationen in QR Code Symbolen: Tabelle 2])
Die Finder Patterns ermöglichen die Erkennung von QR Codes. Sie sind quadratisch und haben immer das Verhältnis bzw. Muster 1:1:3:1:1 (dunkel:hell:dunkel:hell:dunkel), unabhängig von Rotationswinkel, wie in Grafik 6 zu sehen ist (der blaue Pfeil hat auch das Verhältnis 1:1:3:1:1). Zusätzlich sind sie von hellen Seperator Modulen umrandet, damit sie sich vom Rest des Symbols abheben (siehe Abbildung 1).
Abb. 6: Finder Pattern 1:1:3:1:1 Muster immer gleich, unabhängig von Orientierung
Durch ihr fest vorgegebenes Muster definieren sie indirekt auch die Modulgröße in dem QR Code Symbol, da ein Finder Pattern immer 7 Module breit ist.
Das Muster 1:1:3:1:1 tritt nur drei Mal in einem Symbol auf, das wird durch das Masking garantiert. Außerdem sind die Finder Patterns immer an den gleichen Stellen zu finden. Sie sind oben links, oben rechts und unten links im Symbol und geben somit die Ausrichtung des Codes vor. Sobald die drei Muster erkannt wurden, kann das Symbol in seine richtige Lage gedreht werden.
Mit den Alignement Patterns können Verzerrungen und Verformungen in größeren QR Codes korrigiert werden. Solche Probleme können dadurch entstehen, dass das Bild nicht senkrecht zum QR Code aufgenommen wurde oder der Untergrund, auf dem das Symbol gedruckt wurde, uneben ist.
Bei der Korrektur wird zunächst die mathematische Position des Alignment Patterns errechnet, also die theoretische Position relativ zu den drei Finder Patterns und zu anderen schon analysierten Alignment Patterns an der sich das Muster befinden sollte. Dann wird die echte Position gescannt und Beide werden verglichen. Stimmen sie überein gibt es keine Verzerrung, ansonsten wird die Abweichung berechnet.
Alle Alignment Patterns haben eine fest definierte Position im Symbol, abhängig von der QR Code Version (siehe Versionsinformation), die durch 2 Koordinaten repräsentiert wird. Die Koordinaten stehen für das Zentrum des Alignment Patterns und verhalten sich analog zu den Koordinaten der Module. Die Positionen können mit Hilfe der Tabelle 1 errechnet werden.
| Version | # | Positionen |
|---|---|---|
| 1 | 0 | - |
| 2 | 1 | 6, 18 |
| 3 | 1 | 6, 22 |
| ... | ||
| 7 | 6 | 6,22,38 |
| ... | ||
| 40 | 46 | 6, 30, 58, 86, 114, 142, 170 |
Tab. 1: Positionen der Alignment Patterns (Auszug aus [ISO] S. 82)
Dafür wird die Menge aller Permutationen von 2-Tupeln einer Version ermittelt. Für Version 7 sind diese: {(6,6), (6,22), (6,38), (22,6), (22,22), (22,38), (38,6), (38,22), (38,38)}, da die Menge der Positionen {6, 22, 38} ist.
Alle 2-Tupel, die Finder Patterns überlagern würden, werden aus der Menge entfernt. Im Beispiel muss folgende Menge abgezogen werden: {(6,6), (38,6), (6,38)}. Es verbleiben 6 Koordinaten (genau wie in Spalte # vorgesehen), die die Menge der Positionen der Alignement Patterns darstellen: {(6,22), (6,38), (22,6), (22,22), (22,38), (38,22)}.
Es fällt auf, dass Alignment Patterns auch auf Timing Patterns abgebildet werden können. Das funktioniert problemlos, da das Zentrum des Alignment Patterns immer so gewählt wird, dass es sich auf einem dunklen Modul des Timing Patterns befindet (siehe Abbildung 1).
Abb. 7: Es werden immer "quadratische" Flächen entzerrt (vgl. [ISO] S. 64)
Abb. 8: Reihenfolge in der die Alignment Patterns ausgelesen werden (vgl. [ISO] S. 62)
Eine Entzerrung findet immer für eine (quadratische) Fläche statt, die von 4 Alignment Patterns oder Finder Patterns, wie in Abbildung 7 zu sehen ist, aufgespannt wird. Durch die bereits berechneten Abweichungen der Alignment Pattens (von ihren mathematischen Positionen) der Eckpunkte, können alle Module innerhalb dieser Fläche leicht linear interpoliert werden.
Die Reihenfolge, in der die einzelnen Alignment Patterns ausgelesen werden, ist in Grafik 8 abgebildet.
Mit dieser Technik können kleinere Unregelmäßigkeiten der Form ausgeglichen werden. Weicht der Untergrund des QR Code Symbols zu stark von einer linearen Verformung ab, können die Daten nicht korrekt ausgelesen werden.