CSE 586, Spring 2011 Advanced Computer Vision Procrustes Shape Analysis

CSE586

CSE 586, Spring 2011

Advanced Computer Vision

Procrustes Shape Analysis

CSE586

Lecture material from Tim Cootes University of Manchester.

For more info, see http://www.isbe.man.ac.uk/~bim/

(includes code for exploring active shape/appearance models).

Credits

lots of slides are due to

CSE586

Statistical Shape Modelling

•  Represent the shape using a set of points

•  Align a set of training examples, and compute a “mean shape”

•  Model distribution of the variation of shapes in the training set wrt the mean shape

•  This allows us to analyze the major “modes”

of shape variation and to generate realistic

new shapes similar to ones in training set

CSE586

Procrustes Analysis

R, t, s

R₁, t₁, s₁

R₂, t₂, s₂

R_m, t_m, s_m

Procrustes Analysis

Align one shape with another

(not symmetric)

General Procrustes Analysis

Align a set of shapes with respect to some unknown “mean” shape (independent of ordering of shapes)

CSE586

Why “Procrustes”?

http://www.procrustes.nl/gif/illustr.gif

CSE586

Aligning Two Shapes

•  Procrustes analysis:

–  Find transformation which minimises

–  T is a particular type of transformation that you want “shape” to be invariant to.

–  Typically a similarity transformation

–  Involves solving for best rotation, translation and scale between the two sets of points [we talked about how to do this in earlier lectures]

2 2

1 ( ) |

| x −T x

CSE586

Steps in Similarity Alignment

Given a set of K points: Configuration

Translation normalization: Centered Configuration (center of mass at origin)

Scale normalization: Pre-shape

(divide by Sqrt of SSQ centered coordinates) Rotation normalization: Shape

(rotate to align with a second normalized shape)

CSE586

Generalized Procrustes Analysis

•  Generalised Procrustes Analysis

–  Find the transformations T_i which minimise

–  Where

–  Under the constraint that

|2

) (

| m −T x_{i i}

∑

) 1 (

i

Ti

n x

m ⁼

∑

1

|

| m =

CSE586

Aligning Shapes : Algorithm

•  Normalise all so center of mass is at origin, and size=1

•  Let

•  Align each shape with m (via a rotation)

•  Re-calculate

•  Normalise m to default location, size, and orientation

•  Repeat until convergence

x1

m =

) 1 (

i

Ti

n x

m ⁼

∑

CSE586

Hand shape model

•  72 points placed around boundary of hand

–  18 hand outlines obtained by thresholding images of hand on a white background

•  Primary landmarks chosen at tips of fingers and joint between fingers

–  Other points placed equally between

1 2 3 4 5 6

CSE586

Labeling Examples

From Stegmann and Gomez

CSE586

Labeling Examples

From Stegmann and Gomez

CSE586

Point Alignment

From Stegmann and Gomez

Training points before and after alignment

CSE586

Hand Shape Model

Samples from training set, after alignment

CSE586

Statistical Shape Analysis

From Stegmann and Gomez

Problem: each point DOES NOT move independently from all the other points. In fact, the movement of points when the shape undergoes a deformation is often highly correlated.

Independent PCA on each data point cluster

CSE586

Statistical Shape Analysis

From Stegmann and Gomez

Model how the entire ensemble of points varies.

We will concatenate all points into a single vector in a high dimensional space. The full hand shape model is then built by computing PCA on all model points collectively, which captures correlations of motion between points.

Will describe how in a moment, but first let’s look at the results.

CSE586

Hand Shape Model

Varying b₁

Varying b₂

Varying b₃

First 3 modes of variation

CSE586

Face Shape Example

Sample face training image

1st mode of variation

CSE586

Shape Space

Consider K landmark points (x_i,y_i) in 2D

Consider each shape as a concatenated vector x, viewed as a point in 2*K dimensional space.

(note: the “shape” really lives in 2K-4 dimensional space, but that is outside the scope of this lecture) We would like a parameterized model that describes the class of shapes we have observed.

CSE586

Shape Space

•  Each observed shape is now a point (vector) x in 2*K dimensional space.

•  The “mean shape” is the center of mass of all these points

x

space shape

CSE586

Shape Models

•  For shape synthesis

–  Parameterised model preferable –  We will use a linear model

–  That is,

x = x + b₁ p₁ + b₂ p₂ + ... + b_m p_m

€

x = x + Pb

CSE586

Principal Component Analysis

•  Matrix X contains each shape as one column

•  Compute eigenvectors of scatter matrix X

X

•  Eigenvectors : main directions

•  Eigenvalue : spread or variation along that direction

p1

p2

λ1

∝ ∝ λ²

CSE586

Shape Space

•  The eigenvectors p1, p2 form a new (rotated) basis set of coordinate axes

•  Each shape x can now be assigned coordinates (b1,b2) according to the eigenvector axes

x

space shape

x = x + b₁ p₁ + b₂ p₂ p₁

p₂

CSE586

Dimensionality Reduction

•  Coordinates often highly correlated

•  Some dimensions account for most of the observed spread (variation) of the data

•  We don’t lose much by approximating the shape using only those dimensions

1 1

b p x

x ≈ +

b1

x

x

p1

CSE586

Dimensionality Reduction

•  Data lies in subspace of reduced dim.

•  However, for some t,

λi

i

t j

b_j ≈ 0 if >

t

) is

of

(Variance b_j λ_j

n nb

b p

p x

x = + _{1 1} +L

...

CSE586

Building Shape Models

•  Given aligned shapes, { }

•  Apply PCA

•  P – First t eigenvectors of covar. matrix

•  b – Shape model parameters = coordinates of shape along eigenvector axes

x

Pb x

x ≈ +

CSE586

Statistical Shape Models

•  Represent likelihood of observing a given shape with a probability distribution

•  Learn p(b) from training set

•  If x multivariate gaussian, then

–  b gaussian with diagonal covariance

•  Or, can use mixture model for p(b) )

(

b

= diag λ ^L λ

S ...

CSE586

Background Information on PCA

•  principal components analysis (PCA) is a technique that can be used to simplify a dataset

•  It is a linear transformation that chooses a new coordinate system for the data set such that

greatest variance by any projection of the data set comes to lie on the first axis (then called the first principal component),

the second greatest variance on the second axis, and so on.

•  PCA can be used for reducing dimensionality by eliminating principal components that have small variance.

CSE586

PCA Toy Example

CSE586

Geometrical Interpretation:

CSE586

Geometrical Interpretation:

CSE586

Principal Component Analysis (PCA)

•  Given a set of points, how do we know if

they can be compressed like in the previous example?

–  The answer is to look into the correlation between the points

–  The tool for doing this is called PCA

CSE586

Principal component in 2d

CSE586

PCA Theorem

CSE586

PCA Theorem

CSE586

PCA Theorem

CSE586

PCA Theorem

CSE586

Using PCA to Compress Data

•  Expressing x in terms of e₁ … e_n has not changed the size of the data

•  However, if the points are highly correlated many of the coordinates of x will be zero or closed to zero.

CSE586

Using PCA to Compress Data

•  Sort the eigenvectors e

according to their

eigenvalue:

CSE586

Example of Approximation

CSE586

Implementing PCA

•  Need to find “first” k eigenvectors of Q:

CSE586

Singular Value Decomposition

(SVD)

CSE586

SVD Properties

CSE586

More about Shape Space

Consider K landmark points (x_i,y_i) in 2D

Dimension of the space of observations is 2*K

But what is dimension of the space of the shapes?

Recall, two point configurations are equivalent (have the same shape) if one can be translated, rotated and scaled into the other.

Thus, each unique “shape” is an equivalence class.

CSE586

Shape Space

The shape space is then the quotient space induced by this equivalence class on the observation space

So shape space has dimension 2*K - 4

This is often called Kendall’s Shape Space.

k

rotation translation scaling

CSE586

Shape Space

For triangles (K=3), Kendall’s shape space can be visualized as a sphere.

For more points, the space is a more complicated manifold (is it a hypersphere?)

Rather than measure variation in shape on the sphere (or higher dimensional nonlinear manifold), it is

common to project points into the tangent plane taken at the mean shape. This is a linear space, so can use PCA, Gaussians, mixture of Gaussians, etc.

CSE586

Shape Space

http://www.york.ac.uk/res/fme/resources/morphologika/helpfiles/shapespace.html

CSE586

Shape Space

Tangent projection can be carried out by subtracting the vector of normalized shape coordinates of a

figure from the mean vector, and taking just the component perpendicular to the mean.

tangent plane

mean shape

nonlinear shape space

shape sample

shape sample projected into tangent plane

CSE586

Shape Space

If shape variation is relatively small, we can just take the shape difference vector as an

approximation to the vector in the tangent plane.

tangent plane

mean shape

nonlinear shape space

shape sample