Computational Symmetry and Regularity

Course Number: CS468

Time: MF 2:15-3:30pm, Location: Gates B12

Computer Science, Stanford University

Prerequisites: Mathematical maturity (undergraduate-level algebra, geometry), capable of running existing code (executable or MATLAB code) and programming in your favorite computer language (MATLAB is OK).

Instructors: Professors Yanxi Liu (CSE and EE, PSU), Leo Guibas (CS, Stanford), Anthony Norcia (Psychology, Stanford)

>>> First Class: Monday, January 6, 2014 <<<

COURSE DESCRIPTION

This is a course on computational symmetry analysis methods for digitized data, with a unique mixture of theoretical and experimental bases drawn from group theory, pattern theory, statistical learning theory as well as human/animal/insect visual perception research. The students are trained throughout the course to apply theory and algorithms to real world scientific data, including imagery of human faces, urban scenes, zebra in the wild, crowds/cell videos, volumetric images of Zebrafish, C. elegans, neuroradiology images (MR, CT) and MoCap data of human dance/movements. Your own research data sets are welcome.

Motivation:

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, as well as our sense of beauty, is based on the perception and recognition of recurring structures (in space and/or time). With increasing amount and variety of digitized data, seeking for patterns systematically has become increasingly pertinent and necessary in this era of BigData. This course concentrates on rigorous theory, keen observations and automatic discovery of patterns in various data forms in our daily life and our research. We aim to develop effective computational treatments of symmetry to capture real world regular or near-regular patterns in spite of uncertainty.

Rational and Our Approach:

Group theory, the ultimate mathematical theory for symmetry, is not just learned abstractly from textbooks but practiced on real world digitized data sets. The course abandons the classical definition-theorem-proof model, and instead relies heavily on your senses, both visual and tactile, resulting in a solid understanding of group theory that you can touch! The key challenge of turning the concept of mathematical symmetry/regularity into a computationally useful tool is to figure out how to apply the concise group theory to the noisy albeit often near-regular real world. So far, a robust, general symmetry (all types of symmetries) detection algorithm for real world digital data (images or otherwise) remains to be elusive. This challenge leads to the unique role this course will explore computational symmetry (Liu 2000).

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. During the semester, we shall start with intuition and 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 may explore during this course include but are not limited to:

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

-- Static and dynamic near-regular textures (PSU Near-regular Texture Database): applications in computer graphics and computer vision

-- Dancing with (a)symmetry (motion capture data from traditional and modern style dancers, from ballet and 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 street view/Microsoft streetside)

-- Arts: Papercutting, quilting and paintings

-- Your own research data!

COURSE PLAN

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

Grading Policy

1. Written Homework (30%)

2. Presentations/Discussions (20%)

3. Term Project (50%)

TOTAL 100%

REFERENCE

We will use a combination of state of the art research articles and a few books. Some of them are listed below. On-line versions of relevant chapters will be provided to the students.

Computational Symmetry in Computer Vision and Computer Graphics (pdf file page)
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 Wentworth Thompson

SYLLABUS (tentative)

Week 1 (January 6) M: An Introduction of Regularity and Symmetry around us.

(January 10) F: What is a symmetry mathematically? How many types of symmetry?

Where are they? Present your examples (e.g. photos).

Week 2 (January 13) M: What is a symmetry group? Classic mathematical definitions.

Cyclic, Dihedral, Frieze groups. Your presentation on real world symmetries.

(January 17) F: Pattern sorting game

Week 3 (January 20) M: Martin Luther King, Jr., Day (holiday, no classes)

(January 24) F: Inner and inter-structures of Frieze and Wallpaper groups

Modern (and a computational) representation of group theory

(from Symmetries of Things)

Week 4 (January 27) M: Human/animal/insect Perception of Symmetry

(January 31) F: What has been done in Computational Symmetry (Groups)?

What is the latest in computational symmetry? (Student Presentations)

Week 5 (February 3) M: Symmetry as a continuous feature (via crowd sourcing)

(February 7) F: Computational challenges and Sample Applications: Biomedical Data

Week 6 (February 10) M: Student Term Project Proposal Presentations

(February 14) F: Guest Lecture (TBA)

Week 7 (February 17) M: An Introduction to Pattern Theory (Algebra meets Statistics)

(February 21) F: Computational Symmetry in 3D and beyond

Week 8 (February 24) M: Symmetry Groups in Spatiotemporal Data (from Crystals to Gait/Dance/Movement)

(February 28) F: Student Term Project Update Presentation

Week 9 (March 3) M: Texture Regularity: Analysis, Synthesis and Manipulation

(March 7) F: Regularity in saliency, segmentation (e.g. de-fencing),

matching and object recognition

Week 10 (March 10) M: Recurring Pattern Discovery

(March 14) F: Color Symmetry and Group Theory. Let’s finish the game: Pattern Sorting!

Week 11 (March 17-22): TBA: Student Term Project Presentation

A BIT OF HISTORY

A similar course has been offered in CMU/U. of Pittsburgh (Fall 2005) and PSU (Spring 2006, Fall 2006, Fall 2007, Spring 2009, Fall2009, Fall 2011, Fall 2012). Several student term projects from this course have been published. (Check http://vision.cse.psu.edu/publications/publications.shtml to find on-line copies)

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

Supervised Machine Learning for Brain Tumor Detection in Structural MRI

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

Radiological Society of North America (RSNA), 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

Computer Vision and Pattern Recognition Conference (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. 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. C. 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.