Sparse Randomized Approximation of Normal Cycles

Titolo: Approssimazione Sparse Randomizzata dei Cicli Normali

Autori: Allen Paul, Neill Campbell, Tony Shardlow (Università di Bath, UK).

---

1. Il Problema

Nel campo dell'apprendimento geometrico e dell'anatomia computazionale, è fondamentale costruire modelli statistici per la variazione di forme (es. strutture anatomiche). Per farlo, è necessario disporre di metriche di fedeltà che permettano di confrontare forme senza richiedere una corrispondenza parametrica puntuale (correspondence-less).

• Limiti delle metriche esistenti: Le rappresentazioni basate su currents (correnti) e varifolds sono efficaci per il confronto geometrico ma catturano solo informazioni di primo ordine (vettori tangenti e normali). Non riescono a gestire adeguatamente regioni ad alta curvatura, punti di diramazione o confini distinti, portando spesso a risultati indesiderati durante la registrazione diffeomorfa (LDDMM).
• La soluzione teorica: I Normal Cycles (cicli normali) offrono una rappresentazione arricchita che integra informazioni di curvatura (secondo ordine) e confini, rendendoli ideali per forme complesse. Tuttavia, il calcolo della metrica basata sui cicli normali è computazionalmente proibitivo per dataset su larga scala.
• La sfida computazionale: La complessità del calcolo della metrica tra due superfici triangolate con $M$ e $N$ spigoli è $O(MN)$. Per mesh ad alta risoluzione ($>10^5$ elementi), questo rende l'uso dei cicli normali impraticabile, richiedendo tempi di calcolo e memoria eccessivi rispetto alle alternative (currents/varifolds), anche con librerie ottimizzate come KeOps.

2. Metodologia

Gli autori estendono un algoritmo di compressione randomizzata precedentemente sviluppato per currents e varifolds, adattandolo ai cicli normali. La metodologia si articola in tre fasi principali:

A. Decomposizione in Delta di Dirac

Per applicare tecniche di compressione, è necessario esprimere il ciclo normale come una combinazione lineare di delta di Dirac.

• Gli autori derivano una decomposizione esplicita per cicli normali discreti su superfici triangolate, assumendo un kernel normale costante ($K_s = 1$).
• Il ciclo normale $N(T)$ viene scomposto in componenti ortogonali:
  1. Componente Piana: Si annulla nel caso di kernel costante.
  2. Componente Cilindrica: Associata agli spigoli della mesh. Viene approssimata con delta di Dirac centrati sugli spigoli, con pesi vettoriali derivati dalle normali delle facce adiacenti.
  3. Componente Sferica: Associata ai vertici del confine della superficie. Viene approssimata con delta di Dirac sui vertici di confine.
• Questa decomposizione trasforma il ciclo normale in una somma di delta: $\mu = \sum \delta_{x_i} \alpha_i$, dove $\alpha_i$ sono vettori di peso in uno spazio vettoriale di dimensione $k$ (nel caso di superfici in $\mathbb{R}^3$, $k=15$ dopo un'isomorfismo isometrico).

B. Mappatura in RKHS (Reproducing Kernel Hilbert Space)

Per utilizzare l'algoritmo di compressione, il ciclo normale viene immerso nel duale di uno spazio RKHS ($W^*$).

• Viene definito un kernel spaziale (es. RBF Gaussiano) e un kernel sferico costante.
• Viene costruita un'isomorfismo isometrico che mappa lo spazio dei cicli normali in uno spazio di funzioni a valori vettoriali $\mathbb{R}^{15}$, permettendo l'applicazione di algoritmi di regressione standard.

C. Compressione Randomizzata con Ridge Leverage Score (RLS)

Una volta ottenuta la rappresentazione a delta, viene applicato l'algoritmo di compressione di [1]:

• Campionamento: Si selezionano $m$ punti di controllo ($m \ll n$) dal set originale di $n$ delta, utilizzando il campionamento basato sugli Ridge Leverage Scores (RLS). Questo metodo seleziona i punti più "importanti" per la rappresentazione dello spazio.
• Proiezione: Si calcolano nuovi pesi $\beta_i$ per i punti campionati risolvendo un sistema lineare tramite proiezione ortogonale.
• Risultato: Si ottiene un'approssimazione sparsa $\hat{\mu}$ con $m$ delta, che mantiene la struttura geometrica originale con un errore controllato.

3. Contributi Chiave

1. Primo algoritmo di compressione per Cicli Normali: Questo lavoro presenta il primo metodo per comprimere efficientemente la rappresentazione dei cicli normali, rendendo scalabile questa metrica teorica su dataset di grandi dimensioni.
2. Decomposizione Esplicita: Derivazione di una forma esplicita a delta di Dirac per i cicli normali discreti con kernel normale costante, fondamentale per l'applicazione della compressione.
3. Garanzie Teoriche: L'algoritmo eredita le garanzie di convergenza del lavoro precedente [1]. L'errore di compressione decade esponenzialmente con il numero di punti campionati $m$ (per kernel Gaussiani), garantendo che l'approssimazione sia vicina al ciclo originale nella norma del duale RKHS.
4. Efficienza Computazionale: La complessità del calcolo della metrica e dei gradienti scende da $O(N^2)$ a $O(mn)$ (dove $m \ll n$), permettendo un'accelerazione significativa.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset di geometria moderna (Cat, Head, Flamingo, Queen, PumpkinHead) con risoluzioni fino a 400.000 triangoli (600.000 centri delta).

• Decadimento dell'Errore: L'errore di compressione decresce rapidamente all'aumentare di $m$. Con un campionamento RLS, l'errore è significativamente inferiore rispetto al campionamento uniforme e segue strettamente il limite teorico di traccia. È possibile raggiungere compressioni superiori al 99% con errori relativi trascurabili.
• Registrazione LDDMM (Large Deformation Diffeomorphic Metric Mapping):
  • Qualità: La registrazione di forme utilizzando i cicli normali compressi produce risultati visivamente e metricamente (distanza di Hausdorff) quasi identici a quelli ottenuti con la rappresentazione completa. In alcuni casi, la versione compressa ha mostrato una qualità leggermente superiore (es. errore Hausdorff 0.0298 vs 0.0442 per il caso "Queen").
  • Velocità: L'accelerazione è drastica.
    • Caso "Queen" (compressione 97%): Tempo di calcolo ridotto da 2h 42m a 17m (fattore ~10x).
    • Caso "PumpkinHead" (compressione 99%): Tempo di calcolo ridotto da 5h 37m a 17m (fattore ~20x).
• Scalabilità: Il metodo permette di gestire mesh con risoluzione $N, M \sim 10^5$ in tempi pratici, cosa impossibile con la metrica completa.

5. Significato e Impatto

Questo lavoro colma un divario critico tra la teoria geometrica avanzata (cicli normali) e le applicazioni pratiche su larga scala.

• Abilitazione di Metriche di Alta Ordine: Permette l'uso pratico di metriche che catturano la curvatura e i confini, essenziali per l'analisi di forme biologiche complesse o strutture con dettagli fini.
• Efficienza: Riduce drasticamente il costo computazionale, rendendo fattibile l'uso di cicli normali in pipeline di apprendimento automatico e registrazione medica che richiedono iterazioni rapide.
• Fondazione Futura: Apre la strada all'estensione di queste tecniche a kernel normali lineari e Gaussiani, che potrebbero ulteriormente migliorare la sensibilità alle informazioni di curvatura di ordine superiore.

In sintesi, il paper dimostra che è possibile comprimere rappresentazioni geometriche complesse senza sacrificare la precisione, rendendo le metriche basate sui cicli normali uno strumento pratico per l'analisi di grandi dataset geometrici.