Unter einer Symmetrie (von altgriech. σύν syn „zusammen“, μέτρον métron „Maß“) versteht man in der Physik die Eigenschaften eines Systems, nach einer bestimmten Änderung (Transformation, insbesondere Koordinatentransformationen) unverändert zu bleiben (invariant zu sein). — Wikipedia)
Symmetrie bezeichnet eine spezielle Form von Redundanz in einem Phänomen oder Modell: Betrachten wir ein symmetrisches geometrisches Objekt wie z.B. ein Quadrat: Dieses Objekt ist kein beliebig geformtes Viereck. Wir können die vier Eckpunkte nicht beliebig festlegen. Wenn wir zwei Punkte bestimmt haben, gibt es nur noch zwei Möglichkeiten, diese zu einem Quadrat zu ergänzen. Vom geometrischen Standpunkt aus gesehen, hat ein Quadrat Symmetrien - wir können es z.B. um 90° drehen, oder spiegeln, und es sieht wieder genauso aus wie zuvor. Vom Standpunkt der Informationstheorie ist die Beschreibung eines Vierecks durch vier Eckpunkte redundant: Nicht alle Kombinationen sind erlaubt; einige der Koordinaten könnten aus anderen berechnet werden, wobei aber nicht fest steht, welche abhängig und welche unabhängig sind. In diesem Sinne hat die Repräsentation eines Vierecks durch vier Punkte eine Symmetrie. Mathematisch beschreibt man Symmetrie in Repräsentationen durch Gruppen von Symmetrietransformationen. Zunächst definieren wir Transformation, die das Objekt nicht ändern. (Bei dem Viereck wären dies: Drehung um den Mittelpunkt um 90° oder Spiegelung um die Mitte horizontal/vertikal). Jede dieser Transformationen erzeugt wieder eine Repräsentation des exakt gleichen Vierecks. Man erhält eine algebraisch abgeschlossene Struktur, die die Eigenschaften einer Gruppe erfüllt:
Die Hintereinanderausführung ist Assoziativ (das ist immer so: \(f\circ(g\circ h) = (f\circ g) \circ h\) gilt per Definition für alle Transformationen, die man sich vorstellen kann).
Außerdem sind alle Transformationen invertierbar (wir haben ja nichts verändert, daher auch keine Information zerstört).
Die Abgeschlossenheit (man kann die Operationen immer wieder anwenden) folgt aus der Tatsache, dass die Form sich ja nicht geändert hat.
In dem Beispiel mit dem Viereck, repräsentiert als vier Punkte \(\mathbf{x}_1,...,\mathbf{x}_4 \in \mathbf{R}^2\), gibt es immer mehrere verschiedene Listen von Punkten, die das gleiche Viereck repräsentieren. Wenn wir alle gleichen Objekte als dasselbe ansehen, erzeugen wir Äquivalenzklassen. Man sagt hier auch, dass wir die Gleichheit „modulo“ der Gruppe von Transformationen auffassen, die die Form nicht ändern. Symmetrie ist ein fundamentales Konzept in der Mathematik (Gruppen tauchen überall auf, und jede Gruppe beschreibt eine Symmetrie - mehr dazu in der Vorlesung!). Auch in den Naturwissenschaften (vor allem in der Physik) ist Symmetrie essentiell (auch dazu konkrete Beispiele in der Vorlesung). Auch in der Informatik haben wir es oft mit Symmetrien zu tun, denken aber in der Regel nicht darüber in dem hier beschriebenen Sinne nach. Wann immer zwei verschiedene Datenstrukturen oder zwei verschiedene Programme wörtlich oder sinngemäß die gleichen Daten repräsentieren (bzw. den gleiche Vorgang), so haben wir eine symmetrische Beschreibung gefunden (man kann zwischen den Varianten ja ohne semantische Änderung hin- und herwechseln). All dies wollen wir uns auf dem Übungszettel genauer ansehen. Im Folgenden noch ein paar mehr Beispiele:
Gegeben sei ein herkömmliches Schachbrett (\(8\cdot 8\) Felder, die eine Hälfte der Felder sind schwarz, die andere weiß) und \(32\) (Domino-)Steine, wobei jeder genau so groß ist wie zwei nebeneinanderliegende Schachbrettfelder. Die Aufgabe die \(32\) Steine auf das Schachbrett zu legen, sodass alle Felder von genau einem Stein belegt sind ist leicht zu lösen (siehe mittleres Bild). Aufgabe: Nun stellen wir uns vor, das linke obere Feld und das linke untere Feld seien durch Schachfiguren belegt (siehe rechtes Bild). Können Sie die \(31\) Dominosteine (einen müssen wir natürlich entfernen) so auf die \(62\) unbesetzten Felder positionieren, dass wieder jedes Feld von genau einem Stein belegt ist? Regel: Nicht sägen. Die Steine sind geliehen und müssen daher wieder unbeschadet zurückgegeben werden können. ;)
Die Aufgabe ist nicht lösbar. Der Grund dafür ist, dass eine wichtige abstrakte Symmetrie der Aufgabe verletzt wurde. Nämlich die des Verhältnisses der Anzahl der schwarzen Felder gegenüber der Anzahl der weißen Felder. Jeder Dominostein muss zwei aneinander grenzende Felder belegen, also automatisch ein schwarzes und ein weißes. Da das Feld oben links, sowie das Feld unten rechts jeweils weiß ist, gibt es nur noch \(30\) weiße Felder und \(32\) schwarze Felder. Dies kann nicht erfüllt werden.
Bei dem oben genannten Schachrätsel wäre dies das Verhältnis der Felder.
Beim Lösen des Rubics-Cubes erleichtert man sich die Suche nach einer Lösung (jede Seite besteht aus genau einer Farbe) erheblich, indem man sich klar macht, welche Drehungen den Würfel bis auf ein Detail unbeschadet lassen. Ein Algorithmus, der die Brute-Force-Methode, also das Ausprobieren aller Drehungen, bis der Würfel gelöst ist, verwendet, kann nicht in absehbarer Zeit terminieren; es existieren \[
43.252.003.274.489.856.000 \approx 4{,}3 \cdot 10^{19}
\] Stellungen des Würfels. Die Rechnung dafür ist unter diesem Link.
Gegeben sei eine Fotografie mit klaren sich wiederholenden Strukturen und Kanten, wie etwa eines dieser Kollektion.Das automatische Finden der sich wiederholenden Strukturen (z.B. Fenster) unter Berücksichtigung von kleineren Variationen (mit oder ohne Blumenkasten) und perspektivischen Unterschieden enthält die Idee, die Symmetriegruppe des Bildes zu erfassen.
Eine verwandte Aufgabe der Informatik / Computervision ist die Erkennung und von Objekten. Nehmen wir an, eine Gruppe von Menschen wird mit einem 3D-Scanner erfasst. Stellen Sie sich nun vor, Ihre Aufgabe wäre es, nacheinander aufgenommene 3D Scans den Personen zuzuordnen. Da die Szene in jedem Bild komplett verschieden sein kann, müssen Sie vorher die Symmetrien aller gültigen Verformungen (z.B. die Bewegungen von Kopf, Armen und Beinen) definieren, die ein und derselbe Mensch aufweisen (ertragen?) kann. Wenn man diese verstanden hat, kann man auch die Objekte erkennen (auch wenn die Geometrie jedes mal anders aussieht; mit exakter Gleichheit kann man sie nicht erkennen).
Generell befassen sich jedoch viele Probleme der Informatik mit dem Finden oder Ausnutzen von Symmetrien; das Finden von Cliquen im Graphen, RSA-Verschlüsselung und das SAT-Problem kann man durchaus auch als Manifestation dessen ansehen.
Das Verstehen von Symmetrien in Daten ist wichtig, manchmal möchte man jedoch auch das Wissen nutzen um diese zu generieren. Eventuell haben Sie etwas derartiges bereits in prozedural generierten Computerspiel-Welten gesehen. Ein Beispiel dazu wäre etwa diese Stadt hier. Hier ein Video mit etwas mehr Erklärung dazu.
Take-Home-Message
Erkennung und Generierung von visuellen aber auch abstrakten Symmetrien ist eines der zentralen Themen der Informatik. Das alles schauen wir uns (zumindest vereinfacht) auf diesem Übungsblatt an.
Aufgabe 1: Symmetriegruppen, Erzeugendensysteme und Kristalle
Bewertung: 30 Punkte
Ein Bild mit einer kristallographischen Symmetriestruktur (Quelle: Wikimedia, nicht computergeneriert)
Aufgabe Als erstes Versuchen wir uns an einer einfachen generierenden Struktur. Im Folgenden wollen wir ein Malprogramm schreiben, in dem wir mit der Maus malen können, und das Programm immer einen Kristall anzeigt, also alle Pixel symmetrisch kopiert. Das Ergebnis könnte in etwa so aussehen.
In dieser Aufgabe bauen wir zweidimensionale Kristalle. Ein Kristall ist eine Struktur, in der ein einzelnes Element immer wieder als Kopie vorkommt. Der Kristall wird erzeugt, indem man einige Transformationen definiert, die auf ein Objekt wirken. Danach lässt man alle möglichen Kombinationen wirken. In 2D geschieht das immer indem man zwei verschiedene Translationen (Verschiebungen, nicht in die gleiche Richtung!) definiert, die man in allen Kombinationen wiederholt. Dies erzeugt ein Gitter in der 2D Ebene. Zusätzlich kann man, je nach Gitter, weitere Symmetrien einbauen: z.B. kann ein Gitter, das einen 90° Winkel zwischen den Translationsvektoren hat, weitere Spiegelsymmetrien aufweisen (bei krummen Winkeln ist das schwieriger, aber möglich). Sind die Zellen des Gitters quadratisch, ist eine 90° Drehsymmetrie (auch zusätzlich) möglich; bei einem 60° Winkel ergeben sich Drehungen um bis zu \(6\times 60^\circ\). Ein Beispiel für einen Kristall sieht man in der Abbildung am Ende der Aufgabe. Etwas Mathematik Schauen wir uns das ganze formal an: \(E(2)\) ist die Gruppe aller Euklidischen Isometrien. Auf deutsch: Alle starren Transformationen der 2D Ebene, also solche, die Abstände zwischen Punkten geometrischer Objekte nicht ändern. Diese Transformationen sind genau durch (alle) Kombinationen von Translationen, Rotationen und Spiegelungen gegeben. Die Untergruppe der reinen Translationen ist kommutativ; sobald man Rotationen oder Spiegelungen hinzunimmt, ist dem nicht mehr so. Wir betrachten nun Untergruppen von \(E(2)\), die Kristallgitter erzeugen. Man erzeugt eine Gruppe, indem man (ähnlich, aber nicht genauso wie bei einer Basis) Generatortransformationen (Basiselemente, sozusagen) angibt, die man dann in allen denkbaren Reihenfolgen hintereinander ausführt. In Formeln benutzt man die \(\langle ... \rangle\)- Notation: \[
\langle g_1,g_2,...,g_n \rangle := \{g_{i_1}^{j_1} \circ g_{i_2}^{j_2} \circ \cdots \circ g_{i_k}^{j_k} | i_1,...,i_n \in \{1,...,n\}, j_1,...,j_n \in \mathbb{Z} \}
\] (Mit anderen Worten, enthält diese Menge alle Kombinationen der Gruppenoperationen \(g_1,\dots g_n\).) Einen 2D-Kristall erzeugt man, indem man zwei nicht-kollineare Translationen als Generatoren verwendet. Zusätzlich kann man solche Rotationen und Spiegelungen hinzunehmen, die das von den beiden Translationen erzeugte Gitter wieder genau auf sich selbst abbilden (hier muss man ein bisschen probieren, oder den Wikipedia-Artikel über Wallpaper-Groups lesen).
Teilaufgaben zur Hilfestellung
Schreiben Sie ein Zeichenprogramm, mit dem man auf einem Bitmapbild oder alternativ als Vektorgraphik mit der Maus in verschiedenen Farben malen kann.
Ergänzen Sie Ihr Programm so, dass automatisch alle symmetrischen Kopien mitgemalt werden. Transformieren Sie dazu den Punkt, den man mit der Maus bemalt so, dass alle symmetrischen Kopien entstehen. Testen Sie dies an verschiedenen Symmetriegruppen:
Rotationsgruppen um \(360^\circ / k\) für ein \(k \in \mathbb{N}^{\ge1}\)
Transformationsgruppen mit zwei translatorischen Generatoren
Eine kristallographische Gruppe, die zwei translatorische mit einem kompatiblen rotatorischen und/oder Spiegelungsgenerator kombiniert. Suchen Sie sich ein schönes Beispiel aus.
Theorie: Ist es möglich Skalierungen einzubauen? Was muss die kristallographische Struktur für Eigenschaften haben? Denken Sie zum Beispiel an die Koch-Kurve.
In der letzten Aufgabe haben wir Symmetrien erzeugt. In dieser Aufgabe möchten wir die Symmetrien eines Bildes erkennen. Abstrakt gesprochen werden wir die Symmetriegruppe vorgeben und testen, welche Gruppenelemente für Teile des Bildes zutreffen.
Das Ziel dieser Aufgabe ist es, die ähnlichen Teile eines Bildes automatisch zu erkennen.Entwickeln Sie einen Algorithmus, der automatisch (anhand gegebener Symmetrieeigenschaften) bestimmt, welches die wiederholenden Elemente im Datensatz sind. Ein (eher) einfaches Beispiel sind hierbei Hausfassaden. Das schöne an diesen ist, dass die Fenster (als Symmetrische Objekte) auf einem regelmäßigen Gitter auftreten. Unser Ziel is es das Bild (links) einzugeben und die symmetrischen (im Bild rechts eingefärbten) Teile automatisch zu ermitteln.
Segmentiertes Bild der selben Hausfassade. Die Farbe gibt an wo ähnliche Bildteile im Foto zu finden sind. Quelle: Wie links.
Tipp: Beginnen Sie in jeder Aufgabe mit dem einfachsten Datensatz und prüfen Sie bei Erfolg, ob der nächst schwierigere Datensatz auch „gelöst“ werden kann. Testen Sie ihr Programm ruhig immer wieder an einem der folgenden Datensätze.
Datensatz 3 (schwer, Beispiel mit echten Fotos):CMP Facade Dataset (weitere ähnliche Datensätze sind weiter unter auf der Seite verlinkt).
Wie weit kommen Sie hier?Es wird nicht erwartet, dass dieses Bild perfekt in seine Symmetrien — im Datensatz sind diese in jedem zweiten Bild angegeben — zerlegt wird. Dies ist eher als ein Benchmark für Ihren eigenen Algorithmus zu verstehen. Die Bilder wie angegeben automatisch zerlegen zu können ist sehr schwer, Lösungen dafür werden in fortgeschritteneren Vorlesungen präsentiert.
Aufgaben
Als erstes kümmern wir uns um eine geeignete GUI zur Visualisierung und — viel wichtiger — zum Debuggen. Sie können sich dabei an meinen Vorschlag halten (siehe Bild), oder aber sich etwas eigenes Überlegen.
Wir benötigen als erstes eine Möglichkeit Bilder einzulesen und anzuzeigen.
Zusätzlich benötigen wir eine Liste, in der wir häufig auftretende Teilbilder (a.k.a. Patches) auflisten.
Zuletzt benötigen wir auch ein Ausgabefeld, auf dem wir Vorkommen von Bildpatches visualisieren können.
Kümmern wir uns zuerst um den Basisalgorithmus. Konkret möchten wir erst einmal Bildpatches finden, um sie dann nach ihrem „Häufigkeit des Wiedervorkommens im Bild“ (in der Liste) sortieren zu können.
Ein guter Ansatz ist es, erst einmal kleine Teilbilder von \(w \times w\) Pixeln (mit z.B. \(w=4,5,6,...,64\) aus dem Bild zu extrahieren. (Rechteckige Teilbilder wären hierbei auch eine Möglichkeit, diese könnten zusätzlich auch „längliche“ Symmetrien erkennen.)
Eine Möglichkeit wäre, einfach alle Teilbilder des Ursprungsbild zu extrahieren. Dies sind jedoch viele. (Wie viele?)
Teilbilder eines Bildes direkt zu extrahieren und zu testen wie oft es im Bild vorkommt ist natürlich sehr zeitintensiv (erst recht mit Python). Im Prinzip testen wir damit nämlich alle Paare von Bildpatches aus. Daher verfolgen wir einen sehr ähnlichen Ansatz: Wir probieren zufällige Kandidaten aus und merken uns wie gut diese auf das gesamte Bild passen. Nachher möchten wir die \(n\) besten Kandidaten ausgeben lassen. So können wir den Algorithmus im Grunde jederzeit abbrechen und stets die zu diesem Zeitpunkt besten Funde ausgeben lassen. Wir sparen dann zwar keine Laufzeit um den besten Patch zu finden, finden jedoch schneller „mittel-gute“ Ergebnisse. Also entweder:
es werden so lange zufällige Bildpatches in die Liste eingefügt und ausgewertet bis der User einen "Stop"-Button klickt.
etwas abgeschwächter: ziehe nur \(m>n\) Kandidaten und wähle von diesen aus.
Bewertung der PatchesWir wissen schon einmal, dass alle Patches die wir aus Aufgabenteil 2 erhalten haben zumindest einmal im Bild vorkommen. Wir sind jedoch nur an solchen interessiert, die häufiger vorkommen. Diese guten Treffer wollen wir uns merken (die anderen können verworfen werden).
Ähnlichkeit von Patches Ein guter Treffer soll hier bedeuten, dass viele Pixel der „Patches“ mit einigen Teilen des Ursprungsbildes übereinstimmen. Konkret bedeutet das, dass für zwei \(k\times k\) Patches \(p\) und \(q\), zählen, wie nah die Patches pixelweise eigentlich liegen, \[
s_1(p,q) = \sum_{0 \le i,j \le k} (p_{ij} - q_{ij})^2,
\] wobei \(p_{ij}\) den \(j\)-ten Pixel in der \(i\)-ten Reihe bezeichnet. Eine andere Möglichkeit wäre zu testen wann die Summe der pixelweisen Produkte hoch ist, \[
s_2(p,q) = \sum_{0 \le i,j \le k} p_{ij} \cdot q_{ij}.
\] (Probieren sie ruhig beides aus, der Aufwand dazu ist sehr gering. Wie unterscheiden sich die Ergebnisse?)
Achtung Während \(s_1\) möglichst klein sein sollte, muss \(s_2\) möglichst groß sein, damit die beiden Patches \(p\) und \(q\) gleicher sind.
Welche Patches sind Interessant? Bleibt noch die Frage nach der Bewertung eines Patches aus — wie gut passt ein Patch auf ein Bild? Mit welchen Patches \(q\) sollen wir einen Kandidaten \(p\) mittels obiger Formel bewerten? Dazu können wir entweder davon ausgehen, dass das Bild bereits eine Symmetriegruppe enthält oder wir suchen nach beliebigen Symmetrien.
Methode 1 (Symmetriegruppe gegeben): Ersteres könnte wie folgt aussehen. Wir gehen davon aus, dass der Patch mehrmals im Bild vorkommt, wir möchten nur herausfinden welche Symmetrien dies sind. Dazu probieren wir verschiedene translatorische Generatoren aus und zählen dann wie viele Pixel des symmetrisch generierten Patchs mit dem Bild übereinstimmen (und summieren dabei auch die Scores \(s\) durch alle generierten Patches).
Sobald man die Translationen kennt, ist es nicht mehr so schwer, die angegebenen Objekte (hier Fassaden) zu erkennen. Wir bewerten hier also eher die Symmetrien selbst, als die Patches, letzteres bekommen wir dann nämlich Geschenkt. Warum ist das so?
Methode 2 (beliebige Symmetrien): Zufällige Paare von Patches durchzuprobieren und zu messen wie gut ein Patch auf das Bild passt wird leider zu langsam laufen. (Wie viele Paare von Patches der Größe \(k\) gibt es für ein quadratisches Bild mit einer Kantenlänge von \(w\) Pixeln?)
Statt also immer Paare von Patches durchzuprobieren falten wir den Patch mit dem Bild: Das heißt wir setzen den Patch in eine Ecke des Bildes und bestimmen die Ähnlichkeit des Patches zum darunter liegenden Bild (z.B. mit dem Score \(s\)). Danach verschieben wir den Patch horizontal um einen Pixel (sukzessive über das ganze Bild, also auch für die anderen Zeilen) und bestimmen wieder die Ähnlichkeit des Patches. Wenn wir nun die Pixel des Bildes so einfärben, dass höhere Ähnlichkeiten beispielsweise heller sind, können wir so direkt die Vorkommnisse des Patches im Bild visualisieren.
Am Ende Summieren wir die Ähnlichkeiten auf und definieren so die Gesamtähnlichkeit des Patches zum Bild als die aufsummierte Ähnlichkeit zu allen Bildteilen. (Wir suchen hier also allgemeinere Symmetrien im Bild, zum Beispiel Gesichter auf einem Gruppenfoto — alle ungefähr gleich groß, die Translationen sind jedoch nicht gleichmäßig und somit nicht Teil der Symmetriegruppe.)
Hinweis: Sie können sich gerne für eines der beiden Herangehensweisen entscheiden. Der Arbeitsaufwand ist ähnlich hoch, beide Verfahren werden jedoch unterschiedliche Arten von Patches finden. Sie können natürlich auch gerne beides implementieren. ;)
Tipp: Versuchen sie numpy zu verwenden, um die Ähnlichkeitsmaße der Patches zu implementieren. Dies ist sehr viel schneller.
Zuletzt müssen wir nur noch die Vorkommen der Top-\(k\) (\(k\) kann vom User gewählt werden) Patches im Bild mit der gleichen Farbe einfärben.
Überlegen Sie sich eine robustere Methode, die auch mit Fotos (etwas besser) funktioniert. Auch das Distanzmaß aus dem vierten Aufgabenteil hat noch einige Schwächen, wenn noch mehr Variabilität im Bild vorhanden ist. (Mit echten Fotos, etwa Datensatz 3 funktioniert das in der Regel nicht.)
Nutzen Sie als Daten hierzu etwa Beispiele aus Datensatz 3 (oder denken erzeugen Sie sich selbst ein geeignetes Beispiel aus, das nicht ganz so schwer ist).
Achtung Es geht nicht darum, das Problem zu lösen! Dies ist eine kreative Aufgabe — sie gilt als bearbeitet, wenn Sie einen anderen Ansatz vorstellen können, der etwas besser funktioniert. (Vorschläge dazu unten.)
Vorschläge:
Normalized Cross-Correlation NCC) ist deutlich robuster als das quadratische „SSD” Fehlermaß in Teil 2. Es ist nicht so schwer zu implementieren: Es seien \(p_{ij}\) der Farbwert an der Stelle \((x,y)\) im Bild-Patch (mit \(N\times N\) Pixeln) und \(q_{ij}\) entsprechend der Wert eines zweiten Patches. \[
\frac{1}{N^2}\sum_{0 \le i,j \le N} \frac{1}{σ_pσ_q} \left( p_{ij} - \overline{p} \right) \cdot \left( q_{ij} - \overline{q} \right),
\] \(\overline{p}\) bzw. \(\overline{q}\) bezeichnet den Mittelwert des Patches, \(σ_p\) bzw. \(σ_q\) die Standardabweichung.
Frage für den interessierten Leser: Was macht diese Funktion eigentlich bzw. warum ist dies besser als in Teilaufgabe 1 oder 2?
Es hilft auch, bei der Suche nach gleichen Stellen im Bild immer alle Gitterelemente gleichzeitig zu vergleichen; dadurch mitteln sich Fehler raus und man bekommt ein besseres Ergebnis. Das Ganze ist aber deutlich schwieriger zu implementieren.
Man extrahiert zunächst scharfe Kanten und vergleicht nur diese (statt alle Pixel im Bildausschnitt).
Außerdem merkt man sich nicht genau wo die Gradienten sich befinden (man mittelt über z.B. 8x8 Pixel) und auch nicht genau, in welche Richtung diese Zeigen (hier mittelt man Orientierungen in einem 45° Raster in jeder 8x8 Pixel Zelle). Dadurch werden Verformungen der Objekte ignoriert.
Wichtig: Für diese Übungsaufgabe ist es nicht nötig, ein solches schwieriges Verfahren zu implementieren. In Aufgabe 2.5 wird lediglich verlangt, ein wenig mit Ideen zu experimentieren, die das Verfahren robuster machen könnten, und über die Erfahrungen in der Übungsstunde zu berichten. Der Vollständigkeit halber trotzdem der Hinweis: Für diese HOG-Repräsentationen gibt es Python-Bibliotheken (z.B. OpenCV oder scikit-image).
