Manifold-Preserving Superpixel Hierarchies and Embeddings for the Exploration of High-Dimensional Images

Each language version is independently generated for its own context, not a direct translation.

Imaginez que vous avez une photo de la taille d'une ville entière, mais au lieu de voir simplement des couleurs (rouge, vert, bleu), chaque pixel contient des centaines d'informations cachées : la température, la composition chimique, la vitesse du vent, etc. C'est ce qu'on appelle une image haute dimensionnelle.

Le problème ? C'est comme essayer de lire un livre écrit dans 200 langues différentes en même temps. C'est trop d'informations pour notre cerveau, et les ordinateurs ont du mal à trouver des motifs clairs.

Voici comment les auteurs de cette paper proposent de résoudre ce casse-tête, en utilisant une analogie simple : la construction d'une carte de super-héros.

1. Le problème des anciennes cartes (Les "Landmarks" perdus)

Avant, pour simplifier ces images géantes, les chercheurs utilisaient des méthodes qui prenaient des échantillons au hasard, un peu comme si vous preniez des points au hasard sur une carte de France pour dire "ici c'est Paris, ici c'est Lyon".

Le souci : Ces points (appelés "landmarks") pouvaient être éparpillés n'importe où. Un point pouvait représenter une partie de Paris et une autre partie de Marseille en même temps.
Résultat : Quand vous zoomiez sur une région intéressante, la carte devenait confuse. Vous ne saviez plus où vous étiez dans l'image réelle.

2. La solution : Les "Superpixels" (Des quartiers intelligents)

Les auteurs proposent une nouvelle méthode basée sur les superpixels.

L'analogie : Imaginez que vous ne regardez plus chaque brique de la ville, mais que vous regroupez les briques en quartiers (des superpixels).
La magie : Au lieu de faire ces quartiers uniquement par la proximité géographique (comme un quartier résidentiel), ils les créent en regardant ce que les briques ont en commun. Si deux briques ont la même "personnalité" chimique, même si elles sont un peu éloignées, elles peuvent appartenir au même quartier.
Le résultat : Chaque "superpixel" est un groupe cohérent qui a du sens à la fois sur la carte (l'image) et dans le monde des données (les attributs).

3. L'arbre généalogique (La hiérarchie)

Pour explorer ces données, ils ne font pas une seule carte, mais une pyramide de cartes (une hiérarchie) :

Niveau 1 (Le détail) : On voit chaque pixel individuellement. C'est très précis, mais c'est le chaos.
Niveau 2 (Le quartier) : On regroupe les pixels similaires en "superpixels". C'est comme passer d'une vue satellite à une vue de quartier.
Niveau 3 (La ville) : On regroupe les quartiers en zones plus grandes.
Niveau 4 (Le pays) : On voit l'ensemble de la structure.

L'avantage est que vous pouvez zoomer et dézoomer facilement. Si vous voyez quelque chose d'intéressant sur la carte "Pays", vous pouvez descendre d'un cran pour voir le "Quartier", puis le "Pixel", sans jamais perdre le fil de l'endroit où vous êtes.

4. La boussole magique (La marche aléatoire)

Comment savent-ils quels pixels regrouper ? Ils utilisent une technique appelée "marche aléatoire" (random walks).

L'analogie : Imaginez que vous lancez des milliers de petits robots sur votre image. Chaque robot part d'un pixel et se promène. S'il rencontre des pixels très similaires à son point de départ, il s'y attarde. S'il rencontre des pixels très différents, il repart vite.
Le but : En regardant où tous ces robots finissent par s'accumuler, on comprend la "structure cachée" des données. C'est comme si les robots dessinaient une carte des "voisins naturels" de chaque pixel, même si ces voisins sont complexes et non linéaires.

5. Pourquoi c'est génial ? (Deux exemples concrets)

Les auteurs ont testé leur méthode sur deux terrains :

Les images satellites (Hyperspectrales) : Pour voir les champs, les routes et les rivières. Leur méthode permet de voir clairement où finit un champ de maïs et où commence un champ de soja, même si les couleurs sont très proches, car elles regardent la "chimie" de la plante.
Les tissus biologiques (Cancer) : Pour analyser des cellules. Imaginez vouloir trouver des cellules immunitaires spécifiques dans une tumeur. Leur méthode permet de regrouper automatiquement les cellules qui se ressemblent, créant des "quartiers" de cellules saines et des "quartiers" de cellules malades, aidant les médecins à voir la structure de la maladie.

En résumé

Cette paper propose une nouvelle façon de regarder les images complexes :

Au lieu de regarder des points isolés, on regarde des quartiers cohérents.
On construit une pyramide de cartes pour voir le grand tableau ou les détails.
On utilise des robots explorateurs pour comprendre la structure cachée des données.

C'est comme passer d'une liste de numéros de téléphone désordonnée à une annuaire bien organisé par quartier, où vous pouvez facilement trouver qui habite près de qui, même si vous ne connaissez pas la ville par cœur. Cela rend l'exploration de données géantes beaucoup plus intuitive et rapide.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

Les images haute dimensionnelles (où chaque pixel possède un vecteur d'attributs de grande dimension, comme en imagerie hyperspectrale ou en cytométrie de masse) posent un défi majeur pour l'exploration visuelle. Les méthodes classiques reposent souvent sur des vues coordonnées : une représentation de l'image et une projection de l'espace des attributs (via des techniques de réduction de dimensionnalité comme t-SNE ou UMAP).

Cependant, plusieurs limitations existent pour les grands jeux de données (plusieurs millions de pixels) :

Inadéquation des méthodes plates : Les techniques de réduction de dimensionnalité (DR) classiques peinent à gérer l'échelle et la complexité computationnelle.
Limites des hiérarchies existantes : Les méthodes de DR hiérarchiques actuelles (ex: HSNE, HUMAP) construisent des hiérarchies basées uniquement sur les attributs des données. Elles ignorent la disposition spatiale des pixels.
Conséquences : Dans ces hiérarchies, un "landmark" (point de repère) peut représenter des pixels dispersés géographiquement, et une région cohérente de l'image peut être fragmentée en plusieurs landmarks. Cela rend l'exploration interactive difficile, car il n'y a pas de correspondance congruente entre une région d'intérêt (ROI) dans l'espace image et son abstraction dans l'espace des attributs.

2. Méthodologie

Les auteurs proposent une hiérarchie de superpixels qui préserve la structure de la variété (manifold) des données tout en respectant la cohérence spatiale de l'image. La méthode se déroule en trois étapes principales :

A. Construction du graphe de voisinage dans l'espace des attributs

Au lieu d'utiliser des distances euclidiennes globales, les auteurs construisent un graphe de $k$ -plus proches voisins (kNN) basé sur les attributs haute dimensionnels. Pour capturer la structure non linéaire de la variété sous-jacente, ils utilisent des marches aléatoires sur ce graphe plutôt que les plus courts chemins (qui peuvent créer des raccourcis erronés).

Pour chaque nœud (pixel), on effectue $\omega$ marches aléatoires de $\lambda$ étapes.
Cela génère une distribution de probabilité (vecteur de caractéristiques) décrivant le voisinage local du nœud sur le graphe.

B. Construction de la hiérarchie de superpixels

La hiérarchie est construite de bas en haut (bottom-up) en fusionnant des superpixels adjacents dans l'image.

Critère de fusion : La similarité entre deux superpixels n'est pas une distance spatiale ou une distance d'attribut brute, mais le coefficient de Bhattacharyya calculé entre leurs vecteurs de probabilité issus des marches aléatoires. Ce coefficient mesure le chevauchement des distributions de visites sur le graphe d'attributs.
Algorithme : Une adaptation de l'algorithme de Borůvka est utilisée. Contrairement aux méthodes classiques qui fusionnent toujours, ici, une fusion n'a lieu que si la similarité est significative. Si un superpixel n'a aucun voisin similaire (coefficient nul), il n'est pas fusionné à ce niveau, préservant ainsi les structures fines.
Mise à jour des caractéristiques : Lors de la fusion, les lignes et colonnes de la matrice de transition des marches aléatoires sont fusionnées et rénormalisées, évitant ainsi de recalculer de nouvelles marches aléatoires à chaque niveau.

C. Intégration dans l'Embedding (Projection)

Pour visualiser les données à chaque niveau de la hiérarchie, les auteurs utilisent des algorithmes de DR non linéaires (t-SNE ou UMAP).

La matrice de probabilité conditionnelle $P$ utilisée par ces algorithmes est recalculée en remplaçant la distance euclidienne par la distance de Bhattacharyya dérivée des marches aléatoires.
Cela permet de générer des embeddings où chaque point correspond à un superpixel, garantissant que la proximité dans l'embedding reflète à la fois la similarité des attributs et la cohérence spatiale.
Raffinement interactif : L'utilisateur peut sélectionner une région dans l'embedding ou l'image pour "zoomer" vers un niveau inférieur de la hiérarchie, en ne recalculant l'embedding que pour le sous-ensemble de superpixels concernés.

3. Contributions Clés

Hiérarchie guidée par l'image : C'est la première méthode de DR hiérarchique qui intègre explicitement la topologie spatiale de l'image lors de la construction de la hiérarchie, assurant que les landmarks correspondent à des régions spatialement cohérentes.
Mesure de similarité préservant la variété : Utilisation de marches aléatoires sur un graphe kNN d'attributs pour définir une métrique de similarité robuste, adaptée aux structures non linéaires complexes, utilisée à la fois pour la segmentation (fusion) et l'embedding.
Efficacité computationnelle : En réutilisant et en fusionnant les caractéristiques des marches aléatoires plutôt que de les recalculer à chaque niveau, la méthode est plus rapide et moins gourmande en mémoire que les approches itératives classiques.
Outils ouverts : La méthode est implémentée dans la bibliothèque ManiVault et disponible sur GitHub, permettant une exploration interactive coordonnée image/embedding.

4. Résultats et Validation

Les auteurs ont validé leur approche sur deux cas d'usage réels et une évaluation quantitative :

Cas d'usage 1 : Imagerie hyperspectrale (Indian Pines)
- Comparaison avec HSNE (Hierarchical t-SNE).
- Résultat : La hiérarchie de superpixels nécessite beaucoup moins de landmarks pour représenter une même région d'intérêt (ROI) avec le même niveau de détail. Par exemple, une ROI couverte par 1 402 landmarks dans HSNE n'en nécessite que 326 avec la méthode proposée.
- Avantage : Les clusters dans l'embedding sont plus distincts et les frontières spatiales (champs, routes) sont mieux préservées.
Cas d'usage 2 : Imagerie tissulaire CyCIF (Cancer de la peau)
- Exploration de l'abondance de protéines pour identifier des types cellulaires (ex: lymphocytes T régulateurs FOXP3).
- Résultat : La hiérarchie permet de segmenter naturellement les cellules et de visualiser leur distribution spatiale à travers les niveaux d'abstraction. Les structures biologiques (vaisseaux sanguins, jonction dermo-épidermique) émergent clairement à différents niveaux de la hiérarchie.
- Avantage : Fusionne la segmentation et l'exploration en un seul flux de travail.
Évaluation Quantitative
- Comparaison avec des méthodes de superpixels classiques (SLIC, ERS, FH) sur des données avec vérité terrain.
- Résultat : La méthode proposée (SPH) obtient des scores compétitifs en termes d'erreur de sous-segmentation (UE) et de variation expliquée (EV), souvent supérieurs aux méthodes adaptées à l'hyperspectral, tout en étant conçue spécifiquement pour l'exploration hiérarchique.

5. Signification et Impact

Ce travail comble un fossé important entre l'analyse d'images spatiales et l'analyse de données haute dimensionnelles. En garantissant que les abstractions hiérarchiques respectent à la fois la géométrie de la variété des données et la topologie de l'image, la méthode permet :

Une exploration plus intuitive : L'utilisateur peut naviguer du global au local sans perdre le contexte spatial.
Une réduction de la complexité : Moins de points à visualiser pour une même information, ce qui accélère le calcul et améliore la lisibilité.
Une nouvelle approche pour la bio-informatique et la télédétection : La capacité à identifier des structures spatiales cohérentes (comme des cellules ou des types de sols) directement via l'embedding ouvre la voie à de nouvelles analyses de données complexes.

En résumé, cette méthode transforme l'exploration d'images haute dimensionnelles en un processus interactif où l'image et ses attributs sont intrinsèquement liés, offrant une vue d'ensemble claire tout en permettant un zoom détaillé sur les structures pertinentes.