@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Science, Faculty of"@en, "Computer Science, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Li, Ying"@en ; dcterms:issued "2008-09-05T17:23:21Z"@en, "1993"@en ; vivo:relatedDegree "Doctor of Philosophy - PhD"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """The three rotational degrees of freedom between the coordinate system of a sensed object and that of a viewer define the attitude of the object. Orientation-based representations record 3-D surface properties as a function of position on the unit sphere. All orientation-based representations considered share a desirable property: the representation of a rotated object is equal to the rotated representation of the object before rotation. This makes the orientation-based representations well-suited to the task of attitude determination. The mathematical background for orientation-based representations of shape is presented in a consistent framework. Among the orientation-based representations considered, the support function is one-to-one for convex bodies, the curvature functions are one-to-one for convex bodies up to a translation and the radial function is one-to-one for starshaped sets. Using combinations of the support function and the curvature functions for convex bodies, the problem of attitude determination is transformed into an optimization problem. Previous mathematical results on the radial function for convex objects are extended to starshaped objects and the problem of attitude determination by the radial function also is transformed into an optimization problem. Solutions to the optimization problems exist and can be effectively computed using standard numerical methods. A proof-of-concept system has been implemented and experiments conducted both on synthesized data and on real objects using surface data derived from photometric stereo. Experimental results verify the theoretical solutions. Novel contributions of the thesis include: the representation of smooth convex objects by the support function and curvature functions; the definition of a new orientation-based representation for starshaped sets using the 3-D radial function; and solutions to the 3-Dattitude determination problem using the aforementioned representations. In particular, the scope of orientation-based representations has been extended, both in theory and in practice, from convexity to starshapedness."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/1667?expand=metadata"@en ; dcterms:extent "6885109 bytes"@en ; dc:format "application/pdf"@en ; skos:note "Orientation-Based Representations of Shapeand Attitude DeterminationbyYING LIB.Sc., Peking University, 1982M.Sc., Peking University, 1985A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF COMPUTER SCIENCEWe accept this thesis as conforming to the required standardTHE UNIVERSITY OF BRITISH COLUMBIAAPRIL 1993© YING LI, 1993In presenting this thesis in partial fulfillment of the requirements for an advanced degreeat the University of British Columbia, I agree that the Library shall make it freelyavailable for reference and study. I further agree that permission for extensive copyingof this thesis for scholarly purposes may be granted by the head of my department or byhis or her representatives. It is understood that copying or publication of this thesis forfinancial gain shall not be allowed without my written permission.Signature Department of Computer ScienceThe University of British ColumbiaVancouver, CanadaDateAbstractThe three rotational degrees of freedom between the coordinate system of a sensedobject and that of a viewer define the attitude of the object. Orientation-based rep-resentations record 3-D surface properties as a function of position on the unit sphere.All orientation-based representations considered share a desirable property: the repre-sentation of a rotated object is equal to the rotated representation of the object beforerotation. This makes the orientation-based representations well-suited to the task ofattitude determination.The mathematical background for orientation-based representations of shape is pre-sented in a consistent framework. Among the orientation-based representations consid-ered, the support function is one-to-one for convex bodies, the curvature functions areone-to-one for convex bodies up to a translation and the radial function is one-to-one forstarshaped sets.Using combinations of the support function and the curvature functions for convexbodies, the problem of attitude determination is transformed into an optimization prob-lem. Previous mathematical results on the radial function for convex objects are extendedto starshaped objects and the problem of attitude determination by the radial functionalso is transformed into an optimization problem. Solutions to the optimization problemsexist and can be effectively computed using standard numerical methods.A proof-of-concept system has been implemented and experiments conducted both onsynthesized data and on real objects using surface data derived from photometric stereo.Experimental results verify the theoretical solutions.Novel contributions of the thesis include: the representation of smooth convex objectsby the support function and curvature functions; the definition of a new orientation-basedrepresentation for starshaped sets using the 3-D radial function; and solutions to the 3-Dattitude determination problem using the aforementioned representations. In particular,the scope of orientation-based representations has been extended, both in theory and inpractice, from convexity to starshapedness.iiTable of ContentsAbstract^ iiList of Tables^ viiList of Figures^ xAcknowledgment^ xv1 Introduction 12 Mathematical Background 82.1^Representations ^ 122.1.1 The Support Function ^ 142.1.2 The Normal Representation 172.1.3 The Curvature Functions ^ 202.1.4 The Distance Function 232.1.5 The Radial Function ^ 282.1.6 Cross Sectional Measure and Breadth ^ 292.1.7 The Area Function ^ 29iii2.2 Spherical Images ^ 312.3 Numbers Associated with A Set ^ 322.3.1 The Volume ^ 332.3.2 The Surface Area 342.3.3 The Diameter and the Width ^ 342.4 Transformations ^ 352.4.1 Minkowski Vector Addition ^ 352.4.2 Blaschke Addition ^ 382.4.3 Polar Means ^ 392.4.4 The Projection Body ^ 402.4.5 Polar Set, Conjugate, and Legendre Transform ^ 412.5 Mixed Measurements ^ 432.5.1 The Mixed Volumes ^ 442.5.2 The i-th Area Function 492.5.3 The Mixed Area Functions ^ 542.5.4 The Mixed Curvature Function 562.5.5 The Mixed Bodies ^ 572.5.6 The Dual Mixed Volumes ^ 582.6 Summary ^ 60iv3 Previous Research 633.1 The Extended Gaussian Image^ 643.2 Generalization of the EGI 683.3 Related Representations ^ 703.4 Summary ^ 714 Solutions to the Attitude Determination Problem 734.1 Attitude Determination by the Support Function and Curvature Functions 744.2 Attitude Determination by the Radial Function ^ 804.3 Summary ^ 875 Experiments 905.1 Experimental Shapes ^ 915.2 Software Issues 955.2.1^Optimization ^ 965.2.2^Integration and Differentiation ^ 975.2.3^Sphere Tessellation ^ 975.2.4^Interpolation 995.3 Experiments on Synthesized Data ^ 1005.3.1^Experimental Settings 1025.3.2^Experimental Results ^ 1075.3.3 Variational Test ^ 1205.4 Experiments on Real Data 1305.4.1 Experimental Settings ^ 1305.4.2 Experimental Results 1355.5 Summary ^ 1426 Conclusions^ 1446.1 Contributions ^ 1446.2 Future Directions 147Bibliography^ 149Appendices^ 155A Symbols Used in the Thesis^ 155B Glossary^ 156C Spherical Harmonics^ 159viList of Tables2.1 Properties of orientation-based representations. ^623.1 Use of orientation-based representations. ^725.1 Root-mean square gradient estimation errors. ^ 1005.2 Interpolation error for the 20-frequency geodesic dome. ^ 1015.3 Interpolation error for the 40-frequency geodesic dome. ^ 1015.4 The objective functions for group-1, group-2 and group-3 experiments. ^ 1035.5 The objective functions for set-1 experiments. ^ 1045.6 The objective functions for set-2 experiments. 1055.7 The objective functions for set-3 experiments. ^ 1065.8 Results of set-1 experiments: the number of initial guesses out of the 4096initial guesses converging to the optimal point^ 1105.9 Results of set-2 experiments: the number of initial guesses out of the 4096initial guesses converging to the optimal point^ 1115.10 Results of set-3 experiments: the number of initial guesses out of the 4096initial guesses converging to the optimal point^ 112vii5.11 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-1/group-0 experiments. ^ 1135.12 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-1/group-1 experiments. ^ 1135.13 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-1/group-2 experiments. ^ 1145.14 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-3/group-0 experiments. ^ 1145.15 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-3/group-1 experiments. ^ 1155.16 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by set-3/group-2 experiments. ^ 1155.17 Results of testing different sampling rates and hemisphere sampling: thenumber of initial guesses out of the 4096 initial guesses converging to theoptimal point 1225.18 Different choices of origin used in the experiments.^ 1225.19 Results of testing the different choice of origin: the number of initialguesses out of the 4096 initial guesses converging to the optimal point. . 1235.20 The comparisons between R o and the estimated rotations from initial guess(0.1, 0.2, 0.9) by experiments using variational testing data^ 1235.21 The comparison between the estimated a priori rotation for the ellipsoidand the rotations found by optimizations on real data. ^ 136viii5.22 The comparison between the estimated a priori rotation for the pillow andthe rotations found by optimizations on real data^ 137C.1 The Legendre polynomials of degrees up to 10^ 160ixList of Figures1.1 Mappings between surface points and points on the sphere, illustrated in2-D. ^ 32.1 Interdependence of the subsections in Chapter 2 ^ 92.2 The support function of a convex polygon. 112.3 Two polygons with the same support function. 162.4 The distance function of a starshaped set. ^ 242.5 Conjugate functions. ^ 423.1 An open surface patch with positive Gaussian curvature. ^ 694.1 Using the data on a hemisphere in optimization when the object is viewedfrom a single viewpoint. ^ 784.2 Two 2-D convex objects that do match when viewed in the positive z di-rection but that do not match over the whole unit circle. ^ 814.3 A 2-D starshaped set and its radial function, defined for points, (u, v), onthe unit circle. ^ 824.4 Two 2-D sets with the same radial function. ^ 83x4.5 Two 2-D starshaped sets that match when viewed in the positive z direc-tion but that do not match over the whole unit circle^ 875.1 Experimental shape: the ellipsoid^ 935.2 The spherical coordinate system. 945.3 Experimental shape: the peanut. It is a solid of revolution^ 955.4 Experimental shape: the pillow^ 955.5 An 8-frequency geodesic dome. 985.6 Experimental shapes and their rotated images under rotation (7r/6,7r/9,7r/4),projected onto a plane with normal direction (1,1,1)^ 1085.7 Example of the results of set-1 experiments: Minimizing cp(R) for E3,5,9with initial guess (0.1,1.4,1.3) under Boundl. ^ 1165.8 Example of the results of set-1 experiments: Minimizing (R) for E3,5,9with initial guess (0.1,1.4,1.3) under Boundl. ^ 1165.9 Example of the results of set-1 experiments: Maximizing x(R) for thepeanut with initial guess (0.1,1.4,1.3) under Boundl^ 1175.10 Example of the results of set-1 experiments: Maximizing x(R) for thepillow with initial guess (0.1,1.4,1.3) under Boundl. ^ 1175.11 Example of the results of set-3 experiments: Minimizing co(R) for E3,5 ,9with initial guess (0.1, 4.2, 1.7) under Bound3. ^ 1185.12 Example of the results of set-3 experiments: Minimizing (R) for E3,5,9with initial guess (0.1,4.2,1.7) under Bound3. ^ 118xi5.13 Example of the results of set-3 experiments: Maximizing x(R) for thepeanut with initial guess (0.1, 4.2, 1.7) under Bound3^ 1195.14 Example of the results of set-3 experiments: Maximizing x(R) for thepillow with initial guess (0.1, 4.2, 1.7) under Bound3. ^ 1195.15 Example of the results of variational tests: Minimizing cp(R) for E3,5,9 withinitial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates. 1245.16 Example of the results of variational tests: Minimizing 0(R) for E3,5 , 9 withinitial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates. 1245.17 Example of the results of variational tests: Maximizing x(R) for the peanutwith initial guess (0.1, 4.2, 1.7) using data sampled at different samplingrates 1255.18 Example of the results of variational tests: Maximizing x(R) for the pillowwith initial guess (0.1, 4.2, 1.7) using data sampled at different samplingrates 1255.19 Example of the results of variational tests: Minimizing (p(R) for E3,5,9 withinitial guess (0.1, 4.2, 1.7) using data sampled on half sphere^ 1265.20 Example of the results of variational tests: Minimizing 7b(R) for E3 , 5 , 9 withinitial guess (0.1, 4.2, 1.7) using data sampled on half sphere^ 1265.21 Example of the results of variational tests: Maximizing x(R) for the peanutwith initial guess (0.1, 4.2, 1.7) using data sampled on half sphere. . . . . 1275.22 Example of the results of variational tests: Maximizing x(R) for the pillowwith initial guess (0.1, 4.2, 1.7) using data sampled on half sphere. . . . . 127x i i5.23 Example of the results of variational tests: Maximizing X (R) for the peanutwith initial guess (0.1, 4.2, 1.7) using data sampled with new origin T1 . •^1285.24 Example of the results of variational tests: Maximizing X (R) for the peanutwith initial guess (0.1, 4.2, 1.7) using data sampled with new origin T2 • • • 1285.25 Example of the results of variational tests: Maximizing X (R) for the pillowwith initial guess (0.1, 4.2, 1.7) using data sampled with new origin Ti• • • 1295.26 Example of the results of variational tests: Maximizing X (R) for the pillowwith initial guess (0.1, 4.2, 1.7) using data sampled with new origin T2 . . . 1295.27 Example of the results of variational tests: Maximizing X (R) for the pillowwith initial guess (0.1, 4.2, 1.7) using data sampled with new origin T3 . .^1295.28 Images of the ellipsoid under three light sources^ 1315.29 Images of the peanut under three light sources. 1325.30 Images of the pillow under three light sources. ^ 1335.31 Example of the results of real data experiments: Minimizing Co (R) for theellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1)^ 1385.32 Example of the results of real data experiments: Minimizing TP(R) for theellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1)^ 1395.33 Example of the results of real data experiments: Maximizing X(R) for thepeanut imaged in Figure 5.29 with initial guess (0.1, 0.2, 0.1)^ 1405.34 Example of the results of real data experiments: Maximizing T(R) for thepillow imaged in Figure 5.30 with initial guess (0.1, 0.2, 0.1). ^ 141C.1 Projections of I Um,n(0, 6 ) 1 and I Vm,n(0, 0) 1, 0 < n < n2, m = 0,1,2,3,unto a plane that is perpendicular to (1,1,1). ^ 162xivAcknowledgmentI sincerely thank my supervisor Dr. Robert Woodham. I am very grateful for thesupervision Dr. Woodham gave me over the whole period of my PhD program includingtaking courses, writing the thesis proposal, solving the proposed problem theoretically,doing experiments and proofreading this dissertation. I thank him for being a exemplaryresearcher and a considerate mentor. I also thank him for the constant encouragement Ireceive from him.I am grateful to the members of my supervisory committee, Dr. Andrew Adler, Dr. UriAscher, Dr. David Kirkpatrick and Dr. Jim Little for their supervision and contributionsin discussions of my research.Many people helped to make this work possible. Richard Froese introduced theLegendre transformation to me. Felix Jaggi, Norman Goldstein and Herbert Kreyszighelped me to understand the paper by R. Schneider in German. Dr. Marilyn Breenprovided papers on starshaped sets. Tom Nicol suggested using the optimization routineNLPQL and also helped to convert it for local use. Dr. Robert Renka provided thespherical interpolation routine and converted it to double precision for our use. IanCavers provided the integration routine QB01AD from Harwell. Rod Barman assistedin the preparation and mounting of the test objects. Stewart Kingdon provided essentialsoftware for image acquisition. Christopher Healey helped in formatting this thesis inLatex. I also thank Branislav Klco of Studio Apropos!, Vancouver, BC, for machiningthe test objects.I thank the following faculty and staff members at the Laboratory of ComputationalIntelligence: Rod Barman, Stewart Kingdon, Jim Little, David Lowe, Alan Mackworth,Valerie McRae, David Poole, Dan Razzell, Richard Rosenberg and Bob Woodham. TheLab has been a productive and comfortable working environment.I thank the staff members at the Department of Computer Science, particularly, GaleArndt, Carlin Chao, Moyra Ditchfield, Evelyn Fong, George Phillips, Peter Phillips,Deborah Wilson, Carol Whitehead and Grace Wolkosky for their great help with variousaspects of my being a graduate student in the department.I thank Jadranka Alilovic-Curgus, Carl Alphonce, Heinz Breu, John Buchanan, At-jeng Gunawan, Alex Kean, Yggy King, Geng Lin, Dan McReynolds, Jane Mulligan, ArtPope, Pierre Poulin, Runping Qi, Lianwen Zhang and Ying Zhang for their fellowshipwith me. Particularly, I thank Pierre Poulin for proofreading this dissertation.I thank Tracy Urban, Grace Wolkosky, Valerie McRae, Carly Wong, and Ellen Hofor being my dear friends in these years. I thank Carly Wong for helping formatting andproofreading this dissertation.I thank my husband, Chong-Jian Zhu, for loving me and respecting my academicpursuit.This thesis is affectionately dedicated to my mother Wu Zhi-Yong and my father LiZhi-Chun whose love I can never repay.xvChapter 1IntroductionTasks that a robot vision system performs include recognition, localization and inspec-tion. These tasks are carried out based on data about objects collected by a robotvision system through various sensing devices. Recognition identifies the object. Local-ization determines the three translational and the three rotational degrees of freedomof a sensed object in space. Inspection verifies the suitability of the object for a par-ticular task. Attitude determination solves for the three rotational degrees of freedombetween the coordinate system of a sensed object and that of a viewer. Thus, attitudedetermination is a sub-problem of localization.If the shape of an object is invariant with respect to a class of rotations then eachrotation in the equivalence class thus determined is considered to define the same attitude.A 3-D object may have additional rotational invariances when viewed from a particularviewpoint. In this case, it is understood that attitude determination solves for the threerotational degrees of freedom up to an equivalence class of rotations that can not befurther distinguished given the viewpoint provided.Attitude determination is required for many robot vision tasks including directing arobot arm to grasp an object, navigation and camera calibration. Suppose a robot isplaced, in a factory, beside a bin of machine parts all of the same type. The robot isinstructed to grasp a machine part in a specified way. Each part has a 3-D shape thatis known to the robot, i.e., the robot has a model of the part in a standard coordinate1Chapter I. Introduction^ 2system. The parts the robot sees in the bin are instances of the model subject to unknownrotation, scaling and translation. The attitude determination problem for the robot is todetermine the unknown rotation so that the robot can be directed to grasp a machinepart in the specified way.Shape representations are required to support object recognition, localization andinspection. An object is a connected compact set in R3 . The shape of an object concernsthe geometry of the surface of the object modulo translation, scaling and rotation. Arepresentation of shape is a language for encoding a general class of shapes [75], togetherwith rules that specify how it is applied to any particular shape [53].Orientation-based representations of shape are shape representations with particu-lar properties. The term \"orientation-based representation\" was introduced by Wood-ham [76]. An orientation-based representation records 3-D surface properties as a func-tion of position on the unit sphere. These representations are termed orientation-basedbecause one associates each point on the sphere with the unit vector from the center ofthe sphere to that point.This dissertation studies various orientation-based representations and solves the at-titude determination problem by making use of the dependence of the orientation-basedrepresentations of shape on rotations.In order for an orientation-based representation to effectively represent the shape ofan object, a correspondence between the surface point of an object and a point on theunit sphere is required. Two ways to establish such a correspondence are employed in thisdissertation. They are called Gauss map and dilation map and are shown in Figure l.laand Figure 1.1b respectively.The Gauss map takes each surface point to the point on the sphere corresponding tothe unit normal to the tangent plane at that point. Figure l.la illustrates the Gauss map.Chapter 1. Introduction^ 3(a) Gauss map^(b) dilation mapFigure 1.1: Mappings between surface points and points on the sphere, illustrated in 2-D.Many representations based on the Gauss map have been defined. Representations ofthis type used in computer vision include: the Extended Gaussian Image (EGI), definedas the reciprocal of the Gaussian curvature [35], and the support function, defined asthe distance from the origin to the tangent plane [57]. For polyhedra, the EGI specifiesthe area of each face as a function of face orientation. The EGI has been used for bothrecognition and attitude determination of convex polyhedra [12, 37, 47]. The supportfunction appears explicitly in one of the methods described [47].Other representations of 3-D shape based on the Gauss map have been defined. Forexample, the first and second curvature functions are defined, respectively, as the sum ofthe principal radii of curvature and the product of the principal radii of curvature. Thus,for smooth objects, the EGI and the second curvature function are equivalent. Thesecurvature functions possess desirable mathematical properties when combined with thesupport function. The first and second area functions also are defined (see Section 2.5.2).For polyhedra, the EGI is equivalent to the second area function.The Gauss map is one-to-one for smooth (i.e., C 2 ), strictly convex objects. It hasproven difficult to extend representations based on the Gauss map beyond the convexChapter 1. Introduction^ 4case since, in general, the Gauss map is many-to-one. Approaches have been described todecompose non-convex surfaces into regions for which the Gauss map is one-to-one andto augment the information recorded to handle the many-to-one nature of the mapping[40, 46].One can go beyond convexity by choosing a different way to establish the correspon-dence between surface point and point on the sphere. Let the origin be in the interior ofthe object. Without loss of generality, assume that the size of the object is large enoughso that the unit sphere fits entirely within the object. A surface point p is mapped thepoint on the sphere that is the intersection of the sphere with the ray from the origin to p.Call this map the dilation map. Figure 1.1b illustrates the dilation map. Unfortunately,in general, the dilation map is not one-to-one either. However, for a suitable choice oforigin, it is one-to-one when the object is a starshaped set [10, 72].Representations of 3-D shape based on the dilation map can also be defined. Theradial function records the distance from the origin to the boundary point. The distancefunction is the reciprocal of the radial function.The two aforementioned mappings between the surface point and point on the sphereboth lead to a desirable property that all the orientation-based representations consideredshare: the representation of a rotated object is equal to the rotated representation of theobject before rotation. This facilitates the construction of the representation of a rotatedobject from that of the original object. This property also makes orientation-based repre-sentations suitable for attitude determination. Using inequalities involving two objects,one for the model and the other for the sensed surface data, one can define functionsof rotation that achieve extrema when the rotation is such that the rotated model andthe sensed object differ only by scaling and translation. Thus, attitude determination istransformed into the problem of determining the extremum of a known function. This,in turn, can be expressed as an optimization problem for which standard solutions exist.Chapter 1. Introduction^ 5Chapter 2 establishes a consistent framework for orientation-based representationsof shape. A mathematical definition of orientation-based representation and the math-ematical background for orientation-based representations are provided. Definitions ofvarious orientation-based representations are given and their properties are studied. Theemphasis of the study is on:1. The conditions under which the representation is one-to-one;2. The conditions under which a given function is a valid instantiation of an orientation-based representation;3. The conditions under which an object can be reconstructed from its representation.Results concerning these aspects are summarized in Table 2.1 (page 62). The representa-tions introduced in Chapter 2 have been studied in the mathematics literature. However,the source material is diverse both in time and in language. The coherent presentationin Chapter 2 of the mathematical background for orientation-based representations isa contribution of this dissertation. In addition to being the theoretical foundation ofthis dissertation, these results are relevant to research in other areas. For example, theMinkowski sum (Section 2.4.1) is used both in geometric object modeling [17] and inrobotics [48]. On first reading of the thesis Chapter 2 might well be skipped. Resultsare presented in general d-dimensional space Rd to preserve the original generality ofthe mathematics and to connect the special case d = 3 to the generic meaning of therepresentations.As mentioned, a few orientation-based representations have already been proposedand utilized in computational vision. Overall, however, little of the material presented inChapter 2 has been utilized. Objects represented typically are limited to polytopes andto some special non-convex objects [35]. The state of the art is presented in Chapter 3and highlighted in Table 3.1 (page 72).Chapter 1. Introduction^ 6Chapter 4 provides theoretical solutions to the problem of attitude determinationusing orientation-based representations. The results in Chapter 2 on inequalities involv-ing orientation-based representations are utilized. By combining the representation ofa model and that of an object in the inequalities, the attitude determination problemis transformed into optimization problems for which standard numerical methods canbe applied. Indeed, optimization itself is not an intended contribution of the thesisresearch. Instead, existing optimization tools are employed throughout. The orientation-based representations used are the first curvature function, the second curvature function,the support function and the radial function. The use of the first curvature function isnew. The use of the support function on smooth, strictly convex objects also is new.The curvature functions are directly related to the area functions which are well definedfor any convex object. Thus, the use of the curvature functions can be regarded as anapplication of a theory of general convex objects to a specific type of convex objects(smooth, strictly convex objects) rather than as a simple substitute for Gaussian andmean curvatures. Since the support function is one-to-one only for convex bodies andthe curvature functions are only defined for convex bodies, attitude determination usingthem is, in general, not necessarily valid for non-convex bodies. A major contribution ofthis dissertation is to demonstrate that the radial function is an effective representationfor starshaped objects l and that the attitude of starshaped objects can be determinedusing the radial function. Thus the class of objects handled is extended to starshapedobjects (which strictly includes convex objects as a special case).A proof-of-concept system has been implemented and experiments conducted to testnumerical solutions for three cases:1. Attitude determination when both the model and sensed surface are given in knownanalytic form;1 See Appendix B for definition of starshaped objects.Chapter I. Introduction^ 72. Attitude determination when the sensed surface, then the model and then both arediscretized versions of a known analytic form;3. Attitude determination with sensed data obtained, via photometric stereo, fromreal objects and model data given in known analytic form.Cases 1 and 2 represent simulation studies that were essential to software development,error analysis and tests of robustness. Case 3 tests the performance of the system onreal objects machined from data derived from analytic forms. Experimental results showthat attitude determination can be solved by the aforementioned orientation-based rep-resentations of shape. The system and the experiments are described in Chapter 5.Chapter 6 summarizes the contributions of this dissertation and points out futuredirections for research.Appendix A and Appendix B describe notational conventions and basic definitionsused. Appendix C provides a brief introduction to spherical harmonics which are usedin Chapter 5 to define the experimental shapes.Chapter 2Mathematical BackgroundOrientation-based representations are functions defined on the unit sphere or set functionsdefined on sets of the unit sphere. The representations considered in this dissertation arebased on the two mappings from an object to the unit sphere described in Figure 1.1 ofChapter 1. Some representations can be defined using the mappings and basic calculus.To build a theory of orientation-based representations and to solve the attitude deter-mination problem, deeper mathematical background is needed. The orientation-basedrepresentations considered in this dissertation are described in the mathematics litera-ture. However, the source material is diverse both in time and in language. This chaptergives a coherent presentation of the mathematical background for orientation-based rep-resentations. Results are presented in general d-dimensional space Rd to preserve theoriginal generality of the mathematics and to connect the special case d = 3 to thegeneric meaning of the representations.There are six sections in this chapter. The first five sections present definitions,properties and relationships among, respectively, five types of mathematical objects thatestablish the background for orientation-based representations of shape. Each of thesesections is further divided into subsections where one mathematical object of the type ofthe section is presented. Figure 2.1 depicts the interdependence between the subsectionsof this chapter, where subsections directly related to attitude determination in this dis-sertation are emphasized. The last section of this chapter, Section 2.6, summarizes the8Chapter 2. Mathematical Background^92.1.2normalrepresentation2.1.4distancefunction2.1.5radialfunction2.1.6brightnessand breadth2.1.1supportfunction2.1.3curvaturefunctions-rV 2.3.1volume2.1.7area functionIM =MI =IN2 3.2surface area2.2sphericalimage 2.4 3polar means2.4.4projection bodyV 2.4.2Blaschkeaddition2.4.1Minkowskiaddition2.4.5Legendretransform2 5.1mixed volumeCorollary 2.38Corollary 2.432.5.2i-th areafunction2.5.4mixed curvaturefunction2.5 3mixed areafunction2.5.5mixed bodiesLegend:2.5.6dual mixedvolumeheorem 2.54A is used in attitudedeterminationAI A^B B depends on A- B B is related to AFigure 2.1: Interdependence of the subsections in Chapter 2.Chapter 2. Mathematical Background^ 10properties of the orientation-based representations of shape.To further describe the first five sections, let Rd denote the d-dimensional real space,Sd-1 denote the unit sphere in Rd, Bd denote the unit ball in Rd and B(Sd-1 ) the o--algebra of Borel subsets of Sd -1 . The five types of mathematical objects consideredare:1. Functions that are associated with one set and whose domains are Rd ,Sd-1 or B(Sd-1 ) (Section 2.1).Functions in this category are the support function, the normal representation, thecurvature functions, the distance function, the radial function, the cross sectionalmeasure and the breadth and the area functions. These functions define orientation-based representations of shape. Among them, the support function (Section 2.1.1),the curvature functions (Section 2.1.3) and the radial function (Section 2.1.5) arethe orientation-based representations used in attitude determination (Chapter 4and Chapter 5) in this dissertation. All the functions are defined on Sd -1 exceptthe area function which is defined on /3(S d-1 ). The introduction of the a-algebraof Borel subsets of Sd-1 , B(Sd-1 ), provides a way of stating the properties of thearea function since the area function is a set function.To give an example of orientation-based representations, consider the support func-tion of a 2-D polygon, P. For a point u on the unit circle, the value of the supportfunction of P at u is the maximal signed distance between the origin and thesupport plane of P with outer normal u. Figure 2.2 shows the 2-D example of aconvex polygon and its support function defined for vectors u E 5 1 . The value ofthe support function is the distance between the origin and the dashed arc alongthe direction determined by u.2. Mappings from one hypersurface to sets on S d-1 (Section 2.2).Chapter 2. Mathematical Background^ 11Figure 2.2: The support function of a convex polygon.The spherical image is in this category. Although it is not an orientation-basedrepresentation, it is included because of its close relation to Gauss map.3. Mappings from one or more sets to scalar values (Section 2.3).Scalar values are volume, surface area, diameter and width. These numbers can becalculated from the orientation-based representations introduced in Section 2.1.4. Mappings from one or more sets to a new set (Section 2.4).These mappings are called transformations. The transformations are achievedby constructing the representation of a new set from the orientation-based rep-resentations of some given sets. The constructions make use of the properties oforientation-based representations defined in Section 2.1. Typically, the propertiesof the transformed set are of more interest than the transformation itself. Trans-formed sets are the (Minkowski) vector sum, the Blaschke sum, the polar mean,the polar reciprocal set, the Legendre transform, the projection body, the parallelbody and the central body.5. Functions and mappings obtained via combinations of a set with the unitball Bd or combinations of several sets (Section 2.5).Chapter 2. Mathematical Background^ 12Their names are usually prefixed with \"i-th\" or \"mixed\" depending on whetherthe unit ball is involved in the combination. They are called mixed measurements.The mixed measurements included are the mixed volume, the i-th area function, themixed area function, the i-th curvature function, the mixed curvature function, themixed body and the dual mixed volume. Among them, the i-th curvature functionand the mixed curvature function are orientation-based representations, the mixedvolume and the dual mixed volume are scalar values, the i-th area function andthe mixed area function are set functions, and the mixed body is a set. Thetheorems concerning the mixed volumes (Section 2.5.1) and the dual mixed volumes(Section 2.5.6) are directly used in the solutions to the attitude determinationproblem (Chapter 4).The mathematical constructions have been studied intensively in the context of convexbodies. Some of them are only meaningful when applied on convex bodies. Possibilitiesto extend functions and mappings to non-convex sets are discussed. References to themathematical results are provided but the original proofs are not repeated. Generalreferences are Bonnesen and Fenchel [7], Busemann [15], Griinbaum [32], Pogorelov [60]and Schneider [69]. Notation, definitions and facts used but not defined in this chapterare given in Appendix A and Appendix B.2.1 RepresentationsDefinition 2.1 An orientation-based representation of shape is a map from connectedcompact sets in Rd to functions defined on the unit sphere Sd-1 in Rd or set functionsdefined on B(Sd -1 ).An example of an orientation-based representation of shape is the support function.The support function is defined for any set in Rd . Its value at point u on the unitChapter 2. Mathematical Background^ 13sphere is the maximal signed distance (from an origin) to the tangent plane with outernormal u. This mapping from objects to functions defined on the unit sphere conformsto Definition 2.1 and thus is an orientation-based representation of shape. The name ofthe mapped function, the support function, also is used to name the representation.An orientation-based representation represents the shape of an object via a correspon-dence between points on the unit sphere and points on the object surface. Two ways ofestablishing such a correspondence, the Gauss map and the dilation map, are depictedin Figure 1.1. The Gauss map takes each surface point to the point on the sphere corre-sponding to the unit normal to the tangent plane at that point. The dilation map takes asurface point p to the point on the unit sphere that is the intersection of the sphere withthe ray from the origin to p. Representations based on the Gauss map come with usefulmathematical properties. However, many of these properties require the correspondenceto be one-to-one. This restricts the representation to strictly convex objects since theone-to-one correspondence then is guaranteed, as by the following theorem:Theorem 2.1 (Bonnesen-Fenchel [7] page 15.) If a convex body has only regular bound-ary points, then its boundary can be mapped one-to-one and continuously onto Sd -1 bymeans of equally directed support planes.By the definition of starshaped set, correspondence via the dilation map is one-to-onefor starshaped objects when the origin is inside the kernel of the object. The class ofstarshaped objects strictly includes the class of convex bodies. The mathematical studyof starshaped objects is not as extensive as that of convex bodies.Representations studied in the following subsections are the support function, thenormal representation, the curvature functions, the distance function, the radial function,the cross sectional measure, the breadth and the area functions. Definitions are givenand the relations between the representations are described once sufficient background isChapter 2. Mathematical Background^ 14established. For each representation, the following aspects are of main concern:1. Conditions under which a representation is one-to-one;2. Necessary conditions for a function to be the representation of an object;3. Sufficient conditions for a function to be the representation of an object;4. Methods by which an object can be reconstructed from its representation.2.1.1 The Support FunctionDefinition 2.2 (Lay [42] 29.1 page 206.) Let C C Rd be a nonempty set. The supportfunction H(C; v) of C is the real-valued function defined byH (C; v) = sup {(x, v) 1 x E Cl ,for all v E Rd for which the supremum is finite.It is obvious that the support function of a set depends on the choice of the origin ofthe coordinate system. If a set C is translated into C' by a vector a, the support functionof C' isH (C' ; v) = H (C ; v) + (a, v) .^ (2.1)If C is rotated by a rotation R, its support function is rotated by the same rotation, i.e.,H(R(C);v) = H (C ; R- 1 (v)) .^ (2.2)If C is a convex body, the support hyperplane of C with outer normal v E Rd \\ {O}is (x, v) = H(C; v). If v E Sd-1 , the value H (C ; v) is the signed distance from the originto the support plane of C with outer normal v. If C is non-convex, then (x, v) = H(C; v)Chapter 2. Mathematical Background^ 15is the support plane of C with outer normal v that is of maximum signed distance fromthe origin.Examples of support functions are:1. The support function of a point is a linear function. The support function of apolytope is a piecewise linear function.2. The support function of the unit ball with center at the origin is^II.3. The support function of the d-dimensional cube that has edges parallel to the axeswith edge length two and centered at the origin is Eci_ i ivz I.Theorem 2.2 (Bonnesen-Fenchel [7] page 26.) The support function H(C; v) of anonempty set C is positively homogeneous and convex. That is, it satisfies1. H(C; Av) .H(C; v)^for all A > 0, v E Rd ,2. H (C ; v w) H (C ;^H (C ;^for all v, w E Rd .Positive homogeneity and convexity are also sufficient for a function to be the supportfunction of a convex set.Theorem 2.3 (Bonnesen-Fenchel [7] page 29.) If H(v) is any function defined on Rdsuch that1. H(Av) AH(v)^for all A > 0, v E Rd ,2. H(v w) < H(v) H(w)^for all v, w E Rd ,then there exists a nonempty closed convex set C such that H(v) is the support functionH(C; v) of C.Chapter 2. Mathematical Background^ 16Figure 2.3: Two polygons with the same support function.Support functions are defined for any nonempty set. However, only for convex sets isthe support function one-to-one.Theorem 2.4 (Grfinbaum [32] page 14.) If C1 , C2 are nonempty closed convex sets inRd such that H(Ci ; v) = H(C2 ; v) for every v E Rd , then C1 = C2.In general, the support function is not one-to-one for non-convex bodies. For example,in Figure 2.3, the two polygons have the same support function. The left one is convexwhile the right one is not. The support functions are the same because the convex hullsof the two polygons are the same.Theorem 2.5 (Lay [42] page 209.) Let C be a nonempty closed convex set and H(C ; v)its support function with a nonempty domain D. Then C can be characterized by theconditionC = {x I (x,v) 5_ H(C;v) for all v E D} ,or, equivalentlyC^n Ix I (x,v ) 5 H(C; v)} .veDChapter 2. Mathematical Background^ 17Theorem 2.6 (Bonnesen-Fenchel [7] page 27.) Let C 1 and C2 be two convex bodies.Then H(Ci; v) < H(C2; v) holds for all v E Rd if and only if C1 C C2 .The next theorem gives the coordinates of the boundary points of a convex body viathe support function of the convex body.Theorem 2.7 (Bonnesen-Fenchel [7] page 29.) If a convex body C has only regularsupport planes, then its support function H(C; v) has continuous partial derivatives ofthe first order, andOH(C; u)x, —^u E Sd-1 , i = 1,^,d,au,holds for the coordinates x i of its boundary points whose outer normal is u.2.1.2 The Normal RepresentationDefinition 2.3 (Firey [21] page 1.) Let C be a convex body having only regular supporthyperplanes, u E Sd-1 , and let x(C; u) be the point on the boundary of C at which theunit outer normal is u. Function x is called the normal representation of the boundaryof C.Because of the one-to-one correspondence between the sphere and the surface of aregular convex body via directions of support planes, as stated in Theorem 2.1, thenormal representation of a convex body rotates with the convex body, i.e.,^x(R(C); u) = x(C; R - 1 (u)) .^ (2.3)The normal representation x(C; u) can be extended to be defined on Rd\\ {0} byx(C; v) = x(C; v /11 v (I), v E Rd\\{O}. The necessary and sufficient conditions for a con-tinuously differentiable function to be the normal representation of the boundary of aconvex body is given by Firey [21].Chapter 2. Mathematical Background^ 18Theorem 2.8 (Firey [21j page 3.) In order that x(v), assumed to be continuouslydifferentiable, be the normal representation of the boundary of a non-degenerate convexbody with regular support planes, it is necessary and sufficient that, when extended tobe defined over Rd\\{0}, its Jacobi matrixaxi(v) (Xij) ,^= avj , i,j = 1, 2, ... , d,does not vanish identically and is symmetric and non-negative definite on S\".Let C be a convex body with regular support planes, thenH(C; v) = (v, x(C; v)) ,^ (2.4)and by Theorem 2.7aH (C ; v)xi(C; = ^ (2.5)If x(C; v) is continuously differentiable, then H(C; v) is twice continuously differentiable,anda2H(c ; v)ax i(c ; v)^axi (c ; v)aviavi^avi^aviThus the Hessian matrix of the support function H(C; v)(a2 H(C; v))aviavi )is the Jacobi matrix of the normal representation, x(C; v),(axi(C; v))) •The normal representation of a convex body helps to establish relations between theradii of principal curvature and the support function of a convex body. To show this,introduce parameters cr i , a 2, , ced_ i on the unit sphere S\" such that the coordinates ofChapter 2. Mathematical Background^ 19the points u of the unit sphere are analytic functions u(cr i ,^, ad_ i ), and the parametersare such indexed that^ u^ Idet^au au^> 0 .act i (9a2^aad-iLet C be a convex body with regular support planes. Then x(C; v) can be obtained as afunction x(a i ,^, ad_ i ) of the parameters. If the origin is assumed to be in int C, thendet [x^ax > .aal 0a2 • aad_iDifferentiating (2.5) givesax •^aV •^ a2 HE , where H,3 — ^aai^j=i^a (/ VI CI V.7 .If dx and v are parallel to the directions of principal curvature and r is the associatedradius of principal curvature, then dx = rdv. Thus,dE rdvi, i = 1,2, ... ,d .Therefore the radii of principal curvature must satisfy the equationH11 — r • •^Hid. 0 ,^ (2.6)Hdl^' • Hdd — rwhich can be expanded into lrd Di (H)rd-1 D2(H)rd-2 .^Dd_i(H)r (_odpd(H) = 0 ,where Di(H) is the sum of all i-rowed principal minor determinants of the matrix (1/ 12 ).Since H(C; v) is homogeneous of degree 1 in v, and Hi(v) = 8118(vC;v) is homogeneous of1 By Theorem 27.1 in Browne [14] (page 68), for a n-square matrix A with elements in a field .T,A —^j= En .o^, where cm is the sum of all the rn-rowed principal minor determinantsmof A, co = 1, o-7, =I A IChapter 2. Mathematical Background^ 20degree 0 in v, then by Euler's Theorem,dEHij vi =0 , =1,2,...,d.^ (2.7)Thus the determinant Dd(H) of (Hi; ) vanishes. Then equation (2.6) results in a(d — 1)-th degree equation for the radii of principal curvature ri, .. •rd-1 — D1(H)rd-2 D2 (H)rd-3 + • • • + (- 1)d- 1 Dd_ i (H) = 0 .^(2.8)Therefore the radii of principal curvature r i (u),i^1,^, d — 1, at x(u), are the so-lutions to equation (2.8). Thus the radii of principal curvature together with zero arethe eigenvalues of the Hessian matrix of H. From (2.8), Di(H) is also the i-th elemen-tary symmetric function {n. • • • ri} of r1 , ...,rd_ i . In particular, the sum of the radii ofprincipal curvature at x(u) is the trace of the Hessian matrix of H, i.e.,AH(u) = ri (u) -+ r2 (u) -F • • • + rd_ i (u), u E Sd-1 .^(2.9)Furthermore(H) = ri (u)r2 (u)• • • rd_ i (u), u E Sd-1 (2.10)is the product of the radii of principal curvature and is therefore the reciprocal of theGaussian curvature.2.1.3 The Curvature FunctionsDefinition 2.4 (Bonnesen-Fenchel [7] page 121.) Let C be a convex body, H(C; v) beits support function. Let Di(H) be the sum of all i-rowed principal minor determinantsof the matrix (Hid), where H3 = aa:a . DefineFi(C; u) a- Di(H)^= 1, 2, ... , d — 1 ,^(2.11)as the i-th curvature function of the convex body C.Chapter 2. Mathematical Background^ 21Since the normal representation and the support function rotate with the convex body(see (2.2) and (2.3)), the curvature functions rotate with the convex body too, i.e.,Fi(R(C); u) = Fi(C;^(u)) .^ (2.12)Of particular interest are the first and the (d — 1)-th curvature functions:Fi (C; u)^(C; u) + • • • + rd_ i (C; u)Fd—i(C;U) = r i (C; u)r2 (C; u) • • • rd_ i (C; u) .When d = 3, a convex body has two curvature functions, F 1 and F2, which are the sum ofthe radii of principal curvature and the reciprocal of the Gaussian curvature, respectively.Theorem 2.9 (Bonnesen-Fenchel [7] page 121.)ifsd -1 wFi(C; ce)cice = 0 . (2.13)This theorem says that a necessary condition for a function defined on Sd -1 to be thecurvature function of a convex body is that the centroid of the surface on the unit spherecovered with mass density Fi is the center of the sphere. This also is a sufficient conditionfor a function defined on S d-1 to be the (d — 1)-th curvature function of a convex body.Theorem 2.10 (Bonnesen-Fenchel [7] pages 127-128.) Let F(u) be a positive continuousfunction on the unit sphere that satisfies the relationfsd-iwF(w)&4., = 0 .Then there exists a convex body uniquely determined up to translation for which F isthe curvature function Fd_1.Theorem 2.9 and Theorem 2.10 together give a necessary and sufficient condition fora positive continuous function Fd_ 1 on Sd-1 to be the curvature function Fd_ i (C; u) ofChapter 2. Mathematical Background^ 22a convex body C. The existence problem of a closed convex surface C such that thesum of the radii of principal curvature at a point with unit outward normal vector u is agiven function 0(u) defined on S' is called Christoffel's problem. The problem has beenstudied by quite a few mathematicians, including Christoffel himself. A recent solution tothe existence problem is the constructive proof by Firey [21], which Firey claims correctsand complements the incomplete treatment to the problem by earlier researchers.Theorem 2.11 (Firey [21] page 9.) Let 0 be a continuously differentiable function overSd-1 . There exists a non-degenerate convex body C with regular support hyperplanessuch that 0(u) is the sum of the principal radii of curvature at that boundary point ofC at which u is the outer normal if and only if 0 satisfies the following conditions. Let[1 _ ( til, u )211-(1-d) fare cos(u',u)O(u', u) = ^sins-2t dt ,cod^firthenuo(u )dw (u ) . 0 ,19d-1 (u, u ff )0(u' , u)(V 0(u), u\")dw(u)^0 ,for all u' on Sd -1 and u\" for which (u', u\") = 0 with strict inequality for some such choices.The (d — 1)-th and the first curvature function are one-to-one for convex bodies upto a translation.Theorem 2.12 (Bonnesen-Fenchel [7] page 122.) Two convex bodies with interior pointsand continuous curvature function Fd_i can be carried into one another by a translation.Theorem 2.13 (Bonnesen-Fenchel [7] page 122.) A convex body is uniquely determined,up to a translation, by its first curvature function F1.Chapter 2. Mathematical Background^ 23The definition and the theorems of this section assume that the support function of theconvex body has second derivatives. This is only necessary when the curvature functionsare defined via Di(H). The assumption can be dropped if the curvature functions aredefined by mixed volumes as will be described in Section 2.5.1.2.1.4 The Distance FunctionDefinition 2.5 (Bonnesen-Fenchel [7] page 23.) Let C be a convex body with interiorpoints. Suppose the origin 0 is chosen in the interior of C. For any x E Rd \\{O}, letG be the (unique) intersection point of the ray Ox with bd C. The distance functiong(C; x), x E Rd , of C is defined as1. g(C; 0) = 0, and2. g(C; x)^11x11/1111, x E Rd \\ {O}.The distance function of a set depends on the choice of the origin of the coordinatesystem. If a set C is rotated by a rotation R, its distance function is also rotated by thesame rotation, i.e.,g(R(C); v) = g(C; R-1 (v)) .^ (2.14)The general relation between the distance function of a set and that of its translation isunknown.Examples of distance functions are:1. The distance function of the unit ball with center at the origin is Ilx1I;2. The distance function of the cube having edges parallel to the axes with edge lengthtwo and centered at the origin is max{Ix i l I 1 < i 0, x E Rd ,3. g(C; x y) 5 g(C; x) g(C; y)^for all x, y E Rd .Theorem 2.15 (Bonnesen-Fenchel [7] page 24.) If g(x) is any function defined on Rdsuch that1. g(x)^02. g(itx) = pg(x)3. g(x y) C s(x) + g(Y)with equality if and only if x = 0,for all ,u > 0, x E Rd ,for all x, y E Rd ,then there exists a nonempty closed convex set C such that g(x) is the distance functionof C.Sometimes the distance function is called gauge. In topology d(x, y) g(C; y — x) isa gauge. It is used in Minkowski geometry ([7] page 25).It is important to note that Definition 2.5 can be applied, without any change, tocompact starshaped sets with origin in the interior of the kernel, since any ray Ox in-tersects a compact starshaped set only once. Properties 1 to 4 still hold for starshapedsets. Of particular interest is the one-to-one property. Recall that the support functionChapter 2. Mathematical Background^ 26is one-to-one only for convex sets. The distance function is one-to-one for starshapedsets. This is significant because the class of starshaped objects strictly includes that ofconvex objects.A more general definition of the distance function has been used by Valentine [72],Lay [42] and Beer [4] for starshaped sets that are not necessarily compact.Definition 2.6 (Valentine [72] page 33.) Let S be a set in a linear space r, starshapedwith respect to the origin 0. The generalized distance function of S is the functiong : £ [0, oo] defined byg(x) = inf P ti > 0 , xE).S}.^ (2.15)From this definition of the distance function, a result that is stronger than bothTheorem 2.14 and Theorem 2.15 follows.Theorem 2.16 (Valentine [72] page 32.) Suppose S C r is starshaped with respect to0 and each line through 0 intersects S in a relatively closed set. Then S is convex if andonly if the distance function g of S is subadditive and positively homogeneous, that is,1. g(S; x -F y)^g(S; x) g(S; y)^for all x,y E .C.2. g(S; Ax) = Ag(S; x)^for all . > 0, x EThe distance function, g, of the polygon shown in Figure 2.4 is not subadditive,since g((- 2, —3)) = 1.5, g((1, —2)) = 1, g(( —2, —3)) + g((1, —2)) = 2.5 < g(( —2, —3) +(1, —2)) = g((- 1, — 5)) = 4. Thus, by Theorem 2.16, the polygon is not convex.Beer [4] established a selection theorem for starshaped sets by considering the dis-tance function of starshaped sets. He believed that the distance function is intrinsicallyChapter 2. Mathematical Background^ 27related to starshaped set. It is stated in his paper that if g is the distance function ofa nontrivial closed set starshaped with respect to an origin, 0, then g is a nonnegativeextended valued positively homogeneous lower-semicontinuous function and there existsxo 0 satisfying g(x0) oo. Conversely, any function g with these properties is thedistance function of such a set, namely, S = {x : g(x) < 1}. If 0 E int ker S, then thedistance function is continuous. Moreover, it is Lipschitz (see Appendix B).Beer studied the distance function of parallel bodies of starshaped sets. One of histheorems is as follows.Theorem 2.17 (Beer [4] page 24.) Let {Sc} be a sequence of compact starshaped setseach contained in {x E Rd : ilx11 < M}. Then {Sc} has a subsequence convergent in theHausdorff metric to a compact starshaped set.In the study of classes of starshaped sets in R3 , Melzak [55] asserted that the class ofstarshaped sets is identifiable with the class of all real valued positive functions on thesphere S 2 which satisfy a Lipschitz condition. Define 7-1 as follows: S Eli if and only ifS is a bounded closed set in R3 and 0 E int ker S. Let g(S; v) be the distance function ofS. The following theorems were obtained where Theorem 2.18 was mentioned similarlyin Beer [4].Theorem 2.18 (Melzak [55] pages 175-176.) If S E 7-t then g(S; u i ) > 0 and 19(S; ui) —g(S; u 2 )1 < -yslu 1 u 2 1, 0 < -ys < oo, where u 1 , u2 E S 2 and lu i u2 1 is the length of the linesegment between u 1 and u2 . Conversely, any such function g defines a set in 7-1.Theorem 2.19 (Melzak [55] pages 175-176.) Given any convex set C E 7-t, anyA > 0 such that C C AB', and any e > 0, there exists S E 7-1 such that1. ker S = C;Chapter 2. Mathematical Background^ 282. C C int S;3. AB3 c S c (A + 6)B3 .2.1.5 The Radial FunctionThe definition of the radial function parallels Definition 2.6 of the distance function.Definition 2.7 (Lutwak [49] page 531.) The radial function of a convex body C isdefined as^p(C; u) sup{A > 0 Au E^, for u E 8d-1 .^(2.16)From 2.15 and 2.16 it can be seen thatp(C; u) = ^1g(c Thus, by (2.14),^p(R(C); u) = p(C;^(u)) .^ (2.17)For compact convex sets, the properties of the distance function that are derived fromDefinition 2.5 can be transformed into properties of the radial function:1. The points that satisfy the inequality p(C; x) > 1 are precisely the points of C;2. If two convex sets with 0 as their common interior point have the same radialfunction, the two must be the same;3. If the radial function of C is p(C; x), that of AC is Ap(C; x), A > 0;4. For convex sets C1 and C2 ) p(c x) < p(c2; x),v x E Rd if and only if C1 C C2-Chapter 2. Mathematical Background^ 292.1.6 Cross Sectional Measure and BreadthDefinition 2.8 (Bonnesen-Fenchel [7] page 49.) Let C be a convex body and v anarbitrary direction. The (d — 1)-dimensional volume of the orthogonal projection ofC onto a hyperplane with normal direction v is called the (d — 1)-dimensional crosssectional measure of C in the direction v, denoted as o(C; v). For d = 3, o-(C; v) is calledthe brightness function of C, i.e., the area of the orthogonal projection of C onto a planewith normal direction v. (Firey [20] page 96.)Theorem 2.20 (Firey [20] page 96.) If two centrally symmetric convex bodies have thesame brightness function, then they differ at most by a translation.Definition 2.9 (Bonnesen-Fenchel [7] page 56.) Let C be a convex body and v anarbitrary direction. The distance between the two support planes of a convex body Cwith normal direction v is called the breadth of C in the direction v, and is denoted asB(C; v), for all directions v. A convex body is called a body of constant breadth if it hasthe same breadth in all directions.For any convex body C, B(C;v) ,--- H(C;v)-I- H(C; —v).It follows that spheres are the only central bodies of constant brightness.2.1.7 The Area FunctionDefinition 2.10 (Firey [24] page 205.) Let C be a convex body in Rd, S2 E B(Sd- 1 ).Denote, by S(C; 9), the (d-1)-content (area when d = 3) of the set of all those boundarypoints of C, each of which has a support hyperplane with outward normal in a Setfunction S(C; C2) is called the area function (or primary area function by Firey) of C.Chapter 2. Mathematical Background^ 30Theorem 2.21 (Schneider [69] page 47.) For convex body C,wdS(C; w) = 0 .isd-1Theorem 2.22 (Schneider [69] page 47.) Let /./ be a positive measure on B(Sd-1 ) notconcentrated on a great circle, and suppose thatwel kw) = 0 .isd-1Then there exists a convex body C, unique up to translation, with S(C; 52) = p(S2).Obviously, the area function of a polytope P is a discrete system of vectors A(P) ={a 1 I 1 < i < f(P)}, where f(P) is the number of facets of P. For each facet Fi of P,the direction of ai is that of the outward normal of Fi and the length of a i is equal to the(d — 1 )-content of F1.Definition 2.11 (Griinbaum [32] page 332.) A system V = {vi I 1 < i < n} of non-zerovectors in Rd is called equilibrated if E:1_ i vi = 0 and no two of the vectors in V arepositively proportional. V is called fully equilibrated in Rd when it is equilibrated andspans Rd .Theorem 2.23 (Minkowski's Fundamental Theorem, Griinbaum [32] page 332.)(1) If P is a polytope in Rd, then A(P) is equilibrated.^If P is ak-polytope, then A(P) is fully equilibrated in the subspace Rk parallel to the affinespace spanned by P.(2) If V is a fully equilibrated system in Rk , k > 2, there exists a polytope P, uniquewithin a translation, such that V = A(P).Chapter 2. Mathematical Background^ 31The brightness function (Section 2.1.6) cs(C; v) of C can be expressed in terms of thearea function S(C; S2) of C (Firey [20]):o(C; v) = J.^(v, u) 1 dS(C; u) .^ (2.18)2.2 Spherical ImagesDefinition 2.12 (Busemann [15] page 25.) Consider a convex hypersurface C. Thespherical image v'(p) of a point p E C consists of the points of Sd-1 which, as vectors, arethe outward normals of the support hyperplanes of C at p. The spherical image v'(M)of a set M C C isv'(M) = U v'(p) •pEMNote that spherical images are not defined for non-convex hypersurfaces, because thesupport hyperplanes at a concave point are not defined.Theorem 2.24 (Busemann [15] page 25.) For a convex hypersurface C, v'(C) is convex.Definition 2.13 (Busemann [15] page 26.) For any set M C C for which v'(M) ismeasurable, the integral curvature of M is defined asv(M) = measure of v'(M) .Theorem 2.25 (Alexandrov, Busemann [15] page 26.) Given a convex hypersurface C,v'(M) is measurable for any M E B(C) and the integral curvature v(M) is completelyadditive on 8(C).Chapter 2. Mathematical Background^ 32Theorem 2.26 (Alexandrov, Busemann [15] page 29.) For a given completely additivenon-negative set function a(M') defined for all M' E 13(S\") there exists a closed convexhypersurface C containing origin 0 in its interior such that a(M') = v(M) for theprojection M of M' from 0 on C, if and only if1. a(Sd- 1 ) = wd2. a(C) < wd —(wd is the area of Sd-1 , see Appendix A.)for every convex set C on Sd-1 , where /3 is the measure of thespherical image of the cone projecting C from 0 .Theorem 2.2'T (Busemann [15] page 30.) Let C1 and C2 be two closed convex hyper-surfaces containing 0 in the interior. If v(M1 ) = v(M2 ) for any Mi E B(Ci), i = 1, 2,which are projections of each other from 0, then C2 is obtained from Ci by a dilationwith center 0 .2.3 Numbers Associated with A SetThe numbers associated with a set examined in this section are volume, surface area,diameter and width. The emphasis is on how they can be calculated from the represen-tations defined in Section 2.1.Throughout this section, C is a convex body, x is the normal representation of theboundary of C, a1 , a2 , , ad_ i are the parameters introduced on Sd-1 in Section 2.1.2,u is a point on Sd', and du; is the area element on Sd-1 at u. We have (Bonnesen-Fenchel [7] page 64)audhy = det^au 1da l • • • dad--1 •aa i^aad_iChapter 2. Mathematical Background332.3.1 The VolumeLet V(C) denote the volume of C. Then V(C) = 0 if and only if C is at most (d - 1)-dimensional. It is known that V(C) depends continuously on C.Consider a non-degenerate polytope P. Denote by p1 , i = 1,...,N, the facets of P,by A(pi ) the area of p i , by ui the unit outer normal of the support plane of P containingpi. It can be proved (Busemann [15] page 44) that1 NdV (P) = - H(P;u i)A(pi ).A limit process of (2.19) givesV (C) 1dfsd_i H(C; w)dS(C;ci..,) .When H (C ; v) has continuous second derivatives,dS(C; u) = Fd_ l (C; u)dwThus1V (C)^I H(C;co)Fd_ i (C;^.Representing V(C) in terms of the chosen coordinate system gives1 ax^ax V(C) = f det x aaiaad-i dal • • • dad-i1^ax^axaad_i H(C; u)da i • • • dad- 1det aai1 fsd_ i det u a aui acvadu_ii H(C; u)Dd-i (H)(u)dai • • • dad-ia(2.19)Chapter 2. Mathematical Background^ 342.3.2 The Surface AreaLet (C) denote the surface area of a convex body C and S(C; SI) denote the areafunction of C. By Definition 2.10,(C) = S(C; S d-1 ) =^dS(C; w) .By the relation between the area function and the curvature function,S(C) = jS d-1 Fd-1(W)d(4.) .Representing the surface area in terms of the chosen coordinate system gives^ da i • • • dad-i •S(C) = f det [u axsd-1Given the (d — 1)-dimensional cross sectional measure o- (C; v) of convex body C, thesurface area S(C; S' 1 ) of C can be computed via Cauchy's formula (Bonnesen-Fenchel [7]page 53)S(C; Sd-1 ) = 1^o-(C; w)dwisd-12.3.3 The Diameter and the WidthDefinition 2.14 The maximum of B(C; v) over all v is called the diameter of C, denotedas D(C). The minimum of B(C; v) over v is called the width of C, and is denoted asA(C).Obviously, the diameter of a convex body of constant breadth is equal to its width.Chapter 2. Mathematical Background^ 352.4 TransformationsThere are two types of transformations described in this section. Transformations ofthe first type combine two sets into a new one. The new sets are determined by theirorientation-based representations which are the sum of the orientation-based representa-tions of the two given sets, i.e.,R(T(S1 , 82) ) =R(S1)+R(S2) ,where R. is an orientation-based representation of shape, T(Si , S2 ) is the transformedset. Minkowski vector addition, Blaschke addition and polar mean are of this type.Combinations naturally lead to questions of decomposition.Transformations of the second type transform a set into a new one such thatRi (T(S)) = R2 (S)where R1, R2 are two orientation-based representations of shape and T(S) is the trans-formed set. Projection body and polar reciprocal set are of this type.2.4.1 Minkowski Vector AdditionDefinition 2.15 (Griinbaum [32] page 316.) For two sets Q and R in Rd, the vectorsum Q + R of Q and R is defined asQ+R={x+y1xEQ,yER}.If P = Q + R, then Q and R are called summands of P. The process is called vectoraddition. Associated with the vector addition is a scalar multiplication AQ defined asAQ = {Ax 1 x E Q}. The set {a} + AQ, a E Rd , is said to be homothetic to Q, andpositively homothetic to Q if A > 0.Chapter 2. Mathematical Background^ 36Theorem 2.28 (Griinbaum [32] page 316.)(1) A set P is the vector sum of Q and R if and only ifH(P; v) = H(Q; v) H(R; v), for all v E Rd .(2) Let Q and R be two polytopes, qi , i = 1, . , n and ri , j = 1, . , m, be the verticesof Q and R, respectively. A set P is the vector sum of Q and R if and only if P is theconvex hull of the setfqi + ri I = 1 7 • • •^= 1 , • • • ,n2 1.Assertions (1) and (2) can be regarded as equivalent ways to define vector sum.Assertion (1) says that H(Q R; v) = H(Q; v) + H(R; v). Assertion (2) implies that thevector sum of two polytopes is again a polytope.In the same manner as the vector sum of two convex bodies is defined, the linearcombinations of convex bodies can be defined. Let A i > 0, i = 1, . . . , r, be arbitraryconstants. The linear combination of convex bodies Ci , i = 1, . , r, is defined asC =^+ • • • + Arx, I xi E Ci}and is denoted asC =^+ • • • + ArC, = Ei=iThe position of C generally depends on the choice of origin 0. If 0 is replaced by anotherpoint 0', C will be translated by (E1, 1 Ai — 1) 00', where 00' is the vector from 0to 0'. Hence, if >I = 1, linear combinations will be independent of the coordinatesystem. Of particular interest is the linear combination= (1 — e )Ci + 0612 , 0 < 0 <1, of two convex bodies C 1 and C2.Chapter 2. Mathematical Background^ 37Similar to the argument of Theorem 2.28, the support function H(C; v) of the linearcombination C of the convex bodies Ci , i = 1, , r, is the linear combination of thesupport functions H(Ci ; v) of Ci , i.e.,+ • • • + ArCr; v) = AiH(Ci; + • + A r li(Cr ; v).Recall the definitions and properties of the normal representation and the first curva-ture function. The normal representation and the first curvature function of the vectorsum of convex bodies are the sum of the normal representations and the first curvaturefunction of the convex bodies, respectively. There is, however, no study done about thedistance function of the vector sum of convex bodies. The area function of the vectorsum of convex bodies will be used to define the mixed area function of convex bodies.The volume of the vector sum will be used to define the mixed volumes.In the plane, every polygon is the vector sum of finitely many summands of a simpletype (segments and triangles), and every convex set is the limit of finite vector sums oftriangles. Both assertions fail to have analogues in higher dimensions.Since B(C; v) = H(C; v) + H(C; — v) for all direction v, for any convex body C,it follows that the breadth, in any given direction, of a vector sum is the sum of thecorresponding breadth of the summands.Let C' be the reflection of C about the origin. Then C+ C' is called the vector domainof C. A convex body C is a body of constant breadth if and only if its vector domain isa sphere (Firey [20] page 97).Let Bd be the unit ball in Rd having origin as the center. If C is a convex body, thenC + itBd (ti > 0) is called the parallel body of C at distance p.The area functions of parallel bodies will be used to define the i-th area function ofa convex body (Section 2.5.2).Chapter 2. Mathematical Background^ 382.4.2 Blaschke AdditionDefinition 2.16 (Firey [20] pages 94-95.) Let C i and C2 be two convex bodies witharea functions S(Ci ; 52) and S(C2 ; ft), respectively. The Blaschke sum of C 1 and C2 isdefined as the convex body C whose area function equals to S(C i ; + S(C2 ; 9), and isrepresented as C = C1 #C2 . The process is called Blaschke addition. The notion of scalarmultiplication associated with Blaschke addition is defined as the convex body with areafunction AS(C;11), and is denoted as A x C.The Blaschke sum is well defined, as is seen from Theorem 2.22 in Section 2.1.7. Sincethe area functions S(Ci ; CO and S(C2 ; ft) satisfy the conditions of the theorem, so doestheir sum. Thus a convex body is uniquely determined, up to translation, as having thesum of the two area functions as its area function. By definition,S(Ci#C2; C/) = S(Ci; f2) S(C2; 9 )Similar to the vector sum, the weighted Blaschke sum of a family of convex bodiescan be defined. Let Ci , i = 1,^, r, be convex bodies, A > 0, i = 1,^, r. DefineC^x Ci # • • • #A, x Cr = C=1Ai x Cqto be the convex body having function S(C; S2) = A i S(Ci ; C2) + • • • + S(Cr.; C2) as itsarea function. Similarly, Co = (1 — 0) x Cl # 0 x C2 , 0 < 0 < 1, is of particular interestunder certain circumstances.By equation (2.18), the brightness of a Blaschke sum, in any given direction, is thesum of the corresponding brightness of the summands.The decomposition of d-polytopes with respect to Blaschke addition is well behaved,as the following theorems show.Chapter 2. Mathematical Background^ 39Theorem 2.29 (Firey-Griinbaum, Firey [26] page 94.) Every polytope P is expressiblein the formP =where each Pi is a simplex. Further, if P is d-dimensional and the number of facets of Pis f(P) n > d 1, then there is a representation with m < n — d.Theorem 2.30 (Firey-Grunbaum, Firey [26] page 96.) Every d-polytope P is repre-sentable in the form P = #71 1 Pi where each Pi is a d-polytope with the number of facetsof Pi is f (Pi) < 2d.Let C' be the reflection of C, C#C' is defined as the areal domain of C. Since C#C'is central, and C, C' have the same brightness function, by Theorem 2.20, C has constantbrightness function if and only if C#C' is a sphere.2.4.3 Polar MeansAnother combination of convex bodies can be defined by a combination of distance func-tions. The definition and the theorem (of Brunn-Minkowski type, according to Firey) inthis subsection are from Firey [19].Definition 2.17 (Firey [19] page 444.) Let C1 and C2 be two convex bodies containing0 as a common interior point. Define function go(P) as follows:g (1 ) ( x)^1/(1 - 0)(g(Ci; x))P + 0(g(C2; x)) 1'^1 5_ p < 00 ,A,°°) (x) o pgr(x) = max(g(Ci ; x),g(C2; x)) , for 0 < 0 < 1 ,e ) (x)^g(Ci; x) , for i 1, 2.Function g (oP) (x) satisfiesChapter 2. Mathematical Background^ 401. .g,i)) (x) > 0, for x^0, .g 5,7' ) (0) = 0;2. gr (Ax) = Agr (x);3. .91P) (x + y) < .9 P) (x) + .99P) (Y)•By Theorem 2.15, there is a unique convex body Csf,P) whose distance function is 4(x).Call this body the p-th dot-mean of Co and C1 . The convex body with distance function'.\\ 'I (g(Co ; x))P + (g(Ci ; x))P is called the p-th dot-sum of Co and C1 .Theorem 2.31 (Firey [19] page 453.)vl/d(co n CO < vi/d(do) < 1/,'61 — ow-P/d(co ) + eV-p/d(ci ) ,for 1 < p < oo. There is equality on the left if and only if Co = C1 and on the right ifand only if Co = AC1 with center of homothety at 0. Furthervi/d(co n CO = vl/d(d\") ) ) < min(vlid(c0), vl id (ci))with equality on the right if and only if C o = C1 .2.4.4 The Projection BodyDefinition 2.18 (Petty [59] page 234.) Let C be a non-degenerate convex body andlet cr(C; v) be its cross sectional measure. The convex body with center at origin andsupport function o- (C; v) is called the projection body of C, denoted as P(C).By definition, H(P(C); v) = o- (C; v), for all v. That is to say the distance of thesupport hyperplane of P(C) with normal direction v from the origin is equal to the (d- 1)-dimensional content (area, if d = 3) of the projection of C onto the same hyperplane.Chapter 2. Mathematical Background^ 412.4.5 Polar Set, Conjugate, and Legendre TransformDefinition 2.19 (Lay [42] page 140.) Let S be any nonempty subset of Rd. The polarset S* of S is defined byS* {y E Rd : (x,y) < 1 for all x E S} .Theorem 2.32 (Lay [42] page 142.) Let S be nonempty set. Then S* is a closed convexset containing 0.Theorem 2.33 (Minkowski, Lay [42] page 140.) Let C be a compact convex body in Rdwith 0 E int C. Let C* be the polar set of C. Then the support function of C is equalto the distance function of C*, and the distance function of C is equal to the supportfunction of C*.Definition 2.20 (Rockafellar [64] page 201.) Let f be a proper convex function on Rd,i.e., an everywhere-defined convex function with values in (—oo, +oo], not identically +co.Suppose also that f is lower semi-continuous (1.s.c.), in other words that {x I f(x) 0 the volume of C =^AiCi is a formv(c) = E E • E 14,^• Aidi=1 i2 =1^id=1of degree d in the A i , where the coefficients^...id are uniquely determined by requiringthat they are symmetric in their subscripts. Then Vi i ...id depends only on the bodiesCil , .^Cid and not on the remaining bodies^Write V(Ci i ,^, Cid ) for Vi,...i d , andcall it the mixed volume of Ci„^,The most important mixed volumes are the ones that involve only two distinct convexbodies. The notation Vi(C i , C2 ) was introduced as follows (Busemann [15] page 43):Vi (Ci , C2 )^V(Ci, • • • C17^= Vd-i(C2, C1) •d-iThen(dA2C2)^Ai-92Vi(C1, C2) .1=0^iWhen d = 3, A i = )12 = 1,V(C1 + C2) = V(C1) V(C2) 31/1(C1, C2) + 31/1(C2, C1) 'Since V( AiC) = (> Ai)dV(C), then V(C,^C) = V(C) .The mixed volumes can be computed from the support functions and the area func-tions of the convex bodies involved. Recall equation (2.19)NV(P) = E H(P; u1)A(pi)where pt, i = 1, . . . , N, are the facets of a non-degenerate polytope P, A(pi ) the areas ofpi and ui the unit outer normals of the support planes of P containing p1 . This can beChapter 2. Mathematical Background^ 45generalized to the mixed volumes of a polytope P and an arbitrary convex body C1 as(Busemann [15] page 44)1 NVi(P,^d= — EH(Ci; ut)A(pi) .^(2.20)A limit process of the above equation yieldsV1 (C,^= isd_ i H(Ci ; co)dS (C; b.)) ,^(2.21)where C is an arbitrary convex body.Let C1 , C2 ,^, Cd be convex bodies, x( 1 ), x( 2), . , x(d) their normal representations ofthe boundary, a l , a2,^, ad_ 1 the parameters introduced on Sd-1 in Section 2.1.2, thenv(ci,• • • , Cd) = c71^E^det [x(d) 8x(t1)^ax(id-1)] dal • • dad-1Oad-iwhere the sum is taken over all permutations of (1, • • • , d — 1).If Bd is substituted for C* in equality (2.21), thenV1 (C, Bd) =^H(Bd; w)dS(C; w)1 js, dS(C; w)-c-IS(C) , (2.22)because H(Bd;cy) 1 on Sc1-1 . In fact, Bonnesen and Fenchel [7] define the surface areaS(C) of an arbitrary convex body C as d • V1 (C, B\").Let u denote the segment of length 1 that joins origin and the point u E S'. It isnot hard to see that (Bonnesen-Fenchel [7] page 50)V(C -I- A 77;) = V(C)+ Ao- (C; u) .Thus, by the definition of the mixed volume,o-(C; u) = d • Vi (C,it) .Chapter 2. Mathematical Background^ 46Theorem 2.36 (Petty [59] page 234.) The non-degenerate convex bodies C 1 and C2have the same projection body if and only ifL) = V1 (C2 , L)for any convex body L that has a center.DefineWi(C) V (C, ,C, Bd^Bd =_^Bd).Then the volume of the parallel body of C at distance it can be expressed as(V (C ilB d ) = Wo (C)^Wi(C)/i + • • • + dWd(C)p d1The quantity Wi(C) is called the i-th cross sectional measure integral: Wo (C) is thevolume of C, W1 (C) is the surface area of C, and Wd(C) is always the volume of the unitball.Some inequalities between the mixed volumes are of fundamental importance to theuse of orientation-based representations to solve the attitude determination problem.They follow from the next theorem.Theorem 2.37 (Brunn-Minkowski Theorem, Busemann [15] page 48.) If C1 and C2 areconvex bodies in Rd , then7(9) =^- e)ci + 0c2 ) , 0 < B < 1 ,is a concave function of 0, which is linear if and only if C 1 and C2 are homothetic or liein parallel hyperplanes.Corollary 2.38 (Minkowski's Inequality, Busemann [15] page 48.)c2) vd- '(c1 )v(c2 ) .Chapter 2. Mathematical Background^ 47If C1 and C2 do not lie in parallel hypersurfaces the equality sign holds only when Ci.and C2 are homothetic.Corollary 2.39 (Quadratic Inequality of Minkowski, Busemann [15] page 48.)VAC]. , C2 ) ? V (Ci)V2(Ci. , C2 ) •These inequalities are used to solve many extremal and uniqueness problems.The above inequalities involve only two convex bodies. Extensions of those results toother mixed volumes were proven by Fenchel and Alexandrov independently.Theorem 2.40 (General Brunn-Minkowski Theorem, Busemann [15] page 49.) If C 1and C2 are convex bodies in Rd , Co = (1 — 0)C1 + 0C2 , then70) = Illim (C17 • • • 7C:1-77 ,007 • • • ' CO) , 2 < m < d ,where Ci, ... , C[1_,, are convex bodies, is for 0 < 0 <1 a concave function of 0.Theorem 2.41 (Busemann [15] page 51.) If C1 and C2 are convex bodies in Rd ofdimension at least m, and if CI, ... , qi_m are regular convex bodies, Co = (1-0)C1+0C2,then7(0) = vilm(cl, — , c'd_m, co, — , co) , 2 < m < d ,is linear if and only if C1 and C2 are homothetic.With the aid of the above two theorems, in the same way as Minkowski's inequalitywas obtained, the following more general inequalities involving the mixed volumes areobtained.Chapter 2. Mathematical Background^ 48Theorem 2.42 (Busemann [15] page 50.) If C1 and C2 are convex bodies in Rd ofdimension at least m, and if CI, , qi_m are regular convex bodies, then for 2 < m < d,0 < i V (CL • • • , C ld-2, Cl, C1) ' V (C;, • • • , CY 1-2, C2, C2)7with equality if and only if C1 and C2 are homothetic.Alexandrov extended these inequalities further to the following more general inequal-ity:Theorem 2.44 (Busemann [15] page 50.) If C1 , , Cd are convex bodies, then for2 < m < d,Trt-1Vm (Ci, • • • , Cd) >^V(C1, • • • , C d—rn, C d—i, • • • , C d—i) •1=0A special case of the above inequality occurs when m = d.Corollary 2.45 (Busemann [15] page 50.)v(c1y(c2),...,v(cd ). (2.23)Chapter 2. Mathematical Background^ 492.5.2 The i -th Area FunctionDefinition 2.23 Let C be a convex body, Bd be the unit ball, 52 E 13(Sd-1 ). Then forA > 0, S(C ,Bd ; 52) is the polynomial in A (Firey [24] page 205)d — 1iSd_i_i(C; 52)Ai .This defines the measure Si(C; 52) over B(Sd-1 ) for i = 0,1, ... , d — 1 . Call Si(C; 52) thei-th area function of C.Let A equal to zero in the definition, then Sd_i(C; 52) is the (primary) area functionof C defined in Section 2.1.7.If C is a regular convex body and r 1 , r2 ,^,rd_ i are the radii of principal curvatureof the surface of C, then (Firey [23] page 346)-1(d — 1)where {Ti,., ri} is the i-th elementary symmetric function of r 1 , r 2 ,^rd_ i . Thus,the i-th area function of a convex body is the integral of its i-th curvature function. Inparticular,Si (C; 52) =1^fd — 1 io (ri + • • • + rd-l)dw^ (H1 1 + • • • + Hdd)dw , 52 E B(Sc1-1 )^= d —1 1 AI (2.25)Sd-i(C; S2) = L(r i • • • rd_ i )dw ,^52 E B(Sd- 1 ) .Because the support function of a vector sum is the sum of the support functions of thesummands, by (2.25),S1(C1 + C2; 9) = Sel; + Se2; 52 ) •Si (C; 51) {^, ri}dco , ci E B(Sd-1 ) , (2.24)Chapter 2. Mathematical Background^ 50By the definition of the area function,sd_ i (c4c2;^= sd_i(ci; + sd_i(c2; c2)Theorem 2.46 (Schneider [69] page 47.) For convex body C, i = 0,1, ... , d — 1,wdSi(C;co) = 0 .Isd-1Theorem 2.47 (Alexandrov-Fenchel-Jessen Theorem, Schneider [69] Theorem (9.1) page43.) If C1 and C2 are convex bodies in Rd , i E {1, • • • ,d — 1}, dim C 1 , dim C2 > i + 1,then Si (Cl ; •) = Si (C2; •) if and only if C 1 and C2 are translations of each other.Theorem 2.48 (Alexandrov 1961, Schneider [69] Theorem (9.6) page 44.) Suppose C 1and C2 are convex bodies in Rd for which Si(Ci ; Q) < Si(C2 ; Q) for all Q E 13(Sd-1- ) andSi+i (Ci ; Sd-1 ) > Si+i (C2; Sd-1 ), for some i E {1,^, d — 1} (where for i^d — 1 thesecond condition has to be replaced by V(C 1 ) > V(C2 )). Then C1 , C2 are translations ofeach other.The above theorems are about the uniqueness of convex bodies with respect toi-th area functions. Results about the existence of a convex body, for which i-th areafunction is given, are stated in terms of the necessary and sufficient conditions for ameasure defined over 13(Sd-1 ) to be i-th area function of a convex body. The problem iscalled Minkowski-Christoffel problem (Firey [25]). For i = d — 1, the solution is presentedin Section 2.1.7. Firey [22] solved this problem for the case of i = 1.Theorem 2.49 (Firey [22] page 21.) A completely additive set function over B(Sd-1 )is the first area function of a convex body if and only if it satisfiesuto(du) = 0 ,fsd-iChapter 2. Mathematical Background^ 51isd-1^u)(D(du) < -Foo ,where g i is the fundamental singularity/gi (u', u) =^—^ [arc cos((u', u)/Ilull-7 -r in arc cos((u', u)/Ilull Hull) if d = 3,3-d if d > 3,andfsd-1 A(u', ,u)(1.(du) > 0,whereA(u', v', u) = F(u', u)^F(v', u) — F(u' v', u),F(u', u)^^(d — 2)(u', u)G(uf , u) — (u', VG(u', u)),G(u f , u) = 7(s(u',u)) ,7(s)^scosecd- 2t^sire d- 2t'dtf) dt ,Lod 112s(u\",u) = arc cos ((u', u)/I1411u'll) ,G(u' ,u) = 11n [1^(u'' ) II for d = 3 .47rThus for d = 3, the Minkowski-Christoffel problems are solved, although the problemsare still open for d > 3. The quantity So (C; ft) is the area of ft For Si (C; 9), theproblem can be thought of as a generalization of Christoffel's problem, which is discussedin Section 2.1.3. For S2 (C; 9), the problem can be thought of as a generalization ofMinkowski's problem which is also discussed in Section 2.1.3.If P is a polytope, the i-th area function is (Goodey and Schneider [31] and Firey [23])Si(P;^=(d — 1f) n 12)voli(f(P)Chapter 2. Mathematical Background^ 52where ,Pi (P) is the set of i-dimensional faces of P, voli (f) is the i-dimensional volumeof the i-face f, o-(P, f) denotes the spherical image of f, that is, the set of all outer unitnormal vectors to P at the points of f and Ad_i_j is the (d —1— i)-dimensional sphericalLebesgue measure on the (d — 1 — i)-dimensional great sphere of S\".The converse of the above also is true.Theorem 2.50 (Goodey and Schneider [31] page 187.) Let C be a convex body in Rdwith dim C > i 1, 1 < i < d — 1. Suppose that the support of the area functionSi (C; SI) can be covered by finitely many (d — 1 — i)-dimensional great spheres. Then Cis a polytope.A necessary and sufficient condition for a Borel measure on S\" to be the area func-tion Sd_i(P; f2) of a polytope P is given by Theorem 2.23 in Section 2.1.7. Schneider [68]determined necessary and sufficient conditions for a Borel measure cb on S\" to be thefirst area function of a convex polytope. The notion of spherical complex is used in theconditions.Definition 2.24 (McMullen and Shephard [54] page 153.) A spherical polytope in 5\" isthe intersection of a finite number of closed hemispheres which is not empty and containsno pair of antipodal points of Sd_ i . A spherical complex C is a finite set C = , cr l ofdistinct spherical polytopes (cells) q on S\" which satisfies the following two conditions:1. u ci = S d ,2. For each i, j, the intersection q fl cl is a face (proper or improper) of both q andC3'Note 1 Spherical images of all non-empty faces of a polytope determine a sphericalcomplex on 5\".Chapter 2. Mathematical Background^ 53Note 2 Each d-polytope P corresponds to a spherical complex by the mapping,0 : bdP ---4 8d-1 , which maps x to the intersection of the ray, Ox, from 0passing x with the sphere Sd'. The mapping 0 maps proper faces to sphericalpolytopes. It has been shown that the reverse is not necessarily correct, i.e., thereare spherical complexes that are not radial projections of any polytopes.The first area function Si (P, ft) of a polytope P can be represented as (Firey [23]page 351)Si (P' 9) = d 1 —1 E A(e)pd_ 2 (ft n v(e)) ,for any C2 E .6 (Sd-1 ), where the summation goes over all edges e of P, A(c) is the lengthof edge e, v(e) is the spherical image of e, and itd_ 2 (12 fl v(e)) is the (d — 2)-dimensionalcontent of 9 fl v(e) on Sd-1 .Theorem 2.51 (Schneider [68] page 81.) For a Borel measure 0 on Sd -1 there exists ad-polytope P such that 0(52) = Si (P, 52) if and only if 0 satisfies the following conditions:1. The support of 0 is the union of the (d — 2)-dimensional elements of a sphericalcomplex S.2. For each (d-2)-element ( of 5, there exists a positive number A(K) such that 0(s2) =A(C)pd_ 2 (12) for each S2 C C.3. For each (d-3)-element ri E 5,E A(007 , 0 = oCwhere the summation goes over all (d-2)-elements C E S for which ri is a side, andu(77, C) = vc/lIvcji such that v C is the orthogonal projection of C on the 2-dimensionallinear subspace orthogonal to 77.Chapter 2. Mathematical Background^ 54Let s, , G be the (d-1)-elements of S. For any j, 1 < j < k, an ordered sequence, 'in,,) of (d-1)-elements of S can be constructed such that^fl^is a (d-2)-element, r = 1,^, m — 1, i 1 = 1, in, = j. Define xi asm-1nxi = E^ir+1)r=1where v(ir , ir+i ) is the unit vector which is orthogonal to the linear hull of S i r n^i r+l andpointing into the interior of the halfspace containing^The convex hull of the pointsx i ,^, xk is the polytope whose first area function is the given measure.2.5.3 The Mixed Area FunctionsDefinition 2.25 (Schneider [69] page 31.) The area function of C =^AiCi is a formr^r^r^rS(EA2Ci; f/) =EE•-• E Ail • •^• • ,Cid_1; f2 )i=1^i1=1 i2=1^id-1=1(2.26)of degree d — 1 in the Ai, where the coefficients S(Ci„^, Ci d ; 11) are uniquely deter-mined by requiring that they are symmetric in their subscripts. Then S(Ci„^Ci d ;10depends only on the bodies Ci„ , Cid_ i and not on the remaining bodies Ci. CallS(Ci„^, Cid ; 9) the mixed area function of Cif,^,By definition,Si(C; C2) = S(C,^, C, Bd ,^Bd • 52) . (2.27)The mixed area function was originally defined by Alexandrov and Fenchel-Jessen viamixed volume. It can be proven that, for given convex bodies^, Cd_i, there existsa unique measure^, Cd_i; •) on B(Sd-1 ) such thatV (C,^, Cd_ i ) =^H(C; w)dS(Ci , . • Cd- i; (2.28)is H(C1 Li;w)dS(C2, ,Cd_ i ,C;w)d d-i1Chapter 2. Mathematical Background^ 55for any convex body C. This measure was defined as the mixed area function ofC1 ,^, Cd-i. Using this definition, equality (2.26) was then proven.SinceV(Ci + L i , C2 , . , Cd_i, C)d-11+ -(7 isd H(C;co)dS(L i ,C2 ,...,Cd- 1 ;W)H(Ci;co)dS(C2,...H(Li;w)dS(C2 ,.H(C; w)dS(Ci , C2,C ;• • 7 Cd-17 C; C47 ), Cd-i;thenS(C1 + L1, C2, • • • , C d-1;^= S(C1, C 27 • • • 7 C d-1; 9) + S(L.1, C27 • • • , C d-1; 9) • (2.29)Recall (2.22) that d • V(Bd ,C,...,C) is the surface area of C, the quantityd•V(B d ,C1 ,. • • , Cd_i) is defined as the mixed surface area of convex bodies C 1 , C2, • • • , Cd-1.Of particular interest is the mixed area function of two convex bodies. By definition,d — 1A2C2; 9 ) =),C1,C2,••• , C2; P)A1-1-1 A i ^(2.30)i=o^i d-1-iOne fact about the mixed area function is that the measure is not concentrated onany great sphere of S d-1 and has the origin as the centroid (when viewed as mass loadingon Sd -1 ), i.e.,iSd-1 WdS (Ci • • . Cd-i ;^= 0 .^ (2.31)Chapter 2. Mathematical Background^ 562.5.4 The Mixed Curvature FunctionRecall from Section 2.1.3 that the curvature functions of a convex body is defined by theelementary symmetric functions of the radii of principal curvature, which must assumethe continuity of the second derivatives of the support function of the convex body. Amore general definition of the curvature functions employs the mixed volumes and doesnot make smoothness assumptions.Definition 2.26 (Bonnesen-Fenchel [7] page 121.) Let C be a convex body. If a functionFi (C; u) is continuous and non-negative on Sd -1 , and if for an arbitrary convex body Lwith support function H (L; u),V(L,C,. ,C,^= 1 (d — 1 -1 j(d-i H (L; w)Fi(C; w)du, ,^(2.32)it is called the i-th curvature function of C.The i-th curvature function Fi (C ; u) of a convex body C has the following properties:1. A convex body can have at most one continuous i-th curvature function Fi;2. fsd-, wFi(C; w)dw = 0;3. When H(C; u) has continuous second derivatives, Fi(C ; u) = {ri^ri} = Di(H(C)).Definition 2.27 The i-th curvature function of A 1 C1 A2C2 is a homogeneous polyno-mial of degree i in A l and A2. Its coefficients are called the mixed curvature functions ofC1 and C2.Chapter 2. Mathematical Background^ 572.5.5 The Mixed BodiesFirey [20] initiated the study of the mixed bodies with d = 3. The area function ofCo = (1 — 0)C1 0C2 , where C1 and C2 are convex bodies, is given by the generalizedSteiner formula (Firey [20] page 95) as^S(C,9; f2) = (1 — 0) 2 S(Ci ;^+ 20(1 — 0)S12 (52) 02 S(C2; Q) •There is a unique convex body which has 812 as its area function. Firey called this convexbody the mixed convex body resulting from C1 and C2, and denoted it as C(C1 , C2 ). Then(1 — 0)C1 0C2 = (1 — 0) 2 x C1 # 20(1 — 0) x C(Ci , C2 ) # 0 2 x C2 .In general, the mixed body of d — 1 convex bodies in Rd can be defined.Definition 2.28 Let C1 , ... Cd_ i be convex bodies. By Theorem 2.22 and equality (2.26),there is a convex body, unique up to translation, whose area function isS(Ci , • • • , Cd_i; f2). This convex body is called the mixed body of C1 , , Cd_ i , denotedas [C1 ,^• , Cd-i] •By definition,S( [611 ,^, Cd_ i ];^= S(Ci, • • • Cd-1; 9) •From the properties of area function it follows that [C1 ,^, Cd_ i] is symmetric in itsarguments, and that if the Ci are replaced by homothetic copies, the resulting mixedbody will be homothetic to the original. It also follows that [C, , C] = C, whereequality is assumed to mean up to translation. By (2.29),[C1 + L 1 , C2, • • • , Cd-1] = [C1, C2, • • • Cd-l] #[-L1, C2, • • • , Cd-l] •The following notation is introduced:[C1, C2] , :a'^C2 • • •7 C2^[C]i ^[C1, Bd[i •d-1-iChapter 2. Mathematical Background^ 58Then by definition,Cif + c2 =When d = 3,Also by definition,When d = 3,C1 + C2 = C1#2 x [C1, C2]#C2 •S ([C]i; ft) =^12) .S([C, B d]; 52) = Si (C; 52) .Lutwak [50] studied the volume of mixed bodies. The following two theorems are ofspecial interest to us.Theorem 2.52 (Lutwak [50] page 492.) If C1 , , Cd_ i are convex bodies in Rd , thenV(Ci) • • • V(Cd-i) < vd-1 acti,^1\\d-1with equality if and only if C1 are homothetic.Theorem 2.53 (Lutwak [50] page 492.) If C1 and C2 are convex bodies in Rd , then1 1/(d-1)[d--1 d — 1)V 1 ld (C1 )+V 1 ld (C2) < E^od_o/d([ci, c2]1)^<^c2)i-,0with equality, in either of these inequalities, if and only if C 1 and C2 are homothetic.2.5.6 The Dual Mixed VolumesDefinition 2.29 (Lutwak [49] page 532.) Let C1, ... Cd be convex bodies. The dualmixed volume of C1, .^C d is defined as, Cd)^7/1 isd 1 p(Ci; w) • • • P(Cd; w)dwChapter 2. Mathematical Background^ 59The dual mixed volume has the following properties (Lutwak [49] page 532):1. V^ is continuous, V(C1, ...,Cd) > 0;2. V(Ai C1 , • • • , AdCd) =^• A di/ (Cl,^, Cd), Ai > 0;3. If Ai C Bi for all i then \"V(A1,^, Ad) <^• • • , Bd )if A i = B, for all i ;4. f/(C,...,C) = V(C).with equality if and onlyThe notation 14(C1 , C2 ) is introduced:14(Ci, C2)^ • • • ,C2) •d—iTheorem 2.54 (Lutwak [49] page 533.)• • ,cd) 5 H v(ci.,• • • 7 Cd—m,i=01 < m < d ,with equality if and only if Cd_m-Fi, Cd-m+2,^, Cd are all dilations of each other (withthe origin as the center of dilation).A special case of Theorem 2.54 occurs when m = d.Corollary 2.55 (Lutwak [49] page 534.)v (co• • • V(Cd )with equality if and only if C 1 , C2 ,^, Cd are all dilations of each other (with the originas the center of dilation).Combining this corollary with the Alexandrov inequality (2.23) yields:Chapter 2. Mathematical Background^ 60Corollary 2.56 (Lutwak [49] page 534.), cd ) < v(ci ,^, cd) ,with equality if and only if C 1 , C2 ,^, Cd are all dilations of each other (with the originas the center of dilation).A special case occurs when only two convex bodies are involved.Corollary 2.57 (Lutwak [49] page 534.)c2 )^ c2 )with equality if and only if C 1 is a dilation of C2 (with the origin as the center of dilation).2.6 SummaryVarious orientation-based representations of shape have been defined. Foundation forstudying the orientation-based representations have been surveyed and presented coher-ently. The characteristic properties of the orientation-based representations of shapeinclude:1. One-to-one property;2. Necessary and sufficient conditions for a function to be a valid orientation-basedrepresentation;3. Reconstructability.The common property of all the orientation-based representations is that they rotate inthe same way as the object rotates.Chapter 2. Mathematical Background^ 61The support function plays a very important role in the analysis. It links the resultstogether. Most other representations can be computed from the support function. Thesupport function also is related to the Legendre transformation used in applied mathe-matics.The distance function and the radial function deserve special attention because inaddition to convex bodies they are well defined for compact starshaped sets.When d = 3 there are two curvature functions and two area functions. The firstcurvature function is the sum of the radii of principal curvature and the second curvaturefunction is the reciprocal of the Gaussian Curvature. The area functions may seeminappropriate for any practical use because their domains are !3(S\") instead of 5\".But, when the objects are polytopes, the support of their area functions can be coveredby finitely many points (for the (d — 1)-th area function) or line segments (for the firstarea function) on S\".Table 2.1 summarizes the properties of the representations, where S is an arbitraryset in R3 and Q is an arbitrary polyhedron in R 3 . Results about the one-to-one propertyof the representation, necessary conditions for a function to be the representation of ashape and sufficient conditions for a function to be the representation of a shape areknown for all the representations listed. Except for the second curvature function andthe second area function, all representations can be inverted to reconstruct the object.The rest of this dissertation is concerned with attitude determination. Previous re-search is surveyed in Chapter 3 and new results are presented in Chapter 4. The theoremsof this chapter provide the necessary and sufficient conditions for two bodies to be homo-thetic. In particular, conditions on the extrema of inequalities involving orientation-basedrepresentations are used.Chapter 2. Mathematical Background^62DefinedExtentOne-to-oneExtentNecessaryConditionsSufficientConditionsReconstructableH(S; u) arbitrary convex knownTheorem 2.2knownTheorem 2.3yesTheorem 2.5x(S; u) convex convex knownTheorem 2.8knownTheorem 2.8yestrivialg(S; u) arbitrary starshaped knownTheorem 2.14knownTheorem 2.15yesPage 24p(S; u) arbitrary starshaped knownvia g(S; u)knownvia g(S; u)yesvia g(S; u)TVS; u) convex convex, up toa translationknownTheorem 2.9knownTheorem 2.11yesTheorem 2.11F2 (S; u) convex convex, up toa translationknownTheorem 2.9knownTheorem 2.10unknownSi (S; Sl) convex convex, up toa translationknownTheorem 2.46knownTheorem 2.49yesTheorem 2.49S2 (S; 52) convex convex, up toa translationknownTheorem 2.21knownTheorem 2.22unknownSi(Q; Q) convex convex, up toa translationknownTheorem 2.51knownTheorem 2.51yesTheorem 2.51S2 (Q; SI) convex convex, up toa translationknownTheorem 2.23knownTheorem 2.23yesLittle [47]Table 2.1: Properties of orientation-based representations.Chapter 3Previous ResearchIn machine vision, previously used orientation-based representations of shape, as definedby Definition 2.1, include the Extended Gaussian Image (EGI) and generalizations de-fined by Liang and Todhunter [45] and by Kang and Ikeuchi [40]. Representations notpreviously described as orientation-based but which easily fit the framework defined inSection 2.1 are the Gaussian and mean curvatures, as used, for example, by Besl [5].The Extended Gaussian Image and its discrete version are the second curvature func-tion and the second area function respectively. It is known from Chapter 2 that theseorientation-based representations are one-to-one only for convex bodies. There has beensome effort to apply the Extended Gaussian Image to non-convex shapes [35, 47].A different point of view is taken here. Instead of extending the definitions of existingorientation-based representations, new orientation-based representations are sought thatare well defined and well behaved when applied to non-convex sets. In particular, thedistance function and the radial function are of interest since they are well defined andone-to-one for compact starshaped sets. The radial function for two dimensional setshas been used to represent the 2-D contours of objects [28, 29]. Schudy and Ballard [70]used the radial function to model the 3-D shape of hearts. As far as is known, the radialfunction has not previously been used in 3-D attitude determination.Nalwa [57] argued that differential geometric representations are, in general, inade-63Chapter 3. Previous Research^ 64quate and suggested that global geometric information be incorporated. He proposed touse the support function because of its locality, unambiguity and additiveness. However,no suggestion was made about how the representation could be used in surface matching.In fact, Little [47] had already used the support function in object reconstruction andattitude determination. The use of the support function by Little [47], however, is forpolytopes only. One novel contribution of this thesis is to use the support function inattitude determination for smooth, strictly convex objects, as described in Section 4.1.The remainder of this chapter is organized as follows. Section 3.1 reviews the devel-opment of the EGI and its use in recognition and attitude determination. Section 3.2looks at efforts to extend the EGI to handle more complicated objects and to solve otherrelated problems. Section 3.3 surveys the use of these representations in computationalvision. Finally, Section 3.4 summarizes the current state of the art by enumerating whathas been done and what has not been done using these orientation-based representations.Throughout this chapter, only three dimensional space, R3 , is considered (i.e., d = 3).3.1 The Extended Gaussian ImageThe idea of the Extended Gaussian Image originated with Smith [71]. Smith calledthe representation the Enhanced Spherical Image (ESI) because of its connection tothe spherical image (Section 2.2). \"An ESI model for a convex object consists of aset of vectors. An individual vector's direction component represents the direction of asurface normal of the object, and the vector's magnitude signifies the object's surfacearea corresponding to the particular normal direction.\" This is equivalent to the EGIfor a polytope as discussed later in this section. The ESI model could not representsmooth objects since the spherical image of a smooth object includes finite area patcheson the sphere. A theorem of adjacency proposed by Smith [71], which claimed thatChapter 3. Previous Research^ 65adjacent points in an ESI were the mappings of adjacent faces in the correspondingconvex polyhedron, was later shown to be false by a counter example due to Moni [56].The formal definition of the EGI was given by Horn [35].Definition 3.1 (Horn [35] page 1675.) The Extended Gaussian Image is defined, fora surface C, as a map, Gc : Sd' which associates the inverse of Gaussiancurvature at a boundary point of a surface to the orientation u E Sd-1 of the surface atthe point:1Gc (u)= Kc(x(u)) ,where x(u) is the point on C with unit outward normal u, and Kc(x(u)) is the Gausscurvature of C at point x(u). Such a map Gc is called the EGI of C.Clearly, the EGI is exactly the second curvature function of a surface. Thus, Theo-rem 2.10 guarantees the existence of a unique, up to a translation, closed convex surfacewhose second curvature function is a given function satisfying the necessary condition.This definition of the EGI requires that the surface is smooth. A definition of the EGIthat captures the geometric description of a surface without requiring differentiability isneeded when polytopes are encountered. A discretized version of EGI also is neededwhen the EGI is represented numerically. Since the Gaussian curvature at the faces ofa polytope vanishes, Definition 3.1 can no longer be used directly. In this situation,the area function of a polytope (Section 2.1.7) is used, i.e., a discrete system of vectorsA(P) = {a t: I 1 < i < f(P)}, where f(P) is the number of facets of P, the direction ofa i is the same as that of the outward normal of face F, and the length of a i is equal tothe (d — 1)-content ofThe justification for using the area function for polytopes is twofold:Chapter 3. Previous Research^ 661. The curvature function and the area function are associated by equality (2.24),S(C;^=^rir2 • • • rd-idwwhere r 1 , r2 ,^, rd_ i are the radii of principal curvature;2. The Gaussian curvature can be defined as(E)IK(p)^lE, limo IGiEiwhere E is a compact portion of the surface containing p, G(E) is the sphericalimage of E, and I • I is the surface area measure.The EGI has the following properties:1. It is insensitive to the translational position of an object;2. It is one-to-one for convex bodies (cf. Theorems 2.22, 2.23);3. It can be computed easily from needle diagrams obtained using photometric stereo,or depth maps obtained using laser range finders or binocular stereo (cf. [36]).The EGI has been used in recognition and attitude determination. Brou [12, 13]defines matching error, M(y) = .192 Ko(7(0))) — Ki(w) I dw, as a function of the rotation,y, where Ko and Ki are the Gaussian curvatures of the model and the object, respectively.The solution lies in the minimum of the error function and is found by enumerating thediscrete rotation space. In Horn and Ikeuchi [37], the EGI of a prototype is rotated tomatch the EGI of a sensed object until the sum of the square of the differences betweenthe two EGI's is a minimum. The prototype that achieves the minimum difference amongall prototype identifies the sensed object. Ikeuchi [38] viewed the problem of matching asthe determination of the line of sight and the rotation angle with respect to an internalChapter 3. Previous Research^ 67model. The EGI mass center constrains the line of sight, and the EGI inertia directionconstrains the rotation around the line of sight.Little [47] made use of Brunn-Minkowski's Theorem (Theorem 2.37) to reconstructa polytope from its EGI and to determine the attitude of a polytope with respect to amodel. Let P and Q be two convex bodies, R = AP + (1 — A)Q. By the Brunn-MinkowskiTheorem,OOP + (1 — A)Q) AVt(P)d- (1 — A)171(Q)If the left hand side is replaced by its representation in terms of mixed volumes, oneobtainsVi3(Q,P) V(P)V 2 (Q)The Brunn-Minkowski Theorem states that the polytope P, having unit volume, thatminimizes Vi (Q, P) is homothetic to Q.^Now suppose Q has area functionA(Q)^{A(qi) I 1 5 i^N}, where qi are faces of Q with outward unit normal w i .Recall, from equality (2.20), thatNVi3 (QP) = E H(P; wi)A(qi)) 3 .Using this relation, Little developed an iterative method which combines the tech-niques of constructing a polytope from its support vector (values of support functionat the facet orientations of the polytope) and minimization techniques to construct thesupport function of P such that A(P) A(Q). This is to say that given a sensed EGIA(Q), its corresponding polytope can be reconstructed.In attitude determination, a sensed EGI, A(Q), is given and the task is to find theattitude which rotates the sensed EGI into correspondence with the prototype EGI.Consider the P in the above inequalities as the prototype. Then to determine objectattitude, Little minimizedNE H(P; R(wi))A(qi)i=iChapter 3. Previous Research^ 68over all rotations R. When only the portion of a surface corresponding to a single visiblehemisphere is sensed, the EGI of the object is not complete. Little usedE H(P; R(wi))A(qi) ,Lai E S2 (V)where the S 2 (v) is the hemisphere visible from viewing direction v. Good performance ofthe method using the mixed volume with both complete and partial EGI was reported.3.2 Generalization of the EGIThere have been several attempts to generalize the EGI so that a larger class of ob-jects can be represented and more problems can be solved. The generalizations still areorientation-based representations. Among the representations are the surface shape rep-resentation by Liang and Todhunter [45] and the complex EGI by Kang and Ikeuchi [40].The surface shape representation defined by Liang and Todhunter [45] is an extensionto the EGI in that smooth surfaces are considered and principal curvatures/directionsare recorded rather than Gaussian curvature alone. A vector function on the unit sphereis defined for each surface patch. The function value is the vector composed of themaximum principal curvature, the minimum principal curvature and the two componentsof the unit maximum principal curvature direction. An algorithm was proposed formatching surface shapes with strictly positive and strictly negative Gaussian curvatures.For general surface shapes, it was suggested that the surface shapes be partitioned intoregions with positive, negative and zero Gaussian curvature. Matching algorithms areintended. Problems arise, however, when surfaces contain holes even if the Gaussiancurvature is strictly positive. For example, in Figure 3.1, the representation of Liang andTodhunter is not well defined for the surface patch in the figure because there are points onthe surface patch whose normal directions are the same. The one-to-one correspondenceChapter 3. Previous Research^ 69Figure 3.1: An open surface patch with positive Gaussian curvature.between the sphere and the surface via normal vector is only guaranteed for regular closedconvex surfaces.The Complex Extended Gaussian Image (CEGI) defined by Kang and Ikeuchi [401associates a complex number to each normal vector. The magnitude of the complexnumber is the area of the face corresponding to the normal, and the phase of the complexnumber is the normal distance of that face to the origin. Thus, the CEGI is equivalentto the EGI augmented with the value of the support function at each normal. The ideacame from the observation that the EGI is translation invariant. The CEGI was used todetermine the translation parameters using a least-square technique. Suppose the objectis translated by (Sx, Sy, Sz). The method requires thatV(8x)2 (so (6z)2 < 7r .This requirement can be eliminated by making use of the properties of the supportfunction. Recall equality (2.1). If a set C is translated into C' by a vector a, the supportfunction of C' isH(C'; v) = H(C; v) + (a, v) .Let v1 , v2 , and v3 be three normal directions, d i and dT be the corresponding supportChapter 3. Previous Research^ 70function values before and after the translation. Then=^+ (a, v,) , i = 1, 2, 3 .Thus a is the solution of the equationid1 — diaT • (vi V2 V3) =^Ct2 - d2d — d333.3 Related RepresentationsExamples of related representations are Gaussian curvature and mean curvature repre-sented as functions defined on the image plane. The distinction between these functionsand the curvature functions studied in this dissertation is a technical one. Properties ofthese representations follow from differential geometry.Besl [5] proposed using Gaussian and mean curvature as \"visible-invariant surfacecharacteristics\" and used the signs of Gaussian curvature and mean curvature to defineeight visible-invariant HK-sign surface types. From this, a theory of image segmentationwas built. A wide variety of range images and intensity images were tested. This \"sign-of-curvature\" paradigm has been very influential in computational vision, particularly inthe area of viewpoint invariant surface segmentation (see, for example, Li [43]).There are many other representations that involve the use of surface curvature prop-erties. For a more thorough survey, see Besl [5, 6].Chapter 3. Previous Research^ 713.4 SummaryAmong the orientation-based representations, only the second area function for polytopeshas been utilized in computational vision [37, 47]. At the same time, a comprehensivecollection of mathematical results exists about all the representations described.Table 3.1 summarizes the current state of the art.Chapter 4 extends the state of art by solving the attitude determination problem innew ways using combinations of the support function, with the first curvature functionand the second curvature function and the radial function.Chapter 3. Previous Research^ 72Orientation-BasedRepresentationsUsedBeforeReconstruction AttitudeDeterminationH(P; 0 yesLittle [47]trivialTheorem 2.5doneLittle [47]H(C; ) no trivialTheorem 2.5done in Section 4.1g(C; 0 no trivialPage 24p(C;) yesSchudy et al [70]trivialvia g(C;)done in Section 4.2Fi(C; 0 no possibleTheorem 2.11done in Section 4.1F2 (C; ) no unknown done in Section 4.1Si(P;w) no possibleTheorem 2.51S2(P;w) yesLittle [47]doneLittle [47]doneLittle [47]Si (C; w) no possibleTheorem 2.49S2(C;w) no unknownTable 3.1: Use of orientation-based representations.Chapter 4Solutions to the Attitude Determination ProblemIn this chapter, the problem of attitude determination is defined and theoretical solutionsto attitude determination using orientation-based representations are provided. Thefollowing orientation-based representations are used:1. The support function;2. The first curvature function;3. The second curvature function;4. The radial function.For attitude determination, only objects in R3 are considered.Definition 4.1 Attitude determination is the problem of finding a rotation, R, such thatR(C1 ) and C2 are homothetic, where C1 is a known 3-D model and C2 is an instance ofC1 under an unknown rotation, translation and scaling.Section 4.1 uses the support function and the curvature functions to solve the attitudedetermination problem. Section 4.2 uses the radial function in attitude determination.73Chapter 4. Solutions to the Attitude Determination Problem^ 744.1 Attitude Determination by the Support Function and Cur-vature FunctionsThroughout, assume that C1 is a given object model defined in a standard coordinatesystem and that C2 is a measured instance of C 1 subject to unknown rotation, translationand scaling. Let R denote an arbitrary rotation. By Corollary 2.43,V(R(C1), C2, B3 ) ?_ VV(R(Ci), R(Ci), B3 ) V(C2, C2, B3) (4.1)with equality if and only if R(C1 ) and C2 are homothetic. Further, it is known thatV(C, C, B3 ) is equal to 1/3 the surface area of a convex body C. Surface area is in-variant under rotation. Therefore, V(R(Ci), R(C 1 ), B3 ) = V(Ci, Cl , B3 ) and the min-imum value of (4.1) is /V (C 1 , C1, B3 )V(C2, C2, B3 ), independent of R. Accordingly,V(R(C1), C2, B3) achieves this minimum if and only if R(C1 ) and C2 are homothetic.Similarly, by Corollary 2.38,V(R(Ci), C2, C2) \\3/1/(R(C1)) V2 (C2) (4.2)with equality if and only if R(C1 ) and C2 are homothetic. Volume is invariant under rota-tion. Therefore, V(R(C1)) = V(Ci) and the minimum value of (4.2) is 13/V(Ci ) V 2 (C2),independent of R. The left-hand side of inequality (4.2), V(R(C1 ), C2, C2), achieves thisminimum if and only if R(C 1 ) and C2 are homothetic. Now, define functions of R asfollows:CO(R) = V(R(Ci ), C2, B3) , (4.3)(R) V(R(C1), C2, C2) • (4.4)Functions y)(R) and 0(R) depend on C 1 and C2. They attain their known minima at Ro ifand only if Ro (Ci ) and C2 are homothetic. Therefore, by Definition 4.1, the 3-D attitudedetermination problem can be solved if the minima of (,o(R) or '(R) can be found. EitherChapter 4. Solutions to the Attitude Determination Problem^ 75of these minima is an equivalent solution to the 3-D attitude determination problem. Theglobal minimum of (,a(R) is 3/S(C1 )S(C2 ) and that of b(R) is /V(C1 ) V 2 (C2), both ofwhich are known independent of R. By the conditions of Corollary 2.43 and 2.38, theseglobal minima are unique, modulo any rotational symmetries that C 1 possesses.Thus the attitude determination problem can be expressed as one of the followingoptimization problems:minimize: c,o(R)subject to: R is a rotation ,minimize: 0(R)subject to: R is a rotation .A rotation, R, can be represented as a triple (0, 0, it) interpreted to mean a counter-clockwise rotation by angle 52 around unit vector (sinOcos0, sinOsinO, cos). When R isrepresented in this way, cp(R) and '(R) are functions of the three variables 0, 0, 52 ER3 and are written as cp(0, 0,52) and 0(0,0,9). Thus, the problem of 3-D attitudedetermination is transformed into two equivalent optimization problems:minimize: (10 (0, 0 , Q) ,^(0, 0 , n) E R3 ,(4.7)subject to: 0 < 0 < 7r,0<61 < 27r,0 Vv(c2 ', C2 ', B3 ) ,^(4.17)VV (R(C1)', R(C1 )', B3 )andV(R(C1) 1 7 C2 ' , C2') > ,/1/2(C2 1 ) ,^ (4.18)I/V(R(C1 )0with equality if and only if R(C1 )' and C2 ' are homothetic. The minimum values of(4.17) and (4.18) still are known independent of R. Thus functions of rotation, R, canbe defined as follows:c3(R) n, ^V(R(Ci)', C2 ', B3) VV(R(Ci )', R(C1)', B3 )(R) ° V (R(CI)' , C2 ', C2 ')1/V(R(Ci)')^•(4.19)(4.20)Chapter 4. Solutions to the Attitude Determination Problem^ 79However, neither R(C1 )' nor C2 ' is smooth and strictly convex so that the mixedvolumes involved in c,3(R) and (R) can not be computed using Equation (2.32). Instead,they can be computed using Equation (2.28).Let uz denote the vector (0,0,1), uR denote the normal of the plane that containsthe occluding boundary of R(C 1 ), S2- and 8 2+ denote the hemispheres corresponding toz < 0 and z > 0, respectively. The mixed volumes in functions c,23(R) and b(R) are^V(R(Ci )', C2 ', B3 )^-6-1 J H(R(C1 ); w)Fi (C2; w)dwfg2+ H(R(Ci )'; w)dSi (C2 '; co) ,^V(R(C0', R(Ci )' B3 )^H(R(Ci);‘,i)Fi(R(Ci);w)(103s2+ H(R(CO' ; w)dSi (R(Ci )'; w) ,V(R(Ci)', C2', C2')^152 H(R(C1); W)F2(C2; W)(1(4)H(R(C1) ' ; uz) • S2(C2 ' ; uz)V(R(C1 ) 1) =^.42 H(R(C1); C4))112(R(C1); w)dwH(R(C1) '; UR) S2(R(C1) 1 ; UR) •Thusis2- H ( R ( ) ; ) ( C2; w)dw + s 152+ H (R(C1 )' ; w )dSi ( CO(R) =fS2- H(R(C1); W)F1(R(C1); w)dw^f92+ H(R(C1)'; W)do91(R(Ci) f ; (4))1171) (R) = fs2- 11 (R(C1); w)F2(C2; w ) dw H(R(C1); nz) • S2(q; uz) iS2- H(R(C1); W)F2(R(C1); (.4))ck,; H(R(C1)'; uR) • S2(R(C1)'; uR)i lThe value of S2(C2'; uz ) does not depend on R. In fact, by Equation (2.24) and Theo-rem 2.46,S 2(C 2 ; uz) = —f w,F2 (C 2 ; w)dws2-where wz denotes the z component of w. The value of H(R(C1 )'; uz ) is non-negative.When R(C1 )' and C2 ' are homothetic, H(R(C1 )'; uz ) is zero and192+ H(R(Ci )'; w)dS1(C2';(.0 )Chapter 4. Solutions to the Attitude Determination Problem^ 801,52-1- H(R(Ci )'; w)d,51 (R(Ci)'; w) and H(R(Ci)'; uR) • S2(R(Ci )'; uR)are equal to a constant times the area of the region of C2 ' on the occluding plane.The planar regions of R(Ci )' and C2 ' introduce new area and mixed area terms intothe mixed volumes that, while slowly varying, do depend on R. Ignoring these termsaffects the accuracy of the mixed volumes V(R(Ci )', C2 ', B3 ), V(R(Ci )', R(Ci)', B3) andV(R(Ci )', C2 1 , C2 '). When these terms are ignored, the objective functions c23(R) and7,3(R) become the following functions:^(7)(R) =^it. fs2- H(R(Ci); w) Fi (C2; w) du; [s fs2- H(R(Ci); w) Fi(R(Ci); w) d.01 4 '^(R) —^31 fs2- H(R(Ci); w) F2(C2; (h)) do) [1 fs2- H(R(Ci); w) F2(R(Ci); w) dW] k .(4.21)(4.22)Minimizing C5(R) and '(R) only approximates the minimizing solutions to optimizationproblems (4.9) and (4.10). Even if perfect, minimizing (75(R) and 7k(R) does not solve theattitude determination problem, as defined in Definition 4.1, since part of the object isnever seen and therefore may not be matched correctly. It does solve the attitude deter-mination problem correctly to the extent possible, given the data available. Figure 4.2depicts two 2-D convex objects that match when viewed in the positive z direction butthat do not match over the whole unit circle.4.2 Attitude Determination by the Radial FunctionThe motivation to propose the use of the radial function in attitude determination isthat the radial function can be defined for starshaped sets. The radial function andthe distance function are one-to-one for compact starshaped sets, not just convex sets.Thus a class of shapes larger than the class of convex shapes considered in Section 4.1can be dealt with. Starshapedness is a natural step from convexity to non-convexity.Chapter 4. Solutions to the Attitude Determination Problem^ 81Figure 4.2: Two 2-D convex objects that do match when viewed in the positive z directionbut that do not match over the whole unit circle.Some existing mathematical results, see Breen [8, 9, 11] for example, can be exploited.This section provides solutions to the attitude determination problem using the radialfunction.Theorem 2.16 says that a compact starshaped set that has the origin in its kernelis convex if and only if its distance function is convex. This means that the distancefunction captures the starshapedness property. From Definition 2.6 and Definition 2.7,the radial function, p(C;), for a convex set C is the inverse of the distance function ofC. To make the radial function a good representation for starshaped sets, it must firstbe defined for starshaped sets. It is noted that Definition 2.7 of the radial function inSection 2.1.5 can be directly applied on any compact starshaped set without any change.The domain of the radial function can be extended to R3 from S 2 .Definition 4.2 The radial function of a starshaped set S in R3 is defined asp(S; x) sup{A > 01 Ax E^, for x E R3 \\ {0} .^(4.23)Chapter 4. Solutions to the Attitude Determination Problem^ 82Figure 4.3: A 2-D starshaped set and its radial function, defined for points, (u, v), on theunit circle.The radial function of a starshaped set depends on the choice of origin in the coor-dinate system. If the origin is not interior to the set, S, then the radial function is notdefined for every point x E R3 . Suppose S is a compact starshaped set in R 3 with origin,0, in the interior of its kernel, the radial function isp(S; x) = 11G11/114 , for x E R3 , x 0 (4.24)where G is the (unique) point of intersection of the ray Ox with the boundary of S.The radial function is positively homogeneous of degree minus one with respect to x.That is, p(S; Ax) = 1p(S; x), A > 0. Thus, representing the radial function over the unitsphere is sufficient to determine the function over the whole space, R 3 . Figure 4.3 showsa 2-D starshaped set and its radial function defined for points, (u, v), on the unit circle.The analytic expressions between the dashed lines define the radial function for pointson the unit circle, u 2 + v2 = 1, in the corresponding region.The properties of the radial function listed on page 28 also hold for starshaped sets.Chapter 4. Solutions to the Attitude Determination Problem^ 83(a) non-starshaped^(b) starshapedFigure 4.4: Two 2-D sets with the same radial function.In particular, the radial function is one-to-one for starshaped sets. The one-to-one prop-erty is no longer guaranteed for non-starshaped sets. Figure 4.4(a) shows a 2-D non-starshaped set that has the same radial function as the 2-D starshaped set shown inFigure 4.4(b).The dual mixed volume was defined in Section 2.5.6 using the radial function (Defi-nition 2.29) for convex bodies. Since the definition of the radial function is extended tostarshaped sets, Definition 2.29 of the dual mixed volume can be directly applied to anycompact starshaped set whose kernel contains the origin.Definition 4.3 Let 81 ,82 , S3 be compact starshaped sets in R 3 with the origin in theinterior of their kernels. Let p(Si ; x) denote the radial function of Si , i = 1, 2, 3. The dualmixed volume of Si, S2 S3 is defined asS2' s3) 0 152 p(s1 ; w),0(s2; w)p(s3; codw •^(4.25)The condition of Theorem 2.54 and hence Corollary 2.55 in Section 2.5.6 is that theChapter 4. Solutions to the Attitude Determination Problem^ 84objects involved in the dual mixed volumes be convex. Lutwak's proof of the theoremuses Holder's inequality for integrals (see Hardy [33] page 140). The essential requirementis that p(Si ; x), p(S2 ; x), p(S3 ; x) be non-negative, measurable on S 2 and not identicallyzero. The radial function p(S; x) of a compact starshaped set S with the origin in theinterior of its kernel satisfies these conditions. Thus Lutwak's result extends to starshapedsets:Theorem 4.1m_i17m(si, s2, s3)^fi v(si, • • • , S3-7TL,^, 1 < m^3 ,i=0 mwith equality if and only if S3_,Fi,^, S3 are all dilations of each other (with the originas the center of dilation).Corollary 4.2f73 (s1 , s2 , s3 ) < f/(si , Sl, si)17(s2, s2, s2 ) 1/(s3 , s3 , s3 ) ,with equality if and only if Si , S2, 53 are all dilations of each other (with the origin asthe center of dilation).Let Si and S2 be two starshaped sets with origin in the interior of their kernels.Suppose Si is the model defined in a standard coordinate system, S2 the sensed instanceof Si subject to unknown rotation, translation and scaling. Let R denote a rotation. ByCorollary 4.2,f/(R(S1), S2, S2) V V (R(S1), R(S1), R(S1))C/ 2 (S2, S2, S2) , (4.26)with equality if and only if R(S1), 52 are dilations of each other (with the origin as thecenter of dilation). Note that the dual mixed volume 17 (R(S1), R(S1 ), R(51)) is equalto f/(Si , Si, Si ) due to the rotation property (2.17) of the radial function. ThereforeChapter 4. Solutions to the Attitude Determination Problem^ 85the maximum value of (4.26) is known independent of R. Accordingly, V(R(S1), S2, 82)achieves this maximum if and only if R(S1 ) and S2 are homothetic. Now define x(R), afunction of rotation R, byX(R) ''.= f/(R(S1), S2, S2) = 31 is, p(R-i(si); w)p2(s2; w )dw . (4.27)Function x(R) depends on Si and 52. It reaches the known maximum if and only if R(S1 )and S2 are homothetic. By Definition 4.1, the attitude determination problem can besolved if the global maximal point of x(R) can be found. The global maximal points aresolutions to the attitude determination problem. In fact, the global maximum of x(R)is known to be #(Si , Si, S1)1/ 2 (S2, 52, 82). By the conditions of Corollary 4.2, theglobal maximum of x(R) is unique, modulo any rotational symmetries that S i possesses.Thus the attitude determination problem can be expressed as the following optimizationproblem:maximize: X (R)subject to: R is a rotation .(4.28)Representing a rotation by a triple (0, 0, SI) where this is taken to mean a counter-clockwise rotation by angle 52 around unit vector (sin0cos0, sin0sin0, cosq), the functionX(R) becomes x(0, 0, 9), a function of three variables that has domain R3 . The problemof attitude determination is then equivalent to the following constrained optimizationproblem:maximize:subject to:X(0, 0 , g) , (OA f2) E R3 ,0<0 a. A hyperplane H is said to support A if Hdoes not cut A and the distance between H and A is 0. When a hyperplane H thatsupports A is represented as H = {x E Rd ! (x, v) = a} such that (x, v) < a for allx E A, H is referred to as the support hyperplane of A with outward normal v.Appendix CSpherical HarmonicsThis appendix briefly introduces spherical harmonics. More on spherical harmonics canbe found in [51].Definition C.1 (MacRobert [51] page 69.) Any solution (Dm of Laplace's Equation72(11 520 5 20 5 2 0axe aye az2 = °which is homogeneous, of degree m, in x, y, z 1 is called a solid spherical harmonic ofdegree m.Definition C.2 (MacRobert [51] page 70.) Let x = p sin0cos0, y = p sin0sin6, z =p cos0. Let O m = pm m be a solid spherical harmonic of degree m, where kIf m is afunction of 0 and 0 alone. The functions W m, obtained by dividing O m by pm is called asurface spherical harmonic of degree m.A function Wm of 0 and 0 is a surface spherical harmonic of degree m if and only ifit satisfies the following equation ([51], page 70):1^ a 2m(m + 1)T^(sin0awm)^1 54fmm^sin0 ao^502^sin20 502^ = 0 .Let Pm (it) be the Legendre polynomial of degree m. (See [51], page 67, for definitions.)It is known that Pm (cos0) is a surface spherical harmonic of degree m. Expanding Pm (p)in powers of ,u, the Legendre polynomials of degrees up to 10 are listed in Table C.1 ([51],page 80).Let m and n be positive integers, n < m. LetPm,o(P)^Pm(it)Pm,n(p) = dn Pm ( IL), > 0 .un1 A function such that if each of the variables is replaced by A times the variable, A can be completelyfactored out of the function, is said to be homogeneous. The power of A which can be factored out ofthe function is called the degree of homogeneity of the function.159Appendix C. Spherical Harmonics^ 160Po(u)^1 ,Pi(it)^ti ,Nit)^43/22 — 1) ,2P3(1)^2(5113 — 3P) ,P4(P)^8 (35/24 — 30/2 2 + 3) ,1P5 (/2)^—8 (63/2 5 — 70/23 + 1511) ,1P6(1)^—16 (231/26 — 315/2 4 + 105/2 2 — 5) ,1NO^—16(429p7 — 693/25 + 315/23 — 35/2)1Ps(it)^i.---8 (6435/28 — 1201211 6 + 6930/24 —,1260/2 2 + 35) ,P9(11)1 (12155/29 — 25740/2 7 + 18018/2 5 — 4620/23 + 31511) ,1281Pio(P) (46189/2 19 — 109395/2 8 + 90090/2 6 — 30030/24 + 3465/2 2 — 63) .256Table C.1: The Legendre polynomials of degrees up to 10.LetTrn,n(it ) '=.. ( -1 )n ( 1 — /12 ) 4nPm,n(P) 'It is known ([51], page 121) that for arbitrary constants A and B,(Acos(nO) + Bsin(nO))Tm , n (cosq)is a surface spherical harmonic of degree m. It is also known ([51], page 125) that anysurface spherical harmonic kli m,(0, 0) of degree m can be expressed in the formmWm (cb, 0) = AoPm (cos0) + E [An cos(nO) + Bn sin(a)]T„,,,,,,(cos0) ,n=1where the A's and B's are constants.Let f(cb, 0) be a continuous function of cb and 0 defined on the sphere. It is known([51], page 131) that AO, 0) can be expanded in a seriesf (0,0) = > {Am Pm (coscb) + t [Am ,ncos(nO) + Bm ,n sin(n0)]Tni ,n (cos0)}m=-.ol^n=1Appendix C. Spherical Harmonics^ 161for 0 < 0 < 7r , 0 < 0 < 2r.For integers m and n, 0 < n < m, letUni ,„(0, 0) = cos(n0)sinn (0)Pm,n(cos0) ,Vm ,„(0,0) = sin(nO)sinn (4)Prn,n(cos0) .Figure C.1 shows all I Um ,„(0,0) I and I V,,,,,(0,0) I for m = 0,1,2,3. For any giveninteger M > 0 , and arbitrary constants An,,,,, Bm ,,, , 0 < n < m < M, a surface in threedimensional space can be constructed asx = p(cb, 0) sine cos0 ,y = p(cb, 0) sin0 sin° ,z = p(0, 0) cos0 ,where M mp(0, 0) = E E(Ammum,.(0, 0) + Bm ,,,V,,,,,(0, 0))m=O rt=0The reason for absolute value being taken is to guarantee the constructed surface isstarshaped.(b) U1,0(f) U2,1 (g) U2,2(e) U2,0 (h) V2,1(P) V3 ,3(m) U3,3 (n) V3,1 (o) V3, 2(d) V1,1(a) Uo,o (c) U1,1(j) U3, 0 (k) U3,1 (1) U3,2(i) V2,2Appendix C. Spherical Harmonics^ 162Figure C.1: Projections of I Um.,n(0, 0) I and I Vrn,n(0, 0) I, 0 < n < m,m = 0,1, 2,3, untoa plane that is perpendicular to (1,1,1)."@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "1993-05"@en ; edm:isShownAt "10.14288/1.0051427"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Computer Science"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Orientation-based representations of shape and attitude determination"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/1667"@en .