Ce programme est sous licence Creative Commons 2.0 BY
Description en français :
Bonjour à tous,
Comme promis dans la dernière rdp je publie ici la première version de mon algorithme de reconnaissance de sprite.
Comme on peut le deviner ce programme reconnait des sprites.
Au démarrage du programme, on se retrouve dans une interface utilisateur en locate, dans laquelle on peux dessiner le sprite de notre choix (actuellement de taille maximum 7*7 pixels). Puis on presse [EXE], la calto potasse quelques dixièmes de seconde et elle vous dit si le sprite donné est connu. Si oui, alors vous avez une réponse positive, sinon le programme l\'enregistre et sera capable de le reconnaître plus tards. Mieux, si ce sprite est référencé dans la petite base de données intégrée au programme, l'algo vous dit de quelle forme il s'agit. Actuellement les formes implémentées sont:
-carré de 2*2 px;
-carré vide de 3*3 px;
-cercle vide de 4px de diamètre;
-cercle vide de 5px de diamètre;
-pixel (point);
-croix de 3px de largeur.
Pour ceux qui ne veulent pas télécharger le programme, voici son code source:
Do
LpWhile Getkey<>0
0->A~Z
ClrText
'LIST MEM
"MEM"->List 1
If List 1[1]=0
Then 100->Dim List 1
"MEM"->List 1
1->List 1[1]
15->List 1[2]
495->List 1[3]
63903->List 1[4]
186->List 1[5]
4357252->List 1[6]
27030->List 1[7]
15255086->List 1[8]
IfEnd
'PICT BASE
[[0,0,0,0,0,0,0][0,0,0,0,0,0,0][0,0,0,0,0,0,0][0,0,0,0,0,0,0][0,0,0,0,0,0,0][0,0,0,0,0,0,0][0,0,0,0,0,0,0]]->Mat A
'PICT EDITOR
'_->_PICT LOAD
For 1->Theta To 7
For 1-><r> To 7
Mat A[Theta,<r>]=1=>Locate <r>,Theta,"_#E6A6_"
Next
Next
'_->_BACKGROUND
For 1-><r> To 7
Locate 8,<r>,"|"
Next
Red Locate 9,1,"Sprite Recon"
Blue Locate 9,3,"By Disperseur"
Black Locate 9,4,"Use [_#E690__#E692__#E693__#E691_]"
Black Locate 9,5,"and [SHIFT]"
Black Locate 9,6,"and [ALPHA]"
Black Locate 9,7,"then [EXE]"
'_->_POS INIT
1-><r>:1->Theta
Locate 1,1,"+"
'_->_MAIN LEAP
While 1
Do
LpWhile Getkey=0
If Mat A[Theta,<r>]=1
Then Locate <r>,Theta,"_#E6A6_"
Else Locate <r>,Theta," "
IfEnd
Locate <r>,Theta,"+"
Getkey=31=>Break
Do
LpWhile Getkey<>0
WhileEnd
ClrText
"Analyse.."
'FIRST POINT SEARCHING
For 1->Theta To 7
For 1-><r> To 7
If Mat A[Theta,<r>]=1
Then
<r>->A~B
Theta->C~D
Break
IfEnd
Next
Next
'SIZE DETERMINING
For 1->Theta To 7
For 1-><r> To 7
If Mat A[Theta,<r>]=1
Then
<r><A=><r>->A
<r>>B=><r>->B
Theta<C=>Theta->C
Theta>D=>Theta->D
IfEnd
Next
Next
'READING MAT DIM
{D-C+1,B-A+1}->Dim Mat B
'WEIGHT MAT DIM
{D-C+1,B-A+1}->Dim Mat C
For C->Theta To D
For A-><r> To B
Mat A[Theta,<r>]=1=>1->Mat B[Theta-C+1,<r>-A+1]
Next
Next
'WEIGHT MAT FILL
For 1->Theta To D-C+1
For 1-><r> To B-A+1
2^W->Mat C[Theta,<r>]
Isz W
Next
Next
'SOM CALC
0->S
For 1->Theta To D-C+1
For 1-><r> To B-A+1
S+(Mat B[Theta,<r>]*Mat C[Theta,<r>])->S
Next
Next
'SEARCH
"S="
SDisps
'IMAGES REFERENCEES
For 1-><r> To 100
If List 1[<r>]=S
Then "Connu"
Break
IfEnd
If List 1[<r>]=0
Then "Inconnu, enregistré"
S->List 1[<r>]
Break
IfEnd
Next
Le petit bémol est que l'algo ne peux pas reconnaître plusieurs sprites regroupés. Pour parer à ce problème je cherche un moyen de détecter les différents sprites qui pourraient êtres présents dans l'image donnée au début.
Sur ce, si vous avez des questions (et je pense qu'il y en aura ) n'hésitez pas.
La notation O(N) ne sert pas juste à indiquer la variable mais bien la fonction. Par exemple, si la complexité est 4×N×2^N + 3×N² (pour donner un exemple plus compliqué), on la notera O(N×2^N).
(La raison pour laquelle on enlève le ×4 est qu'on se moque des constantes comme celle-ci, et la raison pour laquelle on enlève le 3×N² c'est que cette quantité est négligeable devant N×2^N pour des grandes valeurs de N.)
Si tu as 4 paramètres, eh bien... pour des raisons assez compliquées, on peut pas utiliser de O (prononcer "grand O") sur plusieurs variables en même temps.
Mais tu peux calculer ta complexité et dire que c'est, par exemple, 4×A×B + C×D - 3. Pas de problème de ce côté-là.
Comme je l'ai mentionné la notation O n'est pas bien définie quand il y a plusieurs variables, le mieux que tu puisses dire est donc informel, par exemple "de l'ordre de 3(D-C)(B-A)".
A, B, C et D sont respectivement les variables contenant les valeurs Xmin, Xmax, Ymin et Ymax. Ce sont les dimensions de la plus petite boîte dans laquelle rentre le sprite à reconnaître. Ces valeurs sont calculées par l'algorithme.
Du coup je dit que la complexité de mon algorithme ressemble à 3(B-A)(D-C). (B-A)(D-C) pour le nombre total de pixels et *3 car à trois reprises je parcours la matrice.
D'accord, c'est donc en fonction de la taille du sprite ! Tu peux directement dire que tu as "n" le nombre de pixels de ton sprite, auquel cas ta complexité est 3*n et tu peux noter ça O(n).
Tu veux peut-être aussi prendre en compte la taille de ta base de données, non ?
Oui... mais le truc c'est qu'elle fait 999 cases et que l'algo ne les lit pas toutes a chaque recherche. Une fois qu'il à trouvé une correspondance, la recherche se stoppe.
Ce n'est pas ça qui arrêtera la complexité algorithmique !
On fait un calcul dans le pire des cas, et dans ce cas on parcourt tout la base (disons m cases, même si pour l'instant c'est fixé à 999 ce n'est pas une contrainte de l'algorithme).
Ton algorithme est donc en complexité de l'ordre de n+m où n est la taille du sprite et m la taille de la base. Bien joué, c'est pas grand !
Je note que si tu triais la liste, tu pourrais faire une recherche dichotomique et avoir une complexité n+log(m) qui serait encore plus agréable. Surtout si tu utilises toujours 999 cases.
Ben non en effet ce n'est pas grand. Pour la liste, j'ai prévu la taille maximum en partant du principe que quelqu'un irait peut-être à montrer à l'algo 999 exemples différents. En pratique toutes les cases ne sont pas utilisées. En fait je pense qu'en moyenne avec cet algo on utiliserait 1% de la liste (environ une dizaine de cases).
Ma devise en algorithmique:
"Efficacité, propreté, lisibilité"
Ce que je ne comprends pas, c'est pourquoi tu forces la liste à 999 cases ? Ça prend une place monstre alors que tu pourrais mettre juste assez d'éléments pour la taille de ta base.
Soit dit en passant, ton algo ne renvoie pas toujours le bon résultat non plus à cause de l'encodage. Tu peux améliorer ça encore !
Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd
) n'hésitez pas.
