Image Processing Reference
In-Depth Information
Reprinted from
Information Sciences
50(1990), P. P. Das and B. N. Chatterji, Octagonal Distances for Digital
Pictures, 123-150, Copyright (1990), with permission from Elsevier.
FIGURE 2.8: Vertices of the octagon of a metric d(B) (using wb B).
2.4.2.1
Best Simple Octagonal Distance
We find from Table 2.6 that the summation part of d(B) is often a fairly
complex integer function. For example, if B = {1,1,2,2}, then the sum is
⌊(α + 1)/6⌋ + ⌊(α + 3)/6⌋ + ⌊(α + 4)/6⌋ + ⌊(α + 5)/6⌋, for α = x
1
+ x
2
,
whereas for B = {1,2}, it is ⌊(α + 1)/3⌋+⌊(α + 2)/3⌋ = ⌈2α/3⌉. This is not
a coincidence. For some well-behaved B
′
s the sum turns out to be a single
ceiling function. Such distances are easy to handle and e
cient to perform
computations with. These are called simple octagonal distances [55]. The
following theorem from [55] shows that for every p and p ≤ f(p) ≤ 2p, there
exists a unique B that defines a simple d(B).
Theorem 2.17. ∀x ∈ Σ
2
, d(x;B) is simple and of the form max(x
1
,x
2
,⌈(x
1
+
x
2
)/m⌉) iff b(i) = ⌊if(p)/p⌋−⌊(i− 1)f(p)/p⌋, 1 ≤ i ≤ p, where 1 < m < 2,
m = f(p)/p, and f(p) and p are relatively prime. In addition, for m = 1,
B = {1} and d(x;B) = x
1
+ x
2
, and for m = 2, B = {2} and d(x;B) =
max(x
1
,x
2
) are also simple.
€
Example 2.14. For B = {1,1,2,1,2}, d(x;B) = max(x
1
,x
2
,⌈5(x
1
+x
2
)/7⌉)
is simple and has special significance for its excellent accuracy in approxima-
tion.
Examples of a few other simple octagonal distances are presented in Table
2.6. These are marked as “Simple” in the table.
€
Minimization of the average absolute (normalized) and average relative
errors of these simple distances with regard to the Euclidean norm is used
to identify the best approximate digital distances in 2-D digital geometry.
It is shown in [55] that the neighborhood sequences {2}, {1,2}, {1,1,2}, and
{1,1,2,1,2}have special significance in distance measurement in digital geom-
etry as they are simple, and no octagonal distance of reasonable neighborhood
structure is expected to offer a better accuracy of approximation.
