当前位置:首页 >> 工学 >>

Level


Level Set and PDE Methods for Computer Graphics

Notes for SIGGRAPH 2004 Course #27 Los Angeles, CA August 10, 2004

Organizer
David Breen Drexel University

Speakers
David Breen Ron Fedkiw Ken Museth Stanley Osher Guillermo Sapiro Ross Whitaker Drexel University Stanford University Link?ping University University of California, Los Angeles University of Minnesota University of Utah

Course Abstract
Level set methods, an important class of partial differential equation (PDE) methods, define dynamic surfaces implicitly as the level set (isosurface) of a sampled, evolving nD function. The course begins with preparatory material that introduces the concept of using partial differential equations to solve problems in computer graphics, geometric modeling and computer vision. This will include the structure and behavior of several different types of differential equations, e.g. the level set equation and the heat equation, as well as a general approach to developing PDE-based applications. The second stage of the course will describe the numerical methods and algorithms needed to actually implement the mathematics and methods presented in the first stage. The course closes with detailed presentations on several level set/PDE applications, including image/video inpainting, pattern formation, image/volume processing, 3D shape reconstruction, image/volume segmentation, image/shape morphing, geometric modeling, anisotropic diffusion, and natural phenomena simulation.

Prerequisites
Knowledge of calculus, linear algebra, computer graphics, geometric modeling, image processing and computer vision. Some familiarity with differential geometry, differential equations, numerical computing and image processing is strongly recommended, but not required.

Speaker Biographies
David Breen is an Assistant Professor in the Computer Science Department at Drexel University. He has held research positions at the Center for Advanced Computing Research and the Computer Graphics Lab at the California Institute of Technology, the European Computer-Industry Research Centre, the Fraunhofer Institute for Computer Graphics, and the Rensselaer Design Research Center. His research interests include level set models for computer graphics, volume segmentation, large data

visualization, and geometric modeling. He has published over 50 research papers in these and other areas, as well as the book Cloth Modeling and Animation. Breen received a B.A. in Physics (Colgate University, 1982), and a Ph.D. in Computer and Systems Engineering (Rensselaer Polytechnic Institute, 1993). E-mail: david@cs.drexel.edu Ronald Fedkiw received his Ph.D. in Mathematics from UCLA in 1996 and did postdoctoral studies both at UCLA in Mathematics and at the California Institute of Technology in Aeronautics before joining the Stanford Computer Science Department. He was awarded a Packard Foundation Fellowship, a Presidential Early Career Award for Scientists and Engineers (PECASE), an Office of Naval Research Young Investigator Program Award (ONR YIP), a Robert N. Noyce Family Faculty Scholarship, and two distinguished teaching awards. He is on the editorial board of the Journal of Scientific Computing, IEEE Transactions on Visualization and Computer Graphics, and Communications in Mathematical Sciences, and participates in the reviewing process for a number of journals and funding agencies. He has published over 45 research papers in computational physics, computer graphics and vision, as well as a new book on level set methods. Additionally, he has been a consultant for Industrial Light + Magic for the last three years. E-mail: fedkiw@cs.stanford.edu Ken Museth recently joined the faculty at Link?ping University as a Professor of Computer Graphics. He received his Ph.D. in computational quantum dynamics from the University of Copenhagen in 1997 and came to the California Institute of Technology as a visiting faculty in 1998. While at Caltech he shifted into the computer science field and joined the Computer Graphics Lab as a research scientist in 2000, followed by the Center for Advanced Computing Research in 2002. He has also been a scientific consultant to Digital Domain and NASA's Jet Propulsion Laboratory. His research activities focus on the areas of deforming geometry and level set methods. E-mail: kenmu@itn.liu.se Stanley Osher has been a Professor of Mathematics at UCLA since 1977, where he is the Director of the Applied Mathematics Program and the Director of Special Projects at the Institute for Pure and Applied Mathematics. He is co-inventor of the Level Set Method, TV based image restoration and high resolution nonoscillatory methods (ENO, WENO). He works in the area of scientific computing with applications to many areas,

including image processing, computer vision and graphics. From 1988-95 he was cofounder and co-CEO of Cognitech, Inc. Since 1998 he has been President of Level Set Systems, Inc. He has been both a Fulbright and an Alfred P. Sloan Fellow. He received a NASA Public Service Award, the 2002 Japan Society of Mechanical Engineers Computational Mechanics Award, the 2003 Society of Industrial and Applied Mathematics Pioneer Prize, and is an original ISI Highly Cited Researcher. Osher has coauthored and co-edited two books on Level Set Methods. E-mail: sjo@math.ucla.edu Guillermo Sapiro is a Professor with the Department of Electrical and Computer Engineering at the University of Minnesota. He works on differential geometry and geometric partial differential equations, both in theory and applications in computer vision, computer graphics, and medical imaging. Sapiro has recently written a book in the area and coedited special issues in the IEEE Transactions on Image Processing and the Journal of Visual Communication and Image Representation. He has received the Gutwirth Scholarship for Special Excellence in Graduate Studies, the Ollendorff Fellowship for Excellence in Vision and Image Understanding, the Rothschild Fellowship for Post-Doctoral Studies, the ONR Young Investigator Award, the PECASE Award, and the NSF Career Award. E-mail: guille@ece.umn.edu Ross Whitaker is an Associate Professor in the School of Computing at the University of Utah and is affiliated with the Institute for Scientific Computing and Imaging. He received a B.S. in Electrical Engineering and Computer Science (Princeton University, 1986) and a Ph.D. in Computer Science (University of North Carolina, Chapel Hill, 1993). He was a research staff member at the European Computer-Industry Research Centre, and an Assistant Professor at the University of Tennessee. He teaches and conducts research in computer vision, image processing, medical imaging, and computer graphics/visualization. He has published numerous papers and book chapters on PDE/level set methods for image processing and computer graphics. E- mail: whitaker@cs.utah.edu

Course Schedule
Session 8:30 8:40 9:40 1 - PDE and Level Set Fundamentals Welcome - Breen Introduction to PDEs and Their Application to Imaging - Sapiro Introduction to Level Set Methods - Osher

10:15 Break Session 10:30 11:00 11:25 11:55 2 – Numerical Methods and Applications Dynamic Visibility in an Implicit Framework - Osher Level Set Numerical Methods - Whitaker Level Set Surface Reconstruction and Processing - Whitaker Level Set Methods on a Streaming Architecture - Whitaker

12:15 Lunch Break Session 1:45 2:15 2:45 3:10 3 – PDE/Level Set Applications Image Inpainting - Sapiro Computing Generalized Geodesics for Computer Graphics - Sapiro Algorithms for Level Set Modeling - Museth Level Set Surface Editing Operators - Museth

3:30 Break Session 4 - Level Set Segmentation and Simulation 3:45 3D Volume Segmentation (framework, multiple non-uniform datasets, ???????diffusion tensor MRI, sinograms) - Breen 4:30 Simulation of Water, Fire and Smoke - Fedkiw 5:30 Course Ends

Web Sites
Osher Home Page http://www.math.ucla.edu/~sjo UCLA CAM Technical Reports http://www.math.ucla.edu/applied/cam Level Set Systems, Inc. http://www.levelset.com Sapiro Home Page http://www.ece.umn.edu/users/guille Whitaker Home Page http://www.cs.utah.edu/~whitaker VISPack Web Site http://www.cs.utah.edu/~whitaker/vispack Fedkiw Home Page http://www.graphics.stanford.edu/~fedkiw Museth Home Page http://gg.itn.liu.se Breen - Geometric Modeling and Deformable Models http://www.cs.drexel.edu/~david/geom_mod.html http://www.cs.drexel.edu/~david/deform_mod.html Sethian Home Page http://www.math.berkeley.edu/~sethian

Citations For Included Papers
? ? ? D. Breen, R. Whitaker, K. Museth and L. Zhukov, “Level Set Segmentation of Biological Volume Datasets,” to appear in the Handbook of Medical Image Analysis, 2004. D. Enright, S. Marschner and R. Fedkiw, “Animation and Rendering of Complex Water Surfaces,’’ Proc. SIGGRAPH 2002 Conference, pp. 736-744, July 2002. R. Fedkiw, G. Sapiro, and C.-W. Shu, “Shock Capturing, Level Sets, and PDE Based Methods in Computer Vision and Image Processing: A Review of Osher's Contributions,” Journal of Computational Physics, Vol. 185, No. 2, pp. 309 – 341, March 2003. Also published as UCLA CAM Report # 01-33. N. Foster and R. Fedkiw, “Practical Animation of Liquids,’’ Proc. SIGGRAPH 2001 Conference, pp. 23-30, July 2001. A.E. Lefohn, J.M. Kniss, C.D. Hansen and R.T. Whitaker, “A Streaming NarrowBand Algorithm: Interactive Computation and Visualization of Level Sets,” to appear in IEEE Transactions on Visualization and Computer Graphics, 2004. F. Losasso, F. Gibou and R. Fedkiw, “Simulating Water and Smoke with an Octree Data Structure,” Proc. SIGGRAPH 2004 Conference, August 2004. K. Museth, D.E. Breen, R.T. Whitaker and A.H. Barr, “Level Set Surface Editing Operators,’’ Proc. SIGGRAPH 2002 Conference, pp. 330-338, July 2002. D.Q. Nguyen, R. Fedkiw and H.W. Jensen, “Physically Based Modeling and Animation of Fire,’’ Proc. SIGGRAPH 2002 Conference, pp. 721-728, July 2002. S. Osher and R. Fedkiw, “Level Set Methods: An Overview and Some Recent Results,” Journal of Computational Physics, Vol. 169, pp. 475-502, 2001. Also published as UCLA CAM Report # 00-08. T. Tasdizen, R. Whitaker, P. Burchard and S. Osher, “Geometric Surface Processing via Normal Maps,” ACM Transactions on Graphics, Vol. 22, No. 4, pp. 1012-1033, October 2003. R. Tsai, P. Burchard, L.-T. Cheng, S. Osher and G. Sapiro, “Dynamic Visibility in an Implicit Framework,” UCLA CAM Report # 02-06. H.-K. Zhao, S. Osher and R. Fedkiw, “Fast Surface Reconstruction Using the Level Set Method,” Proc. 1st IEEE Workshop on Variational and Level Set Methods, pp. 194–202, 2001. Also published as UCLA CAM Report # 01-01.

? ? ? ? ? ? ? ? ?

Related Books S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer, New York, 2002. S. Osher and N. Paragios (eds.), Geometric Level Set Methods in Imaging, Vision and Graphics, Springer, New York, 2003. G. Sapiro, Geometric Partial Differential Equations and Image Analysis, Cambridge University Press, 2001. J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999

Table of Contents

Session 1 - PDE and Level Set Fundamentals
PDE’s in Image Processing, Computer Vision, and Computer Graphics (Slides) G. Sapiro Why the World Loves the Level Set Method (and Related) Methods (Slides) S. Osher Level Set Methods: An Overview and Some Recent Results S. Osher and R. Fedkiw Shock Capturing, Level Sets and PDE Based Methods in Computer Vision and ?Image Processing R. Fedkiw, G. Sapiro and C.-W. Shu

Session 2 - Numerical Methods and Applications
Visibility, Its Dynamics, and Related Variational Problems in an Implicit ?Framework (Slides) Y.-H. R. Tsai and S. Osher Dynamic Visibility in an Implicit Framework R. Tsai, P. Burchard, L.-T. Cheng, S. Osher and G. Sapiro Fast Surface Reconstruction Using the Level Set Method H.-K. Zhao, S. Osher and R. Fedkiw Isosurfaces and Level-Set Surface Models R. Whitaker Geometric Surface Processing via Normal Maps T. Tasdizen, R. Whitaker, P. Burchard and S. Osher A Streaming Narrow-Band Algorithm: Interactive Computation and Visualization ?of Level Sets A. Lefohn, J. Kniss, C. Hansen and R. Whitaker

Session 3 – PDE/Level Set Applications
Image Inpainting: An Overview (Slides) G. Sapiro The Art of Distance and Geodesic Computations (Slides) G. Sapiro Distance Functions and Geodesics on Point Clouds (Slides) G. Sapiro Level Set Surface Editing Operators K. Museth, D. Breen, R. Whitaker and A. Barr Algorithms for Interactive Editing of Level Set Models K. Museth, D. Breen, R. Whitaker, S. Mauch and D. Johnson

Session 4 – Level Set Segmentation and Simulation
Level Set Segmentation of Biological Volume Datasets D. Breen, R. Whitaker, K. Museth and L. Zhukov Physically Based Modeling and Animation of Fire D. Nguyen, R. Fedkiw and H. Jensen Practical Animation of Liquids N. Foster and R. Fedkiw Animation and Rendering of Complex Water Surfaces D. Enright, S. Marschner and R. Fedkiw Simulating Water and Smoke with an Octree Data Structure F. Losasso, F. Gibou and R. Fedkiw

Session 1 PDE and Level Set Fundamentals

SIGGRAPH 2002 PDE’s in Image Processing, Computer Vision, and Computer Graphics
Guillermo Sapiro Electrical and Computer Engineering University of Minnesota guille@ece.umn.edu

Moving Curves

Supported by NSF, ONR, NIH
SIGGRAPH 2002
Guillermo Sapiro 1

SIGGRAPH 2002
Guillermo Sapiro

2

Basic curve evolution
Planar curve:
C ( p ) : [0,1] ! R 2

Mathematical morphology
Classical theory, based on Minkowsky addition. The old and (probably wrong) way of doing geometric image analysis. Has very important lessons to learn!!!! Basic definitions:
A: Image in Euclidean space (R or Z) B: Structuring element (symmetric) Nothing else than Minkowsky addition

General flow:

!C = "T + #N !t
General geometric flow:

!C = "N !t
SIGGRAPH 2002
Guillermo Sapiro 3

SIGGRAPH 2002
Guillermo Sapiro

4

Mathematical morphology: Definitions

Mathematical morphology: Is it good or bad?
Advantages:
Nice mathematical properties (set theory) Extension to Lattices

A ! B: = {a + b, a " A, b " B} =  Ab
b"B

Disadvantages:

A!B: = ( A ! B ) =  Ab
c c b"B

Discrete Minkowsky addition does not look good, has to be replaced by better ways of computing “discrete distances.”

Major important concept: Level-sets

f : R N ! R,

g: R N ! {0,"#}

A $ B: = ( A!B ) ! B =

{ y : B y # A}



Ay

f $ g = max { f }
support of g Commutes with thresholding (level-sets): Do binary on each level sets or do gray-level on all the image => same result

A ? B: = ( A ! B )!B
SIGGRAPH 2002
Guillermo Sapiro 5

It is in certain sense a particular case of curve evolution (before the lattices part)
SIGGRAPH 2002
Guillermo Sapiro 6

Mathematical morphology via curve evolution

Mathematical morphology via curve evolution (cont.)
General velocity:

Convex structuring elements B: A ! ( B ! C) = ( A ! B) ! C A ! (rB ) = A ! r1 B ! r2 B !...

! = sup" {r (" ) ! N }
Examples:

!=N ! = max{ N x , N y } ! =| N x |+| N y |
Huygens principle

B = disk B = diamond B = square

Nothing else than changing the metric (distance). Can be explained also based on dynamic programming and time of arrival
See Sapiro et al., Brocket-Maragos, Alvarez et al., Evans, Falcone
7

SIGGRAPH 2002
Guillermo Sapiro

SIGGRAPH 2002
Guillermo Sapiro

8

Planar differential geometry
Euclidean invariant parametrization Affine invariant parametrization

Planar differential geometry (cont.)
Curvature constant for circles or straight lines (=0) Curvature defines curve up to Euclidean motion Curvature constant for ellipses (>0), hyperbolas (<0), and parabolas (=0) Curvature defines curve up to affine motion At least 6 points with dk/ds=0 Defined only for convex curves: segment at inflection points

! C( s ) = 1 !s
< Cs , Css > = 0
Cs ! Css

! C( s ) ! 2 C( s ) = 1 , !s ! s2
Cs , Csss = 0

At least 4 points with dk/ds=0 Defined for all curves

" Cs + Csss = 0 " = Css , Csss
9

" : = Css
SIGGRAPH 2002
Guillermo Sapiro

SIGGRAPH 2002
Guillermo Sapiro

10

Planar differential geometry (cont.)

3D Differential geometry
Remember mean and Gaussian curvatures? Each regular surface has two principal curvatures. The average is the mean curvature, the product the Gaussian. These are also related to the tangential map, etc, etc. See DoCarmo for details.

d ( X , C( s )) : = < X ! C( s) , X ! C( s ) > d ( X , C( s )) : = X ! C( s) , C ( s ) s
X X

C(s)

C(s)

!d = < X ! C , Cs > !s
" ( = 0) X ! C( s ) # Cs ( s ) X ! C( s ) || Css ( s )
SIGGRAPH 2002
Guillermo Sapiro

!d = X ! C( s) , Css ( s) !s
" ( = 0) X ! C( s ) || Css ( s )

Distance has a local extrema iff X is on the normal
11

SIGGRAPH 2002
Guillermo Sapiro

12

Riemannian geometry, Lie theory
What about other non-Euclidean metrics? What about invariants to other (Lie) groups, e.g., projective? What about differential invariants? Semi-differential invariants? Are there any general theories?

Smoothing by classical heat flow

!C = !C !t

"

# x pp & # xt & %y ( = %y ( $ t' % pp ( $ '

Linear Equivalent to Gaussian filtering Unique linear scale-space Non geometric Shrinks the shape Implementation problems

SIGGRAPH 2002
Guillermo Sapiro

13

SIGGRAPH 2002
Guillermo Sapiro

14

Invariant shape deformations
Formulate shape deformations
Geometric Invariant to camera transform The “best” possible Change only the desired features

Basic planar differential geometry
For every Lie group we will consider, exists and invariant parametrization s, the group arc-length

Motivation:
Mathematics:
From static differential geometry to dynamic Beautiful

Computer vision and image processing:
Invariant shape segmentation and analysis Image processing via image deformations

For every such a group exists and invariant signature, the group curvature, k
Low curvature High curvature

Robotics:
Motion planning Accurate geometric object detection and tracking Robot manipulation and grasping
SIGGRAPH 2002
Guillermo Sapiro

Negative curvature
SIGGRAPH 2002
Guillermo Sapiro 16

15

What and why invariant

Euclidean geometric heat flow
Use the Euclidean arc-length: Cs = 1 The deformation:

Camera motion

Deformation

!C !2 C = = "N !t ! s2
Camera/object movement in the space

Transformations description (for “flat” objects):
Euclidean
Motion parallel to the camera and planar projection

Affine
Planar projection

Smoothly deforms to a circle (Gage-Hamilton, Grayson) Geometric smoothing Reduces length as fast as possible

Projective
SIGGRAPH 2002
Guillermo Sapiro 17

SIGGRAPH 2002
Guillermo Sapiro

18

Affine geometric heat flow (Sapiro-Tannenbaum)
Use the affine arc-length: The flow:
Cs ! Css = 1

Affine geometric heat flow (cont.)
Geometric smoothing (preserving area if desired)
Total curvature decreases Maxima of curvature decreases Number of inflections decreases

Css = " 1/ 3 N + f (" ," ) T

!C "Css = # !t $0

non - inflection inflection

Smoothly deforms a shape into an ellipse Decreases area as fast as possible (in an affine form) Existence also for non-smooth curves
Viscosity framework (Alvarez-Guichard-Morel-Lions) Polygons (Angenent-Sapiro-Tannenbaum)

Ct = ! 1/ 3 N

Applications:
Curvature computation for shape recognition: reduce noise (Morel et al.) Simplify curvature computation (Faugeras ‘95) Object recognition for robot manipulation (Cipolla ‘95)
SIGGRAPH 2002
Guillermo Sapiro 20

SIGGRAPH 2002
Guillermo Sapiro

19

General invariant flows
Theorem: For every sub-group of the projective group the most general invariant curve deformation has the form

!C !2 C = f (" ," s ," ss ,...) !t ! s2
Theorem: In general dimensions, the most general invariant flow is given by
ut = g f ( curvatures) E( g )

General Geometric Framework For Object Segmentation

u: graph locally representing the surface g: invariant metric E(g): variational derivative of g

See Olver et al., Alvarez et al., Caselles-Sbert
SIGGRAPH 2002
Guillermo Sapiro 21

SIGGRAPH 2002
Guillermo Sapiro

22

Introduction
Goal: Object detection Approach: Curve/surface deformation
Geometry dependent regularization Image dependent velocity

Notation
Deforming curve:
C ( p ) : [0,1] ! R 2

Characteristics:
Unifies previously considered independent approaches Relates segmentation with anisotropic diffusion General:
Any topology Any type of image data Any dimension

Image:

I : [0,1] " [0,1] ! R

2

(R )

N

Holds formal results

SIGGRAPH 2002
Guillermo Sapiro

23

SIGGRAPH 2002
Guillermo Sapiro

24

Basic active contours approach
Terzopoulos et al., Cohen et al.

Geodesic active contours (Caselles-Kimmel-Sapiro)
2 2

E ( C ) = ! ! C'( p ) dp + " ! C''( p ) dp " ! #I ( C ) dp
Generalize image dependent energy Eliminate high order smoothness term Equal internal and external energies

E ( C ) = ! ! C'( p ) dp + " ! C''( p ) dp " ! #I ( C ) dp
Drawbacks:
Too many parameters Non-geometric Handling topology changes

2

2

E ( C ) = ! C'( p ) dp + ! g[| #I ( C( p ))|] dp
Maupertuis and Fermat principles of dynamical systems

2

E ( C ) = ! g[| #I ( C( s ))|] ds
SIGGRAPH 2002
Guillermo Sapiro 25

SIGGRAPH 2002
Guillermo Sapiro

26

Geodesic computation
Gradient-descent

Further geometric interpretation
The geodesic flow

E(C ) = # ds

!

 !C = "N !t   !C = g " N $ "g % N !t

E(C ) = # g[| "I (C( s ))|] ds
Level-sets (Osher-Sethian)

!

  !C = g"N ! "g # N !t

 ( + gN )

!C = "N !t

!

! ! = " |"!| ! t

SIGGRAPH 2002
Guillermo Sapiro

27

SIGGRAPH 2002
Guillermo Sapiro

28

Model correctness
Theorem: The deformation is independent of the level-sets embedding function Theorem: There is a unique solution to the flow in the viscosity framework Theorem: The curve converges to ideal objects when present in the image
Related work:
Kimia-Tannenbaum-Zucker Caselles et al. Malladi-Sethian-Vemuri Kichenassamy at al. Tek-Kimia, Whitacker

Extensions

E ( C ) = " g[| !I ( C( s ))|] ds
Gray-level values
ds - length element (geodesics) Ordinary edge detector (gradient)

Surfaces
ds - area element (minimal surfaces) 3D edge detector

Vector-valued images (color, texture, medical, etc)
ds - length element Vector-valued edge detector (vector geodesics)
Eigenvalues of the first fundamental form in Riemannian space

New work:
Chan-Vese Paragios-Deriche Yezzi et al. Faugeras et al.
SIGGRAPH 2002
Guillermo Sapiro 29

Invariant detection (affine area geodesics)
ds - affine length element (area related) Affine invariant edge detector Affine norm for “gradient descent”
SIGGRAPH 2002
Guillermo Sapiro 30

Why color edges?

Notation
Image

X : [0, N ]x[0, N ] !  N

L*a*b*

Texture: Gabor decomposition

SIGGRAPH 2002
Guillermo Sapiro

31

SIGGRAPH 2002
Guillermo Sapiro

32

Color edge computation
Given a metric (Euclidean)

# %X = $ %X 2 i i

Compute first fundamental form

[ gij ] = ! X ! ! X !i !j
Compute eigenvectors and eigenvalues Edge: maximal eigenvalue and its eigenvector

Moving Images

(" + ," " ,#+ ,#" )
Basic properties:
Eigenvectors are orthonormal Minimal eigenvalue is not zero
SIGGRAPH 2002
Guillermo Sapiro 33

SIGGRAPH 2002
Guillermo Sapiro

34

Anisotropic diffusion

Isotropic diffusion (Koenderink, Witkin)
All “equivalent:”
Gaussian filtering of the image Heat flow

Isotropic vs. Anisotropic Smoothing

"

! " = $" !t
Minimize the L2 norm

#
Isotropic smoothing Anisotropic smoothing
SIGGRAPH 2002
Guillermo Sapiro 35

!"

2

SIGGRAPH 2002
Guillermo Sapiro

36

Isotropic diffusion: Good things

Isotropic diffusion: Bad things and possible solutions
Non-geometric Problems with implementations

Gaussian filtering if and only if
Linear Shift-invariant No creation of zero crossings

Gaussian filtering if and only if
Linear Shift-invariant Semi-group property Scale-invariant (dimensionless)

Who said linear? Replace heat flow by “parabolic” PDE’s (Hummel’s original idea) Why parabolic? Because of the maximum principle.

Unique linear filter that defines a scale-space: Do not creates information at coarser scales Where everything started (Koenderink, Witkin)

SIGGRAPH 2002
Guillermo Sapiro

37

SIGGRAPH 2002
Guillermo Sapiro

38

Perona-Malik anisotropic diffusion
Replace the L2 by a different norm (e.g., L1, Rudin-OsherFatemi; Lorentzian, Black et. al.; etc)

Selection of “stopping term” h
How do we select h? h=x*x => L2 => linear => Isotropic diffusion h=x => L1 (Rudin-Osher-Fatemi)

!# !! h( "# ) $ ! t =

div' h'( I ) '
&

%

"I "I

( * * )

!# !! ( "# ) $ ! t =

"

SIGGRAPH 2002
Guillermo Sapiro

39

SIGGRAPH 2002
Guillermo Sapiro

40

Robust anisotropic diffusion
General theory for selection “h”, based on the theory of influence functions in robust statistics Edges should be considered outliers: At certain point, h’, the influence, should be zero.

Directional diffusion
Diffuse in the direction perpendicular to the edges (Avarez et al.)

!! = !t

" "! = !
##"!

##

L

SIGGRAPH 2002
Guillermo Sapiro

41

SIGGRAPH 2002
Guillermo Sapiro

42

From active contours to anisotropic diffusion
Replace embedding function in level-sets formulation by image itself

Relation with Perona-Malik anisotropic diffusion

!! = g( I ) " "! + "g (I) # "! !t

!# = g( I ) " !# + !g (I) " !# !t !I = g ( I ) " !I + !g ( I ) " !I !t


!! = !t
"! div& g( I ) &
% $

"I "I
$ %

' ) ) (

Anisotropic diffusion (Alvarez et al.)

Shock-filters (Osher-Rudin)

!! ** h( "! ) + ! t =

div& h'( I ) &

"I "I

' ) ) (

Total variation, Robust estimation Anisotropic diffusion
SIGGRAPH 2002
Guillermo Sapiro 43

SIGGRAPH 2002
Guillermo Sapiro

44

Concluding remarks
Terzopoulos snakes
Terms elimination Geometric interpretation Dynamical systems Level-sets

Curve evolution active contours

Geodesic active contours
Use image as embedding

Anisotropic Diffusion of the Posterior
Mumford-Shah

Geometric diffusion Shock-filters
Add

Self-snakes
Divide by gradient

Perona-Malik flow
Variational interpretation

Total Variation
SIGGRAPH 2002
Guillermo Sapiro

Robust Estimation
45

SIGGRAPH 2002
Guillermo Sapiro

46

ADP in MRI

ADP: Common Techniques

Review: MAP Estimation
3 classes: sulcus, gray matter, white matter Prior probability: Pr(class=C) Posterior probability: Pr(class=C | data) MAP: Choose class C that maximizes posterior: C* = arg max Pr(class=C | data) C Bayes’ Rule: Pr(class=C | data) = Pr(data | class=C).Pr(class=C) Pr(data) What is our prior, Pr(class=C)?
SIGGRAPH 2002
Guillermo Sapiro 47

MAP Estimation: Uniform Prior

Classification

SIGGRAPH 2002
Guillermo Sapiro

48

ADP: Results

ADP: Comparisons

Anisotropic smoothing of posterior (Teo-Sapiro-Wandell)
Posterior Smoothed Posterior Classification

Comparison with manual segmentation

Automatic (2 min)

MR Image

Manual (18 hours)

SIGGRAPH 2002
Guillermo Sapiro

49

SIGGRAPH 2002
Guillermo Sapiro

50

SAR segmentation via vector probability processing

Anisotropic Diffusion in Vector Space

With A. Pardo (see also Haker-Sapiro-Tannenbaum)
SIGGRAPH 2002
Guillermo Sapiro 51

SIGGRAPH 2002
Guillermo Sapiro

52

Goal and approach (Ringach-Sapiro)

Notation
Image

Goal:
Enhancement of vector valued data Extend classical theories of scalar PDE’s in image processing

X : [0, N ]x[0, N ] !  N

Approach:
Work in vector space Compute vector edges Anisotropic diffusion

L*a*b*

Important: Works for any vector data Texture: Gabor decomposition See also: Cumani, Di Zenzo, Chambolle

SIGGRAPH 2002
Guillermo Sapiro

53

SIGGRAPH 2002
Guillermo Sapiro

54

Color edge computation
Given a metric (Euclidean)

Color anisotropic diffusion

# %X = $ %X 2 i i

Direction: Minimal change Strength: g(" ," ! )

(!! )

Compute first fundamental form

+

[ gij ] = ! X ! ! X !i !j
Compute eigenvectors and eigenvalues Edge: maximal eigenvalue and its eigenvector

# X = g(" , " ) # 2 X + _ #! 2 #t !

(" + ," " ,#+ ,#" )
Basic properties:
Eigenvectors are orthonormal Minimal eigenvalue is not zero
SIGGRAPH 2002
Guillermo Sapiro 55

SIGGRAPH 2002
Guillermo Sapiro

56

Level lines for vectorial images (Chung-Sapiro)

Contrast Enhancement (Sapiro-Caselles, and Caselles-Lisani-Morel-Sapiro)
Contrast enhancement via image deformations
Approach: Histogram modification

! I ( x, y) = I ( x, y) ! (# pixels of value " I ( x, y) ) !t
U(I) =
1 2

#

[ I ( x ) ! 1 / 2]2 d x !

1 4

##

[ I ( x ) ! I ( z )] d x d z

Characteristics:

Vector and scalar representation sharing level-lines

Simultaneous contrast enhancement and denoising First explanation of histogram modification in image domain Extended to local First semi-global partial differential equation in image processing Formal existence results
SIGGRAPH 2002
Guillermo Sapiro 58

SIGGRAPH 2002
Guillermo Sapiro

57

The main problem and our goal (Tang-Sapiro-Caselles)
Goal: Enhancement and analysis of directional data (and data on non-flat manifolds) Problem: Directions are unit vectors:

Beyond the flat manifolds

Regular images vs Directions

I: R ! R
Applications:

2

N

vs

I: R ! S

2

N "1

Optical flow, Gradients Vector data (normalized) Color image enhancement Surface normals and principal directions Flows in general manifolds

SIGGRAPH 2002
Guillermo Sapiro

59

SIGGRAPH 2002
Guillermo Sapiro

60

Average

Most popular previous approaches
Work with angles: Operations on the sphere
Average, median, etc Statistics of directional data, Mardia “Orientation Diffusion,” Perona (1998)

Tensor diffusion
Weickert, Granlund-Knuttson

See also Chan-Shen
SIGGRAPH 2002
Guillermo Sapiro 61

SIGGRAPH 2002
Guillermo Sapiro

62

Anisotropic Diffusion

What have we learned from images?

Robust Estimation:min I " !(|!I |)d#
#
Isotropic (Heat equation) Anisotropic

*
"t

Robust function
$ & & & & & & % ' ) ) ) ) ) ) (

Gradient Descent: " I ( x, y,t ) = div !' !I

g := !' |!I |

*

|!I |

Influence function (defines outliers)

! I ( x, y,t ) = !I !t
SIGGRAPH 2002
Guillermo Sapiro

! I ( x, y,t ) = div( g(|"I |)"I ) !t
63

Anisotropic Diffusion:
SIGGRAPH 2002
Guillermo Sapiro

" I ( x, y,t ) = div( g(|!I |)!I ) "t
64

Anisotropic Diffusion

Back to Directions: Basic Idea
Use the theory of harmonic maps
Find a map I from two manifolds (M,g) and (N,h) such that

Isotropic (Heat equation)

Anisotropic

min I : M ! N

In particular, liquid crystals:

$

#"

M

I

p

dvol M

min
! I ( x, y,t ) = !I !t
SIGGRAPH 2002
Guillermo Sapiro

! I ( x, y,t ) = div( g(|"I |)"I ) !t
65

I :R ! S

2

n %1

$

#"I
66

p

dx dy

SIGGRAPH 2002
Guillermo Sapiro

The Gradient-Descent Equations

A Few Theoretical Results (over hundreds relevant)
For 2D unit vectors (n=1), and p=2, a unique solution exists and singularities are isolated points (if they exists at all). For smooth data, singularities do not occur. Singularities occur for 3D unit vectors (p=2). Singularities well characterized for 1<p<=2. Energy well characterized for 1<p<=2.

* H Q H U D O S  

!I = # M I + AN ( I ) < ! M I , ! M I > !t
/ LTX LG  F U \ V W D OV 

!I = div ( !I !t

p"2

!I ) + I !I

p

No singularities for manifolds with non-positive curvature.

SIGGRAPH 2002
Guillermo Sapiro

67

SIGGRAPH 2002
Guillermo Sapiro

68

Intermezzo: Visualizing Directions
Arrows Color Map Line Integral Convolution

Examples (Isotropic)

!
SIGGRAPH 2002
Guillermo Sapiro 69

=

SIGGRAPH 2002
Guillermo Sapiro

70

3D vector (Isotropic)

Denoising

SIGGRAPH 2002
Guillermo Sapiro

71

SIGGRAPH 2002
Guillermo Sapiro

72

SIGGRAPH 2002
Guillermo Sapiro

73

SIGGRAPH 2002
Guillermo Sapiro

74

Optical flow

Optical flow (cont.)

SIGGRAPH 2002
Guillermo Sapiro

75

SIGGRAPH 2002
Guillermo Sapiro

76

Gradient

Gradient (cont.)

SIGGRAPH 2002
Guillermo Sapiro

77

SIGGRAPH 2002
Guillermo Sapiro

78

Color Image Enhancement

Color image enhancement (cont.)

SIGGRAPH 2002
Guillermo Sapiro

79

SIGGRAPH 2002
Guillermo Sapiro

80

Color image enhancement (cont.)

Vector probability diffusion (with Alvaro Pardo)
Perform diffusion on the hyperplane representing probabilities

min I :R 2 #Hn

"

!$I

p

dx dy

! I = % M I + AN ( I ) < $ M I , $ M I > !t ! I p&2 = div( $I $I ) !t
SIGGRAPH 2002
Guillermo Sapiro 81

SIGGRAPH 2002
Guillermo Sapiro

82

Vector probability diffusion (cont.)
The numerical implementation also stays on the hyperplane The numerical implementation also holds a maximum and minimum principle

Vector probability diffusion (cont.)
Diffuse posterior probabilities (following Teo-Sapiro-Wandell
and Haker-Sapiro-Tannenbaum)

SIGGRAPH 2002
Guillermo Sapiro

83

SIGGRAPH 2002
Guillermo Sapiro

84

WHY THE WORLD LOVES THE LEVEL SET METHOD (AND RELATED) METHODS Stan Osher
Mathematics Department UCLA sjo@math.ucla.edu
and

Google: “Level Set Methods”



8200 responses

(September 17, 2003) Osher-Sethian original paper (1988) Now cited

Level Set Systems, Inc. 1058 Embury St. Pacific Palisades, CA 90272-2501 sjo@levelset.com



720 times (web-of-science)

ICCV (2003) Nice

New Book

S. Osher & R.P. Fedkiw
Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag It’s out!! Also S. Osher & N. Paragios (Eds) Geometric Level Set Methods in Imaging, Vision & Graphics Springer-Verlag (2003) Also Course at SIGGRAPH (2002) San Antonio, July 2002

Given an interface in Rn, call it Γ, of codimension one,

r r v = v ( x, geometry, external physics)
O & Sethian (1987)

r v

r r v =v

Also: Unreferenced papers by Move it normal to itself under velocity

r v

Dervieux, Thomassett, (1979, 1980). Some of the key ideas in obscure proceedings.

1

Trivial fact Zero level contour

φ ( x, t ) = 0 d φ ( x(t ), t ) = 0 dt r r ? t + v ? ?? = 0
Normal to Γ : n =
r r ?? | ?? |

r ? t + vn | ?? |= 0 r r ?? vn = v ? r | ?? |

Phase field e.g. Merging is difficult 3D is difficult Reparametrization needed Advect χ(x) ≡ 1 if x ε Ω ≡ 0 outside + Merging ok -- Spurious discontinuity -- Hard to compute curvature. Mean Curvature

ut = Δu ?

1 fu ε

get curvature interface O(ε) width

But Δx < ε, otherwise (Thm: MBO, phase field gives the wrong answer) Need adaptive grid, NO ε in our approach.

(1) Reinitialize ? → signed distance to Γ (SSO). (2) vn → extends smoothly off of Γ (CMOS). (3) Local level set (near interface) |?| < ε.

Easy to implement Near boundary singularities, 2 or 3D.

2

Also
? ?? ? r ? ? vn ( n ) = γ ? ? ? | ?? | ? ? ?? ? ? t + | ?? | γ ? ? | ?? | ? ?=0 ? ? r vn = vn (n ),

Theoretical Justification Viscosity solutions for scalar 2 nd order (or 1 st order) Evolution eqns. Motion by mean curvature e.g.

High order accurate ENO schemes for HJ equations (Kinks develop) [OSe] [OSh]

? t =| ?? | ? ?

?? | ?? |

ESS showed same as classical limit

Level Set Dictionary 1.

1 ut = Δu ? f u ε
f=

Γ(t ){ x | ? ( x, t ) = 0} Ω(t )bdd by Γ(t ) Ω(t ) = { x | ? ( x, t ) < 0}
Unit normal

2.

r r ?? n=+ r | ?? |

as ε ↓ 0 Got e.g. motion of square by mean curvature.

3.

Mean curvature

r ? ?? ? r ? κ = ? ?? ?|? ? ? ? |?

4. Delta function on an interface

7. Volume integral of p(x,t ) over Ω

δ (? ) | ?? |
5. Characteristic function χ of Ω(t)
χ = H (?? ) H ( x) ≡ 1 if H ( x) ≡ 0 if

∫ p( x, t ) H (?? )dx
8. Distance reinitialization d(x,t) = signed distance to nearest point on Γ
x>0 x<0

6. Surface integral of p(x,t) over Γ

| ?d |= 1 d < 0 in Ω, d = 0 on Γ ?ψ + sign? (| ?ψ | ?1) = 0 ?τ

d >0

in

Ωc

Rn

∫ p( x, t )δ (? ) | ?? | dx

as τ↑ ψ → d very fast near d = 0.

3

9. Smooth extension of a quantity e.g. vn on Γ, off of Γ. Let vn = p (x,t)
? ?? ? ?q + (sign? )? ? | ?? | ? ?q ? ?=0 ?τ ? ? q ( x,0) = p ( x, t )

11. Fast marching method: Tsitsiklis (1993) Rediscovered by (1995): Helmsen P.C.D.,…, & Sethian

r ? t + vn ( x ) | ?? |= 0 vn > 0

very fast near d = 0. 10. Local level set method. Solve PDE within 6Δx or so of d = 0.

For more complicated Hamiltonians Use heap-sort, Godunov’s Hamiltonian (upwind, viscosity soln) Solve in O(N log N) (First order accurate), jazzed up hyperbolic space Marching. For this problem, probably fastest. Although local level set more general & accurate. Sweep in pre-ordained directions. Converges rapidly. No heap sort. No large search and initialization regions. Zhao: “convergence theorem” in special cases. Now, with Kao, Jiang & O, can do a very simple sweeping method in very general cases.

r r H ( x , ?? ) = c ( x ) > 0
H convex in grad phi Can do a simple local update Formula of Tsai, et. al. (2001)
0 0

0x0

using a new

4

Level Set Methods: An Overview and Some Recent Results
Stanley Osher ? Ronald P. Fedkiw September 5, 2000
?

?

Abstract The level set method was devised by Osher and Sethian in [64] as a simple and versatile method for computing and analyzing the motion of an interface Γ in two or three dimensions. Γ bounds a (possibly multiply connected) region ?. The goal is to compute and analyze the subsequent motion of Γ under a velocity ?eld v . This velocity can depend on position, time, the geometry of the interface and the external physics. The interface is captured for later time as the zero level set of a smooth (at least Lipschitz continuous) function ?(x, t), i.e., Γ(t) = {x|?(x, t) = 0}. ? is positive inside ?, negative outside ? and is zero on Γ(t). Topological merging and breaking are well de?ned and easily performed. In this review article we discuss recent variants and extensions, including the motion of curves in three dimensions, the Dynamic Surface Extension method, fast methods for steady state problems, di?usion generated motion and the variational level set approach. We also give a user’s guide to the level set dictionary and technology, couple the method to a wide variety of problems involving external physics, such as compressible and incompressible (possibly reacting) ?ow, Stefan problems, kinetic crystal growth, epitaxial growth of thin ?lms,
Research supported in part by ONR N00014-97-1-0027, DARPA/NSF VIP grant NSF DMS9615854, AFOSR FQ8671-9801346, NSF DMS 9706827 and ARO DAAG 55-98-10323. ? Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095 ? Computer Science Department, Stanford University, Stanford, California 94305.
?

1

vortex dominated ?ows and extensions to multiphase motion. We conclude with a discussion of applications to computer vision and image processing.

2

1

Introduction

The original idea behind the level set method was a simple one. Given an interface Γ in Rn of codimension one, bounding a (perhaps multiply connected) open region ?, we wish to analyze and compute its subsequent motion under a velocity ?eld v . This velocity can depend on position, time, the geometry of the interface (e.g. its normal or its mean curvature) and the external physics. The idea, as devised in 1987 by S. Osher and J.A. Sethian [64] is merely to de?ne a smooth (at least Lipschitz continuous) function ?(x, t), that represents the interface as the set where ?(x, t) = 0. Here x = x(x1 , . . . , xn ) ε Rn . The level set function ? has the following properties ?(x, t) > 0 for x ∈ ? ? ?(x, t) < 0 for x ∈ ? ?(x, t) = 0 for x ∈ ? ? = Γ(t) Thus, the interface is to be captured for all later time, by merely locating the set Γ(t) for which ? vanishes. This deceptively trivial statement is of great signi?cance for numerical computation, primarily because topological changes such as breaking and merging are well de?ned and performed “without emotional involvement”. The motion is analyzed by convecting the ? values (levels) with the velocity ?eld v . This elementary equation is ?? + v · ?? = 0. ?t (1)

Here v is the desired velocity on the interface, and is arbitrary elsewhere. ?? Actually, only the normal component of v is needed: vN = v · |? ?| , so (1) becomes ?? + vN |??| = 0. (2) ?t In section 3 we give simple and computationally fast prescriptions for reinitializing the function ? to be signed distance to Γ, at least near the boundary [84], smoothly extending the velocity ?eld vN o? of the front Γ [24] and solving equation (2) only locally near the interface Γ, thus lowering the complexity of this calculation by an order of magnitude [66]. This makes the cost of level set methods competitive with boundary integral methods, in cases when the latter are applicable, e.g. see [42]. 3

We emphasize that all this is easy to implement in the presence of boundary singularities, topological changes, and in 2 or 3 dimensions. Moreover, in the case which vN is a function of the direction of the unit normal (as in kinetic crystal growth [62], and Uniform Density Island Dynamics [15], [36]) then equation (2) becomes the ?rst order Hamilton-Jacobi equation ?? + |??|γ N = 0 ?t (3)

?? where γ = γ (N ) a given function of the normal, N = |? ?| . High order accurate, essentially non-oscillatory discretizations to general Hamilton-Jacobi equations including (3) were obtained in [64], see also [65] and [43]. Theoretical justi?cation of this method for geometric based motion came through the theory of viscosity solutions for scalar time dependent partial di?erential equations [23], [30]. The notion of viscosity solution (see e.g. [8, 27]) – which applies to a very wide class of these equations, including those derived from geometric based motions – enables users to have con?dence that their computer simulations give accurate, unique solutions. A particularly interesting result is in [29] where motion by mean curvature, as de?ned by Osher and Sethian in [64], is shown to be essentially the same motion as is obtained from the asymptotics in the phase ?eld reaction di?usion equation. The motion in the level set method involves no super?uous sti?ness as is required in phase ?eld models. As was proven in [53], this sti?ness due to a singular perturbation involving a small parameter will lead to incorrect answers as in [48], without the use of adaptive grids [59]. This is not an issue in the level set approach. The outline of this paper is as follows: In section 2 we present recent variants, extensions and a rather interesting selection of related fast numerical methods. This section might be skipped at ?rst, especially by newcomers to this subject. Section 3 contains the key de?nitions and basic level set technology, as well as a few words about the numerical implementation. Section 4 describes applications in which the moving interfaces are coupled to external physics. Section 5 concerns the variational level set approach with applications to multiphase (as opposed to two phase) problems. Section 6 gives a very brief introduction to the ever-increasing use of level set method and related methods in image analysis.

4

2
2.1

Recent Variants, Extensions and Related Fast Methods
Motion of Curves in Three Spatial Dimensions

In this section we discuss several new and related techniques and fast numerical methods for a class of Hamilton-Jacobi equations. These are all relatively recent developments and less experienced readers might skip this section at ?rst. As mentioned above, the level set method was originally developed for curves in R2 and surfaces in R3 . Attempts have been made to modify it to handle objects of high codimension. Ambrosio and Soner [5] were interested in moving a curve in R3 by curvature. They used the squared distance to the curve as the level set function, thus ?xing the curve as the zero level set, and evolved the curve by solving a PDE for the level set function. The main problem with this approach is that one of the most signi?cant advantages of level set method, the ability to easily handle merging and pinching, does not carry over. A phenomenon called “thickening” emerges, where the curve develops an interior. Attempts have also been made in other directions, front tracking, e.g. see [41]. This is where the curve is parameterized and then numerically represented by discrete points. The problem with this approach lies in ?nding when merging and pinching will occur and in reparameterizing the curve when it does. The representation we derived in [13] makes use of two level set functions to model a curve in R3 , an approach Ambrosio and Soner also suggested but did not pursue because the theoretical aspects become very di?cult. In this formulation, a curve is represented by the intersection between the zero level sets of two level set functions φ and ψ, i.e., where φ = ψ = 0. From this, many properties of the curve can be derived such ?ψ×?φ as the tangent vectors, T = |? ψ×?φ| , the curvature vectors, κN = ?T · T , and even the torsion, τ N = ??B · T , where N and B are the normal and binormal respectively. Motions of the curve can then be studied under the appropriate system of PDE’s involving the two level set functions. The velocity can depend on external physics, as well as on the geometry of the curve (as in the standard level set approach). The resulting system of PDE’s for ψ and φ is φt = ?v · ?φ ψt = ?v · ?ψ 5

A simple example involves moving the curve according to its curvature vectors, for which v = κN . We have shown that this system can also be obtained by applying a gradient descent algorithm minimizing the length of the curve, L(φ, ψ) =
R3

|?ψ × ?φ|δ(ψ)δ(φ)dx.

This follows the general procedure derived in [88] for the variational level set method for codimension one motion, also described in [90]. Numerical simulations performed in [13] on this system of PDE’s, and shown in ?gures 1 and 2, show that merging and pinching o? are handled automatically and follow curve shortening principles. We repeat the observation made above that makes this sort of motion easily accessible to this vector valued level set method. Namely all geometric properties of a curve Γ which is expressed as the zero level set of the vector equation φ(x, y, z, t) = 0 ψ(x, y, z, t) = 0 can easily be obtained numerically by computing discrete gradients and higher derivatives of the functions φ and ψ restricted to their common zero level set. This method will be used to simulate the dynamics of defect lines as they arise in heteroepitaxy of non-lattice notched materials, see [79] and [80] for Lagrangian calculations. An interesting variant of the level set method for geometry based motion was introduced in [53] as di?usion generated motion, and has now been generalized to forms known as convolution generated motion or threshold dynamics. This method splits the reaction di?usion approach into two highly simpli?ed steps. Remarkably, a vector valued generalization of this approach, as in the vector valued level set method described above gives an alternative approach [74] to easily compute the motion (and merging) of curves moving normal to themselves in three dimensions with velocity equal to their curvature.

2.2

Dynamic Surface Extension (DSE)

Another ?xed grid method for capturing the motion of self-intersecting interfaces was obtained in [73]. This is a ?xed grid, interface capturing formulation based on the Dynamic Surface Extension (DSE) method of Steinho? 6

et. al. [82]. The latter method was devised as an alternative to the level set method of Osher and Sethian [64] which is needed to evolve wavefronts according to geometric optics. The problem is that the wavefronts in this case are supposed to pass through each other – not merge as in the viscosity solution case. Ray-tracing can be used but the markers tend to diverge which leads to loss of resolution and aliasing. The original (ingenious) DSE method was not well suited to certain fundamental self intersection problems such as formation of swallowtails. In [73] we extended the basic DSE scheme to handle this fundamental problem, as well as all other complex intersections. The method is designed to track moving sets Γ of points of arbitrary (perhaps changing) codimension, moreover there is no concept of “inside” or “outside”. The method is, in some sense, dual to the level set method. In the latter, the distance representation is constant tangential to a surface. In the DSE method, the closest point to a surface is constant in directions orthogonal to the surface. The version of DSE presented in [73] can be described as follows: For each point in Rn , set the tracked pointed T P (x) equal to CP (x) the closest point (to x) on the initial surface Γ0 . Set N equal to the surface normal at the tracked point T P (x). Let v (T P (x)) be the velocity of the tracked point. Repeat for all steps: (1) Evolve the tracked point T P (x) according to the local dynamics T P (x)t = v (T P (x)). (2) Extend the surface representation by resetting each tracked point T P (x) equal to the true closest point CP (x) on the updated surface Γ, where Γ is de?ned to be the locus of all tracked points, i.e. Γ = {T P (x)|x ε Rn }. Replace each N (x) by the normal at the updated T P (x). This method treats self intersection by letting moving sets pass through each other. This is one of its main virtues in the ray tracing case. However, it has other virtues – namely the generality of the moving set – curves can end or change dimension. An important extension is motivated by considering ?rst arrival times. This enables us to easily compute swallowtails, for example, and other singular points. We actually use a combination of distance and direction of

7

motion. One interesting choice arises when nodal values of T P (x) are set equal to the “Minimizing Point” M P (x) =
y ε

β |(x ? y) · N ⊥ (y )| + x ? y min Interface

2

for β > 0 (rather than CP (x)), since a good agreement with the minimal arrival time representation is found near the surface. Recall that the minimal arrival time at a point x is the shortest time it takes a ray emanating from the surface to reach x. Using this idea gives a very uniform approximation and naturally treats the prototype swallowtail problem. For the special case of curvature dependent motion we may use an elegant observation of DeGiorgi [28]. Namely the vector mean curvature for a surface 2 where κ is the local of arbitrary codimension is given by κN = ??? d 2 mean curvature and d is the distance to the surface. Using the elementary, but basic fact that d?d = x ? CP (x) where CP (x) is the closest point to x on the surface, we obtain a very simple expression for vector mean curvature κN = ??(x ? CP (x)) = ?CP (x). Thus motion by a function F , of mean curvature for surfaces of arbitrary codimension can be achieved by using v (T P (x)) = ?CP (x). Then curvature dependent velocities are possible by using v = F (?CP (x)|T P (x) · N )N . where numerical experiments in [73] have validated these algorithms to some degree. A variety of interesting topics for future research is still open. In particular, adjustments need to be made if merging is desired. Moreover we can move objects with more complex topology and geometry, such as surfaces with boundaries (or curves with endpoints), objects of composite topology (such as a ?lament attached to a sheet) and surfaces on curves with triple point junctions (see [88], [53] and section 5 of this paper for successful level set based and di?usion generated based approaches for the codimension one case respectively). Further work in the area of curvature dependent motions is also possible. Computationally the construction of fast extension methods and localization 8

as in [66] for the level set method would be of great practical importance. It would be particularly interesting to determine if surfaces fatten (or develop interiors) when mergers occur. See [9] for a detailed discussion of this phenomenon. Additionally in [73] we successfully calculated a geometric optics expansion by retaining the wave front curvature. Thus this method has the possibility of being quite useful in electromagnetic calculations. We hope to investigate its three dimensional performance and include the e?ects of di?raction.

2.3

A Class of Fast Hamilton-Jacobi Solvers

Another important set of numerical algorithms involves the fast solution of steady (time independent) Hamilton-Jacobi equations. We also seek methods which are faster than the globally de?ned schemes originally used to solve equation 2. The level set method of Osher and Sethian [64] for time dependent problems can be localized. This means that the problem ?t + v · ?? = 0 with Γ(t) = {x|?(x, t) = 0} as the evolving front, can be solved locally near Γ(t). Several algorithms exist for doing this, see [66] and [2]. These both report an O(N ) algorithm where N is the total number of grid points on or near the front. However, the algorithm in [66] has O(N log(N )) complexity because a partial di?erential equation based reinitialization step requires log( 1x ) ≈ log(N ) steps to converge (we are grateful to Bjorn Engquist for pointing this out). The algorithm in [2] claims O(N ) complexity, but this is not borne out by the numerical evidence presented there. However for some special Hamilton-Jacobi equations there is a fast method whose formal complexity is O(N log(N )), but which, in our experience, is around one order of magnitude faster than these general local methods. The idea is as follows: For an equation of the form ? (x, ?ψ) = 0, H give ψ = 0 on a non characteristic set S : ? ?ψ = 0 ?ψ · H

9

then we proved in [63] that the t level set {x|ψ(x) = t} = Γ (t) is the same as the zero level set Γ(t) of ?(x, t), for t > 0 where ? satis?es ? x, ? ?? H ?t = 0.

This means that the viscosity solutions of either problem have level sets which correspond to each other. (This was also suggested in the original level set paper of Osher and Sethian [64]). Thus, one would like to ?nd Γ(t), the zero level set of ?(x, t), as Γ (t), the t level set of ψ(x). A canonical example is the eikonal equation ?t + c(x)|??| = 0, c(x) < 0 which can be replaced by: |?ψ| = ? 1 = a(x) > 0. c(x)

So we ?nd ?rst arrival times instead of zero level sets. In [86] J.N. Tsitsiklis devised a fast algorithm for the eikonal equation. He obtained the viscosity solution using ideas involving Dijkstra’s algorithm, adapted to the eikonal equation, heap sort and control theory. From a numerical PDE point of view, however, Tsitsiklis had an apparently nonstandard approximation to |?ψ| on a uniform Cartesian grid. In (1995) Sethian [76] and Helmsen et. al. [40] independently published what appeared to be a simpler algorithm making use of the Rouy-Tourin algorithm to approximate |??|. This has become known as the “fast marching method”. However, together with Helmsen [61] we have proven that Tsitsiklis’ approximation is the usual Rouy-Tourin [69] version of Godunov’s monotone upwind scheme. That is, the algorithm in [76] and [40] is simply Tsitsiklis’ algorithm with a di?erent (simpler) exposition. Our goal here is to extend the applicability of this idea from the eikonal equation to any geometrically based Hamiltonian. By this we mean a Hamiltonian satisfying the properties: H (x, ?ψ) > 0, if ?ψ = 0 and H (x, ?ψ) is homogeneous of degree one in ?ψ 10 (5) (4)

We wish to obtain a fast algorithm to approximate the viscosity solution of ? (x, ?ψ) = H (x, ?ψ) ? a(x) = 0. H (6) The ?rst step is to set up a monotone upwind scheme to approximate this problem. Such a scheme is based on the idea of Godunov used in the approximation of conservation laws. In Bardi and Osher [7], see also [65], the following was obtained (for simplicity we exemplify using two space dimensions and ignore the explicit x dependence in the Hamiltonian)
y y x x ψ, D? ψj ; D+ ψ, D? ψ) H (ψx , ψy ) ≈ H G (D+

= extu where

ε I(u? ,u+ ) extv ε I(v? ,v+ ) H (u, v )

I (a, b) = [min(a, b), max(a, b)] extu I (a, b) =
x ψij = ± u± = D±

mina≤u≤b if a ≤ b maxb≤u≤a if a > b

(ψi±1,j ? ψij ) (ψi,j ±1 ? ψij ) y , v± = D± . ψij = ± ?x ?y

(Note, the order may be reversed in the ext operations above – we always obtain a monotone upwind scheme which is often, but not always, order invariant [65]). This is a monotone upwind scheme which is obtained through the Godunov procedure involving Riemann problems, extended to general HamiltonJacobi equations [7], [65]. If we approximate H (??) = a(x, y ) by
y y x x x ?, D? ?; D+ ψ; D+ ψ, D? ψ) H G (D+

(7)

for Hamiltonians satisfying (4), (5) above, then there exists a unique solution for ψi,j in terms of ψi±1,j , ψi,j ±1 and ψi,j . Furthermore ψi,j is a nondecreasing function of all these variables. However, the fast algorithm needs to have property F : The solution to (7) depends on the neighboring ψ?,ν only for ψ?,ν < ψi,j . This gives us a hint as to how to proceed.

11

For special Hamiltonians of the form: H (u, v ) = F (u2 , v2 ), with F nondecreasing in these variables, then we have the following result [61]
2 + 2 ? 2 + 2 H G (u+ , u? ; v+ , v? ) = F (max((u? + ) , (u? ) ); max((v+ ) , (v? ) ))

(8)

where x+ = max(x, 0), x? = min(x, 0). It is easy to see that this numerical Hamiltonian has property F described above. This formula, as well as the one obtained in equation 10 below enables us to extend the fast marching method algorithm to a much wider class than was done before. For example, using this observation we were able to solve an etching problem, also considered in [3] where the authors did not use a fast marching method algorithm, but instead used a local narrow band approach and schemes devised in [64]. The Hamiltonian was H (?x , ?y , ?z ) = ?2 z 1+
2 4(?2 x + ?y ) 2 2 ?2 x + ?y + ?z

.

We are able to use the same heap sort technology as for the eikonal equation, for problems of this type. See ?gures 3 and 4. These ?gures represent the level contours of an etching process whose normal velocity is a function of the direction of the normal. The process moves down in ?gure 3 and up in ?gure 4. More generally, for H (u, v ) having the property uH1 ≥ 0, vH2 ≥ 0 then we also proved [61]
? + ? ? + + + H G (u+ , u? ; v+ , v? ) = max[H (u? + , v+ ), H (u? , v+ ), H (u+ , v? ), H (u? , v? )] (10) and property F is again satis?ed. Again in [61], we were able to solve a somewhat interesting and very anisotropic etching problem with this new fast algorithm. Here we took 2 H (?x , ?y ) = |?y |(1 ? a(?y )?y /(?2 x + ?y ))

(9)

where a = 0 if ?y < 0 a = .8 if ?y > 0

12

and observed merging of two fronts. See ?gures 5 and 6. These ?gures show a two dimensional etching process resulting in a merger. The fast method originating in [86] is a variant of Dijkstra’s algorithm and, as such involves the tree like heap sort algorithm in order to compute the smallest of a set of numbers. Recently Bou? e and Dupuis [11] have proposed an extremely simple fast algorithm for a class of convex Hamiltonians including those which satisfy (4) and (5) above. Basically, their statement is that the standard Gauss-Seidel algorithm, with a simple ordering, converges in a ?nite number of iterations for equation (7). This would give an O(N ), not O(N log N ) operations, with an extremely simple to program algorithm – no heap sort is needed. Moreover, for the eikonal equation with a(x, y ) = 1, the algorithm would seem to converge in 2d N iterations in Rd , d = 1, 2, 3, which is quite fast. This gives a very simple and fast redistancing algorithm. For more complicated problems we have found more iterations to be necessary, but still obtained promising results, together with some theoretical justi?cation. See [85] for details, which also include results for a number of nonconvex Hamiltonians. We call this technique the “fast sweeping method” in [85]. We refer to it in section 3 when we discuss the basic distance reinitialization algorithm.

13

1 0.5 0 ?0.5 ?1 ?1

1 0.5 0 ?0.5 ?1 ?1 1 ?1 0 1

0

0

1 ?1

0

1

1 0.5 0 ?0.5 ?1 ?1

1 0.5 0 ?0.5 ?1 ?1 1 ?1 0 1

0

0

1 ?1

0

1

Figure 1: Merging and pinching of curves in R3 moving by mean curvature. Reprinted from [13].

14

1 0 ?1 1 0 ?1 ?1 0

1 0 ?1 1 0 ?1 ?1 0

1

1

1 0 ?1 1 0 ?1 ?1 0

1 0 ?1 1 0 ?1 ?1 0

1

1

Figure 2: Merging and pinching of curves in R3 moving by mean curvature. Reprinted from [13].

15

Figure 3: Three dimensional etching using a fast algorithm. Reprinted from [61].

16

Figure 4: Three dimensional etching using a fast algorithm. Reprinted from [61].

17

Figure 5: Two dimensional etching with merging using a fast algorithm. Reprinted from [61].

18

Figure 6: Two dimensional etching with merging using a fast algorithm. Reprinted from [61].

19

3

Level Set Dictionary, Technology and Numerical Implementation

We list key terms and de?ne them by their level set representation. 1. The interface boundary Γ(t) is de?ned by: {x|?(x, t) = 0}. The region ?(t) is bounded by Γ(t) : {x|?(x, t) > 0} and its exterior is de?ned by: {x|?(x, t) < 0} 2. The unit normal N to Γ(t) is given by N =? ?? . |??|

3. The mean curvature κ of Γ(t) is de?ned by κ = ?? · ?? . |??|

4. The Dirac delta function concentrated on an interface is: δ(?)|??|, where δ(x) is a one dimensional delta function. 5. The characteristic function χ of a region ?(t): χ = H (?) where H (x) ≡ 1 if x > 0 H (x) ≡ 0 if x < 0. is a one dimensional Heaviside function. 6. The surface (or line) integral of a quantity p(x, t) over Γ:
Rn

p(x, t)δ(?)|??|dx.

7. The volume (or area) integral of p(x, t) over ? p(x, t)H (?)dx.
Rn

20

Next we describe three key technological advances which are important in many, if not most, level set calculations. 8. The distance reinitialization procedure replaces a general level set function ?(x, t) by d(x, t) which is the value of the distance from x to Γ(t), positive outside and negative inside. This assures us that ? does not become too ?at or too steep near Γ(t). Let d(x, t), be signed distance of x to the closest point on Γ. The quantity d(x, t) satis?es ? c and is the steady state solution |?d| = 1, d > 0 in ?, d < 0 in (?) (as τ → ∞) to ?ψ + sgn(?)(|?ψ| ? 1) = 0 ?τ ψ(x, 0) = ?(x, t). (11)

where sgn(x) = 2H (x)?1 is the one dimensional signum function. This was designed in [84]. The key observation is that in order to de?ne d in a band of width around Γ, we need solve (11) only for τ = O( ). It can easily be shown that this can be used globally to construct distance (with arbitrary accuracy) in O(N log N ) iterations [66]. Alternatively, we may use Tsitsiklis’ fast algorithm [86], which is also O(N log N ), with a much smaller constant, but which is only ?rst order accurate. A locally second order accurate (in the high resolution sense) fast marching method was proposed in [77]. While this method has a much lower local truncation error than a purely ?rst order accurate method, it is still globally ?rst order accurate except for special cases. Finally, we might also use the fast sweeping method from [11] and [85] as described in the last section, which appears to have O(N ) complexity and which is also only ?rst order accurate, although this complexity estimate has not been rigorously justi?ed. 9. Smooth extension of a quantity, e.g. vn on Γ to a neighborhood of Γ. Let the quantity be p(x, t). Solve to steady state (τ → ∞) ?? ?q + sgn(?) · ?q = 0 ?τ |??| q (x, 0) = p(x, t). Again, we need only solve this for τ = O( ) in order to extend p to be constant in the direction normal to the interface in a tube of width . 21

This was ?rst suggested and implemented in [24], analyzed carefully in [88], and further discussed and implemented in both [32] and [66]. A computationally e?cient algorithm based on heap sort technology and fast marching methods was devised in [1]. There are many reasons to extend a quantity o? of Γ, one of which is to obtain a well conditioned normal velocity for level contours of ? close to ? = 0 [24]. Others involve implementation of the Ghost Fluid Method of [32] discussed in the next section. 10. The basic level set method concerns a function ?(x, t) which is de?ned throughout space. Clearly this is wasteful if one only cares about information near the zero level set. The local level set method de?nes ? only near the zero level set. We may solve (2) in a neighborhood of Γ of width m?x, where m is typically 5 or 6. Points outside of this neighborhood need not be updated by this motion. This algorithm works in “?” space – so not too much intricate computer science is used. For details see [66]. Thus this local method works easily in the presence of topological changes and for multiphase ?ow. An earlier local level set approach called “narrow banding” was devised in [2]. Finally, we repeat that, in the important special case where vN in equation 2 is a function only of x, t and ?? (e.g. vN = 1), then equation 2 becomes a Hamilton-Jacobi equation whose solutions generally develop kinks (jumps in derivatives). We seek the unique viscosity solution. Many good references exist for this important subject, see e.g. [8, 27]. The appearance of these singularities in the solution means that special, but not terribly complicated, numerical methods have to be used, usually on uniform Cartesian grids. This was ?rst discussed in [64] and numerical schemes developed there were generalized in [65] and [43]. The key ideas involve monotonicity, upwind di?erencing, essentially nonoscillatory (ENO) schemes and weighted essentially nonoscillatory (WENO) schemes. See [64], [65] amd [43] for more details.

22

4

Coupling of the Level Set Method with External Physics

Interface problems involving external physics arise in various areas of science. The computation of such problems has a very long history. Methods of choice include front tracking, see e.g. [87] and [41], phase-?eld methods, see e.g. [48] and [59], and the volume of ?uid (VOF) approach, see e.g. [60] and [12]. The level set method has had major successes in this area. Much of the level set technology discussed in the previous two sections was developed with such applications in mind. Here, we shall describe level set approaches to problems in compressible ?ow, incompressible ?ow, ?ows having singular vorticity, Stefan problems, kinetic crystal growth and a relatively new island dynamics model for epitaxial growth of thin ?lms. We shall also discuss a recently developed technique, the ghost ?uid method (GFM), which can be used (1) to remove numerical smearing and nonphysical oscillations in ?ow variables near the interface and (2) to simplify the numerical linear algebra arising in some of the problems in this section and elsewhere.

4.1

Compressible Flow

Chronologically, the ?rst attempt to use the level set method in this area came in two phase inviscid compressible ?ow, [55]. There, to the equations of conservation of mass, momentum and energy, we appended equation (1), which we rewrote in conservation form as (ρ?)t + ? · (ρ?v ) = 0 (12)

using the density of the ?uid ρ. The sign of ? is used to identify which gas occupied which region, so it determines the local equation of state. This (naive) method su?ered from spurious pressure oscillations at the interface, as shown in [46] and [45]. These papers proposed a new method which reduced these errors by using a nonconservative formulation near the interface. However, [46] and [45] still smear out the density across the interface, leading to terminal oscillations for many equations of state. A major breakthrough in this area came in the development of the ghost ?uid method (GFM) in [32]. This enables us to couple the level set representation of discontinuities to ?nite di?erence calculations of compressible

23

?ows. The approach was based on using the jump relations for discontinuities which are tracked using equation (1) (for two phase compressible ?ow). What the method amounts to (in any number of space dimensions) is to populate cells next to the interface with “ghost values”, which, for two phase compressible ?ow retain their usual values of pressure and normal velocity (quantities which are continuous across the interface), with extrapolated values of entropy and tangential velocity (which jump across the interface). These quantities are used in the numerical ?ux when “crossing” an interface. An important aspect of the method is its simplicity. There is no need to solve a Riemann problem normal to the interface, consider the RankineHugoniot jump conditions, or solve an initial-boundary value problem. Another important aspect is its generality. The philosophy appears to be: at a phase boundary, use a ?nite di?erence scheme which takes only values which are continuous across the interface, using the natural values whenever possible. Of course, this implies that the tangential velocity is treated in the same fashion as the normal velocity and the pressure when viscosity is present. The same holds true for the temperature in the presence of thermal conductivity. Figure 7 shows results obtained for two phase compressible ?ow using the GFM together with the level set method. Air with density around kg kg 1m 3 is to the left of the interface and water with density around 1000 m3 is to the right of the interface. Note that there is no numerical smearing of the density at the interface itself which is fortunate as water cavitates kg at a density above 999 m 3 leading to host of nonphysical problems near the interface. Note too, that the pressure and velocity are continuous across the interface, although there are kinks in both of these quantities. A more complicated multidimensional calculation is shown in ?gure 8 where a shock wave in air impinges upon a helium droplet. See [32] for more details. While the GFM was originally designed for multiphase compressible ?ow, it can be generalized to treat a large number of ?ow discontinuities. In [33], we generalized this method to treat shocks, detonations and de?agrations in a fashion that removes the numerical smearing of the discontinuity. Figure 9 shows the computed solution for a detonation wave. Note that there is no numerical smearing of the leading wave front which is extremely important when trying to eliminate spurious wave speeds for sti? source terms on coarse grids as ?rst pointed out by [26]. While shocks and detonations have associated Riemann problems, the Riemann problem for a compressible ?ow de?agration discontinuity is not well posed unless the speed of the de?agration is given. Luckily, there is a large amount of literature on the 24

G-equation for ?ame discontinuities which was originally proposed in [50]. The G-equation represents the ?ame front as a discontinuity in the same fashion as the level set method so that one can easily consult the abundant literature on the G-equation to obtain de?agration speeds for the Ghost Fluid Method. Figure 10 shows two initially circular de?agration fronts that have just recently merged together. Note that the light colored region surrounding the de?agration fronts is a precursor shock wave that causes the initially circular de?agration waves to deform as they attempt to merge. The GFM was extended in [34] in order to treat the two phase compressible viscous Navier Stokes equations in a manner that allows for a large jump in viscosity across the interface. This paper spawned the technology needed to extend the GFM to multiphase incompressible ?ow including the e?ects of viscosity, surface tension and gravity as discussed in the next subsection.

4.2

Incompressible Flow

The earliest real success in the coupling of the level set method to problems involving external physics came in computing two-phase Navier-Stokes incompressible ?ow [84], [22]. The equations can be written as: ut + u · ?u + ? · (2?D) δ(?)σκN ?p = g+ + ρ ρ ρ ?·u = 0

where u = (u, v, w) is the ?uid velocity, p is the pressure, ρ = ρ(?) and ? = ?(?) are the piecewise constant ?uid densities and viscosities, g is the gravitational force, D is the viscous stress tensor, σ is the surface tension coe?cient, κ is the curvature of the interface, N is the unit normal and δ(?) is a delta function. See [87] and [12] for earlier front tracking and VOF methods (respectively) using a similar formulation. This equation is coupled to the front motion through the level set evolution equation (1) with v = u. This involves de?ning the interface numerically as having a ?nite width of approximately 3 to 5 grid cells. Within this smeared out band, the density, N viscosity and pressure are modeled as continuous functions. Then the σκ ρ term is used to approximate the surface tension forces which are lost when using a continuous pressure [84]. Successful computations using this model were performed in [84] and elsewhere [22]. Problems involving area loss were observed and signi?cant improvements were made in [83]. As mentioned above, the technology from [34] motivated the extension of the Ghost Fluid Method to this two phase incompressible ?ow problem. 25

First, a new boundary condition capturing approach was devised and applied to the variable coe?cient Poisson equation to solve problems of the form ? 1 ?p = f ρ

where the jump conditions [p] = g and [ 1 ρ ?p · N ] = h are given and ρ is discontinuous across the interface. This was accomplished in [49]. A sample calculation from [49] is shown in ?gure 11 where one can see that both the solution, p, and its ?rst derivatives are sharp across the interface without numerical smearing. Next, this new technique was applied to multiphase incompressible ?ow in [44]. Here, since one can model the jumps in pressure N directly, there is no need to add the σκ ρ source term to the right hand side of the momentum equation in order to capture the surface tension forces. Instead surface tension is modeled directly by imposing a pressure jump across the interface. In addition, [44] allows for exact jumps in both ρ and ? so that the nonphysical ?nite width smeared out interface in [84] can be replaced by a sharp interface. A three dimensional calculation of an (invisible) solid sphere impacting water causing a splash is shown in ?gure kg 12. Here the air has density near 1 m 3 while the water has density near kg 1000 m3 . Recently, in [57], this boundary condition capturing technology was extended to treat two phase incompressible ?ames where the normal velocity is discontinuous across the interface as well. Figure 13 shows an example calculation where two ?ames have just merged. Note that the velocity vectors in ?gure 13 clearly indicate that the velocity is kept discontinuous across the ?ame front. [39] considered two phase incompressible ?ames as well, proposing a method that keeps the interface sharp and removes numerical smearing. Unfortunately, the method proposed in [39] cannot treat topological changes in the ?ame front. Our method improves upon [39] allowing ?ame front discontinuities to merge, as in ?gure 13, or pinch o?. Figure 14 shows two ?ame fronts shortly after merging in three spatial dimensions.

4.3

Topological Regularization

In [37] and [38], it is shown that the level set formulation provides a new and novel way to regularize certain ill-posed equations of interface motion, by blocking interface self-intersection. We computed two and three dimensional unstable vortex motion without regularization other than that in the 26

discrete approximation to δ(?) – this is done over a few grid points. The key observation is that viewing a curve or surface as the level set of a function, and then evolving it with a perhaps unstable velocity ?eld, prevents certain types of blow up from occuring. This is denoted “topological regularization”. For example a tracked curve can develop a ?gure eight pattern, but a level set captured curve will pinch o? and stabilize before this happens. For the set up (involving two functions), see [37], where we perform calculations involving the Cauchy-Riemann equations. The motions agree until pinch o?, when the topological stabilization develops. As an example, we considered the two dimensional incompressible Euler equations, which may be written as ωt + u · ?ω = 0 ?×u = ω ?·u = 0 We are interested in situations in which the vorticity is initially concentrated on a set characterized by the level set function ? as follows Vortex patch: ω = H (?) Vortex sheet: ω = δ(?), (strength of sheet is Vortex sheet dipole: ω = 1 ) |??|

d δ(?) = δ (?). d?

The key observation is that ? also satis?es a simple advection equation and u and ω can be easily recovered. For example, for the vortex sheet case we solve ?t + u · ?? = 0 u = ??y ?x ??1 δ(?).

Standard Laplace solvers may be used. See [38] for results involving two and three dimensional ?ows. In [66] we added reinitialization and extension to this procedure and obtained improved results in the two dimensional case.

27

4.4

Stefan Problem

Another classical ?eld concerns Stefan problems [24], see also [78] for an earlier, but much more involved level set based approach. Here we wish to simulate melting ice or freezing water, or more complicated crystalline growth, as in the island dynamics model discussed below. We begin with a simpli?ed, nondimensionalized model (see [47] for an extension as mentioned below), ?T ?t vN = ?2 T, x ε ? ? = Γ(t) = [?T · N ] , x ε Γ(t)

where [·] denotes the jump across the boundary, and T = ?ε ?c κ(1 ? Acos(kA θ + θ0 )) + ε ?v vn (1 ? A cos(kA θ + θ0 ))
?x on Γ(t), and where κ is the curvature, θ = cos?1 |? ?| , and the constants ?c , and ε ?v depend on the material being modeled. A, kA , θ0 , ε We directly discretize the boundary conditions at Γ: To update T at grid nodes near the boundary, if the stencil for the heat equation would cross Γ (as indicated by nodal sign change in ?), we merely use dimension by dimension one sided interpolation and the given boundary T value at an imaginary node placed at ? = 0 (found by interpolation on ?) to compute Txx and or Tyy , (never interpolating across the interface) rather than the usual three point central stencils. The level set function ? is updated and then reinitialized to be equal to the signed distance to Γ. Note that the level set update uses vN that has been extended o? the interface. See [24] for details. We note that one can easily extend this to

?T = ? · (k?T ) ?t where k is a di?erent positive constant inside and outside of ? and vN = k?T · N , x ε Γ(t). as was recently done in [47]. An important observation is that our ?nite di?erencing at the interface leads to a nonsymmetric matrix inversion when applying implicit discretization in time, although the method does have nice properties such as second 28

order accuracy and a maximum principle. This lack of symmetry is a bit problematic for a fast implementation, especially for very large values of k. Fortunately, an extension of GFM can be used to derive a di?erent spatial discretization producing a symmetric matrix that can be inverted rather easily using fast methods. This was originally proposed by Fedkiw [31] and is described below. It is su?cient to explain how the spatial derivatives are derived with respect to one variable, since there are no mixed partial derivative terms. Suppose the interface point, xf , falls in between two grid points xi and xi+1 . From φ, the distances between xi , xi+1 and xf can be estimated by xf ? xi ≈ xi+1 ? xf ≈ ?φi ?x = θ1 ?x (φi+1 ? φi ) φi+1 ?x = θ2 ?x (φi+1 ? φi ) (13) (14)

To avoid numerical errors caused by division by 0, θ1 or θ2 are not used if either is less than ?x2 . If θ1 < ?x2 , then xf is assumed equal to xi . If θ2 < ?x2 , then xf is assumed equal to xi+1 . Either assumption is e?ectively a second order perturbation of the interface location leading to second order accurate spatial discretization. The nonsymmetric second order accurate discretization for Txx given in [24] is (Txx )i ≈ (Txx )i+1 ≈
Tf ?Ti Ti ?Ti?1 θ1 ?x ? ?x 1 2 (θ1 ?x + ?x) T +1 ?Tf Ti+2 ?Ti+1 ? iθ ?x 2 ?x 1 2 (?x + θ2 ?x)

(15)

(16)

where Tf denotes the value of T at xf and is determined from the boundary condition. Instead of using the nonsymmetric equations (15) and (16), Fedkiw [31] proposed using (Txx )i ≈ (Txx )i+1 ≈
Tf ?Ti θ1 ?x

? ?x

Ti ?Ti?1 ?x

(17) (18)

Ti+2 ?Ti+1 ?x

? ?x

Ti+1 ?Tf θ2 ?x

which leads to a symmetric linear system when using implicit time discretization. Equation (17) is derived using linear extrapolation of T from one side 29

of the interface to the other, obtaining TG = Tf + (1 ? θ1 ) Tf ? Ti θ1 (19)

as a ghost cell value for T at xi+1 . The standard second order discretization 2T of ? ?x2 at xi using TG at xi+1 is (Txx )i ≈
TG ?Ti ?x

? ?x

Ti ?Ti?1 ?x

(20)

and the substitution of equation (19) into equation (20) leads directly to (17). Equation (18) is derived similarly. Formulas (17) and (18) have O(1) errors using formal truncation error analysis. However, they are second order accurate on a problem where the interface has been perturbed by O(?x2 ), making them second order accurate in the interface location. Assume that the standard second order accurate discretization is used to obtain the standard linear system of equations for T at every grid point except for those adjacent to the interface, that is except for xi and xi+1 . Since the linear system of equations for the nodes to the left and including xi is independent of the system for the nodes to the right including xi+1 , only the linear system to the left is discussed here. Equation (20) is used to write a linear equation for Ti introducing a new unknown TG , and the system is closed with equation (19) for TG . In practice, equations (19) and (20) are combined to obtain equation (17) and a symmetric linear system of equations. This linear system of equations results in well determined values (up to some prescribed tolerance near roundo? error levels) of T at each grid node as well as a well determined value of TG (from equation (19)). For the sake of reference, designate T as the solution vector containing the values of T at each grid point to the left and including xi as well as the value of TG at xi+1 which are obtained by solving this symmetric linear system. Below, T is shown to be a second order accurate solution to our problem by showing that it is the second order accurate solution to a modi?ed problem where the interface location has been perturbed by O(?x2 ). Consider the modi?ed problem where a Dirichlet boundary condition of T = TG is speci?ed at xi+1 where TG is chosen to be the value of TG from T de?ned above. This modi?ed problem can be exactly discretized to second order accuracy everywhere using the standard discretization at every node except xi where equation (20) is used. We note that equation (20) is the 30

standard second order accurate discretization when a Dirichlet boundary condition of T = TG is applied at xi+1 . This new linear system can be discretized and solved in a standard fashion to obtain a second order accurate solution at each grid node. Then the realization that T is an exact solution to this linear system implies that T is a second order accurate solution to this modi?ed problem. Next consider the interface location dictated by the modi?ed problem. Since T is a second order accurate solution to the modi?ed problem, T can be used to obtain the interface location to second order accuracy. The linear interpolant that uses Ti at xi and TG at xi+1 predicts an interface location of exactly xf which is the true interface location. Since higher order interpolants (higher than linear) can contribute at most an O(?x2 ) perturbation of the interface location, the interface location dictated by the modi?ed problem is at most an O(?x2 ) perturbation of the true interface location, xf . In [25], we used this strategy to obtain a second order accurate symmetric discretization of the variable coe?cient Poisson equation ? (k?T ) = f

on irregular domains in as many as three spatial dimensions. Then, in a straightforward way, we obtained second order accurate symmetric discretizations of the heat equation on irregular domains using backward Euler time stepping with t = ( x)2 and Crank-Nicolson time stepping with t = x.

4.5

Kinetic Crystal Growth

For an initial state consisting of any number of growing crystals in Rd , d arbitrary, moving outward with given normal growth velocity v (N ) > 0 which depends on the angle of the unit surface normal N , the asymptotic growth shape is a single (kinetic) Wul?-construct crystal. This result was ?rst conjectured by Gross in (1918) [35]. This shape is also known to minimize the surface integral of v (N ) for a given volume. We gave a proof of this result [62], see also [81], using the level set formulation and the Hopf-Bellman formulas [6] for the solution of a Hamilton-Jacobi equation. Additionally, with the help of the Brunn-Minkowski inequality, we showed that if we evolve a convex surface under the motion described in (3), then the ratio to be minimized monotonically decreases to its minimum as time 31

increases, which provides a new proof that the Wul? construction solves the generalized isoperimetric problem as well. Thus there is a new link between this hyperbolic surface evolution and this (generally nonconvex) energy minimization. This also provides a convenient framework for numerically computing anisotropic kinetic crystal growth [67]. The theoretical and numerical results of this work are illustrated in the Uniform Density Island Dynamics models of [15] and [36]. That model describes crystals growing in two dimensions with an anisotropic velocity. An interesting spino? of this work came in [67] in which we proved that any two dimensional Wul? shape can be interpreted precisely as the solution of a Riemann problem for a scalar conservation law – contact discontinuities correspond to jumps in the angle of the normal to the shape, smoothly varying non ?at faces correspond to rarefaction waves and planar facets correspond to constant states, which develop because of kinks in the conservation law’s ?ux function. These kinks are also seen in the convexi?ed Wul? energy.

4.6

Epitaxial Growth of Thin Films

A new continuum model for the epitaxial growth of thin ?lms has been developed. Molecular Beam Epitaxy (MBE) is a method for growing extremely thin ?lms of material. The essential aspects of this growth process are as follows: under vacuum conditions a ?ux of atoms is deposited on a substrate material, typically at a rate that grows one atomic monolayer every several seconds. When deposition ?ux atoms hit the surface, they bond weakly rather than bounce o?. These surface “adatoms” are relatively free to hop from lattice site to site on a ?at (atomic) planar surface. However, when they hop to a site at which there are neighbors at the same level, they form additional bonds which hold them in place. This bonding could occur at the “step edge” of a partially formed atomic monolayer, which contributes the growth of that monolayer. Or, it could occur when two adatoms collide with each other. If the critical cluster size is one, the colliding adatoms nucleate a new partial monolayer “island” that will grow by trapping other adatoms at its step edges. By these means, the deposited atoms become incorporated into the growing thin ?lm. Each atomic layer is formed by the nucleation of many isolated monolayer islands, which then grow in area, merge with nearby islands, and ultimately ?ll in to complete the layer. Because the deposition ?ux is continually raining down on the entire surface, including the tops of the islands, 32

a new monolayer can start growing before the previous layer is completely ?lled. Thus islands can form on top of islands in a “wedding cake” fashion, and the surface morphology during growth can become quite complicated. The Island Dynamics model is a continuum model designed to capture the longer length scale features that are likely to be important for the analysis and control of monolayer thin ?lm growth. It is also intended to model the physics relevant to studying basic issues of surface morphology, such as the e?ects of noise on growth, the long time evolution of islands, and the scaling relationships between surface features (mean island area, step edge length, etc) in various growth regimes (precoalescence, coalescence). Refer to the classic work of [14] for useful background on the modeling of the growth of material surfaces. Our present discussion of the Island Dynamics Model is an abridged version of what was discussed in [54]. We shall present this new model in some detail because, although it has many of the features of the Stefan problem, it also requires some new level set technology. This includes a “wedding cake” formulation involving several level sets of the same function, nucleation of new islands, and nontrivial numerical treatment of the interface to obtain rapid convergence of implicit time marching schemes. In the Island Dynamics model, we treat each of the islands present as having a unit height, but a continuous (step edge) boundary on the surface. This represents the idea that the ?lms are atomic monolayers, so that height is discrete, but they cover relatively large regions on the substrate, so x and y are continuum dimensions. The adatoms are modeled by a continuous adatom density function on the surface. This represents the idea that they are very mobile, and so they e?ectively occupy a given site for some fraction of the time, with statistical continuity, rather than discretely. Thus, the domain for the model is the x ? y region originally de?ned by the substrate, and the fundamental dynamical variables for this model are: ? The island boundary curves Γi (t), i = 1, 2, . . . , N ? The adatom density on the surface ρ(x, y, t) The adatom density ρ obeys a surface di?usive transport equation, with a source term for the deposition ?ux ?ρ = ? · (D?ρ) + F, ?t where F = F (x, y, t) is speci?ed. During most phases of the growth, it is simply a constant. This equation may also include additional small loss 33

terms re?ecting adatoms lost to the nucleation of new islands, or lost to de-absorption o? the surface. This equation must be supplemented with boundary conditions at the island boundaries. In the simplest model of Irreversible Aggregation, the binding of adatoms to step edges leaves the adatom population totally depleted near island boundaries, and the boundary condition is ρ|Γ = 0. More generally, the e?ects of adatom detachment from boundaries, as well as the energy barriers present at the boundary, lead to boundary conditions of the form ?ρ Aρ + B =C ?n where C is given and [·] denotes the local jump across the boundary. In particular, note that ρ itself can have a jump across the boundary, even though it satis?es a di?usive transport equation. This simply re?ects that fact that the adatoms on top of the island are much more likely to incorporate into the step edge than to hop across it and mix with the adatoms on the lower terrace, and vice versa. The island boundaries Γi move with velocities v = vN N , where the normal velocity vn re?ects the island growth. This is determined simply by local conservation of atoms: the total ?ux of atoms to the boundary from both sides times the e?ective area per atom, a2 , must equal the local rate of growth of the boundary, vN : vN = ?a2 [q · N ] (this assumes there is no particle transport along the boundary; more generally, there is a contribution from this as well) where q is the surface ?ux of adatoms to the island boundary and N is the local outward normal. In general, the net atom ?ux q can be expressed in terms of the di?usive transport, as well as attachment and detachment probabilities, all of which can be directly related to the parameters of Kinetic Monte Carlo models. In the special case of Irreversible Aggregation, q is simply the surface di?usive ?ux of adatoms q = ?D?ρ. To complete the model we include a mechanism for the nucleation of new islands. If islands nucleate by random binary collisions between adatoms

34

(and if the critical cluster size is one), we expect the probability that an island is nucleated at a time t, at a site (x, y ), scales like P [dx, dy, dt] = ρ(x, y, t)2 dt dx dy. This model describes nucleation as a site-by-site, timestep-by-timestep random process. A simplifying alternative is to assume the nucleation occurs at the continuous rate obtained by averaging together the probabilistic rates at each site. In this case, if we let n(t) denote the total number of islands nucleated prior to time t, we have the deterministic equation dn = dt ρ2

where · denotes the spatial average. In this formulation, at each time when n(t) reaches a new integer value, we nucleate a new island in space. This is carried out by placing it randomly on the surface with a probability weighted by ρ2 , so that the e?ect of random binary collisions is retained. This basic model also has natural extensions to handle more complex thin ?lm models. For example, additional continuum equations can be added to model the dynamics of the density of kink sites on the island boundaries, which is a microstructural property that signi?cantly in?uences the local adatom attachment rates (see [15]). Also, we can couple this model to equations for the elastic stress that results from the “lattice mismatch” between the size of the atoms in the growing layers and the size of the atoms in the substrate. Conversely, the above model has a particular interesting extreme simpli?cation. We can go to the limit where the adatoms are so mobile on the surface (D → ∞) that the adatom density is spatially uniform, ρ(x, y, t) = ρ(t). In this case, the loss of adatoms due to the absorbing boundaries is assumed to take on a limiting form proportional to the adatom density and the total length L of all the island boundaries, which can be written as a simple sink term dρ = F ? λLρ. dt (This equation can be derived systematically from the conservation law for the total number of adatoms, ρ, that follows from the adatom di?usion equation. The above loss term is just a simpli?ed model for the net loss of adatoms to the island boundaries.) Further, it is assumed the velocity takes on a given normal dependent limiting form, vN = vN (N ) (which implies 35

that growing islands will rapidly assume the associated “Wul? shape” for this function vN (N ) (as in [62])). We have used this “Uniform Density” model to prototype the numerical methods, and to develop an understanding of how the island dynamics models are related to the continuum “rate equation” models that describe island size distribution evolution while using no information at all about the spatial interactions of the islands. Much of the above model is formally a Stefan problem and many of the level set techniques required for this were developed in [24] and can similarly be applied here. In addition, the internal boundary condition discretization of the adatom di?usion equation can be implemented using the symmetric matrix version of the discretization proposed by Fedkiw [31] and discussed earlier in this paper.

36

log(den) 3 2.5 ?500 2 1.5 1 ?1500 0.5 0 ?0.5 ?2500 0 2 4 6 8 10 0 2 4 ?2000 ?1000

vel

0

6

8

10

16 14 12

x 10

5

entropy 7 6 5

x 10

7

press

10 4 8 6 4 2 0 0 2 4 6 8 10 3 2 1 0 0 2 4 6 8 10

Figure 7: Two phase compressible ?ow calculated with the Ghost Fluid Method. Air on the left and water on the right. Reprinted from [32].

37

Figure 8: Mach 1.22 air shock collapse of a helium bubble. Reprinted from [32].

38

x 10

6

press

5

4

3

2

1

0

0

1

2

3

4

5

6

7

8

Figure 9: Nonsmeared detonation wave traveling away from a solid wall. Reprinted from [33].

39

1.6 density 100 1.4 90 80 70 60 50 40 30 20 10 0.6 0.8 1 1.2

10

20

30

40

50

60

70

80

90

100 0.4

Figure 10: Two de?agration fronts depicted shortly after merging. Reprinted from [33].

40

10

5

0

?5

1 ?10 0.5 3 2.5 2 1.5 1 0.5 0 ?1 ?0.5

0

Figure 11: Two spatial dimensions, ? · ( 1 ρ ?p) = f (x, y ), [p] = g (x, y ), [1 ρ ?p · N ] = h(x, y ). Reprinted from [49].

41

Figure 12: Water waves generated by the impact of an (invisible) solid object. Reprinted from [44].

42

velocity field (t=.035) 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.5 1 1.5

Figure 13: Two phase incompressible ?ames depicted shortly after merging (2 spatial dimensions). Reprinted from [57].

43

Figure 14: Two phase incompressible ?ames depicted shortly after merging (3 spatial dimensions). Reprinted from [57].

44

5

A Variational Approach with Applications to Multiphase Motion

In many situations, e.g., crystal growth, a material is composed of three or more phases. The interfaces between the phases move according to some law. If the material is a metal and its grain orientation is di?erent in each region, then an isotropic surface energy means that the velocity is the mean curvature of the interface. Or the velocities of the interfaces may depend on the pair of phases in contact; e.g. a di?erent constant velocity on each interface. Several ?xed grid approaches to this problem have been used. Merriman, Bence and Osher [53] have extended the level set method to compute the motion of multiple junctions. Also in that paper, and in [51] and [52], a simple method based on the di?usion of characteristic functions of each set ?i , followed by a certain reassignment step, was shown to be appropriate for the motion of multiple junctions in which the bulk energies are zero (and hence, the constants ei = 0, i = 1, . . . , n) and the fi,j are all equal to the same positive constant, i.e., pure mean curvature ?ow. See equations (21) below. Another method using an “in?uence matrix” was designed in [75]. However, as cautioned by the author, the method is expensive and complex. More general motion involving somewhat arbitrary functions of curvature, perhaps di?erent for each interface, was proposed in [53] as well. This was implemented basically by decoupling the motions, and then using a reassignment step. Again each region has its own private level set function. This function moves each level set with a normal velocity depending on the proximity to the nearest interface, thus vacuum and overlapping regions generally develop. Then a simple reassignment step is used, removing all the spurious regions. For details see [53]. In that paper there was no restriction to gradient ?ows. However, the general method in [53] lacks (so far) a clean theoretical basis to guide the design of numerical algorithms. These di?culties were recti?ed by the following method. In [88] we developed the variational level set approach inspired by [68]. Given a disjoint family ?i of regions in R2 with the common boundary between ?i and ?j denoted by Γi,j , we associate to this geometry an energy function of the form E = E1 + E2

45

E1 =
1≤i≤j ≤n

fi,j length (Γi,j ) ei area (?i )
1≤i≤n

(21)

E2 =

where E1 is the energy of the interface (surface tension). E2 is bulk energy, and n is the number of phases. The gradient ?ow induces motion such that the normal velocity of each interface is de?ned in (22). At triple points (which can be seen geometrically by the triangle inequality to be the only stable junctions if all the fi,j > 0), the angles are determined by (23) throughout the motion. Normal velocity of Γi,j = (vN )i,j = fi,j κi,j + (ei ? ej ). sin θ2 sin θ3 sin θ1 = = . f2,3 f3,1 f1,2 This could be rewritten as: E = E1 + E2
n

(22) (23)

E1 =
i=1 n

γi ei
i=1

δ(?i (x, y, t))|??i (x, y, t)|dxdy H (?i (x, y, t))dxdy,

(24)

E2 = where

fi,j = γi + γj , 1 ≤ i < j ≤ n. In the (most interesting) case when n = 3 we can solve uniquely for the γi . Now our problem becomes: Minimize E subject to the constraint that
n

H (?i (x, y )) ? 1 ≡ 0.
i=1

(25)

This in?nite set of constraints prevents the development of overlapping regions and/or vacuum. It requires that the level curves {(x, y )|?i (x, y, t) = 0} match perfectly.

46

The implementation of (24) with the in?nite set of constraints (25) is computationally demanding. Instead we try to replace the constraint (25) by a single constraint ( H (?i (x, y, t)) ? 1)2 dxdy = 2 (26)

where > 0 is as small as we can manage numerically. The gradient projection method leads us to an interesting coupled system which involves motion of level contours of each ? with normal velocity a + bκ together with a term enforcing the no overlap/vacuum constraint. We ?nd that ≈ ?x in real calculations. See [88] for details. We have used this technique to reproduce the general behavior of complicated bubble and droplet motions in two and three dimensions [90]. The problems included soap bubble colliding and merging, drops falling or remaining attached to a generally irregular ceiling (see ?gure 15), liquid penetrating through an asymmetric funnel opening (see ?gure 16), and mercury sitting on the ?oor (see ?gure 17). This variational approach has also been found to have many applications in computer vision – this will be discussed in the next section.

47

t=0 50 40 30 20 10 10 20 30 40 50 50 40 30 20 10 10

t=0.0022

20

30

40

50

t=0.00248 50 40 30 20 10 10 20 30 40 50 50 40 30 20 10 10

t=0.00252

20

30

40

50

Figure 15: Three dimensional drop falling from ceiling. Reprinted from [90].

48

dx=0.005, dt=0.00001 t=0 200 150 100 50 100 t=0.03 200 150 100 50 100 t=0.052 200 150 100 50 200 200 150 100 50 200 200 150 100 50 100 t=0.056 200 200 150 100 50 100 t=0.04 200 t=0.01

100 200 100 200 g=50, surface tension with the funnel=0.1, surface tension with the air=0.2

Figure 16: Liquid falling through funnel opening. Reprinted from [90].

49

dx=0.01, dt=0.00001 t=0 100 80 60 40 20 20 40 60 80 100 100 80 60 40 20 20 40 60 80 100 t=0.002

t=0.02 100 80 60 40 20 20 40 60 80 100 100 80 60 40 20 20

t=0.05

40

60

80

100

Figure 17: Mercury droplet responding to surface tension. Reprinted from [90].

50

6

Applications to Computer Vision and Image Processing

The use of PDE’s and level set motion in image analysis and computer vision has exploded in recent years. Good references include [18] and [58]. One basic idea is to view an image as u0 (x, y ), a function de?ned on a square, and obtain a (usually second order) ?ow equation of the form ut = F (u, Du, D2 u, x, t) u(x, y, 0) = u0 (x, y ) which, for positive t, processes the image. For example, if one solves the heat equation with F (u, Du, D2 u, x, t) = ?u, then u(x, y, t) is the same as convolution of u0 with a Gaussian of variance t. L.I. Rudin, in his Ph.D. thesis [70], made the point that images are largely characterized by singularities, edges, boundaries, etc, and thus nonlinearity, especially ideas related to shock propagation, should play a role. This led to the very successful total variation based image restoration algorithms of [72] and [71]. Brie?y, if we are presented with a noisy blurred image (28) u0 = j ? u + n where j is a given convolution kernel, and the mean and variance of the noise are given, we wish to obtain the “best” restored image. This leads us (see [72] and [71]) to the evolution equation ut = ? · ?u ? λj ? (j ? u ? u0 ) |?u| (29) (27)

to be solved for t > 0, where u(x, y, 0) is given, and λ(t) > 0 is obtained as a Lagrange multiplier, or is set to be a ?xed constant. If j ? u = u, this becomes a pure denoising problem. The (very interesting) geometric interpretation of this procedure is that each level contour of u is moved normal to itself with velocity equal to its curvature, divided by the norm of the gradient of u, then “pulled back” in an attempt to deconvolve (28). The results are state-of-the-art for many problems. Noisy regions can be thought of as corresponding to contours having very high curvature, while edges have ?nite curvature and in?nite gradients. Here the motion of level sets is just used to interpret the dynamics. In [4], it was shown that reasonable axioms of image processing lead to the 51

remarkable fact that motion of level contours by a function of curvature is fundamental to the subject. The arti?cial time t is actually the scale parameter [4]. We would like to describe a few new applications of this set of ideas. In [10], we have considered the problem of processing of images de?ned on manifolds. The technique actually can be used to solve a wide class of elliptic equations on manifolds, without triangulation, using only a local Cartesian grid, for very general situations. Given a manifold in R3 , de?ned by ψ(x, y, z ) = 0, we can de?ne the projection matrix ?ψ ?ψ P?ψ = I ? ? . (30) |?ψ| |?ψ| If u is an image de?ned on ψ = 0 we can use our level set calculus to extend it constant normal to the manifold, in some neighborhood of the manifold. If u0 is the original noisy image, the energy to be minimized is E (u) =
R3

|P?ψ ?u|δ(ψ)|?ψ|dx +

λ 2

(u ? u0 )2 δ(ψ)|?ψ|dx.

Using the gradient descent algorithm, i.e. following the general procedure of [72] and [88] leads us to ut = 1 ?· |?ψ| P?ψ ?u |?ψ| ? λ(u ? u0 ). |P?ψ ?u|

This corresponds to total variation denoising. This is done using the local level set method [66] which allows great ?exibility in geometry, while always using a Cartesian grid. See [10] for denoising and deblurring results. The technique is quite general – both variational problems and PDE’s de?ned on manifolds can be solved in a reasonably straightforward fashion, without restrictions on the manifold and without complicated triangulation – just by using a ?xed Cartesian grid. Another basic image processing task is to detect objects hidden in an image u0 . A popular technique is called active contours or snakes, in which one evolves a curve, subject to constraints until the curve surrounds the image. The level set method was ?rst used in [16] as a very convenient tool to follow the motion of active contours in order to surround hidden objects.

52

This was an important step since topological changes could easily be handled, a variational approach could be easily used [17] and stable, easy to program algorithms resulted. The curve is moved with a velocity which vanishes when the object is surrounded. Thus edge detectors are traditionally used to stop the evolving curve. For example, one might use g(|?u0 |) = 1 1 + |?jσ ? u0 |
2

where jσ is a Gaussian of variance σ . In [20] the authors developed a model which was not based on edges, using a scale parameter, based on a simpli?cation of the Mumford-Shah [56] energy based segmentation. The implementation is done through the variational level set approach [88] and the results are remarkable. The method has a denoising capability as well as the ability to perform a multiscale segmentation. See [21] and [20] for details. Here we just present the evolution equation for the level set function ?: ?t = |??| ?? · ?? ? ν ? λ(u0 ? c1 )2 + λ(u0 ? c2 )2 |??|

for parameters ?, ν, λ ≥ 0, where c1 and c2 are the averages of u0 over the region for which ? ≥ 0 and ? ≤ 0 respectively. ν corresponds to the bulk energy of the area for which ? ≥ 0, ? corresponds to the surface tension of the interface, and λ is the penalty for the L2 error between u0 and its mean over each region. Figure 18 shows an active contour segmenting a MRI brain image from its backgound. A somewhat related problem as discussed in [89] is the following. Given a collection of unorganized points, and/or curves, and/or surface patches, ?nd a surface which can be regarded as its shape. This is a fundamental visualization problem which arises in computer graphics, visualization and simulation. No assumptions about the ordering, connectivity or topology of the data sets or of the true shape is given. The input is the general distance to the data set which is given on a (usually logically rectangular) grid. Additionally, we may also input the values of the normal to the surface at the same or di?erent data points. The key idea is to ?nd a function ? whose zero level set is the interpolating surface, ? changes sign as one goes from inside to outside the surface. The output is the discrete values of ?, which can be reinitialized to be signed distance to this surface. 53

We set up a variational problem, which basically minimizes the integral over the unknown surface, of the pth power of distance to the data set. We may include information about the normals in analogous fashion. Gradient descent (as in the image restoration and active contour problems) gives us a weighted motion by curvature plus convection algorithm. The results are very promising as shown ?gure 19. For more details, see [89].

54

Figure 18: Active contour segmentation of an MRI brain image from its backgound. Reprinted from [19].

55

Interpolation of Two Linked Tori, R = 0:24

r = 0:05

initial data

1000 iterations

2000 iterations

2500 iterations

3000 iterations number of data points = 25 10 2

dx

3500 iterations = 0 02 = 0 0002
: dt :

Figure 19: Interpolation of two linked tori. Reprinted from [89].

56

7

Conclusion

The idea of using a level set to represent an interface is a very old one. The level set method itself has antecedents, for example, in the G equation approach of Markstein [50]. What is new is the level set method technology, theoretical justi?cation through viscosity solutions, and the enormous number of wide ranging applications that are now available, with new applications developing quite frequently.

57

References
[1] Adalsteinsson, D. and Sethian, J.A., The Fast Construction of Extension Velocities in Level Set Methods, J. Comput. Phys. 148, 2-22 (1999). [2] Adalsteinsson, D. and Sethian, J.A. A Fast Level Set Method for Propagating Interfaces, J. Comput. Phys. 118, 269-277 (1995). [3] Adalsteinsson, D. and Sethian, J.A., A Level Set Approach to a Uni?ed Model for Etching, Deposition, and Lithography II: Three Dimensional Simulations, J. Comput. Phys. 122, 348-366 (1995). [4] Alvarez, L., Guichard, F., Lions, P.-L., and Morel, J.-M., Axioms and Fundamental Equations of Image Processing, Arch. Ration. Mech. and Anal. 123, 199-257, (1993). [5] Ambrosio, L. and Soner, H.M., Level Set Approach To Mean Curvature Flow in Arbitrary Codimension, J. Di?. Geom. 43 (4) 693-737 (1996). [6] Bardi, M. and Evans, L.C., On Hopf’s Formulas for Solutions of Hamilton-Jacobi Equations, Nonlinear Analysis TMA 8, 1373-1381 (1984). [7] Bardi, M. and Osher, S., The Nonconvex Multidimensional Riemann Problem for Hamilton-Jacobi Equations, SIAM J. on Anal. 22, 344-351 (1991). [8] Barles, G., Solutions de Viscosite des Equations de Hamilton-Jacobi, Springer-Verlag, Berlin (1966). [9] Bellettini, G., Novaga, M. and Paolini, M., An Example of Three Dimensional Fattening for Linked Space Curves Evolving by Curvature, Comm. of Partial Di?. Equations (in press). [10] Bertalmio, M., Cheng, L.T., Osher, S., and Sapiro, G., Variational Problems and Partial Di?erential Equations on Implicit Surfaces: The Framework and Examples in Image Processing and Pattern Formation, UCLA CAM Report 00-23, J. Comput. Phys. (in review). [11] Boue, M. and Dupuis, P., Markov Chain Approximations for Deterministic Control Problems with A?ne Dynamics and Quadratic Cost in the Control, SIAM J. Numer. Anal. 36 (3), 667-695 (1999).

58

[12] Brackbill, J.U., Kothe, D.B. and Zemach, C., A Continuum Method for Modeling Surface Tension, J. Comput. Phys. 100, 335-354 (1992). [13] Burchard, P., Cheng, L.-T., Merriman, B., and Osher, S., Motion of Curves in Three Spatial Dimensions Using a Level Set Approach, UCLA CAM Report 00-29, J. Comput. Phys. (in review). [14] Burton, W.K., Cabrera, N. and Frank, F.C., The Growth of Crystals and the Equilibrium Structure of Their Surfaces, Phil. Trans. Roy. Soc. London, Ser. A, pp. 243-299, (1951). [15] Ca?isch, R.E., Gyure, M., Merriman, B., Osher, S., Ratsch, C., Vvedensky, D. and Zinck, J., Island Dynamics and the Level Set Method for Epitaxial Growth, Appl. Math. Lett. 12, 13-22 (1999). [16] Caselles, V., Catt? e, F., Coll, T., and Dibo, F., A Geometric Model for Active Contours in Image Processing, Numerische Mathematik 66, 1-31 (1993). [17] Caselles, V., Kimmel, R. and Sapiro, G., Geodesic Active Contours, Int. J. Comput. Vision 22, 61-79 (1997). [18] Caselles, V., Morel, J.-M., Sapiro, G., and Tannenbaum, A. Editors, Special Issue on Partial Di?erential Equations and Geometry-Driven Di?usion in Image Processing and Analysis, IEEE Transactions on Image Processing, (1998), v. 7, pp. 269-473. [19] Chan, T., Fedkiw, R., Kang, M. and Vese, L., Improvements in the E?ciency and Robustness of Active Contour Algorithms, (in preparation). [20] Chan, T. and Vese, L., Active Contours Without Edges, UCLA CAM Report 98-53 (1998). [21] Chan, T. and Vese, L., An Active Contour Model Without Edges, in Lecture Notes in Comp. Sci., v. 1687, eds. M. Neilsen, P. Johansen, O.F. Olsen and J. Weickert, pp. 141-151, 1999. [22] Chang, Y.C., Hou, T.Y., Merriman, B. and Osher, S., A Level Set Formulation of Eulerian Interface Capturing Methods for Incompressible Fluid Flows, J. Comput. Phys. 124, 449-464 (1996).

59

[23] Chen, Y.G., Giga, Y. and Goto, S., Uniqueness and Existence of Viscosity Solutions of Generalized Mean Curvature Flow Equations, J. Di?. Geom. 33, 749-786 (1991). [24] Chen, S., Merriman, B., Osher, S. and Smereka, P., A simple level set method for solving Stefan problems, J. Comput. Phys. 135, 8-29 (1997). [25] Cheng, L.T., Fedkiw, R.P., Gibou, F. and Kang, M., A Symmetric Method for Implicit Time Discretization of the Stefan Problem, J. Comput. Phys. (in review). [26] Colella, P., Majda, A., and Roytburd, V., Theoretical and Numerical Structure for Reacting Shock Waves, SIAM J. Sci. Stat. Comput. 7 (4), 1059-1080 (1986). [27] Crandall, M.G., Ishii, H. and Lions, P.-L., User’s Guide to Viscosity Solutions of Second Order Partial Di?erential Equations, Amer. Math. Soc. Bull. 27, 1-67 (1992). [28] DeGiorgi, E., Barriers, Boundaries, Motion of Manifolds, Lectures in Pavia, Italy, 1994. [29] Evans, Y.C. Soner, H.M. and Souganidis, P.E., Phase Transitions and Generalized Motion by Mean Curvature, Comm. Pure and Applied Math. 65, 1097-1123 (1992). [30] Evans, Y.C. and Spruck, J., Motion of Level Sets by Mean Curvature I, J. Di?. Geom. 33, 635-681 (1991). [31] Fedkiw. R.P. A Symmetric Spatial Discretization for Implicit Time Discretization of Stefan Type Problems, (unpublished) June 1998. [32] Fedkiw, R., Aslam, T., Merriman, B., and Osher, S., A Non-Oscillatory Eulerian Approach to Interfaces in Multimaterial Flows (The Ghost Fluid Method), J. Comput. Phys. 152 (2), 457-492 (1999). [33] Fedkiw, R., Aslam, T., and Xu, S., The Ghost Fluid Method for De?agration and Detonation Discontinuities, J. Comput. Phys. 154 (2), 393-427 (1999). [34] Fedkiw, R. and Liu, X.-D., The Ghost Fluid Method for Viscous Flows, Progress in Numerical Solutions of Partial Di?erential Equations, Arcachon, France, edited by M. Hafez, July 1998. 60

[35] Gross, R., Zur Theorie des Washstrums und Losungsforganges Kristalliner Materie, Abhandl. Math.-Phys. Klasse Kongl. Sachs, Wiss, 35, pp. 137-202 (1918). [36] Gyure, M., Ratsch, C., Merriman, B., Ca?isch, R.E., Osher, S., Zinck, J. and Vvedensky, D. Level Set Methods for the Simulation of Epitaxial Phenomena, Phys. Rev. E 59, R6927-6930 (1998). [37] Harabetian, E. and Osher, S., Regularization of Ill-Posed Problems via the Level Set Approach, SIAM J. Appl. Math. 58, 1689-1706 (1998). [38] Harabetian, E., Osher, S. and Shu, C.-W., An Eulerian Approach for Vortex Motion Using a Level Set Approach, J. Comput. Phys. 127, 15-26 (1996). [39] Helenbrook, B.T., Martinelli, L. and Law, C.K. A Numerical Method for Solving Incompressible Flow Problems with a Surface of Discontinuity, J. Comput. Phys. 148, 366-396 (1999). [40] Helmsen, J., Puckett, E., Colella, P. and Dorr, M., Two New Methods for Simulating Photolithography Development in 3D, Proc. SPIE 2726, 253-261 (1996). [41] Hou, T., Numerical Solutions To Free Boundary Problmes, ACTA Num. 4, 335-416 (1995). [42] Hou, T., Li, Z., Osher, S. and Zhao, H.-K., A Hybrid Method for Moving Interface Problems with Application to the Hele-Shaw Flow, J. Comput. Phys. 134, 236-252 (1997). [43] Jiang, G.-S. and Peng, D., Weighted ENO Schemes for Hamilton Jacobi Equations, SIAM J. Sci. Comput. 21, 2126-2143 (2000). [44] Kang, M., Fedkiw, R., and Liu, X.-D., A Boundary Condition Capturing Method for Multiphase Incompressible Flow, UCLA CAM Report 99-21, J. Comput. Phys. (in review). [45] Karni, S., Hybrid multi?uid algorithms, SIAM J. Sci. Comput. 17 (5), 1019-1039 (1996). [46] Karni, S., Multicomponent Flow Calculations by a Consistent Primitive Algorithm, J. Comput. Phys 112, 31-43 (1994).

61

[47] Kim, Y.-T., Goldenfeld, N. and Dantzig, J., Computation of Dendritic Microstructures using a Level Set Method, Physical Review E 62, (2000). [48] Kobayashi, R., Modeling and Numerical Simulations of Dendritic Crystal Growth, Physica D 63, 410 (1993). [49] Liu, X.-D., Fedkiw, R.P. and Kang, M., A Boundary Condition Capturing Method for Poisson’s Equation on Irregular Domains, J. Comput. Phys. 160, 151-178 (2000). [50] Markstein, G.H., Nonsteady Flame Propagation, Pergamon Press, Oxford 1964. [51] Mascarenhas, P., Di?usion Generated Motion by Mean Curvature, UCLA CAM Report 92-33, 1992. [52] Merriman, B., Bence, J. and Osher, S., Di?usion Generated Motion by Mean Curvature, in AMS Select Lectures in Math., The Comput. Crystal Grower’s Workshop, edited by J. Taylor, AMS Providence, 1993, pp. 73-83. [53] Merriman, B., Bence, J. and Osher, S., Motion of Multiple Junctions: A Level Set Approach, J. Comput. Phys. 112 (2), 334-363 (1994). [54] Merriman, B., Ca?isch, R. and Osher, S., Level Set Methods with an Application to Modelling the Growth of Thin Films, in Free Boundary Value Problems, Theory and Applications, pp. 51-70, edited by I. Athanasopoulos, G. Makrikis, and J.F. Rodriguez, CRC Press, Boca Raton, FL 1999. [55] Mulder, W., Osher, S., and Sethian, J.A., Computing Interface Motion in Compressible Gas Dynamics, J. Comput. Phys. 100, 209-228 (1992). [56] Mumford, D., and Shah, J., Optimal Approximation by Piecewise Smooth Functions and Associated Variational Problems, Comm. Pure Appl. Math. 42, 577-685 (1989). [57] Nguyen, D., Fedkiw, R.P. and Kang, M. A Boundary Condition Capturing Method for Incompressible Flame Discontinuities, UCLA CAM Report 00-19, J. Comput. Phys. (in review).

62

[58] Nielsen, M., Johansen, P., Olsen, O.F., and Weickert, J., editors, Scale Space Theories in Computer Vision, in Lecture Notes in Computer Science, v. 1682, Springer-Verlag, Berlin, (1999). [59] Nochetto, R.H., Paolini, M. and Verdi, C., An Adaptive Finite Element Method for Two Phase Stefan Problems in Two Space Dimensions, Part II: Implementation and Numerical Experiments, SIAM J. of Sci. Comput. 12, p. 1207 (1991). [60] Noh, W.F. and Woodward, P.R., SLIC (Simple Line Interface Construction), in Lecture Notes in Physics, v. 59, edited by A. van de Vooren and P.J. Zandbergen, Springer-Verlag, Berlin (1976), p. 330. [61] Osher, S. and Helmsen, J., A Generalized Fast Algorithm with Applications to Ion Etching, (in progress). [62] Osher, S. and Merriman, B., The Wul? Shape as the Asymptotic Limit of a Growing Crystalline Interface, Asian J. Math. 1 (3), 560-571 (1997). [63] Osher, S., A Level Set Formulation for the Solution of the Dirichlet Problem for Hamilton-Jacobi Equations, SIAM J. on Anal. 24, 11451152 (1993). [64] Osher, S. and Sethian, J.A., Fronts Propagating with Curvature Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulations, J. Comput. Phys. 79, 12-49 (1988). [65] Osher, S. and Shu, C.W., High Order Essentially Non-Oscillatory Schemes for Hamilton-Jacobi Equations, SIAM J. Numer. Anal. 28 (4), 907-922 (1991). [66] Peng, D., Merriman, B., Osher, S., Zhao, H.-K., and Kang, M., A PDE-Based Fast Local Level Set Method, J. Comput. Phys. 155, 410438 (1999). [67] Peng, D., Osher, S., Merriman, B. and Zhao, H.-K., The Geometry of Wul? Crystal Shapes and Its Relations with Riemann Problems, in Contemporary Mathematics 238, 251-303, edited by G.-Q. Chen and E. DeBenedetto, AMS, Providence, RI, 1999.

63

[68] Reitich, F. and Soner, H.M., Three Phase Boundary Motions under Constant Velocities I, the Vanishing Surface Tension Limit, Proc. Royal Soc. Edinburgh 126A, 837-865 (1996). [69] Rouy, E. and Tourin, A., A Viscosity Solutions Approach to ShapeFrom-Shading, SIAM J. Num Anal. 29 (3) 867-884 (1992). [70] Rudin, L.I., Images, Numerical Analysis of Singularities, and Shock Filters, Ph.D. thesis, Computer Science Dept., Caltech, #5250:TR:87 (1987). [71] Rudin, L.I. and Osher, S., Total Variation Based Restoration with Free Local Constraints, Proc. ICIP, IEEE Int’l Conf. on Image Processing, Austin, TX, (1994), pp. 31-35. [72] Rudin, L.I., Osher, S. and Fatemi, E., Nonlinear Total Variation Based Noise Removal Algorithms, Physica D 60, 259-268 (1992). [73] Ruuth, S., Merriman and Osher, S., A Fixed Grid Method for Capturing the Motion of Self-Intersecting Interfaces and Related PDEs, UCLA CAM Report 99-22, 1999, J. Comput. Phys. (in review). [74] Ruuth, S., Merriman, B., Xin, J. and Osher, S., Di?usion-Generated Motion for Mean Curvature of Filaments, UCLA CAM Report 98-47, 1998, Comm. Pure and Applied Math (in review). [75] Sethian, J.A., Algorithms for Tracking Interfaces in CFD and Materials Science, Ann. Rev. of Comput. Fluid Mech. (1995). [76] Sethian, J.A., Fast Marching Level Set Methods for Three Dimensional Photolithography Development, Proc. SPIE 2726, 261-272 (1996). [77] Sethian, J.A., Fast Marching Methods, SIAM Review 41, 199-235 (1999). [78] Sethian, J.A. and Strain, J., Crystal Growth and Dendritic Solidi?cation, J. Comput. Phys. 98, 231-253 (1992). [79] Schwarz, K.W., Simulations of Dislocations on the Mesoscopic Scale. I. Methods and Examples, J. Applied Phys. 85, 108-119 (1999). [80] Schwarz, K.W., Simulations of Dislocations on the Mesoscopic Scale. II. Application to Strained-Layer Relaxation, J. Applied Phys. 85, 120-129 (1999). 64

[81] Soravia, P., Generalized Motion of a Front Propagating Along Its Normal Direction: A Di?erential Games Approach, Nonlinear Analysis TMA 22, 1247-1262 (1994). [82] Steinho?, J., Fan, M. and Wang, L., A New Eulerian Method for the Computation of Propagating Short Acoustic and Electromagnetic Pulses, J. Comput. Phys. 157, 683-706 (2000). [83] Sussman, M., Fatemi, E., Smereka, P. and Osher, S., An Improved Level Set Method for Incompressible Two-Phase Flow, Computers and Fluids 27, 663-680 (1998). [84] Sussman, M., Smereka, P. and Osher, S., A Level Set Approach for Computing Solutions to Incompressible Two-Phase Flow, J. Comput. Phys. 114, 146-159 (1994). [85] Tsai, R., Zhao, H.-K. and Osher, S. Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations, (in preparation). [86] Tsitsiklis, J.N., E?cient Algorithms for Globally Optimal Trajectories, IEEE Transactions on Automatic Control 40 (9), 1528-1538 (1995). [87] Unverdi, S.O. and Tryggvason, G., A Front-Tracking Method for Viscous, Incompressible, Multi-Fluid Flows, J. Comput. Phys. 100, 25-37 (1992). [88] Zhao, H.-K., Chan, T., Merriman, B. and Osher, S., A Variational Level Set Approach to Multiphase Motion, J. Comput. Phys. 127, 179195 (1996). [89] Zhao, H.-K., Merriman, B., Osher, S. and Kang, M., Implicit Nonparametric Shape Reconstruction from Unorganized Points using a Variational Level Set Method, UCLA CAM Report 98-7, 1998, Computer Vision and Image Understanding (to appear). [90] Zhao, H.-K., Merriman, B., Osher, S. and Wang, L., Capturing the Behavior of Bubbles and Drops Using the Variational Level Set Approach, J. Comput. Phys. 143, 495-518 (1998).

65

?

?

???? ? ? ? ? ? ? ?× ?? ??? ×× ?

?

? ? ?

×

? ?

? ??×

×

?

????? ? ? × ?? ?? ??

?

? ?? ?×

????

?? ?? ? ?? ?

?

× ?? ? ?? ?? ? ?× ??× ??

??

?

??? ? ?? ?? ? × ? ? ? ? ? ? ? ? × ? ? ? ?? ?× ? × × ?? ? ×?? ??? ×× ? ? ? ?? ? ? ?????

?? ? ? ?? ??? ? ? ??? ?
??? ?

?? ? ? ?? ??? ? ??× ? × ? ×???? ?? ? × ? ? ?? ×??

? ?? ? ?

? ???? ?? ?

???? ? ? ? ? ×? ? ? ? × ? ? ? ? × ? ? × ??? ? ? ? ?? ??×? ? ? ? ? ?× ?

? ? ? × ? ????? ? ? × ?? ? ?? ? ×???× ?? ?? ? ?? ? × ? ??? ? ?

?? × × × ?? ?? ?? ? ?× ??× ???? ?? ?? ? ? × ? ? ? ×? ???? ? ? ? ? × ? ? ? ?? ? ? ? ?

×?×? ?×? ? × ? ?? ? ? ?? × ×? ?

? ×? ?????? ?? ? ??×? ?? ? ? ?? × ?? ? ??×?

? × ?? ? ? ?????? ? ??? ?

??? ? ? ? × ? ? ? ? × ? ? ?? ? ? ? ?? ? ?? ×? ?? × ? ? ? ? ?×? ????? ? ?? ? × ?? ??? ? ????? ? ? × ?? ? ? ?? × ? ? ? ????? ? ? × ??? ?? ?? ??? ×? ? ? ??? ?

× ??? ? ? ? ? × ? ? ? ? ×? ??? ? ? ? ? ? ?× ?? ??? ??? ?? ? ??×? ??? ×× ?

? ? ? ?? ? ????

× ??? ????× ×???? ??× ?? ? ? ?????? ? ??? ×× ? ? ? ?? ? ? ? ? ×?? ×? ? ? ? ??× ?? ? ? ? ?

??? ? ? ? ? ?? ?? ? ?? ?

? ? ???

×

× ? ? ???
????? ?

???? ? ? ? ? ? ? ? ? × ? ? ? ? ? ????? ? ? × ??? ?
? ? ? ?? ? ?? ?? ? ?× ??? ?? ? ?? ? ?? ? ?? ?

????
?

×× ? ? ? ? ? ×?
?
? ? ??? ?? ×?×? ? ?? ? ? ?? ? ??

? ?

? ??? ?? ? ? ? ?? ?

??

?

? ?? ? ? ? ?? ?

????? ?

?

?

? ? ? ?? ? ?× ?? ?

? ?? ×?? ? ? ??

??? ×? ??

?

??

????? ? ? ? ??

? × ?? ? ?

???

×?

???? ?? ? ?× ??? ???? ? ??????? ? ? ??

? ? ??× ?

? ?? ?? ??? ??? ?

?? ?

?

× ? ??

?? ?

????? ? ? ?

?? ?

? ×

×?????? ? ?? ?

? ? ? ?

??????

???

? ??

???

?????

?

? ????? ? ? ??
? × ? ? ? × ?? ?? ? ?? ? ?? ? ?? ?×? ? ? ? ? × ? ? ? ? ×? ? ? ? ×?? ? ? ? ? ? ×? ? ??? ×? ? × × ?? ? ?? ?? ? ?× ??× ?? ? ??? ?? ? ? × ?? × × ? ? ? ???? ? × ?? ? ? ? ×? ??? ×× ? ? ? × ??? ? ? × ? ? ? ? ×? ? ×???? ?? × ? ? × ? ??

? ? ? × ? ????? ? ? × ?? ? ? ???

?? × × × ?? ?? ?? ? ?× ??× ???? ?? ?? ? ? × ? ?? ?? ?? ? ?? ? ? ? ?? ? ? ?? ? ??? × ? ? ?? ? ? ? ×? ?× ? ? ? ?×? ? ? ?? ?? ? ? ? ×? ?

? ?? ? ??? ? ? ? ? ? × ?? ?? ?? ??

× × ? ?? ????? ??? ? ?? ????? ?? ? ×???× ? ? ? ? ?? ? ×???× ? ×? ?? ?? ? ?? ? ? ? ? ???? ? ? ? ?? ? ? ??? ? ??? ? ???? ??× ?? ? ? ×?? ? ×? × ??? ? × ? ? ????? ?? ?? ??? ?

??? ? ?× ?? ? ? ?? ??? ?? ? ?? ??? ? ?×? ? ? ? ? ? ×× ?? ?? ? ?? ?? ?? ×

??? ? ?×? ?? ? ? ???? ?? ? ?×? ? × ? ???? ×× ? ?? ? ? × ? ? ??

???? ? ??? ? ? ? ? ? × ? ? ? ? ×? ? × ? ?? × ?? ? ×? ? ?? ???? ? ? ?×?

??? ? ? ×???? ??× ? ? ? ??? ? ×× ? ?× ??

? ????× ×???? ??×? ??

???? ? ? ?? ? ?? ×?×? ?× ×? ??? ? ?× ? ? ? ×? ? ?? ???

× ?? ? ?? ? ??× ? ?? ? ? ? ? ??? ?? × ??? ?? ? ×

? ? ??? ??× ? ? ?? ? ??? ?× ? ?× ?? ? ??× ? ? ?

? ×???? ?? ??? ? ? ? ? ? × ??? ? ??× ? ? ?? ? × ?? ? ? ? ? ? × ? ????? ? ?? ? ×? ? ??

?? ? ?? × ? × ? ???? ?? ? ? ? ? ?× ?? ? ? × ? ×? ? ? ?×? ? × ?? ?? ? ? ? ×? ? ?? ×? × ?? ? × ??

? × ? ?? ? ? ??×?? ?? ? ??×× ? ?? ? ? ??? ????? ??× ? ??????

? ? ? ?? ? ? ??

? × ? ??? × ? ×??

? ? ? ? ? ? ??? ? ??? ? ? ????×

? ×? ? ? ?× ? ×?? ? ? ? × ? ?× ? ×? ? ? ?? ×?? ? ×? ? ? ? × ???

? ? ? × ? ????? ? ? × ?? ? ? ?? ? ? ?

??? ×× ?

? ×? ? ? ?×?

? ???? ?? ? ? ? ? ? ? ?? ?×? ×???? ?? ????× ? ×???? ?? ??? ? ? × ??? ×× ? ?

× ? ? ? × ? ? ? ? ×? ? ?? ?? ? ?× ? ×?

? ? ? ?? ? ?

? ?? ????× ? ????? ? ? × ?? ? ?

??? ?? ? ???? ?? ??× ?? ?? ? × ? ? ×? ?

?

×?× ? ?×? ?? ? ?

×? ?

?? × ? × ?? ? ? ??× ?? ? ????? ? ?

?? ? ?? ? ??? ? ?× ? ? ?? ? ? ??? ? ??× ? ? ?

× ? ?

? ??× ×? ? ?? ? ? ??× ?? ? ? ? ?

? ?? ? ?×? ? × × ?× ?? ? ?? ????? ? ? ? ×? ?

????? ? ?? ? ? ?× ×? ?? × ? ?× ??? ×???? × × ?? ?× ??× ??? ?? ? ? ???? ?× ? ??? ?

× ? ? ?? ???? ?? ? ?× ??× ???? ? ?? ? ? ??× × ? ? ×?? × ? ?? ??? ?? ? ? ? ?

????? ? ?? ? ? ?× ×? ? × × ? ?? ?? ??? ? ? ?×? ?× ??× ??? ?? ? ?? ? ? ?? ???

?? ? ?? ? ? ?? ×? ? ×? ×? ?? ? ??? ? ?? ? × ? ?? × ? × ? ?? ? ??? ? ? ?? ? ? ?? ? ?? ?? ?? ? ? ? ? ??? ? ? ?? ?

? ×?× ? ? ?× ? × ? ? ?????

? ? ? ?× ? ?× ? ? ×? ? ? ??? ?? ? ×? ? ?? ? ?? ? ? ?? ? ??? × ?

??? ? ? ??? ????? ? ?? × ? ? ? × ? ? ? ? ×? ? ?? ?? × × ? ? ×? ? ??? ×

??? ? × ? ?? ? ? ?×

? ? ?× ? ?

? ? ? ? ?× ? ? ? ?

? ? ? ? ? ?? ?? ? ?? ×?? ?× ? ?

?? ? ? × ?

??? ? ? ?× ? ? ? ? ?× ? ? ?? ? ? ?? ?? ? ? ? ? ? ?? ? ? ?× ? ??? ??? ??? ? × ?? ??×? ????? ? ?? ? ? ?× ×? ? ? ? ?

? ??? ? ? × ? ×? ? ? ?? ? ? ? ? ×? ? ? ? ? ? ? ? ?? ? ? ?? ?? ? ??? ? ?? ? ??? × ? ????? ? ?

? ×? ?

? ? ?× ? ?× ? ? ? ?? ? × ?× ?

? ? ?× ? ?× ? ??? ? ×

? ? ? ? ?× ? ? ??????? ?? ? ?× ? ?? ? ? ? ? ? ? ? ?× ? ?? ? ? ?? ? ? × ? ?? ? ? ?? ? ??? ? ?? ? ×× ? ? ? ? ?? ?? ?× ? ?????? ?? ? ?? ?? ? ? ×? ?? ? ? × ? ??? ×× ? ? ?× ? ?

? ? ? ? ??××? ?? ?? ? ??? ? ? × ?

× ? ? ? ? × ?? ? ???? ×× ? ??? ? × ???× ? ? ? ?? ×??? ?× ? ? ? ? ? ? ? ?× ? ? ?? ? ? ×? ? ? ?? × ? ?????? ?? ? ??× ?? ? ? × ? ??? ? ? ?? ? ?? ? ? ?? ??? ? ? ? ? ??

?? × ? ? ?

? ×???? ?? × ? ??

?? ? ? ? ?? ?

? ?? ×? ? ?× ? ??

??????? ×

? ?? ×???× ?? ?? ?? ×

? ? ? ??? ? ? ? ? ??? ??

?? ? ? ? ?? ? ? × ? ? ? × × ?????×? ?? × ? ?? ? ? ? ? ? ? ?? ? ? ? ×? ? ?? ? ×???×? ? ? ?? ? ×

?× ? ? ? ?

? ×???? ?? × ?

??? ? ? ? ? × ?? ??? ? ?× ? ? ??? ?× ? ? ? ? ?

× ??? ????× ?? ?? ?? × ???×???? ×???? ??×? ? ? ??

? ?? ????? ? ? ? ? × ? ? ? ? ×? ? ?? ??? ? × ? ?? ? ?

?

×

? ? ? × ? ????? ? ? × ?? ? ?

??? ×× ? ?

? ? ? ? ×?
? ×?? ? ? ? ? ? ×? ? ? ?? ? ? ??

? ?? ? ×???×
? ?? ?? ?? ? ??? ? ?? ? ??? ? ? ? ? ? × ?? ?? ? ?? ? ?? ? ? ? ? ? ? × ????? ? ? ? ×× ? ? ??? × ?×? ??? ??? ?? × × ? ?? ????? ??? ? ?? ? ??× × ????× ×??

? ?? ? ??? × ? ? ? ? ? ×? ??? ? ? ? ????? ? ?

×???? ×???? ??×?

? ? ?? ? ? ? ? ?? ? ? ??? ? ?× ? ×???? ? ? ?? ? ?? × × ?? ? ??? ??? ? ×? ? ?? ? ?× ?? ?× ??? ??? ? ?? ?× ???? ?

???? ? ? ? ? ? × ? ?? ? ? ? × ????? ? ? ? ???×???? ×???? ??×? ? ? ? ×? ? ? ? ? ????? ?? ? ? ? ??? ?? ? ??? ? ?× ??× ??? ?? ? ? ? ×? ?? ?? ? ????? ? ?? ?? ? ? ?? ? ? ?? ?? ? ?? ? ? ?? ? ×? ? ? ? ?? ? ?? ? ?? ? × ? ? ?? ? ? ? ? ? ? ? × ? × ? ??? ?? ? ? ? ?× ? ?× ?? ? ?? ?? ? ??? ? ?? ? ? × ? ? ? ? ? ? ? ?? ×× ?? ?? ? ×× ?? ?? ? ?? ?? ? ??? ?? ? ? ? ? ?? ??? ? ?×? ??? ? ?? ?? ? ??× × ?? ????? ? ? ?? × ? ? ?? ?? ×? ? ??? ??? ? ?? ×?

×× ?? ? ? ? ? ?×? ×?? ?? ???

? ?? ?? ? ? ?? ??? ?? ? ?? ??? ? ?× × ???

?? ?? ?? ? ?? × ? ???? ? ?? ? ?

?? ? ? ? × ? ? ?

? ?? ? ????? ? ? ??× ?? ? ? ?? ??? ?? ? ?? ??? ? ?× ?? ? ???? ? ?? ? ? ?? ??? ? ????? ?? ? ?× ? ?? ? ?

?? ? ??×? ? × ? ? ? ??? ? × ? ? ? ?? ??? ? ?? ×× ×? ×?

?×? ××??? ?? ×× ? ??? ×???? ? ? ?? ?? ?× ? ???? ?× ? × ? ? ? ?? ?? ?? ? ?? ? ?? ?? ? ?× ? ? ? ? ? ? ?? ?? ? ??×?

? ? ? ?? ? ??×

? ?? ?? ? ??× ?? ? ? ?? ??? ?? ? ?? ??? ? ?× ?? ??? ? ? ? ? ? ? ? ? ? × ???? ?? ? ??? ? ? ??? ?× ? ? ??? ? ×?

? ? ??? ?

? ?? ??? ?? ? ??? ? ? ? ? ?? ? ??× ? ? ?? ? ? ?? ??× ? ×× ? ? ? ? ??? ?? ? ?? ??? ? ?× ?? ? ? ? ?? ? ?? ? ?? ?? ? ?? ??? × ?? ? ?? ?? ? ? ? ? ?? ? ??× ? ? ??× ? ? ? ??× ?? ? ?? ?? ? ? ? ? ??? ? ???? ?? ? ?? ??? ×??? ?

? × × ? ? ??? ? ??? ? ? ? ? ×?

?? ??? ? ? ?? ??? ? ? ???? ??

? ?× ? ?? ? ? ?× ? ? ??? ?

?? ××? ? ?? ??× ? ×× ?? ? ?? ?? ? ? ?? ??? ?? ? ? ? ×? ??? ? ×? ?? ???? ??×? ?? ? ? ? ?? ? × ? ?? ? ? × ? ? ?? ? ??? ?? ?? ????

? ?? ??? ? ?× ?? ?? ? ?? ? ? ? ? ? ? ?? ?? ?? ? ?? ? × ?? ??? ? ? ? ? ?? ? ?? ×?×? ?×? ? ?× ? ×????

?? ? ??× ?? ? ?× ? ? ?? ????? ?? ? ??×? ?? ??? ? ? ?? ? ? ? ? ???? ??

? ?× ? × ?? ? ?× ? ? × ? ?? ×?

?? ??? ? ? ????? ? ? ??× ?? ??? ? ?? ? ? ?? ? ?? ×? ?? ? ? ? ? × × ??? ?? ? × ? ? ??? ? ?? ?? ?× ? ??

? ? ? ??? ? ? ???? ?? ? ??× ?? ?

? ??? ? ? ?? ???? ? ×? ? ? × ?? ? ? ?×?

????× ?? ?? ? ? ??× ? ? ???? ? ?? ? ????

? ?? ? ? ? ? ? ? ? × ????× ? ??? ?

? ? ? ??? ? ?

? ? ? × ×? ?? ? ?? ???? ? ?

? ? × ??? ?? ? ?? ? ? ?? ? ?

?× ? ? ??? ? ? ? ?? ?? ?? ? ?? ??× ? ? ?

? ?????× ? ×× ? ×???× ?? ? ? ? ??? ?? ? ?? ??? ? ?× ? ? ?? ? ?? ? ??×? ?? ? ? ? ???? × ×? ? ?? ? ?× ?? ? ? ? ? ? ? ?× ? ?? ?? ??? ×? ? × ? ???? ? ?? ?? ?? ? ?? ? ?? ×? ? ? ?? ×?? ?? ? ?× ? ? ? ?? ? ??? ?? ?

?? ?? ? ?? ? ?? ??? ? ? ?? ×?? ?× ? ? ? ? ? ?? ??× ?

? ? ?? ????? ? ? ?? ?? ×?

?? ? ??×?

??? ? ? ? ? ? × ?? ???? ? ?? × ? ?

? ?? ? ? ×?????? × ??

? ?
? ? ? ??

? ×???? ?? × ?
???? ? ? ? ? × ? ? ?? ???? ? × ? × ??? ?? ? × ?× ? ×? ??? ? ×???? ?? ?

???? ? ? ? ? ×
? ×× ? ??? ? ? ? ? ? × ?? ×??? ? ??? ? ?× ??? × ??? ?? ? × ?? ?? ? × ??? ?? ? ×?? ? ? ???? ?? ?? ? ?? ? ??? ?

???? ? ??? × ?? ? ?? ????

× ??? ?? ? × ? ? ??? ×? ?? ? ??

??× ?? ? ?? ? ?? ? ? × ? ? ?? ? ?? ??

×?×? ?? ? ? ? ?? ×? ? ? ? ?× ??
??

· ????

?

?????

?? ? ???? ?? ?× ?? ? ? ? ×? ? ? ? ?× ??×
??

· ???? · ???? · ????

? ×

????? ? ? ? ? ???

? ? ? ? × ?

?? ? × ?

???? ? ? ? ? × × ? ??? ? ??
? ·?

??× ?? ? ?? ??? ?

????? ? ? ? ????? × ? ?
? ?

·

?

? ??

?

?????
??? ??

? ? ? × ? ????? ? ? ?? ?? ? ? ? ?? ?? ? ?? ??? ?? ?? ? ?? ? ? ? ? ? ? ?·? ? × ??? ? ? ??? ? ?? ? ? ??? ??? ?? ? ? ? ? ? ×???? ?? ? ?????? ? · ? ? ? × ?? ?? ?? ? ?? ??×
? ·?

??? ???

?? ?

?

? ·?

?

·??

? × ? ×? × ? ? × ?× ? ??
?

????? ? ??? ?? ? ??× ? × ??× ×? ?? ? ? ?
??

? ?× ? ??? ??? ?

???? ? ? × ? ? ×? ? ?× ?? ??? ????× ? ? ? ×? ? ?? ?? ?× × ? ? × ? ? ? ? ? ? ? ? × ???? ? ? ? × ? ?? ? ??× ?? ? ? × × ? ×? ?× ?? ?× ? ? ????? ??? ? ????? ?? × ? × ?
?

? ?? ??×? ??? ?? ? ????? ? ×? ??? ? ? ?? ???? ? ??? ? ? ? ?? ?

? ? ????? × ?? ?? ? ? ??×? ?×?

?? ? ?

??? ×? ? ? ?? ????? ? ×???? ??× ? ? × ? ×? ×? ? × ? ? ×???? ??× ?? ×? ? ???×? ?? × ?

? ??? ? ??? ? ?? ?? ? ? ?? ? ? ?× ? ?

??? ? ??? ???? ? ×? ? ?? ? ? ?× ?? ? ? ? × ?? ?

×???? ?? ? ?????? ?? ? ?? ?? ?? ? × ? ?× ? ? ? ??? ? ×? ???? ? × × ??? ?? ???×? ? ? ? ? ? ? ? ?? ?? ? ?? ? ? ? ?? ? ?? ?? ? ??? ? ?? ?

??× ?? ? ?? ??? ?????? ??? ? ?? ? ? ? ?? ? ××???? ??×? ?×? ?? ?? ?

?? ? × ?? ? ??× ? ? ??? ? ? ??? ? ?× ? ? ?? ?× ? ??

×?? ? ??× ?? ? ?? ???? ?

???? ??? ??? ?

×???? ??× ?? ? ×? ? ? ? ? ?? ?? × ??? ? ×?

??× ?? ? ?? ??? ?? × ? ??? ×?

? ? ? ??? ? ? ? ??? ? ? ×? ? ?

? ???? ??× ?? ? ?

???

?×? ??

? ???????

?

? ×

?? ?

? ?

?× ?

??? ?×?

× ??

?? ??×? ?? ? ??????? × ? ?? ?? ? × ?

? × ?? ????? ? ? ?× ??? ? ? ?

?????? ? ? ? ? ?? ? ? ???? × × ? ?×

? ??????? × ? ×???? ??× ? ? ? ? × ×

?? ?× ? ??× ? ? ? ?? ? ?

???? ? ?? ??? ? ?? ? ?? ? × ?

? ?? ?

? ×? ??? ? ? ×× ? ? ?? ??? ??×? ?? ? ??????? ? ?? ? ? ×× ? × ? × ?? ? ×? ?? ? ?? ? ?

? ×? ?? ? ? ? × ?×??? ?? ? ?? ? ?? ???? ? ??? ?? ? ??× ???? ? ?× ??? × ???? ?? ??? ????× ?? ??? ×???? ?? ? ?? × ? ×× ? ×× ? ? ? ? × ? ??????? × ?? ?×?? ??? ?? ? ? ? ?? ×? ? ?× ?

? ?? ×???? ?? ? ?

? ? ?? ? ??× ? ?? ? ? ? × ? ? ??× ?? ? ?? ? ?×? ? ? ? ? ? ? ?? ×? ?? ? ?? ? ? ? ? ×???? ? ? ? ×? ?? ×× ? ? ?? ???×? ??? ? ? ? ? ? ???? × ? ×? ? ? ? ?? ? ? ? ? × ?? ????? ? ? ? ??? ? ?? ? ?? × ? ×?? ? × ?? ? ? ?? ? ? ×? ? ? ?? ? ? × ????? ?? ?? ×???? ??× ×? ? ?? ? × ×??? ? ? ?? ????? ?? ×? ? ? ??? ×???? ? ×× ?? ? ??× ? ? ? ?? ? ??×? ?? ? ? ?? ×???× ? × ???? ? ? ? ? × ? ? ? ?? ? ?? ×?×? ?× ? ??× ?? ? ?? ? ? ? ??? ? ? ? ???? × ?× ? × ?? ? × ? ? ? ?? × × ??? ? ??? ? ?? × ?× ? × ? ?? ?

??? ?? ??? ? ??? ? ? ? × ? ×? ??? ? ? ??? × ? ? ? ?× ? ? ? ?

? × ?? ? ? ?????? ?

? ? ?? ?× ? ??? ? ?× ? ? ??????? ? ? ?×? ? ? ? ? ? ? ? × ? ? ? ? ?? × ? ?? ×?×? ?× × ? ??× ? ?? ?? ? ×?×? ?×?? ×???? ? ? ? ? ? ? ? ? ?? ? ? ?? ?? ? ? ××

??? ????? ? ?? ?? ? ?? ? ??× ? ? ??? ? × ?? ? ? ? ?×?

?? ? ? ? ??× ? ?

? ???? ×

× ×? ?? ? ×× ? ? ?? ? ? ? ?? ? ?? ? ??× ?? ??

? ? ??? ? ??× ? ?× ? × × ? × ?

? ? ?? ? ? ?× ? ?? ? ? ?× ? ? ? ? ?× × ? ×? ? × ??× ?? ? ? ??? ? ?× ? ? ?? ??? ? ?? ? ??? ? ? ? ? ? ?? ?????? ? ?? ?? ?? ? ? ×? ? × ?? ??×? ?? ? ??????? × ? ×? ? ???? ? ?? ?

×???? ??× ?? ×?

?? ? ? ? ? ×?

???

?

? ×???? ?? ??

?

? ×

?×? ?? ? ??????? × ?

?× ?

?? ??? ?

??

? ×?

? ?? ?

??? ? ?

?? ? ?

??? ? ?????? ×???? ??×? ?? ? ? ? ? ? ??? ??× ? ?? ??×? ??? ? ??×? ?? ???? ?? ?× ? ?? ? ?? ??× ?? ?? ? × ?×? ?? ?? ? ? ? ? ?× ? ? × ?× ? ??? ?× ? ? ??? ? ? ?? ? ? ? ×?? ? ? ×???? ??? ? ?×? ? ×?? ?? ?? ? ? × ? ??×?? ? ×?? ?× ? ? ×? ? ? ? ?× ?? × ? ?× ? ? ???? ?? ?× ??? ×× ?? ???? ? ?× ?? ? × ??? ? ??×? ? ×???? ?? × ? ? ×? × ?? ?? ? ??? ? × ? ×? ? ? ? × ? × ?? ?? ? ? ??? ? ×? ? ×? ? ? ? ??? ?? ? ?? ??× ?? ×

? ??? ? ? × ×? ??

?? ? ??? ? ? ? ?? ? ?? ?× ? ? × ?

? ×? ? ?? ? ?

× ??? ?? ???× ? ? ???

?? ?? × ? ??

× ? ? ???? ??? ? × ?

? ??× × ? ×?

? ? ? ×? ?? ? ? × ? ? ? ? ? × ? ?? ?? ? ?? ×?? ? × ? ? ??

? ?? ? ?? ? ?? ? ? ?

???? ? ?? ????× ? ×???? ? ??????? ? ??×? ?? ×
??? ?????? ?? ? ??×

?

?????? ?? ? ?? × ? ????? ?? × ??? ?? ???×

??? ?? ??× ?? ? ?? ? ?×? ?? × ? ? ??? ?? ?× ? ? × ? ??

?× ? × ?? ?

×???? ??× ? ??? ?

? ??? ?? ?? ? ?????? ?? ? ??× ? ? ×???? ??? ?× ? ? ?? ?? ? ? ?? ?? ? ??

?? ?? ? ? ?× ??? ? ? ? ??

?????? ?? ? ?? × ? × ? ? ??? ? ? ? ? ? × ?? ??× ?? ? ?? ? ?×? ? ?× ? ???? ? ? ? ?? ? ?? ? × ?? ?? ? ? ??? ? ??? × ? ? ? ? ??? ×? ? ? × ??? ?? ×? ? ? ? ×??? ? ???? ? ? ??× ?? ? ?? ? ?× ? ? ? ? ? ?? ? ? ? ??? ? ?? ? ? ? × ?× ? ×? ×? ???? ? ??? ? ?? ?? ? ? ? ?? ? × ?? ?? ?

× ??? ????× ×???? ??×? ? ? ? ? ???? × ?????? ×???? ??? ? × × ?? ?? ? ?× ? ???? ?? ??? ? ? × ? ×?? ? ? ? ×???? ?? ×

? × ?? ? ? ?× ?? ????? ? ??? ? ?? ?? ? ? ? ??? ? ??×? ? ? ? ? ? ??? ?? ×?? ? ×?×? ? ? ??? ?????? ?? ? ??× ?? ??? ? ?× ? ? ? ? ?? ? ?? ? ?× ? ?????? ?? ? ??×? ? ??? ? ?× ? ?? ??

? ×? ? × ? × ?????

? ? ?? ?

??? ? × ?

? ×? ?

??? ? ?× ? ? ? ??? ? ? ?? ?????? ?? ? ?? ? ×? ? ? × ?? ?? ? × ??? ? ? ? ? ? ?× ? ?? ?? ? ? ? ? ?? ? ×? ?????? ?? ? ?? × ? × ? ?

??? ? ?

? ×???? ?? × ? ???

?????? ?? ? ?? × ? × ? ? ????? ? ? ??× ?? ?
?? ?? ?

??? ??? ?? ? ?? ? ?? ? ?? ?×?? ??? ? ?
? ×

?? ?

?

?× ? ? × ? ? ?

? ? ?? ×

? ×?

×? ? ? ?? ×

? ? ?? ?? ×? ?× ?

? ?? ? × ? ?? ??

? ×???? ?? ???? ?? ×? ??? ? ? ? ?? ? ? ?? × × ? ?? ??? ?? ?? × ? ????

? × ? ??× ?? ? ??? ?

? ? ? ?? ?? ? ×

? ? ? ?? ??×? ?? ? ? ×???? ?? ? ? ? ? ? ?? ? ? ?? ? ?? ????× ? ?? ?? ? ? ??? ? ×?? ? ? ? ? ??? ?? × ?

×???? ?? ?? ? ? ?×? ? ? ? ?? ?? × × ?? ?? ? × ?

? × ?? ?? ??? ?? ? ? ××? ?

? × ? ? ??

× ?? ?? ?? ? ? ?? ×???? ? ??????????? ×???? ??×? ?? ? ×?? ? ??? ? ? ?? ? × ??? ? ? × ? ? ??? × ??? ? ??? ? ? ??? ? ? ??? ? ?? ? ? × ×? ? ×???? ? ?? ? ?? ? ? ???? ? ×

? ? ?? ? ? ?× ? ? ? ? ????

? ??? ? ? ? ? ?? ? ? ?? ?

× ?? ????? × ?? ?? ? ? ??

??? ? ? ??? ? ?? ? ? × ×??? ? ? ? ? ×?

??? ? ×?? ? ?? ?? ?? ? × ?× ? ?? ?

? × ×? ?? ??? ×???? ? ? ?? ? × ? ? ?? ?

? ? ? × ?? ?? ?? ? ?×? ? ×? ?? ? ?? ?? ? ×? ? ?? ? ? ???? ? ? × ???? ?? ?

??? ?? ×× ?? ??? ?????× ?? ????? × ??? ?? ? ×???? ? ×× ? ?

? × ? × ??×? ? ? ? ? ?? ?? ? ?? ×?? ?× ? ? ×???? ??? ? ×?? ?? ? ? × ??? × ??? ? ? ?×

??? ? ? ×???? ??? ? ?× ? ? ?

? ×???? ?

? ?? ? ? ?

×? ? ? ???? ? ??? ?? × ??×× ? ??? ? ? ??? ? ??????? ? ?? ?

× ??? ?? ? ×? ?? ×

? ??? ?? × ?? ? ? × ? ?? ? ? ×? ×× ?? ? ??? ? ??×?

? ?? ? ?× ?? ? ??× ?

? ? ? ? ???? ? ?? ????× ? ? ? ?? ?? ? ?? ?

×???? ?? × ??? ×???? ? ?? × ??× ?

? ??? ? ?? ×?

?× ? ? ? × ??? ? ?? ??? ???? ?? ?× ? ??× ??? ? ? ×???? ?? ? ?? ? ? ?

? ?? ?? ?? ?× ? ?? ? ? ? ?

? ? ? × ??? ??????? ??? ?

?? ? ? ×???? ? ??× ? ?

? ?

?? ? ? ?? × ? ?? ? ×?

?× ?

? ??

?? ? ? ? ?× ?? ? ??????

???? ? ? ?? ? ? ? ?? ? ? ? ????? × ? ?× ??×? ? ? ? ?? ? ? ?× ? ?? ? ?? ??? ? ???? ?×? ?? ? ? ?? × × ? ? ?? ?? ? ?? ×? ??? ? ? ??? ×? ? ?? ? ?? ? ? ?

????? ×

? × ????? ? ? ?

? ?? ? ?

? ? ? ? ?????? ??? ? × × ? ?× ? ? ?? ?? ? ? ???? ?? ?×

? ?× ??×? ?? ? ? ? ? ? ??? ? ?? ?×??? ? ???? ?×? ?? ? × × ? ? ???? ? ? ? ? ???? ? ?? ?? × ?? ?? ? ? ?? ? ? ??? ?? ?? ?

???? ? ? ??×??? ? ?? ???

?? ? ? ? ?? ?? ? ?? × ???

× ?? ? ?? ? ? ?

?×? × ?×? ××? ?? ? ? ?? ? ?

?? ? ??? ? ? ?? ? ??? × ? ?? × ? × ? ?? ?

??? ? ? ??? × ???

?? ??? ? × ? ???? ? ? ?× ??×? ? ? ?? ? ? ? ? ? ?× ? ?? ?? ? ?? × ? ? ?

? ?× ? ? ? ? ? ? ? ? ? ? ? ×? ??

??? ? ? ×???? ??? ?? ×? ?? ? ??× ?? ? ?? ??? ?????? ? ????? ?? ? × ?? ? ?? ?

? ? ????? × ??? ??? ? ? ??? · ? ?? ? ????? ? ? ?? ?? ? ? ? ? ?× ? ? ? ??? ?? ? ? ??? ? ? ??? · ? ? ? ?× ? ??? ? ? · ? ? ? × ? ???? ?? ? × × ??? ?? · ? ????? ? ×? ??? ?? ? ? ?? ?× ? ?? ? ? ? ?

×

? ×? ?

?? ? ?? ???? ? ?? ?? ?
?

?? ?? ? ?? × ? × ? ? ???

?? ? ? ? ??? ?

?? ? ????? ? ? ?? ?? ?? ? ? ? ????

?? ? ·? ?? ?? ? ? ? ×

??? ? ? ??? × ?? ? ? ? ?? ×

?× ? ?? ????? ? ? ?? ? ?

? × ???? × ?? ?? ?

? ? ?? ?? · ?

?

?

??? ? ? ??? × ?? ? ? ? ? ?? ? ?? ? ? ? × ×? ??? × ??? ? ? ?? ? ??? ??? ? ×?? ? ?? ? ?????

?? ? × ? ? ? ? ? ? × ? ?? ?? ? ? ?× ? ??? ? ?

? ?? ? ???

??×??? ? ?? ?

??? × ? ? ? ?×? ? ? ? ? ?? ? × × ×? ? ×× ? ???? ? ??? ×? ? ?? ? ? ? ? ?× ?? ? ??? ????? ? ? ? ×? ? ? ? ? ? ??? ? ??× ? ? × ?? × ? ? ? ? ?? ? ?? ?? ?× ? ?? ? ??? ? ? ?? × ? ? ? ? ??×? ? × ??? ????? ? ? ? × ? ? ?? ×

?? ? ?? ????? ? ? ? ? ? ×? ? ??× × ? ?? ??? ? ? ? ?? ×

? × ? × ? ? ? ? ?? ? ? ??

?? × ? ???

? ?× ?? ? ???? ×× ? ???×? ? ?? ? ??? ?? ? ??

? ? ??×? ? ? ?? ?? ? × ? × ?

? ? ? ? ? ? ?? ? ? ? ?? ? ? ???? ? × ?×??

×

× ?? ?? ? ?????× ?? ???? ×

?× ? ? ??

? ? ? ???? × ? ? ?? ? ? ?????× ?? ???? × ? ?× ? ? ? ? ? ??? ?? ? ?? × ? × ? ? ? ? ? ? ? ? ?× ? ?? ? ? ?? ?×?× ?? ? ? ? ?? ? ? ?? ? ??? ?? ? ? ? ? ? ? ? ?× ? ?? ? ?? ??? × ? ??? ? ?? ? ???

×? ??? ? ?? ? ??? ? ? ? ???× ? ? × ??? ? ? × ????? ? ?? ? ?? × ?? ? ? ? ? ? ×?? ? ?? × ?

? × ? ? ??? ?× ? ? ? ? ??? ? ??? ? ?? ? ? ? × × ???×?? ? ??

? ??? ? ?? ? ? ? ?

? ? ?? ×? ? ×? × ??? ?× ??× ??? ? ? ×?

?? ??×??? ? ×? ? ? ? ? ?
??

? ? ?× ? ?? ?? ??? ? ? × ??

???? ? ? ??? ??? ? ? ? ? ?? ? ? ×? ? ? ? ? ? ?

?? ? ? ×? ? ? ? ?

? ? ? ? ?× ?? ? ? × ?? ?

? ? ? ×? × ?? ? ? ? × ? ?? ? ??× ??

? ? ? × ?? ?×? ?× × × ?? ?? ? ?? × ??×??? ? ?? ?
? ?? ?

??? ? ? ×???? ??× ? × ? ?

? ? ? ? ? ?????? ?

? ×

? ????? ? ?? ? ? ??? ×? ? ?× ? ?

?? ×

? ×? ??

? ?? ?? ?? × ?? ? ?? ?

?

??? ×

??? ?

? × ??×? ?? ? ??? ? ? ? ×? ? ?× ? ?

? ? ?? ?× ? ? ?

? ?? ?

?? ? ? ?? ?× ? ?? ? ×???? ? ×× ? ? ?

? ??×??? ? ?? ???

×???? ?? ?? ???? ? ??? ? ? ?? ? ×? ? ?×? ?

?? ? ? ?????× ?? ???? ???? ??? ? ? ??? ? ?? ? ? ?? ? ?? ? ? ? × ?? ? ??? ? ? ? ? ?? ?? ?

× ??? ?? ? ×? ?? ?× × ?×? ?? ???? ? ? ? ×?? × ?× ? ??? ? ? ?? ? ??×??? ? ?? ? ? ? ?? ?× × ? ×× ? × ???? ? ? ? ?? ? ×? ? ??? ? ? × ? ?? ??

?? ? ×???? ? ×× ? ??? ? ? ?? ? ? ?? ? ? × ? ??? ×?

??? ? ? ×???? ??

?? ? ? ×? ? ?? ? ?? ????? × ???? ?? ? ?? ?×?? ××? ? ×? ? ? ??? ?? ? ???? ? ? ? ?

?? ? ×???? ? ×× ? ??? ×? ???? ?? ×? ? ??? ? ? ?? ? ?? × ?? ? ?? ? ? ? ? ?? ? ?× ? ?? ? ? ??? ×

? × ? ? ? ×?

? ?× ??×? ? ?? ? ? ? ?

? ???? ?? ? ??

?? ? ?? ? ????? ×

? ?× ??× ?× ? ? ?? ×
??

? ?? ?? ?? ? ?? ? ??×? ? ? ?
?

? ?

?× ?

? ? ?

?? ? ??

?? ?

? ×?

× ? ?? ??

?

??? ? ?

? ??? ??? × ? ? ?

? ? ??????

?? ? ??×

? ? ?? ??? ??? ?? ? ? ? ?????? ? × ? ?? ?? ? ? ? × ? ? ? ? ×? ?? ?? ? ?× ? × ? × ×? ?? ? ?

× ? ?? ?? ? ?× ??× ???

?

× ?? ×

? × ?? ×??? ? ?? ?? ? ??

?? ? ??×? ??? ? × ?×× ??× ?? ? × ??? ? ?? ?×? ??? ? ????? × ?? ×???? ??× ?? ? ? × ?× ? ×? ?? ? ? ? ? ? × ?? ? ?? ? ?? × ?? × ? ?? ? ? ?? ?

? ? ?? ??? ? ?× ?? ???? ?? ×? ? ?? ? ? ?× ? ? ?? ×

??? ? ??× ?? ? ?? ? ?× ? ? ? ?????? ? × ? ???? × ? ?× ? ? ? ? ?

?? ? ??×? ? × ? ????? ?? ?? ??? ? ? ? ? ?? ×??? ?× × ? ? ? ? ?? ×???× ? × ? ? × ?×× ? ? ? ? × ? ? ? ? ×? ???? ? ? ? ?? ? ×? ? ?? ? ? ? ?? ?? ? ??× ??

??? ?? ? ?? ? ?? ? ?

??×? ?? ? ??????? × × ?? ?? ? ?? × ? ? ? ? ??? ? ? ??× ? ? ? ?????× ?? ???? × × ? ? ? ?? × ? ? ? ???

? ? ??? ? ? ? ? ×? ?? ? ? ?? ?

? × ?? ×??? ? ? ? ?????? ? ? ???

?? ? ??×? ?× ?

????? ??? ?? ??? ? ? ?? ? ?× ?

?? ? ??? ? ?× ?? ? ?? ? ? ?? ? ??×? ? ? ?? ? ?

? × ?? ×??? ? ? ? ?????? ? ? × ?? ×??? ? ? ? ?????? ? × ? ? ?? ×

?? ? ??× ?? ? ? ? ?? ? ? × × ?

? × ?? ×??? ? ? ? ?????? ?

? ?? ?? ?? ? ?? ? ? × ×?
?? ? ?? ? ??? ×

? ? ? ?? ? ??? ? ?? ????? ? ?? ?× ? ? ? ?

? ? × ??? ? ??? ?? ? ??? ? ? ?? ? ?

? ?? ? ? × × ? ??? ?

??? ? ? ? ? ? ?×? ? ?? ?× ??? ? ? ?? ??×? × ?? ? ?? ???? ?? ? ?? ??? ? ? ??? ?

× ???? ? ?? ?? ? ? ? × ? ? ?× ?? ?? ×??? ? ???? ? ??? ??× ? ??? ? ? ??? ? ×? ×?? ?? ? ?? × ?? ×??? ? × ?? ?× ??? ? ?? ? ? ??

?? ?? × ?? ?? ? ? ? ? ? ? ?? ? ?? ??

? ?? ? ? ? ??? ???? ? ? ? ? ? ?? ? ?

? ? ?? ? ? ? ?? ??

? ? ? ? ? × ? ? ?×

?? ?? ?? ? ? ? × ? ? × ?? ×??? ? ×?

? ?? ? ? ??? ??? ? ? ? ? ? ??? ? ?× ? ? ?? ?× ? ? ?? ? ?? ?? ? ?? ?× ? × ? ?? ? ??? ? ?? ? × ? ? ???? ??×? ? ? ? ?? ? × ??? ? ??×? ? × ? × ? × ??? ? ??×?

?×? ???? ? ?? ?? ? × ? ??×? ??? ? ?× ?

???? ? ? ? ? × ? × ? ?? ? ???

?? ? ?? ??? ?

? ? ?× ?? ? ? ×
?? ???? ? ??? ×

?? ? ? ?× ??×? ??× ????? ×? ?? ? ?? ? ? ??× ×?? ?

? ×??

? ? × ? ? ? × ?? ??? × ? ? ? ×? ?? ?× ? ? ???? ?? ? ?? ? ? ??? ?? × ? ? ? ? ?? ? ? ? ?? ? ×?? × ??? ? ?× ?? ? ×?? ? ? ? ?? ? ? × ? ? ? ??? ? ? ??? ? ? ?? ? ? × ?? ? ? ? ? ×?? ? ? ×? ? ? ? ? ? ? ?

? ? ??? ? ? ?? × ?? ? ??

??? ? ? ?? ??× ?? ? ?? ? ? ??? ?

?× ??? ? ? ?? × ????? ? × × ??? ?? ? ? ? ? ??? ?? ?? ?? ? ? ? ??×?

? ?× ? ?? × ? ?? ? ??×? ????? ? ? ?? ? ?× ×?? × ?? ?? ×?

??? ? ? ??? ?? ? ? ?? ? ? ? ?? ? ×?? ??? ? ×?? ? ×??? ? ??? ?

??? ? ? ?? × ??? ????? ?

×???? × ? ?? ? ?? ? ? ××? ?? ? ? ?? ? ?

? ?? × ?? ? ??×? ? ?

??? ? ? ?? ×??

? ? ? ? ? ? ? ? ??? ? ? ?? × ??? ??? ? ? ?? × ?? ? ?? ? ? ? ?? ? ? ? ? ?? ? ×? ? ×?? ?? ? ? ? ??

?? ? ? ? ? ??×??? ? ? ?? ? ? ?? ? ?? ? ?? ? ??? ×? ?? ? ? ? ?? ?

? ??×?

×?? ??

? ? ? ? × ???? ? ? ?? ??? ? ?? × ? ?

? ?? ??? ? ? ? ?×

? ×? ???? ?? × ? ??? ? ×?? × ? ? ? ? ??? ? ? ? ? ? ??× ? ? ×? ? ? ??? ? ×?? ???? ? ×?? ??? ? ?? ? × ?

× × ? ? ??? ? ? ?? ? × ??? ?

??? ? ? ×??

? ??? ?

???? ? ??? ??? ×? ? ? ? ?× ??×? ??×× ?? ? × × ? ? ? × ×?? ?? ×?

??×? ??? ? ??

? ??? ? ?? ? ??? ??? ×? ? ? ? ?× ??× ?? ?? ? ?? ???? ??× ?? ????

? ? ??? ? ? ??? ? ×? ? ? ? ?× ??×? ? ?? ×? ?????? ? ×?? ??? ? ?? ?? ? ?? × ?? ? ??× ? ?? ?? ?? ????×? ?? ? ??? ? ?

?

? ?? ? ? ?? ?

× ?

? ? ?? ?

?? ? ??

?? ?? × ?? × ???? ? ??? ? ? ? ??? ? ?? ???× ? ?? ?

??

?? ? × ? ? ?

? ? ? ×? ?? × ?× ? ?? ?

? ? ??? ?
? ?

? ? ??? ? × ???

???? ? ?? ? ??× ? ? ? ? ?? ?? ? ? ? ?? ? ?

??? ? ?? ? ? ??×

×? ?? ????? ?

? ? ???

? ? ?? ??? ? ?? ? ??×? ? ? ??? ?? ?× ? ?? ? ? ?? ? ?? ? ??×? ?

? ?? ? ??? ? ???? × ?

??? ? ?? ? ?? ? ?? × ???

? ?? ? ?? ? ??×? ? ? ? ???? ??? ??? ? ?? ? ?? × ??
? ?

? ?? ? ??? ? ???? ? ?? × ??× ?

???? ? ?? ? ? ??? × ??? ×
?

?

? ???? ? ?

? ?
?? ? ? ?? ?
?

? ??? ? ? ?? ? ? ? × ? ?? ?? ?? ? ?? ? ?? ?? ?? ?

× ? ?? ?
??

?? ? ?? ? ?? ?? ?? ? ? ? ?×? ?

×? ??????× ?

?? ?? ? ? ? ? ?? ? ? ?? × ?

× ?? ?

? ?? ×? ?????? ?

?

? ?? × ? ??? ? ? ?? ??× ? × ?

?? ? ?? ? ????? ? ? ???? ? ? ???

?? ?

?? ? ????? ? ? ???? ? ×
?

? ?
?× ?? ? ?? × ?? ?? ? × ?? ? ×?

?? ?? ??× ?? ? ? ?? ? ???? ?? ?? ? ? ?? ?

?? ? ? ? ? ?

? ?? ? ?? ? ??? ? ???? ? ? ? ? ??? ??? ? ?

?? ? ?? ? ? ??? ? ?? ???? ? ?? ?? ??× ?? ? ? ? ? ??? ? ?? ?? ? ? ?? × ? ? ? ? ? ? ×? ?? ? ? ? ?

?? ? ?? ? ? ?

???
×? ? ? ? ? ?? ??? ? ? ??×? ? ? ? ×?
? ???

? ?? ?? ? ? ??× ? ?? ? ?? ? ?? ?? × ? ? ??? ??? ? ?

?? ? ?? ? ? ?

? ? ? ? ?? ? ?? ? ?? ? ??? ?? ? ? ? ?? ? ?? ? ??? ? ? ??? · ? ? ?? ? ?? ? ?? ?· × ?? × ? ? ??? ×
· ???

? ? ?

??? ???

? ?

? ? ?? ? ? ?? ? ?
??

??? ?? ? ? ? ? ?× ?? ? ? ? ×
??

?? ? ?? ? ??? ? ? ?? ? ??× ? ?? ? ?? ? ? ? ?

???? ? ?× ?? ? ? ? ? ?×

?? × ? ? ? ??? ??? ? ?? ?? ??? ? ? ?? ? ??× ? ? ??

× ? ?? ?

?? ?

?

? ? ?

? ?

? ? × ?? ?? ?? ?? ? × ??? ? ×× ?? ?? ×? ? ? × ? ? ? ? ? ??? ? ? ? ? ? ??? ? ? · ??? ? ? ???? ? ? ??? ? ? ? ? ????? ? ????? ?? ? ? ? ? ?? ? ? ? ?? ? ? ?? ? ?? ?? ? ? ?? ? ?? ? ?? ?? × ?? ? ? ? ?? ? ? × ? ?? × ?? ? ? ?? ? ? ?
? ?? ? ?

× ?
? ?? ? ?? ? ? ?? × ?? ? ? × ?

??? ? ???

?

? ? ? ?? ? ?? ? ?? ?· ?? ?? ? ?? ? ? × ????? ? ? ? ?
?

? ???? × ??? ?

??? ? ???? ?

??

? ?× ?? ? ? ? ×

?? ? ??



??? ?? ? ? ? ?????

?? ? ?? ? ?? ?? ? ? ? ? ????
?

???? ? ????

?

? ? ?

×? ?

?? ? ? ? ?? ? ??? ? ?

?? ? ?

?? ? ?? ? ?? ?· ? ?? ?? ? ? ? ?× ???? ? ? ? ??? ???
??

? ? ?? ? ?? ?? ? ??

?? ? ?? ? ? ?

???? ? ? ?

? ?? ? × ?

? ???

?? ?
?? ?

? ???? ??? ? ? ? × ×?? ?? ?? × ???? ???? ? ???

?

×

?? ? ?? ? ? ?? ?
? ???

???? ? ?× ?? ? ? ? ?? ?
? ??

???? ?? ?? ?

? ? ?? ? ?? ? ?? ? ???? ×
? ??

????? ??? ? ? ?? ?
?

? ?

? ????

?× ? ?

? ??? ?? ?

?

? ?

?? ? ?? ? ? ×?

???? ? ??? ?? ? ?? ?? ?? ? ? ? ?×

? ???? ?? ?? ×? ? ? ? ?× ??? ?

?? ?? ? ?? × ?? ?

?? ? ??
??

?

? ??

?

? ???? ?? ??? ? ?? ? ??? ? ? ?? ? ?

??

??

?

??

? ?? ? ?? ? ? ?

?? ? ? ? ? ×

?? ? × ????× ?× ?? ? ?? ? ?? ? ?? ? ???? ×
? ??? ??

???? ? ???

? ????

?× ? ? ? × ? ? ? ×

?? ×??

? ?× ?? ?

?? ?? ? ?? ? ? ?? ?? ? ? ?? ? ?? ? ? ? ?? ? ?

?? ? ?? ?? ? ?
?

??? ?? ? ×

?? ? ?? ?

? ?? ? ?? ? ? ?? × ?? ? ? × ? ?? ? ?× ?? ? ?? ?? ? ??

?

???? ???
?

???? × ??? ? ??? ? ?×
?

? ?? ? ???? ?? ? ? ? ?? ?

? ? ???? ?

?

?? ? ?? ? ? × ×??

??? ???? ????? ?? ? ?× ? ????? ?? ? ?× ? ????? ??? ? ?× ?? ? ×?? ?? ? ?× ? ?× ? ???× ??× ? ?? ? ?? × ?? × ? ? ? ?? ?

?

???? ? ???? ? ???

? ? ? ?? ?

?? ? ?? ? ??? ? ×?? ???? ? ? ×?? ?? ? ? ?? ?? ? ??? ? ? ? ????? ? ??

??? ?? ?? ? × ? ?? ? × ?? ? ?

? ? ? ×? ? ? ? ?× ??×? ? ? ? ?? ? ?× ? ?

? ? ?× ??×? ?? ? ??× ? ? ?? ? ? ? ? ? ?? ? ?? ? ?? ??? ?? ? ??×? ??×? ×?? ? ? ?? ? ? ? ?
??

? ?? ? ? ??

?? ? ? ?? ??

?? ? ? ? ?? ? ?? ? ?? ? ? ? ? ?

? ?× ?? ?

? ???×? ? ??? ? ? ? ? ? ?? ?? ? ??

? ?× ?? ? ?? ? ????? ? ? ?? ?× ??×? ?? ? ??? ? ? ×

× ? ×?? ? ??? ? × ?× ??? ?? ? ? ?? ×? ? ? ??? ? ? ????? ? ? ?? ?? ? × ?? ? ?? ? ?×? ? ?×?? ? ?? ? ×? ? ??? ????? ? ? ?? ? ? ? ?? ? ? · · ? × ?? ? ?? ? ? ?
?
?

?? × ??? ? ? ?? ? ?? ? ×? ?

?? ? ??
??

?

??

??
?

?

? ?? ?

? ? ?

?

×

??? ? ? ? ? ? ? ? ? ??? ??? ?? ? ?? × × ???? ? ? ??
?

? ?? ? × ? ?
?

×? ? ? ? ? ?? ? ?? ? ?? ? ?

? ? ? ? ??? ? ? ? ? ?? ? ?? ? ? ?? ?? ? ?? ? ?? ? ×?? ?? ? ? ?? ? ?×

×? ? ? ? ?? ? ?? ×

?

??× ? ?

?? × ?

×? ?

?

?? ? ? ? ? ?×

?? ? ?? ?? ? ?? ? ???? × ?
??

?? ?? ? ?

?

? ? · ? ?× ? ?? ?? ?

?
?

??

??
?

?

? ? ?

?

×

? ?? ?

×

?? ? ? ×

?? ?? ? ?? ????× ?× ?? ? ?? ? ? ? ?? ×? ×? × ??

? ?? ? ?? ? ?? ? ?× ? ×? ? ×? ? ??? ? ? ×

×? ? ? × ??? ? ?

? ?? ?? ??? ? ? ? ? ???? ? ?? ? ?? ? ?

?? ? ?? ? ?? ? ?? ? ?? ? ?? ??
?

? ?? ? ??× ? ? ? ? ? ? ?? ?? ? ?? ??? × ??? ???? ? ? ? ???
?

×

??

?

?? ? ??
?

??

?

?

? ?? ? ? ? ?? ?? ?? ×????× ? ? × ??? ×? ×? ? ? ? ×? ? ×? ? ×? ? ? ? ?? ?

? ?? ? ?? ? ?? ?

??? ?? ? ? ??× ×? ?? ?? ?

?

?? ??

×?

?? ?? ?? ?

? ? × ? ?? ??? ? ?? ? × ? ? ? ??? ? ?? ? × ??

? ? ??? ? ?? ? × ?? ?? ?

? ?? ?? ? ??? ×? ?

?? ? ?? ? ? ?? ? ?

?? ?

? ?? ?? ?? ?? ?

? ? × ? ?? ??? ? ?? ?

? × ? ??? ? ? ?? ??× ??? ? ?? ? ? ??? ???? ? × ? ?

× ? ??? ?

×? ?

?? ? ?? × ? ??? ? ?? ? ?? ??? × ? ×? ? ?? ?
? ?

?

??? ?? ?? ? ? ?? ? ?

?? ? ??? ?? ?? ? ? ?· ? ??× ×? ?? ?? ?? ?

??

??? ?? ?

? ?? ?? ? ??

?

??

? ? ?? ?? ?? ? ?× ? ? ?? ? ? ????

? ? ? ??? × ?

?

????
?

??

? ?? ? ?

??× ×? ?? ?? ?? ?

?? ?

? ?

×?

?? ? ?? ? ???? ? ? ??

?

??

? ? ? ? ? ? ? ? ×

???×??? ? × ×? ? ? ?×? ?? ? ? ?

?? ? × ?? ??? ? ×?? ? ? ?????? ? ????

×? ?

?

? ? ×? ?? ??

?

???

?? ??? ? ? ×???? ??× ?

? ? ??

?? ? ?? ?? ??? ? ??? ? ×?? ?????× ? ? ? ? × ? ?? ?? ? ? ? ? ?? ??? ?
?

? ? × ? × ??×? ?? ? ? ?? ?? ?? ? ??? ? ×?? ?? ?

× ? ? ? ??? ? ?× ? ? × ? ? × ? ???? ×?? ??

? ?? ?? ?
? ? ?

? ? ? × ?? ???

?? ??× ?? ?

?? ? ×

× ??? ×? ? ? ?? ? ? × × ?? ×??? ?
? ? ? ???

?? ? ?? ? ? ?? ? ?? ? ?? ? ???? ?? ? × × ? ? ? ? ? ????? ? ??

?? ? ?? ?? ?? ? ?? ? ? ? ? ?? ?

????? ? ? ?? ?? ? ? ?

???

????? ?? ?? ? ??? ? ? ? ? ×

? ? ??? ? ??? ? ??? ? ? ?? ??× ?? ×? ?? ? ??? ? ?? ×?? ? ? ? ??× ?× ? ? ??? ? ??× ???

????? ? × ? ?× × ? ? ? ? ? ? ?? ???? × ?

???? ??? ?? ? ??? ? ? ? ??? ? ? ?? ? × ??? ?? ? ? ? ? ?? ?

??? ?× × ? ??× ? ??? ×? ? ? ? ?× ??× ?? ?? ? ? × ? ? ? ×? ? ? ? ?× ??×? ? × × ??? ×? ×???? ?? ? ?? ? ×???? ? ?? ? ?????× ?? ? ?? ? ??
?

? ? ?

? ??? ×???? ??? ?? ? ?? ????? ? ??? ? ? ? ??? ?? ? ? ??× ? ? ??? ?? ? ? ? ? ?? ? ? ? ? ? ??? ? × ??? ? ? ?

??×? ?? ? ? ? ?? ?? ? ? × ???? ?? ? ×

? ? ?? ? ?? ??

× ? ? ? ? ?? ? ?? ? ?? ?? ? ×?? ? ? ×? ? ? ??×?

?? ?? ? ?? ?? ??? ? ?× ? ? ?×? ×?? ? ? ?? × ?? ?????? ??? ? ?? ? ?? ?× ? ?

??? ? ?? ? ×?? ?? ? ??

? ? ??× ?

? ? ? ? ? ?? ? ?? ?? ? ?? × ?? ? × ?? ?? ?

×? ?× ? ? ? ? × ???

? ? ??? ? ?? ? ????

? ?? ???? ?

????? ?? ? ?

??? ? ?? ? ?? ·? ?? ? ?? ? ?? ?

??

? × × ? ?? ? ? ????? ? ?? ? ? ? ??? ? ?? ? ?? × ????×

????? ?? × ? ? ? ?? ?

?? ?

×

????

?

? ? ??× × × ?? ?

? ? ? ? ?

? ????? ? ??? ?? ? ?? ? ???? × ×?? ? ? × ? ?? ? ? ? ?? ? ?? ? ???? ??? ? ?? ? ?× ? ? ?? ×? × ? ? ×? ?????? ? ?? × ??× ? ?? ?

?? × ?

? ? ? × ? ?? ? ???

? ?? ?? ? ? ?? ? ??

? ?? ??? ??? ? ? ?? ?? ? ×??? ×? ?? ?? ? ??? ? ? ?? ?? ×? ?×? ??? ? ? ? ?? ?? ???×? ????? × ? ? ????? × ?? ? ??×? ? ? ? ?? ? ????? ??× ? ? ? ? ???
?

? ??? ? ? ? ? ? ? ?? ??
?

? ?? ?? × ?

? × ??? ?

? ? ? ??
?

?

?? ?? ? ?

??

? ?? ?? ? ? ?? ? ??? ? ? ? × ? ?? ? ?? ? ????

???? ? ? ? ?

? ? ?? ? ? ?? ?? ????? ??× ? ? × ? ? ???
? ?? ? · ?? ? ?

?? ? ??? ?? ? ??? ? ? ??? ×? ? ? ? ?× ??× ? ?
?

·

?? ?

· ?? ?

??
?

?

× ?? ? ? ?? ??
?

· ?? ? ? ?

? ?? ?
?

??? ???? ? × ?
?

??

? ?? ?
?

? ?
?

?

? ?? ?

?

? ? ?? ? ?? ? ?? ? ?? ? × · ?? ? ? ?? ?

? ?

??

×?

????? ?? ? ? ?? ?? ? ? ???? ? ? ? ?? ?? ???? ? ? ?? ???? ?? ? ?? ? ? ? × ? ?? ? ??? ?? ? ?? ? ???? ? ? × ?? ?× ?× ?? ?? ?? ??? ?? ? ?? ?? ???? × ? ? ? ? ?

? ?? ? × ?×? ???? × ? ?? ? ? ?? ?? ? ? ×?
?? ??? ? ? ?

? ?? ?? ? ? × ? ? ?? ? ?? ? ?? ? ? ? × ??

? ?? ×

? × ×? × ? ?? × ? ??? ? ??? ?? ? ?? ? ? ?? ??× ?? ??

× ?×× ?? ? ??? ? ? ? ? ? × ? × ? ??

? ?× ?? ? × ? ? ??× ?? ? ?? ? ?
??

· ???? ?

?

? ?? ?

? ?

?

×?

??× ??

?? ?? ?? ? ?× ?

??? × ?

??? ?? ? ??? ?? ? × ? ?

? ?? ???? ×?×? ? ?? ? ? ??? ?

? ??× ?? ? ?? ? ?× ? ? ?? ? ??× ? ? ? ? ?? ? ×? ? ? ? ?? ×???? ??× ? ? ? ? ??? × ?

?? ? ?? ? ??× ?? ?? × ?? × ? ? ? ? ? ? × ? ×???? ?? ? ? ?×

??? ?? ? ×? ? ? ?? ? ×?? ? ? ??

× ??? ?? ? × ?? × ?? ?? ??×

× ??? ?? ?? × ×× ?? ??? ? ? ?? ? ??? ? ?? ? ×? ? ×? ? ? ?

???? ? ? ? ??? ?

× ??? ?? ?? ????× ×???? ??? ? ?× ???

×???? ?? ??? ? ×× × ??? ? ? ? ? ? ? ?? ? ?? ? ??× ?? ??× ?

? × ? ? ??? ×???? ? ?? ?? ? ×× ? ? ?? ? ×? ??? ? ? ?× ???

? ? ??? ? ? ?? ×???? ?? ? ×?×? ? ?????? ?? ? ?? × ? ??? ? ×???? ??? ?? ????× ??? ? ? ? ? ? ? ?? ? ? ??? ??× × ????× ?? ?? ??? ? ×???? ??? ?? ? ??? ? ? × ? ? × ? ? × ?× ?? ×???? ?? ? ?× ?? ? ? ? ?????? ?
?

? ? × ? ? × ?× ?? ×???? ?? × ?

? ?× ? ?× ??? ??× ×? ??

?? ? ?× ??? ? ? ×× ? ?? ?× ?? × ? ? ?? ? ?? ? ?? ?

· ? ? ??

?

? ??? ? ×???× ?

?? × ? ? ?? · ? ? ??? ? ×? ? ? ?? ?? ? ?
??

?
?
?

? ?? ? ? ?? ? ?? ? ?? ? ? ???? ? ?× ??? ? ? ?? ? ? ×???? ?? ? ?? ??× ?? ? ?? ? ?? ? ? ? ???

?? ?

?? ? ??? ? ?? ? ?

· ? ????

?

×

× ? ? ??× ?? ? ?? ? ?? ? ?× ? ?? ×? ? ? ?? ? ? ? ?????? ? ?? ?? ?

??? ×??? ? ? ?

?? ? ??× ? ??× ?? ? ?? ? ?×? ? ?? ? ? ? ×???? ?? ? ??

??× ?? ? ?? ? ? × ?

×???? ?? ?? ? ? ?????? ? ?? ? ?? × ? ??? ? ? ?× ?? ×???? ?? ? ? ? ???? ?? ? ? ???

?? ? ??? ??? ?× ???

×???? ?? ?? ? ? ?????? ? × ??? ?? ?? × ?

? ?? ? × ????× ?× ?? ?? ?? ??? ?? ? ??× ? ??? ? × ? ?

?×? ?? ? ??? ? × ?

? ? × ??? ?? ?? ? ??×? ?? ? ??×

? ? ? ? ?? ×???? ??× ?? ? ? ?????? ? ? × ? ? ??? ×???? ? ?? ? ??? × ??? ?? ?? ???? ×× ?

×???? ??× ?? ? ? ?????? ?

??? ×??? ?

??× ?? ? ?? ? ? ×???? ??

? ???×

?? ?? ? ???? ? ?×? ×???? ??× ??× ?? ? ?? ? ?× ??? ? ?

?? ?

?? ? ?? ? ?? ? ? ??? ??? ??? ????×? ????? ?? ×???? ??×? ?? ? ? ? ? ?? ×???? ?? ?? ?? ? ?? ? ?? ?? ? × ?× ?? ×???? ??× ?? ? ? ?????? ? ? ??× ?? ? ?? ? ?? ? ?? ? ?? ? ? ? ?? ? ? ? ? ? ?????? ? ?? ? × ? ? ? ? ? ? ???? ?? ? ? ?×? ? ??× × ??? ?

??? ???? ? × ?

× ?? ???? ? ?????? ?? ? ?? ?? ?

? ?× ???

?? ? ??× ? ? ??×? ?????×

? ? ? ?? ?

? ?× ??? ? ? ? ?? ×???? ??? ?? ? ?× ? ??? ? ?? ? ?? ? ?? ?

? ??? ??????? ??×? ? ? ? ?? ? ? ??× ? ?? ? ??× ?? ? ?? ? ?× ?? ? ? ? ??? ? ? ?? ? ? ?? ?

?? ? ??? ? ? ? ? ? × ? ? ??×? ???? ? ?? ??? ? ? ?× ? ? ? ? ?? ? ??× ?? ??×??? ? ??? × ?? ? ??× ?

? ? ?? ?? ? ? ??? ? ? × ? ??

? ×? ? ? ? ??

??× ?? ? ?? ? ?× ? ? ? ?????? ? ?? ? ??× ? ? ?× ? ? ? ? ?????×

?× ? ???? ? ?× ??×? ? ?? ? ? ????? ?? ? ? ? ??? ? ? ×???? ?? ? ? ??? ? ? ?

? ?× ?? ? ? ?× ?? × ??? ? × ???? ? ? ? ? ? ? ??? ? ? ?× ? ? ??? ? ??× ?? ? ?? ? ?× ?? × ?? ? ?

? ? ? ?????? ?

?? ? ??× ?× ? ?? ?? ? ? ? × ??? ? ? ?

???? ? ?× ?? ? ? ? ?? ×??? ? ? ?? ?? ?× ? ?? ? ?? ? ×? ? ? × ? ? ? ? ??× ?× ? ×

×? ?? ? ? ?? ? ???? ? ? ? ? ? ?? ? ? ?? ?? ?

? ×× ?? ??? ?????× ?? ???? ? ??? ??????? ? ??? ? ? ×???? ?? ? ??× ?? ? ?? ×???? ×? ??×× ? ? × ????? ? ? ? ? ? ? ? × ? ??? ? ??? ? ??? ?? ? ? × ? ?? ? ? ? ? ? ? ??××

? ??×??? ? ?? ???? ?

× ?? ????? ??? ? ? ??? ?? ? ??× ?× ? ? ?? ? ??? ? ? ??? ? ?? ? ?? ? ? × ? ??? ??? ? ? ? ? ? ? ? ?? ??? ×

??????? ? ?? ???? ??×? ? ??×??? ? ? ×× ? ? ?????× ? ? ??? ??? ? ?? ?

? ?? ? ? ? ? ?× ? ? ? ? ? ? ? ? ? ? ?? ? ??? ?????

??? ? ? ??? ?? ? ??× ? ?

× ? ? ? ? ?? ? ? ? ?? ? ??×?? ? ? ? ×

?? ?? ? ? ? ? ?? ?? ?? ? ?

? ×? ? ?× × ?? ? ?? ? ×???? ? ??× ? ? ? ?? ?? ??? ? ? ? ? ? ? ?? ? ? ?? ? ?

??? ? ?? ? ? ?? ? ? ????? ? ? ??× ?? ???? ?

?? ????? ? ? ??×? ? ???× ?

× ??? ?? ??? ? × ? ? ? ? ? ? ? ???? ?? ?? ? ? ????? ? ? ??× ? ?? ? ? ? ?? ? ? ? ?? ? ? ?? ? ? ×??? ? ???? ? ?? ? ??× ? ? ?? ?

? ??

??? ? ?? ? ? ?? ? ?? ? ?? ? ? ? ? ?× ???? ?? ? ? ????? ??? ?? ?? ? ? ? ? ????? × ? ? ? ?

????×? ?? ?? × ? ? ×???? ? ??× ? ? × ? ? ?? ???? ?? ?? ? ?? ?? ? ? ?? ? ? ???? ?? ??? ? ?? ? ? ?? ? ? ?? ?? ?

?? ? ??? ? ? ?? ? ?? ???? ?? ?

?× ? ?? ? ?? ? ? ? ? ? ????? ? ? ? ? ??? ? ? × ?? ? ?? ?? ?? ? ??×? ?? × ? ? ?? ? ?

??? ? ? ? ? ?? ?

?? ? ? ×???? ? ??× ? ? ? ??

? ? ?????? ? ? ? ?? ?

? ? ?????? ? ? ?? ?? ?? ? ?? × × ?? ? ?? ??? ? ??? ? ??×? ? ??? ? × ??? ×? ? ?? ??? ? ?? ? ? ??? ? ?? ? ? ? ?? ? ? ?? ?

? ????× ??? ?? ?? ? ?

? ?? ?× ?? × ? ? ? × ?

??? ? ? ????× ? ??? ? ? ? ?? ? ? ? ? ?? ?? ? ????

× ?? ×??? ? ? ? ? ?????? ? ? ? ? × ? ?? ? ?? ×???? ?? ??? ??× ???

? ? ? ? ×???? × ? ?? ?

?? ? ? ×???× ? ? ? ??? ??? ?

× ??? ????× ?? ?????? ?? ? ?? ? ?? ? ? ? ? ? × ?× ? ? ? ?? ?? ? ? ? × ?× ? ? × ? ? ? ?×

?? ? ? ??× ? ?

?? ? ? ? × ? ×? ? ?

??? ? ?? ? ? ??× ? ? ???? ? ?

? ?? ? ? ??? ? ?? ?? ? ?? ? ? ? ?? ? ? ? ?×? ? ? ?? ? ? ? ?? ? ?? ? ? × ?? × ? ?? ??? ? ??? ??? ? × ? ??? × ?? ??× ?

??? ? ? ????×

? ?? ?

??? ?? ? ? ?? × ??? ? ? ? ? ? ?

? ? ? × ? ?? ? ?? ??? ? ? ?? ?? ? ?? ?

? ?? ? ??? ?? ?

? ???? ? ???? ? ?????× ??? ? ? ?× ? ? ? ?× ? ? ? ? ?? ? ×???? ×?

? ??? ? ? ? ? ? × ? ? ? ? ? ? ? ×? ? ?? ? ? × ??

? ? ? ? ? ? ?? ?? ? ?? ? ??××? ?? ?? ? ?? ????? ? ??? ? × ×?? ?×? ??? ? ?? ? ? × ? ×??

?
???

? ??? ? ? ? ? ? ? ? ?? ???? ? ? ??? ? ? ?×?

? ?? ? ? ×? ? ?? ??

? ? ? ? ? ? ??× ? ? ?? ? ??× ? ? ? ×? ??????? ?? ? × ? ? ? ? ??

? ?? ?? ? ?? ? ? ? ? ×?? ? ??? ? ? ×? ? ? ×?? ? ??? ?? ? ? ??? ? ? ? ? ? ? ? ? ? ?? ?? ×? ?? ??? ? ?? ??? ? ?? ? ????? ? ×???? ??× ?? ? ? ?????? ?

? ? ?? ??× ? ? ? ?? ? ??× ?? ? ?? ? ?×? ?××?? ? ? ?

?? ? ? ? ?? ? ? ? ? × ? ????? ?? ?? ?? ×??? ? ? ? ?? ??? ? ? ? ???? ?? ?× × ? ? ? ×? ? ?? ? ? ? × ?× ×? ? ? ? ? ? ??? ?? ??? ? ?? ? ? ×? ? ? ? ? ?????? ? ?? ? ?? ? ?? × ??? ????× ?? ?????? ?? ? ?? ? ? ?? ×? ?????? ? ? ? ×?? ?× ? ?? ? ? ?? ? ×? ? ? ?? ?? × ?? ? ? ?? ? ??? ? ??? ??? ? × ?? ? ? ? ?? ???×?

? ? ? ? ? ? ?? × ? ? × ??×× ? ?? ??×??? ? ? ? ? ×? ? ? ? ? ? ?? ?? ?? ? ? ×? ? ? ??? ??? ? ? ?× ?× ? × ? ? ? ? ? ? ?×? ? ?? ?× ?? ? ??

?? ? ??? ? × ? ?? ? ? ? × ?? ?? ??×? ??? ? ? ?? ? ? × ? ?? ? ? × ? ? ?

????? ? ? ????? ??? × ?

? ?? ?? ? ? ?? ? ? ?? ????? ? ? ? ? ? ??× ? ? ?? ? ? ? ?? ? ??

? × ? ? ? ? × ?? ? ??? ?????× ?? ? ??? ? ? ? ? ×?

? ?× ?× ? ×? ? ? × ? ? ? ? ??? ??

×× ? ? ? ? × ? ? ? ? × ? ? ? × ? ?? ? ?? ×? ??? ? ? ? ×? ? ???? ????? ?

? ? ?? ? ? ? ? ? ? ? ? ?? × ?? ?? ? ×? ? ? ? ??? ? × ? ??? ?? ??×? ?? ×? ? ?? ? ?? ?× ?

???? ? ? ? × ? ? × ?× ?? ×???? ?? × ?? ? × ? ? ? ×? ?? ?×? ??? ??? ? ? ? ??? ×

? ??? ?? ? ? ? ? ? × ? ? × ?× ?? ×???? ??× ? ? ? ? ? ? ? ? ×? ×? ?? ? ? ×?? ? ? ? ? ??? ? ?? ? ? ? ? × ? ?? ?? ? ×?? ? × ??? ? ? ? ? ?? ? ? ? ? ?? ??? ? ?

? ?? ? ? ? ? × ? ? ? ? × ?? ? ?? ? ?? ? ? ? ×?? ? ??? ?× ? ? ??

? ? ? ×? × × ? ??? × ? ?? ? ???? ? ?? ?× ? ? ? ? ? ×? × ? ? × ? ? ? ? ? ?? ? ? × ??? ×?? ?

?? ?? ??? ? ? ? ??? ? ?

?????? ? ?? ? ?? ? ?? ? ? ??? ?× ? ? ??

? ? ? × ? ? ? ? ? ?? ? ???? ? ???

? ??? ? ? ? ? ? × ? ??? × ? ?? ???

? ? ? ×? × ? ?? ? ? × ?? ? ? ?

??? ? ? × ?× ?? ×???? ??? ? ? ? × ? ? ? ? × ? ??? ? ? ? ?? ? ?? × ? ? ? ? ? ?? ? ? ? ×? × ? ?? ? ? ×??? ? ??× ? ? ×? ? ? ?? ? ?? ???? ??×× ? ? ×× ??? ????? ? ? ? ? ? ?× ?? ? ???? ? ? ?? × ??× ? ? ? ? ? × ?× ? ? ??? ? ? ?? ? ?? ? ×× ?? ? ??× ?? ? ? ×× ?? ?

? ??? ???

?? ?? ? ? ???? ×× ? ?? ???? ?? ???? ×??

? ×× ??? ????? ? ??× ?? ? ??? ? ? ? × ? ? ? ?? × ?? ? ? ? ?

? × ? ?? ? ×?

? ? ? ×? × ?? ?? ? ? ? ? ? ??

? ? ? ×? × ? ? ? ?

?

? ???? ×? ?× ??? ?

?? ??

???×??? ?

???? ? ??× ? ?

?? ? ?? ? ?? ???? ? × ? ? ? ×? × × ?

? ? ? ×? × ? ? ? × ? ? ? ? ?? ??? ? ? ?? ? ? ?? ??? ×??? ? ? ?? ? ? ? ? ? ? ? ?? ? ?? ? ? ? ?? ?? ? ? ? ?? ???×? ??? ? ? ×× ?? ? ? ??? ?? ? ? ? ??? ? ?? ? ?? ? ×?
? ?? × ? ? ? ? ?×

× ?? ? ? × ? ? × ?× ?? ×???? ??× ? ? ? ? ??? ??? ? ? ? ? ? ? ?? ?? ?? ? ? ? ? ? ? ? ×? ? ?? ? ? ?? ? ? × ? ? ×× ??×× ××? × ××? ? ??? ? ?? ××?

? ? ? ?? ? ? ? ? × ? ?? ? ?? ?? ? ? ? ?? ? ? ? ×? ? ? × ??? ? ? ×× ? ?? ? ×? ? × ? ? ? ? ? ? ×? ? ? ?

? ? ? ? ? × ? ? ? ? ×? ?? ? ?? ? ? ?? ? ? ? ? ?? ?

? ?? × ? × ?? × ?? ? ? ? ??

? ? ? ? ?? ? × ? ? ? ???? × ???? ? ? ? ? ? ? ?? ? × ??×× ?? ? ? × ? ? ??? ???

?? ? ? ? × ? ? ? ×?

????× ? ??

? ?? ??? ? ? ? ?

? ? ? × ? ?? ? ?? ?× ? ?

? ??? ? ?? ?? × ?? ? ? ×

?????? ? ?

???? ?

??×? ?? ??? ?? ?× ? ? ? ??? ? × ?? × ×? ? ?

???×??? ?

?? ???× ????? ?

?? ?? ? ???

? ?× × ? × ? ? ×??× ? ?

???? ×× ? ???? ??? ? ? ?? ??? ?? ? ???? ×× ? ??? ? ? ×? ? ? ? ? ?× ?? ?? ? ? ?? ? ? ? ?? ? ?? ?? ?? ? ??? ? ? ×? ? ?? ? ? ? × ? × ? ? ? ? ??? ??? ? ? ?? ?×? ??× ? ? ?

? ? ? × ? ?? ? ?? ?? ? ?× ? ?

?? ? ??× ?? ?? ? × ???? ×× ? ???? ?

? ?? ?? ? ?

??? ×??? × ?? ? ?? ? ? ?? ? × ? ? ? ?? ???? ×× ? ?? ×? ? ? ?? ? ?? ?? ? ×

? ? ? ×?? ?

×??? ??× ?× ?? ? ??× ? ? × ? ? ? ? ? ??× ×? ??×× ? ? ?? ? ??? ?× ? ?? ? ?? ?

? ? × ? × ? ? ? ?? ? ?

?×? ??× ??

? ? ????? ? ? ? ×

?×? ?? ? ? ??? ??? ???? × ? ? ? × ? ? ? ? × ? ?? ? ? ??× ?? ? ? ? ?? × ?

? ? ? ??? ?? ?? ??? ?? ? ??× ?×? ?? ? ? ? ? ? ? ?? ? ? ?? ? ?? ? ??? ? ??

?×? ?? ? ? ? ?? ?? ? × ? ?

? ? ? ?? ? ? × × × ?? × ??? ?? ? ×?

? × ?? ? ×

?? ???? ? ???? ×× ? ???× ?? ???? ×× ? ???× ? ?? ? ?? ×?? ? ? ?? ? × ?? ? ? ?

? ??×? ? ? ?? ? ?? ?? × ? ? ?? ? ??×× ? ??? ×? ??×

?

?? ?

? × ? ? ? × ?? ???? ? ? ? ?? ? ? ??×? ×× ? ? ???? ? ? ?

?

? ?? ? ??× ?? ?? ? ?

? ?? ? ??× ? ?? ? ?? ×?? ? ×?? ??? ?? ×? ? ? ×? ? ×? ? × ? ??? ?? ? ? ? ×?

? ? ? × ? ? ? ? ?? ??? ? ?× ????? ? ?? ?? ? ? ?? × ??×× ? ? ???

?? ?? ? ? ?× × ? ? ????? ? ????? × ? ???? ×× ? ???? ? ? ?? ?? ? × ??××? ? ? ? ?? ? ? ? ?? ? ?? ?? ? ? ? ????? × ?? ? ??× ? ? ?× ?? × ? ?? ? ?× ? ? ? ?? ?? ××?? ?? ??? ? × ?? ? ?? ? ? ? ???? ? ?× ? × ? ? × ?× ? × × ??? ????× ?? ? × × ??? ????× ?? ?? ? × ? × ? ? ?? × ?? ?? ?

?? × ? ? ×??

? ?× ?? ?? × ? ×

??? ? ? ?× ×? ?

?? ×? ×? ? ?? ?

? ? ? ? ??

?× ? ?

? ? ? ? ?? ?? ? ??? ?

????? ? ?? ? ? ?? ?? ?? ? × ?????×

? ? ? × ? ? ?? ? ? ? ?? ??? ??? ? ?× ×?

? ? ? ?× ? ? ?? ??? × ? ? ?× ? ??? ?? ??? ? ? ??

× ???? ? ??? ?? ? ? ???? ×× ? ???×? ? × ? ?? ? ? ? ??? ???? ? ×??? ? ? ? ? × ? ?? ? ??×? ???? ???? × ?? ? ? ??? ?×? ×? ??? ?? ? ? ?? ?? ??? ? ×? ? × ? ? ? ? × ?? ? × ? ? ? ? ×?? ? ? ???? ? × ?????? ? ? × ???? ? ???

? ? ?????× ?? ???? ??? ? ? ? ? ? × ?? ? ?? ? ? ? ?? ? ? ? ?×

? × ? ?× ? × ?× ?? × ? ? × ?? ? ?? ? ? ? ? × ×?

??? ? ? ? ? ? ? ? × ? ?? ? ? × ?? ? ? ? ? ???? ? ??? ???? ? ?????? ? ??? ? ?? ? ? × ??? ? ?? ?× ? ? ? ? ? ? ??? ? ? ?× ?? ? × ?? × ???? ×???? ? ? ?× ???? ? ?? ??? ? ? ? ???? ×? ? ? ×

×???? ??? ?

?? ?? ? ???? ×× ? ???? ? ??? ?? ? × ? ? ? ? ? ? ? ?? ? ?? ?? ? ? ?? ×??? ? ? ?× ??×? ? ? ??? ? ? ? ? ?×? ??? ???? ?? × ?? ??? ? ? ? ? × ?× ? ??? × ?

? ???? ×× ? ?? ? ? ??? ? ? ?

? × ?? ?

?? ? ??? ? ? × ??? ? ??×? ??? ? ? ? ??? × ? ?? ? ? ?× ?? ? ???? ? ? ?× ?? ? ???? ? × ?× ? ? ? ?? ?× ? ?? ?? ???? ? ? ?? ??×? ? ? ? ?? ? ?? ? ?

? ?× ?? ? ???? ? × ? ?? ? × ? × ? × ?? ?

? ????? ??

? ?? ? ?? ? ?

?? ? ?? ??? ?? ??

? ?? ? ??× ?? ? ?

? ?× ?? ? ???? ? ×

?? ? ? ??? ? ××?? ? ?? ?

?? ? ??

??

×?? × ×

?? ?

× ×? ? × ? ???? ??? ?

? ? ??

???×??? ? × ? ?×

?

? ???

?? ? ? ?? ? ?? ? ??? ? ?× × ? ??? ? ? ? ??? ? ?× ?? ×?? ? ??×? ? ???? ?? ?? × ?? ?

? ? ??

?? ????? ×???? ??× ?? ??

× ??? ? ? ? ? ?? ????? ? ? ? ?? ? ??×??? ? ? ? × ??? ? ?? × ?? ? ? ? ? ? ? × ? ??? ????? × ? × ?? ? ?

× ??? ? ??× ? × × ??? ? ? ? ? ??? ?? ? ? ? ? ????× ? ×???×

??? ?

? ?× ?? ? ?? ?× ??? ? ?? ?? ???? ? ? ? ??× × ? × ?×? ?×

? ?? ??× ??? × ?? ? ? ? ?? ??? ? ???? ?? ??××? ?

????? ?? ? ??? ? ??×? ?× ??? ? ? ? ???? ? ? ?? ?? ???? ? ? ? ??? ? ?× ? ? ? ? ???? ? ? ? ×? ??? ?? ??? ? ? × × ??????? ??? ?? ? ×?

? ? ??× ? ? ?? ? ?? ? ?

??? ?? ? ? ? × ?×? × ??? ? ? ? ????? ?? ?? ?× ? ? ??? ? ? ? ? ?× ?? ? ???? × ? ?

? ? ? ? ? ? ? ? × ???? ? ? ? ?? ??? × ? ×???? ?? ? ? ?? ? ? ??? ×??? ? ? ? ?? ??? ? ? ???? ? ??? ×??? ?? ??? ? ? ?? ??? × ? ?? ? ? ? ? ? ? ?? ?

?? × ? ? ??× ?? ? ?? ? ? ? ???× ? ? × ??? ?? ? ×? ×???? ?? ? ?? ? ? ? ? ? ?× ??? ×??? ?? ??×? ?? ×? ? ×? ?

× ??? ×??? ?? ? ?

??? ? ? ? ?×? ??? ? ? ?

?? ? ???

?? ? ?? ? ×? ? ×?? ? ? ? × ? ? ? ??

?? ?

×

×?

??? ×? ? ? ? × ?

?? ?× ×? ?×

? ? ? ×× ? ×?? ? ? ?? ??? ?? ? ×? ?

? ?? ? ? × ?? ??? ? ?? ? ??? × ? ? ? ? ???? ? ? ? ???× ? × × ? ?? ???? ? ??? ?? ? ×? ? × ? ? ? ??× ??

? ? ? ?? ?? ×

? × ? ? ? ?? ??? ? ??? ? ?? ? ? ???× ? ? ? ? ?? ? ??? ? ? × ? ? ??? ×? ? ? ?? ? ??? ? ? ?? ? ? × ?

? ? ??? ???? ?? ? ?? ? ?? ? × ?? ? ????? × ? ???? ? ? ? ?
? ? ? ? ?? ?

? ??× ?

? ? ? ?× ? ×

????

?? ???

? ? ? ?? ? ? ? ? × ? ???? ? × ?? ? ?



? ??? ? ? ? ???×?

×?? ? ×?

?× ?

×? ?

? ? ? × ? ?? ? ?? ?? ? ? ?? ? ???? ? ? ? ? ? ? ? ? ?? ? ???? ? ? ?× ? ?? ? ? ?? ??

?? ??? ? ?? ? ? ? ? ? ? ???× ×

?? ?? ? ?? ?? ?? ? ?? ?? ? × ? ?? ?? ? ?? ???×

? ? ?× ? ?

× ? ?? ??? ? ??×? ? ? ? ??? ?? ?? ?

??×? ? × ?? ×?? ? ? ?????

???? ?× ? ??? ? ? ?

? ?× ??× ??? ? ?? ? ??? ? ? ? ? ? ? ??? × ?? ? ?? ?

? ?? ??? ? ?× ? ? ? ? ?

× ? ????? ??? ? ? ? ? ?

?? ??? ?? ? ? ? ?

??

??

? ?? ??

? ?? ??× ? ×??

??? ? ? ? ??

?

?? ? ?? ? ?

? ?

? ?× ?? ? ?? ?? ? ??×??? ? ?? ? ?

? ? ? ? ?× ? ?

? ? ?×

赞助商链接
相关文章:
A-level数学简介_图文
A-level数学简介_理学_高等教育_教育专区。A-level 数学课程简介 一、A-level 简介 A-level(General Certificate of Education Advanced Level)是英国学生进入大学...
A-level数学常用词汇汇总
A-level数学常用词汇汇总 - A-level 数学常用词汇汇总 今天环球教育名师为考生们带来 A-level 数学常用词汇汇总,希望能给 alevel 考生们带来帮助。 MATHEMETI...
GCEA-level
GCEA-level_英语考试_外语学习_教育专区。GCE A-level 1. What’s GCE A-Level? The General Certificate of Education (GCE) Advanced Level or A Le ...
A-level化学知识点梳理系列(一)
A-level化学知识点梳理系列(一) - www.remaa.cn A-level 化学知识点梳理系列(一) A-level 化学的 AS 阶段主要涵盖了三大块的内容,分别是化学理论、元素 化...
A-Level物理知识点梳理系列(一)
A-Level物理知识点梳理系列(一)_高二理化生_理化生_高中教育_教育专区。本次知识梳理将对各个板块所涵盖的知识点、重要公式以及相关的典型真题进行精讲精练。...
DOE level VI 讲解
DOE level VI 讲解_能源/化工_工程科技_专业资料。DOE 外置电源(EPS)能效新要求 2014 年 2 月 10 号,美国能源部(DOE)颁布了外置电源(EPS)能效新要求的最终...
level-2 s函数帮助文件(英文)
level-2 s函数帮助文件(英文)_数学_自然科学_专业资料。Write Level-2 MATLAB S-Functions About Level-2 MATLAB S-Functions The Level-2 MATLAB? S-function...
A-Level 数学术语
A-Level 数学术语 - A-Level 数学术语 据 360 教育集团介绍:数学 mathematics, maths(BrE), math(AmE) 公理 axiom 定理 theore...
A-Level 课程解析之数学介绍
A-Level 基础数学课程的知识体系及对每个知识点的考查方式和国内是有差别的,因此一定要沿着 授课教师的思路逐步适应,自学的学生往往在知识掌握程度上把握不好。 2...
A-Level考纲翻译
剑桥国际 AS Level 的内容和难度水平考试上半年相当于一个相 应的剑桥国际水平。剑桥国际 AS Levels 水平被英国所有大学接受和承担一半 A Level 水平的权重。大学...
更多相关文章: