[Algoritmo]Segment Clouds Matching

[Tommo]

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

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.

[banryu79]

Originariamente inviato da Tommo

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?

[Tommo]

Originariamente inviato da banryu79

- 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!

[gugoXX]

Io proverei con AI.

[Tommo]

Originariamente inviato da gugoXX

Io proverei con AI.

Ma vorrei andasse in tempo reale
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).

[shinya]

Questo può aiutare?

http://en.wikipedia.org/wiki/Shape_context

[Tommo]

Originariamente inviato da shinya

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"
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

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.

[cionci]

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.

[shinya]

Originariamente inviato da Tommo

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"
Come funzionerebbe in pratica l'algoritmo?

Ah no guarda, non ne ho la minima idea
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/1...ion-algorithms dove si accenna, tra le altre cose, a questo Shape Context. Da qui a wikipedia il passo è breve Comunque dai un'occhiata a quest'ultimo link. Nei commenti vengono proposti anche altri metodi...

[Tommo]

Originariamente inviato da cionci

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

Originariamente inviato da shinya

Ah no guarda, non ne ho la minima idea
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/1...ion-algorithms dove si accenna, tra le altre cose, a questo Shape Context. Da qui a wikipedia il passo è breve 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

[DanieleC88]

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.

[Tommo]

Originariamente inviato da DanieleC88

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.

Beh si potrebbe essere un'idea dal lato prestazioni, ma temo che renda tutto più difficile

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

[Tommo]

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 )

[wingman87]

Originariamente inviato da Tommo

Grazie per l'aiuto cmq, se volete posto il codice di riconoscimento (per quanto non interesserà a nessuno )

A me interesserebbe, più del codice, la descrizione dell'algoritmo che non ho molto capito.

[||ElChE||88]

Originariamente inviato da Tommo

Grazie per l'aiuto cmq, se volete posto il codice di riconoscimento (per quanto non interesserà a nessuno )

Io invece sarei molto interessato a vedere il codice; ovviamente se non hai problemi a postarlo.

[banryu79]

Io delle varie soluzioni discusse in questo thread non ho manco capito quale hai adottato alla fine, fai te
Sarei interessato anche io alla descrizione dell'algoritmo

[Tommo]

Allora, alla fine ho implementato un'algoritmo fatto da me
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) 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

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

[banryu79]

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?

[Tommo]

Originariamente inviato da banryu79

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

[banryu79]

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