Citation Envoyé par ToTo13
Bonjour,
je fais de l'imagerie numérique et j'ai du à moment donné lancer un longue récursivité sur une image (calcul de composantes connexe) en 1024*1024.
Besoin de récursivité pour calculer les composantes d'une image? Votre algorithme doit ressembler aux algos de remplissage, non?

Pour calculer les composantes d'une image, il existe des algorithmes itératifs extrêmement performants.

Par exemple, avec l'algo suivant, il faut quelques dixièmes de seconde (moins?) pour calculer les composantes d'une image binaire de taille 5000x7000:

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
Pour L de 0 à Hauteur - 2:
--Calculer les runs des lignes L et L+1;
--Considérer chaque run comme une composante;
--Parcourir les listes de runs des lignes L et L+1:
----A chaque fois que deux runs sont connectés, faire fusionner les composantes auxquells ils appartiennent

Pour mémoriser, à faible coût, quelles composantes ont été fusionnées entre elles, on maintient une structure union-find (dont chaque ensemble est constitué de composantes qui ont été fusionnées en une jusque-là).

A la fin de l'algo, on parcourt la liste des composantes:
- celles qui sont au somment d'un arbre inversé de la structure union-find sont des composantes (maximales) de l'image, car elles n'ont jamais été fusionnées avec d'autres (en revanche elles peuvent être le résultat de nombreuses fusions);

- les autres peuvent être détruires car elles ne sont que des "sous-composantes" résiduelles.


C'est la méthode d'extraction de composante la plus rapide que je connais, elle permet quand on la code dans le détail de nombreuses petites "optimisations", notamment la vitesse d'exécution est la même en 4-connexité et en 8-connexité (car on travaille sur des runs et non sur des pixels). Le parcours des deux listes de runs de deux lignes consécutives a aussi les avantages de l'algo de fusion de deux listes triées (on avance dans une des deux listes au moins à chaque itération). etc. etc.

On m'a cependant soufflé qu'il existait une méthode encore plus rapide qui serait une amélioration de celle-ci, mais je n'en ai jamais trouvé la trace nulle part...