Distance Functions Based on Multiple Types of Weighted Steps Combined with Neighborhood Sequences

Abstract

In this paper, we present a general framework for digital distance functions, defined as minimal cost paths, on the square grid. Each path is a sequence of pixels, where any two consecutive pixels are adjacent and associated with a weight. The allowed weights between any two adjacent pixels along a path are given by a weight sequence, which can hold an arbitrary number of weights. We build on our previous results, where only two or three unique weights are considered, and present a framework that allows any number of weights. We show that the rotational dependency can be very low when as few as three or four unique weights are used. Moreover, by using n weights, the Euclidean distance can be perfectly obtained on the perimeter of a square with side length 2n. A sufficient condition for weight sequences to provide metrics is proven.

1 Introduction

In a digital space (given for example by the pixels on a computer screen), not all properties of the Euclidean geometry are fulfilled. This is mainly due to the discrete (as opposed to continuous) structure of digital spaces. In the digital geometry framework, a classical way to define distance functions and metrics is by means of shortest paths or minimal cost paths. By doing so, the distance between two points is simply the sum of weights along a given path. With appropriate, efficient algorithms, this allows completely error-free, and fast, computation of the distances in two and higher- dimensional digital spaces [1, 17, 21].

The digital approach we follow, where connected paths are used to define distance functions, is fundamentally different from the approach when Euclidean distances are computed. This is usually done by vector propagation [5, 14], fast marching [16], or by separable algorithms [2, 4]. These algorithms either result in errors (i.e., deviations from the metrics under consideration due to approximation errors or deficiencies in the algorithm definition) and/or they don’t generalize to so-called constrained distance transform. See the discussion in [18]. Therefore, we believe that it is important to develop both the theory based on these digital distances and practical algorithms for image processing that can effectively utilize these distances.

The cityblock and chessboard distances are the two digital distances first described in the literature [15]. These distance functions have high rotational dependency, but are easy and efficient to compute. The theory of digital distances has developed rapidly from the 1980s. The weighted (chamfer) distances [1], where the grid points together with costs to local neighbors form a graph in which the minimal cost path is the distance, are a well-known and often used concept in image processing. Contrary to weighted distances, the allowed steps may vary along the path with distances based on neighborhood sequences from a predefined set of steps [6], for instance, by mixing the cityblock and chessboard neighborhood. In [20, 22], the concept of weighted distances is generalized by allowing the size of the neighborhood to vary along the path. In this way, we get a distance function with potentially lower rotational dependency compared to when a fixed neighborhood is used. Recent results on Euclidean distance approximation are found in [3, 7, 9].

In this paper, we extend the idea presented in [19], where distances defined by three different local steps were considered. We are continuing the investigations of [13] and allow using a fixed, but arbitrarily large, number of possible local steps in the neighborhood sequence. Each of the allowed steps use only the 8-neighborhood of the pixels, but with different weights. Our main motivation is to provide a framework for digital distance functions that have as low rotational dependency as possible, which can be used to develop efficient image processing tools. Here, this is obtained by finding weight sequences that approximate the Euclidean distance. Given a distance function, a distance transform is a transform where each element in a set is assigned the distance to the closest (as given by the distance function) element in a complementary set. The result of a distance transform is called a distance map. This tool is often used in image processing and computer graphics [8]. In the digital geometry setting, it is very natural to define distance functions by minimal cost paths. A possible application of our results could be by designing an algorithm for computing the distance map.

The structure of the paper is as follows. In the next section, we present the basic definitions. In Sect. 3, some theoretical results are detailed, e.g., a formula to compute the point-to-point distance. In Sect. 4, the metric properties of these distances are discussed. In Sect. 5, parameter optimization is shown to obtain distances with low rotational dependency, i.e., approximating the Euclidean distance in this sense. Moreover, it is shown that the exact Euclidean distance can be obtained on the perimeter of a square. Finally, conclusions close the paper.

2 Definitions

In this section, we give the basic concepts and fix our notations. First some notions are recalled from the literature mentioned earlier.

We denote the set of integers by ${\mathbb {Z}}$ and the set of nonnegative integers by $\mathbb N$, and the set of positive real numbers is denoted by $\mathbb R^+$.

In this paper, we consider points of the digital two-dimensional (square) grid, with integer coordinates, represented by $\mathbb Z^2$. Of course, in image processing, each grid point is associated with a picture element, pixel. In a cityblock (resp. chessboard) distance, distinct points with unit difference in at most one (resp. two) of the coordinates have unit distance. Here, we use the notion of 1- and 2-neighbors in the following sense: Two grid points $P_1=(x_1,y_1),P_2=(x_2,y_2) \in \mathbb {Z}^2$ are $\rho$-neighbors, $\rho \in \{1,2\}$, if

$$\begin{aligned}&|x_1 - x_2 | + |y_1 - y_2| \le \rho \text { and} \nonumber \\&\quad \max \left\{ | x_1 - x_2 |, |y_1 - y_2|\right\} = 1. \end{aligned}$$

(1)

The points are strict $\rho$-neighbors if the equality in (1) is attained. Two points are adjacent if they are $\rho$-neighbors for some $\rho \in \{1,2\}$.

From now on, we will use the notion of a path as follows:

Definition 1

(path) A path in a grid is a sequence of adjacent grid points. A path $\Pi =(P_0 , P_1 ,\dots , P_n)$ is a path of n steps where for all $i \in \{1,2,\dots ,n\}$, $P_{i-1}$ and $P_{i}$ are adjacent. The path $\Pi$ connects $P_0$ and $P_n$. We may also say that the path starts from $P_0$ and arrives to $P_n$, i.e., they are its startpoint and endpoint, respectively.

Now we recall the distances defined by neighborhood sequences [6, 10].

Definition 2

(neighborhood sequence distance) A neighborhood sequence (ns) B is a sequence $B=\left( b(i)\right) _{i=1}^{\infty }$ of neighborhood relations, i.e., $b(i)\in \{1,2\}$ for all i.

Let $P, Q\in {\mathbb {Z}}^2$, then a finite sequence of points $\Pi (P,Q;B)$ of the form $(P=P_0,$ $P_1,\dots ,P_m=Q)$, where $P_{i-1},$ $P_i \in {\mathbb {Z}}^2$ are b(i)-neighbors for $1\le i\le m$, is called a B-path from P to Q, and $m=\vert \Pi (P,Q;B)\vert$ is the length of the path.

Denote by $\Pi ^*(P,Q;B)$ a shortest path (i.e., a B-path with minimal length) from P to Q, and set $d(P,Q;B)=\vert \Pi ^*(P,Q;B)\vert$. We call d(P, Q; B) the B-distance of P and Q.

Notice that unit weights are associated with both cityblock and chessboard steps; however, the neighborhood sequence gives constraints on which type of steps could be used.

The shortest B-path between any two points can be computed by a greedy algorithm (see, e.g., [10]). A formula to compute B-distances can be found in [11, 12] for the square grid.

Another way to obtain low rotationally dependent distance functions is to use a fixed neighborhood relation, but different weights for the different types of steps. The so-obtained weighted distances are also well known and widely used:

Definition 3

(weighted distance [1]) Let $\alpha ,\beta \in \mathbb R^+$ be positive weights. Let $P,Q\in {\mathbb {Z}}^2$ be two points. Consider a path connecting P and Q, the steps to 1-neighbors have weight $\alpha$ and the steps between strict 2-neighbors have weight $\beta$. The $(\alpha ,\beta )$-weight of the path is the sum of the weights of its steps. A path starting at P and arriving at Q is minimal weighted, if there is no path connecting P and Q with less weight. The $(\alpha ,\beta )$-weighted distance $d_{\alpha ,\beta }(P,Q)$ is the weight of the minimal weighted path(s) connecting P and Q.

Notice that in weight distances one can always use any of the two possible steps; thus, any path can be considered. Usually, the $\alpha \le \beta \le 2\alpha$ condition is applied. The ratio of the weights gives the rotational dependency of the distance function. Therefore, when real number weights are used, $\alpha$ is usually set to one.

Now, we recall a kind of mixture of the previous two types of digital distances.

Definition 4

(weighted neighborhood sequence distance [18]) Let $\gamma \ge 1$ be a positive weight and B be a neighborhood sequence. Let $P,Q\in {\mathbb {Z}}^2$ be two points. Consider a B-path connecting P and Q, where the steps to 1-neighbors have unit weight, while the steps between strict 2-neighbors have weight $\gamma$. The weight of the path is computed accordingly. The $\gamma$-weighted B-distance $d_\gamma (P,Q;B)$ is the weight of the minimal weighted B-path(s) connecting P and Q.

A more complex mixture allowing more flexibility is recalled from [19] by extending the notion of neighborhood sequences to three-neighbor weighted neighborhood sequences.

Definition 5

(three-neighbor weighted neighborhood sequence distance [19]) Let $\gamma \in \mathbb R^+$ be a positive weight and let $B=\left( b(i)\right) _{i=1}^{\infty }$ with $b(i)\in \{1,2,\gamma \}$, for all i. B is called a three-neighbor weighted neighborhood sequence.

Let $P, Q\in {\mathbb {Z}}^2$, then the path $\Pi = (P=P_0,P_1,\dots ,P_m=Q)$ is a B-path if $P_{i-1}, P_i$ are 1-neighbors if $b(i)=1$ for $1\le i\le m$.

The weight of steps to strict 2-neighbors with $b(i)=\gamma$ is $\gamma$; all other steps of $\Pi$ have unit weight. The weight of $\Pi$ is computed accordingly. Finally, the three-neighbor weighted neighborhood sequence distance of $P,Q\in {\mathbb {Z}}^2$ is the weight of the minimal weighted B-path(s) connecting P and Q.

Notice that the meaning of 1’s and 2’s is the same as in Definition 2 (neighborhood sequence distances), i.e., the allowed cityblock and chessboard steps, respectively, with unit weights.

In this paper, we use a further generalization, the weight (or chamfer) sequences, instead of neighborhood sequences. The modified, more general description is as follows:

Definition 6

(weight sequence distance) Let $m\in \mathbb N, \ m\ge 0$ be the number of the used weights, and let $S= \{1, \infty \} \cup \{ w_1, \dots , w_m \}$ be the weight set including 1, the sign $\infty$ and the used weights ($w_i\in \mathbb R$, $w_i >1$ for all $i\in \{1,\dots ,m\}$).

A weight sequence is $W=\left( c(i)\right) _{i=1}^{\infty }$, where $c(i)\in S$, for all $i \in \mathbb N$.

Let $P, Q\in {\mathbb {Z}}^2$, then the weight of the path $\Pi = (P=P_0,P_1,\dots ,P_m=Q)$ is the sum of the weights of its steps, where the weight of the jth step is specified as ${\left\{ \begin{array}{ll} c(j), &{} \hbox {if the } j \hbox {th step is a step to a strict 2-neighbor;} \\ 1, &{} \hbox {otherwise.} \end{array}\right. }$

The W-distance d(P, Q; W) of P and Q is then defined as the weight of the minimal weighted path connecting P and Q.

Notice that all cityblock paths are valid for d(P, Q; W) and have the same weight as in the cityblock distance. Therefore, d(P, Q; W) is upper bounded by the cityblock distance. When the $\infty$ sign in used W for some step i ($c(i)=\infty$), it denotes an arbitrary large weight that prevents paths with a strict 2-neighbor at step i to be minimal.

In a W-distance, by mixing the features of neighborhood sequences and weighted distances, the cost of a move to a 1-neighbor is 1 in every step, and the cost of a move to a strict 2-neighbor is given by the actual element c(j) of the weight sequence.

We should also highlight the difference of the new notion shown in the previous definition and the earlier concepts. The value 1 in the earlier concepts, e.g., in neighborhood sequences B including three-neighbor weighted neighborhood sequences (see Definitions 2 and 5), means that only a step to a cityblock neighbor (1-neighbor) is allowed, whereas a step to a diagonal neighbor (strict 2-neighbor) is forbidden. The sign $\infty$ is used to denote this constraint in weight sequences (Definition 6). On the other side, in neighborhood sequences value 2 refers for the possibility to use 2-steps with a unit cost. This possibility is represented by value 1 in weight sequences, fitting to the new concept (the cost of diagonal steps are shown in the weight sequence).

In this work, by the set S, we allow $m+2$ different neighborhood relations (possible steps by various weights) in our paths:

• a traditional 1-step is a step between 1-neighbors with unit weights, the sign $\infty$ denote these steps in W (practically, strict 2-steps are not allowed, see Lemma 1);

• a traditional 2-step is a step between 2-neighbors with unit weights, and they are denoted by value 1 in W;

and if $m>0$, then, by the used weights $w_1, \dots , w_m$ the further steps are as follows:

• weighted 2-steps: the steps between 1-neighbors with unit weights, and between strict 2-neighbors with weight $w_k$ (where $1\le k \le m$) with $c(i)=w_k$ for some i in W.

In this paper, the weight sequence W can contain $m+2$ values, “weights”, according to a predefined set S, i.e., $W=(c(i))_{i=1}^{\infty }$ where $c(i)\in S$.

The sum of the weights along the path can also be written in a formal way:

$$\begin{aligned}&\sum \limits _{i=1}^n \delta _i , \\&\text { where } \delta _i = {\left\{ \begin{array}{ll} c(i), &{} \text { if } P_{i-1} \text { and } P_i \text { are strict} \ 2 \text {-neighbors}; \\ 1, &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$

When the weight sequence W is fixed, we use the term W-path for paths having finite cost as defined by the weight sequence W.

Lemma 1

Let $P,Q\in {\mathbb {Z}}^2$, S be a weight set and W be a weight sequence. If $\Pi$ is a minimal W-path between P and Q, then it does not contain any steps to strict 2-neighbors by any weight $w_i >2$.

Proof

Let us assume, on the contrary, that $\Pi = (P,P_1,\dots ,P_j,P_{j+1},\dots ,P_n=Q)$ is a minimal path connecting P and Q and it has a diagonal step (step to a strict 2-neighbor) between $P_j$ and $P_{j+1}$ such that $c(j+1)>2$. Let $(x,y)=P_{j+1}-P_j$ be the “direction” of this step. (Obviously, $|x|=|y|=1$.) Then, let $\Pi '$ be defined as the concatenation of

• the beginning sequence of the original path $\Pi$: $(P,P_1,\dots ,P_j)$,

• an x shifted sequence of the remaining part: $P_{j+1}-(x,0),P_{j+2}-(x,0),\dots , P_n-(x,0)$,

• and finally, Q.

One can see that $\Pi '$ is also a W-path connecting P and Q, and it has one more steps than $\Pi$ has. This last step is a step to a 1-neighbor; thus, it has a unit weight.

Now, the weight of $\Pi$ can be written as a sum of three parts: the sum of weights of the first j steps, then $c(j+1)$, and then the sum of the weights of the steps $j+2,\dots n$.

The weights of $\Pi '$ can also be computed: it has exactly the same value for the first j steps since it is identical to $\Pi$ up to that point. Now, it has a unit weight (from $P_j$ to $P_j+(0,y) = P_{j+1}-(x,0)$), then it has exactly the same weights between the $(j+2)$-nd and nth steps as $\Pi$, and finally, one unit weight is added for the additional step.

Therefore, $|\Pi |-|\Pi '| = c(j+1) -2 >0$. This contradicts our assumption that $\Pi$ was a minimal weighted W-path between P and Q. $\square$

This fact allows reducing our notation, the steps and also the values in the weight sequence W with weight $\infty$ (together with all values that are larger than 2) can be replaced by the same number (and it could be any number that is larger than 2). We use the notation $\infty$ for these values in this paper. Based on this, we can say that in our paths only weights between 1 and 2 play important role.

Table 1 summarizes the possible steps of various paths based on the above definitions.

3 Computing the Distance

We start this section by an example which highlights an important property of the proposed distance function.

Example 1

Given the weight sequence $W=(1, 1.9, 1.8, 1, 1.5, \dots )$, the shortest W-path from (0, 0) to (2, 2) includes two diagonal steps with weights $1+1.9 = 2.9$. However, the shortest W-paths from (0, 0) to (3, 3) is not a continuation of the former path, but consists of a diagonal step to (1, 1) with weight 1, then two consecutive 1-steps (to either (1, 2) or (2, 1) and, then, to (2, 2)) and finally a diagonal step with weight 1: in this way, the W-distance of (0, 0) and (3, 3) is 4. Comparing these shortest paths with four steps, one can reach the point (3, 3) in three steps from (0, 0), but the weight of these three diagonal steps 4.7 together.

The W-distance between (0, 0) and (2, 3) is 3.8 and is given by the shortest path including a diagonal step (weight 1), a 1-step, and a diagonal step by weight 1.8.

By Example 1, one can see that a greedy algorithm cannot be used to provide shortest paths. If a smaller weight appears after a larger weight in W, it may be needed in the shortest path depending on both the weight sequence and on the difference of the coordinate values of the points.

Now we give a formula for computing the distance between any two grid points. The formula is used for finding optimal parameters in Sect. 5. Before the theorem, we define a technical notation which will also be helpful later on.

Definition 7

Let a weight sequence $W=(c(i))_{i=1}^\infty$ (based on a weight set $S=\{1, \infty , w_3, \dots , w_m\}$) be given. Let $m,n\in \mathbb N$ such that $n\ge m$. Then, I(n, m) contains the indices of the smallest m weight values among the first n elements of W, i.e., among $(c(1),\dots ,c(n))$.

Theorem 1

Let the weight sequence $W=(c(i))_{i=1}^\infty$ (based on a weight set $S=\{1, \infty , w_3, \dots , w_m\}$) and the point $P(x,y)\in \mathbb {Z}^2$, where $x\ge y\ge 0$, be given. Then, the W-distance of P from the Origin $\mathbf (0)$ is given by

$$\begin{aligned}&d(\mathbf {0},(x,y);W)\nonumber \\&\quad =\min _{f \in \{0..y\}} \left\{ \left. x+y-2f+\sum \limits _{i\in I(x+y-f ,f)} c(i) \right| ~ f\in {\mathbb {Z}}, \right. \nonumber \\&0\le \left. f\le y \right\} . \end{aligned}$$

(2)

Proof

The number of steps in a minimal weighted path from the point ${\mathbf {0}}(0,0)$ to the point P(x, y) is between x and $x+y$, since the former case is obtained when y diagonal steps are in the path and the latter case is obtained by using only 1-steps, which are always allowed. In this latter case, the weight of the path is exactly $x+y$ (each step is with a unit weight). The weight of a path of the former case is given by $x-y$ unit weight 1-steps and y strict 2-steps. If the path starting at $\mathbf {0}$ and arriving to P has minimal weight, then the y smallest weights of the first x elements of W are used. (However, this does not guarantee that there are no W-paths between the points with less weights, but larger number of steps.) Generally, one needs to check the weight of the minimal weighted paths between the points for each possible length (number of steps) between x and $x+y$ inclusively. Let f be the parameter giving the number of steps to strict 2-neighbors in the path. Then, f could be any integer between 0 (specifying path length $x+y$) and y (implying path length x). Having f steps to strict 2-neighbors, the path connecting the Origin with P needs $x+y-2f$ steps to 1-neighbors, and thus, it contains $x+y-f$ steps (at least). To find the minimal weight for paths with a given value of f, one needs to find the f smallest weights among the first $x+y-f$ elements of W, sum up their values with $x+y-2f$. To obtain the W-distance, the minimal such value is chosen for the possible values of f. Thus, the formula of the theorem is proven. $\square$

Since the roles of the x- and y-coordinate are similar, and our distance function is translation invariant, one can compute the W-distance of any pair of points of ${\mathbb {Z}}^2$ by the previous formula.

The proposed concept of path-based distances generalizes several traditional distance functions. Proposition 1 gives the connection to weighted distances, and Proposition 2 gives the connection to neighborhood sequence distances.

Proposition 1

Let $\alpha ,\beta \in \mathbb R^+$. Then, $d_{\alpha ,\beta }(P,Q) = \alpha \cdot d(P,Q;W)$ with the weight set $S=\{1,\infty ,w\}$, $w = \frac{\beta }{\alpha }$, and $W = (c(i))_{i=1}^\infty$ with $c(i) = w$ for all $i\in \mathbb N$.

Proof

It is obvious by the definitions of these distances that d(P, Q; W) gives the traditional $(\alpha ,\beta )$-weighted distance $d_{\alpha ,\beta }(P,Q)$. $\square$

Using zero additional weights, one can obtain exactly the traditional distances based on neighborhood sequences:

Proposition 2

Let $B=(b(i))_{i=1}^\infty$ be a neighborhood sequence. Then, we have the equality $d(P,Q;B) = d(P,Q;W)$ where $S = \{1, \infty \}$ and $W=(c(i))_{i=1}^\infty$ with $c(i)= {\left\{ \begin{array}{ll} 1, &{} \hbox {if } b(i)=2; \hbox { and } \\ \infty , &{} \hbox {if } b(i)=1. \end{array}\right. }$

Proof

Let $B=(b(i))_{i=1}^\infty$ and W be given according to the theorem. Then, $d(P,Q;B) = d(P,Q;W)$ for any $P,Q\in {\mathbb {Z}}^2$ since the shortest paths are identical in the two scenarios (diagonal steps are either allowed by unit weights or they cannot appear at the given position in a shortest path).

Since this relation between neighborhood sequences and weight sequences containing only elements of S is a bijection, the converse also holds. $\square$

Remark 1

It is noted here that the weight sequence $W=(1)_{i=1}^\infty$ defines the chessboard distance, since steps to 2-neighbors are always allowed with unit cost. The weight sequence $W=(\infty )_{i=1}^\infty$ defines the cityblock distance, since, in this case, in any path with finite sum of weights only steps to 1-neighbors may occur (and their cost is always a unit).

The following propositions, Propositions 3 and 4, show that the previously presented weighted neighborhood sequence distance ([18]) and three-neighbor weighted neighborhood sequence distances ([19]) are special cases of the proposed distance functions.

Proposition 3

Let $B=(b(i))_{i=1}^\infty$ be a neighborhood sequence and $\gamma$ be a weight. We have $d_\gamma (P,Q;B) = d(P,Q;W)$ with $S=\{1,\infty ,\gamma \}$ and $W = (c(i))_{i=1}^\infty$ with $c(i)= {\left\{ \begin{array}{ll} \gamma , &{} \hbox {if } b(i)=2; \\ \infty , &{} \hbox {if } b(i)=1. \end{array}\right. }$

Proof

With $S=\{1,\infty ,\gamma \}$ (i.e., having the additional weight $w=\gamma$) and W, the distances defined by w-weighted neighborhood sequences are obtained, the shortest paths of that scene coincide with the shortest paths based on the weight sequence W. Consequently, $d_\gamma (P,Q;B) = d(P,Q;W)$ for any $P,Q\in {\mathbb {Z}}^2$.

By the condition $\gamma \ne 1$, there is a bijection between $\gamma$, B and W, and thus, every W-distance in the above form corresponds to a weighted neighborhood sequence distance. $\square$

Based on similar weight sets, we can also characterize the three-neighbor weighted neighborhood sequence distances:

Proposition 4

Let $\gamma$ be a positive weight, and $B=(b(i))_{i=1}^\infty$ be a three-neighbor weighted neighborhood sequence with $b(i)\in \{1,2,\gamma \}$ for every $i\in \mathbb N$. Then, the distances defined by three types of local steps, i.e., the three-neighbor weighted neighborhood sequence distances can be computed as the distance d(P, Q; W) between and point pair $P,Q\in {\mathbb {Z}}^2$ with the weight set $S=\{1,\infty , \gamma \}$ and $W = (c(i))_{i=1}^\infty$ by $c(i)= {\left\{ \begin{array}{ll} \infty , &{} \hbox {if } b(i)=1; \\ 1, &{} \hbox {if } b(i)=2; \\ \gamma , &{} \hbox {if } b(i)=\gamma . \end{array}\right. }$

Proof

By using $S=\{1,\infty , w\}$ with $w=\gamma$ and the weight sequence W, the shortest paths and also the distances of the two scenarios coincide. With the condition $1<\gamma <2$, there is also a bijection between these W-distances and the three-neighbor weighted neighborhood sequence distances. $\square$

Table 1 summarizes the links between previously defined distance functions and the proposed distance function, the notation and the meaning of the different elements in the weight sequence.

Table 1 Various distances, possible elements of the (neighborhood or weight) sequences and their meaning, i.e., the weights of possible steps

4 Metrical Properties

A metric is a (distance) function which satisfies the metric properties. It is easy to find a weight sequence that generates a distance not satisfying the metric conditions.

Recall that a distance function d is a metric if it satisfies the following three properties:

• $d(p,q)\ge 0$ for any point pair p, q, moreover $d(p,q)=0$ if and only if $p=q$. (positive definiteness)

• $d(p,q)=d(q,p)$ for any point pair p, q. (symmetry)

• $d(p,q)+d(q,r)\ge d(p,r)$ for any three points p, q, r. (triangular inequality)

In the case of distances defined by weight sequences on the square grid, the first two properties, namely the positive definiteness and the symmetry, are always satisfied (one may check the definitions and the results obtained in the previous sections). However, the triangular inequality is problematic in some cases. Let us see some examples.

Example 2

Let the weight sequence contain additional weights $\{1.2,1.3\}$. The weight sequence $W=(1,1.2,1.3,...)$ define a non metrical W-distance: Let $(-1,-1)$, (0, 0), and (1, 1) be three points of the grid, then

$$\begin{aligned}&d((-1,-1),(0,0);W) = 1,d((0,0),(1,1);W) = 1,\\&\quad d((-1,-1),(1,1);W) = 1+1.2=2.2. \end{aligned}$$

Therefore, the triangular inequality fails for this W-distance.

Example 3

Let the weight set be $\{1.2,1.4,1.8\}$. Further, let $W=(1.8,1.2,1.2,1.4,1.2,1.8,1.4,1.2,...)$. Then,

$$\begin{aligned} d((7,6),(3,10);W)= & {} 5.6, d((3,10),(0,12);W) \\= & {} 3.4, d((7,6),(0,12);W) = 9.2, \end{aligned}$$

but $5.6+3.4=9 < 9.2$. Thus, the triangular inequality does not hold for these three points for this W-distance.

To show some sufficient conditions, we first state the following technical lemma.

Lemma 2

Let us consider two weight sequences $W_1=(c_1(i))_{i=1}^\infty$ and $W_2=(c_2(i))_{i=1}^\infty$ with the following property: for every $n,m\in \mathbb N$ ($m\le n$)

$$\begin{aligned} \sum \limits _{i\in I_1(n,m)} c_1(i) \le \sum \limits _{i\in I_2(n,m)} c_2(i) \end{aligned}$$

(where, according to Definition 7, $|I_1(n,m)|=|I_2(n,m)|=m$ and they contain the indices of the m smallest weights/elements among the first n elements of $W_1$ and $W_2$, respectively). Then, for any two points $P,Q\in {\mathbb {Z}}^2$,

$$\begin{aligned} d(P,Q;W_1) \le d(P,Q;W_2). \end{aligned}$$

Proof

Let us assume, by contrary, that there are two points P and Q of ${\mathbb {Z}}^2$ such that $d(P,Q;W_1) > d(P,Q;W_2)$. Then, let the $W_2$-distance of P and Q be defined by a minimal weighted path having n steps including m diagonal steps (for some $n,m \in \mathbb N$). In this case, actually $d(P,Q;W_2) = n-m + \sum _{i\in I_2(n,m)} c_2(i)$. By the condition of Lemma 2, one can also construct a $W_1$-path with n steps between P and Q having m diagonal steps with cost $n-m + \sum _{i\in I_1(n,m)} c_1(i)$. However, since $\sum _{i\in I_1(n,m)} c_1(i) \le \sum _{i\in I_2(n,m)} c_2(i)$, the cost of this path is not more than $d(P,Q;W_2)$. Therefore, $d(P,Q;W_1)$ cannot be larger than $d(P,Q;W_2)$. The lemma is proven by this contradiction. $\square$

Now, based on this result, we are able to provide a sufficient condition for the weight sequence to define a distance that is a metric.

Theorem 2

Let W be a weight sequence. If W contains the weights in a non-increasing order, then it defines a metric.

Proof

We need to prove only the triangular inequality.

Let us assume, by contradiction, that there are three points $P,Q,R\in {\mathbb {Z}}^2$ such that $d(P,Q;W) + d(Q,R; W) < d(P,R; W)$. Then, let us consider $\Pi _{P,Q}$ as a shortest W-path starting from P to Q. Let $n_1$ be the number of its steps. Let us consider also $\Pi _{Q,R}$ as a shortest W-path starting from Q to R. Let $n_2$ be the number of its steps and m be the number of its diagonal steps. Then, $d(Q,R;W) = n_2-m + \sum _{i\in I(n_2,m)} c(i)$. Further, consider the path $\Pi _{P,R}$ that is the extension of $\Pi _{P,Q}$ by $\Pi '_{Q,R}$ which is the same path (including the same steps to adjacent points) as $\Pi _{Q,R}$. Clearly, $\Pi _{P,R}$ it is a path from P to R. Let us analyze its cost with the weight sequence W. It is clear that its first part (n steps from P to Q) is exactly the same and uses the same weights as $\Pi _{P,Q}$; thus, its cost is d(P, Q; W). Now, let $W'=(c'(i))_{i=1}^\infty = (c(i))_{i=n+1}^\infty$, i.e., it is the remaining sequence after cutting the first n elements of W out. Actually, continuing $\Pi _{P,Q}$ from the point Q we are at $c(n+1)$ in W, and actually, it is the same as $c'(1)$. Continuing $\Pi _{P,Q}$ by the $W'$-path, $\Pi '_{Q,R}$ from Q defines a W-path, especially, $\Pi _{P,R}$ from P. Since W contains the weights in a non-increasing order, the condition of Lemma 2 holds for W and $W'$, and thus, the $W'$-path connecting Q and R with the same steps as $\Pi '_{Q,R}$ cannot have a larger cost than $\Pi _{Q,R}$ has. Thus, the sum of the whole W-path from P to R cannot have a larger cost than the sum of the costs of $\Pi _{P,Q}$ and $\Pi _{Q,R}$. It is contradicting to our assumption that the triangular inequality fails; thus, the theorem is proven. $\square$

5 Approximation of the Euclidean Distance

In this section, we give some results on the approximation of the Euclidean distance. We find weight sequences that give a small difference between the Euclidean distance $d_E(\cdot , \cdot )$ and the weight sequence distance $d(\cdot , \cdot ; W)$ between the point $\mathbf {0}$ and the point (x, y), where $x\ge y \ge 0$. See also [7]. The general case follows by symmetry as discussed in the previous section about equation (2). As a technical result, we show special cases when greedy shortest path algorithm works.

Lemma 3

If the weight sequence W is non-decreasing and all elements in W are smaller than or equal to 2, then the distance value in equation (2) is given by

$$\begin{aligned} d(\mathbf 0,(x,y);W)= x-y+\sum \limits _{i=1}^y c(i) \end{aligned}$$

Proof

Since the lowest weights are the first in the weight sequence, we have

$$\begin{aligned}&\min \limits _{f\in \{0,\dots ,y\}} \left\{ x+y-2f +\sum \limits _{i\in I(x+y-f,f)} c(i) \right\} \nonumber \\&\quad =\min \limits _{f\in \{0,\dots ,y\}} \left\{ x+y-2f+\sum \limits _{i=1}^{f} c(i)\right\} , \end{aligned}$$

where the empty sum from $i=1$ to $i=0$ is counted as 0. Since the weights are smaller than or equal to 2, the optimum is attained for $f=y$, so

$$\begin{aligned} \min \limits _{f\in \{0,\dots ,y\}} \left\{ x+y-2f+\sum \limits _{i=1}^{f} c(i)\right\} = x-y+\sum \limits _{i=1}^y c(i). \end{aligned}$$

(3)

$\square$

Now, we give a set of weights that can be used to obtain error-free W-distance on the border points of a square.

Theorem 3

Given an integer $x>0$, the Euclidean distance values from (0, 0) to each point of the set $\{(x,y)\in {\mathbb {Z}}^2, 0\le y\le x \}$ are given without errors by the weight sequence $W=(c(i))_{i=1}^\infty$ with $c(i) = \left( 1+\sqrt{x^2+i^2}-\sqrt{x^2+(i-1)^2}\right)$ for $1\le i \le x$.

Proof

All weights in the weight sequence are smaller than 2, and the sequence is increasing, so by Lemma 3

$$\begin{aligned} d\left( \mathbf {0}, (x,y); W\right)&= x-y + \sum \limits _{i=1}^y c(i)\\&= x-y+\sum _{i=1}^y \left( 1+\sqrt{x^2+i^2}\right. \\&\left. \quad -\sqrt{x^2+(i-1)^2}\right) \\&= x-y+\sqrt{x^2+y^2}-(x-y)\\&= d_E(\mathbf {0},(x,y)). \end{aligned}$$

$\square$

By the previous theorem, one can easily derive the following consequences.

Corollary 1

Observing the weight sequence W defined in Theorem 3, we can conclude the following facts.

• 1. The average of the x elements of the weight sequence W is $\sqrt{2}$.

• 2. As $x\longrightarrow \infty$, in the limit the first element of the sequence $c(1) \longrightarrow 1$ ($c(1)>1$, but in the limit it goes to 1).

• 3. As $x\longrightarrow \infty$, in the limit the last element of the sequence $c(x) \longrightarrow 1+\frac{1}{\sqrt{2}}$.

• 4. $\sum _{i=1}^k c(i) = \sqrt{x^2 + k^2} + (k-x)$

Remark 2

Since the order of the terms c(i) in the sum in (3) is arbitrary, the distance value is invariant to the order of the first y elements of the weight sequence. Consequently, Theorem 3 holds for any permutation of the y first weights in the weight sequence.

Since, by Remark 2 only the set of (the x) weights is important to obtain the exact Euclidean distance at every point on the perimeter of the square (obtained in x steps), there are various ways to order these weights in a weight sequence: some of them could be more important than others.

• Having the x weights in increasing order, greedy shortest path algorithm works inside the square.

• Having the weights in decreasing order, we have a metrical W-distance.

• A third option is to arrange them in a way that the distance values inside the square are close to the Euclidean one. Here this is done by a greedy approach, having the first element the one that is closest to $\sqrt{2}$, etc. (as we detail in the next part, see Algorithm 1).

Given the number of weights in the weight set, Theorem 3 gives a set of weights that optimally approximates the Euclidean distance on the border of a square. In order to obtain a close approximation of the Euclidean distance also inside the square, the order of the weights is computed by a greedy algorithm, Algorithm 1. We form the algorithm in a general way, obtaining the best possible greedy approximation step by step for any predefined set of weights. The input is a list of k weights that should be used in the (greedy) approximation. It also works for weights obtained by Theorem 3 (in this case $k=x$ for the size of the square).

Note that in each pass of the for-loop in Algorithm 1, the element in $\mathcal {K}$ that gives the minimum absolute sum is computed. Since the summation index goes from 1 to i and $\mathcal {K}$ contains $k-i$ elements, the time complexity of the algorithm is $k\cdot 1+(k-1)\cdot 2+(k-2)\cdot 3+\dots +2\cdot (k-1)+1\cdot k = \Sigma _{i=1}^k (k-i+1)\cdot i$. The dominating term is $k^3$. The time complexity is thus $O(k^3)$, where k is the length of the sequence.

Algorithm 2 works similar to Algorithm 1, but the relative difference is used instead of the absolute difference. The time complexity of Algorithm 2 is the same as for Algorithm 1, $O(k^3)$.

Given a square centered in (0, 0) (a chessboard disk of radius k), for $x=0..k$, the weight that minimizes the difference to the Euclidean distance in the next step is added to the weight sequence. The weight sets obtained by Theorem 3, for increasing x, are listed in Table 2 for some small value of x.

Table 2 Optimal weight sequences (with rounded weights) obtained by Theorem 3

Fig. 1

Distance maps from a single point using the weights and sequences in Tables 2 and 3. The color coded distance values are shown modulo 20

Table 3 Greedy weight sequences obtained by the modified version of Algorithm 1 using the weights in Table 2

In the (greedy) Algorithm 1, the mean absolute difference between $d_E(\cdot , \cdot )$ and $d(\cdot , \cdot ; W)$ is minimized in each step. With a small modification, the algorithm can be continued outside of the square. Also if the error-free approximation is not required on the border of the square, we may use some of the weights repetitively, i.e., by deleting the last line of the algorithm we allow to reuse any elements later on, if they provide the best greedy approximation in some next steps. For a better explanation, let us consider the list of weights obtained by Theorem 3 and shown in Table 2 up to a radius 50. The sequences of weights obtained are listed in Table 3 (for clarity, the table is limited to the 20 first weights and displays their indices instead of their values). Figure 1 shows the distances up to 100 steps, and Figure 2 shows the absolute difference with the Euclidean distance, and as one can observe, they are really close to the Euclidean distances, as the same distance points approximate the Euclidean circles very well even in the case of two, three weights.

Fig. 2

Absolute difference between the distance maps in Fig. 1 and the Euclidean distance

6 Conclusions

This paper introduces a framework for digital, path-based distance functions, defined as minimal cost paths, on the square grid. We show how to optimize parameters to approximate the Euclidean distance on the grid points with small error, leading to a very low rotational dependency (actually, without error on a border of a square). Note the fundamental difference with approaches that are not based on minimal cost paths such as vector propagation [5, 14] (errors are introduced and constrained distance transform computation is very time-consuming), fast marching (where a differential equation, the Eikonal equation, is approximated, giving approximate distance values) [16], or by separable algorithms (which are not suited for constrained distance transform computation) [2, 4]. The distance presented here is defined as the minimal cost path and can therefore be used, for example, to efficiently compute distance maps without errors. In our future work, we will design and analyze algorithms to compute distance maps. Finding the globally optimal weight sequence of a given length will also be an interesting future work.

We believe that the proposed distance function is potentially useful in many other image processing algorithms, for example for computing skeletons, or other algorithms where the low rotational independency is required.