Computer Science Department
The University of Western Ontario
CS 4487/9587A --- Algorithms for Image Analysis
Syllabus: Fall 2015
This course has two components. On the one hand,
it is an introduction to digital image analysis presenting selected fundamental problems in computer vision, medical image analysis, 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, clustering 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.
|| Monday || 1:30 - 3:30pm || at AHB-1B04
|| Wednesday || 2:30 - 3:30pm || at NCB-117
||Prof. Yuri Boykov
||Middlesex College 387
|Office Hours :
||after class or by appointment
||yuri 'at' csd.uwo.ca
||(519) 661-2159 (UWO office)
||(226) 289-6980 (UWO vision lab)
Students are responsible for ensuring that they have either the prerequisites for this course,
or written special permission from the instructor.
If a student does not have the course prerequisites, and has not been granted a special permission, it is in 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.
- Analysis of algorithms (CS 3340A/B), non-CS students with good background in math or engineering can obtain instructor's permission
- One of first-year Calculus courses (1301, 1501)
- Linear Algebra (1600A/B)
- Basic programming skills in C/C++ or enthusiasm to learn MATLAB with instructor's permission
The website for the course is
Lecture notes, assignments, code samples, and other supplementary materials
will be posted on this web site. Many important announcements will be posted as well. It is your
responsibility to check this web site on a regular basis.
OWL will be used primarily for collecting homework assignments and projects.
Textbooks and Lecture Notes
There is no required textbook for this course. All lecture notes/slides will be available on the course web site. While the posted slides cover all the necessary material, they are supposed to be complemented by live discussion and blackboard scribbles. Note that class attensdance is very important since the posted slides are not designed for independent reading. Lecture notes could be complemented by readings from recommended text-books on computer vision and standard CS algorithms given below. You will be referred to specific relevant sections of these books in class.
- Richard Szeliski (Microsoft Research). Computer Vision: Algorithms and Applications, 2010.
- Milan Sonka, Vaclav Hlavac, Roger Boyle. Image Processing, Analysis, and Machine Vision,
Thomson Learning, 3d edition, 2007
- Gonzalez and Woods. Digital Image Processing, Prentice Hall, 2nd edition, 2002.
- Stan Z. Li. Markov Random Field Modeling in Image Analysis, Springer, 3d edition, 2009.
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, The MIT Press, 3d edition, 2009
- Kleinberg and Tardos. Algorithm Design, Addison Wesley, 2006.
This course presents many standard computer vision problems and their solution methods using common algorithms (e.g. dynamic programming, shortest paths, graph cuts, minimum ratio cycle). The studied image analysis problems provide an intuitive visual environment helping better understanding of such optimization methods. A tentative list of topics is given below.
- Overview of Imaging Modalities: photo (camera model), video, medical, etc.
- Elements of Image Pre-Processing (gamma and window/center correction, histogram equalization)
- Features and Filtering: colors, edges, corners, SIFT, etc.
- Basic Image Segmentation
- unsupervised and supervised segmentation (e.g. background subtraction vs. photoshop)
- "naive" methods: thresholding, region growing, watersheds
- clustering techniques: mean-shift, K-means (variance clustering criteria)
- boundary regularization: livewire, active contours (snakes), graph cuts, etc.
- combining (known) color model and boundary smoothness: objective function (energy), graph cuts
- Model Fitting
- probability models: Gaussians, GMM, histograms, Parzen density
- color model fitting in segmentation: Chan-Vese, Zhu-Yuille, grabcut. From variance to entropy-based color clustering.
- geometric models (lines, planes, homographies) for reconstruction (structure, panoramas, pose)
- inference methods: ML, least-squares, outlier robustness, L2 vs L1 metric, RANSAC
- multi-model fitting: hard assignemnts (K-means) vs. soft assignments (EM)
- General Image Labeling and Optimization
- applications: restoration, stitching, detection, segmentation, motion, etc.
- inference models: Markov Random Fields (MRF), Minimum-Description Length (MDL), sparcity
- optimization methods: ICM, annealing, binary and multi-label graph cuts (submodularity, a-expansion)
- pair-wise and high-order regularization: smoothness, boundary length and curvature, color-consistency, label cost, etc.
- Correspondence, Matching, and Reconstruction
- template matching, image registration, tracking, motion layers
- shape registration, pictorial structures
- stereo, volumetric reconstruction, laser scanning, kinect
- structure from motion
There will be homework assignments based on programming projects.
- There will be 3 assignments required for all students. One mini project at the end of the course will be required for graduate students only.
- The assignments and project details will be posted on the course web page.
- Assignemnts will require submission of code and a (max 2 page) report discussing the observed results and answering posted qestions. The mini project will require a more substential (max 4 page) report. The page limits only apply to the text, any number of figures is allowed. It is highly recommended to have more figures in the reports.
- Feel free to use Matlab in your assignments/projects, however, some of the discrete algorithms may be harder to implement efficiently using Matlab.
- Submission of your home work (reports and/or code) should be done electronically by the due date. Students
will be instructed to do submissions through their OWL accounts No files will be accepted via email.
- Late assignments: 5% of the mark will be subtracted for each day the assignment is late, up to the maximum of 5 days. Extensions may be granted only in case of serious documented
medical or family emergency, in which case you must take supporting documentation to the office of the Dean of your faculty.
- Assignments may include an extra credit part which may contribute up to 20% toward the mark on that assignment.
- While students may discuss the assignments, any code or written text should be an individual effort of each student.
- Tentative assignment topics and their tentative posting schedule below are subject to change. Assignments will be due in 7-10 days after posting.
- Assignment 1 (Sept. 30): color quantization and superpixes (RGB and RGBXY clustering) via K-means and mean/medoid-shift (extra credit)
- Assignment 2 (Oct. 19): interactive segmentation interfaces: snakes (edges), graph cuts (seeds+edges+color model), grabcut (box+edges+model fitting - extra credit)
- Assignment 3 (Nov. 2): line fitting (RANSAC, multiple lines), real image example with feature detector (extra credit)
- Mini project on stereo (Nov. 18): (a) window-based, (b) scan-lines (DP), (c) TV, (d) Potts model. Graduate students should implement 3 out of 4 methods. All parts will give extra credit. The stereo project is not required for undergraduate students, but enthusiastic students can implement any parts of the project for up to 5% extra credit for each of 4 parts (20% overall max).
There will be 3 short surprise quizzes given at the beginning of classes every 3-4 weeks. Your 2 best results (out of 3) will be used in the grading scheme. No make-ups will be offered.
There will be no exams in this course.
Homework assignments will include some additional parts for graduate students. These parts will be optional (extra credit) for undergraduates taking this course (CS4487). Mini project is required for graduate students only, however undergraduate students enthusiastic about stereo probem can obtain up to 30% extra credit for the project (partial credit is possible).
| || CS4487 (undergrads) || CS9587 (grad. students)
| Quizzes || 10% || 10% ||(5% each for 2 best out of 3)
| Assignments || 30% + 30% + 30% ||20% + 20% + 20%
| Mini Project || 0% (extra credit is possible) ||30%
Best Ways to Contact me
If you have a question and need to contact me, the best way to do so is to talk to me right after class. You can also email me to make an appointment. All emails should be sent from your UWO account and they should have CS4487/9587 in the subject line. Otherwise your email is likely to get filtered out.
Academic Accommodation for Medical Illness
If you are unable to meet a course requirement due to illness or other serious circumstances, you must provide valid medical or supporting documentation to the Academic Counselling Office of your home faculty as soon as possible. If you are a Science student, the Academic Counselling Office of the Faculty of Science is located in WSC 140, and can be contacted at 519-661-3040 or firstname.lastname@example.org. Their website is www.uwo.ca/sci/undergrad/academic_counselling/index.html.
A student requiring academic accommodation due to illness must use the Student Medical Certificate (https://studentservices.uwo.ca/secure/medical_document.pdf) when visiting an off-campus medical facility.
For further information, please consult the university’s medical illness policy at http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_medical.pdf.
Accomodations for properly documented medical illness would be determined on a case-by-case basis. Typically, that could be a deadline extension.
Learning-skills counsellors at the Student Development Centre (http://www.sdc.uwo.ca) are ready to help you improve your learning skills. They offer presentations on strategies for improving time management, multiple-choice exam preparation/writing, textbook reading, and more. Individual support is offered throughout the Fall/Winter terms in the drop-in Learning Help Centre, and year-round through individual counselling.
Students who are in emotional/mental distress should refer to Mental Health@Western (http://www.health.uwo.ca/mental_health) for a complete list of options about how to obtain help.
Additional student-run support services are offered by the USC, http://westernusc.ca/services.
The website for Registrarial Services is http://www.registrar.uwo.ca.
Code of Student Conduct
To foster a supportive and enriching academic environment that is conducive to learning and free inquiry, Western has a Code of Student Conduct (http://www.uwo.ca/univsec/pdf/board/code.pdf).