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

[email protected]


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.


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


Gaussian scale space

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


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)


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.


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


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


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.


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


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


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?


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


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


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


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.


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


How does it look like?

-0.2 -0.1 0 0.1 0.2-0.2

-0.1

0

0.1

0.2


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.


Non-generic events

• …non-generic catastrophes are also of interest.


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.


Example


Scale space saddles

• At a scale space saddle two manifolds intersect


Manifolds in scale space

• Investigate structure through saddles.


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


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.


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


Consider the blobs


Results


Results


The tree

D e5D e3D e1D e2 C e2

C e1C e3

C e5

e4 e2 e1 e3 e5

R demo


A real example


Find critical curves

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


Noise addition


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

Documents

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