Discrete Geometry for Computer Imagery

The relation between a straight line and its digitization as a digital straight line is often expressed using a notion of proximity. In this contribution, we consider the covering of the straight line by a set of balls centered on the digital straight line pixels. We prove that the optimal radius of the balls is strictly less than one, and can be expressed as a function of the slope of the straight line. This property is used to define discrete convexity in concordance with previous works on convexity.

Let (

W

,

d

) be a metric space and

S

 = {

s

1

…

s

k

} an ordered list of subsets of

W

. The distance between

p

 ∈ 

W

and

s

i

 ∈ 

S

is

d

(

p

,

s

i

) =  min {

d

(

p

,

q

) :

q

 ∈ 

s

i

}.

S

is a resolving set for

W

if

d

(

x

,

s

i

) = 

d

(

y

,

s

i

) for all

s

i

implies

x

 = 

y

. A metric basis is a resolving set of minimal cardinality, named the metric dimension of (

W

,

d

). The metric dimension has been extensively studied in the literature when

W

is a graph and

S

is a subset of points (classical case) or when

S

is a partition of

W

; the latter is known as the partition dimension problem. We have recently studied the case where

W

is the discrete space ℤ

n

for a subset of points; in this paper, we tackle the partition dimension problem for classical Minkowski distances as well as polyhedral gauges and chamfer norms in ℤ

n

.

Given a Digital Straight Line (DSL) of known characteristics (

a

,

b

,

μ

), we address the problem of computing the characteristics of any of its subsegments. We propose a new algorithm as a smart walk in the so called Farey Fan. We take profit of the fact that the Farey Fan of order

n

represents in a certain way all the digital segments of length

n

. The computation of the characteristics of a DSL subsegment is then equivalent to the localization of a point in the Farey Fan. Using fine arithmetical properties of the fan, we design a fast algorithm of theoretical complexity

$\mathcal{O}(\log(n))$

where

n

is the length of the subsegment. Experiments show that our algorithm is faster than the one previously proposed by Said and Lachaud in [15,14] for “short” segments.

We study patterns that appear in discrete circles with integer center and radius. As the radius goes to infinity, the patterns get closer to digital straight segments: the notion of tangent words (described in Monteil DGCI 2011) allows to grasp their shape. Unexpectedly, some tangent convex words do not appear infinitely often due to deep arithmetical reasons related to an underlying Pell-Fermat equation. The aim of this paper is to provide a complete characterization of the patterns that appear in integer discrete circles for infinitely many radii.

3D representation of real objects surfaces can be used in applications of computer graphics, medicine, geoinformatics, etc. We consider a problem of measure introducing for comparing of point clouds acquired by different scanning acts and types of scanners and designing of computationally efficient algorithms for their computing. The solution supposes estimation of disparity measure for the fixed position and search of such position that the measure is minimal by solving optimization problem of surface matching. The algorithm for efficient localization of mesh nodes in a Delaunay triangulation is proposed. As the applications several problems of 3D face model analysis were considered.

By using exclusively the customary adjacency relations on ℤ

3

, we generalize the notion of a simple surface point given by Morgenthaler in the 80s. A new definition of simple surface arises, and we show that simple surfaces coincide with the strong separating family of a certain class of digital surfaces defined by means of continuous analogues that, in turn, contains several families of discrete surfaces in the literature.

Grayscale skeletonization offers an interesting alternative to traditional skeletonization following a binarization. It is well known that parallel algorithms for skeletonization outperform sequential ones in terms of quality of results, yet no general and well defined framework has been proposed until now for parallel grayscale thinning. We introduce in this paper a parallel thinning algorithm for grayscale images, and prove its topological soundness based on properties of the critical kernels framework. The algorithm and its proof, given here in the 2D case, are also valid in 3D. Some applications are sketched in conclusion.

We propose new axioms relative to combinatorial topology. These axioms are settled in the framework of completions which are inductive properties expressed in a declarative way, and that may be combined.

We introduce several completions for describing

dyads

. A dyad is a pair of complexes which are, in a certain sense, linked by a “relative topology”.

We first give some basic properties of dyads, then we introduce a second set of axioms for

relative dendrites

. This allows us to establish a theorem which provides a link between dyads and dendrites, a dendrite is an acyclic complex which may be also described by completions. Thanks to a previous result, this result makes clear the relation between dyads, relative dendrites, and complexes which are acyclic in the sense of homology.

Recent work of Brlek

et al.

gives a characterization of digitally convex polyominoes using combinatorics on words. From this work, we derive a combinatorial symbolic description of digitally convex polyominoes and use it to analyze their limit properties and build a uniform sampler. Experimentally, our sampler shows a limit shape for large digitally convex polyominoes.

The critical thickness of an arithmetical discrete plane refers to the infimum thickness that preserves its 2-connectedness. This infimum thickness can be computed thanks to a multidimensional continued fraction algorithm, namely the fully subtractive algorithm. We provide a characterization of the discrete planes with critical thickness that contain the origin and that are 2-connected.

We present a novel 3D curvilinear skeletonization algorithm which produces filtered skeletons without needing any user input, thanks to a new parallel algorithm based on the cubical complex framework. These skeletons are used in a modified path tracing algorithm in order to produce less noisy images in less time than the classical approach.

A 3D object decomposition method is presented, which is based on the decomposition of the linear skeleton guided by the zones of influence. These are the connected components of voxels obtained by applying the reverse distance transformation to the branch points of the skeleton. Their role is to group sufficiently close branch points and to detect perceptually meaningful skeleton branches that are in a one-to-one relation with the object parts.

A new approach to simplify orthogonal pseudo-polyhedra (OPP) and binary volumes is presented. The method is incremental and produces a level-of-detail (LOD) sequence of OPP. Any object of this sequence contains the previous objects and, therefore, it is a bounding orthogonal approximation of them. The sequence finishes with the minimum axis-aligned bounding box (AABB). OPP are represented by the Extreme Vertices Model, a complete model that stores a subset of their vertices and performs fast Boolean operations. Simplification is achieved using a new approach called

merging faces

, which relies on the application of 2D Boolean operations. We also present a technique, based on the model continuity, for a better shape preservation. The method has been tested with several datasets and compared with two similar methods.

In ℝ

2

, rigid transformations are topology-preserving operations. However, this property is generally no longer true when considering digital images instead of continuous ones, due to digitization effects. In this article, we investigate this issue by studying discrete rigid transformations (DRTs) on ℤ

2

. More precisely, we define conditions under which digital images preserve their topological properties under any arbitrary DRTs. Based on the recently introduced notion of DRT graph and the classical notion of simple point, we first identify a family of local patterns that authorize topological invariance under DRTs. These patterns are then involved in a local analysis process that guarantees topological invariance of whole digital images in linear time.

In recent years, the theory behind distance functions defined by neighbourhood sequences has been developed in the digital geometry community. A neighbourhood sequence is a sequence of integers, where each element defines a neighbourhood. In this paper, we establish the equivalence between the representation of convex digital disks as an intersection of half-planes (

$\mathcal{H}$

-representation) and the expression of the distance as a maximum of non-decreasing functions.

Both forms can be deduced one from the other by taking advantage of the Lambek-Moser inverse of integer sequences.

Examples with finite sequences, cumulative sequences of periodic sequences and (almost) Beatty sequences are given. In each case, closed-form expressions are given for the distance function and

$\mathcal{H}$

-representation of disks. The results can be used to compute the pair-wise distance between points in constant time and to find optimal parameters for neighbourhood sequences.

Multidimensional persistent modules do not admit a concise representation analogous to that provided by persistence diagrams for real-valued functions. However, there is no obstruction for multidimensional persistent Betti numbers to admit one. Therefore, it is reasonable to look for a generalization of persistence diagrams concerning those properties that are related only to persistent Betti numbers. In this paper, the

persistence space

of a vector-valued continuous function is introduced to generalize the concept of persistence diagram in this sense. Furthermore, it is presented a method to visualize topological features of a shape via persistence spaces. Finally, it is shown that this method is resistant to perturbations of the input data.

The computation of multidimensional persistent Betti numbers for a sublevel filtration on a suitable topological space equipped with a ℝ

n

-valued continuous filtering function can be reduced to the problem of computing persistent Betti numbers for a parameterized family of one-dimensional filtering functions. A notion of continuity for points in persistence diagrams exists over this parameter space excluding a discrete number of so-called

singular

parameter values. We have identified instances of nontrivial monodromy over loops in nonsingular parameter space. In other words, following cornerpoints of the persistence diagrams along nontrivial loops can result in them switching places. This has an important incidence, e.g., in computer-assisted shape recognition, as we believe that new, improved distances between shape signatures can be defined by considering continuous families of matchings between cornerpoints along paths in nonsingular parameter space. Considering that nonhomotopic paths may yield different matchings will therefore be necessary. In this contribution we will discuss theoretical properties of the monodromy in question and give an example of a filtration in which it can be shown to be nontrivial.

Complex models can be simply described by notions such as skeletons. These robust shape descriptors faithfully characterize the geometry and the topology of an object. Several methods have been developed yet to obtain the skeleton from regular object representations (

e.g.

2D images or 3D volumes) but only a few attempt to extract the skeleton from unstructured 3D mesh patches. In this article, we extract a skeleton by topological thinning from vertex sets lying on arbitrary triangulated surface meshes in 3D. The key idea comes down to eroding a 2D set located on a discrete 2-manifold. The main difficulty is to transpose the notion of neighborhood from the classical thinning algorithms where the adjacency is constant (

e.g.

26-adjacency in digital volumes, 8-adjacency in 2D images) to the mesh domain where the neighborhood is variable due to the adjacency of each vertex. Thus we propose a thinning operator dedicated to irregular meshes in order to extract the skeleton of a vertex set. To estimate the robustness of our technique, several tests and an application to the feature line detection are presented as a case-study.

In many geometry processing applications, the estimation of differential geometric quantities such as curvature or normal vector field is an essential step. In this paper, we investigate a new class of estimators on digital shape boundaries based on Integral Invariants. More precisely, we provide both proofs of multigrid convergence of curvature estimators and a complete experimental evaluation of their performances.

Assume that a simplified liver model consists of some vein cells and liver cells. Such a liver model contains two kinds of components, the vein component and the liver components, each of them consists of cells which are 26-connected. The vein component has a tree-shape topology. Suppose that the vein component has already been cut into two parts, and one of them is diseased. Liver surgery planning systems need to design an algorithm to decompose the liver components into two kinds of subsets, one (usually just one component) that has been affected by the diseased vein component while the other one is still healthy. So far, existing algorithms depend heavily on surgeons’ personal expertise to detect the diseased liver component which needs to be removed. We propose an efficient algorithm for computing the diseased liver component which is based on the diseased vein component, and not on surgeons’ personal manipulations.

This paper presents a method for fitting 4-connected digital circles to a given set of points in 2D images in the presence of noise by maximizing the number of inliers, namely the optimal consensus set, while fixing the thickness. Our approach has a

O

(

n

3

log

n

) time complexity and

O

(

n

) space complexity,

n

being the number of points, which is lower than previous known methods while still guaranteeing optimal solution(s).

A digital annulus is defined as a set of grid points lying between two circles sharing an identical center and separated by a given width. This paper deals with the problem of fitting a digital annulus to a given set of points in a 2D bounded grid. More precisely, we tackle the problem of finding a digital annulus that contains the largest number of inliers. As the current best algorithm for exact optimal fitting has a computational complexity in

O

(

N

3

log

N

) where

N

is the number of grid points, we present an approximation method featuring linear time complexity and bounded error in annulus width, by extending the approximation method previously proposed for digital hyperplane fitting. Experiments show some results and runtime in practice.

In the present paper, we introduced an arc recognition technique suitable for irregular isothetic object. It is based on the digital inter-pixel (DIP) circle model, a pixel-based representation of the Kovalevsky’s circle. The adaptation to irregular image structurations allows us to apply DIP models for circle recognition in noisy digital contours. More precisely, the noise detector from Kerautret and Lachaud (2009) provides a multi-scale representation of the input contour with boxes of various size. We convert them into an irregular isothetic object and, thanks to the DIP model, reduce the recognition of arcs of circles in this object to a simple problem of point separation.

In some applications, the tomographic reconstruction is not an end in itself. When the goal is rather to gather information about the object being studied, the question is if it is more interesting to directly extract these information from the projections without the reconstructing step. We would then know if less projections are needed to directly get the information than to reconstruct the object. In this paper, we address the problem of extracting quantitative information about an object namely an estimation of its area, an upper and a lower bound to the perimeter given its projections from point sources.

In Discrete Tomography there is a wide literature concerning (weakly) bad configurations. These occur in dealing with several questions concerning the important issues of uniqueness and additivity. Discrete lattice sets which are additive with respect to a given set

S

of lattice directions are uniquely determined by

X

-rays in the direction of

S

. These sets are characterized by the absence of weakly bad configurations for

S

. On the other side, if a set has a bad configuration with respect to

S

, then it is not uniquely determined by the

X

-rays in the directions of

S

, and consequently it is also non-additive. Between these two opposite situations there are also the non-additive sets of uniqueness, which deserve interest in Discrete Tomography, since their unique reconstruction cannot be derived via the additivity property. In this paper we wish to investigate possible interplays among such notions in a given lattice grid

$\mathcal{A}$

, under

X

-rays taken in directions belonging to a set

S

of four lattice directions.

In hypergraph theory, determining a good characterization of

d

, the degree sequence of an

h

-uniform hypergraph

$\mathcal{H}$

, and deciding the complexity status of the reconstruction of

$\mathcal{H}$

from

d

, are two challenging open problems. They can be formulated in the context of discrete tomography: asks whether there is a matrix

A

with nonnegative projection vectors

H

 = (

h

,

h

,…,

h

) and

V

 = (

d

1

,

d

2

,…,

d

n

) with distinct rows.

In this paper we consider the subcase where the vectors

H

and

V

are both homogeneous vectors, and we solve the related consistency and reconstruction problems in polynomial time. To reach our goal, we use the concepts of Lyndon words and necklaces of fixed density, and we apply some already known algorithms for their efficient generation.

Given a binary matrix, deciding wether it can be decomposed into three

hv

-convex matrices is an

$\cal NP$

-complete problem, whereas its decomposition into two

hv

-convex matrices or two

hv

-polyominoes can be performed in polynomial time. In this paper we give a polynomial time algorithm that decomposes a binary matrix into three

hv

-polyominoes, if such a decomposition exists. These problems are motivated by the Intensity Modulated Radiation Therapy (IMRT).

We have proposed a complete set of basis Euler operators for updating cell complexes in arbitrary dimensions, which can be classified as homology-preserving and homology-modifying. Here, we define the effect of homology-preserving operators on the incidence graph representation of cell complexes. Based on these operators, we build a multi-resolution model for cell complexes represented in the form of the incidence graph, and we compare its 2D instance with the pyramids of 2-maps, designed for images.

Differentials estimation of discrete signals is almost mandatory in digital segmentation. In our previous work, we introduced the fast level-wise convolution (LWC) and its complexity of

O

(2

n

.

log

2(

m

)). We present convergence proofs of two LWC compatible kernel families. The first one is the pseudo-binomial family, and the second one the pseudo-Gaussian family. In the experimental part, we compare our method to the Digital Straight Segment tangent estimator. Tests are done on different digitized objects at different discretization step using the DGtal library.

In this paper we examine concurrency relations between planes whose position is not precisely known. The simplest case consists of four planes, where we have to determine whether the four planes can be forced to pass through one common intersection point by moving them slightly within specified limits. We prove that if such a concurrency relation is possible then it can be found in a finite number of steps by a simple geometrical construction. This result remains valid for larger collections of planes, with multiple concurrency relations, provided each pair of relations shares at most one plane, and the relations do not form cycles.

We propose an Euclidean medial axis filtering method which generates subsets of Euclidean medial axis were filtering rate is controlled by one parameter. The method is inspired by Miklos’, Giesen’s and Pauly’s scale axis method which preserves important features of an input object from shape understanding point of view even if they are at different scales. Our method overcomes the most important drawback of scale axis: scale axis is not, in general, a subset of Euclidean medial axis. It is even not necessarily a subset of the original shape. The method and its properties are presented in 2D space but it can be easily extended to any dimension. Experimental verification and comparison with a few previously introduced methods are also included.

Binary tomography deals with the problem of reconstructing a binary image from its projections. Depending on properties of the unkown original image, the constraint that the image is binary enables accurate reconstructions from a relatively small number of projection angles. Even in cases when insufficient information is available to compute an accurate reconstruction of the complete image, it may still be possible to determine certain

features

of it, such as straight boundaries, or homogeneous regions. In this paper, we present a computational technique for discovering the possible presence of such features in the unknown original image. We present numerical experiments, showing that it is often possible to accurately identify the presence of certain features, even without a full reconstruction.

Resolving a 3D segmentation problem is a common challenge in the domain of digital medical imaging. In this work, we focus on another original application domain: the 3D images of wood stem. At first sight, the nature of wood image looks easier to segment than classical medical image. However, the presence in the wood of a wet area called sapwood remains an actual challenge to perform an efficient segmentation. This paper introduces a first general solution to perform knot segmentation on wood with sapwood. The main idea of this work is to exploit the simple geometric properties of wood through an original combination of discrete connected component extractions, 2D contour detection and dominant point detection. The final segmentation algorithm is very fast and allows to extract several geometrical knot features.

We propose in this paper an estimator of derivative and curvature of discrete curves. Based on adaptive convolution that preserves contour, we use local geometrical information as the heat kernel to convolve with a discrete curve and give estimation of its geometrical parameters. We recover on regular part of the curve the classical convolution based on gaussian kernel. We study the bounded error of our approach for first and second order derivative and we discuss about the multigrid convergence.