Rozpoznávaní šachových figurek v partii

Mendelova univerzita v Brně Provozně ekonomická fakulta

Rozpoznávaní šachových figurek v partii Bakalářská práce

Vedoucí práce: Ing. Jan Kolomazník

Lukáš Sekanina

Brno 2016

Tímto bych rád pod koval Ing. Janu Kolomazníkovi za vst ícný p ístup, ochotu a poskytnutí cenných informací p i vedení této práce. Velké pod kování pat í také mé rodin , mé p ítelkyni, spolužákům, p átelům a známým.

Čestné prohlášení Prohlašuji, že jsem práci Rozpoznávání šachových figurek v partii vypracoval samostatn a veškeré použité prameny a informace uvádím v seznamu použité literatury. Souhlasím, aby moje práce byla zve ejn na v souladu s § 47b zákona č. 111/1998 Sb., o vysokých školách ve zn ní pozd jších p edpisů a v souladu s platnou Směrnicí o zveřejňování vysokoškolských závěrečných prací. Jsem si v dom, že se na moji práci vztahuje zákon č. 121/2000 Sb., autorský zákon, a že Mendelova univerzita v Brn má právo na uzav ení licenční smlouvy a užití této práce jako školního díla podle § 60 odst. 1 autorského zákona. Dále se zavazuji, že p ed sepsáním licenční smlouvy o využití díla jinou osobou Ěsubjektemě si vyžádám písemné stanovisko univerzity, že p edm tná licenční smlouva není v rozporu s oprávn nými zájmy univerzity, a zavazuji se uhradit p ípadný p ísp vek na úhradu nákladů spojených se vznikem díla, a to až do jejich skutečné výše.

V Brn dne 15. kv tna 2016 …………………………………………… Lukáš Sekanina

Abstract SEKANINA, Lukáš. Recognition of chess pieces in game. Bachelor thesis. Brno, 2016. Thesis supervisor Ing. Jan Kolomazník. This thesis describes the design, implementation and testing program for the recognition chess game. The thesis includes the unsuccessful attempts at implementation. Implementation of the program fails to recognize figures using Matlab. The result is a program that detects the movement of pieces on the chess board. Keywords Bachelor thesis, computer vision, chess game, matlab, image processing.

Abstrakt SEKANINA, Lukáš. Rozpoznávání šachových figurek v partii. Bakalá ská práce. Brno, 2016. Vedoucí práce Ing. Jan Kolomazník. Tato bakalá ská práce se zabývá návrhem, implementací a testováním programu na rozpoznávání šachové partie. Součástí práce jsou i nezda ilé pokusy o implementaci. Implementace programu na rozpoznávání figurek bude realizována pomocí nástroje Matlab. Výsledkem práce je program, který rozpozná pohyb figurek na šachovnici. Klíčová slova Bakalá ská práce, počítačové vid ní, šachy, matlab, zpracování obrazu.

Obsah

9

Obsah 1

Úvod a cíl práce ................................................................... 13 1.1

Úvod .................................................................................................. 13

1.2

Cíl ...................................................................................................... 13 Současný stav ...................................................................... 14

2 2.1

Počítačové vid ní .............................................................................. 14 2.1.1 Nižší úroveň ................................................................................. 14 2.1.2 Vyšší úroveň ................................................................................ 14

2.2

Preprocesní zpracování..................................................................... 15 2.2.1 Prahování ..................................................................................... 15 2.2.2 Normalizace ................................................................................ 15

2.3

Segmentace obrazu ........................................................................... 16 2.3.1 Segmentace na základ detekce hran .......................................... 16 2.3.2 Segmentace narůstáním oblastí .................................................. 16 2.3.3 Segmentace prahováním............................................................. 17

2.4

Houghova transformace ................................................................... 17 2.4.1 Detekce p ímek ............................................................................ 17 2.4.2 Detekce kružnic ........................................................................... 18

2.5

Detekce hran ..................................................................................... 18 2.5.1 Cannyho detektor hran ................................................................ 18 2.5.2 Sobelův detektor hran ................................................................. 18

2.6

Harrisův detektor rohů ..................................................................... 19

2.7

Jas ..................................................................................................... 19

2.8

Programovací jazyk Matlab ............................................................. 20 2.8.1 Historie ....................................................................................... 20 2.8.2 Vlastnosti Matlabu ...................................................................... 21

3

Metodika práce .................................................................... 23 3.1

Metodika hardwarového za ízení .................................................... 23

3.2

Metodika softwaru ........................................................................... 23

4

Vlastní práce........................................................................ 25 4.1

Získávání vstupních dat ....................................................................25

4.2

Šachovnice a figurky .........................................................................25

Obsah

10

4.3

Intenzita jasu ................................................................................... 26 4.3.1 Stín .............................................................................................. 26 4.3.2 Blesk fotoaparátu ....................................................................... 26

4.4

Hledání šachovnice pomocí Houghovy transformace ..................... 27

4.5

Hledání rohů .................................................................................... 28

4.6

Hledání šachovnice pomocí barvy ................................................... 28

4.7

Detekce hran .................................................................................... 30

4.8

Detekce figurek pomocí Houghovy transformace ............................ 31

4.9

Detekce figurek pomocí barvy ..........................................................33

4.10

Pohyb figurek ................................................................................... 34

4.11

Výstup programu ..............................................................................35

4.12

Testování .......................................................................................... 36

4.13

Zhodnocení vlastního ešení............................................................. 37

5

Závěr .................................................................................. 38

6

Literatura ............................................................................39

Přílohy 41 A

Konfigurace hardwaru .........................................................42

B

Ukázka hledaných figurek ....................................................42

11

Seznam obrázků

Seznam obrázků

12

Obr. 1: Stín na šachovnici ............................................................................. 26 Obr. 2: Houghova transformace p ímky ....................................................... 27 Obr. 3: Nalezení šachovnice pomocí Harrise ............................................... 28 Obr. 4: Nalezení šachovnice pomocí barvy .................................................. 30 Obr. 5: Výsledek detekce hran ....................................................................... 31 Obr. 6: Šachovnice s barevnými figurami .................................................... 32 Obr. 7: Detekce figurek pomocí barvy .......................................................... 34 Obr. 8: Zaznamenání tahu ............................................................................ 36 Obr. 9: Textový výpis partie .......................................................................... 36 Obr. 10 Ukázka šachových figurek ................................................................ 42

Úvod a cíl práce

13

1 Úvod a cíl práce 1.1 Úvod Rozpoznávání objektů z fotografií je zahrnuto v oboru počítačové vid ní, což je odv tví výpočetní techniky. Tyto techniky jsou dnes zabudovány v nejrůzn jších softwarech a za ízeních na získávání informací zachycených v obraze. Počítačové vid ní je pom rn nový obor ve výpočetní technice. V začátcích bylo velmi obtížné získat informace z obrázků a fotek. Hardwarové komponenty nebyly tak výkonné a software nedokázal vypočítat obtížné výpočty nutné pro zachycení informací. Obor počítačového vid ní je v poslední dob na vzestupu. K tomu napomáhají jak levn jší a stále dokonalejší kamerové systémy, tak i snadná dostupnost pot ebného výpočetního výkonu. Zároveň je nutné zmínit také stále snadn jší dostupnost různých knihoven algoritmů a materiálů, zam ujících se práv na zpracování obrazu. V současné dob výkonných strojů můžeme pomocí nejrůzn jších algoritmů detekovat skoro vše. Vysoká operační pam ť a velká kapacita úložišt nám poskytla obrovské využití tohoto oboru. Typické využití tohoto softwaru je detekce obličejů v digitálních fotoaparátech. Další využití je nap íklad detekce a určení čísel, písmen a dalších objektů na fotografiích. Počítačové vid ní můžete nalézt rovn ž v automobilovém průmyslu. Jako p íklad lze uvést automatické couvání, detekce značek kolem cesty nebo určení vodorovného dopravního značení.

1.2 Cíl Cílem práce je navrhnout, naimplementovat a otestovat program na určení pozice figurek na šachovnici. Pomocí vývojového nástroje Matlab bude naimplementován program, který z obrázků šachovnice najde všechny figurky na šachové partii a určí jejich charakter a pozici. Následn pozice zapíše do výstupního souboru, který se dále dá použít. Otestování programu bude provedeno na nových šachových partiích. Etapy práce pro spln ní cíle:     

Nastudujte problematiku analýzy obrazu pomocí nástroje Matlab. Navrhn te algoritmus rozpoznávání šachových figur na šachovnici. Implementujte navážený algoritmus v nástroji Matlab. Otestujte implementovaný algoritmus na reálných šachových partiích. Zhodnoťte dosažené výsledky a navrhn te možná vylepšení.

Současný stav

14

2 Současný stav 2.1 Počítačové vidění Hlaváč Ě1řř2ě definuje počítačové vid ní jako „disciplínu, která se snaží technickými prost edky alespoň částečn napodobit lidské vid ní. Oči jsou pro člov ka zdrojem p evážné v tšiny informací o okolním sv t . P i vyhodnocení vizuální informace hraje obrovskou roli inteligence člov ka, která umožňuje reprezentovat dlouho nabývané znalosti a zkušenosti o okolním sv t .“ Úlohou počítačového vid ní je napodobit pomocí technických prost edků schopnosti lidského oka. Jde nejen o samotnou schopnost zpracování obrazu, ale také o rozpoznání toho, co obraz p edstavuje. V tom hraje podstatnou roli inteligence člov ka a jeho p edchozí zkušenosti. Počítačové vid ní lze rozd lit do dvou oblastí: rozpoznávání 2D obrazu Ěnap . textu a znaků na papí eě a rozpoznávání 3D obrazu Ěnap . rozpoznávání součástky pro její následné uchopení). (Volná, 2013) Z definic vyplývá, že počítačové vid ní je softwarová náhražka lidského oka. Tím pádem může počítač rozpoznat objekty a situace na zachyceném obraze. Algoritmy k tomu určené ješt nedosahují takových kvalit, aby mohly zcela nahradit lidské oko, avšak mohou se mu vyrovnat v podstatné části. Rozd lení počítačového vid ní je provedeno na dv části, na nižší a vyšší úroveň. Úrovn jsou dané podle logického účinku jednotlivých algoritmů. ĚHlaváč, 1992)

2.1.1 Nižší úroveň První úroveň, která se použije p i jakémkoliv zpracovávání obrazu, je nižší. Zabývá se analýzou vstupních dvourozm rných dat číselného charakteru a hledá užitečné informace pro vyšší úroveň, která je pak využívá k následnému zjišt ní požadovaných informací. Nižší úroveň využívá algoritmy nap íklad na odstran ní šumu a zkreslení snímku vytvo eného pomocí digitalizace. Snímání obrazů a jejich p esun často ovlivní jejich kvalitu. Tyto techniky se pak nazývají zpracování. Toto může pomoci ovlivnit snímek p i dalším zpracování, nap íklad p i detekci hran. Další zpracování se nazývá segmentace obrazu. Ta nám pomůže najít objekty v obraze. Objekty jsou v ci na snímku, které nás zajímají a kvůli kterým d láme zpracovávání. P i segmentaci se hodn využívá interpolace obrazu. ĚHlaváč, 1992)

2.1.2 Vyšší úroveň Jádrem pokročilejších postupů jsou znalostní systémy a techniky um lé inteligence. Ty se využívají k porozum ní obsahu jednotlivých obrazů. Jedná se o porozum ní interpretaci obrazových dat, o kterých se p edem nic nep edpokládá.

Současný stav

15

V triviálním p ípad by mohlo jít nap íklad o rozd lení objektu do skupiny kruhů nebo čtverců. ĚHlaváč, 1992)

2.2 Preprocesní zpracování Počáteční zpracování je důležitým nástrojem pro hledání objektů v obraze. Vstupní data musíme na počátku zpracování n jakým způsobem ošet it. Tomu se íká preprocesní zpracování Ěimage preprocessingě. Tento úkon nám má zjednodušit nakládání se vstupními daty.

2.2.1 Prahování Prahování Ěthresholdingě je nejjednodušší metodou segmentace obrazu. Na základ jasové nebo barevné složky transformuje vstupní obraz na dvoubarevný obraz. Matematicky lze prahování vyjád it jako funkci. Na základ hodnoty prahu tedy algoritmus porovná všechny pixely vstupního obrazu a nahradí je logickou hodnotou 0 nebo 1. Tím dosáhneme jednak transformace barevné složky obrazu na obraz černobílý a také odd lení pop edí od pozadí. Nejjednodušší metodou určování prahu je procentní prahování. Tuto metodu můžeme využít za p edpokladu, že známe pom r ploch objektu a pozadí. Na základ této znalosti určíme hodnotu prahu tak, aby práv požadované procento plochy m lo nižší, resp. vyšší hodnotu než práh. ĚŽelezný, 2006)

2.2.2 Normalizace Další metodou neprocesního zpracování je normalizace. Tato metoda využívá funkce jako zm na m ítka obrazu, otočení obrazu, zm na šikmosti atd.  Otočení obrazu Jedná se o transformaci obrazu, p i které otočíme obraz kolem daného bodu o určitý úhel. P i zpracování diskrétního obrazu se mohou objevit v transformovaném obraze efekty, které se nevyskytují v původním obraze. Toto je způsobeno nep esným p epočtem sou adnic p i transformaci rastru obrazu a tento jev nazýváme alias. ĚHlaváč, 1992)  Zm na m ítka Zm na m ítka je operace, kdy se nám zm ní velikost objektu ve sm ru osy x nebo osy y.

Současný stav

16

2.3 Segmentace obrazu Pojem segmentace obrazu se vnímá jako soubor procesů, p i nichž dochází k analýze obsahu zpracovaných dat obrazu. Jedním z nejdůležit jších faktorů pro správnou segmentaci je charakter vstupních dat. ĚHlaváč, 2008) Cílem segmentace je rozd lení obrazu na části, které mají souvislost se skutečností. Pro tuto množinu oblastí je nezbytná jejich vzájemná disjunktnost. Podle míry shody mezi nalezenými segmenty a skutečnými objekty se segmentace rozd luje na kompletní a částečnou. U částečné segmentace je míra shody menší než u segmentace kompletní. (Sochor, 1998) U kompletní segmentace je nutné využít vyšší úroveň zpracování a dostatečné množství znalostí o ešeném problému. Můžeme však nalézt i úlohy, které se obejdou bez nutnosti použití této vyšší úrovn . S výhodou se pak používá nižší úroveň zpracování. P íkladem pro použití této nižší úrovn může být situace, kdy jsou zkoumané objekty na pozadí s konstantním jasem. (Parker, 2010) Segmentace se dá rozd lit na t i základní typy:  Segmentace na základ detekce hran.  Segmentace narůstáním oblastí.  Segmentace prahováním.

2.3.1 Segmentace na základě detekce hran Hrana je místo obrazu, kde se náhle m ní jeho jasová funkce. Nalezené hrany jsou spojeny do et zců, ze kterých získáváme informaci o hranicích jednotlivých obrazových objektů. V tšina metod detekce hran pracuje s derivací jasové funkce, jelikož gradient nám udává zm nu tvaru funkce. Detektory hran tedy mohou pracovat s první derivací funkce. Ta nabývá svého maxima v míst hrany. Nejjednodušším p ípadem je stav, kdy derivace určíme pro jednotlivé sloupce pro každý pixel shora dolů. Nevýhodou je zde veliká náchylnost na šum obrazu. Pon kud spolehliv jší jsou metody založené na práci s druhou derivací. Využívá se detekce průchodu nulou, jelikož druhá derivace nabývá v míst hrany nulovou hodnotu. Nevýhodou metod založených na druhé derivaci je značné vyhlazení obrazu, což může znamenat ztrátu ostrých rohů a náchylnost k vytvá ení uzav ených smyček hran. (Kratochvílová, 2007)

2.3.2 Segmentace narůstáním oblastí Uplatňuje se v p ípadech, kdy je obraz výrazn zašum n a není možné využít detekci hran. Základem je rozd lení obrazu na segmenty dle zvoleného parametru homogenity, jehož kritérium je založeno na jasových vlastnostech nebo komplexn jších způsobech popisu obrazu. ĚŽelezný, 2006)

Současný stav

17

2.3.3 Segmentace prahováním Segmentace prahováním pat í k nejstarším známým postupům. Základní princip této metody vychází ze skutečnosti, že objekty v obraze lze charakterizovat pomocí pohltivosti nebo odrazivosti jejich povrchu. Dá se proto využít určité jasové konstanty, tzv. prahu, a odd lit tak objekty a pozadí. K hlavním výhodám této metody pat í malé výpočetní a hardwarové nároky a zejména možnost zpracování obrazu v reálném čase. Segmentace prahováním pat í mezi nejčast ji používané metody. ĚHlaváč, 2005)

2.4 Houghova transformace Houghova transformace byla popsána Paulem Houghem v roce 1962 a dále rozší ena o 10 let pozd ji Richardem Dudou a Peterem Hartem. Metoda byla sepsána k vyhledávání jednotlivých struktur v obraze. Houghova transformace využívá parametrický popis struktur, proto se používá na vyhledávání pozic geometrických tvarů. Nejčast ji se touto metodou vyhledává p ímka, kružnice a další jednoduché tvary, u kterých je známý jejich parametrický popis. Pro Houghovu transformaci jsou vstupní data binární obraz zpracovaný detektorem hran. Binární obraz se zpracovanými hranami zajišťuje snížení výpočetní náročnosti celého procesu. Výstupními daty této metody je parametrický prostor obsahující informace o pravd podobnosti výskytu hledaných tvarů. Tento prostor je také nazýván Houghův prostor. Jak prostor bude velký, záleží na počtu neznámých v rovnici hledaného útvaru. (Duda, 1972) Výhoda Houghovy transformace spočívá v jeho robustnosti vůči vstupním datům, která nebývají často kvalitní. Vyhledá pom rn úsp šn pozice struktur, které jsou v obraze znehodnoceny, nap . silným šumem, nepravidelnostmi nebo porušením. Nevýhodou metody je časová náročnost u složit jších objektů. Další nevýhodou může být nep esné identifikování útvarů, které není ve vstupních datech dostatečn viditelné. ĚŠpan l, 2005ě

2.4.1 Detekce přímek Z Houghovy transformace vyplývá, že hledanou p ímku musíme vyjád it v parametrickém prostoru. Nejčast jší vyjád ení pro p ímku v kartézské soustav je sm rnicový vztah: =

+ ,

kde m je sm rnice p ímky a n úsek na ose y. V p ípad výskytu vertikální p ímky by parametr m nabýval nekonečn mnoho hodnot. Proto se v praxi toto vyjád ení nepoužívá a nahrazuje se normálovým tvarem p ímky, který je definován jako: =

�+

� �,

Současný stav

18

kde r je vzdálenost bodu (x, yě od počátku sou adnicového systému a φ je úhel mezi normálou a osou x.

2.4.2Detekce kružnic Houghova metoda na hledání kružnic je podobná jako pro p ímky. Parametrické vyjád ení pro kružnici je: 2

=

−

2

+

−

2

,

kde r je polom r kružnice, body a, b jsou sou adnice st edu a x, y jsou body v prostoru. Detekce kružnic využívá t i parametry, tím je výpočet náročn jší a časov delší než u detekce p ímek.

2.5 Detekce hran Detekce hran je součástí zpracování obrazu. Hrana v obraze znamená oblast, ve které je n jaká zm na intenzity. Tato důležitá činnost nám pomáhá odhalovat různé objekty v obraze. V současnosti existuje n kolik detektorů hran, které využívají první a druhou derivaci obrazu podle x a podle y. Detektory na základ první derivace jsou Cannyho, Sobelův a Prewittův detektor. Na základ druhé derivace to je detektor Marr-Hildreth1. Další detektor je založený na lokální aproximaci obrazové funkce parametrickým modelem. Tento detektor se nazývá Haralick2.

2.5.1 Cannyho detektor hran Tento detektor hran je v současnosti nejvyužívan jší. Je to výsledek hledání ideálního detektoru. Jaké vlastnosti by m l mít ideální detektor, sepsal John F. Canny v 80. letech. (Canny, 1983). Jde o tyto vlastnosti:  Dobrá detekce - algoritmus by m l označit skutečné hrany v obraze, jak je to možné, a nesmí detekovat falešné hrany.  Dobré lokalizace - označené hrany by m ly být co nejblíže k hran v reálném obrazu.  Minimální odezva - hrany v obrazu by m ly být označeny pouze jednou a tam, kde je to možné, by obrazový šum nem l vytvo it falešné hrany.

2.5.2 Sobelův detektor hran Detektor založený na Sobelovu operátoru tvo í dv matice. Vlastní operátor jsou dv matice 3x3, které jsou zpracovávány pomocí konvoluce s počátečním obrázkem. Jedná se o tyto matice: Marr-Hildreth algoritmus je metoda detekce hran v digitálním obraze, kterou vytvo ili David Marr a Ellen Hildreth. 2 Detektor pojmenovaný po Robertu Haralick.

1

Současný stav

19

− − − − + � = [− ] ∗ �, + ] ∗ �; � = [ − + + + + Kde Gx je matice pro aproximaci derivace v ose x Ěsm r zprava dolevaě, Gy matice pro aproximaci derivace v ose y Ěsm r shora dolůě, a A je matice původního obrázku. Pro každý bod obrázků můžeme vypočítat gradient podle vztahu: Φ=

� �

Hodnoty tohoto gradientu v jednotlivých bodech nám posléze udávají možnost výskytu hrany; čím je hodnota v tší, tím je p echod ost ejší a opačn . Pro p ípadné citliv jší nastavení je nutné nastavit jiné hodnoty v maticích Sobelova operátoru, které tak budou zkoumat v tší úhel gradientu. Obecn je tento detektor citliv jší na šumy a ruchy v obrázku, které může způsobit za ízení digitalizující obraz (scanner, digitální fotoaparátě. ĚHlaváč, 2008)

2.6 Harrisův detektor rohů Jeden z nejčast ji používaných detektorů rohů navrhl Chris Harris a Mike Stephens v roce 1řŘŘ. Odvodili ho ze staršího Moravcova detektoru. Pro tento postup je kladem nízká výpočetní náročnost a odolnost proti šumu. Detektor pracuje s posunem snímku ve všech sm rech 2D prostoru a počítá zm nu gradienty ve všech bodech obrazu. U tohoto detektoru počítáme v každém bod obrazu matici: �=[

�2 � �

� � ] �2

Významnost bodu určíme z vlastních čísel po výpočtu matice, z nichž může vyplynout, že bod není významný, bod je hrana nebo je v bodu nalezen roh. Výpočet vlastních čísel je pom rn složitý. Proto navrhli funkci pro zjednodušení výpočtu vlastních čísel s volitelným parametrem, který ovlivňuje citlivost detektoru.

2.7 Jas Pihan (2006) ve svém elektronickém článku uvádí, že z RGB obrazu je snadno možné vyrobit černobílou fotografii. Stačí p evést všechny barvy na stupn šedé, p ičemž šedé Ěbarevn neutrálníě jsou ty barvy, které mají všechny t i RGB složky stejné. Nabízí se tak jednoduchá metoda: Jas (nová hodnota R, G i B) = ( R+B+G ) / 3 = 1/3*R+1/3*G +1/3*B Tím se každému pixelu fotografie p i adil jeho absolutní jas neboli se zprům rovaly barevné složky, a tak je pro každý pixel jen jedno číslo v rozsahu

Současný stav

20

0-255 označující jeho absolutní jas. Lidské oko však není stejn citlivé na všechny barvy. Na modrou je mnohem mén citlivé než nap . na zelenou nebo žlutou. Souvisí to s barvou sv tla z našeho slunce a „konstrukcí“ sítnice. Proto absolutní jas nemá p íliš velký smysl Ěoko to prost vidí jinakě, a proto se často používá tzv. subjektivní jas, který je definován jako: Subjektivní jas = 0.3*R + 0.59*G + 0.11*B

2.8 Programovací jazyk Matlab Za nástroj, ve kterém celý program bude implementován, je zvolen Matlab. Matlab je interaktivní programové prost edí a skriptovací jazyk čtvrté generace. Toto prost edí se využívá pro v decké a výzkumné účely. Hlavními oblastmi využití jsou technické obory a ekonomie. Matlab dokáže počítat s maticemi, vytvá et 2D a 3D grafy, umožňuje počítačovou analýzu a prezentaci dat, vytvá ení uživatelského rozhraní a mnoho dalších v cí. Matlab je nástroj jak pro pohodlnou interaktivní práci, tak pro vývoj širokého spektra aplikací. Výpočetní systém Matlab se b hem uplynulých let stal celosv tovým standardem v oblasti technických výpočtů a simulací ve sfé e v dy, výzkumu, průmyslu i v oblasti vzd lávání. Matlab poskytuje svým uživatelům nejen mocné grafické a výpočetní nástroje, ale i rozsáhlé specializované knihovny funkcí spolu s výkonným programovacím jazykem čtvrté generace. Knihovny jsou svým rozsahem využitelné prakticky ve všech oblastech lidské činnosti. Díky své architektu e je Matlab určen zejména t m, kte í pot ebují ešit početn náročné úlohy a p itom necht jí nebo nemají čas zkoumat matematickou podstatu problémů. Více než milion uživatelů po celém sv t využívá možnosti jazyka Matlabu, který je mnohem jednodušší než nap íklad Fortran nebo C a který skýtá obrovský potenciál produktivity a tvo ivosti. Za nejsiln jší stránku Matlabu je považováno mimo ádn rychlé výpočetní jádro s optimálními algoritmy, které jsou prov eny léty provozu na špičkových pracovištích po celém sv t . Matlab byl implementován na všech významných platformách ĚWindows, Linux, Solaris, Mac). (Matlab, 2014)

2.8.1 Historie Autorem Matlabu je Cleve Moler, který vytvo il Matlab pro své studenty. V roce 1řŘ4 společn Cleve Moler, Jack Little a Steve Bergert založili firmu MathWorks a Matlab nabídli trhu. Matlab byl původn vyvinutý pro p ístup k matematickým knihovnám (EISPACK, LINPACK). Název vznikl z anglických slov matrix laboratory, voln p eloženo „maticové studio“. Nejd íve existovaly verze pouze pro operační systémy typu UNIX, první verze pro Windows byla uvedena na trh až v roce 1řř4.

Současný stav

21

Zajímavé je, že firma The MathWorks Inc., která je vlastníkem chrán né značky Matlab, až do pom rn nedávné doby Ěp ibližn do roku 2000ě nepovažovala výkon osobních počítačů za dostačující pro profesionální práci s Matlabem. Proto také kopírování Matlabu bylo chrán no pouze na počítačích s unixem, kde byla instalace vázána na sériové číslo procesoru. První verze Ěpro PC XTě vznikla kolem roku 1řŘ5. Jako v tšina programů té doby se potýkala s nedostatkem pam ti, což omezovalo hlavn nejv tší možnou velikost matic, se kterou bylo možno provád t výpočty. Další verze byla určena speciáln pro počítač PC AT, kde byla velikost matic omezena 16 MB Ěmaximální velikost pam tiě. Virtuální pam ť začal Matlab používat s nástupem počítačů s procesorem Ř03Ř6, výpočty ale byly stále velmi pomalé. Pro ilustraci výpočet inverze matice 1000x1000 Ěmatice samotná vyžadovala pouze pro uložení Ř MB fyzické pam tiě trval n kolik minut. V roce 1řř4 byla, jak již bylo ečeno, na trh uvedena verze pro Windows, což s sebou p ineslo velkou výhodu v podob v tších možností grafiky, na druhou stranu ale nevýhodu, protože výpočty byly pomalejší. Čas procesoru byl totiž z velké části v nován pot ebám Windows. ĚDušek, 2005)

2.8.2

Vlastnosti Matlabu

Matlab je určený pro v deckotechnické výpočty, simulace a paralelní výpočty3, dále také vizualizace, výpočty a programování uživatelsky ovladatelných prost edí. Problémy a ešení jsou vyjád eny nejčast ji pomocí matematických vztahů. Typické oblasti využití Matlabu:      

Inženýrské výpočty. Tvorba algoritmů. Modelování a simulace. Analýza dat. Tvorba aplikací Ěvčetn GUI). V decká a inženýrská grafika.

Všechny objekty v Matlabu jsou vyjád eny jako matice, což mohou být čísla, prom nné, ale i obrázky. Otev ená architektura Matlabu vedla ke vzniku knihoven funkcí, nazývaných toolboxy, které rozši ují použití programu v p íslušných v dních a technických oborech. Tyto knihovny jsou navržené v jazyce Matlabu a nabízejí p edzpracované specializované funkce, které je možno rozši ovat, modifikovat anebo jen čerpat informace z p ehledn dokumentovaných algoritmů. Paralelní výpočty umožňují v informatice pomocí paralelního programování naprogramovat úlohy, které zpracovávají data paraleln . Používá se zdánlivý paralelní b h úloh pomocí multitaskingu, víceprocesorové systémy nebo počítačové clustery. Žádoucím výsledkem je jednodušší algoritmus a rychlejší výpočet.

3

Současný stav

jsou:

22

Každý toolbox je zam ený na jistý druh výpočtů. Nejzajímav jší z toolboxů  Image proccessing toolbox o Image Processing Toolbox je výkonný, pružný a snadno ovladatelný nástroj pro zpracování a analýzu obrazu. Obsahuje nadstavby pro návrhy filtrů, rekonstrukcí a analýzu obrazů, dále nadstavby pro manipulaci s barvami, geometrií a strukturou obrazů včetn 2-D transformací.  Matlab compiler o Tvorba samostatn spustitelných aplikací a softwarových komponent z algoritmů vytvo ených v Matlabu.  Database Toolbox o Vým na dat s relačními databázemi, nap . Excel.  Simulink o Simulink je nadstavba Matlabu pro simulaci a modelování dynamických systémů, která využívá jeho algoritmy pro numerické ešení nelineárních diferenciálních rovnic. Poskytuje uživateli možnost rychle a snadno vytvá et modely dynamických soustav ve form blokových schémat a rovnic.

Metodika práce

23

3 Metodika práce 3.1 Metodika hardwarového zařízení Pro získání vstupních dat (obraz) bude použit menší fotoaparát značky Samsung typu St65. Fotoaparát má rozlišení fotografií až 14 megapixelů, objektiv o rozsahu 27-135 milimetrů, možnost po izovat video záznam v HD rozlišení Ěrychlost snímání 30 snímků za vte inuě, digitální stabilizaci. Tento fotoaparát je vhodný pro začínající fotografy. (Megapixel, 2013) Druhou možností vyfocení šachovnice je v tší fotoaparát značky Panasonic s označením DMC-FZ2Ř. Objektiv široký 27mm a zoom až 1Řx zvládá kvalitní záb ry na velkou vzdálenost stejn jako detailní záb ry zblízka. Takto široký objektiv nabídne podstatn širší zorné pole než tradiční fotoaparáty. Fotoaparát disponuje optickým stabilizátorem obrazu, který koriguje chv ní ruky. Systém inteligentního nastavení ISO kompenzuje pohyb fotografovaného objektu a také nabídne inteligentní detekci tvá í. (Megapixel, 2008)

3.2 Metodika softwaru Program na rozpoznávání figurek na šachovnici bude teoreticky rozd len na t i části, p ičemž každá z nich bude vykonávat dílčí funkci určenou k rozpoznání figurek. První část programu se bude zabývat problémem, jak nalézt ve vstupních datech samotnou šachovnici, tedy oblast na snímcích, kde program bude hledat šachové figury. Určení sou adnic šachovnice je důležitý bod programu pro jeho další fungování. Kdyby se šachovnice neurčila, program by nev d l, kde má šachové figurky vyhledat. Pro tento problém existuje mnoho ešení, proto budou vybrány nejrychlejší metody. Pro tuto fázi programu byly vybrány t i různé metody, jak vyhledat šachovnici v obraze. Výsledky metod vyhledávání šachovnice se budou navzájem porovnávat v rychlosti. První z nich bude Houghova transformace na hledání jednoduchých geometrických objektů. Technika se nejčast ji používá na hledání p ímek v obraze, proto je vhodná na vyhledání šachovnice. Druhá metoda se bude zabývat hledáním barevných figurek na šachovnici. Figurky, které budou barevn odlišeny od hrací desky, určí polohu šachovnice v obraze. Za t etí metodu byla vybrána funkce na hledání rohů v obraze. Funkce hledá vnit ní body šachovnice. Po určení oblasti šachovnice na snímcích můžeme určit st edové sou adnice políček a p i adit jim jednotlivá číselná označení na partii. To znamená písmeno a číslo od A1 po HŘ. V druhé části programu se budou vyhledávat jednotlivé figurky na šachovnici. Po jejich nalezení se určí sou adnice hracího políčka, kde se figurky nachází. Pro tento problém byly vybrány metody Houghova transformace kružnice a hledání barevné odlišnosti figurky. Tyto metody by m ly z obrazového materiálu po ízeného jedním z fotoaparátů vyčlenit šachové figurky.

Metodika práce

24

P i pohybu figurek na šachovnici pak nastanou t i pohyby, pro které nestačí jen detekování pozice. Jsou to vyhození figurky, rošáda a p em na p šce v dámu. Pro tyto pohyby se musí napsat v programu výjimky, které je p esn určí. Poslední častí programu bude výstup, tedy klasický výpis partie, kde jeden záznam má hodnotu jednoho tahu. V tomto p ípad můžeme pozpátku zjistit, jaké tahy byly v partii provedeny.

Vlastní práce

25

4 Vlastní práce Kapitola „Vlastní práce“ obsahuje veškeré pokusy o implementaci programu, kombinace úhlů pohledu na rozpoznávání samotné šachovnice a šachových figurek. Zahrnuje také nevyda ené pokusy, které byly provedeny za účelem získání kvalitních výsledků. První podkapitoly se zabývají problémem, jak získat pozici šachovnice v obrazu. V textu ukazuji funkce programu, které jsou klíčové pro program.

4.1 Získávání vstupních dat P i počátečním focení šachovnice byl použit menší fotoaparát značky Samsung typu St65. Fotky na malou vzdálenost byly ideální pro zpracovávání obrazu. Ostré fotky s bleskem se zdály být dobrým materiálem pro rozpoznávání objektů na snímcích. Ve fázi zpracovávání obrazu se p išlo na to, že fotoaparát značky Samsung není ideálním nástrojem na zachycení obrazu pro mou práci, protože snímal s velikým rozlišením, které bylo pro zpracování časov náročné. Proto byla zvolena možnost využít druhou variantu zachycení obrazu a tím byl v tší fotoaparát značky Panasonic. Ten umožňoval focení v rozlišení 1024x76Ř, jež zkracovalo dobu výpočtu na desetiny sekundy. Všechny po ízené obrazy, které se nafotily pro program, se fotily bez stativu. Tímto způsobem nebylo možné udržet šachovnici na stejném míst obrazu. Odchylka jejího umíst ní na fotce se do ešila softwarov . Proto metody hledající šachovnici budou použity p i každém novém obrazu. Všechny fotky, se kterými program bude pracovat, budou foceny tak, aby hrany šachovnice byly co nejvíce rovnob žné s okraji fotky.

4.2 Šachovnice a figurky Klasická šachovnice a figurky, které jsou v zájmu tohoto programu, byly zakoupeny p ímo pro toto využití, tedy pro bakalá skou práci. Již od prvního zpracovávání snímků s t mito figurkami se zdálo, že nejsou dostatečn vhodné pro rozpoznávání. Figurky m ly totiž stejnou barvu jako pozadí, v tomto p ípad jako pole šachovnice vždy, když černá figurka stála na černém poli šachovnice a naopak. Nevyda ené pokusy rozpoznávání černo-bílých figurek uvádím v podkapitole Detekce hran. Po n kolika nevyda ených pokusech rozeznávání vyšlo najevo, že se figurky musí n jak označit nebo úpln nahradit. Využita byla druhá možnost, protože první byla časov náročná. Místo černobílých šachových figurek byly koupeny barevné. Výsledkem byla černo-bílá šachovnice s modrými a červenými figurami. Barevná odlišnost figurek od hrací desky poskytovala vhodné podmínky pro detekci hran. Modrá a červená barva byly výrazn vid t na černém i bílém pozadí.

Vlastní práce

26

4.3 Intenzita jasu Sv tlo dopadající na povrch objektu zachyceného kamerou může zm nit jas snímku. Sv tlo p edstavují p íčné elektromagnetické vlny v dosti úzké oblasti vlnových délek, které se současn projevují jako tok fotonů. Sv tlo a barva jdou ruku v ruce. Bez sv tla p ed objektivem nevyfotíme nic. Na snímku bude jen „černota“. Proto musela být scéna dostatečn osv tlená, aby objekty, které jsou na scén významné, m ly ty správné barvy.

4.3.1 Stín Problémem p i nedostatečném osv tlení byl v p ípad ešeného tématu všudyp ítomný stín. V n kterých p ípadech zachycený stín na snímku byl p i detekci hran brán jako součást objektu, což vedlo k nep esnému určení hranice figurky. Stín lze pozorovat na obrázku 1.

Obr. 1: Stín na šachovnici

4.3.2Blesk fotoaparátu Další z otázek týkajících se nafocení šachovnice byla ta, zda fotit s bleskem, či bez n j. P i focení s bleskem se figurky na ploše zdály být ost ejší a jasn byly vid t hrany i pouhým okem. Avšak barvy na scén , kdy pole šachovnice m la stejnou barvu jako samotné figurky, byly důvodem fotit bez blesku. Tím se muselo p idat osv tlení v okolí scény. Focení šachovnice s bleskem m lo výhodu v tom, že na scén nebyly stíny a barvy byly ost ejší. To bylo výhodou jen p i focení kolmo na šachovnici. Nevýhodou p i focení s bleskem a kolmo na hrací plochu bylo to, že se na šachovnici utvo ilo sv tlé kolo.

Vlastní práce

27

4.4 Hledání šachovnice transformace

pomocí

Houghovy

První metoda na vyhledání šachovnice v obraze je Houghova transformace na detekování p ímek. Pro účely „Houghe“ se dá íct, že klasická herní plocha pro šachy se skládá z ř horizontálních a ř vertikálních p ímek, které jsou na sebe kolmé. Metoda hledá 1Ř p ímek, které stačí pro vyhledání šachovnice a určení jednotlivých políček. Po základní úprav obrazu, která zahrnuje p evod obrazu do šedi a následné p evedení na binární obraz, se použije Sobelův detektor hran. Hledání šachovnice je rozd leno do dvou částí. První část hledá vertikální p ímky a druhá horizontální. Sobelův detektor hran je použit, protože má schopnost vyhledávat hrany svisle nebo vodorovn . Proto je hledání p ímek v obraze rozd leno. Hledat všechny p ímky ve všech úhlech bylo časov náročn jší. Jak je již výše uvedeno, všechny fotky jsou foceny tak, aby hrany šachovnice byly rovnob žné s okraji obrazu. Z toho vyplývá, že se budou hledat p ímky horizontáln , tj. -20 až 20 stupňů, a vertikáln , tj. -ř0 až -Ř0 stupňů. Takto nastavené hranice jsou voleny pro nestálost pozice šachovnice v obraze. Výsledek Houghovy transformace hledání šachovnice můžeme vid t na obrázku 2. P ičtením poloviny vzdálenosti od jedné p ímky k sousední se naleznou st edy jednotlivých políček. Čas, za jaký tato metoda našla šachovnici, se pohyboval okolo 0,4 sekundy.

Obr. 2: Houghova transformace p ímky

Vlastní práce

28

4.5 Hledání rohů Druhá metoda k nalezení šachovnice se zabývá detekcí rohů, kterou navrhl Harris. Vstupem detektoru jsou fotky p evedené do stupn šedi. Výstupem jsou rohy (vrcholy) obrazu, které se reprezentují jako sou adnice a číselná hodnota popisující sílu vrcholu v obraze. Po nalezení všech bodů v obraze pomocí detektoru Harris byly vybrány ty pozice rohů, které jsou nejblíže okraji obrazu. Sou adnice t chto bodů určují hrací desku v obraze. Rozd lením vzdálenosti t chto bodů zvlášť na ose x a zvlášť na y na osminy jsou vyhledána jednotlivá políčka. Výsledek metody lze vid t na obrázku 3. Jako nevýhodu tohoto postupu označuji možnost nalezení vrcholu mimo hrací desku. Toto je eliminováno tím, že je šachovnice focena na jednobarevném pozadí.

Obr. 3: Nalezení šachovnice pomocí Harrise

4.6 Hledání šachovnice pomocí barvy Poslední metoda jak najít šachovnici vychází z barevných šachových figurek. Základem postupu je barevná odlišnost od hrací desky. Program prochází obraz pixel po pixelu. V obrazu, který má rozlišení 1024x76Ř tj. 7Ř6432 pixelů, by bylo

Vlastní práce

29

zbytečné a také zdlouhavé procházet všechny pixely. Pro nalezení šachovnice stačí najít 4 body, které jsou shodné s figurkou. První pixel je situovaný nejvíce nalevo. Druhý pixel je umíst n nejvýše. Hodnota sou adnic prvního pixelu na ose x a hodnota sou adnic druhé hledaného pixelu na ose y určuje levý horní roh hledané šachovnice. Totožný postup jako u prvních dvou pixelů uplatníme i pro další dva, které vytyčují pravý dolní roh hrací desky. Obraz se však bude prohledávat od posledního pixelu a zastaví se p i nalezení prvního, který je položený nejvíce vpravo a nejvíce dole. Vzdálenost mezi rohy šachovnice na ose x a ose y se pak rozd lí na osminy a vzniknou jednotlivá políčka hracího prostoru. Výsledek metody lze pozorovat na obrázku 4. Tento postup by se dal použít jen v p ípad , kdyby všechny snímky partie byly nafoceny ze stejné pozice. Potom by stačilo tímto postupem vyhledat šachovnici jen p i počátku hry, protože v pozd jších fázích hry může nastat chvíle, kdy figurky nebudou na krajních políčkách šachovnice. V tomto p ípad nebude možné íci, kde se šachovnice nachází. Místo toho byla výše uvedená metoda použita na hledání samotné šachovnice. Vezme-li se v úvahu, že fotky nebudou vždy z té samé pozice, je efektivn jší hledat šachovnici na každém snímku. V tomto p ípad p ibyla podmínka, že pozadí4 musí mít jinou barvu než šachovnice. Místo barvy figurky budeme hledat barvu samotné šachovnice. V tomto p ípad je to černá barva. Výsledek je vid t na obrázku 4. Zde i v p edešlé metod pro nalezení šachovnice je nevýhodou, že okraje hrací desky musí být co možná nejvíce rovnob žné s osami obrazu. Z hlediska rychlosti hledáme „jen“ levý horní a pravý dolní roh. Pro p esn jší detekování šachovnice by se mohly najít i ostatní dva rohy.

4

Povrch, na kterém hrací deska leží.

Vlastní práce

30

Obr. 4: Nalezení šachovnice pomocí barvy

4.7 Detekce hran Detekce hran byla použita v Houghov transformaci na vyhledávání p ímek v obraze. V té metod byl použitý výhradn Sobelův detektor, který byl rozd len na vertikální a horizontální hrany. Pro tento účel byl nejvíce účinný. V další metod , ve které je použitý hranový detektor, je metoda na vyhledávání figurek pomocí Houghovy transformace kružnice. Zde je detekce hran použitá jako vstup pro vyhledávání kružnic. První obrazy, na kterých byl detektor vyzkoušen, obsahovaly černobílé figurky. Výsledky t chto detekcí byly nedostačující, protože detektor nedokázal vyhledat černé figurky na černém poli šachovnice. Stejnou chybu vykazoval i v n kolika málo p ípadech, kdy bílé figurky byly na bílém políčku. Toto byl důvod vym nit figurky za barevné. V programu byly vyzkoušeny čty i detektory hran na vyhledávání maxim první derivace:  Canny.  Roberts.

Vlastní práce

31

 Prewitt.  Sobel. Dále byl vyzkoušen detektor hran založený na hledání průchodu druhých derivací nulou. Tato metoda se jmenuje Marr-Hildreth. Všechny vyzkoušené detektory m ly však stejn nedostačující výsledky a nedokázaly vyhledat hrany černé figurky na černém políčku šachovnice. Výsledek Cannyho detektoru hran lze vid t na obrázku 5.

Obr. 5: Výsledek detekce hran

4.8 Detekce figurek pomocí Houghovy transformace První vyzkoušenou metodou jak vyhledat jednotlivé figurky na šachovnici, byla Houghova transformace v oblasti vyhledané výše uvedenými metodami. Houghova transformace nevyhledává jen p ímky, ale jak se píše v kapitole 2.4.2, „Hough“ vyhledává i kruhovité tvary. Toho je využito pro hledání figurek. Pohled shora ukazuje figurky jako nedokonalé kruhy. Metody pro vyhledání šachovnice daly na výstupu sou adnice st edů jednotlivých políček. Pomocí této metody se v oblasti kolem st edu hracích políček program snaží určit, zda se na políčku nachází kružnice, která by odpovídala figurce.

Vlastní práce

32

P íprava obrázku pro tuto detekci znamenala p evod snímku do šedi a použití hranového detektoru. Výsledkem byl binární obraz, v n mž byly vyznačeny hrany. V tomto binárním obraze jsou hledány pomocí Houghovy transformace kružnice. Parametrem pro detekci kružnic je minimální a maximální velikost kružnice. Maximální velikost kružnice určuje vzdálenost mezi sousedními st edy políček mínus 30 %. Minimální velikost je 10 % vzdálenosti mezi st edy. Druhým parametrem je citlivost detekce. Metoda vyhledává i více kruhové objekty, včetn slabých a částečn zakrytých. Proto se nastavuje parametr citlivosti, kterým ovlivníme detekci slabých kružnic. Vysoký stupeň citlivosti zvyšuje riziko detekce falešných objektů. Výstupem této detekce jsou st edy nalezených kružnic, jejich prům r a síla. Propočtem vy adíme nalezené kružnice, které mají sílu menší jak stanovený parametr. To jsou kružnice, které jsou podle detektoru slabé nebo nemají dostatečn viditelné hrany. Pro určení samotných figurek a vy azení falešných kruhových objektů je použit postup, kde v okolí st edu políčka hledáme st ed kružnice. Tímto způsobem program nachází jednotlivé figurky. I p es použití barevných figurek nedokázal Houghův transformátor odhalit všechny kruhy týkající se figurek. Úsp šnost této metody se pohybovala okolo 75 %, což je nedostatečné pro tento typ programu. Výsledek metody je ukázán na obrázku 6.

Obr. 6: Šachovnice s barevnými figurami

Vlastní práce

33

4.9 Detekce figurek pomocí barvy Druhý postup jak vyhledat figurky v obraze využil jejich barevné odlišnosti oproti šachovnici. V modelu RGB je obraz vyjád en jako trojrozm rná matice pixelů, kdy t etí rozm r znázorňuje jednu ze t í hlavních barev, tj. červenou, zelenou a modrou v hodnotách 0 až 256. Pro zjednodušení jsou hodnoty vyd leny 256, aby vzniklo rozmezí od 0 do 1. Rozd lením t chto t í barev vzniknou t i samostatné matice stejného rozm ru znázorňující jednu z barev. Sloučením t chto t í matic do jedné s podmínkami na jednotlivé barvy se vytvo í matice znázorňující jen jednu barvu, která se rovná jedničce. Podmínky pro určení červené barvy figurek jsou následující: červená je v tší než 0,5, zelená je menší než 0,4 a modrá je menší než 0,3. A pro určení modré barvy figurek jsou tyto podmínky: červená je menší než 0,25, zelena je menší než 0,7 a modrá je v tší než 0,5. Ze sloučení s t mito podmínkami vzniknou dva binární obrazy, kde 1 znázorňuje hledané barvy a nula ostatní. Do binárních obrazů, které vyšly z postupu uvedeného výše, jsou dosazeny st edy jednotlivých políček nalezených metodou na hledání šachovnice. Kolem st edů se program snaží zjistit, zda se tam požadovaná barva nachází. Výsledkem jsou políčka šachovnice, kde stojí figurky. Dvojbarevné rozlišení figurek umožňuje rozd lit figurky na dv skupiny, což u p edchozí metody nejde. Výstup pro další zpracování bude ve dvou maticích, p ičemž jedna bude pro bílé figurky, druhá pro černé. Jedná se o matice ŘxŘ, kde políčko s figurkou dostane číslo jedna. Na obrázku 7 je ukázáno nalezení figurek.

Vlastní práce

34

Obr. 7: Detekce figurek pomocí barvy

4.10 Pohyb figurek V následující kapitole bude ešeno, jak se pohybují figury v jednotlivých tazích. Pohyb figurek je ešený jen pro detekci figurek pomocí barvy, protože druhá metoda na jejich vyhledání v obraze je nedostatečná. V počátku partie je vždy základní postavení. Od toho se budou odvíjet další tahy. Tím, že všechny figury jednoho hráče mají stejnou barvu a hardwarov se nedá ošet it, která figura má jaký název, musí program obsahovat různé operace pro zjišt ní, kam která figura na šachovnici skočila. V partii s barevnými figurami můžou nastat jen tyto tahy:    

B žný tah. Vyhození figurky protihráčem. Vým na p šce za královnu. Rošáda.

Vlastní práce

35

B žný tah je zjišt n pomocí hledání figurek na šachovnici. Tato operace je stejná jako p i počátečním hledání všech figurek na šachovnici. Figurky stojí na svém základním postavení. Posunem figurky na jiné pole se zap íčinilo jen to, že se p epsal soubor se sou adnicemi figurek a p ipsal se zápis do logu hry. Toto ešení v programu funguje tak, že jsou figurky vyjád eny jako číslo jedna v matici 8x8. Pro každou barvu jedna matice. V jednoduchém tahu figurky jde jen o rozdíl od p edchozího tahu. Ve výsledku rozdílu 1 znamená novou pozici a -1 p edchozí. Problém nastává p i vyhození figurky protihráčem. Když hráč odebere p i tahu svou figurkou protihráčovu figurku, nastává situace, kdy se počet figurek na šachovnici sníží o jedna. Tato situace je vid t p i rozdílu figurek v jednotlivém tahu. Program zjistí figurku na poli v jednom tahu a p i druhém tahu zjistí v jednom obraze prázdné políčko a v druhém obraze figurku protihráče. Kdyby byly všechny figurky stejné barvy, nebylo by možné zjistit, kam se daná figurka ztratila. Další tahem je vým na p šce za královnu. K zjišt ní tohoto tahu pomůže další matice, která je konečným výpisem programu. Jde o matici 8x8 s prvními písmeny anglických slov označujících jednotlivé figurky. Potom v p ípad , kdy cílový ádek p šce je na konci hrací plochy, zm níme ve výpisu p šce za královnu. Jako poslední tah zůstává rošáda. Tento tah se zjistí pomocí rozdílů tahu, avšak místo jednoho prázdného políčka budou dv . Zde se uplatní standardní pravidlo, kdy rošáda je provedena jen na krále a v ž s tím, že mezi nimi nesmí stát žádná figurka.

4.11 Výstup programu Program má dva výpisy. První výpis bude matice 8x8, kde písmeny budou označeny figurky. Písmeny se má na mysli první písmena anglických slovíček pro šachové figurky (viz. Obr. 8). Tento výstup má jednu chybu v tom, že písmena pro jednotlivé figurky jsou stejná pro ob barvy. Proto má program druhý výstup, a to textový soubor, který vypisuje jednotlivé tahy. Každé táhnutí figurkou vypisuje na jeden ádek. Tento výstup se dá p i adit k jednoduchému logu nebo historii partie. Můžeme tedy vid t, kolik tahů se v partii odehrálo. První ádek výpisu je začátek partie, kdy figurky stojí v p edepsaném postavení. Zápis 4 tahů lze vid t na obrázku ř.

Vlastní práce

36

Obr. 8: Zaznamenání tahu

Obr. 9: Textový výpis partie

4.12 Testování Testování všech uvedených metod prob hlo na souboru 65 fotek odpovídající jedné šachové partii v rozlišení 1024 x 76Ř. V testovaném souboru se vyskytly všechny pohyby zmín né v kapitole 4.10. Testování prob hlo na notebooku HP s konfigurací popsanou v p íloze A. V prvním sloupci následující tabulky jsou vid t prům rné časy, za které metody dokončily vyhledávání šachovnice. V druhém sloupci jsou časy jednotlivých metod vyhledávající šachovnici s metodou detekce figur pomocí barvy, rozpoznání pohybu a následné zapsání do logu. V testování byla vynechána metoda na detekci figur pomocí Houghovy transformace, protože metoda nedosahovala dostatečné úsp šnosti.

Vlastní práce

37

Tab. 1: Testování metod Metoda

Průměrné časy

Houghova transformace Harris

0,8

Průměrné časy celkem 0,95

0,27

0,35

Detekce šachovnice pomocí barvy

0,19

0,25

4.13 Zhodnocení vlastního řešení Praktická část bakalá ské práce se zabývá naprogramováním algoritmu, který vyhledává šachovnici a figurky na ní, také zaznamenává pohyby figur na šachovnici. V kapitole „Vlastní práce“ jsou uvedeny t i metody na vyhledávání šachovnice a dv metody na vyhledání figurek na šachovnici. Zám na figurek, jaká se ud lala, se zdála v tomto p ípad dobrým ešením pro nedostatečnou detekci hran. Dále je v práci uvedeno, jaké postupy program používá pro určení sou adnic figurek. Program, jehož vstupem jsou fotky jednotlivých tahů šachové partie, má na výstupu historii celé hry. Další vývoj této práce by se mohl zabývat rozpoznáváním figurek v rozehrané partii. Prvním vstupem by nebyly figurky v základním postavení, ale již rozházené po šachovnici. Tento problém by se mohl ešit pomocí více než jednoho obrazu, tedy víc úhlů snímání. Další rozvoj by mohl být ve zm n snímacího aparátu. Vym nit fotoaparát za webovou kameru.

Záv r

38

5 Závěr Cílem této bakalá ské práce bylo navrhnout, naimplementovat a otestovat program na rozpoznávání šachových figurek. Pro nalezení šachovnice byly zkoumány t i metody, které byly testovány na snímcích šachové partie. Všechny zkoumané metody vyšly z testování jako úsp šné a dokázaly rozd lit šachovnici na jednotlivá hrací políčka. Podmínkou pro nalezení šachovnice bylo snímání obrazu rovnob žn se stranami šachovnice. Výsledky testování metod jsou popsány v p íslušných kapitolách. Dalším krokem bylo nalezení figurek na šachovnici. K detekování figurek byly navrženy a testovány dv metody: Houghova transformace kružnice a barevná detekce, p ičemž metoda Houghovy transformace p i testování neusp la. Tato metoda m la ve výsledku jen 75% úsp šnost. Nalezení figurek pomocí barev bylo úsp šné. Metoda rozd lila figurky pro jednotlivé hráče. Důležitou částí bylo zjišt ní pohybu jednotlivých figurek na šachovnici, které navazuje na jednotlivé detekce figurek. Tento problém je ešený podle herních pravidel pro šachy. Na základ pohybu figurek se vypisují výstupy programu. Jedním z nich je textový soubor, kde ádky obsahují jednotlivé tahy partie. Druhým výstupem je matice s písmeny označujícími šachové figurky. Tento funkční program jako celek může tedy sloužit pro dokumentaci šachové partie hráče proti hráči nebo může poskytovat detekci figurek pro práci šachového automatu.

Literatura

39

6 Literatura DUDA, R. a P. HART. Use of the Hough transformation to Detect Lines and Curves in Pictures [online]. In: Comm. ACM. 1972, Vol. 15, No. 1, Leden, 1972. Dostupné z: http://www.ai.sri.com/pubs/files/tn036-duda71.pdf. DUŠEK, F. Matlab a Simulink: úvod do používání. Pardubice: Univerzita Pardubice, 2005, 172 s. ISBN 80-719-4776-8. HLAVÁČ, V. a M. SEDLÁČEK. Zpracování signálů a obrazů. 2. vyd., p eprac. Praha: Vydavatelství ČVUT, 2005. ISBN 80-01-03110-1. HLAVÁČ, V. a M. ŠONKA. Počítačové vidění. Praha: Grada Publishing, a.s., 1992, 272 s. ISBN 80-854-2467-3. HLAVÁČ, V., M. ŠONKA a R. BOYLE. Image processing, analysis, and machine vision. Toronto: Thomson, Toronto, 2008, , 872 p. ISBN 978-0495082521. KOTEK, Z. a V. MA ÍK. Metody rozpoznávání a jejich aplikace. 1. vyd. Praha: Academia, 1993, 195 s. ISBN 80-200-0297-9. KRATOCHVÍLOVÁ, A. Parciální diferenciální rovnice ve zpracování obrazu [online]. Praha: ČVUT, 2007, 61 s. [cit. 2014-03-22]. Dostupné z WWW: http://kmlinux.fjfi.cvut.cz/~oberhtom/studenti/07-kratochvilova-anna-pde-in-im age-processing.pdf. LIBRA, M., J. ŠT RBA a I. BLÁHOVÁ. Fyzikalní podstata sv tla [online]. Světlo. 2000, č. 4 [cit. 2013-12-21]. Dostupné z: http://www.odbornecasopisy.cz/index .php?id_document=22854. MathWorks, Inc. MATLAB [online]. 2016 [cit. 2014-03-24]. http://www.humusoft.cz/produkty/matlab/.

Dostupné z:

MEGAPIXEL.cz. Panasonic Lumix DMC-FZ28 [online]. 2008 [cit. 2014-03-22]. Dostupné z: http://www.megapixel.cz/panasonic-dmc-fz28. MEGAPIXEL.cz. Samsung ST65 recenze [online]. Megapixel.cz - digitální fotoaparáty a videokamery Sony, Canon, Nikon, Olympus, Panasonica, 2013 [cit. 2014-02-16]. Dostupné z: http://www.megapixel.cz/samsung-st65/recenze. PARKER, J. R. Algorithms for image processing and computer vision. 2nd ed. New York: Wiley Computer Pub., c2011. ISBN 9781118019627.PARKER, J. R. Algorithms for Image Processing and Computer Vision. John Wiley, 2010. ISBN 978-0470643853. SOCHOR J., J. ŽÁRA a B. BENEŠ. Algoritmy počítačové grafiky. 1. vyd. Praha: ČVUT, Praha, 1998, 258 s. ISBN 80-01-00949-1. ŠPAN L, M. a V. BERAN. Obrazové segmentační techniky [online]. Brno: Vysoké učení technické v Brn , 2005. Dostupné z: http://www.fit.vutbr.cz/~spanel/ segmentace/.

Literatura

40

VOLNÁ, E. Umělá inteligence [online]. Ostrava: Ostravská univerzita v Ostrav , 2013 [cit. 2013-12-02]. Dostupné z: http://www1.osu.cz/~volna/Umela_ inteligence_skripta.pdf ŽELEZNÝ, M. Zpracování digitálního obrazu [online]. 2006 [cit. 2014-03-22]. Dostupné z WWW: .

P ílohy

41

Přílohy

P ílohy

A

42

Konfigurace hardwaru

Program byl vytvo en a testován na notebooku značky HP typ Probook 4525s s t mito parametry:  Procesor Intel I5 480M s frekvencí 2,66 GHz  Operační pam ť 4GB DDR3 1333 MHz  Grafická karta AMD Mobility Radeon HD6370 s 1024 MB pam tí  Displej 17,3 palců LCD s LED podsvícením, rozlišení 1600 x ř00  Pevný disk 500 GB, 7200 RPM

B

Ukázka hledaných figurek

Ukázka šachových figurek, s nimiž se v programu pracuje.

Obr. 10 Ukázka šachových figurek