c-gd-intro.rst

Digital Geometry: Digital Model and Elementary Digital Topology

Author:	David Coeurjolly

Digital Model

Principles

Idea

Take benefit from the regular structure of the lattice to enhance geometrical analysis of shapes

• Integer based computations
• Combinatorial algorithms
• high performance algorithms
• ...

Approach

What do we need ?

• Grid/Lattice to define our cells
• Digital Topology to add, at least, a combinatorial structure on cells
• Digitization schemes to fill the gap between Euclidean/Digital worlds
• Fundamental objects (straight lines, circles, planes, ...)
• Axioms
• Specific Algorithms

Lattice and Tilings

Requirements

• Simplicity of the structure (storage, ...)
• Pixels access (coordinate system)
• Neighbors pixel access
• Consistency w.r.t. acquisition devices or processing pipeline
• Capacity (Information theory)

More formally

• Packing Density: fraction of the volume filled by a given collection of solids. Given a large number of equal Euclidean balls centered in the grid points, this quantity say how efficiently they are packed
• Kissing Number: the number of neighboring balls that each ball touch
• Covering: the least dense way to cover the space with equal overlapping balls

Example in dimension 2

Definitions

Lattice

Given a basis (v_1,\ldots,v_n) of \mathbb{R}^n,

\Lambda= \left \{ \sum_{i=1}^n a_iv_i \,|\, a_i \in \mathbb{Z} \right \}

(finitely-generated free abelian group, symmetry group, ...)

Five fundamental lattices in the Euclidean plane

Paving

Definition (dual lattice structure)

The cell of a lattice point \lambda\in\Lambda is its Voronoi cell

• Following fundamental lattice classification: pavings by squares, hexagons, triangles, rhombi and parallelograms.

• By definition, the paving induced by a lattice is periodic

• Triangular/Hexagonal lattice/paving are dual

  

Speaking of density packing/kissing number and covering, hexagonal lattice is optimal

Dimension 3

Regular cubic grid

V=\left ( \begin{array}{ccc}
1 &0 &0\\
0 & 1 &0\\
0 & 0 & 1
\end{array} \right )

Face-centered cubic grid

V_{fcc}=\left ( \begin{array}{ccc}
1 &1 &0\\
1 & 0 &1\\
0 & 1 & 1
\end{array} \right )

Body-centered cubic grid

V_{bcc}=\left ( \begin{array}{ccc}
1 &1 & -1\\
1 & -1 &1\\
-1 & 1 & 1
\end{array} \right )

Dimension 3 (bis)

• BCC has optimal covering

• FCC has highest packing density and largest kissing number

• FCC and BCC are dual

  V_{fcc}^{-1} = V_{bcc}^T
  

Hexagonal grid

V_{hexa}=\left ( \begin{array}{ccc}
  \sqrt{3}/2 & 0 \\
  1/2 &1
  \end{array} \right )

Semi-regular pavings

Definition

• Several convex tiles paving the plane

• No T-junctions

• Same configuration of tiles around each vertex

  

Lattice Encoding

Square lattice

• Lattice points: \mathbb{Z}^2, direct access to direct neighbors (i\pm 1, j), (i,j\pm 1)

Triangular grid

• Lattice points: special encoding of lattice points to \mathbb{Z}^2, three direct neighbors (two local configurations when mapped to \mathbb{Z}^2)

Hexagonal grid

• Lattice points: special encoding of lattice points to \mathbb{Z}^2, six direct neighbors (two local configurations when mapped to \mathbb{Z}^2)

  

Lattice Encoding (ctd.)

Cubic grid

Trivial

FCC/BCC grid

(x,y,z) \text{ is generated by } V_{fcc} \Leftrightarrow (x,y,z)\in \mathbb{Z}^3,  x+y+z=0\, (mod\, 2)

(x,y,z) \text{ is generated by } V_{bcc} \Leftrightarrow (x,y,z)\in \mathbb{Z}^3,  x=y=z\, (mod\, 2)

Elongated grids

• E.g. square/cubic grid with different resolutions
• \Rightarrow Remapping \mathbb{Z}^3\rightarrow \mathbb{R}^3 on-the-fly

Fundamental Topology Elements

Adjacency relationships in the square/cubic grid

Combinatorial approach

In 2D:

• 4-neighbors: pixels sharing an edge (i\pm 1, j) and (i,j\pm 1)
• 8-neighbors: pixels sharing an edge or a vertex (i\pm 1, j\pm 1)

In 3D:

• 6-neighbors: voxels sharing a face
• 18-neighbors: voxels sharing a face or an edge
• 26-neighbors: voxels sharing a face, an edge or a vertex

Topological approach

Two pixels/voxels are (k)-adjacent is the intersection of their (closed) cell is of dimension k

Mixing all dimensions:

• 4-neighbor, 18-neighbor \equiv (1)-adjacent
• 8-neighbor, 26-neighbor \equiv (0)-adjacent
• 6-neighbor \equiv (2)-adjacent

More definitions

(k)-path

A sequence of digital points :\{p_i\}_{i=0\ldots n} is a (k)-path if for each point, p_i is (k)-adjacent to p_{i-1} (except for i=0)

(k)-arc

A (k)-arc is a (k)-path such that each p_i has exactly two (k)-adjacent neighbors (except for extremities)

(k)-curve

A (k)-curve is a (k)-arc such that p_0 = p_n

(k)-object

A set S of digital point is a (k)-object iff for any pair of points, there exists a (k)-path in S

Illustrations

Illustrations (ctd.)

Can you spot (k)-arcs/(k)-objects/(k)-curves for k=\{0,1\} ?

Toward a definition of contour

Objective: define a notion of object contour/boundary matching with Jordan theory

• C is a Jordan curve (or simple closed curve) in \mathbb{R}^2 if C is the image of a continuous and injective map from the circle to \mathbb{R}^2

Jordan theorem states that:

• \mathbb{R}^2\setminus C has two connected components, one is bounded (aka interior) and the other one is unbounded (exterior)
• Each continuous path \pi from an interior point to an exterior one crosses C (with an odd number of intersections)
• Implies an orientation of C

Idea mimic a digital version of Jordan framework replacing C by a (k)-curve ?

Digital paradox

Given the following (0)- and (1)-curves, do they define Jordan-like curve ?

\Rightarrow It depends.... we need a pair of adjacency relationships !

Example: Filling holes

Adjacency pairs

(\kappa,\lambda) Jordan pair such that k is the adjacency for the object and l the adjacency for the complementary

In dimension 2

(0,1) and (1,0)

In dimension 3

(2,1), (2,0) (1,2) and (0,2)

Border definition

Border: Given a (\kappa,\lambda) Jordan pair, the border of X is the set of (\kappa) -adjacent digital points which are (\lambda) -adjacent to points in X^C

• The result is a (\kappa) -object but we need more constraints to have a (\kappa) -curve
• Hard to generalize to 3D
• We do not have \partial X= X\setminus X^C (or kind of, both are considered as open sets)

Cellular grid space and topology

Idea embed the digital space \mathbb{Z}^n into a cellular space (cartesian cubic space) to represent oriented inter-pixel elements

In 2D

• 0-cells are called pointels (element of dimension 0), by convention, Digital points in \mathbb{Z}^n are embedded into 0-cells
• 1-cells are called linels (element of dimension 1)
• 2-cells are called pixels
• each cell can be signed

In nD

• 0-, ... , n-cells
• by convention: n-cells are called spels and (n-1)-cells are called surfels

(two 0-cells, two 2-cells and four 1-cells)

Digital Surface

Principle defines digital surface as a set of (n-1)-cells (surfels)

• Let us consider a \beta relationship on surfels (anti-reflexive, local transitive closure, locally defined)
• Given a (\kappa,\lambda) Jordan adjacency pair, (\kappa,\lambda,\beta) triplet is a Jordan triplet

• \beta is anti-reflexive
• \beta is a relationship on surfels
• \beta can extract all surfels (informally)

We can demonstrate that such Jordan triplets leads to well-defined digital Jordan surface

Illustration in 2D (here, k=1)

Approach is valid for various digital structures

\beta in 3D

Two valid \beta relationships on (2,1)- or (2,0)- pairs on closed objects

\beta relationship + graph traversal (depth first, breadth first,...) \Rightarrow digital surface tracker

Efficiency of the tracker is guided by the `beta`:math: complexity

Generic Breadth-first tracker

For (2)-object

• \beta is not oriented, each surfel is processed 4 times
• \beta^* with oriented arcs (2 arcs per surfel), each surfel is processed 2 times
• \beta^{*+} with oriented arcs (1 or 2 arcs per surfels), each surfel is processed 4/3 times (on average)
• The graph is 4-regular
• \Rightarrow Hamiltonian path exists if X is homeomorphic to a ball

Digital Surface Extraction

Overall algorithm (for single connected surface)

• Scan the image until we find a first surfel
• Apply the tracker to traverse all surfels

Complex Objects

Several connected components, holes, ...

\Rightarrow Scan the complete volume, mark all surfels as potential starting surfels and apply the tracker on each starting surfel (removing traversed surfels)

Digitization schemes

Main ideas

Formalize the embedding \mathbb{R}^n\rightarrow\mathbb{Z}^n

• To be able to generate digital objects by digitization of Euclidean ones
• Important if we want to propagate properties (roughly, the digitization of a Jordan curve should be a (\kappa,\lambda)- Jordan for some grid steps)
• When we define a differential estimator (e.g. curvature) on digital contour, allows us to design multigrid convergent estimators
• ...

Gauss model

Let \mathcal{X}\subset \mathbb{R}^n and X its digitization

X = \mathcal{X}\cap\mathbb{Z}^n

• Easy to implement
• Mostly used on objects with 2-measure \neq 0 but even in this case, X may be empty
• By definition X \subseteq \mathcal{X}
• We need more constraints on \mathcal{X} to ensure topological properties on X or \partial X

Gauss models (bis)

This model was first used to approximate

\int_\mathcal{X} ds

by

|X|

Grid intersection models

Idea Defined for oriented contours \partial\mathcal{X}

For each intersection \partial\mathcal{X} with a grid edge, we select the {closer,inner,outer} grid point

(resp. GIQ -Grid Intersect Quantization-, OBQ -Object Boundary Quantization-, BBQ -Background Boundary Quantization-)

• We construct (0)-objects which could also be (0)-arcs or (0)-curves
• Less generic than Gauss model
• bubbles can appear on ties (when \partial\mathcal{X} crosses the edge at its mid-point) \Rightarrow global Oracle to remove ties
• Distance properties between X and \partial\mathcal{X}

Analytic models

Generic definition

Let d_* be a metric, B its unit ball and M=\check{B}

\mathbb{A}(\mathcal{X})&=\{p\in\mathbb{Z}^n~|~ B(p)\cap \mathcal{X} \neq \emptyset\}
       \\&=\{p\in\mathbb{Z}^n~|~ d_*(p,\mathcal{X})\leq \frac{1}{2} \} \\&=(\mathcal{X}\oplus M)\cap\mathbb{Z}^n

Still bubbles may exist

Properties

Following the definition (F,G \in \mathbb{R}^n ):

prop.

\mathbb{A}(F\cup G)=  \mathbb{A}(F) \cup  \mathbb{A}(G)

\mathbb{A}(F)= \bigcup_{p\in F} \mathbb{A}(p)

\mathbb{A}(F\cap G)\subseteq  \mathbb{A}(F) \cap \mathbb{A}(G)

\text{if } F\subseteq G\text{ then }  \mathbb{A}(F) \subseteq \mathbb{A}(G)

\Rightarrow Allows modeling of digital objects but CSG approach (Constructive Solid Geometry)

Interesting theoretical tool: multigrid digitization

Idea Digitization parametrized by a grid step

E.g. for Gauss digitization

X_h = \left (\frac{1}{h}\cdot \mathcal{X}\right )\cap \mathbb{Z}^n

Mathematical results can be obtained with constraints on \mathcal{X}, for example

thm.

If \partial \mathcal{X} is C^2 with bounded curvature, there exists a grid step h_0 such that for 0<h<h_0, X_h is topologically equivalent to \mathcal{X}

thm.

If \partial \mathcal{X} is C^2 with bounded curvature, the retro-projection from \hat{x}\in\partial X_h onto \partial \mathcal{X} at x along its normal direction is continuous, mono-valuated and surjective (for 0<h<h_0) and \| \hat{x} -x\|_\infty \le h)

Another example

Question 1 Given a digital object, How to estimate its areas ?

Answer Well, let's count the number of grid points (unit squares) (estimator denoted E)

Question 2 Is this estimator multigrid convergent ? What is the convergence speed ?

Answer

• Let's consider the estimator E_h at grid-step h defined on the digitization of the Euclidean shape \mathcal{X} from a given class of shapes

• If \mathcal{X} is a finite convex shape, there exists a grid step h_0 such that for 0<h<h_0 we have:

  | E_h( X_h ) - \mu(\mathcal{X}) | \leq O(h)
  

[Gauss, Dirichlet]

• If \mathcal{X} is C^3 (or finitely piece-wise C^3 with positive curvature almost everywhere...) then

  | E_h( X_h ) - \mu(\mathcal{X}) | \leq O(h^{\frac{15}{11}+\epsilon})
  

  [Huxley,...]

Would there be better approaches ?