Trovare disposizione di punti in un'insieme di punti qualsiasi!

[Tommo]

mi sto arrovellando da un pò con questo problema, che fa parte di un sistema molto più grosso (che pian piano ho messo insieme), ma è un tassello fondamentale.

Allora:
un Punto è una coppia (posizione, tipo).

un Pattern è un insieme di punti.

In ingresso ho 2 pattern, il primo è una "reference" che deve essere trovata nel secondo.

"reference" può apparire più di una volta, e può essere traslato, ruotato e scalato, e i suoi punti possono trovarsi in posizioni leggermente diverse rispetto all'originale.

In output serve una lista (Pattern, affinity) di tutti i match con la loro somiglianza alla Reference, in percentuale.

Se qualcuno ha idee, o anche solo un link utile, lo stimo moltissimo
Onestamente non riesco a tirare giù nemmeno un algoritmo naive, è un problema bello tosto

Discuss.

[PGI-Bis]

Sono praticamente certo che cercando qualcosa sul riconoscimento ottico di pattern si trovino degli algoritmi ad hoc.

Comunque il problema si risolve, ad esempio, determinando quali sono le costanti espresse dal pattern che devi trovare. Per un insieme di tre o più punti le costanti sono gli angoli formati dalle rette che passano per due coppie di punti e rapporti tra le lunghezze dei segmenti.

Verrebbe meglio con un disegnino ma se io ho tre punti A,B,C, ne piglio uno a caso, A, creo i segmenti AB, AC, stabilisco che l'angolo tra (le rette passanti per) AB e AC è k e che il rapporto tra la lunghezza di AB e AC è m, nel "pattern di ricerca" non devo far altro che pigliare tutte le combinazioni di tre punti, ripetere la "costruzione" per ogni possibile coppia di segmenti e determinare se gli angoli e i rapporti coincidono. In caso affermativo, magari a meno di uno scarto percentuale, ho un match.

Computazionalmente è un incubo ma logicamente non dovrebbe fare una piega. O la fa?

[Tommo]

mmm... si computazionalmente è il male, però potrebbe essere realizzato.
Purtroppo i punti non sono 3, ma un numero n. Quindi enumerare tutte le possibili combinazioni di n punti potrebbe essere semplicemente irrealizzabile.

Sul tipo del tuo avevo pensato a uno fatto tipo "per ogni punto nell'input il cui tipo esiste in Reference, cerco un vicino sempre con un corrispettivo in reference; da questo calcolo una traslazione, di cui usando l'inversa cerco di individuare se ci sono i punti che mi aspetto, dove me li aspetto.
Questo dovrebbe funzionare, e l'Affinità sarebbe una media dell'affinità dei singoli punti misurata come distanza dal punto atteso.
Ma comunque non troverebbe tutti i risultati (le coppie iniziali per ogni punto potrebbero essere tutte quelle possibili, non una sola a caso).

Cercando Point Pattern Matching ho trovato dei risultati interessanti, sul far coincidere due impronte digitali scomposte in "punti feature" (che è praticamente quello che voglio fare io) però loro partivano dal presupposto che tutto il pattern grezzo doveva coincidere alla reference, e bisognava solo trovare l'affinità.
Invece io non so se coincide, e molto probabilmente coincide solo un piccolo sottoinsieme.

Una cosa che stavo pensando era usare una specie di decision tree tipo octree o binary tree, in cui ogni cella è capace di "dire" (tipo con un checksum) se il reference potrebbe essere contenuto dentro.
Scendendo l'albero si dovrebbe poter rifinire la soluzione fino a scartarla o accettarla.
Però c'è il problema dei pattern disposti su più di una cella, che non si possono escludere a priori e anzi potrebbero essere abbastanza probabili.

Oppure qualcosa di grafico, tipo rasterizzando una distance map dai punti su un buffer?

[marco.r]

Originariamente inviato da Tommo

mi sto arrovellando da un pò con questo problema, che fa parte di un sistema molto più grosso (che pian piano ho messo insieme), ma è un tassello fondamentale.

Allora:
un Punto è una coppia (posizione, tipo).

un Pattern è un insieme di punti.

In ingresso ho 2 pattern, il primo è una "reference" che deve essere trovata nel secondo.

"reference" può apparire più di una volta, e può essere traslato, ruotato e scalato, e i suoi punti possono trovarsi in posizioni leggermente diverse rispetto all'originale.

In output serve una lista (Pattern, affinity) di tutti i match con la loro somiglianza alla Reference, in percentuale.

Se qualcuno ha idee, o anche solo un link utile, lo stimo moltissimo
Onestamente non riesco a tirare giù nemmeno un algoritmo naive, è un problema bello tosto

Discuss.

qua dovresti trovare qualche idea interessante
http://graphics.stanford.edu/courses...alt_guibas.pdf

[WarDuck]

Problema molto interessante, potrebbe nascerne un contest pasquale ...

Forse risolvibile mediante alcune tecniche di geometria e algebra lineare.

Supponiamo di avere questi due insiemi di punti A e B, A è il reference e B è quello che vuoi confrontare.

Prima domanda che rivolgo a Tommo:
A e B hanno lo stesso numero di punti?

In questo caso il confronto viene fatto banalmente confrontando uno a uno i singoli punti di A con i corrispondenti punti di B.

Dunque diciamo che nel caso ideale se A=B allora vuol dire che tutti i punti di A sono simili (o uguali) a quelli di B.

Chiaramente il criterio di similitudine va stabilito, perché da questo deriva la percentuale di matching.

Se uno dei punti considerati è oltre la soglia, allora bisogna aggiustare il tiro, in particolare dobbiamo scegliere cosa fare, se effettuare una rotazione o una traslazione.

Ora nel primo caso se consideriamo i punti in notazione modulo e fase, si potrebbe cambiare la fase (l'angolo) e calcolare le nuove coordinate di quei punti, tuttavia bisogna stabilire anche il grado di precisione che si vuole ottenere (di quanto cambi l'angolo)?

La traslazione è più semplice da calcolare, basta applicare ad ogni punto una variazione +x su una delle coordinate.

Il problema è, come scegli cosa fare?

A tal proposito mi veniva in mente il concetto di baricentro, che forse potrebbe darti una idea di massima da quale punto partire.

Il baricentro su una serie di punti viene calcolato come:

Pb(media delle coordinate x; media delle coordinate y)

Ti potrebbe far capire grossomodo dove è centrato il tuo insieme di punti, dunque potresti a quel punto provare a partire da lì.

Se i punti hanno una certa somiglianza presumo che il baricentro bene o male dovrà coincidere.

Potresti a quel punto traslare e ruotare tutto rispetto al baricentro e vedere se riesci ad ottenere qualcosa.

Chiaramente prendi tutto ciò che ti ho detto con le pinze, è la prima volta che ragiono su un problema simile, molto interessante .

[Tommo]

Mi dispiace WarDuck, ma il numero di punti di B >> numero di punti di A

La A è un pattern "acquisito in passato", mentre B è l'input, e contiene un sacco di punti disordinati.

Ad esempio, pensa se B è composto dalle lettere di una pagina in cui vogliamo trovare la parola "nerd". Ogni lettera (il tipo) comparirà moltissime volte anche se in posizioni diverse, e la parola stessa potrebbe apparire in molte occasioni. Inoltre questo è un caso semplificato, perchè è ad una dimensione e non ci interessa la rotazione e l'ingrandimento, ma solo la traslazione di A in B.

L'algoritmo che hai proposto te comunque non è affatto stupido, infatti si usa per le impronte digitali... ma in questo caso non dobbiamo capire "a cosa assomiglia l'immagine" ma "che cosa contiene l'immagine", che è un pò diverso

Il contest non è per niente una cattiva idea, certo prima dovremmo essere sicuri che esista almeno una soluzione

PS: non è necessario trovare tutti i possibili match, solo i "più significativi". Anche se non so come questo possa aiutare.

@marco.r il capitolo 2.2.2 di quel paper sembra parli esattamente del problema in questione, ma è complicatissimo... me lo studio per bene.

[rеpne scasb]

■

[Tommo]

Originariamente inviato da rеpne scasb

*

Il punto 1) pensavo di realizzarlo con un albero tipo octree o kd-tree, come ho scritto sopra... in modo che p siano i punti contenuti nell'ultima cella in cui si esegue il matching completo punto a punto. In questo modo dovrebbe essere molto più fattibile...
comunque la complessità non è n*p, ma n*(ogni sottoinsieme di p coi tipi giusti), che è molto peggio da affrontare brutalmente, in quanto il numero di sottoinsiemi qualsiasi di un insieme è altino.

[rеpne scasb]

■

[Perry_Rhodan]

mi iscrivo alla discussione in quanto il tema mi interessa perchè è affine al problema della ricerca di pattern nelle serie storiche dei prezzi (o il tuo programma riguarda proprio questo argomento? )

in ogni caso è un problema simile a quello del ricoscimento delle forme, dei visi, o al riconoscimento vocale, quindi argomento quantomai ostico ma ampiamente studiato anche se forse è difficile reperire buone fonti (chi ha buoni risultati li tiene per se )

cerca tra i tanti libri di bernardotti, che dovrebbe essere un esperto in materia:

http://www.bernardotti.it/libri.html

forse qualche buon risultato potresti ottenerlo con le reti neurali, visto che con la "forza bruta" mi sembra ad occhio che si faccia poca strada

sorry, ma non posso esserti di aiuto, argomento troppo ostico per me, anche se mi interessa moltissimo

[Tommo]

Originariamente inviato da rеpne scasb

Mi sembri molto lontano. Prova a pensare in modo non convenzionale.

Devo pensare quadrimensionalmente
Comunque dammi pure qualche indizio, non è tanto un contest quanto un problema molto pratico che sto provando a risolvere

Mi è venuto in mente un'altro approccio - considerando che più giù nella pipeline costruisco un Nearest Neighbours Graph sui punti per estrarre i raggruppamenti mai individuati dall'algoritmo in questione, potrei usare direttamente questi raggruppamenti per fare il matching, dato che in fondo non serve trovare "tutti" i match, ma solo quelli più evidenti.

@Perry_Rhodan: non è un caso, sto ricercando tutti e nessuno di quei problemi li
Lo scopo è realizzare un "motore di ricerca di associazioni tra pattern".
Le reti neurali le avevo considerate, ma introducono una "non deterministicità" nel sistema che non mi piace affatto... potrebbero funzionare, ma convincerle a funzionare come dico io sarebbe un gran lavoro di tweaking.

[rеpne scasb]

■

[Tommo]

No, forse stavo pensando ad un'ottimizzazione più spinta di quello che intendi...

Tutti i punti che appartengono "sicuramente" a R di T presi singolarmente sono quei punti che hanno un tipo che esiste in R.
Quindi possiamo escludere tutti i punti di tipi non esistenti in R.
Ma non mi pare che sia un'ottimizzazione importante.

Se invece con "appartiene sicuramente" intendi un punto che fa effettivamente parte di un match... avere quel punto risolverebbe quasi del tutto il problema, ma come?

EDIT: per quanto tu mi stupisca ogni volta con soluzioni a qualsiasi problema, stavolta non mi sembrava possibile che anche questo problema ti sembrasse così banale... quindi ho chiamato in causa google, e sembra che 8 anni fa tu abbia fatto esattamente quello che voglio fare io... la citazione di Ritorno al futuro sembra quantomeno appropriata

PS: per fortuna che quelli della MS si saranno al massimo dati i paper in testa a mò di gibboni (se il risultato è Bing... ), così c'è ancora campo libero
Hai qualche link a questi paper, oppure tutto è finito sotto l'NDA più stretto?

PPS: secondo i miei calcoli, se una istanza del tuo programma emettesse metasimboli sul suo stesso funzionamento e li desse in pasto ad una seconda istanza che controlla la prima, potrebbero succedere cose interessanti dal punto di vista filosofico.

[rеpne scasb]

■

[banryu79]

Originariamente inviato da rеpne scasb

...
5) Quindi, noto B si testino gli m punti di T (avendo cura di sezionare T in sottospazi) in modo da avere un test veloce di congruenza dell'emmesimo punto di T come appartenente al reference pattern R (ad esempio se stiamo testando il punto m-iesimo appartenente a T e noto tale punto non esiste alcun punto distante da esso d0 allora lo si puo' scartare tranquillamente).

Se invece di memorizzare la distanza assoluta dei rimanenti n-1 punti da p memorizzassimo il rapporto tra la ditanza assoluta e una distanza di riferimento (ad esempio quella minima) potremmo riconoscere anche insiemi di punti simili al pattern anche se "scalati" oltre che ruotati, oppure è prematuro fare questo controllo adesso?

Vedo che manca la seconda parte: io procederei in modo analogo alla prima parte da te illustrata, solo che invece delle distanze (o rapporto delle distanze) controllerei le gli angoli formati tra il punto p e tutti gli altri n-1 punti... oppure sono fuori strada?

[OT]

Originariamente inviato da Tommo

...quindi ho chiamato in causa google, e sembra che 8 anni fa tu abbia fatto esattamente quello che voglio fare io... la citazione di Ritorno al futuro sembra quantomeno appropriata

zio gobbo!

[rеpne scasb]

■

[rеpne scasb]

■

[Tommo]

Uhm... in realtà il tuo algoritmo lo avevo pensato, (anzi è l'unico che m'è venuto in mente) ma c'è un motivo per cui non rispetta i requisiti:
i requisiti sono che ogni punto del match che manca apporta un deterioramento della qualità del match uguale a tutti gli altri: tutti i punti hanno lo stesso peso e diminuiscono l'affinity allo stesso modo se mancano.

Al contrario, è evidente che scegliendo arbitrariamente un punto da trovare, se tale punto manca il match manca del tutto. Quindi il suo peso è 100%.
Ad esempio, nella parola "ciao", se prendiamo "c" come primo, "ciap" verrebbe riconosciuto come simile al 75%, mentre "siao" sarebbe scartato al primo passo perchè in R manca del tutto il tipo "s" ( mentre dovrebbe essere simile al 75%). E questo non va bene.

Ovviamente se ho capito bene l'algoritmo

Ma con "punto p" intendi un punto geometrico o un punto con un tipo come i miei?
A pensarci bene, scegliendo un punto geometrico che non appartiene a R (il baricentro, il minimo, etc) la cosa potrebbe funzionare.
Devo iniziare a fare qualche prova

PS: peccato davvero che non puoi parlarne, ma capisco. Se vuoi che edito via tutto non hai che da dirmelo.

[banryu79]

Originariamente inviato da Tommo

Uhm... in realtà il tuo algoritmo lo avevo pensato, (anzi è l'unico che m'è venuto in mente) ma c'è un motivo per cui non rispetta i requisiti:
i requisiti sono che ogni punto del match che manca apporta un deterioramento della qualità del match uguale a tutti gli altri: tutti i punti hanno lo stesso peso e diminuiscono l'affinity allo stesso modo se mancano.
[cut]

Cioè il problema starebbe qui:

1) Si consideri in R un punto p che si trova sul bordo esterno dell'insieme (ad esempio avente le coordinate minime possibili)
...
3) Ora, se in T esiste R allora dovra' esistere in T anche l'equivalente punto p presente in R. Chiamiamo tale equivalente punto come q.

[banryu79]

EDIT:

Originariamente inviato da Tommo

Ma con "punto p" intendi un punto geometrico o un punto con un tipo come i miei?

Penso repne intendesse un punto geometrico, perchè in questo caso l'assunzione sottesa ai punti 1) e 3) del suo algoritmo sembra (a me) accettabile. Forse si può fare qualcosa di più elaborato (sospetto però che la complessità computazionale cominci a decollare).
Ora non ho tempo di pensarci, però è stuzzicante!