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

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

Signal- und Bildverarbeitung, 323.014

Image Analysis and Processing

Arjan Kuijper

07.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

• There is a strong analogy between curve evolution and PDE based schemes. They can be related directly to one another.

• Euclidean shortening / Mean Curvature Motion involves the diffusion to be limited to the direction perpendicular to the gradient only.

• The divergence of the flow in the equation is equal to the second order gauge derivative Lvv with respect to v, the direction tangential to the isophote.

• Implementation with Gaussian derivatives may allow larger time steps


Today

• Morphology

• The Mumford – Shah Functional

• Active Contours / Snakes


Mathematical Morphology

• Mathematical morphology is one of the oldest image processing and analysis techniques.

• The original idea is the application of a logical area-operator (called structuring element) on areas of the image in the same way as convolution filters.

• Logical “and” gives erosions, “or” gives dilations

0 0 0 0 0 0 00 0 0 0 0 0 00 0 1 1 1 0 00 0 1 1 1 0 00 0 1 1 1 0 00 0 0 0 0 0 00 0 0 0 0 0 0

,1 1 11 1 11 1 1

0 0 0 0 0 0 00 1 1 1 1 1 00 1 1 1 1 1 00 1 1 1 1 1 00 1 1 1 1 1 00 1 1 1 1 1 00 0 0 0 0 0 0

0 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 0 1 0 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0


• Erosion and dilation of a curve can be considered as a ball rolled over it at the outer and inner borders. The larger structuring element smoothes the curve more. The size of the ball is the scale of the smoothing process.


• The motion of the contour of the image is governed by the structuring element in exactly the same way as the level set is moved in the direction of the normal.

• This is only true for an isotropic convex (i.e. round) structuring element. One also says that the unit gradient vector |L| is the infinitesimal generator for the normal motion evolution equation.

• The sequence of erosion followed by dilation removes small structures selectively from the image:


• The intermediate stepsTop row: three consecutive erosions of the text image. Bottom row: Three consecutive dilations of the eroded image.


Opening / closing

• Closing = erosion of a dilation (org, s=3, s=5)

• Opening = dilation of an erosion (org, s=3, s=5)


• Subtracting the result of the operation of erosion (of the original image) from the result of the operation of dilation (of the original image) gives us the result of the morphological gradient operator:


Mathematical morphology on gray-valued images

• The classical way to change the binary operators from mathematical morphology into operators for gray-valued images, is to replace the binary operators by maximum/minimum operators.

Where B is the structuring element.• Example: original, dilated, and eroded image


Opening / closing

• Similarly opening and closing are defined:


• … as well as the morphological gradient for this image and structuring element as eroded -dilated:


• It can be shown that dilation or erosion with a ball is mathematically equivalent to constant motion flow, where the isophotes are considered as curves and they are moved in the gradient (or opposite) direction.

Ls

L


• A parabolic structuring element establishes an elegant equivalence between mathematical morphology and Gaussian scale-space.– Decomposition– Unique rotationally

symmetric function– Closed w.r.t. convolution

Boomgaard, R.v.d. and Dorst, L. 1997. The morphological equivalent of the Gaussian scale-space. In Gaussian Scale-Space Theory, volume 8 of Computational Imaging and Vision Series, chap. 15, pp. 203–220.

• Mathematical morphology and Gaussian scale-space are cases from a more general formulation:


Vertical: scale = 2k/2, k=0,…,8

Horizontal:

Gaussian scale space.

dilationerosion

• Pseudo-Linear Scale-Space

Theory Florack, Maas and NiessenIJCV 31(2/3), 247-259, 1999


Mumford Shah


Methods of diffusion-reaction type

• Nordström [1990] has suggested to obtain a reconstruction u of a degraded image f by minimizing the energy functional


• The corresponding Euler equations to this energy functional are given by

• Equipped with a homogeneous Neumann boundary condition for u.

• Solving the second equation gives

• This is the PM term !


• So for

the first equation is the steady state of

• This equation can also be obtained directly as the descent method of the functional


• PM with additional bias term• No need to find the PM stopping time• However, now needs to be found• We still have the ill-posedness problem as PM.


Mumford Shah

• Mumford and Shah [1985] have proposed to obtain a segmented image u from f by minimizing the functional

with ≥ 0. The discontinuity set K consists of the edges, and its one dimensional Hausdorff measure |K| gives the total edge length.

• Like the Nordström functional, this expression consists of three cost terms: – the first one is the deviation cost, – the second one gives the stabilizing cost, and – the third one represents the edge cost.


• Numerical complications arise from the fact that the Mumford-Shah functional has numerous local minima.

• Global minimizers such as the simulated annealing method are extremely slow. Hence, one searches for fast (suboptimal) deterministic strategies, e.g. pyramidal region growing algorithms.

• Another interesting class of numerical methods is based on the idea to approximate the discontinuity set K by a smooth function w, which is close to 0 near edges of u and which approximates 1 elsewhere.

• We may for instance study the functional

with a parameter c>0 specifying the ``edge width'‘.


Convergence

• Ambrosio and Tortorelli proved that this functional converges to the Mumford-Shah functional for c -> 0 (in the sense of convergence).

• Minimizing Ff corresponds to the gradient descent equations

with homogeneous Neumann boundary conditions. • As this is very similar to the Nordström process, similar

problems arise: – The functional Ff is not jointly convex in u and v, so it may have

many local minima and a gradient descent algorithm may get trapped in a poor local minimum.

– Well posedness results for this system have not been obtained up to now, but a maximum-minimum principle and a local stability proof have been established.


Examples

From: Inverse problems in Image processing and Image segmentation: some mathematical and numerical aspectsA. ChambolleSchool on Mathematical Problems in Image Processing4 - 22 September 2000, Trieste, Italyhttp://users.ictp.it/~pub_off/lectures/vol2.html


Active Contours / Snakes


Active Contours / Snakes

• A very short introduction

• Exploit the energy formulation

http://www.icaen.uiowa.edu/~dip/LECTURE/Understanding2.html

A Mathematica demo


Summary

• 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.


Next week

• 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

Documents

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