Domogalla's methode om knooppunt-verplaatsing te
voorkomen
Domogalla voert eerst een normale verdunning van het
beeld uit. In het hieruit verkregen skelet onderscheidt
hij de knooppunten. Vervolgens stelt hij voor elk
knooppunt een bepaald gebied er omheen vast: de
'knooppunt-regio'. Hierna keert hij terug naar het ori-
ginele rasterbeeld, wat opnieuw wordt verdund. Daarbij
worden de pixels binnen de knooppunt-regio's niet be-
handeld. De skeletpixels worden vervolgens gevektori-
seerd en de pixels binnen de knooppunt-regio's worden
weggegooid. Vervolgens wordt van de vektoren, die op
een knooppunt-regio eindigen, het snijpunt bepaald.
Dit vormt het nieuwe knooppunt.
Deze op zieh heel elegante methode bergt een risiko in
zieh. Het is namelijk zo dat tijdens het proces de topo-
logie van het oorspronkelijke beeld geheel verwoest
wordt. In de meeste gevallen zal de methode om deze
topologie te herstellen wel tot bevredigende resultaten
leiden, maar er zijn situaties denkbaar waarbij Proble
men optreden.
Bij de hiervoor genoemde toestand, die leidt tot het op
treden van het 'hourglass'-effekt (figuur 4b), zal het
bijvoorbeeld onduidelijk zijn welke snijpunten waar
zullen ontstaan. Ook de situatie waarin een weg na een
kruispunt aan een zijde verbreed wordt, en vervolgens
in dezelfde richting doorgaat, zal Problemen opleveren.
In de richting van de inkomende vektoren ligt er dan
namelijk geen snijpunt, aangezien de vektoren parallel
op een bepaalde afstand van elkaar lopen.
Op zieh is deze methode echter zo veelbelovend, dat
toekomstig onderzoek naar het oplossen van de bezwa-
ren valt aan te bevelen.
Het TON-algoritme
Figuur 5a vormt een rasterweergave van figuur 4a (bij
het navolgende moet in gedachten gehouden worden,
dat het beeld geen lijneinden bevat). De situatie die
ontstaat na twee verdunningsiteraties is weergegeven in
figuur 5b. Verdere iteraties hebben het gevolg, dat het
gedeelte van de diagonale tak dat nog niet geheel ver
dund is, alsnog loodrecht op de horizontale tak wordt
verdund. Het resulterende knooppunt (pixel C in figuur
5b) is naar links verschoven ten opzichte van de positie
waar het zou moeten zijn (pixel D in figuur 5b). Dit
verschijnsel wordt door ons aangeduid als 'Y-
verplaatsing' (naar de vorm van het kruispunt van we
gen). Men kan aantonen dat voor de grootte van deze
verplaatsing geldt:
DY (d resolutie)/tan (a)
Hierin stelt 'd' de halve lijndikte van de horizontale
tak voor, 'a' de hoek tussen de twee takken en 'resolu-
tie' de grootte van een pixel.
Tijdens de volgende iteraties blijkt dat ook de horizon
tale tak vervormd wordt. Dit is weergegeven in figuur
5c, welke de situatie twee iteraties na de toestand in fi
guur 5b weergeeft. We kunnen zien dat het knooppunt
in de richting van de diagonale tak wordt verschoven.
x xx xx
xxxxx
xxxxx
xxxxx
xxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxx
xxxxx
xxxxxxxxxxxxxxxx
XXXXXXXXCXXXDXXX
b xxxxxxxxxxxxxxxx
Figuur 5. Knooppunt-verplaatsing bij verdunning.
a. Rasterweergave van figuur 4a.
b. De situatie na twee verdunningsiteraties.
c. De situatie na vier verdunningsiteraties.
Deze verplaatsing wordt aangeduid met de term 'T-
verplaatsing'. Voor deze T-verplaatsing geldt de volgen
de vergelijking:
Dt (dj - d2) 2 (indien d, d2)
Hierin stelt 'dj de halve dikte van de horizontale tak
voor en 'd2' de halve dikte van de diagonale tak.
Met behulp van de vergelijking:
D Dy2 Dx2)
kan nu de totale verplaatsing bepaald worden.
Beschouwen we figuur 5 nader, dan kunnen we konklu-
deren, dat de Y-verplaatsing kan worden voorkomen,
als de driehoek van pixels met pixel A als top (zie fi
guur 5b) niet ontstaat. Dit kan worden bewerkstelligd
door tijdens elk van de twee iteraties de twee pixels, die
in figuur 5a als 'G' zijn weergegeven, de waarde 0 te
geven. Het grote probleem is daarbij om deze pixels te
vinden.
Het voert te ver om de hele oplossing middels het
TON-algoritme te beschrijven en daarom wordt hier
volstaan met de opmerking dat dit gebeurt door naar
een konfiguratie van contourpixels te zoeken, die de
binnenhoek van de kruising vormen.
De methode lost alleen die gevallen op waarbij de hoek
tussen de twee takken 45 graden bedraagt. In alle ande-
KT 1990.XVI.4
47
XXXXXXGGXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
X
X
X
X
A
X B X
X
X
X
X
X
XXX
C. XXXXXXXXXXXDXXX
