Approximate Spatial Reasoning Using Vague Objects by Kevin Kennedy B.A.Sc. in Electrical Engineering University of British Columbia, 1991 A THESIS SUBMU thD IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASThR OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING accept this thesis as THE UNIVERSITY OF BRITISH COLUMBIA December 1993 © Kevin Kennedy, 1993 In presenting this thesis in partial fulfilment 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 I The University of British Columbia Vancouver, Canada Date DE-6 (2/88) J t ’ 31 ABSTRACT A method is proposed for implementing spatial reasoning and spatial knowledge representation on a computer which utilizes a new concept named vague objects. Vague objects are an approximate representation system both for solid objects and for spatial relationships between two or more solid objects. A vague object is a simplified solid ob ject where sharp surfaces are replaced with smooth transitions from the solid to its sur roundings. A vague object can be compared to a cloud with a smoothly varying density that resembles a real solid object. Vague objects can be used to represent spatial concepts as well. A spatial concept is defined as a relation between objects, either solid or vague. Many spatial concepts can be visualized as vague objects, and for simple spatial reasoning, they can be implemented as such. Spatial reasoning with vague objects can be performed using a spatial logic that re sembles Venn diagrams in three dimensions. Spatial reasoning by means of vague objects can be executed sequentially in chains allowing complex spatial descriptions to be evalu ated in a visually understandable fashion. The reasoning system used is reminiscent of fuzzy logic, except that its domain of operation is in three dimensional space. Vague objects simulate some aspects of human spatial reasoning using methods in tended for implementation on a computer. This human-centred approach makes vague objects useful not only for emulating humans but, more importantly, for interacting with them. 11 TABLE OF CONTENTS Abstract ii Table of Contents iii List of Figures vi Acknowledgments vii Chapter 1 Introduction I Chapter 2 Spatial Reasoning and Knowledge Representation 5 2.1 Spatial ReasoningApproaches 6 2.1.1 Algebraic Methods 6 2.1.2 Symbolic Logic 7 2.1.3 Object-Oriented Structures 8 2.1.4 Approximate Spatial Reasoning 8 2.2 OtherRe1atedS’orks 9 Chapter 3 Vague Object Theory 12 3.1 SpatialDataRepresentation 13 3.2 TheDensityFunction 3.3 Creation of,7ague Objects 18 3.4FeaturesofVagueObjects 21 19 3.4.1 Sub-Sampling 22 3.4.2 Scalability 23 3.5 SpatialDoncepts 24 3.5.1 Unary SpL cxl Concepts 25 111 3.5.2 Binary and Ternary Spatial Concepts 3.5.3. Examples of Spatial Concept Shapes 26 3.5.4 The Importance ofShape 3.5.5 Origin of Spatial Concepts 31 26 32 3.6 VagueObjects and SpatialLogic 3.6.1 Venn Diagrams and Spatial Reasoning 33 34 3.6.2 Spatial Concept Evaluation 38 3.6.3 Aggregate Propertiesfor Shape Interpretation 42 3.6.3.1 TotalMass 42 3.6.3.2 Centre of Mass 3.6.3.3 Extent and Volume 43 45 3.6.4 Shape Interpretation 46 3.6.5 Semantics and Combinations of Terms 48 3.6.6 Human Perception, Cognition and Spatial Relationships 48 3.7 FuzzyLogicandVagueObjectReasoning 50 3.7.1 Fuzzy Sets 50 3.7.2 Vague Objects as Three-Dimensional Fuzzy Sets 51 3.8. Graphical Pick Implemented with Vague Objects 3.8.1 Semantic Thickness 53 54 3.8.2 Vague Pick Pointer Shape 56 3.8.3 The Pick Decision 57 3.8.4 Vague Object Pick with Moving Objects 60 3.8.5 Three-Dimensional Pick Operations 61 Chapter 4 Implementation and Verification 63 4.1 Experiment 1: Quantification of Human Spatial Reasoning 64 4.1.1 Experimental Procedure 64 4.1.2 Experimental Results 66 67 4.2 Experiment2: Verification 4.2.1 Experimental Procedure 67 4.2.2 Experimental Results 68 70 4.3 1’urther’.4’ork iv Chapter 5 Conclusions 72 References 74 Appendix 76 V LIST OF FIGURES Figure 1. Constructive solid geometry hierarchy 14 Figure 2. A voxel torus 15 Figure 3. Boundary representation 16 Figure 4. A solid teapot and a vague teapot 17 Figure 5. A surface pit and the vague equivalent 19 Figure 6. A surface protrusion and the vague equivalent 19 Figure 7. The spatial concept shape of “above” (truncated) 27 Figure 8. Spatial concept shapes for “in front” and “to the left” (truncated) Figure 9. The spatial concept shape for “between” 28 Figure 10. The spatial concept shape for “inside” the kettle Figure 11. Some internal localization nouns and associated vague shapes 30 Figure 12. The Venn diagram of the logical AND function 34 Figure 13. Simple spatial reasoning using Venn diagrams 35 Figure 14. Simple spatial reasoning using vague objects 36 Figure 15. Vague shape for “above the rug or table and below the lamp” 37 Figure 16. Vague object AND operation of “inside glass” and “spoon” Figure 17. Reasoning steps for “Is the balloon above the back of the car?” 39 41 Figure 18. Various extent boxes 45 Figure 19. Spatial concept shapes for “above”, “not above”, and “below” 48 Figure 20. Three fuzzy sets over universe of discourse “age” 51 Figure 21. Three vague objects around a car 52 Figure 22. Semantic thickening of some text and a line 55 Figure 23. A vague object pick example 59 Figure 24. Motion blur vague objects 60 vi 29 31 ACKNOWLEDGMENTS I would like to thank my supervisor, Dr. Gunther Schrack for indeed living up to that title by providing me with close guidance and valuable assistance. This project was a chal lenge for both of us since spatial reasoning is not only a new area of computer research, but also new to both of us. I would especially like to thank him for allowing me to use as much of his time as I required. My experimental subjects were also helpful for providing me feedback on the experi mental procedure, and for discussing the complexities of spatial relationships and English prepositions. I was pleased that my research work intrigued them enough that they took an interest and volunteered some useful insights. My friend Michael Sahota was helpful in providing free advice on the inner workings of academia and for giving the occasional pep-talk. Nancy Norman also gets my thanks for her work in the motivation department. Laurel Wellman was an unexpected asset in connecting my work with the philosophies of Wittgenstein. Finally I would like to thank Dr. Peter Lawrence for allowing me to use his high-powered graphics workstation during the off-hours to implement some of my visualization programs. vii CHAPTER 1 INTRODUCTION Spatial reasoning is a relatively new field in computer research which deals with the understanding of solid objects and their interactions in three-dimensional space. Spatial reasoning is used in many diverse applications ranging from natural language understand ing to intelligent computer aided design. Spatial reasoning is commonly performed by ap plying artificial intelligence techniques to the domain of three-dimensional solids and their interrelationships in space. An important problem in spatial reasoning is that of knowledge representation. Knowledge representation is flindamental to most artificial intelligence work. Spatial knowledge representation is especially difficult because of the geometric nature of space. Storing spatial data is relatively straightforward, requiring only the recording of shape and location for all objects in a scene. Spatial data storage is sufficient for image rendering ap plications and simple computer aided design. However, for more sophisticated applica tions like scene recognition, natural language interfaces and design evaluation that require a deeper understanding of a spatial configuration, spatial knowledge representation is re quired. Spatial knowledge includes issues such as tolerances of mechanical connectors, constraints on sailboat design or even the correct positioning of cutlery around a dinner 1 plate. Spatial knowledge appears in many different forms depending on the context in which it is used. This thesis deals with the problem of modelling human spatial reasoning. An attempt is made to understand spatial concepts and problems just as humans do. Spatial relation ships such as “between”, “inside”, and “above” which humans use in communication and reasoning, are modelled in an approximate fashion. The concept of a vague object is in troduced to handle the task of spatial knowledge representation for solid objects and spa tial relationships. A vague object is similar to a solid object, except that there is no sharp distinction be tween the inside and the outside of the object. Vague objects are approximate or fuzzy versions of the solid objects commonly used in spatial data representations. The cloudlike and blurred nature of vague objects renders them suitable for representing human spa tial reasoning and human definitions of common spatial relationships. The purpose of the vague object approach is to provide the basis for a general pur pose spatial reasoning system. The knowledge that can be expressed by vague objects is not at a high level. The role of vague objects in spatial reasoning is analogous to that of Boolean variables in predicate logic. Vague objects provide a fundamental method of en coding spatial information, as well as some simple tools for knowledge manipulation. The claim that vague object reasoning duplicates a human’s spatial reasoning ability is not made. Instead, vague objects provide a basis for representing and manipulating spatial knowledge in a manner resembling human reasoning. 2 The aspects of human spatial reasoning that are captured by vague objects are the ap proximations that humans use in modelling space and describing spatial relationships. Human spatial reasoning is performed with only limited accuracy in size and location in formation. Additionally, terms that humans use to communicate and reason with are quite vague in their definitions and usage. Vague objects directly encode and reason with this approximate information. The process of approximation limits the accuracy of vague ob ject reasoning, but helps to ensure that reasoning problems are more tractable. Since hu mans demonstrate that high accuracy is not a prerequisite for effective spatial reasoning, the vague object approach attempts to simplify such reasoning through approximation. The accent on emulating human knowledge representation is a deliberate attempt to adapt vague object reasoning so that it is effective for human interface applications. Vague objects are an attempt to model spatial knowledge in a human compatible fashion. Thus, vague objects become useful for understanding natural language in situations involv ing spatial reasoning. User interfaces to three-dimensional environments would be much enhanced if they were able to understand human terminology for describing spatial rela tionships. Vague objects could also be used as a semantic basis for any application requir ing a spatial rule base. Spatial rules such as “A must be located adjacent to B” or “if A is behind B then move B forwards” can be encoded simply and directly using a vague object approach. Vague objects allow reasoning to be performed directly with solid model data. A standard spatial model can be reasoned with directly by transforming solid models into 3 their vague object counterparts. There is no requirement to extract spatial knowledge in an ad hoc fashion from a pre-existing standard spatial model. Simple spatial reasoning can also be performed with vague objects directly, reminiscent of Venn diagrams used in Bool can logic. Vague objects are comparable to a three-dimensional extension of fuzzy logic; many of their mathematical fundamentals are similar. The existence of a direct spatial in terpretation of vague object reasoning ensures that the process is transparent and easily understandable, lending strength to the claim of a human-friendly reasoning system. This thesis introduces the theory of vague object representation and reasoning. Chapter 2 discusses current research in spatial reasoning as well as some related research in other disciplines. Chapter 3 explains the concepts and terminology of vague object spa tial reasoning. The relationship between vague objects and fuzzy logic is explored and an example application of vague object reasoning applied to user interfaces is discussed. Chapter 4 describes the computer program that was implemented to test the theory as well as the results of some subjective experiments with human volunteers. Chapter 5 summar izes the benefits of the vague object approach as a method of simple spatial representation and reasoning. 4 CHAPTER 2 SPATIAL REASONING AND KNOWLEDGE REPRESENTATION As an area of research, spatial reasoning is best described as diffuse. There are no journals with the words “Spatial Reasoning” in their titles. There are, however, examples of spatial reasoning to be found in many fields of computer science and engineering. As time progresses, a genuine field of spatial reasoning may emerge. Presently, however, spatial reasoning consist of a diverse set of applications from a variety of disciplines. Spatial reasoning is the application of artificial intelligence (Al) techniques to solve a problem involving a spatial configuration. Spatial reasoning problems are difficult to solve because they involve geometric problems that are loosely constrained and cannot easily be solved with standard Al techniques [Davis, 1990]. Typical spatial reasoning problems in volve either arranging solid objects in some useful fashion or answering some questions about a given spatial configuration. An important term used in spatial reasoning is spatial knowledge representation. Standard methods of solid modelling used for computer aided design or for image render ing do not actually contain much spatial knowledge other than location and orientation, usually suitable for only one application [Wing, 1985]. Other types of spatial information 5 or knowledge are required for many spatial reasoning purposes. For example a map is more useful for planning a car trip if road distances between cities are recorded. The road distances are a useful form of spatial knowledge above and beyond the positional informa tion recorded directly by the map. The type of knowledge representation used is an im portant aspect of any spatial reasoning system. 2.1 Spatial Reasoning Approaches There are four major approaches to spatial reasoning problems. These are: algebraic methods, symbolic logic, object-oriented structures, and approximate representations. 2.1.1 Algebraic Methods Algebraic methods of spatial reasoning involve working directly with the geometry of a spatial reasoning problem. The knowledge representation elements used for these methods are the equations and variables of classical geometry. Spatial problems are posed as systems of equations and constraints which are then solved. As an example, Woodbury and Oppenheim use constraints to represent spatial relationships such as parallelism, ort hogonality and verticality. Propagation methods are then used to provide solutions to the constraint systems, thus solving a spatial problem [Woodbury, 1987]. Algebraic approaches to spatial reasoning are useful for problems dealing strictly with geometry, but do not provide a rich representation system for less mathematical problems. 6 2.1.2 Symbolic Logic Logic-based approaches to spatial reasoning use symbolic logic to solve spatial rea soning problems. For knowledge representation, logic methods use symbols and predi cates to represent spatial relationships. As an example of a symbolic logic approach to spatial reasoning consider the following situation. If it is known that object B is behind object A and also that object C is behind object B, the knowledge that the relationship “behind” is transitive allows the deduction that C is behind A. Stated using symbolic logic: Given: fact: behind(B,A) fact: behind(C,B) (B is behind A) (C is behind B) rule: behind(Y,X) AND behind(Z,Y) implies behind(Z,X) (Transitivity) Deduce: behind(C,A) (C is behind A) Given knowledge about spatial relationships and a set of rules about space, it is poss ible to reason with and draw conclusions about a spatial configuration. Symbolic logic approaches have the advantage of being able to draw on a rich body of symbolic logic work in traditional fields of Al. The previous example of “behind” transitivity, for example, is analogous to the temporal relationship of “after”. In fact much work has been reported exploring the relationships between spatial logic and temporal logic [Abbatti, 1991] [Malik, 1983] [Dutta, 1991] [Davis, 1990]. Symbolic logic ap proaches are also common in natural language understanding problems involving space 7 [Lang, 1991]. Symbolic logic approaches are limited, however, because they do not easily handle the intrinsic geometric problems in spatial reasoning. 2.1.3 Object-Oriented Structures Object-oriented structures are a commonly used method for spatial knowledge repre sentation. Since spatial reasoning deals with solid objects and their relationships in space, an object-oriented approach seems justified. Many object-oriented concepts such as ob jects, inheritance, classes, etc. have a direct analogy in the domain of spatial reasoning. Arbab has developed an object-oriented programming language specifically for spatial rea soning [Arbab, 1989]. Object-oriented structures provide a rich knowledge representation system, however, there is no obvious reasoning method associated with them. 2.1.4 Approximate Spatial Reasoning Several methods of reasoning with space in an approximate manner have been pro posed. These methods deal with uncertainties in spatial relationships by representing them in an approximate fashion. Two examples of approximate spatial reasoning methods are qualitative spatial reasoning and fhzzy logic representation. Qualitative spatial reasoning borrows from an area of AT called qualitative physics. Qualitative physics simplifies prob lems by approximating measured quantities. For example, scalar values can be interpreted as either positive, zero, or negative and motion in one dimension can be simplified to either forwards or backwards. Two examples of qualitative spatial reasoning are Mukerjee and Joe’s qualitative modelling system for space [Mukerjee, 1990] and Faltings’ qualitative analysis of simple mechanisms [Faltings, 1992]. 8 Fuzzy logic representations draw on Zadeh’s fuzzy logic [Zadeh, 1973] to describe spatial relationships. The fuzzy logic approach tries to model the approximate nature of many spatial relationships. An example of this approach is Dutt&s expansion of temporal logic to spatial logic. Dutta uses fuzzy logic sets to describe both temporal and spatial relationships [Dutta, 19911. Approximate spatial reasoning is an attempt to model human spatial reasoning. Since humans reason about space in a vague manner quite successfully, it is hoped that com puters can do the same. A disadvantage of approximate spatial reasoning is that simpli fications and approximations introduce the risk of discarding information which is important for the reasoning process. The method of vague objects presented in this thesis is an example of an approximate spatial reasoning system. In certain aspects, vague object reasoning is analogous to fuzzy logic, except that it is extended to three dimensions. Vague objects have no direct precur sors in the field of spatial reasoning or Al. Vague objects do, however, draw on many ideas produced by works on spatial reasoning and knowledge representation. 2.2 Other Related Works Areas of research other than spatial reasoning have contributed to the theory pres ented in this thesis. The method of vague objects attempts to model human concepts of spatial relationships computationally, therefore it draws on related ideas from the fields of human cognition and the philosophy of language. 9 Researchers in the field of cognition are interested in the study of human perception. es This has led to consideration of the meaning of spatial relational terms. Garnham explor ered the meaning of terms including “in front”, “behind”, “above” and “below”. He discov that terms relating to the vertical direction are different from horizontal directional terms. sic” He also explores the differences between the “deictic” (observer centred) and “intrin (object centred) meanings of some spatial directions [Garnham, 1989]. Finally this work draws on some ideas that have been long considered by philos of ophers. Specifically, vague object reasoning is concerned with the approximate nature spatial concepts and terms. In his work “Philosophical Investigations” Wittgenstein states [Wittgenstein, 1958]: If I tell someone “Stand roughly here” may not this explanation work perfectly? And cannot every other one fail too? But isn’t it an inexact explanation? Yes; why shouldn’t we call it “inexact”? Only let us understand what “inexact” means. For it does not mean “unusable”. And let us consider what we call an “ex act” explanation in contrast with this one. Perhaps something like drawing a chalk line round an area? Here it strikes us at once that the line has breadth. So a colour-edge would be more exact. But has this exactness still got a function here: isn’t the engine idling? And re member too that we have not yet defined what is to count as overstepping this exact boundary; how, with what instruments, it is to be established. And so on. -- -- And he also writes: Is an indistinct photograph a picture of a person at all? Is it even always an advantage to replace an indistinct picture by a sharp one? Isn’t the indistinct one often exactly what we need? His comments address the nature of the problem considered in this thesis. How can the vagueness of spatial relations and concepts be represented and reasoned with in a 10 computational environment? What exactly, or perhaps inexactly, do humans mean when they refer to configurations using spatial relational terms? 11 CHAPTER 3 VAGUE OBJECT THEORY This thesis deals primarily with the problem of spatial knowledge representation. The problem is how to represent the spatial terms and concepts used by humans when com municating spatial information and when reasoning about spatial configurations. Human spatial concepts include terms such as “beside”, “above”, and “between”. These concepts, however, are quite vague in nature. Though the terms have specific meanings to humans, their actual spatial interpretation is vague. Additionally, human spatial reasoning is often performed with very poor size and shape information. In order to mimic human spatial reasoning, it is necessary to model the approximate visualization methods used by humans. To make a computer implementation of spatial reasoning usefhl, it should be possible to reason directly from solid model data. No human intervention should be required to transform raw spatial data into another form suitable for reasoning, In fact, the problem of human intervention is commonly overlooked in much research on spatial reasoning. Spatial data is often assumed to be in some form suitable for spatial reasoning. Vague objects are introduced as a knowledge representation scheme that emulates the approximate nature of human spatial reasoning. Vague objects can represent both 12 solid objects and spatial relationship terms with vague forms which simulate the visualiz ation of objects and relationships by humans. In addition to knowledge representation, vague objects can be used for simple spatial reasoning. In turn, simple spatial reasoning can be used to evaluate complex spatial rela tionship phrases involving the combination of several simple spatial terms. Vague object representation and reasoning provide a method of modelling simple human concepts of space in a manner that is computable. Additionally, reasoning can be performed directly from standard solid model information. Vague objects give a computer the ability to represent what is meant by various human-understood spatial terms that are vague and approximate in nature. 3.1 Spatial Data Representation The reasoning system presented here uses a new method of spatial representation. It is concerned with spatial knowledge, rather than an accurate depiction of space. The em phasis on knowledge will facilitate reasoning about spatial objects at the expense of an in accurate representation. If needed, an exact model of space can be maintained separately, while the inexact model is used for reasoning. The problem of spatial data representation is a well-understood area of computer graphics. The aim of all spatial data representations is to model the physical shape of solid objects efficiently and accessibly. A spatial model can be used for creating a graphic 13 image, solid modelling, interaction, animation or other purposes. Usually the representa tion method is chosen to suit the purpose of the modelling application. Three common spatial data representations are constructive solid geometry, bound ary representation, and spatial occupancy [Requicha, 1981]. Each of the three methods has different applications, but all serve the purpose of representing solid objects in three-dimensional space. Constructive solid geometry represents solid objects in terms of simple prototype shapes, e.g. cones, cubes and cylinders. Complex shapes are described by the logical union, intersection, and difference of prototype objects. The logical structure is usually expressed in the form of a tree as shown in Figure 1. Constructive solid geometry is often used for computer aided design applications because the objects being modelled are usually highly structured. Figure 1. Constructive solid geometry hierarchy 14 In the spatial occupancy or voxel representation system, space is divided into small cubes (voxels) which are aligned with the Cartesian coordinate system. An object is speci fied simply as an enumeration of all the voxels occupied by the object. The representation is analogous to a black and white picture which is composed of pixels on a computer video display. This method does not take advantage of object structure and is often used in cases where object data has been captured or measured as opposed to having been generated. Figure 2. A voxel torus Boundary representation specifies an object by storing its boundary surfaces. An ob ject consists of surfaces that form a thin shell which encloses the volume occupied by the object. The boundary can be formed by polygons or parametrically defined surfaces. The solid part of the object is not expressed directly, but is assumed to be the volume enclosed by the surfaces of the object. Boundary representation has limitations as a solid modelling system because non-solid objects are easily created when a surface is not properly closed. 15 Boundary representation is by far the most common spatial data representation system used for image generation and rendering. Figure 3. Boundary representation These three methods, as all other common spatial data representations, are binary in nature. Space is divided into two absolutes: inside or outside. Binary models are suitable for modelling solid objects since solids are binary by nature. They have definite surfaces and interiors which are (except possibly at the atomic level) geometrically exact. There fore, for the purposes of image rendering, computer aided design, and physical modelling, the existing spatial representations are well-suited. For the purposes of spatial reasoning, however, binary representations are inadequate. They are so exact that they are of little value for human-like spatial reasoning. Human spatial reasoning is quite powerful and yet it is performed with little accuracy in representation. As an example of simple human spatial reasoning, consider the task of arranging the furniture in a room. Due to the size and weight of the objects involved, the arrangement process is often decided mentally before-hand. The task is guided by simple rules such as: 16 “the TV should stand against the wall” and “the couch should be across from the TV”. In his mind, a person can juggle such positions until an acceptable room layout has been ar rived at, All reasoning occurs with only a vague idea of the dimensions involved. The human visualization of the furniture and the room only approximates the true shape and size of the objects involved. Additionally, the terms used such as “across from” and “against” do not have strict and accurate geometric interpretations. By introducing the concept of vague objects, implementation of human-like spatial reasoning can be achieved. It becomes possible to model the vagueness of not only human thinking about object dimensions, but also of a human’s understanding of approximate spa tial relationships. A vague object is, as the name suggests, a vague, indistinct version of a solid object. A vague object is similar to a solid object but for which the sharp distinction between in side and outside is blurred. Instead of a distinct polygon or surface, the boundaries of a vague object are smooth transitions from outside to inside. A vague object can be thought Figure 4. A solid teapot and a vague teapot 17 of as a blurry version of a corresponding solid object. A vague object is a shape resem bling a cloud that approximates a solid object (see Figure 4). 3.2 The Density Function Vague objects are, in fact, three-dimensional scalar functions called density functions. A density function returns a value between 0.0 and 1.0 for any given point inside and near a vague object. For a point deep inside of an object the density value is 1.0, meaning solid. For a point distant from the object, the density function is 0.0, meaning far outside the solid. The density function varies between 0.0 and 1.0, depending on its location rela tive to the original solid that it is approximating. The density function p.(x,y, z) = Density at Cartesian coordinate (x,y,z) is defined as: (1) A point that is on the boundary of the solid object has a vague object density func tion of about 0.5 at that point. The exact value of the density function depends on the local geometry of the surface of the solid object. If the boundary point is on a locally flat surface, the density value will be exactly 0.5. 1f however, the boundary point is at the bottom of a pit in the surface, it will have a density value of greater than 0.5. Conversely, if the boundary point is at the tip of a protrusion, the density value will be smaller than 0.5. Although the vague object does not correctly identify boundary points, it represents the concepts of inside and outside intuitively. A point at the bottom of a pit is more “inside” of a solid than its identification as a boundary point would suggest. Alternately, a point on the tip of a potrnsion is clearly more outside than it is inside. The vague object density function gives a more satisfying measure of “inside” and “outside” than representations that deal with boundaries and surfaces. Figure 5. A surface pit and the vague equivalent Figure 6. A surface protrusion and the vague equivalent Another interpretation of the density fhnction is its role as a measure of proximity. The density value of a point inside a solid is a reflection of how many of its neighbouring points are also solid. A point deep inside a solid has a density value of 1.0 because all of the neighbouring space is also solid. Additionally, a point on the boundary has a value near 0.5 because about half of the surrounding space is solid, and the other half empty. Thus a vague object can be thought of as a scheme to encode knowledge in the form of a local proximity to the solid. 3.3 Creation of Vague Objects Usually, vague objects must be created from another solid model representation. Since vague objects inherently lose information, they are not useful as a primary storage 19 scheme for solid model information. Vague objects are intended primarily for reasoning purposes. Therefore, a simple process must be used to create vague objects from their solid counterparts. Fortunately, a vague object is easily created by low-pass filtering a solid object. Just as signal processing is often extended to two-dimensional signals for the pur poses of image processing, it can be used for three-dimensional signals as well. Similar to one-dimensional sound signals, or two-dimensional image signals, the three-dimensional signals of solids and shapes can be manipulated with common signal processing techniques. Three-dimensional signal processing is closely analogous to two-dimensional signal (or image) processing. In the Fourier transform of a shape or image, the high-frequency components correspond to the sharp edges of the shapes or images. When high fre quencies are removed by a low-pass filter, the resulting shape or image is devoid of sharp edges. An image without sharp edges is blurred, comparable to the image from a camera that is poorly focussed. Similarly, a three-dimensional shape is also blurred after a lowpass filter removes the sharp edges. The resulting shape no longer has sharp transitions from solid to empty space, but instead a slow transition in “density”. These properties are exactly what is required of a vague object. An interesting consequence of the low-pass filter operation is the change from a bi nary spatial representation to a scalar one. Both sound and image data contain smooth variations in intensity of their signals. Sound intensity corresponds to air pressure, while 20 image variations represent light’s intensity. Solids, on the other hand, as classically repre sented by boundary representation and spatial occupancy, are limited to only two values: solid and space. The signal associated with a traditional solid model consists entirely of step functions (in fact, precisely this restriction enables a boundary representation to represent a solid). Vague objects, on the other hand, resemble sound and image data be cause they allow smooth variations in “intensity” between solid and space. As a result, vague objects capture more information per unit volume than corresponding binary solid models. The additional information is utilized to facilitate spatial reasoning. The parameters of the low-pass filter can be used to change the characteristics of the vague objects. By changing the cut-off frequency, it is possible to alter the blurriness of the vague shape. As the cut-off frequency is lowered, the resulting vague object gets more and more blurred. Of course, information is lost when the object is low-pass fil tered, and more so as the cut-off frequency is reduced. As will be discussed in the next section, varying the amount of blur is useful when changing the level at which reasoning takes place. It is important to note that the manipulation of blur is easily controlled and can be varied smoothly. 3.4 Features of Vague Objects Using a combination of vague representation and signal processing techniques, the reasoning process with vague objects can be enhanced. The low-pass filter permits sub-sampling while changing the filter parameters allows the vague objects to be scaled as needed. 21 3.4.1 Sub-Sampling The implementation of vague objects requires a voxel representation for storage and manipulation. Unlike normal spatial models, and perhaps more like magnetic resonance imaging data, the voxels used are not simply binary. They have a value corresponding to the density value for the cube of space they represent. Voxel representation is actually a form of sampling. The solid of the original non-vague object is sampled at discrete points of a three-dimensional grid. The resulting signal is a standard voxel representation of the solid object. The sampled representation is then low-pass filtered to blur the sharp edges, resulting in a vague object. In order to sample an object, the sampling grid must be fine enough to capture the details of the object (solid objects cannot be sampled with perfect accuracy since sharp edges require infinitely high sampling frequencies). The Nyquist criterion states that the sampling rate must be twice the rate of the highest frequency in a signal in order to properly reconstruct the signal from the set of samples [Stark, 1988]. Nyquist’s criterion can also be interpreted as meaning that the number of samples required to represent a signal properly (with no loss of information) depends on the highest frequency in that signal. The three-dimensional sampling grid must therefore be twice as fine as the finest detail in the original solid. Since the next step in producing a vague object from a solid object is to low-pass filter it, the sampling frequency required to satisfy the Nyquist criterion is immediately re duced. Since the low-pass filter attenuates the highest frequencies in the signal. (i.e. 22 sampled object), the required sampling rate is lowered. The vague object can be immedi ately resampled at a lower rate. Since the sampling rate for solids actually controls the fineness of the three-dimensional sampling grid, a reduction in the sampling rate leads to a cubed reduction in the number of sample points. A decimation (sample rate reduction) by one-half leads to a reduction to one-eighth of the number of sample points while a decima tion by 1/10 would divide the sample count by 1000. Since reasoning with vague objects also requires their storage and processing, the sample reductions resulting from decimation lead to a significant performance gain. 3.4.2 Scalability The lowering of the cut-off frequency of the low-pass filter increases the blurriness of the vague object. Though blurring greatly reduces the number of samples required, it also reduces the information contained in the vague object and hence the accuracy of any ensu ing reasoning. The loss of information is, however, not necessarily a disadvantage, de pending on the scale at which the reasoning is being performed. When reasoning at a large scale, detailed information is not important, possibly even counterproductive if it im pedes the reasoning process. For large-scale reasoning, a vague object can be blurred (to remove the detail) and then resampled with a coarser grid. Filtering and re-sampling re moves extraneous detail, and significantly increases efficiency by reducing the number of samples representing the object. The result of the re-sampling process is that the data set used for reasoning stays relatively stable. As objects are reasoned with at a larger scale (thus requiring larger 23 numbers of samples), they are blurred and re-sampled to reduce the number of samples back to a lower level. Re-scaling can be implemented smoothly where vague objects are automatically re-scaled depending on the size of the data set being investigated. Variable scaling reflects the human reasoning process. Human spatial reasoning does not work well with large amounts of information. If too much information is present to be reasoned about, a human will abstract and approximate until it is sufficiently simple. For example, when golfers reason about hitting a golf ball, they do not consider the pits in the ball when making their decisions; such information is excluded in the reasoning process. 3.5 Spatial Concepts Most of the discussion until now involved the conversion of existing solid objects into vague objects for the purposes of reasoning. This is not the only scheme for which vague objects are created. Vague objects can be used to represent not only approxima tions of solid objects, but also to represent vague spatial concepts that do not have corre sponding solids. A spatial concept is a relationship between two or more objects. Spatial concepts are commonly either unary, binary, or ternary. A unary spatial concept is an attribute of a single object, usually a such as “long” or “flat”. Binary spatial concepts are relationships between objects involving space such as “beside”, “above” and “inside”. Ternary spatial concepts are,, predictably, relationships involving three objects such as “between” or “connecting”. Of course, spatial concepts of higher orders are possible, but not common in human usage. For many spatial concepts, a mental shape can be used to describe them. 24 The mental shape associated with a spatial concept is approximately the area in space where that concept exists, or perhaps the shape of what a certain spatial concept means to humans. As an example, consider the spatial concept of “above”. If asked to envision the idea of”above object A”, a human would agree that it is a vaguely cone-shaped object that stretches up and away from the top of object A. Using vague objects, approximate mental shapes can be quantified and reasoned with using a computer. Spatial concepts, as understood by humans, tend to be vague and ill-defined. Conse quently, their representation and implementation is difficult using approaches of symbolic logic. Their expression in a logical or computable form is difficult with traditional artificial intelligence techniques. This thesis proposes to use vague objects as a representation method for approximate spatial concepts, that is both computationally efficient and seman tically acceptable. 3.5.1 Unary Spatial Concepts Unary spatial concepts such as “long”, “tilted”, or “square” tend to be represented by a mental image that corresponds to a prototype shape. Unary spatial concepts are often examples of the dimensional adjectives explored by Lang [Lang, 1991]. One possible method to evaluate unary spatial concepts using vague objects is to match the shape of a test object with that of a vague prototype. Here, however, such ideas are not pursued further and unary spatial concepts are not considered. 25 3.5.2 Binary and Ternary Spatial Concepts Binary and ternary concepts, on the other hand, are quite easily specified and manipu lated as vague objects. For many such concepts, a definite mental shape is easily found, and the required vague object is simple to calculate. Usually the vague concept “shape” is created with a simple transformation of one of the objects. For example, the concept of “above” can be formed by extruding a cone vertically above an object, while the “inside” shape is formed using a fill operation. 3.5.3 Examples of Spatial Concept Shapes Some examples of simple spatial concept shapes are shown in Figure 7 through Fig ure 10. The simplest spatial concepts are the directional concepts, e.g. “above” and “in front” (see Figure 7 and Figure 8). Directional spatial concepts are vague cones that radi ate in the direction being described. The dark central part of the cone is the area where the concept is strongest. In the case of the “above” cone, the dark centre portion is the area that is described as “directly above” or “right above”. The use of linguistic hedges (as in fuzzy logic) in natural language for spatial terms supports the idea that spatial concepts have a vague nature. The vague spatial concept gets weaker at a distance from the centre line, reflecting the fact that at a point farther away from the centre line the spatial concept becomes a less accurate description of that point. The shape of the concept “above” depicted in Figure 7 is not the only possible inter pretation of “above” in English. A broad interpretation of “above” could be expressed simply as “higher than”. The “above” depicted in Figure 7 is a narrow interpretation of the 26 term which could be restated more verbosely as “the space where above applies better than other spatial concepts”. The simple “higher than” interpretation is inadequate when the horizontal distance between objects increases. In general, a narrow interpretation for a spatial concept is more useful since it helps to distinguish between competing spatial terms. Figure 7. The spatial concept shape of “above” (truncated) The spatial concept shapes for “to the left” and “in front” are shown in Figure 8. As for the “above” concept, the shapes for these two terms are vague cones extending in the appropriate directions. Subjective tests have been conducted to measure the opinions of humans about the shapes of various spatial concepts. The tests have shown that the “to the left” and “in front” cones are much broader than the “above” cone. Consequently there is a broad overlap between “in front” and “to the left”. It does not appear that using “in 27 front” and “to the left” simultaneously is a contradiction. The shape difference between the horizontal directional concepts and the vertical ones hints at a fundamental difference in the human perception of vertical and horizontal orientations which is considered further in Section 3.6.6. Iii IIrlt To the Left Figure 8. Spatial concept shapes for “in front” and “to the left” (truncated) Not all spatial concepts are simple directional cones. Figure 9 and Figure 10 show two examples of more complex spatial concepts: “between” and “inside”. The “between” shape is the volume of space that intersects the line of sight from one object to the other. The vague edges and dark centre of the “between” shape reflects the fact that the centre of the shape is “directly between” as opposed to “somewhat between” near the edges of the shape. Interestingly, the user tests have shown that the “between” concept extends 28 vertically to some degree, which explains the upward bulge around the centre of the “bet ween” shape shown in Figure 9. Figure 9. The spatial concept shape for “between” The “inside” of an object is that volume that would be occupied by an imaginary fluid filling the object. The “inside” concept is the least vague of the vague concepts discussed so far since the solid object provides a distinct boundary for the “inside” shape. An object need not be closed in order to have an “inside”. The kettle shown in Figure 10 is an example of an object which has a definite inside, although it has an opening at the spout. To determine the inside of a three-dimensional object, it is only necessary to find all points that are enclosed in at least two of the three Cartesian directions. Algorithms for creating “between” and other spatial concept shapes are presented in the Appendix. 29 Figure 10. The spatial concept shape for “inside” the kettle Another class of spatial terms that are easily represented by vague concepts are the internal localization nouns investigated by Aurnuage and Borillo [Aurnuage, 19901. Inter nal localization nouns are used to refer to portions of a large object. Examples of internal localization nouns include “top”, “left edge” and “middle”. Internal localization noun con cepts can be converted into vague objects from any given solid object with simple trans formations (see Appendix) . Figure 11 shows some examples of internal localization nouns and their appropriate vague concept shapes. 30 - Bottom Part Right Edge (deictic sense) I Figure 11. Some internal localization nouns and associated vague shapes 3.5.4 The Importance of Shape Spatial concept shapes are frequently influenced by the shape of the solid objects to which they refer. The influence of shape generally declines with distance. The transform ation which is used to create a vague concept shape should take the original object’s shape into consideration when generating a vague concept. For example, the spatial concept shape for “above” Chile (the country) would be very long and thin at a low altitude, re flecting the long and thin shape of Chile’s borders. As altitude increases to a few thousand kilometres, the actual shape of Chile becomes unimportant when considering the concept 31 “above” Chile. The effect of Chile’s shape on the “above” concept disappears at large distances. Vague object representation facilitates the transition from shape importance to shape indifference. At low altitudes, the horizontal cross-section of “above” Chile is shaped much like Chile itself At high altitudes the cross-section becomes an amorphous blob. Vague object representation allows this cross-section transition to be easily implemented with a linear progression from meaningfiul shape to vague blob. 3.5.5 Origin of Spatial Concepts Spatial concepts are a means of quantifying ideas shared by humans. Spatial con cepts are not natural phenomena, they are solely inherent in the thinking processes and the language of humans. The task of quantifying spatial concepts for computer-based spatial reasoning is not one that can be performed automatically in some fashion from a set of equations or a physical model. The concepts must be created by hand in an ad hoc fashion by a human “knowledge engineer”. This is a common task in the field of knowledge en gineering, where knowledge about a particular domain is entered into a knowledge base by a human technician. Usually, knowledge is taken from human experts in the domain and encoded by the knowledge engineer. In the case of spatial concepts, the domain is the one of common sense spatial reasoning so there are no “experts” per se since the spatial con cepts to be encoded are shared amongst all humans through language and interaction. The approximate shapes of spatial concepts are easily agreed upon by humans since their 32 primary use in communication requires agreement. The exact dimensions are not easily envisioned, but can be (and have been) determined experimentally. 3.6 Vague Objects and Spatial Logic When a spatial concept is expressed in a logical statement such as “A is close to B”, the spatial concept becomes a spatial predicate. A spatial predicate is analogous to a logi cal predicate because it makes a statement about the world that may or may not be true. Unlike a standard logical predicate, a spatial predicate does not have a simple truth value of true or false. Spatial predicates tend to have truth values that are scalar instead of Boolean. For this reason, reasoning about spatial predicates requires a multi-valued logic. Fortunately, much reasoning can be performed without resorting to scalar truth va lues. Scalar truth values are often only required at the end of a chain of reasoning which takes place entirely in the domain of vague objects. The scalar truth value is only ex tracted after the reasoning is completed as an assessment or evaluation of the spatial con figuration or concepts under consideration. This thesis does not consider the problem of reasoning with scalar truth values, but instead deals with vague object reasoning. There is much theoretical work, however, being undertaken in the area of multi-valued logics which can be drawn on to deal with the problem [Ng, 1990] [Fringuelli, 19911 [Gacogne, 19911. 33 3.6.1 Venn Diagrams and Spatial Reasoning Reasoning with vague shapes is performed in a manner that resembles a three-dimen sional set logic. Venn diagrams, which are commonly used to visualize Boolean sets, are a useful analogy to vague objects. Figure 12 shows an example of how logical operations are performed with Venn diagrams. The universe shown comprises two sets: A and B. Logical operations such as the AND function have an intuitive visual interpretation. In Figure 12, the spatial overlap of the two set shapes is the result of the logical AND func tion. AAND B Figure 12. The Venn diagram of the logical AND function The Venn diagram method can also be used to represent a simple spatial configur ation. Figure 13 shows a Venn diagram where each set represents either a solid object or spatial concept. For simplicity, the sets shown here are not vague, but truncated to crisp sets. The set representing A is simply the set of all points that are part of the solid object A. The concept shape for “above A” is similarly formed by all spatial locations which are intuitively “above” the solid object A. The operation for “above A AND above B” is per formed by simply taking the overlap just as in the previous example. 34 Vague object reasoning can be performed in a fashion that is very similar to how Boolean reasoning is performed with Venn diagrams. Above A AND Above B Figure 13. Simple spatial reasoning using Venn diagrams In Venn diagrams, the spatial location and shapes of sets are not significant. Venn diagram representations are usually visual abstractions of other less intuitive domains. For the case of vague object reasoning, though, spatial location is the essence of the represen tation. Venn diagrams are not simply an abstraction of the domain, they are the domain (or at least a two-dimensional projection thereof). For general purpose spatial reasoning, the Venn diagram analogy is easily extended to three dimensions. Vague object reasoning and logic is simply a set logic in a three-dimensional domain where the spatial positioning of sets is significant. Vague object reasoning, however, is not a Boolean set logic. Boolean sets are binary by definition, they have rigid boundaries. A point in the domain is either a member or not a member of any given set. Vague objects, as defined, have density functions which vary between 0.0 and 1.0. This is much like fuzzy logic, where any point in a set has a degree 35 of membership in that set. To some degree vague objects are similar to a three-dimen sional fuzzy logic. Vague object reasoning borrows from fuzzy set theory for many lowlevel operations dealing with the density (i.e. membership) functions. There are, however, fundamental differences between vague objects and fuzzy sets which are discussed in Sec tion 3.7. The next figure (Figure 14) is the previous example of “above A AND above B” where the crisp sets of Boolean logic are replaced by vague objects (projected into two di mensions). The density values of the objects are represented as darkness where the den sity is 1.0 and white where it is 0.0. The grey values represent the range between 0.0 and 1.0. The AND operation is performed point by point. As in fuzzy logic, the AND oper ation for any given point is defmed as the minimum of the individual density values [Lee, 19901. That is for two vague objects A and B with density (x,y, z) and for any point with coordinates (x,y,z): A (x,y, z) and 8 Above A AND Above B LJ / LA IN Figure 14. Simple spatial reasoning using vague objects 36 functions A(x,Y, z) B(x,Y, z) = I E&4(x,Y,z) if PA(x,Y, z) B(x,Y, z) if B(x,Y, z) JIB(x,Y,Z) A(x,y, z) (2) In diagrammatic form, the shade of any given point is the lightest of the two shades of the original shapes being ANDecI together. The OR operation is defined similarly, ex cept that the maximum of both densities is used. The logical operations of AND and OR are useful for creating aggregate shapes or defining complex spatial concepts. For example the phrase “above the rug or table and below the lamp”, or more exactly “above(rug OR table) AND below(lamp)”, would have the vague object interpretation shown in Figure 15. This vague shape can be formed com pletely automatically using vague objects and simple logical operations. Figure 15. Vague shape for “above the rug or table and below the lamp” 37 3.6.2 Spatial Concept Evaluation Another use of the vague object logical AND operation is for the evaluation function. The evaluation function evaluates a spatial concept for a given configuration of spatial ob jects. The evaluation operations resolves the strength of a spatial concept in a particular spatial situation. For evaluation, a target object is logically ANDed with a vague concept shape to produce an evaluation of the spatial concept for the target object. For two ob jects A, B and a spatial relation CONCEPT, the evaluation function answers the question “is A CONCEPT B’?”. The answer to this question is contained in the shape that results from the logical AND operation. For example Figure 16 shows a spoon inside a glass. To evaluate the question “is the spoon inside the glass?” the spatial concept for “inside the glass” is created (using a modified fill algorithm, see Appendix). This vague concept shape is logically ANDed with the vague object that corresponds with the spoon. The re sult of the AND operation is a vague shape that answers the question “is the spoon inside the glass?”. The resulting object contains the answer in a spatial form. In the previous example, it defines the portion of the spoon that is inside the glass. Since the resulting shape is almost as large as the original spoon shape, the answer to the question is: “the spoon is mostly in side the glass”. This shape interpretation phase completes the evaluation operation. Hence the evaluation operation actually comprises two operations: overlap and interpreta tion. 38 Figure 16. Vague object AND operation of “inside glass” and “spoon” The resulting shape need not be interpreted immediately, however, it can be used for further reasoning. To evaluate more complex questions, and to perform simple reasoning, several evaluations may be chained together. The interpretation phase is delayed until after several spatial concept transformations and overlaps are completed. As an example, Figure 17 shows a spatial configuration involving a car and a balloon. Figure 17 shows the chain of reasoning required to answer the question “is the balloon above the back of the car?”. The first operation required is the creation of the “back of the car” vague con cept shape, created by using a simple transformation (see Appendix) that results in the vague shape that is intuitively recognizable as “the back of the car”. The shape is not yet interpreted, but is used directly for the next stage of reasoning. Since the “back of the car” has been converted into a vague shape, the concept of “above the back of the car” is evaluated as if the “back of the car” were a fbzzified solid object. The “above” object is 39 created from the “back of the car” using the simple transformation described earlier. The resulting concept shape is then logically ANDed with the balloon’s vague shape to produce the answer shape for the entire question. It is only at this point that the final shape is in terpreted, completing the evaluation operation. In this case, since the resulting shape is al most as dark as the original balloon, the question is answered as: “the balloon is mostly above the back of the car, but not directly above”. Original Scenario Back of the Car Figure 17. Reasoning steps for “Is the balloon above the back of the car?” (continued) 40 Above the Back of the Car Overlap Resulting Shape 4 Original Interpretation Figure 17. Reasoning steps for “Is the balloon above the back of the car?” 41 A chain of reasoning allows complex questions or descriptions to be evaluated using vague objects and logical operations. Since reasoning is performed using vague objects, the length of reasoning chains should be limited. As reasoning progresses, the inaccur acies created by the vague approach will accumulate, leading to an increasingly uncertain answer. This is not a serious limitation since the approximate process (i.e. human reason ing) that is being modeled is not used for convoluted spatial reasoning either. It is often necessary for humans to rely on diagrammatic aids when confronted with complex spatial problems. Though complex spatial reasoning appears to require a combination of vague and crisp spatial reasoning, the idea is not pursued fhrther. The approach presented here is limited to reasoning problems that humans can easily carry out without external aids. 3.6.3 Aggregate Properties for Shape Interpretation In previous examples, the results of shape interpretation are presented as intuitive answers without explanation of how they are arrived at. The process of shape interpreta tion can be performed in an entirely algorithmic fashion, and is easily automated. Shape interpretation requires the definition of a number of mathematical and geometric prop erties of vague shapes. Properties which are included are centre of mass, total mass, ex tent, and volume, which will now be defined. 3.6.3.1 TotalMass The total mass is a summation (or integral) of the density over the entire object. It is a measurement of the weight or significance of a vague object, The total mass is defined as follows, where j.i(x,y, z) is the vague object density fbnction at point (x,y, z): 42 M = f G S. p.(x,y, z) dx dy dz (3) Since vague objects are implemented as voxels, or samples of objects, it is usefi.il to define their properties in discrete terms. For a vague object sampled within a cube with n samples along each cartesian axis, where the integers i,j,k satisfy: 0in—i , 0jn—1 , 0kn—i (x zk) are the sample points and y the coordinates 1 zk) are the density y zk) are assumed to 3 , 1 (x fhnction samples at those sample points. The sample points , be located in a uniform three-dimensional mesh aligned with the cartesian coordinate sys tem. For a vague object sampled in such a manner, the total mass is found as: n—i n—i n—i M= (4) 1=0 j=0 k=0 where Av is the volume represented by each sample. The total mass is used to measure the strength of the result of an overlap operation. Since the total mass reduces the size and density of an object to a single number, it is use ful for simplifying a resulting vague object shape. 3.6.3.2 Centre ofMass The centre of mass of a vague object is a point which approximates the central point of the object. The centre of mass, as its name suggests, is defined as it is in physics. The center of mass point (CMx, CMy, CMI) is found as: 43 CMx CMy CM fxsyfz p(x,y,z) x dx dy dz M I I I j..t(x,y,z)ydxdydz M x 1 I I j.i(x,y,z)zdxdydz M (5) where M is the total mass calculated in Equation (3). In the discrete case with a vague object sampled as described in Section 3.6.3.1 the center of mass point (cMx,cMy,cMz) is: n—i n—i n—i , p(x , A 1 zjx y v CMx 1=O j=O h=O M n—i n—i n—i , t(x , A 1 z,jy y v CMy 1=0 j=0 k=0 M n—i n—i n—i I.J(xI,yf,zjzkzXv CM 1=0 j=0 k=0 M (6) where Av is the volume represented by each sample and M is the total mass calcu lated in Equation (4). 44 The centre of mass returns the average centre of the density function for a vague ob ject. It is an indicator of the “centre” of a vague object. Unless the object is convoluted (or perhaps actually a combination of objects) the centre of mass will deliver an acceptable result. For convoluted or multiply-centred objects, the “centre” of the object is ill-defined, and the centre of mass does not give a meaningful result. 3.6.3.3 Extent and Volume The extent of a vague object is similar to the bounding box of the vague object. The extent is the smallest box that encloses the object. There are, however, many bounding boxes for vague objects since their boundaries are vaguely defined. The size of the extent depends on how the boundary is decided. A 50 percent extent would be the bounding box for all parts of the vague object that have a density above 50 percent. Figure 18 shows a vague object with various extent boxes. The algorithm for extent box calculation is given in the Appendix. F— 75% 50% Figure 18. Various extent boxes 45 25% The volume of a vague object is the total volume ‘visited” by that object. In discrete form, the volume is the number of all non-zero voxels of the vague object. The discrete volume V, for objects sampled as described in Section 3.6.3.1, is defined as: n—i n—i n—i y i(x 3 . f( , 1 Zk))AV i=O j=O k=O JJO1(xj,yjzk)) =0 ft(xjyjzk) wh ere fl(xiYj,zk)) = 1 (X j,yfzk) 0 (7) > and Av is the volume represented by each sample. The volume is useful for determining how diffuse a result is. A measure of how dif fuse or dispersed a vague object is, is the average density j:I: (8) A low average density is an indicator that a resulting object is losing significance. In chained reasoning, an early operation with a weak result will lead to objects later in the chain with low average densities. This is an indicator that the resulting shape should be treated with skepticism. 3.6.4 Shape Interpretation The total mass is usually the most important measurement to be calculated from a logical AND result shape. The total mass gives an idea of the aggregate overlap of the two shapes. The total mass of the result shape expressed as a fraction of the original mass of the target object reduces the strength of the logical AND result to a single number. 46 This number, called the relative overlap, reflects the overall truth or significance of the spatial concept being evaluated. The relative overlap is a measure of strength for the evaluated spatial concept which varies between 0.0 and 1.0. This measure corresponds with the scalar truth values that were mentioned above. The scalar truth values answer a logical predicate when put in question form such as “is there water in the bottom of the bucket?” or “are the boxes tou ching?” A measure of 0.0 implies that the spatial concept does not apply or is definitely untrue. As the relative overlap increases, it implies that the relative “truth” of the spatial predicate increases also. An overlap of 1.0 implies that the spatial predicate is entirely (or clearly) true. The truth of a spatial predicate does not guarantee that its converse relationship is false. There are many opposite spatial pairs in English that are not genuine logical oppo sites. For example above/below, left/right and inside/outside are complementary in Eng lish, but are not quite semantically opposites. Figure 19 depicts the concept shapes for the terms “above”, “not above” and “below”. The terms “not above” and “below” are distinct ly different. Generally, spatial antonyms in English are not semantically or logically oppo site in their spatial sense. A distinction can be made, however, for spatial concepts between logical complements (above/not above) and converse spatial relationships (above/below). 47 Figure 19. Spatial concept shapes for “above”, “not above”, and “below” 3.6.5 Semantics and Combinations of Terms Although a converse spatial relationship is not necessarily created by a logical com plement, it can often be created by combinations of other spatial concepts. For example, even though “below” is not equivalent to “not above”, it is roughly equivalent to “not above and not beside”. This is an example of how simple spatial concepts can be derived in terms of other basic concepts. It is possible to build a knowledge base of such relations to aid in problem solving. The knowledge base cannot be generated automatically, but must be constructed by a human since the relationships between spatial concepts is entirely tied to human perception and language. 3.6.6 Human Perception, Cognition and Spatial Relationships The definitions and usage of spatial relationships and their corresponding language terms is a product of human cognition. The shape of spatial relationships is tied to the 48 thought processes of humans who have evolved to deal effectively with their environment [Garnham, 19891. The most obvious effect is the distinction made between horizontal and vertical axes. Humans, due to their environment, have a very definite (and quite accurate) definition of the vertical “up and down” axis. The horizontal axes, on the contrary, are not well defined and yet humans can reason quite easily regardless of their horizontal orienta tion. Human spatial reasoning is, in general, rotationally invariant in the horizontal plane. The distinctness of the vertical axis shows itself in several of the spatial concept de finitions shown in Section 3.5.3. The concept shapes for “above” and “below” are much narrower and more specific than the similar concept shapes for “to the left” and “in front”. The concept shape for “between” also spreads vertically much farther than it does horizon tally. Additionally there exist terms such as “beside” that directly reflect the horizontal rotational invariance of human-defined spatial concepts. Human cognition obviously has an important effect on the definition of spatial concepts. Another issue with the human definition of spatial concepts is the distinction between deictic and intrinsic orientation. Deictic orientation is defined as observer-centred orienta tion. “To the left” in a deictic sense means to the observer’s left. Intrinsic, on the other hand, is relative to the object in question. Many objects like houses, animals, and people have a semantic sense of front, back, above and such. These meanings are the object centred or intrinsic directions. When references are made to any directions, it must be un derstood which sense is being used, the deictic or the intrinsic. Confhsion can result es pecially when the vertical orientation of the object and the user do not coincide. Garnham 49 shows that the deictic definition of a spatial concept usually takes precedence when a con flict arises between the deictic and intrinsic orientations [Garnham, 1989]. 3.7 Fuzzy Logic and Vague Object Reasoning There are many similarities between fuzzy logic and vague object reasoning. In fact, vague object reasoning could be considered a specific application of fuzzy logic to three dimensions. If one were to attempt to expand fuzzy logic, which is generally one-dimen sional, the result would probably be quite similar to vague object reasoning. However, vague object reasoning is not general in the sense that fuzzy logic is. It is much like a spe cific application of a three-dimensional fuzzy logic, though such a logic has not yet been formulated. 3.7.1 Fuzzy Sets The fundamental concept in fuzzy logic is that of the fuzzy set. Fuzzy sets are de fined over some type of measurement or quality that is called the “universe of discourse”. Some examples commonly used as a universe of discourse include height, speed, weight, age, etc. For each value in a universe of discourse, a fuzzy set contains a corresponding “degree of membership”. The degree of membership describes how strongly a given point in the universe of discourse belongs to a fuzzy set [Zadeh, 1973]. Figure 20 shows an example of three fuzzy sets for the universe of discourse called age. A person who is eighteen is very much a teen-ager, therefore his membership in the fuzzy set “teen-ager” is 1.0. However, such a person is also becoming what is called a 50 young adult, therefore he is also a member in the fuzzy set “young adult” to a degree of about 0.25. Child, teen-ager and young adult are all examples of linguistic variables. Lin guistic variables are described by fuzzy sets whose membership functions are defined over a given universe of discourse. Child Young Adult II 0 5 10 15 20 Age (years) 25 Figure 20. Three fuzzy sets over universe of discourse “age” 3.7.2 Vague Objects as Three-Dimensional Fuzzy Sets Figure 20 can be compared with the following diagram (Figure 21) showing three vague objects in and around a car. Each vague object describes how well a given point in space is described by the spatial concept associated with that object. In this example it can be seen that vague objects are analogous to fuzzy sets. The density function of a vague object is equivalent to the membership function of a fuzzy set. Spatial concepts are similar to linguistic variables since they ascribe human-understood meanings to the vague objects. The universe of discourse for vague objects is three-dimensional space itself Every el ement in basic fuzzy set theory has a corresponding element in vague object theory. 51 Figure 21. Three vague objects around a car There are differences between fuzzy sets and vague objects. three-dimensional, while fuzzy sets are one-dimensional. Vague objects are As mentioned, vague objects could be viewed as a three-dimensional extension of fuzzy set of theory. Vague objects are not, however, as general as fhzzy sets. Vague objects are restricted to the universe of discourse of three-dimensional space. In fuzzy set theory the universe of discourse can be anything from temperature to shear stress, allowing fuzzy set theory to be applied in many different domains. The restriction to three-dimensional space makes vague objects useful only for spatial reasoning. Vague objects can be viewed as a specific application of three-dimensional fuzzy logic to the area of spatial reasoning. 52 There are may other similarities between vague objects and fuzzy sets that can be ex ploited. Vague object reasoning uses the same definitions of logical AND and OR com monly used for fuzzy sets. The process described for shape interpretation is analogous to the deftizzification process used to extract crisp values from fuzzy sets. Linguistic hedges such as “very” or “slightly” can be applied to vague objects in a similar way to their use in frizzy set theory. These similarities suggest that vague object theory can employ advances in the area of fi.izzy set theory to enhance its functionality. 3.8 Graphical Pick Implemented with Vague Objects The graphical pick or mouse pick operation is a common graphical user interface ac tion. The pick operation involves the user selecting an object on a graphical display using a pointer. For complex graphical scenes with many objects overlapping, the task of pick ing becomes difficult. Such situations are common with object-oriented drawing programs such as MacDraw, CoreiDraw or Pubdraw. The difficulty exists for both the user and the graphical interface. The graphical interface algorithm must resolve ambiguities between overlapping objects where a large set of picked objects are possible. Meanwhile, the user must be particularly careful when picking to override anti-intuitive choices commonly se lected by the user interface. Such a situation, where the computer attempts to second-guess the actions of the user, lends itself to a solution using vague object reasoning. By using vague objects it is possible to design a more intuitive graphical user interface. In this case, the problem is that humans are inaccurate in their ability to point, while the computer is too accurate in 53 its analysis of the user’s input. The vague pick approach approximates the user’s input, as well as the shape of some difficult-to-pick objects and then applies knowledge to extract what the user likely means by his selection. The pick operation calculates which object is being displayed at the point where the mouse pointer (or other pointing device) is triggered. Since the sample that determines the pick object is only one point, it is difficult to select thin objects such as text or line seg ments especially when they overlap another, more solid, object. The problem, of course, is that the point sample as well as some objects are too small for the computer to gauge the intentions of the user. The solution proposed here is to “semantically thicken” such problem objects as well as to blur (or widen) the pick’s point sample. The necessary oper ations are performed in vague object space, and are not represented explicitly on the graphical display. 3.8.1 Semantic Thickness Many types of spatial objects are either too thin or too small to be picked easily with a mouse pointer. The problem is exacerbated by ever-increasing screen resolutions which enable thin lines to be drawn even thinner. In order to overcome problems when evaluat ing a mouse pick operation, it is necessary to transform difficult pick objects using the spa tial concept for “close to”. The “close to” spatial concept is obtained by thickening and blurring objects so that the object and the nearby surrounding area have a high vague ob ject density. The new “close to” version of the original thin object represents the “seman tic thickness” of the object better. Semantic thickness refers to the importance of an 54 object to a human, expressed in vague object terms. Although an object may be infinitesi mally thin on the screen, it is usually more meaningful to the user (e.g. it could be a border or an arrow) than its spatial dimensions suggest. Using vague objects, the thin object can have its semantic thickness represented better through the “close to” spatial concept transformation. The process of semantic thickening is useful for objects such as lines, text, unfilled polygons and very small objects of all types. Text is sometimes difficult to pick since it consists mostly of empty space. The amount of thickening required depends on user accu racy. Objects should be thickened only enough to facilitate the pick operation, excessive blurring leads to conflicts between objects in close proximity. Figure 22 shows an example of a graphic screen and the vague object equivalent after the semantic thickening process. The thickened versions of screen objects are not displayed to the user; they are used in the background to evaluate pick operations. This spad for rent - -— - J Figure 22. Semantic thickening of some text and a line 55 3.8.2 Vague Pick Pointer Shape When a human makes a screen selection, the actual point selected reflects some de gree of error. Since the eye/hand coordination of humans is not perfect, some amount of error can be expected in any mouse pick operation. The vague object pick approach mo dels this uncertainty by blurring the mouse pick location. The effect of blurring a solid object is achieved using a low-pass filter. The vague object that is created by low-pass filtering a point is the impulse response of the low-pass filter being used. Assuming a simple filter impulse response such as a Gaussian pulse or a cone shape, the resulting vague shape will be a blurry blob that is dark in the centre and fades off at a small distance. This pick shape is a vague object version of the sharp point of the standard mouse pick sample. The vague pick shape approximates the user selection and is more semantically accurate at describing how humans point at objects. The size of the vague pick pointer, as with semantic thickening, depends on the inac curacy of the user’s picking ability. Since the vague pick pointer only serves to model human error, its size should reflect average human error. Since humans are more accurate at picking when the mouse pointer is moving slowly, the size of the vague pick pointer should vary with recent mouse speed. Such a scheme, involving dynamic resizing of the expected pointer error would allow users to make rough, large scale selections with fast mouse movements, and also deal with fine objects using slower, more accurate mouse placement. Slow movement for accurate work is a natural human strategy which can be exploited for the vague pick operation. 56 3.8.3 The Pick Decision The decision process required to select a screen object becomes more complex with the vague object approach. Where before a simple point test was needed, now a vague object logical AND is required with all screen objects touched by the vague pointer. However, since this operation is a result of occasional user selections, it is not expected to have a significant effect on computer performance. The process required to decide on the correct pick operation is the same as the process of evaluating vague object configur ations. The pointing ‘concept” is evaluated for all objects and the winner is the one with the highest overlap. All screen objects near the mouse pick location are converted to their semantic counterparts in vague object space. If a screen object is occluded by another in the fore ground, the foreground vague object is subtracted from the background vague object. This subtraction operation is executed on a point by point basis. For any overlap point, (x,y, z), where the background object has a vague object density lLbg(XY z) and the foreground object has a vague object density I..Lfg(XY z), the subtraction operation result 1-’resuitQ’Y’ z) is found by the following equation: ItresultQC,Y, z) = max(O, J..tbg(XY z) — I..Lfg(XY. z)) (9) All vague object shapes (after subtraction) are logically ANDed with the vague pick shape to evaluate the pick operation. The logical AND is performed exactly as with vague object reasoning, except that it is performed in only two dimensions. The resulting shape is interpreted by calculating its total mass. The object chosen for pick selection is the 57 object with the highest total mass for its resulting shape. Special consideration must be given to small objects which can be totally covered by the vague pick shape. Even if a small object has a low logical AND total mass, compared to other larger objects, it should be selected if it is near the centre of the vague pick shape. Figure 23 shows an example of the steps involved in a vague object pick operation. In step 1 screen objects are converted to their semantic equivalents (which can be pre-cal culated during object creation). The triangle, being a filled polygon, requires no semantic thickening. In step 2 the foreground vague object is subtracted from the background vague object. In step 3 the logical AND is performed between the vague pick shape and all nearby vague objects. In step 4 the text object is selected because its logical AND operation’s result shape has the highest total mass. 58 Step 1 Step 2 Step 3 / Step 4 Winner Figure 24. A vague object pick example 59 3.8.4 Vague Object Pick with Moving Objects Moving objects present another problem for the pick operation. It is difficult for a user to select a moving object exactly, especially when the motion is large relative to the size of the object. In this case a point selection is inadequate because it is so easy for the user to miss. Using vague objects, it is possible to implement a “motion blur” concept to aid in the selection process. The motion-blur vague object is created by smearing the screen object forward and backward along its motion trajectory. Figure 24 shows the vague shapes created by the smearing process. The motion blurs are darkest where the actual object positions are, and taper off in directions along the motion trajectories. The motion-blur objects are a simula tion of a human’s perception of an object in motion. The tapering effect that is facilitated by the vague object approach allows situations with overlapping trajectories to be re solved. Figure 23. Motion blur vague objects 60 The screen objects need to be semantically thickened before they are motion-blurred so that thin objects become easier to pick. Aside from the motion blur step, the vague pick operation is performed in the same fashion as in the stationary object case. 3.8.5 Three-Dimensional Pick Operations In three-dimensional interfaces, such as immersive virtual reality environments, the pick operation is also useful. A three-dimensional pick operation is usually implemented as a ray emanating from the tip of the user’s finger (which must have a tracking device at tached). The user must point his finger so that the ray intersects with the desired object (where hopefully there is no obstructing object in the ray’s path.). For everyday human in teraction, however, the finger point gesture is quite inaccurate and usually requires a ver bal qualification. The vague object approach to the three-dimensional pick operation will replace the ray with a vague cone-shaped object, similar to the “above” concept. The cone will radi ate in the direction of the user’s finger and will be most useful when resolving a verbal in dication. For example, in a virtual car lot a user can point at a car and say “the red car there”. The pick operation will logically AND the pointer cone with all red cars in the area and select the one with the strongest overlap. The three-dimensional vague pick method mimics a human listener interpreting the user’s actions in such a situation. The vague object virtual environment pointing operation depends on voice recogni tion to work effectively. Since both the field of virtual reality and voice recognition are 61 progressing at similar rates, however, they should both be able to complement each other in the near future. The vague pick operations in both two and three dimensions are simple applications of vague object reasoning. The process of reasoning progressing from vague object cre ation to overlap calculation and shape interpretation is the same as the process of vague object spatial reasoning. These applications demonstrate the usefulness of the vague ob ject approach for adding intuition to human-computer interaction. 62 CHAPTER 4 IMPLEMENTATION AND VERIFICATION To evaluate vague object reasoning, a set of programs was implemented to create and evaluate simple spatial concepts. The program set includes a simple voxel editor, a vague object evaluator and a visualizer for both solid and vague objects. The voxel editor and the vague object evaluator are both implemented on Sun workstations in C++, while the visualizer is implemented on a Silicon Graphics IRIS VGX workstation using the GL graphics library for C. The voxel editor is a simple tool for building voxel models using X Windows which can display both solid and vague versions of a model. The vague object evaluator can create vague objects from solid voxel models and then evaluate spatial rela tionships between the vague objects. The evaluator includes implementations of “bet ween”, “close”, “inside”, “above”, “to the left”, “to the right”, “in front”, “behind”, “below”, “front part”, “back partH, “left side”, “right side”, “top part”, and finally “bottom part”. The vague object viewer allows interactive viewing of both solid and vague objects and combinations thereof in a three-dimensional scene. The vague object program set provided tools for testing vague object reasoning and permitted the investigation of human judgement of simple spatial relationships. Two ex periments were performed to measure human models of spatial relationships and to evalu ate the vague object evaluator implementation. The first experiment asked subjects to 63 assess a set of three-dimensional scenes, while the second asked subjects if they agreed with computer-generated assessments of some spatial relationships. Both of these tests were subjective in nature, since they asked subjects for their opinions of spatial relationships. 4.1 Experiment 1: Quantification of Human Spatial Reasoning The task of quantifying a spatial relation requires a knowledge engineer to formulate a procedural description for the concept shape. The domain expert can also be the same knowledge engineer since the knowledge domain involved is “common sense” spatial rea soning. This process can, however, only yield the coarse outlines of spatial concept shapes. To fine-tune the computerized versions of vague concept shapes, more subtle methods of analysis are required. By measuring human estimates of spatial relations, it is possible to estimate a more exact shape for spatial concepts. By investigating the human opinions of spatial concepts for various spatial configurations, it is possible to obtain a better understanding of the concept shapes involved. 4.1.1 Experimental Procedure To perform this test, human subjects are presented with a series of three-dimensional scenes presented on a Silicon Graphics IRIS VGX workstation. The scenes are presented by an interactive viewer that allows users to rotate and scale the view of the scene. Sub jects are encouraged to rotate and zoom the scene to enhance their understanding of the 64 three-dimensional nature of the scene. All objects in the scene are simple and constructed of voxels. Each scene consists of a sequence of configurations, with one object moved slightly between configurations. The configurations are shown sequentially, and the moving ob ject travels along a straight line trajectory between configurations. Users are allowed to view previous configurations while making their decisions. The choice of predictable ver sus random sequences was chosen to allow users to consciously consider their estimations of the scene. There were three different scenes used: a computer workstation, a livingroom and a setting involving a garbage can. The test subjects are asked to rate, between zero and ten, how well a certain spatial relationship applies to the configuration shown. For example, while viewing the first scene involving the computer workstation, users are asked how much “above” the monitor is in relation to the computer case. The users are instructed as to which exact semantics of the word “above” to use for their assessments. They are instructed that the simple “higher than” interpretation is not being investigated. They are also told that a score of ten implies “directly above” while zero applies to objects on a level or below the com puter case. The users are not given examples of scenes valued between zero and ten since those values are to be determined by the experiment. The scale between 0 and 10 is an ar bitrary range chosen as a comfortable range for the subjects to express their subjective es timations of spatial concepts. The subject’s assessments are recorded for each configuration. 65 Five subjects were asked to evaluate 30 configurations each. The test investigated the concept shapes for “above”, “in front”, “to the left”, “to the right”, “between” and “inside”. 4.1.2 Experimental Results The spatial relationship assessment experiment provided many insights into the shapes of spatial relationships. In general, the subjects agreed with each other in their assessment of spatial relationships. Differences between subjects were mostly systematic, in that some subjects tended to suggest lower or higher results consistently. The only nu merical analysis of the results performed for this experiment was to take the mean of the evaluations for each spatial configuration. The concept shapes used in the evaluator pro gram were then adjusted so that the program’s evaluations were close to the human esti mate means. For example, the width and density of the “above” cone was adjusted to better reflect the average human judgement of the subjects. More importantly, this test provided evidence of unsuspected perturbations in the shape of human spatial concepts. Initially, the “above” cone was modelled sloping up wards approximately 45 degrees from vertical. The test, however, showed that the “above” cone is steeper, with a slope around 30 degrees from vertical. Similarly, “in front” and “beside” were found to have wider angles than expected. In the “between” test, subjects were found to have a strict line-of-sight sense of “between” as long as all objects were on the same horizontal plane. There was, however, a vertical bulge in their asses sments of “between”. An object was judged “between” even though it was vertically 66 displaced from the strict line-of-sight definition of “between”. These observations were true for all subjects tested. 4.2 Experiment 2: Verification Once a test implementation of some simple spatial concepts was written, it was necessary to test the output of the program. The computer-generated evaluations of spa tial relationships were tested to see how closely they emulated the judgement of the human subjects. 4.2.1 Experimental Procedure The second experiment is also a subjective test similar to the first one. Once again, subjects are presented with different scenes on a Silicon Graphics workstation. Unlike the previous experiment, however, different configurations in a given scene are presented in random order. Subjects are presented with a configuration and are given a sample evalu ation score for a given spatial concept. The subjects are asked to rate the sample evalu ation as “just about right”, “too high”, “much too high”, “too low” or “much too low”. The sample evaluations are based on the computer-generated evaluations, except that they are offset by a random error. The evaluations are given as ratings between 0 and 10 and they do not differ from the computer-generated evaluation by more than plus or minus 3 out of 10. The subjects are told that the evaluations never vary by more than 4 out of 10, suggesting that a rating of “much too high” would imply an overestimate of about 3 to 4 out of 10. Once again, the range of 0 through 10 was chosen as a comfortable range for expressing subjective evaluations. Subjects are not told how random the evaluations are, 67 but they are told that they contain some form of random error. Subjects are presented with a sheet of paper containing the suggested evaluations for each configuration. A total of six subjects were tested, and asked to assess a total of 25 configurations each. The spatial relationships tested were “above”, “between” and “inside”. 4.2.2 Experimental Results The experimental results consist of 25 data sets with six samples each. In order to analyze the data, all subjective evaluations are converted to a subjective scale ranging be tween 0 and 10. These “subjective units” are a measure of how well a given spatial con cept describes a spatial configuration. For example a measure of 10 subjective units for the term “above” would imply “directly above” while a measure of 0 subjective units would mean “not above”. Since the user responses are relative subjective terms, they must be assigned numeri cal weights in subjective units to convert them to absolute subjective units (i.e. between 0 and 10). The following table gives the weights assigned to the relative subjective terms used in the experiment: Relative Subjective Term much too high a little too high correct a little too low thuch too low Weight (in subjective units) 3 1 0 -1 -3 In order to convert a given relative human estimate into absolute subjective units, the weight corresponding to the subjective term expressed by the subject is subtracted from 68 In order to convert a given relative human estimate into absolute subjective units, the weight corresponding to the subjective term expressed by the subject is subtracted from the suggested evaluation that is provided to the subject. As an example, suppose the subject is shown a configuration with object A partially above object B, and he is told that the suggested evaluation of the term “above” is 8 on a scale from 0 to 10. If the subject indicates that the suggested evaluation is much too high, then his evaluation expressed as absolute subjective units is 8 - 3 = 5 subjective units. The values given in the table are chosen because they approximate the weights suggested to the subjects during the experiment (see previous Section). The table values are also the same weights that were used for generating the suggested evaluations (i.e. the computer generated evaluations were adjusted by a random member from the set [-3, -1, 0, 1, 3]). For each spatial configuration data set (of which there are 25), the mean of the subjects’ absolute subjective evaluations was calculated. This mean is an estimate of the true mean of human opinion. Since there are only 6 data points in each set (one per subject tested), the confidence intervals for the true means are relatively wide. The 90 percent confidence intervals for the true means are 1.23 subjective units or less. This interval indicates that we can be 90 percent confident that the true mean of human opinion lies less than +1- 0.62 subjective units from the sample mean of the configurations that were tested. For every subject, the error between the subject’s evaluation and the sample mean for the relevant data set was calculated. This calculation was repeated for all 25 data sets and 69 all six subjects. The errors were averaged for each individual subject to produce an average subjective error value for each subject. The average subjective error is a measure (in subjective units) of how distant, on average, a single subject’s evaluations are from the sample means. The following table lists the average subjective errors for all six subjects. Subject Number 1 2 3 4 5 6 Average Subjective Error 0.83 0.68 0.61 0.71 0.37 0.49 The average subjective error was also calculated for the original computer estimates generated by the evaluator program using vague object reasoning. The average subjective error for the computer generated estimates is 0.72 subjective units. This value is better than one of the subjects shown in the table, but worse than the other five subjects. The computer’s average subjective error of 0.72 subjective units, however, does not compare too poorly with the mean of all six average subjective errors which is 0.62 subjective units. The preceding analysis shows that the computer estimates using vague objects are within the range of human ability at estimating the mean of human opinion. Since the computer is worse than the average subject, there is obviously some room for improvement in the vague model shapes being used. Of course, since the sample size of six subjects is relatively low, the results presented here should only be considered a rough estimate of the vague object approach’s ability to predict human opinion. 70 4.3 Further Work The system implemented so far only evaluates simple spatial concepts involving at most three objects. The process of chained spatial reasoning has not yet been implemented or evaluated. Furthermore, the vague pick method presented as an example of simple vague object reasoning has not been implemented or tested. To create a true spatial reasoning system using the vague object approach, it is necessary to merge vague object spatial reasoning with a higher-level reasoning system that can deal with scalar truth values. Such a spatial reasoning system could be applied to problems of spatial reasoning in the areas of user interfaces, solid modellers, natural language understanding and intelligent computer aided design. 71 CHAPTER 5 CONCLUSIONS The system of spatial reasoning and spatial knowledge representation presented here relies on the application of a new concept named vague objects. Reasoning with vague objects relies on an approximate spatial representation and is especially intended to emu late human spatial reasoning processes. When used in a spatial reasoning system, vague objects have the following advantages: 1. Approximation of dimensions and shape. In an attempt to emulate human reason ing, vague objects approximate all aspects of dimension and shape. In addition, approx imation allows spatial problems to be simplified and made more tractable. 2. Simple reasoning with a visual interpretation. The actual process of vague object reasoning proceeds in a straightforward fashion. All stages in the reasoning process have a visual interpretation which is easily understood by humans. 3. Direct reasoning from solid models. Vague objects can be created directly from classical solid models, as can vague spatial concept shapes. Therefore, vague objects can be used on existing solid models without an intervening human-assisted interpretation phase. 72 4. Evaluation of spatial relations compatible with human assessment. As demon strated by the implementation experiments, the evaluations of spatial concepts carried out with vague objects are similar to those made by humans. It should be possible to employ the system to aid in understanding humans in a user interface application. Vague objects form the foundation of a spatial reasoning system that will be useful in understanding and interacting with humans in a spatial context. The vague object ap proach, as presented here, is not a complete reasoning system, but allows spatial concepts and objects to be manipulated in a simple and approximate fashion, thereby providing a good knowledge representation system. The ability of vague objects to handle spatial rea soning in a human-compatible fashion allows them to apply to any spatial reasoning sys tem that either emulates a human or interacts with one. 73 REFERENCES M. Abbati and S. Odoardi, “A Logic for the Representation of Spatial Knowledge,” Trends in Artflcial Intelligence, Proceedings of the 2nd Congress of the Italian Associationfor Art/icial Intelligence, pp. 425-429, 1991. F. Arbab, “Examples of Geometric Reasoning in OAR,” Intelligent CAD Systems II, pp. 33-57, 1989. M. Aurnuage and M. Borillo, “A Formal Semantics for Internal Localization: An Essay on Spatial Commonsense Knowledge,” in Artficial Intelligence IV: Methodol ogy, Systems, Applications. Proceedings of the Fourth International Conference, pp. 305-317, 1990. E. Davis, Representations of Commonsense Knowledge, Morgan Kaufhiann, 1990. S. Dutta, “Topological Constraints: A Representational Framework for Approximate Spatial and Temporal Reasoning,” Advances in Spatial Databases, 2nd Sympo sium, SSD ‘91, pp. 161-180, 1991. B. Failings, “A Symbolic Approach to Qualitative Kinematics,” Artficial Intelligence, vol. 56(2-3), pp. 139-170, 1992. B. Fringuelli, S. Marcugini, A. Milani, and S. Rivoira, “Truth Maintenance in Approximate Reasoning,” Trends in Artficial Intelligence, Proceedings of the 2nd Congress of the Italian Associationfor Artflcial Intelligence, pp. 430-434, 1991. L. Gacogne, “An Extension of the Possibility Theory in View of the Formalization of Ap proximate Reasoning,” Symbolic and Quantitative Approaches to Uncertainty. Proceedings of the European Conference ECSQA U, pp. 176-81, 1991. A. Garnham, “A Unified Theory of the Meaning of some Spatial Relational Terms,” Cognition, vol. 31, pp. 45-60, 1989 E. Lang, K.-U. Carstensen, and G. Simmons, Modelling Spatial Knowledge on a Linguis tic Basis. Lecture Notes in Artificial Intelligence, 481, 3. Siekman (Ed.), Berlin: Springer-Verlag, 1991. C. C. Lee, “Fuzzy Logic in Control Systems: Fuzzy Logic Controller Part I,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 20(2), pp. 404-418, March/April 1990. - 3. Malik and T. 0. Binford, “Reasoning in Time and Space,” Proceedings IJCAI ‘83, pp. 343-345, 1983. 74 A. Mukerjee and G. Joe, “A Qualitative Model for Space,” AAAI-90 Proceedings Eighth National Conference on Artificial Intelligence, vol. 2, pp. 72 1-727, 1990. K.-C. Ng and B. Abramson “Uncertainty Management in Expert Systems,” IEEE Expert, pp. 29-47, April 1990. A. A. G. Requicha, “Representations for Rigid Solids: Theory, Methods, and Systems,” ACM Computing Surveys, vol. 12(4), pp. 437-464, December 1980. H. Stark, F. B. Tuteur and J. B. Anderson, Modern Electrical Communications, Analog, Digital, and Optical Systems, Second Edition, Prentice Hall, 1988. 3. M. Wing and F. Arbab, “Geometric Reasoning: A New Paradigm for Processing Geo metric Information,” Design Theory for CAD, Proceedings of the IFIP, pp. 107-1 12, 1985. L. Wittgenstein, Philosophical Investigations. Translated by G. E. M Anscombe, Ox ford, 1958. R. F. Woodbury and I. J. Oppenheim, “An Approach to Geometric Reasoning,” Intelligent CAD, I. Proceedings of the IFIP, pp. 149-168, 1987. L. A. Zadeh, “Outline of a New Approach to the Analysis of Complex Systems and Deci sion Processes,” IEEE Transactions on Systems, Man, and Cybernetics, SMC-3(1), pp. 28-44, 1973. 75 APPENDIX Algorithms for the creation of vague concept shapes are presented here using a simple point-form style. ABOVE The following algorithm will create an “above” shape from either a solid object or a vague object. • Project the shape of the original object onto the horizontal plane. This is the cross-section. • Blur the cross-section (low-pass filter). • Starting at the top of the object, extrude the blurred cross-section vertically upwards, expanding the scale of the cross-section linearly with height. Concept shapes for other directions like “to the left” and “below” are similar to “above” except that the extrusion takes place in a different direction. Also the scaling with distance from the original object varies for different directions (e.g. “in front” is wider than “above”). BETWEEN The “between” shape must be created from two initial objects. 76 • Create a projection of each initial object shape onto the plane dividing the two objects. The dividing plane is the plane normal to the line segment joining the centre of mass points for both objects. • Blur each of these projections (low-pass filter). • Extrude each projection towards the other, scaling the shape so that upon reaching the opposite object, the sizes are equal. • Each extruded projection starts with a density of 1.0 near its source object and fades to 0.0 near the opposite object. This creates a linear blend from one object projection to the other. • The extrusions must be stretched vertically near the midpoint of the joining line segment to account for the vertical bulge in the middle of the “between” concept. The “between” algorithm is like a shape morphing algorithm, where consecutive cross-sections between initial shapes are blended versions of the original shapes. INTERNAL LOCALIZATION NOUNS Internal localization nouns are all created in an similar fashion. The algorithm for “bottom part” is presented as a typical example. The algorithm assumes that the object consists of a set of sample points in three dimensions (a set of voxels). Bottom Part: • Determine the set of points in the horizontal plane which have a portion of the object directly above them (assuming the object lies entirely above this plane). • For each of these horizontal plane sample points, calculate the total mass of the object for the samples directly above. • For each horizontal plane sample point, calculate the number of object samples which must be traversed vertically to account for 20 percent of the total mass calculated in the previous step. • All of the sample points produced by the previous step outline a three-dimensional vague object which satisfies the concept of “bottom part”. 77 • For good measure this shape should be blurred since it is an approximation. The “back of car” internal localization shape given as an example in Figure 17 is ob tained similarly to the “bottom part” except that the horizontal plane is replaced by another plane lying directly behind the car (normal to the centre-line of the car). INSIDE The following definition of an “inside” algorithm assumes the initial object is sampled in a Cartesian co-ordinate system. • For each Cartesian axis: Create two vague objects, one smeared in the positive direction and the other in the negative direction. Next, logically AND these two smeared versions together, creating a “partial inside” for each Cartesian axis. • Now for each combination of axes (e.g. XY, YZ, XZ) perform a logical AND operation between the “partial insides” for these axes. This will result in three vague objects whose constituent points are surrounded on at least four sides by solid. • The “inside” of the object is the set of all points that are surrounded by some solid on at least four sides, therefore the final “inside” is the logical OR of the three sets created by the previous step. EXTENT BOXES The algorithm for extent boxes is actually quite simple s long as a bounding box al gorithm is available. The bounding box algorithm is as follows: 78 • ,y,zk) 1 For all sample points (x 1 if x 1 <x, x = x if x>x,xmxj if ify>y,yy if if;> Zmc Zm = • The Bounding box is the box defined by x, y, z, and x, y, z. To find the extent box for N percent: • calculate n = N/100 • subtract n from the density value for each sample point. • discard all zero valued sample points • calculated the new bounding box. This new bounding box is the extent box for N percent. 79
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Approximate spatial reasoning using vague objects
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Approximate spatial reasoning using vague objects Kennedy, Kevin 1993
pdf
Page Metadata
Item Metadata
Title | Approximate spatial reasoning using vague objects |
Creator |
Kennedy, Kevin |
Date Issued | 1993 |
Description | A method is proposed for implementing spatial reasoning and spatial knowledge representation on a computer which utilizes a new concept named vague objects. Vague objects are an approximate representation system both for solid objects and for spatial relationships between two or more solid objects. A vague object is a simplified solid ob ject where sharp surfaces are replaced with smooth transitions from the solid to its sur roundings. A vague object can be compared to a cloud with a smoothly varying density that resembles a real solid object. Vague objects can be used to represent spatial concepts as well. A spatial concept is defined as a relation between objects, either solid or vague. Many spatial concepts can be visualized as vague objects, and for simple spatial reasoning, they can be implemented as such. Spatial reasoning with vague objects can be performed using a spatial logic that re sembles Venn diagrams in three dimensions. Spatial reasoning by means of vague objects can be executed sequentially in chains allowing complex spatial descriptions to be evalu ated in a visually understandable fashion. The reasoning system used is reminiscent of fuzzy logic, except that its domain of operation is in three dimensional space. Vague objects simulate some aspects of human spatial reasoning using methods in tended for implementation on a computer. This human-centred approach makes vague objects useful not only for emulating humans but, more importantly, for interacting with them. |
Extent | 2414354 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-24 |
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. |
IsShownAt | 10.14288/1.0065078 |
URI | http://hdl.handle.net/2429/4986 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-0089.pdf [ 2.3MB ]
- Metadata
- JSON: 831-1.0065078.json
- JSON-LD: 831-1.0065078-ld.json
- RDF/XML (Pretty): 831-1.0065078-rdf.xml
- RDF/JSON: 831-1.0065078-rdf.json
- Turtle: 831-1.0065078-turtle.txt
- N-Triples: 831-1.0065078-rdf-ntriples.txt
- Original Record: 831-1.0065078-source.json
- Full Text
- 831-1.0065078-fulltext.txt
- Citation
- 831-1.0065078.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-0065078/manifest