View Full Version : [Algoritmo]Segment Clouds Matching
Salve,
il problema è di quelli semplicissimi a dirsi, ma difficili a risolversi. in finale devo scrivere un algoritmo per capire se due disegni si assomigliano :asd:
Cioè, date 2 linee continue A e B composte da segmenti (i segmenti di A >> quelli di B), devo capire se esse sono "somiglianti" per una persona; ovvero, i punti possono anche essere in diverso numero, possono essere sovrapposti, il tratto può fare avanti e dietro, può partire da un lato o dall'altro ecc, quello che conta è che la forma sia "più o meno uguale", ovvero che ogni punto di A sia vicino ad un punto di B.
L'algoritmo che uso ora, cioè il matching delle inclinazioni, non è sufficiente perchè troppo "pignolo": infatti i disegni vanno eseguiti in un verso preciso, e un piccolo segmentino in più viene considerato spesso inaccettabile.
Pensavo, data la disparità del numero di segmenti, di prendere ogni punto di A e controllare la sua distanza dalla retta individuata da ogni segmento di B, e vedere se sta "in range".
Forse funzionerebbe, ma non so se può essere fatto in real time su set di 100 e 10 segmenti in media.
E' per un gioco e un piccolo "hang" da molto fastidio.
:D
banryu79
06-07-2009, 13:08
L'algoritmo che uso ora, cioè il matching delle inclinazioni, non è sufficiente perchè troppo "pignolo": infatti i disegni vanno eseguiti in un verso preciso, e un piccolo segmentino in più viene considerato spesso inaccettabile.
- verso preciso dei disegni: non puoi risolvere "invertendo il verso" del disegno con il numero di punti/vertici minori prima del controllo? Basterebbe infilare tutti i vertici in uno stack per poi "popparli" tutti
@EDIT:
Immagino che dei due disegni, quello con il minor numero di vertici sia quello disegnato dall'utente?
- verso preciso dei disegni: non puoi risolvere "invertendo il verso" del disegno con il numero di punti/vertici minori prima del controllo? Basterebbe infilare tutti i vertici in uno stack per poi "popparli" tutti
@EDIT:
Immagino che dei due disegni, quello con il minor numero di vertici sia quello disegnato dall'utente?
Si ho provato a fare così e per qualche forma funziona, ma non per tutte. E poi per esempio non c'è modo partire dal centro, andare da un verso poi ripassarci e arrivare all'altro capo... cosa che si fa spesso scrivendo.
Cmq il disegno con tanti vertici è quello dell'utente, perchè ovviamente è impreciso e storto; invece quello "reference" può essere fatto precisamente e non dovrebbe avere più di 5-10 segmenti, anche perchè altrimenti diventa difficile da copiare.
Cmq avevo pensato ad una cosa stile "rasterizzazione": cioè rasterizzo sia il disegno sia la reference in 2 matrici quadrate, quindi controllo che tutti i punti della prima siano "on" nella seconda.
Tuttavia rimane il problema opposto, dato che in questo modo passerebbe il test anche una matrice vuota (tutti off: nessuno on fuori dal range).
Qualche idea? Eppure l'ho visto fare anche su giochi vecchissimi come Mario Party 1 o sul DS! :mc:
Io proverei con AI.
Ma vorrei andasse in tempo reale :asd:
Sei sicuro che potrebbe riuscire a metterci meno di 1/60 di secondo?
Cmq come ho detto si fa anche su DS, wii e console poco potenti in generale, l'AI mi sembra overkill dati i vincoli che ho sul problema (linea sicuramente continua, simboli molto differenti, ecc).
Questo può aiutare?
http://en.wikipedia.org/wiki/Shape_context
Questo può aiutare?
http://en.wikipedia.org/wiki/Shape_context
Pare proprio di si, da quanto ho capito riesce a dire che le due "A" della figura sono molto simili no?
Fra l'altro io non ho bordi ma linee e dovrebbe essere veloce...
però mi son perso sul "log-polare" :D
Come funzionerebbe in pratica l'algoritmo?
Cmq ho implementato parte del codice per il riconoscimento a rasterizzazione e sembra funzionare bene: disegno + blur non riescono ad andare sopra lo 0.000 sul mio timer :D
In pratica il mio è un approccio grafico, dato che prima rasterizzo & sfoco disegno e reference;
quindi il grado di somiglianza è proporzionale alla sommatoria del delle distanze dei valori ogni pixel delle due matrici...
cioè, nel pixel:
0-0 = uguali, massima somiglianza
1-1 = uguali
1-0.5 = non sono uguali ma c'è un pixel vicino
0.5-1 = idem
Quindi dovrebbe riconoscere anche forme piuttosto diverse e con scale differenti, grazie al fatto che nei pixel è memorizzata la distanza dal pixel acceso più vicino, e l'algoritmo trova le parti circa in comune.
Ma il set di disegni è fisso ? Oppure cambia dinamicamente ?
Se è fisso una rete neurale è perfetta.
Edit: mmmmhhh, ora che ci penso...bisognerebbe vedere quello che si riesce ad ottenere alla fine del training. Il matchin lo fa di sicuro per disegni che si assomigliano, ma mi piacerebbe vedere cosa fa per disegni parziali.
Pare proprio di si, da quanto ho capito riesce a dire che le due "A" della figura sono molto simili no?
Fra l'altro io non ho bordi ma linee e dovrebbe essere veloce...
però mi son perso sul "log-polare" :D
Come funzionerebbe in pratica l'algoritmo?
Ah no guarda, non ne ho la minima idea :D
Ho solo fatto una ricerca per 'shape recognition algorithm' e tra le altre cose (ci sono molti paper sull'argomento) è venuto fuori questo http://stackoverflow.com/questions/126192/shape-recognition-algorithms dove si accenna, tra le altre cose, a questo Shape Context. Da qui a wikipedia il passo è breve :D Comunque dai un'occhiata a quest'ultimo link. Nei commenti vengono proposti anche altri metodi...
Ma il set di disegni è fisso ? Oppure cambia dinamicamente ?
Se è fisso una rete neurale è perfetta.
Edit: mmmmhhh, ora che ci penso...bisognerebbe vedere quello che si riesce ad ottenere alla fine del training. Il matchin lo fa di sicuro per disegni che si assomigliano, ma mi piacerebbe vedere cosa fa per disegni parziali.
Si il set di references è fisso, ma può essere modificato da un'esecuzione all'altra del programma... non che sia vitale, ma lo preferirei per il fattore "mod & editing".
I disegni parziali non vanno riconosciuti come completi, perchè il gameplay richiede che il giocatore disegni bene & velocemente... quindi non dovrebbero essere un problema.
Cmq come potrei fare ad integrare una NN in un programma molto più vasto? Le ho sempre viste come programmi "elusivi" e non saprei dire se funzionerebbe :stordita:
Ah no guarda, non ne ho la minima idea :D
Ho solo fatto una ricerca per 'shape recognition algorithm' e tra le altre cose (ci sono molti paper sull'argomento) è venuto fuori questo http://stackoverflow.com/questions/126192/shape-recognition-algorithms dove si accenna, tra le altre cose, a questo Shape Context. Da qui a wikipedia il passo è breve :D Comunque dai un'occhiata a quest'ultimo link. Nei commenti vengono proposti anche altri metodi...
Molto interessante ora me lo leggo son tonnellate di links :D
DanieleC88
07-07-2009, 14:17
Parlo da perfetto ignorante: se è possibile costruire "progressivamente" una soluzione parziale, ogni volta che viene aggiunto un segmento da parte dell'utente, il riconoscimento sarebbe poi istantaneo. Ovviamente il problema è il "come". E qui mi ritiro. :D
Parlo da perfetto ignorante: se è possibile costruire "progressivamente" una soluzione parziale, ogni volta che viene aggiunto un segmento da parte dell'utente, il riconoscimento sarebbe poi istantaneo. Ovviamente il problema è il "come". E qui mi ritiro. :D
Beh si potrebbe essere un'idea dal lato prestazioni, ma temo che renda tutto più difficile :D
In realtà si sposa bene con il riconoscimento "a rasterizzazione" dato che posso inserire ogni segmento nella matrice solo quando viene terminato.
Cmq ora sto continuando con questo che sembra promettente (meno di 1 millisecondo) però non so molto quanto sarà accurato...
Ho terminato il riconoscimento a rasterizzazione: impiega un tempo infinitesimo per girare ( niente allocazione/deallocazione o chiamate a funzione, solo somme e sottrazioni sui puntatori, circa 256*3*numero_references cicli)
In più sembra essere molto preciso e versatile, anche se creo la distancemap in maniera davvero spannometrica non sono riuscito a fargli sbagliare riconoscimento (ma sono in una situazione controllata)...
la differenza tra una cosa a caso e una reference è sui 200, mentre in caso di somiglianza è < 35, e quindi c'è un'ampio margine di scrematura.
Inoltre riconosce correttamente qualsivoglia percorso fatto dal cursore, anche ripassando più volte sullo stesso punto ecc...
in effetti mi pare strano che non ci abbia pensato nessuno in giro per internet.
Grazie per l'aiuto cmq, se volete posto il codice di riconoscimento (per quanto non interesserà a nessuno :asd:)
wingman87
08-07-2009, 03:14
Grazie per l'aiuto cmq, se volete posto il codice di riconoscimento (per quanto non interesserà a nessuno :asd:)
A me interesserebbe, più del codice, la descrizione dell'algoritmo che non ho molto capito.
||ElChE||88
08-07-2009, 06:35
Grazie per l'aiuto cmq, se volete posto il codice di riconoscimento (per quanto non interesserà a nessuno :asd:)
Io invece sarei molto interessato a vedere il codice; ovviamente se non hai problemi a postarlo. :)
banryu79
08-07-2009, 08:49
Io delle varie soluzioni discusse in questo thread non ho manco capito quale hai adottato alla fine, fai te :D
Sarei interessato anche io alla descrizione dell'algoritmo :)
Allora, alla fine ho implementato un'algoritmo fatto da me :D
Cioè, che è decisamente diverso dagli altri postati.
In pratica io avevo bisogno che il programma riconoscesse la "vicinanza" di tutti i punti di una forma a quelli di un'altra forma di reference... qualsiasi metodo vector based (incluso quello che usavo prima) implicava un'enormità di operazioni vettoriali e angolari...
questo invece si basa sul presupposto di accumulare dentro una matrice 16*16 (la bassa risoluzione aiuta l'elasticità) tutti i segmenti che compongono la linea vettoriale, proprio rasterizzandola: i pixel coperti vengono settati a 1.0, gli altri a 0.0.
Poi, si fa la cosa fondamentale (ispirata ad un paper di Valve (http://www.valvesoftware.com/publications/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf)) cioè si "sfoca" la matrice in maniera che i pixel vicini a quelli accesi hanno dei valori decrescenti al crescere della distanza, es 0.75 il primo, 0.50 il secondo e così via.
Sfocando sia la nuova forma sia la reference, e poi accumulando le distanze dei valori, si ha effettivamente un valore che tende a 0 per le forme identiche, ma che da il giusto peso ad ogni discostamento dalla forma originale grazie alle informazioni sulla distanza; infatti una linea dove non c'è nulla contribuirà sulle 30 unità di differenza, mentre se fosse solo un pò discostata da quella vecchia starebbe sulle 10.
Senza informazioni sulla distanza avrebbero lo stesso valore.
Inoltre ha il vantaggio necessario in un gioco che la figura si può comporre man mano che l'user scrive, senza accumulare tutto alla fine. E poi è quasi assembly :rolleyes:
Ecco qua il codice, ovviamente essendo parte di un mio gioco va usato o modficandolo o citando la source ecc ecc...
Potrebbe non funzionare subito, ma basta cambiare qualche tipo :D
Shape.h + Shape.cpp
#ifndef InkObjectShape_h__
#define InkObjectShape_h__
#include "ogre.h"
namespace Drafted
{
class InkObjectShape
{
public:
InkObjectShape() :
side(16)
{
matrix = new float[ side*side ];
memset( matrix, 0, sizeof(float)*side*side);
}
///Operator that returns the column needed
inline float* operator[] (unsigned int index)
{
return matrix + (index*side);
}
///Rasterize into the matrix the segment given by that two points
void rasterizeSegment( Ogre::Vector2 A, Ogre:: Vector2 B, Ogre::Vector2& min, Ogre::Vector2 dimensions );
///augments the distance map and blurs the image
void blurPass();
float difference( InkObjectShape& shape );
///Returns a string representation of the define
std::string toString()
{
std::string res;
for( unsigned int y = 0; y < side; ++y)
{
res += '|';
for(unsigned int x = 0; x < side; ++x )
res += (matrix[x+y*side] > 0) ? '*' : ' ';
res += "|\n";
}
return res;
}
void toFile( std::string& filename );
///loads a side*side string into the matrix
void fromString( std::string& );
void fromFile( std::string& filePath );
protected:
float* matrix;
unsigned int side;
//vectors stored to avoid continue allocations
Ogre::Vector2 dir, dim;
};
}
#endif // InkObjectShape_h__
//SHAPE SRC
#include "StdAfx.h"
#include "InkObjectShape.h"
#include <fstream>
using namespace std;
using namespace Drafted;
typedef unsigned int uint;
void InkObjectShape::rasterizeSegment( Ogre::Vector2 A, Ogre:: Vector2 B, Ogre::Vector2& min, Ogre::Vector2 dimensions )
{
A.x = (int)((A.x-min.x)/dimensions.x*side);
A.y = (int)((A.y-min.y)/dimensions.y*side);
B.x = (int)((B.x-min.x)/dimensions.x*side);
B.y = (int)((B.y-min.y)/dimensions.y*side);
//find direction
dir = B-A;
dim.x = abs(dir.x);
dim.y = abs(dir.y);
//number of pixels is the biggest side
float pixels = (dim.x > dim.y) ? dim.x : dim.y;
dir.x /= pixels;
dir.y /= pixels;
//for pixels increments
for(float j = 0; j < pixels; ++j)
{
if( A.x < side && A.y < side )
//set corresponding pixel in the matrix
matrix[ (int)(A.x + A.y*side) ] = 1.0;
A += dir;
}
}
void InkObjectShape::blurPass()
{
uint idx;
for( uint y = 0; y < side-1; ++y)
{
for(uint x = 0; x < side-1; ++x )
{
idx = x+y*side;
float accum = matrix[idx];
accum += matrix[idx+1];
accum += matrix[ x+(y+1)*side];
accum *= 0.5;
//write only if bigger
matrix[idx] = std::max(accum, matrix[idx]);
}
}
}
float InkObjectShape::difference( InkObjectShape& shape )
{
float accumDiff = 0;
//check and accumulate the absolute distance of the values in pixels!
for( uint y = 0; y < side; ++y)
{
for(uint x = 0; x < side; ++x )
accumDiff += abs( matrix[x + y*side] - shape[y][x]);
}
return accumDiff;
}
void InkObjectShape::toFile( std::string& filename )
{
//write contents
std::ofstream file( filename.c_str() );
if( file.is_open() )
file << toString();
file.close();
}
void InkObjectShape::fromString(std::string & str )
{
//reset matrix
memset( matrix, 0, sizeof(float)*side*side );
//accept only *
uint cur = 0;
for( uint i = 0; i < str.length() && cur < side*side; ++i)
{
if( str[i] == '*' )
{
matrix[cur] = 1.0;
cur++;
}
else if( str[i] == ' ')
cur++;
}
}
void InkObjectShape::fromFile( std::string& filePath )
{
//load the whole file into a string
string str = "";
char* buf;
ifstream file( filePath.c_str(), ios_base::in | ios_base::ate );
if( !file.is_open() )
return;
uint size = file.tellg();
file.seekg(0);
buf = (char*)malloc( size );
file.read(buf, size);
str.append( buf, size );
file.close();
free( buf );
fromString( str );
}
Nel codice la rasterizzazione ha qualche problema (punti fuori posto) e il blurPass è un pò impreciso (non è omogeneo in tutte le direzioni) ma comunque funziona bastanza.
Per avere un "verdetto" basta creare 2 shapes, usare almeno 2 blur passes su entrambe, quindi chiamare il metodo difference su una delle 2.
Phew che post infinito :D
banryu79
08-07-2009, 10:01
Quindi se invece di una 16*16 usassi una 32*32, per esempio, avresti la stessa funzionalità solo che il sistema di riconoscimento sarebbe "meno permissivo", o meno elastico e pretenderebbe maggiore precisione da parte dell'utente?
Quindi se invece di una 16*16 usassi una 32*32, per esempio, avresti la stessa funzionalità solo che il sistema di riconoscimento sarebbe "meno permissivo", o meno elastico e pretenderebbe maggiore precisione da parte dell'utente?
Precisamente.
Per renderlo più permissivo dovresti fare il doppio dei pass di blur, in modo di "spargere" l'informazione sulla stessa area.
E cmq col blur che c'è adesso non funzionerebbe :asd:
banryu79
08-07-2009, 10:28
Ehm, e invece giocando con "i pesi" per generare il field of depth che effetto si ottiene?
Voglio dire, se il pixel "acceso" vale 1.0, quelli vicino 0.75, quelli a distanza 2 0.50 ecc.. se si modificasse questo "passo di decremento" e lo si portasse dal -0.25 a -0.30 per esempio oppure lo si riducesse a un -0.15, come cambierebbe il comportamento del sistema?
E qual'è il valore giusto del "passo di decremento"? Ha a che fare con la dimensione della matrice quadrata scelta?
Spero di non scocciarti con tutte ste domande, ma mi hai incuriosito :D
Ehm, e invece giocando con "i pesi" per generare il field of depth che effetto si ottiene?
Voglio dire, se il pixel "acceso" vale 1.0, quelli vicino 0.75, quelli a distanza 2 0.50 ecc.. se si modificasse questo "passo di decremento" e lo si portasse dal -0.25 a -0.30 per esempio oppure lo si riducesse a un -0.15, come cambierebbe il comportamento del sistema?
E qual'è il valore giusto del "passo di decremento"? Ha a che fare con la dimensione della matrice quadrata scelta?
Spero di non scocciarti con tutte ste domande, ma mi hai incuriosito :D
Beh la distanza di "falloff" massima rapportata al lato della matrice (ora sta a 2/16 pixels) è la misura più importante dell'imprecisione del riconoscimento... più pixel hanno informazione della distanza rispetto all'area della matrice, più il riconoscimento è elastico... laddove se questa distanza fosse 0 dovresti ricalcare esattamente la forma originale.
cmq non c'è un vero e proprio passo di decremento, il decremento dipende dal fatto che i valori devono andare da 1.0 a 0.0 entro la distanza massima.
Fra l'altro l'algoritmo non richiede nessuno di questi valori, perchè sono ricavati implicitamente facendo la media dei valori dei pixel adiacenti.
Cmq nessun disturbo :asd:
Ehm, e invece giocando con "i pesi" per generare il field of depth che effetto si ottiene?
Voglio dire, se il pixel "acceso" vale 1.0, quelli vicino 0.75, quelli a distanza 2 0.50 ecc.. se si modificasse questo "passo di decremento" e lo si portasse dal -0.25 a -0.30 per esempio oppure lo si riducesse a un -0.15, come cambierebbe il comportamento del sistema?
E qual'è il valore giusto del "passo di decremento"? Ha a che fare con la dimensione della matrice quadrata scelta?
Spero di non scocciarti con tutte ste domande, ma mi hai incuriosito :D
maledizione il forum mi ha perso il post :asd:
EDIT: ora è rispuntato, vabè tanto ora ho spiegato meglio :asd:
Cmq non c'è alcun passo di decremento o peso dei punti, o meglio ci sono ma i valori sono impliciti;
dato che per ogni pixel si fa la media dei valori dei pixel vicini, il decremento e la sensibilità dipendono da quanti pass si fanno in rapporto alla dimensione della matrice.
Cioè, per esempio un pixel vuoto adiacente una linea verticale:
al primo pass vale (1+0+0+0+0)/4 = 0.25
al secondo vale (0.25 +1+0.25+0+0.25)/4 = 0.43
Quindi all'aumentare dei pass diminuisce la variazione ed aumenta l'area coperta.
E' da notare che il codice postato NON fa questo, perchè non mi veniva :asd:
Infatti devo migliorarlo.
banryu79
08-07-2009, 11:07
Credo di aver capito, grazie.
A proposito: quand'è che potremmo giocarci a Drafted? :D
Ciao Tommo, buon lavoro :)
Credo di aver capito, grazie.
A proposito: quand'è che potremmo giocarci a Drafted? :D
Ciao Tommo, buon lavoro :)
Grazie mille :D
Oramai non faccio più timelines, come progetto del tempo libero dipende troppo dalla "real life"...
Invidio troppo tutti i programmatori indie che cacciano decine di giochi l'anno ma come si fa :asd:
banryu79
08-07-2009, 11:17
Invidio troppo tutti i programmatori indie che cacciano decine di giochi l'anno ma come si fa :asd:
Ah bho, forse rinunciando a vedere qualcosa di diverso dal monitor del pc per la maggior parte del tempo di veglia...
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.