12
The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja Kämpfe Zusammenfassung Diese Ausarbeitung beschäftigt sich mit der Earth Mover’s Distance als einem Abstandsmaß auf Signaturen zur Suche in Bilddatenbanken. Zur Veranschaulichung wird die Multidimensionale–Skalierungs–Technik Sam- mon Mapping eingeführt und gezeigt, dass eine Kombination beider Ver- fahren gute Ergebnisse liefert. 1 Motivation Große Bildbestände nach ähnlichen Bildern zu durchforsten ist für einen mensch- lichen Experten langweilig und zeitaufwändig. Teile dieser Aufgabe können dem sog. Automatic Image Database Retrieval überlassen werden. Hier wer- den unter anderem automatische Verfahren zum Auffinden von ähnlichen Bil- dern benötigt, um eine Suchanfrage (beispielsweise gegeben durch das Bild eines Hürdenläufers, Abb. 1) mit den Bildern in der Datenbank zu vergleichen. Die ähnlichsten Bilder werden dann dem Nutzer des Systems als Ergebnis sei- ner Suchanfrage vorgelegt. Im folgenden Abschnitt wird zunächst eine grobe Einführung in die Pro- blematik des maschinellen Vergleichs von Bildern gegeben. Abschnitt 3 führt Histogramme als probates Mittel zur Darstellung von Merkmalen eines Bildes ein, welche jedoch einige Schwächen haben, die in Abschnitt 4 durch die Ein- führung von Signaturen behoben werden. Abschnitt 5 führt auf diesen Signa- turen die Earth Mover’s Distance ein, welche dann in Abschnitt 6 verwendet wird. Abschnitt 7 schließlich zeigt Ergebnisse, welche mit einem Testverfahren erzeugt wurden. Diese Arbeit beruht zu großen Teilen auf den Veröffentlichungen von Y. Rubner, C. Tomasi, und L. J. Guibas. Für nähere Informationen siehe daher [RGT97] und [RTG00] 1 . 1 erwähnenswert ist auch die Internetseite http://robotics.stanford.edu/ rub- ner/emd/default.htm 1

The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

  • Upload
    others

  • View
    9

  • Download
    0

Embed Size (px)

Citation preview

Page 1: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

The Earth Mover’s Distance

Till BovermannTechnische FakultätUniversität Bielefeld

BILDDATENBANKEN–Seminar SS 03Tanja Kämpfe

Zusammenfassung

Diese Ausarbeitung beschäftigt sich mit der Earth Mover’s Distance alseinem Abstandsmaß auf Signaturen zur Suche in Bilddatenbanken. ZurVeranschaulichung wird die Multidimensionale–Skalierungs–Technik Sam-mon Mapping eingeführt und gezeigt, dass eine Kombination beider Ver-fahren gute Ergebnisse liefert.

1 Motivation

Große Bildbestände nach ähnlichen Bildern zu durchforsten ist für einen mensch-lichen Experten langweilig und zeitaufwändig. Teile dieser Aufgabe könnendem sog. Automatic Image Database Retrieval überlassen werden. Hier wer-den unter anderem automatische Verfahren zum Auffinden von ähnlichen Bil-dern benötigt, um eine Suchanfrage (beispielsweise gegeben durch das Bildeines Hürdenläufers, Abb. 1) mit den Bildern in der Datenbank zu vergleichen.Die ähnlichsten Bilder werden dann dem Nutzer des Systems als Ergebnis sei-ner Suchanfrage vorgelegt.

Im folgenden Abschnitt wird zunächst eine grobe Einführung in die Pro-blematik des maschinellen Vergleichs von Bildern gegeben. Abschnitt 3 führtHistogramme als probates Mittel zur Darstellung von Merkmalen eines Bildesein, welche jedoch einige Schwächen haben, die in Abschnitt 4 durch die Ein-führung von Signaturen behoben werden. Abschnitt 5 führt auf diesen Signa-turen die Earth Mover’s Distance ein, welche dann in Abschnitt 6 verwendetwird. Abschnitt 7 schließlich zeigt Ergebnisse, welche mit einem Testverfahrenerzeugt wurden.

Diese Arbeit beruht zu großen Teilen auf den Veröffentlichungen von Y.Rubner, C. Tomasi, und L. J. Guibas. Für nähere Informationen siehe daher[RGT97] und [RTG00]1.

1erwähnenswert ist auch die Internetseite http://robotics.stanford.edu/ rub-ner/emd/default.htm

1

Page 2: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

2 Ähnlichkeit von Bildern

Die Ähnlichkeit zweier Bilder lässt sich nur schwer in einen Formalismus pres-sen; naive Ansätze wie der euklidische Abstand zweier Bildvektoren sind nachmenschlichen Kriterien ungeeignet. Hier gilt es andere Verfahren zu entwickeln,für die der Begriff der Ähnlichkeit zweier Bilder erst differenziert werden muss.

Abbildung 1: Ähnlichkeiten zwischen Bildern

Grundsätzlich unterscheidet man zwischen semantischer, und äußerer Ähn-lichkeit zweier Bilder. Während erstere sich auf den Bildinhalt (beispielsweiseden Hürdenläufer auf Abb. 1) bezieht, ist letztere eher auf technische Aspek-te des Bildes ausgerichtet, also näher an der physikalischen Form des Bildes.Der Übergang zwischen beiden ist, wie man leicht einsieht, fliessend. Da se-mantische Ähnlichkeit mit heutigem Wissensstand nicht zu erreichen ist, ent-wickelt man die äußere Ähnlichkeit weiter, um mit diesem Ansatz allmählich andie semantische Ähnlichkeit zu reichen. Um dabei gute Resultate zu erzielen,werden aus den Bildern Merkmale extrahiert, welche deren Eigenschaften sogewählt sind, dass sie wichtige Komponenten eines Bildes, wie z.B. Farb– oderTexturinformation darstellen.

3 Histogramme

Als Datenstruktur für die im vorherigen Abschnitt dargestellten Merkmale be-dient man sich häufig sog. multidimensionaler Histogramme:

{hi ∈ R+}, i ∈ Zd (1)

Sie lassen sich interpretieren als diskrete Verteilung von Datenpunkten imjeweiligen Merkmalsraum. Abbildung 2 zeigt eine qualitative Darstellung einessolchen zweidimensionalen Histogramms.

Mögliche Histogramme sind z.B. Graustufen– oder RGB–Histogramme, diein den Abbildungen 3 und 4 exemplarisch vorgestellt werden.

2

Page 3: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Abbildung 2: Qualitative Darstellung eines zweidimensionalen Histogramms.Die Säulen repräsentieren die hi, während die Felder, in denen sie stehen diefür die berechneten Abschnitte relevanten Flächen kennzeichnen.

Abbildung 3: Bild eines Mondausschnittes und zugehöriges Graustufenhisto-gramm. Für nähere Informationen s. Tabelle 1.

3

Page 4: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Graustufenhistogramm RGB-HistogrammIndex i 0 . . . 255 ?Dimension d 1 3Anzahl Pixel mit Graustufe i hi s. Abbildungen

Tabelle 1: Details der Histogrammbeispiele aus Abb.3 und 4

Abbildung 4: Bild von Franz Marc: Blue Horses und zugehöriges RGB-Histogramm (Paul Heckbert, 1983). Für nähere Informationen s. Tabelle 1.

4

Page 5: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

3.1 Abstandsmaße in Histogrammen

Abstandsmaße, die auf Histogrammen definiert sind, lassen sich in zwei Ka-tegorien unterteilen: Während Bin-by-Bin–Maße nur den Vergleich zwischenFeldern gleichen Indizes berücksichtigen, werden in Cross-Bin–Verfahren auchNachbarfelder bis hin zu allen Feldern für den Abstand eines jeden Bin’s miteinbezogen(vgl. Abb.5).

Abbildung 5: Qualitativer Unterschied von Bin-by-Bin– und cross Bin–Maßen

Exemplarisch seien hier jeweils ein Bin-by-Bin– und ein Cross-Bin–Maßaufgeführt. Seien H,K Histogramme.

Minkowsky

dLr (H,K) =

(∑i

|hi − ki|r)

(2)

Hier ist leicht zu sehen, dass nur Vergleiche gleichen Indizes den Abstandbeeinflussen.

quadratische Form

dA(H,K) =√

(h− k)τ A (h− k), (3)

mit h, k Vektoren, die alle Einträge in H,K auflisten. Die Cross-Bin Infor-mation steckt hier in der Matrix

A = {aij = 1− dij/dmax | dij = ‖i− j‖}

4 Signaturen

Eine unangenehme Eigenschaft von Histogrammen ist es, den d–dimensionalenMerkmalsraum in regelmäßige Stücke aufzuteilen. Dadurch kommt es beinicht-trivialen Datenverteilungen zu mindestens einem der folgenden Proble-me:

5

Page 6: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Bei einer feinen Unterteilung des Raumes wird der Anteil von in eine Zelle fal-lenden Datenpunkte sehr klein; Dadurch entstehen Regionen, in denenkeine Zelle einen nennenswerten Eintrag erhält (sog. sparse Regionen).Obwohl diese uninteressant für die weitere Verarbeitung sind, da sie kei-nerlei Information enthalten, müssen sie wie alle anderen Regionen voll-ständig untersucht werden.

Unterteilt man dagegen den Raum in wenige große Parzellen, besteht dieGefahr, dass viele informationstragende Teilgebiete zu einem großen zu-sammengefasst werden. Informationen über ihren Inhalt gehen dadurchverloren.

Eine Lösung dieses Problems besteht darin, den Raum nicht a priori in re-gelmäßige Teilräume zu unterteilen, sondern die Parzellierung dynamisch andie jeweilige Datenverteilung anzupassen, so dass interessante Gebiete mitviel Information kleinteiliger, Gebiete mit wenig Information grober repräsen-tiert werden. Hierzu bieten sich verschiedene Clusterverfahren an, die z.B. in[Rip96] beispielhaft aufgeführt sind.

Zur Repräsentation dieser Daten muss die Datenstruktur für jede Parzelleum ihren Mittelpunkt erweitert werden. Die so entstehende Menge

S ={sj = (mj , wmj )

}j∈ S (4)

heißt dann Signatur, wobeimj den Schwerpunkt des (Merkmals)Clusters, undwmj den Anteil der Pixel, die zu Cluster j gehören bezeichnet.

Daraus ergibt sich sofort, dass die Menge der Histogramme H als echte Teil-menge der Menge der Signaturen S betrachtet werden kann, wenn die Histo-grammelemente um ihre jeweilige Position erweitert werden.

4.1 Abstandsmaße in Signaturen

Wie auch auf Histogrammen, können auf Signaturen Abstandsmaße definiertwerden. Ein solches —die sogenannte Earth Mover’s Distance— wird im fol-genden Abschnitt vorgestellt.

5 Earth Mover’s Distance

Die Earth Mover’s Distance (kurz EMD) ist ein durch das hinlänglich bekann-te Transportproblem motiviertes Abstandsmaß auf Signaturen. Es wird ange-nommen, dass die zwei Signaturen P = {(p1, wp1), . . . (pm, wpm)} und Q ={(q1, wq1), . . . (qn, wqn)}, deren Abstand gemessen werden soll, Größen einesErdbewegungsvorganges repräsentieren, wobei P die Position der Hügel undderen Volumen, Q dagegen die Position der Löcher in die die Erde gefüllt wer-den soll darstellen. Das Problem besteht darin, die vorhandene Erde möglichst

6

Page 7: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Abbildung 6: Qualitative Darstellung einer zweidimensionalen Signatur. DieSäulen repräsentieren die wmj , ihre Position im Raum ist durch mj festgelegt.Die Felder bezeichnen die für die Berechnung relevanten Flächen. Man be-achte die Verwandschaft dieser Struktur zum Histogramm (vgl.Abb. 1).

effektiv auf die einzelnen Löcher zu verteilen, so dass eine Ebene entsteht(siehe Abb. 7). Der Aufwand wird hierbei durch transportierte Masse pro Weggemessen.

Formalisiert man das Problem, so ergibt sich folgendes lineare Optimie-rungsproblem, welches beispielsweise mit Hilfe des Simplexalgorithmus gelößtwerden kann 2:

SeiP,Q SignaturenD = [dij ] Distanzmatrix der SignaturelementeF Arbeit

Minimiere bzgl. F:

E(P,Q,D) =∑i,j

dijfij (5)

2näheres s. Vorlesung Optimierungsmethoden der Informatik

7

Page 8: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Abbildung 7: Bei der EMD soll die Signatur P , dargestellt als Erdhügel mög-lichst effizient in Q überführt werden.

unter Nebenbedingungen

fij ≥ 0 (6)∑j

fij ≤ wpi (7)

∑i

fij ≤ wqj (8)

∑i,j

fij = min

∑i

wpi ,∑j

wqj

. (9)

(6) stellt dabei sicher, dass nur Erde von P nach Q bewegt wird, (7) und (8)dass nur soviel Erde bewegt wird, wie vorhanden ist. (9) schließlich verlangt,dass alle vorhandene Erde wirklich verschoben wird. Der Wert der letztenBedingung wird auch total flow genannt.

Die EMD ist dann definiert als

EMD(P,Q) =

(1∑i,j fij

) ∑i,j

dijfij (10)

Der zu E zusätzlich hinzugekommende Faktor dient der Normierung, damitauch Signaturen unterschiedlicher Größe miteinander verglichen werden kön-nen. Besitzen P und Q die gleiche Anzahl von Elementen, genügt die EMDden Eigenschaften einer Metrik.3

3Definition z.B. in [BSMM00]

8

Page 9: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

6 Anwendung

Eine Anwendung des Abstandsmaßes besteht darin, die berechneten Abstän-de eines Datensatzes im möglicherweise hochdimensionalen Merkmalsraumauf einen zwei– bzw. dreidimensionalen Bildraum abzubilden, um ihn dann vi-sualisieren zu können.

Hierzu bieten sich Verfahren aus dem Bereich des multidimensionalen Sca-lierens (kurz MDS) an. Nachfolgend wird ein solches Standartverfahren an dieEMD angepasst, und Bildbeispiele gezeigt.

6.1 Sammon Mapping

Um eine möglichst abstandstreue Dimensionsreduktion eines hochdimensio-nalen Datensatzes zu finden, versucht man beim Sammon Mapping die Sum-me der quadratischen Abstände zwischen den Abständen von Elementen desDefinitions– und Zielraumes möglichst klein zu halten. Es wird also eine Funk-tion

f : Sd → Rk , k � d (11)

gesucht, welche den quadratischen Abstand

E({yi}) =∑i,j

(Dij − dij)2

Dij, (12)

Dij = EMD(P,Q)dij = ‖f(P )− f(Q)‖2

minimiert. Die unterschiedlichen Abstandsmaße sind hier so gewählt, dass dasfür das jeweilige Problem beste verwendet wird; für den Abstand zwischen denSignaturen also die intuitive EMD, für die visuelle Darstellung der euklidsche(L2–)Abstand.

7 Ergebnisse

Um vergleichbare Ergebnisse zu erhalten, muss zunächst ein geeignetes Ver-fahren zur Gewinnung von Queries und zugehörigen Klassen generiert wer-den. Dazu werden aus einer 20 000 Bilder enthaltenen Datenbank 94 zufälligausgewählt, welche jeweils eine Klasse repräsentieren. Aus jedem Bild wer-den dann durch wahlloses Ziehen einer Teilmenge der Pixel 16 Queries erstellt,welche wiederum durch eine Merkmalsextraktion in Signaturen umgewandeltwerden. Dadurch entstehen 1504 Query–Signaturen. Sie werden mittels EMDmit den Bildern aus der Datenbank verglichen. Dadurch entsteht ein NearestNeighbour Klassifikator.

9

Page 10: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Abbildung 8: Precision-Recall–Diagramm des im Text beschriebenen Verfah-rens.

Im in [RTG00] beschriebenen Experiment wurde ein Farbinformationsmerk-mal ermittelt. Die hierbei ermittelten Ergebnisse sind in Abbildung 8 als Precision/Recall–Werte im Vergleich zu anderen Verfahren dargestellt.

Ausserdem sind in den Abbildungen 9 und 10 exemplarische Ergebnissezweier Datenbankanfragen, die mit dem oben beschriebenen Verfahren aufzwei Dimensionen abgebildet wurden dargestellt. Interessant ist hier der Farb-verlauf der Bilder, die in Abbildung 9 zu sehen sind, aber auch die Clusterungder kleineren Datenmenge in Abbildung 10. Wenn der Nutzer weiß, welchesMerkmal verwendet wurde, kann er die Anordnung der Bilder sehr gut nach-vollziehen.

A Precision, Recall

Die Standardmasse für Information Retrieval sind Precision und Recall. Ange-nommen, dass:

Rr Menge der Bilder, die das System auf eine spezifische (13)

Anfrage hin zurückliefert,

Rt Menge der für eine Anfrage relevanten Bilder, (14)

Rr∩t Menge der zurückgelieferten, relevanten Bilder (15)

10

Page 11: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

Abbildung 9: Durch das im Text beschriebene Verfahren berechnete Karte von500 Bildern. Man beachte den Farbverlauf der Bilder von links unten nachrechts oben.

Abbildung 10: Durch das im Text beschriebene Verfahren berechnete Kartevon 10 durch eine Suchanfrage nach Bildern mit 20% Blau– und 80% Don’t-care–Anteil. Es entsteht eine deutliche Clusterung von Bildern mit ähnlichenMotiven.

11

Page 12: The Earth Mover’s Distance - Technische Fakultät · The Earth Mover’s Distance Till Bovermann Technische Fakultät Universität Bielefeld BILDDATENBANKEN–Seminar SS 03 Tanja

sind. Dann sind Precision und Recall folgendermaßen definiert:4

precision =Rr∩tRr

(16)

recall =Rr∩tRt

(17)

Literatur

[Bis95] C. M. Bishop. Neural networks for pattern recognition. Oxford, NewYork: Clarendon Press; Oxford University Press, 1995.

[BSMM00] I. N. Bronstein, K. A. Semendjajew, G. Musiol, and H. Mühlig. Ta-schenbuch der Mathematik. 5. Verlag Harry Deutsch, 2000. ISBN3-8171-2005-2.

[RGT97] Y. Rubner, L. J. Guibas, and C. Tomasi. The earth mover’s distan-ce, multi-dimensional scaling, and color-based image retrieval. InProc. of the APRA Image Understanding Workshop, pages 661–668, May 1997.

[Rip96] S. Ripley. Pattern Recognition and Neural Networks. CambridgeUniversity Press, 1996. ISBN: 0-521-46086-7.

[RTG00] Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover’s distanceas a metric for image retrieval. International Journal of ComputerVision, 40(2):99–121, 2000.

4aus: http://issco-www.unige.ch/ewg95/

12