Esmeralda

Esmeralda :: Úvod

Esmeralda je výsledek zápočtové práce z předmětu Evoluční robotika na Matematicko-fyzikální fakultě Univerzity Karlovy. Cílem semináře bylo seznámit se tvorbou robotů a v praxi se utkat s problémy, které během této krásné činnosti mohou nastat.

Já, protože se nerad kladu nízké cíle (zřejmě podvědomně rád padám na ústa), jsem se rozhodl oprášit a trochu rozšířit svoje zkušenosti s knihovnou OpenCV a se zpracováním obrazu z kamery v reálném čase. Původní plány zahrnovaly téměř robotický fotbal (najít na obrazovce míček a dotlačit ho do branky), naštěstí se ale časem redukovaly na jednodušší (čti splnitelný) cíl dojet na místo určené na obraze.

Esmeralda :: Hardware

Obvyklý postup při vývoji robota na zápočet z tohoto předmětu byl hrát si během semestru s Lego Mindstorm a při té příležitosti z něj sestavit zápočtového robota. To bohužel ale moc neodpovídá obvyklému pracovnímu postupu při získávání zápočtů (totiž celý semestr se flákat a všechny pedagogy obtěžovat až poslední týden v září), proto jsem se s tímto postupem nemohl spokojit.

Úspěšně se mi dařilo práci na robotovi odsouvat až do chvíle kdy jsem zjistil, že zápočet je nutné získat během posledního týdne semestru, neboť zodpovědná osoba odlétá na celé prázdniny a září někam do zahraničí. Na půjčování Lega a kompletní vývoj robota už je pozdě, naštěstí situaci zachraňuje kolega působící v týmu Short Circuits a jeho robot Ferda.

Robot byl tímto zajištěný, další bod programu - webová kamera, která by ho natáčela. Po dlouhém zvažování jsem s ohledem na dobré reference a možné další využití vybral kamerku od Creative.

Esmeralda :: Poprvé před kamerou

Tím byl hardware kompletní, robota jsem dostal půjčeného včetně software pro komunikaci (říkal bych tomu SDK, ale pro tech 5kb mi to přijde jako příliš vznešený název :)), hlavní těžiště mé práce spočívalo v rozpoznání robota na kameře a v jeho navigaci směrem k určenému bodu.

Rozhodl jsem se začít základním úkonem - a to nalezením robota na obraze z kamery...

• První iterace: nalezení robota v obraze pomocí detekce hran.
  Protože Ferda (v té době už Esmeralda) se vyznačuje hlavně tím, že je velmi členitý (pokud má nasazenou králičí hlavu, nebo naopak nemá žádný obleček), nebo naopak zoufale nevýrazný (pokud má jenom obleček), takže je skoro nemožné na něm najít jednoduchý a snadno rozpoznatelný tvar.
  A co je horší, z každé strany vypadá úplně jinak - tudy snadná cesta nevedla.
• Druhá iterace: označní robota pomocí výrazného objektu snadno rozpoznatelného pomocí detekce hran.
  Po předchozím neúspěchu jsem se rozhodl označit robota velmi výraznou červeno-černou šipkou na bílém pozadí, které by určovala nejen pozici, ale i směr, jakým je robot natočený. Toto bohužel skončilo ještě větším fiaskem než první iterace. Z nějakého důvodu se velmi kontrastní šipka žádnému hranovému operátoru nelíbila a místo ní radší hledaly spáry mezi parketama.
• Třetí iterace: výrazné barevné body.
  Neúspěchy s hledáním hran mě dovedly k myšlence zkusit hledat na obraze z kamery něco jiného, třeba souvislé barevné plochy. A vyfiltrovat z obrázku všechny oblasti, které jsou sytě modré/zelené/červené je pak už trivialita.
  Konec teorie, teď trochu praktických ukázek. Praktická zkouška s filtrem na modrou barvu ukázala, že tudy by cesta vést mohla.

Esmeralda :: Hledáme robota

Pro hledání výrazných barevných bodů se osvědčila jednoduchá metoda separace jednotlivých barevných rovin pomocí odečítání ostatních barevných složek od celkové (černobílé) hodnoty pixelu v obrazu z kamery.

Na levém obrázku je vidět obraz snímaný kamerou, na pravém je stejný obrázek po průchodu filtrem, který vybírá a černě označuje jasně modré body.  

Při testování na modré a červené barevné složce filtr fungoval velmi dobře, na první problém jsem narazil když jsem chtěl vyzkoušet filtr pro zelenou barvu. Napřed se ukázalo, že obraz z kamery nedostávám rozložený na červenou, modrou a zelenou složku, ale že na místě zelené složky je celkový jas (čti černobílá barva). No nevadí, zelenou si dopočítáme ze známých hodnot.

Tento drobný zádrhel zřejmě ještě o něco zvýraznil další problém se zelenou barvou, totiž její malé zastoupení v celkovém jasu. Ani jedna z těchto věcí by zřejmě sama o sobě nepůsobila žádné zásadní potíže, díky jejich kombinaci se ale zelená stala hodně špatně zpracovatelnou barvou a po přefiltrování byly vidět jen čistě zelené plochy, na kterých navíc nesměl být žádný odlesk světla.

Pro označení robota jsem chtěl použít barevné míčky. To jsem ale ještě nevěděl, jak velký problém je sehnat míčky, které:

• nejsou moc malé, aby je na kameře bylo vůbec vidět
• nejsou moc velké, aby je bylo možné připevnit k robotovi a nezakrývaly se
• nejsou lesklé, aby byla vidět barva a ne bílé odlesky
• mají jednu ze základích barev bez dalších příměsí
• jsou bez potisku a vzorku

Sehnat takové míčky se ukázalo jako velký problém... Po sobotním odpoledni stráveném s Káťou ve sportovním oddělení nejmenovaného hypermarketu jsem už nevěřil, že takové banální věci, jako jsou míčky bez Pikachu a myšáka Mickeyho vůbec ještě existují. Nakonec jsme vybrali malé florbalové míčky, protože byly lehké a sadu na petanque, protože obsahovala víc barev (a říkali jsme si, že bychom si mohli zahrát). Ironické je, že míčky jsme kupovali dřív, než jsem zjistil jaký se na kameře chová zelená barva - takže jsme koupili jenom čtyři florbalové míčky a z toho dva byly zelené...

Kromě barevných míčků jsme se vybavili barevnýma izolepama, o kterých jsme si říkali, že by se mohly hodit. Ale o tom později.

Esmeralda :: Přesné umístění

Ve chvíli, kdy dokážeme najít výrazné barevné body, pořád ještě zbývá dlouhá cesta k nalezení robota. Jako první velký problém se ukázalo, že zatímco ze zelené barvy filtr nenechá skoro nic, červenou vidí až příliš často. Zlášť když na pozadí jsou parkety a nábytek z třešňového dřeva. Bylo tedy potřeba určit které body jsou dostatečně výrazné a které už ne. Drobné experimentování s pevnými hodnotami prahu jasnosti ukázalo, že jak se během dne mění osvětlení, tak se mění jas obrazu takovým způsobem, že žádná konstatní hodnota prahu neobstojí.

Tento problém se podařilo snadno vyřešit pomocí histogramu a určení prahové hodnoty filtrovaných hodnot tak, aby v filtru zbylo nejvýš 50 bodů. Tato hodnota se během práce ukázala jako poměrně vyhovující, je ale možné, že s menší hodnotou by program pracoval¨ lépe.

Při hledání konkrétních barevných ploch ve filtrovaných barevných složkách jsem používal OpenCV funkce pro vyhledávání souvislých konvexních oblastí. Navíc jsem ještě přidal filtr vyřazující oblasti, které jsou na míček příliš velké. Ani tyto filtry ale nedaly vždy pro všechny barevné složky jednoznačný výsledek.

Výrazně na kameře působily nejen míčky, ale i samotný robot - jeho konstrukce je z větší části vytvořená ze součástek stavebnice Merkur, které jsou prakticky všechny červené, modré, nebo zelené... To ale není nic, co by nedokázaly vyřešit staré papíry a trocha izolepy.

I po odfiltrování nebezpečných ploch na robotovi pomocí izolepy a omezení rozsahu přijímaných barev se stávalo, že pro některou barevnou složku zbyl víc než jeden kandidát. Pro tento případ jsem do programu doplnitl vyhledávání vhodné čtveřice bodů kontrolou některých jejich parametrů.

Hodnoceny jsou všechny čtveřice bodů obsahující práve jeden modrý bod, jeden červený a dva zelené. Okamžitě jsou vyřazeny čtveřice, které obsahují body v nesprávném pořadí (správné pořadí bodů je dáno jejich pozicí na těle robota). Následně jsou jednotlivé kombinace bodovány na základě relativní vzdálenosti bodů, jejich vzájemných úhlů, vzdálenosti od komibnace zvolené v předchozím snímku a dalších parametrů. Tato metoda obvykle vedla k redukci možných kombinací na jednu nebo dvě. Další zlepšení by pravděpodobně bylo možné dosáhnout lepším vyladěním hodnocení jednotlivých kritérií.

Brzy se ukázalo, že tento systém je dostatečný pouze v případě, kdy kamera zabírá robota z takového úhlu, že jsou vidět všechny čtyři míčky. To ale vzhledem k tvaru robota nebyla příliš obvyklá situace, proto bylo nutné rozšířit vyhledávání i na trojice (a v krajním případě dvojice) bodů a polohu neviditelných bodů dopočítávat. Tím se podstatným způsobem ztížilo ohodnocování a velký podíl na problémech ohodnocení jednotlivých trojic a čtveřic má právě nutnost uvažovat i s nekompletními sadami bodů.

Esmeralda :: Navigace

V souladu s původními velkolepými plány jsem velkolepě naplánoval i systém pro navigaci robota. Hledání cesty v prostoru mělo být vyřešeno pomocí pravděpodobnostního plánovače. Protože robot je vybavený zepředu nárazníkem a protože detekovat, kdy se robot má pohybovat, ale nepohybuje je s kamerou poměrně snadné, počítal jsem s tím, že by se postupně budovala mapa neprůchozích oblastí ve které by se později hledala cesta. Dokonce jsem naprogramoval prototyp plánovače cesty, který se ukázal jako překvapivě dobře funkční.

Vzhledem k nedostatku času jsem nakonec použil mnohem jednodušší řešení, které je v prostoru bez překážek stejně efektivní a snáze přežije i takové změny, jako je změna polohy kamery (pravda, s přesunem kamery se sice přesune i bod kam má robot dojet, ale to je věc, které se dá řešit).

Celá navigace spočívá v určení orientace robota (na 2d obraze z kamery), určení úhlu o který je třeba se natočit při cestě směrem k cíli a určení vzdálenosti od cíle. Pokud je cíl v pětistupňovém rozmezí od natočení robota, jede robot rovně. Pokud cíl je do dvaceti stupňů, jede robot dopředu a mírně zatáčí směrem k cíli. Pokud je cíl mimo tyto úhly, robot se otáčí na místě směrem k cíli tak, aby po skončení otáčení měl cíl přímo před sebou. Problém s výhýbáním překážkám jsem snadno vyřešil vyřazením překážek ze zadání problému a tak už nic nestálo v cestě úspěšnému předvedení a odevzdání.

Jak je vidět na přiložených videích, je tento způsob navigace pro zadanou úlohu zcela dostačující a robot je schopný dojet na místo určení i v případě, že systém pro jeho lokalizaci v některém kroku selže.

Esmeralda :: Download

Prototyp plánovacího systému. Mapa na které je plánování prováděno je zadána vektorově a je napevno zadrátována do programu. Zdrojové kódy v C# na požádání zašlu. Pro spuštění je třeba .NET Framework 1.0.
Prototyp plánovače cesty (zip - 8kB)

Videa nahrávaná přímo webovou kamerou při testování robota. Na videu si všimněte jednak bílých kroužků označujících kandidáty na lokalizační body a jednak zelené a fialové čary označující předpokládanou pozici robota. Komprimováno pomocí Intel Indeo kodeku.
Esmeralda - video 1 (avi - 5MB)
Esmeralda - video 2 (avi - 35MB)