Group Theory and Its Applications in Robotics, Computer Vision/Graphics and Medical Image Analysis

 

Instructor: Yanxi LIU (Associate Research Professor)

Fall 2005

 
Course listing: 16899  Sect: B of College:  SCS  Department:  ROB
Course listing: 18799  Sect: D of College:  CIT  Department:  ECE

 

Time: Fridays 12:30 – 3:20pm

Location: NSH 3002

 

 

 

Yanxi's book chapter on Computational Symmetry

 

Description:

 

Group theory, the ultimate theory for symmetry, is a powerful tool that has a direct impact on research in robotics, computer vision, computer graphics and medical image analysis. This course starts by introducing the basics of group theory but abandons the classical definition-theorem-proof model. Instead, it relies heavily on intuitions in (1) 3D Euclidean space, images and patterns; (2) a geometric computational model; and (3) concrete, real world applications in robotics, computer vision, computer graphics and medical image analysis drawing from the instructor’s many years of research experience and from an emerging, vibrant, interdisciplinary international research community.  The material will be taught in a bottom-up (problems to theory) style based on the instructor’s manuscript of “Group Theory Applications in Robotics, Computer Vision and Computer Graphics”, state of art research papers and classical articles in prominent journals/books. The course emphasizes on motivations and justifications for the algorithmic usage of group theory in different domains, computational issues, and hands-on experimentation and illustration. The instructor encourages students to explore new applications while providing a handle on an elegant methodology and available computational tools. This course should be appropriate to any students who have an interest in real world problems that involve 3D Euclidean geometry, regularity, near-regular patterns and symmetry. It should be particularly attractive to students with computational inclinations of using algebraic theory in combination with other tools (e.g. graph theory, statistics). The goal is to provide the course material in a fairly high level of sophistication with intuition, formal justification and algorithmic ease.

JUSTIFICATION: This course addresses both a real need in graduate education and in research communities of using formal methods in symmetry, asymmetry and near-regularity. Symmetry is a pervasive phenomena in both natural and man-made (including biological) environments. Humans have an innate ability to perceive and take advantage of symmetry in everyday life, but it is not obvious how to automate this powerful insight on man-made intelligent beings, such as robots. On the surface, symmetry is simple and basic. In essence, the concept of symmetry is much more than a mirror reflection, rather, it can span a continuous spectrum of multi-dimensional spaces. In basic sciences, the understanding of symmetry played a profound role in several important discoveries including: relativity theory (the symmetry of time and space); human DNA structure (double helix); the quasi-crystals and their mathematical counterpart penrose tiles. We argue that reasoning about symmetry can likewise play a crucial part in the advance of artificial/machine intelligence.

A computational model for symmetry is especially pertinent to robotics, computer vision and machine intelligence in general, because in these fields we are studying how a man-made intelligent being can perceive and interact with the chaotic real world in the most effective way. Recognition of symmetries is the first step towards capturing the essential structure of a real world problem, and minimizing redundancy which can often lead to drastic reductions in computation. One fundamental limitation of computers is their finite representational power. One simple floating point error can destroy any perfect symmetry. One's ability to tolerate departure from perfect symmetry reflects one's level of sophistication in perception, which need to be built into the development of machine/artificial intelligence.

While a compelling mathematical theory of symmetry has existed for more than a century, very few computational tools prevail in recognizing and taking advantage of real world symmetry. One cause of this shortage is the discrepancy between the ideal algebraic formulation of symmetry, namely group theory, and the instantiation of symmetry in the noisy physical world. We have developed a computational framework that can effectively treat real world symmetry as statistical departure from regularity. The final goal of this course is to build perceptual systems that can recognize imperfect structural regularity or symmetry, while discriminating subtle pattern differences.

 

PLAN: The course will follow a text book on “Symmetry Group Applications” by Dr. Liu and state-of-the-art research papers. The course will be in the format of instructor lectures, student presentations, projects and term papers. Guest lectures (by speakers in and out of CMU) will expose students to applications in other domains (e.g. architecture, material science). Expected number of students: 15 to 25. Expected students: graduate or senior undergraduate. Total of 12 credits. Meeting once per week for a 3 hour-session.

 

SYLLABUS:

 

Week 1 (September 9): Regularity and Symmetry

 

What is regularity?

What is symmetry?

Why do we care about symmetry?

How is symmetry related to group theory?

 

An introduction to

 

(1) the spectrum of symmetry from regular to stochastic

 

n      near-regular texture synthesis: symmetry as a double-sided sward

 

(2) the formal concept of symmetry and symmetry groups

 

(3) computational challenges of computational symmetry

 

(4) Goals for this course --- yours and ours

 

References:

 

Near Regular Texture Analysis and Manipulation
Y. Liu, W. Lin, and J.H. Hays
ACM Transactions on Graphics (SIGGRAPH 2004), Vol. 23, No. 3, August, 2004, pp. 368 - 376.

 

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

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

1991

 

 

Week 2 (September 16):  Symmetry Groups rising from real world problems

 

Introduction to some basic concepts in group theory: definition of a group, subgroup, different types of (sub)groups, discrete, continuous, finite, infinitely countable, subgroup hierarchies, transformation groups, matrix representations with concrete examples from

 

n      robotics (surface contact and relative motion between 3D solids),

n      computer vision (periodic pattern perception),

n      papercut-art form

n      biomedical structures/images (the bilateral symmetry of human anatomy).

 

 

Why do we need group theory?

How do we use group theory in real problem formalization and computation?

 

 

Homework #1: understanding of symmetry and symmetry groups

 

References:

 

The First Chapter of ``Symmetry Groups in Robotics Assembly Planning and Specifications'', Yanxi Liu, the Mathematical Methods in Technology series, MARCEL DEKKER, INC., 270 Madison Avenue, New York, New York, 10016.

 

Chapter on Finite groups from group theory textbook. TBA.

 

Week 3 (September 23): How to use group theory on computers?

 

Example: finding relative positions of solids in surface contact using symmetry group representation and computation for assembly planning in robotics.

 

Representation and Computation of the Proper Euclidean Group and all its subgroups: Geometric Invariants.

 

Week 4 (September 30): Wallpapers and Frieze Patterns in Euclidean Space and their corresponding Symmetry Groups

 

Hilbert’s 18th problem and a computational model for periodic pattern perception

 

Homework #2: Literature review for symmetry detection algorithms

 

Week 5 (October 7): Computational Challenges in Symmetry Group Applications

 

From human and animal gaits, to the formalization of papercut-art forms.

 

Literature Reviews: Symmetry detection algorithms – what is the state of the art?

 

Week 6 (October 14): Guest lecture: a symmetry-based grammar of forms in architecture design

 

Week 7 (October 21, Midsemester-break): NO CLASS.

 

Week 8 (October 28): Student Project Proposal Presentations

 

Week 9 (November 4): Global Distortions and Symmetry Groups, Local Distortions and Near-Regular Texture Analysis/Synthesis/Manipulation/Tracking

 

Skewed Symmetry Groups: wallpaper groups and frieze groups

 

Near-Regular Textures: basic symmetry group concepts meet statistical computation

 

Week 10 (November 11):  Guest lecture: group theory in material science

 

Week 11 (November 18): Continues versus discrete cases: Lie group

 

Week 12 (November 25, Thanksgiving Holiday): NO CLASS

 

Week 13 (December 2):  Group theory applications in medical image analysis

 

Week 14 (December 9):  Group Theory and Statistics, Pattern Theory

 

Week 15: (December 16) Student project presentations

 

PREREQUISITES:

Basic algebra, transformations, computer vision/image analysis, robotics or approval of the instructor.

TEXT:
There will be no single text, but some course notes and papers will be distributed. Computer usage of your choice is also required.

METHOD OF EVALUATION:
Grading will be based on a set of homework assignments, one class project, one class presentation, and one term paper.