náhled|upright|QR kód s odkazem na mobilní Wikipedii QR kód (anglicky: QR code) je prostředek pro automatizovaný sběr dat. Zkratka vychází z anglického „Quick Response“, tedy kódy rychlé reakce. QR kód dokáže zakódovat mnohem větší množství dat, než klasický čárový kód EAN. Specifikace QR kódů je od června 2000 standardem ISO 18004. Standard byl upraven v roce 2006. Kódy jsou určeny pro počítačové zpracování, využívají velké množství technik předcházejících chybám interpretace.
Algoritmům rozpoznávání kódu nevadí otáčení kódu ani inverze barev a přestává být čitelným až po odstranění či znečištění velké části kódu. Kódy jsou definovány v 40 velikostních verzích (od 1 do 40). Kód verze v je tvořen čtvercovou mřížkou bodů rozměru 17 + 4·v. Kód se skládá z několika informačních vrstev, které slouží různým účelům a používají různé algoritmy.
Historie QR kód vyvinul v roce 1994 se svým týmem Masahiro Hara, když pracoval pro společnost Denso Wave, dceřinou společnost japonské automobilové společnosti Toyota. Původním účelem QR kódů bylo sledovat vozidla během výrobního procesu. Harův tým čerpal inspiraci ze starověké deskové hry Go, která využívá mřížku s černými a bílými kameny. Tento koncept vedl k vývoji dvourozměrného kódu, který lze číst jak vertikálně, tak horizontálně. Výsledkem byl QR kód schopný pojmout až 7 089 číselných znaků nebo 4 296 alfanumerických znaků, což bylo výrazné zlepšení oproti klasickému čárovému kódu.
Vlastnosti Kapacita Množství dat QR kódu závisí na datovém typu a verzi (1-40). QR kód může obsahovat písmena, čísla nebo japonské znaky kandži. Nejvíce všestranný je QR kód verze 4, lze jej použít v široké řadě aplikací, včetně balení produktů, marketingových materiálů, vstupenek na akce a dalších. Verze 40 dokáže pojmout maximálně toto množství informací: Typ obsahu Počet znaků číslice 7 089 písmena a číslice 4 296 8bitová data 2 953 kandži 1 817
Popis Geometrická vrstva náhled|vpravo|Struktura QR kódu, zvýrazněné funkční elementy1. Informace o verzi2. Informace o formátu3. Data a samoopravné kódy4. Povinné vzory5. Tichá zóna náhled|vpravo|Kód na památkách v Praze 10 z roku 2012 náhled|vpravo|QR kód použitý na čínské jízdence na vlak Tato vrstva slouží k přesné lokalizaci geometrických pozic, kde mají být čteny informační bity. Základem této vrstvy je jednobarevná „tichá zóna“ šířky alespoň 4 body ohraničující celý kód. O barvě tiché vrstvy se hovoří jako o bílé, a barvě k ní kontrastní jako o barvě černé, což koresponduje i s jejich grafickou reprezentací. Při dekódování je určena průměrná tmavost celého kódu a z hlediska rozpoznávání je každý bod buď světlejší, nebo tmavší. Rozměry bodů (základních čtverečků) jsou při dekódování primárně určovány podle čtverců velikosti 7×7 tzv. Finders které jsou ve třech rozích kódu. Uvnitř černého čtverce 7×7 je bílý obvod čtverce 5×5, vnitřek 3×3 je černý. Tyto čtverce jsou od zbytku kódu odděleny bílým proužkem, společně s tímto proužkem tak vytvářejí čtverce 8×8. Nejvíc vnější černý pixel prostředního Finder čtverce slouží jako souřadnice [0, 0]. Všechny verze kódu mají vyhrazen 6. řádek a sloupec na tzv. Timing vzor, v němž se mezi Finders střídají černé a bílé body (černá na lichých pozicích). Ve verzi 1 je geometrická vrstva tvořena pouze pomocí Finders a Timing. V ostatních verzích je použit jeden či více tzv. Alignments.
V modelu 1 QR kódů byly jako Alignments použity malé obdélníčky na krajích kódu. Model zřejmě nebyl dostatečně odolný vůči deformacím a byl nahrazen modelem 2, který se pak celosvětově rozšířil. Zde je popsán model 2 QR kódů. Alignment je obdobně jako Finder tvořen třemi soustřednými čtverci, nyní ale je vnitřní tvořen jediným černým bodem, okolo něj je obvod bílého čtverce 3×3 a okolo něj obvod černého čtverce 5×5. Pokud je horní celá část z (1 + v) / 7 označena A, tak verze v obsahuje A×A Alignments v pravidelných rozestupech konče Alignment se středem na souřadnici [(10 + 4·v), (10 + 4·v)] (tedy [-7, -7] od rohu bez Finder). Vzdálenosti středů sousedních Alignments je dán výrazem (((10 + 4·v) – 6) / A – 0,6) zaokrouhleným nahoru na sudé číslo. Kromě těchto Alignments jsou ve stejných sloupcích či řádkách přidány Alignments i na řádek 6 a sloupec 6, pokud tomu nebrání Finders. Na každý Timing pattern tak přibylo A – 1 Alignments. Od verze 7 výše je navíc číslo verze zabezpečené do délky 18 bitů zapsáno do 3×6 obdélníků dotýkajících se vnějších Finders směrem k souřadnici [0, 0]. Pořadí bitů je od nejmenší souřadnice po největší, po trojicích. Dosud je vzor stále symetrický vůči úhlopříčce procházející bodem [0, 0]. (Oněch 18 bitů vznikne jako BCH kód vzniklý doplněním binárního čísla verze v nejvyšších 6 bitech 12 bity tak, aby jednotlivé bity tvořily koeficienty polynomu nad bity, dávající zbytek nula vůči polynomu s koeficienty nad bity 1111100100101).
Při dekódování slouží jednotlivé Alignments na rozdělení kódu na jednotlivé podoblasti. V podoblastech jsou korigovány geometrické deformace nezávisle. I v případě prohnutého kódu či kódu sejmutého šikmo geometrická vrstva dostatečně přesně lokalizuje středy jednotlivých bodů. + Geometrická vrstva v číslech v Strana Plocha Finders Timing Verze A Alignments Zbývá Vzdálenosti alignments 1 21 441 192 10 0 0 0 239 - 2 25 625 192 18 0 1 25 390 - 3 29 841 192 26 0 1 25 598 - 4 33 1089 192 34 0 1 25 838 - 5 37 1369 192 42 0 1 25 1110 - 6 41 1681 192 50 0 1 25 1414 - 7 45 2025 192 58 36 2 140 1599 16 8 49 2401 192 66 36 2 140 1967 18 9 53 2809 192 74 36 2 140 2367 20 10 57 3249 192 82 36 2 140 2799 22 11 61 3721 192 90 36 2 140 3263 24 12 65 4225 192 98 36 2 140 3759 26 13 69 4761 192 106 36 2 140 4287 28 14 73 5329 192 114 36 3 305 4682 20 15 77 5929 192 122 36 3 305 5274 22 16 81 6561 192 130 36 3 305 5898 24 17 85 7225 192 138 36 3 305 6554 24 18 89 7921 192 146 36 3 305 7242 26 19 93 8649 192 154 36 3 305 7962 28 20 97 9409 192 162 36 3 305 8714 28 21 101 10201 192 170 36 4 520 9283 22 22 105 11025 192 178 36 4 520 10099 24 23 109 11881 192 186 36 4 520 10947 24 24 113 12769 192 194 36 4 520 11827 26 25 117 13689 192 202 36 4 520 12739 26 26 121 14641 192 210 36 4 520 13683 28 27 125 15625 192 218 36 4 520 14659 28 28 129 16641 192 226 36 5 785 15402 24 29 133 17689 192 234 36 5 785 16442 24 30 137 18769 192 242 36 5 785 17514 26 31 141 19881 192 250 36 5 785 18618 26 32 145 21025 192 258 36 5 785 19754 26 33 149 22201 192 266 36 5 785 20922 28 34 153 23409 192 274 36 5 785 22122 28 35 157 24649 192 282 36 6 1100 23039 24 36 161 25921 192 290 36 6 1100 24303 26 37 165 27225 192 298 36 6 1100 25599 26 38 169 28561 192 306 36 6 1100 26927 26 39 173 29929 192 314 36 6 1100 28287 28 40 177 31329 192 322 36 6 1100 29679 28
Informační vrstva náhled|QR kód jenž v obou převráceních dává smysluplný výsledek (08331025600800024 či 42256900000801139), jedná se o kód nalezený po třech dnech hledání. Informace o masce a úrovni zabezpečení nutně musí obsahovat chyby v obou převráceních, v tomto nalezeném případě je v každém převrácení 8 datových chyb, ale zvolená nejvyšší úroveň zotavování se z chyb je dokáže opravit. V informační vrstvě každý černý bod kóduje binární jedničku a bílý bod binární nulu. V řádku 8 a sloupci 8 je vedle Finders uložena informace sloužící k dekódování informací hlavního datového toku. Hlavní datový tok vyplňuje dosud nevyužité body v následujícím pořadí: Začíná v rohu s maximální souřadnicí. Vždy postoupí o jedno vlevo, pak se vrátí a postoupí o 1 vertikálně. Začíná postupovat nahoru a po vyplnění krajních dvou sloupců sestupuje v následujících dvou sloupcích dolů. Takto střídá dvojice sloupců, dokud nenarazí na sloupec 6. Ten přeskočí a pokračuje v dvousloupci 4-5. Průchod končí v levém dolním rohu. Vzhledem k tomu, že v závislosti na kódovaných datech by mohly vznikat vzory matoucí geometrickou vrstvu, je hlavní datový tok maskován. Je vytvořeno 8 jednoduchých maskovacích vzorů a na příslušných souřadnicích je ukládaná negovaná hodnota. Negují se body dávající 0 v následujících výrazech: + Maskování Kód Popis Vzorec Perioda000Šachovnice(x+y) mod 22×2001Vodorovné pruhyy mod 21×2010Svislé pruhy ob 2x mod 33×1011Diagonální pruhy ob 2(x+y) mod 33×3100Šachovnice obdélníků 3×2(⌊y/2⌋+⌊x/3⌋) mod 26×4101První velká dlaždice(x*y) mod 3 + (x*y) mod 26×6110Druhá velká dlaždice((x*y) mod 3 + (x*y)) mod 26×6111Třetí velká dlaždice((x*y) mod 3 + (x+y)) mod 26×6
Datový tok obsahuje bytovou zprávu a zabezpečovací byty. U větších verzí je datová zpráva rozdělena do bloků, kde každý blok má samostatné zotavování se z chyb. Pro každou verzi jsou definovány 4 úrovně zabezpečení. Každá úroveň definuje, na jaké bloky se zpráva rozpadá a kolik zabezpečovacích bytů je pro bloky používáno (počet zabezpečovacích bytů je pro všechny bloky stejný, ale délky bloků se mohou o 1 byte lišit). Vzorec pro určení rozkladu na bloky se mi nepodařilo odvodit, pravděpodobně nebyl generován, ale byl určen ad hoc. Nezbývá než se řídit tabulkou dle specifikace (viz níže). Hlavní datový tok je tvořen prvním bytem prvního bloku, pak prvním bytem druhého bloku, prvním třetího …, pak druhým bytem prvního atd. Pokud nejsou všechny bloky stejně dlouhé, jsou nejprve bloky kratší (délky D) a nakonec bloky delší (D+1). V takovém případě po skončení D-tého bytu posledního bloku následuje poslední blok prvního bloku délky D+1. Až po ukončení bytové zprávy následují zabezpečovací byty počínaje prvním bytem prvního bloku, pak prvním druhého … až posledním bytem posledního bloku. Zbývá-li pro danou verzi počet bitů pro datový tok nedělitelný 8, je konec datového toku doplněn nulami (to že nejsou ukládány celé bloky, ale jsou bloky prokládány, zvyšuje odolnost proti lokálnímu zašpinění či chybějícímu kusu kódu, protože malé chyby ve více blocích problém nejsou na rozdíl od velké chyby v jednom bloku).
Informace uložená vedle Finders v osmém řádku a sloupci v 15 bitech pomocí BCH kódu dvěma bity určuje úroveň zabezpečení a třemi bity masku. Těchto 5 bitů v nejvyšších řádech je doplněno 10 bity tak, aby jednotlivé bity tvořily koeficienty polynomu nad bity, dávající zbytek nula vůči polynomu s koeficienty nad bity 10100110111 (minimální polynom s kořeny α1…, α6 nad GF(24)). Výsledné bity jsou navíc maskovány s 101010000010010. Bity jsou uloženy zleva doprava od nejvýznamnějšího, ale shora dolů od nejméně významného. Bit na souřadnici 8×8 je součástí svislého zápisu. Vedle dolního levého Finder je nahoře vždy bezvýznamný černý bod.
Zabezpečení bloku pomocí K zabezpečovacích bytů je zajištěno Reedovými–Solomonovými kódy nad tělesem GF(28), kde prvky tělesa jsou ztotožněny s byty tak, že bitový zápis je vnímán jako koeficienty polynomu nad bity a tyto polynomy jsou brány modulo polynom s koeficienty bitově 100011101. Primitivním prvkem tohoto tělesa je α=2. Reedovy–Solomonovy kódy vzniknou doplněním polynomu, kde nejvyšší řády budou tvořeny zprávou, pomocí takových koeficientů, aby byl výsledný polynom dělitelný (x-α0)*(x-α1)*…*(x-α(K-1)).
Dle normy má být QR kód vytvořen tak, že vytvoříme 8 variant dle jednotlivých možností maskování a vybereme masku s nejmenší "nevhodností". Tato nevhodnost je definována čtyřmi ukazateli. První trestá jednobarevné úseky řádků či sloupců délky aspoň 5. Za úsek délky 5+k dává 3+k trestných bodů. Druhá trestá třemi body každý jednobarevný čtverec velikosti 2×2 (tedy například za každý Finder dává 4 krát 3 trestných bodů). Třetí trestá vzory WWWWBWBBBWB a BWBBBWBWWWW kde W značí bílou a B černou barvu. Vzor WWWWBWBBBWBWWWW je trestán jen jednou. Tyto vzory dostávají po 40 trestných bodech. Poslední ukazatel hodnotí odchylku od 50% naplnění černou barvou. Překročení o každých 5% je trestáno 10 body (poslední ukazatel zajišťuje, aby průměrná barva byla dostatečně vzdálena jak od bílé, tak černé barvy).
Při dekódování ale kontrola existence efektivnějšího zamaskování prováděna nebývá a nezvolení optimální masky nebývá důvodem pro prohlášení kódu za nevalidní.