3.3 Suchen nach Bildern · Multimedia Retrieval - SS02 Kap.3-57 3.3 Suchen nach Bildern • Die...

Kap.3-57Multimedia Retrieval - SS02

3.3 Suchen nach Bildern

• Die Abbildung der Bilder auf Primäre (Metadaten) und Sekundäre (Merkmale) Datenführt typischerweise zu Anfragen mit– Textbestandteil, z.B. die Beschreibung zum Bild soll die Wörter „rot“ und „Auto“

enthalten– Prädikaten, z.B. das Konzept (logisches/abstraktes Feature) „Auto“ sollte

enthalten sein, oder das Bild soll grösser als 600x300 Pixel sein.

– „Vektorbestandteil“, z.B. die primitiven Merkmale sollen möglichst nahe beidenjenigen der Vorlage(n) liegen.

• Isoliert betrachtet können Anfragen mit nur

– Textbestandteilen mit einer der Methoden in Kapitel 1 gelöst werden– Prädikaten mit einer Datenbank und SQL gelöst werden

Hingegen haben wir bis anhin keine Möglichkeit kennen gelernt, Anfragen mit„Vektorbestandteil“ zu lösen (Bem: In Kapitel 1 haben wir aber bereits mit LSI eineMethode kennen gelernt, welche ebenfalls in diese Kategorie fällt).

• In diesem und dem nächsten Kapitel werden Anfragen mit nur „Vektorbestandteil“gelöst. Die kombinierten Anfragen werden in Kapitel 3.5 behandelt.

• In einem ersten Schritt nehmen wir an, dass Objekte durch genau einen (sehr hoch-dimensionalen) Vektor beschrieben werden. Später werden wir zeigen, wieObjektbeschreibung mit mehreren Vektoren behandelt werden können.


• Die Auswahl der Merkmale bestimmt die Güte des (Vektor) Retrieval. Prinzipiellkönnen beliebig viele, beliebig komplexe Merkmale verwendet werden. Selbst textuelleMerkmale und Konzepte (z.B. erkannte Objekte) könnten als (dünnbesetzte) Vektorenbetrachtet werden (was man aber aus Effizienz- und Platzgründen lieber nicht macht)– Farbverteilung: Farbe spielt eine wichtige Rolle bei der Erkennung von Objekten

(z.B. Hautfarbe); Bildkompositionen bestehen häufig aus wenigen Regionen mitähnlichen Farben

– Textur (Ausrichtungen im Bild): Texturen beschreiben die Oberflächen-beschaffung von Objekten (glatt, strukturiert); Texturen können aber auchzwischen künstlichen und natürlichen Gegenständen unterscheiden (künstlichehaben meist viele horizontale und vertikale Linien)

– Form: Überraschenderweise spielt die Form keine so zentrale Rolle (Ausnahme:Geometrieerkennung); Formen können hilfreich sein bei Objekterkennung, aber:die Form eines Objektes ist abhängig vom Blickwinkel

Blobworld:


Wie misst man die Ähnlichkeit zwischen Merkmalen?– Sei q der Merkmalsvektor des Anfragebildes und pi der Merkmalsvektor des

Bildes i. Ferner sei σ(q,pi ) ein Ähnlichkeitsmass, so dass

σ(q,pi ) im Bereich [0,1] liegt,σ(q,pi )=0 bedeutet, dass q und pi keine Ähnlichkeit haben undσ(q,pi )=1 bedeutet, dass q und pi identisch sind.

Von Distanzen zu Ähnlichkeitswerten– Das Ähnlichkeitsmass σ(q,pi ) wird meistens über eine Distanzfunktion δ(q,pi ) im

Merkmalsraum berechnet. Dabei gilt folgender Zusammenhang:• eine grosse Distanz deutet auf eine kleine Ähnlichkeit hin• eine kleine Distanz deutet auf eine grosse Ähnlichkeit hin

– Die Transformation von Distanzen zu Ähnlichkeitswerten und umgekehrt wirdmittels einer Umkehrfunktion h (engl. correspondence function) implementiert:

σ(q,pi ) = h(δ(q,pi )), δ(q,pi ) = h-1(σ(q,pi ))

– Die Umkehrfunktion h muss dabei folgende Bedingungen erfüllen:

1) h(0)=1,2) h(∞)=0, und3) h’(x)≤0. δ

h(δ)

σ1 1

δ

h(δ)

σ


Distanzfunktionen (Metriken)

• Die Konstruktion des Merkmals bestimmt, welche Distanzfunktion zur Anwendunggelangt.– Falls die Merkmale unkorreliert sind, dann ist eine Lp-Norm sehr nützlich, wobei

p=1,2,…,∞ mittels Evaluation bestimmt wird. Häufig verwendet man für Momentedie L1-Norm:

• L1-Norm (Manhattan Distanz):

• L2-Norm (Euklidsche Distanz):

• L∞-Norm (Maximum Norm):

– Bei korrelierten Merkmalen muss die Abhängigkeit der Achsen berücksichtigtwerden. Z.B. bei Histogrammen gibt es Korrelationen zwischen den Farben(Orange und Rot sind ähnlich, aber Rot und Blau sind nicht ähnlich). SolcheAbhängigkeiten können mittels quadratischer Funktionen erfasst werden. DieMatrix A (dxd) enthält die Korrelationswerte der Komponenten:

• Quadratische Funktion:

∑=

−=d

jjiji pq

0

),( pqδ

( )∑=

−=d

jjiji pq

0

2),( pqδ

jij

d

ji pq −=

=0max),( pqδ

( ) ( )iT

ii pqApqpq −−=),(δ


Visualisierung der Distanzmasse

• Die Flächen enthalten jene Punkte, welche vom Anfragevektor höchstens einenAbstand r haben. Bem: Die Anfragevektoren sind nicht identisch; sie befinden sich im“Zentrum” der jeweiligen Fläche des Distanzmasses.

Euklidisch

Manhattan Quadratische Funktion

Maximum Norm

dim 1

dim 2


• Anwendung der Distanzmasse– Die vorgestellten Metriken sollten nicht direkt auf den Merkmalsvektoren ange-

wendet werden, da die Verteilung der Werte der Komponenten nicht identisch ist:

• Bsp.: Komponente 1 enthalte Werte aus [0,1]; Komponente 2 enthalte Werteaus [100,200].

• Damit ist auch zu erwarten, dass die Differenzen der Komponente 1 wenigerzur Gesamtdistanz beitragen als die Differenzen aus Komponente 2. ImExtremfall entscheidet die Komponente 2 alleine über die Ähnlichkeit zweierVektoren; Komponente 1 könnte man ebenso gut weglassen!

• Abhilfe: Die Verteilung der Komponenten soll „ähnlich“ werden. Dies kannz.B. mit einer Gauss-Normalisierung erfolgen. dazu geht man wie folgt vor:

– Sei µj der Mittelwert und σj die Standardabweichung aller Werte einerKomponente j.

– Die gauss-normalisierten Werte berechnen sich wie folgt:

– Eingesetzt in z.B. die L1-Norm ergibt dies das endgültige Distanzmass

jj

jj

xx µ

σ−=ˆ

∑=

−=d

jjij

ji pq

0

1),(

σδ pq


– Bem.: Die Mittelwerte fallen bei allen Distanzmassen weg, d.h. manbraucht sie nicht zu berechnen.

– Bei quadratischen Distanzfunktionen, wie sie häufig bei Histogrammen auftreten,sollte man unbedingt zuerst eine „Eigenraum-Transformation“ durchführen. Ausder linearen Algebra:

• da Distanzen stets >0 sein müssen (ausser die beiden Vektoren sindidentisch), folgt, dass die Matrix A positiv definit sein muss. Positiv definitheisst, dass für alle Vektoren x≠0 gilt: xTAx>0.

• Da A positiv definit ist, sind auch alle Eigenwerte reel und positiv. DieEigenvektoren definieren somit die Hauptachsen der Ellipsen, welche mit derGleichung xTAx=const. entstehen (die Eigenwerte definieren die Länge derHauptachsen).

• Eine einfache Rotation und Skalierung führt die „gedrehte“ Ellipse in einenKreis über. Mit anderen Worten, durch eine Transformation des Raums kannanstelle der quadratischen Funktion im Ursprungsraum die Euklidsche Metrikim transformierten Raum angewendet werden:

Hauptachsen RotationSkalierung

Ursprungsraum transformierter Raum


Das “Nächste-Nachbar” Suchproblem

• Die Suche nach dem ähnlichsten Bild bedeutet, dass man jenen Merkmalsvektor pifinden muss, der σ(q,pi ) maximiert.

• Falls σ(q,pi ) via eine Distanzfunktion δ(q,pi ) berechnet wird, muss man denjenigenMerkmalsvektor pi finden, der δ(q,pi ) minimiert, d.h. am nächsten zum Anfragevektorq liegt. pi nennt man dann den nächsten Nachbar von q.

• Das “Nächste-Nachbar” Suchproblem ist wie folgt definiert:

Geg: Vektor q, eine Menge von Vektoren pj (0≤j<N) und eine Distanzfunktion δGes: pi, so dass ∀ j: δ(q,pi ) ≤ δ(q,pj ) (d.h. δ(q,pi ) ist minimal)

pi

q


Dimensionsreduktion

• In hoch-dimensionalen Räumen ist der Suchaufwand linear in der Anzahl Objekte, d.h.es müssen alle Merkmalsvektoren gelesen werden. Deshalb wäre es wünschenswert,die zu durchsuchende Datenmenge zu beschränken indem man approximierteVektoren und/oder approximierte Distanzfunktionen verwendet. Die Suchalgorithmenmüssen so angepasst werden, dass trotz ungenauer Distanz das exakte Resultatgeliefert wird.

• Eine Möglichkeit ist die Reduktion der Anzahl Dimensionen. In ihrer einfachsten Formwerden zufällig gewählte Dimensionen weggelassen. Bessere Ansätze verwerfen nurjene Dimensionen welche keine oder nur sehr wenig Information tragen. Amvielversprechendsten sind Methoden, welche die Daten in einen (unkorrelierten)Unterraum transformieren, so dass die Distanzen zwischen den einzelnenDatenobjekten erhalten bleibt. Die bekanntesten Vertreter sind:

– SVD

– K-L-Transformation– Diskrete Fourier Transformation

– Wavelet Transformation


Komplexe Anfragen

• Komplexe Anfragen bestehen aus

– (1) mehreren Anfrageobjekten (Referenzobjekte),

– (2a) mehreren verschiedenen Merkmalen (unter anderem auch Metadaten),– (2b) Textsuch-Anfragen auf Metadaten,

– (3) und “harten Fakten” (d.h. Prädikate auf den Metadaten; Klassifizierungen)

• Beispiele:

– (1) Alle Bilder die ähnlich zu Bild B und C sind

– (2a) Alle Bilder welche bzgl. Farbe und Form zu Bild A ähnlich sind– (2b) Alle Bilder ähnlich zu Bild D, welche die Wörter “Delphin” und “Wal” in der

Beschreibung enthalten– (3) Alle Bilder ähnlich zu Bild E, welche gratis (Preis=0) sind und ein “Auto”

enthalten.


Anfragen mit mehreren Referenzobjekten (Typ 1)

• Graphische Notation der Anfrage:

– Die Anfrage besteht aus K Referenz-objekten Q1,...,QK

– Es wird nur ein Merkmal für dieÄhnlichkeit benutzt

• Auswertung solcher Anfragen

– Für jedes Objekt in der DB wird die Distanz zu jedem Referenzobjekt bestimmt– Die einzelnen Distanzen werden zu einer Gesamtdistanz verrechnet unter

Verwenung einer Verknüpfungsfunktion D:

• Gegeben seien die K Distanzen δi eines Objektes zu den K Referenzobjekten

• die Gesamtdistanz δ ist dann: δ = D (δ1, ..., δK)

• Beispiele für Verknüpfungsfunktionen

• Maximum (fuzzy logic “and”): δ = max δi

• Minimum (fuzzy logic “or”): δ = min δi

• Durchschnitt: δ = 1/K Σ δi

• Gewichteter Durchschnitt : δ = Σ θi⋅ δi (θ : Gewichtsvektor)

Query

Q1 QKReferenz-objekte


v11 v1d v21 v2d

oi1 oid oi1 oid

- - - -

L L

D

h

[0,1]

• Auswertung: Anfrage besteht aus 2 Objekten; der Evaluierungsgraph sieht wie folgtaus:

Vektoren der Referenzobjekte

Vektor des i-ten Objektes

Distanz zwischen Ref.Objektund i-tem Objekt(Distanzfunktion ist L)

Gesamtdistanz des i-ten Objekt(D ist Verknüpfungsfunktion)

Umkehrfunktion h

Ähnlichkeitswert des i-ten Objektes

... ...

... ...


dim 1

dim 2

Minimum

dim 1

dim 2

Maximum

dim 1

dim 2

Gewichteter

Durchschnitt

dim 1

dim 2

Durchschnitt

xx

xx

xx

xx

• Geometrische Bedeutung der Verknüpfungsfunktionen: die Diagramme zeigen einenzweidimensionalen Merkmalsraum mit zwei Referenzobjekten. Die Flächen deckenjene Punkte des Merkmalsraum ab, deren Gesamtdistanz kleiner als r ist.


Anfragen mit mehreren Merkmalen (Typ 2a)

• Graphische Notation der Anfrage:

– Die Anfrage besteht aus einem Referenz-objekt Q

– Die Ähnlichkeit wird aufgrund der JMerkmale F1,...,FJ bestimmt

• Auswertung solcher Anfragen– Für jedes Objekt in der DB wird die Distanz zum Referenzobjekt für jedes Merkmal

bestimmt

– Die einzelnen Distanzen werden zu einer Gesamtdistanz verrechnet unterVerwendung einer Verknüpfungsfunktion D:

• Gegeben seien die J Distanzen δi eines Objektes für die J Merkmale

• die Gesamtdistanz δ ist dann: δ = D (δ1, ..., δJ)

• Beispiele für Verknüpfungsfunktionen

• Maximum (fuzzy logic “and”): δ = max δi

• Minimum (fuzzy logic “or”): δ = min δi

• Durchschnitt: δ = 1/J Σ δi

• Gewichteter Durchschnitt : δ = Σ θi⋅ δi (θ: Gewichtsvektor)

Query

Q

FJ

Referenz-objekt

F1 Merkmale...


v1,1 v1,d1 v2,1 v2,d2

oi,1,1 oi,1,d1 oi,2,1 oi,2,d2

- - - -

L L

D

h

[0,1]

• Auswertung: Anfrage besteht aus 1 Objekt und 2 Merkmalen; derEvaluierungsgraph sieht wie folgt aus:

Vektoren des Referenzobjektes(für jedes Merkmal)

Vektoren des i-ten Objektes(für jedes Merkmal)

Distanz zwischen Ref.Objektund i-tem Objekt bzgl. einesMerkmals (Distanzfunktion ist L)

Gesamtdistanz des i-ten Objekt(D ist Verknüpfungsfunktion)

Umkehrfunktion h

Ähnlichkeitswert des i-ten Objektes

...

... ...

...


Farbe

Textur

Minimum

Farbe

Textur

Maximum

Farbe

Textur

Gewichteter

Durchschnitt

Farbe

Textur

Durchschnitt

• Geometrische Bedeutung der Verknüpfungsfunktionen: die x-Achse der Diagrammeentspricht der Distanz bzgl. des Merkmals “Textur”, die y-Achse bzgl. des Merkmals“Farbe”. Die Flächen decken jene Objekte ab, deren Gesamtdistanz kleiner als r ist.


• Da die Merkmale unterschiedliche Dimensionen und Metriken verwenden, liefern sieDistanzen mit unterschiedlichen Verteilungen. Um Distanzen z.B. mit min, max oderaverage zusammenzufassen, müssen die Distanzen aber vergleichbare Verteilungenaufweisen (siehe auch Distanzberechnung innerhalb eines Merkmals). Dies kann z.B.wiederum mit Gauss-Normalisierung erreicht werden.

– Der Mittelwert und die Standardabweichung werden durch eine genügend grosseStichprobe ermittelt (Vergleich der Vektoren in der Datenbank).

– Im Gegensatz zur Distanzberechnung benötigen einige Verknüpfungsfunktionen(z.B. min) auch den Mittelwert. Andere (z.B. Average) benötigen den Mittelwertnicht unbedingt für die korrekte Ordnung der Bilder

• Bem: Bei mehreren Referenzobjekten braucht es keine Normalisierung, da dieDistanzen dieselbe Verteilung haben (sie werden ja in demselben Merkmalsraumberechnet, aber mit unterschiedlichen Referenzpunkten)


Anfragen mit Textsuchbestandteilen (Typ 2b)

• Textsuchbestandteile können in unterschiedlichen Varianten auftauchen (s. Kap. 1):

a) Boolesche Suche

b) Vektorraumretrievalc) Latent Semantic Indexing

d) Probabilistisches Retrieval

e) Signaturen (Cover, Hamming)f) SQL (alle Bilder von Fotograph XY)

Einige Modelle (b,c,d) liefern Retrieval Status Werte (RSV) zurück, welche zwarähnlich den Distanzen sind, aber semantisch eine andere Bedeutung haben

– „je grösser der RSV, desto besser das Dokument“ vs. „je kleiner die Distanz,desto ähnlicher sind die Bilder“

Andere Modelle (a,f) bestimmen nur eine Menge von Treffern ohne Ordnung derDokumente. D.h. diese Modelle arbeiten wie Prädikate als Filter auf der Kollektion.Letzlich gibt es aber auch Modelle (e) welche Distanzen zurückgegeben.

• Somit benötigen wir für die Integration von Textsuchbestandteilen drei Lösungen für– Modelle mit Distanzen

– Modelle mit RSV

– Modelle mit Prädikaten (siehe „Anfragen mit Prädikaten“)


• Modelle mit Distanzen– Grundsätzlich ist die Integration identisch mit Anfragen über mehrere Vektor-

Merkmale. Da aber die Darstellung der Dokumente und der Referenzobjekte nichtunbedingt in Vektorform ist, ändert sich das Auswertungsschema leicht (z.B.Signaturen):

v1,1 v1,d1 v2,1 v2,d2

oi,1,1 oi,1,d1 oi,2,1 oi,2,d2

- - - -

L L

D

h

[0,1]

...

... ...

... vsig

oi,sig

L

...

...


• Modelle mit RSV– Die RSV Werte müssen kompatibel zu den Distanzen gemacht werden. Z.B.

könnte (-rsv+const.) als Distanzmass benutzt werden (const. sollte genügend grossgewählt werden, damit alle Distanzen >0 sind). Die Auswertung ist dann wie folgt:

v1,1 v1,d1 v2,1 v2,d2

oi,1,1 oi,1,d1 oi,2,1 oi,2,d2

- - - -

L L

D

h

[0,1]

...

... ...

... tref.

ti

RSV

...

...

-rsv+const.


Anfragen mit Prädikaten (Typ 3)

• Dokumente, welche die Prädikate nicht erfüllen sind unerwünscht und sollten deshalbeinen Ähnlichkeitswert von 0 haben. Dokumente, welche die Prädikate erfüllen,behalten den Ähnlichkeitswert, welcher mit den Merkmalen berechnet wurden. DasAuswertungsschema sieht wie folgt aus:

L L

D

h

[0,1]

Prädikat

... ...

Falls Prädikat erfüllt, so wird derEingabewerte durchgereicht,andernfalls wird eine 0 ausgegeben


Gewichtung

• Bisher können wir noch nicht angeben, wie wichtig ein Merkmal oder Referenzobjektist. In einigen Fällen ist dies aber sehr nützlich resp. notwendig. Z.B.:– Falls die Referenzobjekte unterschiedlich gut sind, so möchte man jene stärker

gewichten, welche besser sind.– Merkmale sind nicht immer gleich wichtig. Bei der Suche nach Fotos ist Farbe

wichtiger als Textur, und Textur wichtiger als Form. Bei der Suche inObjektdatenbanken (z.B. CAD-Teile) ist aber die Form wichtiger als die Farbe.

– Das Resultat eines „Relevanz Feedback“ Schrittes ist in vielen Fällen einGewichtschema, welches ausdrückt, wie gut die einzelnen Referenzobjekte,Merkmale oder gar Dimensionen geeignet sind, das Informationsbedürfnis desBenutzers zu beschreiben.

• Wir erweitern deshalb unser Schema um Gewichte auf allen Stufen, d.h. es könnenGewichte für Dimensionen, Merkmale und Referenzobjekte angegeben werden. DieseGewichte werden aber nicht direkt mit den Distanzen verknüpft sondern zusammenmit den Distanzen in die entsprechende Verknüpfungsfunktion „gefüttert“. Wie wirgleich sehen werden, ist das Gewichten von Distanzen nicht ganz trivial.


v1,1,1 v1,1,k v1,sig

o1,1,1 o1,1,k o1,sig

- -

L1,1 L1,sig

δ1

δ

w1,1,1 w1,1,k

w1,1 w1,sig

w1 wi

^^

^ ^

h[0,1] Prädikat

L1,2

w1,2 ^

...

vi,1,1 vi,1,l tref.

oi,1,1 oi,1,l oi,t

- -

Li,1

RSV

δi

wi,1,1 wi,1,l

wi,1 wi,t

^^

^ ^

Li,2

wi,2 ^

...

-rsv+const.

^^Referenzobjekt 1 Referenzobjekt i

w1,2,1 w1,2,a wi,2,1 wi,2,b


• Gewichte und Distanzfunktionen/RSV-Funktionen– Die Gewichte können direkt mit den Komponenten der Vektoren multipliziert

werden. Z.B. sieht die L1-Norm für ein Vektormerkmal nun wie folgt aus:

– Die anderen Distanzfunktionen und RSV-Funktionen können ähnlich angepasstwerden.

• Gewichte und Distanzen– Falls die Verknüpfungsfunktion den Durchschnitt oder gewichteten Durchschnitt

der Distanzen berechnet, so ist das Gewichten kein Problem (analog zu L1).Benutzt man aber „min“ (OR-Semantik) oder „max“ (AND-Semantik), so kann mannicht einfach die Distanz mit dem Gewicht multiplizieren:

• Bsp: d1 und d2 seien Distanzen aus dem Bereich [5..6]. Ferner sei d1 mit 0.4und d2 mit 0.6 gewichtet und „max“ sei die Verknüpfungsfunktion, d.h.d=max(0.4*d1, 0.6*d2).

• Da (0.4*d1) im Bereich [2..2.4] und (0.6*d2) im Bereich [3..3.6] liegen, kann(0.4*d1) nie grösser werden als (0.6*d2) und somit bestimmt alleine d2 dieGesamtdistanz d. Mit anderen Worten: das Merkmal mit Distanz d1 ist ausdem Vergleich gefallen.

∑=

−=d

jjij

j

ji pq

w

0

),(σ

δ pq


– Eine bessere Variante wurde von Fagin 1997 vorgeschlagen. Das Ziel sollte sein,eine gewichtete Verknüpfungsfunktion basierend auf einer ungewichtetenVerknüpfungsfunktion zu erhalten, welche monoton und stetig in den Argumentenist. Also sollte z.B. gelten (Dw sei eine gewichtete Verknüpfunsgsfunktion):

• x1>x1‘ und x2>x2‘ => Dw(x1,x2)>Dw(x1‘,x2‘) (monoton)• stetig: keine „Sprünge“ bei kleinen Änderungen der Distanzen und Gewichte

– Im Folgenden sei D die ungewichtete Verknüpfungsfunktion (z.B. „min“) und Dw

die gewichtete Variante mit w als Gewichtsvektor. Im Weiteren seien die Distanzennach absteigenden Gewichten sortiert (wm=0).

– Im Bsp. von vorne also:d = (0.6 - 0.4)*max(d2) + 2*0.4*max(d1,d2)

= 0.2 * d2 + 0.8 * max(d1,d2)

( ) ( ) ( )

( ) ( ) ( ) ( ) ( )1011021010

101

110

,,,2

,,,,

−−

−=

−−

⋅⋅++⋅−⋅+⋅−=

⋅−⋅=∑

mm

i

m

iiim

w

xxDwmxxDwwxDww

xxDwwixxD

KL

KK


3.4 Indexstrukturen und Algorithmen

• In diesem Kapitel beschränken wir uns auf die Lösung des nächsten Nachbar (NN)Problems mit einem Referenzbild in einem Merkmalsraum ohne Prädikate oderTextbestandteile. Die zu lösende Aufgabe lautet also:

Geg: Vektor q, eine Menge von Vektoren pj (0≤j<N) und eine Distanzfunktion δGes: pi, so dass ∀ j: δ(q,pi ) ≤ δ(q,pj ) (d.h. δ(q,pi ) ist minimal)

• In den vergangenen Jahren wurden zahreiche Vorschläge gemacht, um das obigeProblem in einem d-dimensionalen Raum zu lösen. Allerdings mit bescheidenemErfolg: bis heute gibt es nur für Räume mit weniger als 5 Dimensionen vernünftigschnelle Lösung. Sobald die Dimensionalität gross ist und die Daten nicht zu starkkorreliert sind, kann man das NN-Problem nur noch in linearer Zeit lösen. DiesesPhänomen wird in der Literatur der “Fluch der Dimensionen” (curse of dimensionality)genannt.

• Im Folgenden gehen wir kurz auf einige Vorschläge ein, besprechen dann den “Fluchder Dimensionen” anhand einiger Beispiele und betrachten uns die Lösung, welche ander ETH entwickelt wurde und zur Zeit die schnellste Suche in hoch-dimensionalenVektorräumen erlaubt.

• Hinweis: In Kapitel 3.2 haben wir gesehen, dass die Dimensionalität der Bildmerkmaledeutlich grösser als 5 sind. Die einfachsten verwenden 9 Dimensionen, die besserenmehrere 100 Dimensionen.


• Der Quadtree wurde 1974 von Finkel und Bentley vorgeschlagen. Damals war das Zielnoch einen Index im Hauptspeicher aufzubauen, d.h. der ursprüngliche Quadtreearbeitet nicht effizient mit externen Speicher. Zudem wurde er vor allem für 2-dim.Räume gebaut. Erweiterung für 3 Dimensionen und mehr existieren zwar, haben sichaber nicht durchgesetzt.

• Idee:– Ein 2-dim. Datenraum kann mit 2 senkrechten Linien in 4 Bereiche aufgeteilt

(daher auch der Name Quadtree) werden. Die Bereiche tragen die AbkürzungenNE (nord-ost), NW, SE, und SW:

– Diese Aufteilung kann rekursiv verfeinert werden, so dass eine hierarchischeStruktur entsteht. Die Aufteilung kann unterschiedlich erfolgen:

• Beim „Punkt-Quadtree“ werden neue Datenpunkte in einem der Blätter desBaumes gespeichert. Dabei teilen sie dieses Blatt so, dass die Trennlinien sichim Datenpunkt schneiden. Es entstehen 4 neue Blätter.

• Beim „Regionen-Quadtree“ wird der Raum in der Mitte geteilt. Dadurchvereinfachen sich alle Algorithmen.

3.4.1 Quadtree

NENW

SW SE

NENW

SW SE

Punkt-Quadtree Regionen-Quadtree Hierarchie

NW NE SW SE


• Vorteile:– Einfache Implementierung

– Gute Performanz in 2-dim Räumen, falls der Quadtree balanciert ist• Nachteile

– In höher dimensionalen Räumen nicht sinnvoll, da 2d Teilräume entstehen

– I.A. ist der Quadtree nicht balanciert; die Struktur hängt zudem von derReihenfolge der Punkte beim Einfügen ab.

– Hauptspeicherstruktur; es ist zwar möglich, den Quadtree auf einem sekundärenSpeicher zu verwalten, doch die IO-Performance ist relativ schlecht


3.4.2 k-d-Tree

• Bentley entwickelte im Jahr 1975 eine binäre Struktur, den k-d-Tree, welcher auch inhöher dimensionalen Räumen angewendet werden kann.

• Idee:

– Der k-d-Tree ist ein binärer Baum. Jeder Knoten enthält einen Punkt, welcher denTeilraum des Knotens orthogonal zu einer Achse halbiert. Die Wahl der Achsen istabhängig von der Höhe des Knotens im Baum, d.h. im 2-dim Beispiel werden dieAchsen von oben nach unten alternierend gewählt

– Einfügen: Ein neuer Punkt wird im zugehörigen Blatt eingefügt. Dabei wird dieserin zwei neue Blätter geteilt (d.h. das ursprüngliche Blatt wird zu einem innerenKnoten)

– Varianten:• Teilung entlang eines beliebigen Punktes; Achse kann frei gewählt werden

• k-d-B-Tree: balancierte Variante des k-d-Trees analog zum B-Baum.


• Vorteile:– Einfache Implementierung

– Gute Performanz in 2-dim Räumen, falls der k-d-Tree balanciert ist• Nachteile

– I.A. ist der k-d-Tree nicht balanciert; die Struktur hängt wie beim Quadtree von derReihenfolge der Punkte beim Einfügen ab. Ausnahme: falls der k-d-Tree mitBulkload geladen wird, oder falls ein k-d-B-Tree verwendet wird


3.4.3 Gridfile

• Nievergelt und Hinterberger haben 1981/1984 das Gridfile entwickelt.

• Idee:– Der Datenraum wird mit einem „Gitter“ (grid) unterteilt. Dabei entstehen

rechteckige Zellen. Ein Directory weist jeder Zelle einen Datenblock auf der Diskzu, wobei es möglich ist, das mehrere Zellen auf dem selben Datenblock zu liegenkommen. Die Punkte einer Zelle werden im entsprechenden Datenblockgespeichert.

– Einfügen: Ein Punkt wird dem Datenblock seiner Zelle zugewiesen. Falls einÜberlauf stattfindet, so wird eine neue Trennlinie eingefügt und die neuen Zellenmüssen im Directory eingetragen werden. Falls das Directory gross ist, kann esebenfalls auf Disk gespeichert werden.

1 2 3 123


• Vorteile:– Einfache Implementierung (Löschen und Update sind etwas aufwändiger, falls

man eine ausgeglichene Struktur wünscht)

– Gute Performanz: mit maximal 2 Diskzugriffen kann eine „Punktanfrage“ausgewertet werden (d.h. nachschauen, ob ein Punkt in der Datenbank ist)

• Nachteile– Beim iterativen Einfügen in das Gridfile entsteht häufig eine unausgeglichene

Struktur, d.h. einzelne Zellen enthalten keine Punkte, andere enthalten sehr viele– Schlechtes Verhalten bei Datenmengen mit Clustern und vielen leeren Bereichen.

Das entstehende Gitter enthält zu viele leere Zellen.– Die Directory-Grösse wächst superlinear in der Anzahl Punkte


3.4.4 Space-Filling Curves

• Idee:– Der Raum wird wie beim Gridfile mit einem regelmässigem Gitter aufgeteilt. Die

Zellen werden dann mit einer „space-filling curve“ durchnummeriert, z.B. mit einerZ-Ordnung oder einer Hilbert-Kurve:

– Dank einer solchen Kurven können Teilbereiche des Raumes auf einen einzelnenWert (Suchschlüssel) abgebildet werden. Ein Datenpunkt erhält dabei denSuchschlüssel des ihn umgebenden Teilbereichs. Alle Punkte werden in einem B-Baum gespeichert, geordnet nach ihrem Suchschlüssel.

– Bereichsanfragen im Raum werden in (mehrere) Bereichsanfragen im B-Baumumgewandelt.

z-Ordering Peano-Hilbert-Ordering


– Dieses Konzept wurde in verschiedenen Varianten umgesetzt; auch Oraclebenutzt diese Technik für ihre GIS-Erweiterung.

• Vorteile:– Einfache Implementierung; die Abbilung eines Punktes auf den Schlüsselwert

kann mittels einfacher Operation erfolgen

– Bestehende Indexstrukturen für eindimensionale Daten können wiederverwendetwerden. Besonders interessant ist der Ansatz, falls man bereits über eineDatenbank verfügt

• Nachteile:– Die Abbildung des Punktes ist im 2-dim Raum noch einigermassen gut (wenn

auch nicht immer; z.B. die Mitte des Raumes wird sehr schlecht abgebildet); imhoch-dimensionalen Raum ist der örtliche Zusammenhang mit dem Schlüsselwertnicht mehr befriedigend.


3.4.5 Voronoi Diagramme

• Idee:– Ein Voronoi Diagramm unterteilt einen Raum für eine gegebene Menge von

Punkten so, dass die entstehenden Teilbereiche genau jene Punkte enthaltenwelche zu den gegebenen Punkten am nächsten liegen.

– Um den nächsten Nachbar zu finden, braucht man nur den Teilbereich zuidentifizieren, in dem der Anfragepunkt liegt. Der zum Teilbereich gehörendePunkt ist dann der NN des Anfragepunkts.

– Allerdings gibt es zwei Probleme:• Das Berechnen des Voronoi-Diagrams ist teuer; in höher dimensionalen

Räumen ist es praktisch unmöglich (d.h. die Rechenzeit ist zu hoch)• Das Identifizieren des Teilbereichs ist nicht einfach; in 2-d geht dies noch mit

o(log n)-Aufwand. In höher dimensionalen Räumen ist auch dies zu teuer

Voronoi-Zelle: Alle Punkte in diesemBereich liegen am nächstenzu dem dargestellten Punkt


– An der Universität in München ist dennoch eine Struktur entstanden, welche aufdiesem Konzept basiert. Allerdings werden keine „echten“ Voronoi-Diagrammebenutzt, sondern sich gegenseitig überlappende Approximationen der Voronoi-Zellen. Diese Approximationen können in einer herkömmlichen mehr-dimensionalen Indexstruktur gespeichert werden. Die Suche erfolgt dann alsPunktabfrage über die Approximationen, d.h. es wird ermittelt, welcheApproximationen den Anfragepunkt enthalten. Aus diesen Kandidaten wird derrichtige NN ermittelt (Distanzberechnungen)

• Vorteile:– Relativ gute Antwortzeiten in niedrig dimensionalen Räumen

• Nachteile:– Die Berechnung der Voronoi-Diagramme ist teuer; zudem können die Voronoi-

Zellen nicht einfach abgespeichert werden (Speicheraufwand zu gross)

– Die Suchzeiten sind nicht besser als jene anderer Methoden


3.4.6 R-Tree

• Idee: (Guttman, 1984)– Im Gegensatz zu den bisherigen Strukturen soll der R-Baum perfekt balanciert

sein. Wie beim B-Baum soll jeder Knoten (ausser der Wurzel) einen Mindest-Füllgrad aufweisen und die Blätter sollen alle auf der selben Höhe liegen.

R-Tree


– Im R-Baum gibt es zwei Knotentypen:

• Blattknoten enthalten die Punktdaten. Für jedes Blatt wird zudem daskleinste Rechteck gespeichert, welches alle Punkte des Blattes enthält(minimum bounding region, MBR). Natürlich sollten Blätter so gewähltwerden, dass sie nur benachbarte Punkte enthalten.

• Innere Knoten umfassen entweder eine Menge von Blattknoten oder eineMenge von inneren Knoten. Ein innerer Knoten enthält alle MBRs seinerKindknoten und seine eigene MBR.

– Einfügen eines neuen Punktes in den R-Baum

1. Suche einen Pfad von der Wurzel zu einem Blatt

2. Füge den neuen Punkt in den Blattknoten ein und passe evtl. die MBR desBlattes an (falls der Punkt nicht im MBR des Blattes liegt)

3. Falls das Blatt voll ist, d.h. kein Platz für den Punkt vorhanden ist, dann teiledas Blatt in zwei neue Blätter auf. Füge die neuen Blätter in den Elternknotenein. Dies kann evtl. zu einem Überlauf des Elternknotens führen. In diesemFall wird rekursiv weiter geteilt.

4. Falls die Wurzel geteilt werden muss, dann muss ein neuer Wurzelknotenerzeugt werden. Dabei wird die Höhe des Baumes um 1 grösser.

– Dieser Einfügalgorithmus garantiert, dass der Baum stets balanciert ist und dassalle Knoten (ausser der Wurzel) mind. einen Füllgrad von 50% aufweisen.


– Einige Punkte des Einfügealgorithmuses bedürfen weiterer Erläuterungen

• Suchen eines Pfades von der Wurzel zu einem Blatt: Da sich die MBRs derinneren Knoten überlappen können, gibt es mehrere Möglichkeiten, um einenKindknoten auszuwählen.

– Falls der neue Punkt in keiner MBR enthalten ist, dann wird derjenigeKnoten selektiert, dess MBR am nächsten zum neuen Punkt liegt.

– Falls der neue Punkt in genau einer MBR enthalten ist, dann folge dementsprechenden Kindknoten

– Falls der neue Punkt in mehreren MBRs liegt, dann wähle einen Knotenaus (z.B. zufällig, oder nach einer bestimmten Metrik)

Damit kann also nicht garantiert werden, dass ein neuer Punkt auchtatsächlich in das beste Blatt eingefügt wird.

Neuer Punkt

Auf der ersten Stufe desBaumes (äussere Rechtecke)scheint der neue Punkt besserzum linken Bereich zu passen(Punkt liegt ganz am Randedes rechten Bereichs). AufBlattstufe wäre aber ein Blattdes linken Bereichs besser.

bestes Blatt

gewähltes Blatt


• Aufteilen eines Blattes (splitting): Falls ein Knoten überläuft, so müssenzwei neue Knoten konstruiert werden. Die Aufteilung der Punkte/MBRs solltemöglichst so erfolgen, dass die MBRs der neuen Knoten disjunkt werden. Zudiesem Zweck werden die MBRs eines Knotens entlang einer Achse geteiltund in zwei Gruppen getrennt. Ein Optimalitätskriterium bestimmt, welcheAchse gewählt wird und wie die Gruppen zusammengesetzt sein müssen. Inder Regel führt das Aufteilen aber nicht zu disjunkten Bereichen.

– Punktsuche:• Der Baum wird von der Wurzel zu den Blättern traversiert. Bei jedem inneren

Knoten werden all jene Kindknoten weiterverfolgt, deren MBR den Punktenthalten. In Blattknoten wird direkt nach dem Punkt gesucht.

• Im Gegensatz zum k-d-Tree (k-d-B-Tree) führt die Punktsuche im R-Baumevtl. zum Besuch von mehreren Blättern (wegen der Überlappung der MBR)

– „Spatial data“• Der R-Baum kann nicht nur Punktdaten verwalten sondern beliebige

Extensionen (z.B. Rechtecke, Polygone, Kreise, etc.). Die Blätter enthaltendann nicht mehr Punkte sonder Rechtecke, welche die Extension derDatenobjekte begrenzen (minimum bounding box).

• Der R-Baum ist sehr verbreitet im GIS Bereich. Einzelne Datenbanken (Informix)bieten den R-Baum als Indexstruktur an


• Vorteile:– Der R-Baum ist stets perfekt balanciert. Die Höhe des Baumes ist logarithmisch in

der Anzahl der Punkte.

– Die Implementierung ist optimiert für sekundäre Speicher. Z.B. können die innerenKnoten in einem Cache im Hauptspeicher gehalten werden. Nur die Blättermüssen von Disk geladen werden

– Gute Performanz in niedrig-dimensionalen Räumen

– Es existieren einige Bulkload-Operationen, welche das Aufbauen des Baumesenorm beschleunigen

• Nachteile:– Die Überlappung der MBRs ist eines der grossen Probleme des R-Baums. Der R-

Baum sollte deshalb von Zeit zu Zeit neu aufgebaut werden (und zwar mit einemBulkload-Algorithmus)

– Schlechte Performanz in hoch-dimensionalen Räumen

– Grundoperationen (insert, update, delete) sind recht teuer


• R-Tree Erweiterungen– In den letzten Jahren sind unzählige Erweiterungen/Verfeinerungen des R-Baums

publiziert worden. Das Grundkonzept des Baumes ist aber stets dasselbe. Varriertwurden unter anderem:

• Die Form der MBRs:– Der SS-Baum (SS: similarity search) und SS+-Baum benutzen

kreisförmige Regionen um die Ausdehnung der Knoten zu beschreiben.– Der TV-Baum (TV: telescope vector) benutzt eine variable Anzahl von

Dimensionen für die Indexierung, d.h. die inneren Knoten „sehen“ nur diewichtigsten Komponenten der Vektoren darunter. Wie der SS-Baumwerden die MBRs mit Sphären beschrieben

– Der SR-Baum benutzt eine Kombination von Rechtecken und Sphärenzur Beschreibung der MBRs.

• Splitting:– Der SS+-Baum verwendet einen Clusterungsalgorithmus (k-means), um

den übervollen Knoten aufzuteilen– Der R*-Baum teilt einen Knoten analog zum R-Baum. Um die

Überlappung der MBRs zu verkleinern, wird bei jedem Aufteilen einesBlattknotens ein Teil der Punkte neu eingefügt

– Der X-Baum teilt die Knoten so auf, dass (fast) keine Überlappungenentstehen.


• Seitengrösse der Knoten:– Der X-Baum verwendet sogenannte Superknoten. Falls sich ein split nicht

lohnt (Überlappung zu gross), dann wird der Knoten nicht geteilt sondernauf mehreren Seiten gespeichert (overflow buffer)

– Noch einen Schritt weiter geht der DABS-Baum. Bei jedem Überlauf wirdmit Hilfe eines Kostenmodells überprüft, welche Seitengrösse optimal füreinen Knoten ist.

• Metrik:– Während alle bisher besprochenen Bäume nur für d-dimensionale Räume

mit einer Ls-norm verwendet werden können, bietet der M-Baum einehierarchische Struktur für beliebige Metriken an. Die gespeichertenObjekte müssen nicht mal Punktdaten sein. So kann der M-Baum auchmit Strings und „Edit-Distance“ umgehen.


Übersicht der R-Baum Erweiterungen

• R-Tree [Guttman:1984]

• R+-Tree [Sellis:1987]– nur nicht-überlappende MBRs auf der selben Indexhöhe; zu diesem Zweck

können Objekte mit einer Fläche>0 auf mehrere Knoten verteilt werden, d.h. dieObjekte werden in mehreren Blättern redundant gespeichert

• R*-Tree [Beckmann:1990]– bessere Splitting Strategie im Vergleich zu R- und R+-Baum– Bei jedem split wird ein Teil der Datenobjekte erneut eingefügt; diese

Restrukturierung führen zu einer weiteren Verkleinerung der Überlappung derMBRs

• P-Tree [Jagadish:1990]– Beim Splitting können die Knoten nicht nur entlang der Achsen geteilt werden,

sondern auch entlang weiterer m Richtungen.– MBRs werden durch Polygone beschrieben; die Seitenflächen liegen orthogonal

zu einer der m Richtungen oder einer der Achsen

• TV-Tree [Faloutsos:1994]– In inneren Knoten werden die Vektoren durch niedrig-dimensionale Vektoren

approximiert (eine Art Dimensionsreduktion). Dadurch soll es möglich werden,auch sehr hoch-dimensionale Daten zu indexieren.


• vp-Tree [Chiueh:1994]– Der vp-Tree ist ein binärer Suchbaum, der rekursiv von der Wurzel zu den Blättern

aufgebaut wird (top-down).– In jedem Knoten wird ein so genannter vantage point ermittelt. Die Datenpunkte

werden in Abhängigkeit ihrer Distanz zum vantage point in zwei Gruppenaufgeteilt, d.h. in eine Gruppe mit Distanzen kleiner der Median-Distanz und ineine Gruppe mit Distanzen grösser der Median-Distanz. Die zwei Gruppen bildendie neuen Kindknoten und werden rekursiv weiter geteilt bis die Knoten genügendklein sind.

• X-Tree [Berchtold:1996]– Verbesserter Splitting-Algorithmus (fast keine Überlappungen der MBRs mehr)– Optimierte Disk-Organisation für hoch-dimensionale Räume; Falls sich ein split

nicht lohnt (resultierende Knoten haben eine zu starke Überlappung) werden dieKnoten zu so genannte Super-nodes umgewandelt. Ein Super-node kann aufmehreren Diskseiten liegen

• SS-Tree [White:1996]– Der SS-Baum verwendet wie der R*-Baum eine re-insertion strategy, um die

Überlappung der MBRs zu verkleinern (welche leicht unterschiedlich ist).Desweiteren werden sphärische MBRs benutzt.

• SS+-Tree [Kurniawati:1997]– Eine Erweiterung des SS-Baums, welche im Durchschnitt kleinere MBRs für die

Knoten benutzt. Bei der Teilung wird ein Clusterungs-Algorithmus angewendet.


• SR-Tree [Katayama:1997]– Der SR-Baum ist eine Mischung des R*-Baumes und des SS-Baumes. Die MBRs

werden mit Hilfe von Rechtecken und Sphären bestimmt, d.h. die MBRs werdendurch den Schnitt von Rechteck und Sphäre beschrieben.

• M-Tree [Ciaccia:1997]– Der M-Baum eignet sich nicht nur für Vektorräume mit einer Lp-Norm, sondern

kann beliebige Objekte, für die eine Metrik definiert wurde, verwalten. In einemVektorraum mit L2-Norm sieht der M-Baum wie ein SS-Baum aus.

• DABS-Tree [Böhm:2000]– Verfeinert das Konzept der Super-nodes im X-Tree. Ein Knoten muss nun nicht

mehr auf eine Diskseite passen, sondern kann auf mehrere, nacheinanderliegenden Seiten abgespeichert werden. Die optimale (in Bezug auf Suchkosten)Grösse der Knoten wird mit Hilfe eines Kostenmodells ermittelt.

• GiST [Hellerstein:1995]– Der generalized search tree ist ein Framework für multi-dimensionale

Indexstrukturen. Die Implementierung übernimmt die ganze Verwaltung (inkl.Diskorganisation); der Benutzer muss nur noch die Index spezifischen Merkmalehinzufügen (z.B. splitting, Format der Datenobjekte, Format der inneren Knoten,re-insertion Strategie)


3.4.7 Andere hierarchische Indexstrukturen

• Pyramid-Tree [Berchtold:1998]– Der Pyramid-Baum ist ein auf die L∞-Norm optimierter Index. Der Datenraum wird

durch Pyramiden aufgeteilt, deren Grundfläche einer Aussenfläche des(rechteckigen) Datenraums entsprechen und deren Spitzen sich in einem Punkt imRaum treffen. Jede Pyramide wird entlang der Falllinie von Spitze zu Grundflächein mehrere Scheiben aufgeteilt. Wie bei den space-filling curves kann mit Hilfedieser Scheiben und einer geeigneten Nummerierung eine Abbildung der Punkteauf einen ein-dimensionalen Bereich definiert werden.

• P-Sphere Tree [Goldstein:2000]– Der P-Sphere Baum hat eine zweistufige Struktur: die Wurzel enthält eine Menge

von sphärischen MBRs; jede MBR repräsentiert eine Menge von Punkten, welchein den Blattknoten gespeichert sind.

– Im Gegensatz zu allen bisher besprochenen Ansätzen kann ein Punkt in mehrerenBlättern gespeichert sein, d.h. der P-Sphere Baum nimmt Redundanzen in Kauf.Auf der anderen Seite sind die Blätter und deren MBRs so gross, dass nur nochsehr wenige Blätter bei der NN-Suche betrachtet werden müssen. Mit anderenWorten, die eingeführte Redundanz soll die Suchzeiten reduzieren.

– Der P-Sphere Tree ist, gemäss Messungen, eine gute Alternative für Räume mit10-100 Dimensionen.


3.4.8 NN-Suche in hierarchischen Strukturen

• Hjaltson und Samet haben 1995 einen allgemein gültigen Algorithmus vorgestellt, dereine optimale NN-Suche in Bäumen ausführt. Optimal heisst hierbei, dass die Anzahlbesuchter Blätter und damit auch die Anzahl gelesener Seiten minimal ist.

• Der Algorithmus verwendet eine Priority-Queue für die Knoten und Punkte. DiePriorität ist dabei gegeben als der minimale Abstand des Anfragepunktes zur MBR desKnotens resp. zum Punkt (aufsteigend geordnet, d.h. zuoberst ist der Knoten/Punktmit kleinster Distanz). Die Knoten/Punkte werden dann in dieser Reihenfolge besucht.Für einen gegebenen Anfragepunkt wird der nächste Nachbar wie folgt ermittelt:

1. Initialisierung: der Wurzelknoten wird in die Queue eingefügt

2. Solange die Queue nicht leer ist

a) Lese das oberste Element und entferne es aus der Queueb) Falls das oberste Element ein innerer Knoten ist, dann füge alle Kindknoten

in die Queue ein. Die Priorität der Kindknoten ist gegeben als minimaleDistanz zwischen Anfragepunkt und MBR des Kindknotens.

c) Falls das oberste Element ein Blattknoten ist, dann füge alle Punkte in dieQueue ein. Die Priorität der Datenpunkte ist durch die Distanz zwischenAnfragepunkt und Datenpunkt gegeben.

d) Falls das oberste Element eine Punkt ist, dann ist dies der NN zumAnfragepunkt und die Suche kann abgebrochen werden.


• Beweis der Korrektheit– Die Prioritäten in der Queue entsprechen den minimalen Distanzen zwischen dem

Anfragepunkt und der MBR des Knotens resp. den Distanzen zwischenAnfragepunkt und Datenpunkten.

– Wegen der Konstruktion der MBRs muss gelten: die Prioritäten der Kindelementeeines Knotens ist stets grösser (gleich) wie diejenige des Knotens.

– Falls also ein Datenpunkt zu oberst in der Queue liegt, so bedeutet dies, dass allenicht besuchten Knoten weiter entfernt liegen. Damit sind aber auch alle Punkteunterhalb dieser Knoten weiter entfernt und können somit nicht der nächsteNachbar zum Anfragepunkt sein.

• Beweis der Optimalität– Angenommen wir kennen den nächsten Nachbar bereits. Dann können wir einen

Kreis mit Mittelpunkt=Anfragepunkt durch dennächsten Nachbar legen. Der Kreis heisst NN-Sphäre (NN-sphere) und enthält genau einenDatenpunkt – den nächsten Nachbar (siehe Figur).

– Ein optimaler Algorithmus muss nun all jene Knotendes Baumes betrachten, deren MBR sich mit dieserNN-Sphäre schneidet, um sicher zu sein, dass dergefundene Punkt der NN ist.

NN-sphere

NN-dist


• Beweis der Optimalität (Forts.)– Alle Knoten, deren MBR sich nicht mit der NN-Sphäre schneidet müssen nicht

betrachtet werden, da sie unmöglich den nächsten Nachbar enthalten können.

– Der HS-Algorithmus betrachtet Knoten mit aufsteigender minimalen Distanz zumAnfragepunkt. Falls ein Datenpunkt zu oberst in der Queue liegt, dann wurden nurjene Knoten betrachtet, welche eine kleinere Distanz zum Anfragepunkt hatten alsdieser Datenpunkt. Mit anderen Worten, es wurden nur Knoten betrachtet, derenMBR sich mit der NN-Sphäre schneidet. Die Knoten, deren MBR sich nicht mit derNN-Sphäre schneiden, liegen alle noch in der Queue (resp. deren Elternknotenliegen noch in der Queue). Somit betrachtet der HS-Algorithmus genau jeneKnoten, welche auch ein optimaler Algorithmus lesen muss.

• Bemerkungen– Der HS-Algorithmus muss in der Regel mehrere Blätter lesen bis der NN gefunden

werden kann (auch wenn die MBRs der Blätter sich nicht überlappen)– Da der HS-Algorithmus genau jene Blätter liest, deren MBRs sich mit der NN-

Sphäre schneiden, kann man die Kosten der NN-Suche relativ gut abschätzen. Esgibt eine Anzahl von Modellen, welche zuerst die erwartete NN-Distanz schätzenund dann die zu erwartende Anzahl Blattknoten bestimmen, die gelesen werdenmuss. Damit ist es möglich, die Kosten schon vor der Suche abzuschätzen; diesist vor allem für Query-Optimizer wichtig.


3.4.9 Fluch der hohen Dimensionen

• Ein Grund für die Flut von Indexstrukturen für multi-dimensionale Daten ist dieschlechte Performanz der Methoden in hoch-dimensionalen Räumen. DasHauptproblem liegt darin, dass die Indexstrukturen für 2/3-dimensionale Problemekonstruiert und dann auf höher dimensionale Probleme übertragen wurden. Dabeiwurde häufig nicht berücksichtig (oder zu wenig konsequent), dass ein hoch-dimensionaler Raum sich völlig anders verhält als ein 2/3-dimensionaler Raum.

• Im Folgenden wollen wir das Phänomen des „Fluch der hohen Dimensionen“ näherbetrachten, also das Problem, dass die Indexstrukturen zwar sehr gut in 2/3-dimensionalen Räumen funktionieren, aber in hoch-dimensionalen Räumen komplettversagen. Wir tun dies, indem wir uns zuerst einige Eigenheiten des hoch-dimensionalen Raumes vergegenwärtigen und schliesslich mit einem (einfachen)Kostenmodell belegen, dass NN-Suche in hoch-dimensionalen Räumen nicht effizientsein kann, wenn man hierarchische Strukturen verwendet.

• Annahmen: Zur Vereinfachung der mathematischen Betrachtung nehmen wir imFolgenden an, dass der Raum durch Ω = [0,1]d gegeben ist und dass Datenpunkte undAnfragen uniform im Datenraum verteilt sind.

• Beobachung: Unter diesen Annahmen ist die W‘keit, dass ein Punkt innerhalb einerRegion liegt, gegeben durch das Volumen dieser Region.


1. Eigenheit: Schlechte Intuition für hoch-dimensionale Räume

• Gegeben sei

– Datenraum: Ω = [0,1]d

– Zentrum von Ω : c = (0.5, …, 0.5)

– Punkt p = (0.3, ... , 0.3)

– Kreis um p mit Radius 0.7

• Im 2-dimensionalen Raum (sieheGrafik) deckt der Kreis beinahe denganzen Datenraum ab. Zudem ist esklar, dass das Zentrum c innerhalb desKreises liegt.

• Im hoch-dimensionalen Raum gilt diesnicht mehr! Der Abstand zwischen pund c ist gegeben als: δ = 0.2 sqrt(d).Nur falls δ ≤ 0.7 ist, wird c vom Kreisabgedeckt. Dies ist aber nur fürd < (0.7/0.2)2 = 12.25 der Fall. D.h. inhoch-dimensionalen Räumen ist derKreis zu klein, um c zu überdecken!

Ω = [0,1]d

p0.7

c


2. Eigenheit: Partitionierung in hoch-dim. Räumen nicht möglich

• Gegeben sei


– Nach oben beschränkte Anz. Punkte, z.B. N = 109

• In 2-dimensionalen Räumen kann der Datenraum z.B. partitioniert werden, indemman jede Achse mehrfach teilt (z.B. k-d-Tree, Gridfile, ...). Die entstehendenPartitionen sind recht klein und die räumliche Aufteilung macht Sinn.

• In hoch-dimensionalen Räumen ist dies aber nicht mehr der Fall! Nehmen wir an,dass jede Achse genau einmal geteilt wird (z.B. in der Mitte). Dann können wirfolgende Grössen berechnen:– Anz. Partitionen: p = 2d

– Anz. Punkte/Partition: m = N/2d

d p m

10 103 106

50 1015 10-6

100 1030 10-24

D.h. im hoch-dimensionalen Räumen sind die meisten Partitionen leer. EinePartitionierung macht also keinen Sinn mehr. Um das Problem zu entschärfen, solltennur eine relativ kleine Anzahl Achsen geteilt werden (z.B. 10 Achsen).


3. Eigenheit: Wo liegen die Datenpunkte?

• Gegeben sei


– Ein rechteckiger Bereich mitSeitenlänge s = 0.95 (siehe Grafik)

• In 2-dimensionalen Räumen liegen dieDatenpunkte gleichmässig über denDatenraum verteilt. Bei N=109 Punktenist der Datenraum dicht belegt. Derrechteckige Bereich enthält sehr viele Punkte.

• Im hoch-dimensionalen Räumen ist derBereich fast leer! Das Volumen des Bereichsist gegeben durch sd. Bei d = 100 ist dies gerade mal 0.0059. D.h. 0.59% der Punkteliegen in diesem Bereich. Des weiteren kann man keine Punkte im Zentrum desDatenraums finden. All Punkte liegen in der Nähe einer der Seitenflächen desRaumes. „In der Nähe“ heisst dabei, dass der Abstand zur Aussenfläche kleiner alsε = 0.05 ist. Die W‘keit, dass ein Punkt in der Nähe einer Aussenfläche liegt, istgegeben durch 1 - ( 1-2ε ) d.– für d = 2 ist diese W‘keit 0.19, d.h. 19% der Punkte liegen nahe am Rand

– für d = 100 ist diese W‘keit 1, d.h. alle Punkte liegen jetzt nahe am Rand

s

Ω = [0,1]d

s


4. Eigenheit: Der NN ist in hoch-dimensionalen Räumen weit entfernt

• Gegeben sei


– Nach oben beschränkte Anz.Punkte, z.B. N = 109

– Zentrum von Ω : c = (0.5, …, 0.5)

– Kreis um c mit Radius 0.5

• In einem 2-dimensionalen Raumerwarten wir, dass der NN einesPunktes in unmittelbarer Nähe liegt(d.h. die Distanz ist klein). So würdeder Kreis um c sicher den NN zu centhalten.

• In einem hoch-dimensionalen Raum ist dies aber nicht der Fall! Das Volumen der d-dim. Sphäre geht gegen 0 mit zunehmendem d. Für d = 10 ist das Volumen 0.002, d.h.0.2% der Punkte liegen innerhalb der Sphäre. Für d = 100 ist das Volumen 1.9*10-70,d.h. neben c liegt mit grösster W‘keit kein weiterer Punkt in der Sphäre. Mit anderenWorten, der Kreis um c müsste grösser sein, um den NN zu enthalten resp. dieDistanz von c zu seinem NN ist sehr viel grösser als 0.5!

Ω= [0,1]d

c

0.5


Kostenmodell für NN-Suche

• Auf den folgenden Seiten wollen wir die Kosten für die NN-Suche in hierarchischenStrukturen schätzen. Zu diesem Zweck müssen wir uns erst überlegen, wie gross dieerwartete Distanz zwischen NN und Anfragepunkt ist. Danach müssen wir die Anzahlder Blätter bestimmen, welche während der Suche gelesen wird. Da wir den HS-Algorithmus anwenden, können wir die Anzahl gelesener Blätter relativ leichtabschätzen: gelesen werden müssen genau jene Blätter, welche die NN-Sphäre umden Anfragepunkt schneiden.

• Erwartete NN-Distanz– Die erwartete NN-Distanz ist gegeben als die durchschnittliche Distanz zwischen

einem Anfragepunkt und seinem nächsten Nachbar.– Grundidee der Herleitung:

• Für einen gegeben Anfragepunkt und einen Radius r bestimmt man die W‘keit,dass der NN innerhalb des Kreises um den Punkt mit Radius r liegt.

• Für die Zufallsvariable r definieren diese W‘keiten eine Verteilungsfunktion;der Erwartungswert der Zufallsvariable r ist gerade die erwartete NN-Distanzfür den gegebenen Anfragepunkt

• Die erwartete NN-Distanz für eine beliebigen Punkt im Datenraum ist letzlichder Mittelwert der erwarteten NN-Distanz für alle Punkte im Datenraum.


– Natürlich hängt die erwartete NN-Distanz von der Metrik und der Dimensionalitätdes Raumes ab. Die folgenden Kurven zeigen den Verlauf der NN-Distanz inAbhägnigkeit der Dimensionalität für die Normen L1 , L2 und L∞.


• Kostenmodell– In einem einfachen Kostenmodell werden die Kosten der NN-Suche wie folgt

abgeschätzt:

• CPU-Kosten sind vernachlässigbar im Vergleich zu den IO-Kosten

• IO-Kosten fallen nur beim Besuch eines Blattknotens an, d.h. die innerenKnoten werden im Hauptspeicher gehalten. Das Lesen eines Blattes bewirkteinen „zufälligen“ Zugriff (random access) auf die Harddisk. Dieser kostet mitheutiger Disktechnologie zwischen 5-8ms.

– Um die Performanz eines Baumes zu vergleichen, betrachten wir auch die Kostenfür das sequentielle Durchgehen aller Punkte (sequentieller Scan). Auch hierbeifallen die CPU-Kosten nicht ins Gewicht; die IO-Kosten sind gegeben durch dasLesen aller Vektoren. Heutige Disks haben Datentransferraten zwischen 10 und30 MB/s (RAIDs können sogar noch mehr MB/s übertragen). Die Anzahl zulesender Blöcke ist kleiner als die Anzahl Blätter in einem Baum. Im Durschnitt istnämlich ein Blatt nur zu etwa 60%-80% voll (nach einem split sind es 50%). Sei f(in %) der durchschnittliche Füllgrad und b die Grösse eines Blattes in Bytes. Dannsind die Kosten für NN-Suche mit dem seq. Scan: Tscan ≈ f ⋅ n ⋅ b / (16 MB/s)

– Mit dem HS-Algorihtmus werden bei einer NN-Suche in einem Baum genau jeneBlätter besucht, welche sich mit der NN-Sphäre schneiden. Sei n die totale AnzahlBlätter und v der Prozentsatz der gelesenen Blätter. Dann sind die Kosten für dieNN-Suche im Baum: Tbaum ≈ v ⋅ n ⋅ (7ms + b / (16 MB/s))


– Damit nun der Baum schneller ist als der seq. scan muss gelten:Tbaum < Tscan

Also v < f ⋅ b / (16 MB/s) / (7ms + b / (16 MB/s))

– Die untenstehende Grafik zeigt die oberen Schranken für v (Prozentsatz gelesenerBlätter) als Funktion der Blattgrösse und der Füllrate. D.h. bei vernünftigerBlockgrösse und realistischem Füllgrad sollte v kleiner als 20% sein. In diesemFall ist der Baum aber nur unwesentlich schneller als der Scan. Damit sich derBaum wirklich lohnt für die NN-Suche, sollte v wesentlich kleiner sein, z.B. v <5%.


– Einfache Betrachtung:• Der Baum benutze rechteckige MBRs. Es können aber nur d‘ von d Achsen

geteilt werden. Weiter nehmen wir an, dass die Aufteilung in der Mittevorgenommen wurde. Damit sehen die MBRs der Blattknoten wie in der Grafikunten rechts aus (Achse nach vorne wurde nicht geteilt, die anderen in derMitte).

• Sei lmax der maximale Abstand eines Punktes zu einem Blatt. Aufgrund derMBR-Form der Blätter ist diese Distanz gegeben als: lmax=½ sqrt(d’2)

• Wenn wir nun diese Distanz mit der erwarteten NN-Distanz vergleichen, sostellen wir überraschend fest (siehe Tabelle): lmax ist bei d=100 kleiner als NN-Dist. Mit anderen Worten: jeder Punkt liegtnäher zu diesem Blatt als zu seinem NN. Alsoschneidet die MBR des Blattes auch die NN-Sphäre jedes Anfragepunktes. Das Blatt mussfür jede Anfrage gelesen werden. Oder: für jedeAnfrage muss jedes Blatt besucht werden

Ω = [0,1]d

Blattseite

lmax

d N d‘ lmax NN-dist

40 106 14 1.87 1.8

100 106 15 1.94 3


– Allgemeine Betrachtung:• Wir wollen nun die genaue Anzahl besuchter Blätter berechnen; zudem

betrachten wir nun auch allgemeine MBRs.

• Wir müssen die Anzahl Blätter bestimmen, deren MBRs sich mit der NN-Sphäre eines Anfragepunktes schneiden. Dazu gehen wir wie folgt vor

– Schätzen der erwarteten NN-Distanz (siehe vorherige Grafiken)

– Die NN-Suche kann als Bereichsanfrage („range query“) umformuliertwerden: gesucht sind nun all jene MBRs, welche sich mit der NN-Spähreschneiden.

– Aus der Geometrie (z.B. Legen einer Tangente an zwei Kreise) kennt mandas Verfahren der Minkowski Transformation. Dabei wird die NN-Sphäreauf einen Punkt geschrumpft und alle MBRs um den Radius der NN-Sphäre „aufgeblasen“ (d.h. eine Sphäre mit Radius NN-Dist wird entlangder gesamten Oberfläche der MBRs bewegt. Der Raum, der durch dieseBewegung abgedeckt wird, entspricht gerade der aufgeblasenen MBR).Aus der Bereichsanfrage wurde nun eine Punktanfrage: all jene Blättermüssen besucht werden, deren aufgeblasene MBR den Anfragepunktenthalten.

– Die W‘keit, dass ein Blatt besucht werden muss ist gegeben durch dasVolumen seiner aufgeblasenen MBR, d.h. dem Prozentsatz der Punkte,welche innerhalb der aufgeblasenen MBR liegen.


Transformation im Überblick

NN

Anfragepunkt

range query

point query

NN-dist

NN query

aufgeblasene MBR

NN-Sphäre


• Die Berechnung der Volumen der aufgeblasenen MBRs sei an dieser Stelleausgelassen (Interessierte finden dies unter [Weber:1998]).

• Die folgenden Grafiken zeigen v, den Prozentsatz gelesener Blätter, alsFunktion der Dimensionalität und für verschiedene MBRs (rechteckig,sphärisch; alle anderen Formen können ebenfalls in [Weber:1998]nachgelesen werden). Bei den rechteckigen MBRs repräsentieren „d‘=10“ und„d‘=18“ MBRs, welche entlang d‘ Achsen in der Mitte geteilt wurden.„conservative“ steht für rechteckige MBRs, welche bzgl. ihrer Grösse optimiertwurden (was aber in der Praxis kaum möglich ist).


• Bemerkungen:– Die 20%-Marke, oberhalb derer ein seq. Scan mit Sicherheit besser ist als ein

Baum, wird bereits bei Dimensionalitäten <50 erreicht. Mit anderen Worten, dieVerwendung von Bäumen für die NN-Suche in Bilddatenbanken (d>100) istzwecklos (resp. verlangsamt die Suche im Vergleich zum seq. Scan)

– Für jede hierarchische Struktur (egal welche MBRs, egal wie aufgebaut) gibt eseine Dimensionalität, oberhalb derer die NN-Suche mit einem seq. Scanschneller ist.

– Messungen mit realen Datensätzen (Merkmale aus Bilddatenbanken) habengezeigt, dass der seq. Scan schon bereits ab d=10 schneller sein kann als allebisher besprochenen Verfahren.

– Die NN-Suche in hoch-dimensionalen Räumen hat lineare Komlexität, solange dieAnzahl Punkte nicht exponentiell mit der Anzahl Dimensionen wächst (dies istaber in Datenbanken nicht gegeben). Dies kann man auch mit weiterenmathematischen Modellen zeigen.

– Die Entwicklung der Harddisks zeigt, dass der Datendurchsatz sich stärkerverbessert als die mittlere Zugriffszeit. D.h. die Bäume verlieren mit jeder neuenDiskgeneration weiter an Boden im Vergleich zum seq. Scan.

– Also: Für die Ähnlichkeitssuche in Bilddatenbank sollte man am besten einesequentielle Organisation wählen. Dies ist erstens sehr viel einfacher als ein Baumund zweitens auch wesentlich schneller.


3.4.10 Das Vector Approximation File (VA-File)

• Das Vector Approximation File (VA-File) wurde 1997 an der ETH entwickelt. Das Zieldieser NN-Suchmethode war es, den notwendigen Scan durch die Punktemenge zubeschleunigen. Zu diesem Zweck wurden die Vektoren quantisiert, um die zu lesendeDatenmenge zu reduzieren (bis zu Faktor 8). Trotz des Datenverlustes kann das VA-File den exakten NN zum Anfragepunkt finden. Die Suchzeiten sind in der Regel 4-8mal kleiner als jene des seq. Scan (wiederum ist IO das Hauptproblem; die CPUKosten sind im Vergleich vernachlässigbar).

• In diesem Kapitel wollen wir den Aufbau und die Arbeitsweise des VA-Files genauerstudieren.

• Aufbau:– Das VA-File besteht aus zwei Dateien. Die eine Datei enthält alle Vektoren (resp.

Datenpunkte), die andere enthält die Approximationen der Vektoren. Wichtig ist,dass die Ordnung der beiden Dateien identisch ist, d.h. der Eintrag an der i-tenPosition im Approximationsfile gehört zum i-ten Vektor im Vektorfile.

– Ein Eintrag im Vektorfile setzt sich zusammen aus einer OID (4 bytes) und den dKomponenten des Vektors (jeweils 4 Bytes). Die OID wird von derdarüberliegende Applikation benötigt, um die Vektoren in Relation zu denObjekten (z.B. Bilder) zu bringen.

– Ein Eintrag im Approximationsfile ist ein Bitstring mit einer bestimmten Länge(durch 2 Bytes teilbar). Der genaue Aufbau wird in Kürze beschrieben.


– Headers: Jede Datei speichert in ihrem Header wichtige Informationen zu denDateien. Z.B. die Anzahl Dimensionen, die Länge der Approximationen, die AnzahlEinträge, etc. (siehe nachfolgende Grafik). Ein Besonderheit ist der Support für dieinkrementelle Berechnung der Mittelwerte und Standardabweichungen dereinzelnen Komponenten (xsum[i],x2sum[i]im Header der Vektordatei). Somitlassen sich die Gewichte für die einzelnen Dimensionen leicht berechnen.

• Operationen:– Einfügen: In der Regel wird ein neuer Punkt am Ende eingefügt. Falls aber zuvor

Datenpunkte gelöscht wurden, so können die so entstanden Löcher gefüllt werden(allerdings sollte diese Aufgabe von einer globalen Instanz ausgeführt werden,damit VA-Files des gleichen Datensatzes auf verschiedenen Rechner die gleicheOrdnung haben; dies ist vor allem für die Parallelisierung wichtig). Jedes Einfügenhat eine Änderung des Vektors- und Approximationsfile zur Folge. Das Berechnender Approximation werden wir gleich näher betrachten.

– Update: Die Einträge in beiden Dateien werden entsprechend angepasst.

– Delete: Die Einträge an der entsprechenden Postion in den Dateien werdengelöscht, d.h. auf einen speziellen NULL-Wert gesetzt. Die so entstehendenLöcher können mit späteren Einfügeoperationen wieder gefüllt werden.


Übersicht

Header

01010110001

Header

1873 .21 .63 .13 .07 .94 .82

5136 .62 .41 .55 .23 .94 .34 00110101101

magic number(31415926)

num vectors(N)

num dimensions(d)

max position(maxPos)

pos 0

pos 21

pos 0

pos 21

magic number(27182817)

statistical info.on the vectors(xsum[i],x2sum[i])

num bitsper dimension

(b[i])

partitioning pointsalong eachdimension

(m[i] [j])

num vectors inslices along

each dimension(n[i] [j])

vector file approximation file

VA-File

num changes(nChanges)


• Berechung der Approximationen– Die Vektoren werden mit einem Quantisierungsschema komprimiert. Ein (nicht

notwendigerweise gleichförmiges) Gitter teilt den Datenraum in rechteckigePartitionen auf. Entlang jeder Achse werden 2bi Scheiben gebildet, wobei bi einerAnzahl Bits entspricht (für jede Dimension kann eine andere Anzahl gewähltwerden). Die einzelnen Scheiben können nun mit bi Bits durchnummeriert werden(siehe Grafik). Ebenso können für die einzelnen Partitionen Bitstrings gebildetwerden: sie setzen sich aus den Bitstrings der d Scheiben der Partitionzusammen. In der neben-stehenden Grafik sind dieScheiben durch Markierungs-punkte begrenzt. Z.B. istdie erste Scheibe in x-Richtung begrenzt durchm[0,0] und m[0,1]. DerDatenraum wird durch diePunkte aufgespannt, d.h.durch deren minimale undmaximale Werte entlangder d Achsen (z.B. m[1,0]und m[1,4] für die y-Achse)

00 111001

data space

approximations

1 0.6 0.8

2 0.0 1.0

3 1.0 0.0

4 0.3 0.4

5 0.5 0.1

6 0.3 0.6

vectors

p5

p4

p6

p2

p1

p3

10 11

00 11

11 00

01 01

10 00

01 10x

y

m[0,0]

m[0,1]

m[0,2]

m[0,3]

m[0,4]

m[1,0]

m[1,1]

m[1,2]

m[1,3]

m[1,4]

00

01

10

11

Date post:	27-Jun-2020
Category:	Documents
Upload:	others
View:	3 times
Download:	0 times

3.3 Suchen nach Bildern · Multimedia Retrieval - SS02 Kap.3-57 3.3 Suchen nach Bildern • Die...

Documents