VYSOKÉ U ENÍ TECHNICKÉ V BRN BRNO UNIVERSITY OF TECHNOLOGY

VYSOKÉ UýENÍ TECHNICKÉ V BRNċ BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA ELEKTROTECHNIKY A KOMUNIKAýNÍCH TECHNOLOGIÍ ÚSTAV AUTOMATIZACE A MċěICÍ TECHNIKY

FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF CONTROL AND INSTRUMENTATION

SYSTÉM PRO ROZPOZNÁVÁNÍ 2D ýÁROVÝCH KÓDģ 2D BARCODE RECOGNITION SYSTEM

BAKALÁěSKÁ PRÁCE BACHELOR‘S THESIS

AUTOR PRÁCE

MARTIN SEDLÁě

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2010

Ing. PETR PETYOVSKÝ

ITIIIIJ ITIIIIJ [w'W

VYSOKE UCENi

Iml§ 'if \§

TECHNICKE v BRNE Fakulta elektrotechniky

a komunikacnich technologii Ostav automatizace a merici techniky

Bakalarska prace bakalarsky studijnf obor Automatizacni Student: Rocnik:

Martin Sedlar 3

a merici technika

ID: 106764 Akademicky rok: 2009/10

POKYNY PRO VYPRAcovANi: 1. Prostudujte problematiku carovych k6du. 2. Seznamte se s postupy a metodami detekce carovych k6du pouzfvanymi v prumyslu. 3. Na zaklade nastudovanych znalostf zvolte vhodny system usporadani 20 carovych k6du, pripadne navrhnete vlastni. 4. Navrhnete vhodne usporadani opticke sceny pro snimanf 20 carovych k6du pomoci CCO kamery a vytvorte mnozinu testovacfch snimku. 5. Navrhnete a realizujte algoritmy pro optickou detekci a rozpoznanf 20 carovych k6du. 6. Zhodnot'te dosazene vysledky, urcete presnost klasifikace 20 carovych k6du na zaklade vyhodnocenf testovacich snimku. DOPORUCENA

L1TERATURA:

[1] Sonka, M.; Hlavac, V.: Pocftacove videni, Grada, Praha 1992, ISBN 80-85424-67-3 [2] Zara, J.; Benes, B.; Felkel, P.: Modernf pocftacova grafika, Computer press, 1998, ISBN 80-7226-049-9 [3] Hlavac, V.; Sedlacek, M.: Zpracovanf signalu a obrazu, skriptum CVUT 2001

Vedouci prace:

Ing. Petr Petyovsky

Konzultanti bakalafske prace:

UPOZORNENi: Autor bakalafske prace nesmi pi'i vytvai'en zasahovat nedovolenym zpusobem do ciz' poruseni ustanoveni § 11 a nasledujicich dusledku vyplyvajicich z ustanoveni casti dr

ÚSTAV AUTOMATIZACE A MċěICÍ TECHNIKY Fakulta elektrotechniky a komunikaþních technologií Vysoké uþení technické v BrnČ

ANOTACE Tato bakaláĜská práce se zabývá þtením 2D þárových kódĤ. Na zaþátku je uveden struþný pĜehled nejpoužívanČjších þárových kódĤ. Dále se hlavnČ práce zabývá QR kódy. VysvČtlena je jejich struktura, složení a pravidla pro jejich tvorbu a þtení. NastínČna je problematika uspoĜádání scény pĜi jejich snímání. Popsán je algoritmus pro þtení QR kódĤ, který je psaný v jazyce C++ a využívá knihovnu OpenCV.

ANOTATION This bachelor’s thesis deals with 2D barcode reading. At the beginning a brief overview of the most used barcodes is shown. The work mainly deals with QR codes. Their structure, composition and rules for encoding and decoding are explained. Problems with arrangement of photographic scene are solved too. C++ algorithm for QR code reading is described with usage of the OpenCV library.

KLÍýOVÁ SLOVA QR kód, 2D kód, þárový kód, zpracování obrazu, knihovna OpenCV, Cannyho hranový detektor, Houghova transformace, uspoĜádání scény

KEYWORDS QR code, 2D code, barcode, image processing, OpenCV library, Canny edge detector, Hough transform, scene arrangement

3


Bibliografická citace SEDLÁě, M. Systém pro rozpoznávání 2D þárových kódĤ. Brno: Vysoké uþení technické v BrnČ, Fakulta elektrotechniky a komunikaþních technologií, 2010. 65 s. Vedoucí bakaláĜské práce Ing. Petr Petyovský.

4


3URKOiåHQt „Prohlašuji, že svou bakaláĜskou práci na téma SYSTÉM PRO ROZPOZNÁVÁNÍ 2D ýÁROVÝCH KÓDģ jsem vypracoval samostatnČ pod vedením vedoucího bakaláĜské práce a s použitím odborné literatury a dalších informaþních zdrojĤ, které jsou všechny citovány v práci a uvedeny v seznamu literatury na konci práce. Jako autor uvedené bakaláĜské práce dále prohlašuji, že v souvislosti s vytvoĜením této bakaláĜské práce jsem neporušil autorská práva tĜetích osob, zejména jsem nezasáhl nedovoleným zpĤsobem do cizích autorských práv osobnostních a jsem si plnČ vČdom následkĤ porušení ustanovení § 11 a následujících autorského zákona þ. 121/2000 Sb., vþetnČ možných trestnČprávních dĤsledkĤ vyplývajících z ustanovení § 152 trestního zákona þ. 140/1961 Sb.“

V BrnČ dne: 27. kvČtna 2010

………………………… podpis autora

3RGďNRYiQt

DČkuji vedoucímu bakaláĜské práce Ing. Petrovi Petyovskému za úþinnou metodickou, pedagogickou a odbornou pomoc a další cenné rady pĜi zpracování mé bakaláĜské práce.

V BrnČ dne: 27. kvČtna 2010

………………………… podpis autora

5


OBSAH 1. ÚVOD ...............................................................................................................10 2. TEORETICKÝ ÚVOD ...................................................................................11 2.1 ýÁROVÉ KÓDY............................................................................................11 2.1.1 Jak vznikl þárový kód ...................................................................................11 2.1.2 Co je to þárový kód a kde se používá ...........................................................11 2.1.3 1D þárové kódy.............................................................................................12 2.1.4 2D þárové kódy.............................................................................................14 2.2 QR kód ............................................................................................................17 2.2.1 Úvod .............................................................................................................17 2.2.2 Struktura QR kódu........................................................................................17 2.2.3 Velikosti QR kódu ........................................................................................20 2.2.4 Kódování vlastních dat .................................................................................23 2.2.5 RozdČlení dat QR kódu na codewords .........................................................25 2.2.6 Korekce chyb ................................................................................................26 2.2.7 Používané masky ..........................................................................................27 2.2.8 Kódování informace o použité korekci chyb a masce ..................................30 2.2.9 PĜíklad zakódování dat do QR kódu.............................................................31 3. POěÍZENÍ DATABÁZE SNÍMKģ...............................................................37 4. REALIZOVANÉ ěEŠENÍ .............................................................................42 4.1 Knihovna OpenCV..........................................................................................44 4.2 Popis jednotlivých blokĤ navrženého Ĝešení...................................................45 4.2.1 Vstupní obrázek ............................................................................................45 4.2.2 Prahování vstupního obrázku .......................................................................46 4.2.3 Detekce hran v obraze ..................................................................................48 4.2.4 Houghova transformace pro detekci þar .......................................................49 4.2.5 Algoritmus pro vytvoĜení souĜadnicové sítČ.................................................50 4.2.6 Algoritmus pro zpracování matice QR kódu ................................................55 5. ZHODNOCENÍ VÝSLEDKģ REALIZOVANÉHO ěEŠENÍ ...................60 6. ZÁVċR .............................................................................................................61

6


7. SEZNAM POUŽITÝCH ZDROJģ ...............................................................63 8. SEZNAM POUŽITÝCH ZKRATEK A SYMBOLģ...................................64 9. SEZNAM PěÍLOH .........................................................................................65

7


SEZNAM POUŽITÝCH OBRÁZKģ Obr. 1 - Ukázka kódu EAN-13 [13]........................................................................... 13 Obr. 2 - Ukázka kódu UCC/EAN 128 [8].................................................................. 13 Obr. 3 - Ukázka kódu Code 39 [10]........................................................................... 13 Obr. 4 - Ukázka kódu 2 z 5 [14] ................................................................................ 14 Obr. 5 - Ukázka kódu PDF 417 [9] ............................................................................ 15 Obr. 6 - Ukázka kódu DATAMATRIX [13] ............................................................. 15 Obr. 7 - Ukázka QR kódu .......................................................................................... 16 Obr. 8 - Struktura Finder pattern................................................................................ 18 Obr. 9 - Struktura Alignment pattern ......................................................................... 19 Obr. 10 - Struktura QR kódu verze 1 ......................................................................... 19 Obr. 11 - Struktura QR kódu verze 2 ......................................................................... 20 Obr. 12 - QR kód verze 14 ......................................................................................... 21 Obr. 13 - Postup pĜevodu numerických znakĤ........................................................... 23 Obr. 14 - Postup pĜevodu alfanumerických znakĤ..................................................... 24 Obr. 15 - RozmístČní codewords................................................................................ 25 Obr. 16 - Rozložení jednotlivých bitĤ v CW ............................................................. 26 Obr. 17 - Masky ......................................................................................................... 29 Obr. 18 - Kódování informace o použité masce a korekci chyb................................ 30 Obr. 19 - PĜíklad kódu - Rozložení CW..................................................................... 33 Obr. 20 - PĜíklad kódu - Data, vyplĖující CW a korekce chyb.................................. 34 Obr. 21 - PĜíklad kódu - Maskování kódu.................................................................. 35 Obr. 22 - PĜíklad kódu - Informace o korekci chyb a masce ..................................... 36 Obr. 23 - PĜíklad kódu - Výsledný QR kód v reálné scénČ........................................ 36 Obr. 24 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED shora ......................... 37 Obr. 25 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED šikmo........................ 38 Obr. 26 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED bokem....................... 38 Obr. 27 – NejvhodnČjší scéna pro poĜízení fotografie ............................................... 39 Obr. 28 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové shora ................ 39 Obr. 29 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové šikmo ............... 39

8


Obr. 30 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové bokem.............. 40 Obr. 31 - Snímek - digi. fotoaparát - malý lesklý kód - svČtlo žárovkové................. 40 Obr. 32 - Snímek - digi. fotoaparát - rozdíl mezi lesklým a matným ........................ 40 Obr. 33 - Snímek - mobilní tel. - malý matný kód - svČtlo žárovkové ...................... 41 Obr. 34 - Snímek - mobilní tel. - velký matný kód - svČtlo LED .............................. 41 Obr. 35 – Návrh Ĝešení – Algoritmus pro dekódování QR kódu ............................... 43 Obr. 36 – Vstupní obrázek QR kódu.......................................................................... 45 Obr. 37 – Typy pĜevodních funkcí pĜi prahování [4]................................................. 46 Obr. 38 – Obrázek po prahování ................................................................................ 47 Obr. 39 – Obrázek po detekci hran ............................................................................ 48 Obr. 40 – Obrázek po HoughovČ transformaci .......................................................... 49 Obr. 41 – Detail obrázku po HoughovČ transformaci ................................................ 50 Obr. 42 – Obrázek s pĜedbČžnou sítí þar .................................................................... 51 Obr. 43 – Obrázek s vyznaþením souĜadnicové sítČ .................................................. 54 Obr. 44 – Výpis do konz. okna Binární matice – pĜeþteno z obrázku ....................... 55 Obr. 45 - Výpis do konz. okna – Binární matice – maska, korekce chyb.................. 56 Obr. 46 - Výpis do konz. okna – Binární matice – matice bez masky....................... 57 Obr. 47 - Výpis do konz. okna – Dekódované znaky ................................................ 59

SEZNAM TABULEK Tab. 1 - Maximální poþet znakĤ v QR kódu.............................................................. 17 Tab. 2 - Indikátory datových módĤ............................................................................ 22 Tab. 3 - Poþet bitĤ vyhrazených pro indikátor poþtu znakĤ ...................................... 22 Tab. 4 - Tabulka znakĤ pro alfanumerické kódování ................................................ 22 Tab. 5 – PomČr datových CW a CW korekce chyb ................................................... 27 Tab. 6 - ÚrovnČ korekce chyb.................................................................................... 27 Tab. 7 – Vzorce pro výpoþet nejvhodnČjší masky ..................................................... 28 Tab. 8 – Zhodnocení testování programu .................................................................. 60

9


1.

ÚVOD

Tato práce se zabývá problematikou þtení QR kódĤ. Na zaþátku je uveden struþný pĜehled všech þárových 1D i 2D kódĤ, které se ve velkém rozsahu používají v prĤmyslu, logistice, ale þásteþnČ i v jiných aplikacích, se kterými se lze setkat v každodenním životČ. VýznamnČ urychlují kontrolu produktĤ, pĜi jejich pohybu, výrobČ, þi montáži. Z tČchto kódĤ byly vybrány právČ QR kódy. Z užívaných kódĤ mají, napĜíklad oproti EAN kódu, propracovanČjší korekci chyb a vzhledem k jejich velikosti je možné do nich uložit vČtší množství dat. V této práci je uvedeno jejich složení, dĤležité prvky v nich obsažené, zpĤsoby kódování dat, atd. Jejich struktura, vlastnosti a kódování dat jsou tak složité, že je tato problematika rozdČlena na nČkolik podkapitol. Dále je také uveden pĜíklad pĜevodu dat do QR kódu krok po kroku. V další kapitole je popsán postup zhotovení databáze snímkĤ reálného QR kódu, vytištČného na matném a lesklém papíru. Byly použity rĤzné typy osvČtlení a uspoĜádání scény tak, aby byly poĜízeny co nejkvalitnČjší snímky. Další kapitola popisuje algoritmus zpracování snímku QR kódu, s využitím programovacího jazyku C++ a knihovny OpenCV. Jeho vstupem je zmínČný snímek, výstupem jsou dekódovaná data. V závČru této práce jsou uvedeny dosažené výsledky.

10


2.

TEORETICKÝ ÚVOD

V této kapitole je krátce zmínČna historie þárových kódĤ a oblast jejich použití. V první þásti je uveden pĜehled nejpoužívanČjších þárových kódĤ. V druhé þásti je detailnČ popsán QR kód, jeho struktura, složení, vlastnosti a je zde také uveden pĜíklad zakódování dat do QR kódu.

2.1

ýÁROVÉ KÓDY

Kapitola obecnČ popisuje vznik a použití þárových kódĤ. Uvádí dČlení þárových kódĤ na 1D a 2D kódy a nejznámČjší zástupce z tČchto skupin.

2.1.1 Jak vznikl þárový kód První patent na þárový kód byl podán již v roce 1949 dvČma muži, Bernardem Silverem a Normanem Josephem Woodlandem. Silver se snažil vyhovČt požadavku prezidenta obchodních firem na vývoj systému k automatickému þtení údaje o produktu pĜi kontrole. Ke komerþnímu využití došlo až roku 1966, a to ve tvaru soustĜedných kružnic, tzv. „býþí oko.“ Tento tvar se neosvČdþil, a proto roku 1970 vznikl klasický þárový kód složený z þar. Roku 1974 vznikla jeho první þteþka a produkt s þárovým kódem se objevil v obchodech. [16]

2.1.2 Co je to þárový kód a kde se používá ýárový kód je v dnešní dobČ velice efektivní zpĤsob, jak rychle a bezchybnČ naþítat data do poþítaþe þi jiného systému k dalšímu zpracování, aniž bychom použili klávesnici. Podle zdroje [7] dochází pĜi ruþním zadávání k chybČ prĤmČrnČ pĜi každém tĜístém zadání, zatímco u þárových kódĤ se poþet chyb snižuje až na jednu milióntinu. VČtšina kódĤ obsahuje i zabezpeþení, díky kterému lze zjistit, zda pĜeþtená data jsou korektní nebo ne. Navíc se do nČkterých þárových kódĤ vnáší i korekce chyb, která sice zabere urþité místo, jinak urþené pro data, ale dokáže zpČtnČ zrekonstruovat a opravit poškozený kód. QR kód dokáže napĜíklad opravit až 30%

11


poškozené matice. Do þárového kódu se mĤže ukládat výrobní þíslo, váha, cena, název výrobce, datum výroby, jméno zodpovČdné osoby, skladové informace, atd. PĜi tvorbČ þárového kódu se využívá kontrastních barev jako je þerná a bílá, aĢ už v podobČ þerných þar a bílých mezer nebo þerných a bílých þtvercĤ. Kontrastu se využívá pĜi þtení þteþkami, založenými na principu odrazu infraþerveného nebo spíše laserového paprsku, ale také pĜi snímání kamerou s následnou detekcí hran mezi þernou a bílou barvou pomocí poþítaþového zpracování obrazu. ýárový kód mĤže být také vypálen laserem pĜímo na výrobek. [5], [7], [10].

2.1.3 1D þárové kódy 1D (jednorozmČrné) þárové kódy = skládají se z nČkolika vodorovných þerných þar o rĤzných tloušĢkách oddČlených bílými mezerami. ýtení tedy probíhá jen v jedné souĜadnici. Jsou v EvropČ prozatím nejrozšíĜenČjšími þárovými kódy, ale v budoucnu by je mohly nahradit 2D maticové kódy. EAN „Zkratka EAN znamená European Article Number. NejþastČjší EAN kód a pravdČpodobnČ nejþastČjší þárový kód vĤbec je EAN-13, který byl definován standardizaþní organizací GS1. Kódy EAN-13 jsou používány po celém svČtČ k oznaþování jednotlivých druhĤ zboží. PozmČnČná podoba tohoto kódu napĜíklad umí uchovávat ISBN kódy knižních publikací nebo ISSN kódy þasopisĤ a jiných periodik. Z kódu EAN-13 lze zjistit zemi pĤvodu výrobce nebo zpĤsob užití daného zboží. MénČ jsou používány kódy EAN-8, které jsou vyhrazeny a používány pro menší položky, na které je problém umístit 13místný kód, jako jsou tĜeba cukrovinky“. Citováno z [13]. U kódu EAN-13 platí, že první dvČ nebo tĜi þíslice jsou systémové. Obvykle urþují zemi, kde je zaregistrován výrobce, nebo konverzi do ISBN nebo ISSN. Další þtyĜi nebo pČt þíslic obsahují kód výrobce. Následující pČtice urþuje kód výrobku. Poslední je kontrolní þíslice, která se vČtšinou dopoþítá funkcí modulo 10. Každá þíslice je kódována dvČma þárami a dvČma mezerami. [13]

12


Obr. 1 - Ukázka kódu EAN-13 [13]

UCC/EAN 128 „UCC/EAN128 je þárový kód využívaný pro oznaþování obchodních a logistických jednotek. UmožĖuje zakódovat pomocí standardizovaných aplikaþních identifikátorĤ (AI) mnoho podstatných informací o daném výrobku, jako jsou napĜ. þíslo dodávky, datum výroby, datum balení, minimální trvanlivost, hmotnost, délka, šíĜka, plocha, objem, komu má být zboží zasláno atd. Každá z informací má svĤj vlastní AI, který jednoznaþnČ urþuje o jaký typ údaje se jedná. Pro vlastní kódování znakĤ se využívá Code 128.“ Citováno z [8].

Obr. 2 - Ukázka kódu UCC/EAN 128 [8]

CODE 39 „Kód Code 39 je používaný v automobilovém prĤmyslu, ve zdravotnictví i v dalších odvČtvích prĤmyslu a obchodu. Je schopen kódovat þíslice 0 až 9, písmena A až Z a dalších sedm speciálních znakĤ, pĜiþemž každý znak je reprezentován pČti þárami a þtyĜmi mezerami.“ Citováno z [10].

Obr. 3 - Ukázka kódu Code 39 [10]

13

ÚSTAV AUTOMATIZACE A MċěICÍ TECHNIKY Fakulta elektrotechniky a komunikaþních technologií

14

Vysoké uþení technické v BrnČ

Kód 2 z 5 (2/5) Je možné zakódovat pouze numerická data. Kód obsahuje znak Start a Stop. Každá þíslice se skládá z pČti þar a pČti mezer, z toho 3 þáry jsou slabé a 2 þáry jsou silné (trojnásobek slabé þáry). Dobré ke þtení ve ztížených podmínkách a nekvalitnČ vytištČných kódĤ. Dosahují však pĜíliš velké délky, která je navíc promČnná. [13]

Obr. 4 - Ukázka kódu 2 z 5 [14]

2.1.4 2D þárové kódy 2D (dvourozmČrné) þárové kódy = skládají se vČtšinou z matice þerných a bílých þtvercĤ (modulĤ), tím jsou data uložena v obou souĜadnicích, jak horizontálních,

tak

vertikálních.

Zaþíná

se

rozšiĜovat

jejich

užití,

díky

implementované korekci chyb u vČtšiny z nich a vČtší datové kapacitČ. S ní však roste i nároþnost kódu na jeho zpracování. PDF 417 „PDF 417 je dvourozmČrný (2D) kód s velmi vysokou informaþní kapacitou a schopností detekce a oprav chyb (pĜi porušení kódu). Oznaþení PDF 417 (Portable Data File) vychází ze struktury kódu: každé kódové slovo se sestává ze 4 þar a 4 mezer o šíĜce minimálnČ jednoho a maximálnČ šesti modulĤ. Celkem je však modulĤ ve slovČ vždy pĜesnČ 17. Na rozdíl od 1D þárových kódĤ, které obvykle slouží jako klíþ k vyhledání údajĤ v nČjaké databázi externího systému, si PDF 417 nese všechny údaje s sebou a stává se tak nezávislý na vnČjším systému. Do PDF 417 lze zakódovat nejenom bČžný text, ale i grafiku nebo speciální programovací instrukce. Velikost datového souboru mĤže pĜitom být až 1,1 kB. PĜi


generování symbolu lze zvolit úroveĖ korekce chyb, þímž lze zabezpeþit þitelnost i pĜi þásteþném poškození kódu. PĜíkladem použití PDF 417 mohou být nejrĤznČjší identifikaþní karty, Ĝidiþské prĤkazy (v nČkterých státech USA), kód lze využít i pro zakódování diagnózy pacientĤ apod. Kódy PDF 417 jsou rovnČž využívány v systému EAN/UCC v kombinaci s EAN 13, UPC A, UCC/EAN 128 a GS1 Databar kódy jako tzv. složené (kompozitní) kódy.“ Citováno z [9].

Obr. 5 - Ukázka kódu PDF 417 [9]

DATAMATRIX Je 2D kód, který se skládá z matice þtvercĤ. Referenþním znakem je levý a dolní okraj, který je tvoĜen souvislými þárami. MĤže být ve velikostech od 8x8 do 144x144 bodĤ. Maximální objem dat je 2335 pro alfanumerické znaky a 3116 pro numerické znaky. Datamatrix používá Reed-Solomonovu korekci chyb. [7][13]

Obr. 6 - Ukázka kódu DATAMATRIX [13]

15


QR KÓD Kód je velice podobný Datamatrix kódu, ale obsahuje jiné referenþní obrazce. Nejsou to jen dvČ þáry, ale jsou to tĜi prvky, z nichž každý se skládá ze tĜí soustĜedných þtvercĤ, což usnadĖuje nalezení kódu ve scénČ a jeho správnou rotaci pĜi zpracování. Objem zakódovaných dat mĤže být 4296 alfanumerických znakĤ, 7089 numerických znakĤ, ale i Byte (binární data) a Kanji znaky. Použita je ReedSolomonova korekce chyb.

Obr. 7 - Ukázka QR kódu

16


2.2

QR KÓD

2.2.1 Úvod QR kódy jsou popsány v normČ ISO/IEC 18004, ze které bylo pĜevážnČ þerpáno v celé této kapitole a je uvedena jako zdroj [5]. V následujících podkapitolách je uvedeno, z þeho se QR kódy skládají, k þemu slouží jejich jednotlivé prvky, jaká data mohou být do kódĤ uložena a kolik jakého typu jich mĤže být, informace o zpĤsobu pĜevodu vlastních dat do tvaru pro vložení do kódu a dodateþných informaþních datech kódu. V Tab. 1 je uvedeno, kolik znakĤ lze uložit do QR kódu. Ten je vzhledem k jeho velikosti schopen nést velké množství dat. Implementovány jsou korekce chyb, takže v nejvíce zabezpeþeném pĜípadČ lze obnovit až 30% poškozených dat. Tyto kódy jsou charakteristické svými soustĜednými þtverci ve tĜech ze þtyĜ rohĤ, které urychlují lokalizování kódu ve scénČ. Kód obsahuje i další prvky, které zkvalitĖují a zrychlují þtení kódu. Typ dat Numerická data Alfanumerická data Byte Kanji

Poþet znakĤ 7089 4296 2953 1817

Tab. 1 - Maximální poþet znakĤ v QR kódu

2.2.2 Struktura QR kódu QR kód se skládá z matice þerných a bílých bodĤ (modulĤ). PĜiþemž þerný modul pĜedstavuje logickou jedniþku a bílý logickou nulu. Záchytným bodem je tzv. Finder pattern. Nazýván také jako kotvící obrazec. Využívá se k rychlému lokalizování levého horního rohu kódu. Skládá se ze tĜí soustĜedných þtvercĤ jak je ukázáno na Obr. 8 i s jeho pĜesnČ definovanými rozmČry. Od velikosti kódu verze 2 pĜibývá ještČ další tzv. Alignment pattern a se zvyšující se verzí pĜibývá jejich poþet. Jeho struktura je zobrazena na Obr. 9 a

17


pĜíklad umístČní je na Obr. 11. Tento obrazec slouží k synchronizaci souĜadnic na poĜízeném snímku kódu a souĜadnic matice þerných a bílých bodĤ (=modulĤ) tohoto kódu v reálném prostĜedí. Pokud by byl kód vytištČn na mírnČ nerovném (zvlnČném) povrchu, pomohou tyto obrazce pĜi zpracování a narovnání zdeformovaného obrazu. Dalším dĤležitým prvkem QR kódu jsou Timing patterns (= zamČĜovací znaþky). Skládají se z jednoho Ĝádku (sloupce) stĜídajících se modulĤ þerné a bílé barvy, pĜiþemž vždy se zaþíná a konþí þerným modulem. Urþují tak hustotu souĜadnicové sítČ QR symbolu. Separátor slouží k oddČlení dat a referenþních symbolĤ. Jeho šíĜka je 1 bod (modul). Quiet zone (= prázdný okraj kódu) je tvoĜen oblastí o šíĜce 4 bodĤ kolem celého QR symbolu a umožĖuje þtecím zaĜízením rychleji zamČĜit kód ve scénČ, aniž by splýval s okolím. Zbývající oblast QR kódu je urþena pro vlastní data, data korekce chyb, informaci o použité masce a typu korekce chyb. Celá struktura kódu je zobrazena na Obr. 10. U kódu verze 2 a vyšší pĜibývá navíc zarovnávací symbol, jehož poþet a umístČní se mČní s použitou verzí (velikostí) kódu podle pĜesných pravidel, a také pĜibývá údaj o verzi kódu, kdy u verze 2 pĜedstavuje datový prostor 7 bitĤ a zvyšuje se s verzí kódu dle pravidel. Tento údaj o verzi kódu obsahuje i korekci chyb. Kód verze 2 je na Obr. 11.

1: 1:

3

: 1: 1

3

5

Obr. 8 - Struktura Finder pattern

7

18


1: 1:1 :1: 1

1

3

5

Obr. 9 - Struktura Alignment pattern

3 x Finder pattern - Kotvící obrazec Informace o použité masce a korekci chyb Timing patterns - ZamČĜovací znaþky

Separátor

Data + korekce chyb

Quiet zone - Prázdný okraj kódu Obr. 10 - Struktura QR kódu verze 1

19


3 x Finder pattern - Kotvící obrazec Informace o použité masce a korekci chyb Timing patterns - ZamČĜovací znaþky

Separátor Data + korekce chyb Velikost kódu Alignment pattern - Zarovnávací symbol

Quiet zone - Prázdný okraj kódu Obr. 11 - Struktura QR kódu verze 2

2.2.3 Velikosti QR kódu QR kódy jsou nČkolika velikostí (=verzí). Od verze 1, kdy matice je rozmČru 21x21 bodĤ (Obr. 10), až po verzi 40, kdy má matice rozmČr 177x177 bodĤ. Na Obr. 12 je ukázán jen menší kód verze 14 o rozmČru 73x73 bodĤ, na kterém je dobĜe vidČt, jak pĜibývají zarovnávací obrazce. Existuje také Micro QR kód, který je ve verzích M1-M4, kdy M1 se skládá z 11x11 bodĤ, M4 z 14x14 bodĤ. Micro QR kódy se tato práce nebude dále zabývat, protože nejsou tak používané v praxi a lze do nich uložit jen malý objem dat oproti klasickým QR kódĤm.

20


Obr. 12 - QR kód verze 14

21


Mód

Indikátor módu

ECI

0111

Numerický

0001

Alphanumerický

0010

Byte

0100

Kanji

1000

Structured Append

0011

(Strukturované spojování kódĤ)

0101 (1. pozice)

FNC1

1001 (2. pozice)

Koncový znak (konec zprávy)

0000

Tab. 2 - Indikátory datových módĤ

Verze 1 až 9

Numerický Alphanumerický mód mód 10 9

Binární mód 8

Kanji mód 8

10 až 26

12

11

16

10

27 až 40

14

13

16

12

Tab. 3 - Poþet bitĤ vyhrazených pro indikátor poþtu znakĤ

Písmeno Hodnota Písmeno Hodnota Písmeno Hodnota 0 0 F 15 U 30 1 1 G 16 V 31 2 2 H 17 W 32 3 3 I 18 X 33 4 4 J 19 Y 34 5 5 K 20 Z 35 6 6 L 21 SP 36 7 7 M 22 $ 37 8 8 N 23 % 38 9 9 O 24 * 39 A 10 P 25 + 40 B 11 Q 26 41 C 12 R 27 . 42 D 13 S 28 / 43 E 14 T 29 : 44

Tab. 4 - Tabulka znakĤ pro alfanumerické kódování

22


23


2.2.4 Kódování vlastních dat Vlastní data nesená QR kódem mohou být nČkolika módĤ: Extended Channel Interpretation (ECI), numerický, alfanumerický, binární a Kanji. Módy je možné i kombinovat. Na poþátku je tedy nutné vybrat jaký datový mód budeme používat. Podle Tab. 2 se zvolí indikátor módu a podle verze QR kódu je odeþteno v Tab. 3 kolik bitĤ, bude mít informace o poþtu kódovaných znakĤ. Dále je uveden postup pĜevodu ĜetČzce numerických a alfanumerických znakĤ na binární þíslo se všemi náležitostmi. Pro numerické znaky je postup na Obr. 13 a pro alfanumerické na Obr. 14.

Vstupem je ĜetČzec numerických znakĤ

Vstupní ĜetČzec mĤže mít libovolný poþet znakĤ, proto po rozdČlení na skupiny po tĜech znacích

Typ

Délka

vstupních

vstupního

dat

ĜetČzce

RozdČlit ĜetČzec na

mĤže poslední skupina

trojciferná þísla

obsahovat dvouciferné nebo jednociferné þíslo.

PĜevést trojciferná

(PĜevod v pĜípadČ:

þísla na 10bitová

dvouciferného na 7bitové,

binární þísla

jednociferného na 4 bitové.)

Indikátor

Indikátor

módu

poþtu

Spojit binární þísla

znakĤ

v jeden ĜetČzec

PĜipojit indikátor módu a poþtu znakĤ k

(=výsledný ĜetČzec)

datovému ĜetČzci Obr. 13 - Postup pĜevodu numerických znakĤ


Vstupem je ĜetČzec alfanumerických znakĤ Nahradit každý znak Typ

Délka

dekadickým þíslem podle

vstupních

vstupního

pĜevodní tabulky

dat

ĜetČzce RozdČlit na skupiny po dvou

Indikátor

Indikátor

módu

poþtu znakĤ

dekadických þíslech Platí, oznaþíme-li:

Provést matematickou

První þíslo A

C=A*45+B

Druhé þíslo B

operaci:

ZĤstane-li vlivem

PĜevést C na 11bitové

lichého poþtu

binární þíslo

vstupních znakĤ poslední þíslo jen

Spojit binární þísla v jeden ĜetČzec

A (B již není), nenásobí se *45 a pĜevede se pĜímo na 6bitové binární þíslo

PĜipojit indikátor módu a poþtu znakĤ k

(=výsledný ĜetČzec)

datovému ĜetČzci

Obr. 14 - Postup pĜevodu alfanumerických znakĤ

24


2.2.5 RozdČlení dat QR kódu na codewords Codeword (CW) by se dalo pĜeložit jako zakódované slovo. Myšleno jako 8bitové binární þíslo, které se v QR matici vyskytuje v pĜesnČ definovaném tvaru a velikosti. Velikost je odvozena od zmínČných osmi bitĤ, což znamená, že je to urþitá oblast, ve které je 8bitová informace, kdy logickou jedniþku pĜedstavuje þerný modul a logickou nulu bílý modul v této oblasti. VČtšinou má CW pravidelný tvar obdélníku, ale nČkdy je jeho tvar nepravidelný, napĜíklad kvĤli pĜítomnosti zarovnávacího symbolu. Jak to v tom pĜípadČ vypadá je dobĜe vidČt na Obr. 12. Na Obr. 15 je zobrazeno þíslování datových CW (D1-D19) a CW korekce chyb (E1-E7) na QR kódu verze 1. PomČr poþtu datových CW a CW korekce chyb je rĤzný podle použité úrovnČ Reed-Solomonova kódování (více viz kapitola 2.2.6). Na tomto obrázku má QR kód verze 1 vždy celkem 26 CW. Zvolena byla korekce chyb úrovnČ L, a proto z celkového poþtu obsahuje 7 CW korekci chyb.

D18 D17 D19 D16 D19 D16 E7 E6 E5

E4 E1 D15 D10 D9 D4 D3

E2 D14 D11 D8 D5 D2

E3 D13 D12 D7 D6 D1

Obr. 15 - RozmístČní codewords

Je však dĤležité pĜesnČ definovat i to, jak þíst data z jednotlivých CW. Princip je zobrazen na Obr. 16. Záleží také na tom, kterým smČrem roste þíslo CW (D1-D19) Bit oznaþený jako 7 je v pĜípadČ rĤstu vzhĤru v pravém dolním rohu, v pĜípadČ rĤstu

25


26


dolĤ v pravém horním rohu. Potom se þíslo bitu zvyšuje stĜídavČ vlevo a vpravo jak je naznaþeno na výše zmínČném obrázku. Bit 7 je nejvýznamnČjší bit (MSB).

D18 D17 D4

D19 D16 D19 D16 E7 E6 E5

E4 E1 D15 D10 D9 D4 D3

+ D5

E2 D14 D11 D8 D5 D2

E3 D13 D12 D7 D6 D1 D6

6

7

0

1

4

5

2

3

2

3

4

5

0

1

6

7

6

7

0

1

4

5

2

3

2

3

4

5

0

1

6

7

6

7

0

1

4

5

2

3

2

3

4

5

0

1

6

7

D3

D2

D1

Obr. 16 - Rozložení jednotlivých bitĤ v CW

2.2.6 Korekce chyb QR kódy využívají pro korekci chyb Reed-Solomonovy algoritmy. ÚrovnČ korekce chyb jsou L (7%), M (15%), Q(25%) a H(30%). Procenta v závorkách znaþí, kolik procent je možno obnovit pĜi poškození QR matice. ZároveĖ se také mČní pomČr datových codewords a CW korekce chyb. Platí úmČra, þím vyšší úroveĖ korekce chyb, tím vyšší poþet CW korekce chyb a nižší poþet CW použitelných pro vlastní data. V této práci jsme se omezili na práci s QR kódy verze 1, tedy velikosti 21x21 modulĤ. Tomu odpovídá celkem 26 CW. PomČr dat a korekce chyb u této verze pro rĤzné úrovnČ shrnuje Tab. 5. Pro každou velikost QR kódu existuje pĜesnČ definovaný pomČr dat a korekce chyb, které je možné zjistit v [5]. Je to tabulka, která pro svoji rozsáhlost není v této práci celá uvedena. Tato práce se nezabývá Reed-Solomonovou korekcí chyb více do hloubky, a není zde tedy nijak popsán jejich pĜesný algoritmus.


V Tab. 6 je uveden mimo jiné také binární indikátor použité korekce chyb. Je dĤležitým prvkem pĜi tvorbČ i dekódování QR kódu a urþuje jaká úroveĖ ReedSolomonovy korekce chyb byla použita pĜi tvorbČ kódu. ÚroveĖ korekce chyb L M Q H

Poþet CW pro vlastní data 19 16 13 9

Poþet CW pro korekci chyb 7 10 13 17

Tab. 5 – PomČr datových CW a CW korekce chyb

ÚroveĖ korekce chyb L M Q H

Obnovitelnost kódu (%) 7 15 25 30

Binární indikátor 01 00 11 10

Tab. 6 - ÚrovnČ korekce chyb

2.2.7 Používané masky Koneþný krok pĜi tvorbČ QR kódu je provedení logické funkce XOR mezi maskou a dosud vytváĜenou QR maticí. Ta se v tom okamžiku skládá z vlastních dat pĜevedených do binárního kódu. Masky jsou vzory o velikosti QR kódu, které slouží k tomu, aby ve výsledném QR kódu nevznikala souvislá místa þerné nebo bílé barvy. Kdyby byl snímek s kódem poĜízen obrazovým snímaþem s nižším rozlišením, souvislá místa na poĜízeném snímku by nemusel software správnČ rozpoznat. Proto existuje 8 masek, pĜiþemž se vybere ta, která vytvoĜí výsledný obraz tak, aby tato spojitá místa nevznikala. Dále jsou popsány algoritmy, které dokáží vypoþítat pĜesnou hodnotu tzv. trestných bodĤ za nevhodné rozmístČní þerných bodĤ. Vybírá se maska s nejmenším poþtem trestných bodĤ.

27


V následující tabulce je zobrazen výpoþet promČnných N1 až N4 pĜedstavující trestné body pro urþení nejvhodnČjší masky QR kódu. ýím menší jsou tyto promČnné tím je kód vhodnČjší. Za nerozlišitelné obrazce jsou považovány masky, kdy je vypoþteno N1=3, N2=3, N3=40, N4=10. Jsou-li sousední moduly v Ĝádku, þi ve sloupci, stejné barvy, potom promČnná i udává poþet modulĤ, které pĜesahují poþet 5 modulĤ v této ĜadČ. PromČnná k znaþí o kolik procent (udáváno po 5%) se odchyluje poþet þerných modulĤ od ideálního 50% pomČru þerných a bílých modulĤ. PĜedmČt Vyhodnocení podmínky Sousední moduly v Ĝádku nebo ve Poþet modulĤ = (5 + i) sloupci stejné barvy Blok modulĤ stejné barvy Velikost bloku = m × n

Body (trestné) N1 + i

Existence obrazce 1 : 1 : 3 : 1 : 1 pomČr (tmavý:svČtlý:tmavý:svČtlý:tmavý) obrazec v Ĝádku/sloupci, následován bílou oblastí 4 moduly širokou PomČr tmavých modulĤ v celém 50 ± (5 × k)% až 50 ± (5 × symbolu (k + 1))%

N3

N2 × (m - 1) × (n - 1)

N4 × k

Tab. 7 – Vzorce pro výpoþet nejvhodnČjší masky

Všechny užívané masky jsou zobrazeny na Obr. 17, kde šedČ zbarvené þásti vzorĤ nejsou uplatnČny pĜi tvorbČ výsledného kódu. Pod každým obrázkem je uvedeno binární þíslo pĜedstavující þíslo masky a na dalším Ĝádku je rovnice, která ukazuje jakým algoritmem je obrázek vytvoĜen.

28


j

i

000

001

010

(i+j) mod 2 = 0

i mod 2 = 0

j mod 3 = 0

011

100

101

(i+j) mod 3 = 0

((i div 2) + (j div 3)) mod 2 = 0

(i*j) mod 2 + (i*j) mod 3 = 0

110

111

((i*j) mod 2 + (i*j) mod 3) mod 2 = 0

((i+j) mod 2 + (i*j) mod 3) mod 2 = 0

Obr. 17 - Masky

29


2.2.8 Kódování informace o použité korekci chyb a masce Tyto data jsou uložena do míst na Obr. 10 oznaþených zelenou barvou. Na Obr. 18 je znázornČno jak odeþíst 15 bitové slovo nesoucí zmínČné informace z QR symbolu. NejvýznamnČjší bit (MSB) odeþítaného slova je na pozici þísla 14 v obrázku. Bit 14. a 13. obsahuje informaci o úrovni korekce chyb, 12., 11. a 10 bit udává použitou masku. Ostatních 10 bitĤ obsahuje korekci chyb typu BCH (15, 5), která pro svoji složitost není v práci více popsána. Výše zmínČné 15 bitové slovo se však do kódu nevkládá pĜímo v této podobČ. Je zapotĜebí provést logickou operaci XOR mezi tČmito daty a maskou, která je dle pravidel tvorby QR kódu dána: 101010000010010. Výsledek je možno vložit do QR kódu na urþené místo. PĜíklad vstupních dat:

111101011001000

Maska:

101010000010010

Výsledek operace XOR:

010111011011010 MSB

LSB

0 1 2 3 4 5

14 13 12 11 10 9

6 8 7

8 9 10 11 12 13 14

7 6 5 4 3 2 1 0

Vždy þerný bod

Obr. 18 - Kódování informace o použité masce a korekci chyb

30


2.2.9 PĜíklad zakódování dat do QR kódu V této kapitole je popsáno, jak vytvoĜit svĤj kód krok po kroku. Vstupní data budou v alfanumerickém formátu. Výstupní kód bude verze 1, to znamená velikosti 21x21 bodĤ. Reed-Solomon kódování bylo zvoleno úrovnČ Q, tedy bude možné pĜi poškození kódu obnovit až 25% dat. Zvolený ĜetČzec k vložení do QR kódu je: MARTINS

1. Nahradit každý alfanumerický znak vstupního ĜetČzce odpovídajícím desítkovým þíslem dle Tab. 4. Vstupní ĜetČzec: MARTINS. M = 22, A = 10, R = 27, T = 29, I = 18, N = 23, S = 28. MARTINS = (22,10,27,29,18,23,28)

2. RozdČlit na skupiny po dvou dekadických þíslech z minulého bodu. PĜiþemž první þíslo z dvojice je oznaþeno A a druhé B (A,B) (22,10)

(27,29)

(18,23)

(28)

3. Provést matematickou operaci dle vzorce C = A*45 + B. V pĜípadČ, že poþet dekadických þísel byl lichý a zĤstalo jako poslední jen jedno þíslo, pak se toto þíslo nenásobí þíslem 45 a pĜevádí se v dalším bodČ pĜímo na 6bitové binární þíslo. C1 = 22*45 + 10 = 1000 C2 = 27*45 + 29 = 1244 C3 = 18*45 + 23 = 833 C4 = 28

31


32


4. PĜevést jednotlivá dekadická þísla do dvojkové soustavy. KromČ výjimky popsané v pĜedešlém bodČ, se pĜevádí vždy na 11bitová þísla. 1000 = 01111101000 1225 = 10011011100 833 = 01101000001 28 = 011100

5. Spojit binární þísla v jedno 01111101000 10011011100 01101000001 011100

6. Vybrat indikátor módu dle Tab. 2. Typ vstupních dat: alfanumerická data. Indikátor módu: 0010

7. VytvoĜit indikátor poþtu znakĤ, jeho délka se Ĝídí dle Tab. 3. Poþet znakĤ = 7 Poþet znakĤ ve dvojkové soustavČ (9bitĤ) = 000000111

8. Spojit indikátor módu + indikátor poþtu znakĤ + ĜetČzec z bodu 5. 0010 000000111 01111101000 10011011100 01101000001 011100 OddČlení mezerami po 8 bitech (poslední bity doplnČny nulami do 8bitĤ): 00100000 00111011 11101000 10011011 10001101 00000101 11000000 MSB

LSB

Každých 8 bitĤ nyní pĜedstavuje 1 CW. Celkem tedy data budou v 7 CW.


33


Protože byla zvolena korekce chyb úrovnČ L, bude pomČr datových a korekþních CW tak, jak je na Obr. 19. Na tomto obrázku jsou také znázornČna pĜesnČ jednotlivá CW i s vypoþítanými daty. Ze zdroje [5] bylo odeþteno, že v tomto pĜípadČ je 13 korekþních CW a 13 datových CW.

E5 E4

D4

E6 E3 E6 E3 E13 E12 E11

D5

E10 E7 E2 D10 D9 D4 D3

E8 E1 D11 D8 D5 D2

E9 D13 D12 D7 D6 D1

D7

6

7

0

1

4

5

2

3

2

3

4

5

0

1

6

7

6

7

0

1

4

5

2

3

2

3

4

5

0

1

6

7

0

1

6

7

0

1

2

3

4

5

2

3

4

5

2

3

4

5

6

7

0

1

6

7

D3

D2

D1

D6

Obr. 19 - PĜíklad kódu - Rozložení CW

9. Do nevyužitých datových CW doplnit vyplĖující CW Na Obr. 20 vlevo jsou vytvoĜená CW vložena do kódu. Nevyužitá místa se vyplní tzv. Pad codewords - vyplĖujícími CW. Jsou zobrazeny na obrázku uprostĜed. Jejich tvar je: 11101100 v prvním CW a v následujícím CW je: 00010001. Tyto dva CW se opakují až do úplného vyplnČní datových CW kódu.


10. Na Obr. 20 vpravo jsou CW obsahující korekci chyb. Jak bylo uvedeno v kapitole 2.2.6, korekcí chyb se pro její složitost tato práce tolik nevČnuje. Dosavadní znalosti tedy zatím nedovolují pĜesnČ vygenerovat data korekce chyb, a proto byly získány z existujícího kódu odebráním masky. Kód byl vygenerován pomocí generátoru pĜístupného online na www stránkách, které jsou uvedeny jako zdroj [15].

+

+ Vlastní data

VyplĖující CW

CW korekce chyb

Spojení horních kódĤ Obr. 20 - PĜíklad kódu - Data, vyplĖující CW a korekce chyb

34


XOR

Vstupní kód

Maska

Maskovaný kód Obr. 21 - PĜíklad kódu - Maskování kódu

Kódování informace o použité korekci chyb a masce Zvolená korekce chyb je úrovnČ L, její indikátor = 11 Nejvíce vyhovující maska (odeþtena z existujícího vygenerovaného QR kódu): je þíslo 6, její indikátor = 110. Tyto data jsou také zabezpeþena pomocí korekce chyb. Její výsledek je vybrán z tabulky v literatuĜe [5] nebo vytvoĜen pomocí algoritmu BCH kódování = 1011001000. 11 110 1011001000 = indikátor korekce chyb a masky + korekce chyb 10 101 0000010010 = maska (pro operaci XOR) 01 011 1011011010 = výsledné þíslo pĜipravené k vložení do QR kódu MSB

LSB

35


0 1 2 3 4 5

14 13 12 11 10 9

6 8 7

7 6 5 4 3 2 1 0

8 9 10 11 12 13 14

Obr. 22 - PĜíklad kódu - Informace o korekci chyb a masce

Obr. 23 - PĜíklad kódu - Výsledný QR kód v reálné scénČ

36


3.

POěÍZENÍ DATABÁZE SNÍMKģ

Bylo provedeno snímání nČkolika reálných obrázkĤ QR kódĤ. Pro snímání byly použity dva digitální snímaþe. Jedním z nich byl snímaþ zabudovaný do mobilního telefonu Sony Ericsson K750i, jehož rozlišení je 2Mpx (1632x1224px). Jako druhý byl použit digitální fotoaparát Sony DCS-P72 s rozlišením 2,8Mpx (2048x1360px). Jejich rozlišení je sice témČĜ stejné, ale optické zpracování obrazu v digitálním fotoaparátu je ještČ pĜed pĜíchodem obrazu na CCD (CMOS) snímaþ znaþnČ kvalitnČjší, a tím i výsledná fotografie. Mobilní telefon disponuje jen jednoduchým optickým vybavením v omezeném prostoru, a tudíž jsou fotografie, obzvláštČ pĜi špatnČ osvČtlené scénČ, ménČ kvalitní. Reálný kód byl vyhotoven v nČkolika velikostech na obyþejný bílý a na lesklý fotografický papír. PĜisvČtlování bylo provádČno pomocí žárovkového svítidla a LED svítidla (napájeného stejnosmČrným napČtím) ve tvaru trubice. Použity byly tĜi rĤzné úhly svícení a snímání, jak je zobrazeno na obrázcích dále. Na Obr. 24 je snímek lesklého QR kódu, kdy se LED svítidlo nachází na stejném místČ nad scénou jako obrazový snímaþ. V lesklém povrchu je však vidČt odraz svítidla stejnČ jako na Obr. 25, kde snímaþ a svítidlo svírají úhel pĜibližnČ 30°.

VytištČný QR kód

Obr. 24 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED shora

37



Obr. 25 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED šikmo

Jako nejlepší zpĤsob snímání lesklého kódu byla zvolena scéna, kdy snímaþ je pĜímo nad QR kódem a svČtlo je bokem mimo osu okraje snímaného pĜedmČtu. Nevzniká tak odraz, který by poškodil kvalitu obrazu. Problém by mohl nastat v tom, že scéna není rovnomČrnČ osvČtlena. To bude zĜejmé až pĜi zpracování obrazu.


Obr. 26 - Snímek - digi. fotoaparát - lesklý kód - svČtlo LED bokem

Dalo by se to vyĜešit tím, že by se použily dva zdroje svČtla, pĜiþemž každý z nich by byl na jiné stranČ snímaného pĜedmČtu, tak jak je na Obr. 27. Použitím tČchto dvou nebo i více zdrojĤ se dosáhne rovnomČrnČ osvČtlené scény. Snímání probíhá v ose snímaného pĜedmČtu, takže nedochází k deformacím obrazu.

38



Obr. 27 – NejvhodnČjší scéna pro poĜízení fotografie

Dalším experimentem byla aplikace žárovkového svČtla. Postup byl stejný jako u LED svítidla. Byl také stejný výsledek, a to že nejlepší je umístit zdroj svČtla mimo pĤdorys QR kódu a snímaþ pĜímo nad kód.


Obr. 28 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové shora


Obr. 29 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové šikmo

39



Obr. 30 - Snímek - digi. fotoaparát - lesklý kód - svČtlo žárovkové bokem

Na Obr. 31 je zobrazen QR kód vytištČný v menší velikosti, který je i pĜesto velmi dobĜe þitelný. Na druhém obrázku je vidČt, jak moc mĤže být poškozena jeho kvalita odrazem svítidla.

Obr. 31 - Snímek - digi. fotoaparát - malý lesklý kód - svČtlo žárovkové

Obr. 32 - Snímek - digi. fotoaparát - rozdíl mezi lesklým a matným

40


PĜi snímání mobilním telefonem byly snímky také kvalitní, ale pĜi osvČtlení žárovkovým svítidlem vznikaly pĜes obrázek vodorovné pruhy. Tyto byly pravdČpodobnČ zpĤsobeny postupným snímáním obrazu pomocí CMOS snímaþe ve vertikálním smČru, kdy se pĜi naþítání obrazu projevuje kolísání jasu žárovky a pĜípadnČ další rušení. I pĜes nízké rozlišení a snímání z vČtší vzdálenosti má kód na Obr. 33 (ve skuteþnosti 3 cm velký) jeden bod (modul), který je schopen nést informaci, velikost 25x25 pixelĤ, což je pro zpracovaní obrazu více než dostateþné.

Obr. 33 - Snímek - mobilní tel. - malý matný kód - svČtlo žárovkové

Obr. 34 - Snímek - mobilní tel. - velký matný kód - svČtlo LED Takže nejvýhodnČjší je kombinace snímaþe s vyšším rozlišením a dokonalejším optickým pĜizpĤsobením a nasvČtlení alespoĖ dvČma LED svítidly mimo pĤdorys snímaného QR kódu.

41


4.

REALIZOVANÉ ěEŠENÍ

Byl navrhnut algoritmus pro dekódování snímaného QR kódu, který byl oproti pĤvodnímu návrhu (v semestrální práci) zmČnČn v nČkolika prvcích a jeho pozmČnČná podoba je na Obr. 35. NejdĜíve byl barevný vstupní obraz pĜeveden pĜi naþítání do stupĖĤ šedi, což zjednodušuje práci s ním a nČkdy je i obraz ve stupních šedi podmínkou funkþnosti nČkterých funkcí knihovny OpenCV. Dále bylo zjištČno, že vyprahovaný obraz není možné použít pro detekci hran, a proto se algoritmus nyní dČlí na dvČ vČtve. V jedné vČtvi se provede zmínČné prahování obrazu, ve kterém se pozdČji (až po zpracování pozice modulĤ v QR kódu) zjišĢuje pĜítomnost þerného nebo bílého modulu. Ve druhé vČtvi se v obrazu (ve stupních šedi) detekují hrany pomocí Cannyho detektoru, v tČchto hranách se hledají þáry pomocí Houghovy transformace pro detekci þar. Hledání obrysĤ nebylo dokonþeno, k vytvoĜení algoritmu pro jejich hledání, by bylo zapotĜebí více þasu. Z tohoto dĤvodu není možné kód pĜesnČ najít ve scénČ, a je nutné zajistit samotný obraz QR kódu, aniž by se v okolí nacházely další prvky, které by se po aplikaci Houghovy transformace jevily jako þáry. Z tohoto dĤvodu nebylo možné vyĜešit ani automatické otáþení kódu, a tudíž se pĜedpokládá vstupní kód správnČ a pĜesnČ orientovaný. Algoritmus je naprogramován v jazyce C++ s využitím knihovny pro zpracování obrazu OpenCV, která je popsána dále.

42


Vstupem je obrázek ve stupních šedi (formátu JPG)

Segmentace

Segmentace

prahováním

Detekcí hran Houghova transformace pro hledání þar Algoritmus pro vytvoĜení souĜadnicové sítČ QR kódu

Detekce jednotlivých bodĤ (bitĤ) QR matice Dekódovací algoritmus QR kódu (korekce chyb) Dekódovaná data

Obr. 35 – Návrh Ĝešení – Algoritmus pro dekódování QR kódu

43


4.1

KNIHOVNA OPENCV

Název pochází z anglického Open source Computer Vision library. Je to tedy knihovna, jejíž zdrojové kódy jsou volnČ pĜístupné a je možné je upravovat. Je urþena pro zpracování obrazu v reálném þase a práci s poþítaþovým vidČním. Tato knihovna je napsána v jazyce C a C++ a bČží pod operaþním systémem Linux, Windows a Mac OS X. Je schopná využívat vícejádrové procesory. Knihovna má 5 hlavních þástí: 1. CXCORE – obsahuje datové struktury, maticovou algebru, správu pamČti, datové transformace 2. CV – obsahuje zpracování obrazu, analýzu obrazových struktur, rozpoznání obrysĤ, kalibrace kamery 3. ML – Machine learning – funkce pro seskupování, klasifikaci a analýzu dat 4. HighGUI – poskytuje uživatelské rozhranní a funkce pro ukládání a volání obrázkĤ þi videí 5. CVCAM – obsahuje funkce pro práci s videi

44


4.2

POPIS JEDNOTLIVÝCH BLOKģ NAVRŽENÉHO ěEŠENÍ

Tato kapitola popisuje jednotlivé bloky navrženého Ĝešení, které bylo uvedeno na Obr. 35.

4.2.1 Vstupní obrázek Vstupní obrázek má být ve formátu JPG, takže je možné použít pĜímo soubor vytvoĜený digitálním fotoaparátem. Obrázek by mČl obsahovat QR kód o velikosti alespoĖ 400 x 400 pixelĤ (21 modulĤ o šíĜce alespoĖ 19 pixelĤ). Již ve funkci, která naþítá obrázek do algoritmu v C++, se pĜevede z barevného obrázku na obrázek ve stupních šedi (=grayscale). ýiní se tak, protože nepotĜebujeme informaci o barvách v obrazu a protože nČkteré funkce knihovny OpenCV nepodporují barevný obraz. Je dĤležité, aby vstupní obrázek obsahoval QR kód pĜibližnČ tak, jak je tomu na Obr. 36. NemČl by tedy být pootoþený o více jak 1 – 2°. Kolem kódu by nemČly být vytištČné žádné znaky, neþistoty nebo cokoliv, co by mohlo na vstupním obrázku pĜedstavovat nČjaký tmavý objekt. Tato podmínka platí pĜedevším pro oblast nalevo a nahoĜe od QR kódu. Nebudou-li tyto podmínky dodrženy, bude špatnČ detekována souĜadnicová síĢ QR kódu a dojde k jeho chybné detekci. DĤvod této skuteþnosti bude více popsán v kapitole 4.2.5.

Obr. 36 – Vstupní obrázek QR kódu

45


4.2.2 Prahování vstupního obrázku V anglických textech je používáno oznaþení Threshold. Prahování je proces, kdy se prochází hodnoty stupnČ šedi (0-255) ve všech pixelech obrazu. PĜi prahování se nastaví urþitá hranice, pĜi které se má nastavit výstup podle urþité pĜevodní funkce. Tuto pĜevodní funkci je možné vybrat pĜi použití funkce prahování (v OpenCV nazvána cvThreshold).

Obr. 37 – Typy pĜevodních funkcí pĜi prahování [4]

Cílem prahování v této práci bylo rozdČlit obraz na oblasti, které jsou pouze þerné a pouze bílé. PozdČji, až bude známá souĜadnicová síĢ a pozice, ve kterých se nachází moduly QR kódu, se bude snímat barva (þerná/bílá) v tomto bodu. Proto byla použita pĜevodní funkce Threshold Binary – to znamená, že pokud je aktuální

46


hodnota pixelu vyšší jak daná mez, nahradí se þernou, je-li nižší, pak se nahradí bílou. Ostatní pĜevodní funkce nejsou pro aplikaci v této práci pĜíliš vhodné. PĜíklad použití funkce cvThreshold: cvThreshold( img1, img2, 140, 255, CV_THRESH_BINARY ); img1 – vstupní obrázek img2 – výstupní obrázek 140 – hodnota hranice pro prahování 255 – maximální hodnota výstupu funkce prahování CV_THRESH_BINARY – typ pĜevodní funkce – binární (viz Obr. 37)

Výsledek funkce cvThreshold je tedy uložen do promČnné img2. Po jejím zobrazení pomocí funkce cvShowImage( "Image_::2::", img2 ); se zobrazí obrázek takový, jako je ten na Obr. 38. Argument "Image_::1::" v pĜíkazu pĜedstavuje název okna, ve kterém se obrázek zobrazí. PĜi experimentech byly použity snímky rovnomČrnČ osvČtlené pomocí dvou svítidel, takže byl výsledek po jednom prahování velmi dobrý. V pĜípadČ nedokonale osvČtleného snímku, by bylo možné použít prahování s plovoucím prahem.

Obr. 38 – Obrázek po prahování

47


4.2.3 Detekce hran v obraze Pro detekci hran je používán Cannyho hranový detektor. Hrana se nachází v místČ obrazu, kde se výraznČ (v ideálním pĜípadČ skokovČ) mČní jas. MČní se tedy jasová funkce, a to se dá detekovat pomocí derivace. Cannyho detektor je zĜejmČ jedním z nejlepších hranových detektorĤ. Snaží se, aby hrany nechybČly a žádné se neopakovaly, na každou hranu reaguje pouze jednou a poloha hrany musí být dobĜe popsána. PĜi použití Cannyho detektoru postupuje jeho algoritmus v tČchto krocích: -

eliminace šumu – Gaussovým filtrem

-

nalezení hran – SobelĤv filtr

-

ztenþení – eliminace hran blízko sebe

-

prahování – prahování s hysterezí, nastavení nižšího a vyššího prahu

PĜíklad použití funkce cvCanny: cvCanny( img1, img3, 100 , 150 ); img1 / img3

-

100 / 150

hodnota nižšího / vyššího prahu pro prahování

-

vstupní / výstupní obrázek

Obr. 39 – Obrázek po detekci hran

48


4.2.4 Houghova transformace pro detekci þar Houghova transformace obecnČ slouží k detekci základních geometrických objektĤ v obraze (pĜímka, kružnice, elipsa, trojúhelník). V této práci bude výhodné hledat v obraze pĜímky. Funkce z knihovny OpenCV, která zpracovává Houghovu transformaci pro hledání þar v obraze se oznaþuje cvHoughLines2. Její výstup je ukládán do struktury o dvou prvcích (souĜadnicích x a y). Ve struktuĜe za sebou je uložena vždy nejdĜíve souĜadnice poþáteþního bodu a za ní souĜadnice koncového bodu nalezené þáry. PĜi þtení tČchto þar se zjišĢuje, jestli je þára spíše svislá nebo vodorovná a podle toho se pro lepší orientaci nakreslí tak, jak je na Obr. 40, buć þervenou nebo zelenou barvou. ZároveĖ je také vždy poþáteþní bod urþité pĜímky uložen do pole CarySvisle nebo CaryVodorovne podle jejich orientace. Tato pole jsou dále

zpracovávána.

Obr. 40 – Obrázek po HoughovČ transformaci

49


4.2.5 Algoritmus pro vytvoĜení souĜadnicové sítČ PĜevezmou se pole CaraSvisla a CaraVodorovna, ve kterých jsou poþáteþní souĜadnice þar, nalezených Houghovou transformací. Pro zjednodušení bude algoritmus vytvoĜení souĜadnicové sítČ popsán jen pro vertikální þáry. Pro tuto práci byla vytvoĜena funkce Hough_aprox. NejdĜíve je obraz rozdČlen do nČkolika svislých oblastí o definované šíĜce, uložené v promČnné sirka_oblasti. Na Obr. 41 je tato šíĜka kótována symbolem A. V každé této oblasti se zjišĢuje pĜítomnost svislých þar. To se provádí tak, že se hledá v promČnné CaraSvisla (typu pole obsahující všechny poþáteþní body svislých þar) takový bod, který odpovídá svojí polohou prohledávané oblasti. Tyto se uloží do nového pole Cara. A

A

A

A

A

A

A

A

A

X Y

Obr. 41 – Detail obrázku po HoughovČ transformaci

50


Pokud byl poþet nalezených þar v oblasti vyšší jak 3, potom se uvažuje, že se v této oblasti opravdu nachází þára (není to šum) a spoþítá se tedy aritmetický prĤmČr polohy výsledného bodu (þáry). Tedy nejpravdČpodobnČjší souĜadnice þáry tvoĜící souĜadnicovou síĢ QR kódu. Je-li toto provedeno v celé šíĜce obrazu, a to i v horizontální rovinČ s pomocí promČnné CaraVodorovna, vznikne obraz jako ten na Obr. 42, kde modré þáry pĜedstavují aproximované þáry. Zde však vzniká omezení funkþnosti algoritmu, nachází-li se nalevo nebo nahoĜe od QR kódu nČjaká þára. Ta mĤže být zpĤsobena nČjakým šumem, okrajem nálepky QR kódu na pĜedmČtu, þi nČjaká hrana na pĜedmČtu samotném. To pak zpĤsobí, že se zaþne souĜadnicová síĢ vytváĜet již od této nežádoucí þáry. Proto musí být nalevo a nahoĜe QR kódu prázdná plocha.

Obr. 42 – Obrázek s pĜedbČžnou sítí þar

Pro tuto aproximaci krátkých þar, které jsou rĤznČ posunuty vlivem malého nežádoucího pootoþení nebo geometrickou deformací obrazu, byla vytvoĜena funkce

51


s názvem Hough_aprox. Jde totiž v podstatČ o aproximaci þar nalezených Houghovou transformací. Tato funkce je volána s parametrem CaraSvisla a hned po té s parametrem CaraVodorovna. Jsou tak vypoþteny aproximované souĜadnice pĤvodních þar, které se uloží pomocí návratové hodnoty z funkce Hough_aprox do polí CaraX a CaraY. PĜíklad použití funkce Hough_aprox: CaraX = Hough_aprox(CarySvisle, pocetX, img4, 'x');

CaraX

-

pole, do kterého se má uložit návratová hodnota, která pĜedstavuje pozici aproximovaných þar

CarySvisle pocetX

-

vstupní pole obsahující poþáteþní souĜadnice všech þar poþet aproximovaných þar v promČnné CaraX, je zároveĖ také návratovou hodnotou

img4

-

obrázek, do kterého se mají zakreslit aproximované pĜímky

'x'

-

udává, ve které ose se ve skuteþnosti právČ aproximuje, urþuje hlavnČ v jakém smČru se mají vykreslit aproximované þáry

PĜi popsaných pĜedchozích operacích však mĤže dojít k nežádoucím chybám. Pro jejich eliminaci byla vytvoĜena funkce Cary_selektovani, která funguje následujícím zpĤsobem. Funkce si pĜevezme jako parametr pole CaraX (CaraY), ve kterém jsou uloženy souĜadnice aproximovaných þar. Spoþítá se vzdálenost mezi nimi a uloží se do nového pole deltaX_Y (univerzální název pole, protože se funkce Cary_selektovani volá nejdĜíve se souĜadnicemi X a pozdČji se souĜadnicemi Y).

Z tČchto vzdáleností se vypoþítá prĤmČr (prum) , který však není pĜesným prĤmČrem vzdáleností dvou þar, je totiž ovlivnČn mezerami pĜíliš velkými nebo malými vlivem chybné aproximace. Obr. 41 je vidČt jeden z problémĤ, který þasto nastává. Mezi tĜetí a þtvrtou oblastí dochází k dČlení svislé þáry, která spadá þásteþnČ do tĜetí oblasti a þásteþnČ do

52


þtvrté. Je logické, že skuteþná pozice þáry je na hranici tČchto oblastí. Avšak algoritmus vytvoĜí dvČ aproximované þáry blízko sebe (v každé oblasti jednu). Tento pĜípad je detekován, pokud je hodnota vzdálenosti þar (deltaX_Y) menší než hodnota prĤmČru snížená o hysterezi. Hystereze je zvolena pČtina prĤmČru prum. Je-li uvedený pĜípad zjištČn, potom je zapotĜebí umístit novou þáru mezi tyto dvČ, které byly chybným vyhodnocením funkce Hough_aprox umístČny blízko sebe. Je tedy vypoþtena pozice mezi nimi, kam se pĜesune jedna z nich a druhá se odstraní. Další chyba funkce Hough_aprox mĤže spoþívat v tom, že není dostatek údajĤ (poþtu krátkých þar) nalezených Houghovou transformací pro hledání þar, a proto þára chybí v místČ, kde má být. To je dobĜe vidČt na obrázku Obr. 42, kde vznikly touto chybou prázdné proluky. To detekuje funkce Cary_selektovani tak, že najde hodnotu vzdálenosti mezi þarami vČtší, než je hodnota prĤmČru zvýšená o hysterezi, která je zvolena pČtina prĤmČru. V tom pĜípadČ se tato vzdálenost z pole deltaX_Y odstraní. Mohla by se nahradit hodnotou prĤmČru, ale protože prĤmČr v tuto chvíli není pĜesný (je zkreslený chybnČ aproximovanými pĜímkami, které se tímto právČ eliminují), není tak uþinČno. Po odstranČní této hodnoty (pĜíliš vzdálených pĜímek) z pole deltaX_Y a opravČ polohy pĜímek, které byly pĜíliš blízko, již obsahuje pole jen pravdivé vzdálenosti. Tyto odpovídají skuteþné vzdálenosti þar souĜadnicové sítČ QR kódu. Z nich se tedy vypoþítá pĜesný prĤmČr. Je-li prĤmČr desetinné þíslo, zaokrouhlí se nahoru, což bylo experimentálnČ zjištČno jako výhodnČjší. Pomocí této nové prĤmČrné hodnoty vzdálenosti pĜímek se provede doplnČní chybČjících pĜímek do celkového poþtu 22 pĜímek, tzn. 21 modulĤ QR kódu. Funkce Cary_selektovani tedy vrací výsledné souĜadnice sítČ QR kódu. Ta je vykreslena na obrázku Obr. 43 þervenou barvou.

53


Obr. 43 – Obrázek s vyznaþením souĜadnicové sítČ

Když je vypoþtena souĜadnicová síĢ, dopoþítá se stĜed každého oka této sítČ a uloží se do polí BodyX a BodyY. Vzniknou tak souĜadnice bodĤ, ve kterých budeme pozdČji zjišĢovat pĜítomnost þerného nebo bílého modulu QR kódu. Pro lepší orientaci a kontrolu dosavadních algoritmĤ jsou tyto body vyznaþeny na Obr. 43 modrým kĜížkem s využitím vytvoĜené funkce nakresli_krizek. PĜíklad použití funkce nakresli_krizek: nakresli_krizek(BodyX[x], BodyY[y], img5);

BodyX[x]

-

bod na ose x (roste na obrázku zleva doprava), ve kterém má být kĜížek

BodyY[y]

-

bod na ose y (roste na obrázku shora dolĤ), ve kterém má být kĜížek

img5

-

obrázek, do kterého se má zakreslit kĜížek

54


4.2.6 Algoritmus pro zpracování matice QR kódu Je-li vypoþtena pozice modulĤ QR kódu, mĤže se vytvoĜit matice logických 1 a logických 0. To se provede v cyklech pomocí funkce cvGet2D, která zjistí úroveĖ šedi (0-255) v daném bodČ obrázku. To je potom následnČ pĜevedeno na logické nuly a jedniþky tak, že þerná barva pĜedstavuje logickou 1. VytvoĜí se tak dvourozmČrné pole matice[21][21]. Na Obr. 44 je zobrazena tato matice po výpisu to konzolového okna.

Obr. 44 – Výpis do konz. okna Binární matice – pĜeþteno z obrázku

PĜi dekódování dat z QR kódu je zapotĜebí nejdĜíve pĜeþíst informaci o použité korekci chyb a použité masce. O typu použité masky je dĤležité vČdČt, aby mohla být z kódu odebrána a získala se tak matice vlastních dat. To se odeþte z matice v tČch místech, která byla popsána v kapitole 2.2.8. K tomu byla vytvoĜena funkce s názvem maskaAkorekcechyb. Tato funkce vyhledá v celé matici QR kódu jen ty moduly, které obsahují danou informaci. Ta je také pĜekrytá maskou, která je však již definována a je možné ji z tČch dat odebrat. Pak staþí jen odeþíst použitou masku pro celý zbytek QR kódu a korekci chyb. Za tČmito dvČma

55


informacemi se také nachází korekce chyb tČchto dvou informací, která není v této práci více pospáno tak jak bylo Ĝeþeno v kapitole 2.2.8. PĜíklad použití funkce maskaAkorekcechyb: maska_korekce = maskaAkorekcechyb (matice);

maska_korekce - návratová hodnota funkce, první prvek tohoto pole

obsahuje úroveĖ korekce chyb, druhý použitou masku matice

-

tato matice odeþtená z QR kódu je vstupem

ÚroveĖ použitého Reed-Solomonova kódování je pouze vypsána do konzolového okna a je z þísla pĜevedena na písmena, použitá k oznaþování této úrovnČ. Korekce chyb není více využíváno, tak jak bylo uvedeno v kapitole 2.2.6. Je-li známý typ použité masky. VytvoĜí se maska podle vzorce daného typu masky a uloží do matice maska. Je také zobrazena v konzolovém oknČ. Pak vypadá výpis tak, jako je na Obr. 45.

Obr. 45 - Výpis do konz. okna – Binární matice – maska, korekce chyb

56


Je-li známá matice odeþtená z QR kódu a matice obsahující masku, mohou se pomocí operace XOR mezi tČmito maticemi získat vlastní data. V této chvíli dojde ke zjednodušení tím, že by se správnČ mČla tímto zpĤsobem odebrat maska jen v místech vlastních dat a dat korekce chyb. Tudíž kotvící obrazec (soustĜedné þtverce), zamČĜovací znaþky a místo, kde je uložena informace o použité masce a korekci chyb, by nemČla být odebráním masky zmČnČna. Pro zjednodušení algoritmu, k této zmČnČ však dochází. Tento postup však není nijak chybný, a neztrácíme tak žádnou informaci. PĜíklad matice bez masky je na Obr. 46.

Obr. 46 - Výpis do konz. okna – Binární matice – matice bez masky

Než se zaþnou z matice vlastních dat odeþítat data, je nutné zjistit jaký typ dat je v QR kódu uložen. Tato informace se zjistí z prvních 4 bitĤ dat. Popisovaný algoritmus je omezen jen na alfanumerický datový typ, a to z dĤvodu velké složitosti a nepĜehlednosti pĜi zakomponování všech používaných typĤ. Následujících 9 bitĤ je vyhrazeno pro uložení poþtu znakĤ. To urþí, kam až sahají data, a kde pokraþují vyplĖující CW. S tČmito znalostmi je tedy možné zaþít odeþítat vlastní data z QR kódu. K tomu byla vytvoĜena funkce odecti_jen_data.

57


PĜíklad použití funkce odecti_jen_data: data = odecti_jen_data (kod_bezmasky);

data

-

návratová hodnota funkce, pole obsahující sekvenci logických nul a jedniþek v pĜesném poĜadí

kod_bezmasky -

tato matice vlastních dat je vstupem do funkce

Pak je tedy zapotĜebí dopoþítat z poþtu znakĤ, kam sahají data. Je také nutné zjistit jestli je poþet znakĤ sudý nebo lichý. Je-li sudý, potom jsou vždy dvojice znakĤ uložené v 11 bitovém prostoru, a to tak, že první znak je násoben þíslem 45 a druhý je k tomu pĜiþten. Je-li poþet lichý, potom jsou všechny znaky zakódovány do 11 bitových polí, jak bylo popsáno, ale poslední znak (lichý) je uložen do 6 bitĤ velkého prostoru a není násoben žádným þíslem. Jeho hodnota pĜímo odpovídá urþitému znaku. K rozlišení tČchto stavĤ slouží promČnné bit6 a bit11. S tČmi se potom volá funkce data_na_znaky, která provádí výše popsané operace k získání celoþíselných hodnot každého znaku. PĜíklad použití funkce data_na_znaky: znaky = data_na_znaky (data, bit11, bit6);

znaky

-

návratová hodnota funkce, pole obsahující celoþíselné hodnoty jednotlivých znakĤ

data

-

pole obsahující sekvenci logických nul a jedniþek v pĜesném poĜadí – zakódované znaky

bit6 a bit11 -

pomocné promČnné k dekódování (lichost / sudost)

Nyní už jen staþí pĜevést každý znak v celoþíselné podobČ na alfanumerický tvar podle tabulky v [5]. Nejedná se však o ASCII tabulku. Tuto tabulku využívá funkce vytvoĜená pro úþel tohoto pĜevodu. Jmenuje se vypsat_znak a zároveĖ také vypisuje znak do konzolového okna. Vizualizace potom mĤže odpovídat Obr. 47.

58


PĜíklad použití funkce vypsat_znak: vypsat_znak (znaky[i]);

znaky

-

pole obsahující celoþíselné hodnoty jednotlivých znakĤ

Obr. 47 - Výpis do konz. okna – Dekódované znaky

59


5.

ZHODNOCENÍ VÝSLEDKģ REALIZOVANÉHO ěEŠENÍ

Realizované Ĝešení bylo vyzkoušeno na testovacích snímcích. Zhodnocení je nutné rozdČlit do dvou kategorií. Jedna z nich je testování pĜi dodržených podmínkách pro dekódování a druhá je pĜi nedodržení tČchto podmínek. ZmínČné podmínky jsou: -

velikost vlastního QR kódu na snímku alespoĖ 400x400 pixelĤ

-

QR kód správnČ orientovaný, pootoþení maximálnČ 1-2°

-

nalevo a nahoĜe od QR kódu nemají být rušivé objekty (kap. 4.2.5)

-

v QR kódu nesmí být odraz svítidla, který by poškodil þitelnost

-

snímek nesmí být geometricky deformován

Testování bylo provádČno na 6 snímcích vyhovujících podmínkám a 6 snímcích nevyhovujících podmínkám tak, jak ukazuje Tab. 8. Mezi snímky, u kterých probČhlo dekódování korektnČ, byly i ty, které mČly napĜíklad mírnou deformaci zpĤsobenou snímáním zblízka þi nepĜesnČ kolmo, byl zde snímek s rozlišením pod uvedenou hranicí 400x400 pixelĤ a na jednom snímku se také projevovalo kolísání jasu žárovkového svítidla.

Dekódování probČhlo (ks)

Dekódování neprobČhlo (ks)

ÚspČšnost (%)

Snímky vyhovující podmínkám

6

0

100

Snímky nevyhovující podmínkám

1

5

16

Tab. 8 – Zhodnocení testování programu

60


6.

ZÁVċR

Seznámil jsem se s nejznámČjšími þárovými kódy používanými v logistice, obchodech a prĤmyslu, jejichž pĜehled je uveden v kapitole 2.1. Z tČchto kódĤ jsem si vybral QR kód, kterému jsem se vČnoval nejvíce. Nastudoval jsem jeho složení, dĤležité prvky a jeho princip. QR kód, je kód o mnoho složitČjší než napĜíklad EAN kód. Používá spoustu prvkĤ, které urychlují a usnadĖují þtení kódu, napĜíklad oproti Datametrix kódu. Univerzální popis QR kódu je rozsáhlý dokument (více jak 100 stran) a znaþnČ by zvyšoval objem této práce, a proto jsem se snažil popsat kód tak, aby byl popis struþný, názorný a zároveĖ dostateþný. Pro zjednodušení jsem pĜevážnČ používal jen QR kód velikosti 1 (verze 1). To znamená, že je 21 x 21 modulĤ velký. Na odlišnosti kódu jiných velikostí upozorĖuji pĜímo v daných kapitolách. VytvoĜil jsem také vzorový pĜíklad pĜevodu dat do QR kódu krok po kroku. Ukázal jsem postup tak, aby byl srozumitelný a poukazoval i na odlišnosti postupu v jiných pĜípadech. PĜíklad byl doplnČn obrázky, které charakterizují postupnou tvorbu kódu. Výsledek byl porovnán s kódem vytvoĜeným pomocí online generátoru (napĜ. pomocí: [15]) a byl totožný. MírnČ odlišnou þástí práce bylo poĜízení databáze snímkĤ (kapitola 3), ta se skládá jednak z QR kódĤ vytvoĜenými online generátory, ale hlavnČ fotoaparáty rĤzných typĤ. Kódy byly vytištČny na matný klasický a lesklý fotografický papír. U lesklého papíru jsem pozoroval odrazy použitého pĜisvČtlení, které poškozovaly kvalitu snímku. Záleželo na pozici svČtla a snímacího zaĜízení, kdy bylo zapotĜebí najít nejvhodnČjší scénu, která odrazy eliminuje. Jako nejlepší považuji scénu, kdy snímací zaĜízení je pĜímo nad kódem a svČtlo je umístČno mimo pĤdorys snímku. Dochází však k nerovnomČrnému osvČtlení kódu, což by mohlo þinit problémy pĜi jeho zpracování. Tato nevýhoda by se však dala snadno vyĜešit pĜidáním dalšího zdroje svČtla na protČjší stranu opČt mimo pĤdorys snímku. ZdrojĤ by mohlo být použito i více tak, že by obklopovaly objektiv snímacího zaĜízení.

61


V další kapitole (4) jsem uvedl popis navrženého Ĝešení. Tedy algoritmu, který zpracovává QR kód. Jeho vstupem je snímek poĜízený snímacím zaĜízením a výstupem jsou data, která byla vložena do kódu pĜi jeho tvorbČ. Tento algoritmus má nČkolik omezení. PĜedpokládá obraz QR kódu, který na své levé a horní stranČ má jen þistČ bílou oblast. Kód by také nemČl být pootoþen o více jak 1° - 2°. Velikost sejmutého QR kódu na snímku by mČla být alespoĖ 400 x 400 pixelĤ a obraz by nemČl být geometricky deformován. Tato omezení by se dala eliminovat, bylo by však zapotĜebí více þasu (napĜíklad semestr – jako u diplomové práce) k úpravČ nČkterých modulĤ algoritmu. QR kódy pĜinášejí obrovské množství variací velikostí, typĤ dat a dalších podrobností. Proto byl pro zachování pĜehlednosti zdrojového kódu algoritmu, omezen datový typ jen na alfanumerický. PĜi splnČní tČchto podmínek je algoritmus schopen dekódovat data uložená v QR kódu s pĜesností 100%, tak jak bylo uvedeno v kapitole 5.

62


7.

SEZNAM POUŽITÝCH ZDROJģ

[1]

Šonka, M.; Hlaváþ, V.: Poþítaþové vidČní, Grada, Praha 1992, ISBN 8085424-67-3

[2]

Žára, J.; Beneš, B.; Felkel, P.: Moderní poþítaþová grafika, Computer press, 1998, ISBN 80-7226-049-9

[3]

Hlaváþ, V.; Sedláþek, M.: Zpracování signálu a obrazu, skriptum ýVUT 2001

[4]

BRADSKI, Gary; KAEHLER, Adrian: Learning OpenCV: Computer Vision with the OpenCV Library, O’REILLY, 2008, ISBN 978-0-596-51613-0

[5]

ISO/IEC 18004:2006. Information technology - Automatic identification and data capture techniques - QR Code 2005 bar code symbology specification [draft]

[6]

MANDAU, Markus; KLEGA, Vratislav. QR Kódy: Sejmout a na web. CHIP: Magazín informaþních technologií, kvČten 2008, þ. 5, s. 32–33.

[7]

Kodys: ýárový kód [online]. Cit. 26.11.2009. Dostupné z WWW:

[8]

Kodys: ýárový kód: UCC/EAN128 [online]. Cit. 29.11.2009. Dostupné z WWW:

[9]

Kodys: ýárový kód: PDF 417 [online]. Cit. 29.11.2009. Dostupné z WWW:

[10]

Kodys: ýárový kód: CODE 39 [online]. Cit. 29.11.2009. Dostupné z WWW:

[11]

BELOS Trade s.r.o.: ýárový kód [online]. Cit. 26.11.2009. Dostupné z WWW:

[12]

Denso wave: QR code standardization [online]. Cit. 26.11.2009. Dostupné z WWW:

[13]

Wikipedie: ýárový kód [online]. Cit. 28.11.2009. Dostupné z WWW:

[14]

Barcode Library: Barcode Industrial 2 of 5 [online]. Cit. 26.11.2009. Dostupné z WWW:

[15]

KAYWA: Generátor QR kódĤ [online]. Cit. 28.11.2009. Dostupné z WWW:

[16]

Quido magazín: Objevy - ýárový kód [online]. Cit. 28.11.2009. Dostupné z WWW:

63


8.

SEZNAM POUŽITÝCH ZKRATEK A SYMBOLģ

LSB - Least Significant Bit - bit s nejnižší váhou MSB - Most Significant Bit - bit s nejvyšší váhou CW - Codeword - v pĜekladu kódové slovo, je to 8 bitová binární þást kódu obsahující data

Finder pattern = kotvící obrazec - slouží v rychlejšímu lokalizování QR kódu ve scénČ Alignment pattern = zarovnávací obrazec - pomáhá k softwarové rekonstrukci deformovaného kódu Timing patterns = zamČĜovací obrazec - urþují hustotu souĜadnicové sítČ QR kódu Verze - verzí u QR kódu je myšlena jeho velikost, oznaþení verze a popisy všech verzí jsou pĜevzaty z [5] Bod (=modul) - bodem je myšlen jeden þtvereþek (bílý nebo þerný) v QR symbolu, je to nejmenší popsatelná þást symbolu Quiet zone - je oblast kolem QR kódu, která nemá obsahovat žádný potisk

64


9.

SEZNAM PěÍLOH

PĜíloha 1 - CD s elektronickou verzí této práce a zdrojovým kódem

65

VYSOKÉ U ENÍ TECHNICKÉ V BRN BRNO UNIVERSITY OF TECHNOLOGY

Recommend Documents