1.1.2.1Three Levels of Image Engineering

Image engineering is very rich in content and has a wide coverage. It can be divided into three levels, namely image processing, image analysis, and image understanding, according to the degree of abstraction, data volume, and semantic level and operands, as shown in Figure 1.2. The first book in this set focused on image processing with relatively low level of operations. It treats mainly the image pixel with a very large volume of data. This book focuses on the image analysis that is in the middle level of image engineering, and both segmentation and feature extraction have converted the original pixel representation of the image into a relatively simple non-graphical description. The third book in this set focuses on image understanding, that is, mainly high-level operations. Basically it carries on the symbols representing the description of image. In this level, the process and method used can have many similarities with the human reasoning.

As shown in Figure 1.2, as the level of abstraction increases, the amount of data will be gradually reduced. Specifically, the original image data, through a series of processing, undergo steady transformation and become more representative and better organized useful information. In this process, on the one hand, the semantics get introduced, the operands are changed, and the amount of data is compressed. On the other hand, high-level operations have a directive effect on lower-level operations, thereby improving the performance of lower-level operations.

Example 1.2 From image representation to symbolic expression.

The original collected image is generally stored in the form of a raster image. The image area is divided into small cells, each of which uses a grayscale value between the maximum and minimum values to represent the brightness of the image at the cell. If the grating is small enough, that is, the cell size is small enough, a continuous image can be seen.

The purpose of image analysis is to extract data that adequately describe the characteristics of objects and use as little memory as possible. Figure 1.3 shows the change in expression that occurs in the raster image analyzed. Figure 1.3(a) is the original raster form of the image, and each small square corresponds to a pixel. Some pixels in the image have lower gray levels (shadows), indicating that they differ (in property) from other pixels around them. These pixels with lower grayscale form an approximately circular ring. Through image analysis, the circular object (a collection of some pixels in the image) can be segmented to get the contour curve as shown in Figure 1.3(b). Next, a (perfect) circle is used to fit the above curve, and the circle vector is quantized using geometric representation to obtain a closed smooth curve. After extracting the circle, the symbolic expression can be obtained. Figure 1.3(c) quantitatively and concisely gives the equation of the circle. Figure 1.3(d) abstractly gives the concept of “circle.” Figure 1.3(d) can be seen as a result or interpretation of the symbolic expression given by the mathematical formula in Figure 1.3(c). Compared to the quantitative expression (describing the exact size and shape of the object) of Figure 1.3(c), the interpretation in Figure 1.3(d) is more qualitative and more abstract.

Obviously, from image to object, from object to symbolic expression, and from symbolic expression to abstract concept, the amount of data are gradually reduced, and the semantic levels are gradually increased, along with the image processing, analysis, and understanding.

1.1.2.2Papers Classification for Three Levels

The research and application of the three levels of image engineering are constantly developing. In the survey series of the image engineering that started since 1996, some statistical classifications for papers published are performed (Zhang, 2015e; 2017).

A summary of the number of publications concerning image engineering from 1995 to 2016 is shown in Table 1.1. In Table 1.1, the total number of papers published in these journals (#T), the number of papers selected for survey as they are related to image engineering (#S), and the selection ratio (SR) for each year, are provided.

Table 1.1: Summary of image engineering over 22 years.

It is observed that image engineering is an (more and more) important topic for electronic engineering, computer science, automation, and information technology. The average SR is more than 1/5 (it is more than 1/4 in several recent years), which is remarkable in considering the wide coverage of these journals.

The selected papers on image engineering have been further classified into five categories: image processing (IP), image analysis (IA), image understanding (IU), technique applications (TA), and surveys.

In Table 1.1, the statistics for IP papers and IA papers are also provided for comparison. The listed numbers under #IP and #IA are the numbers of papers published each year belonging to image processing and to image analysis, respectively. The percentages in parenthesis are the ratios of #IP/#S and #IA/#S, respectively. The total number of papers related to image analysis is almost equal to the total number of papers related to image processing in these 21 years.

The proportions and variations of the number of papers in these years are shown in Figure 1.4. The papers related to image processing are generally the most in number, but the papers related to image analysis are on rise for many years steadily and occupies the top spot in recent years. At present, image analysis is considered the prime focus of image engineering.

1.2.1.1Definition of Image Analysis

The definition and description of image analysis have different versions. Here are a few examples:

In this book, image analysis is seen as the process and technique starting from an image, and detecting, extracting, representing, describing, and measuring the objects of interest inside, to obtain objective information and output data results.

1.2.1.2Differences and Connections Between Image Processing and Image Analysis

Image processing and image analysis have their own characteristics, which have been described separately in Section 1.1.2. Image processing and image analysis are also closely related. Many techniques for image processing are used in the process from collecting images to analyze the results. In other words, the work of image analysis is often performed on the basis of the results of image (pre)processing.

Image processing and image analysis are different. Some people think that image processing (such as word processing and food processing) is a science of reorganization (Russ, 2016). For a pixel, its attribute value may change according to the values of its neighboring pixels, or it can be itself moved to other places in the image, but the absolute number of pixels in the whole image does not change. For example, in word processing, the paragraphs can be cut or copied to perform phonics checks, or the fonts can be changed without reducing the amount of text. As in food processing, it is necessary to reorganize the ingredients to produce a better combination, rather than to extract the essence of various ingredients. However, the image analysis is different, and its goal is to try to extract the descriptive coefficients from the image (similar as the extraction of the essence of various ingredients in food processing), which can succinctly represent the important information in the image and can express quantitatively and effectively the content of the image.

Example 1.3 Process flow of image analysis.

Figure 1.5 shows a practical process flow and the main steps involved in a 3-D image analysis program:

From the above steps the links between image processing and image analysis can be understood.

1.2.1.3Image Analysis and Pattern Recognition

The main functional modules of image analysis are shown in Figure 1.6.

As shown in Figure 1.6, image analysis mainly includes the segmentation of the image, the representation/description of the object, as well as the measurement and analysis of the characteristic parameters of objects. In order to accomplish these tasks, many corresponding theories, tools, and techniques are needed. The work of image analysis is carried out around its operand—object. Image segmentation is to separate and extract the object from the image. The representation/description is to express and explain the object effectively, and the characteristic measurement and analysis are to obtain the properties of the object. Since the object is a set of pixels, image analysis places more emphasis on the relationships and connections between pixels (e. g., neighborhood and connectivity).

Image analysis and pattern recognition are closely related. The purpose of pattern recognition is to classify the different patterns. The separation of the objects from the background can be considered as a region classification. To further classify the regions, it is necessary to determine the parameters that describe the characteristics of the regions. A process flow of (image) pattern recognition is shown in Figure 1.7.

The input image is segmented to obtain the object image, the features of the object are detected, measured, and calculated, and the object can be classified according to the obtained feature measurements. In conclusion, image analysis and (image) pattern recognition have the same input, similar process steps or procedures, and convertible outputs.

1.2.1.4Subcategories of Image Analysis

From the survey series mentioned in Section 1.1.2, the selected papers on image engineering have been further classified into different categories such as image processing (IP) and image analysis (IA). The papers under the category IP have been further classified into five subcategories. Their contents and numbers of papers per year are listed in Table 1.2.

1.2.2.1History and Development

Image analysis has a long history. The following are some of the early events of the image analysis system (Joyce, 1985):

Image analysis systems have already obtained in-depth research, rapid development, and wide application, in the 1980s and 1990s of twentieth century. During this period, many typical system structures were proposed, and many practical application systems were established (Zhang, 1991a; Russ, 2016).

Image analysis system takes the hardware as the physical basis. A variety of image analysis tasks can generally be described in the form of algorithms, and most of the algorithms can be implemented in software, so there are many image analysis systems now only need to use a common general-purpose computer. Special hardware can be used in order to increase the speed of operation or to overcome the limitations of general-purpose computers. In the 1980s and 1990s of twentieth century, people have designed a variety of image cards compatible with industry-standard bus, which can be inserted into the computer or workstation. These image cards include image capture cards for image digitization and temporary storage, arithmetic and logic units for arithmetic and logic operations at video speeds, and memories such as frame buffers. Getting into the twenty-first century, the system’s integration is further improved, and system-on-chip (SOC) has also been rapidly developed. The progress of these hardware not only reduces the cost, but also promotes the development of special software for image processing and analysis. There are a number of image analysis systems and image analysis packages commercially available.

1.2.2.2Diagram of Analysis System

The structure of a basic image analysis system can be represented by Figure 1.8. It is similar to the framework of image-processing system, in which the analysis module is continued after the (optional) processing module. It has also specific modules for collecting, synthesizing, inputting, communicating, storing, and outputting functions. The final output of the analysis is either data (the data measured from the object in image and/or the resulting data of analysis) or the symbolic representation for further understanding, which is different from the image processing system.

Because that the basic information about processing modules has been covered in the first book of this set, the techniques of the analysis module will be discussed in detail in this (second) book. According to the survey on the literature of image engineering, the current image analysis researches are mainly concentrated in the following five aspects:

The following two sections give a brief introduction to some fundamental concepts and terminologies of the image analysis.

1.3.1.1Distance and Neighborhood

If assuming that p, q, and r are three pixels and their coordinates are (xp, yp), (xq, yq), and (xr, yr), respectively, then the distance functiond should satisfy the following three metric conditions:

The neighborhood of the pixels can be defined by distance. The four-neighborhood N4(p) of a pixel p(xp, yp) is defined as (see the pixel r(xr, yr) in Figure 1.9(a)):

$N_4(p)=\left\{r\right|d_4(p,r)=1\}(1.2)$

The city block distanced4(p, r) = |xp – xr| + |yp – yr|.

The eight-neighborhood N8(p) of a pixel p(xp, yp) is defined as the AND set of its four-neighborhood N4(p) and its diagonal neighborhood ND(p) (see pixels marked by s in Figure 1.9(b)), that is:

$N_8(p)=N_4(p){\displaystyle \cup N_{\text{D}}(p)}(1.3)$

So the eight-neighborhood N8(p) of a pixel p(xp, yp) can also be defined as (see the pixels marked by r and s in Figure 1.9(c)):

$N_8(p)=\left\{r\right|d_8(p,r)=1\}(1.4)$

The chessboard distanced8(p, r) = max(|xp – xr|, |yp – yr|).

1.3.1.2Discrete Distance Disc

Given a discrete distance metric dD, a disc with radius R (R ≥ 0) and centered on pixel p is a point set satisfying ∆D(p, R) = {q|dD(p, q) ≤ R}. When the position of the center pixel p can be disregarded, the disc with radius R can also be simply denoted by ∆D(R).

Let ∆i(R), i = 4,8, represent an equidistant disc with the distance di from the center pixel less than or equal to R, and #[∆i(R)] represent the number of pixels, except center pixel, in ∆i(R), then the number of pixels increases in proportion with distance. For the city block disc, there is

$\#[{\Delta }_4(R)]=4{\displaystyle \sum _{j=1}^{R}j=4(1+2+3+\cdots +R)=2R(R+1)}(1.5)$

Similarly, for the chessboard disc, there is

$\#[{\Delta }_8(R)]=8{\displaystyle \sum _{j=1}^{R}j=8(1+2+3+\cdots +R)=4R(R+1)}(1.6)$

In addition, the chessboard disc is actually a square, and so the following formula can also be used to calculate the number of pixels, except the central pixel, in the chessboard disc

$\#[{\Delta }_8(R)]={(2R+1)}^2-1(1.7)$

Here are a few different values of ∆i(R): #[∆4(5)] = 60, #[∆4(6)] = 84, #[∆8(3)] = 48, #[∆8(4)] = 80.

1.3.1.3The Chamfer Distance

The chamfer distance is an integer approximation to the Euclidean distance in the neighborhood. Traveling from pixel p to its 4-neighbors needs simply a horizontal or vertical move (called a-move). Since all displacements are equal according to the symmetry or rotation, the only possible definition of the discrete distance is d4 distance, where a = 1. Traveling from pixel p to its 8-neighborhood cannot be achieved by only a horizontally or vertically move, a diagonal move (called b-move) is also required. Combining these two moves, the chamfer distance is obtained, and can be recorded as da,b. The most natural value for b is 21/2a, but for the simplicity of calculation and for reducing the amount of memory, both a and b should be integers. The most common set of values is a = 3 and b = 4. This set of values can be obtained as follows. Considering that the number of pixels in the horizontal direction between two pixels p and q is nx and the number of pixels in vertical direction between two pixels p and q is ny (without loss of generality, let nx > ny), then the chamfer distance between pixels p and q is

$D(p,q)=(n_x-n_y)a+n_{y}b(1.8)$

The difference between the chamfer distance and Euclidean distance is

$\Delta D(p,q)=\sqrt{n_x^2+n_y^2}-[(n_x-n_y)a+n_{y}b](1.9)$

If a = 1, b = $\sqrt{2}$, computing the derivative of ∆D(p, q) for ny gives

$\Delta D^{\prime }(p,q)=\frac{n_y}{\sqrt{n_x^2+n_y^2}}-(\sqrt{2}-1)(1.10)$

Let the above derivative be zero, computing the extreme of ∆D(p, q) gives

$n_y=\sqrt{(\sqrt{2}-1)/2}{n}_x(1.11)$

The difference between the two distances, ∆D(p, q), will take the maximum value (23/2 – 2)1/2nx ≈ –0.09nx when meeting the above equation (the angle between the straight line and the horizontal axis is about 24.5°). It can be further proved that the maximum of ∆D(p, q) can be minimized when b = 1/21/2 + (21/2 – 1)1/2 = 1.351. As 4/3 ≈ 1.33, so in the chamfer distance a = 3 and b = 4 are taken.

Figure 1.10 shows two examples of equidistant discs based on the chamfer distance, where the left disc is for ∆3,4(27), and the right disc is for ∆a,b.

1.3.3.1Fundamentals

Here are some basic knowledge of the digitizing model (Marchand 2000)

The preimages and domain of the digitized set P are first defined:

There are a variety of digitizing models, in which the quantization is always a many-to-one mapping, so they are irreversible processes. Thus, the same quantized result image may be mapped from different preimages. It can also be said that the objects of different sizes or shapes may have the same discretization results.

Now consider first a simple digitizing model. A square image grid is overlaid on a continuous object S, and a pixel is represented by an intersection point p on the square grid, which is a digitized result of S if and only if p ∈ S. Figure 1.13 shows an example where S is represented by a shaded portion, a black dot represents a pixel p belonging to S, and all p make up a set P.

Here, the distance between the image grid points is also known as the sampling step, which can be denoted h. In the case of a square grid, the sampling step is defined by a real value, and h > 0, which defines the distance between two 4-neighbor pixels.

Example 1.4 Effect of different sampling steps.

In Figure 1.14(a), the continuous set S is digitized with a given sampling step h. Figure 1.14(b) gives the result for the same set S being digitized with another sampling step h′ = 2h. Obviously, such an effect is also equivalent to changing the size of successive sets S by the scale h/h′ and digitizing with the original sampling step h, as shown in Figure 1.14(c).

An analysis of this digitizing model shows that it may lead to some inconsistencies, as illustrated in Figure 1.15:

1.A nonempty set S may be mapped to an empty digitizing set. Figure 1.15(a) gives several examples in which each nonempty set (including two thin objects) does not contain any integer points.

2.This digitizing model is not translation invariant. Figure 1.15(b) gives several examples where the same set S may be mapped to an empty, disconnected, or connected digitized set (the numbers of points in each set are 0, 2, 3, 6, respectively) depending on its position in the grid. In the terminology of image processing, the change of P with the translation of S is called aliasing.

3.Given a digitized set P, it is not guaranteed to accurately characterize its preimage S. Figure 1.15(c) shows a few examples where three dissimilar objects with very different shapes provide the same digitized results (points in a row).

As discussed earlier, a suitable digitizing model should have the following characteristics:

Commonly used digitizing models are square box quantization (SBQ), grid-intersect quantization (GIQ) and object contour quantization (Zhang, 2005b). Only the SBQ and GIQ digitizing models are introduced below.

1.3.3.2The Square Box Quantization

In SBQ, there is a corresponding digitization box Bi = (xi – 1/2, xi + 1/2) × (yi – 1/2, yi + 1/2) for any pixel pi = (xi, yi). Here, a half-open box is defined to ensure that all boxes completely cover the plane. A pixel pi is in the digitized set P of preimage S if and only if Bi ∩ S ≠ ∅, that is, its corresponding digitizing cell Bt intersects S. Figure 1.16 shows the set of digitization (square box with a dot in center) obtained by SBQ from the continuous point set S in Figure 1.13. Wherein the dotted line represents a square segmentation, which is dual with the quadratic sampling grid. It can be seen from the figure that if the square corresponding to a pixel intersects S, then this pixel will appear in the digitizing set produced by its SBQ. That is, the digitized set P obtained from a continuous point set S is the pixel set {pi|Bi ∩ S ≠ ∅}.

The result of SBQ for a continuous line segment is a 4-digit arc. The definition of SBQ guarantees that a nonempty set S will be mapped to a nonempty discrete set P, since each real point can be guaranteed to be uniquely mapped to a discrete point. However, this does not guarantee a complete translation invariance. It can only reduce greatly the aliasing. Figure 1.17 shows several examples in which the continuous sets are the same as in Figure 1.15(b). The numbers of points in each discrete set are 9, 6,9, 6, respectively, which are closer each other than that in Figure 1.15(b).

Finally, it should be pointed out that the following issues in SBQ have not been resolved (Marchand, 2000):

1.3.3.3Grid-Intersect Quantization

GIQ can be defined as follows. Given a thin object C formed by continuous points, its intersection with the grid line is a real point t = (xt, yt). This point may satisfy xt ∈ I or yt ∈ I (where I represents a set of 1-D integers) depending on that C intersects the vertical grid lines or the horizontal grid lines. This point t ∈ C will be mapped to a grid point pi = (xi, yi), where t ∈ (xi – 1/2, xi + 1/2) × (yi – 1/2, yi + 1/2). In special cases (such as xt = xi + 1/2 or yt = yi + 1/2), the point pi located at left or top will be taken as belonging to the discrete set P.

Figure 1.19 shows the results obtained for a curve C using the GIQ. In this example, C is clockwise (as indicated by the arrow in the figure) traced. Any short continuous line between C and the pixel marked by dot is mapped to the corresponding pixel.

It can be proved that the result of GIQ for a continuous straight line segment (α, β) is an 8-digit arc. Further, it can be defined by the intersection of (α, β) and the horizontal or vertical (depending on the slope of (α, β) line.

GIQ is often used as a theoretical model for image acquisition. The aliasing effects generated by the GIQ are shown in Figure 1.20. If the sampling step h is appropriate for the digitization of C, the resulting aliasing effect is similar to the aliasing effect produced by SBQ.

A comparison of the GIQ domain and the SBQ domain is given in the following. Figure 1.21(a) gives the result of digitizing the curve C by the SBQ method (all black dots). Pixels surrounded by small squares are those that do not appear in the GIQ result of digitizing the curve C. Clearly, GIQ reduces the number of pixels in a digitized set. On the other hand, Figure 1.21(b) shows the domain boundaries derived from the GIQ and SBQ results for corresponding C. The dotted line represents the boundary of the union of successive subsets defined by the GIQ result, and the thin line represents the boundary of the union of successive subsets defined by the SBQ result.

As shown in Figure 1.21, the area of the SBQ domain is smaller than the area of the GIQ domain. In this sense, SBQ is more accurate in characterizing a preimage of a given digitized set. However, the shape of the GIQ domain appears to be more appropriate for the description of the curve C than the shape of the SBQ domain. The explanation is that if the sampling step is chosen so that the details in Care larger than the size of the square grid, these details will intersect with the different grid lines. Further, each such intersection will be mapped to one pixel, and such pixels determine a contiguous subset as shown in Figure 1.21(a). In contrast, SBQ maps these details to a group of 4-adjacent pixels that define a wider contiguous region, which is the union of the corresponding digital boxes.

1.3.4.1Digital Arcs

Given a neighborhood and the corresponding movement length, the chamfer distance between two pixels p and q with respect to this neighborhood is the length of the shortest digital arc from p to q. Here, the digital arc may be defined as follows. Given a set of discrete points and the adjacency between them, the digital arc Ppq from point p to point q is defined as the arc Ppq = {pi, i = 0, 1,..., n} satisfying the following conditions (Marchand, 2000):

Different digital arcs (4-digit arcs or 8-digit arcs) can be defined as above, depending on the difference in adjacency (e. g., 4-adjacent or 8-adjacent).

Consider the continuous straight line segment [α, β] (the segment from α to β) in the square grid given in Figure 1.22. Using GIQ, points intersecting the grid lines between [α, β] are mapped to their nearest integer points. When there are two equal-distance closest points, the left discrete point in [α, β] can be first selected. The resulting set of discrete points {pi}i=0,...,n is called a digitized set of [α, β].

1.3.4.2Digital Chords

Discrete linearity is first discussed below, then whether a digital arc is a digital chord will be discussed.

The determination of the digital chord is based on the following principle: Given a digital arc Ppq = {pi}i=0,..., n from p = p0 to q = pn, the distance between the continuous line [pi, pj] and the sum of the segments ∪j[pj, pi+1] can be measured using the discrete distance function and should not exceed a certain threshold (Marchand, 2000). Figure 1.23 shows two examples where the shaded area represents the distance between Ppq and the continuous line segments [pi, pj].

It can be proved that given any two discrete points pi and pj in an 8-digit arc Ppq = {pi}i = 0,..., n and the real point1 in any continuous line segment [pi, pj], if there exists a point pk ∈ Ppq such that d8(ρ, pk) < 1, then Ppq satisfies the property of the chord.

To determine the property of the chord, a polygon that surrounds a digital arc can be first defined, which can include all the continuous segments between the discrete points on the digital arc (as shown by the shaded polygons in Figures 1.24 and 1.25). This polygon will be called a visible polygon, since any other point can be seen from any point in the polygon (i.e., the two points can be connected by a straight line in the polygon). Figures 1.24 and 1.25 show two examples of verifying that the chord properties are true and not true, respectively.

In Figure 1.24, there is always a point pk ∈ Ppq such that d8(ρ, pk) < 1 for all points in the shadow polygon of the digital arc Ppq. In Figure 1.25, there is ρ ∈ (p1, p8) that can have d8(ρ, pk) ≥ 1 for any k = 0, ..., n. In other words, ρ is located outside the visible polygon, or p8 is not visible from p1 in the visible polygon (and vice versa). The failure of chord property indicates that Ppq is not the result of digitizing a line segment.

It can be proved that in the 8-digital space, the result of the line digitization is a digital arc that satisfies the properties of the chord. Conversely, if a digital arc satisfies the property of the chord, it is the result of digitizing the line segments (Marchand, 2000).

1.4.3.1Sequential Implementation

For sequential implementation, the mask is divided into two symmetric submasks. Then, each of those submasks is sequentially applied to the initial distance map containing the values as defined by eq. (1.13) in a forward and backward raster scan, respectively.

Example 1.6 Sequential computation of a discrete distance map.

Consider the image shown in Figure 1.28(a) and the 3 × 3 mask (with a = 3 and b = 4) in Figure 1.28(b). The set B is defined as the central white pixels and P is the set of all pixels. The mask is first divided into two symmetric submasks, as shown in Figure 1.28(c, d), respectively.

Forward pass: The initial distance map [DTD(p)](0) is shown in Figure 1.29(a). The upper submask is positioned at each point of the initial distance map and the value of each pixel is updated by using eq. (1.14), according to the scanning order shown in Figure 1.29(b). For values corresponding to the border of the image, only coefficients of the mask that are contained in the distance map are considered. This pass results in the distance map [DTD(p)](t′) shown in Figure 1.29(c).

Backward pass: In a similar way, the lower submask is positioned at each point of the distance map [DT(p)](t′) and the value of each pixel is updated by using eq. (1.14), according to the scanning order shown in Figure 1.30(a). This pass results in the distance map of the image shown in Figure 1.30(b).

Clearly, the complexity of this algorithm is O(W × H) since the updating formula in eq. (1.14) can be applied in constant time.

1.4.3.2Parallel Implementation

In parallel implementation, each pixel is associated with a processor. The discrete distance map is first initialized using eq. (1.13), and the updating operation given by eq. (1.14) is applied to all pixels for each iteration. The process stops when no change occurs in the discrete distance map for the current iteration.

The parallel implementation can be represented by (p = (xp, yp))

${\text{DT}}^{(t)}(x_p,y_p)=\underset{k,j}{\min }\{{\text{DT}}^{(t-1)}(x_p+k,y_p+l)+M(k,l)\}(1.15)$

where DT(t)(xp, yp) is the iterative value at (xp, yp) for the tth iteration, k and l are the relative positions with respect to the center of mask (0, 0), and M(k, l) represents the mask entry value.

Example 1.7 Parallel computation of a discrete distance map.

Consider again the image shown in Figure 1.26(a). The mask used here is still the original distance mask shown in Figure 1.28(b) and the initial discrete distance map is shown in Figure 1.29(a). Figure 1.31(a, b) gives the first two temporary discrete distance maps obtained during the parallel computation. The distance map in Figure 1.31(c) is the final result.