Algorithme pour créer une mosaïque d'images ?

par **Sékiltoyai** » 15 juin 2007, 15:29

Un solveur est tout à fait capable de maximiser ou de minimiser une fonction objective et donc de faire de l'optimisation, tant que le problème connait une solution finie. Comme ici, le but est de minimiser une surface, ça ne devrait pas poser de problème.

En tout cas, en cours d'algo, on ne nous a jamais parlé de solveurs. Après ce n'était pas des cours forcément méga évolués, mais si c'était une pratique si courante que cela, AMHA, on nous en aurait touché un mot...

par **Hywan** » 15 juin 2007, 15:26

Si t'as terminé ton script
Il n'y a pas de script, c'est entièrement théorique, désolé.

C'est pas grave

Ca m'intéresse beaucoup ce problème.
J'aimerais savoir 2 ou 3 petites choses en plus.

On a donc toutes les images dans un tableau (par exemple). Et est-ce qu'on peut redimensionner ces images ? Est-ce qu'on peut les déplacer sur la « grille d'arrivée » ? Quelles sont les données qui nous sont imposées (largeur et/ou hauteur fixée(s) pour la grille d'arrivée) ?

par **iclo** » 14 juin 2007, 21:41

Je ne suis pas d'accord que ca se règle avec un solveur, un solveur n'est pas capable d'optimiser la recherche, parce qu'une telle recherche est de complexité exponentielle, ce qui veut dire qu'avec des tailles de données conséquentes, on fait exploser le nombre de calculs, d'où l'indispensabilité d'une heuristique, donc de développer soi même l'algorithme.
Mais par contre, on est d'accord sur le fait que c'est à priori le seul type d'algorithme qui pourrait donner la solution.

Un solveur est tout à fait capable de maximiser ou de minimiser une fonction objective et donc de faire de l'optimisation, tant que le problème connait une solution finie. Comme ici, le but est de minimiser une surface, ça ne devrait pas poser de problème.

par **Hubert Roksor** » 14 juin 2007, 20:37

Si t'as terminé ton script

Il n'y a pas de script, c'est entièrement théorique, désolé.

par **Klomac** » 14 juin 2007, 17:59

Les programmeurs de Tétris, ils ont pas la solution ?

Ok ok je sors... ----------------> []

par **Sékiltoyai** » 14 juin 2007, 14:28

Je ne peux que confirmer que c'est bien un problème de recherche opérationnelle.
Ce genre de problème après avoir été formulé sous forme d'une fonction objective et d'une série de contrainte se résout avec un solveur. (par exemple dans excell) qui se chargera de trouver la "meilleure" solution (celle qui prend le moins de place, ici) parmis d'autres.

Je ne suis pas d'accord que ca se règle avec un solveur, un solveur n'est pas capable d'optimiser la recherche, parce qu'une telle recherche est de complexité exponentielle, ce qui veut dire qu'avec des tailles de données conséquentes, on fait exploser le nombre de calculs, d'où l'indispensabilité d'une heuristique, donc de développer soi même l'algorithme.
Mais par contre, on est d'accord sur le fait que c'est à priori le seul type d'algorithme qui pourrait donner la solution.

par **iclo** » 14 juin 2007, 14:21

Je ne peux que confirmer que c'est bien un problème de recherche opérationnelle.
Ce genre de problème après avoir été formulé sous forme d'une fonction objective et d'une série de contrainte se résout avec un solveur. (par exemple dans excell) qui se chargera de trouver la "meilleure" solution (celle qui prend le moins de place, ici) parmis d'autres.

par **Sékiltoyai** » 14 juin 2007, 13:52

Il est aussi possible de faire un algo fait maison, par exemple une solution d'algorithme fait maison serait un algorithme d'essais successifs avec élagage par heuristique, c'est à dire tenter toutes les possibilités, mais établir une heuristique pour éliminer les possibilités qui ne peuvent pas être meilleures que la meilleure solution déjà trouvée.
On peut par exemple placer la première pièce en haut à gauche, et la suivante en haut à gauche au dessous de la première ou à droite de la première, etc... En prenant la meilleure solution celle qui minimise la taille de la solution, sachant que l'on a une certaine règle de proportionnalité entre la hauteur et la largeur...

Bref, si tu veux plus de renseignement quant à mon idée, je peux essayer d'élaborer l'algorithme.

par **Hywan** » 14 juin 2007, 13:48

Si t'as terminé ton script, ça m'intéresserait bien de le voir. Même si Kabuki l'a déjà fait, on peut le refaire pour optimiser

Hehe

Enfin voilà, j'aimerais savoir où t'en es

par **Hubert Roksor** » 14 juin 2007, 07:17

Note pour plus tard, Imagick::appendImages est une option potentielle.

par **Hubert Roksor** » 15 déc. 2006, 17:24

Vu sur Zend Developper Zone, ça existe déjà, ça s'appelle ImageMerge et fait partie du framework Kabuki, en Java. Reste plus qu'à convertir ce monstre en... PHP...

par **Hubert Roksor** » 06 déc. 2006, 17:00

Merci pour toutes ces réponses.

J'ai oublié de préciser que je ne suis pas du tout un matheux, même si j'aime beaucoup les nombres. J'avais pensé au forum de Développez, mais j'ai lu trois topics et je ne pense pas que j'arriverais à exploiter ce type de réponse.

albat, je note précieusement ton truc sur la surface et les grilles, ça a l'air d'aller dans le bon sens

Et j'irai creuser Wikipedia pour la recherche opérationnelle.

PS: mon exemple sur les smilies est plutôt pertinent en y réfléchissant, je me demande si on pourrait remplacer tous les smilies statiques par une planche de CSS sprites

par **albat** » 05 déc. 2006, 22:50

Hey ! Y a un matheux sur PHPFrance !!!

Ben oui, c'est moi... Pourquoi ?

Ton problème se classe dans la catégorie "Recherche opérationnelle".
Déjà, ça aidera

à affiner sa recherche.

Ensuite, je te propose l'algorithme suivant :

calcul de la surface totale = somme des surfaces individuelles
(10*3) + (3*4) + (7*1) + (2*3) + (3*2) = 61
identification des grilles légèrements supérieures ou égales à la surface totale :
A : 62 = 31 * 2 (ou 2 * 31)
B : 63 = 9 * 7
C : 63 = 7 * 9
D : 64 = 8 * 8
E : 65 = 5 * 13
F : 65 = 13 * 5
etc.
élimination des grilles incompatibles
les grilles A, B, C, D et E sont incompatibles
car une pièce a une hauteur de 10 et ne rentrera pas.
faire des essais avec les grilles restantes

Ça ne résoud pas le problème,
mais ça limite rapidement et efficacement le champ des possibles.

NB : Je suppose que les pièces ont un sens
et donc que leurs hauteurs et largeurs ne peuvent être inversées.

par **ouckileou** » 05 déc. 2006, 22:33

Ou dans le forum Algorithmes de Developpez.com

Dur dur de connaître le nom de tous ceux qui existent...

par **jobherzt** » 05 déc. 2006, 21:23

moi j'irais demander ca a des matheux

c'est plus dans leur corde, les questions de pavages..

http://les-mathematiques.u-strasbg.fr/p ... st.php?f=2

Algorithme pour créer une mosaïque d'images ?

Répondre

Étendre la vue Revue du sujet : Algorithme pour créer une mosaïque d'images ?