Algorithmes hors-cœur pour les arbres de poids minimum et les hiérarchies de segmentations

Les hiérarchies binaires de partitions et les arbres de poids minimum sont des structures clés pour de nombreuses méthodes d'analyse hiérarchique comme celles impliquées en vision par ordinateur et en morphologie mathématique. Dans cette présentation, nous considérons le problème de leur calcul de manière hors-cœur, c'est-à-dire en minimisant la taille des structures de données qui sont simultanément nécessaires aux différentes étapes du calcul. Les algorithmes hors-cœur sont nécessaires lorsque les données sont trop grandes pour tenir entièrement dans la mémoire principale de l'ordinateur, ce qui peut être le cas avec de très grandes images dans un espace à 2, 3, ou plus, dimensions. Nous proposons un nouveau cadre algébrique composé de quatre opérations principales sur les hiérarchies : ajout d'une arête, sélection, insertion et jointure. Dans ce cadre, nous proposons et établissons la justesse d'un calcul hors-cœur pour les hiérarchies binaires de partitions et pour les arbres de poids minimum. Les premières applications au traitement d'images suggèrent l'efficacité pratique de ce calcul.

Contributeurs : Jean Cousty, Benjamin Perret, Harold Phelippeau, Stela Carneiro, Pierre Kamlay et Lilian Buzer