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,
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, &
-- 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
-- Dr. Jianli Wang MD. Ph.D. (PSU Hershey Radiology)
-- Professor Jeff Cohn (
-- 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 data：Computational 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.
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
Curved
Glide-Reflection Symmetry Detection (In Press)
Seungkyu Lee and Yanxi Liu
Pattern Analysis and Machine Intelligence (PAMI) 2011
Image
De-fencing Revisited
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
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
Leonid Teverovskiy,
James Becker, Oscar Lopez, Yanxi Liu. 5th IEEE International Symposium on
Biomedical Imaging: From Nano to Macro. May 14-17,
2008.
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.