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

 

Instructor: Yanxi LIU (Associate Research Professor)

Office Location 4109 NSH

Office Hours: by appointments

 

Fall 2005

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

 

 

 

 

 

 

 

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

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

 

Reference Material:

 

A text book manuscript on “Symmetry Group Applications” by Professor Liu

 

Generators and Relations for Discrete Groups by Coxeter and Moser

4th Edition, Springer-Verlag

 

Contemporary Abstract Algebra by J. A. Gallian

D.C. Heath and Company

 

Groups: A path to geometry by R.P. Burn

Cambridge University Press

 

And

 

A collection of state-of-the-art research papers.

 

Format

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

Grading Policy

You will be graded on the following items:

1. Written Homework

(20%)

2. Oral Presentations

(20%)

3. Class Participation

(10%)

4. Term Project & Write-up

(50%)

5. Extra Credit

(10%)

 

--------

 

110% total

 

 

Syllabus

 

Week 1 (September 9): Regularity and Symmetry ( slides )

 

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):  Different Types of Symmetries and Symmetry Groups rising from real world problems ( slides )

 

Introduction to some basic concepts in group theory: definition of a group, group action and orbits, 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     periodic patterns and frieze/wallpaper groups

n     papercut-art form

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

 

 

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.

 

Chapters on Finite groups from Contemporary Abstract Algebra by J. A. Gallian

D.C. Heath and Company

 

 

 

 

Week 3 (September 23): Computational Symmetry: Problem Formalization (Part I) ( slides )

 

 

 

n     Surface contact and relative motion between 3D solids: problem formalization,

n     looking for symmetry groups in papercut-art forms for synthesis, folding and cutting (James Hays)

n     Bilateral human brain anatomy: Midsagittal Plane extraction from 3D MR neuroimages  (Leonid Teverovskiy).

 

 

 

 

Week 4 (September 30): Computational Symmetry: Group Representation (orbits)  (Part II all slides included in Part I)

 

Homework #1 due today

 

 

How to represent and compute different types of subgroups of the Proper Euclidean Group?

How to relate discrete with continuous groups?

 

                                                                                            -----------   Geometric Invariants (review the concept of orbits).

 

How to quantify symmetry/asymmetry of biological structures?

 

                                                                                            ----------- a simple interplay of symmetry and statistics

 

n     Robotics surface contact and relative motion between 3D solids: group representation and operation on computers 

n     periodic patterns and frieze/wallpaper groups: Euclidean cases Hilbert’s 18th problem revisited

n     Quantified facial asymmetry for expression invariant subject recognition

n     Age estimation from Statistical Measures of Human Brain Asymmetry  (Leonid Teverovskiy).

 

 

In the Second half of the class:

 

Short presentations by students on a summary of the three symmetry/group related papers each of you has found

 

 

 

 

 

Week 5 (October 7): Departures from Regularity: Global and Local Distortions of Wallpaper Patterns and their Symmetry Groups

 

n     Near-Regular Textures: basic symmetry group concepts meet statistical distortion

n     NRT applications: analysis, synthesis, and manipulation

n     Dynamic NRT tracking  (W.C. Lin)

n     Automatic NRT lattice extraction as a correspondence problem (J. Hays)

 

 

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.

 

The Promise and Perils of Near-Regular Texture [publication grayscale version]
Y. Liu, Y. Tsin, and W. Lin
International Journal of Computer Vision, Vol. 62, No. 1-2, April, 2005, pp. 145 - 159.

 

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

1991

 

CMU Near-Regular Texture Database

 

 

 

Homework #2:      (1) Proof of the existence of seven frieze groups

                               (2 )Wallpaper pattern classification by you (a fun practice)

                               (3) Literature review for symmetry detection algorithms (choose an area of interest in preparation for your class project)

                                    

 

Week 6 (October 14): Guest lecture by Professor Moustapha: Exploring Architectural Designs by means of Group Transformations

 

 

ABSTRACT

 

Design is often described as an exploration: a search for an adequate solution amongst a space of alternatives (Simon 1969). Navigation thought this space involves the development and transformation of alternatives, in the quest for improving the solution's quality. During the exploratory, early phases of architectural design, configurations continually evolve, though modifications of both configuration elements and spatial relations among these elements. Higher-level explorations, thought spatial relationships, yield intellectually stimulating results. These, however, are labor intensive, because they require modification of multiple elements. Such repetitive interaction considerably slows down the exploration, and often discourages it completely, particularly when configurations are complex and interrelations are numerous. My research addresses the computational representation of design configurations, in order to maximize their exploratory potential. It is motivated by the necessity of flexible geometry for early design exploration and by the intellectual stimulation provided by (and the difficulty involved with) the exploration of complex relationships. For this presentation, "Exploring Architectural Designs by means of Group

Transformations", I will review design representations for exploration, and introduce the Interactive Configuration Exploration (ICE) framework, which is a computational representation based on group transformations encapsulating spatial relations. I will discuss the capacity of ICE for describing 3D shapes and configurations, and for describing frieze/wallpaper groups, as well as transformation across those groups. I will conclude by discussing extensions and potential application of the ICE framework.

 

The ICE framework, consist of two parallel endeavors: a notation and a computer implementation. The ICE notation is a formalism for describing shapes and configurations by means of generative transformations. The ICE implementation is a 3D modeling system that supports the exploration of shapes and configurations by means of manipulating parameters of generative transformations. The ICE framework classifies spatial relations into layers based on group transformations, variations, operations, and constraints. It defines methods for generation, and strategies for the compositions of simple relations into higher level organizational structures, in order to maximize the possible types configurations it can describe. By using the ICE framework one can design, generate and manipulate design configurations.

 

 

 

MINI BIOGRAPHY

 

Hoda Moustapha has completed her PhD in Computational Design from the

School of Architecture at Carnegie Mellon University. Hoda is currently an

assistant professor at Chatham College's Interior Architecture Program.

Hoda has co-taught courses in geometric modeling, spatial constructions and

grammar implementations and she is currently teaching courses in computer

aided design, geographical information systems, color psychology, and

materials/assemblies. Hoda worked in the Center for Building Performance

and Diagnostics and she is part of the Green Building Alliance. Hoda

published papers in the Design Studies Journal, as well as in the following

conference proceedings: Generative CAD Systems (GCAD'04), Design Computing

and Cognition (DCC'04), and Mathematic and Design 2001.  Hoda also

exhibited her own artwork at Carnegie Mellon University, at University of

Pittsburgh and at the Frick Art Museum.

 

 

 

Reference:

 

Hoda's WWW: Research

 

 

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

 

Week 8 (October 28): Student Project Proposal Presentations (about 20-25 min each)

 

n     In your area of interest: What is the state of the art in computational symmetry?

n     Propose your computational symmetry projects and initial results (if any) in detail: PowerPoint presentation preferred

 

 

1.    asymmetry of brain as a predictor of age

2.    gait recognition using symmetry analysis

3.    expression classification using wavelet packet correlation methods on facial asymmetry

4.    symmetry as a (neural) code

5.    detection of lattice regions in architectural images

6.    symmetry detection as a higher order correspondence problem

 

 

 

Week 9 (November 4): Quantified Regularity Measurements (slides)

 

·       Facial Asymmetry as a biometric

·       2D facial asymmetry for human identification and expression classification

·       3D facial asymmetry for gender classification

·       “Symmetry As a Continuous Feature”

 

References:

 

Facial Asymmetry Quantification for Expression Invariant Human Identification

Y. Liu, K. Schmidt, J. Cohn, and S. Mitra
Computer Vision and Image Understanding Journal, Vol. 91, No. 1/2, July, 2003, pp. 138 - 159.

 

 Local Facial Asymmetry for Expression Classification

S. Mitra and Y. Liu
Proceedings of the 2004 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'04), June, 2004.

 

A Quantified Study of Facial Asymmetry in 3D Faces

Y. Liu and J. Palmer
Proceedings of the 2003 IEEE International Workshop on Analysis and Modeling of Faces and Gestures, in conjunction with the 2003 International Conference of Computer Vision (ICCV '03), October, 2003.

 

Symmetry as A Continuous Feature

Zabrodsky, H.; Peleg, S.; Avnir, D.;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume 17,  Issue 12,  Dec. 1995 Page(s):1154 - 1166

 

Comments on "Symmetry as a Continuous Feature"

Kenichi Kanatani

 

Volume 19 ,  Issue 3  (March 1997)

Pages: 246 - 247  

Year of Publication: 1997

 

Homework #2 Due

 

 

Week 10 (November 11):  Computational symmetry applications in medical image analysis I

 

·      student course projects update

·      Introduction to Medical Image Analysis: segmentation (slides)

 

 

References:

 

 

Application papers

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/AltersonPlewes2003.pdf

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/ChineseXueDong2005.pdf

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/MEDIA03-Joshi-brain.pdf

 

Methodology papers:

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/pizer1993.pdf

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/IJCV03-Pizer-mreps.pdf

 

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/IPMI03_Fletcher_GausDist.pdf

 

http://www.cs.cmu.edu/~yanxi/www/images/GroupTheory/IPMI03_Yushkevich.pdf

 

 

                                        

Week 11 (November 18): Computational symmetry applications in medical image analysis II

 

·      Medical image segmentation continued (slides)

·      Medical image analysis and Discussion of papers (slides)

 

 

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

 

 

Week 13 (December 2):  Lie group and Pattern Theory

 

Homework #3 due

 

Extra Credit homework (10%):

 

Literature Review on the topic Computational Symmetry, contribute your view to a survey paper on an existing, and ever expanding list of computational symmetry and symmetry group related papers!

 

Seek the list from Professor Liu if you are interested.

 

 

Week 14 (December 9):  Student project presentations (register your project topic and your time slot with Prof. Liu)

 

Week 15: (December 16) Student project presentations (register your project topic and your time slot with Prof. Liu)

·      Course Project Due (report, program and the most relevant papers)

·      Extra credit homework can be handed in two days later.