Trovare disposizione di punti in un'insieme di punti qualsiasi! [Archivio]

Tommo

22-04-2011, 20:21

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 :D
Onestamente non riesco a tirare giù nemmeno un algoritmo naive, è un problema bello tosto :muro:

Discuss.

PGI-Bis

22-04-2011, 20:53

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

23-04-2011, 01:38

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

23-04-2011, 09:57

WarDuck

23-04-2011, 09:59

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

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 :D.

Tommo

23-04-2011, 11:38

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

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 (http://www.cs.mcgill.ca/~cs644/Godfried/2005/Fall/mbouch/)... ma in questo caso non dobbiamo capire "a cosa assomiglia l'immagine" ma "che cosa contiene l'immagine", che è un pò diverso :D

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

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

23-04-2011, 11:38

■

Tommo

23-04-2011, 11:52

*

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

23-04-2011, 12:39

■

Perry_Rhodan

23-04-2011, 23:00

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? :cool: )

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 :D

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

Tommo

24-04-2011, 18:15

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

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

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 :D
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

24-04-2011, 21:57

■

Tommo

26-04-2011, 01:12

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 (http://www.forumzone.it/showpost.php?p=97185&postcount=90), e sembra che 8 anni fa tu abbia fatto esattamente quello che voglio fare io... la citazione di Ritorno al futuro sembra quantomeno appropriata :asd:

PS: per fortuna che quelli della MS si saranno al massimo dati i paper in testa a mò di gibboni (se il risultato è Bing... :doh: ), così c'è ancora campo libero :asd:
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

26-04-2011, 09:05

■

banryu79

26-04-2011, 09:33

...
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]

...quindi ho chiamato in causa google (http://www.forumzone.it/showpost.php?p=97185&postcount=90), e sembra che 8 anni fa tu abbia fatto esattamente quello che voglio fare io... la citazione di Ritorno al futuro sembra quantomeno appropriata

:eek: zio gobbo!

rеpne scasb

26-04-2011, 09:50

■

rеpne scasb

26-04-2011, 09:57

■

Tommo

26-04-2011, 10:02

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 :D

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 :D

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

banryu79

26-04-2011, 10:14

banryu79

26-04-2011, 10:23

EDIT:

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!

banryu79

26-04-2011, 10:30

Forse si può fare qualcosa di più elaborato (sospetto però che la complessità computazionale cominci a decollare

La soluzione naive che mi viene subito in mente è quella di non considerare un singolo punto p di riferimento per il reference R, ma di considerare ogni singolo punto di R e per ognuno costruire la "tabella descrittiva" B per poi fare la ricerca in T con tutte queste tabelle.

Anche qui può esserci un modo "furbo" di fare i controlli corto-circuitati in modo che falliscano subito se non c'è match... ma non ho voglia di pensarci adesso :D

@EDIT: forse c'è un modo per evitare di dover considerare tutti i punti: basterebbero quelli più significativi del reference (sicuramente le estremità e un qualche punto mediano, tipo un baricentro, come proponeva WarDuck.)

rеpne scasb

26-04-2011, 10:36

■

banryu79

26-04-2011, 10:56

Esatto. La domanda e': ma ti serve veramente un punto di R appartenente a T? No. Distanza, rapporti tra distanze li puoi calcolare anche attraverso un punto fittizio inesistenze in entrambi gli insiemi (R e T).

Ok, supponiamo che, dato R considero la sua bounding sphere e prendo il centro come punto di riferimento per calcolare la tabella B.

Ora però si pone un nuovo problema nel momento in cui passo ad analizzare l'insieme di punti di T:

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).

i punti di T non sono più dei validi "candidati" con cui confrontare il punto di riferimento di R... dato che il punto è fittizio; al massimo posso usarli per verificare se ho o no un match con un dato punto arbitrario, ma come scelgo questi punti arbitrari in T?
Al momento mi blocco qui.

Tommo

26-04-2011, 11:21

Ok, supponiamo che, dato R considero la sua bounding sphere e prendo il centro come punto di riferimento per calcolare la tabella B.

...

ma come scelgo questi punti arbitrari in T?
Al momento mi blocco qui.

Se il punto in R è geometrico, in effetti il match potrebbe essere qualsiasi punto geometrico di T, che essendo un sottoinsieme di R3, ne contiene parecchi :D
Cmq vabè, è banale fare il test solo sui punti appartenenti a una griglia, e solo laddove la bounding sphere di R contiene almeno qualche punto di R.

Invece, considerato come funziona l'apprendimento, sto esplorando l'idea di usare l'algoritmo di repne su dei sottoinsiemi di T detti "pattern potenziali".

Funzionerebbe così:

1)estraggo i pattern potenziali da T
-per ogni R
2a)trovo il pattern con più affinità a R tra tutti i pattern potenziali (algoritmo con la tabella delle distanze)
2b)lo aggiungo come singolo punto con un tipo a T

-per ogni pattern potenziale non assegnato
3)ne faccio un reference nuovo e lo aggiungo agli R, e anche a T

E dato che i pattern riconosciuti diventano a loro volta punti di T, girando l'algoritmo finchè ci sono pattern riconosciuti, si possono riconoscere pattern fatti di pattern.
A questo punto il "mistero" si sposta sul punto 1), che per ora viene eseguito come ultimo, trovando i sottografi del NNG dei punti, ma in un caso di utilizzo vero non è abbastanza preciso.

rеpne scasb

26-04-2011, 11:23

■

banryu79

26-04-2011, 11:51

Poiche' uno o piu' punti di R potrebbero essere assenti in T, e' stato introdotto l'uso di un punto fittizio. Ora di quali proprieta' gode tale punto fittizio?
Delle stesse godute dal punto p di prima: è in un certo rapporto con gli altri punti (quelli veri) del pattern (magnitudo-direzioni).
Non so se questa è la considerazione corretta da usare come trampolino per andare avanti con il processo di induzione... e se lo è sono comunque (al momento) bloccato.
Ho lasciato fuori qualcosa di evidente?
Viceversa sto accettando implicitamente qualche assunzione che forse non dovrei fare (come prima, quando davo per scontato il fatto che il/i punto/i da scegliere come riferimento dovesse/ro esser preso/i tra quello/i già appertenete/i a R)?

rеpne scasb

26-04-2011, 12:41

■

banryu79

26-04-2011, 13:04

[cut]

Ok, grazie: mi par di capire che il primo metodo è simile a quello suggerito da Tommo (griglia), mentre usare una partizione non regolare basata sulla distribuzione topologica dei punti può essere più affidabile (l'efficacia maggiore di questo ultimo metodo mi sfugge, perchè non ho conoscenze sufficienti per comprendere... cosa dovrei andare a studiare in merito?)

In ogni caso il concetto è dividere lo spazio secondo un quanche metodo e testare i punti formati dalle intersezioni delle linee di patizionamento come punti di riferimento contro cui testare il pattern (e questo aspetto sembra ora assumere un'importanza critica per la bontà dell'algoritmo)
Io pensavo ad altro, partendo dai soli punti di T (cioè pensavo si potesse usare un qualche altro metodo basato sulla sola analisi di questi punti e il pattern).

Grazie del chiarimento :)

Tommo

26-04-2011, 13:41

Grazie del chiarimento :)

Quoto, ora è piuttosto chiaro. In questa ottica l'idea dei "pattern potenziali" di cui sopra è un'euristica per trovare il partizionamento non regolare di T.
Trovate le partizioni, le confronto una ad una con le reference, e poi traggo le conclusioni.
La griglia così ad occhio la trovo troppo poco significativa (anche se è parecchio parallelizzabile).

Quale potrebbe essere un criterio per estrarre sottoinsiemi di T che sono "potenziali pattern"? Al momento estraggo quelli molto raggruppati tra di loro, ma ci sono diversi casi in cui non va bene... per iniziare lo terrò così però. Almeno tiro fuori qualcosa che funziona, finalmente :asd:

EDIT: articolo interessante su wiki (http://en.wikipedia.org/wiki/Point_location)

banryu79

27-04-2011, 10:25

Anche qui: http://www.hwupgrade.it/forum/showthread.php?t=798584 fu intavolata una discussione interessante.
Sì, ho letto, molto interessante ma difficile da seguire (poi è impossibile in alcuni punti, perchè i tuoi messaggi sono stati cancellati, suppongo in seguito a un NDA) però ho colto l'attinenza sia con l'altro link che in parte con questa discussione.
Again, grazie, è stata una lettura interessante.

@EDIT: perdonate l'inutile (ai fini del topic) up.

Tommo

27-04-2011, 11:25

Gli up fanno sempre piacere :D
Poi almeno da quella discussione sono arrivato all'altra, ancora integra.

OT: sti NDA sono il male. Quelli di MS poi devono essere una specie di maledizione :asd:

Cmq la cosa procede, ho implementato il metodo delle distanze per riconoscere parole, dovrei mettere ancora il controllo della rotazione.
Visto che estraggo prima il "pattern potenziale", basta dividere le distanze per il raggio per farlo funzionare con qualsiasi dimensione del pattern trovato.

Ora ho il problema che i pattern potenziali sono trovati per adiacenza, quindi ad esempio, il programma fallirebbe i CAPTCHA (ma non i reCAPTCHA) a causa delle linee che uniscono le lettere. Oppure non potrebbe riconoscere le parti delle parole tedesche.
Devo trovare un modo migliore per dire cos'è un pattern potenziale.

banryu79

27-04-2011, 11:39

Ora ho il problema che i pattern potenziali sono trovati per adiacenza, quindi ad esempio, il programma fallirebbe i CAPTCHA (ma non i reCAPTCHA) a causa delle linee che uniscono le lettere.

Beh, se davvero riesci a fere questo hai già ottenuto un'ottimo risultato (secondo me), se si considera che i reCAPTCHA vengono usati proprio per sottoporre ad un pubblico umano le immagini/parole che gli OCR usati per digitalizzare testi non riescono a risolvere correttamente...

Tommo

27-04-2011, 11:59

Beh, se davvero riesci a fere questo hai già ottenuto un'ottimo risultato (secondo me), se si considera che i reCAPTCHA vengono usati proprio per sottoporre ad un pubblico umano le immagini/parole che gli OCR usati per digitalizzare testi non riescono a risolvere correttamente...

I reCAPTCHA sono interessanti perchè non fanno leva sul "problema dell'OCR"... se vedi le lettere sono ben staccate e nere su sfondo bianco, quindi il riconoscimento è semplice.
Però reCAPTCHA poi ha parole "sbagliate", con lettere masticate o altro, che non sono proprio riconoscibili, nemmeno da un'essere umano.
Il quale però riesce ad intuire cosa "voleva dire" in base all'assonanza, pescando dalla sua "conoscenza comune" di parole, in sostanza riconoscendo l'intera parola invece che la lettera.
E questo non può farlo nessun bot, ma in teoria sarebbe lo scopo di questo coso :asd:

EDIT: come al solito, qualcuno aveva già pensato a tutto (http://en.wikipedia.org/wiki/Memory-prediction_framework) :asd:
E vabbè, almeno so che era una buona idea :asd: