Reconocimiento de formas

[carles]

Hola gente


Hacia tiempo que no me pasaba. Vengo a traeros un pequeño algoritmo que he hecho que detecta formas simples dibujadas con el ratón(punto linea y circunferencia). La idea es usarlo con algún juego para móvil.


La verdad es que no tengo ni idea de como funcionan los sistemas de reconocimiento de formas en realidad, y como no encontraba ningún ejemplo sencillo decidí hacerlo a mi manera. Agradezco cualquier sugerencia para mejorarlo.


Un saludo

Code Select Expand





Program Reconocimiento_de_formas;


import "mod_debug";
import "mod_draw";
import "mod_key";
import "mod_map";
import "mod_math";
import "mod_mouse";
import "mod_proc";
import "mod_say";
import "mod_text";
import "mod_video";


Const
Tolerancia=15; //Grosor del borde de la figura
Precision=80; //% de puntos que se han de formar parte de la figura
Punto=1;
Linea=2;
Circulo=3;

End


Global
Pos_x[10000]; //posiciones x de la linea
Pos_y[10000]; //posiciones y de la linea
t; //variable auxiliar para contar los puntos de la linea

Grafico; //id del grafico donde dibujaremos
Resultado; //Resultado del reconocimiento de formas
id_texto; //id del texto que muestra los resultados
End


Private
Ant_x; //Valor anteior de la vposicion x del raton
Ant_y; //Valor anteior de la vposicion y del raton
i; //Variable auxiliar para los contadores
end


Begin
Set_mode(300,300,32);

//Creamos un mapa para dibujar
Grafico=new_map(300,300,32);
graph=Grafico;
x=150; y=150;

write(0,150,10,1,"Dibuje un punto, una circunferencia o una recta");
id_texto=write(0,150,20,1,"Tolerancia: "+Tolerancia+" Precision: "+Precision+"%");

//Creamos un cursor para el raton
mouse.graph=new_map(5,5,32);
map_put_pixel (0,mouse.graph,2,0,rgb(200,200,200));
map_put_pixel (0,mouse.graph,2,1,rgb(200,200,200));

map_put_pixel (0,mouse.graph,0,2,rgb(200,200,200));
map_put_pixel (0,mouse.graph,1,2,rgb(200,200,200));

map_put_pixel (0,mouse.graph,3,2,rgb(200,200,200));
map_put_pixel (0,mouse.graph,4,2,rgb(200,200,200));

map_put_pixel (0,mouse.graph,2,3,rgb(200,200,200));
map_put_pixel (0,mouse.graph,2,4,rgb(200,200,200));

loop
while(!mouse.left)
if(key(_esc)) exit(); end
frame;
end

say("reiniciando variables");
map_clear(0,Grafico,0);
delete_text(id_texto);
Resultado=0;
Ant_x=0;
Ant_y=0;
from i=0 to t;
Pos_x[i]=0;
Pos_y[i]=0;
end
t=0;

say("dibujado");
while(mouse.left)
if(mouse.x != Ant_x or mouse.y != Ant_y)
t++;
Pos_x[t]=mouse.x;
Pos_y[t]=mouse.y;
Ant_x=Pos_x[t];
Ant_y=Pos_y[t];
say(t+","+Pos_x[t]+","+Pos_y[t]);
map_put_pixel (0,Grafico,Pos_x[t],Pos_y[t],rgb(255,255,255));
end
frame;
end

Resultado=QueFiguraEs();

If(Resultado==0)
say("???");
id_texto=write(0,150,20,1,"???");
End
If(Resultado==Punto)
say("Punto");
id_texto=write(0,150,20,1,"Punto");
End
If(Resultado==Linea)
say("Linea");
id_texto=write(0,150,20,1,"Linea");
End
If(Resultado==Circulo)
say("Circunferencia");
id_texto=write(0,150,20,1,"Circunferencia");
End

say("---------------------");
end
End






//comprovacion


Function QueFiguraEs();


Private
x1; y1; //inicio (x1,y1)
x2; y2; //fin (x2,y2)
Max_x; Min_x; //x maxima y minima
Max_y; Min_y; //y maxima y minima
ancho; //anchura
alto; //altura
a; b; //centro (a,b)
si[5]; no[5]; //Contadores para determinar el resultado final
r; //radio
float m; //pendiente de la recta
i; //variable auxiliar


Begin


//Rotar el plano


//inicio (x1,y1)
x1=Pos_x[1];
y1=Pos_y[1];

//fin (x2,y2)
x2=Pos_x[t];
y2=Pos_y[t];

//x maxima y minima
//y maxima y minima
Max_x = Pos_x[1];
Min_x = Pos_x[1];
Max_y = Pos_y[1];
Min_y = Pos_y[1];

from i=2 to t;
if(Max_x < Pos_x[i])
Max_x = Pos_x[i];
end
if(Min_x > Pos_x[i])
Min_x = Pos_x[i];
end
if(Max_y < Pos_y[i])
Max_y = Pos_y[i];
end
if(Min_y > Pos_y[i])
Min_y = Pos_y[i];
end
end


//anchura
ancho=Max_x-Min_x;

//altura
alto=Max_y-Min_y;

//centro (a,b)
a=Min_x + (ancho/2);
b=Min_y + (alto/2);

//Calculamos el radio de la figura
if((alto/2) >= (ancho/2))
r=(alto/2);
else
r=(ancho/2);
end

//Comprovar si es un punto

from i=1 to t;
//(x - a)^2 + (y - b)^2 <= (Tolerancia/2)^2
if(pow(Pos_x[i] - a,2) + pow(Pos_y[i] - b,2) <= pow(Tolerancia/2,2))
si[Punto]++;
else
no[Punto]++;
end
end
say("Punto -> si:"+si[Punto]+" no:"+no[Punto]+" "+si[Punto]*100/(si[Punto]+no[Punto])+"%");

//Comprovar si es linea

//Calcular pendiente, multiplicamos por 1.0 para convertir las variabes int en float
m=(y2-y1)*1.0/(x2-x1);

from i=1 to t;
//|a*x+b*y+c|/sqrt(a^2 +b^2) <= (Tolerancia/2)
if(abs(m*(Pos_x[i]-x1)-Pos_y[i]+y1)/sqrt(pow(m,2)+1) <= (Tolerancia/2))
si[Linea]++;
else
no[Linea]++;
end
end
say("Linea -> si:"+si[Linea]+" no:"+no[Linea]+" "+si[Linea]*100/(si[Linea]+no[Linea])+"%");

//Comprovar si es circulo

from i=1 to t;
//(x - a)^2 + (y - b)^2 >= (r - Tolerancia/2)^2
//(x - a)^2 + (y - b)^2 <= (r + Tolerancia/2)^2
if(pow(Pos_x[i]-a,2)+pow(Pos_y[i]-b,2) >= pow(r-Tolerancia/2,2) and pow(Pos_x[i]-a,2) + pow(Pos_y[i]-b,2) <= pow(r+Tolerancia/2,2))
si[Circulo]++;
else
no[Circulo]++;
end
end
say("Circunferencia -> si:"+si[Circulo]+" no:"+no[Circulo]+" "+si[Circulo]*100/(si[Circulo]+no[Circulo])+"%");


//Inserte aqui mas figuras

//Evaluar que figura es

drawing_map(0,Grafico);
drawing_color(rgb(0,255,0));
if( si[Punto]*100/(si[Punto]+no[Punto]) >= Precision)
draw_circle(a,b,Tolerancia/2);
return(Punto);
end

if( si[Linea]*100/(si[Linea]+no[Linea]) >= Precision)
draw_line(x1,y1,x2,y2);
return(Linea);
end

if(si[Circulo]*100/(si[Circulo]+no[Circulo]) >= Precision)
draw_circle(a,b,r-Tolerancia/2);
draw_circle(a,b,r+Tolerancia/2);
return(Circulo);
end
return(0);
End





[panreyes]

Me pregunto qué estarás planeando... xD

[gecko]

Me hizo acordar al Black and White.

En ese juego los hechizos se conjuraban haciendo algun gesto con el mouse. No tenias botones ni GUI.

Suena super interesante, habria que probarlo.

[carles]

Me pregunto qué estarás planeando... xD

Estaba planeando meterle al código que reconozca también cuando se dibuja una curva Sin(x)=y , pero es demasiado complicado hacerlo de forma matemática ya que implicaría resolver un problema de máximos y mínimos en cada punto. Y me da miedo que provoque alguna división entre 0.

Pero tengo un plan B... xD

[Erkosone]

Este tema es interesante. Con ingenio se puede hacer algo muy funcional casi sin matemáticas, yo lo expongo así:


Primero dejar que el usuario trace con el dedo o el mouse la figura que se desea reconocer, de esta figura hay que capturar 2 conceptos, los margenes de la propia figura "para allar el centro" y la forma, aunque a simple vista parece que capturar la forma es bastante complicado existe un sistema que funciona muy bien, es el que utilizó "PRG" para vectorizar escenarios con chipmunk en bennuGD, se trata de capturar constantemente el vector que ocupa el puntero ya sea el dedo o el mouse, y compararlo con el valor del vector en el frame anterior y el ante-anterior, si hay una tendencia clara a modificar la trayectoria se guarda la posición del vector actual como un nuevo punto en una lista, si la trayectoria sigue mas o menos el mismo sentido y dirección no se hace nada.


Luego una vez capturada la forma y los margenes yo lo que haría es solapar la captura con la muestra que se tiene predefinida, y si hay una coincidencia del 80% entre los puntos.. pues hay coincidencia, si no pues no.


Como se sabe si un punto coincide o no? pues facil, si está mas cerca del punto que se supone debería y mas lejos de todos los demás, en este caso coincide.






- Bueno, ahí dejo la idea, es así un pensamiento de cabeza mas que otra cosa, pero creo que se podría empezar por algo así y luego ya se va mejorando, no se si coincide con tu algoritmo Carles, como no explicas como lo has hecho quizá esta manera es la misma que la tuya XD..


También habrá que crear las muestras prefabricadas directamente entrandolas con el dedo o mouse con el mismo algoritmo que se use para la captura de usuario, así habrá coincidencia mayor entre las formas ya que responderan al mismo tipo de algoritmo ;)


Un saludo gente.

[carles]

He conseguido implementar la funcionalidad para curvas y = sen(x). Pero el resultado no me ha gustado así que dejare el código tal y como lo publiqué.


Gracias Erkosone por el consejo, miraré como funciona ese sistema para vectorizar escenarios.

[panreyes]

QUÉ PLANEAS CARLES. DILO xD


¿Tiene que ver con dinosaurios que explotan? xD