Forums Casio - Autres questions

Index du Forum > Autres questions > coordonnées multi drawstat d'une picture
Redeyes
Hors ligne
Membre
Points: 227
Défis: 1
Message
Posté le 12/07/2018 01:25

coordonnées multi drawstat d'une picture :

Je voudrais savoir si il existerait un moyen d'obtenir les coordonnées multi drawstat d'une picture s'il vous plait, merci!




Shadow15510
Hors ligne
Administrateur
Points: 2168
Défis: 15
Message
Citer : Posté le 12/07/2018 07:59 | #
tu peux essayer cet utilitaire.
Sinon ce n'est pas très dur à coder. Tu fait pxlTest si ça renvoie 1 tu met les coordonnées du pxlTest dans les listes que tu veux et c'est bon

Edit : Escusez-moi : j'ai confondu avec le Super DrawStat...
----------------------------------
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Moral
   95%
Zezombye
En ligne
Rédacteur
Points: 1521
Défis: 12
Message
Citer : Posté le 12/07/2018 09:54 | #
Pour l'obtenir efficacement (tracer la picture en le moins de lignes possibles), il faut un algo que je ne connais pas (et que je ne peux pas faire, ça nécessite des cours d'algorithmie que j'ai pas )

Tu peux toujours faire un algo simple qui considère que les lignes verticales/horizontales mais il sera moins performant, il est mieux de tracer toi même les lignes.
----------------------------------
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Lephenixnoir
Hors ligne
Administrateur
Points: 13069
Défis: 136
Message
Citer : Posté le 12/07/2018 14:18 | #
Il y a un membre qui a une patience infinie et m'envoie régulièrement des MPs pour me faire avancer sur ce point. Je vais essayer d'implémenter un bruteforce genre set cover sur les petites images et un découpage type min-cut pour les grosses. J'ai un truc à peu près satisfaisant pour la deuxième phase ; peut-être qu'un jour je finirai par avoir un algo raisonnablement optimal.

Edit : exemple de découpage : http://t0wer.ddns.net/files/superdrawstat.html
----------------------------------
Rise.
Redeyes
Hors ligne
Membre
Points: 227
Défis: 1
Message
Citer : Posté le 13/07/2018 15:29 | #
Merci beaucoup pour votre aide !

@Zezombye: Je vais essayer

@Lephenixnoir: Je suis vraiment désolé je n'ai absolument rien compris ...
----------------------------------
Be perseverant in all that you undertake, and get stronger everytime... Shining hope
Lephenixnoir
Hors ligne
Administrateur
Points: 13069
Défis: 136
Message
Citer : Posté le 29/07/2018 21:21 | #
En gros, je cherche une méthode pour calculer automatiquement un SuperDrawStat ou un MultiDrawStat satisfaisant pour des images, avec un programme.

L'idée c'est que si l'image est assez petite on peut essayer « toutes » les combinaisons de lignes jusqu'à en trouver une pas trop mauvaise. Et si l'image est grande, eh bien on peut la découper en petits morceaux et traiter tous les morceaux un par un.

Sauf que si tu as par exemple une ligne droite et que tu la coupes en deux, tu es obligé de faire deux traits alors qu'un seul aurait suffit. Autrement dit découper a diminué la qualité du résultat final. Donc il faut découper de manière intelligente, et j'ai programmé un truc qui découpe de façon pas trop stupide en faisant un peu d'algorithmique.
----------------------------------
Rise.
Drak
Hors ligne
Rédacteur
Points: 1917
Défis: 38
Message
Citer : Posté le 29/07/2018 21:23 | #
Wow. J'avoue être intéressé / intrigué.
----------------------------------
Eon the Dragon : version 1.2
Let's have a look!
Marre de ces RPGs qui t'imposent des classes, des compétences et des sorts ? Crée tes propres capacités sur Eon the Dragon ! Des monstres, des dragons et des combats aussi épiques que difficiles t'attendent !
Un RPG unique et immense t'attend ! Joue dès maintenant à Aventura, le Royaume Poudingue !
Vous aussi, soyez swag et rejoignez Planète Casio !
Lephenixnoir
Hors ligne
Administrateur
Points: 13069
Défis: 136
Message
Citer : Posté le 29/07/2018 21:26 | #
C'est l'occasion de faire de l'algorithmique alors, ouais ! Pour gagner un peu de temps je te cite ma conversation avec Dyn4moo :

Regarde par ici (c'est une page sur mon serveur personnel): http://t0wer.ddns.net/files/superdrawstat.html

En haut, tu as mon image de test. Ce que je fais pour l'instant c'est que je la découpe en petits morceaux avec pour objectif de dessiner les morceaux indépendamment. Comme a priori les morceaux sont petits, on peut bruteforcer un peu pour obtenir un Super DrawStat intéressant.

J'ai utilisé un algorithme assez simple. Je créer des paquets (chunks) jusqu'à ce que j'ai recouvert toute l'image. Pour créer un chunk, je pars d'un pixel pas encore recouvert et j'ajoute des voisins dedans jusqu'à atteindre une taille convenable.

Au moment de choisir un voisin, je choisis toujours le pixel libre qui est le « plus connecté » au chunk. Intuitivement, ça veut dire que parmi ses 8 voisins à lui il y en aura un grand nombre qui auront déjà été pris dans le chunk. Et ça rejoint les principes algorithmiques derrière l'histoire de la coupe minimale dont je parlais avant.

Je répète cette procédure jusqu'à atteindre ma taille minimale, que ici configurée à 16. Sauf si bien sûr le pixel que j'avais choisi était isolé, auquel cas il n'a pas de voisins et je ne peux rien y faire.

Une fois que j'ai atteint la taille minimale de 16, si le chunk n'est pas trop dense, je continue de rajouter des pixels jusqu'à ce que j'atteigne le maximum de (ici) 32 ou une densité maximum, ic 0.6. (La densité étant le nombre de pixels du chunk divisée par la surface du plus petit rectangle qui contient entièrement le chunk.)

En bas, tu peux voir la même image (affichée depuis mon terminal) où chaque chunk a une couleur. Tu peux considérer que chaque surface de couleur différente sera calculée et affichée indépendamment.

Il me paraît acceptable, pour un utilisateur confirmé, de jouer avec ces paramètres jusqu'à obtenir quelque chose de satisfaisant. Les bons paramètres peuvent dépendre de la taille ou la forme de l'image ; c'est difficile de savoir à l'avance si l'algorithme va bien se comporter. Par exemple ici, en bas de l'image, c'est pas impressionnant : il y a plein de chunks qui se baladent, parfois de taille 1 ou 2.

La prochaine étape sera de trouver une méthode bourrine pour calculer une liste Super DrawStat pour un chunk individuel. Une fois que ce sera fait, tout sera terminé parce qu'afficher l'image quand on sait afficher les chunks c'est une trivialité.

La difficulté principale c'est qu'il faut tenir compte de deux phénomènes :
- Lever le crayon a un coût
- On a le droit de passer deux fois sur le même pixel


Ajouté le 29/07/2018 à 21:28 :
Pendant que j'y suis, voici la partie algorithmique :

Je sais plus exactement où j'en étais la dernière fois... en gros, là j'ai mon algorithme. Essentiellement, ça consiste à appliquer plusieurs fois l'algorithme de la coupe minimale d'un graphe puis à bourriner sur les morceaux qui restent.

L'algorithme de la coupe min te dit en gros à quel endroit il faut couper ton image en deux pour la séparer en parties « en coupant le moins de traits possibles ». L'idée c'est qu'on va faire du DrawStat sur les parties individuelles, donc à chaque endroit où on va couper, on ne pourra pas mettre de ligne, ce qui dégrade un peu la solution. Donc on veut couper le moins de choses possibles.

Ensuite, une fois que les morceaux sont « assez petits » (la taille reste à déterminer par expérimentation), on bourrine, c'est-à-dire qu'on tente le maximum de solutions pour prendre la meilleure. Remiweb a déjà tenté une approche exhaustive et de mémoire c'était une catastrophe, donc faudra être malin.

Pour ça, on peut démarrer par une approximation avec le problème de Set Cover. Ce problème consiste à prendre un ensemble (tous les pixels noirs) et des parties de cet ensemble (toutes les lignes qu'on a le droit de tracer) et cherche quel est le nombre minimal de parties (de lignes) qu'il faut pour recouvrir l'ensemble (tracer l'image). L'approximation qu'on peut obtenir en temps raisonnable est assez grossière et ne tient pas compte du fait que le Super DrawStat est meilleur quand on ne « lève pas le crayon ».

Une fois qu'on a une première approximation, on peut bourriner et backtracker. L'idée c'est qu'on ajoute des traits jusqu'à ce qu'on arrive à dessiner toute l'image, et si avant d'arriver au bout on dépasse le nombre de traits donné par l'approximation de set cover, on laisser tomber parce qu'on sait qu'on peut faire mieux. Ce procédé s'appelle branch-and-bound parce qu'on prend toutes les routes possibles (branch) mais on borne le nombre de traits qu'on prend (bound).

Je ne sais pas à quel point l'approximation par Set Cover peut être pertinente ni quelle taille d'image est bourrinable en temps raisonnable ; j'ai une idée pour bourriner à l'aide d'un graphe un peu intelligent mais ça demande plus réflexion. Il existe aussi une coupe min probabiliste qui va plus vite, mais je crois pas qu'on en aura besoin.
----------------------------------
Rise.


Index du Forum > Autres questions > coordonnées multi drawstat d'une picture

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2018 | Il y a 23 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire indépendant, géré bénévolement et n'est donc pas affilié à Casio | Toute reproduction de Planète Casio, même partielle, est interdite
Les fichiers, programmes et autres publications présents sur Planète Casio restent la propriété de leurs auteurs respectifs et peuvent être soumis à des licences ou des copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd