PŘÍRODOVĚDECKÁ FAKULTA UNIVERZITY PALACKÉHO KATEDRA INFORMATIKY
BAKALÁŘSKÁ PRÁCE
Vzájemné rozpoznávání robotů Khepera III
2011
Tomáš Smékal
Místopřísežně prohlašuji, že jsem celou práci včetně příloh vypracoval samostatně.
2. červen 2011
Tomáš Smékal
i
Anotace V práci se zabývám možnými způsoby vzájemného rozpoznávání robotů, jejich výhodami a nevýhodami. Dále hardwarovou vybavenost robotů Khepera III s rozšiřujícím modulem Korebot LE a implementací algoritmů pro rozpoznání robotů pomocí kamery, včetně porovnání různých typů algoritmů.
ii
Děkuji panu Mgr. Martinu Dostálovi, Ph.D. za odborné vedení bakalářské práce a mnoho cenných rad a podnětů.
iii
Obsah 1. Úvod
1
2. Použité technologie 2.1. Khepera III . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Představení robota . . . . . . . . . . . . . . . . 2.1.2. Hardware . . . . . . . . . . . . . . . . . . . . . 2.1.3. Operační systém . . . . . . . . . . . . . . . . . 2.1.4. Pohyb . . . . . . . . . . . . . . . . . . . . . . . 2.1.5. Orientace v prostoru . . . . . . . . . . . . . . . 2.1.6. Komunikace . . . . . . . . . . . . . . . . . . . . 2.2. IP kamera ANC-606G . . . . . . . . . . . . . . . . . . 2.3. WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4. SSH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5. Wget . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Jazyk C . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7. Knihovny pro Khepera III . . . . . . . . . . . . . . . . 2.7.1. Khepera III toolbox . . . . . . . . . . . . . . . 2.7.2. Libkorebot . . . . . . . . . . . . . . . . . . . . . 2.7.3. Vlastnosti Khepera III v porovnání s libkorebot 3. Metody řešení 3.1. Uložená mapa . 3.2. Pohyb překážky 3.3. RFID . . . . . 3.4. Kamera . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4. Řešení problému 4.1. Datové struktury a jejich základní funkce . . . . . 4.2. Pohyb . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Segmentace obrazu . . . . . . . . . . . . . . . . . 4.3.1. Nalezení žádaných barev . . . . . . . . . . 4.3.2. Nalezení a vyhodnocení barevných ploch . 4.3.3. Nalezení barevné plochy . . . . . . . . . . 4.3.4. Hledání hran . . . . . . . . . . . . . . . . 4.3.5. Nalezení přímek (Houghova transformace) 4.4. Kompletace algoritmů . . . . . . . . . . . . . . . 4.5. Omezení a jejich možná řešení . . . . . . . . . . . 4.6. Ovládání . . . . . . . . . . . . . . . . . . . . . . . 4.7. Uvedení do provozu . . . . . . . . . . . . . . . . . 4.8. Praktická ukázka: rozbor videa . . . . . . . . . .
i
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
2 2 2 3 3 3 3 4 5 5 6 6 6 7 7 7 8
. . . .
9 9 9 10 11
. . . . . . . . . . . . .
12 12 13 14 14 18 18 18 19 20 21 21 22 22
Závěr
24
A. Obsah přiloženého DVD
25
ii
Seznam obrázků 1. 2. 3. 4. 5.
Robot Khepera III . . . . . . . . . . . . . . . . . . . . . . . . . . 2 LED kontrolky Khepera III . . . . . . . . . . . . . . . . . . . . . 4 Prahování: 1. Původní obrázek 2. Černobílý obrázek 3. Otsuova metoda (spočítaný práh=169) 4. Ruční nastavení prahu (práh=155) 14 1. Původní obrázek 2. thresholdRightColor1 3. thresholdRightColor2 4. thresholdRightColor3 (v rámečku nalezení roboti) . . . . . 17 Hledání hran: 1. Vyříznutá nalezená oblast 2. Operátor Prewitové 3. Sobelův operátor 4. Laplaceův operátor . . . . . . . . . . . . . 19
iii
Seznam tabulek
iv
1.
Úvod
Roboty jako pomocníky při různých výrobních procesech využívá lidstvo již několik desetiletí. V posledních letech se však dostávají i k běžným lidem, jako jsou třeba robotické vysavače nebo sekačky na trávu. Těchto robotů bude i nadále do budoucna přibývat. V dalších letech se dokonce plánují i robotická auta, která nebudou potřebovat k provozu řidiče, a také proto je důležitá jejich vzájemná identifikace, aby o sobě věděli a mohli spolu vzájemně pracovat ve společném prostředí. Cílem této práce je tedy navrhnout a implementovat jednoduchý systém, jak by se takoví roboti mohli v budoucnu identifikovat. První kapitola seznamuje s technologiemi, které jsem při vývoji použil. Pojednává o vybavenosti, konstrukci, možnostech pohybu a použití robotů Khepera III současně s rozšiřujícím modulem Korebot LE. Dále se zabývá IP kamerou ANC-606G a nastavením, jaké je ve výsledku použito. Vysvětluje WiFi jako použitý způsob ovládání a komunikace s jednotlivými roboty. Nakonec pojednává o použité knihovně Khepera III toolbox, co všechno obsahuje, jak se používá a porovnává ji s knihovnou libkorebot. Ve druhé kapitole se čtenář seznámí s několika návrhy, jak je možné problém rozpoznávání vyřešit. Jednotlivé metody jsou popsány a následně zhodnoceny jejich výhody a nevýhody. Navíc je přidán komentář, proč jsem si danou metodu vybral nebo nevybral. Třetí, poslední, kapitola se zabývá již konkrétním řešením vyhledávání v obraze získaného z kamery. Postupně se probírají jednotlivé algoritmy, které jsem využil nebo testoval. Algoritmy, které nejsou ve výsledné aplikaci využity, porovnávám s těmi, které použité jsou. Na konci kapitoly je způsob, jakým jsou jednotlivé algoritmy začleněny v cílové aplikaci.
1
2.
Použité technologie
Pro tuto práci jsem využil robotů Khepera III s modulem Korebot LE. V každém robotu, přesněji modulu Korebot LE, je již předinstalován operační systém Linux.
2.1. 2.1.1.
Khepera III Představení robota
Robota Khepera III vyrábí a prodává švýcarská firma K-Team Corporation [?].
Obrázek 1. Robot Khepera III Legenda k obrázku 2.1.1.: 1. Infračervené senzory 2. Ultrazvukové senzory 3. Hlavní sériový konektor 4. USB miniAB konektor 5. Napájecí konektor 6. Reset 7. ON/OFF přepínač 8. Sériový konektor 2
2.1.2.
Hardware
Konstrukce je navržena tak, že jednotlivé desky plošných spojů se součástkami se dají na sebe stohovat. Tím lze robota rozšířit o zařízení, jako jsou kamery, senzory, mechanické ruce a jiné. Robot se skládá ze dvou základních desek. Na jedné jsou umístěny motory s koly, infračervená čidla, procesor a flash paměť. Zespodu se do desky připevňuje baterie, která drží na malých magnetech. Na spodní straně baterie je noha z tvrdé gumy. Druhá deska je umístěna nad první a jsou zde umístěny pouze ultrazvukové senzory. Veškerá elektronika robota je pak ukryta v plastovém krytu, jak je vidět na obrázku 1.. Po stranách vyčnívají infračervená čidla a roboti se jimi zachytávají o překážky. Čidla mohla být ukryta tak, aby nevyčnívala, byla by tím chráněna před mechanickým poškozením. Přidáním další desky zvané Korebot LE robota vybavíme rychlejším procesorem, větší pamětí RAM i flash, konektorem Compact Flash, do které je možné připojit např. WiFi modul a nakonec i operačním systémem Linux. Robot i s Korebot LE je řízen procesorem XScale s hodinovým kmitočtem 400 MHz. K dispozici má 64 MB paměti RAM a 32 MB paměti typu flash. Napájení je zajišťované baterií typu LiIon o kapacitě 1400 mAh. Ke komunikaci se využívá bezdrátový přenos pomocí WiFi a Bluetooth a sériové rozhraní USB nebo RS232. Dále je k dispozici 11 infračervených a 5 ultrazvukových čidel. 2.1.3.
Operační systém
V doplňující desce, zvané Korebot LE, je nainstalován operační systém Linux s Kernelem verze 2.6. Konkrétně: Linux korebot 2.6.25.7-kb1. Výhodami využití operačního systému jsou, mimo jiné, jednodušší programování, díky možnostem použití vestavěných knihoven, multitasking (více procesů současně) a umožňuje nespouštět aplikace okamžitě po zapnutí robota a umožňuje přihlášení více uživatelů najednou a nastavení jejich práv. 2.1.4.
Pohyb
Pohyb obstarává dvojice kol, hnací sílu jim zajišťují dva stejnosměrné servomotory s inkrementálním čítačem (pro posun kola o 1 mm je zapotřebí 22 pulsů). Maximální rychlost je 0,5 m/s. K zajištění stability je využito třetí nepohyblivé gumové nohy. Zatáčení je řešeno změnou rychlosti jednotlivých kol. 2.1.5.
Orientace v prostoru
K orientaci v prostoru a vyhýbání se překážkám, slouží 9 infračervených senzorů vzdálenosti, umístěných po obvodu těla robota. Senzory jsou, podle specifikace, použitelné do vzdálenosti 30 cm, reálně jsou použitelné pouze do cca 15 cm. Rozdíl oproti specifikaci je způsobený dvěma faktory – proměnnou intenzitou 3
okolního světla při průjezdu prostředím a vlastnostmi překážky (typ a barva), od které se paprsek světla odráží. Dva infračervené senzory jsou umístěny i na spodní straně robota, které slouží k určení, zda robot nejede mimo podložku. Pro určení předmětů ve větší vzdálenosti slouží pět ultrazvukových senzorů, umístěných na přední polovině robota. Ty lze použít na vzdálenost od 20 cm do 4 m. Kromě těchto čidel lze k orientaci využít různá přídavná zařízení. Při mé práci jsem využíval síťové kamery. Může jít o jakýkoliv typ a nemusí jít ani o síťovou kameru, jediným kritériem je dostupnost ovladačů pro Linux. 2.1.6.
Komunikace
Komunikaci s okolím (řídící počítač, ostatní roboti, síťové kamery) je možné zajistit, jak drátově (sériovým rozhraním), tak i bezdrátově(WiFi, Bluetooth). Při drátovém spojení můžeme využít, sériových linek pracujících s TTL úrovněmi, slouží pouze ke komunikaci s robotem bez modulu Korebot LE. Je možno využít rozhraní USB až do rychlosti 115 kb/s, nebo RS232. Jedná se o starší, mnohem jednodušší rozhraní než je USB, které má pomalejší přenos dat a nepodporuje plug&play (připojení zařízení za běhu). Pokud chceme využít bezdrátového spojení, což je výhodné kvůli mobilitě robota, můžeme si vybrat mezi technologií Bluetooth nebo WiFi (více popsáno v kapitole 2.3.).
Obrázek 2. LED kontrolky Khepera III Legenda k obrázku 2.1.6.: 1. Stav ovladačů motorů (červená) 2. Napájení ON/OFF (zelená) 3. Dokončeno nabíjení (zelená) 4. Nabíjení (červená) 4
5. Programovatelná (zelená) 6. Programovatelná (červená)
2.2.
IP kamera ANC-606G
Kamera je od firmy Affrey. ANC-606 se vyrábí ve dvou verzích ANC-606V a ANC-606G, obě verze mají ethernet 10/100 Mbps, přičemž G verze má navíc WiFi modul ve verzi 802.11g. Kamera byla dodána společností K-Team včetně montážního držáku a desky spojů k zapojení přímo do robota. Deska slouží pouze k držení kamery a k napájení z baterie. Nevýhodou je velká spotřeba a také, že kamera je poměrně těžká, takže motory se dost zahřívají. Kamera má 1/4” velký CMOS senzor o rozlišení 640x480. Video streamuje ve formátu MPEG4 a rychlosti 30 snímků/sekundu a je nastavitelný ve 3 různých rozlišeních 640x480, 320x240 nebo 160x120. Přímo v kameře běží webové rozhraní, ke kterému se dostaneme jednoduše přes prohlížeč zadáním IP adresy kamery, jehož pomocí můžeme měnit nastavení kamery. Video lze ukládat přímo na FTP server, pro výhodnou archivaci záznamů. Umožňuje nastavit 3 detekční okna. Záznam se začne nahrávat až se v daném okně změní obraz. Toto lze nejlépe využít u zabezpečovacích kamer.
2.3.
WiFi
Robotem získávané obrázky z kamery, spouštění robotů a jejich zpětná odezva, to vše probíhá výhradně pomocí WiFi spojení, kde roboti, kamery a řídící počítač jsou připojeny k jednomu přístupovému bodu. WiFi je název zaměnitelný s technickým termínem IEEE 802.11. Provoz je veden v bezlicenčním pásmu 2,4GHz. I díky tomu se rozšířilo natolik, že jej výrobci dávají do mnoha zařízení od notebooků, mobilních telefonů až po tiskárny a televize. V některých lokalitách je problém se silným zarušením celého pásma, což výrazně omezuje propustnost (rychlost) sítě, vznikají výpadky a v některých případech dokonce úplně síť vyřadí z činnosti. Jedná se o standard určený pro lokální bezdrátové sítě, kdy zajišťuje propojení bezdrátových zařízení a dále jejich připojení do lokální sítě. V dnešní době se ještě navíc využívá i pro bezdrátové připojení k Internetu. Existují dva způsoby vytvoření sítě: Ad-hoc a infrastrukturní síť. U obou se pro rozlišení sítě používá identifikátor SSID (Service Set Identifier), jedná se o řetězec 32 ASCII znaků. Při připojování klienta je nutné znát SSID, jinak není možné spojení navázat. • Ad-hoc je spojení dvou přímo propojených zařízení, které se vzájemně vidí (přímý rádiový dosah). Využívá se pro sítě o dvou zařízeních, případně příležitostná spojení. 5
• Infrastrukturní síť je tvořena jedním nebo více přístupovými body (AP acces point). AP mohou být mezi sebou spojeni bezdrátově, nebo ve většině případů klasicky drátově, zaručující vyšší spolehlivost i rychlost. Uživatelé se připojují k jednotlivým AP podle SSID, případně podle síly signálu. Vzhledem k tomu, že komunikace je přenášena prostorem do všech stran, je poměrně snadno zachytitelná i nežádoucími osobami, a proto je potřeba síť zabezpečit. Možností je několik a je dobré je kombinovat. • Skryté SSID: nevysílání identifikátoru sítě. • Blokování MAC adres: povolení jen některých síťových karet v síti. • WEP: šifrování přenosu, dnes nedostačující. • WPA: vylepšené WEP šifrování, při správně zvoleném hesle dostatečné. • WPA2: založené na AES šifrování. V dnešní době nejlepší dostupný způsob.
2.4.
SSH
SSH neboli Secure shell, je program, který umožňuje vytvořit šifrované vzdálené spojení (tzv. tunel) mezi dvěma zařízeními. Tento tunel nabízí přístup k příkazovému řádku, dovoluje přenášet velké množství dat oběma směry a kompletně spravovat vzdálené zařízení. Dovoluje také nastavit bezeztrátovou kompresi. Nahradil zastaralý Telnet, kdy hlavním důvodem změny bylo zabezpečení spojení.
2.5.
Wget
Wget [?] je program, který je určen pro stahování souborů ze sítě. Podporuje protokoly HTTP, HTTPS a FTP. Umožňuje stahovaní jednotlivých souborů i celých adresářových struktur. Zvládá také stahování pouze částí souborů, jako jsou například hlavičky HTML souborů. Zvládá také stahování přes nestabilní spojení, pokud je spojení přerušeno, tak počká než bude znovu obnoveno a soubor stáhne od místa přerušení. Program Wget má spoustu dalších možností nastavení a stahování, já jej však používám pouze pro stažení jednoho obrázku z IP kamery, další možnosti jsou na dokumentačních stránkách [?].
2.6.
Jazyk C
Pro programování robota využívám jazyk C společně s knihovnou Knihovna Khepera III toolbox (viz. 2.7.1.). Programovací jazyk C vytvořila v 70. letech dvojice amerických programátorů Denis M. Ritchie a Brian W. Kernighan [?]. Vytvořený standard běžně označovaný jako K&R nahradil v roce 1988 dodnes používaný standard ANSI C. Vlastnosti: 6
• Největší výhodou jazyka je přenositelnost na různé počítače a operační systém, pokud je zdrojový kód správně napsaný a využívá pouze standardní knihovny. Relativně jednoduchá tvorba překladače. • Jazyk je nízkoúrovňový, je strukturovaný a má velké množství operátorů. • Pro většinu úloh je efektivnější a rychlejší než stejná úloha napsaná v jiném jazyce. • Další vlastností, někdy výhodnou někdy ne, je absence garbage collectoru. Výhodou je to u menších aplikací, kdy programátor přesně ví, kdy a jaká paměť se alokuje/uvolňuje. U větších programů je mnohem těžší až nemožné udržet si naprosto přesný přehled o paměti, v těchto případech je garbage collector velice užitečný. Garbage collector si zabírá výpočetní čas procesoru a u pomalejších zařízení ani není vhodné jej používat. V dnešní době se používá pro programování, např. jednočipů, ostatních zařízení, spíše nízkoúrovňových, pro které nemá smysl vytvářet překladače pro vysokoúrovňové jazyky a nakonec také v případě potřeby vysoké rychlosti programu (realtime systémy).
2.7.
Knihovny pro Khepera III
Při programování robota Khepera III v jazyce C se můžeme spolehnout na své vlastní schopnosti a veškerou komunikaci s hardwarem si naprogramovat sami, nebo využít jedné ze dvou knihoven, pro robota již napsaných. 2.7.1.
Khepera III toolbox
Knihovna je určena pro jednodušší práci a programování robotů Khepera III [?]. Obsahuje různé skripty pro nastavení robota, jako je například nastavení WLAN, SSH, nebo vytváření nových modulů. Dále obsahuje různé moduly, které můžeme využít ve svých programech. Jedná se o ovládání I2C rozhraní, parsování příkazové řádky, ovládání motorů včetně měření vzdálenosti ujeté každým kolem zvlášť, zjišťování hodnot senzorů a některé další, které nevyužívám. V knihovně jsou také vyhotoveny různé příklady využití snad všech možností knihovny, které výrazně pomáhají nejen začínajícím programátorům robotů Khepera III. Knihovna je psaná konkrétně pro robota Khepera III. 2.7.2.
Libkorebot
Firma K-team dodává více druhů robotů nejen Khepera III. Knihovna libkorebot je psaná pro všechny tyto roboty a je tedy napsaná obecně, aby pokryla
7
všechny rozdíly jednotlivých robotů. Z toho vyplývají určité nevýhody vůči Khepera III toolbox (více 2.7.3.). Funkcionalita se však oproti Khepera III toolbox nijak neliší. 2.7.3.
Vlastnosti Khepera III v porovnání s libkorebot
• Jednodušší API. Jako příklad vezmeme načtení hodnoty infračerveného senzoru. – U Khepera III toolbox zavoláme funkci khepera3 infrared proximity(), která zjistí a uloží hodnoty senzorů do pole khepera3.infrared proximity.sensor. Odtud si můžeme zjistit hodnotu konkrétního senzoru podle jeho indexu. – Libkorebot čte zprávy od senzorů přes I2C sběrnici a programátorovi je dodává pouze uložené v bufferu. Programátor pak musí buffer zpracovat a hodnoty každého senzoru zvlášť získat. Kód se tak stává příliš složitým a hlavně špatně čitelným. • Spuštění více programů současně. Libkorebot s tím vůbec nepočítá, a proto při přístupu dvou a více programů současně k hodnotám senzorů je téměř jisté, že hodnoty budou špatné. Naopak Khepera III toolbox s touto možností počítá. Knihovna totiž komunikuje se senzory a ovladači pomocí atomických funkcí (je zajištěno provedení celé operace – ostatní procesy do ní nemohou vstoupit). Hodnoty tedy vrací správné i v případě více spuštěných programů současně. Pokud bychom se však snažili ovládat motory dvěma programy současně, tak by robot nefungoval správně, protože by pozdější proces přepsal nastavení procesem předchozím. • Obě knihovny jsou rychlostně srovnatelné, protože obě dvě čtou hodnoty a odesílají příkazy periferním jednotkám (senzory, motory, . . . ) přes I2C sběrnici. • Libkorebot neobsahuje žádné srovnatelné skripty pro nastavení robota. • Khepera III toolbox, má několik menších testovacích programů, které pokrývají téměř veškerou funkcionalitu knihovny, zatímco program khepera3 test z libkorebot je jeden program, který obsahuje několik testovacích algoritmů současně. Při použití khepera3 test si programátor nejdříve ve zdrojovém souboru vyhledá, kde se příklad nachází, poté jej společně se všemi proměnnými zkopíruje do své aplikace. Výhoda khepera3 test je v tom, že si programátor vezme konkrétní příklad, který chce řešit a ihned může zdrojový soubor použít ve své aplikaci.
8
3.
Metody řešení
Tato kapitola se zabývá metodami rozpoznání ostatních robotů a jejich výhodami i nevýhodami.
3.1.
Uložená mapa
Jedním ze způsobů je předem každému robotu uložit mapu prostředí, ve kterém se bude pohybovat a jeho startovní pozici na mapě. Robot pak z pohybu svých motorů pouze přepočítává svoji pozici na mapě. V případě, že narazí na překážku, kterou nemá na mapě zaznamenanou, zjistí od ostatních jejich pozici na mapě, z čehož odvodí koho potkal. Mapu by si mohl robot vygenerovat i sám tím, že by si projel prostředí a ukládal si polohu překážek. Samozřejmě by musel v daném prostředí být sám, bez ostatních robotů. Výhody • Snadné a rychlé vyhodnocení, o kterého robota se jedná. Nevýhody • Složité navrhování a převedení mapy ze skutečného prostředí do podoby pro robota vhodné. • Jakákoliv změna v prostředí by znamenala nutnost znovu překreslit i mapu v robotovi. • Před každým vypuštěním robota bychom museli zjistit a oznámit robotovi jeho výchozí pozici. Hlavně z důvodu dlouhé přípravy, před samotným startem robotů, jsem tuto možnost velice brzo zavrhl. Její použití je vhodné v systémech s neměnným prostředím.
3.2.
Pohyb překážky
Dalším možným řešením je určování pomocí pohybu překážky. Příklad: Robot přijede k překážce. Pokud zjistí, že se překážka snaží uhnout, naváže komunikaci s některým z robotů a pomocí smluvených pohybů zjistí, jestli se doopravdy jedná o správného robota. Vzhledem k postupnému navazování komunikace a domlouvání se s roboty, kteří se mohou vyskytovat úplně jinde, se tak může stát, že správný robot mezi tím ujede. Muselo by se to řešit například zastavením všech robotů.
9
Výhody • Nezávislé na prostředí. Nevýhody • Dlouhé a složité rozpoznávání, kterého robota potká. • Možné problémy v případě pohyblivých překážek. • Složitá implementace. • Se vzrůstajícím počtem robotů roste i čas na jejich rozpoznání. Implementace by byla příliš složitá a navíc samotné určení správného robota by bylo pomalé. To jsou hlavní důvody, proč jsem se nerozhodl pro tento způsob.
3.3.
RFID
RFID - Radio Frequency Identification, rádio-frekvenční identifikace. Jedná se o čip, který po přiblížení snímače vyšle jedinečný kód (více informací o technologii [?]). Jelikož roboti tento čip nemají již od výroby, musel by se každému robotu doplnit jak snímač, tak čip. Anténu snímače bych umístil kolem těla robota a čip připevnil na přední část robota. V případě přiblížení se robotů, by snímač přijal kód sousedního robota, podle kterého by jej dokázal poznat. Problém by mohl nastat, když roboti k sobě nepřijedou vždy tak, aby se načetly kódy u obou robotů. Tzn. robot, který přijal kód, by musel navázat spojení a sdělit své označení druhému robotu. Výhody • Snadné a rychlé vyhodnocení, o kterého robota se jedná. • Nezávislé na prostředí. • Snadná softwarová implementace Nevýhody • Nutnost doplnění hardware o snímač i identifikační čip RFID. Tento způsob je již velice dobrý a řekl bych, že i ideální. Ovšem bohužel potřeba osazení drahého snímače pro každého robota mi neumožnila tento způsob realizovat.
10
3.4.
Kamera
Poslední možností je využití kamery. Každý robot bude mít na sobě připevněnou kameru, ze které si bude stahovat jednotlivé snímky, které se následně zpracují a určí, jestli na nich nejsou ostatní roboti. Ti by se samozřejmě od sebe museli nějak fyzicky odlišovat. Například barevnými proužky, různými znaky nebo textem. Čím složitější útvar na rozpoznání, tím je také obtížnější jej rozpoznat a s tím roste i čas, který robot potřebuje na samotné zpracování jednotlivého snímku. Ovšem u jednodušších objektů, jako je třeba pouze barevné odlišení, je problém se světelnými podmínkami, kdy jedna stejná barva může za různých světelných podmínek vypadat jinak. Výhody • Možnost využití pro rozpoznávání mnoha dalších objektů. • Se vzrůstajícím počtem robotů zůstává čas na jejich rozpoznání stejný. Nevýhody • Potřeba roboty odlišit vzhledem. • Rozpoznání nemusí být správné. • Velká časová náročnost na rozpoznání. • Potřeba složitých matematických algoritmů. Tento způsob jsem si vybral, kvůli jeho možnosti rozšíření (viz kapitola 4.).
11
4.
Řešení problému
Aplikaci pro rozpoznávání robotů jsem rozdělil do dvou vláken. První vlákno zajišťuje pohyb robota, vyhýbání se překážkám a uživatelské ovládání procesu. Druhé vlákno již řeší samotný problém rozpoznávání.
4.1.
Datové struktury a jejich základní funkce
Základní a nejdůležitější datovou strukturou je struktura pojmenovaná Bitmap. V této struktuře jsou uloženy informace o načteném obraze. Je to velikost obrazu (šířka, výška), ukazatele na pole s obrazem a pole s pomocnými informacemi a nakonec příznak černobílého obrazu. Samotný obraz je uložen jako jednorozměrné pole, kde jednotlivé pixely, které jsou reprezentovány složkami červená, zelená, modrá, jsou řazeny postupně za sebou ve tvaru RGBRGB. . . Navíc jsou za sebou řazeny i řádky, tzn. tam, kde skončí jeden řádek, tak bezprostředně za ním začíná další řádek. Pro přístup k jednotlivým pixelům jsem vytvořil dva typy jednoduchých funkcí. Důvodem k tomu byla nutnost vypočítat ze souřadnic přesné umístění bodu v poli, a omezení možné chyby při častém používání přístupu k jednotlivým pixelům. Jeden typ je pro získání hodnoty barevné složky pixelu podle zadaných souřadnic. A druhý typ je pro nastavení hodnot barevných složek podle souřadnic a daných hodnot. Na stejném principu je ve struktuře vloženo další pole, které znovu představuje pixely v obraze, ale slouží pro označení si programem, jestli daný pixel již nebyl jednou vyhodnocen. Pixely jsou již reprezentovány jedním číslem. I v tomto případě jsou vytvořeny pomocné funkce. Jsou pro zjištění prošlého pixelu a pro jeho nastavení (logická 1) a vynulování (logická 0). Obě pole nejsou fyzicky ve struktuře, ale je na ně odkazováno pomocí ukazatelů. Alokují se až v momentě, kdy jsou skutečně potřeba. Poslední položkou ve struktuře je označení, jestli je obraz černobílý. V tomto případě se používá pouze červená barevná složka, jinak se používá jako v předešlém případě. Při používání struktury Bitmap se musí dodržet určitý postup. Pro vytvoření nové struktury se musí zavolat funkce bitmapNew, která vrací ukazatel na novou strukturu. Kromě vytvoření nové struktury funkce ještě vynuluje všechny své proměnné a hlavně ukazatele nastaví na NULL. To je důležité pro ověřování, jestli je již vytvořeno pole obrazu a v případě požadavku na vytvoření nového, aby se uvolnilo původní pole. Další funkce bitmapInit slouží pro samotnou inicializaci. Uloží si zadanou šířku a výšku a podle nich vytvoří samotné pole pro obraz. Navíc ještě zkontroluje a případně uvolní pozůstatky starších obrazů. Po dokončení používání struktury se nakonec použije funkce bitmapEnd, která uvolní všechny prostředky ze struktury. Další struktura ShareAttr je ovládací a je určena ke komunikaci mezi vlákny. Obsahuje proměnnou pro nastavení ukončení, tzn. obě vlákna dokončí činnost 12
cyklu a skončí. Druhá proměnná je pouze pro předání IP adresy kamery od ovládacího vlákna k vláknu pro rozpoznávání. Více proměnných neobsahuje, ale bylo by možné ji doplnit např. o proměnnou pro rychlost, kdy by si uživatel mohl za běhu programu nastavovat rychlost robota. Histogram je struktura obsahující pouze jednorozměrné pole o velikosti 256 prvků. Slouží pro uložení, histogramu obrazu. Tuto strukturu nakonec nepoužívám, jelikož byla využívána v algoritmech prahování, které ve výsledné aplikaci nejsou využity (více v kapitole 4.3.1.). Poslední struktura Pen slouží pro uložení informací při kreslení do obrazu, jako je barva a tloušťka. V aplikaci jsem vytvořil jednoduché funkce pro kreslení obdélníku, křížku a čar, ve kterých je struktura použita. Funkce používám pouze pro potřeby ladění programu a zobrazení do výsledného obrazu, v kterých místech daného robota nalezl.
4.2.
Pohyb
Pohyb robota je díky knihovně Khepera III toolbox velmi snadný. Na začátku programu se provede inicializace obou motorů, zadá se rychlost, jakou se mají jednotlivé motory otáčet a robot se pohybuje zadanou rychlostí a směrem. Změna směru a rychlosti se provede zadáním jiných hodnot. Pro zatáčení se zadají pro každý motor různé hodnoty. Rychlost se mění změnou hodnot pro oba motory. Záporná hodnota znamená, že se robot pohybuje dozadu, kladná dopředu. Díky tomu, že ovládám každý motor zvlášť, tak je robot velice obratný a může se otočit i na místě. V aplikaci jsem použil pouze infračervené senzory, protože se roboti mají pouze vyhýbat překážkám a na to jsou tyto senzory dostačující. Pro vzájemné aktivní vyhledávání robotů by bylo výhodné použití ultrazvukových senzorů, aby měl robot větší dosah na překážky a ostatní roboty. Algoritmus funguje tak, že se nejprve zjistí maximální rychlost, kterou můžeme nastavit při spuštění aplikace argumentem -s. Potom jsou v nekonečné smyčce postupně procházeny hodnoty na senzorech, porovnávají se s nastavenými konstantami a poté podle stavu senzorů je určena rychlost pro jednotlivé motory. V aplikaci jsem nepotřeboval, aby se robot snažil dostat na nějaké konkrétní místo, nebo jezdil přesně podél překážek, ale stačilo, aby se robot v prostoru bezpečně pohyboval. Proto jsem nemusel řešit přesné výpočty pohybu robota, např. přesné pootočení o 90◦ . V principu robot zjišťuje, jestli se náhodou nepřibližuje z jedné strany k překážce. Pokud ano, tak začne zatáčet na opačnou stranu. Téměř vždy je však v prostředí, ve kterém se robot pohybuje, spousta rohů, zákoutí a úzkých průjezdů. V těchto případech by algoritmus nefungoval správně. Např. pokud by robot přijel do rohu, tak by se zablokoval, protože by se snažil zatočit na opačnou stranu než detekuje překážku. V tomto případě by ji však detekoval na obou stranách, a tak by se zablokoval, nebo by do překážky narazil. Proto bylo potřeba algorit13
mus ještě rozšířit o tyto zvláštní případy. Případ, kdy se robot dostane do rohu, jsem vyřešil jednoduše tak, že robot se začne na místě otáčet doleva, tak dlouho, dokud platí, že je blokovaný z obou předních stran. V případě, kdy robot pomocí podlahových senzorů zjistí blížící se konec podložky, robot o kousek couvne a pootočí se doleva přibližně o 90◦ . Posledním případem, který se musí ještě řešit odděleně, je pohyb v úzké uličce. Problém vzniká opět detekcí překážky po obou stranách, jenže v tomto případě ji nedetekuje zepředu. Problém tedy řeším tak, že pokud se hodnoty na jedné, případně obou stranách nedostanou pod určitou hodnotu (přílišné přiblížení se k překážce), tak nechám robota jet rovně. Když se přiblíží více než je nastavená prahová hodnota, tak využije otočení se o cca. 180◦ . Celkově je řešení konkrétních situací seřazeno v cyklu podle jejich důležitosti. První je ověření podlahových senzorů, následně pak příjezd do rohu, ulička a nakonec běžný pohyb volným, případně z jedné strany ohraničeným prostředím.
4.3.
Segmentace obrazu
Získávání informací z obrazu je obecně výpočetně náročné. Proto jsem se rozhodl problém rozpoznání robotů co nejvíce zjednodušit. Na kamery robotů jsem připevnil barevné pruhy pro každého robota s jinou barvou. Díky tomu, že jsem měl k dispozici čtyři roboty, tak jsem barvy zvolil v závislosti na jednotlivých složkách jednoho pixelu kamery, tj. červená, zelená, modrá. Pro čtvrtou barvu se nabízela kombinace dvou z těchto tří barev – žlutá, azurová nebo fialová. Z těchto barev jsem nakonec vybral fialovou, a to proto, že žlutá se dost vyskytuje v pozadí (dřevěné bariéry), a ze základní modré se za určitých světelných podmínek stává azurová. 4.3.1.
Nalezení žádaných barev
K detekci jednotlivých vybraných barev jsem použil algoritmus prahování, který jsem částečně upravil.
Obrázek 3. Prahování: 1. Původní obrázek 2. Černobílý obrázek 3. Otsuova metoda (spočítaný práh=169) 4. Ruční nastavení prahu (práh=155) Algoritmus prahování [?] využívá hodnotu jasu k oddělení objektů v popředí od objektů v pozadí. Vychází z předpokladu, kdy jednotlivé objekty mají stejnou, 14
nebo podobnou odrazivost světla po celé své ploše. Funguje to tak, že se určí hodnota prahu a poté se procházejí jednotlivé pixely. Pokud je hodnota jasu menší než práh, potom se hodnota pixelu nastaví na 0, pokud je jas stejný nebo větší, nastaví se na 1. Vznikne jednobarevný obraz, jehož pixely jsou jednobitové, buď nastaveno, nebo nenastaveno. Hodnota prahu se dá nastavit ručně, kdy pokaždé, když algoritmus spustíme, se rozhoduje podle stejného prahu. Nebo se hodnota prahu vypočítá automaticky, to se práh určuje před každým spuštěním znovu. Většinou algoritmy získávají práh z analýzy histogramu, ve kterém předpokládají dva hlavní vrcholy, popředí a pozadí. Histogram je graf počtu stejných jasových hodnot. Způsobů automatického nalezení prahu je několik, viz. [?]: • Metoda automatického hledání prahu Je založena na postupném hledání prahu jako průměru středních hodnot oblastí odpovídajících popředí a pozadí. 1. Určíme si počáteční odhad prahu Tpoc , jako průměr mezi minimální Jmin a maximální hodnotou Jmax jasu Tpoc = T0 =
Jmin + Jmax 2
(1)
Kde n je krok výpočtu, n = 0. 2. Rozdělíme obraz dle Tn na dvě množiny, první s hodnotami jasu menšími než Tn a druhou s hodnotami většími než Tn . 3. Spočítáme průměrné hodnoty jasu v obou množinách 4. Určíme nový práh Tn+1 jako průměr hodnot jasu v obou množinách 5. Pokud platí |Tn −Tn+1 | > 0, 5 inkrementujeme n a pokračujeme s nově nastaveným prahem znovu od bodu 2 do doby nalezení prahu T . • Metoda nalezeni optimálního prahu (Otsuova) Toto řešení navrhl Otsu a v praxi se používá tak, že v původním rozdělení hledáme dvě nová rozdělení co nejdále od sebe. Jedno rozdělení odpovídá pozadí a druhé popředí. 1. Stanovíme počáteční práh Tpoc = T0 =
Jmin +Jmax 2
2. Spočítáme součet pravděpodobností jasu ω0 a střední hodnotu μ0 v první oblasti. T −1 p(k) (2) ω0 = k=0
μ0 =
T −1 kp(k) k=0
15
ω0
(3)
3. Spočítáme součet pravděpodobností jasu ω1 a střední hodnotu μ1 ve druhé oblasti. L−1 p(k) (4) ω1 = k=T
μ1 =
L−1 k=T
kp(k) ω1
(5)
4. Spočítáme střední hodnotu v původním rozdělení μT . μT =
L−1
kp(k)
(6)
k=0
5. Hledáme maximální hodnotu mezitřídního rozptylu. σ 2 = ω0 (μ0 − μT )2 + ω1 (μ1 − μT )2
(7)
• Lokální prahování Používá se v případě rozdílných hodnot jasu v různých částech objektu, protože v tomto případě by globální práh nedával správné výsledky. Lokální prahování zohledňuje různé hodnoty jasu v různých částech obrazu a pro tyto typy obrazu dává daleko lepší výsledky. Prakticky se provádí tak, že se sleduje okolí každého bodu v obraze, z něhož se určí práh a až podle tohoto prahu se určí hodnota bodu. Okolí je určeno maskou dané velikosti, která se pohybuje po obraze. Pro zjištění prahu v daném okolí se používá některá z metod pro určení globálního prahu. Ve svém programu jsem implementoval více algoritmů prahování. Prahování s ručně nastaveným prahem a hledání optimálního prahu Otsuovou metodou. Nakonec se však nehodil algoritmus ani jeden (viz. obrázek 3.), a protože mám na robotech použité konkrétní barvy, zaměřil jsem se přímo na ně. Postupně jsem navrhl tři algoritmy založené na principu prahování. Nazval jsem je toThresholdRightColor, každý s číselným indexem na konci. Jak název napovídá, mají za úkol nalézt požadované barvy použité na robotech. Rozdíl je vidět na obrázku 4. První byl upravený algoritmus konstantního prahování. Jediná změna byla v porovnávání s hodnotou prahu všemi třemi barevnými složkami. Hlavní nevýhodou byl výstup, který byl jednobarevný. Proto by se později, po detekci objektu robota, musela znovu hledat barva, kterou objekt vlastnil. Další nevýhoda spočívala ze samotného konstantního prahování. Při nedostatku světla jsou snímané barvy tmavé a ty pak tento algoritmus nenalezne. Druhý měl za úkol odstranit problém s tmavými barvami. Je nejvíce podobný lokálnímu prahování, ale pixely neporovnává s jejich okolím. Porovnává pouze 16
hodnoty svých barevných složek. Nejprve vybere jednu barvu (červenou) a označí ji jako dominantní a zároveň si poznačí počet nalezených barev na 1. Potom zbylé dvě barvy postupně porovná s dominantní tak, že pokud je jas dané barvy v daném rozmezí od barvy dominantní, tak přičte 1 k nalezeným barvám. V případě, že je vyšší než dosavadní dominantní barva, tak ji označí jako dominantní. Nakonec nastaví pixel na černou nebo bílou barvu, podle počtu nalezených barev, které jsou podobného jasu. Při jednom nebo dvou barvách, nastaví pixel na bílou, jinak na černou. Bohužel původní odhad, kdy měl algoritmus fungovat i pro dvě barevné dominantní složky se nenaplnil a funguje dobře pouze pro jednu barevnou složku.
Obrázek 4. 1. Původní obrázek 2. thresholdRightColor1 3. thresholdRightColor2 4. thresholdRightColor3 (v rámečku nalezení roboti) Třetí algoritmus vychází ze druhého, ale funguje už i pro dvě barevné složky. Navíc zachová a obnoví svou barvu (dostane ji k maximálním hodnotám). Algoritmus si uchovává indexy hlavní a vedlejší barvy. Je to podobné jako u druhého algoritmu, jenom místo jedné barvy si pamatuje dvě a místo hodnoty barvy si pamatuje její index. Začíná pracovat podobně. Nastaví obě hodnoty indexů na 0 (červená), potom postupně porovnává další dvě barvy. Pokud je barva menší než barva vedlejší o více než je povolený rozptyl, pak se tato barva úplně vynechá, nemá vliv na hlavní barvy našeho zájmu. Když je naopak barva větší než hlavní barva, zase bráno i s povoleným rozptylem, pak se tato barva nastaví jako hlavní i jako nejnižší zároveň. Když naopak bude barva v rozptylu, pak se nastaví jako hlavní nebo jako vedlejší podle velikosti a inkrementuje se počet barev. Na konci se nastaví pixel na barvu podle indexů. Pro tu, která je v indexech zastoupena se zapíše 255, pokud není, tak 0. Dále ještě ve struktuře bitmapy označí černé pixely, na již vyřešené. Vychází z toho, že tam, kde je černý pixel nemůže být žádný hledaný objekt. Zjednoduší se a hlavně zrychlí se tím algoritmy, které se budou provádět následně. Jednou z výhod tohoto řešení ještě je, že můžu filtrovat některé barvy. Tohoto využívám, protože robot jezdí v prostředí, kde jsou dřevěné (žluté) zátarasy. Jednoduchým porovnáním indexů tak zjistím, jestli se nejedná o žlutou barvu a tu můžu snadno vymazat. Nakonec moje algoritmy nemají s výše popsanými, běžně používanými algoritmy moc společného. Ovšem výsledek je stejný, tj. nalezení jednotlivých objektů.
17
4.3.2.
Nalezení a vyhodnocení barevných ploch
Jakmile máme nalezené barvy jednotlivých pixelů, je potřeba je spojit do jednotných celků a zanalyzovat. K tomuto účelu jsem napsal funkci searchColorCamp. Ta funguje kaskádově, prochází jednotlivé pixely a provádí testy. Po každém testu pustí test další nebo v cyklu pokračuje dalším kolem. První krok otestuje, jestli je aktuální pixel již vyřešen. Pokud není, může jít k nalezení velkých stejnobarevných ploch. 4.3.3.
Nalezení barevné plochy
Funkce colorCampSize, k tomu naprogramovaná, je rekurzivní a vrací oblast nalezené plochy a počet bodů, které plocha obsahuje. Vstupní parametry funkce jsou bitmapa, souřadnice procházeného pixelu, hledaná barva a oblast. Nejprve vyhodnotí vyřešenost bodu kvůli následnému všesměrovému rekurzivnímu posunu. Tady opět platí – pokud je vyřešený, tak jej dál neřeší. Následně porovná svou barvu s barvou ze svých vstupních parametrů. Pokud se barvy nerovnají, funkce skončí a vrátí nulu. V opačném případě si do proměnné suma nastaví jedničku a pak k ní přičte návratové hodnoty ze zavolání sebe sama, s tím rozdílem, že souřadnice odpovídají sousedním bodům. Dále ještě je potřeba zkontrolovat a případně rozšířit nalezenou oblast. Funkce jednoduše zkontroluje, zda je bod v aktuální oblasti, a pokud není, tak oblast rozšíří tak, aby v ní byl. Nakonec nastaví bod jako vyřešen a vrátí proměnnou suma. 4.3.4.
Hledání hran
Jakmile máme oblast a suma barevných bodů v ní, provedeme test, jestli je suma, alespoň polovina ze všech bodů v oblasti. Důvodem je odstranění barevného šumu, který se občas rozprostírá na velkých plochách. Pro odstranění velkých skvrn, které nepatří do námi hledaného objektu jsem využil nalezení hran a z nich následně určení přímek v obraze. Pruhy na robotech jsou rovné. Proto by i ve výsledném obraze, pokud se jedná o robota, mělo být k nalezení dostatečně dlouhá a rovná hrana. Pro hledání hran jsem využil principu konvoluce [?]. Ta funguje tak, že máme masku h, která obsahuje číselné hodnoty. Masku postupně posouváme po obraze a po každém posunu se provede součin bodů obrazu s hodnotami v masce a spočítá se suma těchto součinů. Výsledná suma se uloží do nového obrazu g(x) kde x je pozice středu masky. Pro příklad masky obsahující tři hodnoty, uvažujeme jednorozměrný obrázek. g(x) =
1
h(s)f (x + s) = h(x − 1)f (x − 1) + h(x)f (x) + h(x + 1)f (x + 1) (8)
s=−1
Pro hledání hran jsem využil následujících masek. Rozdíl je vidět na obrázku 5.: 18
⎛
⎞ −1 0 1 ⎝ −1 0 1 ⎠ −1 0 1 Operátor Prewitové
⎛
⎞ −1 0 1 ⎝ −2 0 2 ⎠ −1 0 1 Sobelův operátor
⎛
⎞ 0 1 0 ⎝ 1 −4 1 ⎠ 0 1 0 Laplaceův operátor
Obrázek 5. Hledání hran: 1. Vyříznutá nalezená oblast 2. Operátor Prewitové 3. Sobelův operátor 4. Laplaceův operátor
4.3.5.
Nalezení přímek (Houghova transformace)
Ze získaného obrázku s hranami velikosti W ×H, kde W je šířka a H je výška, je potřeba zjistit, jestli se v něm vyskytují nějaké úsečky dostatečně dlouhé délky. Pokud se takové přímky v obraze vyskytují, je možné, že se jedná o pruh robota. K tomuto účelu jsem využil algoritmu Houghovy transformace [?]. Ten předpokládá prahovaný obraz, který jsme získali pomocí předchozích funkcí. Algoritmus využívá směrnicového vyjádření přímky, do kterého si dosadí hodnotu bodu a podle toho zjistí, jestli se bod na přímce vyskytuje. y = ax + b
(9)
Nedostatkem metody je případ, kdy se sklon přímky blíží k 90◦ , proto se v praxi využívá spíše vyjádření přímky v normálovém tvaru. r = x cos ϕ + y sin ϕ
(10)
Přímka je dána vzdáleností r a úhlem ϕ od bodu 0. Algoritmus si nejprve vytvoří dvojrozměrné pole tzv. akumulátor Accu všech možných přímek, které by v obraze mohly existovat. Velikost M × N je dána právě na základě úhlu ϕ = 180 a dvojnásobkem maximální vzdálenosti, tj. vzdálenosti protilehlých rohů obrazu √ 2 2 r = W + H . Nyní přejdeme k samotnému algoritmu: • Vynulujeme akumulátor Accu[ϕ, r] = 0 pro každé ϕ a r, kde ϕ = 1, 2, . . . , M a r = 1, 2, . . . , N. • Pro každý bod v obraze (xi , yj ), kde i = 1, 2, . . . , W a j = 1, 2, . . . , H rovnající se 1 a pro každou hodnotu ϕm ,m = 1, 2, . . . , M spočítáme rn = xi cos ϕm + yj sin ϕm a inkrementujeme Accu[ϕm , rn ]. • Po skončení algoritmu dostaneme v Accu[ϕm , rn ] počet nalezených bodů ležících na přímce danými parametry ϕm a rn . 19
Po provedení tohoto algoritmu se porovná maximální hodnota z Accu s danou konstantou, podle čehož se určí, zda je v obraze dostatečně dlouhá úsečka, která by mohla patřit pruhu na robotu. Pokud ano vypíše na obrazovku barvu nalezeného robota.
4.4.
Kompletace algoritmů
Jak již bylo uvedeno na začátku kapitoly, aplikace je rozdělena na 2 vlákna. První vlákno ovládá pohyb a uživatelský vstup a druhé načítání a zpracování obrázku z kamery. Po spuštění program vyhodnotí a uloží vstupní parametry. Inicializuje robota a následně vytvoří druhé vlákno, ve kterém spustí funkci ImageSegmentation a jako vstupní parametr předá strukturu ShareAttr. Poté program pokračuje do nekonečného cyklu, na jehož začátku testuje uživatelský vstup. • Pokud byl zadán požadavek na ukončení programu, nastaví příznak ukončení ve struktuře ShareAttr a vyskočí z cyklu, uvolní zdroje, počká na dokončení činnosti druhého vlákna a poté se ukončí. • V případě požadavku pro zastavení, se pouze nastaví příznak pro zastavení. Následně se testuje příznak pro zastavení, podle kterého se určí, zda se mají motory zastavit, nebo se naopak má pokračovat algoritmem pro pohyb (viz. kapitola 4.2.). Funkce ImageSegmentation běžící ve druhém vláknu nejprve vytvoří některé pomocné struktury, zejména pak strukturu Bitmap pojmenovanou image, do které bude ukládat obraz. Do příkazu, který bude volat, doplní adresu kamery, ze které bude načítat obrázky. Následně skočí do nekonečné smyčky, kdy na začátku zkontroluje příznak ukončení ze struktury ShareAttr, kterou dostal vstupním parametrem. Pokud je příznak nastaven na ukončení, z cyklu se vyskočí a uvolní všechny používané prostředky a skončí se. Pokud nastaven není, pak se nestane nic a pokračuje se v cyklu dále. Zavolá se do systému příkaz, který jsme si na začátku vytvořili a příkaz zavolá externí program Wget, který stáhne aktuální obrázek z kamery. Následně přijde na řadu funkce loadHalfImage. Ta má za úkol načíst do image ze zdrojového obrázku dolní polovinu. Dolní polovinu proto, že barevný pruh robotů se vyskytuje pouze ve spodní polovině obrazu a pokud tak není, nachází se stejně příliš daleko. Hlavní výhoda je ve výrazném zkrácení výpočetního času. Následně je volána funkce toThresholdRightColor3 (viz. kapitola 4.3.1.) a searchColorCamp (viz. kapitola 4.3.2.). Poslední jmenovaná vypíše barvu nalezeného robota na obrazovku, nebo pokud žádného nenajde, nevypíše nic. Navíc uloží pomocné obrázky na disk (FLASH paměť). Uživatel si tak může prohlédnout jednotlivé kroky celého procesu. Kvůli použití dvou vláken, bylo potřeba vyřešit, aby nemohly obě vlákna přistupovat v jeden čas ke sdíleným datům. Tento problém jsem vyřešil po20
mocí synchronizačního prostředku mutex (mutual exclusive). Mutex se používá tím způsobem, že se před vstupem do kritické části (sdílená data) zavolá funkce pthread mutex lock (zamknout) a po skončení kritické části pthread mutex unlock (odemknout). Vždy, když se program dostane do funkce pthread mutex lock, tak zjistí, jestli už není zamčené jiným vláknem. Pokud není, vlákno kritickou část uzamkne a pokračuje dál. Jakmile skončí práci s kritickou sekcí, znovu ji odemkne. Pokud je zamčená, tak čeká, dokud jej dané vlákno znovu neodemkne. Ve své aplikaci používám dva mutexy, jeden pro uzamykání struktury ShareAttr a druhý pro zamykání systémových a knihovních prostředků.
4.5.
Omezení a jejich možná řešení
Díky používání kamery jako rozpoznávacího zařízení je funkčnost celého systému závislá na dostatečném osvětlení (pokud možno denního) a také na kvalitě kamery. Kamera musí být kvalitní zejména ve věrném podání barev. Kamery, které jsem měl k dispozici, bohužel nejsou příliš kvalitní, obrázky byly často zašuměné a barvy zkreslené. Proto se někdy vyhodnocená barva robota lišila od skutečnosti. Algoritmus rozpoznávání má dále problémy, pokud se rozpoznávaný robot nachází ve stínu nebo je snímán proti světlu. V takovém případě je barva rozpoznávaného robota příliš tmavá a algoritmus ji nedokáže rozpoznat. Použití barev navíc neumožňuje použití více robotů najednou než pět nebo v případě nefiltrování žluté barvy v algoritmu šest (blíže vysvětleno v kapitole 4.3.1.). Ovšem největším problémem je vliv cizích předmětů na rozpoznávání. Často se stávalo, že roboti viděli v pozadí různé barevné předměty, knihy, červený potah židle (lze vidět na doprovodném videu). Možné řešení těchto problémů by bylo rozpoznávat roboty podle různých tvarů, například geometrické obrazce, tím si nepomůžeme v případě použití více robotů, ale vyřeší problém s nedokonalostí snímání barev. Pro využití více robotů by se musely použít složitější tvary, jako třeba písmo nebo čárový kód.
4.6.
Ovládání
Program má několik spouštěcích atributů pro nastavení základních požadavků. • -h Pouze vypíše základní informace o programu, tj. aplikace dále nepoběží. • -ip Nastavení IP adresy kamery, ze které bude stahovat obrázky. Výchozí nastavení je 192.168.1.101 • -s Nastavení základní rychlosti robota (5 – 12). Výchozí 8. • -f Při pohybu nebudou testovány podlahová čidla. 21
Při běhu programu má uživatel možnost zastavit/rozjet robota pomocí klávesy „p nebo „P . Zastaví se pouze motory, samotný proces rozpoznávání přerušen nebude. Pomocí klávesy „Enter je možné proces ukončit. Z ovládacích pokynů je to vše, ovšem je zde ponechán prostor pro další rozšíření – zvyšování/snižování rychlosti za běhu aplikace.
4.7.
Uvedení do provozu
K uvedení celé aplikace do provozu je potřeba nejprve připravit robota. Jako první musíme nainstalovat kameru. Kamera se přišroubuje k pomocné desce a pak se deska i s kamerou z vrchu zasune do robota. Dále, pokud nepoužíváme externí napájení, musíme mít plně nabité baterie robota, protože použitá kamera má velkou spotřebu. Robot s kamerou dokáže na jedno nabití jezdit maximálně kolem osmi minut, a asi od páté minuty se roboti výrazně zpomalí ve svých výpočtech, což má za následek občasné naražení na překážku nebo pomalejší vyhodnocení snímaných obrázků. Tento čas je bohužel celkem krátký, ale je ovlivněn hlavně stářím baterek robota a také použitou kamerou. Jakmile máme roboty připravené, můžeme je spustit. Roboti jsou přednastavení tak, že se po spuštění sami připojí do WiFi sítě s SSID Khepera a určenou IP adresou, každý robot ji má na sobě napsanou. Totéž dělají i kamery. Nahrajeme aplikaci „mutual identification , kterou najdeme na doprovodném DVD ve složce „bin , do robota. Následně se přihlásíme pomocí protokolu SSH ke každému z robotů (user: root, heslo: khepera) a aplikaci spustíme.
4.8.
Praktická ukázka: rozbor videa
Video je rozděleno na dvě hlavní části, vlevo je plocha, kde roboti jezdí a vpravo jsou tři okna, kde je zobrazován výpis jednotlivých robotů. Okna náleží od shora červenému, zelenému a modrému robotu. 0:08 - každý robot je spuštěn příkazem mutual identification -ip. Za -ip je dosazena konkrétní IP adresa kamer jednotlivých robotů. 0:16 - zelený robot je zastaven příkazem „p , protože má poškozené infračervené čidlo a příliš by narážel do ostatních robotů. 0:20 - zelený správně určí barvu blížícího se červeného robota, červený robot bohužel zeleného nerozpozná, jelikož jej snímá proti světlu a tak ho snímá příliš tmavého, viz. 4.5. 0:30 - modrý robot zahlásí, že vidí modrého robota, občas se tyto paradoxy stávají, když vidí v okolí jednobarevné předměty, v tomto případě modrá kniha na stole. Po otočení již správně rozpozná červeného robota. Červený správně určuje modrého robota. 1:24 - modrý rozpozná cizí předmět v pozadí. 2:10 - protože zelený robot nebyl kvůli protisvětlu rozpoznávaný, je přemístěn do protějšího rohu. 22
2:23 - modrý robot v protisvětle určil červeného robota jako purpurového, o chvíli později jej už určí správně. 3:22 - červený robot správně určí zeleného robota. 3:33 - modrý robot určí správně zeleného robota malinko se zpožděním, někdy robotům trvá vyhodnocení obrázku delší dobu. 4:00 - již se začíná projevovat pokles napětí baterie, snímky z kamery jsou od této chvíle méně kvalitní a procesor se začíná zpomalovat ve výpočtech. 5:45 - červený robot narazí do překážky, protože je zpomalení výpočtu příliš velké, tato chyba se zopakuje ještě několikrát. 5:50 - je vidět, že po přemístění zeleného robota tak, aby nebyl v protisvětle, je správně rozpoznávaný ostatními. 7:00 - od této chvíle kamery vracejí příliš špatné snímky a proto jsou také často špatně vyhodnocené. 8:08 - pomocí klávesy „enter ukončím běh aplikace na každém robotu zvlášť. Na videu je vidět, že se aplikace neukončí okamžitě po stisknutí klávesy, ale nejdříve se dokončí výpočet zrovna načteného obrázku.
23
Závěr Napsal jsem aplikaci, která dokáže řídit robota a zároveň rozpoznávat ostatní roboty v daném prostředí. Vybraný způsob vyhledávání barevných pruhů ostatních robotů z obrazu umožňuje použití relativně jednoduchých algoritmů. Zanechává však velký prostor pro zlepšení celého systému rozpoznávání, jako je použití různých obrazců. Práci jsem koncipoval tak, aby seznámila s technologiemi použitými při vývoji aplikace, s podrobně popsanými možnými postupy vyřešení zadaného cíle rozpoznávání robotů a zpracovaným postupem vývoje s porovnáním různých algoritmů.
24
Reference [1] Corporation, K.-T.: Khepera III. 2011, [Online]. URL
[2] Dobeš, M.: Zpracování obrazu a algoritmy v C#. Nakladatelství Ben, 2008, ISBN 978-80-7300-233-6. [3] Herout, P.: Učebnice jazyka C. Nakladatelství Kopp, 1993, ISBN 80-8582802-2. [4] RFID portál. 2011, [Online]. URL [5] GNU Wget 1.12 Manual. 2011, [Online]. URL [6] Khepera III Toolbox - Wikibooks, collection of open-content textbooks. 2011, [Online]. URL
25
A.
Obsah přiloženého DVD
V závěru práce je uveden obsah a struktura přiloženého DVD bin/ V této složce je spustitelný program mutual identification, který je nutné nahrát do jednotlivých robotů. doc/ Dokumentace ve formátu PDF a všechny zdrojové soubory potřebné pro její vygenerování. Dokumentace je vytvořena ze závazného stylu katedry informatiky Přírodovědecké fakulty. src/ Složka obsahuje zdrojové soubory programu mutual identification pro vytvoření spustitelné verze programu. data/ Ukázkové video demonstrující, jak rozpoznávání robotů funguje.
26