Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction on Polyspheres with

Application to Skeletal Representations
joint work with Stephan Huckemann and Sungkyu Jung

Benjamin Eltzner
University of Göttingen

conference on Geometric Science of Information, 2015-10-30

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction on Manifolds

PCA relies on linearity.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction on Manifolds

PCA relies on linearity.

Tangent space approaches ignore geometry and periodic topology.

Intrinsic approaches rely on manifold geometry.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction on Manifolds

PCA relies on linearity.

Tangent space approaches ignore geometry and periodic topology.

Intrinsic approaches rely on manifold geometry. Two classes:

Forward methods: Submanifold dimension d = 1, 2, 3, . . .

Needs “good” geodesics and a construction scheme.

Backward methods: d = D − 1, D − 2, D − 3, . . .
Needs rich (parametric) set of submanifolds.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Polysphere Dimension Reduction

Almost all geodesics of PD = Srd11 × · · · × SrdKK are dense in (S1 )K .

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Polysphere Dimension Reduction

Almost all geodesics of PD = Srd11 × · · · × SrdKK are dense in (S1 )K .

Low symmetry isom(PD ) = SO(d1 + 1) × · · · × SO(dK + 1), no

generic rich set of submanifolds.
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Deformation for Unit Spheres

Dimension reduction methods exist for spheres: GPCA1 , HPCA2 , PNS3

Recursively deform polysphere to sphere f : PD → SD .

Squared line elements of two unit spheres:
   
d1 k−1 d2 k−1
2
X Y 2 2 2
X Y
ds1 =  sin φ1,j  dφ1,k , ds2 =  sin φ2,j  dφ22,k
2

k=1 j=1 k=1 j=1

Q 
d2
Deformation: ds2 = ds22 + j=1 sin2 φ2,j ds21

1
S. Huckemann and H. Ziezold. Advances in Applied Probability 2.38 (2006), pp. 299–319.
2
S. Sommer. Geometric Science of Information. Vol. 8085. Lecture Notes in Computer Science. 2013, pp. 76–83.
3
S. Jung, I. L. Dryden, and J. S. Marron. Biometrika 99.3 (2012), pp. 551–568.
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Deformation for Unit Spheres

Dimension reduction methods exist for spheres: GPCA1 , HPCA2 , PNS3

Recursively deform polysphere to sphere f : PD → SD .

Squared line elements of two unit spheres:
   
d1 k−1 d2 k−1
2
X Y 2 2 2
X Y
ds1 =  sin φ1,j  dφ1,k , ds2 =  sin φ2,j  dφ22,k
2

k=1 j=1 k=1 j=1

Q 
d2
Deformation: ds2 = ds22 + j=1 sin2 φ2,j ds21

Degrees of freedom: Rotation and ordering of spheres.

1
S. Huckemann and H. Ziezold. Advances in Applied Probability 2.38 (2006), pp. 299–319.
2
S. Sommer. Geometric Science of Information. Vol. 8085. Lecture Notes in Computer Science. 2013, pp. 76–83.
3
S. Jung, I. L. Dryden, and J. S. Marron. Biometrika 99.3 (2012), pp. 551–568.
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Fixing Degrees of Freedom

Rotation:

Embed Srdii into Rdi +1 .

Determine Fréchet mean µ̂i and use rotation along a geodesic to move it
to positive xi,di +1 -direction (north pole).

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Fixing Degrees of Freedom

Rotation:

Embed Srdii into Rdi +1 .

Determine Fréchet mean µ̂i and use rotation along a geodesic to move it
to positive xi,di +1 -direction (north pole).

Ordering:
N
d2 (ψi,n , µ̂i )
P
Data spread: si =
n=1

Choose permutation p such that sp−1 (1) is maximal and sp−1 (K) is minimal.

Minimizes distortion due to factors sin2 φj , i. e. deviation from polysphere

geometry.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Mapping Data Points

Embedding S1di ⊂ Rdi +1 we get
∀1 ≤ j ≤ d2 : yj = x2,j , ∀1 ≤ k ≤ d1 + 1 : yd2 +k = x2,d1 +1 x1,j

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Mapping Data Points

Embedding S1di ⊂ Rdi +1 we get
∀1 ≤ j ≤ d2 : yj = x2,j , ∀1 ≤ k ≤ d1 + 1 : yd2 +k = x2,d1 +1 x1,j

For different radii, rescale

∀1 ≤ j ≤ d1 + 1 : x1,j 7→ x̃1,j = R1 x1,j ,
∀i > 1 ∀1 ≤ j ≤ di : xi,j 7→ x̃i,j = Ri xi,j
and use x̃ in definition of y coordinates.
This yields an ellipsoid
( )
d2
X 1 +1
dX
d2 +d1 +1 −2 2 −2 2
x∈R
e x2,k +
R2 e R1 (e x1,k ) = 1 .
x2,d2 +1e
k=1 k=1
Q  K1
K
Normalize all y-vectors to length R := j=1 Rj as final step.
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Illustration for Different Radii

1. Map from blue

polysphere to
green ellipsoid.
2. Map to red
sphere.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

A Brief Review of Principal Nested Spheres (PNS)

PNS determines a sequence SK ⊃ SK−1 ⊃ · · · ⊃ S2 ⊃ S1 ⊃ {µ}.

Recursively fit small subsphere Sd−1 ⊂ Sd minimizing sum of squared

geodesic projection distances.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

A Brief Review of Principal Nested Spheres (PNS)

PNS determines a sequence SK ⊃ SK−1 ⊃ · · · ⊃ S2 ⊃ S1 ⊃ {µ}.

Recursively fit small subsphere Sd−1 ⊂ Sd minimizing sum of squared

geodesic projection distances.

At every projection, save signed projection distance (residuals).

Parameter space dimension for Sd−1 ⊂ Sd is p = d + 1, compared to

linear PCA where for Rd−1 ⊂ Rd it is p = d.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Skeletal Representation (s-rep) Parameter Space

S-rep consists of

1. A two-dimensional mesh of m × n
skeletal points.

2. Spokes from mesh points to the surface.

Image from: J. Schulz et al. Journal of Computational and Graphical Statistics 24.2 (2015), p. 539
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Skeletal Representation (s-rep) Parameter Space

S-rep consists of

1. A two-dimensional mesh of m × n
skeletal points.

2. Spokes from mesh points to the surface.

Parameters: Size of centered mesh, spoke lengths, normalized

mesh-points, spoke directions:

K
Q = R+ × RK+ × S3mn−1 × S2

K
Polysphere deformation on S3mn−1 × S2 yields

Q0 = S5mn+2m+2n−5

Image from: J. Schulz et al. Journal of Computational and Graphical Statistics 24.2 (2015), p. 539
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction for Real S-reps

PNDS: Deform polysphere to sphere and apply PNS.
CPNS: PNS on spheres individually and linear PCA on joint residuals.

100
PNDS
CPNS
80
Variances [%]

60

40

20

0
0 10 20 30 40 50
Dimension

Figure : PNDS vs. CPNS: residual variances for s-reps of 51 hippocampi5 .

5
S. M. Pizer et al. Ed. by M. Breuß, Bruckstein, and Maragos. Springer, Berlin, 2013, pp. 93–115.
Benjamin Eltzner University of Göttingen
Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Dimension Reduction for Simulated S-reps

component 1 component 1
0.40
variance = 92.02% components 2 and 1 components 3 and 1 0.45
variance = 62.73% components 2 and 1 components 3 and 1
100 100
0.35 0.40 100 100
0.35
0.30
50 50
0.30 50 50
0.25
0.25
0.20 0 0 0 0
0.20
0.15
0.15 −50 −50
−50 −50
0.10
0.10
0.05 0.05 −100 −100
−100 −100
0.00 0.00
−100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100

component 2 component 2
components 1 and 2 1.2
variance = 5.95% components 3 and 2 components 1 and 2 0.5
variance = 32.10% components 3 and 2
100 100
100 100
1.0
0.4
50 50
0.8 50 50
0.3

0 0.6 0 0 0

0.2
0.4 −50 −50
−50 −50
0.1
0.2
−100 −100
−100 −100
0.0 0.0
−100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100

component 3 component 3
components 1 and 3 components 2 and 3 1.8
variance = 0.64% components 1 and 3 components 2 and 3 1.2
variance = 2.17%
100 100
1.6 100 100
1.0
1.4
50 50
1.2 50 50 0.8

1.0
0 0 0 0 0.6
0.8

0.6 −50 −50 0.4

−50 −50
0.4
0.2
0.2 −100 −100
−100 −100
0.0 0.0
−100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100 −100 −50 0 50 100

Figure : PNDS vs. CPNS for simulated twisted ellipsoids: scatter plots of residual
signed distances for the first three components.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Reflection on Parameter Space Dimension

1.0

0.5

0.0

−0.5
Parameter space dimensions:
−1.0
1.0

−1.0
0.5 PNS on SD : p = 12 D(D + 3) − 1.
0.0
−0.5
0.0 −0.5
0.5
PCA on RD : p = 12 D(D + 1).
1.0 −1.0

Figure : Simulated twisted ellipsoid

data projected to the second
component (a small two-sphere) in
PNDS with first component (a small
circle) inside.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations
Introduction Deformation Skeletal Representations Conclusion

Conclusion

We propose a deformation procedure mapping data on a polysphere to

sphere.

The construction aims at minimizing geometric distortion.

We achieve lower dimensional representations than CPNS.

The success of our method is rooted in the higher parameter space

dimension.

Benjamin Eltzner University of Göttingen

Dimension Reduction on Polyspheres with Application to Skeletal Representations