PHP

Problème de complexité d'algorithme

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Problème de complexité d'algorithme

vateux

Vateux pendre

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 :

Code :

<?php
function tone($r,$r2,$g,$g2,$b,$b2,$coef)
{
if((abs($r-$r2)<=$coef)AND(abs($g-$g2)<=$coef)AND(abs($b-$b2)<=$coef))
{
return 0;
}
else
{
$total=(($r-$r2)+($g-$g2)+($b-$b2))/3;
if($total>$coef)
{
return $total-$coef;
}
else
{
return 0;
}
}
}
function hexa($input)
{
if(strlen($input)==1)
{
return "0".$input;
}
else
{
return $input;
}
}
$way="http://127.0.0.1/symbiose/tone.png";
$image = imagecreatefrompng($way);
list($larg,$haut)=getimagesize($way);
$max[0]=0;
$max[1]=0;
$max[2]=0;
$max[3]=0;
$max[4]=0;
$max[5]=0;
$coef=5;
for($k=0;$k<$larg-1;$k++)
{
for($l=0;$l<$haut-1;$l++)
{
$pixel=imagecolorat($image,$k,$l);
$r = ($pixel >> 16) & 0xFF;
$g = ($pixel >> 8) & 0xFF;
$b = $pixel & 0xFF;
$toned[$k][$l]=0;
for($i=0;$i<$larg-1;$i++)
{
for($j=0;$j<$haut-1;$j++)
{
$pixel=imagecolorat($image,$i,$j);
$r2 = ($pixel >> 16) & 0xFF;
$g2 = ($pixel >> 8) & 0xFF;
$b2 = $pixel & 0xFF;
if(tone($r,$r2,$g,$g2,$b,$b2,$coef)==0)
{
$toned[$k][$l]++;
}
}
}
}
}
for($i=0;$i<$larg-1;$i++)
{
for($j=0;$j<$haut-1;$j++)
{
if($max[0]<$toned[$i][$j])
{
$max[0]=$toned[$i][$j];
$max[1]=$i;
$max[2]=$j;
}
}
}
$pixel=imagecolorat($image,$max[1],$max[2]);
$max[3] = ($pixel >> 16) & 0xFF;
$max[4] = ($pixel >> 8) & 0xFF;
$max[5] = $pixel & 0xFF;
//Debug
$rouge=hexa(dechex($max[1]));
$vert=hexa(dechex($max[2]));
$bleu=hexa(dechex($max[3]));
echo "R:".$max[1]." G:".$max[2]." B:".$max[3]." </br>";
echo '<div style=" height:'.$haut.'px; width:'.$larg.'px; background-color:#'.$rouge.$vert.$bleu.'"></div>';
?>

Message cité 1 fois

Publicité

honrisse

vateux a écrit :

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).

Message édité par honrisse le 17-09-2016 à 01:26:42

rufo

Pas me confondre avec Lycos!

+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

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta

MaybeEijOrNot

but someone at least

/!\ Attention : idée du dimanche soir !

[EDIT] Encore pire qu'un dimanche soir, un lundi soir de week-end prolongé. :pt1cable: [/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 :

Spoiler :

1- ne pas analyser chaque pixel, par exemple avec un pas de i et j de 4 soit un pixel sur 16, cela n'a pas que du mauvais, en effet ça permet de minimiser un artefact sur une image. Disons que si tu compares les pixels avec une très faible variation de couleur alors une tâche monochromatique localisée pourrait te biaiser la couleur dominante.

2- ne pas comparer les pixels entre eux mais diviser pour chaque pixel ton espace RGB par ton coeff, arrondir le résultat, et stocker le nombre d’occurrence pour chaque nouvelle valeur de ton espace RBG réduit.

exemple : px_n°1 = RGB(50;50;50) et px_n°2 = RGB(60;60;60)

au lieu de regarder si px_n°2 est entre RGB(45;45;45) et RGB(55;55;55) tu fais :

px_n°1 = RGB(50;50;50)/5 = RGB(10;10;10)
RGB_reduit[10;10;10] += 1
px_n°2 = RGB(60;60;60)/5 = RGB(12;12;12)
RGB_reduit[12;12;12] += 1

Et en fin de parcours de tes pixels, tu cherches juste le nombre maximal d'occurrences atteint dans ton espace RGB réduit et la clé te donne la couleur dominante (à remultiplier par le coeff). Alors évidemment tu obtiens à la fin un tableau assez énorme qui dépend de ton coeff, pour un coeff de 5 tu peux atteindre un tableau de taille maximale 51*51*51, donc à voir si php arrive à gérer ça.

Après si ça ne vous paraît pas totalement débile, on peut toujours rajouter de l'info dans le nombre d'occurrence afin de remonter à une couleur qui diffère de celles de l'espace réduit multiplié par le coeff. Au lieu de ne stocker que le nombre d'occurrences on peut stocker aussi un offset de correction :
RGB(61;61;61)/5 = RGB(12,2;12,2;12,2) = RGB(12;12;12)
RGB(62;62;62)/5 = RGB(12,4;12,4;12,4) = RGB(12;12;12)

On obtient 2 occurrences pour RGB(12;12;12) donc la couleur dominante est le RGB(12*5;12*5;12*5) soit RGB(60;60;60) ce qui n'est pas très juste.
Mais si on stocke en plus du nombre d'occurrences la somme des décimales soit : 0,2 + 0,4 = 0,6

On sait que la moyenne des décimales donne : 0,6 / nbre occurrences soit 0,6 / 2 = 0,3
Donc la couleur dominante n'est plus RGB(12*5;12*5;12*5) mais RGB(12,3*5;12,3*5;12,3*5) soit RGB(61,5;61,5;61,5).
Bon ok au final ça donne RGB(62;62;62) mais c'était juste un exemple pour illustrer la démarche.

Message édité par MaybeEijOrNot le 19-09-2016 à 21:18:50

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

rufo

Pas me confondre avec Lycos!

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.

Message cité 1 fois

MaybeEijOrNot

but someone at least

rufo a écrit :

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.

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 :

Citation :

au lieu de regarder si px_n°2 est entre RGB(45;45;45) et RGB(55;55;55)

Normalement ça aurait dû être :

Citation :

au lieu de regarder si px_n°2 est entre RGB(47.5;47.5;47.5) et RGB(52.5;52.5;52.5)

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. [:julm3]

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.

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.

rufo

Pas me confondre avec Lycos!

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

FORUM HardWare.fr

Programmation

PHP

Problème de complexité d'algorithme

Sujets relatifs
Probleme de quote	Probleme pour finir VBA sur mon fichier
[Novice] De la ldc à Tkinter Problème de fonction	[Script Windows] Problème Shutdown Windows 10
problème socket et envoi paquet UPD	probleme de structure lors de l'affichage de la page
Problème d'heure en php (décalage)	Problème de transfert Filezilla
Problème classe vb.net	[VBA] Problème avec tableau
Plus de sujets relatifs à : Problème de complexité d'algorithme

Page générée en 0.062 secondes