Search

This paper proposes a concise coding of the cells of n-dimensional finite regular grids. It induces a simple, generic and efficient framework for implementing classical digital topology data structures and algorithms. Discrete subsets of multidimensional images (e.g. regions, digital surfaces, cubical cell complexes) have then a common and compact representation. Moreover, algorithms have a straightforward and efficient implementation, which is independent from the dimension or sizes of digital images. We illustrate that point with generic hypersurface boundary extraction algorithms by scanning or tracking. This framework has been implemented and basic operations as well as the presented applications have been benchmarked. [Copyright &y& Elsevier]

This paper is dedicated to the study of metrical properties of a collection of 2D thinning algorithms that we have proposed. Here, we characterize their underlying metrics and use it to reduce the classical metrical biases that affect thinning algorithms in the square grid. We show that some algorithms from the collection lead to skeletons based on a particular geometry, corresponding to the (4,8)-median axis, which is a new shape descriptor, featuring nice robustness and conditioning-properties. [Copyright &y& Elsevier]

A digital naive plane is a subset of points (x, y, z) ∈ Z3 verifying a double inequality h ≤ ax + by + cz < h + max{∣a∣, ∣b∣, ∣c∣} where (a, b, c) ∈ R/{(0,0,0)} and h ∈ R. Given a finite subset of Z3, a problem is to determine whether or not there exists a digital naive plane containing it. This question is rather classical in the field of digital geometry (also called discrete geometry). We suggest in this paper a new algorithm for solving it. It uses 2-simplexes called triangles and an original strategy of optimization. The code is short and elementary (less than 300 lines). Its theoritical complexity is bounded by O(n7) but its behaviour is quasi-linear in practice. [Copyright &y& Elsevier]

In this paper, we aim to formulate the recognition of a linear manifold from a discrete point set as a nonlinear optimization problem, and we prove a uniqueness theorem for the solution of this problem. We also develop an algorithm for the computation of parameters of the Euclidean linear manifold from pixels and voxels on a plane and in a space, respectively. [Copyright &y& Elsevier]