Discussion :

[xxiemeciel]

Salut,

Je voulais savoir si certains d'entre vous connaissent des algorithmes performants pour calculer des histogrammes sur des images dont chaque pixel est codé sur 32 Bits (je ne parle pas forcement d'images RGB)

Je ne parle pas d'algo basique ce serait trop simple Dans mon cas l'image peut avoir des pixels avec des valeurs comprises entre
MIN_FLOAT et MAX_FLOAT (je sais plus les valeurs exactes mais c'est un tres grand intervalle) et les images peuvent etre tres grosses aussi (plusieurs Go)

Pour l'instant le seul algorithme que j'ai consiste a parcourir l'image une premiere fois pour determiner le pixel min et le pixel max

de decouper cet intervalle en 65536 intervalles

de prevoir un tableau en memoire de 65536 emplacements

et de parcourir l'image une deuxieme fois pour classer les pixels.

Sinon on a proposé aussi d'utiliser une map utilisant la valeur du pixel en clef, mais il semblerait que la perte de performance soit trop importante pour etre utilisé sur des grosses images.

J'ai essayé quelques recherches pour trouver mieux mais en vain jusqu'a present.



XXiemeciel

[mathieu_t]

Salut !

Sinon on a proposé aussi d'utiliser une map utilisant la valeur du pixel en clef, mais il semblerait que la perte de performance soit trop importante pour etre utilisé sur des grosses images

Ta deuxième proposition, je comprends pas bien la phrase. Est-ce que c'est :
parcourir directement l'image :
- pour chaque nouvelle valeur d'intensité, créer une nouvelle instance,
- pour une valeur déjà existante, ajouter un à l'instance correspondante ?

Là tu ne parcoures qu'une fois l'image, et tu fais un rangement par liste chaînée par exemple... Mais c'est sûr que le fait de créer des insertions dans la liste risque de faire perdre un peu de temps... En même temps je doute que ça puisse être pire que de parcourir 2 fois l'image !

A+

[Matthieu Brucher]

Allouer de la mémoire pour chaque pixel ou presque, à la volée, ça coûte beaucoup plus, je pense ! Et effectivement, la map est sans doute plus adaptée que la liste chaînée - c'est déjà trié -
Ensuite, pour tes 65536 pas, ça dépend plutôt de al taille de ton image.

[Jean-Marc.Bourguet]

Tout depend de la precision que tu veux sur ton histogramme.

Une technique possible: tu lis des points jusqu'a ce que tu en ait deux de differents. Tu partages l'intervalle en 256K ou 512K (donc plus que les 64K que tu voulais). Tant que les nouveaux points sont dans l'intervalle couvert, pas de probleme. Quand il y en a un en dehors, tu agrandis l'intervalle par un facteur entier de sort qu'il couvre le nouveau point (tu peux aller plus loin que lui a cause de la contrainte entiere; tu peux aussi essayer simplement de decaler l'intervalle si l'autre extremite n'a pas ete atteinte). A la fin, tu refusionnes dans le nombre d'intervalle ue tu desires.

[xxiemeciel]

Salut !

Sinon on a proposé aussi d'utiliser une map utilisant la valeur du pixel en clef, mais il semblerait que la perte de performance soit trop importante pour etre utilisé sur des grosses images

Ta deuxième proposition, je comprends pas bien la phrase. Est-ce que c'est :
parcourir directement l'image :
- pour chaque nouvelle valeur d'intensité, créer une nouvelle instance,
- pour une valeur déjà existante, ajouter un à l'instance correspondante ?

Là tu ne parcoures qu'une fois l'image, et tu fais un rangement par liste chaînée par exemple... Mais c'est sûr que le fait de créer des insertions dans la liste risque de faire perdre un peu de temps... En même temps je doute que ça puisse être pire que de parcourir 2 fois l'image !

A+

La complexité de se que tu propose avec une liste chainé est en O(n2) dans le pire des cas si tout les pixels ont des valeurs differentes.

La complexité avec la MAP est de O(nlog(n))

Alors que parcourir deux fois l'image est lineaire.

XXiemeciel

[xxiemeciel]

Allouer de la mémoire pour chaque pixel ou presque, à la volée, ça coûte beaucoup plus, je pense ! Et effectivement, la map est sans doute plus adaptée que la liste chaînée - c'est déjà trié -
Ensuite, pour tes 65536 pas, ça dépend plutôt de al taille de ton image.

Oui mais l'insertion d'une clef dans une map ne se fait pas en temps constant. C'est en log(n)

XXiemeciel

[xxiemeciel]

Tout depend de la precision que tu veux sur ton histogramme.

Une technique possible: tu lis des points jusqu'a ce que tu en ait deux de differents. Tu partages l'intervalle en 256K ou 512K (donc plus que les 64K que tu voulais). Tant que les nouveaux points sont dans l'intervalle couvert, pas de probleme. Quand il y en a un en dehors, tu agrandis l'intervalle par un facteur entier de sort qu'il couvre le nouveau point (tu peux aller plus loin que lui a cause de la contrainte entiere; tu peux aussi essayer simplement de decaler l'intervalle si l'autre extremite n'a pas ete atteinte). A la fin, tu refusionnes dans le nombre d'intervalle ue tu desires.

J'aime bien ton idée mais sa oblige a allouer beaocup de memoire aux fins de stockage des données, je vais y reflechir

XXiemeciel

[Jean-Marc.Bourguet]

Tu traites plusieurs giga de donnees, mais tu rechines a allouer un ou deux megas pour le traitement ?

[xxiemeciel]

Tu traites plusieurs giga de donnees, mais tu rechines a allouer un ou deux megas pour le traitement ?

Ce n'est pas parceque je traite de images de plusieurs Go que toute l'image est en memoire.

En fait on decoupe les images en Tiles et on ne traite qu'une partie de l'image a la fois, la gestion de la memoire est tres importante. mais dans mon cas se traitement est transparent au niveau ou j'utilise l'image.

XXiemeciel

[Jean-Marc.Bourguet]

Tu traites plusieurs giga de donnees, mais tu rechines a allouer un ou deux megas pour le traitement ?

Ce n'est pas parceque je traite de images de plusieurs Go que toute l'image est en memoire.

J'espere. Un giga par ici, un giga par la et on finit par ne plus ternir dans 32 bits d'espace d'adresse. Note que nous autres on fournis aussi nos appli en 64 bits pour cette raison.

Mais il y a quand meme un rapport mille entre 1G et 1M. Si allouer 4 ou 8 fois la taille du resultat ne convient pas, je crains que tu sois force de faire deux passes. Tu peux peut-etre te contenter de 2 fois, mais alors la precision commence a devenir tres faible. Tout depend de a quoi ca sert apres.

[xxiemeciel]

Mais il y a quand meme un rapport mille entre 1G et 1M. Si allouer 4 ou 8 fois la taille du resultat ne convient pas, je crains que tu sois force de faire deux passes. Tu peux peut-etre te contenter de 2 fois, mais alors la precision commence a devenir tres faible. Tout depend de a quoi ca sert apres.

C'est vrai tu as raison, sinon au niveau de la precision on a emis la possibilité d'avoir un histogramme moins precis mais d'utiliser les overview de l'image qui dans certain format sont stocké sur le disque, on a des overview au 1/3, 1/9 et 1/27. Ce qui permettrait de diminuner grandement la quantité de traitement.

XXiemeciel

[Matthieu Brucher]

Allouer de la mémoire pour chaque pixel ou presque, à la volée, ça coûte beaucoup plus, je pense ! Et effectivement, la map est sans doute plus adaptée que la liste chaînée - c'est déjà trié -
Ensuite, pour tes 65536 pas, ça dépend plutôt de al taille de ton image.

Oui mais l'insertion d'une clef dans une map ne se fait pas en temps constant. C'est en log(n)

XXiemeciel

Jamais dit le contraire... Je ne vois pas le rapport entre ce que je dis et ta réponse.

[Matthieu Brucher]

J'espere. Un giga par ici, un giga par la et on finit par ne plus ternir dans 32 bits d'espace d'adresse. Note que nous autres on fournis aussi nos appli en 64 bits pour cette raison.

Mais il y a quand meme un rapport mille entre 1G et 1M. Si allouer 4 ou 8 fois la taille du resultat ne convient pas, je crains que tu sois force de faire deux passes. Tu peux peut-etre te contenter de 2 fois, mais alors la precision commence a devenir tres faible. Tout depend de a quoi ca sert apres.

Je traite aussi des Go d'images - IRM 3D -, mais jamais je n'ai assez de mémoire, même en 64bits, ça swappera, donc inutile. Je préfère travailler sur des blocs

[xxiemeciel]

Allouer de la mémoire pour chaque pixel ou presque, à la volée, ça coûte beaucoup plus, je pense ! Et effectivement, la map est sans doute plus adaptée que la liste chaînée - c'est déjà trié -
Ensuite, pour tes 65536 pas, ça dépend plutôt de al taille de ton image.

Oui mais l'insertion d'une clef dans une map ne se fait pas en temps constant. C'est en log(n)

XXiemeciel

Jamais dit le contraire... Je ne vois pas le rapport entre ce que je dis et ta réponse.

Allouer la memoire ne couteras pas plus cher qu"une insertion en log(n)
sauf evidemment si je fais un malloc a chaque nouveau pixel mais se serait un peu stupide.

xxiemeciel

[xxiemeciel]

Tout depend de la precision que tu veux sur ton histogramme.

Une technique possible: tu lis des points jusqu'a ce que tu en ait deux de differents. Tu partages l'intervalle en 256K ou 512K (donc plus que les 64K que tu voulais). Tant que les nouveaux points sont dans l'intervalle couvert, pas de probleme. Quand il y en a un en dehors, tu agrandis l'intervalle par un facteur entier de sort qu'il couvre le nouveau point (tu peux aller plus loin que lui a cause de la contrainte entiere; tu peux aussi essayer simplement de decaler l'intervalle si l'autre extremite n'a pas ete atteinte). A la fin, tu refusionnes dans le nombre d'intervalle ue tu desires.

J'ai repensé un peu a cette solution et dans le pire des cas le resultat serait probablement desastreux, le pire des cas etant que le pixel suivant est toujours un peu plus grand que le precedent, alors on fait un traitement important a chaque pixel.

Par contre on pourrais adapter ton idée au niveau de chaque block, on parcours deux fois chaque block de l'image pour en construire l'histogramme suivant la methode simple. et on fera une fusion avec l'histogramme du block suivant.

- le premier avantage et de lire deux fois un block en memoire, donc on aura pas a aller le lire deux fois sur le disque
- Et la fusion des histogramme se fera seulement au niveau des changement de block.

XXiemeciel

[Matthieu Brucher]

Allouer la memoire ne couteras pas plus cher qu"une insertion en log(n)
sauf evidemment si je fais un malloc a chaque nouveau pixel mais se serait un peu stupide.

Je pensais au cas de la liste chaînée.

[xxiemeciel]

Je pensais au cas de la liste chaînée.

la liste chainée est completement innefficace puisque tu dois la parcourir a chaque nouvelle valeur pour savoir si cette valeur a deja été trouvé ou non.

XXiemeciel

[Matthieu Brucher]

Oui, c'est ce que j'ai dit...............

[xxiemeciel]

j'avoue la je te suis plus , je n'ai jamais parlé de liste chainee dans aucun de mes messages excepté pour dire que c etait mauvais ...

XXiemeciel