Bonjour,
Je travail depuis peu sur un projet personnel concernant du traitement d'images. Dans le cas suivant, je recherche à connaitre le ton (couleur) le plus présent sur une image.
Pour cela j'ai une double boucle qui va vérifier sur chaque pixel si il en a d'autres qui se rapprochent de sa couleur (dépend de la variable $coef).
Je ne vois pas comment faire pour avoir une complexité d'algorithme inférieure à "x^4+x".
Le problème est que pour une image en 1080p, le traitement met plusieurs heures, ce qui est énorme et impensable, quelqu'un pourrait me conseiller pour une optimisation ?
 
voici le code :

 
Je ne connais pas le php mais de ce que je comprends en survolant le code utilisé, je ferais plutôt :

• un calcul d'histogramme 3D, par exemple en niveau de gris on a tableau de 256 cases et pour chaque valeur de niveau de gris le nombre d'occurrence dans l'image.
• difficile de reproduire les conditions de la fonction tone, à la place j'utiliserais un certain nombre de bins (avec un vote pondéré si l'on veut aller plus loin).

Note :

• normalement en traitement d'images, les images sont stockées dans un tableau en une dimension et l'itération se fait d'abord en hauteur/ligne et ensuite en largeur/colonne, à vérifier comment ça se passe en php.
• au lieu d'utiliser l'espace colorimétrique RGB, je convertirai en HSV et je calculerai l'histogramme sur la composante H (à tester/comparer) (par exemple : Extracting the Dominant Color from an Image in Processing ou Color Thief).

+1 pour l'histogramme 3D en 256 niveaux de gris.
 
Après, on peut simplifier en réduisant le nb de cases en fonction du niveau de précision souhaité (faire des tranches de 2 en 2, 5 en 5 ...).
Après tout, 255/0/0, c'est pas très éloigné de 254/0/2, donc on peut compter que c'est la même couleur.
 
Pour plus de perfs par contre, je déconseille PHP mais un binaire codé en C, pourquoi pas appelé par PHP via system() (ou similaire). Autre méthode d'appel du binaire : http://korben.info/websocketd-comm [...] mande.html

/!\ Attention : idée du dimanche soir !
 
[EDIT] Encore pire qu'un dimanche soir, un lundi soir de week-end prolongé.  [/EDIT]
 
Avec le niveau de gris tout comme le HSV tu risques de confondre 2 teintes RGB différentes. Par exemple les teintes de gris en HSV : RGB(X;X;X) et RGB(Y;Y;Y) donnent tous un H de 0. Quant au niveau de gris il faut fixer arbitrairement une couleur à un certain niveau puis convertir sur niveau de gris sur les 2 autres couleurs si je ne me trompe pas.
 
Donc, sans rien y connaitre, je soumets une idée me venant à l'esprit :
 

MaybeEijOrNot : c'est bien pour ça qu'on parlait d'un histogramme 3D ainsi on conserve le lien entre les 3 niveaux de gris obtenus sur R, G, B et la couleur dans l'espace RGB.
 
Après, ton idée de réduire l'espace colorimétrique rejoint mon idée de fonctionner par pas sur les composantes RGB. Tu proposes un pas de 10, moi, je proposais 2 ou 5.
 
Ton idée de ne pas parcourir toute l'image est une bonne idée. A la limite, on pourrait même partir sur l'idée de la compression JPEG qui découpe en petits carrés de 8x8 pixels et définir la teinte moyenne du bloc.

 
Ah ok je n'avais pas compris ça, après le pas de 10 c'était juste pour l'exemple (d'ailleurs c'est un pas de 10 au tout début que j'ai transformé en un pas de 5).
Cette phrase était fausse :

Normalement ça aurait dû être :

 
L'histogramme 3D je n'avais pas bien saisi ce que c'était, je viens d'aller voir sur wiki et en fait c'est exactement ce que je propose sans l'idée de représenter graphiquement. Faut m'excuser, je réinvente souvent la roue mais c'est parce que je n'ai jamais fait d'études d'informatique.  
Mais enfin, je suis content de voir que souvent j'arrive à retomber sur une roue bien ronde.
 
 
L'essentiel est je pense afin de diminuer la complexité :
Ne pas comparer les pixels entre eux ou fonctionner sur une seule variable (mais dans ce cas là problème d’antécédents) afin de pouvoir trier les données et faciliter les comparaisons. Mais bon avec un tri des données on reste sur une complexité élevée. La solution de ne pas comparer permet de retourner sur une complexité quasi linéaire, en effet il ne reste que la question du nombre de couleurs différentes que possède l'image. Plus l'image possèdera de couleurs, plus l'espace réduit sera complet et plus le temps pour le parcourir afin de trouver le max augmentera.
 
Après réduire le nombre de données, ça reste une incidence linéaire mais non négligeable quand tu tables sur du 16 ou 64 fois plus rapide.

Comme je le disais, passer sur un binaire codé en C réduirait grandement le temps de traitement.
 
Autre solution si un binaire ne peut être envisagé et donc rester sur du PHP : passer par une BD et faire les traitement en SQL. Ca sera beaucoup plus rapide que du full PHP