Algo BMP->Multi Drawstat
Posté le 15/08/2018 23:40
Le sujet est apparu dans la shout, et je me suis dit qu'il y avait peut être possibilité de faire un algo potable. L'algorithme vise à obtenir la solution optimale (pas juste une solution potable).
On va prendre comme l'exemple le sprite de drak, avec uniquement la plus grosse partie :
(du coup il lui manque un oeil et une partie de sa carapace, mais shh.)
Il fait 32x32 px, et on vise un ordre de magnitude de quelques minutes.
On ne prend que le multi drawstat, car dans le super drawstat on doit aussi prendre en compte l'ordre de dessin.
L'algo fera :
0) Division du sprite en plusieurs parties qui ne se touchent pas, et calcul séparé de chacune de ces parties
1) Recensement de chaque point noir du sprite (à la louche, on va dire qu'il y en a 256, soit 1/4 des pixels)
2) Traçage de chaque ligne existante entre chaque point (soit 256*255 = ~65000 ce qui est faisable)
3) Parmi les lignes tracées, ne retenir que celles qui ne traversent que des pixels noirs
On devrait obtenir environ 1000 lignes (au pif total).
4) Parmi les lignes tracées, enlever celles qui sont totalement incluses dans une et une seule ligne, et qui ne voisinent pas d'autres lignes :
On enlève donc la ligne verte (car totalement incluse dans la ligne rouge) :
Par contre, on n'enlève pas la ligne verte ici, parce qu'elle pourrait faire partie de la solution optimale (elle est voisine à une autre ligne) :
5) Parmi les lignes qui restent, enlever celles qui sont superposées (comme on trace les lignes dans les 2 sens, ce qui est obligé car avec l'algo de brezenham ça ne donne pas les mêmes résultats, on peut avoir des lignes verticales ou horizontales superposées)
6) La partie la plus consommatrice : calculer (avec un algo magique) le nombre de lignes minimum pour couvrir tout le sprite.
On a ensuite uniquement besoin de trouver un groupement de lignes qui est égal au nombre de lignes minimum et qui couvre tout le sprite (ça doit se faire assez simplement).
Pour optimiser cette partie, on ne peut pas enlever les lignes qui se superposent. Par exemple, dans ce sprite, la solution optimale contient deux lignes qui se superposent :
La seule optimisation qui me vient à l'esprit est de ne prendre que les groupements qui couvrent tout le sprite. Par contre pour faire ça sans itérer sur chaque groupement (qui, pour 500 lignes, est de l'ordre de 2^500 = 10^150 = quand même beaucoup) aucune idée.
Du coup faudrait implémenter cet algo afin de voir les lignes qui restent à l'étape 6, voir si c'est faisable
Citer : Posté le 16/08/2018 10:13 | #
Pour information, il y a 2^n groupements de lignes possibles pour n lignes, donc si tu n'arrives pas à descendre de 1000 lignes à 30 grand maximum, tu as perdu.
Tes optimisations sont intéressantes... on voit bien le point (4) qui tient compte du levé de crayon, par exemple. Tu attises ma curiosité, maintenant j'ai bien envie de voir ce que ton algo donne.
Citer : Posté le 16/08/2018 11:08 | #
Je vais suivre tout ça avec grand intérêt, j'essaie dès que possible de lancer ce sujet alors je suis vraiment content qu'il devienne plus qu'une idée pour certains.
Je me demandais : est-ce que ce genre de problème ne serait pas intéressant à traiter par un réseau de neurones à 32*32=1024 entrées ? Le soucis c'est que le nombre de sorties (coordonnées des points) n'est pas connu à l'avance...
Pour le point 2), si je ne me trompe pas, le nombre de lignes reliant n points n'est que de n(n-1)/2. C'est la somme arithmétique des premiers entiers de 0 à n-1. Donc pour 256 points nous avons maximum 32640 segments.
La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Citer : Posté le 16/08/2018 11:32 | #
Cette formule ne compte pas les deux sens (le segment de A à B est considéré le même que de B à A) or ce n'est pas le cas dans les lignes diagonales avec l'algorithme de Brezenham, il ne faut donc pas diviser par 2.
Y'a pas de prise en compte du levé de crayon, c'est le multi drawstat (sinon il faut en plus prendre en compte l'ordre de dessin des lignes, et dans ce cas je crois bien que c'est n^n au lieu de 2^n)
Le point 4 c'est juste pour enlever les lignes dont on est 100% sûr qu'elles ne font pas partie de la solution optimale.
Corrigé
Pour les groupements, même si on en a 2^100 possibles, on peut affiner notre itération : par exemple, ignorer les groupements de moins de 10 lignes, parce que c'est impossible de tracer le sprite en moins de 10 lignes. (par contre, aucune idée de comment calculer un nombre minimum de lignes)
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 16/08/2018 11:42 | #
Intéressant cette méthode, disons que c'est la méthode intuitive. Je pense qu'il doit exister des méthodes plus mathématiques pour résoudre ce genre de problème. J'avais fait une détection de ligne avec l'algorithme de Hough, c'est efficace mais pas déterministe du coup ce sont des probabilités de ligne. Dans notre cas c'est pas possible puisqu'on cherche à être "parfait" ... :/
La partie 6 va être plutôt chaude à réaliser
Sinon j'imagine la chose comme cela :
Prendre un segment au hasard A
Chercher tout les segments B qui partagent un point en commun avec A et enregistrer tout les cas.
Boucler pour tous les segments AB
Ça va te donner un arbre de solutions et il faudra prendre là branche la moins profonde qui utilise tout les segments...
Nan en fait je suis même pas sûr que ça marche...
Surtout si le sprite est en plusieurs partie distinctes !
J'ai une idée qui me vient, peut être que l'algo de digstra pourrait aider dans ce cas.
En tout cas si t'y arrives ça sera d'une grande utilité !
Citer : Posté le 16/08/2018 11:56 | #
« Mauvaise réponse » j'ai envie de dire : il n'y a que "10 parmi 100" groupements de 10 lignes (1.71 × 10¹³) sur les 2^100 groupements (1.27 × 10³⁰) donc tu gagnes strictement rien.
Au contraire, tu as plutôt envie de tester tous les petits groupements, car ça va vite. Par exemple ton algorithme pourrait commencer par couvrir le dessin d'une façon bourrine. Si tu obtiens un résultat de 50 lignes, tu sais déjà que c'est inutile de chercher les groupements qui en ont plus, ce qui te simplifie beaucoup les choses.
Je serais plutôt tenté d'essayer tous les groupements de i lignes pour i petit, et de m'arrêter dès que je trouve un groupement valide.
Même si je ne suis pas encore convaincu que le bruteforce soit réalisable en pratique.
Citer : Posté le 16/08/2018 12:04 | #
C'est une idée, mais qui se charge de générer un dataset suffisant pour entrainer le réseau ?
Sinon en y réfléchissant, ça doit pouvoir se générer automatiquement. Pour la fonction d'évaluation, il suffit de regarder sir la solution est valide et garder le nombre de traits trouvés comme score.
Citer : Posté le 16/08/2018 12:18 | #
10^18 calculs à faire en moins c'est déjà pas mal
L'idée ce serait de définir une lower bound et de commencer à partir de ça, et comme tu le dis de ne pas chercher les groupements supérieurs si on a une solution en x lignes.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 16/08/2018 12:23 | #
Certes c'est un énorme gain ! Mais s'il t'en reste 10³⁰ ça ne t'avance pas tant que ça...
Oui, ça me semble beaucoup plus judicieux.
Tu avances vers la méthode raffinée du bruteforce : le backtracking, aka branch-and-bound. Là tu peux espérer avoir des temsp décents, peut-être. Je te laisse regarder si ça t'intéresse.
Citer : Posté le 16/08/2018 13:12 | #
Cette formule ne compte pas les deux sens (le segment de A à B est considéré le même que de B à A) or ce n'est pas le cas dans les lignes diagonales avec l'algorithme de Brezenham, il ne faut donc pas diviser par 2.
Tu veux dire que sur Casio, tracer une ligne de A vers B ou de B vers A n'affiche pas la même chose ? Maintenant que tu le dis je crois que c'est tout à fait vrai (exemple : une diagonale de cinq de large et deux de haut donne deux résultats différents suivant le sens). Dans ce cas en effet le sens importe, et il ne faut pas diviser par 2 (à préciser dans ton énoncé initial tout de même "segment orienté"). Ce n'est pas vraiment un détail qui nous aide à simplifier le problème, malheureusement...
Est-ce que ça force pour autant à implémenter l'algo de Bresenham (pas de "z") quelquepart dans l'algorithme ?
La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Citer : Posté le 16/08/2018 13:52 | #
« Mauvaise réponse » j'ai envie de dire : il n'y a que "10 parmi 100" groupements de 10 lignes (1.71 × 10¹³) sur les 2^100 groupements (1.27 × 10³⁰) donc tu gagnes strictement rien.
Au contraire, tu as plutôt envie de tester tous les petits groupements, car ça va vite. Par exemple ton algorithme pourrait commencer par couvrir le dessin d'une façon bourrine. Si tu obtiens un résultat de 50 lignes, tu sais déjà que c'est inutile de chercher les groupements qui en ont plus, ce qui te simplifie beaucoup les choses.
Je serais plutôt tenté d'essayer tous les groupements de i lignes pour i petit, et de m'arrêter dès que je trouve un groupement valide.
Même si je ne suis pas encore convaincu que le bruteforce soit réalisable en pratique.
N'est-il pas possible de commencer à partir du groupement le plus petit, pour ensuite, dans un ordre croissant, aller chercher les groupements qui contiennent plus de lignes, jusqu'à tomber sur un groupement correct ? Ainsi, on pourrait espérer trouver une solution optimale, à condition bien sûr d'avoir balayé l'ensemble des possibilités au nombre de lignes inférieur.
Citer : Posté le 16/08/2018 13:58 | #
C'est ce que je pensais faire, mais tester même des groupements de 10 lignes (parmi 100) ça doit faire dans les 10^10 ce qui fait beaucoup
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 16/08/2018 14:19 | #
10 parmi 100 ~= 1.73e13
Ajouté le 17/08/2018 à 13:07 :
Concernant le réseau de neurones, j'ai regardé du coté de TensorFlow, ça a vachement progressé depuis le temps. A priori ça ne sera pas compliqué de créer le réseau.
Je suis en train de réfléchir sur le format du réseau, mais pour l'instant je pars sur :
- input : sprite de 32x32 = 1024
- couches : deux ou trois couches denses (fully-connected) de 256 neurones
- output : un tableau de 128 = 64x2, qui correspondrait à la liste drawstat directement, remplie de 0 une fois le dessin fini.
Concernant le dataset, comme je l'avais prévu ça va être chiant de le faire, mais je verrai si y'a pas moyen de le créer automatiquement. Faut juste que je regarde comment sont gérés les traits par la Casio (c'est pas du Bresenham, malheureusement...) histoire de pas faire un truc qui soit pas reproductible on-calc.
La plus grande inconnue, ça va être la précision du réseau : par définition, il est pas capable de sortir des résultats exacts, juste des "probabilités". Peut-être qu'en l'entrainant sur un gros dataset (entre 10^6 et 10^7 images) assez longtemps, on aura des résultats corrects. C'est à voir.
Citer : Posté le 17/08/2018 13:20 | #
Heu si, j'avais justement vérifié avec BIDE, les sprites que je trace avec Bresenham sont identiques à ceux tracés sur la calto.
Tu le sors d'où le 64 ? Qui te dit que la solution optimale ne fait pas 70 lignes
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 17/08/2018 13:24 | #
Je fais la supposition qu'un sprite de plus de 64 points, c'est en pratique jamais atteint. Au pire je monte à 128, mais bon...
Mais oui, c'est arbitraire et on pourra toujours trouver un cas où c'est trop peu. Tiens, question simple mais dont la réponse est pas évidente : sur un sprite de 32*32, quel est le nombre maximal de points/lignes ? A quoi correspond-t-il ?
Citer : Posté le 17/08/2018 14:33 | # |
Fichier joint
Le sprite de Drak est plus gros que 64 points en tous cas.
Sur un sprite de 32×32, une majoration triviale du nombre de lignes à tracer est 1024 ; une ligne par point.
Le maximum semble difficile à calculer, je peux affirmer que c'est au moins 256 en utilisant le sprite de 32×32 suivant :
Citer : Posté le 17/08/2018 18:16 | #
T'es sûr que Bresenham donne des résultats différents suivant le sens du segment ?
M'enfin si c'est le cas, ça m'arrange.
Citer : Posté le 17/08/2018 18:17 | #
En voyant ton image je me suis dit que le plus simple serait peut être d'avoir l'image en fond clair, puis redessiner par dessus l'image avec des traits. Laisser l'utilisateur trouver la meilleure façon...
Ajouté le 17/08/2018 à 18:18 :
Il me semble que Bresenham est symétrique, peu importe le sens du segment
Citer : Posté le 17/08/2018 18:19 | #
C'est pas faux. Peut-être que 32*32 c'est un peu gourmand comme début. Je commencerai par 8*8, éventuellement 16*16. Faudrait déjà que les résultats soient probant sur de petits sprites avant de lancer le calcul sur des images plus grandes
Citer : Posté le 17/08/2018 18:20 | #
C'est ce que je fais, je redessine dessus en ce moment
Nope :
Ajouté le 17/08/2018 à 18:30 :
J'ai fini de tracer au dessus du sprite, j'ai fait 70 lignes. Je pense que j'aurais pu optimiser à un endroit ou 2, donc je dirais que la solution optimale est dans les 68-69 lignes. (enfin bon ça fait quand même beaucoup...)
Il faudrait, comme lephé le dit, couper en petits morceaux, mais lorsqu'on est sûr qu'on ne coupe pas une ligne en 2. Par exemple, on peut couper une partie rouge ici :
Par contre aucune idée de comment trouver les endroits de coupage.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 17/08/2018 18:40 | #
D'accord, merci pour l'exemple !
Il y a pas un prblème de continuité entre les traits dans ton exemple ?
Parce que le dernier point d'un segment doit être exactement le même que le premier du second. Là tu as trouvé les traits qui ne chevauchent pas.