Image Processing Reference
In-Depth Information
2. Separating Dimension: The dimension m of the separating hyperplane is
bounded by a constant r such that 0 ≤ r ≤ m < n. For example, in 2-D,
4-neighbors have r = 1, m = 1 and consequently only line separation is
allowed. 8-neighbors, on the other hand, have r = 0, m = 0,1, and both
point and line separations are allowed. That is, n−m =
n
i=1
|w
i
| ≤
n−r.
3. Separating Cost: The cost between neighbors is integral. That is, δ(w) ∈
P. Often the cost is taken to be unity.
4. Isotropy and Symmetry: The neighborhood is isotropic in all (discrete)
directions. That is, all permutations and/or reflections of w, φ(w) ∈
N(·).
5. Uniformity: The neighborhood relation is identical at all points along a
path and at all points of the space Z
n
.
In addition, translation invariance follows directly from the difference
vector definition of neighborhood sets.
Though most distances in digital geometry follow the above characteriza-
tion, there are many exceptions where one or more of the above properties are
violated such as:
1. Knight's distance [67] does not obey proximity (see Section 2.3.4),
2. t-cost distances [58] use non-unity costs (see Section 2.3.2),
3. hyperoctagonal distances [59] use path-dependent neighborhoods, albeit
cyclically, and thus violate uniformity (see Section 2.4.1).
Common neighborhood definitions in n-D that generalize the notions of
well-known 2-D and 3-D distances are presented in Table 2.1.
Example 2.2. In 2-D, City Block (4-neighbors) and Chessboard (8-
neighbors) distances are defined by neighborhood sets {(±1,0),(0,±1)} and
{(±1,0),(0,±1),(±1,±1)}, respectively, with costs associated with every ad-
jacency being 1.
€
Using simple combinatorial reasoning we count the number of m-neighbors
of a point in n-D as follows [60]:
Lemma 2.1. ∀x ∈ Z
n
and ∀m,1 ≤ m ≤ n, the number of m-neighbors and
O(m)-adjacent neighbors of x are given by 2
m
, respec-
m
i=1
2
i
n
m
n
i
and
tively.
€
Note that O(m)-adjacent neighbors do not count the central point x.
Should this point be included in the count, the above summation should start
from 0 instead of 1.
Example 2.3. We illustrate well-known neighborhoods in low dimensions.
