ISSN:
1436-5057
Keywords:
68 G 10
;
Image processing
;
quadtrees
;
three-dimensional border
;
pattern recognition
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Eine neue Methode zur 3D-Objektgrenzen-Bestimmung wird präsentiert: sie beginnt mit der 3D-Objektdarstellung in „linear octtree form”, gefolgt von einer Eliminierung interner Grenzen zwischen Knoten („nodes”) gleicher Größe und einer Löschung interner Knoten. Das Verfahren endet mit der Feststellung, daß nur mehr „border voxels” vorliegen. Der Algorithmus führt grundsätzlich eine Abbildung eines 3D-Objektes in seinen eigenen Grenzen durch, wobei es sich sowohl bei „input” als auch bei „output” um „linear octtrees” handelt. Es wird gezeigt, daß die Exekutionszeit des Algorithmus von der Ordnungkn(N+M) ist, worink die maximale Knotenzusammenfassung undN die Anzahl der Knoten des ursprünglichen „octtrees” bedeuten.n ist die Genauigkeit des Binärbildes („bilevel image”) undM ist die Anzahl der „border voxels”. Der Anwendungsbereich des vorgeschlagenen Algorithmus ist ziemlich groß: er bestimmt die äußeren Grenzen eines einfach zusammenhängenden Gebietes genauso wie die äußeren und inneren Grenzen eines Satzes mehrfach zusammenhängender Objekte.
Notes:
Abstract A novel approach to the 3D border determination is presented: it starts by representing the 3D object in linear octtree form, proceeds by eliminating internal boundaries between nodes of the same size while deleting internal nodes and terminates when only border voxels remain. The algorithm basically performs a mapping of the 3D object into its own border, with both input and output being represented as linear octtrees. The algorithm is shown to be executable inO(kn(N+M)) time, wherek andN are the maximum node grouping and number of nodes (respectively) of the initial linear octtree,n is the resolution of the bilevel image andM is the number of border voxels. The range of applicability of the proposed algorithm is quite wide: it can determine the external border of a simply connected region as well as the external and internal borders of a set of multiply connected objects, all at the same time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02243773
Permalink