Bonjour,
La solution finale de ces question sera en java, mais comme mes interrogations sont d'un ordre d'amélioration de mon algorithme, du pseudo-code ira très bien, cependant, si vous connaissez des recette en java permettant de faciliter les choses, c'est encore mieux
 
J'expose donc d'abord le cadre.
Je dois reconstituer une image à partir d'images miniatures, pour faire un effet mozaique en fait. Vous avez surement déja vu ca ^^
 
J'ai bien avancer, en fait c'est fonctionnel, je dois reparametrer certains trucs, rien de bien grave. Par contre, pour une image de 100*80, une "imagethèque" d'image en 100*80 également, et des miniatures de 20*20, ca me prend 12min de calcul sur un Duron 1900mhz ^^". Je cherche donc a optimiser tout ca, et également a améliorer mes algo de comparaison de couleurs (afin de mieux s'approcher de la couleur de départ).
 
Bref, pour l'instant je voudrais avoir votre avis sur les méthodes de tri des images miniature selon la valeur moyenne de chaque image.
Tout d'abord, la valeur moyenne, pour la calculer j'ai pris la composante rgb de chaque pixel de l'image, j'en fait la somme et je divise par le nombre de pixel. Ca marche mais c'est pas rapide, mais je vois pas trop comment changer ca ^^.
 
Au niveau du tri lui-même par contre, comme je savais pas trop, j'ai fait un methode ... au pif, qui consiste a retourner le résultat suivant :  

 
Selon le signe, j'en deduis que l'un est plus grand que l'autre. Cette methode marche a peu pres, mais je ne sais pas si c'est le mieux (j'en doute).
 
Autre chose, quand je veux trouver une image correspondant a une couleur donnée. Je dois donc comparer la valeur moyenne de l'image a la couleur du pixel.
Pour ca, j'ai un code de ce genre :  
 

 
t est un TreeSet de mes images (donc triée par valeur moyenne croissante selon le principe donné précédemment)
ImageElement est une classe contenant le nom du fichier, sa valeur moyenne et le nombre de fois que j'ai utilisé l'image. Au début j'avais aussi la BufferedImage, mais au bout d'un moment j'avais un debordement mémoire de la JVM, donc j'ai lacher ca, et j'instancie les BufferedImage au fur et a mesure.
 
Voila, je voudrais donc optimiser tout ca, si vous avez des propositions, j'suis preneur
 
merci

tu peux chercher à Voronoi et/ou quantization sur Google.
 
exemples:
http://maxwell.me.gu.edu.au/spl/pu [...] 97_ram.pdf
 
http://www.ics.uci.edu/~eppstein/vorpic.html

Deja utiliser du java quand on recherche une vitesse optimisé avec des calculs lourds, comment dire...
 
Tu peux pas faire ca en C ?

Legreg => merci, je vais regarder ca
 
Toxic => nop, le java c'est imposé (projet de cours)

Sinon sans aller jusqu'à Voronoi, tu peux peut-etre essayer d'implanter un KD tree.
 
KD tree = arbre ou chaque branche correspond à une division de l'espace en deux (c'est un arbre binaire) mais en alternant le plan de division selon les axes.
 
En general l'implantation selon KD tree est l'une des plus efficace en ressources machine.
 
Et je ne pense pas que java soit trop un problème. De toute façon il n'y a pas d'exigences de temps réel, non ?

Non, non, pas besoin de temps réel ^^
 
J'ai quand même changer mes structures de données qui prenait beaucoup trop d'espace en mémoire (12mo au minimum ... plus d'1go dans le pire des cas (ca plantait evidement ) et qui faisait que ca prenait 12min de calcul. (c'était un tableau a 4 dimensions qui était en cause). J'suis repassé en 2 dimensions et tout roule, je met une douzaine de seconde maintenant (apres ca depend de la taille des images).
 
 
Concernant l'implementation de KDtree, ca me semble encore un poil compliqué, c'est un projet noté mais ce genre d'optimisation ne sera probablement pas pris en compte dans la note (sans compter qu'il faut que le reste de mon groupe comprenne ce qu'il se passe dans le programme, lol)
 
Mais j'vais continuer a regarder cette solution est voir si c'est tout de même implentable sans trop de probleme

Je pense qu'il y a une faute fondamentale dans ta manière de comparer 2 pixel. sauf si tu traite des images en niveau de gris. Mais dans ce cas la multiplication ne t’apporte rien.
Ce que je veux dire c'est que ta méthode va donner un poids plus fort à un pixel blanc, qu'a un pixel gris, un poids sup. à un pixel gris qu'a un pixel noir.
par contre si tu compare un pixel jaune pétant a un pixel gris foncé (presque noir), le gris l'emportera.
car le jaune à les valeur rgb suivante. 255*255*0 = 0
et le gris foncé voir noir, peux avoir les valeur suivante 1*1*1.
 
le mieux ça serrait d'abord de convertit tes pixel de RGB à Y.Cr.Cg, comme cela tes images seront triées par niveau d'intensité lumineuse.
 
Mais le vrai problème n'est certainement pas la. La première question qu'il te faut te poser, est pourquoi désire tu trier tes images ? Et sur quelles critères ?
 
Note qu’au lieu de lire toute l’image, pourquoi est-ce que tu ne pratiquerais pas un échantillonnage plus grossier ?

 
Pas forcément besoin de changer d'espace de représentation. Tout ce qu'il a besoin c'est d'une distance, pour identifier la couleur la plus proche.

tu ferais mieux de trouver des correspondances entre les histogrammes

Ha oui, la distance, j'vais essayer d'implementer ca, comme l'a dit maxmoi, mon truc n'est pas performant en couleur, et ca se voit a la fin de mon traitement.
 
Sinon, l'interet de trier mes images, c'est que pour rechercher l'image de couleur moyenne la plus proche, c'est plus rapide de parcourir une collection d'image triée, des que j'ai trouvé la plus proche je peux sortir.
 
Merci pour vos pistes, j'vais essayer la distance entre couleur cette apres midi

(si)
 
alors, ça donne quoi ?
 
sinon,
 
si tes miniatures font au maximum 20*20,
ça veut dire qu'elles comportent au maximum 400 couleurs différentes.
 
Pour chaque image,
dans un tabelau d'entiers (de 400x2 éléments adressé par couleur) compte par incréments combien de fois chaque couleur apparait en scannant l'imagette,
"trie" (ou partitionne) ce tableau par nombre d'apparitions décroissant.
Tu peux alors calculer la moyenne pondérée du miniature (sa future clé)  
en lisant seulement un pourcentage des couleurs ce tableau (ie. 75% en fonction du nombre de pixels occupés)
Tu élimines ainsi la partie basse de l'histogramme (si elle existe, elle peut être énorme et ne tend qu'à donner du gris)
Tes miniatures sont davantage différenciées, tu les tries.
 
Pour l'image a traiter, tu peux créer de la même manière
en une passe, un tableau de listes de pixels adressé par couleur,
pour chaque couleur
 tu cherches (par dychotomie) la miniature la plus proche
 tu l'affiches à tous les endroits nécessaires dans l'image destination
fin pour
 
j'espère que ça prend pas plus d'1 seconde, même en java.

tant qu'on y est,
voici quelques couleurs 24bits prises au hasard (à gauche), et leur plus proche voisin RGB dans une palette unique de 32 éléments  (également aléatoire, à droite)
 
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
█ -> █
 
avec 200 couleurs de base la différence devient vraiment subliminale...

Une méthode de calcul de distance qui marche hyper bien:
http://moktar1er.site.voila.fr/docs/distanceCouleur.ps

Ca avance pas mal, pour l'instant je reste sur la solution de la distance entre deux couleurs, ca marche pas mal et je dois essayer d'optimiser une autre partie du code qui prend un temps fou sur les grandes images (resizement etc écriture de tout les pixels d e la miniature dans l'image finale).

Hop la, juste pour dire que finalement j'ai implementer un KDTree, mais pas de moi, je l'ai trouvé deja tout fait par un monsieur : http://www.cs.wlu.edu/~levy/  
Donc merci au monsieur ^^
Ca marche mieux la :]
(plus rapide est plus efficace)
 
Par contre j'vais m'amuser pour expliquer le fonctionnement du KDTree en soutenance oral, faut que je potasse un peu les explications