Sparse Randomised Approximation of Normal Cycles

Technische Samenvatting: Spaarse Gerandomiseerde Approximatie van Normale Cycli

Probleemstelling
In toepassingen van geometrisch leren, zoals computationele anatomie, is er een behoefte aan het bouwen van statistische modellen van vormvariatie met behulp van discrete curven en oppervlakken. Een cruciale vereiste is een getrouwheidsmetriek om data te vergelijken met door modellen gegenereerde vormen. Hoewel metrieken voor puntenwolken (bijv. Chamfer, Hausdorff) bestaan, schieten deze vaak tekort in het vastleggen van de onderliggende geometrische structuur of vereisen ze dichte correspondenties die mogelijk niet goed gedefinieerd zijn.

Geometrische meetkunde biedt een alternatief zonder correspondentie via stromen (currents) en varifolds, die vormen inbedden in de duale ruimte van differentiaalvormen binnen een Reproducerende Kern Hilbertruimte (RKHS). Deze representaties leggen echter alleen eerste-orde geometrische informatie vast (raak-/normaalrichtingen) en hebben moeite met regio's met hoge kromming, vertakkingspunten of grenzen, wat ongewenste kenmerken kan genereren tijdens diffeomorfe registratie (LDDMM).

De normale cyclus-representatie adresseert deze beperkingen door te integreren over de eenheidsnormaalbundel, waardoor hogere-orde eigenschappen zoals gemiddelde en Gaussische kromming worden gecodeerd. Hoewel theoretisch superieur voor complexe vormen, is de praktische berekening van de normale cyclus-metriek evenredig duur. De complexiteit ervan schaalt als $O(MN)$ voor getrianguleerde oppervlakken met $M$ en $N$ randen, wat het 3–5 keer computationeel intensiever maakt dan stromen of varifolds. Dit beperkt de toepassing ervan voor grootschalige datasets (bijv. resoluties $>10^5$).

Methodologie
De auteurs stellen een algoritme voor spaarse gerandomiseerde approximatie voor normale cycli voor, dat hun eerdere werk op stromen en varifolds [1] uitbreidt naar deze hogere-orde representatie. De methodologie verloopt in drie hoofdfasen:

1. Expliciete Dirac Delta Decompositie:
   De auteurs leiden een expliciete decompositie af van de discrete ingebedde normale cyclus voor een getrianguleerd oppervlak onder het geval van de constante normaal kern ($K_s = 1$). Voortbouwend op de decompositie van normale cycli in planaire, cilindrische en sferische componenten [12, 13], tonen zij aan dat voor $K_s=1$ de planaire component verdwijnt. De resterende normale cyclus $N(T)$ wordt uitgedrukt als een som van Dirac deltas gelokaliseerd op de middelpunten van randen (cilindrische component) en de randvertices (sferische component):
   $$N(T) \approx 2 \sum_{j=1}^{n_e} \delta_{c_j} \gamma_j + \pi \sum_{x_k \in \partial T} \delta_{x_k} \alpha_k$$
   waarbij $\gamma_j$ en $\alpha_k$ vectorwaardige gewichten zijn in $\Lambda^2(\mathbb{R}^3 \times \mathbb{R}^3)$.

2. Vectorwaardige Inbedding:
   Om standaard compressie-algoritmen toe te passen, mappen de auteurs de ruimte van $\Lambda^2(\mathbb{R}^3 \times \mathbb{R}^3)$-waardige vormen naar een RKHS van $\mathbb{R}^{15}$-waardige functies via een isometrische isomorfisme. Dit maakt het mogelijk om de normale cyclus te behandelen als een generieke discrete functionaal $\mu = \sum \delta_{x_i} \alpha_i$ in een vectorwaardige RKHS duale ruimte.

3. Ridge Leverage Score (RLS) Sampling:
   De kernstap van de compressie maakt gebruik van Ridge Leverage Score (RLS) sampling [24, 25]. In plaats van uniforme subsampling, selecteert het algoritme een kleine subset van $m$ controlepunten ($m \ll n$) uit de originele $n$ Dirac-centra op basis van hun statistische belang (leverage scores). De gewichten van de gecomprimeerde approximatie worden vervolgens berekend via orthogonale projectie. Dit resulteert in een spaarse approximatie $\hat{\mu}$ van omvang $m$.

Belangrijkste Bijdragen

• Eerste Compressie-algoritme voor Normale Cycli: Dit werk presenteert de eerste methode om normale cyclus-representaties te comprimeren, wat de toepassing van de metriek op hoog-resolutie problemen ($M \sim 10^5$) mogelijk maakt.
• Theoretische Garanties: De methode erft theoretische foutgrenzen van [1]. Voor Gaussische RKHS-kernen vervalt de compressiefout exponentieel met het aantal samples $m$:
  $$\|\mu - \hat{\mu}\|_{W^*}^2 \leq O(m \exp(-\alpha m^{1/d}))$$
• Computationele Efficiëntie: Na compressie kan de metriek tussen twee vormen worden berekend in $O(m^2)$ in plaats van $O(M^2)$, met een overeenkomstige reductie in de kosten van gradiëntberekening.
• Expliciete Decompositie: Het artikel biedt een rigoureuze afleiding van de Dirac delta-vorm voor de discrete normale cyclus in de constante normaal kern-setting, waarbij prefactoren uit eerdere literatuur [13] worden gecorrigeerd en verduidelijkt.

Experimentele Resultaten
De auteurs evalueerden het algoritme op grootschalige geometry processing datasets (Cat, Head, Flamingo, Queen, PumpkinHead) met behulp van de PyKeops-bibliotheek voor kerneloperaties.

• Foutverval: Experimenten bevestigden een snelle afname van de RKHS dual-norm fout. Het comprimeren van een oppervlak met ~50.000 driehoeken naar 1.000 Dirac-centra (<0,1% fout) duurde minder dan één seconde. RLS-sampling presteerde consequent beter dan uniforme sampling.
• LDDMM Registratie: De gecomprimeerde metriek werd toegepast op niet-lineaire vormregistratie.
  • Queen Oppervlak (344k centra): Het comprimeren naar 10.000 centra (97% compressie) reduceerde de registratietijd van ~2,7 uur naar ~17 minuten (9–10x versnelling) terwijl de Hausdorff-afstand nauwkeurigheid licht verbeterde ($0,0298$ vs $0,0442$).
  • PumpkinHead Oppervlak (591k centra): Het comprimeren naar 5.000 centra (99% compressie) reduceerde de tijd van ~5,6 uur naar ~17 minuten (20x versnelling) met een verwaarloosbaar verlies in visuele matchkwaliteit ($d_H = 0,1662$ vs $0,1621$).
• Vergelijking met Decimatie: Wanneer vergeleken met quadric edge-collapse decimatie bij een gelijk budget ($m=2.000$), bereikte de RLS-compressie een aanzienlijk lagere dual-norm discrepantie (de werkelijke verloren functie die in LDDMM wordt geminimaliseerd) en een betere gemiddelde Chamfer-afstand. Hoewel decimatie iets beter presteerde op de worst-case Hausdorff-afstand voor vormen met grote gebieden met lage kromming, was de compressiemethode superieur voor het specifieke doel van de registratieverliesfunctie.

Betekenis en Claims
Het artikel claimt dat dit werk de praktische toepassing van normale cyclus-metrieken op grootschalige vormdata mogelijk maakt, een taak die voorheen werd gehinderd door computationele kosten. Door een versnelling van een orde van grootte te bereiken in downstream LDDMM-registratietaken zonder aan nauwkeurigheid in te boeten, maakt de methode hoogwaardige, correspondentievrije vormmatching haalbaar voor complexe, hoog-resolutie anatomische en geometrische data. De auteurs merken op dat het compressieschema al succesvol is ingezet in een begeleidend leer-gebaseerd proces [15] voor gearticuleerde meshes.

Toekomstig werk wordt geïdentificeerd als het uitbreiden van het compressie-algoritme naar lineaire en Gaussische normale kernen om de gevoeligheid voor hogere-orde kromminginformatie verder te vergroten.