TY - GEN

T1 - A family of algorithms for generating discrete embeddings of continuous objects

AU - Overveld, van, C.W.A.M.

PY - 1988

Y1 - 1988

N2 - A substantial part of algorithms both in raster graphics and in scene analysis can be considered to deal with the problem: given a set L , L ⊂ R n , find the set Emb(L ) with: Emb(L)={x ∊ bold Z sup n |:(E l ∊ L :dist(x,l)≤ 1)}. Here dist(x,l ) stands for the distance between x and l. and n is the dimension of the space we are interested in. Using the technique of invariants [1], by means of which algorithms are derived mathematically from their specifications. we construct an algorithm for generating Emb(L) for an arbitrary, finite and connected L. The complexity of this algorithm is, worst case, O(nlogn) in the number of elements n of Emb(L ). The internal memory requirements are an order of magnitude less than n, and the algorithm is well suited for vectorization. Algorithms, similar to the one in this paper, have been applied in the field of pattern recognition (propagation labeling-or dilation algorithms [2]). In that case, L represents some spatial object from the real world. We will focus on what we believe to be new applications in the domain of rastergraphics. Here L is the mathematical definition of the object to be rasterized. We illustrate the algorithm with some examples.

AB - A substantial part of algorithms both in raster graphics and in scene analysis can be considered to deal with the problem: given a set L , L ⊂ R n , find the set Emb(L ) with: Emb(L)={x ∊ bold Z sup n |:(E l ∊ L :dist(x,l)≤ 1)}. Here dist(x,l ) stands for the distance between x and l. and n is the dimension of the space we are interested in. Using the technique of invariants [1], by means of which algorithms are derived mathematically from their specifications. we construct an algorithm for generating Emb(L) for an arbitrary, finite and connected L. The complexity of this algorithm is, worst case, O(nlogn) in the number of elements n of Emb(L ). The internal memory requirements are an order of magnitude less than n, and the algorithm is well suited for vectorization. Algorithms, similar to the one in this paper, have been applied in the field of pattern recognition (propagation labeling-or dilation algorithms [2]). In that case, L represents some spatial object from the real world. We will focus on what we believe to be new applications in the domain of rastergraphics. Here L is the mathematical definition of the object to be rasterized. We illustrate the algorithm with some examples.

U2 - 10.1007/978-3-642-83539-1_21

DO - 10.1007/978-3-642-83539-1_21

M3 - Conference contribution

SN - 978-3-642-83541-4

T3 - NATO ASI Series, Series F: Computer and Systems Sciences

SP - 587

EP - 598

BT - Theoretical foundations of computer graphics and CAD

A2 - Earnshaw, R.A.

PB - Springer

CY - Berlin

ER -