Signal- und Bildverarbeitung, 323.014 Image Analysis and Processing Arjan Kuijper 14.12.2006

1/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Signal- und Bildverarbeitung, 323.014

Image Analysis and Processing

Arjan Kuijper

14.12.2006

Johann Radon Institute for Computational and Applied Mathematics (RICAM)

Austrian Academy of Sciences Altenbergerstraße 56A-4040 Linz, Austria

arjan.kuijper@oeaw.ac.at

2/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Last Week

• Normal motion flow is equivalent to the mathematical morphological erosion or dilation with a ball. – The dilation and erosion operators are shown to be

convolution operators with boolean operations on the operands.

– Morphology with a quadratic structuring element links to Gaussian scale space

– There exists a “pseudo-linear” equation linking them.

• The Mumford-Shah functional is designed to generate edges while denoising– Not unique– Complicated

• Active contours / snakes are defined as an energy minimizing splines that are supposed to converge to edges.

3/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Today

• Deep structure in Gaussian Scale Space– Critical points– Movement of critical points– Catastrophe points (singularity theory)

• Annihilations• Creations

– Scale space critical points– Iso-manifolds– Hierarchy– Topological segmentation

4/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Gaussian scale space

Famous quote: “Gaussian scale space doesn’t work because it blurs everything away”

5/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Deep structure

The challenge is to understand the imagereally on all the levels simultaneously,

and not as an unrelated set of derived imagesat different levels of blurring.

Jan Koenderink (1984)

6/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

What to look for

• Gaussian scale space is intensity-based.

• Consider an n - dimensional image, i.e. a (n+1) dimensional Gaussian scale space (Gss) image.

• Investigated intensity-related items.

• “Things” with specialties w.r.t. intensity.– Equal intensities – isophotes, iso-intensity manifolds: L=c

• n - dimensional iso-manifolds in the Gss image• (n-1) - dimensional manifolds in the image.

– Critical intensities – maxima, minima, saddle points: L=0• 0 – dimensional points in the Gss image.

– Critical intensities – maxima, minima, saddle points, .....:• 0 – dimensional critical points in the blurred image,• 1 – dimensional critical curves in the Gss image.

7/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Example image

• Consider a simple 2D image.• In this image, and its blurred

versions we have • Critical points L=0:

– Extrema (green)• Minimum• Maxima

– Saddles (Red)• Isophotes L=0:

– 1-d curves, only intersecting in saddle points

8/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

What happens with these structures?

• Causality: no creation of new level lines

• Outer scale: flat kernel– All level lines disappear– One extremum remains– Extrema and saddles

(dis-)appear pair-wise

• View critical points in scale space: the critical curves.

x

yt

9/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Critical points

• Let L(x,y) describe the image landscape.

• At critical points, TL = (∂xL,∂yL) = (Lx,Ly) = (0,0).

• To determine the type, consider de Hessian matrix

• H = TL(x,y) = ((Lxx , Lxy), (Lxy , Lyy)). – Maximum: H has two negative eigenvalues– Minimum: H has two positive eigenvalues– Saddle: H has a positive and a negative eigenvalue.

10/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

When things disappear

• Generically, det [H] = Lxx Lyy - Lxy Lxy <> = 0, there is no eigenvalue equal to 0.This yields an over-determined system.

• In scale space there is an extra parameter, so an extra possibility: det [H] = 0.

• So, what happens if det [H] = 0? -> Consider the scale space image

11/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Diffusion equation

• We know that Lt = Lxx + Lyy So we can construct polynomials (jets) in scale space.

• Let’s make a Hessian with zero determinant:

• H=((6x,0),(0,2))

• Thus Lxx = 6x, Lyy = 2, Lxy = 0And Lt = 6x +2

• Thus L = x3 + 6xt + y2 + 2t

• Consider the critical curves

12/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Critical Curves

• L = x3 + 6xt + y2 + 2t

• Lx = 3x2 + 6t, Ly = 2y

• For (x,y;t) we have – A minimum at (x,0;-x2/2), or (√-2t,0;t)– A saddle at (-x,0;- x2/2), or (-√-2t,0;t)– A catastrophe point at (0,0;0), an annihilation.

• What about the speed at such a catastrophe?

13/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Speed of critical points

• Higher order derivatives: -L = H x + L t• x = -H-1(L + L t) • Obviously goes wrong at catastrophe points, since then det(H)=0. • The velocity becomes infinite: ∂t (√-2t,0;t)= (-1/√-2t,0;1)

-4 -2 2 4

-2

-1.5

-1

-0.5

0.5

1

14/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Speed of critical points

• Reparametrize t = det(H) x = -H-1(L + L det(H) )• Perfectly defined at catastrophe points • The velocity becomes 0: -H-1(L det(H) v

-3 -2 -1 1 2

-4

-3

-2

-1

15/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

To detect catastrophes

• Do the same trick for the determinant:

• -L = H x + L t-det(H) = det(H) x + det(H) t

• Set M = ((H, L), (det(H), det(H))

• Then if at catastrophes– det[M] < 0 : annihilations– det[M] > 0 : creations

16/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Creations

• Obviously, critical points can also be created.

• This does not violate the causality principle.

• That only excluded new level lines to be created.

• At creations level lines split, think of a camel with two humps.

17/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

To create a creation

• Let’s again make a Hessian with zero determinant:

• H=((6x,0),(0,2+f(x)))

• With f(0)=0.

• Thus Lxx = 6x, Lyy = 2 + f(x), Lxy = 0

• To obtain a path (√2t,0;t) require Lt = -6x +2, so f(x) = -6x.

• Thus L = x3 - 6xt + y2 + 2t -6 x y2

18/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

How does it look like?

-0.2 -0.1 0 0.1 0.2-0.2

-0.1

0

0.1

0.2

19/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

On creations

• For creations the y-direction is needed:

• Creations only occur if D>1.

• Creations can be understood when they are regarded as perturbations of non-generic catastrophes.

• At non-generic catastrophes the Hessian is “more” degenerated: there are more zero eigenvalues and/or they are “more” zero.

20/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Non-generic events

• …non-generic catastrophes are also of interest.

21/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Critical points in scale space

L = 0L = 0

– Scale space critical points are always spatial saddle points.

– Scale space critical points are always saddle points.– Causality: no new level lines implies no extrema in scale

space.– Visualize the intensity of the critical curves as a function

of scale:• the scale space saddles are the local extrema of these

curves. • Extrema (minima/maxima) branches in/de-crease

monotonically.

22/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Example

23/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Scale space saddles

• At a scale space saddle two manifolds intersect

24/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Manifolds in scale space

• Investigate structure through saddles.

25/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Void scale space saddles

-1.5

-1

-0.5

0

-1.5

-1

-0.5

0

00.20.4

0.6

0.8

-1.5

-1

-0.5

0

26/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Hierarchical Algorithm

• Initializing• Build a scale space. • Find the critical points at each scale

level.• Construct the critical branches.• Find the catastrophe points.• Construct and label the critical curves,

including the one remaining extremum.

• Find the scale space saddles.

• Determining the manifolds• Find for each annihilations extremum

its critical iso-intensity manifold.• Construct the dual manifolds.

27/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Hierarchical Algorithm

• Labeling• Assign to each extremum the dual

manifolds to which it belongs, sorted on intensity.

• Build a tree:• Start with the remaining extremum at

the coarsest scale as root.• Trace to finer scale until at some value

it is labeled to a dual manifold.• Split into two branches, on the existing

extremum, one the extremum having the critical manifold.

• Continue for all branches / extrema until all extrema are added to the tree.

D C

SSS

P

28/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Consider the blobs

29/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Results

30/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Results

31/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

The tree

D e5D e3D e1D e2 C e2

C e1C e3

C e5

e4 e2 e1 e3 e5

R demo

32/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

A real example

33/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Find critical curves

Pairs e6-s1, e1-s3, e3-s4, e2-s2

34/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Noise addition

35/35Johann Radon Institute for Computational and Applied Mathematics: www.ricam.oeaw.ac.at

Conclusions

• A scale space approach justifies continuous calculations on discrete grids.

• Structure of the image is hidden in the deep structure of its scale space image.

• Essential keywords are– Critical curves– Singularities– Deep structure– Iso-manifolds