Computational Regularity

 (CSE 598G, #Schedule 76343, Three Credits)

Time: Wednesdays 2:00-4:30pm, Location: 333 IST Building

Professor Yanxi LIU yanxi@cse.psu.edu, CSE and EE of PSU

(http://www.cse.psu.edu/~yanxi/)

 

>>> First Class: 333 IST, 2pm, Wednesday, August 24, 2011 <<<

 

 

 

 

COURSE DESCRIPTION

 

This is a course on computational methods for real applications, based on a unique combination of group theory, pattern theory, statistical learning theory and human/animal/machine perception models. The students are trained to work with domain experts and apply theory and algorithms to real world scientific data, ranging from human faces, zebra horse skin textures, MoCap data of human dance/movements, to biological and medical data (e.g. plants, C. elegans and radiology neuroimages).

 

Symmetry or regularity is an essential and ubiquitous concept in nature, science and art. Numerous biological, natural or man-made structures exhibit symmetries as a fundamental design principle or as an essential aspect of their function. Whether by evolution or by design, symmetry implies potential structural efficiencies that make it universally appealing. Much of our understanding of the world is based on the perception and recognition of recurring structures (in space and/or time), and so is our sense of beauty. This course concentrates on keen observations and automatic discovery of symmetry patterns in various data forms in our daily life and our research. We develop effective computational treatments of symmetry to capture real world regular or near-regular patterns.

 

Group theory, the ultimate mathematical theory for symmetry, will be well motivated in this course by real world examples and be learned in an intuitive yet systematic manner. The course abandons the classical definition-theorem-proof model, instead, relies heavily on your senses, both visual and tactile, resulting in a solid understanding of group theory that you feel you can touch it!

 

Computation forms the key component of this course which links theory and applications. Students will witness effective computational models with concrete applications in robotics, computer vision, computer graphics and medical image analysis.

The emphasis is on hands-on computational experience and on producing state of the art, publishable research projects. From instructor’s past experience at CMU and PSU, this course is particularly attractive to graduate and senior undergraduate students in engineering and in sciences who appreciate the beauty of uncovering hidden patterns. As a consequence, material with a fairly high level of sophistication can be absorbed and utilized with relative ease.

 

The key challenge of turning the concept of symmetry into a computationally useful tool is to figure out how to apply the concise symmetry group theory to the noisy albeit often near-regular real-world. So far, a robust, widely applicable general symmetry (all types of symmetries) detection algorithm for real world digital data (images or otherwise) remains to be elusive in spite of many years of effort. This challenge leads to the unique role this course will explore “computational symmetry” (Liu 2001). During the semester, we shall start with intuition, learn the basic mathematical concepts and develop state of the art computer algorithms for real-world problems.  Our goal is to build “bridges” connecting, symmetry, symmetry group theory, general and specific regularities and real-world applications.

 

 

Data sets that we will explore during this semester include but are not limited to:

 

-- Publicly available object Recognition image sets (e.g. CalTech 256)

-- Static and dynamic near-regular textures (all types of data with near-periodical patterns): applications in computer graphics and computer vision

-- Dancing with (a)symmetry (motion capture data from traditional and modern style dancers,  from ballet, Japanese traditional dance to disco dances)

-- Human brain asymmetries (quantitative evaluation of age, gender and pathological differences)

-- 3D and 4D Human faces (3D face with expression variations)

-- Tracking of near-regular patterns (Marching bands – PSU blue band videos, cardiac tagged MRI videos)

-- Urban scene analysis and synthesis (Google map and Microsoft “street view”)

-- Biology data set (plants, zebrafish, C. elegans video/images)

-- Arts: Papercutting, quilting and paintings

-- Your own research data!

 

 

REFERENCE

 

We will use a combination of state of the art research articles and few classically acclaimed books. Some of them are listed below. Relevant on-line portions of the book will be provided to the students.

 

Computational Symmetry in Computer Vision and Computer Graphics
Yanxi Liu and Hagit Hel-Or and Craig S. Kaplan and Luc Van Gool
Foundations and Trends® in Computer Graphics and Vision 2010
Volume 5, Number 1-2, Pages 199

 

 

 

The Symmetries of Things by John H. Conway, Heidi Burgiel and Chaim Goodman-Strauss (May 2, 2008). A. K. Peters, Ltd. Wellesley, Massachusetts. Pages 426.

 

 

Symmetries of Culture: Theory and Practice of Plane Pattern Analysis. Dorothy K. Washburn, Donald W. Crowe 1991

 

 

Computational Symmetry Symmetry 2000, Portland Press, London, Vol. 80/1, January, 2002, pp. 231 - 245.

 

 

On Growth and Form, D’Arcy Thompson

 

 

COURSE PLAN

 

The course will be taught in the form of instructor lectures, guest lectures and student presentations.

 

Guest lectures (tentative and not limited to):

 

-- Professor Venkatraman Gopalan (PSU Materials Science and Engineering, Associate Director, Center for Optical Technologies)

-- Professor Rick Gilmore (PSU Psychology, Director of Human Imaging, Social, Life, & Engineering Sciences Imaging Center (SLEIC))

-- Dr. Dan T.D. Nguyen, MD (PSU, Chief and Program Director of Neuroradiology)

-- Professor Hong Ma, (PSU, Distinguished Professor of Biology, Professor and Dean of Life Sciences at Fudan University)

-- Dr. Jianli Wang MD. Ph.D. (PSU Hershey Radiology)

-- Professor Jeff Cohn (Univ. of Pittsburgh, Psychology)

-- Professor Robert Collins (PSU, CSE)

 

Qualifications of Expected Students: graduate and senior undergraduate students from all disciplines with basic knowledge in algebra and geometry and basic programming skills. More importantly, it is desirable to have an open-mindedness to across academic boundaries, a curiosity to learn one of the most abstract mathematical theories, group theory, through a hands-on experience, and a desire to experiment with real data and publish.

Maximum number of students: 12.

 

Grading Policy

1. Written Homework           (15%)

2. Oral Presentations             (15%)

3. Class Participation            (10%)

4. Term Project & Write-up (60%)

5. Extra Credit                       (10%)

-------                                      110% total

 

 

 

SYLLABUS

 

 

Week 1 (August 24) An Introduction of Regularity and Symmetry around us

 

Week 2 (August 31) What is a symmetry, informally and formally? Where are they?

 

Week 3 (September 7) What is a symmetry group? Math and reality

 

Week 4 (September 14): The inter and inner structures of symmetry groups – surprising facts about the symmetry groups of periodic patterns

 

Week 5 (September 21): What has been done in Symmetry Detection from Real World Images ?

Literature Review + Student Presentations

 

Week 6 (September 28):  Guest Lecture by Professor Gopalan: Rotation-reversal symmetries in crystals and handed structures

 

Week 7 (October 5) Fundamentals and Applications: Problem Formulation and Methodology Development

 

Week 8 (October 12): Applications of symmetry/regularity in real dataComputational Symmetry (Groups) in Computer Vision and Computer Graphics

 

Week 9 (October 19): Student Term Project Proposal Presentations (about 20-25 min each)

 

Week 10 (October 26): Quantified Regularity Measurements (symmetry as a continuous feature, Facial asymmetry)

 

Week 11 (November 2): Computational Regularity in Biomedical Data (methodology and applications, Term Project update

                                            

Week 12 (November 9): Symmetry Perception by Human and Animal (insects), New Symmetries, Guest Lectures

 

Week 13 (November 16):  An Introduction to Pattern Theory (Algebra meets Statistics)

 

Week 14 (November 30):  Symmetry Groups in Gait/Dance/Movement Analysis

 

Week 14 (December 7): Student Term Project Presentations

 

 

STUDENTS FEEDBACK (CMU, U. Pittsburgh, PSU)

 

 

Computational Symmetry is the most unique course that I have taken. It provided me with an introduction to Group Theory with practical applications rather than as an abstract idea. But most importantly, the course allowed me to view the field of Computer Vision from a completely new angle. Symmetry is ubiquitous and can be used as a stepping stone to solve many seemingly unrelated computer vision problems. This is an insight that would have not been possible for me (to see) not for this course.  

 

 

 

This course exposed me to the state-of-the-art in Facial Analysis Research. Through the  literature survey that I did  for my project, I came across many  interesting experiments/research going on in this field. I also learned a lot from the work of other members of this class. This course made me aware of the symmetry around us, which we hardly seem to notice in our day-to-day work. It also exposed me to the amazing and diverse applications of symmetry. I think this course compliments computer vision courses. The techniques learned in this course (e.g Frieze analysis) provide a novel way to analyze video data. Though the Projects in this course are a little challenging, but it also gives an opportunity to learn. I suggest fixing some objective goals for the project very early in the semester and working towards it. In case the enrollment is high for the course, it might be useful to divide students into groups so that more complex projects can be accomplished in a semester. On the whole, I enjoyed this course.  

 

 

 

Anyone feeling as though their research in image processing or computer vision has reached a "plateau" or has otherwise stagnated should seriously consider studying computational symmetry, and this course is an un-intimidating yet thorough introduction to the field. The mathematical treatment of group theory is not trivial, but it is also relatively painless -- even for those who, like me, don't have as strong a background in mathematics or computer science as some of the other students. Once you cover the mathematics and have access to the codes, then you can really let loose on the applications. It helps if you can "bring your own project" to the course -- if it's something you're already passionate about, you'll find that the exchange of ideas in the course will stimulate you to think about your project in completely different way. To that end, the small class size is a benefit, as it helps to promote discussion, and in doing so, the class feels more like a research lab, and hopefully you and your new "labmates" will inspire each other over the course of the semester. As it has been largely (and inexplicably) overlooked in the CV community, the field of computational symmetry is ripe for the picking -- so jump in now, make an impact, and become one of the early pioneers! 

 

 

 

 

The course, I felt and still feel that what you teach is fundamental and that everyone should know it.  The tools you provide helped solidify my understanding of geometry and I only wish I had more time to dedicate to studying the topic.  I believe that this course should be taught to first year computer vision graduate students because it will help give them a better appreciation for the role of geometry in computer vision and supply some building blocks that they need for other endeavors.  I like the projects.  I do think they're hard, but that's the appeal.

 

 

The most exciting part of the course is the exposure to the existence of symmetry. The variety of the selected topics provides me a 'symmetry' glass to re-examine the surrounding world. The course projects are also very interesting. I enjoyed a lot in doing own my project and the discussions about others' projects.  The detailed feedback from you was very helpful. I was always interested when you were sharing your hands-on experiences. It made me learn a lot not only for this project but also general approaches in research. Thank you! The course successfully arose my interests in symmetry group, especially, the challenge of computational symmetry. Though I hope we could go deeper in some topics. But I don't think it's possible to squeeze more in such a short time.

 

 

My comments are as follows. I gave the class a very high ranking because it was immensely useful to me to learn about wallpaper groups and invariance under group action. I also had a lot of fun, which speaks to the nature of the work discussed. Overall, since my principal interest has always been how the human brain uses invariance under transformation as a code, the experience gained from this course will help me give a more rigorous account of invariance under transformation than others in the field. The process of presenting incremental results was also very useful, and helpful in helping me to accustom myself to the research process.

 

The only thing that I should add is that it would be nice to cover more of the Lie Group stuff in the context of Computer Vision, since it is so ubiquitous. If you could get one of the statisticians you have worked with in the past to help you, you could also make the course more appealing to a wider audience by concentrating on less regular structures that still have symmetries (NRT's are just one example). If this could be cross-listed as a statistics course, you would get many more people, because the common misconception about group theory is that it is useless in the face of real data (because real data is noisy).

 

 

 

I think the course was great. I learn a lot about symmetry that I didn't know could have existed and could be used to complement other computer vision techniques.

 

 

 

I enjoyed the course.  Specifically I enjoyed the term project.  Feedback from you and from the class was very helpful when formulating a machine learning algorithm to solve my specific problem.  It is very helpful to work with real world problems of our choosing.  I'm glad that we didn't only focus on theory in this course.  Real world problems give us the ability to try to think through a problem critically which is invaluable considering that a majority of the people in the class will move into careers where they will have to solve their own real world problems and even lead others to do the same.

 

 

 

I think this course is great. I not only learned about symmetry theory, but also learned machine learning and related approaches to solve real problem. And I also realized the big gap and ambiguity between human perception and

machine computation.

 

 

 

A BIT OF HISTORY

 

An earlier, less diverse version of this course has been offered in CMU (Fall 2005) and PSU (Spring 2006, Fall 2006, Fall 2007, Spring 2009, Fall2009).  A total of ~50 students have taken this course taught by Professor Liu. Several research papers by the students who took the course have published in the subsequent years.

 

(Check http://vision.cse.psu.edu/publications/publications.shtml to find on-line copies)

 

 

Supervised Machine Learning for Brain Tumor Detection in Structural MRI (to appear)

D Koshy, D T Nguyen, MD; C Yu; S Kashyap; R T Collins; Y Liu

Radiological Society of North America (RSNA), 2011

 

Curved Glide-Reflection Symmetry Detection (In Press)
Seungkyu Lee and Yanxi Liu
Pattern Analysis and Machine Intelligence (PAMI) 2011

 

Image De-fencing Revisited
Minwoo Park and Kyle Brocklehurst and Robert T. Collins and Yanxi Liu
Asian Conference on Computer Vision (ACCV) 2010

 

Curved Reflection Symmetry Detection with Self-validation
Jingchen Liu and Yanxi Liu
Asian Conference on Computer Vision (ACCV) 2010

 

Translation-Symmetry-based Perceptual Grouping with Applications to Urban Scenes
Minwoo Park and Kyle Brocklehurst and Robert T. Collins and Yanxi Liu
Asian Conference on Computer Vision (ACCV) 2010

 

Skewed Rotation Symmetry Group Detection
Seungkyu Lee and Yanxi Liu
Pattern Analysis and Machine Intelligence (PAMI) 2010
Volume 32, Number 9, Pages 1659 - 1672

 

Multi-Target Tracking of Time-Varying Spatial Patterns
Jingchen Liu and Yanxi Liu
Computer Vision and Pattern Recognition (CVPR) 2010

 

Deformed Lattice Detection in Real-World Images using Mean-Shift Belief Propagation
Minwoo Park and Kyle Brocklehurst and Robert T. Collins and Yanxi Liu
Pattern Analysis and Machine Intelligence (PAMI) 2009
Volume 31, Number 10, Pages 1804-1816

 

Curved Glide-Reflection Symmetry Detection (oral, acceptance rate: 4%)
Seungkyu Lee and Yanxi Liu
Computer Vision and Pattern Recognition (CVPR) 2009

 

Deformed Lattice Detection via Mean-Shift Belief Propagation

Minwoo Park, Robert T. Collins, and Yanxi Liu

European Conference on Computer Vision (ECCV), Marseille, France, October 2008.

 

Rotation Symmetry Group Detection Via Frequency Analysis of Frieze-Expansions

Seungkyu Lee, Robert T. Collins and Yanxi Liu

Computer Vision and Pattern Recognition Conference (CVPR '08)

 

Performance Evaluation of State-of-the-Art Discrete Symmetry Detection Algorithms.

Minwoo Park, Seungkyu Lee, Po-Chun Chen, Somesh Kashyap, Asad A. Butt and Yanxi Liu (CVPR '08)

 

Quantified Brain Asymmetry for Age Estimation of Normal and AD/MCI Subjects.

Leonid Teverovskiy, James Becker, Oscar Lopez, Yanxi Liu. 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro. May 14-17, 2008. Paris, France.

 

Automatic Lattice Detection in Near-Regular Histology Array Images

B.A. Canada, G.K. Thomas, K.C. Cheng, J.Z. Wang, and Y. Liu. Proceedings of the IEEE International Conference on Image Processing, October 2008.

 

Quantified Symmetry for Entorhinal Spatial Maps
E. Chastain and Y. Liu   (first author was a CMU undergraduate student)
Special Issue in Neurocomputing Journal, Vol. 70, No. 10 - 12, June, 2007, pp. 1723 - 1727.

 

Shape Variation-based Frieze Pattern for Robust Gait Recognition
S. Lee, Y. Liu, and R. Collins. Proceedings of CVPR 2007, June, 2007.

 

A Lattice-based MRF Model for Dynamic Near-regular Texture Tracking
W. Lin and Y. Liu
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 29, No. 5, May, 2007, pp. 777 - 792.

 

Discovering Texture Regularity as a Higher-Order Correspondence Problem
J.H. Hays, M. Leordeanu, A.A. Efros, and Y. Liu
9th European Conference on Computer Vision, May, 2006.

 

Truly 3D Midsagittal Plane Extraction for Robust Neuroimage Registration
L. Teverovskiy and Y. Liu
3rd IEEE International Symposium on Biomedical Imaging: Macro to Nano, 2006, April, 2006, pp. 860 - 863.