Growing Set: avi mpg
Final Set: avi mpg
|1||Friday, Sept. 10||List of likely course topics.|
|2||Wednesday, Oct. 6||Description of course project. A list of potential projects is available from the professor.|
|3||Monday, Nov. 29||Assessment form for project presentations.|
Homework Submission Policy:
|#||Due Date||Assignment||Solution||Other Files|
|1||September 22||Problem Set||Solutions||none|
|2||October 6||Problem Set||Solutions||none|
|3||October 20||Problem Set||Solutions||testImage.png,
Matlab image generation routine.
Expected reach set for question #2.
|4||November 8||Problem Set||Solutions||none|
|*||*||Midterm||Solutions||Mean 48.4, Standard Deviation 8, Median 50, Maximum 60.5, Minimum 35.5|
Course OverviewLevel set methods are a class of numerical algorithms for simulation of dynamic implicit surfaces and approximation of solutions to the Hamilton-Jacobi (HJ) partial differential equation (PDE).
Dynamic implicit surfaces prove useful in such fields as:
The benefits of an implicit representation of surfaces include hassle free merging and separation of surfaces, easy computation of geometric properties like normals and curvature, and the fact that both curves in two dimensions and surfaces in three dimensions can be treated with the same theory and computational algorithms.
The course will begin with an examination of numerical methods for computing dynamically evolving implicit surfaces. Students will experiment in Matlab with state-of-the-art high order accuracy methods using a Toolbox of Level Set Methods developed by the instructor, and will therefore be able to progress rapidly to application specific details from the fields mentioned above.
The second part of the class will turn to the HJ PDE, which arises in such fields as:
This component will examine generalizations of the level set methods mentioned above, as well as other classes of algorithms (including fast marching, ordered upwind, and sweeping) and some of the viscosity solution theory underlying this ubiquitous equation. Applications will be explored depending on students' interests.
In addition to attending lectures, students will be expected to:
Intended Audience: Graduate students in
Prerequisites: None officially.
Instructor: Ian Mitchell
Lectures: 11 - 12:30, Mondays and Wednesdays, Forest Sciences Center (FSC) 1002
Grades: Your final grade will be based on a combination of
|#||Date||Topic||Links||Required Readings||Optional Readings|
|1||Sept 13||Introduction. Surface Representations.||Matlab's Introduction to initial value ODEs (available locally through Matlab's helpdesk command)||none.||Representations: Farin. Hoffmann.
ODEs: Boyce & DiPrima chapter 8. Burden & Faires chapter 5. Heath chapter 9.
|2||Sept 15||Implicit Surface Functions. Constructive Solid Geometry. Matlab introduction.||Toolbox of Level Set Methods||OF chapter 1||T section 3.3|
|3||Sept 20||Signed Distance Functions. Computer representation of continuous functions.||none||OF 2||OF 3.3-3.4, Heath 8.6, Burden & Faires 4.1, Strikwerda 1|
|4||Sept 22||Motion by convective flow. Upwind spatial derivative approximation.||none||OF 3.1-3.2, T 2.1||T 3 (as needed), Heath 11.1-11.2, Burden & Faires 12.2-12.3|
|5||Sept 27||Temporal derivative approximation. CFL timestep restriction. Multiple dimensional motion.||none||OF 3.2||none|
|6||Sept 29||High order methods (TVD RK, ENO, WENO). Motion in the normal direction.||none||OF 3.3-3.5||T 2.7.2|
|7||Oct 4||Motion in the Normal direction. Combinations of Motion. Reinitialization||none||OF 6.1, 6.2, 6.4, T 2.3.2-2.3.3||none|
|8||Oct 6||Reinitialization Equation. Motion by Mean Curvature. Course Project Discussion.||none||OF 7.1-7.4, 4.1-4.3, T 2.2.1, 2.3.1, 2.4||S 2.3-2.4, 12.1-12.3||Oct 11||Thanksgiving Holiday (no class)|
|9||Oct 13||Constraints and Masking. Applications: Reach Sets (no inputs), Image Segmentation.||none||OF 12.1, T 2.2.3||S 12.4.3|
|10||Oct 18||Optimal Control and the Hamilton-Jacobi Bellman equation.||none||none||Evans 10.3|
|11||Oct 20||General first order HJ terms.||none||OF 5.1, 5.3, T 2.2.2, 2.5||OF 5.2|
|12||Oct 25||Forcing terms. Differential Games.||none||none||"Differential Games and Representation Formulas for Solutions of Hamilton-Jacobi-Isaacs Equations" by Evans & Souganidis, Indiana U. Math. J., v.33, n.5, pp.773-797 (1984).|
|13||Oct 27||Continuous Reach sets (with inputs)||Application of Level Set Methods to Control and Reachability Problems in Continuous and Hybrid Systems by Mitchell. Reach Set Lecture Slides.||T 2.6, section 2.1 of Mitchell||Mitchell 2-3|
|14||Nov 1||Reach Sets: Projections & Hybrid Systems. Minimum time to reach.||Reach Set Lecture Slides.||none||S 20.1-20.3, Mitchell 4-6|
|15||Nov 3||Static to Time-Dependent Transformation.||"A Toolbox of Hamilton-Jacobi Solvers for Analysis of Nondeterministic Continuous and Hybrid Systems" by Mitchell & Templeton, submitted to HSCC 2005.||Mitchell & Templeton section 3.||"A Level Set Formulation for the solution of the Dirichlet Problem for Hamilton-Jacobi Equations" by Osher, SIAM J. Math. Anal. v.24, pp. 1145-1152 (1993).|
|16||Nov 8||Fast Marching||"Efficient algorithms for globally optimal trajectories" by Tsitsiklas. "A fast marching level set method for monotonically advancing fronts" by Sethian.||OF 7.5||S 8|
|Nov 10||Midterm exam|
|17||Nov 15||Path Planning with Fast Marching Method.||Path Planning Slides. "Optimal Algorithm for Shape from Shading and Path Planning" by Kimmel & Sethian. "Continuous Path Planning with Multiple Constraints" by Mitchell & Sastry.||none.||none.|
|18||Nov 17||Iterative and Sweeping Methods. Velocity Extension.||"Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations" by Tsai et. al. "The Fast Construction of Extension Velocities in Level Set Methods" by Adalsteinsson & Sethian.||OF 8||S 11.2-11.4|
|19||Nov 22||Conservation Laws. Particle Level Set Method.||"Animation and Rendering of Complex Water Surfaces" by Enright, Marschner and Fedkiw. "A Hybrid Particle Level Set Method for Improved Interface Capturing" by Enright et. al. PLS lecture slides.||OF 9||OF 14-21|
|20||Nov 24||Vector Level Sets. Stochastic Systems and the Kolmogorov Equation. Course Summary||"A Toolbox of Hamilton-Jacobi Solvers for Analysis of Nondeterministic Continuous and Hybrid Systems" by Mitchell & Templeton, submitted to HSCC 2005.||OF 10.1-10.3, Mitchell & Templeton section 4.||none.|
|21||Nov 29||Project Presentations.|
|22||Dec 1||Project Presentations.|
|Dec 7-21||Exam period. Projects due at noon on Friday, December 17.|
|Eric Brochu||3D Visualization||Implicit Surface Ray Tracer|
|Tyson Brochu||Faster Time Integration Algorithm||Semi-Lagrangian Time Integration|
|Wan Chen||Image Segmentation Application||Active Contour Without Edges in Level Set Formulation|
|Sarah Cormier||Algorithm to Reduce Computational Complexity||A Toolbox Implementation of the Local Level Set Method|
|Kevin Loken||Algorithm to Reduce Numerical Dissipation||Particle Level Set Method|
|Zhenguo Pan||New Type of Surface Motion||Level Set Method for Motion by Surface Diffusion|
|Scott Olsen||Path Planning Application||Level Set Methods Approach to Optimal Path Planning|
|Tiberiu Popa||Generation of Explicit Surface Representation in 3D||Survey of Triangulation Algorithms of Implicit Function Represented on Regular Grids|
|Tim Rees||Financial Mathematics Application||A Level Set Approach to a Stochastic Differential Equation in Mathematical Finance|
|Dana Sharon||Algorithm for Solving the Stationary HJB||Implementation of the Fast Marching Method|
|Ian Stavness||Surface Reconstruction Application||Reconstruction of Surfaces from Unorganized Data Points|
|David White||Additional Toolbox Features||Spatial and Time-Dependent Boundary Conditions|
|Alan Woo||Physically Based Modelling Application||Low-Speed Flame|
|Yongning Zhu||Adaptive Mesh Refinement||Adaptively Refined Meshes for Level Set Functions|