delle parti degli oggetti
Nel campo della robotica, l’obiettivo di molte applicazione `e la comprensione del significato della scena osservata. Il riconoscimento degli oggetti e la loro corretta interpretazione sono requisiti fondamentali per compiti di pi`u alto livello, come ad esempio la manipolazione. A loro volta, il riconoscimento e l’interpretazione sono dipendenti dalla suddivisione dei dati in porzioni signi-ficative. Per questo motivo, una volta ottenuta la superficie di un oggetto, si cerca di risalire alle parti che lo compongono.
Esistono algoritmi e strumenti per caratterizzare una superficie rispetto ad una funzione reale. Lavorando sugli insiemi di livello, questi sono in grado di calcolare massimi, minimi e selle. Una delle funzioni di misurazione migliori allo scopo di segmentare l’oggetto `e la funzione integrale geodesica [19], che possiede l’importante pregio di essere invariante alla rotazione.
A partire da tali caratteristiche, si `e poi in grado di creare il corrispon-dente grafo di Reeb. Un grafo di questo tipo descrive infatti la connettivit`a degli insiemi di livello di un oggetto. I grafi di Reeb sono molto utilizzati per il riconoscimento di forme basato sulla topologia, che avviene mediante in-terrogazione di un database di grafi ed estrazione della classe corrispondente al grafo pi`u simile.
Rita Beltrami [5], durante il corso di Robotica, ha effettuato numerose procedure di acquisizione. Sono state fatte molte prove impiegando ogget-ti reali e costruiogget-ti ad-hoc, usando svariaogget-ti materiali e rivesogget-timenogget-ti. `E stata
motore dell’ambiente OpenRAVE, che utilizza l’algoritmo Rapidly-exploring Random Tree (RRT). Dopo questa fase si dispone di una lista di coordinate nello spazio dei giunti del manipolatore, corrispondenti ad una serie di pose da attraversare. Tale lista `e suddivisa in cinque parti, ognuna relativa ad una particolare fase della manipolazione:
partendo dalla posizione iniziale, ci si avvicina all’oggetto muovendosi a velocit`a elevata;
si inizia la fase di pre-grasp, ovvero quella antecedente alla presa, po-sizionando con cura la pinza in corrispondenza della parte dell’oggetto da afferrare, e concludendo con la chiusura della stessa;
muovendosi a velocit`a moderata si solleva dunque l’oggetto;
poi, aumentando la velocit`a, lo si sposta poco al di sopra del punto dove dev’essere rilasciato;
infine, si abbassa lentamente l’oggetto e si apre la pinza.
Sono state effettuate prove sperimentali, sia nell’ambiente simulato Open-RAVE, sia nell’ambiente reale utilizzando il robot Comau Smart SiX insieme alla pinza Schunk PG 70. Per l’esattezza, il locale del laboratorio e la con-figurazione hardware sono state replicate in simulazione. In questo modo `e stato possibile eseguire realmente le traiettorie pianificate da OpenRAVE, nonch´e collaudare alcune delle prese.
strato come sfruttare le relazioni di vicinanza tra scansioni e come costruire una mesh basata sui vincoli di prossimit`a.
A partire da una nuvola di punti, si effettuano tali elaborazioni con l’obiet-tivo di ottenere una rappresentazione della superficie del suddetto oggetto. La superficie pu`o essere descritta mediante una variet`a bidimensionale nello spazio euclideo tridimensionale, composta da pi`u triangoli (triangolazione) o in generale da pi`u poligoni.
Il sistema di acquisizione utilizzato garantisce il rispetto di alcune ipotesi, fondamentali per il funzionamento degli algoritmi esposti nel seguito. In primo luogo, ogni punto `e acquisito da un sensore avente una posizione nello spazio. Nel nostro caso questo punto `e rappresentato del centro del sensore laser.
I punti appartenenti alla medesima scansione giacciono inoltre sullo stes-so piano, identificato dal punto di osservazione e da due o pi`u punti della scansione. All’interno della scansione, inoltre, i punti sono ordinati secondo l’angolo formato dal raggio con il sistema di riferimento del sensore, e spesso
punti adiacenti sono anche vicini tra loro. L’affermazione si rivela inesatta soltanto in presenza di discontinuit`a, come accade ad esempio vicino ai con-torni di un oggetto. L’indice dei punti `e comunque un criterio da utilizzare come prima traccia di prossimit`a.
In ultimo luogo, si presuppone che i punti appartenenti a due scansioni acquisite in istanti temporali consecutivi siano con buona probabilit`a vici-ni tra loro. Questa coerenza temporale in alcuvici-ni casi non `e rispettata, ad esempio se la posa del sensore varia quando lo stesso `e spento, oppure nel caso vengano concatenate pi`u acquisizioni differenti. Una condizione del ge-nere tuttavia pu`o essere rilevata, attivando meccanismi pi`u complessi per l’identificazione del vicinato.
Nel seguito sono illustrati alcuni metodi per la ricostruzione di superfici a partire da dati sensoriali.
4.1 Costruzione incrementale
di triangolazioni su superfici
Un obiettivo del lavoro `e la costruzione incrementale della superficie di un oggetto a partire dai punti acquisiti con un sensore di prossimit`a per cui val-gono le ipotesi illustrate in precedenza. In particolare, le ipotesi sull’esistenza di un punto di osservazione e l’organizzazione delle scansioni suggeriscono la possibilit`a di elaborare l’insieme di punti dello spazio sfruttando l’apparte-nenza ad una variet`a bidimensionale. Per ogni nuovo punto misurato dal sensore, la superficie iniziale viene modificata in maniera tale da includerlo all’interno di essa.
4.1.1 Triangolazione di Delaunay
Utilizzando le informazioni provenienti dal sensore, ovvero l’orientamento del punto sulla superficie che racchiude l’oggetto, l’obiettivo `e ricostruire con buona approssimazione la sua superficie. A questo scopo ci si avvale delle
Dato un insieme di punti, un diagramma di Voronoi bidimensionale `e una decomposizione del piano formata associando ad ogni punto una determinata regione di influenza (figura 4.1a). Chiamato P = {p1, p2, . . . , pn} ⊆ R2questo insieme, la regione di Voronoi per pi ∈ P `e l’insieme di punti x ∈ R2 che sono pi`u vicini al sito pi che ad ogni altro sito pj ∈ P . In altre parole,
Vpi = {x ∈ R2 | kx − pik ≤ kx − pjk , ∀pj ∈ P , j 6= i}.
Poich´e ogni punto deve possedere almeno un vicino in P , le regioni di Voronoi coprono l’intero piano. I punti che appartengono a pi`u di una regione, ovvero i punti equidistanti da due o pi`u siti, formano il diagramma di Voronoi dell’insieme P . Questo tipo di diagrammi risulta utile per determinare, per ogni punto, quale sia il sito pi`u vicino.
La triangolazione di Delaunay, come mostrato in figura 4.1b, `e il duale di un diagramma di Voronoi. Essa si ottiene connettendo i punti pi ∈ P tra loro se e soltanto se le regioni di Voronoi hanno un segmento in comune. Il risultato generale `e il conseguimento di una suddivisione del piano in regioni triangolari (figura 4.2a). All’interno di tale triangolazione, vale la seguente propriet`a: la circonferenza circoscritta ad ogni triangolo non contiene alcun vertice di altri triangoli (figura 4.2b).
La descrizione intuitiva del concetto di “variet`a” `e quella di seguito il-lustrata. Per disegnare una mappa della superficie terrestre, `e necessario proiettare la superficie sferica convessa su di un piano. Non essendo possi-bile effettuare questa operazione per l’intera sfera, bisogna suddividerla in
(a) Diagramma di Voronoi (b) Triangolazione di Delaunay
Figura 4.1: Diagramma di Voronoi con sovrapposizione della relativa triangolazione di Delaunay.
(a) Triangolazione di Delaunay (b) Circonferenze circoscritte
Figura 4.2: Triangolazione di Delaunay con visualizzazione delle circonferenze circoscritte ad ogni triangolo.
Il lavoro svolto si basa sui risultati ottenuti da Guibas e Stolfi [18] per quanto riguarda la sfera ed il piano esteso ˆR2 = R2 ∪ {∞}. Ci si pone l’obiettivo di adoperare la soluzione proposta dagli autori per triangolare una variet`a all’interno dello spazio tridimensionale, adattando in maniera opportuna le primitive geometriche.
4.1.2 Costruzione della triangolazione di Delaunay
con quad-edge
Ogni suddivisione, come la triangolazione di Delaunay, pu`o essere rappresen-tata da strutture dati in grado di mettere in relazione tra loro gli elementi della suddivisione, ossia i vertici, i lati e le facce che la costituiscono. Le relazioni tra tali elementi, per esempio l’incidenza dei lati o l’adiacenza delle facce) possono essere convenientemente rappresentata da strutture basate su grafo.
Un esempio di struttura dati nota in letteratura ed ideata per trattare le triangolazioni `e il quad-edge [18]. In questo modo si rappresenta ovviamente anche la suddivisione duale, ovvero il diagramma di Voronoi. Il quad-edge `e costituito da tre tipi di elementi: i vertici, i lati e le facce (figura 4.3). Ogni lato possiede due puntatori agli altrettanti vertici connessi dal lato, e due puntatori per le relative facce che condividono il lato. Ciascun lato comprende in se stesso, quindi, due archi orientati che connettono vertici e
Figura 4.3: Elementi della struttura dati quad-edge.
facce. Inoltre `e possibile passare dal grafo vertici-lati al suo duale facce-lati senza ulteriore elaborazione.
Le operazioni topologiche di base su una tale struttura sono la creazione di un nuovo arco e la cosiddetta operazione di “giunzione” tra due archi (dal termine inglese splice). L’effetto dell’esecuzione quest’ultima sulla struttura dati `e il seguente:
se gli archi condividono lo stesso vertice di origine, ma non hanno la medesima faccia sulla sinistra, allora i vertici verranno separati e le facce saranno unite;
se gli archi non condividono il medesimo vertice di origine, ma sono connessi sulla sinistra alla stessa faccia, allora le facce verranno separate ed i vertici saranno uniti.
Nel caso in esame, in cui gli archi fanno parte di un diagramma di Vo-ronoi o di una triangolazione di Delaunay, alcuni semplici interventi quali la
esposte sono presentati in [24]. Servendosi di questi meccanismi `e stato svi-luppato un algoritmo per la costruzione incrementale della triangolazione di Delaunay relativa alla superficie di un oggetto.
Inizializzazione della triangolazione
Poich´e ogni punto viene inserito singolarmente all’interno della struttura at-tualmente esistente, `e necessario inizializzare la triangolazione. In altre paro-le, bisogna definire una superficie entro la quale saranno inclusi tutti i punti. Un’inizializzazione conveniente consiste in una singola faccia triangolare, ov-vero composta da tre archi e tre vertici, di dimensioni sufficientemente grandi da contenere le proiezioni dei punti della scansione.
L’area di lavoro del manipolatore adoperato `e sicuramente limitata. Gra-zie a questa condizione, si possono facilmente trovare dei limiti per le coor-dinate x, y, z. Dati i limiti dell’area di lavoro xmin = −2 m, xmax = 2 m, ymin = 0 m ed ymax = 2 m, sono stati utilizzati i seguenti valori per i primi tre vertici: A = (5, −1, 0) m, B = (0, 10, 0) m, C = (−5, −1, 0) m. La scelta di un valore nullo per la coordinata z `e motivata dal fatto che il punto di os-servazione nel setup utilizzato `e sicuramente collocato al di sopra della quota zero.
I tre vertici A, B, C vengono connessi con altrettanti archi (figura 4.4). `E importante sottolineare ancora una volta che la faccia ABC deve essere in grado di contenere tutti i punti inseriti nel seguito, pena il malfunzionamento
0 2 4 6 8 10 -6 -4 -2 0 2 4 6 asse y asse x A B C Area di lavoro
Figura 4.4: La triangolazione iniziale e l’area di lavoro del manipolatore.
dell’algoritmo. Tale faccia deve essere memorizzata al fine di essere adoperata durante le fasi successive della ricerca.
Ricerca nella suddivisione
Dopo aver effettuato una scansione, l’algoritmo prevede l’inserimento di ogni punto separatamente dagli altri. Il punto di osservazione, coincidente con il centro del sensore laser, `e il medesimo per ciascuno dei punti appartenenti alla scansione. Prima di inserire un singolo punto, si procede alla ricerca della faccia che contiene la proiezione del punto se osservato dal centro del sensore. Siccome il punto di vista `e conosciuto, `e possibile adottare alcune semplificazioni illustrate nel seguito.
Per poter effettuare una ricerca sulla superficie orientata rappresentata dalla triangolazione, occorrono delle primitive geometriche che consentano di determinare la posizione relativa degli elementi della suddivisione, per
0 2 4 6 -2 0 2 4 6 8 10 x y
Figura 4.5: Ricerca della faccia contenente la proiezione del punto.
esempio se un punto giace “a destra” oppure “a sinistra” del lato di una faccia. Nel seguito verranno illustrate le primitive applicate al problema in esame.
La procedura di ricerca `e illustrata nell’algoritmo 4.1. Dato un nuovo pun-to p da inserire, e calcolata la semiretta uscente dall’osservapun-tore o passante per p, si vuole trovare una faccia f che intersechi tale semiretta (figura 4.5). Perch´e la ricerca abbia inizio, `e necessario mantenere un puntatore alla fac-cia f0 che sar`a la prima ad essere esaminata dalla procedura. Un’opportuna scelta di f0 pu`o accelerare significativamente la ricerca.
In primo luogo si controlla se la faccia corrente risulta essere visibile. Il piano passante per i tre vertici della faccia suddivide lo spazio in due parti. A seconda dell’orientamento degli archi, il punto di osservazione pu`o essere dalla parte visibile (superiore) oppure dalla parte non visibile (inferiore) della superficie.
L’o-rigine e la destinazione di ognuno dei tre archi formano con p ed o altrettanti tetraedri. Grazie al segno del volume di questi tetraedri si `e in grado di deter-minare se il punto p si trova a destra (negativo) oppure a sinistra (positivo) dell’arco ei quando visto dall’osservatore.
Inoltre, prendendo gli archi in senso antiorario, ciascun arco avr`a alla sua sinistra la medesima faccia, ed alla sua destra una faccia differente. Anche per tali facce fi si effettua un controllo di visibilit`a. Questo serve a determinare in che direzione spostarsi in funzione della visibilit`a della faccia di partenza e della faccia di destinazione.
Se la faccia di partenza o la faccia di destinazione sono visibili ed il volume del tetraedro indica che il punto p si trova alla destra dell’arco, ci si muove lungo quella direzione; lo stesso movimento verso destra accade nel caso in cui n´e la faccia di partenza n´e la faccia di destinazione sono visibili, ma il volume del tetraedro indica che p `e a sinistra dell’arco. Nel caso in cui nessuna di queste condizioni di spostamento sia soddisfatta, significa che il punto `e all’interno della faccia corrente, e la ricerca ha termine.
Stabilito che una faccia `e per definizione visibile se i tre archi che la deli-mitano formano un circuito antiorario quando visti dal punto o, esaminiamo con maggiore dettaglio la condizione di visibilit`a (algoritmo 4.2). Questa con-dizione equivale ancora una volta a studiare il segno del volume del tetraedro formato dai vertici della faccia e dall’osservatore.
Il volume di un generico tetraedro avente vertici a, b, c, o pu`o essere cal-colato con la seguente formula, come suggerito da [29] in forma generale per un simplesso di dimensione arbitraria:
V = 1 6 ax ay az 1 bx by bz 1 cx cy cz 1 ox oy oz 1
Il predicato geometrico VolumeTetraedro `e dunque equivalente al computo del determinante di una matrice, ovvero ad effettuare semplici somme di
for i = 1 → 3 do ei ← ArcoFaccia(f0, i) si ← OrigineArco(ei) di ← DestinazioneArco(ei) ti ← VolumeTetraedro(si, di, p, o) fi ← FacciaDestra(ei) vi ← Visibile(fi, o) end for if (v0∨ v1) XOR (t1 < 0) then f0 ← f1
else if (v0∨ v2) XOR (t2 < 0) then f0 ← f2
else if (v0∨ v3) XOR (t3 < 0) then f0 ← f3
else
return f0 end if end loop
Algoritmo 4.2 La condizione booleana Visibile Input: faccia da esaminare f , punto di osservazione o
Output: vero se la parte superiore della faccia `e visibile, falso altrimenti for i = 1 → 3 do
ei ← ArcoFaccia(f, i) di ← DestinazioneArco(ei) end for
return VolumeTetraedro(d1, d2, d3, o) < 0
prodotti. Per semplicit`a, si definiscono i valori di appoggio α = a − o, β = b − o, γ = c − o e poi si procede a calcolare il volume
V = 1
6(−αzβyγx+ αyβzγx+ αzβxγy − αxβzγy− αyβxγz+ αxβyγz) . Tale volume pu`o avere segno sia positivo che negativo, in base all’ordinamento dei vertici a, b, c osservati dal restante vertice o: positivo se sono in senso orario, negativo se sono in senso antiorario.
Avendo imposto come condizione iniziale la creazione forzata della pri-ma faccia, sappiamo con certezza che la proiezione del primo punto inserito ricadr`a entro di essa. Per il punto successivo, il risultato della ricerca sar`a una delle tre facce formatesi durante l’inserimento del primo punto. Questo ragionamento si pu`o estendere a tutti i punti che verranno inseriti in seguito, sempre a patto che le ipotesi sull’area di lavoro siano rispettate.
Dopodich´e si effettua un controllo per evitare che il nuovo punto inserito coincida con uno gi`a esistente oppure ricada a poca distanza da un arco attualmente presente (algoritmo 4.3). A questo scopo, per ciascun arco della faccia identificata mediante la ricerca, si esaminano: la distanza tra il punto e l’origine, la distanza tra il punto e la destinazione, la lunghezza dell’arco, la distanza del punto dall’arco.
Qualora il punto risultasse troppo vicino ad un vertice, oppure troppo vicino all’arco tra due vertici della faccia, esso viene scartato in quanto con-siderato non importante al fine di aggiungere informazioni sulla superficie.
for i = 1 → 3 do ei ← ArcoFaccia(f0, i) si ← OrigineArco(ei) di ← DestinazioneArco(ei) psi ← DistanzaPuntoPunto(p, si) pdi ← DistanzaPuntoPunto(p, di) sdi ← DistanzaPuntoPunto(si, di) if psi < ε ∨ pdi < ε then ri ← vero else if psi > sdi∨ pdi > sdi then ri ← f also else ri ← DistanzaPuntoSegmento(p, si, di) < ε end if end for return r1∨ r2∨ r3
-2 0 2 4 6 8 10 12 -6 -4 -2 0 2 4 6 asse y asse x e1 e2 e3 f p
(a) Inserimento del punto
-2 0 2 4 6 8 10 12 -6 -4 -2 0 2 4 6 asse y asse x e1 e2 e3 f p eb
(b) Inserimento del primo arco
-2 0 2 4 6 8 10 12 -6 -4 -2 0 2 4 6 asse y asse x e1 e2 e3 f p fn eb
(c) Inserimento del secondo arco
-2 0 2 4 6 8 10 12 -6 -4 -2 0 2 4 6 asse y asse x e1 e2 e3 f p fn eb
(d) Inserimento del terzo arco
Figura 4.6: Inserimento di un nuovo punto p nella faccia f .
In tutti gli altri casi esso `e invece conservato ed inserito nella triangolazione, come illustrato nel seguito.
Inserimento ed aggiornamento della struttura
In questa fase, il nuovo punto viene inserito nello spazio determinato dalla faccia f che ne contiene la proiezione (algoritmo 4.4). Si identificano in primo luogo gli archi e1, e2, e3 presenti sul bordo della faccia, e si procede creando un nuovo arco eb tra il punto p ed il vertice origine di e1. Tale arco avr`a inizialmente la stessa faccia f sia sulla sinistra che sulla destra. Inoltre, effettuando l’operazione di giunzione CongiungiArchi si sistemano i collegamenti di eb con l’arco e1.
con-ei ← ArcoFaccia(f, i) end for eb ← NuovoArco(OrigineArco(e1), p) FacciaSinistra(eb) ← f FacciaDestra(eb) ← f CongiungiArchi(eb, e1) for i = 1 → 2 do fn← NuovaFaccia FacciaSinistra(ei) ← fn FacciaDestra(eb) ← fn eb ← ConnettiArchi(ei, ArcoSimmetrico(eb)) FacciaSinistra(eb) ← fn end for FacciaDestra(eb) ← f
A questo punto bisogna assicurarsi che la triangolazione cos`ı modificata sia ancora una triangolazione di Delaunay. Il criterio utilizzato nel caso bidimensionale, ovvero l’assenza di altri punti all’interno della circonferenza circoscritta ad ogni triangolo, non `e valido in uno spazio a tre dimensioni.
Si analizzano pertanto tutti gli archi che potrebbero dover essere modifi-cati dopo l’inserimento del punto p (algoritmo 4.5). In particolare, per ogni arco ei si memorizzano l’origine s e la destinazione d; si prende nota poi
della destinazione t dell’arco precedente rispetto all’origine, ovvero dell’arco pi`u vicino muovendosi ruotando in senso orario intorno all’origine dell’arco.
Qualora osservando t dal punto o esso si trovi dal lato destro dell’arco ei, si analizza il triangolo s, d, t per controllare se il nuovo punto p si trova all’interno della sfera circoscritta a tale triangolo. Se anche questa condizione `e soddisfatta, si procede a scambiare l’arco ei con un nuovo arco il quale connette i punti t, p, avendo cura di sistemare correttamente le facce di tutti gli archi del quadrilatero di vertici s, t, d, p.
Algoritmo 4.5 Capovolgimento di alcuni archi
Input: nuovo punto p, osservatore o, insieme degli archi da esaminare E for all ei ∈ E do
s ← OrigineArco(ei) d ← DestinazioneArco(ei)
t ← DestinazioneArco(ArcoPrecedenteOrigine(ei))
if LatoArco(s, d, t, o) = destra ∧ InternoCircosfera(p, s, d, t) then ScambiaArco(ei) {origine, destinazione, faccia sinistra, faccia destra} end if
end for
Il capovolgimento degli archi per soddisfare il requisito di Delaunay av-viene quindi secondo una determinata proposizione logica. Essa `e formata combinando due parti: la prima serve ad assicurarsi che il punto t si tro-vi rigorosamente a destra dell’arco ei; la seconda `e un’approssimazione del criterio di ottimalit`a di Delaunay nel caso tridimensionale.
Il predicato geometrico LatoArco, illustrato nell’algoritmo 4.6, effettua il calcolo del volume del tetraedro (s, d, t, o). Per quanto visto precedentemente, il segno del volume del tetraedro varia in base all’ordinamento dei vertici s, d, t osservati da o. Se esso `e positivo i vertici sono in senso orario, pertanto il punto t si trova a destra dell’arco (s, d). Viceversa, un volume negativo significa che i vertici sono in senso antiorario, e che quindi il punto t si trova a sinistra dell’arco (s, d).
return sinistra else if V > ε then return destra else return centro end if
Il criterio di pseudo-ottimalit`a di Delaunay InternoCircosfera viene verificato calcolando dapprima il circocentro della faccia triangolare (s, d, t) sul piano passante per questi tre punti, ovvero il centro della circonferenza circoscritta al triangolo.
Per sicurezza, nello spazio tridimensionale si verificano le distanze tra il circocentro ed i vertici del triangolo, prendendo la distanza massima come raggio della sfera. Il punto p risulta essere contenuto nella sfera circoscritta alla faccia (s, d, t) semplicemente se la distanza tra punto e circocentro `e minore del raggio della sfera.
4.1.3 Problemi incontrati
Vi sono casi in cui l’algoritmo finora esposto `e perfettamente funzionante, altri in cui il risultato ottenuto non `e affatto soddisfacente. I problemi