ETH Zurich - D-INFK - IVC - CVG - Lectures - Computational Regularity

Computational Regularity


Instructors: Prof. Yanxi Liu, Dr. Martin Oswald
Teaching assistant: Ian Cherabier
Lectures: Thursdays from 09:15-11:00 in CHN D 44
Exercises: Thursdays from 11:15-12:00 in CHN D 44

You may find additional information on the previous course webpage.

Course Abstract

Regularity is an essential and ubiquitous concept in nature, science and art. Numerous biological, natural or man-made structures exhibit regularities, abstracted by 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. With increasing amount and variety of digitized data, seeking for patterns systematically has become increasingly pertinent and necessary. This course concentrates on rigorous theory (group theory), keen observations and computational (automatic) discovery of patterns in various data forms in our daily life and our research. We aim to develop effective computational treatments of regularity to capture real world regular or near-regular patterns in spite of uncertainty.

Group theory, the ultimate mathematical theory for symmetry will not be textbook-learned only but practiced on real world digitized data sets. The course abandons the classical definition-theorem-proof model, instead, relies heavily on your senses and intuitions, 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 (covering 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, 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.

Lecture Syllabus (Tentative)

Sep 22, 2016Introduction of Regularity and Symmetry
Sep 29, 2016Symmetry groups. Classical mathematical definitions. Cyclic, Dihedral, Frieze groups.
Oct 06, 2016Wallpaper Groups
Oct 13, 2016No lecture and exercises
Oct 20, 2016Symmetry Detection Algorithms
Oct 27, 2016Symmetry Detection / Digital Papercutting
Nov 03, 2016Student Term Project Presentation
Nov 10, 2016Student Term Project Presentation (continued)
Human and Animal Perception of Patterns
Nov 17, 2016Symmetry Groups in Spatiotemporal Data
Nov 24, 2016Student Term Project Mid-Term Presentations
Dec 01, 2016Student Term Project Mid-Term Presentations (continued)
Dec 08, 2016Quantified regularity in Biomedical Image Applications
Dec 15, 2016Introduction to Pattern Theory
Exercise: finish pattern sorting game
Dec 22, 2016Student Term Project Final Presentations / Discussions

Course Material

The course is managed through the course management system moodle. All lecture material will be shared there and further all homeworks and exercises will be submitted through this system. Homeworks are generally to be submitted at latest the night before the next lecture, i.e. Wednesday midnight.

Course Grading

Written Homework30%
Presentations/Discussions20%
Term Project50%

References

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
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
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


© CVG, ETH Zürich lm@inf.ethz.ch