CMSC828J Advanced Topics in Information Processing

On Thursday, October 12, at 5:00 I changed the link to the Shi and Meila paper to a slightly different one. Please read and review the paper pointed to by the new link, if possible.

The current plan is to hand out the midterm on October 19th, and for it to be due on the 26th.

There will be a 15 minute quiz on the 26th of September. It will cover material up to non-linear diffusion, discussed on the 21st.

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 projects in which they implement and test an approach to segmentation, or propose novel work on segmentation. There will also be quizzes, 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 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 some 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. This will be a substantial part of the grade. The number of times students will do this, and whether it is done is groups, will depend on course enrollment. 15 % of grade.

3) Quizzes, Midterm, Final. These will be based on material from the lectures, and background reading for the lectures. 50% of grade

a) Write a detailed, paper, approximately five pages in length, proposing research that extends or adapts one of the approaches discussed in class. You may choose to base this on the papers for which you served as expert.

b) Programming project: in teams, student will implement a technique discussed in class, and apply it to some real data. This is not meant to be a research project, but something closer to an extended problem set.

Class Schedule

This schedule should be considered more of a guideline than a rigid plan. I have divided the schedule into two parts. The first part contains 18 lectures on fundamental topics. The second part contains ten proposed classes in which we will discuss research papers. We will not get to all of these topics. The set of proposed research papers to discuss is especially tentative; I am also very open to suggestions. These discussion classes will be inserted in between appropriate lectures, they won't all come at the end.

Class	Presenters	Topic	Background Reading
1. 8/31	Jacobs	Introduction.
2. 9/5	Jacobs	Perceptual grouping in human vision	Vision Science, by Stephen Palmer, Chapter 6. (on reserve in CS library). Kanizsa, G., "Subjective Contours" Sci. Am. 234 (1976) 48-52. (On reserve in CS library.) You're responsible for this material.
3. 9/7	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 (on reserve in CS library). 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/12	Jacobs	Fourier Transforms (2)
5. 9/14	Jacobs	Diffusion Processes	R. Ghez, Diffusion Phenomena . John Wiley and Sons, 2001, chapter 1. On reserve in the CS library. You're responsible for this material.
6. 9/19	Jacobs	Edge Detection	Forsyth and Ponce Chapter 8
7. 9/21	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/26	Jacobs	QUIZ Markov models, belief propagation, Markov Random Fields, Relaxation Labeling.	Excerpt from Computer Vision by Ballard and Brown, pp. 408-430. Available at Computer Science Library. Textbooks on Stochastic Processes, such as Chapters 3 and 4 of An Introduction to Stochastic Modeling, by Taylor and Karlin, 3rd Edition, Academic Press, 1998. Jordan M.I. and Weiss Y. Graphical models: probabilistic inference In Arbib, M. (ed): Handbook of Neural Networks and Brain Theory. 2nd edition. MIT Press J. Yedidia,W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. International Joint Conference on Artificial Intelligence (IJCAI 2001) Distinguished Papers Track, 2001. Check Lise Getoor's references for the Graphical Models Reading Group
9. 9/28	Jacobs	Markov models, belief propagation, Relaxation Labeling (continued).
10. 10/3	Jacobs	Shortest path algorithms for finding boundaries.	Intelligent Scissors for Image Composition, by Eric Mortensen and William Barrett, SIGGRAPH '95. 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. M. Kass, A. Witkin and D. Terzopoulos : Snakes: active contour models. Int. J. of Comp. Vision, 1, 321-331 (1988).
11. 10/5	Guangyu - Presentation	Contour grouping - You should read both the Shashua and Ullman and Alter and Basri papers referenced on the right. You should hand in a one page summary of one of these papers.	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. T. D. Alter and Ronen Basri, Extracting Salient Curves from Images: An Analysis of the Saliency Network, International Journal of Computer Vision, 27(1): 51-69, 1998.
12. 10/10	Deva Ramanan	Attend Ramanan's talk in AVW 2120
13. 10/12	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.
14. 10/17	Roman - Presentation	Interpretations of Normalized Cut	To review: Meila and Shi. Learning Segmentation by Random Walks. To read: Luxburg. A Tutorial on Spectral Clustering. http://www.kyb.mpg.de/publications/attachments/Luxburg06_TR_[0].pdf If time: Agarwal, et al. Beyond Pairwise Clustering.
15. 10/19	Zhe - Presentation Midterm Handed out	Graph Cuts Read both papers on the right, and review one.	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.
16. 10/24	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.
17. 10/26	Jacobs Midterm due	Algebraic multigrid	An Introduction to Algebraic Multigrid, by Klaus Stuben. Appendix A in Multigrid, by U. Trottenberg, C. Oosterlee and A. Schuller, Academic Press, 2001.
18. 10/31	Jacobs	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.
19. 11/2	Jacobs	Texture	Forsyth and Ponce, Chapter 9
20. 11/7	Jacobs - Discussion	Texture Segmentation: Read Galun et al. and Malik et al. and review one of them. Time permitting we'll also discuss Krishnamachari and Chellappa, so you might also want to read that.	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. Krishnamachari and Chellappa. Multiresolution Gauss-Markov Random Field Models for Texture Segmentation, IEEE Trans. on Image Processing Vol 6, No. 2, 1997.
21. 11/9	Fatemeh - Discussion	Text Segmentation - Read both and review one.	Wu, V.; Manmatha, R.; Riseman, E.M Textfinder: an automatic system to detect and recognize text in images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 21 (11), 1999, Page(s): 1224-1229 Raju, S.S.[S. Sabari], Pati, P.B., Ramakrishnan, A.G., Text Localization and Extraction from Complex Color Images, ISVC05(486-493).
22. 11/14	Jacobs	E-M, Mean shift, Mixtures of Gaussians	Forsyth and Ponce, Computer Vision A Modern Approach, Chapter 16 E-M tutorial by Yair Weiss
23. 11/16	Mohamed - Discussion	Background Subtraction	Non-parametric model for background subtraction, ElGammel, Harwood and Davis Adaptive background mixture models for real-time tracking, Stauffer and Grimson
24. 11/21	Raghuraman - Discussion	Motion Segmentation Read both papers and summarize one.	M. Irani, B. Rousso, and S. Peleg, Computing Occluding and Transparent Motions . International Journal of Computer Vision (IJCV), Vol. 12, No. 1, pp. 5-16, February 1994. (A shorter version in ECCV'92). A. Jepson and M. Black, Mixture models for optical flow, Tech. Report, Res. in Biol. and Comp. Vision, Dept. of Comp. Sci., Univ. of Toronto, RBCV-TR-93-44, 1993
25. 11/28	Jacobs - Discussion	Color and color segmentation (part lecture, part discussion). Read and summarize Comaniciu and Meer.	Forsyth and Ponce, Chapter 6 The Foundations of Color Measurement and Color Perception, by Brian Wandell Mean shift: a robust approach toward feature space analysis, by Comaniciu and Meer. PAMI Publication Date: May 2002 Volume: 24, Issue: 5 On page(s): 603-619
26. 11/30	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
27. 12/5	Jacobs	Level Sets (continued)
28. 12/7	Carlos - Discussion	Level Sets for Segmentation Read and summarize Chan and Vese.	Active contour without edges Chan, T.F.; Vese, L.A., IEEE Transactions on Image Processing, 10 (2), Feb. 2001, pp. 266 -277
29. 12/12	Jacobs	Conclusions
FINAL 12/14	8AM, in Classroom

Class	Presenters	Topic	Possible Reading
1.		Psychological theories of Perceptual Grouping	Chapter 5 of Rock's book. The logic of perception. Cambridge, MA: MIT Press. Van der Helm, P. Leeuwenberg, E. (1996). Goodness of visual regularities: a nontransformational approach." Psychological Review, 103(3), 429-456. Pomerantz, J. Kubovy, M. (1986). \Theoretical approaches to perceptual organization." In K. Boff, L. Kaufmann J. Thomas (editors, Hand- book of perception and human performance: Vol. II. cognitive processes and per- formance (36.1-36.46). New York, NY: Wiley. Chater, N. (1996). Reconciling simplicity and likelihood principles in perceptual organization." Psychology Review, 103(3), 566-581. Jepson, A. Richards, W. (1992). What makes a good feature? (Memo #1356). MIT AI Lab.
2		Non-linear Diffusion for Segmentation	N. Sochen, R. Kimmel and R. Malladi, ``A General Framework for Low Level Vision", IEEE Trans. in Image Processing, Special Issue on Geometry Driven Diffusion, 7 (1998) 310-318. N. Sochen , ``Affine Invariant Flows via the Beltrami Framework'', Journal of Mathematical Imaging and Vision, 20:133-145, 2004. See Sochen and Kimmel's web pages for other related material. Donoho on Wavelet Shrinkage Weickert on connections between wavelet shrinkage and anisotropic diffusion
3.		Texture Segmentation	B.S. Manjunath and R. Chellappa. Unsupervised texture* segmentation using markov random field models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:478--482, 1991. 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.
4.		Segmentation Using Level Sets	Active contour without edges Chan, T.F.; Vese, L.A., IEEE Transactions on Image Processing, 10 (2), Feb. 2001, pp. 266 -277
5.		Diffusion Interpretations of Normalized Cut	On Spectral Clustering: Analysis and an algorithm, Andrew Y. Ng, Michael Jordan, and Yair Weiss. In NIPS 14,, 2002 Deepak Verma and Marina Meila "Comparison of Spectral Clustering Methods" (submitted). Learning Segmentation with Random Walk Marina Maila and Jianbo Shi Neural Information Processing Systems, NIPS, 2001 Segmentation using eigenvectors: a unifying view. Weiss Y. Proceedings IEEE International Conference on Computer Vision p. 975-982 (1999)
6.		Contour Grouping	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. P. Parent and S. W. Zucker. Trace inference, curvature consistency, and curve detection. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 11, August 1989. T. D. Alter and Ronen Basri, Extracting Salient Curves from Images: An Analysis of the Saliency Network, International Journal of Computer Vision, 27(1): 51-69, 1998.
7.		Graph Cuts for Segmentation (not normalized cut)	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. Kumar, M. P. , Torr, P. H. S. and Zisserman, A. OBJ CUT Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, San Diego (2005)
8.		Alpha Matting	A Bayesian approach to digital matting -YY Chuang, B Curless, DH Salesin, R Szeliski Bayesian video matting using learnt image priors - N Apostoloff, A Fitzgibbon - Computer Vision and Pattern Recognition, 2004.
9.		Background Subtraction	Non-parametric model for background subtraction, ElGammel, Harwood and Davis. Adaptive background mixture models for real-time tracking, Stuaffer and Grimson.
10.		Motion Segmentation	A. Jepson and M. Black, Mixture models for optical flow, Tech. Report, Res. in Biol. and Comp. Vision, Dept. of Comp. Sci., Univ. of Toronto, RBCV-TR-93-44, 1993

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)."

CMSC828J Advanced Topics in Information Processing: Image Segmentation

Description

Requirements

Class Schedule