Image Processing Reference
In-Depth Information
2.2.1 Neighborhoods
Definition 2.6. The n-D digital space or grid is the infinite set Z
n
. The
elements of this set are referred to interchangeably as Points or Vectors or
hypervoxels or vertices (of the underlying graph).
€
Definition 2.7. The neighborhood of a point u ∈ Z
n
is a set of points
Neb(u) from Z
n
that are adjacent to u in some sense.
€
We associate a non-negative (finite or infinite) cost δ : Z
n
×Z
n
→ R
+
∪{0}
between u and its neighbor v so that δ(u,v) = c where v ∈ Neb(u). Note
that though the cost may be real-valued in general, it is usually integral in
most cases.
Example 2.1. In 2-D, u = (2,3) has a neighborhood Neb(2,3) =
{(3,3),(1,3),(2,2),(2,4)} with all 4 costs being 1. This is called the 4-
neighborhood [182].
€
The above notion naturally induces a weighted graph over Z
n
where we
define shortest paths and distances. However, it is impractical to enumerate
the neighborhood of every vertex (point) in an infinite graph, and we need a
compact repeatable structure for the neighborhood at every point for mean-
ingfully building up a geometry. This is done through the introduction of
neighborhood sets.
Definition 2.8. A neighborhood set N is a (finite) set of (difference)
vectors from Z
n
such that ∀u ∈ Z
n
, Neb(u) = {v : ∃w ∈ N,v = u ± w}.
With N, we associate a cost function δ : N → P, where δ(w) is the incremental
distance or arc cost between neighbors separated by w. Hence, ∀v ∈ Neb(u),
δ(u,v) = δ(u−v).
€
Note that since the neighborhood sets apply on difference vectors, the
neighborhoods induced by them are translation invariant, that is, the choice
of origin has no effect on the overall geometry, specifically the neighborhood
structures and paths that are defined using them. We shall often use this fact
in the ensuing analysis.
We often denote a neighborhood set as N(·) to indicate the existence of
one or more parameters on which the set may depend. Various choices of
neighborhood sets and associated cost functions, therefore, induce different
graph structures with different notions of paths and distances.
2.2.1.1
Characterizations of Neighborhood Sets
While any choice of a neighborhood set is possible, certain structures in
them often make the distance geometry interesting and useful. Hence, usually
neighborhood sets are characterized by the following factors [71]. ∀w ∈ N(·) ⊂
Z
n
:
1. Proximity: Any two neighbors are proximal and share a common hyper-
plane. That is, max
i=1
|w
i
|≤ 1.
