Plánování pohybu range-finderu pro rekonstrukci modelu
3D tìlesa

Jaroslav Fojtík, Tomáš Pajdla

Abstract

Našim cílem je provedení rekonstrukci povrchu (nebo objemu) tìlesa. Snímání objemu tìlesa bude uskuteèòováno pomocí Range-Finderu, který je umístìn na rameni robota. V této konfiguraci bude mít range finder 6 stupòù volnosti. Bylo by vhodné nìjakým zpùsobem minimalizovat cenu mìøení. Napøíklad se mùže jednat o poèet mìøení nutných k rekonstrukci.

Za tímto úèelem je vhodné naplánovat místa pro snímání jednotlivých mìøení. Algoritmus plánování mìøících míst vychází jednak z apriorní informace o modelu a navíc musí zohlednit namìøené hodnoty ze všech pøedchozích mìøení. Souèástí algoritmu je metoda pro urèení okamžiku ukonèení sekvence mìøení.

Apriorní informace obsahuje údaje o prostoru, který je dosažitelný paží robota. Dále bude v apriorní informaci obsažena nìjaká standardní výchozí poloha paže robota, ve které robot nezavadí o tìleso. Bylo by též vhodné do apriorní znalosti zahrnout polohu stolku nebo podložky pod tìleso a všech ostatních pøedmìtù, které nesouvisí s mìøeným tìlesem. Bylo by vhodné omezit polohu tìlesa na místo, ze kterého bude tìleso pozorovatelné a mìøitelné range-finderem. Pokud range-finder nezjistí pøítomnost tìlesa z výchozí polohy, mìl by se pohybovat po pøedem pøipravené trajektorii (tuto trajektorii lze též zahrnout do apriorní znalosti). Pokud ani poté na žádné tìleso nenarazí, bude mìøení ukonèeno.

Sekvence mìøení má být ukonèena v okamžiku, kdy již další mìøení nepøináší zlepšení vnitøního modelu tìlesa. Z fyzikálních vlastností range-finderu vyplývá, že nìkteré detaily na povrchu nebudou vùbec mìøitelné. Ze snahy o co nejmenší poèet mìøení vyplývá nutnost ignorování nìkterých detailù. Algoritmus by mìl mít parametr: "maximální velikost ignorovaného detailu" a podle pøedaného parametru se rozhodnout, zda další mìøení mùže zlepšit model o detaily vìtší než nejmenší požadované èi zda nikoliv. Zde je nutno zvážit, v jakých jednotkách takový parametr zadávat a co vlastnì bude urèovat. V pøípadì pokraèování v mìøení bude nutno urèit, do které polohy pøesunout range-finder za úèelem dalšího mìøení.

Posledním problémem, který zbývá vyøešit je volba vnitøní reprezentace mìøeného objektu. Vnitøní reprezentace by mìla umožòovat snadné sluèování dat z jednotlivých mìøení. Bylo by vhodné ji vytvoøit též s ohledem na požadovaný výstup z celého algoritmu. Formát výstupních dat bude nutno též upøesnit.

1 Úvod

Ve strojírenství se vyskytují požadavky na digitalizaci již hotových výrobkù. Je žádoucí, aby digitalizovaný model sloužil buï ke kontrole rozmìrù anebo jako podklad pro novou výrobu.

V souèasné dobì se zavádìjí elektronické obchody. V nich by bylo také velmi pøínosné mít nìjaké 3D snímací zaøízení pro zboží nabízené elektronickou formou. 3D model by si pak mohl každý doma prohlížet pomocí www prohlížeèe. Mohl by se na dokonce zboží dívat z rùzných pohledù.

Také herní prùmysl vyžaduje stále více digitalizovaných reálných objektù. Ty jsou umísovány do jednotlivých her.

Právì zjednodušením, zkvalitnìním a zrychlením digitalizace 3D dat se zabývá zpráva, kterou držíte v ruce. Je v ní obsažen rozbor již používaných postupù. Dále je ukázán nový postup. Ten je založen na Range Finderu¹ umístìném v paži robota. Ve zprávì je øešeno dvourozmìrné snímání v øezech s tím, že v následujícím kroku v našem výzkumu bude provedeno zobecnìní pro 3D.

2 Rozbor úkolu na dílèí èásti

Úloha zpìtné rekonstrukce objemu tìlesa je pomìrnì nároèná. Proto ji rozdìlíme na jednotlivé èásti a budeme se podrobnì vìnovat každé z nich.

2.1 Omezení scény, objektù a relace objekt - scéna

V tomto oddílu diskutujme možné konfigurace scény a jednotlivých objektù. Na volbì konfigurace závisí do jisté míry i obtížnost a typ úlohy rekonstrukce tìlesa. Je potøeba peèlivì zvážit požadavky, aby nedošlo ke zbyteèné komplikaci úlohy.

Omezující podmínky na scénu

Objekt musí být celý umístìn ve scénì.
Objekt mùže ze scény vyènívat / senzor mùže vstoupit do scény.

Druhý pøípad nastává napøíklad pøi rekonstrukci tvaru hor, budov a vzájemné polohy hvìzd. V dalším textu jej nebudeme uvažovat.

První pøípad je nejbìžnìjší v laboratorním prostøedí. Øešení prvního pøípadu je o nìco jednodušší. U prvního pøípadu lze obecnì rozlišovat dvì modifikace. Úloha se výraznì komplikuje pokud mùže dojít ke kolizi senzoru a snímaného objektu. Taková situace nastane, když mùže senzor vstoupit do prostoru, který je vyhrazen pro snímanou scénu. Rozšíøená úloha zatím nebyla uspokojivì vyøešena.

Objekty, které se mohou vyskytnout ve scénì

Rozdìlení objektù do kategorií podle pohybu:

Základní úloha rekonstrukce poèítá s pevnými tìlesy. Pokud se tìleso pohybuje, je nutno pøi rekonstrukci jeho tvaru pohyb buï uvažovat a nebo provést mìøení tak rychle, že je vlastní pohyb zanedbatelný. U nìkterých vìtších pohyblivých tìles je možno dokonce pohybu výhodnì využít (napø. pro rekonstrukci objemu jedoucího vlaku).

Úlohu je možno navíc ještì komplikovat tím, že tìleso bude v èase mìnit svùj tvar (jedná se napø. o snímání živých zvíøat).

Pro požadavky zkoumání zpùsobù rekonstrukce budeme zatím uvažovat jen první variantu tuhých a nehybných tìles.

Omezení kladená na tvar objektu

Nìkteré aplikace požadují, aby byly objekty složeny pouze z kvádrù popøípadì z válcù. Jindy je požadován pouze konvexní tvar objektu. Zatím nebudeme klást na tvar objektu další omezení. U konkávních objektù v takovém pøípadì mohou nastat i pøípady, kdy nebude možno rekonstruovat tvar celého objektu. Použitému algoritmu by nemìly tyto situace vadit.

Další omezení se týkají nejmenších detailù, které jsou mìøitelné použitou metodou. Menší detaily budou jednoduše ignorovány.

Optické vlastnosti rekonstruovaného tìlesa

Objem je nejèastìji rekonstruován pomocí optiky. Proto je velmi dùležité provést rozbor optických vlastností scény. Nejsnadnìji jsou snímána tìlesa s Lambertovským povrchem. Za tímto úèelem jsou nìkdy tìlesa dokonce natírána šedou barvou.

Zrcadlový odraz a prùhledná tìlesa velmi komplikují nároky na vyhodnocovací algoritmus. Zatím jsem se nesetkal s algoritmem, který by se rekonstrukcí tvaru takových tìles zabýval, a proto je nebudeme v dalším výkladu uvažovat.

2.2 Zpùsoby rekonstrukce

Zde budou diskutovány dva základní zpùsoby rekonstrukce, které se od sebe liší. Jedná se o:

V prvním pøípadì jde o ovìøení tvaru tìlesa. V praxi se používá napøíklad pøi kontrole rozmìrù hotových výrobkù. U nich je znám prostorový model a tím pádem všechny rozmìry. Poloha tìlesa mùže být buï pevnì fixována anebo algoritmus sám urèí polohu tìlesa na základì namìøených dat.

Druhý pøíklad je o nìco složitìjší, ponìvadž není kladeno žádné explicitní omezení na tvar tìlesa. Je potøeba používat rùzné strategie pro snímání èástí tìlesa. Obecnì nelze zaruèit, že všechny èásti tìlesa bude možno rekonstruovat. V takových pøípadech je nutno nasnímat co možná nejvìtší množství dat.

2.3 Metody reprezentace

Pro rekonstrukci tvaru je nutno nìjakým zpùsobem ukládat namìøená data. Volba interní reprezentace mùže zásadním zpùsobem ovlivnit jak pøesnost tak i rychlost a kvalitu rekonstrukce.

Nejèastìji jsou používány následující reprezentace:

CAD model - vzniká jako výstup z nìjakého objemového modeláøe.
Triangulovaný povrch - popisuje pouze povrch tìles sítí trojúhelníkù.
Voxelová reprezentace - urèuje v každém bodì pøítomnost tìlesa.
3D primitiva - mnohostìny, válce.
Analytická funkce - snaží se popsat tìleso jedinou funkcí.

CAD model je vhodný pro kontrolu tvaru již známých tìles. Pro rekonstrukci objemu je používán pouze tehdy, pokud je k dispozici knihovna pro práci s tímto modelem. Byl použit napø. v práci [].

Triangulovaný povrch² je nejèastìjší reprezentací a vyskytuje se napø. u tìchto autorù [,,,]. Triangulovaný povrch se pomìrnì snadno ukládá do pamìti. Složité je však sluèování informací z jednotlivých pohledù a vytváøení nové triangulace.

Voxelová reprezentace vypadá na první pohled jako nejjednodušší. Voxel s hodnotou '1' bude považován za obsazený a voxel s hodnotou '0' za prázdný. V praxi je situace o nìco složitìjší. Nìkteré voxely nelze vùbec vidìt a nìkteré zatím nebyly prozkoumány senzorem.

Proto je potøeba pøidat další hodnotu pro netestované voxely. Je vhodné napøíklad schéma -1 voxel je prázdný, 0 - hodnota voxelu není známa, 1 voxel je plný.

Voxelová reprezentace má z pochopitelných dùvodù problémy s objemem dat. Proto se používá v kombinaci s nìkterým typem komprimace napøíklad s oktalovými-stromy.

3D objemová primitiva jsou také pomìrnì èasto využívána [,,]. Vìtšina reálných tìles se neskládá pouze z tìchto primitiv a tato aproximace je nedokáže vìrnì reprezentovat. Teoreticky by sice bylo možno primitiva libovolnì zmenšovat, ale algoritmy postavené na primitivech neumìjí zpracovat tak velké množství primitiv.

Zdálo by se velmi efektivní použít k reprezentaci tìlesa analytickou funkci. Bohužel pouze velmi jednoduchá tìlesa by bylo možno popsat relativnì jednoduchou analytickou funkcí. Ostatní tvary by nebyly popsatelné vùbec a nebo za cenu extrémnì složité funkce

2.4 Parametrizace snímacího prostoru

Objem tìlesa je snímán pomocí senzoru. Témìø nikdy nemùže senzor provést mìøení celého objemu naráz. Proto musí být plánováno snímání objemu z více poloh.

0.5

Figure 1: Snímací senzor v prostoru

Na obrázku obr. 1 je ukázána konfigurace jediného senzoru v prostoru. Jako každé pevné tìleso má snímaè 6 stupòù volnosti. Jedná se o polohu x,y,z a náklony a,b,j. Každý pohled je tedy charakterizován 6 souøadnicemi.

Nìkteré senzory mají navíc zdroj svìtla (nebo signálu). Pokud se jedná o bodový zdroj svìtla, tak je potøeba uvažovat ještì další 3 stupnì volnosti. Obecnì se jedná o 6 dalších stupòù volnosti pro zdroj svìtla.

Úkol prozkoumání stavového prostoru s velkým poètem rozmìrù se èasto øeší následujícími zpùsoby:

Napøíklad Range-Finder má spolu vázán zdroj svìtla a snímací kameru. Zbývá nám 6 stupòù volnosti. I pøes omezování a vyluèování stupòù volnosti se jedná o velmi složitý problém hledání nejlepšího pohledu v parametrickém prostoru. V tomto prostoru je potøeba se nìjakým zpùsobem orientovat.

Pro orientaci v parametrickém prostoru jsou používány následující postupy:

Analytický popis parametrického prostoru je velmi elegantní. Bohužel je též natolik složitý, že se èasto nedá snadno manipulovat s výslednou analytickou funkcí.

Dodateèná omezení parametrického prostoru jsou nejèastìji založena na heuristikách. Pro nì není jasné chování ve všech situacích a v nìkterých pøípadech nejsou optimální.

Diskretizace prostoru je èasto provádìna do kulové (pùlkulové) sítì bodù a nebo do válcové sítì, jak je ukázáno na obr. a a obr. b. Ve zvolených bodech je ohodnocena kvalita snímání a je hledáno optimum v diskretizaèní møížce.

0.35

Figure 2: Pùlkulová a válcová sí snímacích bodù

Diskretizace má také nevýhody dané nízkým rozlišením diskretizaèní sítì. Též dochází k citelné ztrátì stupòù volnosti snímacího èlenu.

Metody používající sledování paprskù (ray tracing) dávají pomìrnì uspokojivé výsledky. Pøi sledování paprskù pro všechny plochy mají tyto algoritmy extrémní výpoèetní nároènost.

2.5 Metody hledání dalších pohledù

Metody hledání dalších pohledù závisí zèásti na tom, jakým zpùsobem je parametrizován snímací prostor. U diskretizovaného prostoru lze projít všechny jeho body.

U spojitých prostorù jsou èasto využívány techniky z umìlé inteligence a heuristiky. Také se používají metody generuj a testuj.

Plánovací strategie

Podle [] lze rozlišit 3 základní strategie v plánování pozorování pro rekonstrukci:

sep 0pt
Úvodní hra: Zde se jedná o velmi hrubé a rychlé získání tvaru objektu.
Støední hra: V tomto kroku jsou snímány a rekonstruovány velké plochy.
Koneèná hra: V tomto kroku mají být nalezeny a rekonstruovány všechny jemné detaily.

Navržené strategie jsou vhodné pro postupnou rekonstrukci tìlesa od nejhrubších rysù až k jemným detailùm ve tøech krocích. Pro každý krok mùže existovat samostatný algoritmus. Nìkteré plánovací strategie v sobì mohou zahrnovat všechny tøi kroky souèasnì.

3 Práce ostatních

V této kapitole jsou diskutovány práce ostatních, které se týkají plánování dalších pohledù.

3.1 Conolly 1985 []

Prostor objektu je rozdìlen oktalovým stromem. Pøi snímání objektu jsou oblasti ležící na místì objektu oznaèeny jako objekt, oblasti pøed objektem jako vidìné a všechny ostatní oblasti jako nevidìné. Pro výpoèet NBV³ jsou navrženy dva algoritmy. Jeden algoritmus je nazván "normální" a druhý älgoritmus planetária".

Algoritmus planetária hodnotí viditelnost povrchu pro každou možnou pozici senzoru. Senzor bude umístìn do takové pozice, která maximalizuje poèet nevidìných krychlí. Použitý algoritmus má velkou výpoèetní nároènost a navíc nerespektuje geometrii senzoru.

Druhý algoritmus nazvaný "normální" poèítá plošky krychlí, které oddìlují prázdnou a vidìnou oblast pro 6 pohledù. Z nich si pak jeden pohled vybere. Toto je velmi rychlý a jednoduchý algoritmus, který urèuje omezený poèet 6 pohledù a nebere v úvahu viditelnost.

3.2 Hutchinson 1989 []

Tento èlánek se zabývá plánováním s využitím modelù a testováním hypotéz. Je zajímavý svým pøístupem, který se odlišuje od hlavního proudu NBV a mùže vést (podle []) k lepšímu porozumìní nìkterých aspektù problému NBV. Základní pøedkládanou myšlenkou je nalézt takové umístìní senzoru, které by minimalizovalo nejednoznaènost metriky v prostoru hypotéz, které se týkají typu objektu postaveného pøed senzorem. Tomu èásteènì pomáhá graf aspektù, který je využit k seskupení podobných operací týkajících se umístìní senzoru ve vztahu k èásteènì hypotetizovanému objektu. Nejednoznaènost je mìøena s využitím koncepcí z informaèní teorie, které mohou vést k mnohem rafinovanìjšímu pøístupu pøi definování nových mìøení. Bohužel tyto pøístupy nevypadají pøíliš prakticky pro pøímé využití v NBV, vzhledem k odlišným pøedpokladùm o objektech a obrovské výpoèetní nároènosti.

3.3 Maver a Bajcsy 1993 []

Maver a Bajcsy 1993 vyvinuly algoritmus pro plánování bodù pohledu range-finderu. Pohyb proužku svìtla je omezen na posuny a rotace v rovinì nad objektem. Nevidìné oblasti objektù jsou reprezentovány polygony. Viditelnosti dosud nevidìných oblastí (z rùzných pohledù dle nastavení senzoru) jsou urèeny dle hranic polygonù. Pøedkládané øešení je bohužel omezeno pouze na urèitou speciální konfiguraci senzoru.

3.4 Whaite a Ferrie 1990-1997 [,,]

Whaite a Ferrie aproximují snímaná data parametrickým modelem ze superkvadrik. Pøíští pohled je urèován tak, že se minimalizuje neurèitost modelu v místech, kde data nejhùøe aproximují model. Rangefinder je navádìn ve smìru, který minimalizuje nejistotu aktuální aproximace modelu. Tento algoritmus umožòuje daty øízené zkoumání objektu za úèelem tvorby modelu. Zvolený parametrický model nemùže pøesnì reprezentovat objekty s velkým množstvím povrchových detailù. Tato skuteènost pøedstavuje omezení celé navrhované metody. Omezení daná viditelností povrchu a zákryty nejsou zahrnuta do procesu plánování, což má za následek nemožnost snímání složitých povrchù vzhledem k zákrytùm.

3.5 Pito 1995-1996 [,]

Pito navrhuje obecný algoritmus plánování pohledù, který bere v úvahu jak omezení viditelnosti senzoru tak i nevidìné èásti zkoumaného objektu. Nejlepší pohled maximalizuje pomìr nevidìných èástí, které musí sousedit s èástmi již vidìnými. Omezení viditelnosti je pøedpoèítáno pro každou oblast aby byla snížena extrémní výpoèetní nároènost. Prezentovaný pøístup je omezen na posuny snímacího èidla po válci, který obklopuje objekt.

3.6 Papadopoulos-Orfanos a Schmitt 1997

Papadopoulos-Orfanos a Schmitt navrhují plánovací algoritmus který navádí senzor se tøemi stupni volnosti. Senzor mùže dokonce vstoupit do prostoru urèenému pro objekt.

3.7 Tarabanis 1995 []

Tento èlánek obsahuje pøehled plánovacích technik urèených pro detekci pøíznakù v prostøedí se známou geometrií. Tím že se jedná o snímání známých oblastí se tato úloha liší od NBV. V pøehledu jsou detailnì rozebrány techniky HEAVEN, VIO, ICE, SRI a MVP []. V èlánku jsou rozlišovány techniky typu generuj a testuj, které se vyskytují hlavnì u NBV, a analytický pøístup. V analytickém pøístupu je vytvoøený kompletní prostor øešení vèetnì zadaného omezení porovnán s ostatními prostory øešení. U syntetického pøístupu se mùže též jednat o hledání optima mnohaparametrové optimalizaèní funkce. Jednotlivé parametry mohou zahrnovat napøíklad polohu snímaèe, zoom a zaostøení kamery. Geometrické kalkulace jsou velmi zajímavé, ponìvadž zahrnují množství vzorkovacích technik (napø automatické dìlení dlaždic v obklopující sféøe) a technik sledování paprskù (BSP stromy, pøedzpracování, konvexní obálky a výpoèet množin bodù). Obecnì je použitá geometrie jednodušší než jaká je nejèastìji používána u NBV.

3.8 Banta 1995 []

Èlánek je podle [] výsledkem neefektivní týmové spolupráce a 'školského' zpracování. Navzdory mnoha citacím⁴ èlánek popisuje nejménì efektivní algoritmus. Pro reprezentaci geometrie je využita matice obsazenosti. Podle køivosti dosud nasnímaného povrchu jsou vybrány tøi možné pohledové body. Ty jsou navzájem relativnì ohodnocovány metodou sledování paprskù s pøihlédnutím ke všem ostatním datùm (viditelnost). Použitá terminologie není pøesná. Na druhou stranu jsou v tomto èlánku nápady, které se nevyskytují v jiných èláncích. Pøedevším se jedná o charakteristiky cesty snímacího èidla a o množství nové informace, které je odkryto novým mìøením.

3.9 Massios 1998 []

V tomto èlánku je popisován algoritmus NBV založený na voxelové reprezentaci. Pohled je plánován z mnoha bodù rozmístìných na kulové ploše. Každý voxel mùže nabývat nìkolika hodnot: Nevidìno, vidìno, prázdný a rovina zákrytu. Rovina zákrytu vzniká tam, kde spolu pøímo sousedí voxely typu nevidìno a vidìno. Voxely typu vidìno obsahují navíc atribut úhlu mezi rangefinderem a mìøenou rovinou. V každém možném bodì pohledu je poèítána viditelnost rovin zákrytu a vidìných rovin.

4 Formalizace úlohy

Nech M je snímané tìleso. Je kladen požadavek na pøevedení tìlesa M do digitální reprezentace. Duplikát tìlesa M si nazvìme [`(M)]. Je rozumné požadovat, aby se [`(M)] co nejménì lišilo od M. Vzhledem k používání iterativních metod je duplikát postupnì vylepšován pøidáváním dalších informací. Proto máme k dispozici celou posloupnost modelù [`(M)]. Nazvìme si je [`(M)]₀ až [`(M)]_n.

Nech vektor [x\vec] obsahuje souøadnice snímacích èlenù pro jednu konfiguraci. Do souøadnic snímacích èlenù se promítají též všechny stupnì volnosti kamery a zdroje svìtla. Jednotlivá mìøení si oznaème [x\vec]₁, [x\vec]₂ ... [x\vec]_n a uložme si je do matice X.

0.5

Figure 3: Cyklus zahrnující jednotlivé kroky pøi snímání dat

Na obr. 3 je zobrazen celý proces snímání 3D tìlesa. Do procesu vstupuje prázdný model [`(M)]₀. Ten je postupnì vylepšován dalšími mìøeními tak, že data z tìchto mìøení jsou do nìho integrována. Pøed každým mìøením je nutno naplánovat novou konfiguraci snímací sestavy [x\vec]_k+1.

Dùležitý krok ve snímacím cyklu pøedstavuje rozhodování o zastavení jednotlivých iterací. K tomu by mìlo dojít z následujících dùvodù:

Pøekroèení stanoveného èasu.

Pøekroèení maximálního poètu iterací.

Nelze-li již dalším mìøením výraznì vylepšit stávající model.

Definujme si funkci, která provede celé nové mìøení s následnou aktualizací namìøeného modelu:

M2_k+1 = update(M2_k,

k+1

)

(1)

V této rovnici musí být známa následující hodnota polohy senzoru. K jejímu výpoètu použijeme funkci NBV.

k+1

= NBV(X,M2_k)

(2)

Ještì je nutno definovat funkci, která nìjakým zpùsobem ohodnocuje odhadované možné zlepšení modelu dalšími mìøeními. Této funkci již postaèí pouze znalost modelu v k té iteraci.

q = Possible_Improvement(M2_k)

(3)

Funkce ohodnocující možné zlepšení nemùže sama o sobì zaruèit ukonèení algoritmu po koneèném poètu krokù. Nejvìtším problémem algoritmù iterativního typu pøedstavuje vznik cyklù. Kdyby se každé mìøení nevratnì projevilo nìjakým zpùsobem na vznikajícím modelu, tak by vždy po urèitém maximálním poètu krokù došlo k zakonèení algoritmu. Bohužel v praxi existují taková mìøení, která nepøinášejí žádnou novou informaci o modelu. Proto je nutno k rekonstruovanému modelu pøidat ještì dodateènou stavovou informaci. Datová struktura kombinující stavovou informaci a rekonstruovaný model již mùže mít vlastnosti požadované na poèátku tohoto odstavce.

5 Navržené øešení

V tomto oddílu bude vìnován prostor popisu metod, které byly použity k øešení úlohy v experimentální implementaci. Zatím se jedná jen o snímání v jedné rovinì pomocí robota. Po odladìní tohoto algoritmu je uvažováno o rozšíøení do všech tøí rozmìrù.

5.1 Volba reprezentace

Pro plánovaè pohledù je potøeba volit reprezentace následujících skuteèností:

Je snaha, aby byla jednotlivá fakta (presentovaná v pøedchozím výètu), pokud to pùjde, reprezentována stejným nebo alespoò podobným formalismem. Hlavním dùvodem jednotné reprezentace je zjednodušení a zefektivnìní výsledného algoritmu.

Reprezentace možných mìøení

Po analýze problému byla zvolena reprezentace møížkou (v Matlabu se jedná o matici). Jednotlivé buòky mohou nabývat 3 základních hodnot: 0 buòka není známa; 1 buòka je plná; -1 buòka je prázdná. Møížka obecnì má nevýhodu vyjádøenou pomìrem velké pamìové nároènosti a malé pøesnosti. Tento nedostatek jsme se rozhodli pøekonat tak, že ke každé plné buòce bude pøidán seznam všech namìøených bodù, které do ní spadají. Po dokonèení mìøení pak bude možno ze všech namìøených hodnot rekonstruovat pøesný tvar snímaného 2D tìlesa.

Zvolená reprezentace umožòuje snadnou fúzi namìøených dat. Nech M1 je matice vzniklá z jednoho mìøení a M2 je matice z druhého mìøení. Pak jejich slouèení lze vypoèítat M = sgn(M1 + M2). Za jednu z výhod møížky je možno též považovat snadný a rychlý pøístup k datùm.

Reprezentace apriorní znalosti o úloze

Apriorní znalost se týká nìkolika èástí úlohy.

První znalost se týká použitého snímaèe. Zatím uvažujme pouze Range-Finder s kamerou. Ten musí být zkalibrován a plánovacímu algoritmu musí být známa jeho geometrická konfigurace. Pøedevším se jedná o vzájemnou vzdálenost ohniska kamery a laseru, dále se jedná o náklon laseru, náklon kamery a zorný úhel kamery.

Další apriorní informace se týkají velikosti snímaného objektu. Ta je v zásadì dána manipulaèním rozsahem robota v jehož paži je range-finder umístìn. V algoritmu se projeví volbou velikosti møížky a skuteènými rozmìry jedné buòky.

5.2 Použité speciální termíny

V dalším textu o plánování jsou použity následující termíny. Ty jsou zobecnìny tak, že je lze použít jak v pixelové tak i ve vektorové implementaci.

Neznámá oblast. Neznámá oblast pøedstavuje prostor, o kterém se dosud nepodaøilo získat žádnou informaci ze snímacího senzoru.

Prázdná oblast. Prázdná oblast pøedstavuje prostor, ve kterém se nevyskytuje žádné plné tìleso.

Rùstový bod. Za rùstový bod je považován takový plný bod, v jehož okolí se nachází neznámá oblast.

Rovina zákrytu. Rovina zákrytu pøedstavuje styènou plochu vznikající na rozhraní prázdné a neznámé oblasti. Nejèastìji se na takovémto rozhraní vyskytuje plná oblast.

Kandidát na snímání. Pøedstavuje bod s dosud neznámou hodnotou, který leží v sousedství plného bodu. U rastrové reprezentace je sousedství dáno osmiokolím, u vektorové se jedná o urèitou malou vzdálenost.

Predikovaný bod. Predikovaný bod je kandidátem na snímání, který leží v sousedství rùstového bodu. Pokud lze proložit nìjakou plochu (køivku ve 2D pøípadì), která prochází rùstovým bodem a jeho sousedními plnými body, tak rùstový bod leží na této ploše. Jinými slovy, rùstový bod leží v místech, kam s nejvìtší pravdìpodobností pokraèuje dosud nasnímaná plocha (èi køivka ve 2D pøípadì).

6 Plánovací strategie mìøení

Základní mìøící cyklus je ukázán na obrázku obr. 3. První krok spoèívá v nalezení tìlesa (tzn. alespoò jeho jediného bodu). V souèasné implementaci se rangefinder pohybuje po pøímce do té doby, dokud nenamìøí nìjakou hodnotu. Nejvhodnìjší strategií by bylo objet celé tìleso po nìjaké kruhové dráze.

Od okamžiku nalezení objektu zaèíná vlastní plánování. Pokud rangefinder namìøil dosud jen jediný bod, tak se plánovaè pokusí udìlat malý krok stranou (z dùvodu minimalizace pohybu RF) a provést nové mìøení.

Sousedí-li rùstový bod alespoò s jedním plným bodem, pak probíhá vlastní plánování. Jedním z požadavkù na optimální smìr pohledu je kolmost na predikovanou pøímku vycházející z predikovaného bodu. Je žádoucí, aby ani jeden paprsek neprocházel plnou oblastí. Paprsek by mohl ještì navíc procházet pøes dalšího kandidáta ke snímání (ležel by na spojnici Rangefinder - predikovaný bod). Celá situace je zachycena na obrázku obr. .

0.8

Figure 4: Zobrazení situace pøi snímání range finderem.

6.1 Kritéria pro výbìr pohledu

Pro splnìní podmínek pøedchozího odstavce je zvolen následující postup. Je vybrán jeden kandidát na snímání. Kolem nìho je zkonstruována kružnice viditelnosti. Ta je v souèasné implementaci pøedstavována vektorem s 360 položkami (reprezentují kruhové výseky po jednom stupni). Pro konstrukci této struktury je nutno projít celou matici. Každá neprázdná buòka vytvoøí v kružnici viditelnosti neprázdnou stopu. Samozøejmì, že jednotlivé stopy se mohou pøekrývat. I zde by nebylo nutno používat diskrétní reprezentaci, ale bylo by možno použít i reprezentaci vektorovou založenou na intervalech.

Z výsledné kružnice viditelnosti lze vyèíst smìry, kterými se lze dívat na vybraného kandidáta ke snímání a smìry, kterými nelze. Zvolme si Viditelnost_m=0, je-li paprsek odpovídající m v zákrytu s nìjakou plnou buòkou. Jinak Viditelnost_m=1.

Další kritérium Kolmost zohledòuje požadavek na kolmý pohled k povrchu tìlesa. Nech a je odklon normály dosud nasnímaného povrchu od nastavení RF pro jeden možný pohled. Kolmost pro danou konfiguraci vypoèteme následujícím zpùsobem:

Kolmost_i = vaha cos a_i + (1-vaha)

(4)

Vektor kritéria kolmosti [Kolmost\vec] = [Kolmost₀, ... Kolmost_n] vznikne složením jednotlivých kritérií.

Promìnná vaha reprezentuje sílu kritéria. Mùže nabývat hodnot v rozsahu (0,1). Pomìrnì uspokojivé výsledky lze dosáhnout napø. s hodnotou 0,5.

Poslední kritérium Pohyb_i zohledòuje pohyb snímacího èlenu z aktuální polohy do i-té polohy.

Po vypoèítaní všech tøí kritérií je potøeba provést jejich fúzi. Nejjednodušší operací je jednotlivá kritéria vynásobit po prvcích (položku po položce). Z tohoto dùvodu byl kladen požadavek na rozsah hodnot jednotlivých kritérií Kriterium Î < 0;1 > . Fúzí vlastnì vznikne celkové kritérium vhodnosti pohledu z urèitého smìru. Nazvìme jej [Pohled\vec].

Pohled_i = Viditelnost_i Kolmost_i Pohyb_i

(5)

6.2 Plánovací strategie mìøení

Celé mìøení je založeno na expanzi rùstových bodù. Je dobré si udržovat aktuální seznam rùstových bodù. Vždy si lze jeden rùstový bod vybrat a snažit se o jeho expanzi. K tomu slouží nalezení všech kandidátù na snímání v okolí zvoleného rùstového bodu. Vše je zakresleno na obr. . Vektor rùstových bodù je oznaèován symbolem p, aktuální rùstový bod pp, vektor všech kandidátù na snímání c a koneènì vybraný kandidát na snímání symbolem cc.

0.7

Figure 5: Algoritmus pro výbìr a snímání kandidátù podle rùstových bodù.

Po zvolení kandidáta na snímání nastupují jednotlivé strategie. Ty jsou primárnì urèeny k naplánování takové konfigurace mìøících senzorù, aby bylo možno co nejlépe zmìøit vybraného kandidáta na snímání. Jednotlivé snímací strategie se mohou spoleènì chovat jako stavový automat viz. obr. . Jednotlivé pøechody mezi stavy jsou znaèeny písmeny a jsou vysvìtleny u jednotlivých strategií.

0.7

Figure 6: Plánování strategií pro zmìøení vybraného kandidáta cc.

Základní strategie 0 - rovná èi mírnì zakøivená køivka

Základní strategie je optimalizována na snímání rovných a mírnì zakøivených obvodových linií. Celá situace je zakreslena na obrázku obr. .

V pøedchozím textu byl popsán zpùsob ohodnocování možných pohledù. Pøedpokládejme, že jsme si vypoèítali optimální pohled pro strategii 0. Následnì se pøesune Range-Finder na novì urèenou pozici a provede se mìøení. Po mìøení mùže nastat pìt základních situací (viz též pøechody na obr. 6):

A0 Byl vidìn požadovaný dosud neznámý bod: Tato situace je optimální. Rùstový bod se pøesune do novì namìøeného bodu, lze nalézt jeho kandidáty ke snímání a takto pokraèovat dále.
B0 Byl vidìn dosud neznámý bod, který je též kandidátem na snímání: Tato situace je velmi obdobná situaci pøedchozí. Lze ji zpracovat tak, jako kdybychom pùvodnì chtìli zmìøit právì nalezený bod.
C0 Byl vidìn jiný dosud neznámý bod: Uvedená situace ukazuje na výskyt nespojitosti povrchové køivky (popø. plochy). Vhodná následující akce je napø naplánování nového pohledu na již pøedem zvoleného kandidáta ke snímání.
D0 Byl vidìn již vidìný bod: Pohled na již vidìný bod znamená v každém pøípadì chybu. Buïto se mùže jednat o nepøesnost RF a nebo o špatné vyhodnocení viditelnosti. Rozumné zotavení pøedstavuje napø. zákaz pohledu danou konfigurací RF a naplánování nového pohledu na již pøedem zvoleného kandidáta ke snímání.
E0 Nebylo vidìt nic: Tato situace též poukazuje na možný výskyt nespojitosti povrchové køivky (popø. plochy). Na rozdíl od pøedchozí situace "Byl vidìn jiný dosud neznámý bod" nelze pøíliš odhadovat typ nespojitosti. Je možno také zakázat pohled danou konfigurací RF a naplánovat nový pohled na již pøedem zvoleného kandidáta ke snímání. Mnohem výhodnìjší se však jeví pøepnutí na jinou plánovací strategii.

0.6

Figure 7: Další pohled ve strategii 0

Základní strategie 0 by mohla teoreticky nasnímat jakýkoliv povrch. Optimální výsledky však dává jen v místech, kde se nevyskytují nespojitosti. Pøi výskytu nespojitosti je lepší zvolit jinou strategii a testovat hypotézy ohlednì typu nespojitosti.

Samozøejmì mùže pøi plánování pohledu nastat situace, kdy pohled na kandidáta na snímání naplánovat nelze. Pak se kandidát na snímání oznaèí jako nezmìøitelný a je nalezen nový kandidát.

Strategie 1 - ostrý úhel

Pokud snímání probíhala dobøe až do bodu, kdy nebylo nic vidìt, je nejpravdìpodobnìjší pøíèinou ostrý úhel na obvodové hranì tìlesa. Situaci zachycuje napø. obr. . Požadujeme strategii, která vzniklou situaci detekuje a pokraèuje v mìøení pøes ostrý úhel. Dále by bylo vhodné, kdyby zvolená strategie byla schopna ovìøit, zda se se skuteènì jedná o ostrý úhel èi zda se jedná o jinou formu zákrytu.

0.6

Figure 8: Strategie 1 - zpùsob plánování

Navržená strategie podle obrázku obr. 8 tyto požadavky splòuje. Jejím základem je pohled pøes kandidáta na snímání na rùstový èi jiný plný bod. Pak mohou nastat ètyøi situace:

A1 Byl vidìn požadovaný dosud neznámý bod.: Tato situace je optimální. Rùstový bod se pøesune do novì namìøeného bodu, lze nalézt jeho kandidáty ke snímání a takto pokraèovat dále.
B1 Byl vidìn jiný dosud neznámý bod.: Uvedená situace ukazuje na výskyt nespojitosti povrchové køivky (popø. plochy). Vhodná následující akce je napø naplánování nového pohledu na již pøedem zvoleného kandidáta ke snímání.
C1 Byl vidìn již vidìný bod.: Kandidát na snímání je prázdný a je nalezen nový kandidát na snímání. Strategie pokraèuje do té doby, dokud snímací senzor nenarazí na nìjaký plný bod.
D1 Nebylo vidìt nic.: Pokud nebylo nic vidìt, tak to znamená v této strategii chybu. Ve snímaném modelu existuje nìjaký zákryt, který nebyl dosud zjištìn. Je nejlepší v této pøepnout na jinou strategii.

Pøi použití popisované strategie vìtšinou nedojde k zákrytu, èímž je zaruèeno, že bude vidìn alespoò nìjaký plný bod. Pro ohodnocování a následné plánování vhodnosti pohledù lze využít pøedchozí kritéria viditelnosti a pohybu paže robota. Kritérium kolmosti je u strategie 1 nepoužitelné, protože hledáme pokraèování obvodové linie v místì ostrého úhlu. Místo nìho lze použít kritérium viditelnosti sousedních plných bodù (do omezené vzdálenosti) pøes kandidáta na snímání.

U výpoètu nových pohledù ve strategii 1 je vhodné použít kružnici viditelnosti. Kružnice viditelnosti zaruèuje, že u již namìøených dat nedojde k zákrytu.

Ve strategii 1 lze detekovat situaci (s využitím kružnice viditelnosti), kdy pohled na kandidáta na snímání naplánovat nelze. Pak se kandidát na snímání oznaèí za nezmìøitelný a je nalezen nový kandidát.

Strategie 2 - ostrý úhel

Použitím strategie 1 dochází ke zbyteènému pohybu senzoru pøi pøepnutí strategie. Pak se snímací senzor nepohybuje po hladké køivce. Proto byla definována nová strategie, která by mìla umožnit hladký prùchod snímacího senzoru pøes ostrou hranu i za cenu mírného snížení robustnosti.

0.6

Figure 9: Strategie 2 - zpùsob plánování

Strategie provádí jakési obcházení rùstového bodu, jak je ukázáno na obr. 9. Kandidáti na snímání pak leží na jednotkové kružnici kolem rùstového bodu. Snímací senzor testuje jednotlivé kandidáty po nastaveném úhlu. Pokud by se v modelu nacházel pouze ostrý úhel, pak snímaè vždy musí narazit na neprázdného kandidáta na snímání.

Horší situace, než v pøípadì ostrého úhlu, nastane v pøípadì zákrytu. Protože praktická kontrola snímaných dat ve strategii 2 je pomìrnì slabá⁵, mùže se stát, že snímaè zbyteènì obkrouží celý objekt. Ve strategii 2 nelze detekovat situaci, kdy požadovaný bod není zmìøitelný. To se nìkdy pozná až po obkroužení celého objektu snímacím senzorem.

Kružnice viditelnosti je v této strategii nepoužitelná vzhledem k neustálé zmìnì predikovaného bodu (pohybuje se po kružnici).

Ve strategii 2 mohou nastat následující situace:

A2 Byl vidìn dosud neznámý bod, který je kandidátem na snímání: Protože ve strategii 2 neexistuje pevnì definovaný kandidát na snímání, žádaného cíle bylo dosaženo.
B2 Byl vidìn jiný dosud neznámý bod: Uvedená situace ukazuje na výskyt nespojitosti povrchové køivky (popø. plochy). Nespojitost je nejspíše jiného typu než ostrý úhel. Vhodnou následující akcí by bylo pøepnutí na strategii 1.
C2 Byl vidìn již vidìný bod: Pohled na již vidìný bod znamená pøetoèení na pomyslné kružnici. Další otáèení již nemá smysl a tak by bylo nejlepší pøepnout na jinou strategii.
D2 Nebylo vidìt nic: U strategie 2 je tato situace normální. Doporuèenou další akcí je pokraèování snímání na dalším bodì pomyslné kružnice.

Ukonèení mìøící sekvence

Dùležitou èástí každého plánovacího procesu je ukonèení sekvence mìøení a prohlášení namìøených dat za výsledek mìøení. Zatím neomezujme mìøící sekvenci ani poètem mìøení ani dobou vyhrazenou na mìøení. Sekvence mìøení bude považována za ukonèenou když žádné nové mìøení nepovede ke zpøesnìní namìøeného modelu.

Pøi jednotlivých mìøeních dochází ke zpøesòování modelu. Algoritmus usiluje vždy o expanzi vybraného rùstového bodu. V jeho okolí je vybrán kandidát ke snímání. Po jeho zmìøení je kandidát na snímání oznaèen pøíslušným zpùsobem (plný/prázdný). Pokud jej nebylo možno z nìjakého dùvodu promìøit pak bude oznaèen za nezmìøitelný a bude nalezen nový kandidát. V každém pøípadì jeden kandidát na snímání nemùže být za kandidáta na snímání oznaèen dvakrát⁶.

Kandidáti na snímání obklopují rùstové body. Kolem jednoho rùstového bodu mùže být kandidátù jen omezené množství. Pokud dojde k vyèerpání všech kandidátù, pøestává být rùstový bod rùstovým bodem.

Definujme tedy konec snímací sekvence jako vyèerpání všech možných rùstových bodù.

7 Výsledky

7.1 Citlivost algoritmu na vzdálenost Laser-Kamera

Navržená a realizovaná plánovací strategie plánuje pohled na støedy ètvereèkù. Pøi pøekroèení úhlu mezi kamerou a laserem nad urèitou mez pøestane být plánovaè schopen naplánovat viditelnost nìkterých bodù, jak je ukázáno na obr. .

0.45

Figure 10: Simulovaná snímání objektu - vliv vzdálenosti LASER-Kamera na mìøení

Pro krátkou tyè je trajektorie RF plynulá, jak je vidìt na obr. 10(a). Èáry na obrázku obr. 10(b) znamenají pøejezdy robota z místa na místo. Nìkdy jsou zbyteènì dlouhé a to znamená málo efektivní plánování trajektorie. Dùvodem takového množství a délky pøejezdù je, že plánovaè již nemohl najít vhodný pohled na tìleso pøimìøenì blízko pøedchozímu pohledu.

Možné øešení vzniklé situace spoèívá v plánování pohledù ne na støedy, ale na obvod ètvercové buòky. Místo jednoho bodu by bylo možno uvažovat 4 body umístìné ve støedech jednotlivých hran a plánovat pohledy souèasnì na všechny body.

0.45

Figure 11: Ukázky dalších mìøení na simulovaných datech

7.2 Mìøení na reálných datech

Obrázky obr. a obr. ukazují namìøená data z reálného rangefinderu drženého v paži robota. První obr. zachycuje zbyteèné pøejezdy robota v dùsledku šumu v namìøených datech.

0.9

Figure 12: Záznam z mìøení na reálných datech

Zejména obr. ukazuje, že lze s plánovaèem provádìt experimenty i na reálných datech. Pro práci s reálnými daty je potøeba zvýšit robustnost navrhované plánovací strategie. Použitá plánovací strategie je trochu citlivá na chyby v datech. Jedná se zejména o situaci, kdy je nastavena kamera do urèité pozice a je namìøen bod, kterým by teoreticky paprsek laseru ani procházet nemìl.

0.9

Figure 13: Zdaøilý experiment z mìøení na reálných datech

A Implementace v Matlabu

A.1 Popis promìnných

circ kružnice viditelnosti bodu

Promìnná circ je vektorem s 360 položkami. Každá položka reprezentuje viditelnost daného bodu v kruhové výseèi o velikosti 1 stupnì. Protože v Matlabu nelze pøistupovat k položce è.0 je místo ní využita položka è. 360. Hodnota 0 v promìnné circ znamená, že do výseèe zasahuje plný objekt a hodnota 1 znamená, že výseè nezasahuje do nìjakého plného objektu.

M matice obsazenosti plochy.

Popisovaná plocha pøedstavuje obdélník. Každý element matice popisuje ètvercovou oblast se støedem v bodì [x,y]. První element odkazuje oblast [(0.5 : 1.5),(0.5 : 1.5)] se støedem v bodì [1,1].

Hodnoty elementù v matici:

0	o dané ploše není známa žádná informace
1	daná plocha odkazuje plné tìleso
-1	plocha je prázdná

-0.1	plocha je asi prázdná
0.1	plocha je asi plná

Vlastním algoritmem jsou použity 2 doplòkové hodnoty -0.1 a 0.1.

pos

urèuje nastavení rangefinderu. Pro 2D se jedná o matici o rozmìrech 2 x 3.

pos(1,:) = [Xzdroje_svìtla, Yzdroje_svìtla]
pos(2,:) = [Xsnímaèe, Ysnímaèe]
pos(3,:) = [Xsmìr, Ysmìr]

Tøetí bod popisuje nasmìrování rangefinderu. Paprsek prochází pøímkou od zdroje svìtla do bodu [Xsmìr, Ysmìr].

vec vektor èásti kontury

Matice vec obsahuje nìkolik okolních bodù z již nasnímané linie. Body
jsou uloženy do øádkù matice.

vec(bod,:) vrací [Xbodu,Ybodu]

A.2 Popis jednotlivých procedur a funkcí

Procedury jsou pro pøehlednost seøazeny podle abecedy.

[M]=bkrangef2d[M,pos,X]
[M]=bkrangef2d_[M,pos,X]

Funkce bkrangef2d provádí aktualizaci interního modelu na základì znalosti namìøených dat. Bod X by mìl být výsledkem funkce [X]=rangef2d(M,pos) . Matice modelu M použitá u funkce bkrangef2d by se nemìla shodovat s originální maticí popisující mìøený objekt. Na poèátku by mìla být inicializována nulami.

Procedura bkrangef2d je témìø shodná s procedurou bkrangef2d_. Jediný rozdíl spoèívá v lepší implementaci algoritmu raytracingu. Za pixely pøíslušející trasované úseèce jsou považovány všechny pixely, jejichž ètvercovou oblastí prochází sebemenší èást trasované úseèky.

[dir]=ComputeDirection(M,X,Count)

Funkce ComputeDirection vypoèítá smìrový vektor hranice, která prochází bodem X z matice M. Výpoèet smìrového vektoru je provádìn metodou nejmenších ètvercù z maximálnì Count bodù. Menší množství než Count je použito pouze v pøípadì, pokud na hranì již nelze nalézt další body.

[angle]=GetAngle(vec)

Funkce vypoèítá orientovaný úhel, který svírá vektor [1,0] s vektorem vec .

[c]=getcandidates2d(M,X)

Funkce najde všechny kandidáty ke scanovaní v okolí bodu X . Za kandidáta je považován takový bod, který ve svém osmiokolí souèasnì sousedí s prázdným bodem a plným rùstovým bodem (v našem pøípadì se jedná o bod X ). Kandidát sám musí mít v matici M hodnotu "neznámá hodnota". Je-li kandidátù více, pak má matice c více øádek.

[dist]=getdistance(X1,X2)

Funkce vypoèítá Euklidovskou vzdálenost dvou bodù X1 a X2 podle vzorce dist = Ö{ (X₁(1) - X₂(1))² + (X₁(2) -X₂(2))² } .

[d]=GetDistanceVC(X1,X2,P)

Funkce urèí vzdálenost bodu P od pøímky procházející body X1 a X2 .

[pp]=GetNearestPP(M2,p,pp_old)

Funkce najde nejbližší rùstový bod (Všechny rùstové body jsou umístìny v matici p.) ve kterém muže dojít k expanzi rekonstruované plochy. U vybraného bodu je ovìøeno zda se stále jedná o rùstový bod. V opaèném pøípadì je vybrán jiný bod pp. Pokud nelze vybrat žádný bod pp, pak funkce vrací [-1,-1].

[M]=getmodel()
[M]=getmodel2()
[M]=getmodel3()
[M]=getmodel4()
[M]=getmodel5()
[M]=getmodel6()

Rodina funkcí getmodel? vytvoøí nìjaký model a uloží jej do matice M.
Jedna z funkcí je vždy volána na poèátku snímacích skriptù.

[pp]=getpoints2d(M)

Funkce vrací vektor všech základních bodù. Za základní bod je považován takový bod, který sousedí minimálnì s jedním kandidátem ke snímání. Nelze-li nalézt ani jeden základní bod, pak funkce vrací hodnotu [-1,-1].

[vc]=getvc(a,b,c)

Funkce urèí souøadnici prùseèíku úseèky ab a výšky vc v trojúhelníku abc .

0.3

[circ]=MakeCircleOfVisibility(M,Xs)

Funkce MakeCircleOfVisibility vrací kružnici viditelnosti bodu Xs . Kružnice je vytváøena z dosud rekonstruované èásti modelu.

paintRF(M2)
paintRF(M2,pos,cc,x)
paintRF(M2,pos,cc,x,LastMovement)

Funkce vykreslí aktuální model spolu s pozicí rangefinderu na obrazovce. Souèasnì s tím je nakreslen právì namìøený bod x a kandidát ke snímání, na kterého byla naøízena kamera.
Volitelnì je možno nakreslit celou minulou trajektorii range-finderu. Každý øádek matice LastMovement obsahuje jednu polohu RF.

[pos,angles]=PlanNewPos(circ,Xs,OldPos)
[pos,angles]=PlanNewPos2(circ,Xs,pp)
[pos,angles]=PlanNewPos3(circ,Xs,pp,M2)
[pos,angles]=PlanNewPos4(circ,Xs,pp,M2,OldPos)
[pos,angles]=PlanNewPos5(circ,Xs,pp,M2,OldPos,LLine)

Plánovaèe nového pohledu ve strategii 0. K naplánování pohledu využívají kružnici viditelnosti circ vybraného bodu Xs . Nelze-li naplánovat pohled do Xs je vráceno pos=[-1,-1;-1,-1;-1,-1]. Pro testování je vhodné testovat pouze tøetí øádek matice pos .

Algoritmus PlanNewPos5 odhaduje aktuální pohled tak, aby procházel pøes požadovaný bod a souèasnì pøes predikovaný bod. LLine obsahuje poèet bodù, ze kterých je poèítána povrchová pøímka. Z povrchové pøímky je predikován nový bod pohledu.

[pos,angles]=PlanNewPos_s1_0(circ,Xs,pp)
[pos,angles]=PlanNewPos_s1_1(circ,Xs,pp,OldPos)
[pos,angles]=PlanNewPos_s1_2(circ,Xs,pp,vec,OldPos)

Plánovaèe nového pohledu ve strategii 1. Strategie 1 se používá zejména na ostrých hranách objektu. Je preferován pohled ve smìru pøes vybraný bod tak aby pohled konèil uvnitø již zmìøeného plného bodu. Nelze-li naplánovat pohled na Xs je vrácena pozice pos=[-1,-1;-1,-1;-1,-1].

[pos]=PlanNewPos_s2_2(pp,BaseFi)
[pos,rotation]=PlanNewPos_s2_2(M2,pp,BaseFi,rotation)

Plánovaèe nového pohledu ve strategii 2. Strategie 2 je též používána na ostrých hranách objektu. Nebere v úvahu viditelnost a pomalu otáèí se senzorem do té doby dokud nenarazí na nìjaký neprázdný bod. Nelze-li naplánovat pohled na Xs je vrácena pozice pos=[-1,-1;-1,-1;-1,-1]. K této situaci by došlo, kdyby se senzor otoèil o 360 stupòù a nic nezmìøil.

[X]=rangef2d(M,pos)
[X]=rangef2d_(M,pos)

Tato procedura provede jeden scan range-finderu. Ve dvourozmìrném pøípadì je výsledkem již pøímo pozice bodu [x_bodu,y_bodu] , ve kterém vyslaný paprsek narazil na neprùhledný bod v matici M a odrazil se zpìt do senzoru. Pokud by paprsek minul neprùhledné body a nebo se nemohl dostat ke snímacímu senzoru, vrací procedura hodnotu [-1,-1]. Pøi sledování úseèky ray-tracingem vzniká spojitá linie v osmiokolí.

Procedura rangef2d je témìø shodná s procedurou rangef2d_. Jediný rozdíl spoèívá v lepší implementaci algoritmu raytracingu v proceduøe rangef2d. Pixely trasované úseèky jsou všechny pixely, jejichž ètvercovou oblastí prochází sebemenší èást trasované úseèky.

rfconfig

Tato procedura nastaví globální promìnné popisující geometrii snímaèe. Pøi zmìnì geometrie snímacího èlenu postaèí nastavit pouze tyto konstanty. Jedná se o RFlength : obsahuje vzdálenost ohniska kamery od laseru. RFalpha : odklon roviny laseru (pøímky) od spojnice laser-kamera. RFbeta : odklon støední roviny (pøímky) kamery od spojnice laser-kamera. FRgamma šíøka svazku paprsku kamery ve 2D rovinì. Úhly jsou zadávány v radiánech.

[vec]=TraceContour(M,X,count)

Procedura sleduje konturu snímaného objektu do délky maximálnì count bodù. Trasování kontury zaèíná v bodì X.

[line]=TraceLine2D(Start,Stop,Bound)

Procedura trasuje úseèku vycházející z bodu Start a konèící v bodì Stop . Matice line obsahuje ve svých øádcích jednotlivé body pøíslušející zadané úseèce. Omezení Bound obsahuje souøadnice levého dolního rohu Bound(1,:) a pravého horního rohu Bound(2,:). Pokud sledovaná úseèka vystupuje ze zadaného obdélníku je uvažována jen ta její èást, která v nìm leží.

[circ]=UpdateCirc(circ,Xs,X)

Procedura provede aktualizaci kružnice viditelnosti pro bod X , který se stal neprùhledným. Bod Xs je støedem kružnice a pøedstavuje tzv. vztažný bod. Ve vektoru circ budou vynulovány všechny jednostupòové výseèe, která zasahují do ètvercové oblasti urèené bodem X .

verify=verifypoint2d(M,p)

Funkce ovìøí, zda je bod p tzv. rùstovým bodem. Pokud je, tak vrací 1 jinak 0.

A.3 Popis jednotlivých skriptù

circpix

Skript rekonstruující daný objekt pohybem po kružnici. Pøi pohybu se snímací prvek již nesmí vrátit.

fullpix

Skript rekonstruující daný objekt. Kritérium konce rekonstrukce nastane pøi vyèerpání všech možných kandidátù. Za kandidáta je považován bod, ve kterém mùže pokraèovat hrana.

stratpix

Skript rekonstruující daný objekt. Kritériem konce rekonstrukce je vyèerpání všech možných kandidátù. Za kandidáta je považován bod, ve kterém mùže pokraèovat hrana. Navíc je v tomto skriptu kladen dùraz na lepší trajektorii senzoru. Toho je dosaženo pøepínáním použitých strategií.

Footnotes:

¹Range-finder je zaøízení urèené ke snímání hloubkových map, tj. produkuje matici, jejíž prvky pøedstavují vzdálenosti od pozorovatele.

²Triangulovaný povrch je povrch popsaný možinou bodù v prostoru, které jsou seskupeny do sítì trojúhelníkù.

³NBV = Next Best View - nejlepší pohled, který pøinese nejvíce nové informace o snímaném tìlese.

⁴Ty by byly pro nás možná pøínosné

⁵Kontrolu snímaných dat definujme jako schopnost rozeznat z namìøených dat, že se skuteènì vyskytla konfigurace, kterou chceme zmìøit.

⁶Úlohu je potøeba ještì hloubìji analyzovat pro pøípad pøepínání strategií.

Go to the Fojtik's Home Page

File translated from T_EX by T_TH, version 3.74.
On 17 Apr 2006, 23:53.

Plánování pohybu range-finderu pro rekonstrukci modelu 3D tìlesa