A family of algorithms for generating discrete embeddings of continuous objects

C.W.A.M. Overveld, van

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


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.
Originele taal-2Engels
TitelTheoretical foundations of computer graphics and CAD
RedacteurenR.A. Earnshaw
Plaats van productieBerlin
Aantal pagina's11
ISBN van elektronische versie978-3-642-83539-1
ISBN van geprinte versie978-3-642-83541-4
StatusGepubliceerd - 1988

Publicatie series

NaamNATO ASI Series, Series F: Computer and Systems Sciences
ISSN van geprinte versie1387-6694

Vingerafdruk Duik in de onderzoeksthema's van 'A family of algorithms for generating discrete embeddings of continuous objects'. Samen vormen ze een unieke vingerafdruk.

Citeer dit