Algorithmique : classification automatique non paramétrique

[Philou67]

Bonjour à tous,

Je me propose d'appliquer les notions de classification automatique à la gestion d'une palette de couleur d'image (palette RVB à trois coordonnées donc). L'objectif final étant de passer d'une image RVB à une image utilisant un sous-ensemble de taille déterminé (par l'utilisateur) dans une palette de plus de 500 couleurs pré-déterminées (dont je connais déjà les valeurs RVB).

L'idée est de définir une distance entre les couleurs (et éventuellement une compacité d'une classe de couleur) et d'utiliser une méthode de classification automatique adaptée basée sur cette distance. Une fois rangés dans mes n classes de couleurs, il me suffit de chercher dans la palette de couleur celle correspond le mieux à la classe.

J'ai pour l'instant identifié deux méthodes de classification :
- la méthode de classification hiérarchique, pour laquelle j'ai peur que la quantité de donnée ne pose des problèmes de complexité (et donc, de temps de calcul), mais qui prend en compte la compacité des classe (ce qui une propriété qui m'intéresse particulièrement)
- la méthode des centres mobiles

J'ai actuellement défini la distance de deux couleurs comme étant la somme des carrés des différences de chaque composante RVB.
J'ai actuellement défini la compacité d'une classe comme étant la somme des variances de chaque composante pour toutes les couleurs de la classe.

Mes questions :
- les choix de ma dimension et de ma compacité sont-il corrects ?
- existe-t-il d'autres méthodes de classification adaptées à mon cas (notamment qui utilise directement la palette) ?
- quelle méthode privilégieriez-vous ?
- pensez-vous qu'il soit possible d'adapter les méthodes citées pour prendre en compte dès la classification de la palette de couleur ? Exemple : la palette contient un trou dans certaines teintes qui sont pourtant utilisées dans une image. Plutôt que de construire une classe de couleur dans le trou, il est plus pertinent de construire deux classes évitant ce trou (je ne sais pas si c'est clair). En quelque sorte, ce serait introduire une part de paramétrique dans ces méthodes non paramétriques.

Tout autre avis sur la question est bien entendu le bienvenu.
J'indique néanmoins que j'ai déjà tenté d'utiliser Gimp avec une palette personnalisée et l'appliquer à l'image. Cela dit, les palettes sont limitées à 256 couleurs, et par ailleurs, je ne peux alors pas réduire cette palette à un sous-ensemble de taille réduite de cette palette. Par ailleurs, je trouve un intérêt particulier à étudier ces méthodes de classification en dehors de l'application présente.

Merci et bonne journée.
-----

[Philou67]

Ce sujet n'inspire-t-il personne ?
Aurait-il plus sa place en mathématique ?

[invite765732342432]

Ce sujet n'inspire-t-il personne ?

Inspirer, si sans doute... mais c'est un sujet complexe
Tout ce que je suis capable de dire, c'est que normalement on n'est pas sensé travailler avec la somme des carrés comme "distance". Elle ne traduit pas correctement la vue qu'on en a.

Mais je ne saurais pas indiquer de solution de remplacement (travailler en premier sur les niveaux de gris pourrait cependant être intéressant... mais ça dépend un peu du but que tu poursuis)

Désolé de ne pas être plus utile.

[Philou67]

Quels artéfacts engendrent l'usage de la somme des carrés comme choix pour la distance ?

L'objectif est de faire une réduction (drastique) de couleur de manière optimale en utilisant un extrait d'une palette pré-déterminée. J'ai donné comme condition une quantité de couleur à utiliser. On peut bien sûre préciser que c'est un nombre de couleur maximum.

Par contre, passer en niveau de gris (hormis pour valider l'algorithme) ne me semble pas approprié car je perd une notion essentielle à ce que je cherche à faire, la teinte (l'application de cet algorithme est celui du domaine textile et des teintures de fils).

Cela dit, une piste pourrait être de convertir les couleurs RVB en couleurs TSV (Teintes Saturation Valeur). Cela dit, la notion de distance dans ce référentiel est-elle plus facile à trouver que dans le référentiel RVB ?

Un élément de réponse : , une distance entre couleurs

[A voir en vidéo sur Futura]

[Philou67]

Bon, j'ai finalement implémenté la méthode de classification des centres mobiles qui était bien adaptée à ma problématique de réduction d'une palette de couleur.

J'ai utilisé la distance euclidienne sur les coordonnées de couleur dans le modèle L*a*b* dont le calcul des distances semble adapté aux différences perçues par l'œil humain.

Le critère d'arrêt, basé sur ce que j'ai peut-être nommé à tord "entropie" (la somme de toutes les distances de chaque couleur par rapport au centre de son groupe) est que cette entropie soit minimale (n'évolue plus); indiquant une stabilité des groupes constitués.
Pour 500 couleurs (prises au hasard parmi 256*256*256) à classer en 10 groupes, le nombre d'itération est autour de 20.

Exemple en image :

[invite79d10163]

Bonjour,

C'est un projet intéressant que j'avais aussi traité par le passé. L'espace Lab est effectivement bien adapté au calcul des distances.

En ce qui concerne la classification, cette méthode est rapidement limitée si les couleurs ne sont pas distribuées équitablement. En d'autres termes, la méthode des centres mobiles ne prend en compte que la moyenne d'un cluster et non les variances des clusters qui peuvent être différentes. (Son extension est néanmoins facile, c'est l'algorithme EM pour classifier des populations représentées par des mélanges de distribution gaussiennes.)

[Philou67]

Merci pour cette information. Effectivement, le choix de couleurs aléatoires pour tester mon programme n'était sans doute pas judicieux, d'autant qu'il est fort probable que les images sur lesquelles je souhaite appliquer l'algorithme sera constitué de palettes de couleurs non équiprobables.

As-tu une source plus accessible que wiki pour l'algo EM ?

[invite79d10163]

Bonjour,

Je n'ai pas vraiment d'autres sources. Je comprend que les notations utilisées sur wiki ne sont pas les plus intuitives. Alors je peux vous l'expliquer avec les mains car l'algo est assez simple.

1) Vous initilisez les centres mobiles d'une façon ou d'une autre (en fait c'est cette étape qui est vraiment déterninante)...

2) Pour chaque centre, vous calculez l'ensembles des couleurs les plus proches de ce centre par rapport aux autres. Vous mettez à jour la moyenne de ce cluster ainsi que sa variance.

3) pour les itérations suivantes, l'ensembles des points les plus proches sont calculés par rapport à la loi gaussienne. C'est à dire qu'une couleur x va être attribué à un cluster, modélisé par une moyenne m et une variance sigma, si la probabilité P(x) = exp(-(m-x)^2/(2*sigma^2)) est la plus grande parmi tout les autres clusters.

Je ne sais pas si c'est assez clair...

[Philou67]

Ca me semble clair, je vais essayer d'implémenter les deux variantes dans des classes dérivées de sorte que je puisse comparer les deux méthodes facilement. Merci encore.

D'après vous, dois-je adapter mon critère de fin ? (à priori, je dirais qu'une moyenne n'évoluant plus, comme c'est le cas aujourd'hui avec ma méthode des centres mobiles, peut être conservée, donc sans utiliser la variance).

Pour déterminer la couleur de synthèse d'un cluster, pourrais-je, au final, faire une simple moyenne, ou faut-il que je tienne compte de la variance ? (à priori, je dirais qu'une simple moyenne est suffisante, mais je n'en ai pas la certitude, notamment pour un cluster qui contiendrait une forte dominante de teinte avec quelques couleurs très distinctes).

[invite79d10163]

Le critère d'arrêt est bon, même si on peut éventuellement le combiner aussi avec une variance qui n'évolue plus.

La représentation des clusters par leur moyenne est aussi souvent utilisé. Par contre le problème que j'ai souvent observé est que les moyennes sont souvent des couleurs assez fades, genre pastels, et qui en fait ne sont pas présent dans l'image originale. Je n'ai pas de solutions pour ce problème.

[Philou67]

Par contre le problème que j'ai souvent observé est que les moyennes sont souvent des couleurs assez fades, genre pastels, et qui en fait ne sont pas présent dans l'image originale. Je n'ai pas de solutions pour ce problème.

Une des solutions pourrait être de prendre la couleur médiane du cluster, plutôt que la couleur moyenne.
Au moins, on serait sur que la couleur existe dans la palette originale. Mais comment trouver une médiane à trois dimension ?
En tout cas, merci de l'intérêt que tu prêtes à ma problématique.

Je dois encore appliquer l'algorithme de réduction de couleur à une image réelle (lecture de l'image, réduction de la palette, réaffectation des couleurs), pour avoir des résultats sur des cas réels et comparer les deux méthodes.
Pour info, ImageMagick, dans son option de modification d'image "-colors" applique un algorithme basé sur la distance euclidienne dans le modèle RGB. On dirait pas ailleurs qu'il utilise une méthode de classification hiérarchique, c'est bien cela ?

[Philou67]

Une petite question tout de même : quand vous parlez de moyenne et variance d'un cluster, vous parlez de moyennes et variances de triplets. Faut-il donc tenter de maximiser P_L*(x) + P_a*(x) + P_b*(x) ? (c'est à dire, calculer les moyennes et variances des composantes individuellement)

[Philou67]

Outre me dernière question, je rencontre quelque difficultés dans l'implémentation de la méthode EM (qui peuvent être des bugs, bien sur) :
- il m'arrive que certains cluster deviennent vide lors de la constitution des clusters suite au calcul de nouvelles moyennes/variances (basées sur les coordonnées prises individuellement). Je suis donc obligé de les supprimer car la moyenne n'a plus de sens
- il m'arrive que certains cluster ne contiennent plus qu'un élément, ce qui pose également problème, car la variance est nulle. La formulation basée sur le calcul de probabilité n'est donc pas utilisable pour le groupement. Il faudrait alors que je fige ce cluster

Bref, je pense que je m'y prend mal, d'autant que si j'observe les étapes intermédiaires de cette méthode, je m'aperçois que certains groupes deviennent de plus en plus petits et restrictif, alors qu'un autre devient de plus en plus gros, jusqu'à devenir l'unique dernier.
Ne faudrait-il pas que je calcule les moyennes et variances des distances (par rapport à l'origine des couleurs par exemple), plutôt que les moyennes et variances de chaque composantes ?

[Philou67]

J'ai le sentiment que

tenter de maximiser P_L*(x) + P_a*(x) + P_b*(x) ? (c'est à dire, calculer les moyennes et variances des composantes individuellement)

est le cœur de mon problème.
Je pense que sommer les probabilités par composante est inadapté. Quelqu'un saurait me dire ce qu'il convient de faire ?