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

Deze paper introduceert een superpixel-hiërarchie voor hoogdimensionale afbeeldingen die de ruimtelijke lay-out en het attributenmanifold combineert om een consistente verkenning van zowel de afbeeldings- als attributenruimte mogelijk te maken, in tegenstelling tot bestaande methoden die de ruimtelijke structuur negeren.

De kern

Stel je voor dat je een gigantische, complexe foto hebt gemaakt. Maar dit is geen gewone foto met alleen rood, groen en blauw. Dit is een hyper-foto. Elke pixel op deze foto bevat niet één kleur, maar een heel dossier met duizenden gegevens: de chemische samenstelling, de temperatuur, de hoeveelheid licht van verschillende golflengten, of zelfs welke eiwitten er in een cel zitten.

Wetenschappers moeten deze foto's analyseren om patronen te vinden, maar dat is als proberen een heel boek te lezen terwijl je blinddoekt op een berg met miljoenen losse letters zit.

Hier komt dit nieuwe onderzoek van de auteurs (Vieth en collega's) om de hoek kijken. Ze hebben een slimme manier bedacht om deze "hyper-foto's" te verkennen, door ze te vertalen naar iets wat ons menselijk brein wel kan bevatten.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Losse Pijlen"

Stel je voor dat je een enorme stad hebt (de foto) en je wilt de bewoners (de pixels) groeperen op basis van wat ze eten (hun data).

• De oude methode: Ze keken alleen naar het eten. Ze zeiden: "Jij eet pizza, jij ook, jij ook... jullie horen bij elkaar!" Maar ze keken niet naar waar je woont. Het resultaat? Een groep mensen die bij elkaar horen qua eten, maar die in de hele stad verspreid wonen. Als je op de kaart kijkt, zie je geen samenhangend wijkje, maar een hoop losse stippen overal. Dat maakt het moeilijk om te zeggen: "Ah, in deze wijk wonen allemaal pizza-liefhebbers."
• Het gevolg: Als je een interessant gebied op de kaart wilt bestuderen, moet je duizenden losse stippen aanklikken. Dat is rommelig en traag.

2. De Oplossing: De "Wijk-Boekjes" (Superpixels)

De auteurs zeggen: "Wacht even, laten we eerst kijken naar de buurt."
Ze gebruiken een techniek die Superpixels noemt. Denk hierbij aan het maken van een mozaïek. In plaats van elke losse steen (pixel) apart te bekijken, plakken ze steentjes die dicht bij elkaar liggen en op elkaar lijken, samen tot één groter blokje.

• De slimme twist: Bij de oude methoden keken ze alleen naar de "smaken" (data). Deze nieuwe methode kijkt naar twee dingen tegelijk:
  1. De smaak: Hebben deze steentjes vergelijkbare data?
  2. De locatie: Wonen ze in dezelfde buurt?

Ze bouwen hiermee een hiërarchie (een ladder van details).

• Bovenste sport: Je ziet de hele stad als één groot, vaag blok.
• Middelste sport: Je ziet grote wijken.
• Onderste sport: Je ziet de individuele straten en huizen.

3. De Magische Kleefstof: De "Wandeltocht"

Hoe weten ze nu of twee blokken echt bij elkaar horen, als de data zo complex is? Ze gebruiken een wiskundig trucje dat lijkt op wandelaars.

Stel je voor dat je op een steen staat en je stuurt 50 kleine wandelaars (random walks) de stad in.

• Als de wandelaars van Steen A en Steen B vaak dezelfde routes lopen en dezelfde plekken bezoeken, dan zijn ze "verwant".
• Als de wandelaars van Steen A alleen naar de kust gaan en die van Steen B alleen naar de bergen, dan horen ze niet bij elkaar, ook al lijken ze op het eerste gezicht hetzelfde.

De auteurs gebruiken deze wandelroutes om te bepalen welke blokken (superpixels) bij elkaar gevoegd moeten worden. Hierdoor blijft de structuur van de data (de "manifold") behouden, maar is het ook nog eens ruimtelijk logisch.

4. Waarom is dit zo handig?

Stel je voor dat je een detective bent die een verdachte wijk onderzoekt.

• Met de oude methode: Je moet 1.000 losse verdachten (landmarks) opzoeken die verspreid zitten over de hele stad om die ene wijk te begrijpen.
• Met deze nieuwe methode: Je klikt op één groot wijkblok. Omdat het blok al is samengesteld uit logische buurten, zie je direct de hele wijk in één keer. Je hoeft niet te zoeken naar losse stukjes; het is al een compleet plaatje.

Dit maakt het veel sneller en duidelijker om patronen te zien. Je kunt inzoomen van "Hele stad" naar "Deze specifieke wijk" en dan naar "Deze specifieke straat", zonder dat de kaart in duizenden losse puntjes uit elkaar valt.

5. Waar is dit voor goed?

De auteurs testen dit op twee soorten foto's:

1. Satellietfoto's: Waar ze kunnen zien welke velden maïs zijn en welke soja, zelfs als ze er op het oog hetzelfde uitzien.
2. Medische foto's van weefsels: Waar ze kunnen zien hoe verschillende cellen (zoals immuuncellen) zich gedragen in een tumor. Ze kunnen nu makkelijk zien: "Ah, hier in deze groep cellen zitten veel 'vechters' (immuuncellen) die de tumor aanvallen."

Samenvattend

Dit onderzoek is als het maken van een slimme, interactieve atlas voor complexe data. In plaats van een hoop losse, verwarrende stippen te tonen, groeperen ze de data in logische, samenhangende blokken (buurten) die zowel qua inhoud als qua locatie bij elkaar horen. Hierdoor kunnen wetenschappers sneller en duidelijker de "verhaal" achter de data ontdekken, of het nu gaat om het landschap van de aarde of de cellen in ons lichaam.

Technische samenvatting

Hieronder volgt een gedetailleerde technische samenvatting van het artikel "Manifold-Preserving Superpixel Hierarchies and Embeddings for the Exploration of High-Dimensional Images" in het Nederlands.

1. Het Probleem

Hoge-dimensionale beelden (waarbij elke pixel een vector van attributen heeft, zoals in hyperspectrale beeldvorming of massacytometrie) worden vaak geanalyseerd door de attributenruimte te projecteren naar een lage dimensie (bijv. met t-SNE of UMAP) en deze te koppelen aan de ruimtelijke weergave van het beeld.

De huidige uitdagingen zijn:

• Schaalbaarheid: Beelden met miljoenen pixels zijn te groot voor directe verwerking door standaard dimensiereductiemethoden.
• Hiërarchische beperkingen: Bestaande hiërarchische dimensiereductiemethoden (zoals HSNE) bouwen hiërarchieën puur op basis van attributen. Ze negeren de ruimtelijke lay-out van de pixels.
• Inconsistentie: Hierdoor vertegenwoordigt één "landmark" (een samengevoegde punt in de hiërarchie) vaak verspreide pixels over het hele beeld, terwijl coherente ruimtelijke gebieden met vergelijkbare attributen door meerdere landmarks worden weergegeven. Dit maakt het moeilijk om gebieden van belang (ROI's) in de beeldruimte te exploreren en te koppelen aan hun abstracties in de attributenruimte.

2. Methodologie

De auteurs stellen een nieuwe methode voor die een superpixel-hiërarchie combineert met manifold-behoudende embedding. De kern van de methode is dat de hiërarchie niet alleen gebaseerd is op ruimtelijke nabijheid, maar ook op de onderliggende structuur van de hoge-dimensionale data.

Stappenplan:

1. Constructie van de KNN-grafiek (Attribute Space):

   • Er wordt een $k$-nearest neighbor (kNN) grafiek $G$ gebouwd in de attributenruimte (niet in de beeldruimte).
   • De grafiek wordt gesymmetriseerd en verbonden (via een minimum spanning tree) om te garanderen dat alle punten bereikbaar zijn.

2. Manifold-bewuste Similariteit via Random Walks:

   • In plaats van Euclidische afstanden of kortste paden (die gevoelig zijn voor "shortcuts"), gebruiken de auteurs random walks over de kNN-grafiek.
   • Voor elke vertex (pixel) worden $\omega$ wandelingen van $\lambda$ stappen uitgevoerd.
   • Dit resulteert in een transitie-kansvector (een feature) die de lokale structuur van de manifold beschrijft.
   • De similariteit tussen twee pixels (of superpixels) wordt berekend met de Bhattacharyya-coëfficiënt op basis van de overlap van deze kansverdelingen. Dit is robuust en behoudt de niet-lineaire structuur van de data.

3. Bouwen van de Superpixel-Hiërarchie:

   • De hiërarchie wordt van onderen naar boven (bottom-up) opgebouwd.
   • Er wordt een aangepaste versie van Borůvka's algoritme gebruikt om superpixels te mergen.
   • Merg-criterium: Twee superpixels worden samengevoegd als ze ruimtelijk aangrenzend zijn in het beeld en een hoge Bhattacharyya-similariteit hebben in de attributenruimte.
   • Bij het mergen worden de transitie-matrices (features) van de vertices samengevoegd en genormaliseerd, waardoor de nieuwe superpixel de eigenschappen van de onderliggende pixels behoudt zonder nieuwe random walks te hoeven berekenen.

4. Embedding per Hiërarchieniveau:

   • Op elk niveau van de hiërarchie worden de superpixels ingebed in een 2D-ruimte (bijv. met t-SNE of UMAP).
   • De afstandsmeting in de embedding wordt vervangen door de Bhattacharyya-afstand (afgeleid van de similariteit).
   • Dit zorgt ervoor dat de embedding op elk niveau consistent is met zowel de ruimtelijke samenhang als de attributenstructuur.

5. Subset Refinement (Verfijning):

   • Gebruikers kunnen een ROI selecteren in de embedding of het beeld.
   • Het systeem "zoomt in" door de geselecteerde superpixels te vervangen door hun onderliggende, fijnere superpixels van het volgende niveau.
   • Om geïsoleerde punten te voorkomen, kan een niet-exacte verfijning worden toegepast waarbij ook aangrenzende superpixels worden toegevoegd als hun connectiviteit boven een drempelwaarde ligt.

3. Belangrijkste Bijdragen

• Ruimtelijk-Attribuut Hiërarchie: De eerste hiërarchische embedding-methode die expliciet de ruimtelijke samenhang van pixels combineert met de niet-lineaire structuur van hoge-dimensionale attributen.
• Manifold-Preserving Similariteit: Het introduceren van een similariteitsmaat op basis van random walks (Bhattacharyya-coëfficiënt) die specifiek is ontworpen om de onderliggende manifold van hoge-dimensionale data te behouden tijdens het mergen van superpixels.
• Consistente Exploratie: Het mogelijk maken van een naadloze exploratie waarbij selecties in de beeldruimte direct corresponderen met coherente clusters in de attributenruimte, zonder verspreide landmarks.
• Implementatie: De methode is geïmplementeerd als een standalone bibliotheek en als plugin voor het ManiVault-framework.

4. Resultaten en Validatie

De methode is gevalideerd via twee use-cases en een kwantitatieve evaluatie:

• Use Case 1: Hyperspectrale Satellietbeelden (Indian Pines):

  • De superpixel-hiërarchie vereiste aanzienlijk minder landmarks om dezelfde ruimtelijke regio te vertegenwoordigen vergeleken met HSNE (bijv. 326 superpixels vs. 1.402 landmarks voor een ROI).
  • De resulterende embeddings tonen duidelijkere clusters en behouden de ruimtelijke grenzen van objecten (zoals velden en rivieren) beter dan de ruimtelijk-agnostische HSNE.

• Use Case 2: CyCIF Beeldvorming (Weefselanalyse):

  • Toepassing op kankerweefsel met 54 kanalen.
  • De superpixels op hogere abstractieniveaus matchen de contouren van individuele cellen (bijv. immuuncellen).
  • Het systeem kon specifieke celtypen (zoals FOXP3-positieve T-cellen) identificeren en lokaliseren binnen de weefselstructuur, wat de integratie van segmentatie en exploratie mogelijk maakt.

• Kwantitatieve Evaluatie:

  • Vergelijking met bestaande superpixel-methoden (FH, ERS, SLIC, BB) op datasets met ground truth.
  • De methode (SPH) presteert vergelijkbaar of beter op Explained Variation (EV) en ondersegmentatiefout (UE), wat aantoont dat de hiërarchie van hoge kwaliteit is, ondanks de focus op manifold-behoud in plaats van puur kleur-gebaseerde segmentatie.

5. Betekenis en Conclusie

Deze paper lost een fundamenteel probleem op in de visualisatie van grote, hoge-dimensionale datasets: het gebrek aan congruentie tussen ruimtelijke gebieden en hun attributen-abstracties.

Door een hiërarchie te bouwen die zowel de beeldruimte (via superpixel-aangrenzing) als de attributenruimte (via manifold-bewuste random walks) respecteert, biedt de methode:

1. Efficiëntie: Minder datapunten nodig voor een duidelijke weergave.
2. Interpretatie: Landmarks zijn semantisch betekenisvol in de ruimtelijke context (bijv. een hele veld of een groep cellen).
3. Exploratie: Onderzoekers kunnen moeiteloos zoomen van een globaal overzicht naar gedetailleerde regio's, waarbij de samenhang tussen beeld en data behouden blijft.

Dit is een belangrijke stap vooruit voor domeinen zoals geowetenschappen, systembiologie en cultureel erfgoed, waar de interactie tussen ruimtelijke locatie en complexe meetwaarden cruciaal is.