Skip to main content
main-content

Über dieses Buch

"La narraci6n literaria es la evocaci6n de las nostalgias. " ("Literary narration is the evocation of nostalgia. ") G. G. Marquez, interview in Puerta del Sol, VII, 4, 1996. A Personal Prehistory In 1972 I started cooperating with members of the Biodynamics Research Unit at the Mayo Clinic in Rochester, Minnesota, which was under the direction of Earl H. Wood. At that time, their ambitious (and eventually realized) dream was to build the Dynamic Spatial Reconstructor (DSR), a device capable of collecting data regarding the attenuation of X-rays through the human body fast enough for stop-action imaging the full extent of the beating heart inside the thorax. Such a device can be applied to study the dynamic processes of cardiopulmonary physiology, in a manner similar to the application of an ordinary cr (computerized tomography) scanner to observing stationary anatomy. The standard method of displaying the information produced by a cr scanner consists of showing two-dimensional images, corresponding to maps of the X-ray attenuation coefficient in slices through the body. (Since different tissue types attenuate X-rays differently, such maps provide a good visualization of what is in the body in those slices; bone - which attenuates X-rays a lot - appears white, air appears black, tumors typically appear less dark than the surrounding healthy tissue, etc. ) However, it seemed to me that this display mode would not be appropriate for the DSR.

Inhaltsverzeichnis

Frontmatter

1. Cloning Flies on Sugar Cubes

Abstract
Many imaging devices will produce estimated values of a physical quantity at certain points (referred to as grid points) in three-dimensional space. For example, a computerized tomography (CT) scanner estimates the X-ray attenuation coefficient inside a human body at points of a three-dimensional rectangular grid. When displaying the results of such an estimation, we usually use a sequence of two-dimensional images, such as those shown in Figure 1.1.1. In these images the bone in the spine and in the ribs appears light (the more concentrated the bone is, the lighter it appears), softer tissues appear gray, and the air outside the body and in the lungs appears dark.
Gabor T. Herman

2. Enhancing the Cube

Abstract
The cubic grids in R 3 (just as the square grids in R 2 ) are ubiquitous in image processing. In fact, the percentage of publications which use grids other than these is very small. Even in mathematics, one can develop a full-fledged theory of topology (see Chapter 4) based only on these grids; see, e.g., [33]. Therefore it is reasonable to ask why we should bother to develop a theory more general than the one based on the cubic grids in R 3 and on the square grids in R 2 . In this chapter we respond to this question. The current section compares the cubic grids with the so-called fee grids and shows that the latter have several advantages. In the next section we discuss a host of different spaces and adjacencies which have arisen for various reasons in the literature.
Gabor T. Herman

3. Digital Spaces

Abstract
Our aim is to provide a mathematical framework for a theory of objects and their surfaces which is applicable to multidimensional discrete spaces. Our motivation comes from practical applications in which boundaries need to be identified in multidimensional data sets with the further aim of displaying them on a computer screen (see Figure 1.1.3). Our definitions are biased towards such applications. One of our aims is to characterize surfaces with a well-determined inside and outside and to define boundaries of objects so that they are indeed surfaces of this type. (In particular, this means that our surfaces must have an orientation, so that we can tell which side is the inside as opposed to the outside.) Furthermore, we want to make our presentation general enough to incorporate many of the reasonable but ad hoc ways that notions, such as “connectedness” and “boundary,” may be defined in digital geometry. We need a framework appropriate for a mathematical treatment of the intuitive notion of a “surface with a connected inside and a connected outside” (a “Jordan surface”) in the discrete multidimensional environment.
Gabor T. Herman

4. Topological Digital Spaces

Abstract
This chapter is for the mathematically minded. Others may skip it without any danger of losing the thread of our presentation. The content of the chapter justifies for mathematicians the approach that we have decided to take and discusses its relationship to some other possible mathematical approaches. So if you are happy with the way we are doing things and you do not particularly desire to learn more about mathematics than what is absolutely necessary to know to understand the rest of the book, just go right ahead to the next chapter.
Gabor T. Herman

5. Binary Pictures

Abstract
After our brief excursion into matters which had to do with topology in the classical sense, we return to our main topic: the geometry of digital spaces. In fact, this is not quite correct; we return to digital spaces, but what we do with them in this chapter may be considered a departure from “geometry.”
Gabor T. Herman

6. Simply Connected Digital Spaces

Abstract
Let S be a surface in a digital space (V,π). For any practical application, it would be impossible to determine whether S is near-Jordan by examining all π-paths from II(S) to IE(S). It is desirable to have a result which says that S is near-Jordan if some local condition is satisfied at every surfel of S. We illustrate this with the digital space (Z33). Let (c, d) be a surfel of a surface S in (Z33). If one of the edges of (c, d) is “loose” (in the sense that no other surfel in the surface shares this edge; see Figure 6.1.1), then one is able to get from c to d via an ω3-path of length 3 which does not cross S. For S to be near-Jordan, it is in particular necessary that ω3-paths of length not more than 3 from c to d must cross S. It would be very useful if this local condition were also sufficient. However, this is not the case for an arbitrary digital space (V, π), even if we restrict our attention to finite ππ-boundaries in binary pictures over (V, π).
Gabor T. Herman

7. Jordan Graphs

Abstract
In the previous chapter we have pointed out the existence of digital spaces (V,π) for which π,π is a strong Jordan pair. According to Theorem 6.4.1, all 1-simply connected digital spaces are in this category, including by Theorem 6.4.5 (Z N , α N ), (Z N N ), (Z N , κ N ), (Z N , ε e ) (for any N-dimensional direction vector e) and, when N ≥ 2, (Z N , β s ), for any N-dimensional sign function s. That the digital spaces of this last kind have the stated property also follows directly from Theorem 6.3.13. We have also shown (in Theorem 6.3.14) that the fcc grid with face-adjacency (i.e., (F, β 1 )) also has the stated property. Following [2], we refer to digital spaces with this property as strong Jordan graphs.
Gabor T. Herman

8. Boundary Tracking

Abstract
Now we are ready to start proving rigorously that boundary tracking algorithms perform exactly as they are intended to do. As an initial demonstration of this, we show that there is a “one-size-fits-all” algorithm which, given a binary picture over a finitary 1-simply connected digital space and a boundary face between a 1-spel and a 0-spel, will return the set of all boundary faces between the component of 1-spels containing the given 1-spel and the component of 0-spels containing the given 0-spel, provided only that this set is finite. We show that a proof of correctness of this algorithm is an immediate consequence of some the general results presented in the earlier chapters.
Gabor T. Herman

Backmatter

Weitere Informationen