Orientation-Based Representations of Shape and Attitude Determination by YING LI B.Sc., Peking University, 1982 M.Sc., Peking University, 1985 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF COMPUTER SCIENCE We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA APRIL 1993 © YING LI, 1993 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Signature Department of Computer Science The University of British Columbia Vancouver, Canada Date Abstract 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-D attitude 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. ii Table of Contents Abstract^ ii List of Tables^ vii List of Figures^ x Acknowledgment^ xv 1 Introduction 1 2 Mathematical Background 8 2.1^Representations ^ 12 2.1.1 The Support Function ^ 14 2.1.2 The Normal Representation ^ 17 2.1.3 The Curvature Functions ^ 20 2.1.4 The Distance Function ^ 23 2.1.5 The Radial Function ^ 28 2.1.6 Cross Sectional Measure and Breadth ^ 29 2.1.7 The Area Function ^ 29 iii 2.2 Spherical Images ^ 31 2.3 Numbers Associated with A Set ^ 32 2.3.1 The Volume ^ 33 2.3.2 The Surface Area ^ 34 2.3.3 The Diameter and the Width ^ 34 2.4 2.5 2.6 Transformations ^ 35 2.4.1 Minkowski Vector Addition 35 2.4.2 Blaschke Addition 2.4.3 Polar Means ^ 39 2.4.4 The Projection Body ^ 40 2.4.5 Polar Set, Conjugate, and Legendre Transform ^ 41 ^ ^ 38 Mixed Measurements ^ 43 2.5.1 The Mixed Volumes ^ 44 2.5.2 The i-th Area Function ^ 49 2.5.3 The Mixed Area Functions ^ 54 2.5.4 The Mixed Curvature Function ^ 56 2.5.5 The Mixed Bodies 57 2.5.6 The Dual Mixed Volumes ^ ^ Summary ^ 58 60 iv 3 4 5 Previous Research 63 3.1 The Extended Gaussian Image ^ 64 3.2 Generalization of the EGI ^ 68 3.3 Related Representations ^ 70 3.4 Summary ^ 71 Solutions to the Attitude Determination Problem 73 4.1 Attitude Determination by the Support Function and Curvature Functions 74 4.2 Attitude Determination by the Radial Function ^ 80 4.3 Summary ^ 87 Experiments 90 5.1 Experimental Shapes ^ 91 5.2 Software Issues ^ 95 5.2.1^Optimization ^ 96 5.2.2^Integration and Differentiation ^ 97 5.2.3^Sphere Tessellation ^ 97 5.2.4^Interpolation 5.3 ^ 99 Experiments on Synthesized Data ^ 100 5.3.1^Experimental Settings 102 ^ 5.3.2^Experimental Results ^ 107 5.3.3 Variational Test ^ 5.4 Experiments on Real Data ^ 120 130 5.4.1 Experimental Settings ^ 130 5.4.2 Experimental Results ^ 135 5.5 Summary ^ 142 6 Conclusions^ 144 6.1 Contributions ^ 144 6.2 Future Directions ^ 147 Bibliography^ 149 Appendices^ 155 A Symbols Used in the Thesis^ 155 B Glossary^ 156 C Spherical Harmonics^ 159 vi List of Tables 2.1 Properties of orientation-based representations. ^62 3.1 Use of orientation-based representations. ^72 5.1 Root-mean square gradient estimation errors. ^ 100 5.2 Interpolation error for the 20-frequency geodesic dome. ^ 101 5.3 Interpolation error for the 40-frequency geodesic dome. ^ 101 5.4 The objective functions for group-1, group-2 and group-3 experiments. ^ 103 5.5 The objective functions for set-1 experiments. ^ 104 5.6 The objective functions for set-2 experiments. ^ 105 5.7 The objective functions for set-3 experiments. ^ 106 5.8 Results of set-1 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point ^ 110 5.9 Results of set-2 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point ^ 111 5.10 Results of set-3 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point ^ vii 112 5.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. ^ 113 5.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. ^ 113 5.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. ^ 114 5.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. ^ 114 5.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. ^ 115 5.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. ^ 115 5.17 Results of testing different sampling rates and hemisphere sampling: the number of initial guesses out of the 4096 initial guesses converging to the optimal point 122 5.18 Different choices of origin used in the experiments. ^ 122 5.19 Results of testing the different choice of origin: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. . 123 5.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 ^ 123 5.21 The comparison between the estimated a priori rotation for the ellipsoid and the rotations found by optimizations on real data. ^ 136 viii 5.22 The comparison between the estimated a priori rotation for the pillow and the rotations found by optimizations on real data ^ C.1 The Legendre polynomials of degrees up to 10 ^ ix 137 160 List of Figures 1.1 Mappings between surface points and points on the sphere, illustrated in 2-D. ^ 3 2.1 Interdependence of the subsections in Chapter 2 2.2 The support function of a convex polygon. 11 2.3 Two polygons with the same support function. 16 2.4 The distance function of a starshaped set. 24 2.5 Conjugate functions. ^ 42 3.1 An open surface patch with positive Gaussian curvature. ^ 69 4.1 Using the data on a hemisphere in optimization when the object is viewed from a single viewpoint. 4.2 ^ ^ ^ 4.4 78 Two 2-D convex objects that do match when viewed in the positive z direction but that do not match over the whole unit circle. 4.3 9 ^ 81 A 2-D starshaped set and its radial function, defined for points, (u, v), on the unit circle. ^ 82 Two 2-D sets with the same radial function. ^ 83 x 4.5 Two 2-D starshaped sets that match when viewed in the positive z direction but that do not match over the whole unit circle ^ 87 5.1 Experimental shape: the ellipsoid^ 93 5.2 The spherical coordinate system. ^ 94 5.3 Experimental shape: the peanut. It is a solid of revolution ^ 95 5.4 Experimental shape: the pillow ^ 95 5.5 An 8-frequency geodesic dome. ^ 98 5.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) ^ 108 5.7 Example of the results of set-1 experiments: Minimizing cp(R) for E3,5,9 with initial guess (0.1,1.4,1.3) under Boundl. ^ 116 5.8 Example of the results of set-1 experiments: Minimizing (R) for E3,5,9 with initial guess (0.1,1.4,1.3) under Boundl. ^ 116 5.9 Example of the results of set-1 experiments: Maximizing x(R) for the peanut with initial guess (0.1,1.4,1.3) under Boundl ^ 117 5.10 Example of the results of set-1 experiments: Maximizing x(R) for the pillow with initial guess (0.1,1.4,1.3) under Boundl. ^ 117 5.11 Example of the results of set-3 experiments: Minimizing co(R) for E3,5 9 , with initial guess (0.1, 4.2, 1.7) under Bound3. ^ 118 5.12 Example of the results of set-3 experiments: Minimizing (R) for E3,5,9 with initial guess (0.1,4.2,1.7) under Bound3. ^ 118 xi 5.13 Example of the results of set-3 experiments: Maximizing x(R) for the peanut with initial guess (0.1, 4.2, 1.7) under Bound3 ^ 119 5.14 Example of the results of set-3 experiments: Maximizing x(R) for the pillow with initial guess (0.1, 4.2, 1.7) under Bound3. ^ 119 5.15 Example of the results of variational tests: Minimizing cp(R) for E3,5,9 with initial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates. 124 5.16 Example of the results of variational tests: Minimizing 0(R) for E3,5 9 , with initial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates. 124 5.17 Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates 125 5.18 Example of the results of variational tests: Maximizing x(R) for the pillow with initial guess (0.1, 4.2, 1.7) using data sampled at different sampling rates 125 5.19 Example of the results of variational tests: Minimizing (p(R) for E3,5,9 with initial guess (0.1, 4.2, 1.7) using data sampled on half sphere ^ 126 5.20 Example of the results of variational tests: Minimizing 7b(R) for E3 5 9 , , with initial guess (0.1, 4.2, 1.7) using data sampled on half sphere ^ 126 5.21 Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1, 4.2, 1.7) using data sampled on half sphere. . . . . 127 5.22 Example of the results of variational tests: Maximizing x(R) for the pillow with initial guess (0.1, 4.2, 1.7) using data sampled on half sphere. . . . . 127 xii 5.23 Example of the results of variational tests: Maximizing X (R) for the peanut with initial guess (0.1, 4.2, 1.7) using data sampled with new origin T1 . •^128 5.24 Example of the results of variational tests: Maximizing X (R) for the peanut with initial guess (0.1, 4.2, 1.7) using data sampled with new origin T2 • • • 128 5.25 Example of the results of variational tests: Maximizing X (R) for the pillow with initial guess (0.1, 4.2, 1.7) using data sampled with new origin Ti• • • 129 5.26 Example of the results of variational tests: Maximizing X (R) for the pillow with initial guess (0.1, 4.2, 1.7) using data sampled with new origin T2 . . . 129 5.27 Example of the results of variational tests: Maximizing X (R) for the pillow with initial guess (0.1, 4.2, 1.7) using data sampled with new origin T3 . .^129 5.28 Images of the ellipsoid under three light sources ^ 131 5.29 Images of the peanut under three light sources. ^ 132 5.30 Images of the pillow under three light sources. ^ 133 5.31 Example of the results of real data experiments: Minimizing Co (R) for the ellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1) ^ 138 5.32 Example of the results of real data experiments: Minimizing TP(R) for the ellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1) ^ 139 5.33 Example of the results of real data experiments: Maximizing X(R) for the peanut imaged in Figure 5.29 with initial guess (0.1, 0.2, 0.1) ^ 140 5.34 Example of the results of real data experiments: Maximizing T(R) for the pillow imaged in Figure 5.30 with initial guess (0.1, 0.2, 0.1). ^ 141 C.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). ^ xiv 162 Acknowledgment I sincerely thank my supervisor Dr. Robert Woodham. I am very grateful for the supervision Dr. Woodham gave me over the whole period of my PhD program including taking courses, writing the thesis proposal, solving the proposed problem theoretically, doing experiments and proofreading this dissertation. I thank him for being a exemplary researcher and a considerate mentor. I also thank him for the constant encouragement I receive from him. I am grateful to the members of my supervisory committee, Dr. Andrew Adler, Dr. Uri Ascher, Dr. David Kirkpatrick and Dr. Jim Little for their supervision and contributions in discussions of my research. Many people helped to make this work possible. Richard Froese introduced the Legendre transformation to me. Felix Jaggi, Norman Goldstein and Herbert Kreyszig helped me to understand the paper by R. Schneider in German. Dr. Marilyn Breen provided papers on starshaped sets. Tom Nicol suggested using the optimization routine NLPQL and also helped to convert it for local use. Dr. Robert Renka provided the spherical interpolation routine and converted it to double precision for our use. Ian Cavers provided the integration routine QB01AD from Harwell. Rod Barman assisted in the preparation and mounting of the test objects. Stewart Kingdon provided essential software for image acquisition. Christopher Healey helped in formatting this thesis in Latex. I also thank Branislav Klco of Studio Apropos!, Vancouver, BC, for machining the test objects. I thank the following faculty and staff members at the Laboratory of Computational Intelligence: Rod Barman, Stewart Kingdon, Jim Little, David Lowe, Alan Mackworth, Valerie McRae, David Poole, Dan Razzell, Richard Rosenberg and Bob Woodham. The Lab has been a productive and comfortable working environment. I thank the staff members at the Department of Computer Science, particularly, Gale Arndt, Carlin Chao, Moyra Ditchfield, Evelyn Fong, George Phillips, Peter Phillips, Deborah Wilson, Carol Whitehead and Grace Wolkosky for their great help with various aspects of my being a graduate student in the department. I thank Jadranka Alilovic-Curgus, Carl Alphonce, Heinz Breu, John Buchanan, Atjeng Gunawan, Alex Kean, Yggy King, Geng Lin, Dan McReynolds, Jane Mulligan, Art Pope, Pierre Poulin, Runping Qi, Lianwen Zhang and Ying Zhang for their fellowship with me. Particularly, I thank Pierre Poulin for proofreading this dissertation. I thank Tracy Urban, Grace Wolkosky, Valerie McRae, Carly Wong, and Ellen Ho for being my dear friends in these years. I thank Carly Wong for helping formatting and proofreading this dissertation. I thank my husband, Chong-Jian Zhu, for loving me and respecting my academic pursuit. This thesis is affectionately dedicated to my mother Wu Zhi-Yong and my father Li Zhi-Chun whose love I can never repay. xv Chapter 1 Introduction Tasks that a robot vision system performs include recognition, localization and inspection. These tasks are carried out based on data about objects collected by a robot vision system through various sensing devices. Recognition identifies the object. Localization determines the three translational and the three rotational degrees of freedom of a sensed object in space. Inspection verifies the suitability of the object for a particular task. Attitude determination solves for the three rotational degrees of freedom between the coordinate system of a sensed object and that of a viewer. Thus, attitude determination is a sub-problem of localization. If the shape of an object is invariant with respect to a class of rotations then each rotation 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 particular viewpoint. In this case, it is understood that attitude determination solves for the three rotational degrees of freedom up to an equivalence class of rotations that can not be further distinguished given the viewpoint provided. Attitude determination is required for many robot vision tasks including directing a robot arm to grasp an object, navigation and camera calibration. Suppose a robot is placed, in a factory, beside a bin of machine parts all of the same type. The robot is instructed to grasp a machine part in a specified way. Each part has a 3-D shape that is known to the robot, i.e., the robot has a model of the part in a standard coordinate 1 Chapter I. Introduction^ 2 system. The parts the robot sees in the bin are instances of the model subject to unknown rotation, scaling and translation. The attitude determination problem for the robot is to determine the unknown rotation so that the robot can be directed to grasp a machine part in the specified way. Shape representations are required to support object recognition, localization and inspection. An object is a connected compact set in R3 . The shape of an object concerns the geometry of the surface of the object modulo translation, scaling and rotation. A representation of shape is a language for encoding a general class of shapes [75], together with rules that specify how it is applied to any particular shape [53]. Orientation-based representations of shape are shape representations with particular properties. The term "orientation-based representation" was introduced by Woodham [76]. An orientation-based representation records 3-D surface properties as a function of position on the unit sphere. These representations are termed orientation-based because one associates each point on the sphere with the unit vector from the center of the sphere to that point. This dissertation studies various orientation-based representations and solves the attitude determination problem by making use of the dependence of the orientation-based representations of shape on rotations. In order for an orientation-based representation to effectively represent the shape of an object, a correspondence between the surface point of an object and a point on the unit sphere is required. Two ways to establish such a correspondence are employed in this dissertation. They are called Gauss map and dilation map and are shown in Figure l.la and Figure 1.1b respectively. The Gauss map takes each surface point to the point on the sphere corresponding to the unit normal to the tangent plane at that point. Figure l.la illustrates the Gauss map. Chapter 1. Introduction^ (a) Gauss map ^ 3 (b) dilation map Figure 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 of this type used in computer vision include: the Extended Gaussian Image (EGI), defined as the reciprocal of the Gaussian curvature [35], and the support function, defined as the distance from the origin to the tangent plane [57]. For polyhedra, the EGI specifies the area of each face as a function of face orientation. The EGI has been used for both recognition and attitude determination of convex polyhedra [12, 37, 47]. The support function appears explicitly in one of the methods described [47]. Other representations of 3-D shape based on the Gauss map have been defined. For example, the first and second curvature functions are defined, respectively, as the sum of the 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. These curvature functions possess desirable mathematical properties when combined with the support 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 has proven difficult to extend representations based on the Gauss map beyond the convex Chapter 1. Introduction^ 4 case since, in general, the Gauss map is many-to-one. Approaches have been described to decompose non-convex surfaces into regions for which the Gauss map is one-to-one and to 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 correspondence between surface point and point on the sphere. Let the origin be in the interior of the object. Without loss of generality, assume that the size of the object is large enough so that the unit sphere fits entirely within the object. A surface point p is mapped the point 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 of origin, 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. The radial function records the distance from the origin to the boundary point. The distance function is the reciprocal of the radial function. The two aforementioned mappings between the surface point and point on the sphere both lead to a desirable property that all the orientation-based representations considered share: the representation of a rotated object is equal to the rotated representation of the object before rotation. This facilitates the construction of the representation of a rotated object from that of the original object. This property also makes orientation-based representations suitable for attitude determination. Using inequalities involving two objects, one for the model and the other for the sensed surface data, one can define functions of rotation that achieve extrema when the rotation is such that the rotated model and the sensed object differ only by scaling and translation. Thus, attitude determination is transformed 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^ 5 Chapter 2 establishes a consistent framework for orientation-based representations of shape. A mathematical definition of orientation-based representation and the mathematical background for orientation-based representations are provided. Definitions of various orientation-based representations are given and their properties are studied. The emphasis 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 orientationbased 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 representations 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 presentation in Chapter 2 of the mathematical background for orientation-based representations is a contribution of this dissertation. In addition to being the theoretical foundation of this dissertation, these results are relevant to research in other areas. For example, the Minkowski sum (Section 2.4.1) is used both in geometric object modeling [17] and in robotics [48]. On first reading of the thesis Chapter 2 might well be skipped. Results are presented in general d-dimensional space Rd to preserve the original generality of the mathematics and to connect the special case d = 3 to the generic meaning of the representations. As mentioned, a few orientation-based representations have already been proposed and utilized in computational vision. Overall, however, little of the material presented in Chapter 2 has been utilized. Objects represented typically are limited to polytopes and to some special non-convex objects [35]. The state of the art is presented in Chapter 3 and highlighted in Table 3.1 (page 72). Chapter 1. Introduction^ 6 Chapter 4 provides theoretical solutions to the problem of attitude determination using orientation-based representations. The results in Chapter 2 on inequalities involving orientation-based representations are utilized. By combining the representation of a model and that of an object in the inequalities, the attitude determination problem is transformed into optimization problems for which standard numerical methods can be applied. Indeed, optimization itself is not an intended contribution of the thesis research. Instead, existing optimization tools are employed throughout. The orientationbased 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 is new. 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 defined for any convex object. Thus, the use of the curvature functions can be regarded as an application 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 and mean curvatures. Since the support function is one-to-one only for convex bodies and the curvature functions are only defined for convex bodies, attitude determination using them is, in general, not necessarily valid for non-convex bodies. A major contribution of this dissertation is to demonstrate that the radial function is an effective representation for starshaped objects l and that the attitude of starshaped objects can be determined using the radial function. Thus the class of objects handled is extended to starshaped objects (which strictly includes convex objects as a special case). A proof-of-concept system has been implemented and experiments conducted to test numerical solutions for three cases: 1. Attitude determination when both the model and sensed surface are given in known analytic form; 1 See Appendix B for definition of starshaped objects. Chapter I. Introduction^ 7 2. Attitude determination when the sensed surface, then the model and then both are discretized versions of a known analytic form; 3. Attitude determination with sensed data obtained, via photometric stereo, from real 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 on real objects machined from data derived from analytic forms. Experimental results show that attitude determination can be solved by the aforementioned orientation-based representations of shape. The system and the experiments are described in Chapter 5. Chapter 6 summarizes the contributions of this dissertation and points out future directions for research. Appendix A and Appendix B describe notational conventions and basic definitions used. Appendix C provides a brief introduction to spherical harmonics which are used in Chapter 5 to define the experimental shapes. Chapter 2 Mathematical Background Orientation-based representations are functions defined on the unit sphere or set functions defined on sets of the unit sphere. The representations considered in this dissertation are based on the two mappings from an object to the unit sphere described in Figure 1.1 of Chapter 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 determination problem, deeper mathematical background is needed. The orientation-based representations considered in this dissertation are described in the mathematics literature. However, the source material is diverse both in time and in language. This chapter gives a coherent presentation of the mathematical background for orientation-based representations. Results are presented in general d-dimensional space Rd to preserve the original generality of the mathematics and to connect the special case d = 3 to the generic 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 that establish the background for orientation-based representations of shape. Each of these sections is further divided into subsections where one mathematical object of the type of the section is presented. Figure 2.1 depicts the interdependence between the subsections of this chapter, where subsections directly related to attitude determination in this dissertation are emphasized. The last section of this chapter, Section 2.6, summarizes the 8 Chapter 2. Mathematical Background ^ 2.1.2 normal 2.1.4 distance function representation 2.1.3 curvature functions -r 2.1.1 support function 2.1.5 radial function 2.1.6 brightness and breadth 2.1.7 area function 2.2 spherical image IM =MI =IN V 2.3.1 volume 2 3.2 surface area V 2.4.2 Blaschke addition 2.4.1 Minkowski addition 9 2.4 3 polar means 2.4.4 projection body 2.4.5 Legendre transform 2 5.1 mixed volume Corollary 2.38 Corollary 2.43 2.5.2 i-th area function 2.5.4 mixed curvature function 2.5 3 mixed area function 2.5.6 dual mixed volume heorem 2.54 2.5.5 mixed bodies Legend: A is used in attitude determination A I A^B B depends on A - B B is related to A Figure 2.1: Interdependence of the subsections in Chapter 2. Chapter 2. Mathematical Background^ 10 properties 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 considered are: 1. Functions that are associated with one set and whose domains are R d , S d-1 or B(S d-1 ) (Section 2.1). Functions in this category are the support function, the normal representation, the curvature functions, the distance function, the radial function, the cross sectional measure and the breadth and the area functions. These functions define orientationbased 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) are the orientation-based representations used in attitude determination (Chapter 4 and Chapter 5) in this dissertation. All the functions are defined on Sd -1 except the area function which is defined on /3(S d-1 ). The introduction of the a-algebra of Borel subsets of S d-1 , B(Sd -1 ), provides a way of stating the properties of the area function since the area function is a set function. To give an example of orientation-based representations, consider the support function of a 2-D polygon, P. For a point u on the unit circle, the value of the support function of P at u is the maximal signed distance between the origin and the support plane of P with outer normal u. Figure 2.2 shows the 2-D example of a convex polygon and its support function defined for vectors u E 5 1 . The value of the support function is the distance between the origin and the dashed arc along the direction determined by u. 2. Mappings from one hypersurface to sets on S d-1 (Section 2.2). Chapter 2. Mathematical Background^ 11 Figure 2.2: The support function of a convex polygon. The spherical image is in this category. Although it is not an orientation-based representation, 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 be calculated 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 achieved by constructing the representation of a new set from the orientation-based representations of some given sets. The constructions make use of the properties of orientation-based representations defined in Section 2.1. Typically, the properties of the transformed set are of more interest than the transformation itself. Transformed sets are the (Minkowski) vector sum, the Blaschke sum, the polar mean, the polar reciprocal set, the Legendre transform, the projection body, the parallel body and the central body. 5. Functions and mappings obtained via combinations of a set with the unit ball B d or combinations of several sets (Section 2.5). Chapter 2. Mathematical Background^ 12 Their names are usually prefixed with "i-th" or "mixed" depending on whether the 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, the mixed area function, the i-th curvature function, the mixed curvature function, the mixed body and the dual mixed volume. Among them, the i-th curvature function and the mixed curvature function are orientation-based representations, the mixed volume and the dual mixed volume are scalar values, the i-th area function and the mixed area function are set functions, and the mixed body is a set. The theorems 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 determination problem (Chapter 4). The mathematical constructions have been studied intensively in the context of convex bodies. Some of them are only meaningful when applied on convex bodies. Possibilities to extend functions and mappings to non-convex sets are discussed. References to the mathematical results are provided but the original proofs are not repeated. General references are Bonnesen and Fenchel [7], Busemann [15], Griinbaum [32], Pogorelov [60] and Schneider [69]. Notation, definitions and facts used but not defined in this chapter are given in Appendix A and Appendix B. 2.1 Representations Definition 2.1 An orientation-based representation of shape is a map from connected compact sets in Rd to functions defined on the unit sphere S d-1 in Rd or set functions defined 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 unit Chapter 2. Mathematical Background^ 13 sphere is the maximal signed distance (from an origin) to the tangent plane with outer normal u. This mapping from objects to functions defined on the unit sphere conforms to Definition 2.1 and thus is an orientation-based representation of shape. The name of the mapped function, the support function, also is used to name the representation. An orientation-based representation represents the shape of an object via a correspondence between points on the unit sphere and points on the object surface. Two ways of establishing such a correspondence, the Gauss map and the dilation map, are depicted in Figure 1.1. The Gauss map takes each surface point to the point on the sphere corresponding to the unit normal to the tangent plane at that point. The dilation map takes a surface point p to the point on the unit sphere that is the intersection of the sphere with the ray from the origin to p. Representations based on the Gauss map come with useful mathematical properties. However, many of these properties require the correspondence to be one-to-one. This restricts the representation to strictly convex objects since the one-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 boundary points, then its boundary can be mapped one-to-one and continuously onto Sd -1 by means of equally directed support planes. By the definition of starshaped set, correspondence via the dilation map is one-to-one for starshaped objects when the origin is inside the kernel of the object. The class of starshaped objects strictly includes the class of convex bodies. The mathematical study of starshaped objects is not as extensive as that of convex bodies. Representations studied in the following subsections are the support function, the normal representation, the curvature functions, the distance function, the radial function, the cross sectional measure, the breadth and the area functions. Definitions are given and the relations between the representations are described once sufficient background is Chapter 2. Mathematical Background ^ 14 established. 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 Function Definition 2.2 (Lay [42] 29.1 page 206.) Let C C Rd be a nonempty set. The support function H(C; v) of C is the real-valued function defined by H (C; v) = sup {(x, v) 1 x E Cl , for all v E R d for which the supremum is finite. It is obvious that the support function of a set depends on the choice of the origin of the coordinate system. If a set C is translated into C' by a vector a, the support function of C' is H (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 R d \ {O} is (x, v) = H(C; v). If v E Sd -1 , the value H (C ; v) is the signed distance from the origin to the support plane of C with outer normal v. If C is non-convex, then (x, v) = H(C; v) Chapter 2. Mathematical Background^ 15 is the support plane of C with outer normal v that is of maximum signed distance from the origin. Examples of support functions are: 1. The support function of a point is a linear function. The support function of a polytope 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 axes with 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 a nonempty set C is positively homogeneous and convex. That is, it satisfies 1. H(C; Av) .H(C; v)^for all A > 0, v E R d , 2. H (C ; v w) H (C ;^H (C ;^for all v, w E R d . Positive homogeneity and convexity are also sufficient for a function to be the support function of a convex set. Theorem 2.3 (Bonnesen-Fenchel [7] page 29.) If H(v) is any function defined on R d such that 1. H(Av) AH(v)^for all A > 0, v E Rd , 2. H(v w) < H(v) H(w)^for all v, w E R d , then there exists a nonempty closed convex set C such that H(v) is the support function H(C; v) of C. Chapter 2. Mathematical Background ^ 16 Figure 2.3: Two polygons with the same support function. Support functions are defined for any nonempty set. However, only for convex sets is the support function one-to-one. Theorem 2.4 (Grfinbaum [32] page 14.) If C1 , C2 are nonempty closed convex sets in R d such that H(C i ; v) = H(C2 ; v) for every v E R d , then C 1 = 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 convex while the right one is not. The support functions are the same because the convex hulls of 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 the condition C = {x I (x,v) 5_ H(C;v) for all v E D} , or, equivalently nI C^ x veD I ( x,v 5 H(C; v)} . ) Chapter 2. Mathematical Background^ 17 Theorem 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 R d if and only if C 1 C C2 . The next theorem gives the coordinates of the boundary points of a convex body via the support function of the convex body. Theorem 2.7 (Bonnesen-Fenchel [7] page 29.) If a convex body C has only regular support planes, then its support function H(C; v) has continuous partial derivatives of the first order, and OH(C; u) x, —^u E S d-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 Representation Definition 2.3 (Firey [21] page 1.) Let C be a convex body having only regular support hyperplanes, u E S d-1 , and let x(C; u) be the point on the boundary of C at which the unit outer normal is u. Function x is called the normal representation of the boundary of C. Because of the one-to-one correspondence between the sphere and the surface of a regular convex body via directions of support planes, as stated in Theorem 2.1, the normal 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} by x(C; v) = x(C; v /11 v (I), v E R d \{O}. The necessary and sufficient conditions for a con- tinuously differentiable function to be the normal representation of the boundary of a convex body is given by Firey [21]. Chapter 2. Mathematical Background^ 18 Theorem 2.8 (Firey [21j page 3.) In order that x(v), assumed to be continuously differentiable, be the normal representation of the boundary of a non-degenerate convex body with regular support planes, it is necessary and sufficient that, when extended to be defined over Rd\{0}, its Jacobi matrix axi(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, then H(C; v) = (v, x(C; v)) ,^ and by Theorem 2.7 aH (C ; v) xi(C; = ^ (2.4) (2.5) If x(C; v) is continuously differentiable, then H(C; v) is twice continuously differentiable, and a2H(c ; v)ax i (c ; v)^ax i (c ; v) avi avi^avi^avi Thus the Hessian matrix of the support function H(C; v) (a 2 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 the radii of principal curvature and the support function of a convex body. To show this, introduce parameters cr i , a 2 , , ce d _ i on the unit sphere S" such that the coordinates of 19 Chapter 2. Mathematical Background^ the points u of the unit sphere are analytic functions u(cr i ,^, a d _ i ), and the parameters are such indexed that ^au^ I det^au au^> 0 . act i (9a 2^aad-i Let C be a convex body with regular support planes. Then x(C; v) can be obtained as a function x(a i ,^, ad_ i ) of the parameters. If the origin is assumed to be in int C, then det [x^ ax aal 0a2 • aad_i > . Differentiating (2.5) gives ax •^aV E^a^ aai^j=i •^ a2 H , where H, 3 — ^ . (/ VI CI V.7 If dx and v are parallel to the directions of principal curvature and r is the associated radius of principal curvature, then dx = rdv. Thus, d E rdvi, i = 1,2, ... ,d . Therefore the radii of principal curvature must satisfy the equation H11 — r • •^Hid .0 Hdl^' • Hdd — (2.6) ,^ r which can be expanded into l rd Di (H)rd-1 D2(H)rd-2 .^ Dd_i(H)r (_ o dp d(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) = 1 8118(vC;v) is homogeneous of By Theorem 27.1 in Browne [14] (page 68), for a n-square matrix A with elements in a field .T, A —^j= Enm .o^, where cm is the sum of all the rn-rowed principal minor determinants of A, co = 1, o- 7, =I A I Chapter 2. Mathematical Background^ 20 degree 0 in v, then by Euler's Theorem, d EHi j 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, .. • r d-1 — D1(H)r d-2 D 2 (H)r d - 3 + • • • + ( - 1) d 1 D d _ i (H) = 0 .^(2.8) - Therefore the radii of principal curvature r i (u),i^1,^, d — 1, at x(u), are the solutions to equation (2.8). Thus the radii of principal curvature together with zero are the eigenvalues of the Hessian matrix of H. From (2.8), Di(H) is also the i-th elementary symmetric function {n. • • • ri} of r 1 , ...,rd_ i . In particular, the sum of the radii of principal curvature at x(u) is the trace of the Hessian matrix of H, i.e., AH(u) = r i (u) -+ r 2 (u) -F • • • + rd_ i (u), u E S d-1 .^(2.9) Furthermore (H) = r i (u)r 2 (u)• • • rd_ i (u), u E S d-1 (2.10) is the product of the radii of principal curvature and is therefore the reciprocal of the Gaussian curvature. 2.1.3 The Curvature Functions Definition 2.4 (Bonnesen-Fenchel [7] page 121.) Let C be a convex body, H(C; v) be its support function. Let Di(H) be the sum of all i-rowed principal minor determinants of the matrix (Hid), where H3 = a a:a . Define Fi(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^ 21 Since 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)r 2 (C; u) • • • r d _ i (C; u) . When d = 3, a convex body has two curvature functions, F 1 and F2, which are the sum of the radii of principal curvature and the reciprocal of the Gaussian curvature, respectively. Theorem 2.9 (Bonnesen-Fenchel [7] page 121.) sd -1 wFi(C; ce)cice = 0 . if This theorem says that a necessary condition for a function defined on Sd (2.13) -1 to be the curvature function of a convex body is that the centroid of the surface on the unit sphere covered with mass density Fi is the center of the sphere. This also is a sufficient condition for 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 continuous function on the unit sphere that satisfies the relation fsd-iwF(w)&4., = 0 . Then there exists a convex body uniquely determined up to translation for which F is the curvature function Fd_1. Theorem 2.9 and Theorem 2.10 together give a necessary and sufficient condition for a positive continuous function Fd_ 1 on S d-1 to be the curvature function Fd _ i (C; u) of Chapter 2. Mathematical Background^ 22 a convex body C. The existence problem of a closed convex surface C such that the sum of the radii of principal curvature at a point with unit outward normal vector u is a given function 0(u) defined on S' is called Christoffel's problem. The problem has been studied by quite a few mathematicians, including Christoffel himself. A recent solution to the existence problem is the constructive proof by Firey [21], which Firey claims corrects and complements the incomplete treatment to the problem by earlier researchers. Theorem 2.11 (Firey [21] page 9.) Let 0 be a continuously differentiable function over Sd -1 . There exists a non-degenerate convex body C with regular support hyperplanes such that 0(u) is the sum of the principal radii of curvature at that boundary point of C at which u is the outer normal if and only if 0 satisfies the following conditions. Let O(u', u) = [1 _ ( til, u )211-(1-d) f are cos(u',u) ^sins-2t dt , cod^fir then u 19d- 1 o( u ) dw ( u ) . 0 , (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 up to a translation. Theorem 2.12 (Bonnesen-Fenchel [7] page 122.) Two convex bodies with interior points and 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^ 23 The definition and the theorems of this section assume that the support function of the convex body has second derivatives. This is only necessary when the curvature functions are defined via Di(H). The assumption can be dropped if the curvature functions are defined by mixed volumes as will be described in Section 2.5.1. 2.1.4 The Distance Function Definition 2.5 (Bonnesen-Fenchel [7] page 23.) Let C be a convex body with interior points. Suppose the origin 0 is chosen in the interior of C. For any x E R d \{O}, let G be the (unique) intersection point of the ray Ox with bd C. The distance function g(C; x), x E R d , of C is defined as 1. g(C; 0) = 0, and 2. g(C; x)^11x11/1111, x E R d \ {O}. The distance function of a set depends on the choice of the origin of the coordinate system. If a set C is rotated by a rotation R, its distance function is also rotated by the same 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 is unknown. 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 length two and centered at the origin is max{Ix i l I 1 < i < Chapter 2. Mathematical Background^ 24 Figure 2.4: The distance function of a starshaped set. 3. The distance function of the d-dimensional analogue of the regular octahedron is i ixil; 4. The distance function of a starshaped polygon is shown in Figure 2.4. The analytic expressions between the dashed lines define the distance function for points on the unit circle, u 2^= 1, in the corresponding region. The following observations regarding the distance function follow from its definition: 1. The points that satisfy the inequality g(C; x) < 1 are precisely the points of C; 2. If two convex sets with 0 as their common interior point have the same distance function, the two must be the same; 3. If the distance function of C is g(C; x), that of AC is I ^x); Chapter 2. Mathematical Background^ 25 4. (Firey [19] page 444.) For convex sets C 1 and C2, g(C1; X)^g(C2; X), VX C R d if and only if C 1 C C2. Theorem 2.14 (Bonnesen-Fenchel [7] page 23.) The distance function, g(C; x), of a convex set C has the following properties : 1. g(C; x) 0^ with equality if and only if x = 0, 2. g(C; fix) = Ag(C; x)^for all ,u, > 0, x E R d , 3. g(C; x y) 5 g(C; x) g(C; y)^for all x, y E R d . Theorem 2.15 (Bonnesen-Fenchel [7] page 24.) If g(x) is any function defined on Rd such that 1. g(x)^0 with equality if and only if x = 0, 2. g(itx) = pg(x) for all ,u > 0, x E R d , 3. g(x y) C s(x) + g(Y) for all x, y E R d , then there exists a nonempty closed convex set C such that g(x) is the distance function of C. Sometimes the distance function is called gauge. In topology d(x, y) g(C; y — x) is a 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, to compact starshaped sets with origin in the interior of the kernel, since any ray Ox intersects a compact starshaped set only once. Properties 1 to 4 still hold for starshaped sets. Of particular interest is the one-to-one property. Recall that the support function Chapter 2. Mathematical Background ^ 26 is one-to-one only for convex sets. The distance function is one-to-one for starshaped sets. This is significant because the class of starshaped objects strictly includes that of convex 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, starshaped with respect to the origin 0. The generalized distance function of S is the function g: £ [0, oo] defined by g(x) = inf P ti > 0 , xE).S}.^ (2.15) From this definition of the distance function, a result that is stronger than both Theorem 2.14 and Theorem 2.15 follows. Theorem 2.16 (Valentine [72] page 32.) Suppose S Cr is starshaped with respect to 0 and each line through 0 intersects S in a relatively closed set. Then S is convex if and only 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 E The 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 distance function of starshaped sets. He believed that the distance function is intrinsically Chapter 2. Mathematical Background^ 27 related to starshaped set. It is stated in his paper that if g is the distance function of a nontrivial closed set starshaped with respect to an origin, 0, then g is a nonnegative extended valued positively homogeneous lower-semicontinuous function and there exists x o 0 satisfying g(x 0 ) oo. Conversely, any function g with these properties is the distance function of such a set, namely, S = {x : g(x) < 1}. If 0 E int ker S, then the distance function is continuous. Moreover, it is Lipschitz (see Appendix B). Beer studied the distance function of parallel bodies of starshaped sets. One of his theorems is as follows. Theorem 2.17 (Beer [4] page 24.) Let {Sc} be a sequence of compact starshaped sets each contained in {x E R d : ilx11 < M}. Then {Sc} has a subsequence convergent in the Hausdorff metric to a compact starshaped set. In the study of classes of starshaped sets in R3 , Melzak [55] asserted that the class of starshaped sets is identifiable with the class of all real valued positive functions on the sphere S 2 which satisfy a Lipschitz condition. Define 7-1 as follows: S Eli if and only if S is a bounded closed set in R3 and 0 E int ker S. Let g(S; v) be the distance function of S. The following theorems were obtained where Theorem 2.18 was mentioned similarly in 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 u 2 1 is the length of the line segment between u 1 and u 2 . Conversely, any such function g defines a set in 7-1. Theorem 2.19 (Melzak [55] pages 175-176.) Given any convex set A > 0 such that C C AB', and any e > 0, there exists S E 7-1 such that 1. ker S = C; C E 7-t, any Chapter 2. Mathematical Background^ 28 2. C C int S; 3. AB 3 c S c (A + 6)B 3 . 2.1.5 The Radial Function The 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 is defined as ^p(C; u) sup{A > 0 Au E^, for u E 8 d-1 .^(2.16) From 2.15 and 2.16 it can be seen that 1 p(C; u) = g(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 from Definition 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 radial function, 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 R d if and only if C 1 C C2) Chapter 2. Mathematical Background ^ 29 2.1.6 Cross Sectional Measure and Breadth Definition 2.8 (Bonnesen-Fenchel [7] page 49.) Let C be a convex body and v an arbitrary direction. The (d — 1)-dimensional volume of the orthogonal projection of C onto a hyperplane with normal direction v is called the (d — 1)-dimensional cross sectional measure of C in the direction v, denoted as o(C; v). For d = 3, o-(C; v) is called the brightness function of C, i.e., the area of the orthogonal projection of C onto a plane with normal direction v. (Firey [20] page 96.) Theorem 2.20 (Firey [20] page 96.) If two centrally symmetric convex bodies have the same 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 an arbitrary direction. The distance between the two support planes of a convex body C with normal direction v is called the breadth of C in the direction v, and is denoted as B(C; v), for all directions v. A convex body is called a body of constant breadth if it has the 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 Function Definition 2.10 (Firey [24] page 205.) Let C be a convex body in Rd, S2 E B(S d 1 ). - Denote, by S(C; 9), the (d-1)-content (area when d = 3) of the set of all those boundary points of C, each of which has a support hyperplane with outward normal in a Set function S(C; C2) is called the area function (or primary area function by Firey) of C. Chapter 2. Mathematical Background^ 30 Theorem 2.21 (Schneider [69] page 47.) For convex body C, is d-1 wdS(C; w) = 0 . Theorem 2.22 (Schneider [69] page 47.) Let /./ be a positive measure on B(S d-1 ) not concentrated on a great circle, and suppose that is d-1 wel kw) = 0 . Then 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-zero vectors in Rd is called equilibrated if E: _ i vi = 0 and no two of the vectors in V are 1 positively proportional. V is called fully equilibrated in R d when it is equilibrated and spans R d . 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 a k-polytope, then A(P) is fully equilibrated in the subspace R k parallel to the affine space spanned by P. (2) If V is a fully equilibrated system in R k , k > 2, there exists a polytope P, unique within a translation, such that V = A(P). Chapter 2. Mathematical Background ^ 31 The brightness function (Section 2.1.6) cs(C; v) of C can be expressed in terms of the area function S(C; S2) of C (Firey [20]): o(C; v) = J. ^(v, u) 1 dS(C; u) .^ (2.18) 2.2 Spherical Images Definition 2.12 (Busemann [15] page 25.) Consider a convex hypersurface C. The spherical image v'(p) of a point p E C consists of the points of Sd -1 which, as vectors, are the outward normals of the support hyperplanes of C at p. The spherical image v'(M) of a set M C C is v'(M) =U v'(p) • pEM Note that spherical images are not defined for non-convex hypersurfaces, because the support 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) is measurable, the integral curvature of M is defined as v(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 completely additive on 8(C). Chapter 2. Mathematical Background^ 32 Theorem 2.26 (Alexandrov, Busemann [15] page 29.) For a given completely additive non-negative set function a(M') defined for all M' E 13(S") there exists a closed convex hypersurface C containing origin 0 in its interior such that a(M') = v(M) for the projection M of M' from 0 on 1. a(Sd- 1 = wd ) 2. a(C) < wd — C, if and only if (wd is the area of S d-1 , see Appendix A.) for every convex set C on S d-1 , where /3 is the measure of the spherical image of the cone projecting C from 0 . Theorem 2.2'T (Busemann [15] page 30.) Let C 1 and C2 be two closed convex hypersurfaces 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 C i by a dilation with center 0 . 2.3 Numbers Associated with A Set The 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 representations defined in Section 2.1. Throughout this section, boundary of C is a convex body, x is the normal representation of the C, a 1 , a 2 , , 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 S d-1 at u. We have (BonnesenFenchel [7] page 64) au au 1 dhy = det^ da l • • • dad--1 • aa i^aad_i Chapter 2. Mathematical Background 33 2.3.1 The Volume Let 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(p i ) the area of p i , by ui the unit outer normal of the support plane of P containing pi. It can be proved (Busemann [15] page 44) that 1N V (P) = - H(P;u i )A(p i ). d (2.19) A limit process of (2.19) gives V (C) 1 d f sd_i H(C; w)dS(C;ci..,) . When H (C ; v) has continuous second derivatives, dS(C; u) = Fd _ l (C; u)dw Thus 1 V (C)^I H(C;co)Fd_ i (C;^. Representing V(C) in terms of the chosen coordinate system gives ax^ax V(C) =1 f det x aai aad-i da l • • • dad-i 1^ax^ax det aai aad_i H(C; u)da i • • • dad 1 fsd _ i det u a au ai acvadu_ii 1 H(C; u)Dd-i (H)(u)dai • • • dad-i Chapter 2. Mathematical Background^ 34 2.3.2 The Surface Area Let (C) denote the surface area of a convex body C and S(C; SI) denote the area function 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 det [u ax S(C) = f sd-1 ^ da i • • • dad-i • Given the (d — 1)-dimensional cross sectional measure o- (C; v) of convex body C, the surface area S(C; S' 1 ) of C can be computed via Cauchy's formula (Bonnesen-Fenchel [7] page 53) S(C; S d-1 ) = 1^o-(C; isd-1 w)dw 2.3.3 The Diameter and the Width Definition 2.14 The maximum of B(C; v) over all v is called the diameter of C, denoted as D(C). The minimum of B(C; v) over v is called the width of C, and is denoted as A(C). Obviously, the diameter of a convex body of constant breadth is equal to its width. Chapter 2. Mathematical Background^ 35 2.4 Transformations There are two types of transformations described in this section. Transformations of the first type combine two sets into a new one. The new sets are determined by their orientation-based representations which are the sum of the orientation-based representations 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 transformed set. 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 that R i (T(S)) = R 2 (S) where R1, R2 are two orientation-based representations of shape and T(S) is the transformed set. Projection body and polar reciprocal set are of this type. 2.4.1 Minkowski Vector Addition Definition 2.15 (Griinbaum [32] page 316.) For two sets Q and R in Rd, the vector sum Q + R of Q and R is defined as Q+R={x+y1xEQ,yER}. If P = Q + R, then Q and R are called summands of P. The process is called vector addition. Associated with the vector addition is a scalar multiplication AQ defined as AQ = {Ax 1 x E Q}. The set {a} + AQ, a E R d , is said to be homothetic to Q, and positively homothetic to Q if A > 0. Chapter 2. Mathematical Background^ 36 Theorem 2.28 (Griinbaum [32] page 316.) (1) A set P is the vector sum of Q and R if and only if H(P; v) = H(Q; v) H(R; v), for all v E R d . (2) Let Q and R be two polytopes, qi , i = 1, . , n and ri , j = 1, . , m, be the vertices of Q and R, respectively. A set P is the vector sum of Q and R if and only if P is the convex hull of the set f qi + ri I = 1 7 • • •^= 1 , • • • ,n 2 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 the vector sum of two polytopes is again a polytope. In the same manner as the vector sum of two convex bodies is defined, the linear combinations of convex bodies can be defined. Let A i > 0, i = 1, . . . , r, be arbitrary constants. The linear combination of convex bodies Ci i = 1, . , r, is defined as , C =^+ • • • + Arx, I xi E Ci} and is denoted as C =^+ • • • + ArC, = E i=i The position of C generally depends on the choice of origin 0. If 0 is replaced by another point 0', C will be translated by (E1, 1 Ai — 1) 00', where 00' is the vector from 0 to 0'. Hence, if >I = 1, linear combinations will be independent of the coordinate system. Of particular interest is the linear combination = (1 of two convex bodies C 1 and C2. — e )Ci + 0 6 2 , 0 1 < 0 <1,, Chapter 2. Mathematical Background^ 37 Similar to the argument of Theorem 2.28, the support function H(C; v) of the linear combination C of the convex bodies Ci i = 1, , r, is the linear combination of the , support 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 curvature function. The normal representation and the first curvature function of the vector sum of convex bodies are the sum of the normal representations and the first curvature function of the convex bodies, respectively. There is, however, no study done about the distance function of the vector sum of convex bodies. The area function of the vector sum 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 simple type (segments and triangles), and every convex set is the limit of finite vector sums of triangles. 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 the corresponding breadth of the summands. Let C' be the reflection of C about the origin. Then C+ C' is called the vector domain of C. A convex body C is a body of constant breadth if and only if its vector domain is a sphere (Firey [20] page 97). Let Bd be the unit ball in Rd having origin as the center. If C is a convex body, then C + itB d (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 of a convex body (Section 2.5.2). Chapter 2. Mathematical Background^ 38 2.4.2 Blaschke Addition Definition 2.16 (Firey [20] pages 94-95.) Let C i and C2 be two convex bodies with area functions S(C i ; 52) and S(C 2 ; ft), respectively. The Blaschke sum of C 1 and C2 is defined as the convex body C whose area function equals to S(C i ; + S(C2 ; 9), and is represented as C = C1 #C2 . The process is called Blaschke addition. The notion of scalar multiplication associated with Blaschke addition is defined as the convex body with area function 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. Since the area functions S(Ci ; CO and S(C2 ; ft) satisfy the conditions of the theorem, so does their sum. Thus a convex body is uniquely determined, up to translation, as having the sum 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 bodies can be defined. Let Ci , i = 1,^, r, be convex bodies, A > 0, i = 1,^, r. Define C^x Ci # • • • #A, x Cr = C=1Ai x Cq to be the convex body having function S(C; S2) = A i S(C i ; C2) + • • • + S(Cr.; C2) as its area function. Similarly, Co = (1 — 0) x C l # 0 x C2 0 < 0 < 1, is of particular interest , under certain circumstances. By equation (2.18), the brightness of a Blaschke sum, in any given direction, is the sum 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 ^ 39 Theorem 2.29 (Firey-Griinbaum, Firey [26] page 94.) Every polytope P is expressible in the form P= where each Pi is a simplex. Further, if P is d-dimensional and the number of facets of P is 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 representable in the form P = #71 1 Pi where each Pi is a d-polytope with the number of facets of 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 constant brightness function if and only if C#C' is a sphere. 2.4.3 Polar Means Another combination of convex bodies can be defined by a combination of distance functions. The definition and the theorem (of Brunn-Minkowski type, according to Firey) in this subsection are from Firey [19]. Definition 2.17 (Firey [19] page 444.) Let C1 and C2 be two convex bodies containing 0 as a common interior point. Define function go(P) as follows: 1/ g1 ( x)^ (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 o( P) (x) satisfies Chapter 2. Mathematical Background^ 40 1. .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(C i ; 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(c o ) + eV-p/d(c i ) , for 1 < p < oo. There is equality on the left if and only if Co = C1 and on the right if and only if Co = AC1 with center of homothety at 0. Further vi/d(co n CO = vl/d(d") ) ) < min(vlid(c0), v l i d (ci)) with equality on the right if and only if C o = C1 . 2.4.4 The Projection Body Definition 2.18 (Petty [59] page 234.) Let C be a non-degenerate convex body and let cr(C; v) be its cross sectional measure. The convex body with center at origin and support 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 the support 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 ^ 41 2.4.5 Polar Set, Conjugate, and Legendre Transform Definition 2.19 (Lay [42] page 140.) Let S be any nonempty subset of Rd. The polar set S* of S is defined by S* {y E R d : (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 convex set containing 0. Theorem 2.33 (Minkowski, Lay [42] page 140.) Let C be a compact convex body in Rd with 0 E int C. Let C* be the polar set of C. Then the support function of C is equal to the distance function of C*, and the distance function of C is equal to the support function 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) < is closed in R d for every ja E R. The function f* on Rd defined by f*(x*) sup { (x, x*) — f(x) I x E R d } is called the conjugate of f. Fenchel [18] proved that f* is again a 1.s.c. proper convex function on Rd and that the conjugate of f* is in turn f. Fenchel also mentioned that the distance function and the support function of a convex body are conjugate functions of each other. Given a convex function f defined on A C R d , let A+ be the point set in Rd+' E Rd+ I bounded by {(x, f(x))^x E Al. A+ is convex because f is convex. Let Chapter 2. Mathematical Background^ 42 f*(P) (p, -1) Figure 2.5: Conjugate functions. v E Rd, v+ = (v, —1) E R d + i , then H(A + ;v + ) = max{(x+, v + ) 1 x + E A ll = f* (v) . This means that f*(v) is the value of the support function of A+ in the orientation v+. Figure 2.5 demonstrates the relation between f and f*, and gives a visual explanation of the above statement. The Legendre transform is a very useful mathematical tool. It establishes a duality between objects. It is also used in the theory of partial differential equations to reduce the order of a partial differential equation. (By means of a Legendre transformation, a Lagrangian system of second-order differential equations is converted into a symmetrical system of first-order equations, called a Hamiltonian system. See Arnold [2].) Definition 2.21 (Rockafellar [64] page 200.) Let Ii be a differentiable real-valued function given on a non-empty open set X in R d . Let X* be the image of X under the gradient map Vh : x —* Vh(x). If Vh is one-to-one, the function h*(x*) =. ° (x*,(Vh) - 1 (x*)) — h((Vh) - 1 (x*)) is well-defined on X*. The pair (X*, h*) is called the Legendre transform of (X, h). Chapter 2. Mathematical Background^ 43 Theorem 2.34 (Rockafellar [64] page 201.) Let (X, h) be a convex function of Legendre type on R d . The Legendre transform (X*, h*) is then well-defined. It is another convex function of Legendre type on R d , and Vh* = (Vh) -1 on X*. The Legendre transform of (X*, h*) is (X, h) again. Theorem 2.35 (Rockafellar [64] page 202.) Let h be a (real-valued) differentiable convex function defined on all of Rd. Then Vh is a continuous one-to-one mapping of Rd onto itself, if and only if h is strictly convex and lirn h(Ax)/A = +(Do for every x 0 . The conjugate of h is the same as its Legendre transform. 2.5 Mixed Measurements Let C 1 , C2 , ..., Cr be convex bodies. The vector sum C = E 7i=1 AiCi is defined (Section 2.1.1) and the support function of C is the corresponding linear sum of the support functions of Cg i = 1, 2, ... , r. The volume of C is a polynomial in Ai, i = 1, 2, ... , r, , the coefficients of which define the mixed volumes (Section 2.5.1). Similarly, the area function of C AB d is a polynomial in A, the coefficients of which define the i-th area function of C (Section 2.5.2). The area function and the curvature functions of C lead to the definition of the mixed area functions (Section 2.5.2) and the mixed curvature functions (Section 2.5.4). From mixed area functions, the mixed body is defined (Section 2.5.5). Finally, the dual mixed volume is defined using the radial function of convex bodies (Section 2.5.6). Chapter 2. Mathematical Background ^ 44 2.5.1 The Mixed Volumes Definition 2.22 (Busemann [15] page 43.) The d-dimensional measure (or volume ) of C is denoted by V(C). For variable A i > 0 the volume of C =^AiCi is a form v(c) = E E • E i=1 i 2 =1^id=1 14,^• Aid of degree d in the A i , where the coefficients^...id are uniquely determined by requiring that they are symmetric in their subscripts. Then Vi i ...i d depends only on the bodies Ci l , .^Cid and not on the remaining bodies^Write V(Ci i ,^, Ci d ) for Vi,...i d , and call it the mixed volume of Ci„^, The most important mixed volumes are the ones that involve only two distinct convex bodies. The notation Vi(C i , C 2 ) was introduced as follows (Busemann [15] page 43): Vi (Ci , C2 )^V(Ci, • • • C17^= Vd-i(C2, C1) • d-i Then (d A2C2)^Ai-92Vi(C1, C2) . 1=0^i When 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 functions of the convex bodies involved. Recall equation (2.19) V(P) = N E H(P; u1)A(pi) where pt, i = 1, . . . , N, are the facets of a non-degenerate polytope P, A(pi ) the areas of pi and u i the unit outer normals of the support planes of P containing p1 . This can be Chapter 2. Mathematical Background^ 45 generalized to the mixed volumes of a polytope P and an arbitrary convex body C1 as (Busemann [15] page 44) 1N Vi(P,^ = — EH(C i; ut)A(pi) .^(2.20) d A limit process of the above equation yields V1 (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 of the boundary, a l , a2,^, ad_ 1 the parameters introduced on S d-1 in Section 2.1.2, then 8x(t1) 1^E^det [x(d) ^ax(id-1)] da l • • dad-1 v(ci,• • • , Cd ) = c7 Oad-i where the sum is taken over all permutations of (1, • • • , d — 1). If Bd is substituted for C* in equality (2.21), then V1 (C, B d ) =^H(Bd; w)dS(C; w) 1 js, dS(C; w) -cI- S(C) , (2.22) because H(Bd;cy) 1 on Sc1-1 . In fact, Bonnesen and Fenchel [7] define the surface area S(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 is not 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^ 46 Theorem 2.36 (Petty [59] page 234.) The non-degenerate convex bodies C 1 and C2 have the same projection body if and only if L) = V1 (C2 , L) for any convex body L that has a center. Define Wi(C) V (C, ,C, B d^Bd =_^Bd). Then the volume of the parallel body of C at distance it can be expressed as ( d V (C ilB d ) = Wo (C)^Wi(C)/i + • • • + 1 Wd(C)p d The quantity Wi(C) is called the i-th cross sectional measure integral: Wo (C) is the volume of C, W1 (C) is the surface area of C, and Wd(C) is always the volume of the unit ball. Some inequalities between the mixed volumes are of fundamental importance to the use 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 are convex bodies in R d , then 7(9) =^- e)ci + 0 c2 ) , 0 < B < 1 , is a concave function of 0, which is linear if and only if C 1 and C2 are homothetic or lie in parallel hyperplanes. Corollary 2.38 (Minkowski's Inequality, Busemann [15] page 48.) c2 ) vd - '( c1 )v(c2 ) . Chapter 2. Mathematical Background ^ 47 If 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.) VA C]. , C2 ) ? V ( Ci) V2(C i. , C2 ) • These inequalities are used to solve many extremal and uniqueness problems. The above inequalities involve only two convex bodies. Extensions of those results to other mixed volumes were proven by Fenchel and Alexandrov independently. Theorem 2.40 (General Brunn-Minkowski Theorem, Busemann [15] page 49.) If C 1 and C2 are convex bodies in R d , Co = (1 — 0)C1 + 0C2 , then 70) = 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 C 1 and C2 are convex bodies in Rd of dimension at least m, and if CI, ... , qi _ m are regular convex bodies, C o = (1-0)C1+0C2, then 7(0) = v il m(cl, — , c'd_m, co, — , co) , 2 < m < d , is linear if and only if C 1 and C2 are homothetic. With the aid of the above two theorems, in the same way as Minkowski's inequality was obtained, the following more general inequalities involving the mixed volumes are obtained. Chapter 2. Mathematical Background^ 48 Theorem 2.42 (Busemann [15] page 50.) If C 1 and C2 are convex bodies in Rd of dimension at least m, and if CI, , qi _ m are regular convex bodies, then for 2 < m < d, 0<i< 1 lint(C ,• • • Orj — m C17 • • •^S2L.:;,C2) Trt—i V ni—i (C;, • • • , C d—rn, Cl, • • • , C1) • V i (CI, • • • C d_ f rn , C2, • • • C2) , with equality if and only if C 1 and C2 are homothetic. A special case of the above inequality occurs when in = 2, i = 1 yielding the following inequality: Corollary 2.43 (Busemann [15] page 49.) v2(q,..•, Cl, C1) ' V (C;, • • • , CY 1-2, C2, Cd-2, C1, C2) > V (CL • • • , C d-2, l l with equality if and only if C1 and C2 C2)7 are homothetic. Alexandrov extended these inequalities further to the following more general inequality: Theorem 2.44 (Busemann [15] page 50.) If C1 , , Cd are convex bodies, then for 2 < m < d, Trt-1 V m (Ci, • • • , Cd) >^V(C1, • • • , C d—rn, C d—i, • • • , C d—i) • 1 =0 A special case of the above inequality occurs when m = d. Corollary 2.45 (Busemann [15] page 50.) v(c y(c ),...,v(c 1 2 d ). (2.23) ^= Chapter 2. Mathematical Background^ 49 2.5.2 The i th Area Function - Definition 2.23 Let C be a convex body, Bd be the unit ball, 52 E 13(Sd -1 ). Then for A > 0, S(C ,B d ; 52) is the polynomial in A (Firey [24] page 205) d—1 i Sd_i_i(C; 52)Ai . This defines the measure Si(C; 52) over B(S d-1 ) for i = 0,1, ... , d — 1 . Call Si(C; 52) the i-th area function of C. Let A equal to zero in the definition, then Sd_i(C; 52) is the (primary) area function of C defined in Section 2.1.7. If C is a regular convex body and r 1 , r 2 ,^,r d _ i are the radii of principal curvature of the surface of C, then (Firey [23] page 346) (d — 1) -1 Si (C; 51) where {Ti,., {^, ri}dco , ci E B(S d-1 ) , (2.24) 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. In particular, Si (C; 52) = d 1^f d — 1 io (ri + • • • + rd-l)dw ^ (H1 1 + • • • + Hdd)dw , 52 E B(S c1-1 ) —1 1 AI^ Sd-i(C; S2) = L(r i • • • rd _ i )dw ,^52 E B(S d - 1 ) . (2.25) Because the support function of a vector sum is the sum of the support functions of the summands, by (2.25), S1(C1 + C2; 9) = Sel; + Se2; 52 ) • Chapter 2. Mathematical Background^ 50 By 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, Is d-1 wdSi(C;co) = 0 . Theorem 2.47 (Alexandrov-Fenchel-Jessen Theorem, Schneider [69] Theorem (9.1) page 43.) If C 1 and C2 are convex bodies in R d , i E {1, • • • ,d — 1}, dim C 1 , dim C2 > i + 1, then Si (C l ; •) = 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 and C2 are convex bodies in Rd for which Si(Ci ; Q) < Si(C2 ; Q) for all Q Si +i (Ci ; S d-1 ) > Si +i (C2; Sd -1 ), for some i E E 1 13(S d-1- ) and {1,^, d — 1} (where for i^d — 1 the second condition has to be replaced by V(C 1 ) > V(C2 )). Then C 1 , C2 are translations of each other. The above theorems are about the uniqueness of convex bodies with respect to i-th area functions. Results about the existence of a convex body, for which i-th area function is given, are stated in terms of the necessary and sufficient conditions for a measure defined over 13(S d-1 ) to be i-th area function of a convex body. The problem is called Minkowski-Christoffel problem (Firey [25]). For i = d — 1, the solution is presented in 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 satisfies fsd-i uto(du) = 0 , ^ Chapter 2. Mathematical Background^ isd-1 51 ^u)(D(du) < Foo , - where g i is the fundamental singularity g i (u', u) = and / 7- r- in if d = 3, arc cos((u', u)/Ilull Hull) ^ 3-d — ^ [arc cos((u', u)/Ilull fsd- 1 A(u ', if d > 3, ,u)(1.(du) > 0, where A(u', v', u) = F(u', u)^F(v', u) — F(u' v', u), F(u', u)^(d — 2)(u', u)G(u f , u) — (u', VG(u', u)), G(u , u) = 7(s(u',u)) , f 7(s)^s Lod 112 cosec d 2 t^sire d - - 2 t'dtf) dt , s(u",u) = arc cos ((u', u)/I1411u'll) , G(u' ,u) = 1 1n [1^(u'' 47r ) I for d = 3 . Thus for d = 3, the Minkowski-Christoffel problems are solved, although the problems are still open for d > 3. The quantity So (C; ft) is the area of ft For S i (C; 9), the problem can be thought of as a generalization of Christoffel's problem, which is discussed in Section 2.1.3. For S 2 (C; 9), the problem can be thought of as a generalization of Minkowski'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 — 1 f) n 12)voli(f (P) Chapter 2. Mathematical Background^ 52 where ,Pi (P) is the set of i-dimensional faces of P, voli (f) is the i-dimensional volume of the i-face f, o-(P, f) denotes the spherical image of f, that is, the set of all outer unit normal vectors to P at the points of f and Ad_i_j is the (d —1— i)-dimensional spherical Lebesgue 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 Rd with dim C > i 1, 1 < i < d — 1. Suppose that the support of the area function Si (C; SI) can be covered by finitely many (d — 1 — i)-dimensional great spheres. Then C is a polytope. A necessary and sufficient condition for a Borel measure on S" to be the area function 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 the first area function of a convex polytope. The notion of spherical complex is used in the conditions. Definition 2.24 (McMullen and Shephard [54] page 153.) A spherical polytope in 5" is the intersection of a finite number of closed hemispheres which is not empty and contains no pair of antipodal points of S d _ i . A spherical complex C is a finite set C = , c r l of distinct spherical polytopes (cells) q on S" which satisfies the following two conditions: 1. u c i = S d , 2. For each i, j, the intersection q fl cl is a face (proper or improper) of both q and C3' Note 1 Spherical images of all non-empty faces of a polytope determine a spherical complex on 5". Chapter 2. Mathematical Background ^ 53 Note 2 Each d-polytope P corresponds to a spherical complex by the mapping, 0 : bdP ---4 8 d-1 , which maps x to the intersection of the ray, Ox, from 0 passing x with the sphere S d '. The mapping 0 maps proper faces to spherical polytopes. It has been shown that the reverse is not necessarily correct, i.e., there are 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 (S d-1 ), where the summation goes over all edges e of P, A(c) is the length of edge e, v(e) is the spherical image of e, and itd_ 2 (12 fl v(e)) is the (d — 2)-dimensional content of 9 fl v(e) on S d-1 . Theorem 2.51 (Schneider [68] page 81.) For a Borel measure 0 on Sd -1 there exists a d-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 spherical complex 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 = o C where the summation goes over all (d-2)-elements C E S for which ri is a side, and u(77, C) = v c /lIvcji such that v C is the orthogonal projection of C on the 2-dimensional linear subspace orthogonal to 77. Chapter 2. Mathematical Background^ Let s, , G 54 be the (d-1)-elements of S. For any j, 1 < j < k, an ordered sequence , 'i n,,) of (d-1)-elements of S can be constructed such that^fl^is a (d-2)element, r = 1,^, m — 1, i 1 = 1, i n, = j. Define xi as xi = m-1 E^ n ir+1) r=1 where v(i r , i r+i ) is the unit vector which is orthogonal to the linear hull of S i r n^i r+l and pointing into the interior of the halfspace containing ^The convex hull of the points x i ,^, xk is the polytope whose first area function is the given measure. 2.5.3 The Mixed Area Functions Definition 2.25 (Schneider [69] page 31.) The area function of C =^AiCi is a form r^r^r^r S(EA2Ci; f/) =EE•-• E i=1^i1= 1 i2=1^id-1=1 Ail • •^• • ,Cid_1; f2 ) (2.26) of degree d — 1 in the Ai, where the coefficients S(Ci„^, Ci d ; 11) are uniquely determined by requiring that they are symmetric in their subscripts. Then S(Ci„^Ci d ;10 depends only on the bodies Ci„ , Ci d _ i and not on the remaining bodies Ci. Call S(Ci„^, Ci d ; 9) the mixed area function of Cif,^, By definition, Si(C; C2) = S(C,^, C, B d ,^B d • 52) . (2.27) The mixed area function was originally defined by Alexandrov and Fenchel-Jessen via mixed volume. It can be proven that, for given convex bodies^, Cd_i, there exists a unique measure^, Cd_i; •) on B(S d-1 ) such that V (C,^, Cd_ i ) =^H(C; w)dS(C i , . • Cd - i; (2.28) 55 Chapter 2. Mathematical Background^ for any convex body C. This measure was defined as the mixed area function of C1 ,^, Cd-i. Using this definition, equality (2.26) was then proven. Since 1 is H(C1 Li;w)dS(C2, ,Cd_ i ,C;w) d d-i V(Ci + L i , C2 , . , Cd_i, C) H(Ci;co)dS(C2,... H(Li;w)dS(C2 ,. i d-1 + -17 ( H(C; w)dS(Ci , C2, C; • • 7 Cd-17 C; C47 ) , Cd-i; sd H(C;co)dS(L i ,C2 ,...,Cd- 1 ;W) then S(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(B d ,C,...,C) is the surface area of C, the quantity d•V(B d ,C 1 ,. • • , 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, A2C2; 9 ) = d—1 ) i=o^i ,C1,C2,••• , C2; P)A1 -1-1 A i ^(2.30) d-1-i One fact about the mixed area function is that the measure is not concentrated on any great sphere of S d-1 and has the origin as the centroid (when viewed as mass loading on Sd -1 ), i.e., iSd- 1 WdS ( Ci • • . Cd-i ;^= 0 .^ (2.31) Chapter 2. Mathematical Background^ 56 2.5.4 The Mixed Curvature Function Recall from Section 2.1.3 that the curvature functions of a convex body is defined by the elementary symmetric functions of the radii of principal curvature, which must assume the continuity of the second derivatives of the support function of the convex body. A more general definition of the curvature functions employs the mixed volumes and does not make smoothness assumptions. Definition 2.26 (Bonnesen-Fenchel [7] page 121.) Let C be a convex body. If a function Fi (C; u) is continuous and non-negative on Sd -1 , and if for an arbitrary convex body L with support function H (L; u), -1 V(L,C,. ,C,^ = 1 (d — 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. fs d-, wFi(C; w)dw = 0; 3. When H(C; u) has continuous second derivatives, Fi(C ; u) = {r i^ri} = Di(H(C)). Definition 2.27 The i-th curvature function of A 1 C1 A2C2 is a homogeneous polynomial of degree i in A l and A2. Its coefficients are called the mixed curvature functions of C1 and C2. Chapter 2. Mathematical Background^ 57 2.5.5 The Mixed Bodies Firey [20] initiated the study of the mixed bodies with d = 3. The area function of Co = (1 — 0)C1 0C2 , where C1 and C2 are convex bodies, is given by the generalized Steiner formula (Firey [20] page 95) as ^S(C,9; f2) = (1 — 0) 2 S(C i ;^+ 20(1 — 0)S 12 (52) 0 2 S(C2; Q) • There is a unique convex body which has 812 as its area function. Firey called this convex body the mixed convex body resulting from C1 and C2, and denoted it as C(C 1 , C2 ). Then (1 — 0)C1 0C2 = (1 — 0) 2 x C 1 # 20(1 — 0) x C(Ci , C2 ) # 0 2 x C2 . In general, the mixed body of d — 1 convex bodies in R d 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 is S(C i , • • • , Cd_i; f2). This convex body is called the mixed body of C 1 , , Cd_ i , denoted as [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 its arguments, and that if the Ci are replaced by homothetic copies, the resulting mixed body will be homothetic to the original. It also follows that [C, , C] = C, where equality 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 d-1-i • • •7 C2^[C]i ^[C1, B d[i • Chapter 2. Mathematical Background^ 58 Then by definition, Cif + c2 = When d = 3, C1 + C2 = C1#2 x [C1, C2]#C2 • Also by definition, S ([C]i; ft) =^12) . When d = 3, S([C, B d]; 52) = Si (C; 52) . Lutwak [50] studied the volume of mixed bodies. The following two theorems are of special interest to us. Theorem 2.52 (Lutwak [50] page 492.) If C 1 , , Cd_ i are convex bodies in R d , then V(Ci) • • • V(Cd-i) < vd-1 acti,^1\ d-1 with equality if and only if C1 are homothetic. Theorem 2.53 (Lutwak [50] page 492.) If C1 and C2 [d--1 d 1) V 1 l d (C1 )+V 1 l d (C 2 ) < E^od_o/d([ci, are convex bodies in R d then 1 1/(d-1) , — c2]1) ^<^c2) i-,0 with equality, in either of these inequalities, if and only if C 1 and C2 are homothetic. 2.5.6 The Dual Mixed Volumes Definition 2.29 (Lutwak [49] page 532.) Let C1, ... Cd be convex bodies. The dual mixed volume of C1, .^C d is defined as , Cd)^71/ isd 1 p(Ci; w) • • • P(Cd; w)dw Chapter 2. Mathematical Background ^ 59 The 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 ) with equality if and only if A i = B, for all i ; 4. f/(C,...,C) = V(C). The notation 14(C 1 , C2 ) is introduced: 14(Ci, C2)^ • • • ,C2) • d—i Theorem 2.54 (Lutwak [49] page 533.) •• ,cd) 5 H v(ci.,• • • i=0 7 1<m<d, Cd—m, with equality if and only if Cd_m-Fi, Cd-m+2, ^, Cd are all dilations of each other (with the 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 , C 2 ,^, Cd are all dilations of each other (with the origin as the center of dilation). Combining this corollary with the Alexandrov inequality (2.23) yields: Chapter 2. Mathematical Background^ 60 Corollary 2.56 (Lutwak [49] page 534.) , cd ) < v(c ,^, cd) i , with equality if and only if C 1 , C2 ,^, Cd are all dilations of each other (with the origin as 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 Summary Various orientation-based representations of shape have been defined. Foundation for studying the orientation-based representations have been surveyed and presented coherently. The characteristic properties of the orientation-based representations of shape include: 1. One-to-one property; 2. Necessary and sufficient conditions for a function to be a valid orientation-based representation; 3. Reconstructability. The common property of all the orientation-based representations is that they rotate in the same way as the object rotates. Chapter 2. Mathematical Background^ 61 The support function plays a very important role in the analysis. It links the results together. Most other representations can be computed from the support function. The support function also is related to the Legendre transformation used in applied mathematics. The distance function and the radial function deserve special attention because in addition to convex bodies they are well defined for compact starshaped sets. When d = 3 there are two curvature functions and two area functions. The first curvature function is the sum of the radii of principal curvature and the second curvature function is the reciprocal of the Gaussian Curvature. The area functions may seem inappropriate 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 covered by finitely many points (for the (d — 1)-th area function) or line segments (for the first area function) on S". Table 2.1 summarizes the properties of the representations, where S is an arbitrary set in R3 and Q is an arbitrary polyhedron in R 3 . Results about the one-to-one property of the representation, necessary conditions for a function to be the representation of a shape and sufficient conditions for a function to be the representation of a shape are known for all the representations listed. Except for the second curvature function and the second area function, all representations can be inverted to reconstruct the object. The rest of this dissertation is concerned with attitude determination. Previous research is surveyed in Chapter 3 and new results are presented in Chapter 4. The theorems of this chapter provide the necessary and sufficient conditions for two bodies to be homothetic. In particular, conditions on the extrema of inequalities involving orientation-based representations are used. Chapter 2. Mathematical Background H(S; u) x(S; u) g(S; u) p(S; u) TVS; u) F2 (S; u) Si (S; Sl) S2 (S; 52) Si(Q; Q) S2 (Q; SI) ^ 62 Defined One-to-one Necessary Sufficient Extent Extent Conditions Conditions arbitrary convex known known yes Theorem 2.2 Theorem 2.3 Theorem 2.5 known known yes Theorem 2.8 Theorem 2.8 trivial known known yes Theorem 2.14 Theorem 2.15 Page 24 known known yes via g(S; u) via g(S; u) via g(S; u) convex, up to known known yes a translation Theorem 2.9 Theorem 2.11 Theorem 2.11 convex, up to known known unknown a translation Theorem 2.9 Theorem 2.10 convex, up to known known yes a translation Theorem 2.46 Theorem 2.49 Theorem 2.49 convex, up to known known unknown a translation Theorem 2.21 Theorem 2.22 convex, up to known known yes a translation Theorem 2.51 Theorem 2.51 Theorem 2.51 convex, up to known known yes a translation Theorem 2.23 Theorem 2.23 Little [47] convex arbitrary arbitrary convex convex convex convex convex convex convex starshaped starshaped Reconstructable Table 2.1: Properties of orientation-based representations. Chapter 3 Previous Research In machine vision, previously used orientation-based representations of shape, as defined by Definition 2.1, include the Extended Gaussian Image (EGI) and generalizations defined by Liang and Todhunter [45] and by Kang and Ikeuchi [40]. Representations not previously described as orientation-based but which easily fit the framework defined in Section 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 function and the second area function respectively. It is known from Chapter 2 that these orientation-based representations are one-to-one only for convex bodies. There has been some 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 existing orientation-based representations, new orientation-based representations are sought that are well defined and well behaved when applied to non-convex sets. In particular, the distance function and the radial function are of interest since they are well defined and one-to-one for compact starshaped sets. The radial function for two dimensional sets has 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 radial function has not previously been used in 3-D attitude determination. Nalwa [57] argued that differential geometric representations are, in general, inade63 Chapter 3. Previous Research^ 64 quate and suggested that global geometric information be incorporated. He proposed to use 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 and attitude determination. The use of the support function by Little [47], however, is for polytopes only. One novel contribution of this thesis is to use the support function in attitude 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 development of the EGI and its use in recognition and attitude determination. Section 3.2 looks at efforts to extend the EGI to handle more complicated objects and to solve other related problems. Section 3.3 surveys the use of these representations in computational vision. Finally, Section 3.4 summarizes the current state of the art by enumerating what has 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 Image The idea of the Extended Gaussian Image originated with Smith [71]. Smith called the representation the Enhanced Spherical Image (ESI) because of its connection to the spherical image (Section 2.2). "An ESI model for a convex object consists of a set of vectors. An individual vector's direction component represents the direction of a surface normal of the object, and the vector's magnitude signifies the object's surface area corresponding to the particular normal direction." This is equivalent to the EGI for a polytope as discussed later in this section. The ESI model could not represent smooth objects since the spherical image of a smooth object includes finite area patches on the sphere. A theorem of adjacency proposed by Smith [71], which claimed that Chapter 3. Previous Research^ 65 adjacent points in an ESI were the mappings of adjacent faces in the corresponding convex 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, for a surface C, as a map, Gc : S d ' which associates the inverse of Gaussian curvature at a boundary point of a surface to the orientation u E S d-1 of the surface at the point: Gc (u)= 1 Kc(x(u)) , where x(u) is the point on C with unit outward normal u, and Kc(x(u)) is the Gauss curvature 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, Theorem 2.10 guarantees the existence of a unique, up to a translation, closed convex surface whose 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 EGI that captures the geometric description of a surface without requiring differentiability is needed when polytopes are encountered. A discretized version of EGI also is needed when the EGI is represented numerically. Since the Gaussian curvature at the faces of a 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 vectors A(P) = {a t: I 1 < i < f(P)}, where f(P) is the number of facets of P, the direction of a i is the same as that of the outward normal of face F, and the length of a i is equal to the (d — 1)-content of The justification for using the area function for polytopes is twofold: Chapter 3. Previous Research^ 66 1. The curvature function and the area function are associated by equality (2.24), S(C;^=^rir2 • • • rd - idw where r 1 , r 2 ,^, r d _ i are the radii of principal curvature; 2. The Gaussian curvature can be defined as K(p) , li mo ^lE IG (E)I iEi where E is a compact portion of the surface containing p, G(E) is the spherical image 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 the discrete rotation space. In Horn and Ikeuchi [37], the EGI of a prototype is rotated to match the EGI of a sensed object until the sum of the square of the differences between the two EGI's is a minimum. The prototype that achieves the minimum difference among all prototype identifies the sensed object. Ikeuchi [38] viewed the problem of matching as the determination of the line of sight and the rotation angle with respect to an internal Chapter 3. Previous Research^ 67 model. The EGI mass center constrains the line of sight, and the EGI inertia direction constrains the rotation around the line of sight. Little [47] made use of Brunn-Minkowski's Theorem (Theorem 2.37) to reconstruct a polytope from its EGI and to determine the attitude of a polytope with respect to a model. Let P and Q be two convex bodies, R = AP + (1 — A)Q. By the Brunn-Minkowski Theorem, 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, one obtains Vi3(Q,P) V(P)V 2 (Q) The Brunn-Minkowski Theorem states that the polytope P, having unit volume, that minimizes Vi (Q, P) is homothetic to Q.^Now suppose Q has area function A(Q)^{A(qi) I 1 5 i^N}, where q i are faces of Q with outward unit normal w i . Recall, from equality (2.20), that Vi3 (QP) = EN H(P; wi)A(qi)) 3 . Using this relation, Little developed an iterative method which combines the techniques of constructing a polytope from its support vector (values of support function at the facet orientations of the polytope) and minimization techniques to construct the support function of P such that A(P) A(Q). This is to say that given a sensed EGI A(Q), its corresponding polytope can be reconstructed. In attitude determination, a sensed EGI, A(Q), is given and the task is to find the attitude which rotates the sensed EGI into correspondence with the prototype EGI. Consider the P in the above inequalities as the prototype. Then to determine object attitude, Little minimized N E H(P; R(wi))A(qi) i=i Chapter 3. Previous Research^ 68 over all rotations R. When only the portion of a surface corresponding to a single visible hemisphere is sensed, the EGI of the object is not complete. Little used E Lai H(P; R(wi))A(qi) , E S 2 (V) where the S 2 (v) is the hemisphere visible from viewing direction v. Good performance of the method using the mixed volume with both complete and partial EGI was reported. 3.2 Generalization of the EGI There have been several attempts to generalize the EGI so that a larger class of objects can be represented and more problems can be solved. The generalizations still are orientation-based representations. Among the representations are the surface shape representation 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 extension to the EGI in that smooth surfaces are considered and principal curvatures/directions are recorded rather than Gaussian curvature alone. A vector function on the unit sphere is defined for each surface patch. The function value is the vector composed of the maximum principal curvature, the minimum principal curvature and the two components of the unit maximum principal curvature direction. An algorithm was proposed for matching surface shapes with strictly positive and strictly negative Gaussian curvatures. For general surface shapes, it was suggested that the surface shapes be partitioned into regions with positive, negative and zero Gaussian curvature. Matching algorithms are intended. Problems arise, however, when surfaces contain holes even if the Gaussian curvature is strictly positive. For example, in Figure 3.1, the representation of Liang and Todhunter is not well defined for the surface patch in the figure because there are points on the surface patch whose normal directions are the same. The one-to-one correspondence Chapter 3. Previous Research^ 69 Figure 3.1: An open surface patch with positive Gaussian curvature. between the sphere and the surface via normal vector is only guaranteed for regular closed convex surfaces. The Complex Extended Gaussian Image (CEGI) defined by Kang and Ikeuchi [401 associates a complex number to each normal vector. The magnitude of the complex number is the area of the face corresponding to the normal, and the phase of the complex number is the normal distance of that face to the origin. Thus, the CEGI is equivalent to the EGI augmented with the value of the support function at each normal. The idea came from the observation that the EGI is translation invariant. The CEGI was used to determine the translation parameters using a least-square technique. Suppose the object is translated by (Sx, Sy, Sz). The method requires that V(8 x )2 (so (6 z )2 < 7r . This requirement can be eliminated by making use of the properties of the support function. Recall equality (2.1). If a set C is translated into C' by a vector a, the support function of C' is H(C'; v) = H(C; v) + (a, v) . Let v 1 , v 2 , and v3 be three normal directions, d i and dT be the corresponding support Chapter 3. Previous Research^ 70 function values before and after the translation. Then =^+ (a, v,) , i = 1, 2, 3 . Thus a is the solution of the equation id1 — d i a T • (v i V2 V3) =^Ct2 - d2 d — d33 3.3 Related Representations Examples of related representations are Gaussian curvature and mean curvature represented as functions defined on the image plane. The distinction between these functions and the curvature functions studied in this dissertation is a technical one. Properties of these representations follow from differential geometry. Besl [5] proposed using Gaussian and mean curvature as "visible-invariant surface characteristics" and used the signs of Gaussian curvature and mean curvature to define eight visible-invariant HK-sign surface types. From this, a theory of image segmentation was built. A wide variety of range images and intensity images were tested. This "signof-curvature" paradigm has been very influential in computational vision, particularly in the area of viewpoint invariant surface segmentation (see, for example, Li [43]). There are many other representations that involve the use of surface curvature properties. For a more thorough survey, see Besl [5, 6]. Chapter 3. Previous Research ^ 71 3.4 Summary Among the orientation-based representations, only the second area function for polytopes has been utilized in computational vision [37, 47]. At the same time, a comprehensive collection 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 in new ways using combinations of the support function, with the first curvature function and the second curvature function and the radial function. Chapter 3. Previous Research^ 72 Used Representations Before H(P; 0 yes trivial done Little [47] Theorem 2.5 Little [47] no trivial done in Section 4.1 H(C; ) Reconstruction Attitude Orientation-Based Determination Theorem 2.5 g(C; 0 no trivial Page 24 p(C;) Fi(C; 0 yes trivial Schudy et al [70] via g(C;) no possible done in Section 4.2 done in Section 4.1 Theorem 2.11 F2 (C; ) no unknown Si(P;w) no possible done in Section 4.1 Theorem 2.51 S2(P;w) Si (C; w) yes done done Little [47] Little [47] Little [47] no possible Theorem 2.49 S2(C;w) no unknown Table 3.1: Use of orientation-based representations. Chapter 4 Solutions to the Attitude Determination Problem In this chapter, the problem of attitude determination is defined and theoretical solutions to attitude determination using orientation-based representations are provided. The following 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 R 3 are considered. Definition 4.1 Attitude determination is the problem of finding a rotation, R, such that R(C1 ) and C2 are homothetic, where C 1 is a known 3-D model and C2 is an instance of C1 under an unknown rotation, translation and scaling. Section 4.1 uses the support function and the curvature functions to solve the attitude determination problem. Section 4.2 uses the radial function in attitude determination. 73 Chapter 4. Solutions to the Attitude Determination Problem^ 74 4.1 Attitude Determination by the Support Function and Curvature Functions Throughout, assume that C 1 is a given object model defined in a standard coordinate system and that C2 is a measured instance of C 1 subject to unknown rotation, translation and scaling. Let R denote an arbitrary rotation. By Corollary 2.43, V(R(C1), C2, B 3 ) ?_ VV(R(Ci), R(Ci), B 3 ) V(C2, C2, B 3 ) (4.1) with equality if and only if R(C1 ) and C2 are homothetic. Further, it is known that V(C, C, B 3 ) 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 ), B 3 ) = V(Ci, Cl , B 3 ) and the minimum value of (4.1) is /V (C 1 , C1, B 3 )V(C2, C2, B3 ), independent of R. Accordingly, V(R(C1), C2, B 3 ) 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)) V 2 (C2) (4.2) with equality if and only if R(C1 ) and C2 are homothetic. Volume is invariant under rotation. 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 this minimum if and only if R(C 1 ) and C2 are homothetic. Now, define functions of R as follows: 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 if and only if Ro (C i ) and C2 are homothetic. Therefore, by Definition 4.1, the 3-D attitude determination problem can be solved if the minima of (,o(R) or '(R) can be found. Either Chapter 4. Solutions to the Attitude Determination Problem^ 75 of these minima is an equivalent solution to the 3-D attitude determination problem. The global minimum of (,a(R) is 3/S(C1 )S(C2 ) and that of b(R) is /V(C1 ) V 2 (C2), both of which are known independent of R. By the conditions of Corollary 2.43 and 2.38, these global minima are unique, modulo any rotational symmetries that C 1 possesses. Thus the attitude determination problem can be expressed as one of the following optimization problems: minimize: c,o(R) subject to: R is a rotation , minimize: 0(R) subject to: R is a rotation . (4.5) (4.6) A rotation, R, can be represented as a triple (0, 0, it) interpreted to mean a counterclockwise rotation by angle 52 around unit vector (sinOcos0, sinOsinO, cos). When R is represented in this way, cp(R) and '(R) are functions of the three variables 0, 0, 52 E R3 and are written as cp(0, 0,52) and 0(0,0,9). Thus, the problem of 3-D attitude determination is transformed into two equivalent optimization problems: minimize: subject to: minimize: subjectto: (10 (0, 0 , Q) ,^(0, 0 , n) E R3 , 0 < 0 < 7r,0<61 < 27r,0 <ft< 7r 0(0, 0 , 52 ) ,^(0, 0 , Q) E R 3 , 0<0<71- ,0<0<27r,0<52<7:- (4.7) (4.8) Since the feasible regions of the above optimization problems are closed and bounded, solutions to the optimization problems necessarily exist. Thus solutions to the attitude determination problem formulated in this way necessarily exist. Since any triple (0, 0, 52) in R3 corresponds to a rotation, it is not necessary to set the bounds on (0, 0,52) to [0, 7] x [0, 27r] x [0, 7r], which only ensures that the representation Chapter 4. Solutions to the Attitude Determination Problem^76 is unique within the bounds. Thus, the problem of attitude determination can again be transformed into the following equivalent optimization problems: minimize:^yo(0, 0,52) , (0,0,Q) E R 3 , (4.9) minimize:^0(0, 0 ,n) , (0, 0,Q) ER3 . (4.10) Since the objective functions are periodic and bounded, solutions to both of these optimization problems also necessarily exist. It is important to note that the required mixed volumes are well defined as long as C 1 and C2 are 3-D convex bodies. Thus, optimization problems (4.9) and (4.10), derived from Corollary 2.43 and 2.38, apply to polyhedra too. If C 1 and C2 are smooth and strictly convex, then the objective functions c,o(R) and 7.1)(R) can be written explicitly, according to Equation (2.32), as is2 H(R(Ci ); Fi (C2 ; w) dcv , (4.11) coo (R) = zP(R) = -31 is, H(R(Ci ); F2 (C2 ; co) du; . (4.12) 61 When the support function of C2 has continuous second derivatives, Fi (C2 ; w) and F2 ( C2 j w) are the sum of the radii of principal curvature and the reciprocal of the Gaussian curvature of the surface of C2, respectively. The interpreted roles of C 1 , C2 as the model and the sensed object can be exchanged depending on what measurement can be made about the object. Suppose the support function of an object can be measured instead of the curvature functions. Then the roles of C1 and C2 in the derivations of this section can be exchanged. Then the curvature functions, instead of the support function, of the model are needed in order to minimize y)(R) and '(R). Because of the symmetry between R and R 1 and between C 1 and C2 the attitude - , determination problem may also be expressed as an optimization involving one of the Chapter 4. Solutions to the Attitude Determination Problem^ 77 following functions: (pi(R) 'a V (R - 1 (C2 ), C i , B3 ) , 01(R) .-,'I'- V (R -1 (C2 ), C1 , C1) , (p 2 (R) a V (C 2 , R(C1), B 3 ) , 02(R) = V (C 2 , WO, R(C1)) • Again, using Equation (2.32), these functions can be calculated as follows when C2 is smooth and strictly convex: 1, coi(R) = -61- 7,bi(R) = d s2 (,02(R) = -6- 02(R) _, i is2 H(c2 ; w)F2(R(ci) H ( R-1 c2 ) ,,,,)Fi ( ci, w)dw , (4.13) i H(R -1 (C2 ); w)F2 (C i ; cv)dr.i..) , (4.14) H c2 ; w)Fi (R(Ci ); w)dco , (4.15) 2 L ( ( ; w)du, . (4.16) In practice, sensed surface data typically is obtained from a single viewpoint. Thus, the points at which the curvature functions of C2 are known span only a hemisphere. Therefore, the objective functions can not be computed over the whole unit sphere as in Equation (4.11) and (4.12). To proceed, it is necessary to "complete" the visible surface, to convert it into a convex body. Suppose the viewpoint is in the positive z direction. Further, suppose that the occluding boundaries of C2 and R(C1 ) each lie in a plane'. Assume coordinate systems are assigned so that the plane for C2 is z = 0. Let R(C 1 )' be the convex body bounded by points of R(C 1 ) that are visible in the positive z direction and by the plane containing the occluding boundary. Let C2 be the convex body bounded by points of C2 that are ' visible in the positive z direction and by the plane i Marr z = 0. Figure 4.1 provides a 2-D [52] provides if and only if conditions for an occluding contour to be planar, independent of viewpoint. Here, this is equivalent to assuming the surface is quadratic. Chapter 4. Solutions to the Attitude Determination Problem^ (a) R(C1)' ^ 78 (b) C2 ' Figure 4.1: Using the data on a hemisphere in optimization when the object is viewed from a single viewpoint. example where C 1 and C2 are ellipses and where R(C1 )' and C2 ' are the shaded regions shown. Of course, Corollary 2.43 and 2.38 still apply to R(C1 )' and C2 ' . Therefore, V(R(Ci)', C2', B 3 ) ^> Vv(c2 ', C 2 ', B 3 ) ,^(4.17) 3 ) )', B VV (R(C1)', R(C1 and V(R(C1) 1 C2 ' , C2') > ,/1/2(C2 1 ) ,^ 7 I/V(R(C1 )0 with equality if and only if ( 4.18) 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, can be defined as follows: c3(R) n, ^V(R(Ci)', C2 ', B 3 ) VV(R(Ci )', R(C1)', B 3 ) 2 ') (R) ° V (R(CI)' , C2 ', C 1/V(R(Ci)') ^• (4.19) (4.20) ^ ^ Chapter 4. Solutions to the Attitude Determination Problem^ 79 However, neither R(C1 )' nor C2 ' is smooth and strictly convex so that the mixed volumes 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 u z denote the vector (0,0,1), uR denote the normal of the plane that contains the occluding boundary of R(C 1 ), S 2- and 8 2 + denote the hemispheres corresponding to z < 0 and z > 0, respectively. The mixed volumes in functions c,23(R) and b(R) are ^V(R(Ci )', C2 ', B 3 )^-6- 1J H(R(C 1 ); w)Fi (C2; w)dw f g2+ V(R(C0', R(C i )' B 3 )^H(R(Ci);‘,i)Fi(R(Ci);w)(103 s2+ V(R(Ci)', H(R(Ci )'; w)dSi (C2 '; co) , C2', C2') H(R(CO' ; w)dS i (R(Ci )'; w) , ^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)dw H(R(C1) ' ; UR) S2(R(C1) 1 ; UR) • Thus CO(R) = 71) ( R ) = is2- H ( R ( ); ) ( C 2; w)dw + s 152 + H (R(C 1 )' ; w )dSi ( fS2- H(R(C1); W)F1(R(C1); w)dw^f92+ H(R(C1)'; W)do91(R(Ci) f ; (4))11 fs2- 11(R(C1); w)F2(C2; w ) dw H(R(C1); nz) • S2(q; uz) (.4))ck,; H(R(C1)'; uR) • S2(R(C1)'; uR)i l The value of S2(C2'; u z ) does not depend on R. In fact, by Equation (2.24) and TheoiS2- H(R(C1); W)F2(R(C1); rem 2.46, S 2(C 2 ; u z ) = —f w,F2 (C 2 ; w)dw s2where wz denotes the z component of w. The value of H(R(C1 )'; u z ) is non-negative. When R(C 1 )' and C2 ' are homothetic, H(R(C1 )'; u z ) is zero and 192+ H(R(C i )'; w)dS1(C2';(.0 ) Chapter 4. Solutions to the Attitude Determination Problem^ 1 ,52-1- 80 H(R(C i )'; 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(C i )' and C2 ' introduce new area and mixed area terms into the mixed volumes that, while slowly varying, do depend on R. Ignoring these terms affects the accuracy of the mixed volumes V(R(C i )', C2 ', B 3 ), V(R(Ci )', R(Ci)', B 3 ) and V(R(C i )', C2 1 , C2 ' ). When these terms are ignored, the objective functions c23(R) and 7,3(R) become the following functions: ^(7)(R) fs2- H(R(Ci); w) Fi (C2; w) du; =^it. [s fs2- H(R(Ci); w) Fi(R(Ci); w) d. 0 1 4 ' (4.21) ^(R) 1 fs2- H(R(Ci); w) F2(C2; (h)) do) — ^3 [1 fs2- H(R(Ci); w) F2(R(Ci); w) dW] k . (4.22) Minimizing C5(R) and '(R) only approximates the minimizing solutions to optimization problems (4.9) and (4.10). Even if perfect, minimizing (75(R) and 7k(R) does not solve the attitude determination problem, as defined in Definition 4.1, since part of the object is never seen and therefore may not be matched correctly. It does solve the attitude determination problem correctly to the extent possible, given the data available. Figure 4.2 depicts two 2-D convex objects that match when viewed in the positive z direction but that do not match over the whole unit circle. 4.2 Attitude Determination by the Radial Function The motivation to propose the use of the radial function in attitude determination is that the radial function can be defined for starshaped sets. The radial function and the 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.1 can be dealt with. Starshapedness is a natural step from convexity to non-convexity. Chapter 4. Solutions to the Attitude Determination Problem ^ 81 Figure 4.2: Two 2-D convex objects that do match when viewed in the positive z direction but 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 radial function. Theorem 2.16 says that a compact starshaped set that has the origin in its kernel is convex if and only if its distance function is convex. This means that the distance function 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 of C. To make the radial function a good representation for starshaped sets, it must first be defined for starshaped sets. It is noted that Definition 2.7 of the radial function in Section 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 as p(S; x) sup{A > 01 Ax E^, for x E R3 \ {0} .^(4.23) Chapter 4. Solutions to the Attitude Determination Problem^ 82 Figure 4.3: A 2-D starshaped set and its radial function, defined for points, (u, v), on the unit circle. The radial function of a starshaped set depends on the choice of origin in the coordinate system. If the origin is not interior to the set, S, then the radial function is not defined 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 is p(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 unit sphere is sufficient to determine the function over the whole space, R 3 . Figure 4.3 shows a 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 points on the unit circle, u 2 + v 2 = 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^ (a) non-starshaped ^ 83 (b) starshaped Figure 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 property is no longer guaranteed for non-starshaped sets. Figure 4.4(a) shows a 2-D nonstarshaped set that has the same radial function as the 2-D starshaped set shown in Figure 4.4(b). The dual mixed volume was defined in Section 2.5.6 using the radial function (Definition 2.29) for convex bodies. Since the definition of the radial function is extended to starshaped sets, Definition 2.29 of the dual mixed volume can be directly applied to any compact starshaped set whose kernel contains the origin. Definition 4.3 Let 8 1 ,82 , S3 be compact starshaped sets in R 3 with the origin in the interior of their kernels. Let p(Si ; x) denote the radial function of Si , i = 1, 2, 3. The dual mixed volume of Si, S2 S3 is defined as S2' 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 the Chapter 4. Solutions to the Attitude Determination Problem^ 84 objects involved in the dual mixed volumes be convex. Lutwak's proof of the theorem uses Holder's inequality for integrals (see Hardy [33] page 140). The essential requirement is that p(Si ; x), p(S 2 ; x), p(S3 ; x) be non-negative, measurable on S 2 and not identically zero. The radial function p(S; x) of a compact starshaped set S with the origin in the interior of its kernel satisfies these conditions. Thus Lutwak's result extends to starshaped sets: Theorem 4.1 m_i 17m(si, s2, s3)^ fi v(si, • • • , S3-7TL,^, 1 < i= 0 m^3 , m with equality if and only if S3_, F i,^, S3 are all dilations of each other (with the origin as the center of dilation). Corollary 4.2 f7 3 (s1 , s2 , s3 ) < f/(si , Sl, si)17(s2, s2, s2 ) 1/(s3 , s3 , s3 ) , with equality if and only if S i , S2, 53 are all dilations of each other (with the origin as the center of dilation). Let Si and S2 be two starshaped sets with origin in the interior of their kernels. Suppose S i is the model defined in a standard coordinate system, S2 the sensed instance of S i subject to unknown rotation, translation and scaling. Let R denote a rotation. By Corollary 4.2, f/(R(S1), S2, S2) V with equality if and only if V (R(S1), R(S1), R(S1))C/ 2 (S2, S2, S2) , (4.26) R(S1), 52 are dilations of each other (with the origin as the center of dilation). Note that the dual mixed volume 17 (R(S1), R(S 1 ), R(51)) is equal to f/(S i , Si, S i ) due to the rotation property (2.17) of the radial function. Therefore Chapter 4. Solutions to the Attitude Determination Problem ^ 85 the maximum value of (4.26) is known independent of R. Accordingly, V(R(S1), S2, 8 2) achieves this maximum if and only if R(S1 ) and S2 are homothetic. Now define x(R), a function of rotation R, by X(R) .= '' f/(R(S1), S2, S2) = 31 is, p(R-i(si); w)p2(s2; w ) dw . (4.27) Function x(R) depends on S i and 52. It reaches the known maximum if and only if R(S 1 ) and S2 are homothetic. By Definition 4.1, the attitude determination problem can be solved if the global maximal point of x(R) can be found. The global maximal points are solutions to the attitude determination problem. In fact, the global maximum of x(R) #(Si , Si, S1)1/ 2 (S2, 52, 82). By the conditions of Corollary 4.2, the global maximum of x(R) is unique, modulo any rotational symmetries that S i possesses. is known to be Thus the attitude determination problem can be expressed as the following optimization problem: maximize: X (R) (4.28) subject to: R is a rotation . Representing a rotation by a triple (0, 0, SI) where this is taken to mean a counterclockwise rotation by angle 52 around unit vector (sin0cos0, sin0sin0, cosq), the function X(R) becomes x(0, 0, 9), a function of three variables that has domain R3 . The problem of attitude determination is then equivalent to the following constrained optimization problem: maximize: X(0, 0 , g) , subject to: (OA f2) E R 3 , 0<0<r,0 < 0 < 27r,0<12<r. (4.29) Since any triple (0, 0, ft) in R3 corresponds to a rotation, it is not necessary to set the bounds on (0, 0, 52) to [0, 7r] x [0, 2r] x [0, id, which only ensures that the representation is unique within the bounds. Thus, the problem of attitude determination again is transformed into the following equivalent optimization problem: maximize: x(0, 0, fl) , (0, 0, ft) E R3 .^(4.30) Chapter 4. Solutions to the Attitude Determination Problem ^ 86 Since the objective function is periodic and bounded, solutions to the optimization problem necessarily exist. Because of the one-to-one onto correspondence between R and R - 1 , and because of the symmetry between S i and S2, the attitude determination problem may also be expressed as maximizing the following two functions: xi(R)^ifs2 p(R -1 (s 2); co) P 2 (S w)clw (4.31) X2(R) =^s i p(S 2; w) P 2 (R(s 1); w)dzo (4.32) The approach described so far assumes that the radial functions of both the object and the model are known over the whole unit sphere. When p(S 2 ; x) is known only at points clustered in one region of the unit sphere, the objective function, x(R), defined in Equation (4.27), may not be appropriate. For example, when p(S2 ; x) is obtained from sensed data from a single viewpoint, the points at which the radial function is known will never cover the whole unit sphere. An altered objective function is needed to solve the attitude determination problem when the radial function is known only on a portion of the sphere. Let V denote the smallest union of spherical polytopes (see Definition 2.24) in S 2 that contains all the points x on S 2 where p(S2 ; x) is available. Again, by Holder's inequality, 1^ Jv 2 p(R(S i ); co)p 2 (S2 ; w)dc.o^p3(R(Si); w)dwi 3 [jv p3 (S2 ; w)dd 3 V , (4.33) with equality if and only if p(R(Si ); x) and p(S2 ; x) are proportional to each other over V. Simply substituting V for S 2 in Equation (4.27), however, is not sufficient since the right side of (4.33) depends on R when V is not equal to 5 2 . Define a new objective function as 1 (R)^ = A, p(R(Si) w)P 2 (S2; w)dw Ely P (R(S 1); w)due 3 (4.34) Chapter 4. Solutions to the Attitude Determination Problem ^ 87 Figure 4.5: Two 2-D starshaped sets that match when viewed in the positive z direction but that do not match over the whole unit circle. Holder's inequality implies that X(R) achieves a maximum if and only if dilations of each other over V. The maximal value is s[f v p 3 (.52 ; w)dce] 3 R(S1 ) and S2 are . Thus, the part of the object where the radial function is sensed is matched to the model by maximizing T(R)Strictly speaking, this does not solve the attitude determination problem, as defined in Definition 4.1, since part of the object is not seen and therefore may not be matched correctly. It does solve the attitude determination problem correctly to the extent possible, given the data available. Figure 4.5 depicts two 2-D starshaped figures that match when viewed in the positive z direction but that do not match over the whole unit circle. 4.3 Summary The attitude determination problem is solved using the support function and the curvature functions for convex objects. It has been shown to be equivalent to the optimization problem: minimize: f (R) subject to: R is a rotation , Chapter 4. Solutions to the Attitude Determination Problem^ 88 where f (R) is one of the following functions: I BP(R) =^is2 H(R(C i ); w)Fi (C2 ; w)dw , 7,b(R) 1 .= 5 is2 H(R(C1); W)F2(C2 j w)&0 , (701(R) 1 = -6 is2 H(R -1 (c2); w)Fi(Ci; w)dw , 771) 1(R) CO2 (R) 1 is2 H(R-1 (C2); W)F2(C1; = 5 W)C1Lt; 1 =^is2 H (C2 ; w)Fi (R(Cl i ); w)du, , l fs2 H(C2; 7,b2(R) = i w)F2(R(ci); w)dw . When the curvature functions are available only over a hemisphere, for example, when computed with sensed data from a single viewpoint, only approximate solutions to the attitude determination problem have been obtained. The objective functions considered are: f s2- H(R(Ci); Fi(C 2; w) dw 6 c(R) (R) f.92- H(R(C1); =^ Fi(WO; (.4) ) CIA/1 12 H(R(C1);w F2(C2; w) dw ) [A fg,-- H(R(Ci ) ;^F2 (R(C1 ) ; w) du)] k • The attitude determination problem also has been solved using the radial function for starshaped sets. It is shown to be equivalent to the following optimization problem: maximize: f (R) subject to: R is a rotation , where f (R) is one of the following functions: X(R) = Xi (R) = X2(R) 1 1 1 3 Is2 P(R(Si); w)P 2 (S2; w)dw , J92 P(R-1 (S2); w)P 2 (Si; w)dw , 1,92 P(S2; co)P 2 (R(Si); w)dw • Chapter 4. Solutions to the Attitude Determination Problem^ 89 When the radial function of the sensed object is available only over a region, V, on the unit sphere, the objective function is 'Y(R) = 1 Iv p(R(Si);w)p 2 (S2;w)clw 3 [iv P3 (R(Si); w)c1(.0] k Maximizing y(R) solves the attitude determination problem correctly to the extent possible, given the data available. Chapter 5 Experiments Experiments have been carried out on test shapes to solve the attitude determination problem using combinations of the support function, the first curvature function and the second curvature function for convex bodies and the radial function for starshaped sets. The convex body is an ellipsoid, and the starshaped surfaces are two surfaces constructed using spherical harmonics as base functions. Experiments have been conducted using synthesized data, where the orientationbased representations involved are given either analytically or by data sampled from an analytical representation. Let the model be a shape in a standard attitude, either a convex body or a starshaped surface. Rotate the model by a fixed but unknown rotation, Ro , and let the rotated shape be the object that is sensed. The goal is to find R o . Experimental results described here show that the rotation, R o , can be found when the orientation-based representation is given either analytically or by sampled data. The rotation, Ro , also can be found from discrete data sampled at different scales. Experiments also have been conducted with sensed data obtained, via photometric stereo, from real objects. The orientation-based representations of the model still are in known analytical form, while the orientation-based representations of the object are computed from the output of photometric stereo. Experimental results described here show that the unknown rotation, R o , really can be determined based on the theory of Chapter 4. 90 Chapter 5. Experiments^ 91 This chapter is organized as follows. Section 5.1 introduces the test shapes and their orientation-based representations used in the experiments. Section 5.2 discusses the software issues that arose during the experiments. Section 5.3 describes experiments on synthesized data and the results. Section 5.4 describes experiments on real data and the results. 5.1 Experimental Shapes The shapes used in the experiments are an ellipsoid and two starshaped surfaces constructed using spherical harmonics. These shapes are used both in the experiments on synthesized data (Section 5.3) and in the experiments on real data (Section 5.4). In this section, the support function and the curvature functions of the ellipsoid are derived. The radial functions of the starshaped surfaces are readily obtained from the spherical harmonics from which they are constructed. Spherical harmonics have been used before in computational vision [3]. In particular, Schudy and Ballard [70] used spherical harmonics to model the 3-D shape of hearts. Appendix C provides a brief introduction to spherical harmonics. Let Ea b c denote the ellipsoid determined by 2^y 2^z 2 x , , a 2^b 2^c 2^1 Lemma 5.1 (O'Neill [58] page 148.) If M : g = c is a surface in W, then the gradient vector field Vg = E(ag/ax i )Ui (considered only at points of M) is a nonvanishing normal vector field on the entire surface M, where is the i-th unit vector in the coordinate system. Theorem 5.2 The support function of the ellipsoid Ea ,b, c is H(E a ,b, c ; v) = a 2 v? b 2 v3 c 2 v3 , for v = (v 1 , v 2 , v3 ) E R .^(5.1) ^ Chapter 5. Experiments^ 92 Proof^The gradient vector of Ea , b , c is Vg 2(Q, b 3-). Given v (v 1, v 2 , v3 ) E R 3 , let w= 1 ^ (a2vi, b 2 v 2 , c 2 v3 ) . a 2 v1 b 2 v3 c 2 v3 V Substituting w into Vg gives Vg I„— 2 ^ (vi, v 2 , v3 ) a 2 v1 b 2 v3 c 2 v3 V By Lemma 5.1, the normal direction of Ea ,b, c at w is Vg^which is the same direction as determined by (v i , v 2 , v 3 ). Obviously w is on Ea,b,c. By Definition 2.3, w is the normal representation, x(E a , b , c ; v), of the ellipsoid E Since the support function H(C; v) of a convex body C can be obtained from its normal representation x(C; v) by (2.4) as (v, x(C; v)), the support function of the ellipsoid Ea,b,c is ^H(Ea ,b, c ; v)^(v, x(Ea ,b, c ; v))^Va 2 vi^b 2 v3 c 2 v3 . Q.E.D. Recall (2.11) that when the support function H(C; v) of a d-dimensional convex body C has continuous second derivatives, the curvature function Fi(C; v) of C is Fi(C;v) Di(H(C;v)) ^1, 2 , where Di(H) is the sum of all i-rowed principal minors of the Hessian matrix (H 1j ) of H. Thus the curvature functions of Ea, b ,c are obtained. Corollary 5.3 a 2b2 v 3 (Ea,b,c; v) F2(Ea ,b, c ; v) a2c2v3 a 2b2 v i b2 c 2 v3 a 2 c 2 v12 b2c2v2 (a 2 v? b 2 t4 c 2 v3) 3 / 2 a 2b2 c 2( v 2 v2 v2\ 1 + 2 + 3/ (a 2 v?^b 2 v3 c 2 v3) 2 • 2 Chapter 5. Experiments^ (a) front view ^ 93 (b) top view^(c) side view Figure 5.1: Experimental shape: the ellipsoid. The convex surface for the experiments is the ellipsoid E3,5,9. Three side views of the ellipsoid are drawn in Figure 5.1. Its support function and curvature functions are H( E3,5,9 v) Fi(E3,5,9; v) F2 (E3,5,9; v) V9v? 25v3 81v3 , 954v? + 225074 + 2754v3 (9v? + 2574 + 8174)3/2 18225(v? +q+ v3) (9v? + 257)3 + 817)3)2 The spherical coordinate system drawn in Figure 5.2 is used to construct starshaped surfaces. The transformations between Cartesian coordinates and spherical coordinates are x = p sin4cos0 , p = ( x 2 + y 2 + z 2)1/2 y = p sincksin0 , = tan -1^, z = p cos0 , = cos -1 \P The base spherical harmonics used here are^0) and^0) for integers m and n, 0 < n < m. They are defined in Appendix C and are the same as used in [3]. Two starshaped surfaces, SH 1 and SH2 , are constructed for experiments. The surfaces Chapter 5. Experiments^ 94 Figure 5.2: The spherical coordinate system. are nicknamed "peanut" and "pillow". Their radial functions are: peanut : p(S Hi; 0, 0) = 2110,o(s b ^+ 2 U2,0(§6 , 0 ) I = 1 + 3cos 2 (0) pillow : p(S H2; 0, 0) = 4110,0(0, + 2V2,2(0 , 0) = 4 + 3sin(20)sin2(q) • The parametric equations of the object surface, given in terms of the radial function, p(S Hi ; 0,0), and parameters 0 and 0 are x = p(S Hi; 0, 0)sinOcos0 , y = p(S Hi ; 0, 0)simOsin0 , z = p(S Hi; .1,, 0)cosck , i = 1,2. The peanut is a solid of revolution. A side view sketch is shown in Figure 5.3. Three side views of the pillow are shown in Figure 5.4. The pillow is not a solid of revolution. Chapter 5. Experiments^ 95 Figure 5.3: Experimental shape: the peanut. It is a solid of revolution. (a) top view^ (b) front view^(c) side view Figure 5.4: Experimental shape: the pillow. 5.2 Software Issues Recall from Chapter 4 that the problem of attitude determination is equivalent to the optimization problems (4.9), (4.10), and (4.30). Also recall (4.11), (4.12) and (4.27). The objective functions ço(R), O(R) and x(R) are integrals over the unit sphere. Further recall (4.21), (4.22) and (4.34). The objective functions (7,(R),V.,(R) and y(R) are integrals over a region on the unit sphere. Thus an optimization routine and an integration routine are needed. Depending on the optimization scheme, a differentiation routine also may be Chapter 5. Experiments^ 96 needed. A tessellation of the sphere is needed when discretized data are to be represented at points on the sphere. An interpolation routine is needed to determine function values at points other than sample points. Thus the following types of routines are needed for the experiments: 1. Optimization; 2. Integration; 3. Differentiation; 4. Tessellation of the sphere; 5. Interpolation. 5.2.1 Optimization The subroutine NLPQL [67] was chosen because of its recommended good performance. It is an implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions [65, 66]. It handles bounds separately from constraints. It can be used to solve optimization problems with constraints, optimization problems with simple bounds, or unconstrained optimization problems. It requires the gradients of the objective functions or an estimate thereof. An accuracy can be specified to the routine. Convergence is considered to have been achieved if the Kuhn-Tucker conditions (Fletcher [27] page 51) are satisfied to within the specified accuracy or if the objective function can not be improved significantly when the constraints are satisfied to within the specified accuracy. Chapter 5. Experiments^ 97 5.2.2 Integration and Differentiation The ideal integration routine would calculate surface integrals directly on the sphere. Here the integration routines used are QB01AD from Harwell [1] and DBLINT taken from Gerald [30] (pages 238-239), both of which calculate 2D integrals. The surface integrals that define the objective functions are transformed into volume integrals as follows: L 2 is2_ f(W)dl.,/ = jo ir 10 27r f(sinOcosO, sincksinO, cosOsin0d0d0 , f(w)clo) =^ f2ir f(sinOcosO, sinOsinO, cosO)sincbd0d0 . The differentiation routine does simple forward differencing. 5.2.3 Sphere Tessellation There are various ways to tessellate a sphere. Geodesic domes are the most often used in computational vision [3, 36]. The sphere tessellations implemented are based on geodesic domes built from the icosahedron. The following implementation of geodesic domes is from [16]. A more theoretical study is found in [41] and the references therein. Let ^1 +^ 1 a =^, b = ^ ^2T = ^,^5v4^(v,F51/4) The icosahedron is oriented in a three dimensional rectangular coordinate system so that the vertices of the icosahedron are (^0, +a, +b^) , (^+b, 0, +a^) , (^+a, ±b, 0^) . For any triangular facet of the icosahedron, let its vertices be (X 1 , Yl Z1 ), (X 2 , Y2 , Z2 ), , and (X3 , Y3, Z3). Divide the triangle into equilateral triangles whose vertices are Chapter 5. Experiments ^ 98 Figure 5.5: An 8-frequency geodesic dome. (x1 + 0 JX3N-X2 ^JY3--Y2 ^+ TZ2,71-v.ZIL JZ3NZ2) where N is the desired frequency of the geodesic dome and I and J are integers such that 0 < J < I < N. Each of these vertices is then projected onto the unit sphere along the direction from the origin to the vertex. The frequency of the geodesic dome can be chosen based on the need for accuracy. The number of vertices, arcs and facets of a N-frequency geodesic dome are as follows: vertices(N) = 10N 2 + 2 , arcs(N) = 30N 2 , facets(N) = 20N 2 Figure 5.5 shows the 8-frequency geodesic dome. It has 642 vertices, 1920 arcs, and 1280 facets. Chapter 5. Experiments^ 99 5.2.4 Interpolation An interpolation routine is used to interpolate function values when the function is given only on a fixed set of sample points. The interpolation package TOMS ALGORITHM 623 [62, 63] by R.J. Renka is chosen because it is designed to interpolate points on the unit sphere. It constructs a C 1 function defined on the unit sphere that interpolates the data values associated with arbitrarily distributed nodes on the sphere. The interpolation process consists of three steps (Renka [63]): 1. Constructing a spherical triangulation of the nodes 1 ; 2. Estimating a gradient vector using either a local method or a global method; 3. Computing the interpolated value at the desired point P using the data values and gradient estimates at each of the points of the triangle that contains P. The accuracy of the gradient estimation is tested on the support function and the curvature functions of the ellipsoid E3,5,9. The sets of nodes are the sets of vertices of the geodesic domes generated in Section 5.2.3. For a point P on the sphere, the gradient G(P) is assumed to be an element in R 3 that is orthogonal to P. Given a function f , the true gradient was obtained by projecting V f onto the tangent plane at P, i.e., G(P) = V f — (V f, P)P Let Ei be the difference between the true and the estimated gradient vector at node i. Table 5.1 displays \ Eil\r.-_-1 1 Ei 1 2 N (i.e., the root-mean square of the Euclidean norms of gradient estimation errors) for both the local method and the global method. 'The geodesic dome in Figure 5.5 is drawn based on the triangulation generated by the routine. 100 Chapter 5. Experiments^ method H(E3,5,9; u) Fi(E3,5,9; u) F2 (B3,5,9; u) on 20-frequency dome, N=4002 global 0.0029066 0.0382040 0.2251672 local 0.0112057 0.4334782 4.2150756 on 40-frequency dome, N=16002 global 0.0010251 0.0132873 0.0756826 local 0.0028079 0.1096620 1.0701663 Table 5.1: Root-mean square gradient estimation errors. The accuracy of the interpolation is tested on all the functions involved in the experiments. The set of interpolation points is {(sinOcos0, sinOsinO, cos0) :^= i R. 0 = j^j 30'^30 ' = 0, 1,^, 30 } . Table 5.2 and Table 5.3 display the root-mean square and maximum interpolation errors over the interpolation point set for the 20-frequency and 40-frequency geodesic domes respectively. The interpolations use the true gradient, the locally estimated gradient and the globally estimated gradient for H(E3,5,9; u), Fi(E3,5,9; u) and F2(E 3 , 5 , 9 ; u). Since the true gradients of p(SHi ; u), i = 1, 2, can not be calculated easily, interpolations of the two functions use only the estimated gradients. 5.3 Experiments on Synthesized Data When the orientation-based representations appearing in the objective function are given either by analytical expressions or by the values of analytical expressions on a fixed set of sample points, the experiments are said to be based on synthesized data. 101 Chapter 5. Experiments^ method H(E3 , 5 , 9 ; u) Fi(E3 , 5 , 9 ; u) F2(45,9; u) p(S H i ; u) p(SH2 ; u) root-mean-square error true 0.0000044 0.0001283 0.0011730 global 0.0000116 0.0001500 0.0012980 0.0003007 0.0004388 local 0.0000355 0.0009455 0.0094281 0.0000137 0.0000189 maximum error true 0.0000224 0.0009821 0.0078369 global 0.0000855 0.0009900 0.0077944 0.0011137 0.0018455 local 0.0002023 0.0054026 0.0678233 0.0000362 0.0000726 Table 5.2: Interpolation error for the 20-frequency geodesic dome. method H(E3 , 5 ,9 ; u) Fi(E3,5,9; u) F2(E3,5,9; u) P(SHi; u) p(SH2 ; u) root-mean-square error true 0.0000006 0.0000217 0.0002347 global 0.0000021 0.0000277 0.0002711 0.0001472 0.0002093 local 0.0000043 0.0001226 0.0012059 0.0000017 0.0000024 maximum error true 0.0000034 0.0001350 0.0015285 global 0.0000143 0.0001496 0.0015457 0.0004824 0.0008584 local 0.0000263 0.0008814 0.0082720 0.0000052 0.0000074 Table 5.3: Interpolation error for the 40-frequency geodesic dome. Chapter 5. Experiments^ 102 5.3.1 Experimental Settings Let the model be a shape in a standard attitude, either a convex body or a starshaped surface. Rotate the model by a fixed rotation, R o , and let the rotated shape be the object. The goal is to find R o using the orientation-based representations of the model and the object. By the theory in Chapter 4, the rotation, R o , can be found by optimizing functions (p(R), 7,b(R), (p i (R), 0 1 (R), (,o 2 (R), 0 2 (R), x(R), x i (R) and x 2 (R) as defined in (4.11), (4.12), (4.13), (4.14), (4.15), (4.16), (4.27), (4.31) and (4.32). The orientationbased representation of the object can be obtained from that of the model and the rotation Ro. Experiments are divided into three sets, set-1, set-2 and set-3, according to how the representations are given. For set-1 experiments, the orientation-based representations of both the model and the object are given analytically. Thus, function evaluations in optimization are done by directly evaluating the corresponding analytical expressions. For set-2 experiments, the orientation-based representation of one of the model or object is given in analytical form and that of the other is given by discrete samples. Function evaluations are done by interpolating the corresponding discrete functions. For set-3 experiments, representations of both the model and the object are given by discrete samples. Each set of experiments is divided into three groups, group-0, group-1 and group-2, according to which forms of the objective functions are used. Group-0 experiments use functions co(R), '(R) and x(R) as objective functions. Group-1 experiments use w i (R), 01(R) and xi(R), and group-2 experiments use (p2(R), 02(R) and x 2 (R). For the special cases of E3 , 5 , 9 , SH1 and SH2 and rotation Bo , these functions are listed in Table 5.4. Recall the properties of the orientation-based representations, (2.2), (2.12) and (2.17), H(R(C); 4") II(C; R -1 (0) , Fi(R(C); = Fi(C; R-1(0) Chapter 5. Experiments ^is2 103 = H( sP(R) R(E 3,5,9) (A) )F1 (RO E3,5,9)^, group-0 ^2 0 (R) = X(R) = 3= fs2 f s2 p(R(S Hi ); co) p 2 (Ro (S Hi); w)ch.4.) , i = 1,2, r^pr^).w)F1 (E3 5 9 i coi(R) group-1 0 1 (R) xi (R) group-2 H (R(E3 , 5 79 ); w)F2 (Ro (E3 , 5 , 9 );^, to ) r^R^(Rn(F!^ 1 \ --u \ -3,5,9 )): I 17^2 3^ —^ (^ W)C1W f s2 p(R -1 (Ro (S Hi)); w)p 2 (S Hi; co)dw , i = 1, 2, (p2(R) (pf(p, 1P1 \-•-•.' =^f^R^1 j s2 —43 \ —3,5,9 j; Wi-• 02(R) F ( R(^),, =^f TER —3,5,9i; C1-7 /- 2 \^j; JS2 — - \ f^ — s2 X2(R) p(R.9 (S Hi); co) p 2 (R(S Hi); w)dc,.; , i = 1, 2. Table 5.4: The objective functions for group-1, group-2 and group-3 experiments. p(R(S); = p(S ; () . Thus the functions listed in Table 5.4 can be computed from the support function and the curvature functions of E3,5,9 and Ro (E3 , 5 , 9 ), and from the radial functions of SH 1 , SH2 , Ro (SH i ), and Ro (SH2 ). The objective functions for set-1 experiments are listed in Table 5.5. For set-2 experiments, one orientation-based representation involved in 0(R), '(R), and x (R) is given by discrete samples. Suppose H(E 3 , 5 , 9 ; u) is given by a set of discrete samples, i.e., the function value of H(E 3 , 5 , 9 ; 4') is given only at a finite set of points in S 2 . Using interpolation, an estimate of H(E 3 , 5 , 9 ; u) at any point u E S 2 is obtained. Denote the interpolated function by Hs(E3 , 5 , 9 ; u). Similarly, denote the interpolated Fi (E3 , 5 , 9 ; u) and p(S Hi ; u) by Fis(E3 , 5 , 9 ; u) and ps (S Hi; u), respectively, i 1, 2. Each group of experiments in set-2 is divided into two subgroups, group-a and group-b, with 104 Chapter 5. Experiments group-0 set-1 group-1 group-2 cp(R) = fs2 H(E3 , 5 , 9 ;^(w))Fi(Ro(E3,5,9); co)clw z1)(R) = f s2 H(E3,5,9; R -1 (w))F2(Ro(E3,5 ,9); (.0)&0 , X(R) = f s2 p(S^R -1 (w))p 2 (Ro (S Hi); w)clw , i = 1,2, (pi (R) = f s2 H(Ro(E3,5,9); R(w))Fi(E3,5,9;c0)clw , 0 1 (R) = f s2 H(Ro(E3,5,9); R(w))F2(E3,5,9; w)dw , Xi(R) = f s2 p(R o (S Hi); 44)))P 2 ( 911i; cii)d(.4) , i = 1,2, 02(R) = f^H(Ro(E3,5,9); w)F2(E3,5,9; ^(w))dtv , y,2 (R) = f s2 H(Ro(E3,5,9); (.0).Fi(E3,5,9; R 1 (w))th..4., , X2(R) = f s2 p(Ro(S Hi); (4))p 2 (S Hi; R -1 (c.o))dw , i = 1,2. Table 5.5: The objective functions for set-1 experiments. experiments in each subgroup optimizing the corresponding objective functions when the representations of either the object or the model are given by discrete samples. The objective functions for set-2 experiments are listed in Table 5.6. Using the same notation, the objective functions for set-3 experiments are listed in Table 5.7, where the representations of both the object and the model are given by discrete samples. There are three clusters of optimization problems defined in Chapter 4. The first cluster, (4.5), (4.6) and (4.28), are, in general, constrained optimization problems. If the rotation is represented by quaternions, the number of constraints is one, i.e., the length of the quaternion is equal to one. Representing the rotation by the axis-angle triple (0,0, Si) gives the second cluster of optimization problems, (4.7), (4.8) and (4.29), which are optimization problems with bounds. The third cluster, (4.9), (4.10) and (4.30), are unconstrained optimization problems. Since optimization routine NLPQL handles bounds separately from constraints, the axis-angle triple (0, 0, 52) is chosen to represent Chapter 5. Experiments^ 105 cp(R) = fs2 Tk(R) = fs2 Hs (4 5 , 9 ; 11-1(w))F2(Ro(E3,5,9); X (R) fs2 los (S Hi; R -1 (w))p 2 (R o (S Hi); co)dw , i = 1, 2, group-Oa = H 3 (E3 5 9; R -1 (w))Fi (Ro (E3 , 5 , 9 ); ce)du, , , , w)dw , yo(R) = sfs2 H(E3 , 5 , 9 ; R 1 (w))Fis(Ro (E3 , 5 , 9 ); w)dw , group Ob 1 0 (R) = sfs2 H(E3 , 5 , 9 ; R -1 (w))FAR0 (E3 , 5 , 9 ); (.4.,)clu..7 , - - X(R) group-la = A fs2 P(S Hi; R -1 (w))(P s (Ro(S Hi); w)) 2 dw , i = 1, 2, soi(R) = fs2 Hs (Ro(E3,5,9); R(w))Fi(E3,5,9; w)dw 7/11 (R) = fs2 X1 (R) = fs2 ps (Ro(S Hi); R(w))p 2 (S Hi; w)dw , i = 1, 2, II S (RO (E3,5 9); R(W))F2 , set-2 group lb - So1(R) = 4. fs2 H(Ro(E3,5,9); R(w))Fis (E3 , 5 ,9; w)dw , 0 1 (R) = sfs2 H(Ro(E3,5,9); R(w)) fi3 (E 3 , 5 , 9 ; w)dw , Xi(R) = P 2 (R) = 02(R) = ( group-2a fs2 Hs (Ro (E3 , 5 , 9 ); w)Fi(E3,5,9; 1? -1 ((.4.)))dce , f5.2 Hs (Ro (E3 , 5 , 9 ); w)F2(E3 7 5,9; R 1 (w))clo.; , X2 (R) = fs2 ps (Ro (S Hi); w)p 2 (S Hi; R -1 (w))du., , i = 1,2, P 2 (R) = fs2 H(Ro(E3,5,9); w)FAE3,579; R 1 (w))clw 7 02 (R) = fs2 H(Ro(E3,5,9); ^F2 (E3 5,9; R^((w)) (141) X2(R) = fs2 p(Ro (S Hi); w)(ps(S Hi; R -1 (w))) 2^, i = 1, 2. ( group-2b .- fs2 p(Ro(S Hi ); R(w))(ps(S Hi; u..,)) 2 cki) ,i = 1, 2, 7 Table 5.6: The objective functions for set-2 experiments. Chapter 5. Experiments group 0 - 106 co(R) = iS2 H s ( E3, 5,9 ;^(U)))Fi (R° (E3, 5 ,9); w)dw O(R) = fs, Hs (E3 , 5 , 9 ;^(w))F2 (R0(E 3 , 5 , 9 );^, X(R) = fs2 Ps (S Hi; R -1 (w))(ps (Ro(S Hi ); w))2dcv , i = 1, 2, (pi (R) set 3 - group-1 f s2 Hs(Ro(E3,s,9); R(w))Fis (E3 , 5 , 9 ; w)dw , 01(R) = s f s2 H s (Ro(E3,5,9); R(w)) Fl(E3,5,9; w)dw , xi(R) = sf6.2 ps(Ro (S Hi ); R(w))(ps (S Hi ; w)) 2 dw , i = 1,2, = (p2 (R) = 02(R) group 2 - X2(R) = -31- f s2 Hs (R o (E3 , 5 , 9 ); w)F2 (E3,5,9; R - 1 (w))dw , 4 f s2 Hs (Ro(E3,5,9); w)F1(E3,5,9; R -1 (w))cic.o , - s f s2 ps (Ro(S ili); w)(P s (S Hi); R -1 (w))) 2 dw , i = 1,2. Table 5.7: The objective functions for set-3 experiments. rotations in the experiments. The representation of a rotation by a triple (4), 0, SI) is unique within bound [0, r] x [0, 27r] x [0, 7r]. If the bound is extended, the objective functions become periodic but are still well defined. Thus for each experiment, the following three different bounds are given to routine NLPQL: Bound1 : [0, 7r] x [0, 2r] x [0, 7r] , Bound2 : [-40r, 807r] x [-407r,1 607r] x [-407r, 807r] , Bound3 : [ B, B] x[ B,B] x [ B, B] ,B = 3.5 x 10 14 . — — — Bound1 and Bound3 correspond to the second and third clusters of the optimization problems. Bound3 effectively indicates to NLPQL that the variables are unbounded. Bound2 is used to investigate the convergence pattern of the rotation space. Chapter 5. Experiments^ 107 When R is represented by a triple (0,0, 1), the rotation matrix corresponding to R(q, 0, S2) can be obtained by the following theorem. Thus the values of R(w) and R -1 (w) in the objective functions can be computed via the rotation matrix of R. Theorem 5.4 (Kanatani [39] page 203.) The matrix representing a 3-D rotation by angle 52 around unit vector n = (n i , n 2 , n 3 ) is cos52 +74(1 — cos1)^n i n 2 (1 — cos52) — n 3 sinS2 n i n 3 (1 — cosSI) + n 2 sinf2 n 2 7/ 1 (1 — cos52) + n 3 sinS2^cos/ +74(1 — cos12)^n 2 n 3 (1 — cosft) — n i sinfI n 3 n 1 (1 — cosf2) — n 2 sint2 n 3 n 2 (1 — cosS2) + n i sinft^cosf2 + n3(1 — cosft) _^ _ 5.3.2 Experimental Results For each experiment, three different bounds, Boundl, Bound2 and Bound3, are given to routine NLPQL, where Bound3 effectively indicates to NLPQL that the variables are unbounded. For each given bound, each optimization process was tried with 4096 different initial guesses as starting point. These input points are (i x 0.1,j x 0.2,k x 0.1) , i,j,k = 1,3,5,...,31. The rotation, R o , for the experiments is (0o, 00, 11:1) = (116,70,7r/4) = (0.5235987758, 0.3490658504, 0.7853981635) . Figure 5.6 shows the rotated surfaces for E3,5,9, SHi , and SH2 . In the figure, the shapes in thick gray are the models in standard attitude and the shapes in solid black are the models rotated by Ro. One way to evaluate the optimization results is to check the number of the initial guesses from which the global optimal point, R 0 , is found by the optimization process, under a given bound. Table 5.8, Table 5.9 and Table 5.10 list these numbers for set-1, set-2 and set-3 experiments, respectively, under the three bounds. 108 Chapter 5. Experiments^ (a) the ellipsoid ^ (b) the peanut ^ (c) the pillow Figure 5.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). The results of the optimization fall into three categories: 1. The rotation Ro is found; 2. A boundary point of the feasible region is reached before the rotation R o is found; 3. The number of line searches in NLPQL exceeds the specified limit. The distribution of the first two categories over the initial guesses suggests connected regions within the feasible region, which may assist selecting favorable initial guesses to obtain R o . The second category does not apply to optimization under Bound3. When the third category happens to an initial guess, the result is often very close to the optimal point. This category can be reduced by adjusting the parameters given to NLPQL. Another way to evaluate the optimization results is to measure how close the rotation found by optimization is to the rotation R o . However, there are three difficulties: 1. No metric in rotation space is commonly agreed upon in computational vision to Chapter 5. Experiments^ 109 measure how close two rotations are to each other; 2. Two very different triples may represent the same rotation due to periodicity; 3. Two triples that represent different rotations may correspond to the same attitude for an object that possesses symmetries. To evaluate how close a rotation R = (OA SI) is to another rotation R o = (00,0o, flo), the difference, (I 00 — 0 1,1 00 - 0 Id C2o - Q I) between the two triples representing the two rotations can be considered as a measurement. The rotation angle, Sr, of R0 R -1 can also be used to measure the closeness between R and Ro . Tables 5.11-5.16 list the differences between (0 0 , 00 , s20) and the triples, (0, 0, 52), found by optimizations with initial guess (0.1, 0.2, 0.9). The corresponding values of Sr are also listed. The choice of (0.1, 0.2, 0.9) is based on no particular consideration except that the optimization results then all are within the bound, [0, 71 ] x [0, 27] x [0, r], - thus avoiding the issue of periodicity. The results listed under the heading of x(R), Xi(R) and x2(R) are from the experiments on the pillow. The results on the peanut are not listed because the peanut has rotational symmetries with infinitely many rotations representing the same attitude. A way to visualize the optimization result is to superimpose the rotated model onto the object. As examples of the results of set-1 experiments, the results of minimizing so(R) and 0(R) on E3,5,9 with initial guess (0.1, 1.4,1.3) under Boundl are shown in Figure 5.7 and Figure 5.8, respectively. The results of maximizing x(R) on the peanut and the pillow with the same initial guess, (0.1,1.4, 1.3), under the same bound, Boundl, are shown in Figure 5.9 and Figure 5.10, respectively. As examples of the results of set-3 experiments, the results of minimizing co(R) and '0(R) on E3 5,9 , with initial guess (0.1,4.2,1.7) under Bound3 are shown in Figure 5.11 and Figure 5.12, respectively. The Chapter 5. Experiments^ 110 E3,5,9 set-1 Boundl Bound2 Bound3 SH1 SH2 (,o(R) 71)(R) x(R) x(R) group-0 1178 860 1814 1485 group-1 1180 1070 1814 1588 group-2 1163 982 1814 1589 group-0 3910 3052 3882 3756 group-1 3909 3234 3879 3795 group-2 3905 3069 3884 3777 group-0 4096 3918 4096 4087 group-1 4096 4065 4096 4064 group-2 4095 4070 4096 4064 Table 5.8: Results of set-1 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. results of maximizing x(R) on SH1 and 8112 with the same initial guess under the same - bound are shown in Figure 5.13 and Figure 5.14, respectively. In the figures, the shapes in thick gray are the models and the shapes in solid black are the shapes obtained at different iterations. Chapter 5. Experiments ^ 111 E3,5,g set-2 Boundl Bound2 Bound3 SH1 SH2 (,o(R) O(R) X(R) X(R) group-Oa 1181 863 1818 1482 group-Ob 1178 860 1814 1487 group-la 1175 1070 1816 1590 group-lb 1179 1071 1813 1588 group-2a 1163 981 1814 1588 group-2b 1162 963 1821 1589 group-0a 3897 3092 3879 3775 group-Ob 3894 3074 3475 3751 group-la 3881 3236 3878 3794 group-lb 3908 3226 3886 3805 group-2a 3904 3069 3875 3795 group-2b 3901 3058 3887 3786 group-Oa 4091 4041 4095 4095 group-Ob 4096 4078 4096 4094 group-la 4075 4067 4096 4095 group-lb 4095 4034 4096 4069 group-2a 4095 4046 4096 4095 group-2b 4094 3925 4095 4096 Table 5.9: Results of set-2 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. Chapter 5. Experiments^ 112 E3,5,9 set-3 Boundl Bound2 Bound3 SHi SH2 co(R) O(R) X(R) x(R) group-0 1184 863 1819 1481 group-1 1177 1068 1815 1591 group-2 1162 971 1821 1590 group-0 3889 3096 3874 3775 group-1 3905 3229 3876 3799 group-2 3901 3058 3890 3792 group-0 4092 4096 4095 4096 group-1 4096 4028 4096 4094 group-2 4096 4094 4095 4096 Table 5.10: Results of set-3 experiments: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. Chapter 5. Experiments set group ^ bound Boundl set-1 group-0 Bound2 Bound3 113 function 1 co - 95 1^1 Bo - 0 1^1 520 - f2 1 li* o(R) 0.001292^0.000331^0.000496 0.001114 0(R) 0.002772^0.000969^0.002783 0.003521 X(R) 0.000006^0.000120^0.000003 0.000045 co(R) 0.001041^0.000697^0.000804 0.001163 /(R) 0.002793^0.000987^0.002765 0.003518 X(R) 0.000032^0.000019^0.000007 0 (p(R) 0.001041^0.000697^0.000804 0.001163 0 (R) 0.002793^0.000987^0.002765 0.003518 X(R) 0.000032^0.000019^0.000007 0 Table 5.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. set group bound Boundl set-1 group-1 Bound2 Bound3 function ( 00 - 0 1^1 00 - 0 1^1 520 - 521 Sr co1(R) 0.000035^0.000003^0.000034 0.000045 01(R) 0.000000^0.000001^0.000002 0 X1(R) 0.000004^0.000041^0.000022 0 (p 1 (R) 0.000147^0.000305^0.000264 0.000310 01(R) 0.000002^0.000008^0.000005 0 X1(R) 0.000057^0.000095^0.000028 0.000063 co 1 (R) 0.000147^0.000305^0.000264 0.000310 01(R) 0.000002^0.000008^0.000005 0 X1(R) 0.000057^0.000095^0.000028 0.000063 Table 5.12: The comparisons between Ro and the estimated rotations from initial guess (0.1, 0.2, 0.9) by set-l/group-1 experiments. Chapter 5. Experiments set group ^ bound Boundl set-1 group-2 Bound2 Bound3 114 function 1 00 - 0 1^1 00 - 0 1^I 9 0 - 9 1 9* ca 2 (R) 0.003893^0.001203^0.001635 0.003427 02(R) 0.018105^0.001630^0.009638 0.016824 X2(R) 0.000042^0.000082^0.000005 0.000045 cp 2 (R) 0.003915^0.001185^0.001622 0.003435 zk 2 (R) 0.018106^0.001641^0.009647 0.016830 X2( R) 0.000019^0.000054^0.000011 0 (P2(R) 0.003915^0.001185^0.001622 0.003435 0 2 (R) 0.018106^0.001641^0.009647 0.016830 X2 ( 0.000019^0.000054^0.000011 0 R) Table 5.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. set group bound Boundl set-3 group-0 Bound2 Bound3 function 1 0o - 0 1^1 00 - 0 1^1 9 0 - 9 1 9* co(R) 0.001034^0.000657^0.000998 0.001298 0(R) 0.002665^0.001086^0.002973 0.003632 X(R) 0.000084^0.000468^0.000107 0.000219 (p(R) 0.000718^0.000997^0.001358 0.001514 '(R) 0.002678^0.001104^0.002956 0.003624 X(R) 0.000051^0.000384^0.000109 0.000190 (p(R) 0.000718^0.000997^0.001358 0.001514 b(R) 0.002678^0.001104^0.002956 0.003624 X(R) 0.000051^0.000384^0.000109 0.000190 Table 5.14: The comparisons between Ro and the estimated rotations from initial guess (0.1, 0.2, 0.9) by set-3/group-0 experiments. Chapter 5. Experiments set group ^ bound Boundl set-3 group-1 Bound2 Bound3 115 function I co - 0 1^1 00 - 0 I^1 9 0 - 9 1 9* Sol(R) 0.000258^0.000213^0.000227 0.000313 zk i (R) 0.000155^0.000138^0.000098 0.000161 xi (R) 0.000106^0.000583^0.000081 0.000249 (Pi (R) 0.000273^0.000192^0.000231 0.000319 01(R) 0.000149^0.000125^0.000087 0.000155 x i (R) 0.000139^0.000581^0.000085 0.000261 co 1 (R) 0.000273^0.000192^0.000231 0.000319 0 1 (R) 0.000149^0.000125^0.000087 0.000155 X1(R) 0.000139^0.000581^0.785313 0.000261 Table 5.15: The comparisons between Ro and the estimated rotations from initial guess (0.1, 0.2, 0.9) by set-3/group-1 experiments. set group bound Boundl set-3 group-2 Bound2 Bound3 function I 00 - cb I^10o - 0 I^1 fl o - 52 1 52* CO2(R) 0.002839^0.002202^0.002389 0.003335 02(R) 0.017779^0.002051^0.008529 0.016018 X2(R) 0.000116^0.000764^0.000206 0.000369 (p 2 (R) 0.002977^0.002078^0.002389 0.003393 02(R) 0.017857^0.002041^0.008536 0.016072 X2(R) 0.000077^0.000774^0.000199 0.000361 co 2 (R) 0.002977^0.002078^0.002389 0.003393 02(R) 0.017857^0.002041^0.008536 0.016072 X2(R) 0.000077^0.000774^0.000199 0.000361 Table 5.16: The comparisons between Ro and the estimated rotations from initial guess (0.1,0.2,0.9) by set-3/group-2 experiments. Chapter 5. Experiments^ (a) Initial guess^(b) 2nd iteration 116 (c) 3rd iteration^(d) final result Figure 5.7: Example of the results of set-1 experiments: Minimizing co(R) for E3,5 9 , with initial guess (0.1,1.4,1.3) under Boundl. dr, ' (a) Initial guess^(b) 2nd iteration (c) 3rd iteration^(d) final result Figure 5.8: Example of the results of set-1 experiments: Minimizing b(R) for initial guess (0.1,1.4,1.3) under Boundl. E3 5 9 , , with Chapter 5. Experiments^ (a) Initial guess^(b) 2nd iteration 117 (c) 3rd iteration^(d) final result Figure 5.9: Example of the results of set-1 experiments: Maximizing x(R) for the peanut with initial guess (0.1, 1.4,1.3) under Boundl. (a) Initial guess (b) 2nd iteration (c) 3rd iteration^(d) final result Figure 5.10: Example of the results of set-1 experiments: Maximizing x(R) for the pillow with initial guess (0.1,1.4,1.3) under Boundl. Chapter 5. Experiments^ (a) Initial guess^(b) 2nd iteration 118 (c) 3rd iteration^(d) final result Figure 5.11: Example of the results of set-3 experiments: Minimizing cp(R) for E3,5,9 with initial guess (0.1, 4.2, 1.7) under Bound3. (a) Initial guess^(b) 2nd iteration (c) 3rd iteration^(d) final result Figure 5.12: Example of the results of set-3 experiments: Minimizing 0(R) for initial guess (0.1, 4.2, 1.7) under Bound3. E3 5 9 , , with Chapter 5. Experiments^ (a) Initial guess 119 (b) 2nd iteration^(c) 3rd iteration (d) final result Figure 5.13: Example of the results of set-3 experiments: Maximizing x(R) for the peanut with initial guess (0.1, 4.2, 1.7) under Bound3. (a) Initial guess (b) 2nd iteration (c) 3rd iteration^(d) final result Figure 5.14: Example of the results of set-3 experiments: Maximizing x(R) for the pillow with initial guess (0.1, 4.2, 1.7) under Bound3. Chapter 5. Experiments^ 120 5.3.3 Variational Test Experiments have been conducted on the synthesized models and objects to test the methods in the situations where the orientation-based representations of the synthesized models and objects are given by sampled data with one of the following variations: 1. The sampling rates for the model and the object are different; 2. The sampling data of the object are only given on a hemisphere; 3. For the starshaped surfaces, the choices of origin for the model and the object are different. The objective functions for group-0 of the set-3 experiments are used accordingly. Let Hs•f (E 3 , 5 , 9 ; w) denote the interpolated function from the value of H (E3 , 5 , 9 ; w) at the vertices of the geodesic dome of frequency f . Similar notation applies to Fi(E3 , 50 ; w) and p(S Hi ; w), i = 1,2. The objective functions for experiments using the data sampled at different rates are: p(R)^6 s2 1 3 s2 1 Tr^77,^n n s.2(:\ rj3,50; rt -1(4Fi .12(Ro (E3,50 ) ; ci_ ) ck.„) Hs.2o(E3,50;^( c.4.)))Fp12 00(E3,5,9); w)du , = _ 0(R)^ X(R) = 3 Ise2 16.' 2° (S Hi ; R -1 (w))(ps .12 (Ro (S Hi ); ce)) 2 du; , i = 1,2. Let S 2- denote the hemisphere with z < 0. Let Fis . '(E3 , 5 , 9 ; w) denote the interpolated function from the value of H(E 3 , 5 , 9 ; w) at the vertices of the geodesic dome that belong to S 2- . Similar notation applies to p(S Hi; w), i = 1, 2. The objective functions for experiments using the data sampled on the hemisphere are: pp(R) = 1 ^ Is e H s (E3,5,9;^(w))Fr - (Ro(E3 , 5 , 9 ); w)dw , Chapter 5. Experiments^ o(R) =^is2 Hs(E , , 3 5 9; 121 R -1 (w))Fr - (Ro(E3,5,9); w)dw , X(R) = L_ p s (S Hi; -11-1 ( 0)))(Ps.z- (Ro(S Hi); (-0)) 2 , i = 1, 2. Each optimization process proceeded with 4096 initial guesses under Bound3. Table 5.17 presents the number of the initial guesses from which the optimal point R o is found. Suppose the origin of the coordinate system for the object is located at position T in the coordinate system for the model, where T is a 3-D vector. Let ps• T (S Hi ; w) denote the interpolated function from the value of p(T (S Hi); w), where p(T (S Hi ); w) is the radial function of SHi with respect to T. The objective functions for experiments with different choices of origin are: I X(R) = 31 s 2 ps (S Hi; R -1 (w))(ps (T(R o (S Hi )); w)) 2 , i = 1,2. The vectors used in the experiments are listed in Table 5.18 along with indications about whether they are inside the objects. With each choice of the origin, the optimization process was tried with the 4096 initial guesses under Bound3. Table 5.19 lists the number of initial guesses that lead the optimization converge to the optimal point R o . The optimizations fail to converge to R o for the peanut when T3 and T4 are chosen and for the pillow when T4 is chosen. This is because T3 is outside the peanut, T4 outside the kernel of the peanut' and T4 outside the pillow. With the 4096 initial guesses, the optimizations converge to the same point for the same choice of vector T and the same object. Like in Section 5.3.2, differences between (0 0 , 00, It o ) and the triples, (0, 0, It), found by the optimizations with initial guess (0.1, 0.2, 0.9) are listed in Table 5.20. The corre2 Let q = 1.058436335 and 0 = 4. The point on the surface of the peanut determined by (0, 0) is T' = (0, 1.499999999, 0.8436918116). The line segment T'T 4 intersects the xy-plane at (.0569588428, 1.272164628, 0), which is outside the peanut. Chapter 5. Experiments^ 122 E3,5,9 SH1 SH2 Experiments (p(R) b(R) X(R) X(R) different sampling rates 4085 4070 4095 4095 sampling on half sphere 4095 3985 4096 4095 Table 5.17: Results of testing different sampling rates and hemisphere sampling: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. vectors inside the peanut inside the pillow Ti. = (0.3, 0.3, 0.7) yes yes T2 = (0.5, —0.7, 0.4) yes yes T3 = (0.7,1.0,0.3) no yes T4 = (0.3,0.3, —3.6) yes no Table 5.18: Different choices of origin used in the experiments. sponding rotation angles, 52*, of the rotation Ro R - 1 are also listed. The results on the peanut are not presented because the peanut has rotational symmetries with infinitely many rotations representing the same attitude. To visualize the optimization result, matchings at different iterations from initial guess (0.1,4.2,1.7) are drawn. Figures 5.155.18 show the results for experiments using data sampled at different sampling rates. Figures 5.19-5.22 show the results for experiments using data sampled over half sphere. Figures 5.23-5.27 show the results for experiments using data sampled with different choices of origin. In the figures, the shapes in thick gray are the models and the shapes in solid black are the shapes obtained at different iterations. 123 Chapter 5. Experiments^ X(R) SHi SH2 T1 = (0.3, 0.3, 0.7) 4096 4096 T2 = (0.5, -0.7, 0.4) 4096 4096 T3 = (0.7, 1.0, 0.3) 0 4096 T4 = (0.3, 0.3, -3.6) 0 0 Choice of origin Table 5.19: Results of testing the different choice of origin: the number of initial guesses out of the 4096 initial guesses converging to the optimal point. experiment function 100 - 01 1 00 -0 1 1 9 0 -9 1 9* (p(R) 0.000746 0.000914 0.001287 0.001451 b(R) 0.002660 0.000996 0.002903 0.003568 X(R) 0.000051 0.000375 0.000114 0.000190 co(R) 0.011209 0.003319 0.015578 0.017868 71) ( R ) 0.013292 0.005738 0.012407 0.016240 X(R) 0.000115 0.000314 0.000073 0.000167 origin is at T1 for SH2 x(R) 0.041500 0.106776 0.027117 0.056632 origin is at T2 for SH2 x(R) 0.020306 0.082305 0.022585 0.042571 origin is at T3 for SH2 x(R) 0.050782 0.044203 0.033828 0.053769 different sampling rate sampling on half sphere Table 5.20: The comparisons between R0 and the estimated rotations from initial guess (0.1,0.2,0.9) by experiments using variational testing data. Chapter 5. Experiments^ (a) Initial guess^(b) 2nd iteration 124 (c) 4th iteration^(d) final result Figure 5.15: Example of the results of variational tests: Minimizing co(R) for E3 5,9 , with initial guess (0.1,4.2,1.7) using data sampled at different sampling rates. (a) Initial guess^(b) 2nd iteration (c) 5th iteration^(d) final result Figure 5.16: Example of the results of variational tests: Minimizing 5(R) for initial guess (0.1,4.2,1.7) using data sampled at different sampling rates. E3 5,9 , with 125 Chapter 5. Experiments^ (a) Initial guess^(b) 1st iteration (c) 2nd iteration^(d) final result Figure 5.17: Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1,4.2,1.7) using data sampled at different sampling rates. (a) Initial guess ^ (b) 4th iteration ^ (c) 8th iteration^(d) final result Figure 5.18: Example of the results of variational tests: Maximizing x(R) for the pillow with initial guess (0.1,4.2,1.7) using data sampled at different sampling rates. Chapter 5. Experiments^ (a) Initial guess^(b) 2nd iteration 126 (c) 4th iteration^(d) final result Figure 5.19: Example of the results of variational tests: Minimizing w(R) for E3 5 9 , , with initial guess (0.1,4.2,1.7) using data sampled on half sphere. (a) Initial guess^(b) 3rd iteration (c) 6th iteration^(d) final result Figure 5.20: Example of the results of variational tests: Minimizing 7/)(R) for initial guess (0.1,4.2,1.7) using data sampled on half sphere. E3 5 9 , , with 127 Chapter 5. Experiments^ (a) Initial guess^(b) 1st iteration (c) 2nd iteration^(d) final result Figure 5.21: Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1,4.2,1.7) using data sampled on half sphere. (a) Initial guess (b) 3rd iteration (c) 6th iteration^(d) final result Figure 5.22: Example of the results of variational tests: Maximizing with initial guess (0.1,4.2,1.7) using data sampled on half sphere. x(R) for the pillow Chapter 5. Experiments^ (a) Initial guess^(b) 1st iteration 128 (c) 2nd iteration^(d) final result Figure 5.23: Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1,4.2,1.7) using data sampled with new origin T 1 . (a) Initial guess^(b) 1st iteration (c) 2nd iteration^(d) final result Figure 5.24: Example of the results of variational tests: Maximizing x(R) for the peanut with initial guess (0.1, 4.2,1.7) using data sampled with new origin T2. Chapter 5. Experiments (a) Initial guess ^ ^ (b) 2nd iteration 129 ^ (c) 3rd iteration^(d) final result (R) for the pillow Figure 5.25: Example of the results of variational tests: Maximizing X with initial guess (0.1,4.2,1.7) using data sampled with new origin T 1 . (a) Initial guess ^ (b) 2dn iteration ^ (c) 4th iteration^(d) final result (R) for the pillow Figure 5.26: Example of the results of variational tests: Maximizing X with initial guess (0.1,4.2,1.7) using data sampled with new origin T2. (a) Initial guess ^ (b) 2nd iteration ^ (c) 4th iteration^(d) final result Figure 5.27: Example of the results of variational tests: Maximizing X with initial guess (0.1,4.2,1.7) using data sampled with new origin T3. (R) for the pillow Chapter 5. Experiments^ 130 5.4 Experiments on Real Data 5.4.1 Experimental Settings The three experimental shapes defined in Section 5.1 and used in experiments described in Section 5.3 were custom fabricated as real solid objects of polyvinyl-chloride using automated, numerically controlled milling machine. The ellipsoid was machined from numerical data derived from its three axis lengths. The starshaped objects were machined from numerical data sampled from their radial functions. A fourth object, a sphere, was machined from the same material to serve as a calibration object for photometric stereo. Photometric stereo was used to obtain surface gradients [74] and the principal curvatures [77]. Photometric stereo uses reflectance data obtained from the calibration sphere to determine surface gradient, (p, q), at each visible point. At the same time, the partial derivatives of the reflectance map are determined. Photometric stereo then combines the partial derivatives of the intensity with the partial derivatives of the reflectance map to estimate the surface Hessian matrix. Combining the Hessian and the gradient determines the principal curvatures, k 1 and k 2 . Three images of each object are taken under three different lighting conditions with the same imaging geometry. The visible hemisphere is the half sphere with z < 0, denoted as 8 2- . The attitude of the objects with respect to the camera is set manually. The object is homothetic to its model in the standard attitude, subject to an unknown rotation R o , an unknown translation and an unknown scaling. The goal of the experiments is to determine the rotation, R o . Images of the ellipsoid for attitude determination using the combination of the support function and the curvature functions are shown in Figure 5.28. Images of the peanut and the pillow for attitude determination using the the radial function are shown in Figure 5.29 and Figure 5.30, respectively. 131 Chapter 5. Experiments^ (a) first light source (b) second light source (c) third light source Figure 5.28: Images of the ellipsoid under three light sources. 132 Chapter 5. Experiments^ (a) first light source (b) second light source (c) third light source Figure 5.29: Images of the peanut under three light sources. Chapter 5. Experiments^ 133 r (a) first light source (b) second light source (c) third light source Figure 5.30: Images of the pillow under three light sources. Chapter 5. Experiments^ 134 In the experiments, the gradient, (p, q), determines the mapping from sensed surface point to the point on the sphere as: (x, y, z) E C^u = vp2 1 q2 + 1 x (p, q, —1) E^S 2- . The principal curvatures, k 1 and k 2 , determine values for the first and second curvature functions as: Fi(C ; u) = ^1 1^1 + 172- , F2(C ; u) = 1 x 70-2- • The coupled depth/slope method by Harris [34] was used to reconstruct depth from gradient and obtain the relative height z of each surface point (x, y, z). Then the radial function was computed as the distance from a fixed point inside the kernel of the object to each visible surface point. The radial function does depend on the choice of this fixed point. By convention, the origin of the object coordinate system is taken to be the center of gravity of the object, whenever possible. Since surface data are acquired from a single viewpoint, the curvature functions and the radial function are not known over the entire sphere. Thus the objective functions (,-(3 R , if) (R) and 7(R) defined in Equation (4.19), (4.20) and (4.34) are used. The objects were arranged in such a way that the region over which the orientation-based representations are available is the hemisphere S 2- . Since the ellipsoid satisfies the conditions set in Chapter 4 the objective functions CO(R) and 71)(R) can be approximated by R and zP(R). Thus the objective functions for the real data experiments are: (7)(R) =^s f s2_ H (R(E 3 , 5 , 9 ); w) Fi (Ro (E3 , 5 , 9 ); w) du; [!- f s2_ H(R(E3 , 5 , 9 ); w) F1 (R(E3 , 5 , 9 ); w) cludi f s2_ H(R(E3,5,9); w) F2 (Ro(E3,5,9); w) dw 0(R) =^ f s2_ H(R(E3 , 5 , 9 ); w) F2 (R(E3 , 5 , 9 ); w) clw]i 1 fs .._ p(R(S Hi ); x) p 2 (R0 (S Hi ); x)dx , i^= 1, 2. X(R) = 3^ [fs2_ p3 (R(SHi); x)dx] ^ ) Chapter 5. Experiments ^ 135 5.4.2 Experimental Results In the experiments, the optimization process was executed 4096 times, each time corresponding to a different initial guess for object rotation. The bound given to NLPQL is Bound3 (of Section 5.3.2), which effectively makes a constrained optimization into an unconstrained optimization. All the initial guesses converged to points with the same function values of CO(R), TP(R) or '(R) and with the same object attitude. Thus, for the objects tested, the method is robust with respect to the initial guess. The attitude of the sensed object is established manually for each experiment. The true rotations of the objects with respect to their standard attitudes also are estimated manually. These estimated rotations are used as rough measures of accuracy to evaluate the rotations found by the optimization process. One way to evaluate the optimization results is to compare the rotation found by optimization with the estimated a priori rotation matrices. This approach is feasible for objects that have few symmetries. The ellipsoid, E3,5,9, has few symmetries since its three axes all are different. The pillow also has few symmetries. When an object is highly symmetric, like the peanut, it is difficult to evaluate the optimization results by comparing rotation because different rotations correspond to the identical object attitude. Table 5.21 presents the estimated a priori rotation, R o , for the ellipsoid imaged in Figure 5.28 and the rotations, R 1 and R2, found by minimizing, respectively, (75(R) and 0(R). Also presented in the table are the matrices R o RT 1 , i = 1, 2, and their rotation angles. Table 5.22 presents the same material for the pillow imaged in Figure 5.30. The rotations found by the optimizations are either the corresponding matrix in the two tables or that matrix multiplied on the right by a matrix corresponding to a reflection about one or more symmetry axis the object possesses. These matrices all define the same attitude for the given objects. 136 Chapter 5. Experiments The estimated a priori rotation for the ellipsoid 0 -0.4975121 0 R0 in Figures 5.28: The rotation found by minimizing (7(R): The rotation found by minimizing V(R): 1 -0.8674570 0.8674570 -0.4975121 0 0 0.1771714 -0.4824572 -0.8578143 Ri = -0.1338156 0.9750404 0.8516999 -0.5066563 0.2045539 0.0863366 0.0555034 -0.5356140 -0.8426369 R2 -= Ro Rr l = RoRV = 0.0083401 0.8441571 -0.5360310 0.9984237 0.0227239 0.0513206 0.9841453 0.0157715 -0.1766613 0.0082621 0.9908807 0.1344883 0.1771714 -0.1338156 0.9750404 0.9974258 0.0450055 -0.0558238 -0.0454001 0.9989519 -0.0058206 0.0555034 0.0083401 0.9984237 the angle of Ro RT 1 = 0.2239258 the angle of Ro RV = 0.0721171 Table 5.21: The comparison between the estimated a priori rotation for the ellipsoid and the rotations found by optimizations on real data. Chapter 5. Experiments 137 The estimated a priori rotation^for^pillow^in Ro = Figure 5.30: The rotation, R 1 , found by maximizing y(R): R1 = RoRT 1 = -0.5074230 -0.5061200 0.6973984 0.5418145 0.4419271 0.7149388 -0.6700440 0.7406369 0.0499792 -0.5364304 -0.4966460 0.6823380 0.5150653 0.4478123 0.7308707 -0.6685434 0.7435098 0.0155850 0.9994210 0.0217053 -0.0262020 -0.0222971 0.9994980 -0.0225070 0.0257003 0.0230782 0.9994033 the angle of Ro RT 1 = 0.0409629 Table 5.22: The comparison between the estimated a priori rotation for the pillow and the rotations found by optimizations on real data. A way to visualize the optimization result is to superimpose the rotated model onto the image of the object. As examples, the results of minimizing (7(R) and (R) with initial guess (0.1, 0.2, 0.1) are shown in Figure 5.31 and Figure 5.32, respectively. The results of maximizing (R) for the peanut and the pillow with the same initial guess are shown in Figure 5.33 and Figure 5.34, respectively. In the figures, the black and white shows the silhouette of the object and the wire frame shape in gray is the rotated model. Chapter 5. Experiments 138 (a) initial guess. (b) 1st iteration. (c) 3rd iteration. (d) 6th iteration. (e) 8th iteration.^(f) 12th (the last) iteration. Figure 5.31: Example of the results of real data experiments: Minimizing 7, (R) for the - ellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1). Chapter 5. Experiments ^ 139 (a) initial guess.^(b) 2nd iteration. (c) 3rd iteration. ^(d) 4th iteration. (e) 8th iteration.^(f) 13th (the last) iteration. Figure 5.32: Example of the results of real data experiments: Minimizing '(R) for the ellipsoid imaged in Figure 5.28 with initial guess (0.1, 0.2, 0.1). Chapter 5. Experiments^ (a) initial guess. 140 (b) 1st iteration. (c) 2nd iteration.^(d) 5th iteration. (e) 7th iteration. (f) 9th (the last) iteration. Figure 5.33: Example of the results of real data experiments: Maximizing T(R) for the peanut imaged in Figure 5.29 with initial guess (0.1,0.2,0.1). 141 Chapter 5. Experiments^ (a) initial guess. (b) 2nd iteration. (c) 3rd iteration. (d) 7th iteration. (e) 10th iteration. (f) 14th (the last) iteration. Figure 5.34: Example of the results of real data experiments: Maximizing X(R) for the pillow imaged in Figure 5.30 with initial guess (0.1, 0.2, 0.1). Chapter 5. Experiments^ 142 5.5 Summary Experiments have been conducted on three experimental shapes. Both synthetic data and data obtained from images of the real objects of the three experimental shapes have been used to test the feasibility of the approaches developed in Chapter 4. Existing numerical routines, the optimization routine NLPQL, the interpolation routine by Robert Renka and the integration routine QB01AD, are utilized. Experimental results have been presented in three ways: 1. Listing the numbers of the initial guesses, out of the 4096 initial guesses, that lead to the optimal point when the objective function is optimized; 2. Listing both the difference between the triples found by optimization and the optimal points and the rotation angle of R0 R -1 , where Ro denotes the optimal rotation and R denotes the rotation found by optimization; 3. Superimposing the rotated model onto the image of the object at different iterations of the optimization process. From the results shown in Tables 5.8-5.10 it can be concluded that slightly more initial guesses converge to the optimal point when using the first curvature function than the second curvature function. It is noted, from Tables 5.11-5.16, that optimizing co(R) and cp 2 (R) estimates the optimal point slightly better than 0(R) and 2 (R), whereas optimizing oi(R) estimates the optimal point slightly better than v, i(R). From Figure 5.31 and Figure 5.32, it can be seen that the combination of the support function and the first curvature function gives a closer estimation of the true attitude of the real object than does the combination of the support function and the second curvature function. Thus the first curvature function performs slightly better than the second curvature function. This may be related to nothing more than the observation that, all else being equal, there Chapter 5. Experiments^ 143 is less uncertainty in the sum of two numbers than there is in their product. This observation is merely anecdotal since, of course, one also needs to take into account properties of the particular numerical optimization routines used. As expected, larger bounds allow more initial guesses converge to the optimal points. This is confirmed by the results shown in Tables 5.8-5.10. The methods are also tested with variations in data: data sampled at different rates for the model and for the objects, data sampled only over a half sphere and, for starshaped objects, data sampled with different choices of origin. The variations do not alter the performance of the methods, i.e., optimization converges to the correct attitude. Chapter 6 Conclusions Orientation-based representations are a compact description of 3-D object shape. A desirable property that all orientation-based representations share is that the object and the representation rotate together. This makes an orientation-based representation wellsuited to the task of attitude determination. This dissertation studies orientation-based representations and solves the attitude determination problem using some of the representations. To conclude, Section 6.1 highlights the major contributions of this research and Section 6.2 points out future research directions. 6.1 Contributions The following orientation-based representations are surveyed: the support function, the normal representation, curvature functions, the distance function, the radial function, the cross sectional measure and the breadth and area functions. The coherent presentation of the mathematical background for these orientation-based representations is a contribution of this thesis. The support function, the first curvature function, the second curvature function and the radial function are used to solve the attitude determination problem. Inequalities that relate the orientation-based representations of more than two sets are used to transform the attitude determination problem into optimization problems for which standard 144 Chapter 6. Conclusions^ 145 numerical methods exist. The transformations are theoretically justified. An important additional property of the optimizations is the fact that the value of the extremum is known a priori. Thus, one can always assess the validity of the solution found by the optimization. The use of the support function on smooth objects and the use of the first curvature function are novel. The first curvature function and the second curvature function are orientation-based representations based on the Gauss map. The Gauss map is one-to-one for smooth strictly convex objects. The support function does not treat smooth objects and polytopes differently. The support function is defined for all points on the unit sphere regardless whether the object is smooth, a polytope or a combination. This is one of the reasons conjectured for its success in polyhedral shape matching [47]. The theorems on mixed volumes that have been used to transform the attitude determination problem into optimization problems apply to all convex bodies. When the objects are strictly convex and smooth, the mixed volumes can be computed via the support function of one object and the curvature functions of another object. A (technically) different treatment is required to develop algorithms for convex objects with developable or planar surfaces. The radial function is one-to-one for starshaped sets. It is defined based on the dilation map. Starshaped objects appear here as a useful generalization of convexity that extends, in a principled way, previous work on shape matching. The radial function also does not treat smooth objects and polytopes differently. The radial function is defined for all points on the unit sphere regardless whether the object is smooth, a polytope or a combination. The theorems on dual mixed volumes that have been used to transform the attitude determination problem into optimization problems apply to all compact starshaped objects. Photometric stereo provides dense, local estimates of both surface orientation and surface curvature. Imaging from an unknown viewpoint determines a visible hemisphere Chapter 6. Conclusions^ 146 of the representation. For smooth, strictly convex objects, matching the visible hemisphere to the full spherical model can be formulated as a single, uniform optimization process. Within this framework, depth need not be represented explicitly. In particular, one does not need multiple viewpoint dependent representations of a modeled object. For starshaped objects, the radial function sensed from a single viewpoint may determine a portion of the representation that is bigger or smaller than a hemisphere. It is proven that the method matches the sensed portion of the representation to the complete representation of the model. The methods are empirically demonstrated for smooth strictly convex objects and (compact) starshaped sets. Good matching results have been obtained. In the implementation described, optimization proceeds using a large number of initial guesses. The correct attitude is found even when there is no a priori knowledge of object attitude. At the same time, optimization benefits from a good initial guess. This suggests that the approach also is well-suited to motion tracking and navigation tasks where the solution at time t can be used as the initial guess at time t At. The method is robust because it is a true 3-D method that employs dense surface data, not just data from 2-D contours or other sparse sets of features. Indeed, for the ellipsoid, the 2-D occluding contour alone does not determine 3-D attitude. The radial function does, of course, depend on the choice of coordinate system origin. For most object shapes, the radial function will not change significantly for (slight) changes in the location of the origin. Intuitively, this suggests that the method is stable with respect to choice of origin, provided the origin is within the kernel of the starshaped set. Experiments on synthetic data support this intuition. Chapter 6. Conclusions^ 147 6.2 Future Directions Precise determination of accuracy and robustness on real data requires more quantitative work. Accuracy assessment must take into account sensor calibration, a priori determination of the "correct" attitude of the presented object and uncertainty in the "shape-from" method used to acquire the raw orientation and curvature data. It would be helpful to agree upon a metric for rotation space to quantify differences between the correct and the estimated object attitude. The approach is intended for recognition, localization and inspection tasks using dense surface data that can be obtained from laser ranging, shape-from-shading or photometric stereo. The work here used data obtained from photometric stereo. It would be useful to experiment with other sources of dense surface data. Because of its flexibility in handling bounds and constraints, the optimization package NLPQL was chosen. Experiments were conducted under different conditions. Now, it is clear that the system can be implemented using unconstrained optimization, in which case significant speed up would be expected. Special hardware may improve efficiency, including that of numerical interpolation. Other possible practical enhancements include one shot uniform resampling of the non-uniformly sampled measured data on the sphere and calculating the required integrations directly on the sphere. Attempts to generalize representations based on convexity to handle more complex shapes have been of limited success. Attempts to generalize based on the theory of starshaped sets may be more successful. One reason is because there is a direct connection between visibility and starshaped set. The object surface visible from a particular viewpoint naturally defines a set starshaped with respect to the robot. One can define the star hull of a non starshaped set analogous to the convex hull of a non convex set [44]. Star hulls are, by definition, starshaped. Matching of the star hull of the visible surface to Chapter 6. Conclusions^ 148 the star hull of the modeled objects fits within the framework of the methods developed in this thesis and thus is a generalization that merits exploration. 149 Bibliography^ Bibliography [1] Advanced Computing Department, AEA Industrial Technology, Harwell Laboratory, Oxfordshire, England. Harwell Subroutine Library Specifications, September 1990. [2] V. I. Arnold. Mathematical Method of Classical Mechanics. Graduate Texts in Mathematics. Springer-Verlag, 1978. [ 3 ] D.H. Ballard and C.M. Brown. Computer Vision. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982. [4] G. A. Beer. Starshaped sets and the Hausdorff m etric. Pacific Journal of Mathematics, 61:21-27, 1975. [5] P. J. Besl. Surfaces in Range Image Understanding. Springer Series in Perception Engineering. Springer-Verlag, New York, 1988. [6] P. J. Besl and R. C. Jain. Invariant surface characteristics for 3D object recognition in range images. Computer Vision, Graphics, and Image Processing, 33:33 80, 1986. - [7] T. Bonnesen and W. Fenchel. Theory of Convex Bodies. BCS Associates, Moscow, Idaho, USA, 1987. Translated from German (Theorie der konvexen KOrper) and edited by L. Boron, C. Christenson and B. Smith. [8] M. Breen. Admissible kernels for starshaped sets. Proceedings of the American Mathematical Society, 82:622 628, 1981. - [9] M. Breen. Clear visibility and the dimension of kernels of starshaped sets. Proceedings of the American Mathematical Society, 85:414 418, 1982. - [10] M. Breen. A characterization theorem for bounded starshaped sets in the plane. Proceedings of the American Mathematical Society, 94:693 698, 1985. - [11] M. Breen. Krasnosel'skii-type theorems. In J. E. Goodman, E. Lutwak, J. Malkevitch, and R. Pollack, editors, Discrete Geometry and Convexity, volume 440 of Annals of The New York Academy of Science, pages 142 146. New York Academy of Sciences, New York, NY, 1985. - [12] P. Brou. Finding the Orientation of Objects in Vector Maps. PhD thesis, The Department of Electrical Engineering and Computer Science, MIT, July 1983. Bibliography^ 150 [13] P. Brou. Using the Gaussian image to find the orientation of objects. The International Journal of Robotics Research, 3(4):89-125, Winter 1984. [14] E. T. Browne. Introduction to the Theory of Determinants and Matrices. The University of North Carolina Press, Chapel Hill, 1958. [15] H. Busemann. Convex Surfaces, volume 6 of Interscience Tracts in Pure and Applied Mathematics. Interscience Publishers Inc., New York, 1958. [16] J.D. Clinton. Advanced structural geometry studies, part I—polyhedral subdivision concepts for structural applications. CR 1734, NASA, 1971. [17] R. C. Evans, Koppelman G, and V. T. Rajan. Shaping geometric objects by cumulative translational sweeps. IBM J. Res. Develop., 31(3):343-360, May 1987. [18] W. Fenchel. On conjugate convex functions. Canadian Journal of Mathematics, 1:73-77, 1949. [19] W. J. Firey. Polar means of convex bodies and a dual to the Brunn-Minkowski theorem. Canadian Journal of Mathematics, 13:444-453, 1961. [20] W. J. Firey. Blaschke sums of convex bodies and mixed bodies. In Proc. Colloquium on Convexity, pages 94-101, Copenhagen Kobenhavns Univ. Mat. Inst., 1965. [21] W. J. Firey. The determination of convex bodies from their mean radius of curvature functions. Mathematika, 14(27):1-13, June 1967. [22] W. J. Firey. Christoffel's problem for general convex bodies. Mathematika, 15:7-21, 1968. [23] W. J. Firey. Local behaviour of area functions of convex bodies. Pacific Journal of Mathematics, 35:345-357, 1970. [24] W. J. Firey. An integral-geometric meaning for lower order area functions of convex bodies. Mathematika, 19:205-212, 1972. [25] W. J. Firey. Some open questions on convex surfaces. In Proceedings of the International Congress of Mathematicians, pages 479-484, Vancouver, 1974. [26] W. J. Firey and B. Griinbaum. Addition and decomposition of convex polytopes. Israel Journal of Mathematics, 2:91-100, 1964. [27] R. Fletcher. Practical Methods of Optimization, volume 2. John Wiley & Sons, Chichester, 1981. Bibliography^ 151 [28] N. Friedland and A. Adam. Automatic ventricular cavity boundary detection from sequential ultrasound images using simulated annealing. IEEE Transactions on Medical Imaging, 8(4):344-353, December 1989. [29] N. S. Friedland and A. Rosenfeld. Compact object recognition using energy-functionbased optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(7):770-777, July 1992. [30] C.E. Gerald. Applied Numerical Analysis. Addison-Wesley Publishing Company, Reading, Massachusetts, 1978. [31] P. R. Goodey and R. Schneider. On the intermediate area functions of convex bodies. Mathematische Zeitschrift, 173:185-194, 1980. [32] B. Griinbaum. Convex Polytopes, volume 16 of Pure and Applied Mathematics. Interscience Publishers, London, 1967. [33] G. H. Hardy, J. E. Littlewood, and G. POlya. Inequalities. Cambridge University Press, Cambridge, 1964. [34] J. G. Harris. The coupled depth/slope approach to surface reconstruction. Technical Report 908, Artificial Intelligence Laboratory, MIT, 1986. [35] B.K.P. Horn. Extended Gaussian Images. Proceedings of the IEEE, 72:1671-1686, 1984. [36] B.K.P. Horn. Robot Vision. The MIT Press, Cambridge, Massachusetts, 1986. [37] B.K.P. Horn and K. Ikeuchi. The mechanical manipulation of randomly oriented parts. Scientific American, 251:100-112, 1984. [38] K. Ikeuchi. Determining attitude of object from needle map using Extended Gaussian Image. A.I. Memo 714, Artificial Intelligence Laboratory, MIT, 1983. [39] K. Kanatani. Group-Theoretical Methods in Image Understanding. Springer Series in Information Sciences. Springer-Verlag, Berlin, 1990. [40] S.B. Kang and K. Ikeuchi. Determining 3-D object pose using the complex Extended Gaussian Image. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 580-585, 1991. [41] C.J. Kitrick. Geodesic domes. Structural Topology, 11:15-20, 1985. [42] S.R. Lay. Convex Sets and Their Applications. Pure and Applied Mathematics, Wiley-Interscience Series of Texts, Monographs, and Tracts. John Wiley & Sons, 1982. Bibliography^ 152 [43] S.Z. Li. Invariant surface segmentation through energy minimization with discontinuities. International Journal of Computer Vision, 5(2):161-194, 1990. [44] Y. Li. St arshaped sets, distance functions, and star hulls. TR 91-4, Department of Computer Science, UBC, Vancouver, Canada, 1991. [45] P. Liang and J.S. Todhunter. Description and recognition of 3-D surface shapes in range image: A differential geometry approach. Technical report, Department of Electrical Engineering, University of Pittsburgh, Pittsburgh, PA, 1987. [46] P. Liang and J.S. Todhunter. Representation and recognition of surface shapes in range images: A differential geometry approach. Computer Vision Graphics and Image Processing, 52:78-109, 1990. [47] J.J. Little. Recovering shape and determining attitude from Extended Gaussian Images. TR 85-2, Department of Computer Science, UBC, Vancouver, Canada, 1985. [48] T. Lozano-Perez. Spatial planning: A configuration space approach. IEEE Transactions on Computers, C-32(2):108-120, February 1983. [49] E. Lutwak. Dual mixed volumes. Pacific Journal of Mathematics, 58:531-538, 1975. [50] E. Lutwak. Volume of mixed bodies. Transactions of The American Mathematical Society, 294:487-500, 1986. [51] T.M. MacRobert. Spherical Harmonics. International Series of Monographs in Pure and Applied Mathematics. Pergamon Press, Oxford, London, 1967. [52] D. Marr. Analysis of occluding contour. Proc. R. Soc. Loud. B., 197:441-475, 1977. [53] D. Marr and H.K. Nishihara. Representation and recognition of the spatial organization of three dimensional shapes. A.I. Memo 416, MIT AI Laboratory, May 1977. [54] P. McMullen and G.C. Shephard. Convex Polytopes and The Upper Bound Conjecture. London Mathematical Society Lecture Note Series 3. Cambridge University Press, London, 1971. [55] Z.A. Melzak. A class of star-shaped bodies. Canadian Mathematical Bulletin, 2:175180, 1959. [56] S. Moni. A closed-form solution for the reconstruction of a convex polyhedron from its Extended Gaussian Image. In Proc. 10th Int. Joint Conf. on Pattern Recognition, pages 223-226, 1990. Bibliography^ 153 [57] V.S. Nalwa. Representing oriented piecewise C 2 surfaces. In IEEE Proc. 2nd Int. Conf. on Computer Vision, pages 40-51, 1988. [58] B. O'Neill. Elementary Differential Geometry. Academic Press, New York, 1966. [59] C.M. Petty. Projection bodies. In Proceedings of the Colloquium on Convexity, pages 234-241, Copenhagen, 1965. [60] A.V. Pogorelov. Extrinsic Geometry of Convex Surfaces, volume 35 of Translations of Mathematical Monographs. American Mathematical Society, Providence, Rhode Island, 1973. [61] M.M. Rao. Measure Theory and Integration. Pure and Applied Mathematics, WileyInterscience Series of Texts, Monographs, and Tracts. John Wiley & Sons, New York, 1987. [62] R.J. Renka. Algorithm 623 interpolation on the on the surface of a sphere. ACM Transactions on Mathematical Software, 10:437-439, 1984. [63] R.J. Renka. Interpolation of data on the surface of a sphere. ACM Transactions on Mathematical Software, 10:417-436, 1984. [64] R.T. Rockafellar. Conjugates and Legendre transforms of convex functions. Canadian Journal of Mathematics, 19:200-205, 1967. [65] K. Schittkowski. The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, part 1: Convergence analysis. Numerische Mathematik, 83:83-114, 1981. [66] K. Schittkowski. The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function, part 2: An efficient implementation with linear least squares subproblems. Numerische Mathematik, 83:115-127, 1981. [67] K. Schittkowski. NLPQL: A FORTRAN subroutine solving constrained nonlinear programming problems. Annals of Operations Research, 5:485-500, 1985/6. [68] R. Schneider. Das Christoffel-problem ffir polytope. Geometriae Dedicata, 6:81-85, 1977. [69] R. Schneider. Boundary structure and curvature of convex bodies. In J. Take and J. M. Wills, editors, Contribution to Geometry, pages 13-59. Proceedings of the Geometry Symposium in Siegen, Birkhiuser Verlag Basel, 1978. Bibliography^ 154 [70] B.B. Schudy and D.H. Ballard. A computer model for extracting moving heart surfaces from four-dimensional cardiac ultrasound data. In Proceedings of sixth conference on computer applications in radiology and computer/aided analysis of radiological images, pages 366-376, 1979. [71] D.A. Smith. Using enhanced spherical images for object representation. A.I. Memo 530, Artificial Intelligence Laboratory, MIT, May 1979. [72] F.A. Valentine. Convex Sets. McGraw-Hill Series in Higher Mathematics. McGrawHill Book Company, New York, 1964. [73] B.L. van der Waerden. Modern Algebra. Frederick Unger Publishing Co., New York, 1949. [74] R.J. Woodham. Photometric method for determining surface orientation from multiple images. Optical Engineering, 19:139-144, 1980. [75] R.J. Woodham Shape analysis. In S. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 1039-1048. John Wiley & Sons, New York, NY, 1986. [76] R.J. Woodham. Stable representation of shape. In Z. W. Pylyshyn, editor, Computational Processes in Human Vision: An Interdisciplinary Perspective, pages 443461. Ablex Publishing Corparation, Norwood, New Jersey, 1988. [77] R.J. Woodham. Surface curvature from photometric stereo. In L. Wolff, S. Shafer, and G. Healey, editors, Physics-Based Vision: Principles and Practice (Vol III: Shape Recovery), pages 121-155. Jones and Bartlett Publishers, Inc., Boston, MA, 1992. Appendix A Symbols Used in the Thesis The left side is defined by the right side ^The d-dimensional real space Rd R d \ {O}^The set of points in R d except the origin A C B^set A is a subset of set B int A^The interior of a set A bd A^The boundary of a set A ker A^The (convex) kernel of a set A dim A^The dimension of a set A hull(A)^The convex hull of a set A S 1^The unit circle in R 2 , also called the Gaussian circle 5 2^The unit sphere in R3 , also called the Gaussian sphere sd-1^ The unit sphere in R d B d^The unit ball in Rd The volume of Bd, rd = r d/ 2 /F(d/2 + 1) wd^ The area of S d-1 , cod = chrd = 27rd/ 2 /F(d/2) det [a l a2^ad}^The d-rowed determinant whose i-th column consists of the coordinates of d-dimensional vectors as in Rd B(A)^The o--algebra of Borel subsets of a set A 155 Appendix B Glossary algebra (Rao [61] page 14.) Let S be a nonempty point set. A class, A, of subsets of S isanalgebraif 1. OEA,SEA; 2. {A, B}CAAUBEAandA—BE A. center Let S be a compact set. A point p in S is called a center of S if each chord of S through p is bisected by p. chord Let S be a compact set. A chord of S is a line segment between two boundary points of S. completely additive set function A set function f () on 8(A) is said to be completely additive if for any two set El, E2 E 13(A) with E 1 n E2 = 0 then f(Ei -I- E2 ) = f (Ei) + f (E2)• convex body (Busemann [15] page 41.) A convex body is a bounded closed convex set not necessarily with interior points. convex hull (Griinbaum [32] page 14.) The convex hull of a set A C Rd is defined as the intersection of all the convex sets in R d which contain A. convex hypersurface (Busemann [15] page 3.) A convex hypersurface in Rd is the boundary of a d-dimensional convex set C in Rd provided it is non-empty and connected. convex set (Griinbaum [32] page 8.) A set C C R d is said to be convex if for each pair of distinct points x, y E C the closed segment with endpoints x and y is contained in C. convex set on Sd -1 (Griinbaum [32] page 10.) A set M on S d-1 is (spherical) convex if for every u, v E M, u +v, M contains the shorter arc of the great circle determined on S d-1 by u and v. elementary symmetric function (van der Waerden [73] page 78.) Let x i , ... , x n be variables. Define al = X1 + X2 + • ' • + Xn ) 0.2 =--- X1X2 + X1X3 + • • • + X2X3 + • • • + X n _iX n , 0 3 = X1X2X3 + X1X2X4 + ' • • + Xn-2Xn—iXn , - 156 Appendix B. Glossary^ 157 0-n = X1X2 • • • Xn The function ca is called the i-th elementary symmetric function of x l ,^, x n . kernel of a set (Lay [42] page 11.) The (convex) kernel of a set S C Rd is the set of all points x E S such that every point of S is visible from x via S. Lipschitz condition A function is f(x) is said to satisfy a Lipschitz condition (with constant a) at a point x o if I f(x) — f (x0) l< a I x—x o l for all x in some neighbourhood of x o . polytope (Griinbaum [32] page 31.) A compact convex set C C R d is called a polytope provided it is the convex hull of a finite set. A d-polytope is a polytope of dimension d. principal minor determinant (Browne [14] page 21 - 22.) Let A be an m x n matrix and let ‘s and t be two positive integers such that s < m, t < n. Let the symbol A 3132 denote the s xt matrix lying in the i 1 , i 2 .^i s rows and in the j 1 , j 2 , . , j t columns of A. This matrix is called a minor matrix of A. If t = .9, so that the minor matrix is square, the determinant , 2122-3t I is called a minor determinant of A. The minor matrix ^is called a principal minor matrix and its determinant a principal minor determinant of A. regular boundary point (Bonnesen-Fenchel [7] page 15.) If C has only one support hyperplane at a boundary point p, p is called regular. regular support plane (Bonnesen-Fenchel [7] page 15.) A support hyperplane of C is said to be regular if it intersects C at only one point. a--algebra (Rao [61] page 15.) Let S be a nonempty point set. An algebra, A, of subsets of S is called a o--algebra if A n E A, n = 1, 2, ...^U`'°_ 1 A„ E A also. simplex (Grilinbaum [32] page 53.) A d-simplex is defined as the convex hull of some d +1 affinely independent points. singular boundary point (Bonnesen-Fenchel [7] page 15.) A boundary point p of a convex body C is said to be singular if C has more than one support hyperplane at p. Appendix B. Glossary^ 158 starshaped set (Lay [42] page 11.) Let S C R d . For points x, y E S, we say x sees y via S (y is visible from x via S) if the line segment Ty lies in S. A set S C Rd is starshaped if there exists a point x E S such that x sees every point of S via S. We say that S is starshaped with respect to x. - strictly convex set A set C C Rd is said to be strictly convex if for each pair of distinct points x, y E C the open segment with endpoints x and y is contained in the interior of C. support of a measure (Rao [61] page 80.) The support of a measure ii defined in space SI is defined as the closed set spt(p) = 52 — U{G : ii(G) = 0 , G open } . support plane (Griinbaum [32] page 10.) Let v E R d . A hyperplane H = {x E R d j (x, v) = a} is said to cut a subset A of Rd if there exist x 1 , x 2 E A such that (x 1 , v) < a and (x 2 , v) > a. A hyperplane H is said to support A if H does not cut A and the distance between H and A is 0. When a hyperplane H that supports A is represented as H = {x E R d ! (x, v) = a} such that (x, v) < a for all x E A, H is referred to as the support hyperplane of A with outward normal v. ^ Appendix C Spherical Harmonics This appendix briefly introduces spherical harmonics. More on spherical harmonics can be found in [51]. Definition C.1 (MacRobert [51] page 69.) Any solution (D m of Laplace's Equation 52 0 52 0 52 0 72(11 axe aye az 2 = ° which is homogeneous, of degree m, in x, y, z 1 is called a solid spherical harmonic of degree 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 a function of 0 and 0 alone. The functions W m, obtained by dividing O m by pm is called a surface spherical harmonic of degree m. A function W m of 0 and 0 is a surface spherical harmonic of degree m if and only if it satisfies the following equation ([51], page 70): 1 54fm m 1^ a (sin0awm)^ 2 m(m + 1)T^ ^ =0. sin0 ao^502^sin20 502 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. Let Pm,o(P)^Pm(it) m ( IL) ,n Pm,n(p) = dn Pu n> 0 . 1 A function such that if each of the variables is replaced by A times the variable, A can be completely factored out of the function, is said to be homogeneous. The power of A which can be factored out of the function is called the degree of homogeneity of the function. 159 Appendix C. Spherical Harmonics^ 160 Po(u)^1 , Pi(it)^ti , Nit)^43/22 — 1) , 2 P3(1)^2(5113 — 3 P) , P4(P)^ (35/2 4 — 30/2 2 + 3) , 8 1 P5 (/2)^— (63/2 5 — 70/2 3 + 1511) , 8 1 P6(1)^— (231/2 6 — 315/2 4 + 105/2 2 — 5) , 16 1 NO^— (429p7 — 693/2 5 + 315/2 3 — 35/2) , 16 1 Ps(it)^i.--- (6435/28 — 1201211 6 + 6930/2 4 — 1260/2 2 + 35) , 8 P9(11) Pio(P) 1 (12155/2 9 — 25740/2 7 + 18018/2 5 — 4620/2 3 + 31511) , 128 1 (46189/2 19 — 109395/2 8 + 90090/2 6 — 30030/2 4 + 3465/2 2 — 63) . 256 Table C.1: The Legendre polynomials of degrees up to 10. Let Trn,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 any surface spherical harmonic kli m,(0, 0) of degree m can be expressed in the form m W m (cb, 0) = Ao Pm (cos0) + E [A n cos(nO) + Bn sin(a)]T„,,,,,,(cos0) , n=1 where 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 series f (0,0) = > {A m Pm (coscb) + t [A m , n cos(nO) + Bm , n sin(n0)]Tni , n (cos0)} m=-.ol^n=1 Appendix C. Spherical Harmonics^ 161 for 0 < 0 < 7r , 0 < 0 < 2r. For integers m and n, 0 < n < m, let Uni ,„(0, 0) = cos(n0)sin n (0)Pm,n(cos0) , Vm ,„(0,0) = sin(nO)sin n (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 given integer M > 0 , and arbitrary constants A n,,,,, Bm ,,, , 0 < n < m < M, a surface in three dimensional space can be constructed as x = p(cb, 0) sine cos0 , y = p(cb, 0) sin 0 sin° , z = p(0, 0) cos0 , where p(0, 0) = Mm E E(Ammum,.(0, 0) + B m=O rt=0 m ,,,V,,,,,(0, 0)) The reason for absolute value being taken is to guarantee the constructed surface is starshaped. Appendix C. Spherical Harmonics^ 162 (a) Uo,o (b) U1,0 (c) U1,1 (d) V1,1 (e) U2,0 (f) U2,1 (g) U2,2 (h) V2,1 (i) V2,2 (j) U3, 0 (k) U3,1 (1) U3,2 (m) U3,3 (n) V3,1 (o) V3, 2 (P) V3 ,3 Figure 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, unto a plane that is perpendicular to (1,1,1).
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Orientation-based representations of shape and attitude...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Orientation-based representations of shape and attitude determination Li, Ying 1993
pdf
Page Metadata
Item Metadata
Title | Orientation-based representations of shape and attitude determination |
Creator |
Li, Ying |
Date Issued | 1993 |
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. |
Extent | 6885109 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-09-05 |
Provider | Vancouver : University of British Columbia Library |
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. |
DOI | 10.14288/1.0051427 |
URI | http://hdl.handle.net/2429/1667 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1993_spring_phd_li_ying.pdf [ 6.57MB ]
- Metadata
- JSON: 831-1.0051427.json
- JSON-LD: 831-1.0051427-ld.json
- RDF/XML (Pretty): 831-1.0051427-rdf.xml
- RDF/JSON: 831-1.0051427-rdf.json
- Turtle: 831-1.0051427-turtle.txt
- N-Triples: 831-1.0051427-rdf-ntriples.txt
- Original Record: 831-1.0051427-source.json
- Full Text
- 831-1.0051427-fulltext.txt
- Citation
- 831-1.0051427.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051427/manifest