$\alpha$-Pixels for Hierarchical Analysis of Digital Objects

Abstract

In this paper, we apply a scale space analysis method to digital geometry. We deal with the reconstruction of Euclidean polylines controlling the size of pixels in discrete space. Numerical examples show that the size of pixels of digital geometry processes the scale for the hierarchical reconstruction of Euclidean objects from digital objects.

1 Introduction

In this paper, we apply a scale space analysis method to digital geometry [1,2,3]. Linear digital geometry on a plane mainly deals with two problems: (1) the generation of a string of pixels from polylines and (2) the reconstruction of polylines from a string of pixels. The string generated in the first problem is called a digital object. The second problem is called Euclidean reconstruction [1,2,3] in digital geometry. Therefore, digital and discrete geometry deals with mathematical relations between the generation of digital objects and the reconstruction of Euclidean objects from digital objects.

We deal with Euclidean reconstruction if the size of pixels varies. We numerically show that the size of pixels in digital expression governs the scale in the hierarchical expression for the reconstruction of Euclidean objects. In digital geometry, there are three types of local structure of strings: naive, standard and supercover [1,2,3]. We deal with supercover [3, 4] for the string expression constructed from Euclidean polylines.

Two-dimensional digital geometry deals with geometric objects defined on the equi-spaced grid system Furthermore, objects in digital geometry are collections of pixels centred at grid points. Therefore, since digital geometry is an application of interval analysis to geometry, each point is dealt with as a square centred at a grid point. On the other hand, the $\alpha$-shape method [5] is dealt with a point as a small circle centred at the point for geometric processing with rounding errors [6, 7], As an analogue of the $\alpha$-shape method to digital geometry, we introduce $\alpha$-digital geometry, which deals with various sizes of pixels. An extension of the geometric properties of pixels in digital geometry is the isothetic irregular grid system geometry. In the irregular grid system geometry, digital images are expressed by isothetic rectangles [4, 9, 10]. The irregular grid system geometry has advantages for the expression and analysis of digital images, since for smooth parts on the boundary of an object, the less numbers of the isothetic rectangles are expected for image expressions.

The curve shorting flow [11,12,13] is used for shape retrievals since the flow extracts dominant local features from the boundary curves of objects. The proposing method extracts the local features by reducing the number of edges in polylines extracted from the digital boundary of digitised objects on a plane.

2 Pixels and Discrete Object

Setting $\boldsymbol{n}=(m,n)^\top$ to be a point in $\textbf{Z}^2$, a square,

$$\begin{aligned} \textbf{p}(\boldsymbol{n}) =\left\{ \boldsymbol{x}|\, |\boldsymbol{x}-\boldsymbol{n}|_\infty \le \frac{1}{2} \right\} , \end{aligned}$$

(1)

for $\boldsymbol{x}=(x,y)^\top$ is called a pixel of $\textbf{R}^2$ centred at point $\boldsymbol{n}$, where $|\boldsymbol{x}|_\infty =\max (|x|,|y|)$ is the infinity norm $\ell _\infty$ of $\textbf{R}^2$.

Definition 1

For $\boldsymbol{n}=(m,n)^\top$,

$$\begin{aligned} \textbf{p}^\alpha (\boldsymbol{n}) =\left\{ \boldsymbol{x}|\, |\boldsymbol{x}-\boldsymbol{n}|_\infty \le \alpha \frac{1}{2}, \alpha >0 \right\} , \end{aligned}$$

(2)

is an $\alpha$-pixel of $\textbf{R}^2$ centred at point $\boldsymbol{n}\in \textbf{Z}^2$.

Therefore, the pixels are 1-pixels. We call the 1-pixels simply pixels. Furthermore, we set $\lim _{\alpha \rightarrow 0}{} \textbf{p}^\alpha (\boldsymbol{x})=\boldsymbol{x}$

We define the connectivity of points in $\textbf{Z}^2$.

Definition 2

For $\boldsymbol{x}=(x,y)^\top \in \textbf{Z}^2$, the set $\textbf{N}(\boldsymbol{x})=\{(x\pm 1,y)^\top , (x,y\pm 1)^\top \}$ is the four neighbourhoods of $\boldsymbol{x}$.

Definition 3

If $\boldsymbol{y}\in \textbf{N}(\boldsymbol{x})$, $\boldsymbol{y}$ is four connected to $\boldsymbol{x}$ and described as $\boldsymbol{x}\sim \boldsymbol{y}$.

Therefore, a pair points $\boldsymbol{x}$ and $\boldsymbol{y}$ in $\textbf{Z}^2$ are four connected, the pair of pixels $\textbf{p}(\boldsymbol{x})$ and $\textbf{p}(\boldsymbol{y})$ shares an edge. We describe $\textbf{P}(\boldsymbol{x})\sim \textbf{P}(\boldsymbol{y})$ if $\boldsymbol{x}\sim \boldsymbol{y}$. Therefore, for the collection of centre points $\textbf{p}=\{\boldsymbol{x}_1, \boldsymbol{x}_2,\cdots , \boldsymbol{x}_n\}$, if the connection relations $\boldsymbol{x}_1\sim \boldsymbol{x}_2\sim \cdots \sim \boldsymbol{x}_n$ are satisfied elements in a collection of pixels $\textbf{P}=\{\textbf{p}_1, \textbf{p}_2,\cdots , \textbf{p}_n\}$ satisfy the connection property such that $\textbf{p}_1\sim \textbf{p}_2\sim \cdots \sim \textbf{p}_n$, We call the collection of pixels $\textbf{P}$ four-connected objects.

Definition 4

If pixels in the collection of four-connected pixels $\textbf{P}=\{\textbf{p}\}_{i=1}^n$ are replaced with $\alpha$-pixels, we call the object an $\alpha$-object and express it as $\textbf{P}^\alpha$.

Definition 5

If the $\alpha$-object $\textbf{P}^\alpha$ is generated from a string of $\alpha$-pixels, we call this object an $\alpha$-string.

Definition 6

We express the $\alpha$-string generated from string $\textbf{S}$ as $\textbf{S}^\alpha$.

Next, we define the supercover of sample points.

Definition 7

For $a,b,\mu \in \textbf{Z}$ and $\omega =|a|+|b|$, points $(x,y)^\top \in \textbf{Z}^2$ on the supercover satisfy the double Diophantus inequality

$$\begin{aligned} 0\le ax+by+\mu + \frac{\omega }{2} \le \omega \end{aligned}$$

(3)

for $\textrm{gcd}(a,b)=1$ and $\textrm{gcd}(\mu ,1)=1$.

Furthermore, we define the supercover of sample points.

Definition 8

For $a,b,\mu \in \textbf{Z}$ and $\omega =|a|+|b|$, points $(x,y)^\top \in \textbf{Z}^2$ on the $\alpha$-supercover satisfy the double inequality

$$\begin{aligned} 0\le ax+by+\mu + \alpha \frac{\omega }{2} \le \alpha \omega \end{aligned}$$

(4)

for $\textrm{gcd}(a,b)=1$ and $\textrm{gcd}(\mu ,1)=1$.

The $\alpha$-pixels satisfy the following properties.

Property 1

For $\alpha _1<\alpha _2$, the inclusive relation $\textbf{p}^{\alpha _1}(\boldsymbol{x})\subset \textbf{p}^{\alpha _2}(\boldsymbol{x})$ is satisfied.

Property 2

For the four-connected point set $\textbf{s}=\{\boldsymbol{x}_i\}_{i=1}^n$, the collection of $\alpha$-pixels $\textbf{S}^\alpha =\{p_\alpha (\boldsymbol{x}_i)\}_{i=1}^n$ satisfies the inclusive relation $\textbf{S}^{\alpha _1}\subset \textbf{S}^{\alpha _2}$ if $1\le \alpha _1<\alpha _2$.

For $\alpha =1$, the supercover of line $ax+b+\mu =0$ is the four connected pixel string $\textbf{P}_{(a,b,\mu )}$. The line $ax+b+\mu =0$ crosses with all elements of the string $\textbf{P}_{(a,b,\mu )}$. Figure 1(a) shows the configuration pixels in the supercover of a line. In Fig. 1(b) and 1(c), dark squares are $\alpha$-pixels for $\alpha =2$ and $\alpha =3/4$, respectively. Furthermore, in Fig. 1(b) and 1(c), light gray squares are $\alpha$-supercovers for $\alpha =2$ and $\alpha =3/4$, respectively. Figures 1(b) and 1(c) the local structures of 2-supercove and 3/4-supercover for a line, respectively.

Fig. 1.

Supercover and $\alpha$-supercovers (a) Supercover of an Euclidean line. (b) The local structure of 2-supercover. (c) The local structure of 3/4-supercover. In (b) and (c) dark squares are $\alpha$-pixels of sample points and light grey squares are elements of $\alpha$-supercovers.

If $\textbf{S}$ is a string of four-connected pixels, Property 2 implies the inclusive relations of regions in which Euclidean reconstructions exist. Figure 2 shows the geometrical expressions of this inclusive relation for digital circles $\textbf{C}^{\alpha }$ for $\alpha =1,2^2,2^3, \, \, \textrm{and}, \, \, 2^4$ in (a), (b), (c) and (d), respectively.

Fig. 2.

$\alpha$-pixel strings of circles. (a) Circle of pixels $\textbf{C}=\textbf{C}_{2^0}$. (b) Circle of 2-pixels $\textbf{C}^{2}$ (c) Circle of 4-pixels $\textbf{C}^{4}=\textbf{C}^{2^2}$. (d) Circle of 4-pixels $\textbf{C}^{8}=\textbf{C}^{2^3}$. These figures show that digital circles satisfy the inclusive relation $\textbf{C}^{2^0}\subset \textbf{C}^{2^1}\subset \textbf{C}^{2^2}\subset \textbf{C}^{2^3}$.

3 Reconstruction of Line

Definition 9

Recognition of the $\alpha$-supercover from sample pixels $\{\boldsymbol{x}_i=(x_i,y_i)^\top \}_{i=1}^n$ is to find integers a, b and $\mu$ which minimise

$$\begin{aligned} M=|a|+|b|+|\mu | \end{aligned}$$

(5)

with the conditions

$$\begin{aligned} 0\le ax_i+by_i+\mu + \alpha \frac{\omega }{2} \le \alpha \omega , \, \, i=1,2,\cdots , n, \end{aligned}$$

(6)

for $\textrm{gcd}(a,b)=1$, $\textrm{gcd}(\mu ,1)=1$ and $\omega =|a|+|b|$.

It is possible to assume $a\ge 0$ since the line $ax+by+\mu =0$ can be transformed to $-ax-by-\mu = 0$ if a is negative. Therefore, assuming $b\ge 0$, Eq. (3) can be expressed as

$$\begin{aligned} \textrm{case1}&:&0\le ax+by+\mu + \alpha \frac{a+b}{2} \le \alpha (a+b), \end{aligned}$$

(7)

$$\begin{aligned} \textrm{case2}&:&0\le ax-by+\mu + \alpha \frac{a+b}{2} \le \alpha (a+b). \end{aligned}$$

(8)

Theorem 1

For these two cases, the vector forms of inequalities of Eqs. (7) and (8) for $\boldsymbol{a}=(a,b)^\top$ are

$$\begin{aligned} {\left\{ \begin{array}{ll} -\boldsymbol{x}_i^\top \boldsymbol{a}-\alpha \displaystyle {\frac{1}{2}\omega } \le \mu ,\,\, \mu \le -\boldsymbol{x}_i^\top \boldsymbol{a}+ \alpha \displaystyle {\frac{1}{2}\omega },\\ \boldsymbol{x}_{ij}^\top \boldsymbol{a}>0,\\ \boldsymbol{a}>0, \end{array}\right. } \text{ for } {\left\{ \begin{array}{ll} \boldsymbol{x}_{ij}=\boldsymbol{x}_i-\boldsymbol{x}_j+\alpha \boldsymbol{e}, \\ \boldsymbol{e}=(1,1)^\top , \\ \omega =a+b \end{array}\right. } \end{aligned}$$

(9)

and

$$\begin{aligned} {\left\{ \begin{array}{ll}-\boldsymbol{x}_i^\top \boldsymbol{M}\boldsymbol{a} -\alpha \displaystyle {\frac{1}{2}\omega }\le \mu ,\, \, \mu \le -\boldsymbol{x}_i^\top \boldsymbol{M}\boldsymbol{a} +\alpha \displaystyle {\frac{1}{2}\omega },\\ \boldsymbol{x}_{ij}^\top \boldsymbol{a}>0,\\ \boldsymbol{a}>0, \end{array}\right. } \text{ for } {\left\{ \begin{array}{ll} \boldsymbol{x}_{ij}=\boldsymbol{M}(\boldsymbol{x}_i-\boldsymbol{x}_j)+\alpha \boldsymbol{e},\\ \boldsymbol{e}=(1,1)^\top , \\ \omega =a+b, \end{array}\right. } \end{aligned}$$

(10)

where $\boldsymbol{M}=\left( \begin{array}{cc} 1,&{}0\\ 0,&{}-1 \end{array}\right) .$

(Proof) For case 1, using the system of inequalites

$$\begin{aligned} {\left\{ \begin{array}{ll} ax_i+by_i+\mu + \alpha \displaystyle {\frac{\omega }{2}}\ge 0, \\ -ax_j-by_j-\mu - \alpha \displaystyle {\frac{\omega }{2}}\ge -\alpha (a+b), \end{array}\right. } \end{aligned}$$

(11)

Eq. (6) implies the system of inequalities

$$\begin{aligned} {\left\{ \begin{array}{ll} -(x_{i}a+y_{i}b)- \alpha \displaystyle {\frac{a+b}{2}} \le \mu , \\ -(x_{j}a+y_{j}b)+\alpha \displaystyle {\frac{a+b}{2}} \ge \mu , \\ X_{ij}a+Y_{ij}b \ge 0, \\ a,b > 0, \end{array}\right. } \end{aligned}$$

(12)

for $i\ne j$, $i,j=1,2,\cdots ,n$, where $X_{ij}=x_{i}-x_{j}+\alpha$ and $Y_{ij}=y_{i}-y_{j}+\alpha$. Therefore, $\boldsymbol{x}_{ij}=(X_{ij},Y_{ij})^\top =\boldsymbol{x}_i-\boldsymbol{x}_j+\alpha \boldsymbol{e}$ for $\boldsymbol{e}=(1,1)^\top$.

For case 2, since

$$\begin{aligned} {\left\{ \begin{array}{ll} -(ax_i-by_i)-\alpha \displaystyle {\frac{1}{2}\omega } \le \mu , \\ -(ax_j-by_j)+\alpha \displaystyle {\frac{1}{2}\omega } \ge \mu , \\ (ax_i-by_i)+\mu + \alpha \displaystyle {\frac{\omega }{2}}\ge 0, \\ -(ax_j-by_j)-\mu - \alpha \displaystyle {\frac{\omega }{2}}\ge -\alpha (a+b). \end{array}\right. } \end{aligned}$$

(13)

we have the relations

$$\begin{aligned} \boldsymbol{x}_{ij}=\boldsymbol{M}(\boldsymbol{x}_i-\boldsymbol{x}_j)+\alpha \boldsymbol{e} \end{aligned}$$

(14)

and

$$\begin{aligned} -\boldsymbol{x}_i^\top \boldsymbol{M}\boldsymbol{a}-\alpha \frac{1}{2}\omega< \mu ,\, \, \mu <-\boldsymbol{x}_i^\top \boldsymbol{M}\boldsymbol{a}+\alpha \frac{1}{2}\omega . \end{aligned}$$

(15)

(Q.E.D)

For case 1, setting $\boldsymbol{a}^*=(a^*,b^*)^\top = \arg \min _{k} (|\boldsymbol{a}|_1=k, \, \, \boldsymbol{x}_{ij}^\top \boldsymbol{a}\ge 0),$ where $|\boldsymbol{a}|_1=a+b=\boldsymbol{e}^\top \boldsymbol{a}$, $\mu ^*\in \textbf{Z}$ is computed from the system of inequalies

$$\begin{aligned} {\left\{ \begin{array}{ll} -\boldsymbol{x}_i^\top \boldsymbol{a}^*-\alpha \displaystyle {\frac{1}{2}\boldsymbol{e}^\top \boldsymbol{a}^*} \le \mu ^*, \\ -\boldsymbol{x}_j^\top \boldsymbol{a}^*+\alpha \displaystyle {\frac{1}{2}\boldsymbol{e}^\top \boldsymbol{a}^*} \ge \mu ^*\end{array}\right. } \end{aligned}$$

(16)

for $i\ne j$, $i=1,2,\cdots ,n$. These relations imply that the computation of a positive integer pair $(a,b)^\top$ and an integer $\mu$ is decomposed into two steps. Furthermore, this decomposition strategy leads to the following lemma.

Lemma 1

There is no solution for $(a,b)^\top$, if $\textbf{A}_2=\{\boldsymbol{a}=(a,b)^\top | a>0, b>0, a,b\in \textbf{Z} \}$ is empty.

Definition 10

We call the region defined by $\boldsymbol{x}_{ij}^\top \boldsymbol{a}\ge 0$ the feasible region.

For $\alpha$-supercover recognition, we analyse the relation between the geometrical configuration of sample points $\boldsymbol{x}_i=(x_i,y_i)^\top$ for $i=1,2,\cdots n$ and the feasible region defined by the sample points. From the geometric configurations of regions

$$\begin{aligned} H= & {} \{\boldsymbol{x}_{ij}|i\ne j,i,j=1,2,\cdots ,n\}, \\ Q_{++}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,X_{ij}>0,Y_{ij}>0,i\ne j\},\\ Q_{--}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,X_{ij}<0,Y_{ij}<0,i\ne j\},\\ Q_{+-}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,X_{ij}>0,Y_{ij}<0,i\ne j\},\\ Q_{-+}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,X_{ij}<0,Y_{ij}>0,i\ne j\}, \\ Q_{0X}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,X_{ij}=0,i\ne j\},\\ Q_{0Y}= & {} \{\boldsymbol{x}_{ij}|\boldsymbol{x}_{ij}\in H,Y_{ij}=0,i\ne j\},\\ \end{aligned}$$

and the regions defined by Eq. (6), Eq. (6) has no solution if all the following conditions

• 1. $Q_{--}\ne \emptyset ,$

• 2. $\forall \boldsymbol{x}_{ij}\in Q_{0X}, Y_{ij}\le 0$,

• 3. $\forall \boldsymbol{x}_{ij}\in Q_{0Y}, X_{ij}\le 0$,

• 4. $Q_{+-}\ne \emptyset$, $Q_{-+}\ne \emptyset$ and

  $$ \min \left( -X_{ij}/Y_{ij}\right) _{|\boldsymbol{x}_{ij}\in Q_{+-}}< \max \left( -X_{nm}/Y_{nm}\right) _{|\boldsymbol{x}_{nm}\in Q_{-+}} $$

are satisfied. Therefore, we have the following theorem for recognition of the supercover from sample points in $\textbf{Z}^2$.

Theorem 2

If all relations

$$\begin{aligned} {\left\{ \begin{array}{ll}Q_{--} = \emptyset , \\ \forall \boldsymbol{x}_{ij}\in Q_{0X}, Y_{ij}> 0, \\ \forall V\in Q_{0Y}, X_{ij}> 0, \\ \min (-\frac{X_{ij}}{Y_{ij}})_{|\boldsymbol{x}_{ij}\in Q_{+-}}\ge \max (-\frac{X_{nm}}{Y_{nm}})_{|\boldsymbol{x}_{nm}\in Q_{-+}}, \\ \end{array}\right. } \end{aligned}$$

(17)

are satisfied, the corresponding pixels $\{\textbf{p}(\boldsymbol{x}_i)\}_{i=1}^n$ of sample points $\{\boldsymbol{x}_i\}_{i=1}^n$ on $\textbf{Z}^2$ define a supercover of the line $ax+by+\mu =0$ for $a>0$, $b>0$ and $\textrm{gcd}(a,b)=1$.

For the computation of a Euclidean line from sample points $\{\boldsymbol{x}_i\}_{i=1}^n$, we define

$$\begin{aligned} (\widehat{X}_{ij},\widehat{Y}_{ij})= & {} \min (-X_{ij}/Y_{ij})_{|(X_{ij}, Y_{ij})\in Q_{+-}},\end{aligned}$$

(18)

$$\begin{aligned} (\widetilde{X}_{nm}, \widetilde{Y}_{nm})= & {} \max (-X_{nm}/Y_{nm})_{|(X_{nm}, Y_{nm})\in Q_{-+}} \end{aligned}$$

(19)

Then, Eq. (17) implies the following theorem.

Theorem 3

There exists a line if the region defined by the system of inequalities

$$\begin{aligned} {\left\{ \begin{array}{ll} \widehat{X}_{ij}a+\widehat{Y}_{ij}b\ge 0, \\ \widetilde{X}_{mn}a+\widetilde{Y}_{mn}b\ge , 0 \end{array}\right. } \end{aligned}$$

(20)

is not empty.

Assuming the feasible region is the positive cone in (a, b)-space defined by the system of inequalities

$$\begin{aligned} {\left\{ \begin{array}{ll} u_{1}a+v_{1}b\le 0,\\ u_{2}a+v_{2}b\ge 0,\\ a>0,\\ b>0, \end{array}\right. } \end{aligned}$$

(21)

the solutions of the system of linear equations

$$\begin{aligned} \begin{array}{ll} {\left\{ \begin{array}{ll}a+b=k, \\ u_{1}a+v_{1}b=0, \end{array}\right. } &{} {\left\{ \begin{array}{ll} a+b=k, \\ u_{2}a+v_{2}b=0, \end{array}\right. } \end{array} \end{aligned}$$

(22)

are

$$\begin{aligned} \begin{array}{ll} {\left\{ \begin{array}{ll} a_{1}=\displaystyle {\frac{v_{1}}{v_{1}-u_{1}}}k,\\ b_{1}=k-a_{1}, \end{array}\right. } &{} {\left\{ \begin{array}{ll} a_{2}=\displaystyle {\frac{v_{2}}{v_{2}-u_{2}}}k, \\ b_{2}=k-a_{2}. \end{array}\right. } \end{array} \end{aligned}$$

(23)

These solutions are points on the boundary of the positive cone. By incrementing k until both $a_{1}$ and $b_{2}$ are integers, we compute the minimiser of $a+b$. Once $a>0$ and $b>0$ are computed from Eq. (20), Eq. (12) implies

$$\begin{aligned} \max \left\{ -(x_{i}+\frac{1}{2})a-(y_{i}+\frac{1}{2})b \right\} \le \mu , \mu \le \min \left\{ (\frac{1}{2}-x_{i})a+(\frac{1}{2}-y_{i})b \right\} . \end{aligned}$$

(24)

Therefore,

• If $\max \left\{ -(x_{i}+\frac{1}{2})a-(y_{i}+\frac{1}{2})b \right\} \ge 0$, then $\mu =\max \left\{ -(x_{i}+\frac{1}{2})a-(y_{i}\right.$ $\left. +\frac{1}{2})b \right\} .$

• If $\min \left\{ (\frac{1}{2}-x_{i})a+(\frac{1}{2}-y_{i})b \right\} \le 0$, then $\mu = \min \left\{ (\frac{1}{2}-x_{i})a+(\frac{1}{2}-y_{i})b \right\} .$

• If $\max \left\{ -(x_{i}+\frac{1}{2})a-(y_{i}+\frac{1}{2})b \right\} < 0$ and $\min \left\{ (\frac{1}{2}-x_{i})a+(\frac{1}{2}-y_{i})b \right\} > 0$, then $\mu = 0.$

4 Polygonalisation of $\alpha$-String

For the computation of a Euclidean polyline from the 1-string, at least three connected sample points are requested. Even if there is no solution for four-connected sample points $\{\boldsymbol{x}_i=(x_i,y_i)^\top \}_{i=1}^n$, there might be two supercovers for each connected $\{\boldsymbol{x}_i=(x_i,y_i)^\top \}_{i=1}^m$ and $\{\boldsymbol{x}_i=(x_i,y_i)^\top \}_{m+1}^n$ for $3\le m\le n-3$. This geometrical property of connected sample points implies the computation of open and closed polygonal curves from connected-sample points. This problem automatically requests the computation of the partition of connected sample points and the supercover to each partition of sample points.

We assume that strings of pixels $\textbf{S}$ form the four-connected digital boundary of segment $\textbf{S}$ on $\textbf{Z}^2$. This boundary curve is extracted using appropriate morphological operations [14]. For the sample points $\{\boldsymbol{x}_i\}_{i=1}^n$, $\boldsymbol{x}_{i}\ne \boldsymbol{x}_j$ if $i\ne j$. Furthermore, we can set $\boldsymbol{x}_{i+m}=\boldsymbol{x}_i$. Then, the polygonalisation of $\textbf{S}$ is described bellow.

Problem 1

Let $\textbf{S}^\alpha$ be the digital boundary curve of an object on the square grid system. Compute a partition of $\textbf{S}^\alpha$ such that $\textbf{S}^\alpha =\cup _{i=1}^n\textbf{S}^{\alpha }_{i}$, $\textbf{S}^{\alpha }_{i}=\{\textbf{p}^{\alpha }_{ij} \}_{j=1}^{n(i)}$ $|\textbf{S}^{\alpha }_{i}\cap \textbf{S}^{\alpha }_{i+1}|=\varepsilon$ for an appropriate small integer $\varepsilon$.

The polygonalisation of $\textbf{S}^\alpha$ is described as following.

Problem 2

Compute the number of polygonal edges n and triplets of parameters $\{(a_i,b_i,\mu _i)\}_{i=1}^n$ for edges that minimise the criterion

$$\begin{aligned} z=\sum _{i=1}^{n}(|a_i|+|b_i|+|\mu _i) \end{aligned}$$

(25)

with respect to the system of inequalities

$$\begin{aligned} 0\le a_ix_{ij}+by_{ij}+\mu _i + \alpha \frac{\omega _i}{2} \le \alpha \omega _i, \end{aligned}$$

(26)

for $i=1,2,\cdots n$ and $j=1,2,\cdots ,n(i)$, where $\omega _i=|a_i|+|b_i|$, $\textrm{gcd}(a_i,b_i)=1$ and $\textrm{gcd}(\mu _i,1)=1$.

The solution of Problem 2 yields a collection of curves

$$\begin{aligned} \mathcal{L}_i =\left\{ (x,y)^\top \,|\, |a_ix+b_iy+|\mu _i| \le \alpha \frac{1}{2}(|a_i|+|b_i|)\right\} \end{aligned}$$

(27)

$i=1,2,\cdots , n$ for an appropriate integer n.

Since we reconstruct polygonal edges from the $\alpha$-string generated from four-connected pixels, the minimum number of connected pixels for the initialisation of the algorithm is three. Then, incrementing four connected pixels on the string, the algorithm computes feasible regions from a series of the local string of $\alpha$-pixels whose centre points are four-connected. If no feasible region exists upon incrementing the $\alpha$-pixel, the algorithm fixes the parameters $(a_i,b_i)$ and $\mu _i$ from a partial string one step before using the algorithm for supercover recognition. The algorithm restarts the parameter computation pixel by pixel. Finally, if all $\alpha$-pixels in the string are used for parameter computation, the algorithm stops and outputs polygonal edges.

Fig. 3.

Euclidean reconstruction from $\alpha$-pixels. (a), (b), (c), (d), (e) and (f) show the four-connected pixel contour, the Euclidean contour reconstructed 2-pixels, the Euclidean contour reconstructed 4-pixels, the Euclidean contour reconstructed 1/60-pixels, the Euclidean contour reconstructed 1-pixels and the Euclidean contour reconstructed 10-pixels, respectively.

Fig. 4.

Koch curves for evaluation of Euclidean reconstruction. (a) is the pixel curve. The Euclidean reconstruction from digital contour curves in (b) and (c) is reconstructed for $\alpha =1$ and $\alpha =10$, respectively.

Fig. 5.

Hierarchical analysis of Euclidean reconstruction. The numbers of edges, the lengths of contour curves and the areas encircled by reconstructed curves for $\alpha <1$ are shown in (a), (b) and (c), respectively, The numbers of edges, the lengths of contour curves and the areas encircled by reconstructed curves for $\alpha <1$ are shown in (d), (e) and (f), respectively.

5 Numerical Examples

Figure 3 shows the hierarchical expression of contour curves. Figures 3 (a), (b), (c), (d), (e) and (f) show the four-connected pixel contour, the Euclidean contour reconstructed 2-pixels, the Euclidean contour reconstructed 4-pixels, the Euclidean contour reconstructed 1/60-pixels, the Euclidean contour reconstructed 1-pixels and the Euclidean contour reconstructed 10-pixels, respectively. These examples show that if $\alpha <0$, the Euclidean reconstructed curve is similar to the polyline fitting to sample points. For $\alpha >0$, the Euclidean curves reconstructed form $\alpha$-pixel strings extracts absolute shapes if $\alpha$ increases.

For the analysis of the reconstructed curves, the Euclidean reconstruction curves are computed for various $\alpha$ values for the Koch curve in Fig. 4(a). Figures 4(b) and (c) show the Euclidean reconstruction from digital contour curves of $\alpha =1$ and $\alpha =10$, respectively.

Figure 5 shows evaluations of the numbers of edges, the lengths of contour curves and the areas encircled by reconstructed curves, respectively. These results show that for $\alpha <1/2$ the numbers of edges, the lengths of contour curves and the areas encircled by reconstructed curves are almost stational. On the other hand, for $\alpha >1$, $\alpha$ acts as a scale for the hierarchical expression of shapes.

6 Conclusions

The Euclidean reconstruction problem of a line from samples $\{\boldsymbol{x}_i=(x_i,y_i)^\top \}_{i=1}^n$ for $\alpha \rightarrow 0$ implies the minimisation criterion

$$\begin{aligned} J(a,b,\mu )=\sum _{i=1}^n(|ax_i+b_i+|\mu |). \end{aligned}$$

(28)

Equation (28) is the minimiser for the $\ell _1$ line fitting [15, 16]. Setting

$$\begin{aligned} \boldsymbol{s}=(s_1,s_2,\cdots ,s_n)^\top , \, \, \, \boldsymbol{e}=(1,1,\cdots ,1)^\top , \end{aligned}$$

(29)

the $\ell _1$ line fitting is established by minimising $z=\boldsymbol{e}^\top \boldsymbol{s}$ subject to

$$\begin{aligned} \boldsymbol{s}\ge 0, \, \, \, -\boldsymbol{s}\le (\boldsymbol{X}\boldsymbol{a}+\mu \boldsymbol{e})\le \boldsymbol{s}, \, \, \, \boldsymbol{X}^\top =\left( \begin{array}{cccc} \boldsymbol{x}_1,&\boldsymbol{x}_2,&\ldots ,&\boldsymbol{x}_n \end{array}\right) , \end{aligned}$$

(30)

where $\boldsymbol{a}=(a,b)^\top$ [16, 17], using linear programming [17].

Therefore, our methods for Euclidean line reconstruction and polyline reconstruction from a collection of $\alpha$-pixels, respectively, are modifications of $\ell _1$ line fitting [16] and $\ell _1$-polyline estimation [18, 19] optimisation to interval analysis [6,7,8].