Discussion :

[carton99]

Bonjour,
Je fait une étude sur les différents algorithme d'étiquetage temps réel.
J'en ai trouvé que deux convenables: Algorithme de difusion et Union-Find.

Je travail sur une image binaire ou la valeur 1 est considéré comme délimeteurs ces pixels ne sont pas traité, j'ai choisit 4-conexcité.

J'ai réalisé plusieurs implémentations des deux algorithmes.
Celle donnant les meilleurs résultats sont l'algorithme de difusion optimisé par traitement de ligne intégrant la seconde optimisation visant à ajouter dans la pile uniquement les extrémités des lignes.(voir le sujet sur wikipedia http://fr.wikipedia.org/wiki/Algorit..._par_diffusion )
Le deuxième est le Union find classique disponible sur ce site grace à Pseudo-code.

Et bien bizarrement Union find est plus lent que la difusion par ligne. Pour une image de 480*320 j'ai 80ms en moyenne pour la difusion et 130 ms pour union find.
Je pensais que Union find était le meilleur.

Du coup sa m'énerve car je ne trouve pas sur le net d'étude comparative ou un site expliquant clairement quel est la meilleur méthode, de plus je ne sais pas quel méthode est utilisé dans l'opérateur de labeling sur openCV.

Trois remarque importante.

- Je travail en AS3, et j'ai l'impression que l'utilisation des tableaux semble ralentir gravement mes algorithmes orienté sur les listes. je vai essayé de remplacer le tableau de type Array par un bitmap mais c'est pas gagné.

- Je n'ai pas recopié exactement la méthode de Pseudo-code, mes listes sont des structures comprenant deux tableaux le premier tableau contient les cordonnées des points d'une classe et le deuxième tableau contient les liens entre les classe et les structures, ce qui me permet d'évité les root(root(root)) l'ors de la concaténation. De plus je me suis rendu compte que l'or de la concaténation la plus petite taille de ce tableau de correspondance entre les deux classes faisait généralement une taille de 1 (98% des cas) je ne peut donc pas perdre de temps de ce coté.

- La troisième remarque est que la deuxième passe de l'algorithme de Union-find fait généralement la moitié en temps de l'algorithme de difusion, je ne voit donc pas comment si ce n'est en l'égalent, Union-find pourrais être plus rapide. Ce qui confirme les faiblesses de l'utilisation de tableau en AS3.


Cordialement,
Christophe

[pseudocode]

L'algo Union-Find utilise un tableau statique, alors que l'algo FIFO utilise des piles dynamiques.

L'accès à un tableau est généralement plus performant que la gestion d'une pile. Cela dit, il se peut que dans ton langage ca soit l'inverse. Ca parait tout de même curieux.

[carton99]

Bonjour,
ok en faite c'était une erreur de ma faute. J'ai fait erreur dans l'algorithme union-find.

Du coup effectivement UnionFind est meilleur, mais la différence est légere sur les images de petite taille, par contre l'écart est bien visible sur des grande taille 1080p. L'écart type des résultats et plus important sur union-find j'en déduit qu'il est sensible à la forme et au nombre de classe

Au niveau de documentation je ne trouve toujours rien, à par cette article sur wikipedia qui donne quelque référence http://en.wikipedia.org/wiki/Connect...onent_labeling


Merci