Algorithms for Medical Image Processing

I teach the course of Algorithms for Medical Image Processing (CS 4487a/9587a) in the autumn semester of 2010, for senior undergraduates and graduates in University of Western Ontario. This course was originally developped by Prof. Yuri Boykov.

Course Description

This course has two components. On the one hand, it is an introduction to digital image analysis presenting selected fundamental problems in medical image analysis, computer vision, photo/video editing, and graphics. We cover such basic concepts as image segmentation, registration, object recognition/matching, tracking, texture, etc. On the other hand, this is an applied course on standard computer science algorithms where students develop practical understanding of dynamic programming, graph based algorithms, computational geometry methods, etc. In fact, image analysis provides a stimulating environment for studying algorithms as their outputs can be intuitively visualized. Students with previous background in algorithms will be exposed to applications in image analysis, while students already familiar with problems in imaging will learn efficient methods based on standard CS algorithms. The course emphasizes the design, analysis, and implementation of algorithms in the context of 2D/3D medical images, photo and video data.

Prerequisites

• • Analysis of algorithms (CS 3340A/B)

  • One of first-year Calculus courses (1301, 1501)

  • Linear Algebra (1600A/B)

  • Basic programming skills in C/C++

  • Alternatively, instructor permission may be given based on math and programming skills

Note: Students are responsible for ensuring that they have either the prerequisites for this course, or written special permission from their Dean to enrol in. If a student does not have the course prerequisites, and has not been granted a special permission to take the course by the department, it is his/her best interest to drop the course well before the end of the add/drop period. If a student is not eligible for a course, he/she may be removed from it at any time, and will receive no adjustment to his/her fees. These decisions can not be appealed. Lack of prerequisites may not be used as the basis of appeal.

Course Topics

This course presents applications in image analysis for standard Computer Science algorithms such as dynamic programming (DP), minimum-spanning trees, shortest paths, graph cuts, minimum ratio cycle, and some methods from computational geometry. Despite its strong emphasis on discrete algorithms, the course is structured around image analysis problems. Some of the studied algorithms appear in a number of different imaging applications giving an opportunity to study them from several view points. A brief description of course content is given below.

• • Segmentation and Deformable Models in 2D and 3D

  • Correspondence

  • Stereo/Motion

  • 3D object/shape reconstruction

  • Anisotropic Reconstruction of Images

  • Template matching

  • Image Registration

  • Elements from Computational Geometry

  • Local vs. Global Optimization

  • Texture (time permitting)

  • Shape (time permitting)

  • Object recognition/matching (time permitting)

Instructors / TAs

Best way to contact me: If you have a question and need to contact me, best way to do so is after class or during my office hours. You may contact me by email, but do not expect an answer within 2 minutes. I may be able to answer quickly, or it may take me a few days. For questions requiring detailed explanations (like "I didn't get that concept, can you go over it again?"), I might ask you to come to talk to me during my office hours. If scheduled office hours are not convenient, please make an appointment.

If you e-mail anyone, please include "CS 4487a" in the subject line. Otherwise your email is likely to get filtered out.

Lectures – 3 hours per week

Computing Facilities

Each student can get an account on the Computer Science Department senior undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department's Policies and Procedures .

Textbooks & Reading Notes

The required textbook for this course is

• • Milan Sonka, Vaclav Hlavac, Roger Boyle. Image Processing, Analysis, and Machine Vision . Thomson Learning; 3 edition (March 2007)

Please note that the latest 3rd edition of the book significantly extends the earlier 2nd edition, which is not acceptable. Students can also supplement their lecture notes with readings from recommended books on image analysis and texts on standard algorithms of Computer Science given below. You will be referred to specific relevant sections of these books in class. Additional supplementary materials from scientific journals/conferences and various internet resources will also be provided on the course's web page. Some sections will be recommended from the following two books:

• • Richard Szeliski (Microsoft Research). Computer Vision: Algorithms and Applications

  • Kleinberg and Tardos. Algorithm Design , Addison Wesley, 2006 (available for 2-hour loan in Taylor library).

  • Gonzalez and Woods. Digital Image Processing , Prentice Hall, second edition, 2002.

  • Stan Z. Li. Markov Random Field Modeling in Image Analysis , Springer, third edition, 2009.

Students (mainly non-CS major) with limited experience in C++ and/or data structures may also find very useful the following book as an additional reference:

• • Michael Main and Walter Savitch, Data Structures and Other Objects Using C++ , third edition, Addison Wesley, 2005.

A lot of the material in the lectures will be presented from slides, yet some material will be presented on a blackboard. All slides can be found on the course's website.

Lecture Notes

• • Topic 1. Introduction

  • Topic 2. Overview of different image modalities: photo images, video, and 2D-3D-4D medical data

  • Topic 3. Overview of basic image processing (point and local neighborhood processing): gamma correction, histogram equalization, window-center adjustment, linear filtering, image gradients.

  • Topic 4. Basic image segmentation in 2D (thresholding, region-growing, mean-shift, live-wire).

  • Topic 5. Deformable models (snakes): gradient descend, DP-snakes. Also distance transforms and generalized distance transforms.

  • Topic 6. Beyond snakes: implicit vs. explicit representation of boundaries, level-sets, geodesic active contours, geometric energy functionals.

  • Topic 7. Correspondence, Stereo (Window-based, scan-line based, grid-based), Graph Cuts algorithm for energy minimization on grids.

  • Topic 8. Surface extraction in 3D, binary labeling, and graph cuts: volume segmentation, multi-view reconstruction, implicit vs. explicit boundary representation, binary submodular energies, geometric functionals, Markov Random Fields.

  • Topic 9. Multi-label image analysis problems: image restoration, stereo, texture synthesis, multi-object segmentation, pair-wise interaction potentials (convex vs. discontinuity preserving), energy minimization algorithms (simulated annealing, ICM, Ishikawa's algorithm, multi-way graph cuts, a-expansions).