Trovare ripetizioni in gruppi di coordinate
Ciao forum, ho un problema (e questo si capiva..).
Al momento sto trafficando con un rtls, ovvero un sistema di posizionamento che usa un laser (mobile) e dei target riflettenti (fissi) + triangolazione + trilaterazione.
Il mio problema non è nel trovare la posizione ma nel trovare un sistema per disporre in maniera "ottimale" i target (mi basta che non si diano fastidio a vicenda).
Il problema principale è che quando il numero di target sale, iniziano a presentarsi delle "ripetizioni" nello schema dei target stessi e il sistema di misura sbaglia a misurare.
In pratica crede di essere da un'altra parte.
Riassumendo io ho un insieme di coordinate x,y e, offline, dovrei cercare tra queste coordinate degli schemi, dei pattern, ripetuti (e poi rimuoverli...).
(Magari è un problema già noto con la soluzione in letteratura, al che chiedo solo il nome del problema.)
La soluzione di forza bruta (reticolo di posizioni da analizzare da confrontare una con l'altra) non mi ispira molto e non so quanto possa essere precisa/affidabile.
Siccome le ripetizioni nei target ci sono indipendentemente dall'osservatore ho pensato di studiare i triangoli simili che questi target formano.
Ho pensato che si poteva fare un ciclo su tutte le triple di target, costruendo in un sotto ciclo tutti gli altri triangoli possibili e valutandone con una funzione di costo la somiglianza.
Poi, per avere un output grafico, avevo pensato di usare una funzione potenziale in xy che ha dei picchi in corrispondenza dei triangoli simili di altezza pari alla funzione di costo.
In questo modo però ottengo solo dove c'è una somiglianza, ma non il con chi. Questo sarebbe importante invece.
Qualche suggerimento?
Una parte su cui proprio non mi trovo è la costruzione di una funzione di costo per la somiglianza da introdurre poi come input per il potenziale.
ps: lo script mi farebbe comodo farlo in matlab..
Al momento sto trafficando con un rtls, ovvero un sistema di posizionamento che usa un laser (mobile) e dei target riflettenti (fissi) + triangolazione + trilaterazione.
Il mio problema non è nel trovare la posizione ma nel trovare un sistema per disporre in maniera "ottimale" i target (mi basta che non si diano fastidio a vicenda).
Il problema principale è che quando il numero di target sale, iniziano a presentarsi delle "ripetizioni" nello schema dei target stessi e il sistema di misura sbaglia a misurare.
In pratica crede di essere da un'altra parte.
Riassumendo io ho un insieme di coordinate x,y e, offline, dovrei cercare tra queste coordinate degli schemi, dei pattern, ripetuti (e poi rimuoverli...).
(Magari è un problema già noto con la soluzione in letteratura, al che chiedo solo il nome del problema.)
La soluzione di forza bruta (reticolo di posizioni da analizzare da confrontare una con l'altra) non mi ispira molto e non so quanto possa essere precisa/affidabile.
Siccome le ripetizioni nei target ci sono indipendentemente dall'osservatore ho pensato di studiare i triangoli simili che questi target formano.
Ho pensato che si poteva fare un ciclo su tutte le triple di target, costruendo in un sotto ciclo tutti gli altri triangoli possibili e valutandone con una funzione di costo la somiglianza.
Poi, per avere un output grafico, avevo pensato di usare una funzione potenziale in xy che ha dei picchi in corrispondenza dei triangoli simili di altezza pari alla funzione di costo.
In questo modo però ottengo solo dove c'è una somiglianza, ma non il con chi. Questo sarebbe importante invece.
Qualche suggerimento?
Una parte su cui proprio non mi trovo è la costruzione di una funzione di costo per la somiglianza da introdurre poi come input per il potenziale.
ps: lo script mi farebbe comodo farlo in matlab..
Risposte
Vediamo se ho capito: ti trovi in un certo punto nel piano, fai una scansione tutt'intorno (360 gradi) con il laser e ottieni una lista di coppie angolo-distanza, una per ciascun marker visibile (i marker riflettono in tutte le direzioni). Da questa lista risali alle coordinate x, y dei marker nel tuo riferimento, e quindi cerchi di ottenere la rototraslazione che ti riporta nel riferimento dei marker, in modo da sapere dove sei. Fin qui è corretto?
Si, è proprio così.
Io ho pensato che la cosa migliore sia analizzare i marker indipendentemente dal soggetto che effettua la misura.
Per due motivi:
1) se ci sono schemi di posizionamento (dei target) ripetuti, ci sono indipendentemente da me che misuro.
2) se analizzo direttamente i target non devo preoccuparmi di determinare le zone di interesse per l'osservatore, cioè quelle in cui posso effettivamente passare, ma diventa una soluzione più generale.
Al momento stavo pensando di provare così:
- ripeto la procedura su ogni target,
- costruisco una curva con ascisse 0-360° e come ordinate la distanza di quello che leggo (calcolo, per ogni target, tutte le coppie distanza-angolo e le ordino in base all'angolo),
A questo punto penso di avere una funzione abbastanza rappresentativa della "visuale" che ha ogni target, devo trovare un metodo efficace per il confronto.
Se in questa funzione io non assegno la "distanza" solo in un angolo preciso, ma la distribuisco con qualche "campana" opportuna attorno a quell'angolo, dovrei avere una funzione ancora più fisicamente aderente a quello che il laser effettivamente legge.
Adesso il punto è come confrontare le varie funzioni...
Io ho pensato che la cosa migliore sia analizzare i marker indipendentemente dal soggetto che effettua la misura.
Per due motivi:
1) se ci sono schemi di posizionamento (dei target) ripetuti, ci sono indipendentemente da me che misuro.
2) se analizzo direttamente i target non devo preoccuparmi di determinare le zone di interesse per l'osservatore, cioè quelle in cui posso effettivamente passare, ma diventa una soluzione più generale.
Al momento stavo pensando di provare così:
- ripeto la procedura su ogni target,
- costruisco una curva con ascisse 0-360° e come ordinate la distanza di quello che leggo (calcolo, per ogni target, tutte le coppie distanza-angolo e le ordino in base all'angolo),
A questo punto penso di avere una funzione abbastanza rappresentativa della "visuale" che ha ogni target, devo trovare un metodo efficace per il confronto.
Se in questa funzione io non assegno la "distanza" solo in un angolo preciso, ma la distribuisco con qualche "campana" opportuna attorno a quell'angolo, dovrei avere una funzione ancora più fisicamente aderente a quello che il laser effettivamente legge.
Adesso il punto è come confrontare le varie funzioni...
Aggiungo un punto di cui ti chiedo conferma: l'acquisizione non tiene conto di tutti i marker ma solo di quelli più vicini. Perché mi sembra che, se tu potessi tener conto di tutti i marker (tranne quelli eventualmente occultati da altri), la determinazione del punto in cui si trova il laser non sarebbe difficile.
Potendo invece analizzare solo una porzione della distribuzione di marker, c'è la possibilità che la disposizione in questa porzione sia ambigua.
Se è così, forse potresti disporre i marker su una griglia ottenuta a partire da una griglia regolare, spostandone ciascun nodo in una direzione pseudorandom.
Esistono delle sequenze pseudorandom, sia mono che bidimensionali, studiate in modo che qualsiasi sottosequenza contigua di dimensione maggiore o uguale ad una certa dimensione minima sia univoca. Vengono utilizzate, ad esempio, in certi encoder di posizione assoluti, al posto dei vecchi Gray codes. Se non ricordo male esiste anche un encoder di posizione bidimensionale, prodotto forse dalla Heidenhain, basato su questo principio.
Frugando nei meandri del mio hard disk ho trovato questi titoli al proposito:
Tuvi Etzion, Constructions for Perfect Maps and Pseudorandom Arrays, IEEE Transactions on Information Theory, vol 34, no 5, September 1988
Sheelagh Lloyd, John Burns, Finding the Position of a Subarray in a Pseudo-random Array, HP Laboratories Bristol, October 1991
Subhash Kak, The Algebra of Two Dimensional Patterns
Non dovresti avere difficoltà a trovarli in rete. Tieni presente che questi pseudorandom arrays sono noti anche come M-codes.
Poi ci sono altre possibili soluzioni che però stravolgerebbero quel che hai già; ad esempio, potresti codificare le posizioni dei nodi usando più target disposti in verticale, ma per leggerli dovresti avere più laser, o un laser a lama; oppure potresti usare una telecamera al posto del laser e dei barcode 2D al posto dei marker. In questo caso, se le dimensioni del barcode 2D sono note, ti basterebbe acquisirne uno per sapere dove si trova la telecamera. C'è anche un prodotto commerciale, della Sick mi pare, che funziona proprio così.
Potendo invece analizzare solo una porzione della distribuzione di marker, c'è la possibilità che la disposizione in questa porzione sia ambigua.
Se è così, forse potresti disporre i marker su una griglia ottenuta a partire da una griglia regolare, spostandone ciascun nodo in una direzione pseudorandom.
Esistono delle sequenze pseudorandom, sia mono che bidimensionali, studiate in modo che qualsiasi sottosequenza contigua di dimensione maggiore o uguale ad una certa dimensione minima sia univoca. Vengono utilizzate, ad esempio, in certi encoder di posizione assoluti, al posto dei vecchi Gray codes. Se non ricordo male esiste anche un encoder di posizione bidimensionale, prodotto forse dalla Heidenhain, basato su questo principio.
Frugando nei meandri del mio hard disk ho trovato questi titoli al proposito:
Tuvi Etzion, Constructions for Perfect Maps and Pseudorandom Arrays, IEEE Transactions on Information Theory, vol 34, no 5, September 1988
Sheelagh Lloyd, John Burns, Finding the Position of a Subarray in a Pseudo-random Array, HP Laboratories Bristol, October 1991
Subhash Kak, The Algebra of Two Dimensional Patterns
Non dovresti avere difficoltà a trovarli in rete. Tieni presente che questi pseudorandom arrays sono noti anche come M-codes.
Poi ci sono altre possibili soluzioni che però stravolgerebbero quel che hai già; ad esempio, potresti codificare le posizioni dei nodi usando più target disposti in verticale, ma per leggerli dovresti avere più laser, o un laser a lama; oppure potresti usare una telecamera al posto del laser e dei barcode 2D al posto dei marker. In questo caso, se le dimensioni del barcode 2D sono note, ti basterebbe acquisirne uno per sapere dove si trova la telecamera. C'è anche un prodotto commerciale, della Sick mi pare, che funziona proprio così.
Grazie per la risposta.
Al momento sono da tenere virtualmente in considerazione tutti i marker, nel senso che tutti sono potenzialmente leggibili, mentre per il calcolo del posizionamento vengono utilizzati solo i "tot" più vicini (5).
Da quello che ho capito al volo tu mi consigli come disporre la griglia di target ma questa è una soluzione che non posso seguire: la disposizione dei target è già stata effettuata e ha dei requisiti "fisici" che impongono il posizionamento solo in certi punti (i target possono essere montati solo li, praticamente).
Il mio problema è determinare se, su uno schema di posizioni dei target (già fisicamente installati), sono presenti zone ambigue (e successivamente correggere queste zone aggiungendo o togliendo un target).
Al momento sono da tenere virtualmente in considerazione tutti i marker, nel senso che tutti sono potenzialmente leggibili, mentre per il calcolo del posizionamento vengono utilizzati solo i "tot" più vicini (5).
Da quello che ho capito al volo tu mi consigli come disporre la griglia di target ma questa è una soluzione che non posso seguire: la disposizione dei target è già stata effettuata e ha dei requisiti "fisici" che impongono il posizionamento solo in certi punti (i target possono essere montati solo li, praticamente).
Il mio problema è determinare se, su uno schema di posizioni dei target (già fisicamente installati), sono presenti zone ambigue (e successivamente correggere queste zone aggiungendo o togliendo un target).
Se i target non sono tantissimi potresti fare una ricerca bruta. Se sono tantissimi, potresti provare col geometric hashing.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo