QR kód

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
QR kód verze 8 obsahující html odkazy

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ý EAN čárový kód. Specifikace QR kódů je od června 2000 standardem ISO 18004. Standard byl upraven v roce 2006.[1] 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. Kód přestává být čitelným až po odstranění či znečištění velké části kódu. Algoritmům rozpoznávání kódu nevadí otáčení kódu ani inverze barev, kód nevyžaduje velký kontrast barev. 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.

Vlastnosti[editovat | editovat zdroj]

Kapacita[editovat | editovat zdroj]

QR kód může obsahovat písmena, čísla nebo japonské znaky kandži a je schopný pojmout různé množství informací podle obsahu:

Typ obsahu Počet znaků
číslice 7 089
písmena a číslice 4 296
8bitová data 2 953
kandži 1 817

Popis[editovat | editovat zdroj]

Geometrická vrstva[editovat | editovat zdroj]

Struktura QR kódu, zvýrazněné funkční elementy
1. Informace o verzi
2. Informace o formátu
3. Data a samoopravné kódy
4. Povinné vzory
5. Tichá zóna
Kód na památkách v Praze 10 z roku 2012
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í vyhraněn 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 prostřední 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[editovat | editovat zdroj]

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 Perioda
000 Šachovnice (x+y) mod 2 2×2
001 Vodorovné pruhy y mod 2 1×2
010 Svislé pruhy ob 2 x mod 3 3×1
011 Diagonální pruhy ob 2 (x+y) mod 3 3×3
100 Šachovnice obdélníků 3×2 (⌊y/2⌋+⌊x/3⌋) mod 2 6×4
101 První velká dlaždice (x*y) mod 3 + (x*y) mod 2 6×6
110 Druhá velká dlaždice ((x*y) mod 3 + (x*y)) mod 2 6×6
111 Třetí velká dlaždice ((x*y) mod 3 + (x+y)) mod 2 6×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 Reed-Solomonovy 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. Reed-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ý (x0)*(x1)*…*(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í.

Informační vrstva v číslech
v Zbytek bodů Formát a bod Info Bitů Do bytu Info Bytů L (kód 01) M (kód 00) Q (kód 11) H (kód 10)
Bloků Max. blok EC bytů Celkem dat Bloků Max. blok EC bytů Celkem dat Bloků Max. blok EC bytů Celkem dat Bloků Max. blok EC bytů Celkem dat
1 239 31 208 0 26 1 26 7 19 1 26 10 16 1 26 13 13 1 26 17 9
2 390 31 359 7 44 1 44 10 34 1 44 16 28 1 44 22 22 1 44 28 16
3 598 31 567 7 70 1 70 15 55 1 70 26 44 2 35 18 34 2 35 22 26
4 838 31 807 7 100 1 100 20 80 2 50 18 64 2 50 26 48 4 25 16 36
5 1110 31 1079 7 134 1 134 26 108 2 67 24 86 4 34 18 62 4 34 22 46
6 1414 31 1383 7 172 2 86 18 136 4 43 16 108 4 43 24 76 4 43 28 60
7 1599 31 1568 0 196 2 98 20 156 4 49 18 124 6 33 18 88 5 40 26 66
8 1967 31 1936 0 242 2 121 24 194 4 61 22 154 6 41 22 110 6 41 26 86
9 2367 31 2336 0 292 2 146 30 232 5 59 22 182 8 37 20 132 8 37 24 100
10 2799 31 2768 0 346 4 87 18 274 5 70 26 216 8 44 24 154 8 44 28 122
11 3263 31 3232 0 404 4 101 20 324 5 81 30 254 8 51 28 180 11 37 24 140
12 3759 31 3728 0 466 4 117 24 370 8 59 22 290 10 47 26 206 11 43 28 158
13 4287 31 4256 0 532 4 133 26 428 9 60 22 334 12 45 24 244 16 34 22 180
14 4682 31 4651 3 581 4 146 30 461 9 65 24 365 16 37 20 261 16 37 24 197
15 5274 31 5243 3 655 6 110 22 523 10 66 24 415 12 55 30 295 18 37 24 223
16 5898 31 5867 3 733 6 123 24 589 10 74 28 453 17 44 24 325 16 46 30 253
17 6554 31 6523 3 815 6 136 28 647 11 75 28 507 16 51 28 367 19 43 28 283
18 7242 31 7211 3 901 6 151 30 721 13 70 26 563 18 51 28 397 21 43 28 313
19 7962 31 7931 3 991 7 142 28 795 14 71 26 627 21 48 26 445 25 40 26 341
20 8714 31 8683 3 1085 8 136 28 861 16 68 26 669 20 55 30 485 25 44 28 385
21 9283 31 9252 4 1156 8 145 28 932 17 68 26 714 23 51 28 512 25 47 30 406
22 10099 31 10068 4 1258 9 140 28 1006 17 74 28 782 23 55 30 568 34 37 24 442
23 10947 31 10916 4 1364 9 152 30 1094 18 76 28 860 25 55 30 614 30 46 30 464
24 11827 31 11796 4 1474 10 148 30 1174 20 74 28 914 27 55 30 664 32 47 30 514
25 12739 31 12708 4 1588 12 133 26 1276 21 76 28 1000 29 55 30 718 35 46 30 538
26 13683 31 13652 4 1706 12 143 28 1370 23 75 28 1062 34 51 28 754 37 47 30 596
27 14659 31 14628 4 1828 12 153 30 1468 25 74 28 1128 34 54 30 808 40 46 30 628
28 15402 31 15371 3 1921 13 148 30 1531 26 74 28 1193 35 55 30 871 42 46 30 661
29 16442 31 16411 3 2051 14 147 30 1631 28 74 28 1267 38 54 30 911 45 46 30 701
30 17514 31 17483 3 2185 15 146 30 1735 29 76 28 1373 40 55 30 985 48 46 30 745
31 18618 31 18587 3 2323 16 146 30 1843 31 75 28 1455 43 55 30 1033 51 46 30 793
32 19754 31 19723 3 2465 17 145 30 1955 33 75 28 1541 45 55 30 1115 54 46 30 845
33 20922 31 20891 3 2611 18 146 30 2071 35 75 28 1631 48 55 30 1171 57 46 30 901
34 22122 31 22091 3 2761 19 146 30 2191 37 75 28 1725 51 55 30 1231 60 47 30 961
35 23039 31 23008 0 2876 19 152 30 2306 38 76 28 1812 53 55 30 1286 63 46 30 986
36 24303 31 24272 0 3034 20 152 30 2434 40 76 28 1914 56 55 30 1354 66 46 30 1054
37 25599 31 25568 0 3196 21 153 30 2566 43 75 28 1992 59 55 30 1426 70 46 30 1096
38 26927 31 26896 0 3362 22 153 30 2702 45 75 28 2102 62 55 30 1502 74 46 30 1142
39 28287 31 28256 0 3532 24 148 30 2812 47 76 28 2216 65 55 30 1582 77 46 30 1222
40 29679 31 29648 0 3706 25 149 30 2956 49 76 28 2334 68 55 30 1666 81 46 30 1276

Překlad mezi zprávou a bitovým obsahem[editovat | editovat zdroj]

Bitová zpráva, která je předávána v informační vrstvě vzniká „komprimací“ originální zprávy. Zpráva (může být tvořena několika) samostatně kódovanými úseky. Každý úsek začíná čtyřbitovou identifikací režimu kódování. Nejkompaktnější je režim numerický (identifikace 1) umožňující zaznamenat dekadické číslice, s tím, že tři číslice (1000) kóduje pomocí 10 bitů (konec zprávy je kódován minimálním nutným počtem bitů). Následuje co do kompaktnosti režim alfanumerický (identifikace 2), umožňující kódovat i velká písmena, znaky $%*+-./: a mezeru. Těchto 45 znaků je po dvojicích (2045) kódováno pomocí 11 bitů (konec zprávy je kódován minimálním nutným počtem bitů). Bytový režim (identifikace 4) ukládá osmice bitů, existují i další varianty. Za každou identifikací kódování je oznámena délka úseku zprávy kódovaná v daném režimu. Počet bitů nutných k určení této délky záleží jak na režimu, tak na verzi QR kódu (aby byla zajištěna dostatečná kapacita). Úseky zprávy na sebe bitově navazují. Pokud zpráva končí před vyčerpáním kapacity kódu, a zbývá více než byte, je doplněna čtveřicí nul (identifikace režimu konce zprávy), pak je doplněna nulami na celý byte a pak střídavě pomocí 0xEC11 dokud se byty do prostoru pro zprávu vejdou. Typicky je snahou zvolit co nejmenší verzi, do níž se zpráva vejde. Optimální délku bitové zprávy a způsob rozdělení na jednotlivé úseky je možno získat technikou dynamického programování (stačí si při postupném přidávání znaků pamatovat optimální délku bitového obsahu pro každý možný způsob kódování posledního úseku).

Počet bitů kódujících délku úseku zprávy
v Numericky Alfanumericky Bytově Kanji
1-9 10 9 8 8
10-26 12 11 16 10
27-40 14 13 16 12

Další vrstvy[editovat | editovat zdroj]

Norma definuje i způsob jak sdružovat několik QR kódů dohromady. Každý kód ví, o kolikátou z kolika částí se jedná. Začínají být používány standardy interpretace obsahu zpráv… například vizitky či příkazy k úhradě do banky.

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  1. ISO/IEC 18004:2006 [online]. [cit. 2008-05-06]. Dostupné online. (anglicky) 

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]