Discussion :

[marko1587]

hello,
je veux calculer le nombre de couleurs d'une image, quelle est la meilleure façon de le faire ???

[Celelibi]

Qu'appelles-tu le nombre de couleur d'une image ?

[marko1587]

si par exemple dans l'image il n y a que des pixels noirs et blancs alors le nombre de couleurs est 2, bref on suit ce raisonnement

[Celelibi]

Bien...
Ce que je peux te proposer c'est de parcourir toute l'image, et à chaque pixel d'une nouvelle couleur, la stocker dans un coin et incrémenter un compteur de couleur.

C'est un algo en O(N) en temps (avec N le nombre de pixels). Et en O(P) en espace, avec P le nombre de couleur de ton image. Ce qui peut faire 16777216 sur une image RGB avec 256 niveaux par canal. Ce qui peut facilement monter à 100Mo de mémoire consommée sur une implémentation naïve.

Un autre algo que je peux te proposer c'est de traiter ton image comme un tableau 1D et de trier les pixels de ton image par valeur (à toi de choisir la relation d'ordre que tu veux). Ensuite tu n'as plus qu'à reparcourir ton image triée et compter le nombre de transition de couleur.

Cet algo est en O(N log N) en temps, et en O(N) en espace.

[marko1587]

merci, en effet j'ai posée la question à cause de la complexité et le temps du calcul, pouvez m'expliquer ta solution car je ne l'ai pas bien comprise

[Celelibi]

Quelle solution n'as-tu pas compris ? Je t'en ai proposé 2.

[marko1587]

la deuxieme

[Celelibi]

Bien :
1) Trier les pixels de ton image par valeur. Cela va avoir le bon goût de les regrouper par valeurs identique.
2) Parcourir tous les pixels de ton image pour déterminer le nombre de "zone" de couleur uniforme.

[Alexis.M]

Comme il ne peut pas y avoir plus de couleurs différentes que de pixels dans l'image (au pire on a une couleur différente par pixel donc P<=N), une implémentation de la première méthode basée par exemple sur une table de hashage, devrait toujours être plus intéressante en complexité temporelle et spatiale que la deuxième, non ?

[marko1587]

merci pour les réponses,
la taille des images que je manipule est fixe : 128x128, dois je utiliser un tabelau statique ou une liste dynamique ???

[Tiffado]

Quelque soit la méthode utilisé, ça ne sera fatalement pas du O(n), avec n le nombre de pixel.

La méthode que j'utiliserais (sans doute pas le mieux, mais facilement implémentable, et relativement efficace) :

Tu crées une liste vide de couleur (genre une liste de String avec des valeurs comme "FF0000" pour le rouge).

Tu parcours ton image (matrice), et pour chaque élément, tu as 2 possibilités :
1- Cette couleur n'est pas présente dans ta liste créée par tes soins => Tu l'ajoutes dans la liste.
2- Cette couleur est présente dans la liste => tu fais rien.

Quand c'est fini, tu regarde simplement le nombre d'élément de ta liste, et en plus de ça, tu as la liste exhaustive des couleurs présentes dans ton image.

Pour voir si l'élément est présent dans la liste, tu peux faire un taListe.contain(taCouleur) si c'est du Java que tu utilises.

Donc tu ne parcours qu'une seule fois ta matrice, mais vu que tu parcours ta liste sans arrêt, j'ai un doute sur le fait que ce soit du O(n).

PS : j'ai pas suivi de cours sur les complexités, dont je dis peut être une énorme ********.

Ca me parait en tout plus simple à implémenter et moins gourmand que la méthode de tri qui est déjà facilement en O(n*log(n)) suivant la méthode utilisée

[Alexis.M]

@marko quel langage utilises-tu ?

@Tiffado, l'utilisation d'une hash map permet l'accès à un élément en O(1), donc on a bien un algo en O(n).

En supposant que l'image est donnée sous forme de tableau numpy en python on aurait:

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
def count_colors(image):
    colors = {}
    height, width = image.shape
    for i in range(height):
        for j in range(width):
             c = tuple(image[i,j])
             if colors.has_key(c):
                 colors[c] += 1
             else:
                 colors[c] = 1
    return colors

Edit:

1) La complexité O(1) est théorique si on a une bonne fonction de hashage.
2) Il me semble qu'il existe HashMap en Java et unordered_map en C++0x pour les tableau associatifs.

[marko1587]

merci pour les réponses,
j'utilise Delphi, est ce que les hash map existent en Delphi ? ou autre structure equivalente ?

[Celelibi]

Comme il ne peut pas y avoir plus de couleurs différentes que de pixels dans l'image (au pire on a une couleur différente par pixel donc P<=N), une implémentation de la première méthode basée par exemple sur une table de hashage, devrait toujours être plus intéressante en complexité temporelle et spatiale que la deuxième, non ?

Avec une table de hashage, y'a toujours un facteur chance. Puisque quelque soit la fonction de hashage, la complexité d'un ajout ou d'une recherche peut être en O(M).
On a donc du O(N) en moyenne et du O(N*M) au pire. (Avec N le nombre de pixels, et M le nombre de couleurs distinctes.)

Si on remplace la table de hashage par une structure de données plus déterministe comme un arbre équilibré, cette méthode passe en O(N * log(M)) en moyenne, idem au pire.

En espace ça reste du O(M).