Table Of Content

Preface This book presents a collection of contributions concerning the task of solv- ing geometry related problems with suitable algebraic embeddings. It is not only directed at scientists who already discoveredthe powerof Cli(cid:11)ord algebras for their (cid:12)eld, but also at those scientists who are interested in Cli(cid:11)ord algebras and want to see how these can be applied to problems in computer science, signal theory, neural computation, computer vision and robotics. It was therefore tried to keep this book accessible to newcomers to applications of Cli(cid:11)ord algebra while still presenting up to date research and new developments. Theaimofthebookistwofold.Itshouldcontributetoshiftthefundamen- talimportanceofadequategeometricconceptsintothefocusofattention,but also show the algebraicaspects of formulating a particularproblem in terms of Cli(cid:11)ord algebra. Using such an universal, general and powerful algebraic frameasCli(cid:11)ordalgebra,resultsinmultiplegains,suchascompleteness,lin- earityand lowsymboliccomplexityof representations.Evenproblemswhich may not usually be classi(cid:12)ed as geometric, might be better understood by the human mind when expressed in a geometric language. As a misleading tendency, mathematical education with respect to geometric concepts disappears more and more from curricula of technical sub- jects. To a certain degree this is caused by the mathematicians themselves. What mathematicians today understand as geometry or algebraic geometry is far from beeing accessible to engineers or computer scientists. This is the more regrettable as the Erlangen program of Felix Klein [136] on the strong relations between algebra and geometry is of great potential also for the applied sciences. This book is a (cid:12)rst attempt to overcome this situation. As computer scientists and engineers know in principle of the importance of algebra to gain new qualities of modelling, they will pro(cid:12)t from geometric interpreta- tions of their models. This was also the experience the authors of this book had made. However, it is not necessarily trivial to translate a geometry related problem into the language of Cli(cid:11)ord algebra. Once translated, it also needssomeexperiencetomanipulateCli(cid:11)ordalgebraexpressions.Themany appliedproblemspresentedinthis bookshouldgiveengineers,computersci- VI Preface entists and physicists a rich set of examples of how to work with Cli(cid:11)ord algebra. Theterm‘geometricproblem’willattimesbeunderstoodveryloosely.For instance,whatrelationexistsbetweenaFouriertransformoritscomputation asFFT(fastFouriertransformalgorithm)andgeometry?Itwillbecomeclear thattheFouriertransformisstronglyrelatedtosymmetryasgeometricentity and that its multidimensional extension necessitates the use of an adequate algebraic frame if all multidimensional symmetries are to be kept accessible. William K. Cli(cid:11)ord (1845{1879)[47] introduced what he called \geometric algebra1".It is ageneralisationof HermannG. Grassmann’s(1809{1877) exterioralgebraandalsocontainsWilliamR.Hamilton’s(1805{1865)quaternions. Geometric or Cli(cid:11)ord algebra has therefore a strong unifying aspect, sinceitallowsustoviewdi(cid:11)erentgeometryrelatedalgebraicsystemsasspe- cializations of one \mother algebra". Cli(cid:11)ord algebras may therefore (cid:12)nd a useinquitedi(cid:11)erent(cid:12)eldsofscience,whilestillsharingthesamefundamental properties. DavidHesteneswasoneofthe(cid:12)rstwhorevivedGAinthemid1960’sand introduced it in di(cid:11)erent (cid:12)elds of physics with the goal to make it a uni(cid:12)ed mathematicallanguagethatencompassesthesystemofcomplexnumbers,the quaternions,Grassmann’sexterioralgebra,matrixalgebra,vector,tensorand spinoralgebrasandthe algebraof di(cid:11)erentialforms.Inordertoachievethis, hefashionedhisGAasaspecializationofthegeneralCAwhichisparticularly well suited for the use in physics and, as it turned out, engineering and computerscience.ItishismeritthatGAgotwidelyacceptedindiverse(cid:12)elds of physics[116,113]andengineering.ThealgebramostsimilartoHestenes’s GA is probably Grassmann’s exterior algebra which is also used by a large part of the physics community [86]. Those readers who are interested in the evolution of the relations between algebra and geometry can (cid:12)nd a short overview in [245]. I (cid:12)rst became interested in Cli(cid:11)ord or geometric algebra by reading a shortpaperinPhysicsWorld,writtenbyAnthonyGarrett[89].Atthattime I was searching for a way to overcome some serious problems of complete representations of local, intrinsically multidimensional structures in image processing.Igotimmediatelyconvincedthatthealgebraiclanguagepresented in this paper would open the door to formulate a real multidimensional and linear signal theory. Since then we not only learned how to proceed in that way, but we also discovered the expressive power of GA for quite di(cid:11)erent aspects of multidimensional signal structure [34, 85]. In the Cognitive Systems research group in Kiel, Germany, we are working on all aspects concerning the design of seeing robot systems [221]. This includes pattern recognition with neural networks, computer vision, multidimensional signal theory and robot kinematics. We found that in all these 1 Today the terms \geometric algebra" (GA) and \Cli(cid:11)ord algebra" (CA) are being used interchangeably. Preface VII (cid:12)elds GA is a particularly useful algebraic frame. In the process of this research we made valuable experiences of how to model problems with GA. Several contributions to this book present this work2. Designingaseeingrobotsystemisataskwherequiteanumberofdi(cid:11)erent competences have to be modelled mathematically. However, in the end the wholesystemshouldappearasone.Furthermore,allcompetenceshavetobe organizedorhavetoorganizethemselvesinacycle,whichhasperceptionand actionastwopoles.Therefore,it isimportanttohaveacommonmathemat- ical language to bring the diverse mathematical disciplines, contributing to thediverseaspectsoftheperception-actioncycle,closertogetherandeventu- ally to fuse them to a general conception of behaviour based system design. In 1997 we brought to life the international workshop on algebraic frames for the perception-action cycle (AFPAC) [223], with the intention to further this fusion of disciplines under the umbrella of a uni(cid:12)ed algebraic frame. This workshop brought together researchers from all over the world, many of whom became authorsin this book. In this respectthis bookmay be considered acollectionof researchresultsinspired bythe AFPAC’97.Hopefully, the AFPAC 2000 workshopwill be of comparable success. Anothermid-rangegoalisthe designof GAprocessorsforreal-timecom- putations in robot vision. Today we have to accept a great gap between the low symbolic complexity on the one hand and the high numeric complexity ofcodinginGAontheotherhand.Becauseavailablecomputerscannoteven process complexnumbersdirectly,we havetopayahigh computationalcost attimes,whenusingGAlibraries.Insomecasesthisisalreadycompensated by the gain achieved through a concise problem formulation with GA. Nev- ertheless, full pro(cid:12)t in real-time applications is only possible with adequate processors. The book is divided into three main sections. Part I (A Uni(cid:12)ed Algebraic Approach for Classical Geometries) intro- ducesEuclidean,sphericalandhyperbolicgeometryintheframeofGA.Also the geometric modelling capabilities of GA from a general point of view are outlined. In this (cid:12)rst part it will become clear that the language of GA is developingpermanentlyandthatbyshapingthislanguage,itcanbeadapted to the problems at hand. David Hestenes, Hongbo Li and Alyn Rockwood summarize in chapter 1 the basic methods, ideas and rules of GA. This survey will be helpful for the readerasa generalreferencefor all other chapters.Of chapters 2,3, and 4, written by Hongbo Li et al., I especially want to emphasize two aspects. Firstly, the use of the so-called conformal split as introduced by Hestenes [114] in geometric modelling. Secondly, the proposed uni(cid:12)cation of classical geometries will become important in modelling catadioptic camera systems (see [91]), possessing both re(cid:13)ective and refractive components, for robot vision in a general framework. In chapter 6 Leo Dorst gives an introduction 2 This research was fundedsince 1997 bythe DeutscheForschungsgemeinschaft. VIII Preface to GA which will help to increase the in(cid:13)uence of GA on many (cid:12)elds in computer science. Particularly interesting is his discussion of a very general (cid:12)lter scheme. Ambjo(cid:127)rn Naeve and Lars Svensson present their own way of constructing GA in chapter 5. Working in the (cid:12)eld of computer vision, they choosetodemonstratetheirframeworkinapplicationstogeometricaloptics. Part II (Algebraic Embedding of Signal Theory and Neural Computa- tion)isdevotedtothedevelopmentofalineartheoryofintrinsicallymultidi- mensional signals and to make Cli(cid:11)ord groupsaccessible in neural computa- tionswiththeaimofdevelopingneuralnetworksasexpertsofbasicgeometric transformations and thus of the shape of objects. This part is opened by a contribution of Valeri Labunets and his daugh- ter Ekaterina Rundblad-Labunets, both representing the Russian School of algebraists. In chapter 7 they emphasize two important aspects of image processing in the CA framework. These are the modelling of vector-valued multidimensionalsignaldata,includingcoloursignals,andtheformulationof invariants with that respect. Their framework is presented in a very general setting and, hopefully, will be picked up by other researchers to study its application. The other six chapters of part II are written by the Kiel Cognitive Sys- temsGroup.Inchapters8to11ThomasBu(cid:127)low,MichaelFelsbergandGerald Sommer, partially in cooperation with Vladimir Chernov, Samara (Russia) forthe (cid:12)rsttime areextensivelypresentingthe waytorepresentintrinsically multidimensionalscalar-valuedsignalsinalinearmannerbyusingaGAem- bedding. Several aspects are considered, as non-commutative and commuta- tivehypercomplexFouriertransforms(chapters8,9),fastalgorithmsfortheir computation (chapter 10), and local, hypercomplex signalrepresentationsin chapter 11. As a (cid:12)eld of application of the proposed quaternion-valued Ga- bortransforminthe twodimensionalcase,theproblemof textureanalysisis considered.Inthatchaptertheoldproblemsofsignaltheoryasmissingphase conceptsof intrinsicallytwodimensionalsignals,embedded in2Dspace,and the missing completeness of local symmetry representation (both problems have the same roots) could be overcome. Thus, the way to develop a linear signal theory of intrinsically multidimensional signals is prepared for future research. Quite a di(cid:11)erent topic is handled by Sven Buchholz and Gerald Sommer in chapters12 and 13. This is the design of neurons and neural nets (MLPs) which perform computations in CA. The new quality with respect to modelling neural computation resultsfrom the fact that the use of the geometric product in vector spaces induces a structural bias into the neurons. Looking onto the data through the glasses of \CA-neurons"givesvaluable contraints whilelearningtheintrinsic(geometric)structureofthedata,whichresultsin an excellent generalization ability. As a nearly equally important aspect the complexityofcomputationsisdrasticallyreducedbecauseofthelinearization Preface IX e(cid:11)ects of the algebraic embedding. These nets indeed constitute experts for geometric transformations. Part III (Geometric Algebra for ComputerVision and Robotics) is con- cernedwithactualtopicsofprojectivegeometryinmodellingcomputervision tasks (chapters 14 to 17) and with the linear modelling of kinematic chains of points and lines in space (chapters 18 to 21). In chapter 14, Christian Perwass and Joan Lasenby demonstrate a geo- metricallyintuitivewayofusingtheincidencealgebraofprojectivegeometry in GA to describe multiple view geometry. Especially the use of reciprocal frames should be emphasized. Many relations which have been derived in matrixalgebraandGrassmann-Cayleyalgebrainthe lastyearscanbefound here again. An application with respect to 3D reconstruction using vanish- ing points is laid out in chapter 15. Another application is demonstrated in chapter16byEduardoBayro-CorrochanoandBodoRosenhahnwithrespect tothe computationoftheintrinsicparametersof acamera.Usingtheideaof the absoluteconicinthe contextofPascal’stheorem,theydevelopamethod which is comparable to the use of Kruppa equations. HongboLiandGeraldSommerpresentinchapter17analternativewayto chapter14offormulatingmultipleviewgeometry.Intheirapproachtheyuse a coordinate-free representation whereby image points are given as vectors (cid:12)xed at the optical centre of a camera. Chapters 18-21 are concerned with kinematics. In chapter 18, Eduardo Bayro-Corrochanoisdevelopingthe frameworkofscrewgeometryinthe language of motor algebra, a degenerate algebra isomorphic to that of dual quaternions. In contrast to dual quaternions, motors relate translation and rotationasspinorsand,thus,resultinsomecasesinsimplerexpressions.This is the case especially in consideringkinematic chains, as is done by Eduardo Bayro-Corrochanoand Detlev Ka(cid:127)hler in chapter 19. They are modelling the forwardandtheinversekinematicsofrobotarmsinthatframework.Theuse of dualquaternionswith respecttomotion alignmentis studied asatutorial paper by Kostas Daniilidis in chapter 20. His experience with this framework is based on a very successful application with respect to the hand-eye calibration problem in robot vision. Finally,inchapter21,YiwenZhang,GeraldSommerandEduardoBayro- CorrochanoaredesigninganextendedKalman(cid:12)lterforthetrackingoflines. Because the motion of lines is intrinsical to the motor algebra, the authors candemonstratetheperformancebasedondirectobservationsofsuchhigher order entities. The presented approach can be considered as 3D-3D pose estimation based on lines. A more extensive study of 2D-3D pose estimation based on geometric constraints can be found in [224]. In summary, this book can serve as a reference of the actual state of applying Cli(cid:11)ord algebra as a frame for geometric computing. Furthermore, it shows that the matter is alive and will hopefully grow and mature fast. X Preface Thus,thisbookisalsotobeseenasasnapshotofcurrentresearchandhence as a \workbench" for further developments in geometric computing. To complete a project like this book requires the cooperation of the contributing authors. My thanks go to all of them. In particular I would like to thank Michael Felsberg forhis substantial help with the coordination of this book project. He also prepared the (cid:12)nal layout of this book with the help of the student Thomas Ja(cid:127)ger. Many thanks to him, as well. Kiel, June 2000 Gerald Sommer Table of Contents Part I. A Uni(cid:12)ed Algebraic Approach for Classical Geometries 1. New Algebraic Tools for Classical Geometry David Hestenes, Hongbo Li, and Alyn Rockwood::::::::::::::::: 3 1.1 Introduction ........................................... 3 1.2 Geometric Algebra of a Vector Space...................... 4 1.3 Linear Transformations ................................. 13 1.4 Vectors as Geometrical Points............................ 19 1.5 Linearizing the Euclidean Group ......................... 23 2. Generalized Homogeneous Coordinates for Computational Geometry Hongbo Li, David Hestenes, and Alyn Rockwood::::::::::::::::: 27 2.1 Introduction ........................................... 27 2.2 Minkowski Space with Conformal and ProjectiveSplits...... 29 2.3 Homogeneous Model of Euclidean Space................... 33 2.4 Euclidean Spheres and Hyperspheres...................... 40 2.5 Multi-dimensional Spheres, Planes, and Simplexes .......... 41 2.6 Relation among Spheres and Hyperplanes ................. 46 2.7 Conformal Transformations.............................. 52 3. Spherical Conformal Geometry with Geometric Algebra Hongbo Li, David Hestenes, and Alyn Rockwood::::::::::::::::: 61 3.1 Introduction ........................................... 61 3.2 Homogeneous Model of Spherical Space ................... 62 3.3 Relation between Two Spheres or Hyperplanes ............. 66 3.4 Spheres and Planes of Dimension r ....................... 68 3.5 Stereographic Projection ................................ 70 3.6 Conformal Transformations.............................. 72 3.6.1 Inversions and Re(cid:13)ections ......................... 72 3.6.2 Other Typical Conformal Transformations........... 73 XII Table of Contents 4. A Universal Model for Conformal Geometries of Euclidean, Spherical and Double-Hyperbolic Spaces Hongbo Li, David Hestenes, and Alyn Rockwood::::::::::::::::: 77 4.1 Introduction ........................................... 77 4.2 The Hyperboloid Model ................................. 79 4.2.1 Generalized Points................................ 79 4.2.2 Total Spheres .................................... 83 4.3 The Homogeneous Model................................ 83 4.3.1 Generalized Points................................ 84 4.3.2 Total Spheres .................................... 85 4.3.3 Total Spheres of Dimensional r..................... 89 4.4 Stereographic Projection................................. 90 4.5 The Conformal Ball Model .............................. 92 4.6 The Hemisphere Model.................................. 93 4.7 The Half-Space Model .................................. 94 4.8 The Klein Ball Model ................................... 97 4.9 A Universal Model for Euclidean, Spherical, and Hyperbolic Spaces ................................................ 99 5. Geo-MAP Uni(cid:12)cation Ambjo(cid:127)rn Naeve and Lars Svensson::::::::::::::::::::::::::::: 105 5.1 Introduction ........................................... 105 5.2 Historical Background................................... 106 5.3 Geometric Background.................................. 108 5.3.1 A(cid:14)ne Space ..................................... 108 5.3.2 Projective Space ................................. 109 5.4 The Uni(cid:12)ed Geo-MAP Computational Framework .......... 110 5.4.1 Geo-MAP Uni(cid:12)cation............................. 110 5.4.2 A Simple Example................................ 112 5.4.3 Expressing Euclidean Operations in the Surrounding Geometric Algebra ............................... 113 5.5 Applying the Geo-MAP Technique to Geometrical Optics.... 114 5.5.1 Some Geometric-Optical Background ............... 114 5.5.2 Determining the Second Order Law of Re(cid:13)ection for Planar Light Rays................................ 115 5.5.3 Interpreting the Second Order Law of Re(cid:13)ection Geometrically.................................... 121 5.6 Summary and Conclusions............................... 122 5.6.1 The Geo-MAP Uni(cid:12)cation Technique ............... 122 5.6.2 Algebraic and Combinatorial Construction of a Geometric Algebra ............................... 123 5.7 Acknowledgements ..................................... 123 5.8 Appendix: Construction of a Geometric Algebra............ 123 Table of Contents XIII 6. Honing Geometric Algebra for Its Use in the Computer Sciences Leo Dorst::::::::::::::::::::::::::::::::::::::::::::::::::: 127 6.1 Introduction ........................................... 127 6.2 The Internal Structure of Geometric Algebra............... 128 6.3 The Contraction: An Alternative Inner Product ............ 134 6.4 The Design of Theorems and ‘Filters’ ..................... 136 6.4.1 Proving Theorems................................ 137 6.4.2 Example: Proof of a Duality ....................... 139 6.4.3 Filter Design to Speci(cid:12)cation ...................... 141 6.4.4 Example: The Design of the Meet Operation......... 141 6.5 Splitting Algebras Explicitly ............................. 143 6.6 The Rich Semantics of the Meet Operation ................ 145 6.6.1 Meeting Blades .................................. 145 6.6.2 Meets of A(cid:14)ne Subspaces ......................... 146 6.6.3 Scalar Meets Yield Distances between Subspaces ..... 148 6.6.4 The Euclidean Distance between A(cid:14)ne Subspaces .... 148 6.7 The Use and Interpretation of Geometric Algebra .......... 150 6.8 Geometrical Models of Multivectors....................... 151 6.9 Conclusions............................................ 151 Part II. Algebraic Embedding of Signal Theory and Neural Computation 7. Spatial{Color Cli(cid:11)ord Algebras for Invariant Image Recognition Ekaterina Rundblad-Labunets and Valeri Labunets::::::::::::::: 155 7.1 Introduction ........................................... 155 7.2 Groups of Transformationsand Invariants ................. 157 7.3 Pattern Recognition .................................... 157 7.4 Cli(cid:11)ord Algebras as Uni(cid:12)ed Language for Pattern Recognition160 7.4.1 Cli(cid:11)ord Algebras as Models of Geometrical and Perceptual Spaces ................................ 160 7.4.2 Cli(cid:11)ord Algebra of Motion and A(cid:14)ne Groups of Metric Spaces.................................... 164 7.4.3 Algebraic Models of Perceptual Color Spaces......... 165 7.5 Hypercomplex{Valued Moments and Invariants............. 169 7.5.1 Classical R{Valued Moments and Invariants ......... 169 7.5.2 Generalized Complex Moments and Invariants ....... 175 7.5.3 Triplet Moments and Invariants of Color Images...... 177 7.5.4 Quaternionic Moments and Invariants of 3{D Images . 180 7.5.5 Hypercomplex{Valued Invariants of n{D Images...... 183 7.6 Conclusion ............................................ 185 XIV Table of Contents 8. Non-commutative Hypercomplex Fourier Transforms of Multidimensional Signals Thomas Bu(cid:127)low, Michael Felsberg, and Gerald Sommer:::::::::::: 187 8.1 Introduction ........................................... 187 8.2 1-D Harmonic Transforms ............................... 188 8.3 2-D Harmonic Transforms ............................... 191 8.3.1 Real and Complex Harmonic Transforms ............ 191 8.3.2 The Quaternionic Fourier Transform (QFT) ......... 192 8.4 Some Properties of the QFT ............................. 194 8.4.1 The Hierarchy of Harmonic Transforms ............. 194 8.4.2 The Main QFT-Theorems ......................... 196 8.5 The Cli(cid:11)ord Fourier Transform........................... 205 8.6 Historical Remarks ..................................... 206 8.7 Conclusion ............................................ 207 9. Commutative Hypercomplex Fourier Transforms of Multidimensional Signals Michael Felsberg, Thomas Bu(cid:127)low, and Gerald Sommer:::::::::::: 209 9.1 Introduction ........................................... 209 9.2 Hypercomplex Algebras ................................. 210 9.2.1 Basic De(cid:12)nitions ................................. 210 9.2.2 The Commutative Algebra ..................... 212 2 H 9.3 The Two-Dimensional Hypercomplex Fourier Analysis ...... 213 9.3.1 TheTwo-DimensionalHypercomplexFourierTransform213 9.3.2 Main Theorems of the HFT2....................... 216 9.3.3 The A(cid:14)ne Theorem of the HFT2................... 218 9.4 The n-Dimensional Hypercomplex Fourier Analysis ......... 221 9.4.1 The Isomorphism between and the 2n 1-Fold n (cid:0) Cartesian Product of C ...H........................ 221 9.4.2 The n-Dimensional Hypercomplex Fourier Transform . 227 9.5 Conclusion ............................................ 229 10. Fast Algorithms of Hypercomplex Fourier Transforms Michael Felsberg, Thomas Bu(cid:127)low, Gerald Sommer, and Vladimir M. Chernov:::::::::::::::::::::::::::::::::::::::: 231 10.1 Introduction ........................................... 231 10.2 Discrete Quaternionic Fourier Transform and Fast Quaternionic Fourier Transform .......................... 232 10.2.1 Derivation of DQFT and FQFT.................... 232 10.2.2 Optimizations by Hermite Symmetry ............... 236 10.2.3 Complexities..................................... 240 10.3 Discrete and Fast n-Dimensional Transforms............... 242