Aplikace usnadňující skládání Rubikovy kostky pomocí rozšířené reality

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Martin Španěl Aplikace usnadňující skládání Rubikovy kostky pomocí rozšířené reality Katedra softwarového inženýrství

Vedoucí bakalářské práce: Ing. Jan Kamenický Ph.D. Studijní program: Informatika Studijní obor: Obecná informatika

Praha 2016

Prohlašuji, že jsem tuto bakalářskou práci vypracoval(a) samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona.

V . . . . . . . . dne . . . . . . . . . . . .

Podpis autora

i

Název práce: Aplikace usnadňující skládání Rubikovy kostky pomocí rozšířené reality Autor: Martin Španěl Katedra: Katedra softwarového inženýrství Vedoucí bakalářské práce: Ing. Jan Kamenický Ph.D., Oddělení zpracování obrazové informace, ÚTIA Abstrakt: V této práci je představen program asistující se složením Rubikovy kostky pomocí počítačového vidění prostřednictvím rozšířené reality. To se děje ve dvou fázích nejprve je rozpoznán stav, do kterého je kostka zamíchána a potom jsou postupně ukazovány tahy. Oboje nevyžaduje žádný vstup od uživatele kromě dat z kamery a uživatel může při rozpoznávání stěny kostky ukazovat v jakémkoli pořadí z jakýchkoli úhlů a při skládání může držet kostku jakkoli otočenou. Klíčová slova: počítačové vidění, rozšířená realita, Rubikova kostka

Title: Rubik’s Cube augmented reality helper application Author: Martin Španěl Department: Department of Software Engineering Supervisor: Ing. Jan Kamenický Ph.D., Department of Image Processing, ÚTIA Abstract: The program introduced in this thesis assists with solving a Rubik’s cube using computer vision and augmented reality. The assistance consists of two phases - in the first phase the state of the cube is recognized. In the second phase the next turn to make is shown until the cube is solved. Both of these phases do not need any other input from the user other than the data from the camera. The user can show the faces of the cube in arbitrary order and from arbitrary angle. During the solving phase the cube can be held in any orientation. Keywords: computer vision, augmented reality, Rubik’s Cube

ii

Rád bych poděkoval svému vedoucímu Janu Kamenickému za cenné rady, věcné připomínky a vstřícnost při konzultacích bakalářské práce. Dále bych rád poděkoval Adamu Španělovi za zapůjčení sbírky kostek.

iii

Obsah 1 Úvod 1.1 Motivace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Popis programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Stěžejní části programu . . . . . . . . . . . . . . . . . . . . . . . .

3 3 3 3

2 Rubikova kostka 2.1 Části kostky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Tahy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 5

3 Rozpoznání Rubikovy kostky 3.1 Vrstvy rozpoznávání . . . . . . . . 3.2 Reprezentace kostky . . . . . . . . 3.3 Míra jistoty . . . . . . . . . . . . . 3.4 Vynucení konsistence . . . . . . . . 3.4.1 Neexistující kostičky . . . . 3.4.2 Duplicitní kostičky . . . . . 3.5 Rozpoznání nálepek . . . . . . . . . 3.5.1 Algoritmus . . . . . . . . . 3.6 Přiřazení nálepek pozicím na kostce 3.6.1 Základní kroky . . . . . . . 3.6.2 Klastrování . . . . . . . . . 3.6.3 Určení první stěny . . . . . 3.6.4 Ostatní stěny . . . . . . . . 3.7 Určení barvy nálepky . . . . . . . . 3.8 Bílé nálepky na bílé kostce . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

4 Navigování 4.1 Nalezení postupu složení . . . . . . . . 4.1.1 Kociemba two-phase algoritmus 4.1.2 Algoritmus two-phase+ . . . . . 4.1.3 Inverzní two-phase . . . . . . . 4.2 Rozpoznání . . . . . . . . . . . . . . . 4.2.1 Ověření tahu . . . . . . . . . . 4.2.2 Otočení modelu kostky . . . . . 5 Uživatelská dokumentace 5.1 Instalace . . . . . . . . . . . 5.2 Podrobný návod na použití . 5.2.1 Detekční fáze . . . . 5.2.2 Navigační fáze . . . . 6 Programátorská dokumentace 6.1 Rozdělení tříd . . . . . . . . 6.2 Reprezentace kostky . . . . 6.3 Algoritmy . . . . . . . . . . 6.3.1 Analyser . . . . . . .

. . . .

. . . .

. . . .

. . . . 1

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

. . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . . .

6 6 6 7 7 7 7 7 8 8 8 9 9 10 10 10

. . . . . . .

12 12 12 12 13 13 14 14

. . . .

15 15 15 15 16

. . . .

17 17 17 17 17

6.4

6.3.2 Visor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 StickerDetector . . . . . . . . . . . . . . . . . . . . . . . . Externí knihovny . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 18

Závěr

20

Seznam použité literatury

21

Přílohy

22

2

1. Úvod 1.1

Motivace

Rubikova kostka je nejprodávanějším hlavolamem na světě a existuje mnoho počítačových i mobilních aplikací, které slouží k asistenci s jejím složením. Počítačové vidění je zjevně uživatelsky nejpohodlnějším způsobem, jak vložit informace o zamíchání kostky do programu. Žádná existující aplikace ale nevyužívá plný potenciál počítačového vidění. Program, který je v této práci představen, nemá žádný jiný vstup od uživatele, než pravidelné snímky náhledu kamery. Výstup je grafický přímo do náhledu kamery. Pro demonstraci funkčnosti je implementována asistence se složením kostky na dvacet tahů. Snadno ale může být program rozšířen třeba o výuku algoritmů, kde mohou být zvýrazněny podstatné části kostky přímo na aktuálním obrazu kostky v náhledu kamery.

1.2

Popis programu

Program, o kterém je tato práce, se jmenuje Mistr Kostky. Je napsán v Javě a má verzi pro PC a pro Android. Ty se od sebe z uživatelského hlediska ničím neliší. Program projde postupně dvěma kroky - rozpoznáváním a navigováním. V prvním kroku nechá program uživatele ukazovat kostku do kamery z libovolných úhlů a ukazuje mu, které části kostky byly úspěšně rozpoznány a které ještě ne. Není potřeba skenovat stěny v nějakém určitém pořadí ani někam explicitně zadávat, kterou stěnu uživatel ukazuje, program se o vše postará sám. Jakmile je takto rozpoznána celá kostka, přichází druhý krok a tím je navigace k jejímu co nejrychlejšímu složení. Podle Rokicki (2013) pro každou kostku existuje řešení na nejvýše dvacet tahů, kde se tahem myslí otočení jedné stěny o 90◦ nebo o 180◦ . Program jedno takové řešení najde a kreslí přímo do náhledu kamery šipky znázorňující tah, který má uživatel udělat, viz obrázek 1.1. Ověří, že jej udělal správně a naviguje k dalšímu tahu. To opakuje tak dlouho, dokud kostka není složena. Na stránce http://www.ms.mff.cuni.cz/~spanelm je program ke stažení a je tam i video demonstrující jeho používání.

1.3

Stěžejní části programu

Základní struktura programu je znázorněna na obrázku 1.2. Nejdůležitější částí programu je rozpoznání kostky na snímku z kamery. To musí být takové, aby fungovalo co nejlépe i v neznámém prostředí s neznámou kostkou (kostky jednotlivých výrobců se od sebe výrazně liší odstíny nálepek a barvou těla kostky). skládá se ze dvou kroků - rozpoznání jednotlivých barevných nálepek a jejich přiřazení pozicím na kostce. Takto je v každém snímku rozpoznána kostka - někdy jenom jedna stěna a někdy dvě najednou nebo dokonce tři. Z každého takového pohledu vytvoříme nějaký neúplný model kostky. Tyto modely postupně spojujeme do jednoho. 3

Obrázek 1.1: Snímek z použití programu na počítači.

Obrázek 1.2: Základní struktura programu. V průběhu ověřujeme, že model odpovídá nějakému možnému zamíchání kostky. Když je kostka celá rozpoznána, kreslí program přímo na obrázek v náhledu kamery, jak udělat další tah. Program automaticky rozpozná, že byl tah vykonán a že má navigovat k vykonání dalšího tahu.

4

2. Rubikova kostka 2.1

Části kostky

Rubikova kostka (dále jen kostka) se skládá z pohyblivých dílků. Pro nás budou důležité ty na povrchu kostky. Těch je 26 a budeme jim říkat kostičky. Dělí se do tří kategorií podle toho, kolik jejich stěn je vidět. Těch, ze kterých jsou vidět tři stěny je 8 a budeme jim říkat rohy, protože v každém rohu kostky je jedna. Kostiček, z nichž jsou vidět dvě stěny je 12 a budeme jim říkat hrany, protože na každé hraně kostky je jedna a podobně kostičkám, ze kterých je vidět jenom jedna stěna, budeme říkat středy, protože jsou ve středech stěn kostky. Středů je 6. Na každé kostičce je na každé stěně, která je na povrchu kostky, jednobarevná nálepka. Na standardní kostce je těchto šest barev nálepek: bílá, žlutá, červená, oranžová, modrá a zelená. Ve složeném stavu je bílá naproti žluté, červená naproti oranžové a modrá naproti zelené. Kostičky je možné přeuspořádat pomocí tahů, neboli otočení jedné vrstvy kostiček. Tím je možné kostku zamíchat a následně složit. Na obrázku 2.1 je vidět zamíchaná kostka, na které je prováděn tah.

2.2

Tahy

Tahem rozumíme otočení jedné z vnějších vrstev kostiček o 90◦ nebo o 180◦ . Možných tahů je 18 - každou z 6 stěn můžeme otočit třemi způsoby. Pro reprezentaci tahů je použit standardní textový zápis. Každý tah má svůj kód, který začíná písmenem označujícím otáčenou stěnu (U: up, D: down, L: left, R: right, F: front, B: back). Pokud je tah otočení o 90◦ po směru hodinových ručiček, tah značíme pouze písmenem dané stěny. Pokud je tah o 90◦ proti směru hodinových ručiček, přidáváme k písmenu symbol ’. Pokud se jedná o tah o 180◦ , přidáváme místo něj symbol 2. Například otočení horní stěny proti směru hodinových ručiček bychom tedy značili U’. Poloha středů zůstává po provedení každého tahu stejná. Jednotlivé kostičky se tahy také nemění – na každé jsou stále stejné nálepky. To znamená, že pracujeme s jednou pevně danou neměnnou množinou kostiček.

Obrázek 2.1: Zamíchaná Rubikova kostka. 5

3. Rozpoznání Rubikovy kostky Program dostává každý snímek náhledu kamery a zpracuje ho. To mu pro každý snímek trvá řádově desítky milisekund na počítači, stovky milisekund na telefonu. Zpracování zahrnuje rozpoznání kostky z obrazu a rozšíření znalostí o stavu kostky.

3.1

Vrstvy rozpoznávání

Algoritmus rozpoznání kostky na jednom snímku se dá rozdělit do dvou kroků: Rozpoznání jednotlivých barevných nálepek a přiřazení nálepek pozicím na stěně kostky. Tím získáme neúplný model kostky. Další kroky se liší podle toho, v jaké fázi používání programu uživatel je. Pokud už máme z předchozích kroků úplný model kostky se všemi nálepkami, najdeme jeho umístění v obrázku nejlépe odpovídající novému pozorování. Tím končí rozpoznávání. Pokud úplný model teprve budujeme, děláme to v následujících krocích: první krok je spojení dosavadního modelu a nového modelu s dostatečným překryvem. Druhý krok je vynucení konsistence, neboli zajištění toho, že po správném doplnění neznámých barev nálepek bude kostka odpovídat nějakému platnému zamíchání. Třetí krok je zahrnutí nově objevených nálepek do starého modelu. Na obrázku 3.1 je porovnání průměrného času potřebného na jednotlivé kroky od získání snímku z kamery po jeho vykreslení. Je vidět, že rozpoznávání je nejnáročnější část.

3.2

Reprezentace kostky

Pro interní reprezentaci kostky je potřeba si pevně stanovit formát, ve kterém budeme kostku ukládat. Není žádný standardní formát, ve kterém kostku popisovat, proto si zavedeme formát vhodný pro účely našeho programu. K reprezentování kostky existují dva základní přístupy – popisovat ji po stěnách, nebo po kostičkách. V případě popisování po stěnách je potřeba pro každou

Obrázek 3.1: Čas potřebný pro hlavní části algoritmu. 6

ze šesti stěn popsat, které nálepky na ní jsou. V případě popisování po kostičkách stačí popsat pro každou z 20 pohyblivých kostiček (8 rohových a 12 hranových), na které pozici a v jaké orientaci je. Oba tyto přístupy mají své výhody. Reprezentace po kostičkách umožňuje přímočaře ověřit, že je každá kostička obsažena právě jednou. Také se v ní jednodušeji reprezentují tahy. Pro rozpoznávání obrazu je ale výrazně příhodnější reprezentace pomocí stěn, protože algoritmus popsaný v této práci rozpoznává kostku po stěnách a základní jednotkou kostky z hlediska rozpoznávání není kostička, ale nálepka. Pozice každé nálepky je určena číslem stěny a číslem pozice na této stěně.

3.3

Míra jistoty

U každé nálepky udržujeme veličinu nazvanou ”míra jistoty”. Míra jistoty udává, jak spolehlivá je informace o její barvě. Tato hodnota se bude zvyšovat, pokud se barva nějaké nálepky potvrdí, a bude se snižovat, pokud naopak nový obrázek nasvědčuje tomu, že má daná nálepka jinou barvu.

3.4

Vynucení konsistence

Je pevně daná množina kostiček, z nichž se kostka skládá. Kostičky neubývají ani nepřibývají. Každá kostička kostky musí být v této množině obsažena a žádná kostička nesmí být v kostce dvakrát. Z toho mimo jiné plyne, že je každá barva přesně na devíti nálepkách. Během rozpoznávání se může stát, že získáme model kostky, který tato pravidla nesplňuje. V takovém případě je potřeba model opravit.

3.4.1

Neexistující kostičky

V případě, že po rozpoznání vznikne model obsahující neexistující kostičku, model upravíme tak, aby se tento konflikt odstranil. Nejjednodušší řešení by bylo označit všechny nálepky na problematické kostičce jako neznámé. Tím se ale zbytečně ztrácí informace. Proto označíme jako neznámou pouze nálepku s nejnižší mírou jistoty c na kostičce. U ostatních snížíme jejich míru jistoty o c.

3.4.2

Duplicitní kostičky

V případě, že se stejná kostička vyskytuje vícekrát, postupujeme podobně. Mezi nálepkami příslušných kostiček vybereme tu, která má nejnižší míru jistoty c. Její barvu označíme jako neznámou a u ostatních snížíme míru jistoty o c.

3.5

Rozpoznání nálepek

Rubikova kostka má na každé stěně devět barevných nálepek. Jejich určení stačí k jednoznačnému popisu stavu kostky.

7

Nálepku na obrázku charakterizujme jako zhruba rovnoběžníkovou jednobarevnou oblast ohraničenou tmavším okolím (pro kostky z černého plastu) nebo světlejším okolím (pro kostky z bílého plastu). Rozpoznávat budeme jenom nálepky v určitém rozsahu velikostí. Této charakteristice nemusí odpovídat všechny nálepky a ne všechny objekty mající tyto charakteristiky jsou nálepka. Konkrétně třeba bílou nálepku na bílé kostce není možné tímto algoritmem rozpoznat.

3.5.1

Algoritmus

Je určen rozsah barev v barevném prostoru HSV, který by měl přibližně odpovídat barvě těla kostky - bílé nebo černé. V HSV je barva reprezentována třemi hodnotami: hue (odstín), saturation (sytost) a value (intenzita). Při rozpoznávání černé i bílé můžeme odstín ignorovat, sytost bude omezena shora a intenzita zdola, resp. shora. Zda je barva těla kostky bílá nebo černá není známo předem. Vyzkouší se obě možnosti a použije se ta, která povede k lépe rozpoznané kostce. Vytvoříme binární obrázek I indikující, které pixely mají barvu v tomto rozsahu. Nechť I 0 je jeho negace. Nechť O je obrázek vzniklý provedením eroze s malým kruhovým jádrem a dilatace s dvakrát větším jádrem na obrázku I 0 . Konečně P bude průnik obrázku O a I 0 . Obrázek P je tedy I 0 , ze kterého jsou odstraněny příliš malé oblasti. Potom budeme rozhodovat, které spojité oblasti v obrázku P odpovídají jedné z nálepek. Pro každou nálepku ověříme její velikost a tvar. Obrys nálepky aproximujeme čtyřúhelníkem pomocí Douglasova-Peuckerova algoritmu Ramer (1972). Pokud je odchylka aproximace příliš velká nebo pokud mají směrnice protějších stran moc velkou odchylku, nálepku zamítneme. Tímto jsme získali množinu čtyřúhelníků, které by mohly být nálepky. Ke každému čtyřúhelníku přiřadíme jeho barvu. To budiž barva pixelu v jeho středu. Tuto barvu zatím nijak neinterpretujeme, uložíme jenom hodnotu pixelu v barevném prostoru HSV. Přiřazení jedné z šesti barev se bude dít až v dalších krocích.

3.6

Přiřazení nálepek pozicím na kostce

Zaznamenání nálepek je velice neurčité. Mnoho nálepek může být zcela vynacháno a mnoho věcí označených jako nálepka může být něco na pozadí. Proto je odhadování orientace kostky věnována v této práci velká pozornost.

3.6.1

Základní kroky

Nejprve najdeme co největší skupinu nálepek, které jsou poblíž sebe, jsou podobně velké a mají podobný tvar. Budeme předpokládat, že to jsou nálepky z jedné stěny. Najdeme takové její umístění, které nejlépe odpovídá pozicím rozpoznaných nálepek v obrázku. Protože dokážeme odhadnout vzdálenost kostky od kamery podle velikosti nálepek na obrázku, dá se podle jedné stěny přibližně určit poloha dalších viditelných stěn. Těm přiřadíme nálepky, pokud na odpovídajících místech byly nějaké zaznamenány. 8

3.6.2

Klastrování

Mezi rovnoběžníky je potřeba najít takovou skupinu, která by mohla být stěnou kostky. Nálepky na jedné stěně mají dvě společné vlastnosti – mají podobně orientované strany a jsou blízko u sebe. Můžeme v tomto smyslu měřit podobnost nálepek. i-tou nálepku charakterizujme třemi dvourozměrnými vektory: vektor si bude poloha středu v obrázku. Další dva vektory pi , qi budou průměry vektorů protějších stran. Průměry protějších stran ve čtyřúhelníku ABCD jsou myšleny vektory (AB + DC)/2 a (BC + AD)/2. Volba těchto vektorů není jednoznačná, závisí na tom, který bod čtyřúhelníku budeme podle této definice považovat za A, jsou tedy čtyři možnosti přiřazení vektorů pi , qi čtyřúhelníku. Můžeme o nálepkách přemýšlet jako o bodech v šestirozměrném prostoru. Použijme heuristiku, že nálepky, které jsou si v tomto vektorovém prostoru blízké, budou s větší pravděpodobností na stejné stěně. Všimněme si, že je zohledněna nejen podobnost tvaru, ale i jejich vzdálenost v obrázku. To odpovídá očekávání, že nálepky, které jsou na jedné stěně, budou blízko sebe a budou mít podobný tvar a orientaci. Blízkost středů ale bude mít menší váhu, než podobnost tvaru. V takto zavedeném vektorovém prostoru můžeme počítat eukleidovskou vzdálenost. Aby heuristika fungovala správně, je nutné při hledání vzdálenosti nálepek i a j spočítat jejich euklidovské vzdálenosti pro všechny čtyři možné volby dvojice pj , qj a vybrat z nich minimum. Pro každou dvojici rozpoznaných nálepek vypočítáme jejich vzájemnou vzdálenost tak, jak jsme ji právě zavedli. Tím získáme matici vzdáleností nálepek D ∈ Rn×n , kde n je počet nálepek. Tato matice bude vstupem pro hierarchický klastrovací algoritmus. Použitou implementaci poskytl Lbehnke. Výstupem tohoto algoritmu je hierarchická struktura klastrů reprezentovaná jako strom. Provedeme řez tímto stromem na vhodné úrovni tak, aby počet klastrů byl co nejnižší, ale aby si byly nálepky v klastrech dostatečně blízké.

3.6.3

Určení první stěny

Když jsou nálepky rozděleny na klastry, vybereme ten největší z nich. Určíme v něm průměrné hodnoty vektorů p,q u jednotlivých nálepek. Tím získáme vektory charakterizující rovinu, ve které se nálepky nacházejí. Pokud použijeme vektory p,q jako bázi vektorového prostoru, budou v ní mít nálepky šířku i výšku přibližně 1. Vzdálenost středů sousedních nálepek bude v této bázi pro typické kostky přibližně r = 1,3. Pokud se opravdu jedná o nálepky na jedné stěně kostky, měl by přibližně platit následující vztah: pro každou dvojici středů nálepek na stěně si , sj charakterizované vektory p,q platí: ∃k,l ∈ {−2, − 1,0,1,2} : si ≈ sj + krp + lrq. Vybereme takovou nálepku, která splňuje tento vztah s nejvíce dalšími nálepkami z tohoto klastru. Pro všechna její možná umístění ve stěně zjistíme, kolik nálepek z klastru bychom mohli přiřadit jiné pozici ve stěně tak, aby s dostatečně malou odchylkou odpovídala tomuto vztahu. Pokud takto stěně přiřadíme dostatek nálepek, budeme s ní pracovat dále. Reprezentujme ji jako rovnoběžník.

9

Obrázek 3.2: Dvě možnosti, jak podle jedné stěny určit orientaci kostky.

3.6.4

Ostatní stěny

Je-li v ortogonální projekci krychle pevně určena jedna stěna, jsou dvě možnosti, jak narýsovat další dvě viditelné stěny. K jednoznačnému určení je totiž potřeba určit, který ze čtyř vrcholů rovnoběžníku bude projekcí toho vrcholu krychle, který je nejblíže pozorovateli. To nemůže být žádný z vrcholů s ostrým úhlem. Mohou to být ale oba vrcholy s tupým úhlem. Podle ortogonální projekce určíme rovnoběžníky, které odpovídají dalším viditelným stěnám. Na každé je devět míst, na kterých očekáváme nálepky. Pokud je projekce stěny dostatečně velká, přiřadíme každé pozici na stěně takovou nálepku, která je na dostatečně blízkém místě a má dostatečně podobný tvar očekávanému tvaru. Pokud je projekce stěny příliš malá, budeme ji zcela ignorovat. Obraz kostky v náhledu kamery telefonu nebo počítače odpovídá perspektivní projekci. Díky tomu, že dokážeme odhadnout vzdálenost kostky od kamery, můžeme převést krychli z ortogonální projekce do perspektivní projekce, která v obrázku vypadá lépe a přesněji předvídá pozice nálepek.

3.7

Určení barvy nálepky

Úloha rozhodnout, jaké barvy je daná nálepka, je překvapivě nejednoznačná. Stejná hodnota pixelu totiž může v různém kontextu znamenat různé věci. Červená v teplejším světle může mít stejnou barvu jako oranžová v chladnějším světle. V určitých světelných podmínkách může být dokonce žlutá zcela nerozlišitelná od bílé. Proto nestačí parametry rozlišující mezi barvami jenom přesně nastavit, ale musí se pro co nejrobustnější fungování i přizpůsobit kostce a osvětlení. Pro porovnávání barev je použit barevný prostor HSV. Každá z šesti rozpoznávaných barev nálepky má pevně daný povolený rozsah hue, saturation a value. Barvy, které tímto způsobem budeme rozpoznávat, jsou červená, oranžová, žlutá, zelená, modrá a bílá.

3.8

Bílé nálepky na bílé kostce

Kostky s bílým tělem jsou poměrně rozšířené a jsou velkou výzvou pro rozpoznávání, protože bílé nálepky jsou na bílém těle obtížně zaznamenatelné. Proto 10

bílé nálepky nerozpoznáváme v první fázi algoritmu spolu s ostatními nálepkami, ale až po určení orientace kostky v prostoru. Pro všechna místa na kostce, kde je očekávána nálepka, ale žádná nebyla rozpoznána, zjistíme, jestli se jedná o bílou nálepku – zjistíme, jestli dostatek pixelů v dané oblasti je v rozsahu odpovídajícím bílé barvě. Proto algoritmus rozpoznává obtížněji stěny, na kterých je hodně bílých nálepek.

11

4. Navigování Navigování program provádí, pokud už úspěšně proběhlo rozpoznání, tedy pokud už máme k dispozici nějaký model kostky, který odpovídá nějakému možnému zamíchání a který má vyplněné všechny nálepky. Při navigování program říká uživateli, jaké má dělat tahy, aby kostku poskládal.

4.1

Nalezení postupu složení

Když je dokončeno rozpoznávání a je tedy k dispozici úplný model, proběhne nalezení posloupnosti tahů, která povede ke složení kostky.

4.1.1

Kociemba two-phase algoritmus

Zatímco běžné postupy skládání kostky lidmi vyžadují obvykle více než 50 tahů, Kociemba two-phase algoritmus umožňuje najít nejvýše dvacetitahové řešení jakékoli kostky během několika vteřin. Více o tomto algoritmu je na stránce http://kociemba.org/cube.htm. Takové řešení vždy existuje, důkaz viz Rokicki (2013).

4.1.2

Algoritmus two-phase+

Algoritmus na nelezení dvacetitahového řešení two-phase v první fázi poskládá kostku tak, že bílé nálepky jsou buď na stěně s bílým středem, nebo na stěně se žluým středem. Podobně zelené jsou buď na stěně se zeleným středem, nebo na stěně s modrým středem a červené buď na stěně s červeným, nebo na stěně s oranžovým středem. Jinými slovy je každá nálepka buď na správné stěně, nebo na protější. Ve druhé fázi jsou všechny tahy o 180◦ , takže se tento invariant zachovává, tedy po každém tahu platí, že každá nálepka je buď na svojí stěně, nebo na protější. Jak bylo rozebráno v kapitole 3, rozpoznávání zanáší hodně chyb a snadno se může stát, že jsou nějaké barvy zaměněny. A to se stává nejčastěji právě mezi bílou a žlutou, mezi modrou a zelenou a mezi červenou a oranžovou, tedy mezi barvami, které jsou na kostce naproti. Proto v druhé fázi občas může dojít k chybě prvního druhu, tedy k falešnému rozpoznání tahu, protože se mezi tahy vzhled kostky mění jenom málo. Je možné kvůli větší robustnosti použít algoritmus two-phase+, který najde řešení na nejvýše 21 tahů, což není optimální, ale tahy jsou z hlediska počítačového vidění snáze rozpoznatelné. Využívá následující myšlenky: Algoritmus two-phase dokáže najít dvacetitahové řešení z jakéhokoli validního zamíchání. Validní zamíchání jsou právě ty permutace nálepek, které můžeme dostat ze složené kostky pomocí základních tahů. Protože jsou validní permutace Rubikovy kostky grupa, jsou uzavřené na skládání. Jinými slovy dostat se z jednoho stavu do druhého je nějaká permutace, která odpovídá vyřešení nějaké zamíchané kostky. Tedy z jakéhokoli stavu

12

se můžeme dostat pomocí dvaceti tahů nejen do složeného stavu, ale i do jakéhokoli jiného, viz Rokicki (2013). Najdeme postup, jak ze zadané kostky získat pomocí dvaceti tahů kostku, která bude zcela složená až na poslední tah U’, neboli až na otočení horní vrstvy o 90◦ proti směru hodinových ručiček. K tomu stačí vhodně změnit barvy vstupních nálepek. Kostka se skládá ze čtyř druhů kostiček - rohových (těch, ze kterých jsou vidět tři stěny s nálepkami), hranových (ze kterých jsou vidět dvě) a středových, ze kterých je vidět jen jedna. Každá kostička je unikátní - na žádných dvou nejsou stejné nálepky. O tahu U’ tedy můžeme přemýšlet nejen jako o permutaci nálepek, ale i jako o permutaci kostiček. Když místo složené kostky chceme dostat kostku slouženou až na jeden tah, stačí každou kostičku nahradit za kostičku, na jejíž místo se po tahu U’ dostane. Většina kostiček tedy zůstane stejná, jenom kostičky s bílou nálepkou se změní. Tím dostaneme nějaký jiný validní stav kostky, pro který najdeme algoritmem two-phase řešení. Kdybychom v získané kostce přejmenovali jednotlivé kostičky zpátky, dostali bychom kostku složenou až na poslední tah U’. Z toho je vidět, že nalezená posloupnost tahů použitá na nepřejmenovanou kostku dosáhne přesně toho, co jsme potřebovali. Když k ní totiž přidáme na konec tah U’, jedná se o složení kostky na nejvýše 21 tahů bez problému špatně rozlišitelných stěn ve druhé fázi.

4.1.3

Inverzní two-phase

Jiný způsob, jak se vyhnout dlouhé posloupnosti tahů o 180◦ na konci je najít inverzní permutaci kostky, najít řešení pro ni a to provést pozpátku. Takové řešení bude začínat posloupností tahů o 180◦ , ale to nijak nebrání rozpoznávání a ve většině případů bude končit tahem o 90◦ , takže se tím náš problém vyřeší. Není to ale ve všech případech, v některých případech může i takto získané řešení končit posloupností tahů o 180◦ , v takovém případě je vhodné použít algoritmus two-phase+.

4.2

Rozpoznání

Rozpoznávání je nutné dělat i v navigační fázi, aby bylo možné správně nakreslit šipky přímo do náhledu kamery. Oproti první fázi teď ale nový model nemění průběžný model, protože ten považujeme za správný. Rozpoznávání probíhá tak, že se v obrázku z náhledu kamery nejprve najdou čtyřúhelníky, které by mohly být nálepky kostky a ty se přiřadí pozici na kostce. Tento proces je podrobněji rozepsán v kapitole 3. Pokud jsme získali nějaký částečný model z aktuálního náhledu kamery, pokusíme se jej spojit s modelem očekávané kostky. Je 24 způsobů, jak to udělat. Orientace kostky je totiž jednoznačně určena tím, která stěna je nahoře a jakým směrem je otočená. Nahoře může být jedna z šesti stěn a otočená může být čtyřmi způsoby. Vyzkoušíme všechny možnosti a zvolíme tu, kde se modely nejlépe překrývají. To se děje následovně: Máme dva modely kostky, jeden úplný a jeden neúplný. Ten neúplný zafixujeme a u úplného budeme postupně měnit jeho orientaci. Na 13

každé stěně je devět nálepek, na celé kostce je jich 54. Pro každou z nich zjistíme, zda si na daném místě nálepky v obou modelech odpovídají (mají stejnou barvu), nebo jestli si odporují (mají různé barvy), nebo jestli je jedna z nich neznámá. Za odpovídající si nálepky se bude přičítat k celkovému ohodnocení, za odporující si se bude odčítat, jestliže je nálepka na daném místě v jednom modelu neznámá, nijak ohodnocení nezmění. Ze všech 24 možností vzájemné orientace zvolíme tu s nejlepším ohodnocením a pokud přesahuje nějakou prahovou hodnotu, budeme ji považovat za správnou. Tímto zjistíme, jak průběžný model orientovat tak, aby odpovídal kostce, co je vidět na obrázku z náhledu kamery. Protože je už v této fázi známo, jaké tahy je potřeba udělat ke složení kostky, můžeme do obrázku přesně nakreslit šipky znázorňující, kterou stěnu má uživatel otočit.

4.2.1

Ověření tahu

Zároveň je potřeba dostatečně spolehlivě rozpoznávat, zda byl tah proveden. Proto kromě průběžného modelu, zkoušíme paralelně rozpoznávat i model takové kostky, jakou bychom dostali po správném provedení tahu. Pokud je přiřazena s výrazně lepším ohodnocením, budeme předpokládat, že byl tah proveden. Na tomto místě přichází v úvahu zkoušet rozpoznávat i špatné tahy, tedy když uživatel pohnul jinou stěnou, než měl, nebo pohnul jiným směrem. Možných tahů je ale 18. To dělá ověřování časově náročné a navíc může zanášet zbytečné chyby, když algoritmus nesprávně zaznamená špatný tah. Při ověřování provedení tahu může nastat chyba dvou druhů. Chyba prvního druhu (false positive) nastává, když tah nebyl proveden, ale algoritmus řekne, že ano. Chyba druhého druhu (false negative) nastává, když tah byl proveden, ale algoritmus to nezaznamená. Chyba prvního druhu je v tomto případě mnohem horší. Pokud je algoritmus o krok napřed před uživatelem, bude mu radit špatné tahy a nebude moci správně rozpoznávat kostku, protože to, co je na skutečné kostce, neodpovídá modelu očekávané kostky. To má skoro jistě za následek, že kostku už vůbec nepůjde složit a bude nutné začít zcela od začátku a znovu ji naskenovat. Proto jsou parametry při rozhodování nastaveny tak, aby dávaly přednost chybě druhého druhu, jež znamená jenom mírné zdržení. K tomu, abychom se chybě prvního druhu s co největší jistotou vyhnuli, musí provedení tahu nasvědčovat nejen poslední snímek, ale i několik po sobě jdoucích předchozích snímků.

4.2.2

Otočení modelu kostky

Při porovnávání dvou modelů kostky je potřeba jeden z nich otáčet. Otočení kostky znamená změnění orientace celé kostky. Je to tedy něco jiného než tah. Otočení modelu kostky je jednoznačně určeno tím, která stěna má být nahoře a tím, jak má být otočená. Otočení modelu kostky je ekvivalentní nějaké permutaci nálepek.

14

5. Uživatelská dokumentace 5.1

Instalace

K instalaci programu na Android použijte přiložený instalační soubor MistrKostky.apk. Před prvním spuštěním programu na počítači je potřeba nejprve nainstalovat OpenCV verze 2.4.12 a Ant. Ve složce MistrKostkyPC spusťte příkaz: ant -DocvJarDir=cesta/k/adresáři/bsahujícímu/soubor/opencv-2412.jar -DocvLibDir=cesta/k/adresáři/obsahujícímu/nativní/knihovnu/opencv Tedy například: ant -DocvJarDir=C:/opencv/build/java/ -DocvLibDir=C:/opencv/build/java/x86 Tím by se program měl zkompilovat a spustit. Program potřebuje 300 MB operační paměti.

5.2

Podrobný návod na použití

Na stránce http://www.ms.mff.cuni.cz/~spanelm a v příloze je video demonstrující používání tohoto programu. Pro nejlepší fungování algoritmu je potřeba zvolit dobře osvětlenou místnost, nejlépe se silným nepřímým bílým světlem. Na volbě pozadí příliš nezáleží, jednobarevné pozadí ale může v některých případech snížit chybovost a zvýšit rychlost. Program by měl podporovat většinu standardních kostek s běžnými barvami nálepek, tedy kostky, které po úspěšném složení mají takto barevné stěny: žlutá nahoře, bílá dole, modrá vepředu, oranžová vpravo, zelená vzadu a červená vlevo. Problematické pro rozpoznávání jsou kostky s reflexními nálepkami a kostky s tak velkými nálepkami, že mezi nimi jsou velmi malé mezery. Ovládání programu se skládá ze dvou kroků: detekce a navigace. Po zapnutí programu jste na začátku detekční fáze a program rozpoznává rubikovu kostku.

5.2.1

Detekční fáze

Během detekční fáze není povoleno dělat žádné tahy. Kostka se smí pouze otáčet celá. Je potřeba kostku postupně plynule ukázat ze všech stran. Obzvláště důležité jsou záběry, ve kterých jsou vidět dvě nebo tři stěny najednou, protože jenom ty nesou informaci o tom, jak jsou stěny umístěny vzájemně. Pokud vše probíhá správně, uživatel během detekce vidí kostku nakreslenou do náhledu, která znázorňuje, které nálepky byly úspěšně rozpoznány. Kromě toho vidí ukazatel říkající, kolik procent kostky už je úspěšně rozpoznáno. Jakmile je rozpoznáno 100%, automaticky se přejde do druhé fáze a uživatel uvidí šipky znázorňující první tah, který má udělat.

15

5.2.2

Navigační fáze

V této fázi může uživatel opět ukazovat kostku z jakéhokoli úhlu a program přímo do obrazu kostky bude kreslit šipky znázorňující další tah potřebný ke složení kostky. Po otočení příslušné vrstvy kostiček je nutné nechat program ověřit jeho úspěšné provedení ukázáním změněné stěny nebo stěn.

16

6. Programátorská dokumentace Program Mistr Kostky je napsán v Javě. Zdrojové soubory jsou ke stažení na adrese www.ms.mff.cuni.cz/~spanelm/ a jsou přiloženy k této práci. Je také přiložena vygenerovaná dokumentace javadoc ve formátu HTML, která slouží jako hlavní dokumentace programu. Kompilace programu je popsaná v kapitole 5.1.

6.1

Rozdělení tříd

Program se skládá ze tří balíčků: algorithms, datastructures a gui. Balíček datastructures obsahuje třídy týkající se reprezentace kostky a třídu Parameters, která spravuje všechny parametry jednotlivých algoritmů programu. Nejdůležitější třídy v balíčku algorithms jsou BodyRecognizer, StickerDetector, Visor a Analyser, které se starají o jednotlivé vrstvy rozpoznávání Rubikovy kostky, třída Thinker spravující hledání řešení zamíchané kostky a třída Drawer umožňující kreslit do snímku překryvnou vrstvu s rozpoznanou kostkou. Balíček gui se implementací liší u mobilní a počítačové verze a obsahuje třídy zodpovědné za vykreslování okna v případě počítače a aktivity v případě telefonu. Třída Main získává pravidelně nové snímky z kamery a předává je objektu Analyzer. Ten do snímku dokreslí překryvnou vrstvu a upravený snímek je předán gui.

6.2

Reprezentace kostky

Reprezentace rubikovy kostky a operace na ní jsou ústřední částí programu. To se děje v rámci následující struktury: Objekt Cube reprezentuje celou kostku. Implementuje operace otočení kostky a provedení tahu, umožňuje přistupovat k barvám a mírám jistoty jednotlivých nálepek a také umožňuje vynutit konsistenci kostky, viz kapitola 3. Každá instance třídy Cube obsahuje šest instancí třídy Face a každá z nich obsahuje devět instancí třídy Sticker. Indexují se tak, jak je popsáno v kapitole 3. Třída Cube se používá pro reprezentaci kostky bez informace o jejím umístění ve snímku. V případech, kdy je potřeba pracovat i s umístěním a orientací kostky je použit její potomek - CubeRelative, jenž obsahuje instance objektů FaceRelative a ty obsahují instance StickerRelative.

6.3

Algoritmy

Algoritmy jsou podrobněji popsány v předchozích kapitolách, tato kapitola uvádí především rozdělení jednotlivých částí algoritmu do tříd.

6.3.1

Analyser

Na nejvyšší úrovni pracuje objekt Analyser. Ten spravuje model kostky a průběžně jej aktualizuje ve funkci analyse volané pro každý nový snímek znovu. 17

Volá funkci Visor, od které získá seznam několika instancí třídy CubeRelative, které reprezentují rozpoznané kostky. Více jich je kvůli tomu, že Visor nedokáže vždy kostku rozpoznat jednoznačně a proto vrací několik možných výsledků. Analyser zvolí jeden podle toho, jak dobře odpovídá očekávanému modelu a podle toho, s jakou jistotou byly rozpoznány jednotlivé nálepky.

6.3.2

Visor

Analyser obsahuje instanci objektu Visor, která se používá především při každém volání funkce analyse k rozpoznání kostky. Ústřední funkcí ve třídě Visor je detect. Ta dostane na vstupu zmenšený snímek z náhledu kamery a vrátí seznam několika možností, jak může být orientovaná kostka na obrázku a jaké může mít barvy nálepek. Visor získá seznam rozpoznaných nálepek od objektu StickerDetector a pomocí klastrovacího algoritmu z balíčku Lbehnke. mezi nimi vybere skupinu nálepek s podobným tvarem a velikostí na obrázku. V této skupině vybere několik možností, jak může v obrázku být umístěna příslušná stěna, na níž rozpoznané nálepky jsou. Pro každou pozici první stěny zjistí obě dvě možné předpokládané polohy dalších stěn. Do každého takto vzniklého modelu kostky zahrne nálepky, které jsou na očekávaných místech a podle toho, jak dobře odpovídají očekávanému tvaru a pozici jim přiřadí míru jistoty. Do vyšší úrovně projde jenom několik modelů kostky s nejlepší mírou jistoty.

6.3.3

StickerDetector

StickerDetector zajišťuje rozpoznání nálepek v obrázku. K tomu slouží funkce detect, která najde pomocí morfologických transformací vždy několik oblastí jednolité barvy a pomocí funkce detectStickers vybere ty z nich, které mohou odpovídat nějaké nálepce.

6.4

Externí knihovny

Program využívá externí knihovnu OpenCV, která nabízí funkce týkající se počítačového vidění. Tato knihovna je pod licencí 3-clause BSD License. Dále je použita knihovna apporiented clustering Lbehnke com.apporiented.algorithm.clustering , která poskytuje klastrovací algoritmy potřebné pro nalezení stěny kostky podle zaznamenaných nálepek. Pro nalezení řešení na 20 tahů je použit balíček org.kociemba.twophase , který je vydán pod licencí Apache License, Version 2.0. Je k dispozici na internetové stránce Kociemba.

18

Závěr Splnění cílů Tato práce měla za cíl vytvořit program, který bude co nejlépe rozpoznávat Rubikovu kostku a v reálném čase uživatele navigovat. Program funguje a umožňuje bez obtíží kostku během půl minuty naskenovat a během minuty ji složit a to v počítačové i mobilní verzi.

Výjimečné prvky programu Hlavní, čím je tato práce výjimečná, je schopnost rozpoznávat kostku z jakéhokoli úhlu a rozpoznávat více stěn najednou. Díky tomu se dosáhne velmi robustního rozpoznávání, protože se jednotlivé náhledy na kostku překrývají a při rozpoznávání je díky tomu velká redundance měření, díky které je možné snáze odhalovat chybně rozpoznané části kostky. Také je díky tomu fáze rozpoznávání pro uživatele pohodlnější, protože se nemusí řídit instrukcemi o tom, jak kostku otáčet, jako u jiných aplikací využívajících počítačové vidění pro rozpoznání kostky. Zde stačí kostku otáčet plynule libovolnými směry, podobně, jako by se ukazovala člověku. Stejně tak při skládání můžeme držet kostku otočenou jakkoli. Další výjimečnou částí je opravování nesprávně rozpoznaných částí kostky na základě znalostí o uspořádání nálepek na kostičkách Rubikovy kostky. To řádově snižuje pravděpodobnost, že bude kostka rozpoznána nepsrávně. Dokáže také spolehlivě rozpoznávat i kostky s bílým tělem a bílými nálepkami, které jsou poměrně rozšířené, ale pro počítačové vidění obtížně rozpoznatelné.

Hranice možností Program není zcela dokonalý. Spolehlivost rozpoznávání závisí na kvalitě kamery a na osvětlení, pohodlnost pro uživatele zase závisí na výkonu zařízení. Rozpoznávání je výpočetně náročné. Na počítačích běží plynule, ale na méně výkonných telefonech trvá až v řádu stovek milisekund. Program také nerozpoznává správně některé kostky, které mají méně obvyklé odstíny barev nálepek nebo jsou jinak atypické.

Srovnání s existujícími aplikacemi Nejlepší aplikace, které využívají počítačové vidění pro asistenci s Rubikovou kostkou jsou CubeCheater a Rubik Cube Wizard. CubeCheater byl vydán pouze pro iOS. Funguje tak, že naviguje uživatele postupně k zaznamenání šesti stěn a potom ukazuje animaci Rubikovy kostky znázorňující jednotlivé tahy. Rubik Cube Wizard rozpoznává Rubikovu kostku podobnou metodou jako CubeCheater, tedy dává uživateli instrukce, jak má postupně kostku otáčet a

19

rozpoznává stěny jednu po druhé. Při navigaci uživatel musí držet kostku v jednom určitém úhlu, otáčet stěny podle instrukcí a zadávat do programu ručně, že byl proveden tah. Rubik Cube Wizard ale už využívá prvků rozšířené reality. Rozpoznává, jak je přesně kostka orientovaná a podle toho okolo ní kreslí šipky. Program Mistr Kostky, o kterém je tato práce vyžaduje minimum interakce s uživatelem. Jediné, co musí uživatel dělat, je při rozpoznávání ukázat kostku jakkoli tak, aby ji program viděl postupně ze všech úhlů. Při navigování program kreslí šipky znázorňující tahy přímo na kostku, kterou rozpozná bez ohledu na to, jak je natočená.

Další práce Program je napsaný v Javě. Protože jednou z jeho slabin je rychlost, mělo by smysl jej přepsat do C++. Zároveň to, co dělá, pro uživatele není příliš zajímavé. Umožňuje složit kostku nejrychlejším možným způsobem, ale bez porozumění. Proto by pro uživatele bylo zajímavé, kdyby umožňoval i výuku algoritmů na skládání Rubikovy kostky. V tom má program velký potenciál, protože umožňuje elegantně přímo na kamerou zachytávané kostce znázorňovat tahy a třeba zvýrazňovat důležité vzory, které v průběhu algoritmu na kostce vznikají. Dále by se dala vylepšit grafika programu. V současnosti je vykreslovaný obraz velice minimalistický, grafika by mohla být mnohem hezčí.

20

Seznam použité literatury Ant, A. http://ant.apache.org. Kociemba. http://kociemba.org. Lbehnke. https://github.com/lbehnke/. OpenCV. http://opencv.org. Ramer, U. (1972). An iterative procedure for the polygonal approximation of plane curves. Computer graphics and image processing, 1(3), 244–256. Rokicki, K. (2013). The diameter of the Rubik’s cube group is twenty. SIAM J. Discrete Math, 27(2).

21

Přílohy Na přiloženém DVD jsou následující přílohy: • Zdrojové soubory k PC verzi ve složce MistrKostkyPC v podobě projektu pro eclipse • Zdrojové soubory k aplikaci pro Android ve složce MistrKostkyAndroid v podobě projektu pro Android Studio • Video demonstrující funkčnost programu demo.mp4 • Spustitelný program pro PC MistrKostkyPC.jar • instalační soubor pro Android MistrKostky.apk

22