CMSC828J
Advanced Topics in Information Processing: Image Segmentation
General Information 


Announcements:
Midterm is now available
Problem Set 2 is now available.
Description
What differentiates image segmentation from other clustering problems is that images have a natural 2d neighborhood structure. As a consequence, many segmentation algorithms can be thought of as diffusing information about image similarity among nearby pixels. We will begin by discussing diffusion processes, including anisotropic diffusion processes, which do exactly that. At the same time, we will discuss other local operations, such as edge detectors, that make judgements about image boundaries based on this information. We will then discuss approaches that diffuse probabilistic information by assuming Markov models of image probabilities. These methods include Markov random fields, belief propagation, and linear relaxation labeling. Other segmentation methods that rely on the natural graph structure of the image include normalized cut approaches to image segmentation, algebraic multigrid methods, and other graph algorithms such as shortest path methods for finding image segmentations. Finally, we will discuss methods for applying more generic clustering techniques, such as EM, to capitalize on the neighborhood structure of images. Along the way, we will consider segmentation methods that rely on texture, color, and motion cues. The goal of the class will be to familiarize students with current research approaches to image segmentation, while at the same time teaching the theoretical foundations underlying this work. A secondary goal will be to introduce many concepts that are fundamental in lowlevel vision (eg., filtering, edge detection, color and texture analysis).
The class will consist of lectures on basic material, and discussion and reading of work that is more current and/or speculative. Students will be required to prepare for and help lead some of the discussions. Students who are not leading discussions will still be expected to read papers to prepare for them. They will also do problem sets or projects in which they implement and test an approach to segmentation, or propose novel work on segmentation. There will also be a midterm and a final exam covering the basic computational techniques we’ve learned. Students will find it important to have some prior knowledge of vision, mathematical sophistication, and familiarity with topics such as calculus, linear algebra, probability and statistics.
Requirements
Here is my current plan for the workload of the class. This may change during the first two weeks, as the number of students settles down.
1) Reports. There will be about 68 classes in which we discuss research papers. Prior to each of these classes, students must turn in a one page summary and critique of one of the papers to be discussed. I prefer if you turn in a hardcopy to me at the start of class. This should contain one paragraph summarizing the paper to be discussed, and one paragraph critiquing the paper. The summary should focus on what you think is most important. The critique should explain whether you think the paper is worthwhile, and why. Late papers will not be accepted, since the goal of these reports is to get you to think about papers before we discuss them. However, each student can skip two of these reports. 10% of grade
2) Topic expert. Students will be assigned to become experts on one of the topics we will discuss. Students should be prepared to help lead discussion, to answer our questions, and to provide interesting and insightful extra comments culled from the literature. 15 % of grade.
3) Midterm, Final. These will be based on material from the lectures, and background reading for the lectures. 50% of grade
4) Problem Set/Project. Student will choose one: 25% of grade
a) Three problem sets will be assigned, requiring implementations of three of the algorithms discussed in class.
b) Programming/research project: This is meant to be a more openended project for students interested in research in image segmentation. It should involve implementation of existing or novel algorithms for segmentation, and experiments on a realworld data set.
Problem Sets
Please hand in your solution to the problem sets, including: 1) A document, with pictures when appropriate, describing your results; 2) Your code. I would prefer to receive your code by email in a zip file, and a hardcopy of the document, but I'll accept everything by email.
If problem sets are late, I will deduct 10% for each day they are late. Problem sets will not be accepted after the class following the due date.
Problem Set 
Supplementary Material 
Assigned 
Due 
9/23/09 
10/7/09 


11/02/09  


11/09/09  
Problem Set 3  11/30/09  12/09/09 
Class Schedule
This schedule should be considered more of a guideline than a rigid plan.
Lectures
Class 
Presenters 
Topic 
Background 
1. 8/31 
Jacobs 


2. 9/2 
Jacobs 
Vision Science, by Stephen Palmer, Chapter 6.
Subjective Contours in Early Vision and Beyond, by Bela Julesz.
You're responsible for this material. See also:
Kanizsa, G., "Subjective Contours" Sci. Am. 234 (1976) 4852. 

3. 9/9

Jacobs 
This material is covered in many standard techniques. You might look at:A Wavelet Tour of Signal Processing , by Mallat for this and material on wavelets. Chapters 2 and 3 are on the Fourier Transform.
I also like the discussion in Elementary Functional Analysis by Shilov (This is part of the Dover Classics series, so there is a cheap paperback edition).
Some of this material is discussed in Forsyth and Ponce, Chapter 7. 

4. 9/14 
Jacobs 

5. 9/16 
Jacobs 
R. Ghez, Diffusion Phenomena . John Wiley and Sons, 2001, chapter 1. You're responsible for this material. 

6. 9/21 
Jacobs 
Forsyth and 

7. 9/23 
Jacobs 
"A review of nonlinear diffusion filtering," by Joachim Weickert. In ScaleSpace Theory in Computer Vision, Lecture Notes in Computer Science, Vol. 1252, Springer, Berlin, pp. 328, 1997. 

8. 9/28 
Jacobs 
Discussion: Nonlinear Diffusion 
L. Alvarez, P. Lions, and J.M. Morel. Image
selective smoothing and edge detection by nonlinear diffusion II. SIAM J.
of Numerical Analysis, Vol. 29, No. 1, 1992. 
9. 9/30 
Jacobs 
D. Geiger, A. Gupta, L.A. Costa, and J. Vlontzos, "Dynamic programming for detecting, tracking, and matching deformable contours", IEEE Trans. PAMI, vol. PAMI17, no. 3, pp. 294302, Mar. 1995. Intelligent Scissors for Image Composition, by Eric Mortensen and William Barrett, SIGGRAPH '95. Williams, L.R. and K.K. Thornber, A Comparison of Measures for Detecting Natural Shapes in Cluttered Backgrounds, Intl. Journal of Computer Vision 34 (2/3), pp. 8196, 1999. A. Shashua and S. Ullman. Structural saliency: The detection of globallly salient structures using a locally connected network. In International Conference on Computer Vision, pages 321327, 1988. 

10. 10/5 
Jacobs 
Markov Random Field Modeling in Image Analysis (Computer Science Workbench) by Stan Z. Li (excerpt on reserve in CS library).
Fast Approximate Energy Minimization via Graph Cuts, by Boykov, Veksler, and Zabih. S.Geman and D.Geman. "Stochastic relaxation, gibbs distributions, and the bayesian restoration of images", IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721741, 1984. 

11. 10/7 
Daozheng, Joao, Qiang 
Discussion: Conditional Random Fields 
(*** This paper is given as a good background reference
for CRFs. Do
not summarize this. Summarize one of
the two following papers). C. Sutton
and A. McCallum. An
introduction to conditional random fields for relational learning. In An
Introduction to Statistical Relational Learning, edited by Getoor and Taskar. 
12. 10/12 
Nitesh, Jai 
Discussion: Higher Order Markov Random Fields 
P. Kohli, L. Ladicky, P. Torr. (2009). Robust
Higher Order Potentials for Enforcing Label Consistency, IJCV. 
13. 10/14 
Jacobs 

Forsyth and Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence , 22(8):888905, August 2000. For more explanation, read: Meila and Shi. Learning Segmentation by Random Walks. Luxburg. A Tutorial on Spectral Clustering. http://www.kyb.mpg.de/publications/attachments/Luxburg06_TR_[0].pdf Agarwal, et al. Beyond Pairwise Clustering. 
14. 10/19 
Jacobs 
Graph Cuts 
Interactive
Graph Cuts for Optimal Boundary & Region Segmentation of Objects in ND
images.
GrabCut 
Interactive Foreground Extraction using Iterated Graph Cuts 
15. 10/21 
Jacobs 
Distribution modeling: EM, Mean shift, Mixtures of Gaussians 
Forsyth and EM tutorial by Yair Weiss
D. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, IEEE Trans. PAMI, 2002. 
16. 10/26 
Jacobs 
J. A. Sethian, Level Set Methods and Fast
Marching Methods. Level
Set Methods in Image Science Richard Tsai and 

17. 10/28 
Jacobs 
Level Sets (continued) 

18. 11/2 
Ken, Leo 
Discussion: MumfordShah segmentation and level sets 
D. Mumford and J. Shah. Optimal approximations by piecewise smooth functions and associated variational problems. Comm on Pure and Applied Math, 1989. (excerpts) Chan, T.F.; Vese, 
19. 11/4 
Jacobs 
Multiscale: Multigrid 
An Introduction to Algebraic Multigrid,
by Klaus Stuben. Appendix A in Multigrid,
by U. Trottenberg, C. Oosterlee
and A. Schuller,, Academic Press, 2001. 
20. 11/9 
Jacobs 
Multiscale: Wavelets 
There are many texts on wavelets available. I have made use of the following: A Wavelet Tour of Signal Processing, by Stephane Mallat, Academic Press, 1998. Ten Lectures on Wavelets, Ingrid Daubechies, 
21. 11/11 
Jacobs 
Forsyth and 

22. 11/16 
Jacobs 
Catch up on wavelets and texture. 

23. 11/18 
Chris, John, Ching Lik 
Discussion: Texture Segmentation 
M. Galun, E. Sharon, R. Basri, A. Brandt, Texture Segmentation by Multiscale Aggregation of Filter Responses and Shape
Elements,
Proceedings IEEE International Conference on Computer Vision, 716723, Nice, France, 2003.
Jitendra Malik, Serge Belongie,
Thomas Leung, and Jianbo Shi. Contour and
texture analysis for image segmentation. International Journal of
Computer Vision, 2000. 
24. 11/23 
Jayant, MingYu, Allie 
Discussion: Learning 
D. Hoiem, A. Stein, A. Efros, M.
Hebert. Recovering
occlusion boundaries from a single image. ICCV 2007. 
25. 11/25  Jacobs  Discussion: Wavelet shrinkage and waveletbased segmentation. 
H. Choi, R. Baraniuk. Multiscale
image segmentation using waveletdomain hidden Markov models. IEEE
Trans. on Image Processing, 2001. D. Donoho, I.Johnstone. Ideal spatial adaptation by wavelet shrinkage. Biometrika, 1994. 
26. 11/30 
Jacobs 
Structure from motion and optical flow are well described in many texts, such as Forsyth and Ponce, Hartley and Zisserman, and Trucco and Verri.
C.W. Gear, Multibody grouping from motion images. IJCV,
1998. (Available from me) 

27. 12/2 
Jacobs 
Discussion: Optical Flow and Motion Segmentation 
R. Vidal, R. Tron, and R. Hartley. Multiframe Motion Segmentation with Missing Data Using PowerFactorization and GPCA. IJCV 2008. D. Cremers and S. Soatto. Motion Competition: A Variational Approach to Piecewise Parametric Motion Segmentation, IJCV 2005. 
28. 12/7  Jacobs  Discussion: Objectbased segmentation 
A. Levin and Y. Weiss,
Learning to Combine BottomUp and TopDown Segmentation, IJCV 2009. M. Kumar, P. Torr, and A. Zisserman, OBJ CUT, CVPR 2005. 
29. 12/9 
Jacobs 
Conclusions 

FINAL 12/17 
1:30 PM, in Classroom 


Student Honor Code
The University of Maryland, College Park has a nationally recognized Code of Academic Integrity, administered by the Student Honor Council. This Code sets standards for academic integrity at Maryland for all undergraduate and graduate students. As a student you are responsible for upholding these standards for this course. It is very important for you to be aware of the consequences of cheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrity or the Student Honor Council, please visit http://www.shc.umd.edu. To further exhibit your commitment to academic integrity, remember to sign the Honor Pledge on all examinations and assignments: "I pledge on my honor that I have not given or received any unauthorized assistance on this examination (assignment)."