J
lil;
111!
He
ill
quadtrees, zoals de MX-quadtree, de PR-quadtree en de PMR-
quadtree, om slechts enkele te noemen. Daarnaast wordt een
substantieel deel van de stof in beslag genomen door de ontwikke
ling van algoritmen om de gegevens in de gekozen structuur te raad
plegen en te muteren.
In boek II komen de toepassingen aan de orde. Hierbij verloochent
Samet zijn wetenschappelijke afkomst niet: bijna het gehele boek is
gerefereerd aan digitale beelden. (Samet heeft samengewerkt met A.
Rosenfeld, die men met recht de peetvader van de digitale beeldver
werking mag noemen.)
In hoofdstuk 1 wordt boek I nog eens dunnetjes overgedaan.
De representatie in de vorm van een boomstructuur heeft, hoewel hij
direct toegankelijk is, het nadeel van een aanzienlijke overhead in de
vorm van pointers. Dit heeft geleid tot de pointerloze quadtree, die
gebruik maakt van lijsten. Hoofdstuk 2 is hieraan volledig gewijd.
De quadtree heeft tot gevolg dat elk object, bestaande uit een aan
eengesloten homogeen gebied op het raster, wordt opgeslagen in
meerdere kwadranten op meerdere niveaus. De vraag hoe vanuit
deze structuur de buren van een object op te sporen, is onderwerp
van hoofdstuk 3.
Naast de quadtrees worden ook veelvuldig andere typen opslag
structuren gebruikt, zoals de run-lengthcode, de Freemancode en
polygonen. Voor het combineren van gegevens uit meerdere bestan
den met verschillende structuur is conversie nodig; onderwerp van
hoofdstuk 4.
Na segmentatie van een beeld, dat wil zeggen de opsplitsing ervan
in beelddelen die homogeen zijn in één of meerdere eigenschappen,
zoals kleur en textuur, worden vaak, met name voor de patroon
herkenning, geometrische eigenschappen zoals omtrek, vorm en
volume van de segmenten berekend. Het meten dient te worden
voorafgegaan door een connected component labelling; dit is het
opsporen van pixels behorend bij eenzelfde beeldsegment. Deze
zaken zijn onderwerp van hoofdstuk 5.
Hoofdstuk 6 is geheel gewijd aan bewerkingen op als quadtree gere
presenteerde beelden, zoals de omzetting van de ene kleur naar de
andere, het maken van uitsneden, het uitvoeren van een geometri
sche transformatie gepaard met resampling en de expansie (dilatie)
van homogene beelddelen.
Het displayen van een 3-D scene vereist een projectie op een vlak.
De twee voornaamste projectievormen zijn de centrale projectie en
de parallele projectie. Doordat objecten op de voorgrond objecten op
de achtergrond afdekken, ontstaat het hidden-surface probleem.
Om het geblokte aanzicht van objecten onvermijdelijk gevolg van
het digitaliseringsproces te vermijden, dient interpolatie met
behulp van splines plaats te vinden. Met ray tracing, beam tracing of
radiosity kunnen kleur en tint van elk pixel na projectie worden be
paald. Bovenstaande zaken worden aangesneden in hoofdstuk 7.
Verdergaande opslagreductie is mogelijk door gebruik te maken van
regelmaat in de quadtree. Het oorspronkelijke beeld kan daarbij
volledig gehandhaafd blijven, men spreekt dan van compressie, of
worden benaderd door weglating van details (een vorm van generali
seren). Quadtree compressie en benadering, vooral beperkt tot
binaire beelden, worden behandeld in hoofdstuk 8.
Bij de quadtree moeten de blokken een vaste plaats hebben, mogen
ze elkaar niet overlappen en moeten ze een vast formaat hebben.
Door invoering van de concepten afstand, skelet en midden-as-
transformatie (medial axis transformation) kunnen de laatste twee
eisen vervallen. De quadtree-midden-as-transformatie (QMAT) geeft
geen informatieverlies. Nooit méér knooppunten zijn nodig bij de
QMAT dan bij de quadtree. De QMAT is veel minder gevoelig voor
translatie dan de quadtree. Deze modificaties van de quadtree
komen aan de orde in hoofdstuk 9.
Samet heeft voor de behandeling van de stof gekozen voor een algo
ritmische aanpak. Elk hoofdstuk bevat tal van algoritmen in pseudo
code, een variant op ALGOL. Veel algoritmen zijn recursief, pro
grammeerbaar in onder andere PASCAL en C.
00000000
2
3
4
6
$|lQ
II
\Z
i$jl6
19
17 10
Level 3
Level 2
Level I
Level 0
7 8 9 10
15 16 17 18
Een schaakbord en zijn quadtree.
Een voorbeeld van een quadtree, (a) een object, (b) de binaire raster
representatie van het object, (c) opsplitsing in homogene kwadran
ten en (d) de bijbehorende quadtree.
Elke paragraaf wordt afgesloten met veel opgaven; verdeeld over
beide delen meer dan 1200! De oplossingen worden achterin gege
ven. Soms bestaat deze, vooral als het schrijven van een algoritme
wordt gevraagd, uit verwijzing naar de literatuur.
Met de nauwgezetheid waarmee hij de literatuur refereert, verraadt
Samet zich als consciëntieuze wetenschapper. Niets wordt als koek
je van eigen deeg gepresenteerd. Zelfs wanneer opgaven van de
hand van een ander zijn, wordt dat vermeld. Door de uitstekende,
soms zelfs overdadig aandoende, literatuurverwijzing wordt voor de
lezer een reusachtige bibliotheek aan metaliteratuur geopend.
Samet heeft veel onderzoek verricht op het onderhavige terrein en
heeft navenant gepubliceerd in vooraanstaande wetenschappelijke
tijdschriften. Deze wetenschappelijke georiënteerdheid heeft geleid
tot een kwalitatief hoogstaand werk, maar soms krijgt men de indruk
dat de docent heeft moeten wijken voor de prudente wetenschapper.
Samet heeft de onderwerpen in beide boeken van een algemeen ka
der willen voorzien, hoewel zijn eigen achtergrond duidelijk die van
de digitale beeldverwerking en patroonherkenning is. Dit wreekt
zich, want de onderwerpen zijn tegelijkertijd te oppervlakkig en te
diepgaand. Ze beslaan een te breed scala en bevatten te weinig rode
draad. De inhoud lijkt een reflectie van eigen onderzoeksactiviteiten.
Bovendien is de verdeling van de stof over de twee delen oneven
wichtig. Zo worden in boek II (de toepassingen) alternatieve quad
tree representaties, conversies tussen verschillende representaties
en geometrische eigenschappen besproken, en dit is duidelijk basis
stof. De octrees en displaymethoden zouden binnen de doelstellin
gen heel goed onbehandeld hebben kunnen blijven. Er vindt veel
herhaling plaats. Beide boeken hadden dan ook heel goed in één
deel kunnen worden ondergebracht, met het bijkomende voordeel
van een besparing van 49 pagina's, want de literatuurlijsten zijn voor
beide delen identiek. Beide boeken lijken daardoor meer geschreven
voor de onderzoeker en de docent dan voor de student.
Na lezing ontkomt men niet aan de conclusie dat geodeten zich meer
moeten richten op de theorievorming van de ruimtelijke informatie.
Hier ligt een brede discipline van onderwijs en onderzoek open. Ook
blijkt onomstotelijk hoe nauw de huidige ontwikkelingen in de digitale
fotogrammetrie (de toepassing van beeldverwerkingstechnieken en
patroonherkenning bij de uitwerking van beeldmateriaal) en de GIS-
problematiek op elkaar aansluiten. Niet alleen liggen ze in eikaars
verlengde wat procesgang betreft, maar ook qua wiskundige tech
nieken en modelvorming. De huidige internationale ontwikkelingen
in de digitale fotogrammetrie liggen zeer sterk op het vlak van de
patroonherkenning, dat wil zeggen de extractie van semantische
informatie uit beelden. De wiskundige technieken in de patroonher
kenning lijken zeer sterk op die van de rastergestructureerde GIS-
sen. Zij vertonen echter nauwelijks verwantschap met de wiskunde
waar de geodeet zo vertrouwd mee is: de mathematische statistiek
en de matrixrekening.
M. J. P. M. Lemmens
26
NGT GEODESIA 90 - 1
