Image Processing Reference
In-Depth Information
2.6 Error Estimation and Approximation of Euclidean
Distance
Image processing and other related applications over the digital space Z
n
require a quantification of the continuous space R
n
. Thus, for all types of
Euclidean measures we need some discrete approximation applicable in grid
point space. Among such measures in Euclidean space, the distance mea-
sure is most important. Common approximations of this Euclidean distance,
E
n
include trunc(E
n
) or ⌊E
n
⌋, round(E
n
) or ⌊E
n
+ 0.5⌋, (E
n
)
2
, and ⌈E
n
⌉.
Unfortunately, the first three of these violate the requirements of a metric.
And the last one, though a metric in the topological sense, suffers from high
computational cost and the lack of a suitable neighborhood definition in Z
n
for well-formed shortest path structures and algorithms. Hence, attempts are
made to use digital metrics to approximate E
n
in such cases. Rosenfeld and
Pfaltz [182] show that in 2-D, the octagonal distance provides a good ap-
proximation to E
2
. Using variable neighborhood sets, Yamashita and Ibaraki
present an algorithm in [221] to formulate an approximate digital function.
In this section, we explore the potential of the distance functions discussed
in this chapter, especially m-Neighbor distance d
m
and t-cost distance D
t
as
an approximation for E
n
in n-D grid point space. Depending on the neigh-
borhood set (characterized by its parameters, like m for m-Neighbor distance
d
m
or t for t-cost distance), we have several choices for digital distances in
n-D. Any one of them could be used to approximate E
n
. The best choice
would clearly be the one with minimum error. Thus, a measurement of errors
between d(N·) and E
n
would indicate the goodness of approximation of such
distances. Our main focus, in this section, is to investigate the properties of
errors between d(N(·)) and E
n
.
Naturally, there are two obvious choices for error measures—the absolute
error and the relative or proportional error. Unfortunately, the absolute er-
ror is often not useful (unless it is constrained within a finite subset Z
n
), as
it grows in an unbounded manner as the image dimensions increase. On the
other hand, the proportional error (the ratio between d(N(·)) and E
n
) is usu-
ally bounded. Since any relative error is a linear function of the proportional
error, we conclude that all types of relative errors are also bounded. Thus,
we concentrate on various kinds of relative errors. In some cases, however, we
also use the absolute error with a given image dimension to understand how
the approximations work within finite limits.
Using such measures, we choose an appropriate distance from among
d(N(·)) distances in n-D (that is, make an optimal choice of the parame-
ters of the neighborhood set), which produces the least error to approximate
E
n
. This choice necessitates the computation of the maximum of relative error
between d(N(·)) and E
n
. In this section, we present various bounds for these
errors to make optimal choices of parameters for these distances.
