Discrete Representation of Spatial Objects in Computer Vision

A fundamental task of knowledge representation and processing is to infer properties of real objects or situations given their representations. In spatial knowledge representation, and in particular, in computer vision, real objects are represented in a pictorial way as finite sets (also called discrete sets), since computers only can handle finite structures. The discrete sets result from a quantization process, in which real objects are approximated by discrete sets. This is a standard process in finite element models in engineering. In computer vision, this process is called sampling or digitization and is naturally realized by technical devices like CCD cameras or scanners. Consequently, a fundamental question addressed in spatial knowledge representation is: which properties inferred from discrete representations of real objects correspond to properties of their originals, and under what conditions is this the case? In this book, we present a comprehensive answer to this question with respect to important topological and certain geometrical properties.

In this section we review some definitions from digital topology and geometry mostly following Rosenfeld [129] and Kong and Rosenfeld [82] . Unless explicitly stated otherwise, we consider Z ² as the set of points with integer coordinates in the plane ℝ.², and similarly Z ³ as the set of points with integer coordinates in space IR³ As usual we assume that all sets are subsets of a digital plane Z ² or a digital space Z ³ with some adjacency (neighborhood) relations which are defined below.

In this approach, it is possible to show that some particular properties of a digital concept are the same as the corresponding properties of its continuous original. The considerations in Chapter 1 demonstrate that it is necessary to introduce a special graph structure into a discrete representation in order to ensure the required properties of a digital analog of a continuous concept. Thus, while defining a digital analog, one must specify at the same time in whichgraph structure this analog is defined. For example, if one defines a digital analog of a simple closed curve as a subgraph of the digital plane Z ² in which each point is 4-adacent to exactly two other points, then the Jordan curve theorem holds for this curve in a graph with changeable 4/8-adjacency or in a well-composed graph. However, as demonstrated in Chapter 1, the Jordan curve theorem does not hold for the simple closed 4-curve in a graph with only one 4-adjacency relation. If we use the changeable ad- acenc 4/ 8 , we have 4-connectedness for the foreground and 8-connectedness for the j Y background. Consequently, connected components are not intrinsic features of the digital representation and the neighborhoods of points are not homogeneous as it is the case for ℝ² with the usual topology.

Starting with an intuitive concept of “nearness” as a binary relation, semi-proximity spaces (sp-spaces) are defined. The restrictions on semi-proximity spaces are weaker than the restrictions on topological proximity spaces. Thus, semi-proximity spaces generalize classical topological spaces. We will use semi-proximity spaces to establish a formal relationship between the topological concepts of digital image processing and their continuous counterparts in ℝ ⁿ . This is possible, since ℝ ⁿ with the usual topology and digital images with their usual structure are sp-spaces. Examples of different semi-proximity relations on digital images are given which induce the usual connectedness on digital images. This is not possible in classical topology.

Any continuous model of some class of real objects should on the one hand be able to reflect relevant shape properties as exactly as possible, and on the other hand should be mathematically tractable, in the sense that it should allow for precise, formal description of the relevant properties. For example, it does not make much sense to model the boundaries of 2D projections of real objects as all possible curves in ℝ². This class is too general to allow us to formally describe any shape properties of sets in this class and there are curves with very unnatural properties (e.g., plane filling curves). Therefore, some restrictions must be added.

In this Chapter we relate topological and geometric properties of digital objects to their continuous originals by digitization and embedding approaches. A digitization is modeled as a mapping from the real plane or space to a discrete graph structure. Based on technical properties of sampling devices which are the main source of spatial information for artificial systems, the graph structure is usually assumed to form a square grid and is modeled as a finite subset of Z ² (or Z ³ for computer tomography scanners) with some adjacency relations. For example, digital images obtained by a CCD camera are represented as finite rectangular subsets of Z ². We characterize a digitization as a function that maps subset of the real plane to discrete objects represented in a graph structure. Our starting point is a digitization and segmentation scheme defined in Pavlidis [120] and in Gross and Latecki [55], in which the sensor value depends on the area of the object in the square at which the sensor is centered.