GEOMETRICAL PROPERTIES OF 3D DIGITIZED IMAGES - Fundamentals of Three-Dimensional Digital Image Processing - page 104

Table 4.6. Examples of distance functions on 3D space ( [ ] means the ceiling
function).

Neighborhood d c (P , Q; β ) = Distance between P and Q, where P = ( i, j, k ) ,
sequence β Q=( l, m, n ) , and β = neighborhood sequence

1 { 6 } d 1 = |i − l| + |j − m| + |k − n|

2 { 18 } d 2 = max(max( |i − l|, |j − m|, |k − n| ) ,

[( | i − l | + | j − m | + | k − n | +1) / 2])

3 { 26 } d 3 =max( |i − l|, |j − m|, |k − n| )

4 { 6 , 18 } d 4 = max(max( |i − l|, |j − m|, |k − n| ) ,

[2( |i − l| + |j − m| + |k − n| +1) / 3])

5 { 18 ,

26 }

d 5 = max(max( | i − l | , | j − m | , | k − n | ) ,

+2) / 5])
d 6 = max(max( |i − l|, |j − m|, |k − n| ) ,
[( |i − l| + |j − m| + |k − n| +2) / 4]+

[2( | i − l | + | j − m | + | k − n |

6 { 6 , 26 } [( |i − l| + |j − m| + |k − n| +3) / 4] ,

[2 { max( |i − l| + |j − m|, |i − l| +
|k − n|, |j − m| + |k − n| )+1 }/ 3])
d 7 = max(max( |i − l|, |j − m|, |k − n| ) ,
[( |i − l| + |j − m| + |k − n| +2) / 3]+

7 { 6 , 18 , 26 } [( |i − l| + |j − m| + |k − n| +4) / 6] ,

[3 { max( |i − l| + |j − m|, |i − l| +
|k − n|, |j − m| + |k − n| )+4 }/ 5])

Remark 4.18. The length of the minimal path for a variable neighborhood
path stated in Def. 4.13 becomes the distance measure if an appropriate neigh-
borhood sequence is adopted. In 2D images, for example, the lengths of the
minimal paths for the 4-connected, the 8-connected, and the octagonal path
reduce to the 4-neighbor, the 8-neighbor, and the octagonal distance, respec-
tively. Then what condition should a neighborhood sequence satisfy in order
that the corresponding minimal path length becomes a distance measure?
The following two theorems provide solutions to this problem for a 2D image
[Yamashita84].

Theorem 4.6. If a neighborhood sequence β M = { b 0 ,b 1 ,...,b M− 1 } satisfies

the equation

b i b i +1 ,

N ⊆N ∀ i, i = 1 , 2 ,...,M − 1 , (4.66)

then the length of the minimal path for the variable neighborhood path with
the above neighborhood sequence becomes a distance measure.

Theorem 4.7. Given the neighborhood sequence β M b 0 ,b 1 ,...,b M− 1 }

consisting of the 4- and the 8-neighborhood, that is, b i = 4 or 8 for all i s,
consider an arbitrary cyclic permutation of the sequence β M ,thatis,

= {

β M

= b K ,b K− 1 ,...,b M− 1 ,b 0 ,b K− 1 .

(4.67)