richtingen waarin naar oplossingen is gezocht. Het zal
hierbij desondanks in sommige gevallen niet te vermij-
den zijn om af te dalen naar beschrijvingen van opera-
ties op 'bit'niveau. Voor de lezer, die zieh nog verder
wil verdiepen in de hier behandelde materie, kan wor
den verwezen naar het onderzoeksverslag (oeepe, 1990).
'Skeletonization' of verdunning
Bij het scannen van een kaart wordt het analoge beeld
op papier omgezet in een serie geheugenplaatsen, die
een bepaalde waarde krijgen. Hierbij vertegenwoordigt
elke geheugenplaats een bepaalde positie en is de waar
de ervan een maat voor de inktbedekking van die posi
tie op het gescande kaartblad. Zo'n geheugenplaats
wordt in het algemeen aangeduid met de term 'pixel'.
Lijnsymbolen worden aldus omgezet in een serie aan
grenzende pixels waarbij, afhankelijk van de resolutie,
de breedte van het lijnsymbool ook door meerdere
pixels kan worden weergegeven. Voor het vektoriseren
van deze lijn is het echter nodig, dat deze wordt gere-
presenteerd door een serie aaneengesloten pixels met
een dikte van een pixel. Wij kunnen hiervoor gebruik
maken van de serie pixels die de rand van de lijn vor-
men (de 'contourpixels') of van de pixels in de as van
de lijn (de 'skeletpixels'). Het gevektoriseerde beeld van
de lijn zal in het eerste geval uit twee evenwijdige Vek
toren bestaan, die de rand van de oorspronkelijke lijn
beschrijven, en in het tweede geval uit een vektor, die
de middellijn van het symbool beschrijft.
Vaak zullen de lijnsymbolen op een bestaande kaart
een netwerktopologie vertonen, die na het scannen en
vektoriseren niet meer volledig aanwezig is. Het herstel
van die topologie zal ernstig bemoeilijkt worden wan-
neer gebruik gemaakt is van de contourenmethode. In
de eerste plaats komt dat doordat de topologische rela-
tie tussen de twee vektoren die een lijn beschrijven niet
expliciet aanwezig is in het vektorbestand en dus her-
steld moet worden. Ten tweede zullen er gaten in de
vektorbeschrijving van de lijn voorkomen. De plaatsen
waar twee lijnen elkaar snijden zijn namelijk niet be-
schreven, omdat hier geen contourpixels voorkomen.
Het is daarom niet aan te bevelen om van deze metho-
de gebruik te maken voor het vektoriseren van lijn
symbolen.
Maken we gebruik van skeletpixels om de lijn te vekto
riseren, dan bestaan deze Problemen niet. Elke lijn be-
Figuur 1. De stoppen in het proces van automatische digitali-
sering.
Staat immers slechts uit een vektor en alle gedeelten
zullen beschreven zijn. Tijdens de verdunning wordt de
lijn geredueeerd tot een zuiver lineaire vorm, dat wil
zeggen een vorm zonder breedte. Informatie over deze
breedte zal daarom op een andere manier behouden
moeten blijven. Zoals nog zal blijken is dit echter geen
probleem.
Een kaart bevat echter naast lijnsymbolen ook vlak- en
puntsymbolen. Verdunning volgens de skeletmethode
redueeert het vlaksymbool tot een (serie) lijn(en). Infor
matie over de oorspronkelijke vorm gaat dan voor een
belangrijk deel verloren. Het is niet eenvoudig om deze
informatie op een andere manier te behouden. En om
dat bij vlaksymbolen een netwerktopologie in het alge
meen afwezig is, kan hier beter gebruik worden ge
maakt van de contourenmethode. Wat de beste
oplossing is voor het vektoriseren van puntsymbolen is
niet zonder meer te zeggen. Hebben zij een netwerkto
pologie, dan ligt de methode met de skeletpixels het
meest voor de hand. Is een dergelijke topologie daaren-
tegen afwezig, dan werkt de contourpixel-methode het
best. Om uit de rasterweergave van de kaart te bepalen
welke methode op de aanwezige Symbolen moet worden
toegepast, kan gebruik gemaakt worden van de ratio
contourlengte/oppervlak van de Symbolen. Bij Symbo
len met een netwerktopologie zal deze veel groter zijn
dan bij Symbolen die dit niet hebben.
In dit artikel zal verder uitsluitend aandacht worden be-
steed aan het vektoriseren van lijnen. Daarom wordt nu
nader ingegaan op methoden ter identifikatie van de
skeletpixels van een lijn. Dit proces wordt in het alge
meen aangeduid met de term 'skeletonization' (of ver
dunning).
Verdunningsalgoritmen zijn in het algemeen iteratief
van aard. Dat wil zeggen dat het proces is op te delen
in een aantal gelijksoortige stappen. In elke stap wor
den uitsluitend de contourpixels van het Objekt be-
schouwd. Er wordt voor elk van die pixels gekeken of
bepaalde kondities gelden. Is dat niet het geval dan
wordt de pixel 'weggegooid' (dat wil zeggen: krijgt de
waarde 0). Het is duidelijk dat de kondities bepalen
wat de uiteindelijk vorm van het skelet zal zijn. In een
belangrijk deel van de sinds de jaren zestig ontwikkelde
algoritmen hebben de kondities betrekking op de aan
grenzende pixels van een onder beschouwing zijnde
pixel. Figuur 2 toont een situatie, die wordt aangeduid
met de term '8-omgeving'.
Een belangrijk voordeel van deze algoritmen is dat de
individuele pixeloperaties parallel kunnen worden uitge-
voerd. Dit houdt in dat voor elke pixel de omgeving be-
schouwd wordt, zoals die bestond aan het begin van de
iteratie. Dit betekent ook dat gebruik gemaakt kan wor
den van een parallelle Computer, waarbij de pixels ge-
lijktijdig door afzonderlijke processoren worden behan-
deld. Weliswaar is hiervoor speciale (dure) hardware
nodig, maar het probleem van de lange tijdsduur van
het gehele verdunningsproces, in het algemeen gezien
als een groot knelpunt, kan aanmerkelijk worden ver-
minderd.
KT 1990.XVI.4
Scannen
Verwijdenng
van ruis
Skeletonization
of verdunning
Node
improvement
Are attribute
coding
Topological
reconstruction
Segment Merging«-
Vectoriseren
Complex object
reconstruction
Complex object
feature coding
44
