CMSC828J Advanced Topics in Information Processing

CMSC828J Advanced Topics in Information Processing: Image Segmentation

General Information

Class Time

Mon, Wed. 2:00-3:15

Room

CSI 3120

Course Info

See below

Text

Readings available on reserve in CS library and on web. See below

Personnel

	Instructor
Name	David Jacobs
Email	djacobs at cs
Office	AVW 4421
Office hours	Tue. 3:00-4:00 or by appt.

Announcements:

Midterm is now available

Problem Set 2 is now available.

Quiz Schedule

Review notes for final

Description

Image Segmentation is the process of dividing images up into meaningful subsets that correspond to surfaces or objects. This is a central problem in vision, because recognition and reconstruction often rely on this information. In this class we will survey a variety of different approaches to image segmentation.

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 E-M, 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 low-level 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 6-8 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 open-ended project for students interested in research in image segmentation. It should involve implementation of existing or novel algorithms for segmentation, and experiments on a real-world 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
Problem Set 1	Test Image	9/23/09	10/7/09
Problem Set 2	Test Image Results: 1, 2, 3, 4	10/19/09	11/02/09
Midterm	For more on problem 2, see papers by Witkin (PAMI 84) and by Babaud et al. (PAMI 86).	11/2/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 Reading
1. 8/31	Jacobs	Introduction.
2. 9/2	Jacobs	Perceptual grouping in human vision	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) 48-52.
3. 9/9	Jacobs	Fourier Transforms (1)	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	Fourier Transforms (2)
5. 9/16	Jacobs	Diffusion Processes	R. Ghez, Diffusion Phenomena . John Wiley and Sons, 2001, chapter 1. You're responsible for this material.
6. 9/21	Jacobs	Edge Detection	Forsyth and Ponce Chapter 8
7. 9/23	Jacobs	Non-linear Diffusion	"A review of nonlinear diffusion filtering," by Joachim Weickert. In Scale-Space Theory in Computer Vision, Lecture Notes in Computer Science, Vol. 1252, Springer, Berlin, pp. 3-28, 1997.
8. 9/28	Jacobs	Discussion: Non-linear 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. (*** This paper is listed for reference. You should not summarize it; choose either the paper below or the one above). F. Catte, P. Lions, and J.M. Morel, and T. Coll. Image selective smoothing and edge detection by nonlinear diffusion. SIAM J. of Numerical Analysis, Vol. 29, No. 1, 1992. L. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D. 60, 1992.
9. 9/30	Jacobs	Contours, Dynamic Programming and Markov Processes	D. Geiger, A. Gupta, L.A. Costa, and J. Vlontzos, "Dynamic programming for detecting, tracking, and matching deformable contours", IEEE Trans. PAMI, vol. PAMI-17, no. 3, pp. 294--302, 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. 81-96, 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 321--327, 1988.
10. 10/5	Jacobs	Markov Random Fields	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:721--741, 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. X. Ren, C. Fowlkes, and J. Malik. Learning probabilistic models for contour completion in natural images. Kumar, S., and Hebert, M. (2006). Discriminative random fields. International Journal of Computer Vision, 68(2). See also: X. He, R. Zemel, and M. Carreira-Perpinan. Multiscale conditional random fields for image labeling, CVPR 2004.
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. S. Roth and M. Black. Field of Experts (2009). IJCV
13. 10/14	Jacobs	Normalized Cut.	Forsyth and Ponce, Section 14.5 Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence , 22(8):888-905, 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 N-D images. Yuri Boykov and Marie-Pierre Jolly. In International Conference on Computer Vision, (ICCV), vol. I, pp. 105-112, 2001. GrabCut - Interactive Foreground Extraction using Iterated Graph Cuts Carsten Rother, Vladimir Kolmogorov and Andrew Blake. In ACM Transactions on Graphics (SIGGRAPH), August 2004.
15. 10/21	Jacobs	Distribution modeling: E-M, Mean shift, Mixtures of Gaussians	Forsyth and Ponce, Computer Vision A Modern Approach, Chapter 16 E-M 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	Level Sets	J. A. Sethian, Level Set Methods and Fast Marching Methods. Cambridge monographs on applied and computational methods. 1996. On reserve in CS library. Level Set Methods in Image Science Richard Tsai and Stanley Osher
17. 10/28	Jacobs	Level Sets (continued)
18. 11/2	Ken, Leo	Discussion: Mumford-Shah 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) Active contour without edges Chan, T.F.; Vese, L.A., IEEE Transactions on Image Processing, 10 (2), Feb. 2001, pp. 266 -277
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, SIAM, 1992.
21. 11/11	Jacobs	Texture	Forsyth and Ponce, Chapter 9
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, 716-723, 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, Ming-Yu, Allie	Discussion: Learning	D. Hoiem, A. Stein, A. Efros, M. Hebert. Recovering occlusion boundaries from a single image. ICCV 2007. D. Martin, C. Fowlkes, J. Malik. Learning to detect natural image boundaries using local brightness, color and texture cues. PAMI, PAMI, 2004.
25. 11/25	Jacobs	Discussion: Wavelet shrinkage and wavelet-based segmentation.	H. Choi, R. Baraniuk. Multiscale image segmentation using wavelet-domain 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	Motion and Optical Flow.	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) J.P. Costeira and T. Kande. A multibody factorization method for independently moving objects. IJCV 1998.
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: Object-based segmentation	A. Levin and Y. Weiss, Learning to Combine Bottom-Up and Top-Down 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)."